突発簡単チュートリアル１：代入(substitution)と環境(environment)

「ブログの内容がないよー」と怒られてしまったので、反省してチュートリアルもどきを始めてみる。

let pi = 3.14 in pi *. 10. *. 10.

みたいな、変数定義のある式を考えます。上のプログラムは(.が多いことからもわかるように:-)OCamlですが、HaskellでもSchemeでもStandard MLでもOKです。

このような式の値を計算するには、主に二通りの方法があります。

piを3.14で置換(substitute)してから、"in"以降の式を計算する。
「piは3.14である」という情報を記憶しつつ、"in"以降の式を計算し、piという変数が出てきたら、値として3.14を用いる。この「変数の値が何か」という情報を記憶する写像のことを環境(environment)といいます。

前者の方法は、「環境」などという余計な構造を導入しなくてよいので、（すごく大ざっぱな言い方ですが）λ計算とかの定義で良く用いられます。しかし、前者の方法だと

let x = e1 in e2

という式を計算するのに

という手間が個々のletごとにかかるので、

let x1 = e1 in
let x2 = e2 in
...
let xn = en in
e

みたいな式を計算するのに、nの2乗ぐらいのオーダーで時間がかかってしまいます（言語によってはそれ以上）。「じゃあ実装を工夫すれば…」と思うわけですが、それが後者の方法です。

ところで、日本語では、上のような「置換」のことを「代入」と言います。英語ではsubstitutionなのですが…。Cなど命令型言語の代入(assignment)とは別個の単語です。

…って簡単すぎてアホらしいですか。そうですか。;_;