ochalog

Ruby と MediaWiki が好きな電子・情報系の学生のブログ。

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 は手続きでないので作用させることができない