什么是 Scala 延续以及为什么使用它们？

Question

我刚刚完成Scala 编程，并且我一直在研究Scala 2.7 和 2.8 之间的变化。似乎最重要的是 Continuations 插件，但我不明白它有什么用处或它是如何工作的。我发现它对于异步 I/O 有好处，但我一直无法找出原因。关于该主题的一些更受欢迎的资源如下：

• 分隔延续和 Scala
• Scala 中的 Goto
• 2.8 体验：延续
• < em>分隔延续解释（在 Scala 中）

StackOverflow 上的这个问题：

• Scala 2.8 和 Scala 2.7 之间最大的区别是什么？

不幸的是，这些参考文献都没有尝试定义延续的用途或移位/重置函数应该做什么，而且我还没有找到任何这样做的参考文献。我无法猜测链接文章中的任何示例如何工作（或它们的作用），因此帮助我的一种方法可能是逐行浏览其中一个示例。即使是第三篇文章中的这个简单的问题：

reset {
    ...
    shift { k: (Int=>Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8

为什么结果是 8？这可能会帮助我开始。

Answer 1

我的博客确实解释了重置 和 shift 会执行此操作，因此您可能需要再次阅读该内容。

另一个很好的来源（我也在我的博客中指出）是关于连续传递样式的维基百科条目。到目前为止，这个是关于这个主题最清晰的，尽管它不使用 Scala 语法，并且延续是显式传递的。

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

但我认为分隔延续概念的最好例子是 Scala Swarm。在其中，库停止代码在某一时刻的执行，而剩余的计算则成为继续。然后，库会执行某些操作 - 在本例中，将计算传输到另一台主机，并将结果（所访问的变量的值）返回到已停止的计算。

现在，您甚至不理解 Scala 页面上的简单示例，所以请阅读我的博客。在其中，我仅关心解释这些基础知识，以及为什么结果是8。

Answer 2

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

当调用延续函数 cf 时：

1. 执行会跳过 shift 块的其余部分，并在其末尾再次开始
   • 传递给 cf 的参数是 shift 块在执行继续时“评估”的结果。每次调用 cf

   时，这可能会有所不同

2. 执行将继续，直到 reset 块结束（或者直到调用 reset，如果没有堵塞）
   • reset 块的结果（如果没有块，则为 reset() 的参数）是 cf 返回的内容李>
3. 结果 直到 shift 块结束
4. 执行会跳过，直到 reset 块结束（或者调用重置？）

在 cf 之后继续， 在此示例中，按照从 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

Answer 3

给出研究论文中关于 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 的输入参数内）为 < em>替换为shift输入的函数（例如f）。

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

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 输入参数的签名。

另一个 借用 具有概念上等效抽象的示例，即 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)
  }
}

我希望这阐明了连贯的公共抽象，而先前的这两个示例的演示在某种程度上使该抽象变得模糊不清。例如，规范的第一个示例在研究论文 作为一个匿名函数，而不是我命名的 f，因此一些读者并不能立即清楚它抽象地类似于 借用第二个示例。

因此，分隔的延续创造了一种控制反转的错觉，从“你从 reset 外部呼叫我”到“我在 reset 内部呼叫你”。

注意f的返回类型是，而k不是，要求与reset的返回类型相同，即f 可以自由地为 k 声明任何返回类型，只要 f 返回与 reset 相同的类型。 读取和捕获也是如此（另请参阅下面的ENV）。

---

分隔延续不会隐式反转状态控制，例如，read 和callback 不是纯函数。因此，调用者无法创建引用透明的表达式，因此无法对预期的命令进行声明式（也称为透明）控制语义。

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

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) 类型推断取决于不支持钻石多重虚拟继承。

Answer 4

延续捕获计算的状态，以便稍后调用。

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

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

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

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

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

Answer 5

从我的角度来看，这里给出了最好的解释： 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

Answer 6

另一篇关于 Scala 延续的文章（最近的 - 2016 年 5 月）是：
"时间旅行in Scala：Scala 中的 CPS（scala 的延续）”
Shivansh Srivastava (shiv4nsh)。
它还引用了 Jim McBeath 的 Dmitry Bespalov< 中提到的文章 /a> 的答案。

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

延续是计算机程序控制状态的抽象表示。
所以它实际上意味着它是一种数据结构，表示流程执行中给定点的计算过程；创建的数据结构可以被编程语言访问，而不是隐藏在运行时环境中。

为了进一步解释它，我们可以举一个最经典的例子，

假设您在厨房的冰箱前，正在考虑吃三明治。您就在那里继续并把它放在口袋里。
然后你从冰箱里拿出一些火鸡和面包，给自己做一个三明治，现在它就放在柜台上。
您调用口袋中的延续，然后您发现自己再次站在冰箱前，想着三明治。但幸运的是，柜台上有一个三明治，而且制作它的所有材料都没有了。所以你吃它。 :-)

在此描述中，sandwich 是程序数据的一部分（例如，堆上的对象），而不是调用“make sandwich””例程然后返回，该人调用了“用当前继续制作三明治”例程，该例程创建三明治，然后从执行停止的地方继续。

话虽这么说，正如 2014 年 4 月，Scala 2.11.0-RC1

我们正在寻找维护者来接管以下模块：scala-swing，< a href="https://github.com/scala/scala-continuations" rel="nofollow noreferrer">scala-continuations。
如果没有找到新的维护者，2.12 将不会包含它们。
我们可能会继续维护其他模块（scala-xml、scala-parser-combinators），但仍然非常感谢您的帮助。

Answer 7

通过有意义的示例实现 Scala Continuations

让我们定义 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< /code>：

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 之后的块。传递给被调用代码的参数之一是返回地址，它显示调用代码的哪一部分尚未执行 (**)。调用代码的该部分是延续。被调用的代码可以对该参数执行任何它决定的操作：将控制权传递给它，或忽略，或多次调用它。这里 from0to10 为 0..10 范围内的每个整数调用该延续。

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

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

现在，我们看到延续被声明为 cont: Int =>;单位。为什么？我们将 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，后者最终将控制权返回给 back，它是 back 将控制权返回给第一次调用 from0to10。当第一个（是的！第一个！）from0to10 退出时，整个 reset 块就会退出。

这种返回控制权的方法称为回溯，这是一种非常古老的技术，至少从 Prolog 和面向人工智能的 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

Within a function, succ() is not required：

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() /code>：

// 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