問題4-21

問題4-18〜20は深追いしませんでしたが、感じたことを一応メモしておきます。
問題4-18については、別名の束縛変数に元々のdefine式の本体を放り込んで、その後にset!で投入するという方法のようですが、これだとsolveのdyの本体をbに束縛する時、その中でyを使っていますが、この時点ではyは'*unassigned*ですので、正しく動かないのではと思いました。
問題4-19での三人の討論については、論理的には内部定義は同時と見なすことが正しいが、実装上それは難しいということで、注釈26を読みながら、ぼんやりと理解することができました。
問題4-20は、'*unassigned*した後にset!するという手間を省くためのletrecが紹介されています。上手くやれば正しく動く変換ロジックを組めそうですが、今回は飛ばしました。
そして、問題4-21です。lambdaばっかりがでてくる手続きが何を意味しているのか、最初はさっぱりわかりませんでしたが、注意深く解読していくと、確かにこれで動きそうだと理解することができました。手続き名を一切使っていないのに、再帰的なロジックを組めるという事実は驚きでした。

((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)
;=>3628800

二つ目のlambdaの引数であるfactには、三つ目のlambda式が渡されます。三つ目のlambda式の引数は二つである点が重要で、二つ目のlambdaの本体で(fact fact n)とやっているということは、三つ目のlambda式の第一引数には、自分自身が渡されるということになります。だから、三つ目のlambda式の第二引数を調節していきながら、計算処理を再帰的に進めていくことができます。Fibonacci数の計算を上記のように表現するなら、以下のようになります。

((lambda (n)
   ((lambda (fib)
      (fib fib n))
    (lambda (fib k)
      (cond ((= k 0) 0)
            ((= k 1) 1)
            (else (+ (fib fib (- k 1))
                     (fib fib (- k 2))))))))
 10)
;=>55

また、偶奇判断ロジックは、以下のように書くことができます。二つ以上の手続きを扱うことも可能だということを実感することができました。

(define (f x)
  ((lambda (even? odd?)
     (even? even? odd? x))
   (lambda (ev? od? n)
     (if (= n 0) #t (od? ev? od? (- n 1))))
   (lambda (ev? od? n)
     (if (= n 0) #f (ev? ev? od? (- n 1))))))

(f 10) ;=>#t
(f 11) ;=>#f

この問題を解きながら、たまたま昨日再読したdankogaiさんの｢TuringとChurchの狭間で｣というエントリーに書かれてあることへの理解を少しだけ深めることができたのも、今日の収穫の一つだったような気がしています。