-- OtherLispImpl.mesa
-- Last Edited May 31, 1983 10:37 pm
-- Last Edited by: Gnelson, November 21, 1983 2:26 pm

-- This is like LispImpl but uses its own record type to represent CONS cells, instead
-- of relying on the record type that is implicit in LIST OF REF.  The result is that
-- the Cdr of a pair is not restricted to be a list.

DIRECTORY Lisp;

LispImpl: PROGRAM EXPORTS Lisp =
BEGIN OPEN Lisp;

PairRecord: TYPE = RECORD[a: Value, b: Value];

Cons: PUBLIC PROC [a, b: Value] RETURNS [Value] = 
 {RETURN [NEW[PairRecord ← [a, b]]]};

Reverse: PUBLIC PROC [l: Value] RETURNS [r: Value]
 = {r ← NIL; WHILE l # NIL DO r ← Cons[Car[l], r]; l ← Cdr[l] ENDLOOP};

Pair: PUBLIC PROC [u: Value] RETURNS [BOOL] = 
   {RETURN [ISTYPE[u, REF PairRecord]]};

Append: PUBLIC PROC [x, y: Value] RETURNS [Value] =
  {IF x = NIL 
   THEN RETURN [y] 
   ELSE RETURN [Cons[Car[x], Append[Cdr[x], y]]]};
   
Car: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {xx: REF PairRecord = NARROW[x]; RETURN [xx.a]};

Cdr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {xx: REF PairRecord = NARROW[x]; RETURN [xx.b]};
 
Cadr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {RETURN [Car[Cdr[x]]]};

Caddr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {RETURN [Car[Cdr[Cdr[x]]]]};
 
Rplaca: PUBLIC PROC [x: Value, y: Value] = 
  {xx: REF PairRecord = NARROW[x]; xx.a ← y};

Rplacd: PUBLIC PROC [x: Value, y: Value] = 
  {xx: REF PairRecord = NARROW[x]; xx.b ← NARROW[y]};

Linearize: PUBLIC PROC[l, op: Value] RETURNS [Value] =
  {IF Pair[l] AND (Car[l] = op) 
   THEN RETURN [Cons[Cadr[l], Linearize[Caddr[l], op]]]
   ELSE RETURN [Cons[l, NIL]]};

Unlinearize: PUBLIC PROC[v, op: Value] RETURNS [Value] =
  {IF Cdr[v] = NIL THEN RETURN [Car[v]];
   RETURN [Cons[op, Cons[Car[v], Unlinearize[Cdr[v], op]]]]};

Subst: PUBLIC PROC[target, replacee, replacer: Value] RETURNS [Value] =
  {RETURN[MapSubst[target, Cons[replacee, NIL], Cons[replacer, NIL]]]};

MapSubst: PUBLIC PROC[target, replaceelist, replacerlist: Value] RETURNS [Value] =
  {IF Pair[target] 
   THEN RETURN[Cons[MapSubst[Car[target], replaceelist, replacerlist],
   					     MapSubst[Cdr[target], replaceelist, replacerlist]]];
   {t: Value ← replaceelist;
    u: Value ← replacerlist;
    WHILE t # NIL AND Car[t] # target DO t ← Cdr[t]; u ← Cdr[u] ENDLOOP;
    IF t = NIL THEN RETURN[target] ELSE RETURN [Car[u]]}};

Memq: PUBLIC PROC[x, y: Value] RETURNS [BOOL] =
  {WHILE y # NIL AND Car[y] # x DO y ← Cdr[y] ENDLOOP;
   RETURN [y # NIL]};

END.