((call/cc call/cc) (call/cc call/cc)) とは？

“L.i.S.P”より (C. Queinnec’s L.i.S.P book and code — https://pages.lip6.fr/Christian.Queinnec/WWW/LiSP.html) 第３章の問題。後続の文 Does 〜 は直前の問題からこちらに移動して足しました。

Exercise 3.2: What’s the value of ((call/cc call/cc) (call/cc call/cc))? Does the evaluation order influence your answer?

単に ((call/cc call/cc) (call/cc call/cc)) だけだとよくわからないので、出力を挟むようにします。

参考にさせて頂くのは、

Scheme:使いたい人のための継続入門, call/cc パズル — https://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3A%E4%BD%BF%E3%81%84%E3%81%9F%E3%81%84%E4%BA%BA%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E7%B6%99%E7%B6%9A%E5%85%A5%E9%96%80#H-2x6wuk

こちらのデバッグ手法を利用させて頂きます。というわけで以下のようにして考えます。

(((lambda (k) (newline) k)
  (call/cc call/cc))
 ((lambda (k) (write-char #\*) k)
  (call/cc call/cc)))

call/ccパズルというものがある。以前comp.lang.schemeというニュースグループで話題になったプログラムだ。

ところで、この元ネタってどこなのかしらん、と思ったのだけれども:

call/cc mind-boggler — https://groups.google.com/forum/#!msg/comp.lang.scheme/Fysq_Wplxsw/awxEZ_uxW20J

さて、ほとんどこのパズルと同じですけれども、違いはあります。手続き呼び出しの評価順序によっては出力が異なりそうだな、ということ。(Scheme言語の手続き呼び出し、評価順序 — https://t.laafc.net/2018/04/14/rnrs-procedure-calls.html)

というわけで、まず、オペレータが先に評価される場合を考えます。 racket(v6.12) や csi(chicken Version 4.12.0 (rev 6ea24b6)) で確認しました。

_ で狭まれた式の評価をしようとして、 (call/cc <arg>) だったら、式の評価を待ち構えている継続がどんなものかを考えて書き落ろしてゆきます。

;; 評価
(((lambda (k) (newline) k)
  _(call/cc call/cc)_)
 ((lambda (k) (write-char #\*) k)
  (call/cc call/cc)))
;; 継続 #0#
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       ((lambda (k) (write-char #\*) k)
        (call/cc call/cc))))
    x)))
;; 評価
(((lambda (k) (newline) k)
  _(call/cc #0#)_)
 ((lambda (k) (write-char #\*) k)
  (call/cc call/cc)))
;; 継続 これは #0# と同じ。次からは省略します。
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       ((lambda (k) (write-char #\*) k)
        (call/cc call/cc))))
    x)))
;; 評価 続継 #0# 呼び出し
(((lambda (k) (newline) k)
  _(#0# #0#)_)
 ((lambda (k) (write-char #\*) k)
  (call/cc call/cc)))
;; 評価 継続 (#0# #0#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       ((lambda (k) (write-char #\*) k)
        (call/cc call/cc))))
    _ #0#_)))
;; 出力 改行
;; 評価 (継続 #0# 内の評価が続くわけだけれども必要な所だけ)
(#0#
 ((lambda (k) (write-char #\*) k)
  _(call/cc call/cc)_))
;; 継続 #1#
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (#0#
       ((lambda (k) (write-char #\*) k)
        v)))
    x)))
;; 評価
(#0#
 ((lambda (k) (write-char #\*) k)
  _(call/cc #1#)_))
;; 継続は #1# と同じ
;; 評価 継続 #1# 呼び出し
(#0#
 ((lambda (k) (write-char #\*) k)
  _(#1# #1#)_))
;; 評価 継続 (#1# #1#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (#0#
       ((lambda (k) (write-char #\*) k)
        v)))
    _ #1#_)))
;; 出力 *
;; 評価 (続継 #1# 内の評価が続くわけだけれども必要な所だけ)
(#0# #1#)
;; 評価 継続 (#0# #1#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       ((lambda (k) (write-char #\*) k)
        (call/cc call/cc))))
    _ #1#_)))
;; 出力 改行
;; 評価 (継続 #0# 内の評価が続くわけだけれども必要な所だけ)
(#1#
 ((lambda (k) (write-char #\*) k)
  _(call/cc call/cc)_))
;; 継続 #2#
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (#1#
       ((lambda (k) (write-char #\*) k)
        v)))
    x)))
;; 評価
(#1#
 ((lambda (k) (write-char #\*) k)
  _(call/cc #2#)_))
;; 継続は #2# と同じ
;; 評価 継続 #2# 呼び出し
(#1#
 ((lambda (k) (write-char #\*) k)
  _(#2# #2#)_))
;; 評価 継続 (#2# #2#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (#1#
       ((lambda (k) (write-char #\*) k)
        v)))
    _ #2#_)))
;; 出力 *
;; 評価 (継続 #2# 内の評価が続くわけだけれども必要な所だけ)
(#1# #2#)
;; 評価 継続 (#1# #2#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (#0#
       ((lambda (k) (write-char #\*) k)
        v)))
    _ #2#_)))
;; 出力 *
(#0# #2#)
;; 評価 継続 (#0# #2#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       ((lambda (k) (write-char #\*) k)
        (call/cc call/cc))))
    _ #2#_)))
;; 出力 改行
;; 評価 (継続 #0# 内の評価が続くわけだけれども必要な所だけ)
(#2#
 ((lambda (k) (write-char #\*) k)
  _(call/cc call/cc)_))
;; 継続 #3#
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (#2#
       ((lambda (k) (write-char #\*) k)
        v)))
    x)))
;; 評価
(#2#
 ((lambda (k) (write-char #\*) k)
  _(call/cc #3#)_))
;; 継続は #3# と同じ
;; 評価 継続 #3# 呼び出し
(#2#
 ((lambda (k) (write-char #\*) k)
  _(#3# #3#)_))

;; :'m,.g/出力/p
;; 出力 改行
;; 出力 *
;; 出力 改行
;; 出力 *
;; 出力 *
;; 出力 改行

call/ccパズルと同じ出力です。違いは let* で継続を束縛しない替わりに (call/cc call/cc) で呼び出す継続を作って、手前の継続の呼び出しを数珠つなぎに、今作った呼び出す継続が渡されていく、という巧妙な構造になっています。すごいなこれ。

さて。今度はオペランドが先に評価される場合を考えます。chibi-scheme(0.7.3-566-g10759e8b), mit-scheme(Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 LIAR/x86-64 4.118 || Edwin 3.116) で確認しました。

Gauche(version 0.9.5) の場合 -fno-post-inline-pss を付けると確認できました。(付ける/付けないでどうして変わるのかはわかりません！)

;; 評価
(((lambda (k) (newline) k)
  (call/cc call/cc))
 ((lambda (k) (write-char #\*) k)
  _(call/cc call/cc)_))
;; 継続 #0#
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        (call/cc call/cc))
       ((lambda (k) (write-char #\*) k)
        v)))
    x)))
;; 評価
(((lambda (k) (newline) k)
  (call/cc call/cc))
 ((lambda (k) (write-char #\*) k)
  _(call/cc #0#)_))
;; 継続は #0# と同じ
;; 評価 継続 #0# 呼び出し
(((lambda (k) (newline) k)
  (call/cc call/cc))
 ((lambda (k) (write-char #\*) k)
  _(#0# #0#)_))
;; 評価 継続 (#0# #0#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        (call/cc call/cc))
       ((lambda (k) (write-char #\*) k)
        v)))
    _ #0#_)))
;; 出力 *
;; 評価 (継続 #0# 内の評価が続くわけだけれども必要な所だけ)
(((lambda (k) (newline) k)
  _(call/cc call/cc)_)
 #0#)
;; 継続 #1#
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       #0#))
    x)))
;; 評価
(((lambda (k) (newline) k)
  _(call/cc #1#)_)
 #0#)
;; 継続は #1# と同じ
;; 評価 継続 #1# 呼び出し
(((lambda (k) (newline) k)
  _(#1# #1#)_)
 #0#)
;; 評価 継続 (#1# #1#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       #0#))
    _ #1#_)))
;; 出力 改行
;; 評価 (続継 #1# 内の評価が続くわけだけれども必要な所だけ)
(#1# #0#)
;; 評価 継続 (#1# #0#)
(lambda (x)
  ((lambda (v) (PRINT-THEN-REPL v))
   ((lambda (v)
      (((lambda (k) (newline) k)
        v)
       #0#))
    _ #0#_)))
;; 出力 改行
;; 評価 (続継 #1# 内の評価が続くわけだけれども必要な所だけ)
(#0# #0#)

;; :'m,.g/出力/p
;; 出力 *
;; 出力 改行
;; 出力 改行

このように、がむしゃらに継続を関数で表現しようとすることを繰り返すことで、動作をトレースすることはできます。

継続が以前よりも恐くなくなった気がしますけれども、使いこなすことができるかと問われると…