86

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

还有这个关于 Stack Overflow 的问题：

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

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

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

4

7 回答 7

38

我的博客确实解释了做什么reset和shift做什么，所以你可能想再读一遍。

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

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

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

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

于 2009-10-03T15:04:35.233 回答
31

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

当cf调用延续函数时：

  1. 执行跳过shift块的其余部分并在其末尾重新开始
    • 传递给的参数cf是shift块在执行继续时“评估”的内容。每次调用都可能不同cf
  2. 执行一直持续到块结束（或者直到没有块 reset的调用）reset
    • 块的结果（如果没有块，则为 ()reset的参数）是返回的内容resetcf
  3. 在块cf结束后继续执行shift
  4. 执行一直跳到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
于 2009-11-05T12:02:23.980 回答
9

鉴于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 插件对这个示例进行了转换，使得reset从 eachshift到调用 的计算（在 的输入参数内）reset被替换为函数（例如f）输入到shift.

被替换的计算被转移（即移动）到一个函数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

注意Int输入参数x的类型（即 的类型签名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)
  }
}

我希望这能阐明之前对这两个示例的介绍有些混淆的连贯的通用抽象。例如，规范的第一个示例在研究论文中以匿名函数的形式呈现，而不是我的 named f，因此一些读者并不清楚它与借来的第二个示例read中的抽象相似。

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

注意返回类型f是，但k不是，必须与 的返回类型相同reset，即只要返回与 相同的类型，f就可以自由声明任何返回类型。和（也见下文）同上。kfresetreadcaptureENV

定界延续不会隐式反转状态控制，例如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的全局类型推断，因此据我所知不能支持隐式提升到状态单子unit（作为隐藏显式环境的一种可能策略），因为Haskell的全局（Hindley-Milner）类型推断取决于不支持菱形多重虚拟继承。

于 2012-11-05T16:21:36.467 回答
8

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

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

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

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

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

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

于 2009-10-03T06:57:46.437 回答
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
于 2016-04-19T16:59:33.407 回答
1

关于 Scala 延续的另一篇（最近 - 2016 年 5 月）文章是Shivansh Srivastava ( )
撰写的 “ Scala 中的时间旅行：Scala 中的 CPS（scala 的延续） ” 。 它还参考了Dmitry Bespalov的回答中提到的Jim McBeath的文章。shiv4nsh

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

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

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

假设你在冰箱前的厨房里，想着三明治。你在那里拿一个延续，把它放在你的口袋里。
然后你从冰箱里拿出一些火鸡和面包，给自己做一个三明治，现在放在柜台上。
你调用你口袋里的延续，你发现自己又站在冰箱前，想着一个三明治。不过好在柜台上有一个三明治，所有用来做三明治的材料都没有了。所以你吃它。:-)

在这个描述中，它sandwich是程序数据的一部分（例如，堆上的一个对象），而不是调用“<code>make sandwich”例程然后返回，这个人调用了一个“<code>make sandwich with current continuation”例程，它创建三明治，然后从执行停止的地方继续。

话虽如此，正如 2014 年4 月宣布的 Scala 2.11.0-RC1

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

于 2016-08-01T18:20:35.670 回答
0

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。为什么？我们调用from0to10as 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将控制权返回给 2nd 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

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

// 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
于 2019-12-19T23:12:40.173 回答