5-1. 束縛の話

さて、いよいよ、関数の処理である。 OCaml でいえば、(fun x -> e) の形の式(関数を作る式) と、(e1 e2) の形の式(関数を引数に適用する式) の処理である。前者は、「ラムダ計算」という形式的体系では、「λx.e」と表現され、「λ抽象」とか「関数抽象 (function abstraction)」と呼ばれる。後者は、「関数適用 (function application)」あるいは、省略して「適用」と呼ばれる。

これらをどう処理すればよいだろうか？まず、明らかなことは、「関数を評価した結果は、関数がそのまま返ってくる」ということである。たとえば、(fun x -> 1 + 1) という式を OCaml で評価しても、(1+1)は計算されず、「関数」が計算結果である。(OCaml は関数の中身をプリントしないので、計算が進んだのかどうかわからないかもしれないが、実際は、関数の中身に計算できる部分があっても、計算はしない。たとえば、(fun x -> 1 / 0 ) のような式を評価しても、 (1/0）というエラーが起きないことから、「関数に引数を与えるまでは、関数の中身を計算しない」ことがわかる。

結局のところ、計算の結果、つまり、「値」の世界に「関数」をいれる必要がある。

(* 値の型 *)
type value = 
  | IntVal  of int        
  | BoolVal of bool       
  | FunVal  of string * exp

たとえば、(fun x -> 1) という式は、exp型の式としては Fun ("x", IntLit 1) と表現するが、 value型の式としては、 FunVal ("x", IntLit 1) と表現することになる。

しかし、これだけで良いだろうか？実は、もう少し考えないといけないことがある。問題点を理解するために、普通の OCaml プログラムで、以下のものを考えよう。

let x = 1 in
  let f = fun y -> x + y in
    let x = 2 in
      f (x + 3)

頭の中で、このプログラムを実行して、答えを予測してみよう。

問題となるのは、変数 x の値が、一番外側でセットされた 1 であるのか、内側の 2 であるのか、という点である。まず、一番下の行の (x + 3) における x は、2 である。これは問題がない。問題があるのは、関数 f の本体 x + y に含まれる x であり、これが 1 なのか 2 なのかである。これが 1 であれば、上記の実行結果は 1 + (2 + 3) = 6 となり、これが 2 であれば、上記の実行結果は 2 + (2 + 3) = 7 となる。

実は、結果は 6 である。つまり、前者が正しい。ここまでは、おそらく、多くの人の予想通りだろうが、その理由を正しく言えるだろうか？

問題 (提出課題ではない)

上記の OCamlプログラムの実行過程を理解し、なぜ 6 が返るか言葉で説明せよ。

let x = 1 のように、プログラム中の変数に値を対応付けることを「束縛 (binding)」と呼ぶ。たとえば、let x = 1 in x + 1 というプログラムにおける x は let x = 1 という部分で「束縛」される。逆に、let y = 2 in (let x = 1 in x + 2) + 3 というプログラムでは、内側の let が変数 xを束縛している範囲は、 x + 2 の部分である。このように、束縛している方から見て、その束縛が有効な部分を「スコープ (scope)」と言う。

プログラム中の変数への束縛がどのように行われるか、というのは、古くからプログラム言語の意味に関して検討されてきている重要なテーマであり、基本的な束縛の方式は以下の2つである。

静的束縛 (lexical binding あるいは static binding); 束縛関係(スコープがどこになるか)は、プログラムを書いた時に決まる。 OCaml や C言語をはじめ、現代のほとんどのプログラム言語が採用している方式である。
動的束縛 (dynamic binding): 束縛関係(スコープがどこになるか)は、プログラムが実行される時に決まる。昔の Lisp言語などで使われたが、現在では emacs-lisp (Emacs を記述する Lispもどきの言語)など一部のプログラム言語のみで使われている。

なお、現代のプログラム言語の中には、静的束縛を基本としつつも、動的束縛を実現するための特殊な構文を用意しているものもある。

言葉だけではわかりにくいので、以下のプログラムをもう一度取りあげよう。

let x = 1 in
  let f = fun y -> x + y in
    let x = 2 in
      f (x + 3)

静的束縛では、プログラムを書いた時に、スコープが決定される。つまり、外側の let x = 1 in のスコープは、それ以降全部であり、内側の let x = 2 in のスコープは、f (x + 3) である。スコープが重なっている部分では、内側の束縛が勝つので、一番下の行の x は 2である。一方、関数 f の定義の中にある x は、外側のスコープにのみはいっているので、その値は 1 であり、OCaml での計算結果 6 が導かれる。

一方、上記のプログラムを動的束縛の言語で実行したらどうなるだろう？動的束縛では、スコープは、最初から決まるのではなく、実行時に決まる。すなわち、以下のように実行される。

プログラム全体を、空の束縛のもとで実行する。
x = 1 という束縛を有効にして、2行目以下のプログラムをこの束縛のスコープとする。
f = fun y -> x + y という束縛を有効にして、3行目以下のプログラムをこの束縛のスコープとする。
x = 2 という束縛を有効にして、4行目のプログラムをこの束縛のスコープとする。
f (x + 3) を実行する。つまり、(fun y->x+y) 5 を実行する。
y = 5 という束縛を有効にして、(x + 3) をこの束縛のスコープとする。
ここで (x+y) を実行する際に、このプログラムを含むスコープをもっているのは、x=1 と x = 2 の2つであり、x=2 の方が新しいので、こちらが採用され、結局 2+5 = 7 となる。

言葉で書くとややこしいが、動的束縛というのは、プログラムの中での配置とは関係なく、実行順序により、束縛関係が生きてくるものである。

課題 5-1.

上記のことを念頭において、次のプログラムを静的束縛および動的束縛のもとで，手で実行して、計算結果を導いてみよう。 (計算の過程をレポートに記しなさい．)
```
let x = 10 in
  let f = fun y -> x + y in
    let y = f x in 
     let x = 20 in 
       f (x * y)
```

トップ, 前へ, 次へ.

亀山幸義