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.


トップ, 前へ, 次へ.

亀山幸義