SICP: Exercise 1.34

「1.3.2 lambda を使う手続きの構築」でついに無名関数 lambda が出てきた。先に JavaScript で見慣れていたから驚きは少なかったけれど、他の言語でプログラミングを始めていたら大きく驚いたかも（とはいえ、例えば C 言語でも関数ポインタとかあるしなぁ…）。だんだん関数型プログラミングらしくなっていく。

あと、局所変数束縛の特殊形式 let も出てきた。

(let ((var1 exp1)
      (var2 exp2)
       ...
      (varn expn))
  body)

は

((lambda (var1 var2 ... varn)
   body)
  exp1
  exp2
  ...
  expn)

のシンタックスシュガー。「変数の値は let の外側で計算される」ということは覚えておいた方がよさそう。

というわけで問題。

問題 1.34

手続き

(define (f g)
  (g 2))

を定義したとする。その時

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

解釈系に組合せ (f f) を（意地悪く）評価させるとどうなるか。説明せよ。

「計算機プログラムの構造と解釈 第二版 1.3.2 lambda を使う手続きの構築」より

置換モデルで少しずつ還元していく。ややこしいので「1.1.5 手続き作用の置換えモデル」の手順で一歩ずつ。

(f f)
(g 2) ; g：仮引数
(f 2) ; 仮引数 g -> f
(g 2) ; g：仮引数
(2 2) ; 仮引数 g -> 2
; エラー
; 2 は手続きでないので作用させることができない