Let's start Scheme

2015-09-11

call/ccで嵌った話

call/ccというよりはguardなんだけど。

エラー処理をしたいとか、エラーが起きても処理を継続したいという場合はままある。そういったときに使えるのはguardであることもまぁ周知の事実だと思う。これから提示する例も常識的に理解されているものかもしれない。

まずは以下の例を見てもらいたい。
(import (rnrs))
;; (import (scheme base) (scheme write))
;; (define mod modulo)

(define count 100000)

(define (run)
  (let loop ((i 0))
    (if (= i count)
        i
        (guard (e (else (loop (+ i 1))))
          (when (zero? (mod i 5))
            (error 'who "dummy"))
          (loop (+ i 1))))))

(display (run)) (newline)
(flush-output-port (current-output-port))
これをみて、「あぁ、これはまずいわ」と一目で分かったら以下を読む必要はないです。

これがまずいプログラムだということは既に書いているのでいいとして、何がまずいか。問題になるのはguard内で外側のloopを呼んでいること。一見すると問題ないように見えるのだが、多くの処理系でguardの実装にcall/ccを使用しているのが問題になる。実装例:SRFI-34
参照実装を展開して簡潔に書くと以下のようになる。
(define (run)
  (let loop ((i 0))
    (if (= i count)
        i
        ((call/cc (lambda (k)
                    (let-values ((args (loop (+ i 1))))
                      (k (lambda () (apply values args))))))))))
はい、末尾再帰じゃないですね。なのでスタックがあふれます・・・orz

実際のところとして、R6RS的には末尾再帰になることを要求しているので上記はスタックがあふれるとまずいのだが、(嘘ついた。<cond>を<body>と空目した。)これが問題なく動いたのは確認した中ではChezとRacketだけ。(GuileとVicareは試してない。) もちろん、この2つはスタックを拡張して動かしてるだけかもしれないけど・・・ちなみにR7RSは末尾再帰であることを要求していないので、上記は動かなくても問題ない。

この挙動で嵌ったの実は2回目で、3度目があると嫌だなぁと思ったので適当に書き記しておく。 しかし、どうやったら末尾再帰なguardが実装できるんだろう?参照実装では無理だよなぁ?

追記:
直した。https://bitbucket.org/ktakashi/sagittarius-scheme/commits/7bab13c1e83820eda28fc7878b14209fe1b87df3?at=default

追記の追記:
Shiroさんとのやり取りで上記の修正が正しいのか不安になってきた。っが、問題になるケースが思い浮ばない+スタック消費しないのでこのままで行くことにする。

6 comments:

Shiro Kawai said...

あれ、srfi-34でも"That implicit cond expression is evaluated with the continuation and dynamic environment of the guard expression."なので末尾再帰にならないとだめじゃないですか? 参照実装はバグってるのかもしれないけど。
Gaucheはもうちょい内部的な理由で末尾再帰になってないのですがバグと認識してます。

kei said...

<body>部分についての言及がないので、そこは末尾再帰じゃなくてもいいのかなぁと思ってましたが、暗黙的に末尾再帰なんですかね?参照実装はcond部分は末尾再帰になってるみたいですけど、<body>部分はなってないので敢えて言及してないのかなぁと解釈したのですが(ちょっと自信ない)

Shiro Kawai said...

ああ、ハンドラ部分でなくbody部分の話でしたか。あれ、body部分は原理的に末尾再帰ではありえなくないですか? だってbody部分実行後にハンドラ(dynamic environmentの一部)を戻す必要がありますよね。r6rsでもbody部分を末尾呼び出しにしろとは書いてないような。

kei said...

あ、本当だ。<cond>を<body>と空目したみたいです。

Shiro Kawai said...

(with-exception-handler handler thunk) の thunkの実行が末尾コンテキストにならないと思うんですが(終了後にハンドラを戻す必要があるので)、なんか上手い方法あります?

kei said...

そういえば、そうですね。call/ccの呼び出しでフレームがヒープに押し出されてるから見かけ上スタックを消費していない(警告がでない)だけっぽいです。(ただ、修正後の方が動作が安定しているので、多少メリットはあるのかも?)

Post a Comment