2

I have superficially read a couple of blog articles/Wikipedia about continuation-passing style. My high-level goal is to find a systematic technique to make any recursive function (or, if there are restrictions, being aware of them) tail-recursive. However, I have trouble articulating my thoughts and I'm not sure if what my attempts of it make any sense.

For the purpose of the example, I'll propose a simple problem. The goal is, given a sorted list of unique characters, to output all possible words made out of these characters in alphabetical order. For example, sol("op".toList, 3) should return ooo,oop,opo,opp,poo,pop,ppo,ppp.

My recursive solution is the following:

def sol(chars: List[Char], n: Int) = {
    def recSol(n: Int): List[List[Char]] = (chars, n) match {
        case (_  , 0) => List(Nil)
        case (Nil, _) => Nil
        case (_  , _) =>
            val tail = recSol(n - 1)
            chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _)
    }
    recSol(n).map(_.mkString).mkString(",")
}

I did try to rewrite this by adding a function as a parameter but I did not manage to make something I was convinced to be tail-recursive. I prefer not including my attempt(s) in the question as I'm ashamed of their naiveness, so please excuse me for this.

Therefore the question is basically: how would the function above be written in CPS ?

4

2 回答 2

2

试试看：

import scala.annotation.tailrec
def sol(chars: List[Char], n: Int) = {
  @tailrec
  def recSol(n: Int)(cont: (List[List[Char]]) => List[List[Char]]): List[List[Char]] = (chars, n) match {
    case (_  , 0) => cont(List(Nil))
    case (Nil, _) => cont(Nil)
    case (_  , _) =>
      recSol(n-1){ tail =>
        cont(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _))
      }
  }
  recSol(n)(identity).map(_.mkString).mkString(",")
}
于 2016-06-13T10:52:17.350 回答
1

执行 CPS 转换的首要任务是确定延续的表示。我们可以将延续视为带有“洞”的暂停计算。当用一个值填充孔时，可以计算剩余的计算。所以函数是表示延续的自然选择，至少对于玩具示例：

type Cont[Hole,Result] = Hole => Result

这里Hole表示需要填充的洞Result的类型，表示计算最终计算的值的类型。

现在我们有了一种表示延续的方法，我们可以担心 CPS 转换本身。基本上，这涉及以下步骤：

  • 转换递归地应用于表达式，在“琐碎的”表达式/函数调用处停止。在这种情况下，“琐碎”包括由 Scala 定义的函数（因为它们不是 CPS 转换的，因此没有延续参数）。
  • 我们需要给Cont[Return,Result]每个函数添加一个类型参数，这里Return是未转换函数的返回类型，Result是整体计算的最终结果的类型。这个新参数代表当前的延续。转换后的函数的返回类型也更改为Result。
  • 每个函数调用都需要转换以适应新的延续参数。调用后的所有内容都需要放入一个延续函数中，然后将其添加到参数列表中。

例如，一个函数：

def f(x : Int) : Int = x + 1

变成：

def fCps[Result](x : Int)(k : Cont[Int,Result]) : Result = k(x + 1)

和

def g(x : Int) : Int = 2 * f(x)

变成：

def gCps[Result](x : Int)(k : Cont[Int,Result]) : Result = {
  fCps(x)(y => k(2 * y))
}

现在 gCps(5) 返回（通过柯里化）一个表示部分计算的函数。我们可以从这个部分计算中提取值，并通过提供一个延续函数来使用它。例如，我们可以使用恒等函数来提取不变的值：

gCps(5)(x => x)
// 12

或者，我们可以通过使用println来打印它：

gCps(5)(println)
// prints 12

将此应用于您的代码，我们获得：

def solCps[Result](chars : List[Char], n : Int)(k : Cont[String, Result]) : Result = {
  @scala.annotation.tailrec
  def recSol[Result](n : Int)(k : Cont[List[List[Char]], Result]) : Result = (chars, n) match {
    case (_  , 0) => k(List(Nil))
    case (Nil, _) => k(Nil)
    case (_  , _) =>
      recSol(n - 1)(tail =>
                      k(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _)))
  }

  recSol(n)(result =>
              k(result.map(_.mkString).mkString(",")))
}

如您所见，虽然recSol现在是尾递归的，但它伴随着在每次迭代中构建更复杂的延续的成本。所以我们真正所做的只是用 JVM 控制栈上的空间换取堆上的空间——CPS 转换并没有神奇地降低算法的空间复杂度。

此外，recSol它只是尾递归，因为递归调用recSol恰好是第一个（非平凡的）表达式recSol执行。但是，一般来说，递归调用将发生在延续中。在有一个递归调用的情况下，我们可以通过仅将对递归函数的调用转换为 CPS 来解决这个问题。即便如此，一般来说，我们仍然只是用堆栈空间来交换堆空间。

于 2017-09-22T19:15:16.577 回答