0

Lisp のコンス/ペアを C などの低レベル言語で実装するオプションは何ですか?

一般的な実装の 1 つは、フィールドtype、car、およびcdrで構成される構造体です。リンクされたリストは保存にはあまり効率的ではないことはわかっていますが、追加の型フィールドによってさらに悪化します。

ウィキペディアで、Lisp マシンが型情報のために各単語にビットを追加していたことを読みました。しかし、今日のアーキテクチャ (x86、ARM) のオプションは何ですか?

4

2 に答える 2

3

コンスセルは、Lisp で表現する必要があるデータの 1 つのタイプにすぎません。その他は配列またはベクトルです。弦。文字。数字。シンボル。記録。クラスのインスタンス。

Lisp マシンだけがタグ ビットを使用したわけではありません。ほとんどの Lisp 実装はそれらを使用します。

ほとんどの Lisp 実装は、各メモリ ワード内のビットだけを使用します。さまざまな Lisp マシンでは、1 ワードあたりのビット数が異なります。Symbolics 36** マシンは 36 ビット ワードを使用していました。Symbolics Ivory は 40 ビット ワードを使用していました。TI Explorer は 32 ビット ワードを使用していました。そのため、Symbolics は異常なワード サイズを使用し、TI は通常のワード サイズを使用しました。Symbolics は、40 ビット CPU (16 GB) により、より多くのメモリをアドレス指定することができました。タグには 1 ワードの 8 ビットが使用されました。シンボリックには、データを表現する際に他のさまざまな最適化もありました (たとえば、リストはcdr コード化されたベクトルとして表現できます。この手法は現在の Lisp 実装では使用されていません)。

現在の CPU のほとんどは、32 ビットまたは 64 ビットのアーキテクチャです。これにより、Lisp コンス セルが作成され、サイズがこれらのワードの 2 つになり、ビットはこれらのワード サイズに収まる必要があります。fixnum が 32 ビットまたは 64 ビットより小さいです。fixnum は、単語からタグ ビットを引いた値に収まる整数です。より大きな整数の場合、数値を別の方法で表す必要があります。したがって、完全な 64 ビット長の数値は、64 ビット マシンでは fixnum として表現できません。Common Lisp は、これらのサイズに関する情報を提供します。私の 64 ビット LispWorks では、最も正の fixnum は 1152921504606846975 です。

CL-USER > MOST-POSITIVE-FIXNUM
1152921504606846975

タグ ビットのために余分なメモリを浪費することは通常ありません。現在のほとんどの Lisp 実装では、タグ ビットをデータ ワード (32 ビットまたは 64 ビット) に配置する必要があります。Lisp の実装者は、これを可能な限り効率的にするために懸命に取り組んできました。

于 2012-11-02T19:21:11.750 に答える
2

typeフィールドをポインターのタグに置き換えることができます。

NaN ボクシングと組み合わせると、各スタック スロット (および構造体のcarおよびcdrフィールドcons) を のサイズに縮小できdoubleます。

mallocただし、各コンス セルのオーバーヘッド (1 つまたは 2 つの単語) は引き続き発生します。

于 2012-11-02T19:45:29.120 に答える