12

Fregeで末尾呼び出しが最適化されていますか。JavaにもClojureやScalaのようなJVMバイトコードにコンパイルされる言語にもTCOがないことを私は知っています。フレーゲはどうですか？

4

1 に答える 1

27

Fregeは、whileループを生成するだけで、末尾再帰の最適化を行います。

一般的な末尾呼び出しは、怠惰によって「ちなみに」処理されます。コンパイラーが（間接的に）再帰的であることがわかっている疑わしい関数への末尾呼び出しを検出した場合、遅延結果（サンク）が返されます。したがって、その関数を呼び出すことの本当の負担は呼び出し元にあります。このようにして、深さがデータに依存するスタックが回避されます。

そうは言っても、すでに静的スタックの深さは、Javaよりも関数型言語の方が本質的に深いです。したがって、一部のプログラムには、より大きなスタックを指定する必要があります（つまり、-Xss1mを使用）。

大きなサンクが構築され、それらが評価されると、スタックオーバーフローが発生するという病理学的なケースがあります。悪名高い例はfoldl関数です（Haskellと同じ問題）。したがって、フレーゲの標準的な左フォールドはフォールドです。これは、アキュムレータで末尾再帰的で厳密であるため、一定のスタックスペースで機能します（Haskells foldl'のように）。

次のプログラムは、スタックオーバーフローではなく、2〜3秒後に「false」を出力する必要があります。

module Test
    -- inline (odd) 
  where

even 0 = true
even 1 = false
even n = odd (pred n)

odd n = even (pred n)

main args =  println (even 123_456_789)

これは次のように機能します。printlnには印刷する値が必要なので、評価を試みます（nでも）。しかし、それが得るのは（odd（pred n））へのサンクだけです。したがって、このサンクを評価しようとします。これにより、別のサンクが（even（pred（pred n）））になります。（pred（pred n））を評価して、引数が0か1かを確認してから、別のサンク（odd（pred（n-2））を返す必要があります。ここで、n-2はすでに評価されています。このように、すべての呼び出し（at JVMレベル）はprintln内から実行されます。実際に奇数を呼び出すことはなく、その逆もありません。

インラインディレクティブのコメントを外すと、末尾再帰バージョンのevenが取得され、結果は10倍速く取得されます。

言うまでもなく、この不器用なアルゴリズムはデモンストレーション専用です。通常、ビット演算で均一性をチェックします。

これは病理学的でスタックオーバーフローする別のバージョンです：

even 0 = true
even 1 = false
even n = not . odd  $ n
odd    = even . pred

問題はここにあります。これnotは末尾呼び出しであり、その引数は厳密です（つまり、何かを否定するには、最初にその何かを持っている必要があります）。したがって、Wheneven nが計算されると、完全に評価するnot必要があり、次に完全に評価する必要があるため、2*nスタックフレームがodd n必要になります。even (pred n)

残念ながら、JVMがいつか適切な末尾呼び出しを行う必要がある場合でも、これは変更されません。その理由は、正格の引数の再帰です。

于 2012-04-05T15:53:57.763 に答える