BeginPackage["CSM`Lisp`"]

cons::usage = "cons[a, b] is the pair (a . b)."
car::usage  = "car[pair] is the first element of pair."
cdr::usage  = "cdr[pair] is the second element of pair."
list::usage = "list[e1, e2,..., en] is the Lisp list (e1 e2 ... en)."

nil::usage = "nil is the empty Lisp list."

pairQ::usage = "pairQ[e] is True if e is a pair."
atomQ::usage = "atomQ[e] is True if e is an atom."
nullQ::usage = "nullQ[l] is True if l is the empty list."

Begin["`Private`"]

$RecursionLimit = Infinity (* necessary for long lists *)

(* constructors *)

list[] = nil
list[e_, r___] := cons[e, list[r]]

(* selectors *)

car[cons[e_, l_]] := e
cdr[cons[e_, l_]] := l

(* predicates *)

atomQ[_?AtomQ] = True  (* leave undefined otherwise *)
atomQ[_cons] = False
pairQ[e_] := !atomQ[e]
nullQ[nil] = True
nullQ[_cons] = False

(* output formats *)

listToNest[nil] := {}
listToNest[c_cons] := {car[c], listToNest[cdr[c]]}
listToList[l_] := Flatten[listToNest[l]] (* conversion into List[] *)

listQ[nil] = True      (* nil is both an atom and a list *)
listQ[l_cons] := listQ[cdr[l]]
listQ[_] = False

Format[nil] = "()"	(* the empty list *)
Format[l_cons?listQ] :=
    SequenceForm["(", Infix[listToList[l], " "], ")"]
Format[l_cons] := SequenceForm["(", Infix[l, " . "], ")"]

(* problem with Infix[] *)

protected = Unprotect[Infix]
Infix[_[e_], h_:Null] := e
Protect[Evaluate[protected]]

End[]

Protect[ car, cdr, cons, pairQ, atomQ, nullQ, list ]

EndPackage[]
