[Skip Navigation] [Remove Frame] [CS320] [Text Version] lisp.semantics.html Sat Dec 23 08:00:19 PST 2006


    Semantics of LISP

      Internal Representation of a list


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


        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};
        		image:PACKED ARRAY [1..] OF char; {...}
        		CASE type:(number, string, word) IN
        	END {atoms};


        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;
      2. 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
      3. Node(pair, Data(Pair(a, c))), where a is the address of an object
      4. Atom("CAR", word, ...) and c the address of an object
      5. Node(pair, Data(Pair(b, null_address))) where b is the address of an object
      6. Atom("B", word,...).

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

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

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

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


      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.


      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.


    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.


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

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


      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.


      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.


      The "Q" in "SETQ" indicates that the atom is quoted.
       	"(" "SETQ" a e ")" = "(" "SET" "(" "QUOTE" a ")" e ")"
       	"(" 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 variable espression)::=following
      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 e1 e2 e3 e4 ...)::=following
      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)
         		append(v, result);//put val at end of result
         	  return result;

      (End of Net)


      (QUOTE argument)::=following
      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
      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

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