ゼミ第四回
「局所変数の導入」

四則演算が出来るだけでは、プログラミング言語というには貧弱ですよねー

ということで、今回は局所変数定義

let x = 式 in 式

を構文に追加します！
構文木には、今までの Number, Plus 等に加えて let 文と変数を加えます。

type expr_t = ...
                    | Variable of string
                    | Let of string * expr_t * expr_t

といった感じ。
例えば let x = 4 + 2 in x * 3 は
Let("x", Plus(Number 4, Number 2), Times(Variable"x", Number 3))
となります。これをインタープリタに渡すと 18 を返すようにしたいわけです。
そうするには、変数 x の値が何であるかを保持しておく必要があります。
そのために使うのが「環境(environment)」です。
環境というのは変数テーブルのことで、変数の値が何であるかを記録しておくものです。
ここでは環境を変数名( string 型)と値( value_t 型とする)のペアのリストで表すとします。

type env_t = (string * value_t) list

例えば環境が [("x", Number 3); ("y", Number 2), ("z", Bool true)] となっていれば、
変数 x の値が 3、y の値が 2、 z の値が true であり、その他の変数は未定義です。

============================================================
問題 1（相談、質問可）

変数と環境を受け取ったら、その値を返す関数 get を作れ。
例えば
get "y" [("x", Number 3); ("y", Number 2); ("z", Bool true)]
なら Number 2 が返る。

値が未定義の場合には
exception Unbound_variable of string
を raise するようにせよ。
例えば
get "a" [("x", Number 3); ("y", Number 2); ("z", Bool true)]
は Unbound_vairable "a" となる。
============================================================

get 関数ができあがれば、変数の値を環境から取って来られるようになります。
環境に新しい変数を加えるには、("a", Number 4)のような変数名と値のペアを
環境の先頭に :: で加えてやります。
さて、環境を使って let 文と変数を扱えるインタープリタを作ります。
上の let x = 4 + 2 in x * 3 を実行するにはどうすればいいでしょうか？
まず、変数 x の値を特定するために 4 + 2 を実行する必要があります。
結果が出たら、("x", Number 6)を環境に加えて、 x * 3 の実行に行きます。
x * 3 を実行しようとするとその中で x が出てきますが、x の値は環境に
入れておいたので、環境から get してくれば x の値を返すことができます。

============================================================
問題 2（質問、相談可）

expr_t 型の式と env_t 型の環境を受け取ってきたら、この環境のもとでこの
式を実行した結果を返す関数 eval を作れ。いくつかの入力に対して計算でき
ていることを確かめよ。

普通、この関数を実行するときには、空の環境 [] で呼び出します。これは、
最初は何も定義されている変数がないことを示しています。もし、最初からあ
らかじめ定義されている変数を使いたければ、最初に与える環境に

[("year", 2007)]

などと入れておけば、let 文で定義していなくても year + 3 などという式が
実行できるようになります。

問題 3（質問、相談可）

let x = 3 in let x = x * 2 in x * 2
let x = let x = 3 + 2 in x + 1 in x * 2

はいくつになるか。どの x がどの x と同じかを示せ。作ったインタプリタで
は、それはどのようになっているだろうか。

============================================================

なお、新しい項が増えるたびに lexer, parser も書き足して行く必要があります。
"let","x","in"等を読み込めるように、
新しいトークンを定義することはだいたい想像がつくと思います。
変数名には（他のトークンとかぶらず、数字ではない）任意の文字列を使うので、
lexer の下の方に
| lower (lower|upper|digit)*
    { VARIABLE(Lexing.lexeme lexbuf) }
と加えます。
こう書くと、"x" 等の文字列を VARIABLE というトークンとして読んでくれます。
NUMBER 等と見比べながら書くといいかもしれません。