-- LispImpl.mesa
-- Last Edited May 31, 1983 10:37 pm
-- Last Edited by: Gnelson, December 10, 1983 11:28 pm

DIRECTORY Lisp;

LispImpl: PROGRAM EXPORTS Lisp =
BEGIN OPEN Lisp;

Cons: PUBLIC PROC [a, b: Value] RETURNS [Value] = 
 {RETURN [CONS[a, NARROW[b, LIST OF REF ANY]]]};

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 [u # NIL AND ISTYPE[u, LIST OF REF ANY]]};

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: LIST OF REF ANY = NARROW[x]; RETURN [xx.first]};

Cdr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {xx: LIST OF REF ANY = NARROW[x]; RETURN [xx.rest]};
 
Cadr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {RETURN [Car[Cdr[x]]]};

Caddr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {RETURN [Car[Cdr[Cdr[x]]]]};

Cddr: PUBLIC PROC [x: Value] RETURNS [Value] = 
 {RETURN [Cdr[Cdr[x]]]};

Rplaca: PUBLIC PROC [x: Value, y: Value] = 
  {xx: LIST OF REF ANY = NARROW[x]; xx.first ← y};

Rplacd: PUBLIC PROC [x: Value, y: Value] = 
  {xx: LIST OF REF ANY = NARROW[x]; xx.rest ← 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], Cons[Unlinearize[Cdr[v], op], NIL]]]]};

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.