.Open Semantics of LISP
.Open Internal Representation of a list
. Theory
Each list is coded internally as dotted pairs:
	(A B C D ... Y Z) = (A.(B.(C.(.D ... (Y. (Z. NIL)) ... ).
Internally lists are therefore binary trees.  The trees are implemented as
records which are either atoms or have two links (pointers) called the 'car' and
the 'cdr'. 

. Pascal
For example in Pascal variant records and points are used:
.As_is TYPE	list = ^ node;
.As_is 	node= RECORD {...}
.As_is 		CASE type:(nil, atom, pair) IN
.As_is 			nil: ();
.As_is 			atom: (^atoms);
.As_is 			pair:( car, cdr: list ); {...}
.As_is END {node};
.As_is 	atoms=RECORD 
.As_is		image:PACKED ARRAY [1..] OF char; {...}
.As_is		CASE type:(number, string, word) IN
.As_is			string:(...);
.As_is			word:(...)
.As_is			number:(...);
.As_is	END {atoms};
. C++
In C++ we would get:
.As_is enum node_type{nil, atom, pair};
.As_is enum atom_type{number, string, word  /*,...*/ };
.As_is struct Pair {Node *car, *cdr}pair;
.As_is struct Atom;//defined below.
.As_is struct Pair;//defined below.
.As_is 	union Data {
.As_is 		Atom *atom;
.As_is 		Pair pair;
.As_is 	};//either an atom or a pair
.As_is struct Node{
.As_is 		/* various useful things*/
.As_is 		enum node_type type;
.As_is 		Data d;
.As_is 		Node(node_type t, Data d0){type=t;d=d0;}
.As_is 	};
.As_is typedef struct Node * list;
.As_is struct Atom{
.As_is 		char *image;
.As_is 		enum atom_type type;
.As_is 		union atomic_data{	char *string;
.As_is 			char *word;
.As_is 			int number;
.As_is 			/*...*/
.As_is 		}d;
.As_is 		Atom(/*...*/){/*...*/}
.As_is 		/*...*/
.As_is 	};

. Parsing input lists
I will use the constructors for Atom, Data, and Node to try and
explain how Lists are handled.

There is a map that parses and stores the output from the lexical stage. Call 
this `store` then for instance, store("(" car a ")") is the address an object 
       Node(pair, Data(Pair(a, c))),
where a is the address of an object
 Atom("CAR", word, ...)
and c the address of an object
 Node(pair, Data(Pair(b, null_address)))
where b is the address of an object
 Atom("B", word,...).

In general store works like this:
store("()")::= address(Node(nil)),
For a: atom, store(a)::= address(Node(atom, Atom(a,...))),
-- atoms that are not strings and numbers are capitalized at this point in the processing.
For a,b: list, store( "(" a "." b ")" )::= address(Node(pair, Data(Pair(store(a), store(b))))).

For a: list, store( "(" a ")" )::= address(Node(pair, Data(Pair(store(a), Node(nil))))).

For a: list, b: list (comma|) #list, store( "(" a b ")" )::= store( "(" a ","  b ")" )::= address(Node(store(a), store("(" b ")"))).


The interpreter reinterprets lists when it evaluates them according to the
semantics of `S_expressions`.
.Close Internal Representation

. Variables
At any time the LISP interpreter  binds values to some atoms. At any time there
are sets of variables and function names:
	variable==>atom~(number|string).
	function_name==>atom~(number|string).
The following function names are always available:
	{"CAR" , "CDR", "CONS", "NULL", "ATOM","COND", "EVAL", ...}==>function_name.

. Expressions
The meaning of input to a LISP interpreter is based on the value returned
when the expression is `evaluated`.

The evaluation of an expression depends on the meanings currently bound
to the function names and variables:
	For f:function_name, mapping(f)::=`mapping bound to f`,
	For v:variable, value(v)::=`value bound to v`.

These bindings can be changed as the side-effect of obeying the LISP function
EVAL.  Notice that "EVAL" is the LISP function that implements a function we can
call 'eval':
	mapping("EVAL") = eval.

For x, we write eval(x) for the value returned by EVAL when string x is input:
	For some defined==>#char, eval: defined>->#char.
The original definition included the environment (variables and function_names)
as parameters of `eval` - but we will treat these informally here.  

. Constants 
	constant::= NIL | T | number | string | quoted_list,

	quoted_list::="(" "QUOTE" list ")" | single_quote list,
		-- The second form is an abbreviation for the first.

Constants avoid most evaluation - numbers are converted to
binary and atoms are capitalised,...

	eval(NIL)=NIL . eval("T") = T.

	For n:number, eval(n) = `value of n as a decimal number`,

	For L:list, eval("(" "QUOTE" L ")") = eval("'" L) 
				= store(L),

	For S:#non(quote), eval( quote S quote )= `Internal string encoding S`.
	
. S_Expressions

	S_expression::=  constant | "(" function #expression ")" | variable.  -- The function determines the correct number of expressions.

	function::= function_name | lambda_form | ... .
	For c:constant, eval(c) = ` defined above`.
For f:function_name, e:#expression, eval( "(" f  e ")" )= mapping(f)(eval o e), -- `eval o e` applies eval to each element of e in turn,then the mapping associated with f is applied to the resulting list.
Example: 
.Net
	eval( "(CAR '(A B))")=mapping("CAR")(eval("'(A B)"))
	                     =car(eval("'(A B)"))
	                     =car(node(car=>A, cdr=>B))
	                     =A.
.Close.Net

	lambda_form::= "(" lambda "(" arguments ")" S_expression ")"

 	arguments::= (atom #((comma|) atom)|).

A mapping is very like a function in C/C++/Pascal/Ada except it has
not been given an identifier.  Instead the whole Lambda expression
`is` the name of the  function:
In place of short name f in
.As_is	f(a){return e;}
we hav a description of 'f' and no 'f'
.As_is	(LAMBDA (a) e){ return e; }
However.... DEFINE and DEFUN do give names to functions, when we
want to.

Inside the S_expression, the atoms (if any) are new variables which are bound to
a value when the lambda_form is applied as a function.

	For a:arguments, e:S_expression, mapping("("lambda "(" a ")" e ")" )= map[a](e).

So for example
.Net
	mapping("( (LAMBDA (X) (+ X X))"= map[x](x+x),
	eval("( (LAMBDA (X) (+ X X)) 2 ")= map[x](x+x)(2)= 2+2 = 4.
.Close.Net

Some functions have predefined mappings (here I've used the C/C++
"->" operator):
	mapping("CAR")::= map [n:node](n->car),
	mapping("CDR")::= map [n:node](n->cdr),
	mapping("NULL")::=map [a:structure] (a->type=nil)),
	mapping("ATOM")::=map [a:structure] (a->type=atom).

Using Ada record notation for CONS we get:
	mapping("CONS")::=map [a,b:structure] node(type=>pair,car=>a, cdr=>b),

. Conditional expressions
"COND" is more complex. "COND" stands for `conditional` and requires a 
sequence of pairs as its arguments:
.As_is 	"(" "COND" 
.As_is 		"("c1 e1")" 
.As_is 		"("c2 e2")" 
.As_is 		"("c3 e3")"
.As_is 		 ... 
.As_is 		"(" c[n] e[n] ")" 
.As_is 	")"

mapping("COND")::=eval(e[i]) where i is the first i in 1,2,3,...,n such that eval(c[i]) <> NIL.

. Defining new functions.

The exact syntax for defining a new function varies for system to system. For
example XLisp uses:
.As_is 	"(" DEFUN a "(" p ")" e ")"
The effect is to add atom to the set of function_names and bind it to the
mapping defined by
.As_is 	"(" "LAMBDA" "(" p ")" e ")".

Or in C/C++
.As_is	List a( p){return e;}

Others use a general DEFINE function for binding atoms to meanings:
.As_is 	"(" "DEFINE" (form) expression")"
where form is typically like this
.As_is 	"(" name arguments ")"

Another variation is
.As_is 	"(" "DEFINE" name expression ")"

Scheme LISP (and our version of XLISP) has a macro with these syntaxes
.As_is 	"(" "DEFINE" "("function arguments")" expression ")"
.As_is 	"(" "DEFINE" function lambda_expression ")"
.As_is 	"(" "DEFINE" "("function arguments")" "( EVAL" expression ")" ")"
The last form implies that the body of the function is itself the
value of the expression.... not the expression itself. (read this twice).

. Note
Scheme uses static binding and LISP use dynamic binding, but our XLISP
manages to have both!  Our DEFINE substitutes the function for the
call and so uses dynamic binding, but a function defined with DEFUN
is a closure that encapsulates the environment of the DEFUN and this
is used when the functions is called.

. Assignments

In pure LISP variables are actual formal parameters that are bound to a value
when functions are called and freed when the function returns a result. 

Most LISPS provide
.As_is 	"(" "SETQ" atom S_expression ")"
As a function with side effects.
. Note.
The "Q" in "SETQ" indicates that the atom is quoted.
.As_is 	"(" "SETQ" a e ")" = "(" "SET" "(" "QUOTE" a ")" e ")"
where
.As_is 	"(" SET e1 e2 ")"
evaluates both e1 and e2 (using `eval`) and if eval(e1) is an atom
will bind eval(e2) as the value of eval(e2).

. SETQ
(SETQ variable espression)::=following
.Net
	Evaluates the expression giving value V say
	Sets the variable to have value V (as a side-effect)
	Returns V as its result.
.As_is 	List SETQ( List & variable, Expression expression)
.As_is 	{	List v=value(expression);
.As_is 		bind(variable, v);
.As_is 		return v;
.As_is 	}
.Close.Net
. LIST
(LIST e1 e2 e3 e4 ...)::=following
.Net
	Evaluates all the expressions in turn.
	Combines the values into a single list;
	Returns the result.
.As_is 	List LIST( ... )
.As_is 	{ List arg, val, result;
.As_is 	  bind(result, NIL);
.As_is 	  for(each arg in turn)
.As_is 	  {
.As_is 		val=value(arg);
.As_is 		append(v, result);//put val at end of result
.As_is 	  }
.As_is 	  return result;
.As_is 	}
.Close.Net
. QUOTE
(QUOTE argument)::=following
.Net
	Returns a copy of the argument UNCHANGED.
.Close.Net
. Evaluated Quoted Lists
XLISP provides a strange combination of a quoted constant with
evaluated parts.  It is usefil for defining macros.
`X is like 'X or (quote X), except that
.Net
 it's called an evaluator macro
 commas inside its argument signify evaluation. 
 no comma in front of an item means it is stored verbatim.
.Close.Net
For example
 .As_is 	`(a b ,c d)
means (list 'a 'b c 'd) to the evaluator.
. The Basic Rule of LISP Evaluation

(NORMALFUNCTION e1 e2 e3 e4 ...)::=following
.Net
        Evaluates all the expressions in turn and
		binds them to the formal arguments.
        Constructs a result from the values of the formal arguments.
        Returns the result.
.Close.Net

.Close Semantics