疑問に思っていたのですが...メモ化が、私が知っている言語によって言語機能としてネイティブに提供されないのはなぜですか？
編集：明確にするために、私が意味するのは、言語が特定の関数をメモ可能として指定するキーワードを提供することであり、特に指定されていない限り、すべての関数が「デフォルト」で自動的にメモ化されるわけではありません。たとえば、fortranは、特定の機能をそのように指定するためのキーワードPUREを提供します。コンパイラーはこの情報を利用して呼び出しをメモできると思いますが、PUREを副作用のある関数として宣言した場合に何が起こるかは無視します。
あなたがメモ化に求めるものは、コンパイラのメモ化オプションが提供するものと同じではないかもしれません。
関数がどのように使用されるかを知っているので、計算された最後の 10 個程度の個別の値をメモすることだけが有益であることを知っているかもしれません。
それより古い値を使用することは決してないため、最後の 2 つまたは 3 つの値をメモすることだけが意味があることを知っているかもしれません。（フィボナッチ数列が思い浮かびます。）
いくつかの実行では多くの値を生成し、他の実行ではほんのわずかしか生成しない場合があります。
メモ化された値の一部を「破棄」して、最初からやり直すことができます。(この方法で乱数ジェネレーターをメモ化したので、特定の構造を構築する一連の乱数を再生できましたが、構造の他のパラメーターが変更されていました。)
最適化としてのメモ化は、値の再計算よりもはるかに安価なメモ化された値の検索に依存します。これは、入力要求の順序に依存します。これはメモ化データベースに影響を与えます: スタック、可能なすべての入力値の配列 (非常に大きい可能性があります)、バケット ハッシュ、または B ツリーを使用しますか?
メモ化コンパイラは、「フリーサイズ」のメモ化を提供するか、多くの可能な選択肢と選択肢を制御するパラメータを提供する必要があります。ある時点で、ユーザーに自分のメモ化を要求することが誰にとっても簡単になります。
コンパイラは意味的に正しいプログラムを発行する必要があるためです。参照透過でない限り、プログラムのセマンティクスを変更せずに関数をメモ化することはできません。ほとんどのプログラミング言語では、すべての関数が参照透過的であるとは限りません (純粋な関数型プログラミング言語は例外です)。そのため、すべてを記憶することはできません。しかし、参照透過性を検出するためのメカニズムが必要ですが、それは難しすぎます。
Haskell では、引数を取らない定義済みの (純粋な) 関数のメモ化は自動的に行われます。そして、その Wiki のフィボナッチの例は、私が考えることができる最も単純で実証可能な例に関するものです。
Haskell がこれを行うことができるのは、純粋関数が毎回同じ結果を生成するように定義されているためです。もちろん、副作用に依存するモナド関数はメモ化されません。
上限が何であるかはわかりません-明らかに、利用可能なメモリを超えてメモ化することはありません。また、メモ化がコンパイル時に発生するか (コンパイル時に値を決定できる場合)、または関数が最初に呼び出されたときに常に発生するかどうかもわかりません。
Clojure には memoize 機能があります ( http://richhickey.github.com/clojure/clojure.core-api.html#clojure.core/memoize ):
memoize
function
Usage: (memoize f)
Returns a memoized version of a referentially transparent function. The
memoized version of the function keeps a cache of the mapping from arguments
to results and, when calls with the same arguments are repeated often, has
higher performance at the expense of higher memory use.
言語自体で簡単に実装できる場合は、言語機能として何かを実装するべきではないからです。メモ化機能はライブラリに属しており、ほとんどの言語がまさにその場所にあります。
A)メモ化は空間を時間と交換します。これは、プログラムやライブラリが保存しなければならない量のデータがメモリの大部分を非常に速く消費する可能性があるという意味で、かなりバインドされていないプロパティになる可能性があると思います。
いくつかの言語では、メモ化は簡単に実装でき、特定の要件に合わせて簡単にカスタマイズできます。
例として、テキストの基本的なプロパティ (単語数、頻度、共起など) を何度も計算したくない、大量のテキストに対する自然言語処理を取り上げます。その場合、変更されていないコーパスでアプリケーションを複数回実行する可能性があるため、メモリ キャッシングとは対照的に、オブジェクトのシリアル化と組み合わせたメモ化が役立ちます。
B）別の側面：すべての関数またはメソッドが同じ入力に対して同じ出力を生成するというのは真実ではありません。とにかく、メモ化のためのキーワードまたは構文が必要であり、構成（メモリ制限、無効化ポリシーなど）...
すべての言語が関数デコレータをネイティブにサポートしているわけではありません。メモ化だけをサポートするのではなく、サポートする方が一般的なアプローチだと思います。
あなたの質問は、より多くの言語を学ぶという解決策も未解決のままにしています。Lisp はメモ化をサポートしていると思いますし、Mathematica がサポートしていることも知っています。
質問を逆にします。なぜそれが必要なのですか？誰かが言ったように、ライブラリに入れることができるので、言語に構文を追加する必要はありません。自動的に識別するのが難しい純粋な関数でのみ使用できます（プログラマーに注釈を付けさせない限り）。また、メモ化によって速度が向上するかどうかを判断することも非常に困難です。プログラミング言語にとって望ましい機能ではないと思います。
私は本当にそのようなオプションがあるべきだと思います。
データ処理タスクには、不変の入力データがあります (時系列のように、たとえば、値が既知になるとすぐに特定の時間に変化することはありません)。今日の RAM の手頃な価格を念頭に置いて、関数の結果がそのような不変データにのみ依存する場合、必要になるたびに再読み取りするのではなく、メモ化する方が合理的です。現在、(Scala と C# で) インメモリ ストレージ テーブルを手動で導入し、1 つではなく 3 つの関数を作成する必要があります。利用可能な場合はメモリから読み取り、ない場合は生の関数を呼び出します。これはキーワードとして実装し、舞台裏で行うことができるし、そうすべきだと思います。