11

このサイトと Web の他の場所を検索すると、テール コールの最適化は JVM でサポートされていません。したがって、非常に大きな入力リストで実行される可能性のある次のような末尾再帰の Scala コードは、JVM で実行する場合は記述すべきではないということですか?

// Get the nth element in a list    
def nth[T](n : Int, list : List[T]) : T = list match {
            case Nil => throw new IllegalArgumentException
            case _ if n == 0 => throw new IllegalArgumentException
            case _ :: tail if n == 1 => list.head
            case _ :: tail  => nth(n - 1, tail)
}

Martin Odersky の Scala by Example には、再帰が適切な状況またはその他の環境があることを示唆しているように見える次のパラグラフが含まれています。

原則として、テール コールは常に呼び出し関数のスタック フレームを再利用できます。ただし、一部のランタイム環境 (Java VM など) には、末尾呼び出しでスタック フレームを効率的に再利用するためのプリミティブがありません。したがって、生産品質の Scala 実装は、最後のアクションがそれ自体への呼び出しである直接末尾再帰関数のスタック フレームを再利用するためにのみ必要です。他の末尾呼び出しも最適化される可能性がありますが、実装間でこれに依存するべきではありません。

この段落の真ん中の 2 つの文の意味を説明できる人はいますか?

ありがとうございました！

4

5 に答える 5

22

直接末尾再帰は while ループと同等であるため、Scala コンパイラは単にジャンプを使用してこれを内部でループにコンパイルできるため、この例は JVM 上で効率的に実行されます。ただし、一般的な TCO は JVM ではサポートされていませんが、コンパイラによって生成されたトランポリンを使用したテール コールをサポートする tailcall() メソッドが利用可能です。

コンパイラーが末尾再帰関数をループに正しく最適化できるようにするために、scala.annotation.tailrec アノテーションを使用できます。これにより、コンパイラーが目的の最適化を行うことができない場合にコンパイラー エラーが発生します。

import scala.annotation.tailrec

@tailrec def nth[T](n : Int, list : List[T]) : Option[T] = list match {
            case Nil => None
            case _ if n == 0 => None
            case _ :: tail if n == 1 => list.headOption
            case _ :: tail  => nth(n - 1, tail)
}

(IllegalArgmentException をねじ込みます!)

于 2011-04-17T20:56:48.640 に答える
19

原則として、テール コールは常に呼び出し関数のスタック フレームを再利用できます。ただし、一部のランタイム環境 (Java VM など) には、末尾の呼び出しでスタック フレームを効率的に再利用するためのプリミティブがありません。したがって、生産品質の Scala 実装は、最後のアクションがそれ自体への呼び出しである直接末尾再帰関数のスタック フレームを再利用するためにのみ必要です。他の末尾呼び出しも最適化される可能性がありますが、実装間でこれに依存するべきではありません。

この段落の真ん中の 2 つの文の意味を説明できる人はいますか?

末尾再帰は、末尾呼び出しの特殊なケースです。直接末尾再帰は末尾再帰の特殊なケースです。直接末尾再帰のみが最適化されることが保証されています。他のものも最適化される可能性がありますが、それは基本的にコンパイラの最適化にすぎません。言語機能として、Scala は直接末尾再帰の除去のみを保証します。

それで、違いは何ですか？

末尾呼び出しは、サブルーチンの最後の呼び出しです。

def a = {
  b
  c
}

この場合、への呼び出しcは末尾呼び出しであり、への呼び出しbはそうではありません。

末尾再帰とは、末尾呼び出しが以前に呼び出されたサブルーチンを呼び出す場合です。

def a = {
  b
}

def b = {
  a
}

これが末尾再帰です:a呼び出しb(末尾呼び出し) で、これがa再び呼び出します。(以下で説明する直接末尾再帰とは対照的に、これは間接末尾再帰と呼ばれることもあります。)

ただし、2 つの例はいずれも Scala によって最適化されません。または、より正確には、Scala 実装はそれらを最適化できますが、そうする必要はありません。O(1)これは、上記のすべてのケースでスタック スペースが必要になることが言語仕様で保証されているたとえば、Scheme とは対照的です。

Scala 言語仕様は、直接末尾再帰が最適化されることのみを保証します。つまり、サブルーチンが他の呼び出しを間に挟まずにそれ自体を直接呼び出す場合です。

def a = {
  b
  a
}

この場合、への呼び出しaは末尾呼び出し (サブルーチンの最後の呼び出しであるため) であり、末尾再帰 (自分自身を再度呼び出すため) であり、最も重要なのは直接末尾再帰です。a最初に別の呼び出し。

メソッドが直接末尾再帰的でなくなる原因となる微妙なことがたくさんあることに注意してください。たとえば、aがオーバーロードされている場合、再帰は実際にはさまざまなオーバーロードを通過する可能性があるため、直接的ではなくなります。

実際には、これは次の 2 つのことを意味します。

  1. 少なくとも末尾呼び出しを含めずに、末尾再帰メソッドで Extract Method Refactoring を実行することはできません。最適化されています）。
  2. 直接末尾再帰のみを使用できます。間接的な末尾再帰を使用して非常にエレガントに表現できる末尾再帰降下パーサー、またはステート マシンが出てきました。

これの主な理由は、基礎となる実行エンジンにGOTO、継続、ファーストクラスの可変スタック、または適切な末尾呼び出しなどの強力な制御フロー操作機能がない場合、その上に独自のスタックを実装するか、トランポリンを使用する必要があるためです。一般化された適切な末尾呼び出しを提供するために、グローバル CPS 変換または同様の厄介なものを作成します。これらはすべて、パフォーマンスに重大な影響を与えるか、同じプラットフォーム上の他のコードとの相互運用性をもたらします。

または、Clojure の作成者である Rich Hickey が同じ問題に直面したときに言ったように、「パフォーマンス、Java 相互運用性、テール コール。2 つ選んでください」。Clojure と Scala はどちらも末尾呼び出しで妥協し、完全な末尾呼び出しではなく末尾再帰のみを提供することを選択しました。

簡単に言うと、あなたが投稿した特定の例は直接末尾再帰であるため、最適化されます。@tailrecメソッドに注釈を付けることで、これをテストできます。メソッドが最適化されるかどうかにかかわらず、注釈は変更されませんが、メソッドが最適化されない場合はコンパイル エラーが発生することが保証されます。

上記の微妙な点の@tailrecため、コンパイル エラーを取得するためだけでなく、コードを保守している他の開発者へのヒントとしても、最適化が必要なメソッドに注釈を付けることをお勧めします。

于 2011-04-18T02:23:59.463 に答える
3

Scala コンパイラーは、テール呼び出しをループに「フラット化」することで最適化を試みます。これにより、継続的にスタックが拡大することはありません。

もちろん、そのためにはコードが最適化可能である必要があります。ただし、メソッド (scala.annotation.tailrec) の前に注釈 @tailrec を使用すると、コンパイラはメソッドが最適化可能である必要があるか、コンパイルに失敗します。

于 2011-04-17T20:57:44.783 に答える
2

マーティンの発言は、直接自己再帰的な呼び出しのみがTCO最適化の候補（他の基準が満たされている）であると述べています。間接的な相互再帰的なメソッドのペア（または再帰的なメソッドのより大きなセット）は、それほど最適化できません。

于 2011-04-17T22:07:33.327 に答える
2

末尾呼び出しの最適化をサポートするJVMがあることに注意してください(IIRC、IBM の J9 はサポートしています)。それは JLS の要件ではなく、Oracle の実装ではサポートされていません。

于 2011-04-18T09:55:33.853 に答える