nucさんのcall/ccクイズ

diary scheme

最近はずっとやる気がない。


かなり前に、

これに挑戦して、途中まで解いたメモが残っていたので、一応、最後まで解いてみた。
(以下、自力で解いてみたい人はネタバレ注意)




まず、以下の基本形から始める。

(define a
  (lambda ()
    ...))

この状態で、(a)を何度呼んでも、副作用が無いので、(a)は常に同じ値を返すしかない。
そこで、とりあえずcall/ccを導入してみる。

(define a
  (call/cc
    (lambda (goto-define-a)
      (lambda ()
        ...))))

これで、(a)を実行した時に、(a)の内部で(goto-define-a val)が実行される事で、(define a ...)の継続に戻れるようになった。
しかし、ここに戻った場合、返される値は「(define a ...)」の結果になってしまい、任意の値を返す事ができない。
call/ccの位置をどう変更しても、一番外側に(define a ...)がある限り、返り値は変更できないが、(define a ...)を実行しなくては、aの束縛を変更する事もできない。
もう少し、工夫が必要なようだ。

(begin
  (define a
    (call/cc
      (lambda (goto-define-a)
        (lambda ()
          ...))))
  ...)

これで、(define a ...)を実行後に、任意の値を返せるようになった。
defineはトップレベル束縛を操作できなくてはいけないので、begin以外では入れ子にする事はできないので、おそらく、この形以外には無いと思う。
どうも、二番目の問題の方が簡単そうなので、先にそっちに挑戦してみる。

(begin
  (define a
    (call/cc
      (lambda (goto-define-a)
        ;; this is binded to 'a
        (lambda args
          (if (null? args)
            (goto-define-a 1)
            #t))))) ; dummy return value of (a #t)
  (if (number? a)
    0 ; return value of (a)
    (a #t)))

綺麗とは言えないが、一応、二番目の問題の解が完成した。
しかし、これは要するに、defineによってaを再定義している訳で、set!と類似の技法と言わざるを得ない。


とりあえず、さっきの解を応用して、一番目の問題も解くだけ解いてみる。

(begin
  ;; (counter) => get saved number
  ;; (counter 123) => save number and goto backtrack point
  (define counter
    (call/cc
      (lambda (goto-define-counter)
        (letrec ((counter-maker
                   (lambda (init-num)
                     ;; this is true counter
                     (lambda opt-new-num
                       (if (null? opt-new-num)
                         init-num
                         (goto-define-counter
                           (counter-maker (car opt-new-num))))))))
          (counter-maker -1))))) ; initial number is -1
  (define old-count (counter))
  (define (a)
    (counter (+ old-count 1)))
  old-count)

実に手続き的だと言わざるを得ない。
また、内部でletrecを使ってしまっている。これはちょっと前提条件の「!を使わない」に引っかかる可能性がある(もしletを使ってletrecを実装してみろと言われた時に、どうも、set!無しには実装できないような気がするので)。


もう少しエレガントに解く方法がありそうに思えて、結構な期間考えてみたが、他の方法では微妙に上手く行かなかった。


尚、上の回答は「REPLから呼び出される事」を前提条件としている。
REPL以外から呼び出されても大丈夫にするには、Kahuaで使われている部分継続のようなテクニックを使う必要がある……が、今回は面倒なのでこのままにしておく。