什么是 Scala 延续，为什么要使用它们？

我的 blog 确实解释了 reset 和 shift 的作用，因此您可能需要再次阅读。

另一个很好的来源（我也在我的博客中指出）是 continuation passing style 上的 Wikipedia 条目。到目前为止，该主题是最清楚的，尽管它不使用 Scala 语法，并且显式传递了延续。

关于定界延续的论文，我在我的博客中链接到，但似乎已经损坏，给出了许多使用示例。

但我认为分隔延续概念的最佳示例是 Scala Swarm。在其中，库在某一时刻停止执行您的代码，剩余的计算成为继续。然后库做一些事情——在这种情况下，将计算转移到另一个主机，并将结果（访问的变量的值）返回给停止的计算。

现在，你连 Scala 页面上的简单示例都看不懂，所以做阅读我的博客。其中我只关心解释这些基础知识，以及为什么结果是 8。

---

我发现现有的解释在解释这个概念方面没有我希望的那么有效。我希望这个是清楚的（和正确的）。我还没有使用延续。

当调用延续函数 cf 时：

执行跳过移位块的其余部分并在其末尾重新开始，传递给 cf 的参数是移位块在执行继续时“评估”的内容。这对于每次调用 cf 可能是不同的 执行一直持续到重置块结束（或者直到调用重置，如果没有块）重置块的结果（或者参数重置（）如果没有块) 是什么 cf 在 cf 之后继续执行，直到 shift 块结束执行跳过直到 reset 块结束（或调用 reset？）

所以在这个例子中，按照从 A 到 Z 的字母

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

这打印：

11
101

---

鉴于 research paper 中用于 Scala 的定界延续的规范示例，稍作修改，因此 shift 的函数输入被命名为 f，因此不再是匿名的。

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

Scala 插件对这个示例进行了转换，使得从每个 shift 开始到 reset 调用的计算（在 reset 的输入参数内）替换为函数（例如 f ) 输入到 shift。

被替换的计算被转移（即移动）到函数k中。函数 f 输入函数 k，其中 k 包含 被替换的计算，k 输入 x: Int，k 中的计算将 shift(f) 替换为 {9 }。

f(k) * 2
def k(x: Int): Int = x + 1

这与以下效果相同：

k(k(k(7))) * 2
def k(x: Int): Int = x + 1

注意输入参数 x 的类型 Int（即 k 的类型签名）由 f 的输入参数的类型签名给出。

另一个具有概念等效抽象的 borrowed 示例，即 read 是 shift 的函数输入：

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

我相信这将转化为以下逻辑等价物：

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

我希望这能阐明之前对这两个示例的介绍有些混淆的连贯的通用抽象。例如，规范的第一个示例在 research paper 中以匿名函数的形式出现，而不是我命名的 f，因此一些读者并不清楚它是否抽象地类似于 borrowed 中的 read } 第二个例子。

因此，分隔的延续会产生一种控制反转的错觉，从“您从 reset 外部呼叫我”到“我在 reset 内部呼叫您”。

注意 f 的返回类型是，但 k 不是，要求与 reset 的返回类型相同，即 f 可以自由声明 k 的任何返回类型，只要f 返回与 reset 相同的类型。 read 和 capture 同上（另请参阅下面的 ENV）。

定界延续不会隐式反转状态控制，例如 read 和 callback 不是纯函数。因此调用者不能创建引用透明的表达式，因此没有 declarative (a.k.a. transparent) control over intended imperative semantics。

我们可以显式地实现带有分隔延续的纯函数。

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

我相信这将转化为以下逻辑等价物：

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

由于显式环境，这变得嘈杂。

切线注意，Scala没有Haskell的全局类型推断，因此据我所知不能支持隐式提升到状态monad的unit（作为隐藏显式环境的一种可能策略），因为Haskell的全局（Hindley-Milner ) 类型推断取决于 not supporting diamond multiple virtual inheritance。

---

继续捕获计算的状态，稍后调用。

考虑离开移位表达式和将重置表达式作为函数之间的计算。在移位表达式中，这个函数被称为 k，它是延续。您可以传递它，稍后调用它，甚至不止一次。

我认为重置表达式返回的值是 => 之后的移位表达式内的表达式的值，但对此我不太确定。

因此，通过延续，您可以在函数中封装一段相当随意且非本地的代码。这可用于实现非标准控制流，例如协同程序或回溯。

因此，应该在系统级别上使用延续。将它们洒在你的应用程序代码中肯定会成为噩梦，比使用 goto 的最糟糕的意大利面条代码更糟糕。

免责声明：我对 Scala 中的延续没有深入的了解，我只是通过查看示例和了解 Scheme 中的延续来推断它。

---

从我的角度来看，这里给出了最好的解释：http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

示例之一：

为了更清楚地查看控制流，您可以执行以下代码片段：

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

这是上面代码产生的输出：

A
B
D
E
G
F
C

---

另一篇（最近的——2016 年 5 月）关于 Scala 延续的文章是：
Shivansh Srivastava (shiv4nsh) 的“Time Travel in Scala: CPS in Scala (scala’s continuation)”。
它还指 Dmitry Bespalov 中提到的 Jim McBeath 的 article answer。

但在此之前，它像这样描述 Continuations：

延续是计算机程序控制状态的抽象表示。所以它实际上的意思是它是一个数据结构，代表了进程执行中给定点的计算过程；创建的数据结构可以被编程语言访问，而不是隐藏在运行时环境中。为了进一步解释，我们可以举一个最经典的例子，假设你在冰箱前的厨房里，想着一个三明治。你在那里拿一个延续，把它放在你的口袋里。然后你从冰箱里拿出一些火鸡和面包，给自己做一个三明治，现在放在柜台上。你调用你口袋里的延续，你发现自己又站在冰箱前，想着一个三明治。不过好在柜台上有一个三明治，所有用来做三明治的材料都没有了。所以你吃它。 :-) 在这个描述中，三明治是程序数据的一部分（例如，堆上的一个对象），而不是调用“制作三明治”例程然后返回，该人称为“制作三明治并具有当前延续”例程，它创建三明治，然后从执行停止的地方继续。

话虽如此，正如 April 2014 for Scala 2.11.0-RC1 中宣布的那样

我们正在寻找维护者来接管以下模块：scala-swing、scala-continuations。如果没有找到新的维护者，2.12 将不包含它们。我们可能会继续维护其他模块（scala-xml、scala-parser-combinators），但仍然非常感谢您的帮助。

---

Scala 延续通过有意义的例子

让我们定义 from0to10 来表达从 0 到 10 的迭代思想：

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

现在，

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

印刷：

0 1 2 3 4 5 6 7 8 9 10 

事实上，我们不需要 x：

reset {
  print(s"${from0to10()} ")
}
println()

打印相同的结果。

和

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

打印所有对：

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

现在，这是如何工作的？

有被调用代码、from0to10和调用代码。在这种情况下，它是 reset 之后的块。传递给被调用代码的参数之一是返回地址，它显示调用代码的哪一部分尚未执行（**）。调用代码的那部分是continuation。被调用的代码可以使用该参数做任何决定：将控制权传递给它，或者忽略它，或者多次调用它。这里 from0to10 为 0..10 范围内的每个整数调用该延续。

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

但延续在哪里结束？这很重要，因为延续的最后一个 return 将控制权返回给被调用的代码 from0to10。在 Scala 中，它在 reset 块结束 (*) 处结束。

现在，我们看到延续被声明为 cont: Int => Unit。为什么？我们将 from0to10 调用为 val x = from0to10()，而 Int 是转到 x 的值的类型。 Unit 表示 reset 之后的块必须不返回任何值（否则会出现类型错误）。一般来说，有 4 种类型签名：函数输入、延续输入、延续结果、函数结果。所有四个必须匹配调用上下文。

上面，我们打印了成对的值。让我们打印乘法表。但是我们如何在每一行之后输出 \n 呢？

函数 back 让我们指定控制返回时必须执行的操作，从延续到调用它的代码。

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

back 首先调用其延续，然后执行动作。

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

它打印：

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

好吧，现在是时候进行一些脑筋急转弯了。 from0to10 有两次调用。第一个 from0to10 的延续是什么？它遵循 二进制代码 中的 from0to10 调用，但在源代码中它还包括赋值语句 val i =。它在 reset 块结束的地方结束，但 reset 块的结尾不会将控制权返回给第一个 from0to10。 reset 块的末尾将控制权返回给第二个 from0to10，而第二个 from0to10 最终又将控制权返回给 back，并且是 back 将控制权返回给 from0to10 的第一次调用。当第一个（是的！第一个！）from0to10 退出时，整个 reset 块退出。

这种将控制返回的方法称为回溯，这是一种非常古老的技术，至少从 Prolog 和面向 AI 的 Lisp 衍生产品时代就知道了。

名称 reset 和 shift 用词不当。这些名称最好留给按位运算。 reset 定义延续边界，而 shift 从调用堆栈中获取延续。

笔记）

(*) 在 Scala 中，延续在 reset 块结束的地方结束。 另一种可能的方法是让它在函数结束的地方结束。

(**) 被调用代码的参数之一是返回地址，显示调用代码的哪一部分还没有执行。嗯，在Scala中，返回地址序列用于那。多少？自进入 reset 块以来放置在调用堆栈上的所有返回地址。

UPD 第 2 部分丢弃延续：过滤

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

这打印：

0 2 4 6 8 10 

让我们分解出两个重要的操作：丢弃延续（fail()）并将控制权传递给它（succ()）：

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

succ()（上图）的两个版本都有效。事实证明，shift 有一个有趣的签名，虽然 succ() 什么都不做，但它必须具有该签名才能实现类型平衡。

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

正如预期的那样，它打印

0 2 4 6 8 10

在函数中，succ() 不是必需的：

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

再次，它打印

0 2 4 6 8 10

现在，让我们通过 onEven() 定义 onOdd()：

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

上面，如果 x 是偶数，则抛出异常并且不调用延续；如果 x 为奇数，则不抛出异常并调用延续。上面的代码打印：

1 3 5 7 9 

---