あれから The Little Schemer の第八章を何度か読み直している。特に後半の継続のところはわからないのでわかるまで読もうと思って今日も読んだ。読んだだけではわからないので模写したり自分でもっと単純そうなのを書いたりした。いま、動作の仕組みがわかった気がするので試しに書いておく。
まず occur という関数を考える。アトムとリストを受け取り、リストの中にアトムが何回出現したか数える。
(define occur (lambda (a lat) (cond ((null? lat) 0) ((eq? (car lat) a) (+ 1 (occur a (cdr lat)))) (else (occur a (cdr lat))))))
普通に再帰している。ちなみに俺は再帰を「オシリに数珠つなぎ」というイメージでとらえられるようになってから再帰関数の読み書きが少しだけイメージしやすくなった。再帰している箇所、つまり自分自身を呼び出してる箇所を丸ごと (+ 1 ...) とかで置き換えてしまう。すると結局残る計算は (+ 1 (+ 1 (+ 1 0))) のようになり、 occur という名前は消えてしまうので安心できる。 + じゃなくて cons のほうがより「オシリに数珠つなぎ」モデルでイメージしやすい。 (cons 'bacon (cons 'and (cons 'tuna (cons 'potato '())))) みたいなの。 cons は必然的にこういう形を作る。
で、継続だ。 The Little Schemer の例題で三つほどでてきたがどれも同じようなパターンなのでそれらに共通した部分を拝借してもっと単純な occur&co を考える。アトムとリストと手続きを受け取り、アトムの出現回数と、アトムが出現するたびにそれをコンスしたリスト（特に集める意味はない）の二つを計算する。
(define occur&co (lambda (a lat col) (cond ((null? lat) (col 0 (quote ()))) ((eq? (car lat) a) (occur&co a (cdr lat) (lambda (num newlat) (col (+ 1 num) (cons (car lat) newlat))))) (else (occur&co a (cdr lat) (lambda (num newlat) (col num newlat)))))))
これはちゃんと動く。動くんだけど、どういう仕組みで動いてるのか、再帰の「オシリに数珠つなぎ」モデルのときのように「最終的にどういう計算の形になっているか」がイメージできなくて悩んだ。
gosh> (occur&co 'tuna '(bacon and tuna potato) (lambda (num newlat) (list num newlat))) (1 (tuna))
The Little Schemer の最初のほうの何章かにならって occur&co が具体的にどういう引数で呼ばれてどう実行されていくかを展開してみると、要するに occur&co が再帰するたびに lat が一要素ずつ減り、それと同時に col がどんどん lambda で囲われていくのだ、ということがわかった。これを「タマネギの皮むき逆再生」モデルと名付けた。
(occur&co 'tuna '(bacon and tuna potato) (lambda (n l) (list n l)) ) ; 最初の呼び出し ~~~~~~~~~~~~~~~~~~~~~~~~~(col1) ; lat == '(bacon and tuna potato) ; (eq? (car lat) a) => #f (occur&co 'tuna (and tuna potato) (lambda (num newlat) (col num newlat))) ; col 展開前 (occur&co 'tuna (and tuna potato) (lambda (num newlat) (col1 num newlat))) ; col == 直前の呼び出し時に渡された手続き == col1 (occur&co 'tuna (and tuna potato) (lambda (num newlat) ((lambda (n l) (list n l)) num newlat)) ) ; col1 展開後 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(col2) ; lat == '(and tuna potato) ; (eq (car lat) a) => #f (occur&co 'tuna '(tuna potato) (lambda (num newlat) (col num newlat))) ; col 展開前 (occur&co 'tuna '(tuna potato) (lambda (num newlat) (col2 num newlat))) ; col == 直前の呼び出し時に渡された手続き == col2 (occur&co 'tuna '(tuna potato) (lambda (num newlat) ((lambda (num newlat) ((lambda (n l) (list n l)) num newlat)) num newlat)) ) ; col2 展開後 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(col3) ; lat == '(tuna potato) ; (eq? (car lat) a) => #t (occur&co 'tuna '(potato) (lambda (num newlat) (col (+ 1 num) (cons (car lat) newlat)))) ; col 展開前 (occur&co 'tuna '(potato) (lambda (num newlat) (col3 (+ 1 num) (cons (car lat) newlat)))) ; col == 直前の呼び出し時に渡された手続き == col3 (occur&co 'tuna '(potato) (lambda (num newlat) ((lambda (num newlat) ((lambda (num newlat) ((lambda (n l) (list n l)) num newlat)) num newlat)) (+ 1 num) (cons (car lat) newlat))) ) ; col3 展開後 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(col4) ; lat == '(potato) ; (eq? (car lat) a) => #f (occur&co 'tuna '() (lambda (num newlat) (col num newlat))) ; col 展開前 (occur&co 'tuna '() (lambda (num newlat) (col4 num newlat))) ; col == 直前の呼び出し時に渡された手続き == col4 (occur&co 'tuna '() (lambda (num newlat) ((lambda (num newlat) ((lambda (num newlat) ((lambda (num newlat) ((lambda (n l) (list n l)) num newlat)) num newlat)) (+ 1 num) (cons (car lat) newlat))) num newlat)) ) ; col4 展開後 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(col5) ; lat == '() ; (null? lat) => #t (col 0 (quote ())) ; col 展開前 (col5 0 (quote ())) ; col == 直前の呼び出し時に渡された手続き == col5 ((lambda (num newlat) ((lambda (num newlat) ((lambda (num newlat) ((lambda (num newlat) ((lambda (n l) (list n l)) num newlat)) num newlat)) (+ 1 num) (cons (car lat) newlat))) num newlat)) 0 (quote ())) ; col5 展開後、最終的に残った計算がこれ。この式を評価した結果が返り値となる。
occur&co が再帰するたびに、三つ目の引数である手続き col を新しい手続き (lambda (num newlat) ...) で囲ってやる。 col は引数を二つ受け取る手続きなので、囲う側の新しい手続きの引数を col に渡してやる。そうやってどんどん囲っていくわけだが、これを逆向きに考えると、ある手続きの中に手続きがあり、その中にまた手続きが・・・と、タマネギの皮をむくように手続きが出てくる。最後に出てくるのが occur&co をトップレベルで呼び出したときに渡した手続き。タマネギの皮をむくのと逆で、芯に皮をかぶせていってるようにみえるので、タマネギの皮むきを逆再生している様子をイメージしてみることにした。
最終的に残される計算は、引数を二つ受け取る手続きがネストしたもので、外側から順番に引数を渡しながら評価していく。一番外側の、つまり一番最初に評価される手続きの引数は、null? でチェックしたときに返していた初期値。なのでこの場合は 0 と (quote ()) となる。そうして引数に 0 と空リストを渡していって、途中で +1 したり cons したりされる。すると次の、一つ内側の手続きには 1 とか (tuna) とかが引数として渡される。最終的に (list 合計数値 合計リスト) が評価されて式全体の値が返る。
いちおう自分の言葉で説明できた。けど、ウェブで「継続」について調べるとこの本に書いてあるのとは全然違った説明がなされていて、本当に同じものを扱っているのか疑わしい気になる。 call/cc は引数を一つとり、とかいうしさ。俺が一瞬わかった気になった「継続」は一体、なんなんだ？
