継続パズルyin-yangの回答

Ruby Scheme

Shiroさんに教えてもらったyin-yang puzzleの回答。

課題のプログラムは次の通りです。

(let* ([yin ((lambda (foo) (newline) foo) (call/cc (lambda (bar) bar)))]
       [yang ((lambda (foo) (write-char #\*) foo)
              (call/cc (lambda (bar) bar)))])
  (yin yang))

以下ネタバレ。

let*をlambdaと関数適用に分解して、名前をわかりやすくすると次のようになります。

((lambda (yin)
   ((lambda (yang)
      (yin yang))
    ((lambda (yang*) (write-char #\*) yang*)
     (call/cc (lambda (cc) cc)) ; (B)
     )))
 ((lambda (yin*) (newline) yin*)
  (call/cc (lambda (cc) cc)) ; (A)
  ))

注目するべき点は、Bで捕捉される継続では、yinになんらかの値が束縛されている、ということです。実際には、AかBで捕捉される継続のいずれかが束縛されます。Bの継続が束縛されている場合、その継続ではyinになんらかの値、具体的にはAかBで捕捉される継続のいずれかが束縛されており、Bの継続が束縛されている場合、その継続では……。

Aの継続が呼び出されると、改行して、引数で渡された値がyinに束縛されます。

Bの継続が呼び出されると、その継続が捕捉された時点でのyinへの束縛が再現され、アスタリスクが出力され、引数で渡された値がyangに束縛されます。

ステップを追うと次のとおり。

1. (newline), そしてAの継続がyinに渡される。ここで名前環境を{yin=A}と書く。
2. (write-char #\*), そしてBの継続がyangに渡される。このBの継続において、上述したとおり、yinにはAの継続が束縛されている。これを{yin=A, yang=B{yin=A}}と書く。
3. (yin yang)を呼ぶということは、(A B{yin=A})を呼ぶということ。Aに戻って(newline), そしてyin*, yinにはB{yin=A}が渡される。{yin=B{yin=A}}
4. (write-char #\*), そしてyangにはBの継続が渡されるが、このBの継続において、yinにはB{yin=A}が束縛されている。つまり{yin=B{yin=A}, yang=B{yin=B{yin=A}}}。
5. (yin yang)は(B{yin=A} B{yin=B{yin=A}})。Bに戻るが、そのときyinにはAが束縛された状態。(write-char #\*)を呼んで、yangには(yin yang)の引数であるB{yin=B{yin=A}}が渡される。{yin=A, yang=B{yin=B{yin=A}}}。
6. (yin yang)は(A B{yin=B{yin=A}})。Aに戻って(newline), そしてyinにはB{yin=B{yin=A}}が渡される。{yin=B{yin=B{yin=A}}}。
7. (write-char #\*), そしてyangにはBの継続が渡されるが、このBの継続において、yinにはB{yin=B{yin=A}}が束縛されている。{yin=B{yin=B{yin=A}}, yang=B{yin=B{yin=B{yin=A}}}}。
8. (write-char #\*), {yin=B{yin=A}, yang=B{yin=B{yin=B{yin=A}}}}
9. (write-char #\*), {yin=A, yang=B{yin=B{yin=B{yin=A}}}}
10. (newline), {yin=B{yin=B{yin=B{yin=A}}}}
11. (write-char #\*), {yin=B{yin=B{yin=B{yin=A}}}, yang=B{yin=B{yin=B{yin=B{yin=A}}}}}
12. (write-char #\*), {yin=B{yin=B{yin=A}}, yang=B{yin=B{yin=B{yin=B{yin=A}}}}}
13. ...

Rubyで書き直すと次の通り。

require 'continuation'

def let(v, &block)
  block[v]
end

let(lambda {|foo| puts ''; foo }[callcc{|bar| bar }]) {|yin|
  let(lambda {|foo| print '*'; foo }[callcc{|bar| bar }]) {|yang|
    yin[yang]
  }
}