3

これは、末尾再帰関数を解釈するためのトランポリンを実装するための「Scala での関数型プログラミング」の第 13 章の演習です。

runTrampoline2末尾再帰ではなく、テスト入力でスタックをオーバーフローさせます。さらに、tailrec注釈は のコンパイラ エラーを示しrunTrampoline2ます。 runTrampoline末尾再帰であり、注釈のコンパイル時チェックに合格します。

私の最善の策は、これら 2 つのトランポリンの違いは、次のvalようにユニットをキャプチャする方法とキャプチャしない方法にあるということです。

scala> val foo = println("abc")
val foo = println("abc")
abc
foo: Unit = ()

scala> foo
foo

scala> val bar: Int = {println("xyz"); 5}
val bar: Int = {println("xyz"); 5}
xyz
bar: Int = 5

scala> bar
bar
res8: Int = 5

そうでなければ、これらの 2 つのトランポリンは私には同じように見えます。Free モナドと、Suspend、Return、および FlatMap コンストラクターのコードが、この質問にとって重要であると誰かがコメントした場合は含めますが、そうではないと思います。の末尾再帰はrunTrampoline2、s から漏れる副作用によって壊れていvalますか? ありがとう！

@annotation.tailrec
def runTrampoline[A](tra: Free[Function0,A]): A =
  tra match {
    // case Return(A)
    case Return(a1) => a1
    // case Suspend(Function0[A])
    case Suspend(function0A1) => function0A1()
    // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
    case FlatMap(free1, aFree2) => free1 match {
      // case Return(A)
      case Return(a2) => runTrampoline(aFree2(a2))
      // case Suspend(Function0[A])
      case Suspend(function0A) => runTrampoline(aFree2(function0A()))
      // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
      case FlatMap(a0,g) =>
        runTrampoline {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
    }
  }


//@annotation.tailrec
def runTrampoline2[A](tra: Free[Function0,A]): A =
  tra match {
    // case Return(A)
    case Return(a1) => a1
    // case Suspend(Function0[A])
    case Suspend(function0A1) => {
      val a1: A = function0A1()
      a1
    }
    // case FlatMap(Free[Function0[_],A], A=>Free[Function0,A]]
    case FlatMap(free1, aFree2) => free1 match {
      // case Return(A)
      case Return(a2) => {
        val free2: Free[Function0,A] = aFree2(a2)
        val a3: A = runTrampoline2(free2)
        a3
      }
      // case Suspend(Function0[A])
      case Suspend(function0A) => {
        val a2: A = function0A()
        val free2: Free[Function0,A] = aFree2(a2)
        val a3: A = runTrampoline2(free2)
        a3
      }
      // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
      case FlatMap(a0,g) =>
        runTrampoline2 {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
      }
      }

型注釈が末尾再帰を壊すことについて、1 か月前に同様の質問をしました: Scala: 型注釈により末尾再帰チェックが失敗する

Aiveanによって解決されました。これはトランポリンの修正版です。各再帰呼び出しは、それを含むケースの最後にあります。

@annotation.tailrec
def runTrampoline3[A](tra: Free[Function0,A]): A =
  tra match {
    case Return(a1) => a1
    case Suspend(function0A1) => {
      val a1 = function0A1()
      a1
    }
    case FlatMap(free1, aFree2) => free1 match {
      case Return(a2) => {
        val free2 = aFree2(a2)
        runTrampoline3(free2)
      }
      case Suspend(function0A) => {
        val a2 = function0A()
        val free2 = aFree2(a2)
        runTrampoline3(free2)
      }
      case FlatMap(a0,g) =>
        runTrampoline3 {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
     }
  }
4

1 に答える 1

4

Scala コンパイラは、それ自体への呼び出しが関数内の実際の最後の操作である場合にのみ、末尾再帰を認識するようです。

これを確認するために、2 つの異なる例を逆コンパイルしました。

テール再帰:

スカラ:

def rec:Int = rec

ジャバ:

public final class _$$anon$1 {
  private int rec() {
    while (true) {}
  }
}

末尾再帰なし:

スカラ:

def rec:Int = {
  val i = rec
  i
}

ジャバ:

public final class _$$anon$1 {
  private int rec() {
    final int i = this.rec();
    return i;
  }
}
于 2015-07-25T02:05:04.610 に答える