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

参见Programming Languages, Application and Interpretation，从第 15 章开始。第 18 章讨论了如何自动完成，但如果你不熟悉如何表达一个“下一步做什么”的函数，你可能会想要首先尝试手指练习。

不要让别人为你做：你真的很想了解这个过程，并且能够手工完成，独立于 Scheme 或其他方式。它尤其出现在异步 JavaScript Web 编程中，你真的别无选择，只能进行转换。

在 CPS 变换中，所有非原始函数现在都需要使用一个表示“下一步做什么”的函数。这包括所有 lambda。对称地，非原始函数的任何应用程序都需要提供“下一步做什么”函数，并将其余的计算填充到该函数中。

因此，如果我们有一个程序来计算三角形的对角线：

(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)))

最后一个表达式表明您最终必须计算“由内而外”，并且这种转换是普遍存在的：原始源程序中的所有 lambdas 最终都需要接受一个额外的参数，所有非原始应用程序都需要填充“下一步做什么”作为该论点。

仔细查看引用书的第 17.2 节：它涵盖了这一点，以及 17.5，其中讨论了为什么需要接触源程序中的所有 lambda，以便高阶情况也可以工作。

作为转换的另一个示例，应用于高阶情况，假设我们有：

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

那么这样的翻译是：

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

...因为那个 lambda 只是一个可以传递给k1. 但当然，翻译也需要通过 lambda。

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 风格，那么您需要更多。

首先假设只有第二个y参数(lambda (k) (k y0))（

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

最后假设两者x都y属于CP风格。然后你需要类似的东西：

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

x在这里，您可以自由地重新排序对和的调用y。或者也许您只需要一次调用x，因为您知道它的值不依赖于调用它的延续。例如：

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

您询问的其他表达式可以类似地转换。

于 2015-12-13T15:50:47.620 回答