Scheme修行　第13章　ホップ、スキップ、ジャンプ（その１）

ここではcall-with-current-continuationを習います。この本では単にletccと言う名前になっています。処理系によってはcall/ccと言う名前もある様ですが、DrRacketではフルスペルでcall-with-current-continuationが使われています。

ノート：

intersectall

まずはintersectのおさらい。
intersectは二つの集合に適用し、積集合を意味する。
intersectの値は：

set1が空の時は空集合
set1の先頭要素がset2に含まれる場合、set1の残りの要素とset2にintersectを適用した集合にset1の先頭要素を加えた集合
set1の先頭要素がset2に含まれない場合、set1の残りの要素とset2にintersectを適用した集合

である。

> (let ((set1 '(tomatoes and macaroni))
        (set2 '(macaroni and cheese)))
    (intersect set1 set2))
(and macaroni)
>

set2は不変としてletrecを使って以下のコードではintersect2として再定義する。

> (let ((set1 '(tomatoes and macaroni))
        (set2 '(macaroni and cheese)))
    (intersect2 set1 set2))
(and macaroni)
>

intersectallは集合のリストに適用し、全ての集合の積集合を意味する。
intersectallの値は

集合のリストに集合が一つであれば、その集合
そうでなければ、集合リストの先頭の集合と、残りの全ての集合の積集合との積集合

> (intersectall '((a b c d e f)
                  (b c d e f g)
                  (c d e f g h)))
(c d e f)
>

一度だけ確かめれば良い条件を再帰の度にチェックしない様にletrecを使う。
letrec版intersectallをintersectall2として定義。

> (intersectall2 '((a b c d e f)
                   (b c d e f g)
                   (c d e f g h)))
(c d e f)
> (intersectall2 '((a b c)))
(a b c)
> (intersectall2 '())
()
> (let ((lset '((3 mangos and)
                (3 kiwis and)
                (3 hamburgers))))
    (intersectall2 lset))
(3)
> (let ((lset '((3 steaks and)
                (no food and)
                (three baked potatoes)
                (3 diet hambergers))))
    (intersectall2 lset))
()
> (let ((lset '((3 mangoes and)
                ()
                (3 diet hambergers))))
    (intersectall2 lset))
()
>

lsetに含まれる集合が一つになる前に空集合を見つけたとしても、再帰の帰り道にintersectを毎回適用してしまうので、一部しか節約出来ない。

call-with-current-continuation版をintersectall3として定義する。

> (intersectall3 '((a b c d e f)
                   (b c d e f g)
                   (c d e f g h)))
(c d e f)
> (intersectall3 '((a b c)))
(a b c)
> (intersectall3 '())
()
> (let ((lset '((3 mangos and)
                (3 kiwis and)
                (3 hamburgers))))
    (intersectall3 lset))
(3)
> (let ((lset '((3 steaks and)
                (no food and)
                (three baked potatoes)
                (3 diet hambergers))))
    (intersectall3 lset))
()
> (let ((lset '((3 mangoes and)
                ()
                (3 diet hambergers))))
    (intersectall3 lset))
()
>

call-with-current-continuationはつまり、

引数として与えられた関数をすぐに呼び出す。
その関数には引数として、その関数から戻った時に実行される関数が渡される。

つまりcall-with-current-continuationの引数となる関数では、その関数の引数として渡された関数を呼ぶ事でcall-with-current-continuationが呼ばれた直後に戻る事が出来る。setjump/longjumpやtry/catchと似ている。

次にintersectをintersectallの内部関数として、その第２引数が空リストの場合にも同じくhopを呼ぶ形に変形する。intersectの関数値が空リストになった瞬間にhopを呼ぶ事も考えられるが、恐らくその判定をする箇所は複数に分散してしまう。intersectで判定する場合１回だけ余分にintersectを呼んでしまう。

intersectを内部関数に取り込んだ定義が間違っている様に思う。

((member? (car s1) s2) (J (cdr s1)))
(else (cons (car s1) (J (cdr s1))))

となっているが、これではs1のcarがs2に含まれていない時に結果に足してしまうのでunionの定義と混同しているのでは。正しくは

((member? (car s1) s2) (cons (car s1) (J (cdr s1)))
(else (J (cdr s1)))

ではないか。

intersectを内部関数に取り込んだ定義をintersectall4として評価する。

> (intersectall4 '((a b c d e f)
                   (b c d e f g)
                   (c d e f g h)))
(c d e f)
> (intersectall4 '((a b c)))
(a b c)
> (intersectall4 '())
()
> (let ((lset '((3 mangos and)
                (3 kiwis and)
                (3 hamburgers))))
    (intersectall4 lset))
(3)
> (let ((lset '((3 steaks and)
                (no food and)
                (three baked potatoes)
                (3 diet hambergers))))
    (intersectall4 lset))
()
>  (let ((lset '((3 mangoes and)
                ()
                (3 diet hambergers))))
    (intersectall4 lset))
()
>