第5回

課題1

クロージャの定義をClosure =((関数の名前, ) 変数, 関数本体, 環境) としている人へ

関数本体を「式」型を表す expr で表す必要がありますが、Closure は「値」型の value のバリアント型のひとつに付け加える必要が出てくるかと思います。

しかし、すでにexpr型はvalue型を用いて定義されているため、このような仕様にしてしまうとさらにその上value型をexpr型で定義することになってしまい、

ちょうど型を相互再帰する形になると思います。

さらには、環境にも同様の問題が生じるかと思います。

そこで、以下のような形で「型の相互再帰的定義」ができるようなので参考にしてください。どうもレジュメに載ってないようなので。

   1 type expr = 
   2 (* expr型の定義 *)
   3 and value = 
   4 (* value型の定義：
   5 ここで例えばクロージャを
   6 Closure of string * string * expr * env
   7 などとする。
   8 *)
   9 and env =
  10 (* 環境の定義：
  11 環境をモジュール module Env = ... で実装している人は
  12 環境の定義において value が使われている箇所（例えば add : string -> value -> t -> t を add : string -> 'a -> t -> t と定義しておく）をとりあえず型パラメタでおいて定義してから
  13 env = value Env.t
  14 と定義するとできます（できました）。
  15 *);;

もし同じところで詰まってたら参考にしてください。-- TakuyaKuwahara

関数適用の右結合癖が治らない人へ

おそらく大半の人が、関数適用を文法規則「expr -> expr expr」によって実装しているかと思います。（レジュメの例と同じ） この時に生じがちな問題について。

例えば、次のような関数

   1 let f = (fun x -> (fun y -> x+y));;

を定義したとします。（ただの加算です）

これに対し、普通に関数適用式を書くなら

   1 f 1 2;;

となりますが、このとき評価エラーが生じてしまうことがあります。（生じなかったら多分この項読む意味ないです）

これはパーサが構文を

   1 (f (1 2));;

と誤って解析してしまうことによります。

対策は次の２つ。

1.「左結合」を明示する（情報源：IS2009wiki）

レジュメのUMINUSの様に、関数の左結合則を明示するためのダミーのトークンFUNCを

   1 %token FUNC
   2 %token (*
   3 ...
   4 その他のトークンの定義
   5 ...
   6 *)
   7 %token INT BOOL
   8 
   9 %left ADD (*
  10 ...
  11 優先度の指定
  12 ...
  13 *)
  14 %left FUNC

と定義します。このときFUNCには最も優先度の高い左結合を設定してください。

次に関数適用の規則に

   1 expr expr %prec FUNC {(* ... *)}

で優先度をFUNCに従うようにします。これで、関数適用には最も優先度の高い左結合則が割り当てられます。

2.VAL, INT, BOOL の還元タイミングを早める

上の優先度設定を行っただけで、うまくいく人はうまく行きます。

そうでない--俺のような--人は、おそらくINT, BOOL, VAL（VALは変数型）がそれだけで記号exprに還元されるタイミングが遅く、それゆえに

(1) [スタック: (empty) ] <- [入力:f 1 2]

(2) [スタック: f:VAL ] <- [入力:1 2]

(3) [スタック: f:VAL,1:INT, ] <- [入力:2]

(4) [スタック: f:VAL,1:INT,2:INT ] <- [入力:(empty)]

(5) [スタック: f:VAL,1:INT,2:expr ] <- [入力:(empty)]

(6) [スタック: f:VAL,1:expr,2:expr ] <- [入力:(empty)]

(7) [スタック: f:VAL,(1 2):expr] <- [入力:(empty)]

(8) [スタック: f:VAL,1:INT,2:INT ] <- [入力:(empty)]

(9) [スタック: (f (1 2)):expr] <- [入力:(empty)]

のように構文解析が進んでしまう可能性が高いそうです。（説明のアイデアはNaoaki Iwakiriさんより。もしかしたらもっと別の理由かもしれません。情報求む。）

このように構文解析が進んでしまうと、結合則云々よりも適用可能な文法規則の制約から文の解釈が「(f (1 2))」に決まってしまいます。

(追記:シフト(shift)と還元(reduce)のどちらの状態遷移も考えられるような状況を「shift/reduce conflict」といい、基本的にはshiftが優先されるそうなので、上のような構文解析がなされてしまうと解釈できます。この衝突(conflict)はよろしくない状態のようなので、なるべく消したほうがいいそうです。（第4回レジュメ参照）)

これを防ぐには、先の結合規則の部分に

   1 %left ADD (*
   2 ...
   3 優先度の指定
   4 ...
   5 *)
   6 %nonassoc INT BOOL VAL
   7 %left FUNC

を追加してみてください。これで還元のタイミングが「スタックに積まれた直後」になり、

(1) [スタック: (empty) ] <- [入力:f 1 2]

(2) [スタック: f:VAL ] <- [入力:1 2]

(3) [スタック: f:expr ] <- [入力:1 2]

(4) [スタック: f:expr,1:VAL ] <- [入力:2]

(5) [スタック: f:expr,1:expr ] <- [入力:2]

(6) [スタック: (f 1):expr ] <- [入力:2]

(7) [スタック: (f 1):VAL,2:VAL] <- [入力:(empty)]

(8) [スタック: (f 1):expr,2:expr ] <- [入力:(empty)]

(9) [スタック: ((f 1) 2):expr] <- [入力:(empty)]

のように構文解析が進み、うまくいくはずです。

（注意:ホントに優先度設定の時点で下の方に書けば還元のタイミングが早められるんだろうかとか、そもそも構文解析の進行は上の（要は言語処理系論第四回で習った）方法で行われてるのかとかいろいろ疑問が残りますが、そう解釈すると上のようにスパッと説明が付くので一応書いときます っていうかみんな動けばそこまで深いこと気にしないよね 。）-- TakuyaKuwahara

関数の多変数化について

関数は「let VAL VAL = expr」のような文法で実装すると当然1変数にしか対応できません。変数に対応するIdentiferがたった一つなので当たり前です。 ただ、これがレジュメに（例）として載ってる以上、コレで実装できれば十分な気もします（保証はしませんよ？）

多変数対応にするには、例えば筆者は

   1     |LET VAL arg EQUAL expr IN expr {(* hogehoge *)}
   2 
   3 (* hugahuga *)
   4 
   5     |expr expr %prec FUNC {(* hogehoge *)}
   6 ;
   7 
   8 arg:
   9     |VAL arg         {(*   1   *)}
  10     |VAL             {(*   2   *)}

と「変数部分」を表す非終端記号argを導入しました。

あとは(* 1 *) (* 2 *)を実装するだけですが、これは

   1 let f x y z = e;;

が

   1 f = (Closure x (Closure y (Closure z (e))))
   2 (* Closureはクロージャの型 *)

と解釈されればいいので、argが「構文木exprを受け取って変数VをもつクロージャClosure(V, e)のeの部分に代入する関数」を返すようにすれば、上のような階層的に連なって最終的に関数本体がそれらの変数で拡張された環境でもって評価されるような構造を作ることができます。-- TakuyaKuwahara

Categoryノート