Scheme手習い(12) 継続 - kb84tkhrのブログ

第8章「究極のlambda」の続きの続き

Scheme手習いもそろそろ終盤
継続ってやつが出てきます
中ボスクラス

Schemeはもともと継続を扱う機能を持っているんですが
ここではlambdaを使って継続を手作りします
たぶん原理的には同じもの

では、これはどうでしょう。

(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)))))))

わかりません！

本でも一歩ずつ進めていますが慣れたやりかたで確かめていきます
colには次の関数を入れます

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

そもそもこの関数が何かって話もありますが細かいことは忘れて進みます
一番簡単なやつから

  (multirember&co 'tuna '() a-friend)
= (a-friend '() '())
= (null? '())
= #t

a-friendというのは最後に呼ばれる関数のようです
たぶんa-friendがやってることには大した意味はなくてただ呼ばれるだけのもの

次は(tuna)を与えます
eq?が成り立ちますね

  (multirember&co 'tuna '(tuna) a-friend)
= (multirember&co 'tuna '()
    (lambda (newlat seen) (a-friend newlat (cons 'tuna seen))))
= ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen))) '() '())
= (a-friend '() (cons 'tuna '()))
= (a-friend '() '(tuna))
= (null? '(tuna))
= #f

seenにtunaがconsされました

lambdaの中の引数はさっさと置き換えたけど大丈夫だったかな
最後まで値に置き換えないのが正しいのかもしれない
そうするとこう

  (multirember&co 'tuna '(tuna) a-friend)
= (multirember&co 'tuna '()
    (lambda (newlat seen) (col newlat (cons (car lat) seen))))
    ;ここでcolはa-friend、latは(tuna)
= ((lambda (newlat seen) (col newlat (cons (car lat) seen))) '() '())
    ;ここでcolはa-friend、latは(tuna)
= ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen))) '() '())
    ;ここで初めてcolやlatを値に置き換える？
= (a-friend '() (cons 'tuna '()))
= (a-friend '() '(tuna))
= (null? '(tuna))
= #f

式の上に現れない情報があってちょっと書きにくいです
結果は同じでした
すぐ置き換えちゃうことにします

次はeq?が成り立たない引数で

  (multirember&co 'tuna '(and) a-friend)
= (multirember&co 'tuna '()
    (lambda (newlat seen) (a-friend (cons 'and newlat) seen)))
= ((lambda (newlat seen) (a-friend (cons 'and newlat) seen)) '() '())
= (a-friend (cons 'and '()) '())
= (a-friend '(and) '())
= (null? '())
= #t

今度はnewlatにandがconsされました
パターンが見えてきました

普通っぽい引数で

  (multirember&co 'tuna '(tuna and swordfish) a-friend)
= (multirember&co 'tuna '(and swordfish)
    (lambda (newlat seen) (a-friend newlat (cons 'tuna seen))))
= (multirember&co 'tuna '(swordfish)
    (lambda (newlat seen)
      ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
       (cons 'and newlat) seen)))
= (multirember&co 'tuna '()
    (lambda (newlat seen)
      ((lambda (newlat seen)
         ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
          (cons 'and newlat) seen))
       (cons 'swordfish newlat) seen)))
= ((lambda (newlat seen)
     ((lambda (newlat seen)
        ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
         (cons 'and newlat) seen))
      (cons 'swordfish newlat) seen))
   '() '())
= ((lambda (newlat seen)
     ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
      (cons 'and newlat) seen))
   '(swordfish) '())
= ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
   '(and swordfish) '())
= (a-friend '(and swordfish) '(tuna))
= #f

colは最終的に、()にswordfishをくっつけて、andをくっつけて
それとは別に()にtunaをくっつけてからa-friendを呼ぶ関数になりました
リストの後ろのほうからくっつけていくことになるので少しイメージしにくいですが
consを使うとリストの先頭に要素をくっつけていくため
つじつまが合って元の順番を崩さずに要素が取り出せています

colが膨れ上がって見づらくなったので、変数っぽいもので置き換えてみます

  (multirember&co 'tuna '(tuna and swordfish) a-friend)
;ここでcol1 = a-friendとする
= (multirember&co 'tuna '(and swordfish)
                  (lambda (newlat seen) (col1 newlat (cons 'tuna seen))))
;ここでcol2 = (lambda (newlat seen) (col1 newlat (cons 'tuna seen)))とする
= (multirember&co 'tuna '(swordfish)
                  (lambda (newlat seen) (col2 (cons 'and newlat) seen)))
;ここでcol3 = (lambda (newlat seen) (col2 (cons 'and newlat) seen))とする
= (multirember&co 'tuna '()
                  (lambda (newlat seen) (col3 (cons 'swordfish newlat) seen)))
;ここでcol4 = (lambda (newlat seen) (col3 (cons 'swordfish newlat) seen))とする
= (col4 '() '())
= ((lambda (newlat seen) (col3 (cons 'swordfish newlat) seen)) '() '())
= (col3 '(swordfish) '())
= ((lambda (newlat seen) (col2 (cons 'and newlat) seen)) '(swordfish) '())
= (col2 '(and swordfish) '())
= ((lambda (newlat seen) (col1 newlat (cons 'tuna seen))) '(and swordfish) '())
= (col1 '(and swordfish) '(tuna))
= (a-friend '(and swordfish) '(tuna))
= #f

すごくわかりやすくなったのかというとそうでもない気もします
まあ練習練習

(lambda (newlat seen) (col newlat (cons (car lat) seen)))といった関数は
その場では実質的な処理は行ってなくて
あとでこんな風に引数をいじって最後にa-friendを呼び出してね、と言ってるんですね

(multirember&co a lat col)

というのは

latから、newlatにa以外の要素を、seenにaを集めてcolを適用しろ

という関数です
multirember&coは上の処理を少しだけ簡単にして、multirember&coを呼び出します

(multirember&co a (cdr lat)
  (lambda (newlat seen) (col (cons (car lat) newlat) seen)))

こういう風に理解しました

multirember&coさんはある日、上司から仕事を頼まれました
ひとりでやるのは大変なので、自分そっくりの能力を持つ下請けさんと仕事の相談をします

あのさあ、上からこんな問題解けって言われたんだよ

latからaを取り除けと言われました

ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？

(cdr lat)についてだけ解けばいいようにして、下請けさんに仕事を依頼します

でさあ、答えが出たらオレの分の実作業もやっといてよ

(cons (car lat) newlat)もやっといてねと下請けさんにお願いします

あとさあ、答えが出たらコレしとけって言われてんだよね
これもやっといてくんね？

上司に頼まれたcolも下請けさんにやらせようとします
下請けさんも自分でやるのは大変なのでやはり下請けさんとそっくりの能力を持つ
部下と仕事の相談をします

あのさあ、上からこんな問題解けって言われたんだよ
ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？
でさあ、答えが出たらオレの分の実作業もやっといてよ
あとさあ、答えが出たらコレしとけって言われてんだよね
これもやっといてくんね？

上司さんがオレさんに頼んだ分とオレさんが下請けさんに頼んだ分までやるように
お願いされてしまいました
下請けさんの部下は困ってしまって二次請けさんの（以下同文）

n次受けさんは

()からaを取り除く？ああそれくらい簡単だよ

それはいいんですが

え、実作業全部オレがやるの？

そうですあなたがやるんです
こういう仕事ね

((lambda (newlat seen)
   ((lambda (newlat seen)
      ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
       (cons 'and newlat) seen))
    (cons 'swordfish newlat) seen))
 '() '())

継続で渡すというのはたいへんな多重請負丸投げ構造だったというわけです
丸投げして結果すら見てないという世界
オマエが返してくる値なんかいらないよと
その代わり値が求まったらその値についてこうしとけと

という理解

ついでに普通の再帰だとどういう理解になるか

(define multirember
  (lambda (a lat)
    (cond ((null? lat) (quote ()))
          ((eq? (car lat) a) (multirember a (cdr lat)))
          (else (cons (car lat) (multirember a (cdr lat)))))))

multiremberさんはある日、上司から仕事を頼まれました
ひとりでやるのは大変なので、自分そっくりの能力を持つ下請けさんと仕事の相談をします

あのさあ、上からこんな問題解けって言われたんだよ

latからaを取り除けと言われました

ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？

(cdr lat)についてだけ解けばいいようにして、下請けさんに仕事を依頼します

答えが出たら教えてねあとはやっとくから

ここが違います

下請けさんは(cdr lat)からaを取り除くことだけ考えます
とはいえ下請けさんも自分で全部やるのは大変なので部下と仕事の相談をします

あのさあ、上からこんな問題解けって言われたんだよ
ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？
答えが出たら教えてねあとはやっとくから

下請けさんの部下は(cdr (cdr lat))についてだけ解けばいいんですが
でもやっぱり二次請けさんの（以下同文）

n次受けさんは

()からaを取り除く？ ()でしょはいどうぞ

あとはそれぞれが自分の分担に応じてリストにアトムをくっつけたりくっつけなかったりしながら
答えを作って上司さんに答えを返します
健全な社会です

さて話を戻して

colが何を表すか知っていますか。
colは「collector(収集子)」の短縮形です。
収集子は「continuation(継続)」と呼ばれることもあります。

自分が呼び出す関数に、「自分の仕事（＝carを適切な引数にconsする仕事）が
終わったらコレやっとけよ」と関数を渡す
この「コレ」が「継続」ということ

最後の戒律

第10の戒律
同時に２つ以上の値を集める際には関数を作るべし。

関数はひとつの値しか返しませんが継続はいくつもの引数を取れますからね
multirember&coなんか少々不自然な例だなーと思ってましたが
（片方のリストにはtunaしか入らないし）
２つ以上の値を集める例を考えるのに苦労したということでしょうか

とはいっても関数だってリストで複数の値を返せるはず
(newlat seen)という形で値を返す関数を考えてみますよ
a-friendの代わりの関数はこうなります
seenを取り出すには(car (cdr ...))を使います

(define another-friend
  (lambda (newlat-seen)
    (null? (car (cdr newlat-seen)))))

いつものパターンにしたがって

(define multirember-list
  (lambda (a lat)
    (cond ((null? lat) (quote (() ())))
          ((eq? (car lat) a) (

えーと？
multirember-listを呼んで
返ってきた(newlat seen)からseenを取り出してtunaをconsして
またnewlatとconsして返したいんですけど
単純に(car (cdr (multirember-list ...)))としてseenを取り出すと
newlatを忘れてしまいます
何かに記憶しておかないと

手持ちの技だとlambdaの引数に入れるくらいしかなさそう

(define multirember-list
  (lambda (a lat)
    (cond ((null? lat) (quote (() ())))
          ((eq? (car lat) a)
           ((lambda (newlat-seen)
              (cons (car newlat-seen)
                    (cons (cons (car lat) (car (cdr newlat-seen))) '())))
            (multirember-list a (cdr lat))))
          (else
           ((lambda (newlat-seen)
              (cons (cons (car lat) (car newlat-seen))
                    (cons (car (cdr newlat-seen)) '())))
            (multirember-list a (cdr lat)))))))

これでいけるかな？

> (multirember-list 'tuna '(tuna and swordfish))
((and swordfish) (tuna))

> (another-friend (multirember-list 'tuna '(tuna and swordfish)))
#f

いけました

継続とくらべてわかりやすいかっていうとまあなんとも言えないですね
いくつか関数を定義してやれば見やすくはなると思いえますが
そこまで苦労して名前をつけるなら関数の引数にしておけば、って話でしょうか？

multiinsertLR&coは引数が増えただけなので割愛