7

私は C# で小さな Scheme インタープリターを書きましたが、それを実装した方法では、適切な継続のサポートを追加するのが非常に簡単であることに気付きました。

だから私はそれらを追加しました...しかし、私がそれらを追加した方法が正しいことを「証明」したいのです。

ただし、Scheme インタープリターは「変更」状態をサポートしていません。すべてが不変です。

したがって、「上向き」の継続を公開する単体テストを作成するのは非常に簡単でした。

AssertEqual(Eval("(call/cc (lambda (k) (+ 56 (k 3))))"), 3);

ただし、継続が「エスケープ」した場合でも機能することを示す単体テストも作成したいと思います。

AssertEqual(Eval("(call/cc (lambda (k) k))", <some continuation>);

しかしもちろん、上記は「継続を取得した」ことをテストするだけであり、実際に有効な継続であるとは限りません。

ただし、私が見つけることができるすべての例は、常に「set!」を使用して終了します。エスケープされた継続を示すために。

ミューテーションに依存せずに後方継続を適切にサポートしていることを示す最も単純なSchemeの例は?

後方継続は突然変異なしで役に立ちますか? まったく同じ計算を再度実行するためにしか使用できないため、そうではないのではないかと疑い始めています...副作用がなければ意味がありません。これが Haskell に継続がない理由ですか?

4

4 に答える 4

8

これが最も単純かどうかはわかりませんが、次のような呼び出しを行わずに後方継続を使用する例を次に示しますset!。

(apply
  (lambda (k i) (if (> i 5) i (k (list k (* 2 i)))))
  (call/cc (lambda (k) (list k 1))))

これは に評価され8ます。

もう少し興味深いのは次のとおりです。

(apply
  (lambda (k i n) (if (= i 0) n (k (list k (- i 1) (* i n)))))
  (call/cc (lambda (k) (list k 6 1))))

を計算6!します (つまり、評価すると になり720ます)。

で同じことを行うこともできますlet*：

(let* ((ka (call/cc (lambda (k) `(,k 1)))) (k (car ka)) (a (cadr ka)))
      (if (< a 5) (k `(,k ,(* 2 a))) a))

（男、stackoverflowの構文強調表示はスキームで大規模に失敗します。）

于 2009-06-11T22:03:32.603 に答える
2

私はあなたが正しいと思います-突然変異がなければ、後方継続は前方継続ができないことを何もしません。

于 2009-06-11T21:39:39.027 に答える
0

機能スレッド:

再帰ループを使用して、突然変異なしで状態を更新できます。呼び出される次の継続の状態を含みます。これは他の例よりも複雑ですが、実際に必要なのはthread-1andmainループだけです。他のスレッドと「更新」関数は、継続が些細な例以上に使用できることを示すためにあります。さらに、この例が機能するには、let という名前の実装が必要です。これは、define ステートメントで作成された同等の形式に変換できます。

例：

(let* ((update (lambda (data) data))                ;is identity to keep simple for example
       (thread-1                                    
         (lambda (cc)                               ;cc is the calling continuation
           (let loop ((cc cc)(state 0))
             (printf "--doing stuff       state:~A~N" state)
             (loop (call/cc cc)(+ state 1)))))      ;this is where the exit hapens
       (thread-2
         (lambda (data)                             ;returns the procedure to be used as 
           (lambda (cc)                             ;thread with data bound
             (let loop ((cc cc)(data data)(state 0))
               (printf "--doing other stuff state:~A~N" state)
               (loop (call/cc cc)(update data)(+ state 1)))))))
  (let main ((cur thread-1)(idle (thread-2 '()))(state 0))
    (printf "doing main stuff    state:~A~N" state)
    (if (< state 6)
        (main (call/cc idle) cur (+ state 1)))))

どの出力

doing main stuff    state:0
--doing other stuff state:0
doing main stuff    state:1
--doing stuff       state:0
doing main stuff    state:2
--doing other stuff state:1
doing main stuff    state:3
--doing stuff       state:1
doing main stuff    state:4
--doing other stuff state:2
doing main stuff    state:5
--doing stuff       state:2
doing main stuff    state:6
于 2016-04-24T01:23:44.983 に答える
0

これが私が思いついた最高のものです：

AssertEqual(Eval("((call/cc (lambda (k) k)) (lambda (x) 5))", 5);

驚くべきことではありませんが、これは逆方向の継続であり、呼び出したい実際の関数、つまり数値 5 を返す関数で「呼び出し」ます。

ああ、私もこれを良い単体テストケースとして思いつきました：

AssertEqual(Eval("((call/cc call/cc) (lambda (x) 5))", 5);

私はJacob Bに同意します-可変状態がなければそれほど有用ではないと思います...しかし、それでも反例に興味があります。

于 2009-06-11T22:05:24.440 に答える