9
  • 定点组合器是引入递归的非常有用的工具。
  • Continuation-Passing 风格是一种 lambda 演算风格，其中函数永远不会返回。相反，您将程序的其余部分作为 lambda 参数传递给您的函数并继续执行它们。它使您可以更好地控制执行流程并更轻松地定义各种流程更改结构（循环、协程等）

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

  • 是因为不可能在普通 CPS 中定义定点组合器（或类似的），没有FIX？如果是这样，你知道这件事的证据吗？
  • 或者仅仅是因为打字问题？
  • 或者也许这是可能的，但由于某种原因不切实际？
  • 或者我根本没有找到一个解决方案......？

我希望类似 Y-combinator 的 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 函数的递归
  • 它的定义不依赖递归
  • 它的定义以连续传递样式给出（在 的主体内任何地方都没有返回 lambda CPSY）
4

4 回答 4

3

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增加了额外的偶然性论证（我说“偶然性”是为了消除与真正延续的歧义）。在方案中，

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

这将返回 120。

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

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

我们可以切换到总是首先使用应急参数，并且总是以柯里化的方式编码（每个函数只有一个参数，可能会产生另一个这样的函数，或者应用完之后的最终结果）。它也有效：

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

如果你的语言是输入的，也有办法输入这样的东西。或者，在无类型语言中，我们可以将所有参数打包在一个列表中。

于 2016-03-11T01:14:57.430 回答
3

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

维基百科页面通过以下等式定义定点组合子 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 情况相同：我们需要“重击”递归(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

我相信这回答了这个问题。

于 2017-05-03T06:55:48.793 回答
2

延续传递风格的匿名递归可以如下完成（使用 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)
}

这是我制作的完全异步 FizzBu​​zz 的一部分https://gist.github.com/Recmo/1a02121d39ee337fb81fc18e735a0d9e

于 2017-02-01T09:02:09.210 回答
1

这是“简单的解决方案”，而不是 OP 想要的非递归解决方案——它留作比较。

如果你有一种提供递归绑定的语言，你可以fix为 CPS 函数定义（这里使用 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会对性能产生影响（如果您的延续不仅仅表示为闭包），或者是由于“传统” lambda 演算没有可以递归使用的函数的名称。

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

于 2016-03-10T19:11:01.317 回答