6

The Seasoned Schemerを読んだ後、私はcall/ccきちんと理解できたと感じました。しかし、いくつかの WOW トリックを見た後、call/cc私が間違っていることがわかりました。

(define cc 0)
(define (f)
  (call/cc (lambda (k)
             (set! cc k)
             3)))

(+ 1 2 4 (f)) ; eval's to 10
(cc 13) ; eval's to 20

それは私の理解と完全に一致します。call/cc電話に出たとき、プログラムの状態を保存しているだけだと思います。関数でその隣の関数を呼び出します。その関数 ( k) がどこかから呼び出された場合(call/cc ...)、指定されたパラメーターで全体を置き換えるだけです。上記のプログラムもそのように機能したようです


しかし、

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

  (define (generator)
    (call/cc (lambda (k) (state k))))
  generator)

(define (next)
  (itr (range 2)))

3 回呼び出すnextと、0、1、および が生成され'doneます。つまり、それによって与えられstateた関数を使用すると、プログラムの状態が復元されませんでした。私はそれを理解しようとしたことをあなたに示しました。kgenerator


call/ccでは、実際にはどのように機能するのでしょうか。

4

2 に答える 2

8

継続渡しスタイルあり (なしcall/cc)

最初ではなく明示的な継続渡しスタイルを使用するバージョンを実装すると、この例を理解しやすくなる場合がありますcall/cc。この場合、継続渡しバージョンの から始めましょうmap:

(define (kmap fn list k)
  (if (null? list)
      (k list)
      (fn (car list)
          (lambda (head)
            (kmap fn
                  (cdr list)
                  (lambda (tail)
                    (k (cons head tail))))))))
(define (identity x) x)

(kmap (lambda (x k) (k (+ 1 x))) '(1 2 3 4) identity)
;=> (2 3 4 5)

継続渡しスタイルに慣れていない場合、これは頭を悩ませるかもしれませんが、それほど難しくはありません。それぞれが「結果」で呼び出す必要がある追加のパラメーターを最後に取ることkmapを覚えておいてください。fnしたがって、fnwithを呼び出すときは、マッピングの残りの処理を担当(car list)するプロシージャも渡します。マッピングの残りの部分は、再び(lambda (head) ...)によって定義されます。kmapへの各呼び出しkmapは、リストをマッピングした結果のリストを受け取ることを期待する最終的な継続を取りfnます。

これで、継続渡しスタイルでマッピングを実装する方法がわかったので、それを使用してイテレータ生成手順を記述できます。このプロシージャiteratorはリストを受け取り、 の各要素を取得するために呼び出すことができるプロシージャを返しますlist

(define (iterator list)
  (define (next k)
    (kmap (lambda (item more-next)
            (set! next more-next)
            (k item))
          list
          (lambda (results)
            (k 'done))))
  (lambda ()
    (next identity)))
> (define get (iterator '(1 2)))
> (get)
1
> (get)
2
> (get)
done
> (get)
done
> (define get (iterator '(a b c)))
> (get)
a
> (get)
b
> (get)
c
> (get)
done
> (get)
done

ここでの秘訣は、ローカル プロシージャを定義することnextです。の各要素がいつ処理されるかを の残りの部分を処理するプロシージャとして再定義kmapするプロシージャで呼び出します。を再定義した後、要素で呼び出します。に渡された最後の継続は、実際には渡された結果を無視し、シンボルで呼び出すだけです。返されるのはの値ではなく、継続で呼び出す手続きです。ここでの間接化は、常にwithの最新の値を呼び出すことを意味します。通過 nextlistlistnextkkmapkdoneiteratornextnextidentitynextidentityidentity継続とは、リスト要素を取得することを意味するためです。

call/cc

を使用せず にこれを行う方法がわかったのでcall/cc、 を使用call/ccしてそれを行う方法を確認する準備が整いました。質問の定義を思い出してください。

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

  (define (generator)                   
    (call/cc (lambda (k) (state k))))   
                                        
  generator)                            

発電機の返却

最初に注意してください

  (define (generator)
    (call/cc (lambda (k) (state k))))

  generator

に簡略化できます

(lambda () (call/cc (lambda (k) (state k))))

これが、実装で行ったこととほぼ同じです。これを REPL から呼び出す場合、必要kなのは値を取得して返す (そして出力する) ことだけです。私たちのバージョンでは、単純に変更せずに返すことで近似しています。つまり、 を使用し、 の代わりにidentity名前を使用しました。そうnextstate

(lambda () (call/cc (lambda (k) (state k))))

のようです

(lambda () (next identity))

(stateまたはnext) 手順

残りは

  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

私たちが行ったことと非常によく似ています。2 つの引数 (アイテムと継続) を取るkmapand aを使用する代わりに、1 つの引数 (アイテム) のプロシージャを受け取り、そのプロシージャ内で継続を取得するために使用します。そうfnfor-eachcall/cc

(for-each
  (lambda (item)
    (call/cc (lambda (h)
               ...

のようです

(kmap (lambda (item h)
        ...

for-eachは最後の継続引数を必要としないため、 result-ignoring を渡すことはできません(lambda () (k 'done))。代わりに、呼び出しの(k 'done) for-each呼び出すだけです。あれは、

(for-each fn list)
(k 'done)

のようです

(kmap fn
      list
      (lambda (result)
        (k 'done)))

プログラム状態の保存

これらの実装の両方で、ある意味で「プログラムの状態を保存」しています。保存している重要な状態は、リストを反復処理し続ける状態です。

于 2014-06-12T14:51:57.983 に答える
1

何かがおかしいというあなたの疑いは正しいです。コードは完全に壊れています。これは、ジェネレーターがアイテムを呼び出すために呼び出されるたびに、メインライン プログラムの新しい継続をキャプチャーできないという事実から明らかです。というか、その続きを手探りで捨てる。その結果、2 番目の項目を取得しようとしたときに間違った継続が呼び出され、無限ループが発生します。

まず、質問の文言から何かを修正しましょう。呼び出しnextてもアイテムは得られません。を呼び出すnextと、ジェネレーター関数が生成されます。使用されることになっている方法nextは、次のように例示されます。

(let ((g (next)))
  (list (g) (g) (g)))  ;; should return (0 1 done)

しかし、実際には機能しません。それを調べてみましょう:

(define (itr lst)
  (define (state k)
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (k item))))
              lst)
    (k 'done))

  (define (generator)
    (call/cc (lambda (k) (state k))))
  generator)

(define (next)
  (itr (range 2)))

何が起こっているのかをたどってみましょう。

セットアップ:(next)呼び出されると、式は、変数がバインドされている環境でキャプチャされたクロージャーであるを(iter (range 2))返します。generatoritrlststate

最初の反復:nextしたがって、によって返されるジェネレーターへの最初の呼び出しは、 を呼び出しますgeneratorgeneratorのように表示される独自の継続を取得しklambdaに渡しますstate。そのため、stateが実行され、generatorの継続が にバインドされkます。それは最初の反復に入り、それ自体を新しい継続で置き換えることによって自身の状態を保存します: (set! state h). この時点で、以前の-d 関数stateへのバインディングは上書きされます。を再開する継続関数になりました。次のステップは、継続に戻ることです。definestatefor-eachitemkgeneratorアイテムを返します。これが、 への最初の呼び出しから最初のアイテムが表示される方法(next)です。

2 回目の反復:ここから、事態は悪化します。再び返されたジェネレーターへの 2 番目の呼び出しはnext、継続を再度キャプチャし、state現在生成中のコルーチンの継続であるを呼び出します。ジェネレーターは、独自の継続を に渡しますstate。しかしstate、もはや!defineによって -d された機能ではありません。そのため、 で新たにキャプチャされた継続は、 のレキシカル スコープ内にあるパラメータに接続されません2 番目の項目を生成するために が呼び出された場合、これはへの最初の呼び出しで最初にキャプチャされた継続を保持する元のバインディングを引き続き参照します。itrgeneratorkfor-each(k item)kkgeneratorこれは後方への goto に似ており、非終了動作になります。

これを修正する方法は次のとおりです。

(define (itr lst)
  (define yield '()) ;; forward definition (could use let for this).

  (define (state)    ;; k parameter is gone
    (for-each (lambda (item)
                (call/cc (lambda (h)
                           (set! state h)
                           (yield item))))  ;; call yield, not k
              lst)
    (yield 'done))  ;; yield, not k.

  (define (generator)
    (call/cc (lambda (self) 
               (set! yield self) ;; save new escape on each call
               (state))))
  generator)

;; test
(let ((g (itr (range 2))) ;; let's eliminate the "next" wrapper
  (display (list (g) (g) (g))))

出力は(0 1 done)です。

于 2016-06-20T14:50:11.910 に答える