如何转换 ackermann 函数的变体以支持尾调用？

Question

我目前正在解决一个问题，即在具有尾调用优化支持的 Scala 中实现 ackermann 函数的变体，以便堆栈不会溢出。

问题是，我找不到尾调用优化它的方法。有人告诉我 continuation-pass-style(CPS) 会有所帮助，但即使我成功地用 CPS 风格重新实现了它，我仍然迷路了。

阿克曼函数的变体是这样的：

ppa(p, a, b) = p(a, b)               (if a <= 0 or b <= 0)
ppa(p, a, b) = p(a, ppa(p, a-1, b))  (if p(a, b) is even and a, b > 0)
ppa(p, a, b) = p(ppa(p, a, b-1), b)  (if p(a, b) is odd and a, b > 0)

未经优化的代码如下：

def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
  def ppa_cont(a: Int, b: Int, ret: (Int, Int) => Int): Int = {
    if (a <= 0 || b <= 0) ret(a, b)
    else (a, b) match {
      case (_, _) if (p(a, b) % 2 == 0) => ret(a, ppa_cont(a-1, b, (x, y) => ret(x, y)))
      case (_, _) => ret(ppa_cont(a, b-1, (x, y) => ret(x, y)), b)
    }
  }

  ppa_cont(a, b, p)
}

另一个试验是这样的：

def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
  def ppa_cont(a: Int, b: Int, cont: (Int, Int) => Int): (Int, Int) => Int = {
    if (a <= 0 || b <= 0) cont
    else if (p(a, b) % 2 == 0) (a, b) => cont(a, ppa_cont(a-1, b, cont)(a-1, b))
    else (a, b) => cont(ppa_cont(a, b-1, cont)(a, b-1), b)
  }
 
  ppa_cont(a, b, p)(a, b)
}

我试着尾调用优化它：

def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
  @annotation.tailrec
  def ppa_cont(a: Int, b: Int, ret: (Int, Int) => TailRec[Int]): TailRec[Int] = {
    if (a <= 0 || b <= 0) tailcall(ret(a, b))
    else (a, b) match {
      case (_, _) if (p(a, b) % 2 == 0) => {
        tailcall(ret(a, ppa_cont(a-1, b, (x, y) => ret(x-1, y))))
      }
      case (_, _) => {
        tailcall(ret(ppa_cont(a, b-1, (x, y) => ret(x, y-1)), b))
      }
    }
  }

  val lifted: (Int, Int) => TailRec[Int] = (x, y) => done(p(x, y))

  ppa_cont(a, b, lifted).result
}

但由于类型不匹配，无法编译。

可能是什么问题？我走错方向了吗？小提示和帮助之手将不胜感激。谢谢 :)

p.s。我从以下位置得到提示：why scala doesn't make tail call optimization?

Answer 1

试试 cats.free.Trampoline 或 scala.util.control.TailCalls.TailRec。不是 @tailrec 而是 stack-safe.

import scala.util.control.TailCalls._

def ppa(p: (Int, Int) => Int, a: Int, b: Int): Int = {
  def hlp(a: Int, b: Int): TailRec[Int] = {
    if (a <= 0 || b <= 0) done(p(a, b))
    else if (p(a, b) % 2 == 0) tailcall(hlp(a - 1, b)).map(p(a, _))
    else tailcall(hlp(a, b - 1)).map(p(_, b))
  }

  hlp(a, b).result
}

http://eed3si9n.com/herding-cats/stackless-scala-with-free-monads.html

http://eed3si9n.com/herding-cats/tail-recursive-monads.html

实际上你的函数看起来不像 Ackermann。实际的 Ackermann 进行了两次递归调用

f(m, n) = f(m - 1, f(m, n - 1))

你的函数进行了一次递归调用。编写函数的迭代版本并不难（通常使用尾递归，因为编译器可以自动将其转换为迭代版本）。假设我们已经为 0 <= i <= a - 1、0 <= j <= b - 1（黄色区域）计算了 ppa(i, j)。然后我们计算两个橙色段(a, 0), (a, 1), ..., (a, b - 1)（按此顺序）和(0, b), (1, b), ..., (a - 1, b)（按此顺序）。然后我们计算红细胞(a, b).

如何转换 ackermann 函数的变体以支持尾调用？

How to convert a variation of ackermann function to support tail call?

scala

tail-recursion

tail-call-optimization

continuation-passing

ackermann