10

この講演では、最初の 8 分間で Runar が、Scala にはテール コールの削除に問題があると説明しています。そうでない場合、なぜですか？

4

3 に答える 3

23

Scala での適切な末尾呼び出しの問題は、エンジニアリング上のトレードオフの 1 つです。PTC を Scala に追加することは簡単に可能です: SLS に文を追加するだけです。ほら: Scala の PTC。言語設計の観点からは、これで完了です。

今、貧弱なコンパイラ作成者はその仕様を実装する必要があります。PTC を使用して言語にコンパイルするのは簡単ですが、残念ながら、JVM バイト コードはそのような言語ではありません。さて、ではどうGOTOですか？いいえ。継続？いいえ。例外 (継続と同等であることが知られている)? ああ、今、私たちはどこかに到達しています！したがって、例外を使用して PTC を実装できます。あるいは、JVM コール スタックをまったく使用せずに、独自のスタックを実装することもできます。

結局のところ、JVM には複数の Scheme 実装があり、それらはすべて PTC を適切にサポートしています。JVM が PTC をサポートしていないという理由だけで、JVM で PTC を使用できないというのは神話です。結局のところ、x86 にもそれらはありませんが、x86 で実行されている言語にはそれらがあります。

では、JVM に PTC を実装できるのであれば、なぜ Scala には PTC がないのでしょうか? 上で述べたように、例外または独自のスタックを使用してそれらを実装できます。しかし、制御フローに例外を使用したり、独自のスタックを実装したりすると、JVM 呼び出しスタックが特定の方法で表示されることを期待するすべてが機能しなくなります。

特に、Java ツール エコシステム (デバッガー、ビジュアライザー、静的アナライザー) との相互運用性がほぼすべて失われます。また、Java ライブラリと相互運用するためのブリッジを構築する必要がありますが、これは遅くなり、Java ライブラリ エコシステムとの相互運用も失われます。

しかし、それは Scala の主要な設計目標です! そのため、Scala には PTC がありません。

私はこれを「Hickey の定理」と呼んでいます。これは、Clojure の設計者である Rich Hickey がかつて講演で「Tail Calls, Interop, Performance – Pick Two.」と言ったことにちなんでいます。

また、JIT コンパイラーに、適切な最適化方法がわからない非常に珍しいバイト コード パターンを提示することもできます。

F# を JVM に移植する場合は、基本的にまさにその選択を行う必要があります: テール コールを放棄しますか (言語仕様で要求されているため、できません)、相互運用を放棄しますか、それともパフォーマンスをあきらめますか？.NET では、F# のテール コールは MSIL のテール コールに簡単にコンパイルできるため、3 つすべてを使用できます。(ただし、実際の変換はそれよりも複雑であり、MSIL でのテール コールの実装はいくつかのまれなケースでバグがあります。)

これは、JVM にテール コールを追加しないのはなぜでしょうか?という疑問を提起します。JVM バイト コードの設計上の欠陥により、これは非常に困難です。設計者は、JVM バイト コードに特定の安全性を持たせたいと考えていました。しかし、そもそも安全でないプログラムを記述できないような方法で JVM バイトコード言語を設計するのではなく (たとえば、Java では、ポインターの安全性に違反するプログラムを記述できないようにします。そもそもポインターへのアクセスを提供しません)、JVM バイト コード自体は安全ではなく、安全にするために別のバイト コード検証ツールが必要です。

そのバイト コード検証はスタック インスペクションに基づいており、テール コールはスタックを変更します。したがって、この 2 つを調整するのは非常に困難ですが、JVM はバイト コード ベリファイアなしでは機能しません。バイトコードベリファイアを失わずにJVMにテールコールを実装する方法を最終的に理解するのに長い時間がかかり、一部の非常に賢い人々がいますRose (JVM リード デザイナー) ) のおかげで、オープンな研究課題だった段階から、「単なる」オープンなエンジニアリング課題である段階に移行しました。

Scala やその他のいくつかの言語には、メソッド内直接末尾再帰があることに注意してください。ただし、これは実装に関してはかなり退屈です。これは単なるwhileループです。ほとんどのターゲットにはwhileループまたは同等のものがあります。たとえば、JVM には intra-method がありGOTOます。Scala にはscala.util.control.TailCallsobjectもあり、これはトランポリンを再構成したようなものです。(このアイデアのより一般的なバージョンについては、Rúnar Óli Bjarnason によるStackless Scala With Free Monadsを参照してください。末尾呼び出しだけでなく、スタックのすべての使用を排除できます。) これは、Scala で末尾呼び出しアルゴリズムを実装するために使用できます。 、しかし、これはJVMスタックと互換性がありません。つまり、他の言語やデバッガーへの再帰的なメソッド呼び出しのようには見えません:

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
 if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

fib(40).result

Clojure には、明示的なトランポリンでもあるrecur特別な形式があります。

于 2014-03-31T16:32:54.063 に答える
17

F# には末尾呼び出しに関する問題はありません。これが何をするかです：

  • 単一の末尾再帰関数がある場合、.tail命令を生成するよりも高速であるため、コンパイラは突然変異を伴うループを生成します。

  • 他の末尾呼び出し位置 (たとえば、継続または 2 つの相互再帰関数を使用する場合) では、.tail命令が生成されるため、末尾呼び出しは CLR によって処理されます。

  • 既定では、Visual Studio のデバッグ モードでは末尾呼び出しの最適化はオフになっています。これは、デバッグが容易になる (スタックを調べることができる) ためですが、必要に応じてプロジェクト プロパティでオンにすることができます。

以前は、一部のランタイム (CLR x64 および Mono) で命令に問題がありました.tailが、現在はすべて修正され、すべて正常に動作しています。

于 2014-03-31T12:24:43.640 に答える
4

適切な末尾呼び出しを行うには、デフォルトの「デバッグ モード」ではなく「リリース モード」でコンパイルするか、プロジェクト プロパティを開いて、[ビルド] メニューで下にスクロールして [末尾呼び出しの生成] をオンにする必要があることがわかりました。 "。ヒントをくれた IRC.freenode.net #fsharp の Arnavion に感謝します。

于 2016-01-24T05:52:14.580 に答える