在 Continuation Passing Style 中定义定点组合器

Question

fix-point combinators 是引入递归的非常有用的工具。
Continuation-Passing style 是 lambda 演算的一种风格，其中函数从不 return。相反，您将程序的其余部分作为 lambda 参数传递给您的函数并继续执行它们。它允许您更好地控制执行流程并更轻松地定义各种流程改变结构（循环、协程等...）

但是，我想知道你是否可以用一种表达另一种表达方式？我见过的所有 CPS 风格的语言都有一个明确的 FIX 结构来定义递归。

是否因为在没有 FIX 的情况下无法在普通 CPS 中定义定点组合器（或类似的）？如果是这样，你知道这样的证据吗？
还是只是打字问题？
或者也许可行，但由于某些原因不切实际？
或者我只是没有找到可用的解决方案...？

我希望类似 Y 组合器的 CPS 函数 CPSY 可以这样工作：如果我定义一个Y-ready CPS函数，比如：

function Yready(this, return) = 
    return (lambda <args> . <body using 'this' as recursion>);

然后我将其放入 CPSY 以生成一个递归到自身的函数：

function CPSY(F, return) = ?????

CPSY(Yready,
    lambda rec . <body where 'rec' names 'lambda <args>' from above, but with the loop closed>
)

CPSY 应该是一个简单的延续传递风格的函数，它本身不依赖于任何递归。 Y-combinator 可以在没有内置递归的普通 lambda 演算中以这种方式定义。它也可以以某种形式存在于 CPS 中吗？

再次说明：我正在寻找一个类似组合器的函数CPSY，它：

将启用 CPS 函数的递归
它的定义不依赖于递归
它的定义以连续传递的方式给出（return在CPSY正文中的任何地方都没有 lambdas）

Answer 1

这是 "trivial solution"，不是 OP 想要的非递归 - 它留作比较。

如果您有一种提供递归绑定的语言，您可以为 CPS 函数定义 fix（此处使用 Haskell）：

Prelude> let fixC f = \c -> f (fixC f c) c
Prelude> :t fixC
fixC :: (t -> t1 -> t) -> t1 -> t
Prelude> let facC' = \rec c n -> if n == 0 then c 1 else c (n * rec (n-1))
Prelude> let facC = fixC facC'
Prelude> take 10 $ map (facC id) [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]

也许提供 fixC 作为原语会对性能产生影响，但是（如果你有延续表示而不仅仅是闭包），或者是因为 "traditional" lambda 演算没有名字对于可以递归使用的函数。

（可能还有一个更有效的变体类似于fix f = let x = f x in x。）

Answer 2

TL;DR：相同的应用顺序 Y 适用于以延续柯里化风格编写的 CPS 函数。

在组合式中，Y 的阶乘的通常定义当然是

_Y (\r -> \n -> { n==0 -> 1 ; n * r (n-1) })     , where
                               ___^______
_Y = \g -> (\x-> x x) (\x-> g (\n-> x x n))  -- for applicative and normal order

CPS 阶乘定义为

fact = \n k -> equals n 0         -- a conditional must expect two contingencies
                 (\True -> k 1) 
                 (\False -> decr n 
                                 (\n1-> fact n1          -- *** recursive reference
                                             (\f1-> mult n f1 k)))

CPS-Y 增加了额外的 contingency 参数（我说 "contingency" 是为了消除与真正延续的歧义).在方案中，

(define (mult a b k)     (k (* a b)))
(define (decr c   k)     (k (- c 1)))
(define (equals d e s f) (if (= d e) (s 1) (f 0)))

(((lambda (g) 
     ( (lambda (x) (x x))
       (lambda (x) (g (lambda (n k) ((x x) n k))))))

  (lambda (fact)
    (lambda (n k)
      (equals n 0 (lambda (_) (k 1))
                  (lambda (_) (decr n 
                                (lambda (n1) (fact n1
                                               (lambda (f1) (mult n f1 k))))))))))

  5 (lambda (x) (display x)) )

This returns 120.

当然，在通过 eta 收缩的自动柯里化惰性语言（但未类型化！）中，上述 CPS-Y 与常规 Y 本身 完全相同。

但是，如果我们的递归函数有两个实际参数，以及延续 ⁄ 偶然性——第三个呢？在类似 Scheme 的语言中，我们是否必须有另一个 Y，里面有 (lambda (n1 n2 k) ((x x) n1 n2 k)) ？

我们可以切换到总是有偶然性参数第一个，并且总是以柯里化的方式编码（每个函数只有一个参数，可能产生另一个这样的函数，或者一个最终的全部应用后的结果）。还有it works，也是：

(define (mult   k)   (lambda (x y) (k (* x y))))
(define (decr   k)   (lambda (x)   (k (- x 1))))
(define (equals s f) (lambda (x y) (if (= x y) (s) (f))))

((((lambda (g)                                ; THE regular,
     ( (lambda (x) (x x))                        ; applicative-order
       (lambda (x) (g (lambda (k) ((x x) k))))))   ; Y-combinator

   (lambda (fact)
    (lambda (k)
      (lambda (n)
        ((equals  (lambda () (k 1))
                  (lambda () ((decr (lambda (n1) 
                                        ((fact 
                                            (lambda (f1) ((mult k) n f1)))
                                         n1)))
                               n)))
          n 0)))))

   (lambda (x) (display x))) 
  5)

如果您的语言是键入的，也有一些方法 to type such a thing。或者，在无类型语言中，我们可以将所有参数打包在一个列表中。

Answer 3

continuation-passing-style中的匿名递归可以如下完成（使用JS6作为语言）：

// CPS wrappers
const dec = (n, callback)=>{
    callback(n - 1)
}
const mul = (a, b, callback)=>{
    callback(a * b)
}
const if_equal = (a, b, then, else_)=>{
    (a == b ? then : else_)()
}

// Factorial
const F = (rec, n, a, callback)=>{
    if_equal(n, 0,
        ()=>{callback(a)},
        ()=>{dec(n, (rn)=>{
            mul(a, n, (ra)=>{
                rec(rec, rn, ra, callback)
            })
        })
    })
}

const fact = (n, callback)=>{
    F(F, n, 1, callback)
}

// Demo
fact(5, console.log)

为了摆脱标签 F 的双重使用，我们可以使用像这样的效用函数：

const rec3 = (f, a, b, c)=>{
    f(f, a, b, c)
}
const fact = (n, callback)=>{
    rec3(F, n, 1, callback)
}

这允许我们内联 F:

const fact = (n, callback)=>{
    rec3((rec, n, a, callback)=>{
        if_equal(n, 0,
            ()=>{callback(a)},
            ()=>{dec(n, (rn)=>{
                mul(a, n, (ra)=>{
                    rec(rec, rn, ra, callback)
                })
            })
        })
    }, n, 1, callback)
}

我们可以继续内联 rec3 使 fact 独立：

const fact = (n, callback)=>{
    ((f, a, b, c)=>{
        f(f, a, b, c)
    })((rec, n, a, callback)=>{
        if_equal(n, 0,
            ()=>{callback(a)},
            ()=>{dec(n, (rn)=>{
                mul(a, n, (ra)=>{
                    rec(rec, rn, ra, callback)
                })
            })
        })
    }, n, 1, callback)
}

下面JavaScript用同样的方法实现for循环

const for_ = (start, end, func, callback)=>{
    ((rec, n, end, func, callback)=>{
        rec(rec, n, end, func, callback)
    })((rec, n, end, func, callback)=>{
        func(n, ()=>{
            if_equal(n, end, callback, ()=>{
                S(n, (sn)=>{
                    rec(rec, sn, end, func, callback)
                })
            })
        })
    }, start, end, func, callback)
}

它是我制作的完全异步 FizzBuzz 的一部分 https://gist.github.com/Recmo/1a02121d39ee337fb81fc18e735a0d9e

Answer 4

让我们先推导 lambda 演算中正常阶求值的 CPS-Y，然后将其转换为应用阶。

Wikipedia page 通过以下等式定义定点组合子 Y：

Y f = f (Y f)

在 CPS 形式中，这个等式看起来像这样：

Y f k = Y f (λh. f h k)

现在，考虑以下 Y 的非 CPS 正序定义：

Y f = (λg. g g) (λg. f (g g))

将其转换为 CPS：

Y f k = (λg. g g k) (λg.λk. g g (λh. f h k))

现在，对这个定义进行 beta-reduce 几次，以检查它是否确实满足上面的“CPS 不动点”条件：

Y f k = (λg. g g k) (λg.λk. g g (λh. f h k))
      = (λg.λk. g g (λh. f h k)) (λg.λk. g g (λh. f h k)) k
      = (λg.λk. g g (λh. f h k)) (λg.λk. g g (λh. f h k)) (λh. f h k)
      = Y f (λh. f h k)

瞧！

现在，对于应用顺序评估，我们当然需要稍微改变一下。这里的推理与非 CPS 情况相同：我们需要“thunk”递归 (g g k) 调用并仅在下次调用时继续：

Y f k = (λg. g g k) (λg.λk. f (λx.λk. g g (λF. F x k)) k)

这里直接翻译成 Racket：

(define (Y f k)
  ((λ (g) (g g k))
   (λ (g k) (f (λ (x k) (g g (λ (F) (F x k)))) k))))

我们可以检查它是否确实有效——例如，这是 CPS 中的递归三角数计算（为了简单起见，算术运算除外）：

(Y (λ (sum k) (k (λ (n k) (if (< n 1)
                              (k 0)
                              (sum (- n 1) (λ (s) (k (+ s n))))))))
   (λ (sum) (sum 9 print)))
;=> 45

我相信这回答了问题。

在 Continuation Passing Style 中定义定点组合器

Define fix-point combinator in Continuation Passing Style

functional-programming

scheme

continuation-passing

fixpoint-combinators