2

我目前正在解决一个问题，即在具有尾调用优化支持的 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
}

但是由于类型不匹配，这不会编译。

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

ps 我得到了提示：为什么 scala 不进行尾调用优化？

4

1 回答 1

3

尝试cats.free.Trampoline或scala.util.control.TailCalls.TailRec。它不是@tailrec堆栈安全的。

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 进行了两次递归调用

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

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

在此处输入图像描述

于 2020-10-08T20:39:43.083 回答