multirember&coをトレースしてみる

The Little Schemer

fact/cpsでやった要領で、multirember&coもトレースしてみる。
っていうか、今からやるようなことはちゃんと本でやってますね。
継続渡しがわかんねワカンネ言ってましたが、継続渡しが分からないんじゃなくて英語が読めてないだけでした。
僕くらい脳みそがすっとこどっこいだと、The Little Schemerくらいの英語にもつまづいてしまうのですよ、と。
...ってか、この本に何ヶ月かけるつもりだよ、僕チンは。

さて、では前にも書いたけどmultirember&co関数の定義をば。

(define multirember&co
  (lambda (a lat col)
    (cond
      ((null? lat) (col (quote ()) (quote ())))
      ((eq? (car lat) a) (multirember&co a (cdr lat)
                                         (lambda (newlat seen)
                                           (col newlat (cons (car lat) seen)))))
      (else (multirember&co a (cdr lat)
                            (lambda (newlat seen)
                              (col (cons (car lat) newlat) seen)))))))

で、一番最初に渡す継続は

(define a-friend
  (lambda (x y)
    (null? y)))

だそうです。なんでこんな名前なのかよう分からんのですが。
っていうか、これも名前付ける必要はないんだろうな。本では名前付けてるけど。
こんな関数でもって、

(multirember&co 'tuna '(and tuna) a-friend)

の評価過程を見ていきしょう。

(multirember&co 'tuna '(and tuna) a-friend)
	-> (multirember&co 'tuna '(tuna) cont1)
		-> (multirember&co 'tuna '() cont2)
		-> (cont2 '() '())
	-> (cont1 '() '(tuna))

    

  • > (a-friend '(and) '(tuna))
    • 

  • >#f
    •

と、こんな感じでしょうか。ただし、cont1とcont2は以下のような関数です。

(define cont1
  (lambda (newlat seen)
    (a-friend (cons (car lat) newlat) seen)))
    
(define cont2
  (lambda (newlat seen)
    (cont1 newlat (cons (car lat) seen))))

で、ここで皆さんもお気づきでしょうが、cont1とcont2の定義内で使用されているlatが未定義ですね。
Schemeでは「未定義」っていうのかな。「unbound」だから未束縛？

さて、このやり方もあっけなく破綻したわけですね。
クロージャだからlatにも問題なく触れるのか...。


多くの手続き言語では関数に名前を付けずに定義することができませんよね。
できても、関数を値として扱うという考え方が一般的でないため、無名関数だのクロージャだのは手続きな人にとってはマイナーな概念です。
なので、そういう文化に慣れた僕は関数に名前を付けないと、少し不安な気持ちになってしまうのですよ。
これは慣れるしかないか。

この先Yコンビネータの話しも出てくるから、名前付けないと分かんない、なんて言ってられないよな...。