問題4-14 - TAKUYA’s CODE RECORDER

｢4.1.4 評価器をプログラムとして走らせる｣ということで、これまでに本文の中で登場してきた手続き達をコピペして、実際にevalを通せるようにしました。コピペなので動いて当然ですが、それでも今まで解読してきたことが実行されるのを確認できたということで、とても感動しました。
しかし、問題4-14のように、mapをprimitive-proceduresに登録して実行すると上手くいきません。その理由がわからず、2〜3日悩んでしまいました。以下のエントリーを参考にしても、なかなか腑に落ちない状況が続きましたが、何度もeval-applyに関わる手続きを読み返しているうちに、何とかわかったような気がする状態にまで持っていくことができました。

例えば、

(define (square x) (* x x))
(map square (list 1 2 3 4))

を実行してみた場合、mapを以下のように自前で定義しておけば、

(define (map proc items) 
  (if (null? items)
      '() 
      (cons (proc (car items)) 
            (map proc (cdr items)))))

実行結果は(1 4 9 16)となり、正しく動きます。しかし、mapをprimitiveとして登録してしまうと、以下のようなエラーが発生してしまいます。

map: expects type <procedure> as 1st argument, given: #0=(procedure (x) ((* x x)) (((square false true car cdr cons null? + - * / map list) #0# #f #t (primitive #<primitive:car>) (primitive #<primitive:cdr>) (primitive #<primitive:cons>) (primitive #<primitive:null?>) (primitive #<primitive:+>) (prim...; other arguments were: (1 2 3 4)

このエラーをなかなか解読することができませんでしたが、要するに('procedure (x) (* x x) env)がmapの第一引数に渡されているということになるのではと思いました。これは、make-procedureが実行された結果で、squareがevalされた時に、squareは(lambda (x) (* x x))で束縛されているので、これがevalされlambda?に引っかかって、make-procedureされたという流れになります。
それで、二つのmapの違いは何かということを考えてみると、それはmapがprimitive-procesure?かcompond-procedure?かということがわかります。primitiveの場合は、apply-primitive-procedureにprocedureであるmapと、argumentsである上記('procedure (x) (* x x) env)と(list 1 2 3 4)が渡されます。それで、mapの第一引数に('procedure ...)が作用されてエラーが発生してしまったと考えられます。
逆に、mapを事前に定義していた場合、mapがlambda式として束縛されます。そして、mapがevalされた時に、make-procedureが行なわれ、compond-procedure?に引っかかる形に変形されます。すると、eval-sequenceが実行されます。ここで、extend-environmentが行なわれ、mapの仮パラメータ(proc items)と、実際の引数である(square (list 1 2 3 4))が関連づけられます。eval-sequenceの実処理は、mapの本体を実行していくことになり、その中で利用されるmapの仮パラメータは、実パラメータに束縛されているので、procであるsquareがevalされる時は、lambda式に引数であるリストの各要素が渡された上で実行され、正しい答えが返ってくるということなるのではないかと思われます。
グダグダ書いた割には、まだまだ理解が曖昧な点が多々あります。しかし、昨日よりは理解を深めることができたということで、この問題には感謝しています。