再帰的にメモ化するSchemeインタープリターを作成したいと思います。評価中のどの時点でも、インタプリタは、以前に見た式と環境のペアを引数として受け取ったときにそれを検出できる必要があります。
との単純なメモ化evalはapply非効率的です。eval/を呼び出すたびに、ハッシュテーブル内の引数を検索applyする必要があります。これには、ハッシュテーブルの一致で（おそらく大きな）引数全体をウォークする必要があります。
たとえば、インタプリタがプログラムを評価するとします。
(car (list A))
ここで、Aは大きなオブジェクトに評価されます。インタプリタがアプリケーション(list A)を評価するとき、最初listに個別に評価しAます。に適用listする前Aに、ハッシュテーブルでこのアプリケーションを以前に見たことがあるかどうかを調べ、Aオブジェクト全体を調べてハッシュを計算します。後で、メモ化インタプリタがcarAを含むリストに適用されると、このリストのハッシュが計算されます。これには、Aオブジェクト全体のウォークも含まれます。
代わりに、ほぼ一意のハッシュを段階的に構築し、可能な場合は再計算を回避し、衝突が発生しにくいことを保証するインタープリターを構築したいと思います。
たとえば、インタプリタが操作する各オブジェクトを、その値のMD5を使用して再帰的に拡張できます。複合オブジェクトの場合は、そのコンポーネントハッシュのMD5を使用して拡張できます。環境は、その変数/値エントリごとにハッシュを格納する場合があり、環境のハッシュは、個々のハッシュの関数として計算される場合があります。次に、環境内のエントリが変更された場合、環境全体をリウォークして環境の新しいハッシュを計算する必要はありません。代わりに、変更された変数/値のペアのハッシュのみを再計算する必要があり、エントリハッシュのセットのグローバルハッシュを更新する必要があります。
特に再帰的なメモ化やプログラム評価のコンテキストで、ほぼ一意のハッシュを段階的に構築するための関連作業はありますか？