A Linear Lisp Machine

このセクションの中で、私たちは、全てのconsセルがちょうど1の参照カウントを持っているLisp Machine のオートマトン理論モデル(それはデータ構造がすべて木であることを暗示する)を導入します――なぜなら、それらは共有またはサイクルを持っていません。例えば、私たちの線形のリスプでは、NREVERSEはREVERSEに同形です。

私たちの機械は、consセルにアトムかポインターのいずれかを固定することができる有限状態コントロールおよびnポインターレジスタから成ります。
アトムはNILかシンボルのいずれかです。
レジスタの1つ(fr)は、「free list」レジスタとして区別されて、NILの無限のリストを示すために初期化されます。
別のレジスタ(sp)は「スタックポインタ」レジスタとして指定されます。

マシンは以下のアトム操作のどれかを実行することができます:

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;

はたして、この文献を掘り下げる価値はあるのだろうか…

Linear Lispで言っているのは単一のセルをふたつ以上のポインタが決して
指さないように評価機を構成する話ですね。プログラム自身がどう
表現されているかはとは別の話ですね。

shiroさまのご指摘で掘り下げる意味がないことが判明。ありがとございます。