##master-page:NoteTemplate
#format wiki
#language ja
= 第5回 =

== 課題1 ==

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

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

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

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

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

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

{{{#!highlight ocaml
type expr = 
(* expr型の定義 *)
and value = 
(* value型の定義：
ここで例えばクロージャを
Closure of string * string * expr * env
などとする。
*)
and env =
(* 環境の定義：
環境をモジュール module Env = ... で実装している人は
環境の定義において value が使われている箇所（例えば add : string -> value -> t -> t を add : string -> 'a -> t -> t と定義しておく）をとりあえず型パラメタでおいて定義してから
env = value Env.t
と定義するとできます（できました）。
*);;
}}}

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


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

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

例えば、次のような関数

{{{#!highlight ocaml
let f = (fun x -> (fun y -> x+y));;
}}}

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

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

{{{#!highlight ocaml
f 1 2;;
}}}

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

これはパーサが構文を

{{{#!highlight ocaml
(f (1 2));;
}}}

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

対策は次の２つ。

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

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

{{{#!highlight ocaml
%token FUNC
%token (*
...
その他のトークンの定義
...
*)
%token INT BOOL

%left ADD (*
...
優先度の指定
...
*)
%left FUNC

}}}

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

次に関数適用の規則に

{{{#!highlight ocaml
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回レジュメ参照）)


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

{{{#!highlight ocaml
%left ADD (*
...
優先度の指定
...
*)
%nonassoc INT BOOL VAL
%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がたった一つなので当たり前です。
ただ、これがレジュメに（例）として載ってる以上、コレで実装できれば十分な気もします（保証はしませんよ？）

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

{{{#!highlight ocaml

    |LET VAL arg EQUAL expr IN expr {(* hogehoge *)}

(* hugahuga *)

    |expr expr %prec FUNC {(* hogehoge *)}
;

arg:
    |VAL arg         {(*   1   *)}
    |VAL             {(*   2   *)}
}}}

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

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

{{{#!highlight ocaml
let f x y z = e;;
}}}

が

{{{#!highlight ocaml
f = (Closure x (Closure y (Closure z (e))))
(* Closureはクロージャの型 *)
}}}

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

----
[[Categoryノート]]