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 个问题，但它们背后的基本思想（我不确定我是否理解正确）是相同的。其他 Lisps、Haskell、Erlang 或其他函数式语言的解释都很好。

4

1 回答 1

9

延续传递式变换可以是部分的，也可以是完整的。您通常使用的系统中某些原语（+、- 等）被卡在非 cps-land 中。幸运的是，无论哪种方式，CPS 都能正常工作。

CPSing中的步骤：

  • 选择哪些功能将是原始的。
  • CPS 转换，以便所有非原始函数（包括延续）仅在尾部位置调用。

因此，在您的代码中，您的 'lift/k' 本质上是将其给定功能视为原始功能：请注意，lift/k 的主体在非尾部位置调用 'f'。如果您不想将提升的函数视为原语，则必须进入并显式重写它。

您的 'compose' 函数由两个 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 回答