[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [Samples] / lisp.semantics
Tue Sep 18 15:26:06 PDT 2007

# Semantics of LISP

## Internal Representation of a list

### Theory

Each list is coded internally as dotted pairs:
1. (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:
` TYPE	list = ^ node;`
` 	node= RECORD {...}`
` 		CASE type:(nil, atom, pair) IN`
` 			nil: ();`
` 			atom: (^atoms);`
` 			pair:( car, cdr: list ); {...}`
` END {node};`
` 	atoms=RECORD`
`		image:PACKED ARRAY [1..] OF char; {...}`
`		CASE type:(number, string, word) IN`
`			string:(...);`
`			word:(...)`
`			number:(...);`
`	END {atoms};`

### C++

In C++ we would get:
` enum node_type{nil, atom, pair};`
` enum atom_type{number, string, word  /*,...*/ };`
` struct Pair {Node *car, *cdr}pair;`
` struct Atom;//defined below.`
` struct Pair;//defined below.`
` 	union Data {`
` 		Atom *atom;`
` 		Pair pair;`
` 	};//either an atom or a pair`
` struct Node{`
` 		/* various useful things*/`
` 		enum node_type type;`
` 		Data d;`
` 		Node(node_type t, Data d0){type=t;d=d0;}`
` 	};`
` typedef struct Node * list;`
` struct Atom{`
` 		char *image;`
` 		enum atom_type type;`
` 		union atomic_data{	char *string;`
` 			char *word;`
` 			int number;`
` 			/*...*/`
` 		}d;`
` 		Atom(/*...*/){/*...*/}`
` 		/*...*/`
` 	};`

### 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

2. Node(pair, Data(Pair(a, c))), where a is the address of an object
3. Atom("CAR", word, ...) and c the address of an object
4. Node(pair, Data(Pair(b, null_address))) where b is the address of an object
5. Atom("B", word,...).

In general store works like this: store("()")::= address(Node(nil)),

6. 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.
7. For a,b: list, store( "(" a "." b ")" )::= address(Node(pair, Data(Pair(store(a), store(b))))).

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

9. 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.

. . . . . . . . . ( end of section Internal Representation) <<Contents | End>>

## Variables

At any time the LISP interpreter binds values to some atoms. At any time there are sets of variables and function names:
1. variable==>atom~(number|string).
2. function_name==>atom~(number|string). The following function names are always available:
3. {"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:

4. For f:function_name, mapping(f)::=mapping bound to f,
5. 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':

6. mapping("EVAL") = eval.

For x, we write eval(x) for the value returned by EVAL when string x is input:

7. 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

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

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

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

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

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

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

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

## S_Expressions

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

15. 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
1. eval( "(CAR '(A B))")=mapping("CAR")(eval("'(A B)"))
2. =car(eval("'(A B)"))
3. =car(node(car=>A, cdr=>B))
4. =A.

(End of Net)

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

17. 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

`	f(a){return e;}`
we hav a description of 'f' and no 'f'
`	(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.

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

So for example
Net

1. mapping("( (LAMBDA (X) (+ X X))"= map[x](x+x),
2. eval("( (LAMBDA (X) (+ X X)) 2 ")= map[x](x+x)(2)= 2+2 = 4.

(End of Net)

Some functions have predefined mappings (here I've used the C/C++ "->" operator):

19. mapping("CAR")::= map [n:node](n->car),
20. mapping("CDR")::= map [n:node](n->cdr),
21. mapping("NULL")::=map [a:structure] (a->type=nil)),
22. mapping("ATOM")::=map [a:structure] (a->type=atom).

Using Ada record notation for CONS we get:

23. 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:
` 	"(" "COND"`
` 		"("c1 e1")"`
` 		"("c2 e2")"`
` 		"("c3 e3")"`
` 		 ...`
` 		"(" c[n] e[n] ")"`
` 	")"`

24. 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:

` 	"(" DEFUN a "(" p ")" e ")"`
The effect is to add atom to the set of function_names and bind it to the mapping defined by
` 	"(" "LAMBDA" "(" p ")" e ")".`

Or in C/C++

`	List a( p){return e;}`

Others use a general DEFINE function for binding atoms to meanings:

` 	"(" "DEFINE" (form) expression")"`
where form is typically like this
` 	"(" name arguments ")"`

Another variation is

` 	"(" "DEFINE" name expression ")"`

Scheme LISP (and our version of XLISP) has a macro with these syntaxes

` 	"(" "DEFINE" "("function arguments")" expression ")"`
` 	"(" "DEFINE" function lambda_expression ")"`
` 	"(" "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

` 	"(" "SETQ" atom S_expression ")"`
As a function with side effects.

## Note.

The "Q" in "SETQ" indicates that the atom is quoted.
` 	"(" "SETQ" a e ")" = "(" "SET" "(" "QUOTE" a ")" e ")"`
where
` 	"(" 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
1. Evaluates the expression giving value V say
2. Sets the variable to have value V (as a side-effect)
3. Returns V as its result.
` 	List SETQ( List & variable, Expression expression)`
` 	{	List v=value(expression);`
` 		bind(variable, v);`
` 		return v;`
` 	}`

(End of Net)

## LIST

(LIST e1 e2 e3 e4 ...)::=following
Net
1. Evaluates all the expressions in turn.
2. Combines the values into a single list;
3. Returns the result.
` 	List LIST( ... )`
` 	{ List arg, val, result;`
` 	  bind(result, NIL);`
` 	  for(each arg in turn)`
` 	  {`
` 		val=value(arg);`
` 		append(v, result);//put val at end of result`
` 	  }`
` 	  return result;`
` 	}`

(End of Net)

## QUOTE

(QUOTE argument)::=following
Net
1. Returns a copy of the argument UNCHANGED.

(End of 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
1. it's called an evaluator macro
2. commas inside its argument signify evaluation.
3. no comma in front of an item means it is stored verbatim.

(End of Net)

For example
25. .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

1. Evaluates all the expressions in turn and
2. binds them to the formal arguments.
3. Constructs a result from the values of the formal arguments.
4. Returns the result.

(End of Net)

. . . . . . . . . ( end of section Semantics) <<Contents | End>>