継続マラソン - 継続の実装方法を考える7

Scheme

継続の実装方法に関して、理解できたと思ったりやっぱりだめだというのを繰り返していたのだけど、理解を妨げていたものが分かった。
ずばり僕の処理系の実装におけるS式の扱いに問題がある。
処理系は

text => S式 => Scheme内部オブジェクト => Scheme内部オブジェクトを eval

という作りなのですがScheme内部オブジェクトの設計が悪いのか、これがいろいろなものの理解の妨げになっていた。


処理系の内部での主役をS式にすると、とても理解しやすい。

(define cont '())
(define a (lambda ()
            (display "1")
            ( (lambda ()
               (display "2")
               (call/cc (lambda (c) (set! cont c)))
               (display "3")))
            (display "4")))
(a) ; => 1 2 3 4
(cont 0) => 3 4

S式を解釈して eval する処理系を考えると

  1. cont に '() というS式を束縛
  2. a に (lambda ...)というS式を束縛
  3. (a)というS式を eval
  4. (lambda ...)というS式を eval
    1. ( (display "1") ( (lambda () (display "2") (call/cc ..) (display "3"))) (display "4"))を順に eval していく
    2. とりあえず call/cc を無視すれば 1 2 3 4 と表示される
    3. call/cc の set! で cont に( (display "3") (display "4")) というS式が束縛される
    4. この場合 (display "3")と(display "4")では参照しているEnvが違う点に注意
  5. (cont 0)というS式を eval。
  6. contには、( (display "3") (display "4"))というS式が束縛されているので eval すればよい。

手続き呼び出しの場合はどうだろうか

(define cont '())
(define a (lambda ()
            (+ 1
               (+ 2 3)
               (call/cc (lambda (c) (set! cont c) 4))
               (+ 5 6))))
(a) ; => 21
(cont 5) ; => 22
  1. cont に '() というS式を束縛
  2. a に (lambda ...)というS式を束縛
  3. (a)というS式を eval
  4. (lambda ...)というS式を eval
  5. (+ 1 (+ 2 3) (call/cc ..) (+ 5 6))を eval する
  6. call/cc の set! で cont に ( (+ 1 5 (call/cc ..) (+ 5 6))) というS式が束縛される
    1. ポイントは (+ 2 3) は 結果のS式に置き換えられている点
  7. (cont 5)というS式を eval する
  8. ( (+ 1 5 5 (+ 5 6))) というS式を evalする

特殊構文 if の場合はどうだろうか？

(define cont '())
(define a (lambda ()
            (if (call/cc (lambda (c) (set! cont c) #f))
                (display "#t")
                (display "#f"))
            (display "if end")))
(a)
(cont #t)
  1. いろいろ略
  2. call/cc の set! で cont に ( (if (call/cc ..) (display "#t") (display "#f")) (display "if end")) というS式に束縛する
  3. いろいろ略

Envの話

そろそろ Env も考慮しないとダメだな。
うーんと。最初に例に出したパターンだと cont に束縛されるS式は
( (display "3") (display "4"))と思ったのだけど、それぞれ Env が違うことを考慮しないといけない。

(define cont '())
(define a (lambda ()
            (display "1")
            ( (lambda ()
               (display "2")
               (call/cc (lambda (c) (set! cont c)))
               (display "3")))
            (display "4")))
(a) ; => 1 2 3 4
(cont 0) => 3 4

正確に書くと cont に束縛されるS式はのようになるかな。
(begin ( (lambda () (display "3"))) ( (lambda () (display "4"))))
1つ目、2つ目の lambda にはそれぞれ call/cc 時の適切な Env を与えないといけない。


これはどうやるのがきれいだろうか。
call/cc 時に Env を保存してやるのは分かる。
あぁ。フレームを上にたどるのであれば、
( (lambda () ( (lambda () ( (display "3")) (display"4")))))
が正しいね。納得した。