CDRコーディング

コンピュータサイエンス において、 CDR コーディングはLispリンクリストの圧縮 データ表現です。これはMIT 人工知能研究所で開発され、特許を取得しており、MIT CADRから派生した多数のLisp マシンのコンピュータハードウェアに実装されています。

CDR コーディングは、実際にはかなり一般的な考え方です。データ オブジェクトA が別のデータ構造Bへの参照で終わるときはいつでも、代わりに構造B自体をそこに配置して、 Aの終わりと重複して実行することができます。これを行うと、参照に必要なスペースが解放されます。このスペースは、何度も実行すると蓄積される可能性があります。また、参照の局所性が向上し、最新のマシンでのパフォーマンスが向上します。この変換は、それが作成されたconsベースのリストに特に効果的です。この変換を実行する各ノードで約半分のスペースが解放されます。

この置換は、A の末尾を超える十分な大きさの空き領域がない場合があるため、常に実行できるとは限りません。したがって、一部のオブジェクトは実際の参照で終了し、一部のオブジェクトは参照先オブジェクトで終了するため、マシンは最終セルを読み取ることでどちらであるかを判断できなければなりません。これは、タグ付きポインターを使用してソフトウェアで非効率に実行できます。タグ付きポインターを使用すると、最終位置のポインターにそのように具体的にタグ付けできますが、ハードウェアで行うのが最適です。

可変オブジェクトが存在する場合、CDR コーディングはより複雑になります。参照が別のオブジェクトを指すように更新されたが、現在そのフィールドにオブジェクトが格納されている場合、そのオブジェクトと、それを指す他のすべてのポインターを再配置する必要があります。このような移動は通常、コストがかかったり不可能になったりするだけでなく、時間の経過とともにストアの断片化を引き起こします。この問題は通常、不変データ構造 でのみ CDR コーディングを使用することで回避されます。

• Mark Kantrowitz、Barry Margolin (編)。「(2-9) CDR コーディングとは何ですか?」FAQ: Lisp に関するよくある質問。Advameg, Inc. 2011-10-09に取得。
• L. Peter Deutsch: 非常にコンパクトなプログラムを備えた LISP マシン。IJCAI 1973、697 - 703 ページ
• Greenblatt, R.、「LISP マシン進捗レポート」、メモ 444、AILab.、MIT、マサチューセッツ州ケンブリッジ、1977 年 8 月。
• L. Peter Deutsch: マイクロプログラミング Interlisp システムの経験。MICRO 11: マイクロプログラミングに関する第 11 回年次ワークショップの議事録、1978 年 11 月、128 ～ 129 ページ
• アレン、ジョン (1978)。Lispの解剖学。マグロウヒル。399-401ページ