scheme - 转换为CPS(继续传递样式)

Question

如何将Scheme中的这些过程转换为CPS形式？

(lambda (x y)
  ((x x) y))

(lambda (x)
  (lambda (f)
    (f (lambda (y)
         (((x x) f) y))))

((lambda (x) (x x)
 (lambda (x) (x x))

*这不是任何作业!

Answer 1

请参见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)))

最后一个表达式表明您最终不得不计算“由内而外”，并且转换无处不在:原始源程序中的所有lambda最终都需要采用附加参数，并且所有非原始应用程序都需要填充“下一步做什么”作为该参数。

请仔细阅读所引用书的第17.2节:它涵盖了本章以及第17.5节，其中讨论了为什么需要触摸源程序中的所有lambda，以便更高阶的情况也适用。

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

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

然后这样的翻译是:

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

...因为该lambda只是可以传递给 k1的值。但是，当然，翻译也需要遍历lambda。

我们必须首先使用 f对 x进行内部调用(并且请记住，所有非原始函数应用程序都需要传递适当的“下一步做什么!”):

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

...取该值，然后将其再次应用于...

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