3-1. 変数と let の処理 (環境の話)

let とは何であろうか？足し算やif は、C言語などにも同じものがある。しかし、let という式は、他の言語では、あまり見られない。数学の教科書などで、定義や説明の冒頭で、「x を 3とせよ。そうすると。。。」という表現をするときがあるが、「x を 3 とせよ。」という部分の英語が、"Let x be 3." である。つまり、let というのは変数に値を割り当て、それ以降で使えるようにする機能がある。

ML や Lispなどの関数型言語では let は、非常によく使われる。なぜなら、(純粋な)関数型言語には、C言語の代入文 "x = x + 1;" のようなものはないからである。そのかわりに "let x=1 in ..." と書く。(もっとも両者の意味は、非常にデリケートな部分で異なる。そして、その違いが「本当にわかる」と関数型言語の本質がわかったことになる。) なお、OCaml では、in以下を書かないこともある。その場合、「これ以降ずっと(次に、他の let文で x の値を決めるまでは) x を 1 にする。」という意味である。

なんだ、単に「変数x をある値にして、それ以降の式を評価する」という意味か、簡単じゃないか、と思った人は、素晴しい。いや、正確にいうと、そそっかしい。実は、eval2 が扱う対象言語には、まだ、変数すら含まれていなかったのである。そう、let式をいれるために、初めて、変数のきちんとした処理が必要になる。このためには、今回のインタープリタの主役である「環境」を使う。

環境 (environment)

近頃は、新聞などをみても、地球環境という言葉がしょっちゅうでてきて、環境という言葉は日常的な言葉になってきた。プログラム言語の世界で環境といえば、「それぞれの変数がどういう値をもっているか」という情報のことである。x+1という式は、 x が 3 のときは 4 になり、x が 10のときは 11になる、という具合いに、 x の持つ値によって x+1という式の値は変わってくる。つまり、環境によって、プログラムの意味がかわってくるのである。

ここで必要となる環境は、「変数x,y,z,... が、それぞれ、 1, true, 13,...という値をもつ」といった情報を1つにまとめたデータである。ここで、1つの環境が含む変数の個数は上限がない。そこで、OCamlのリストを使って環境を表現することにする。

たとえば、x=1, y=true, z=5 という環境を、

[("x",IntVal 1); ("y",BoolVal true); ("z", IntVal 5)]

というリストで表現する。コンマ (,) やセミコロン (;) がまじっていて、ちょっとわかりにくいと思うが、("x",IntVal 1) というのは、x という変数と 1という値をペアにしたものであり、そのような表現が 3つ続いてできたリストが上の環境である。セミコロンはリストの要素の区切りであり、コンマはペアの区切りである。リストとペアは間違えやすいので、この機会に確認してほしい。

なお、上記のペアの部分をリストで表現することはできない。なぜなら、リストは同じ型の要素を並べたものであるが、たとえば、"x" は string型で (IntVal 1) は value型なので、 ["x"; IntValu 1] というリストは作れないのである。

逆に、リストの部分をペアや組を使って表現することはできない。上記の例だけであれば、

(("x",IntVal 1), ("y",BoolVal true), ("z", IntVal 5))

という 3つ組を作ることは可能だし、型もつくのであるが、 x=1, y=true, z=5 という環境に、更に w=10 という情報を追加した環境:

(("x",IntVal 1), ("y",BoolVal true), ("z", IntVal 5), ("w", IntVal 10))

も、上記の3つ組と同じ型をもってくれないと、インタープリタを作成しようがなくなるので、(「環境」の型が1つに決まらない) 上記のリストを、ペアや組で表すことはできないのである。

また、今のところ、ペアたちを並べる順番には意味がないので、

[("z",IntVal 5); ("y",BoolVal true); ("x", IntVal 1)]

という環境も、上の環境と実質的に同じものを表している。さらに、空リスト:

[]

も環境の一種であり、これは、「まだ、どの変数も値をもっていない環境」である。プログラム中で、変数に値を持たせる前は、どの変数も値をもっていないので、そのような「最初の時点の環境」は空リストに対応する。(はずだが、実際の OCaml の処理系では、立ち上げると、最初から自動的にたくさんの定義を読みこむので、ユーザが使う時点では、空の環境ではない。) これから皆さんが作成する処理系では、最初の時点では空リストで表現される環境になる。

さて、環境を扱う関数群を定義しよう。

let emptyenv () = []

let ext env x v = (x,v) :: env

let rec lookup x env =
   match env with
     [] -> failwith ("unbound variable: " ^ x)
   | (y,v)::tl -> if x=y then v 
                  else lookup x tl

最初の emptyenv という関数は、無意味な引数 ()を1つ受けとり、いつでも空リスト []を返すものであり、要するに、「空っぽの環境」を作るためのものである。こんな関数をわざわざ作らなくても、「空っぽの環境」を表すためには、いつでも []を使えばいいのだからちょっと無駄なことをしているのだが、このようにしておくと、あとで、環境の表現方法を変更するときに都合がよいので、ちょっとまわりくどい定義をしている。

次の extという関数は、環境の拡張 (extension) を行う関数であり、たとえば、env1を [("y",BoolVal true); ("z", IntVal 5)]という環境とすると、そこに新たに「変数"x"は 1という値を持っている」という情報を追加した環境 [("x",IntVal 1); ("y",BoolVal true); ("z", IntVal 5)] を作るためには、 (ext env1 "x" (IntVal 1)) とすればよい。関数ext は、let式などを実行して、変数が新しく値を持つようになるたびに呼ばれ、環境に含まれる情報を増やす役割を担う。(ちなみに、今回作成するインタープリタでは、環境に含まれる情報を「減らす」関数は必要ない。)

最後の関数は、環境のルックアップ(look up)と呼ばれる仕事をする。環境env の中に、x であらわされる変数があれば、それに対応する値を返すものである。なければ、例外を発生して処理を終了する。たとえば、

lookup "y" [("x",IntVal 1); ("y",BoolVal true); ("z", IntVal 5)]

を実行すると BoolVal true が返るはずである。

ところで、特に気にしてこなかったが、環境にも型がつかなければいけない。その型は、(string * value) list というものであり、これは、文字列(変数名を表す)と値のペアが、リスト状に並んでいるものの型である。

課題 6.

上記で定義された環境を操作する関数を使って、 [("x",IntVal 1); ("y",BoolVal true); ("z", IntVal 5)] という環境を作りなさい。
この環境に "y" という変数が登録されているかどうか、 lookup関数で調べなさい。同様に "w" という変数が登録されているか調べなさい。
1つの環境の中に同じ変数が2回以上あらわれると、 lookupのときに、どちらの値が使われるか、考えなさい。たとえば、 [("x",IntVal 1); ("y",BoolVal true); ("x", IntVal 5)] に対して、変数"x" に対応する値を lookup してみよ。
関数ext の定義を理解し、「新しく環境に定義された変数と値のペア」が、環境の先頭に追加されるか、末尾に追加されるか考えなさい。このことと前問の結果から、ある変数に対して異なる値を続けて、環境に登録すると、古い値が生き残るか、新しい値が生き残るか、どちらであるか考えなさい。

トップ, 前へ, 次へ.

亀山幸義