8

これらの手順を Scheme で CPS 形式に変換するにはどうすればよいですか?

  1. (lambda (x y)
  ((x x) y))

  2. (lambda (x)
  (lambda (f)
    (f (lambda (y)
         (((x x) f) y))))

  3. ((lambda (x) (x x)
 (lambda (x) (x x))

※これは宿題ではありません！

4

2 に答える 2

24

第15章から始まるプログラミング言語、アプリケーション、および解釈を参照してください。第18章では、それを自動的に行う方法について説明していますが、「次に何をするか」を実行する関数の表現について考えることに慣れていない場合は、おそらく最初に指のエクササイズを試してみてください。

誰かにやらせてはいけません。Schemeなどに関係なく、プロセスを理解し、手作業で実行できるようにする必要があります。これは特に非同期JavaScriptWebプログラミングで発生します。この場合、変換を行う以外に選択肢はありません。

CPS変換では、すべての非プリミティブ関数が「次に何をするか」を表す関数を消費する必要があります。これにはすべてのラムダが含まれます。対称的に、非プリミティブ関数のアプリケーションは、「次に何をするか」関数を提供し、残りの計算をその関数に詰め込む必要があります。

したがって、三角形の斜辺を計算するプログラムがある場合は、次のようになります。

(define (hypo a b)
  (define (square x) (* x x))
  (define (add x y) (+ x y))

  (sqrt (add (square a)
             (square b))))

*ここでのプリミティブアプリケーションは、、、+およびだけであると述べた場合sqrt、他のすべての関数定義と関数呼び出しは、次のように変換する必要があります。

(define (hypo/k a b k)
  (define (square/k x k)
    (k (* x x)))

  (define (add/k x y k)
    (k (+ x y)))

  (square/k a 
            (lambda (a^2)
              (square/k b
                       (lambda (b^2)
                         (add/k a^2 b^2
                                (lambda (a^2+b^2)
                                  (k (sqrt a^2+b^2)))))))))

;; a small test of the function.
(hypo/k 2 3 (lambda (result) (display result) (newline)))

最後の式は、「裏返し」を計算する必要があり、変換が普及していることを示しています。元のソースプログラムのすべてのラムダは、追加の引数を取る必要があり、すべての非プリミティブアプリケーションは詰め込む必要があります。その議論として「何をすべきか」。

引用された本のセクション17.2をよく見てください。これと、ソースプログラムのすべてのラムダに触れる必要がある理由について説明している17.5について説明しているので、高階の場合も機能します。

高次の場合に適用される変換の別の例として、次のようにするとします。

(define (twice f)
  (lambda (x) 
    (f (f x))))

次に、このようなものの翻訳は次のとおりです。

(define (twice/k f k1)
  (k1 (lambda ...)))

...そのラムダは、に渡すことができる単なる値だからk1です。ただし、もちろん、変換はラムダを介して実行する必要があります。

f最初にwithの内部呼び出しを行う必要がありxます（そして、すべての非プリミティブ関数アプリケーションが適切な「次の処理」を渡す必要があることを忘れないでください）：

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               ...)))))

...その値を取得し、それをfに再度適用します...

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               (f fx-val ...))))))

...そして最後にその値をk2：に返します

(define (twice/k f k1)
  (k1 (lambda (x k2)
        (f x (lambda (fx-val)
               (f fx-val k2))))))

;; test.  Essentially, ((twice square) 7)
(define (square/k x k) (k (* x x)))
(twice/k square/k 
         (lambda (squaresquare)
           (squaresquare 7
                         (lambda (seven^4) 
                           (display seven^4)
                           (newline)))))
于 2012-02-02T15:42:46.923 に答える
0

CPS 変換に必要な/したいレベルを選択する必要があります。

(lambda (x y) ((x x) y))継続渡し（CP）スタイルが必要な場合は、問題(lambda (k x y) (k ((x x) y)))ありません。

その引数も CP スタイルとして扱われるようにしたい場合は、もう少し必要です。

最初に、2 番目の引数 ( y) のみが CP 形式であり、実際には次のようなもの(lambda (k) (k y0))であり、その値を抽出するためにいくつかの継続で呼び出す必要があると仮定すると、次のものが必要になります。

(lambda (k x y)
  (y (lambda (y0) (k ((x x) y0)) )) )

最後に、 と の両方が CP スタイルであるxと仮定します。y次に、次のようなものが必要になります。

(lambda (k x y)
  (x (lambda (x0)
       (x (lambda (x1)
            (y (lambda (y0)
                 (k ((x0 x1) y0)) ))))

xここでは、およびへの呼び出しを自由に並べ替えることができますy。xまたは、 の値が呼び出された継続に依存しないことがわかっているため、 を1 回呼び出すだけでよい場合もあります。例えば：

(lambda (k x y)
  (y (lambda (y0)
       (x (lambda (x0)
            (k ((x0 x0) y0)) ))))

あなたが尋ねた他の式も同様に変換できます。

于 2015-12-13T15:50:47.620 に答える