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 ..." と書く。(注. ただし、代入文と let文は「似て非なる」ものである。その違いについては、この授業の終わり頃に各自考えてもらいたい。) なお、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つの環境が持つ変数の個数は上限がないため、長さの上限がないデータ構造である、リストを使って環境を表現することにする。

たとえば、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式などを実行して、変数が新しく値を持つようになるたびに呼ばれ、環境に含まれる情報を増やす役割を担う。 (ちなみに、今回作成する処理系では、環境に含まれる情報を「減らす」操作は必要ないので、そのような関数は用意しない。)

関数lookupは、環境env の中に、変数x があれば、それに対応する値を返すものである。なければ、例外を発生して処理を終了する。たとえば、

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

を実行すると BoolVal true が返るはずである。 lookup の定義の中で使われている ("unbound variable: " ^ x) という式は、文字列"unbound variable: " と、文字列型の変数xに格納されたデータを連接した文字列を返す。

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

課題 3-1.

上記で定義された環境を操作する関数を使って、 [("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 の定義を理解し、「新しく環境に定義された変数と値のペア」が、環境の先頭に追加されるか、末尾に追加されるか考えなさい。このことと前問の結果から、ある変数に対して異なる値を続けて、環境に登録すると、古い値が生き残るか、新しい値が生き残るか、どちらであるか考えなさい。

トップ, 前へ, 次へ.

亀山幸義