問題タブ [tail-call]

Microsoft の新しい F# プログラミング言語は、関数型プログラミング (ファーストクラスのレキシカル クロージャーとテール コール) と、マルチコアの活用を容易にする効率的な同時実行ガベージ コレクターの強力な組み合わせを提供します。

OCaml、Haskell、Erlang、および私が知っているすべての無料の Lisp と Scheme の実装には、同時 GC がありません。Scala と Clojure には並行 GC がありますが、テール コールはありません。

したがって、これらの機能を組み合わせたオープンソースのプログラミング言語はないようです。あれは正しいですか？

Clojure について読んでいて、Java が現在のバージョンでテール コールをサポートしていないという議論を見つけました。JVM でテール コールをシミュレートするために人々が例外をスローしていました。それで、これはC＃のテールコール、同じ問題について疑問に思いましたか？

その質問への回答によると 、末尾再帰の最適化を行う C++ コンパイラはありますか? コンパイラは末尾再帰の最適化を行う必要があるようです。

しかし、提案されたオプションを試してみましたが、テンプレート関数の場合、コンパイラはこの最適化を実行できないようです。どうにかして修正できますか？

カスタム仮想マシンに末尾呼び出しを実装するにはどうすればよいですか？

元の関数のローカルスタックをポップオフし、次に引数を取得してから、新しい引数をプッシュする必要があることはわかっています。しかし、関数のローカルスタックをポップオフした場合、新しい引数をどのようにプッシュする必要がありますか？それらはスタックからポップされたばかりです。

単純な場合もありますが (自己呼び出しが最後のステートメントの場合は末尾再帰です)、それでも混乱する場合があります。「自己呼び出しの後に実行する命令がない場合は、末尾再帰です」と教授に言われました。これらの例はどうですか (あまり意味がないという事実は無視してください):

a) これは、自己呼び出しが最後のステートメントであり、その後に実行するものが残っていないことを確認して、末尾再帰にする必要があります。

b) でも、これはどうですか？条件が真の場合、それ以外は何も実行されないため、末尾呼び出しにする必要がありますが、最後のステートメントではありませんか?

c) これはどうですか？どちらの場合も、自己呼び出しが最後に実行されます。

C＃で末尾呼び出しの最適化が欠落しているために、言語が再帰的なアルゴリズムの実装に適していないという質問がいくつかあります。ただし、これは疑問を投げかけます。例外が発生した場合、またはリフレクションを使用して呼び出しスタックを検査して処理する場合に、末尾呼び出しの最適化を実行し、適切なスタックトレースを提供するにはどうすればよいですか。

私はaho-corasickアルゴリズムを試して、F＃を少し改善しようとしていますが、Trieの実装で問題が発生しました。これらはすべて変更可能であるか、末尾呼び出しを最適化できません。

私が見ることができる基本的な問題は、不変のデータ構造は、それらが指すものを変更できないため、「ボトムアップ」で構築する必要があるということです。したがって、オプションは、それらを可変にするか、進行中にノードを見つけるかのいずれかです。 （つまり、建設中の再帰）。

構造の末尾呼び出しを最適化して不変のトライデータ構造を作成する方法はありますか？（コピーによって効率が低下しないようにします）。

背景：学校のプロジェクト用に.NETコンパイラ（C＃に非常によく似ています）をプログラミングしています。現在追加しようとしている機能の1つは、メソッド内の末尾呼び出しの再帰です。

詳細：CILでは、「this」は単なる別の引数であるかのようにインスタンスメソッドに渡されます。したがって、静的メソッドの最初の引数にアクセスするとldarg.0が発行されますが、インスタンスメソッドの最初の引数にアクセスするとldarg.1が発行され、インスタンスメソッドの「this」にアクセスするとldarg.0が発行されます。 。（インスタンスメソッドは、私が想像していたよりも拡張メソッドにさらに似ています。）

質問：starg.0を使用して、副作用なしに「これ」を設定できますか？

これが問題となる理由：メソッドがインスタンスメソッドであるかどうかは、少しブラックボックスであるMethodBuilderで設定されます。「this」は他の引数とまったく同じように見えますが、一部のJITコンパイラは「this」を個別に追跡し、この値に応じて動作を変更することを知っています。インスタンスメソッドで「this」を設定したときに副作用がある場合、どうすればそれらを回避できますか？

標準のArduino環境が末尾呼び出しの除去をサポートしているかどうか疑問に思っていました...誰かがそれについて何か知っていますか？

コンパイルして実行すると、テール コールとして動作しますか?

私が知らない動作をテストする簡単な方法があるかもしれませんが、それは別の問題かもしれません。