转换为CPS(续传样式)

Question

如何将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))
   

*这不是任何功课!

Answer 1

请参阅编程语言,应用程序和解释,从第15章开始.第18章讨论如何自动执行,但如果您不熟悉表达"做下一步该做什么"的函数,您可能会想要首先尝试手指练习.

不要有人为你做这件事:你真的想要理解这个过程,并且能够独立于Scheme或其他方式手工完成.它特别出现在异步JavaScript Web编程中,你真的别无选择,只能进行转换.

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

所以如果我们有一个程序来计算三角形的hypothenuse:

(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,它讨论了为什么你需要触摸源程序中的所有lambdas,以便更高阶的情况也适用.

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

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

然后翻译这样的东西是:

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

...因为lambda只是一个可以传递给的值k1.但当然,翻译也需要贯穿lambda.

首先,我们必须尽到内心的召唤f与x(记住,所有非基本功能的应用需要通过适当的"什么到DO-下!"):

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