レジスタとメモリ

ウィキペディア小見出し辞書

レジスタとメモリ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/04/02 07:04 UTC 版)

「SECDマシン」の記事における「レジスタとメモリ」の解説

SECDマシンはスタックベースであり、関数（組み込み関数とユーザー定義関数）はスタックから引数を取り出す。一方、命令のオペランドは命令形式に含まれている。 他の内部データ構造と同様にスタックもリストとなっている。Sレジスタはそのリストの先頭を指している。リスト構造であるため、このスタックは連続したメモリブロックである必要がなく、リスト用のセルが空いていればスタックを伸ばすことができる。全てのセルが使用されている場合でも、ガベージコレクションで空きメモリが見つかる可能性がある。 Cレジスタは評価（実行）すべきコードのリストの先頭を指している。その命令を実行したら、Cはリスト上の次の命令を指す。これはちょうど通常のCPUの命令ポインタと同じだが、コード自体もリスト構造であるため、次の命令がメモリ上連続した位置にあることは滅多にない。 現在の変数の環境はEレジスタによって管理される。Eはリストのリストを指している。ここで、各リストは環境レベルを表しており、現在の関数の引数はそのリストの先頭にある。現在の環境では束縛されていないがそれを取り囲む関数では束縛されている変数は、その次のリストにある。 Dレジスタの指すダンプとは、他のレジスタの内容を一時的に保管するのに使われ、例えば関数呼び出しの際などに使われる。これは、いわゆるコールスタックの役目を果たしている。 SECDマシンのメモリ構成は多くの関数型言語インタプリタと同様である。多数のメモリセルが存在し、1個のセルには「アトム」を保持するか、空または空でないリストを表す。後者の場合、セルには2つのポインタが存在し、1つめのポインタがリストの先頭のセルを指し、2つめのポインタがリストの残りの部分を指す。これらは慣習的に car と cdr と名づけられている。セルには様々な型の値が保持できるが、これをタグ(tag)で識別する。アトムの値にも整数型や文字列型などがあるが、これらもタグで識別される。 1、2、3 という数を持つリストは "(1 2 3)" と表記され、内部では以下のように表現される: アドレス タグ 内容（integer の場合は値、list の場合は car と cdr） 9 [ integer | 2 ] 8 [ integer | 3 ] 7 [ list | 8 | 0 ] 6 [ list | 9 | 7 ] ... 2 [ list | 1 | 6 ] 1 [ integer | 1 ] 0 [ nil ] ここで、3番から5番のメモリセルはリストには属していない。リストに使用するセルはメモリ全体から無作為に選択される。セル 2 はリストの先頭であり、先頭の要素を保持するセル 1 とリストの残りを保持するセル 6 を指している。セル 6 は 2 を保持するセルとセル 7 を指し、セル 7 は 3 を保持するリストとなっている。リストの最後尾では空リストを表すセル 0 を cdr で指している。SECDマシンでは、セル 0 は空リストを常に表しており、空リストを表すためにタグの値を別途用意する必要はない（単にセル 0 を指せばよい）。 なお、cdr がリストを指すというのは説明を簡単にするための言い方であって、必ずしもそのような制限があるわけではない。car も cdr もアトムであるような形式も可能で、これを "(1 . 2)" などと表記する。