如何将跳板适应于Continuation Passing Style？

Question

这是一个天真的右折叠实现:

const foldr = f => acc => ([x, ...xs]) =>
  x === undefined
    ? acc 
    : f(x) (foldkr(f) (acc) (xs));

这是非尾递归，因此我们不能应用跳板。一种方法是使算法变成迭代的，并使用堆栈来模拟函数调用堆栈。

另一种方法是将递归转换为 CPS：

const Cont = k => ({runCont: k});

const foldkr = f => acc => ([x, ...xs]) =>
  Cont(k =>
    x === undefined
      ? k(acc)
      : foldkr(f) (acc) (xs)
          .runCont(acc_ => k(f(x) (acc_))));

这种方法还比较简单，但速度非常慢。以下是一个较少占用内存的版本：

const foldkr = f => acc => xs => {
  const go = i =>
    Cont(k =>
      i === xs.length
        ? k(acc)
        : go(i + 1)
            .runCont(acc_ => k(f(xs[i]) (acc_))));

  return go(0);
};

递归调用现在处于尾部位置，因此我们应该能够应用我们选择的跳板（trampoline）：

const loop = f => {
  let step = f();

  while (step && step.type === recur)
    step = f(...step.args);

  return step;
};

const recur = (...args) =>
  ({type: recur, args});

const foldkr = f => acc => xs =>
  loop((i = 0) => 
    Cont(k =>
      i === xs.length
        ? k(acc)
        : recur(i + 1)
            .runCont(acc_ => k(f(xs[i]) (acc_)))));

这种方法不可行，因为跳板调用在 continuation 内部，因此会进行惰性评估。如何改进跳板以使其与 CPS 协同工作？

- user5536315

---

除非您将f变为惰性求值或从右侧迭代，否则无法进行有效的右折叠。 - Bergi

@Bergi你的意思是第二个参数像Haskell中的lazy吗？ - user5536315

go(i + 1).runCont(...) 不在尾部位置具有 go - runCont 是尾调用。 - Mulan

@user633183 你确定吗？因为如果没有 Cont 包装器，那只会是另一个函数调用。 - user5536315

啊，这可能是尾递归取模 Cont。 - user5536315

是的，非常确定；go() 运行并完成后会返回 {runCont: ...}，然后调用 .runCont(...)。 - Mulan

Answer 1

尾调用优先（第一部分）

首先将循环编写为在尾部位置递归。

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              )
   )

给定两个参数small和large，我们测试foldr函数 -

const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => RangeError: Maximum call stack size exceeded

但它使用了跳板，为什么对于large会失败？简短的答案是因为我们构建了一个巨大的延迟计算，k...

loop
  ( ( i = 0
    , k = identity // base computation
    ) =>
      // ...
      recur // this gets called 20,000 times
        ( i + 1
        , r => k (f (r, xs[i])) // create new k, deferring previous k
        )
  )

在终止条件下，我们最终调用k（init），它会触发一系列延迟计算栈，深度为20,000个函数调用，这将导致堆栈溢出。

在继续阅读之前，请展开下面的片段以确保我们在同一页面上 -

const identity = x =>
  x
  
const loop = f =>
{ let r = f ()
  while (r && r.recur === recur)
    r = f (...r.values)
  return r
}

const recur = (...values) =>
  ({ recur, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? k (init)
          : recur
              ( i + 1
              , r => k (f (r, xs[i]))
              )
   )

const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, large))
// RangeError: Maximum call stack size exceeded

---

延迟溢出

我们在这里看到的问题，就是当你将 compose(...) 或 pipe(...) 连接20,000个函数时可能会遇到的问题 -

// build the composition, then apply to 1
foldl ((r, f) => (x => f (r (x))), identity, funcs) (1)

或使用comp来实现类似效果 -

const comp = (f, g) =>
  x => f (g (x))

// build the composition, then apply to 1
foldl (comp, identity, funcs) 1

当然，foldl非常安全，并且它可以组合20,000个函数，但是一旦你调用这个庞大的组合，就可能会造成栈溢出。现在我们来对比一下 -

// starting with 1, fold the list; apply one function at each step
foldl ((r, f) => f (r), 1, funcs)

该算法不会因为计算未被延迟而耗尽堆栈。相反，一个步骤的结果会覆盖前一个步骤的结果，直到达到最终步骤。

实际上，当我们编写代码时-

r => k (f (r, xs[i]))

另一种看待这个问题的方式是 -

comp (k, r => f (r, xs[i]))

这将准确地突出问题出在哪里。

---

可能的解决方案

一个简单的解决方法是添加一个单独的call标签，它会将延迟计算在跳板中展开。因此，不直接调用函数如f (x)，而是写成call (f, x) -

const call = (f, ...values) =>
  ({ call, f, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          // k (init) rewrite as
          ? call (k, init)
          : recur
              ( i + 1
              // r => k (f (r, xs[i])) rewrite as
              , r => call (k, f (r, xs[i]))
              )
   )

我们修改蹦床(trampoline)以对call标记值进行操作。

const loop = f =>
{ let r = f ()
  while (r)
    if (r.recur === recur)
      r = f (...r.values)
    else if (r.call === call)
      r = r.f (...r.values)
    else
      break
  return r
}

最后，我们看到large输入不再导致堆栈溢出 -

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => (Press "Run snippet" below see results ...)

const identity = x =>
  x
  
const loop = f =>
{ let r = f ()
  while (r)
    if (r.recur === recur)
      r = f (...r.values)
    else if (r.call === call)
      r = r.f (...r.values)
    else
      break
  return r
}

const recur = (...values) =>
  ({ recur, values })
  
const call = (f, ...values) =>
  ({ call, f, values })

const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , k = identity
      ) =>
        i >= xs.length 
          ? call (k, init)
          : recur
              ( i + 1
              , r => call (k, f (r, xs[i]))
              )
   )
   
const small =
  [ 1, 2, 3 ]

const large =
  Array.from (Array (2e4), (_, n) => n + 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console.log(foldr ((a, b) => `(${a}, ${b})`, 0, large))
// (Press "Run snippet" to see results ...)

---

哇，你建立了自己的评估器

在上面，recur和call看起来像是魔法函数。但实际上，recur和call创建简单对象{ ... }，而loop则完成所有工作。这样，loop就是一种接受recur和call 表达式的评估器。唯一的缺点是我们希望调用者总是在尾部位置使用recur或call，否则循环将返回不正确的结果。

这与Y组合器不同，后者将递归机制作为参数具象化，并且不仅限于类似于这里的recur只能在尾部位置使用的情况。

const Y = f => f (x => Y (f) (x))

const fib = recur => n =>
  n < 2
    ? n
    : recur (n - 1) + recur (n - 2) // <-- non-tail call supported
    
console .log (Y (fib) (30))
// => 832040

Y 的一个缺点是，由于您通过 调用函数 来控制递归，因此您仍然像 JS 中的所有其他函数一样不安全。结果就是堆栈溢出 -

console .log (Y (fib) (100))
// (After a long time ...)
// RangeError: Maximum call stack size exceeded

那么在非尾部位置支持recur并保持堆栈安全，这是可能的吗？当然可以，一个足够聪明的loop应该能够评估递归表达式-

const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              ) 
    )

fib (30)
// expected: 832040

loop变成一个CPS尾递归函数，用于评估输入表达式call，recur等。然后我们将loop放在一个跳板上。 loop实际上成为我们自定义语言的求值器。现在您可以忘记所有关于堆栈的限制 - 您唯一的限制是内存！

另外一种替代方案-

const fib = (n = 0) =>
  n < 2
    ? n
    : call
        ( (a, b) => a + b
        , call (fib, n - 1)
        , call (fib, n - 2)
        )

loop (fib (30))
// expected: 832040

在这个相关的问答中，我使用JavaScript编写了一个未类型化lambda演算的正常序求值器。它展示了如何编写不受宿主语言实现影响（求值策略、堆栈模型等）的程序。在那里我们使用Church编码，在这里我们使用call和recur，但技术是相同的。

多年前，我使用上述技术编写了一个堆栈安全的变体。我将看看是否能使其复活，并随后在此回答中提供它。目前，我将把loop求值器作为读者的练习留下。

第二部分添加：循环求值器

---

可选方案 在这个相关的问答中，我们构建了一个堆栈安全的continuation monad。

- Mulan

---

我认识你已经三年了，至今仍像初次见面时一样惊叹。你的代码（以及其中蕴含的思想）是美妙心灵的具体化。祝福跨越大洋送到。 - user5536315

你的话对我来说意义重大。感谢你给了我一个机会与志同道合的人讨论这些想法和问题。我从我们的交流中学到了很多。干杯！ - Mulan

抱歉，我忍不住又添加了一个更直接回答你问题的答案。 - Mulan

Answer 2

是的，是的，还是的（第二部分）

因此，我相信这个答案更接近您的问题的核心-我们是否可以使 任何 递归程序具有堆栈安全性？即使递归不在尾部位置？即使宿主语言没有尾调用消除？是的。是的。而且是的-只需一个小要求...

我的第一个答案的结尾谈到了loop作为一种评估器，然后描述了如何实现的大致想法。理论听起来不错，但我想确保该技术在实践中有效。所以我们开始吧！

---

非平凡程序

斐波那契数列很适合这个问题。二进制递归实现会构建一个庞大的递归树，而且每个递归调用都不在尾部位置。如果我们能正确地编写这个程序，就可以有合理的信心我们正确地实现了loop。

这里有一个小要求：您不能调用函数进行递归。而是使用call (f, x)代替f(x)。

const add = (a = 0, b = 0) =>
  a + b

const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          <del>: add (recur (n - 1), recur (n - 2))</del>
          : call (add, recur (n - 1), recur (n - 2))
    )

fib (10)
// => 55

但是这些call和recur函数并没有什么特别之处。它们只创建普通的JS对象。

const call = (f, ...values) =>
  ({ type: call, f, values })

const recur = (...values) =>
  ({ type: recur, values })

在这个程序中，我们有一个依赖于两个recur的call。每个recur都有可能生成另一个call和额外的recur。这确实是一个非平凡的问题，但实际上我们只是处理一个定义明确的递归数据结构。

---

编写循环

如果循环要处理这个递归数据结构，最简单的方式是将循环编写成递归程序。但我们不会在其他地方遇到堆栈溢出问题吗？让我们来看看！

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b 
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? // todo: when given { type: recur, ... }
  : expr.type === call
      ? // todo: when given { type: call, ... }
  : k (expr) // default: non-tagged value; no further evaluation necessary

  return aux1 (f ())
}

所以loop接受一个要循环的函数f。我们期望f在计算完成时返回普通的JS值。否则，返回call或recur来增加计算。

这些待办事项有点琐碎，现在让我们填写它们 -

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b 
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? aux (expr.values, values => aux1 (f (...values), k))
  : expr.type === call
      ? aux (expr.values, values => aux1 (expr.f (...values), k))
  : k (expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    // todo: implement me

  return aux1 (f ())
}

直观来说，aux1（“辅助一”）就是我们在一个表达式expr上挥舞的魔棒，然后result会在延续中返回。换句话说 -

// evaluate expr to get the result
aux1 (expr, result => ...)

为了评估recur或call，我们必须先评估相应的values。我们希望能够写出类似于以下内容的东西 -

// can't do this!
const r =
  expr.values .map (v => aux1 (v, ...))

return k (expr.f (...r))

接下来的...是什么内容？我们不能像那样在.map中调用aux1。相反，我们需要另一种神奇的工具，可以采取表达式数组，并将结果值传递给其续集，如aux。

// evaluate each expression and get all results as array
aux (expr.values, values => ...)

---

肉和土豆

好的，这可能是问题中最困难的部分。对于输入数组中的每个表达式，我们必须调用aux1并将延续链接到下一个表达式，最后将值传递给用户提供的延续k。

// aux : (('a expr) array, 'a array -> 'b) -> 'b
const aux = (exprs = [], k) =>
  exprs.reduce
    ( (mr, e) =>
        k => mr (r => aux1 (e, x => k ([ ...r, x ])))
    , k => k ([])
    )
    (k)

我们最终不会使用这个，但它有助于将我们在aux中进行的操作表达为普通的reduce和append。

// cont : 'a -> ('a -> 'b) -> 'b
const cont = x =>
  k => k (x)

// append : ('a array, 'a) -> 'a array
const append = (xs, x) =>
  [ ...xs, x ]

// lift2 : (('a, 'b) -> 'c, 'a cont, 'b cont) -> 'c cont
const lift2 = (f, mx, my) =>
  k => mx (x => my (y => k (f (x, y))))

// aux : (('a expr) array, 'a array -> 'b) -> 'b
const aux = (exprs = [], k) =>
  exprs.reduce
    ( (mr, e) =>
        lift2 (append, mr, k => aux1 (e, k))
    , cont ([])
    )

将所有内容组合在一起，我们得到 -

// identity : 'a -> 'a
const identity = x =>
  x

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b 
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? aux (expr.values, values => aux1 (f (...values), k))
  : expr.type === call
      ? aux (expr.values, values => aux1 (expr.f (...values), k))
  : k (expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    exprs.reduce
      ( (mr, e) =>
          k => mr (r => aux1 (e, x => k ([ ...r, x ])))
      , k => k ([])
      )
      (k)

  return aux1 (f ())
}

是时候庆祝一下了 -

fib (10)
// => 55

但只有一点点 -

fib (30)
// => RangeError: Maximum call stack size exceeded

---

你的原始问题

在我们尝试修复loop之前，让我们重新审视你问题中的程序foldr，并看看如何使用loop、call和recur表达它-

const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          <del>: f (recur (i + 1), xs[i])</del>
          : call (f, recur (i + 1), xs[i])
    )

它是如何工作的？

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => RangeError: Maximum call stack size exceeded

好的，对于small它可以工作，但是对于large它会导致堆栈溢出。但这正是我们所期望的，对吗？毕竟，loop只是一个普通的递归函数，注定会发生堆栈溢出……对吗？

在继续之前，请在您自己的浏览器中验证到此为止的结果 -

// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
  ({ type: call, f, values })

// recur : * -> 'a expr
const recur = (...values) =>
  ({ type: recur, values })

// identity : 'a -> 'a
const identity = x =>
  x

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? aux (expr.values, values => aux1 (f (...values), k))
  : expr.type === call
      ? aux (expr.values, values => aux1 (expr.f (...values), k))
  : k (expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    exprs.reduce
      ( (mr, e) =>
          k => mr (r => aux1 (e, x => k ([ ...r, x ])))
      , k => k ([])
      )
      (k)

  return aux1 (f ())
}

// fib : number -> number
const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              )
    )

// foldr : (('b, 'a) -> 'b, 'b, 'a array) -> 'b
const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          : call (f, recur (i + 1), xs[i])
    )

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

console .log (fib (10))
// 55

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, large))
// RangeError: Maximum call stack size exc

---

反弹循环

我在转换函数为CPS并使用跳板来反弹的答案上得到了太多的答案。本答案不会过多涉及此类内容。如上所示，我们有aux1和aux作为CPS尾递归函数。可以通过机械方式完成以下转换。

与我们在其他答案中所做的一样，对于每个函数调用f（x），将其转换为call（f，x） -

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  <del>return aux1 (f ())</del>
  return run (aux1 (f ()))
}

将return包装在run中，这是一个简化的跳板 -

// run : * -> *
const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

现在它是如何工作的？

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

fib (30)
// 832040

foldr ((a, b) => `(${a}, ${b})`, 0, small)
// => (((0, 3), 2), 1)

foldr ((a, b) => `(${a}, ${b})`, 0, large)
// => (Go and see for yourself...)

通过扩展和运行下面的片段，您可以在任何JavaScript程序中见证堆栈安全递归 -

// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
  ({ type: call, f, values })

// recur : * -> 'a expr
const recur = (...values) =>
  ({ type: recur, values })

// identity : 'a -> 'a
const identity = x =>
  x

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  // aux : (('a expr) array, 'a array -> 'b) -> 'b
  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return run (aux1 (f ()))
}

// run : * -> *
const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

// fib : number -> number
const fib = (init = 0) =>
  loop
    ( (n = init) =>
        n < 2
          ? n
          : call
              ( (a, b) => a + b
              , recur (n - 1)
              , recur (n - 2)
              )
    )

// foldr : (('b, 'a) -> 'b, 'b, 'a array) -> 'b
const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          : call (f, recur (i + 1), xs[i])
    )

// small : number array
const small =
  [ 1, 2, 3 ]

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

console .log (fib (30))
// 832040

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, small))
// (((0, 3), 2), 1)

console .log (foldr ((a, b) => `(${a}, ${b})`, 0, large))
// YES! YES! YES!

---

评估可视化

使用foldr评估一个简单的表达式，看看我们是否能窥探loop的奥秘。

const add = (a, b) =>
  a + b

foldr (add, 'z', [ 'a', 'b' ])
// => 'zba'

您可以将此复制到支持括号高亮的文本编辑器中以跟随–

// =>
aux1
  ( call (add, recur (1), 'a')
  , identity
  )

// =>
aux1
  ( { call
    , f: add
    , values:
        [ { recur, values: [ 1 ]  }
        , 'a'
        ]
    }
  , identity
  )

// =>
aux
  ( [ { recur, values: [ 1 ]  }
    , 'a'
    ]
  , values => aux1 (add (...values), identity)
  )

// =>
[ { recur, values: [ 1 ]  }
, 'a'
]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (add (...values), identity))

// beta reduce outermost k
(k => (k => (k => k ([])) (r => aux1 ({ recur, values: [ 1 ]  }, x => k ([ ...r, x ])))) (r => aux1 ('a', x => k ([ ...r, x ])))) (values => aux1 (add (...values), identity))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 ({ recur, values: [ 1 ]  }, x => k ([ ...r, x ])))) (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ])))

// beta reduce outermost k
(k => k ([])) (r => aux1 ({ recur, values: [ 1 ]  }, x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 ({ recur, values: [ 1 ]  }, x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...r, x ]))) ([])

// =>
aux1
  ( { recur, values: [ 1 ]  }
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux
  ( [ 1 ]
  , values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))
  )

// =>
[ 1 ]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 (1, x => k ([ ...r, x ])))) (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => k ([])) (r => aux1 (1, x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 (1, x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([])

// =>
aux1
  ( 1
  , x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])) (1)

// =>
(values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], 1 ])

// =>
(values => aux1 (f (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ 1 ])

// =>
aux1
  ( f (...[ 1 ])
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( f (1)
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( call (add, recur (2), 'b')
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( { call
    , f: add
    , values:
        [ { recur, values: [ 2 ] }
        , 'b'
        ]
    }
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux
  ( [ { recur, values: [ 2 ] }
    , 'b'
    ]
  , values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))
  )

// =>
[ { recur, values: [ 2 ] }
, 'b'
]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => (k => k ([])) (r => aux1 ({ recur, values: [ 2 ] }, x => k ([ ...r, x ])))) (r => aux1 ('b', x => k ([ ...r, x ])))) (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 ({ recur, values: [ 2 ] }, x => k ([ ...r, x ])))) (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ])))

// beta reduce outermost k
(k => k ([])) (r => aux1 ({ recur, values: [ 2 ] }, x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 ({ recur, values: [ 2 ] }, x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...r, x ]))) ([])

// =>
aux1
  ( { recur, values: [ 2 ] }
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux
  ( [ 2 ]
  , values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))
  )

// =>
[ 2 ]
.reduce
  ( (mr, e) =>
      k => mr (r => aux1 (e, x => k ([ ...r, x ])))
  , k => k ([])
  )
(values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => (k => k ([])) (r => aux1 (2, x => k ([ ...r, x ])))) (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ]))))

// beta reduce outermost k
(k => k ([])) (r => aux1 (2, x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ])))

// beta reduce outermost r
(r => aux1 (2, x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([])

// =>
aux1
  ( 2
  , x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], x ])) (2)

// spread []
(values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[], 2 ])

// beta reduce outermost values
(values => aux1 (f (...values), (x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])))) ([ 2 ])

// spread [ 2 ]
aux1
  ( f (...[ 2 ])
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( f (2)
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( 'z'
  , x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], x ])) ('z')

// spread []
(r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ ...[], 'z' ])

// beta reduce outermost r
(r => aux1 ('b', x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...r, x ]))) ([ 'z' ])

// =>
aux1
  ( 'b'
  , x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[ 'z' ], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[ 'z' ], x ])) ('b')

// spread ['z']
(values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ ...[ 'z' ], 'b' ])

// beta reduce outermost values
(values => aux1 (add (...values), (x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])))) ([ 'z', 'b' ])

// =>
aux1
  ( add (...[ 'z', 'b' ])
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( add ('z', 'b')
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// =>
aux1
  ( 'zb'
  , x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])
  )

// beta reduce outermost x
(x => (r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], x ])) ('zb')

// spead []
(r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ ...[], 'zb' ])

// beta reduce outermost r
(r => aux1 ('a', x => (values => aux1 (add (...values), identity)) ([ ...r, x ]))) ([ 'zb' ])

// =>
aux1
  ( 'a'
  , x => (values => aux1 (f (...values), identity)) ([ ...[ 'zb' ], x ])
  )

// beta reduce outermost x
(x => (values => aux1 (f (...values), identity)) ([ ...[ 'zb' ], x ])) ('a')

// spead ['zb']
(values => aux1 (f (...values), identity)) ([ ...[ 'zb' ], 'a' ])

// beta reduce values
(values => aux1 (f (...values), identity)) ([ 'zb', 'a' ])

// spread [ 'zb', 'a' ]
aux1
  ( f (...[ 'zb', 'a' ])
  , identity
  )

// =>
aux1
  ( f ('zb', 'a')
  , identity
  )

// =>
aux1
  ( 'zba'
  , identity
  )

// =>
identity ('zba')

// =>
'zba'

闭包确实很神奇。以上，我们可以确认CPS保持了计算的平稳性：我们在每一步中都看到aux、aux1或简单的beta规约。这就是使我们能够将loop放在一个反弹器上的原因。

这就是我们对call进行双重利用的地方。我们使用call为我们的循环计算创建一个对象，但aux和aux1也会产生由run处理的call。我本可以（也许应该）为此制作不同的标签，但call足够通用，可以在两个地方使用。

所以，当我们看到aux (...)和aux1 (...)以及beta规约(x => ...) (...)时，我们只需将它们分别替换为call (aux, ...)、call (aux1, ...)和call (x => ..., ...)。将它们传递给run，这就是——任何形式的堆栈安全递归。就这么简单。

---

调优与优化

我们可以看到，虽然是一个小程序，但loop在保持您的思维不受堆栈问题困扰方面做了大量的工作。我们还可以看到loop不是最高效的；特别是我们注意到有大量的剩余参数和展开参数（...），这些都是昂贵的。如果我们可以在没有它们的情况下编写loop，我们可以期望看到巨大的内存和速度提升 -

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
  { switch (expr.type)
    { case recur:
        // rely on aux to do its magic
        return call (aux, f, expr.values, k)
      case call:
        // rely on aux to do its magic
        return call (aux, expr.f, expr.values, k)
      default:
        return call (k, expr)
    }
  }

  // aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
  const aux = (f, exprs = [], k) =>
  { switch (exprs.length)
    { case 0: // nullary continuation
        return call (aux1, f (), k) 
      case 1: // unary
        return call
          ( aux1
          , exprs[0]
          , x => call (aux1, f (x), k) 
          )
      case 2: // binary
        return call
          ( aux1
          , exprs[0]
          , x =>
            call
              ( aux1
              , exprs[1]
              , y => call (aux1, f (x, y), k) 
              )
          )
      case 3: // ternary ...
      case 4: // quaternary ...
      default: // variadic
        return call
          ( exprs.reduce
              ( (mr, e) =>
                  k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
              , k => call (k, [])
              )
          , values => call (aux1, f (...values), k)
          )
    }
  }

  return run (aux1 (f ()))
}

现在，我们只有在用户编写的循环或连续具有超过四（4）个参数时才使用rest/spread (...)。这意味着我们可以避免在最常见的情况下使用高昂的可变参数提升.reduce。我还注意到，与链接的三元?:表达式O(n)相比，switch提供了速度改进(O(1))。

这使得loop的定义变得更加复杂，但这种权衡是非常值得的。初步测量显示，速度提高了100%以上，内存减少了50%以上-

// before
fib(30)      // 5542.26 ms (25.7 MB)
foldr(20000) //  104.96 ms (31.07 MB)

// after
fib(30)      // 2472.58 ms (16.29 MB)
foldr(20000) //   45.33 ms (12.19 MB)

当然，有许多方法可以优化loop，但这个练习的重点不在于向您展示所有这些方法。 loop是一个明确定义的纯函数，它使您可以自由地进行必要的重构。

第3部分添加：增加循环的功能

- Mulan

---

通过这种语言的手段扩展语言的基本边界——我以前认为这是不可能的，我会在接下来的几天里花费它应有的时间来仔细阅读你的答案。谢谢！ - user5536315

非常感谢！说实话，当我看到所有的工作都在运行时，我感觉非常好。我修复了aux中的一个小错误，它以错误的顺序调用连续体（将[x，...r]更改为[...r，x]）。我注意到foldr可以从call（r => f（r，xs [i]），recur（i + 1））简化为call（f，recur（i + 1），xs [i]）-这是一个很大的改进，我认为。 - Mulan

我从未想过像Racket这样的语言如何承诺为非尾递归程序提供堆栈安全的递归。现在我可以说我终于明白这种事情是如何可能的了！ - Mulan

Answer 3

隐藏的力量（第三部分）

在我们上一个回答中，我们使得使用自然表达式编写foldr成为可能，并且即使递归调用不在尾部位置，计算仍保持堆栈安全 -

// foldr : (('b, 'a) -> 'b, 'b, 'a array) -> 'b
const foldr = (f, init, xs = []) =>
  loop
    ( (i = 0) =>
        i >= xs.length
          ? init
          : call (f, recur (i + 1), xs[i])
    )

这是可能的，因为loop实际上是call和recur表达式的求值器。但在过去的一天里发生了一些令人惊讶的事情。我意识到loop在表面下还有更多潜力...

---

第一类continuations 使用延续传递风格使得具有堆栈安全的loop成为可能，并且我意识到我们可以具体化其延续并使其可用于loop用户：你 -

<b>// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
  ({ type: shift, f })

// reset : 'a expr -> 'a
const reset = (expr = {}) =>
  loop (() => expr)</b>

const loop = f =>
{ const aux1 = (expr = {}, k = identity) =>
  { switch (expr.type)
    { case recur: // ...
      case call: // ...

      <b>case shift:
        return call
          ( aux1
          , expr.f (x => run (aux1 (x, k)))
          , identity
          )</b>

      default: // ...
    }
  }

  const aux = // ...

  return run (aux1 (f ()))
}

---

例子

在这个第一个例子中，我们用 k 捕获了继续执行的表达式 add(3, ...)（或3 + ?）。

reset
  ( call
      ( add
      , 3
      , shift (k => k (k (1)))
      )
  )

// => 7

我们将k应用于1，然后将其结果再次应用于k-

//        k(?)  = (3 + ?)
//    k (k (?)) = (3 + (3 + ?))
//          ?   = 1
// -------------------------------
// (3 + (3 + 1))
// (3 + 4)
// => 7

捕获的延续可以在表达式中任意深入。这里我们捕获了延续(1 + 10 * ?) -

reset
  ( call
      ( add
      , 1
      , call
          ( mult
          , 10
          , shift (k => k (k (k (1))))
          )
      )
  )

// => 1111

在这里，我们将对输入为 1 的内容应用连续三次的k-

//       k (?)   =                     (1 + 10 * ?)
//    k (k (?))  =           (1 + 10 * (1 + 10 * ?))
// k (k (k (?))) = (1 + 10 * (1 + 10 * (1 + 10 * ?)))
//          ?    = 1
// ----------------------------------------------------
// (1 + 10 * (1 + 10 * (1 + 10 * 1)))
// (1 + 10 * (1 + 10 * (1 + 10)))
// (1 + 10 * (1 + 10 * 11))
// (1 + 10 * (1 + 110))
// (1 + 10 * 111)
// (1 + 1110)
// => 1111

到目前为止，我们一直在捕获一个 continuation，k，然后应用它，k (...)。现在看看当我们以不同的方式使用 k 时会发生什么 -

// r : ?
const r =
  loop
    ( (x = 10) =>
        shift (k => ({ value: x, next: () => k (recur (x + 1))}))
    )

r
// => { value: 10, next: [Function] }

r.next()
// => { value: 11, next: [Function] }

r.next()
// => { value: 11, next: [Function] }

r.next().next()
// => { value: 12, next: [Function] }

出现了一个野生的无状态迭代器！事情开始变得有趣了...

---

harvest and yield

JavaScript 生成器允许我们使用 yield 关键字表达式产生一系列懒惰计算的值。然而，当 JS 生成器进入下一个状态时，它会永久性地改变。

const gen = function* ()
{ yield 1
  yield 2
  yield 3
}

const iter = gen ()

console.log(Array.from(iter))
// [ 1, 2, 3 ]

console.log(Array.from(iter))
// [] // <-- iter already exhausted!

iter是不纯的，每次针对Array.from都会产生不同的输出。这意味着JS迭代器不能共用。如果你想在多个地方使用迭代器，你必须每次重新计算完整的gen -

console.log(Array.from(gen()))
// [ 1, 2, 3 ]

console.log(Array.from(gen()))
// [ 1, 2, 3 ]

正如我们在使用 `shift` 的示例中看到的那样，我们可以多次重复使用相同的 continuation 或保存它并稍后调用它。 我们可以有效地实现自己的 `yield`，但是没有这些讨厌的限制。 下面我们将其称为 `stream` -

// emptyStream : 'a stream
const emptyStream =
  { value: undefined, next: undefined }

// stream : ('a, 'a expr) -> 'a stream
const stream = (value, next) =>
  shift (k => ({ value, next: () => k (next) }))

现在我们可以编写自己的惰性流，就像这样 -

// numbers : number -> number stream
const numbers = (start = 0) =>
  loop
    ( (n = start) =>
        stream (n, recur (n + 1))
    )

// iter : number stream
const iter =
  numbers (10)

iter
// => { value: 10, next: [Function] }

iter.next()
// => { value: 11, next: [Function] }

iter.next().next()
// => { value: 12, next: [Function] }

---

高阶流函数

stream 构建一个迭代器，其中 value 是当前值，next 是生成下一个值的函数。我们可以编写高阶函数比如 filter，它接受一个过滤函数 f 和一个输入迭代器 iter，并产生一个新的惰性流 -

// filter : ('a -> boolean, 'a stream) -> 'a stream
const filter = (f = identity, iter = {}) =>
  loop
    ( ({ value, next } = iter) =>
        next
          ? f (value)
            ? stream (value, recur (next ()))
            : recur (next ())
          : emptyStream
    )

const odds =
  filter (x => x & 1 , numbers (1))

odds
// { value: 1, next: [Function] }

odds.next()
// { value: 3, next: [Function] }

odds.next().next()
// { value: 5, next: [Function] }

我们将使用take来限制无限流到20,000个元素，然后使用toArray将流转换为数组-

// take : (number, 'a stream) -> 'a stream
const take = (n = 0, iter = {}) =>
  loop
    ( ( m = n
      , { value, next } = iter
      ) =>
        m && next
          ? stream (value, recur (m - 1, next ()))
          : emptyStream
    )

// toArray : 'a stream -> 'a array
const toArray = (iter = {}) =>
  loop
    ( ( r = []
      , { value, next } = iter
      ) =>
        next
          ? recur (push (r, value), next ())
          : r
    )

toArray (take (20000, odds))
// => [ 1, 3, 5, 7, ..., 39999 ]

这只是一个开始。我们还可以做许多其他的流操作和优化来增强可用性和性能。

---

高阶续体

有了一级续体，我们可以轻松地实现新的、有趣的计算方式。下面是一个著名的“模棱两可”运算符amb，用于表示非确定性计算 -

// amb : ('a array) -> ('a array) expr
const amb = (xs = []) =>
  shift (k => xs .flatMap (x => k (x)))

直观来说，amb 允许你评估一个模糊的表达式——可能没有返回结果[]，也可能有多个返回结果[...]。

// pythag : (number, number, number) -> boolean
const pythag = (a, b, c) =>
  a ** 2 + b ** 2 === c ** 2

// solver : number array -> (number array) array
const solver = (guesses = []) =>
  reset
    ( call
        ( (a, b, c) =>
            pythag (a, b, c) 
              ? [ [ a, b, c ] ] // <-- possible result
              : []              // <-- no result
        , amb (guesses)
        , amb (guesses)
        , amb (guesses)
      )
    )

solver ([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ])
// => [ [ 3, 4, 5 ], [ 4, 3, 5 ], [ 6, 8, 10 ], [ 8, 6, 10 ] ]

在这里再次使用amb来编写product -

// product : (* 'a array) -> ('a array) array
const product = (...arrs) =>
  loop
    ( ( r = []
      , i = 0
      ) =>
        i >= arrs.length
          ? [ r ]
          : call
              ( x => recur ([ ...r, x ], i + 1)
              , amb (arrs [i])
              )
    )


product([ 0, 1 ], [ 0, 1 ], [ 0, 1 ])
// [ [0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0], [1,0,1], [1,1,0], [1,1,1] ]

product([ 'J', 'Q', 'K', 'A' ], [ '♡', '♢', '♤', '♧' ])
// [ [ J, ♡ ], [ J, ♢ ], [ J, ♤ ], [ J, ♧ ]
// , [ Q, ♡ ], [ Q, ♢ ], [ Q, ♤ ], [ Q, ♧ ]
// , [ K, ♡ ], [ K, ♢ ], [ K, ♤ ], [ K, ♧ ]
// , [ A, ♡ ], [ A, ♢ ], [ A, ♤ ], [ A, ♧ ]
// ]

---

闭环

为了让这个答案与帖子相关，我们将使用一级续延重写foldr。当然，没人会像这样编写foldr，但我们想展示我们的续延是强大和完整的。

// 
const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , r = identity
      ) =>
        i >= xs.length
          ? r (init)
          : call
              ( f
              , shift (k => recur (i + 1, comp (r, k)))
              , xs[i]
              )
    )

foldr (add, "z", "abcefghij")
// => "zjihgfedcba"


foldr (add, "z", "abcefghij".repeat(2000))
// => RangeError: Maximum call stack size exceeded

这正是我们在第一个答案中提到的“延迟溢出”。但由于在这里我们完全控制着连续体，所以我们可以以安全的方式将它们链接起来。只需将上面的comp替换为compExpr，一切都按预期工作 -

// compExpr : ('b expr -> 'c expr, 'a expr -> 'b expr) -> 'a expr -> 'c expr
const compExpr = (f, g) =>
  x => call (f, call (g, x))

foldr (add, "z", "abcefghij".repeat(2000))
// => "zjihgfecbajihgfecbajihgf....edcba"

---

代码示例

展开下面的片段以在您自己的浏览器中验证结果 -

// identity : 'a -> 'a
const identity = x =>
  x

// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
  ({ type: call, f, values })

// recur : * -> 'a expr
const recur = (...values) =>
  ({ type: recur, values })

// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
  ({ type: shift, f })

// reset : 'a expr -> 'a
const reset = (expr = {}) =>
  loop (() => expr)

// amb : ('a array) -> ('a array) expr
const amb = (xs = []) =>
  shift (k => xs .flatMap (x => k (x)))

// add : (number, number) -> number
const add = (x = 0, y = 0) =>
  x + y

// mult : (number, number) -> number
const mult = (x = 0, y = 0) =>
  x * y

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
  { switch (expr.type)
    { case recur:
        return call (aux, f, expr.values, k)
      case call:
        return call (aux, expr.f, expr.values, k)
      case shift:
          return call
            ( aux1
            , expr.f (x => run (aux1 (x, k)))
            , identity
            )
      default:
        return call (k, expr)
    }
  }

  // aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
  const aux = (f, exprs = [], k) =>
  { switch (exprs.length)
    { case 0:
        return call (aux1, f (), k) // nullary continuation
      case 1:
        return call
          ( aux1
          , exprs[0]
          , x => call (aux1, f (x), k) // unary
          )
      case 2:
        return call
          ( aux1
          , exprs[0]
          , x =>
            call
              ( aux1
              , exprs[1]
              , y => call (aux1, f (x, y), k) // binary
              )
          )
      case 3: // ternary ...
      case 4: // quaternary ...
      default: // variadic
        return call
          ( exprs.reduce
              ( (mr, e) =>
                  k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
              , k => call (k, [])
              )
          , values => call (aux1, f (...values), k)
          )
    }
  }

  return run (aux1 (f ()))
}

// run : * -> *
const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

// example1 : number
const example1 =
  reset
    ( call
        ( add
        , 3
        , shift (k => k (k (1)))
        )
    )

// example2 : number
const example2 =
  reset
    ( call
        ( add
        , 1
        , call
            ( mult
            , 10
            , shift (k => k (k (1)))
            )
        )
    )

// emptyStream : 'a stream
const emptyStream =
  { value: undefined, next: undefined }

// stream : ('a, 'a expr) -> 'a stream
const stream = (value, next) =>
  shift (k => ({ value, next: () => k (next) }))

// numbers : number -> number stream
const numbers = (start = 0) =>
  loop
    ( (n = start) =>
        stream (n, recur (n + 1))
    )

// filter : ('a -> boolean, 'a stream) -> 'a stream
const filter = (f = identity, iter = {}) =>
  loop
    ( ({ value, next } = iter) =>
        next
          ? f (value)
            ? stream (value, recur (next ()))
            : recur (next ())
          : emptyStream
    )

// odds : number stream
const odds =
  filter (x => x & 1 , numbers (1))

// take : (number, 'a stream) -> 'a stream
const take = (n = 0, iter = {}) =>
  loop
    ( ( m = n
      , { value, next } = iter
      ) =>
        m && next
          ? stream (value, recur (m - 1, next ()))
          : emptyStream
    )

// toArray : 'a stream -> 'a array
const toArray = (iter = {}) =>
  loop
    ( ( r = []
      , { value, next } = iter
      ) =>
        next
          ? recur ([ ...r, value ], next ())
          : r
    )

// push : ('a array, 'a) -> 'a array
const push = (a = [], x = null) =>
  ( a .push (x)
  , a
  )

// pythag : (number, number, number) -> boolean
const pythag = (a, b, c) =>
  a ** 2 + b ** 2 === c ** 2

// solver : number array -> (number array) array
const solver = (guesses = []) =>
  reset
    ( call
        ( (a, b, c) =>
            pythag (a, b, c)
              ? [ [ a, b, c ] ] // <-- possible result
              : []              // <-- no result
        , amb (guesses)
        , amb (guesses)
        , amb (guesses)
      )
    )

// product : (* 'a array) -> ('a array) array
const product = (...arrs) =>
  loop
    ( ( r = []
      , i = 0
      ) =>
        i >= arrs.length
          ? [ r ]
          : call
              ( x => recur ([ ...r, x ], i + 1)
              , amb (arrs [i])
              )
    )

// foldr : (('b, 'a) -> 'b, 'b, 'a array) -> 'b
const foldr = (f, init, xs = []) =>
  loop
    ( ( i = 0
      , r = identity
      ) =>
        i >= xs.length
          ? r (init)
          : call
              ( f
              , shift (k => recur (i + 1, compExpr (r, k)))
              , xs[i]
              )
    )

// compExpr : ('b expr -> 'c expr, 'a expr -> 'b expr) -> 'a expr -> 'c expr
const compExpr = (f, g) =>
  x => call (f, call (g, x))

// large : number array
const large =
  Array .from (Array (2e4), (_, n) => n + 1)

// log : (string, 'a) -> unit
const log = (label, x) =>
  console.log(label, JSON.stringify(x))

log("example1:", example1)
// 7

log("example2:", example2)
// 1111

log("odds", JSON.stringify (toArray (take (100, odds))))
// => [ 1, 3, 5, 7, ..., 39999 ]

log("solver:", solver ([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]))
// => [ [ 3, 4, 5 ], [ 4, 3, 5 ], [ 6, 8, 10 ], [ 8, 6, 10 ] ]

log("product:", product([ 0, 1 ], [ 0, 1 ], [ 0, 1 ]))
// [ [0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0], [1,0,1], [1,1,0], [1,1,1] ]

log("product:", product([ 'J', 'Q', 'K', 'A' ], [ '♡', '♢', '♤', '♧' ]))
// [ [ J, ♡ ], [ J, ♢ ], [ J, ♤ ], [ J, ♧ ]
// , [ Q, ♡ ], [ Q, ♢ ], [ Q, ♤ ], [ Q, ♧ ]
// , [ K, ♡ ], [ K, ♢ ], [ K, ♤ ], [ K, ♧ ]
// , [ A, ♡ ], [ A, ♢ ], [ A, ♤ ], [ A, ♧ ]
// ]

log("foldr:", foldr (add, "z", "abcefghij".repeat(2000)))
// "zjihgfecbajihgfecbajihgf....edcba"

备注

这是我第一次在任何语言中实现一级延续，它是一次真正启发性的体验，我想与他人分享。我们只需添加两个简单的函数 shift 和 reset 就可以得到所有这些-

// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
  ({ type: shift, f })

// reset : 'a expr -> 'a
const reset = (expr = {}) =>
  loop (() => expr)

在我们的loop评估器中添加相应的模式匹配 -

// ...
case shift:
  return call
    ( aux1
    , expr.f (x => run (aux1 (x, k)))
    , identity
    )

在仅使用stream和amb这两个函数的情况下，就已经拥有了巨大的潜力。让我想知道，如果我们能够使loop运行得更快，那么在实际应用中我们会达到多快的速度。

- Mulan

---

我真的需要赶上这个。我在让你的一些想法变得可以生产使用方面积累了相当多的经验。我们会看的... - user5536315