問題タブ [tail-call-optimization]

末尾再帰であることがわかっている関数があります。しかし、私がそれを定義する方法のために、コンパイラーは、関数が非テール位置で再帰呼び出しを行うことについて不平を言います。これが機能です。

私は得る

このように書くとうまくいきます。

def: (Input) => Output = {}型宣言のスタイルと関係があると思います。ネストされた一致やタプルでの一致を書き込むよりも見た目がきれいなので、これを使用します。

私は階層データ構造で何かをしており、以下で説明するように、間接再帰でそれをトラバース/分析するためのメソッドのグループを設計しました。

メソッドa、b、c、およびがありd、すべてUnit戻り値の型があります。メソッドaが最初に呼び出されます。データに応じて、何かを実行してから停止するか、いずれかを呼び出しますb/c/d。b、c、および d のそれぞれについても同じです。各メソッドは、停止するか、他の 3 つのメソッドのいずれかを呼び出すことができます。そのため、どのメソッドが呼び出され、その実行順序は実行時まで不明であり、メソッド自体を直接呼び出すメソッドはないため、再帰は直接明らかではありません (心配しないでください。すべてのメソッドは、呼び出します)。

a、b、c、またはへの追加の各呼び出しdは、各メソッドで最後に実行されますが、文字通り各メソッドの最後のステートメントではありません。どちらが呼び出されるかを制御するiforcaseステートメントがあります。

どのメソッドも自分自身を直接呼び出していない場合、Scala コンパイラはこの多層呼び出しチェーンを分析し、末尾再帰を実装できますか?

テールコール最適化とは? テール コール最適化とは？

そこで、プレーン C でどのように実行できるかを確認することにしました。

そこで、2 つの階乗プログラムを作成しました。最初のプログラムでは、テール コールの最適化を適用できます。このファクト関数を fact(n, 1) と呼びます。

2 つ目は、複数のスタック フレームが必要な通常の再帰です。

これは、-O2 を使用して前者の 32 ビット コンパイラによって生成されたアセンブリです。

これは、-O2 を使用して後者の 32 ビット コンパイラによって生成されたアセンブリです。

両方のプログラムをコンパイルし、生成されたアセンブリを確認すると、両方のプログラムにまだ再帰呼び出しがあります。しかし、前者で -O2 オプション(上記のアセンブリ)を使用してコンパイルすると、再帰呼び出しがまったく表示されないため、gcc は末尾呼び出しの最適化を行っていると思います。

しかし、後者を -O2 オプションでコンパイルすると、再帰呼び出しも削除され、代わりに -O2 で前者に起こることと比較して、かなりの数のアセンブリ命令が配置されます。

後者でコンパイラが何をしているのか、O4 でも前者によって生成されたアセンブリに変換できない理由を正確に理解したかったのです。

私が知る限り、Clojurerecurはコンパイラによってサポートされていますが、他の Lisp では低レベルで実装されています。

私が読んだように、これは「一般的な」TCO ではありません。明白なこと (キーワード + チェックが必要) は別として、何らかの方法でrecurそれほど強力ではありませんか?

自動的に末尾呼び出しが最適化されるClojureの関数を定義する方法はありますか？

例えば

内部的に次のようなものに変換されます：

このようなものがすでに存在するかどうか教えていただけますか？

質問のタイトルは少し奇妙かもしれませんが、私が知る限り、末尾呼び出しの最適化に反対するものは何もありません。ただし、オープンソースプロジェクトを閲覧しているときに、コンパイラが末尾呼び出しの最適化を実行するのを積極的に阻止しようとするいくつかの関数にすでに遭遇しました。たとえば、そのようなハックでいっぱいのCFRunLoopRefの実装です。例えば：

なぜこれがとても重要に見えるのか知りたいのですが、通常の開発者として私もこれを念頭に置いておく必要がある場合はありますか？例えば。末尾呼び出しの最適化に関する一般的な落とし穴はありますか？

末尾再帰関数についていくつか質問があります。たとえば、これとこれですが、次のようなものは見つかりませんでした。

私の理解では、末尾呼び出しに最適化された関数は、それ以上の評価なしに、最後の呼び出しで累積値を返す必要があります。たとえば、ループ2に最適化される階乗関数を使用すると、非常に簡単に理解できます。しかし、他の場合、たとえば次のように、その最後の呼び出しは何であるかを伝えることは必ずしも明白ではありません。関数は体内で複数回再帰的に呼び出されるため、それらの多くがあります。

ブライアンはそれを見つける方法を提案しますが、末尾呼び出しを最適化する方法がわかりません。フラグをコンパイラに渡し--tailcallsて自動的に実行できますが、常に成功しますか？

f同じタイプをg返します。

上記のコードを末尾呼び出しで最適化するためのヘルプをいただければ幸いです。

Haskell を 2 日前に始めたばかりなので、コードを最適化する方法がまだわかりません。

練習問題として、foldland foldr( ここでは与えfoldlますが、 andにfoldr置き換えlastても同じです) を書き直しました。headinittail

コードは次のとおりです。

私の唯一の懸念は、再帰呼び出しが関数の最後で行われないため、Haskell がここで末尾呼び出しの最適化を適用できないのではないかと思うことです。

このテールコールを最適化するにはどうすればよいですか? Haskell の組み込み実装はfoldl、私の実装とは異なる方法で実装されていますか?

クラスで、再帰呼び出しの後にブール演算子が評価されるため、次の関数は末尾再帰ではないと言われました。

しかし、これは1,000万サイズのリストのスタックを爆破するものではなく、さらに、標準ライブラリでの実装です。末尾再帰でなければ、一見同等で明らかに末尾再帰の代わりにこのフォームを使用する理由はありません。

したがって、OCamlコンパイラは、このような単純なケースでブール演算を最適化して、末尾再帰を利用できるようです。しかし、私がそのようにオペランドの順序を切り替えると、私は気づきました

その後、スタックは実際に10mの要素に吹き飛ばされます。したがって、OCamlは、再帰呼び出しが右側に表示されている場合にのみこれを利用できるように見えます。これにより、コンパイラが行うのは、ブール値のopを同等の式に置き換えることだけであると思われますif。誰かがこれを確認または反論できますか？

私は SICP演習 2.28を行っていて、次のコードの奇妙な動作に出くわしました。

通常fringeのバージョンは、反復バージョンよりもはるかに高速に実行されますfringe-tail。

対。

fringeループに最適化されているように見え、割り当てを回避しますが、fringe-tail実行ははるかに遅くなり、オブジェクトの作成と破棄に時間を費やします。

誰かが私にこれを説明できますか? （ラケット5.2.1を使用している場合に備えて）