Linear Lisp -- A Linear Lisp Machine
A Linear Lisp Machine
Linear Lispマシン
In this section we introduce an automata-theoretic model of a Lisp Machine in which all cons cells have reference counts of exactly 1, which implies that all data structures are trees--i.e., they have no sharing or cycles.
このセクションでは私達は全てのデータ構造は木である全てのコンスセルが厳密に1の参照カウントをもつ(すなわちそれらは共有やサイクルを持ちません)Lispマシンのオートマトン理論のモデルを紹介します。
For example, in our Linear Lisp, NREVERSE is isomorphic to REVERSE.
例えば、私達のLinear Lispでは、NREVERSEはREVERSEに同形です。
Our machine consists of a finite state control and n pointer registers which can hold either atoms or pointers to cons cells.
私達のマシンは有限状態制御とアトムかコンスセルへのポインタのどちらでも保持できるnポインターレジスタから成ります。
An atom is either NIL or a symbol.
アトムはNILかシンボルです。
One of the registers--fr--is distinguished as the "free list" register, and is initialized to point to an infinite list of NIL's.
レジスタの1つ(fr)は「フリーリスト」レジスタとして割り当てられ、無限のNILのリストの意味で初期化されます。
Another register--sp--is designated as the "stack pointer" register.
別のレジスタ(sp)は「スタックポインタ」レジスタとして指定されます。
The machine can execute any of the following atomic operations:
マシンは次のいづれかの基本操作を実行することができます：
r1<->r2; /* swap r1,r2. */
r1<->CAR(r2); /* r1,r2 distinct; precondition(not ATOM(r2)) */
r1<->CDR(r2); /* r1,r2 distinct; precondition(not ATOM(r2)) */
NULL(r1); /* predicate for r1=NIL */
ATOM(r1); /* predicate for r1=NIL or symbolp(r1) */
EQ(r1,r2); /* defined only for atomic r1,r2; see [Baker93ER] */
r1:='foo; /* precondition(ATOM(r1) and ATOM('foo)) constant 'foo */
r1:=r2; /* precondition(ATOM(r1) and ATOM(r2)) */
CONS(r1,r2): /* r1,r2 distinct; r2<-CONS(r1,r2) and set r1=NIL */
{r1<->CAR(fr); r2<->fr; fr<->CDR(r2);};
PUSH(r1,r2): /* r1,r2 distinct; Push r1 onto r2 and set r1=NIL */
CONS(r1,r2);
POP(r1,r2): /* r1,r2 distinct; Pop CAR(r2) into r1 if r1=NIL */
if NULL(r1) and not ATOM(r2)
then {fr<->CDR(r2); r2<->fr; r1<->CAR(fr);}
else die;
Proposition 1. List cell reference counts are conserved and are always identically 1.
提案１．リストセルの参照カウントは保存され常に1に一致する。
Proof by induction [Suzuki82,s.4].
帰納法による証明。
All cons cells start out with unity reference counts, and are only manipulated by exchanges which preserve reference counts.
全てのコンスセルは唯一の参照カウントで始まり、参照カウントを維持するやりとりでだけ操作される。
QED
証明終わり
Proposition 2. All list cells are always accessible--i.e. live, and no garbage is created.
提案２．全てのリストセルは常にアクセス可能(すなわち生きている)でゴミは生成されない。
Proof by induction [Suzuki82,s.5].
帰納法による証明。
Storage could "leak" only if we performed ri<->CXR(ri), but we do not allow the swapping of a register with a portion of its own contents.
ストレージは私たちがri<->CXR(ri)を実行したときのみかつその時に限り「リークする」とする、しかし私達はそれ自身の内容の一部でレジスタの入れ換えを許しません。
QED
証明終わり
Programming Note: The only way to "clear" a register which points to a list is to decompose the list stored there and put it back onto the free list.
1つはWeizenBaumの遅延再利用トリックを使用してゴミをフリーリストに置きます。また、このトリックは[Wise85]によって支持されました。
Putting garbage onto the free list moves work from the point of freeing to the point of allocation; this may smooth out the work, but does not decrease its amount, unless the program terminates with a dirty free list.
フリーリストへゴミを置くことは割り当てたもののポインタを開放する仕事を提案します。これはその仕事を片付ける、しかしその総量は減りません、ダーティーフリーリストで終わらないことを除いて。
プログラミングノート：リストを指すレジスタを「クリア」するたった1つの方法はそこに格納されているリストを分解してフリーリストへ戻すことだけです。
FREE(r1): /* Essentially the K combinator! */
if not NULL(r1) then
if ATOM(r1) then r1:='NIL;
else
{PUSH(r2,sp); POP(r2,r1); /* temporary r2 ~= r1. */
FREE(r1); /* free the cdr of the cell. */
r2<->r1; FREE(r1); /* free the car of the cell. */
POP(r2,sp);}
これら(5,6行目)は再帰呼び出しで「古いPC」スタック操作を含むと暗示されている、しかし私達は読者へそれらの詳細を任せる。
We can copy, but only by destroying the original list and creating two new lists.
私達はコピー可能である、しかしオリジナルのリストを破棄して2つの新しいリストを生成することによってのみです。
COPY(r1,r2): /* assert(r2=NIL). Essentially the S combinator! */
if not NULL(r1) then
if ATOM(r1) then r2:=r1;
else
{PUSH(t1,sp); PUSH(t2,sp);
POP(t1,r1); COPY(r1,r2);
t1<->r1; t2<->r2; COPY(r1,r2);
t1<->r1; t2<->r2; PUSH(t1,r1); PUSH(t2,r2);
POP(t2,sp); POP(t1,sp);}
Finally, we can program recursive EQUAL by destroying and recreating both lists. (We switch to Lisp notation in order to utilize the capabilities of prog1.)
最後に、私達は破棄と両方のリストの再生制によって再帰的EQUALをプログラムすることができる。(私達はprog1の可能性を利用するためにLisp表記に切替える。)
EQUAL(r1,r2): /* Recursive list equality. */
(or (and (ATOM r1) (ATOM r2) (EQ r1 r2))
(and (not (ATOM r1)) (not (ATOM r2))
(progn (PUSH t1 sp) (PUSH t2 sp) (POP t1 r1) (POP t2 r2)
(prog1
(and (EQUAL r1 r2)
(progn (<-> t1 r1) (<-> t2 r2)
(prog1 (EQUAL r1 r2)
(<-> t1 r1) (<-> t2 r2))))
(PUSH t1 r1) (PUSH t2 r2) (POP t2 sp) (POP t1 sp)))))
Using these definitions, it should be clear that we can program a traditional Lisp interpreter (see Appendix).
これらの定義を使用して、私達は従来のLispインタプリタをプログラムすることが可能であることをはっきりさせなければなりません(付録をみてください)。
However, this interpreter will be inefficient, due to the extra expense of copying.
しかしながら、余計なコピーのコストのために、このインタプリタは役に立たないでしょう。
The one minor problem to be faced is how to handle recursive functions, since we cannot create cycles.
ある直面するより小さい問題はどのように再帰関数を取り扱うかで、私達がサイクルを生成出来ないことによります。
We suggest the following trick based on the lambda calculus Y combinator [Gabriel88]:
私達は次のλ計算に基づいたYコンビネータを提案します。
(defun fact (f n) (if (zerop n) 1 (* n (funcall f f (1- n)))))
(defun factorial (n) (fact #'fact n))
>> Lively Linear Lisp
>> Abstract
>> Introduction
>> A Linear Lisp Machine
>> A Linear Lisp Machine with FREE, COPY, EQUAL and Assignment
>> Dataflow-like Producer/Consumer EVAL
>> Reconstituting Trees from Fresh Frozen Concentrate
>> Linear Lisp EVAL
>> Implications for Real Multiprocessors
>> Conclusions and Previous Work
0 件のコメント:
コメントを投稿