6

I have been trying to wrap my head around the complex typing issues with scala continuations. I've been reading all the material I can find on it, including the reference docs on the continuations package. I think I have it figured out to some degree and it makes SOME sense when you think about it.

I think my understanding of it (and some of my question) can be best summed up by this program:

package com.whatever;
import scala.util.continuations._;

object methods {

  /* The method takes an Int as its parameter.  Theoretically, at some point in the future,
   * it will return a Float to the remainder of the continuation.  This example does it
   * immediately but doesn't have to (for example it could be calling a network service
   * to do the transformation)
   * 
   * Float @cpsParam[Unit,Float] means that whatever part of the reset{} that is captured
   * as a closure should receive a Float and needn't return anything (would it be meaningful
   * if Unit were something else?)
   * 
   * The reason I have to return 0.toFloat is so the compiler can properly type the
   * method.  That zero will never go anywhere.  Is this a sign I'm doing it wrong?
   */
  def method1(param:Int): Float @cpsParam[Unit,Float] = shift { cb:(Float=>Unit) =>
    cb(param.toFloat); 
    0.toFloat;
  }

  /* This method is basically identical but returns a String instead of a Float (Again,
   * theoretically this would be done by a network service and cb would be called at some
   * point in the future.
   */
  def method2(param:Int): String @cpsParam[Unit,String] = shift { cb:(String=>Unit) =>
    cb(param.toString);
    ""
  }
}

object Main {
  def main(args:Array[String]):Unit = {
    reset {
      val f = methods.method1(5);
      println(f);
    }
  }
}

Incidentally, it's criminal that StackOverflow doesn't highlight scala! (I stand corrected; it actually does a pretty good job but just not in the live preview)

My questions are as follows:

  1. Judging from the comments in the program above, what is missing from my understanding of scala's CPS? Is there ever a situation where you would NOT want Unit as B in @cpsParam[B,C]?
  2. The above program compiles and works (it prints out "5.0"). But, the issue I'm running into now that's causing my confusion is when I change the reset block to try to call method2 after method1:

(Apparently you can't have a code block right after a list)

reset {
  val f = methods.method1(5);
  println(f);
  val s = methods.method2(42);
  println(s);
}

When I do this (which seems like a pretty simple thing), I get the following compiler error at the reset (this is scala 2.10 Milestone 2):

illegal answer type modification: scala.util.continuations.cpsParam[Unit,Float] andThen scala.util.continuations.cpsParam[Unit,String]

I interpret this to mean "Your first shift returns a Float and your second shift returns a String and you can't do that." Is this accurate? Does that mean you cannot use CPS to do two (or more) things in sequence unless they have the same return type? Because that seems like kind of a serious limitation. I'm guessing I'm either 1) Missing something that allows you to do this, or B) Missing some obvious reason why it's impossible for that to happen with CPS. But which one is it?

I'm starting to feel less like you need to be a post-doc student in order to understand scala's CPS. But I'm certainly not quite there yet.

4

1 回答 1

4

在我问了这个问题之后,我做了更多的研究,我想我现在可以回答我自己的问题了(我希望这不是失礼)。

我做了三件事帮助我理解了这个问题,我认为任何在 scala 的延续上遇到问题的人都应该遵循这些步骤:

  1. 阅读有关 scala 延续的原始学术论文。它非常枯燥,我怀疑它主要是一群疯子的胡言乱语,但它也很有帮助,因为它可以让您深入了解编译器如何转换您的延续驱动代码以及它的类型和纯度问题面对这样做。
  2. 以回调传递方式重写您的代码。 这是您可以做的最重要的事情,以真正掌握延续流及其类型的情况。
  3. 检查,我的意思是真正检查类型签名shift并注意它在做什么。这将驱使你进入我所拥有的顿悟。

就我而言,我输入的@cpsParams 和cb参数shift都错了。我将解释我是如何找出我做错了什么的,以便任何像我一样愚蠢的人都可以遵循相同的步骤,并希望在延续编译器让他们发疯时获得一些洞察力。

步骤1

我读了上面的论文。大约十几次。我对它的了解仍然很少。但我所理解的非常有帮助。

第2步

我用回调传递风格重写了我的块,假装每个方法都不reset是 a ,而是调用第二个参数,该参数将使用一个函数来完成块的其余部分。这是重置块在此之后的样子:shiftcb

  methods.method1(5, {f: Int => {
    println(f);
    methods.method2(42, {s: String => {
        println(s);
    });
  });

看看发生了什么?因此,现在我不再编写看似阻塞的代码,而是自己明确界定延续并将它们作为函数传递给每个方法。因此,对于每种情况,很明显我的每个匿名回调函数都不需要返回任何内容,事实上,它们都应该返回Unit,否则它们会污染它们被传递到的方法的返回类型。我认为这是编译器试图告诉我的(尽管我可能是错的)。

这是method1我的回调样式程序的外观

   def method1(param:Int, cb:(Float=>Unit)):Unit = {
     cb(param.toFloat);
   }

method2相似但需要一个(String=>Unit). 现在很明显,我的方法也应该返回Unit,否则它们可能会污染回调函数的返回类型。

步骤 2 结论

我认为我的很多困惑源于这样一个事实,即出于某种原因,我脑海中的画面是每一个都只是作为一个延续而shift捕捉到下一个。shift当然不是这样。eachshift必须捕获块的整个其余部分reset包括所有以下shifts,以便它形成一个大的嵌套回调回调情况。此外,所有回调和所有调用 CPS 的方法都应该总是(据我所知) return Unit,因为它们的结果不仅不会做任何事情,而且可能会污染调用它们的函数的返回类型,所以在回调链上。

第 3 步

现在我查看了shift. 它就在我面前:

def shift[A,B,C](fun: (A => B) => C)): A @cpsParam[B,C]

当我看到这个时,我意识到结合我的回调式练习,这里有足够的信息(即使没有完全理解shift幕后的内容)可以将其变成基本上是维度分析的练习。

我知道结果method1将是一个Float. 因此,延续回调(如上(A => B)所示)需要接受 aFloat作为其参数。这修复AFloat. 因此method1现在看起来像这样:

def method1(param:Int): Float @cpsParam[B,C] = shift { cb: (Float => B) => {
    ...
    C
  }
}

换句话说,我传递给shift的函数必须将一个函数从 Float 传递到 B,然后返回 C。好吧,我从练习中知道回调应该返回 Unit,否则事情会变得一团糟。我还知道,在我的回调练习中,方法本身显然应该返回Unit,因为它们将实际结果作为参数传递给延续。这类似于 C 也是 Unit。所以这意味着method1必须看起来像这样:

def method1(param:Int): Float @cpsParam[Unit,Unit] = shift { cb: (Float => Unit) => {
    cb(param);
  }
}

并且method2将是相同的,除了回调将采用字符串。

我学到的是

现在在我看来,与其被抛出的所有类型参数弄糊涂,你可以简单地记住,如果你正在编写一个回调驱动的程序,几乎所有涉及的函数都会返回Unit,因为任何结果都作为参数传递而不是被退回。

这意味着,据我B所知Cshift除了Unit. 这很有意义,因为有一个注释@suspendable是一个快捷方式,@cps[Unit]它是@cpsParam[Unit,Unit].

我不知道为什么 scala-lang.org 上的示例如此垃圾。但实际上他们只需要说,“如果你需要使用其他任何东西,MyReturnType @suspendable那么你可能做错了,顺便说一下,函数参数也shift应该返回Unit。” 那样我还能拥有我生命中最后的宝贵日子。

美好的结局

我上面提到的具有更改的程序完全可以按顺序使用两种方法编译和运行。所以这让我相信我终于做对了。如果您是对 CPS 有深刻理解的博士,那么请纠正我的胡言乱语中的任何不准确之处。

于 2012-02-29T17:16:01.040 回答