「末尾最適化」を正しく理解する - ブートストラッピングでコンパイラを作る日記
以下の記事でPythonやRubyの末尾再帰関数をループに変換する手法が「末尾再帰最適化」や「末尾呼び出し最適化」として紹介されているのですが、これらの用語を使うのは間違いです。 紹介されている手法(動的束縛を利用して制御フローを変形する手法)自体は大変面白いですね。 Pythonで末尾再帰最適化をする。 Rubyで末尾再帰最適化をする。 参考文献として以下を挙げておきます。 William D. Clinger "Proper Tail Recursion and Space Efficiency" ちゃんと読み直していないので、以下の説明に間違いがあるかも知れません。その場合はご指摘お願いします。 まず「末尾呼び出し(Tail Call)」は関数の一番最後の式(末尾式)であって、関数呼び出しであるものを指します。 void foo() { bar(); baz(); /* 末尾呼び出し
プログラミング言語の最適化のしやすさについて - ブートストラッピングでコンパイラを作る日記
プログラミング言語の高級化はえてしてプログラムを複雑化し最適化を阻害してしまいます。 rowlの開発ではこのトレードオフについて神経質になろうと思っています。 最適化の基本 最適化には命令数削減・並列化・パイプライン最適化・レジスタ割り当て・スケジューリング・キャッシュ最適化・・・とさまざまな対象・手法が存在しますが、いずれにも共通する事は 元のプログラムをより良いものに変形する という事で、その際に重要なのは プログラムの意味を変えてはならない という最適化の基本原則です。プログラムの意味を変えない為にはプログラムの解析が必要で、その為の手法は大きく分けると フロー解析 型解析 です。最適化がしやすい言語とはこれらを精度よく行う事が出来る言語と言う事ができます。 また、Haskellの様な参照透過性が完璧に保たれている言語ではこれらの解析をすることなくプログラムの変形が可能です。 型解析
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
