4

私は Racket で CPS について学んでおり、これらの関数を書き上げることができました。

;lift a regular single-arg function into CPS
(define (lift/k f)
  (lambda (x k)
    (k (f x))))

;compose two CPS functions
(define (compose/k f g)
  (lambda (x k)
    (g x (lambda (y)
           (f y k)))))

それらは正しく動作しているようです

(define (is-two/k x k)
  (k (= x 2)))
(define is-not-two/k (compose/k (lift/k not) is-two/k))
(is-not-two/k 3 display)
(is-not-two/k 2 display)

#t#f

これらの関数がまだ「真の CPS」であるかどうか疑問に思っています。これらの関数で「真の」継続渡しを台無しにしましたか? CPS で関数構成手法を使用することはコーシャですか? 奨励されていますか？それとも、これを行うことは「妥協」と見なされますか? それを行うためのよりCPS-yの方法はありますか?

はい、5 つの質問をしたことはわかっていますが、それらすべての背後にある基本的な考え方 (正しく理解しているかどうかはわかりません) は同じです。他の Lisp、Haskell、Erlang、または他の関数型言語での説明は問題ありません。

4

1 に答える 1

9

継続渡しスタイルの変換は、部分的または完全にすることができます。通常、特定のプリミティブ (+、- など) が非 cps ランドにスタックしているシステムで作業しています。幸いなことに、CPS はどちらの方法でも問題なく機能します。

CPSing の手順:

  • プリミティブにする関数を選択します。
  • すべての非プリミティブ関数 (継続を含む) が末尾位置でのみ呼び出されるように CPS 変換します。

つまり、あなたのコードでは、'lift/k' は本質的に、指定された関数をプリミティブとして扱っています。lift/k の本体は末尾以外の位置で 'f' を呼び出していることに注意してください。リフトされた関数をプリミティブとして扱いたくない場合は、明示的に書き直さなければなりません。

あなたの 'compose' 関数は 2 つの CPSed 関数を構成しますが、それ自体は CPS ではありません (つまり、'compose' はプリミティブであると想定しています。おそらく CPS を使用する必要があります。値を直接返すだけなので、これは注意してください。簡単です：

;compose two CPS functions
(define (compose/k f g k)
  (k (lambda (x k)
       (g x (lambda (y)
              (f y k))))))
于 2011-03-07T05:39:15.730 に答える