LISPなどのリンクリストがコンピュータのメモリでどのように表されるかについて、誰かが概要を教えてもらえますか？コンピューターはCPUレジスターを使用して、ポインターをリストの先頭と残りの部分に保持しますか、それともヒープを使用しますか？
1684 次
3 に答える
4
これは、使用されている特定のコンパイラと言語ランタイムに強く依存します。ただし、一般に、Lispに似た言語のデータ構造は、ヒープに割り当てられたセルであり、隣接するセルへのポインタがあります。これらは、関数がデータを操作するときにハードウェアレジスタにロードされます。
Haskellのリンクリストタイプを考えてみましょう。
data [a] = [] | a : [a]
与えられたリストは次のように書かれるかもしれません：
1：（2：（3：（4：（5：[]））））
またはより簡潔に：
[1,2,3,4,5]
これは、次の形式のヒープ割り当てオブジェクトとして表されます。
ここで、矢印はポインタを表します。(:)「conscell」、現在の要素へのポインタを格納する小さな構造、およびリストの末尾を表します。
これで、関数がこのデータ構造にアクセスすると、構造へのポインターがレジスターにロードされ、それらのポインターからデータのロードが開始されます。その正確な詳細は、コンパイルモデルとランタイムシステムモデルによって異なります。たとえば、GHC Haskellの場合、これはSTGMachineによって提供されます。さらに、ポインターの下限ビットを使用して、ポイントされている特定のコンストラクターを示すことができます。その評価ステータス（評価済みまたは未評価）、および値が小さい場合は値自体（これはポインタータグ付けの最適化です）。
于 2012-06-06T12:41:48.090 に答える
3
Lispに関するそのような哲学的な質問については、最も刺激的な情報源の1つはAnatomyofLispです。今は少し古くなっていても。それを読むことは（まあ、何年も前に）、Lispだけでなくプログラミング全般についての私にとっての啓蒙でした。Lispの実装に関するもう1つの優れた本は、Lisp inSmallPiecesです。Lispの内部を学ぶことに真剣に取り組んでいるなら、これら2つはあなたを大いに助けます。
于 2012-06-07T06:43:40.143 に答える
2
依存します。実際に問題が発生した場合は、Stackoverflowが最適です。
「LISP」は言語の大きなファミリーであり、何百もの異なる実装です。
リンクリストを実装するためのあらゆる種類の方法がすでに試されています。
Lispの実装に関する本があり、研究すべき大小のオープンソースのLisp実装がたくさんあります。
関連する文献は、たとえばここで見つけることができます：http: //library.readscheme.org/page8.html
于 2012-06-06T10:48:48.043 に答える