The Pitmanual: The Evaluator


Evaluation	Concept	`The Lisp Interpreter`

When you type a form to the toplevel Lisp reader, the EVAL function is called to interpret that form. This is a somewhat sketchy description of how evaluation behaves by default; it ignores the fancy features, which are described elsewhere.

If the form to EVAL is a number, the number is returned. Numbers are said to self-evaluate.

(eval '7)
7

If the form to EVAL is a symbol, the symbol's value is returned.

(eval 'X)
3 ;if X is bound to 3

If the form to EVAL is a list, the evaluation of the list depends upon the car of the list.

If the car of the list is an atom other than a symbol, an error will result.

If the car of the list is a non-list, it should be a LAMBDA expression to be applied. The arguments are evaluated from left to right, then bound in parallel to the variables named in the bound variable list of the LAMBDA. Then the body of the LAMBDA is evaluated and its result returned (see LAMBDA).

(eval '((lambda (x) (plus x x)) 2.5))
5.0

If the car of the list to be evaluated has a normal functional definition (or an array definition), the arguments are evaluated from left to right. The function's definition is then applied to those arguments. (In the case of an array, the arguments are the indices of the slot to be accessed.) For information about defining functions, see documentation on DEFUN.

(eval '(+ (* 2 3) 1))
7

If the car of the list to be evaluated has a fexpr or fsubr definition, then the arguments are not evaluated. It is up to the function to decide which [parts] of the arguments are to be evalauted, if any. There are a number of system-provided fsubrs. Users can write such functions, but are encouraged not to; whenever possible, they should prefer to write normal functions, or in some cases macros.

(eval '(comment comments dont eval their args ever))
COMMENT

If the car of the list is the name of a macro, then MACROEXPAND is called on the list and then EVAL is called recursively on the macroexpanded result.

;; This first expands to ((lambda (x) (+ x 4)) 7), then evals as above
(eval '(let ((x 2.5)) (plus x x))) 
5.0

If the car of the list is a symbol which is not defined, but which has an AUTOLOAD property, the filename which is the value of that property is loaded and then EVAL is retried.

By default, hunks are evaluated like lists, but their “middle” is ignored. This behavior can be usefully modified to implement extended datatypes. Such extensions, however, are beyond the scope of this draft.

See also: Hunks

Variables


Variable	Concept	`Program Constituent`

Atomic symbols are used to name variables in Lisp. When the evaluator tries to evaluate a symbol, it will return the contents of that symbol's “value cell.” For example, if X's value cell contains the number 5, then (+ X 1) will produce 6.

See also: SETQ, SYMBOL, SYMEVAL, BOUNDP


`SETQ`	Special Form	`(SETQ sym₁ exp₁ sym₂ exp₂ ...)`

To assign values to variables, we use SETQ. The body of a SETQ consists of pairs which are processed sequentially, left to right. The first member of each pair is the variable, the second is the value. The value is evaluated but the variable is not. The variable in each case is set to the value specified. For example:

(SETQ X 7) ; gives the variable X a value of 7

Note that the first assignment is fully processed before the second assignment is. This means that if one writes:

(SETQ X 3)
(SETQ X (+ X 1) Y (* X 2))

the result will be that Y has a value of 8 and X has a value of 4. We call this sequential assignment. It is a common error for beginners to believe that Y might be bound to 6 after this form because they believe both computations might be done before the assignments are made, but this is not the case. For that to be true would require parallel assignment; see PSETQ.

The value returned by SETQ is the last value assigned, i.e. the value of its last argument.

The special symbols T and NIL may not be assigned as they are intended to be constants. Attempting to SETQ them will signal an error.

See also: PSETQ, DESETQ, SET, BOUNDP


`PSETQ`	Special Form	`(PSETQ sym₁ exp₁ sym₂ exp₂ ...)`

Like SETQ, but values are assigned in parallel, not in series. Unlike SETQ, the return value of PSETQ is not guaranteed to be anything in particular; it will probably be one of the values assigned, but this is not something code should depend on.

(progn (setq x 'a y 'b)
       (psetq x y y x)
       (list x y))
=> (B A)

Multics users must (%include other_other) to get PSETQ.


`QUOTE`	Special Form	`(QUOTE exp)`

Quote returns its unevaluated argument. Quote is used to include constants in a form. For convenience, the read function normally converts any S-expression preceded by the apostrophe (acute accent) character into this form, so 'exp is the same as (QUOTE exp).

Examples:

(LIST (+ 3 4) '(+ 3 4))	=>	(7 (+ 3 4))

(LIST 'BASE BASE)	=>	(BASE 10)

(LIST 'A (QUOTE A))	=>	(A A)

Definition:

(DEFUN QUOTE FEXPR (X) (CAR X))


`EVAL`	Function	`(EVAL form [pdlptr])`

In the one arg case (which is most frequent) evaluates form just as if it had been typed in at toplevel (except that all bindings are still in effect) and returns the result.

Note that since EVAL is a function, it receives its arguments already evaluated. Since it will then evaluate the argument itself, it may seem as though the evaluation is double.

A stack pointer, pdlptr, can be supplied as an optional second argument. In that case, the evaluations occurs in the binding context specified by that pointer. The use of stack pointers is an advanced concept which is not yet described well in this manual. For now, see documentation on EVALFRAME for more information.

Examples:

(EVAL (+ 3 4))		=> 7 ;7 self-evaluates

(EVAL '(+ 3 4))		=> 7

(EVAL ''(+ 3 4))	=> (+ 3 4)

(EVAL (LIST '+ 3 4))	=> 7

(EVAL '(LIST '+ 3 4))	=> (+ 3 4)

(EVAL ''(LIST '+ 3 4))	=> (LIST (QUOTE +) 3 4)


`EVAL`	Style Note	`Using EVAL`

The author disapproves of the use of EVAL in production code. It is almost always too powerful for the task required. Its inclusion in the language is primarily to allow the implementation of imbedded languages. Because many variable names are “compiled out” by the compiler, EVAL may not behave in the expected way in compiled code. If you ever find yourself writing a FEXPR definition wanting to call EVAL, you almost certainly want to be using a MACRO instead.

Dynamically Scoped Functions


`FUNCTION`	Special Form	`(FUNCTION f)`

Function is like quote except that its argument is a function. It is used when passing a functional argument (so that the compiler can recognize it as a form which can be compiled. Otherwise it would have to leave lambda expressions alone, as it would with any other constant list structure in case the user was planning to use list-manipulation operators on the lambda expression).

Just as (QUOTE thing) can be written 'thing, there is also a syntactic abbreviation for (FUNCTION thing), which is #'thing.

Typically, the thing quoted is a lambda expression. It is also acceptable to quote symbols which are being used to name functions. In the case of f being a symbol, QUOTE and FUNCTION have the same effect. FUNCTION is preferred, however, because it makes it clear to the user how the symbol is being used.

For more information about lambda expresions, see LAMBDA.

Note: FUNCTION makes no attempt to solve the “funarg problem.” For a partial solution to that problem, see documentation about *FUNCTION.

;; Simple example using lambda
(mapcar (function (lambda (x) (+ x 2))) '(1 2 3))
=> (3 4 5)

(mapcar (function car) '((A B C) (D E F) (G H I)))
=> (A D G)

;; Shorthand notation (preferred)
(mapcar #'(lambda (x y) (+ x y)) '(1 2 3) '(3 2 1))
=> (4 4 4)

;; Use #'sym for symbols used as functions
(mapcar #'cadr '((a b c) (d e f) (g h i)))
=> (B E H)

;; Use 'sym for symbols not used as functions
(setq x 'something)
=> SOMETHING

Funargs


*`FUNCTION`**	Special Form	`(*FUNCTION f [alist])`

The value of (*FUNCTION f) is a "funarg" of the function f. A funarg can be used like a function. It has the additional property that it contains an “a-list pointer” (actually, a stack pointer; see EVALHOOK) so that the values of variables are bound the same during the application of the funarg as at the time it was created, provided that the binding environment in which the funarg was created still exists on the stack. Returning the funarg upward on the stack higher than its creation point, or putting its value in a global location that can be accessed after return past that point on the stack is expressly not guaranteed and sure to lose badly.

*FUNCTION is intended to help solve the “funarg problem,” however it only works in some easy cases. In particular, two general cases of the funarg problem are not solved. Funargs generated by *FUNCTION are not “first class”; i.e., they are intended for use as functional arguments and cannot be used as return values from functional applications. Thus, the user should be careful in his use of *FUNCTION to make sure that his use does not exceed the limitations of the funarg mechanism.

Web-Only Note:

The two-argument version of *FUNCTION was controversial and partly went away. I tried it in a recent version of MACLISP (version 2149) and got:

(*function foo (a))
;((*FUNCTION FOO (A)) ?) WRONG NUMBER OF ARGS TO FSUBR

A funarg is just a normal cons of the form:

(FUNARG f . alist)

and the alist is actually a stack pointer. For more details about stack frames and stack pointers, see documentation on EVALFRAME.

Examples:

(DEFUN FOO (F X) (LIST X (FUNCALL F X)))	=>	FOO

(DEFUN BAR (Y) (+ X Y))				=>	BAR

(SETQ X 5)					=>	5

(FOO ( FUNCTION BAR) 2)				=>	(2 4)

(FOO (*FUNCTION BAR) 2)				=>	(2 7)

(FOO (PROG (A B C) (RETURN ( FUNCTION BAR))) 2)	=>	(2 4)

(FOO (PROG (A B C) (RETURN (*FUNCTION BAR))) 2) =>	error!

Web-Only Note:

My belief is that, although the *FUNCTION interface to creating this kind of closure seems now to be gone, you can still access the underlying functionality by following these notes I found among my files:

Date: 04/15/81 23:35:20
From: KRD at MIT-AI
To:   KMP at MIT-AI

By the way, how do I do closures in maclisp?  I tried the *FUNCTION
but it seemed not to do the right thing.  Can you send me a simple
example?  thanks.

R.

Date: 16 April 1981 14:32-EST
From: Kent M. Pitman <kmp at MIT-MC>
Sender: ___046 at MIT-MC
Subject: Closures in Maclisp
To: KRD at MIT-MC
cc: KMP at MIT-MC

Well, here's an example of something that should work:

  (DEFUN CONS-A-CLOSURE (FN &REST ALIST)
    `(FUNARG ,FN ,@ALIST . T))

  (DEFUN INCREMENT-I () (SETQ I (1+ I)))

  (SETQ NATURAL-NUMBER-GENERATOR (CONS-A-CLOSURE #'INCREMENT-I '(I . 0)))

  (DEFUN N () (FUNCALL NATURAL-NUMBER-GENERATOR))

  (LIST (N) (N) (N))

Basically, if you call *FUNCTION, you get back something that looks like
  (FUNARG fn . pdl-pointer)

but there used to be this form of *FUNCTION that allowed an alist 
specification somehow -- i forget the syntax. Anyway, it would cons
a form looking like

  (FUNARG fn (var1 . val1) (var2 . val2) ... (varN . valN) . T)

The ". T)" has to do with the fact that this closure can be passed upward 
and downward and hacks only the variables in the given alist but is stack
frame independent. The interpreter still understands this. Hence, forms 
like

  ((FUNARG (LAMBDA () I) (I . 3) . T))

will work. This returns 3, as you might guess. The CONS-A-CLOSURE will
compile, too, since it creates the closures at runtime and FUNCALL will
just do an interpreted call to the FUNARG, which will recall fn, which
can have been compiled and things will still work. e.g.,

  ((FUNARG CAR . T) '(A))

will correctly return A. Hope you find this useful. I can't guarantee this
feature won't disappear overnight, but if it does, I'll show you some other
ways that you can get the same effect if you do a bit more work. -kmp

The APPLY Family


`APPLY`	Function	`(APPLY fn argl [pdlptr])`

In the common case (with two args) just applies the function fn to the list of arguments, argl.

Unless fn is an FSUBR or FEXPR such as COND or AND which evaluates its arguments in a funny way, the arguments in the list argl are used without being evaluated.

A stack pointer, pdlptr, can be supplied as an optional third argument. In that case, the application occurs in the binding context specified by that pointer. The use of stack pointers is an advanced concept which is not yet described well in this manual. For now, see documentation on EVALFRAME for more information.

   ;; Some initializations
   (setq f '+)
   => +

   (defun f (x y z) (list z y x))	
   => F	

   ;; Some tests

   (apply f '(1 2 3))
   => 6

   (apply 'f '(1 2 3))
   => (3 2 1)

   (apply 'cons '((+ 2 3) 4))
   => ((+ 2 3) . 4)			; not (5 . 4) !!

The CALL Family


`FUNCALL`	Function	`(FUNCALL f arg₁ arg₂ ...)`

Calls the function f with the arguments arg₁, arg₂, .... It is similar to apply except that the seperate arguments are given to funcall, rather than a list of arguments. If f is an expr, a lexpr, a subr, or an lsubr, the arguments are not re-evaluated. If f is a fexpr or an fsubr there must be exactly one argument. f may not be a macro.

;; simple examples
(funcall #'+ 1 2)
=> 3

(funcall #'list 'a 'b 'c)
=> (A B C)

(funcall #'(lambda (a b) (+ a (* 2 b))) 1 4)
=> 9

;; funcalling variable quantities
(defun f3 (fn x) (funcall fn x 3))
=> F3

(f3 #'+ 4)
=> 7

(f3 #'(lambda (x y) (cons y x)) 'A)
=> (3 . A)

;; Normally, naming variables the same as functions is a 
;; very bad idea, but we do it here to make a point...
(setq cons #'list)
=> LIST

(funcall #'cons 3 4)
=> (3 . 4)

(funcall 'cons 3 4)
=> (3 . 4)

(funcall cons 3 4)
=> (3 4)

For the amusement of sophisticated readers, we provide the following almost meta-circular description of FUNCALL ...

(DEFUN FUNCALL (F &REST ARG-LIST)
  (LEXPR-FUNCALL F ARG-LIST))


`LEXPR-FUNCALL`	Function	`(LEXPR-FUNCALL f arg₁ arg₂ ... argN restargs)`

Calls the function f with the arguments arg₁, arg₂, .... and each of the elements of restargs (which should be a list). With 2 args, is similar to APPLY. Stack frame made is much different, though.

;; Simple examples
(lexpr-funcall #'+ 1 2 '(3 4 5))
=> 15.


(lexpr-funcall #'list '(a b) '(c d) '(e f))
=> ((A B) (C D) E F)	

(lexpr-funcall #'+ '(1 2 3 4))
=> 10.

;; The two-argument case is the same as the two-argument case of APPLY
(apply #'+ '(1 2 3 4))
=> 10.

Although using fexprs at all is a discouraged practiced, a programmer may sometimes encounter a need to APPLY or LEXPR-FUNCALL a fexpr. It should be noted that the application strategies are different for these functions in that case. LEXPR-FUNCALL treats fexprs like any other function of one argument, while APPLY passes its second argument as the single argument to the fexpr. If you understand the following sequences, you're probably on the right track:

With an expr... The same thing with a fexpr...
;; Make a simple function ;; Make G be a fexpr form of F
(defun f (x) (list 'answer x)) (putprop 'g (get 'f 'expr) 'fexpr)
F (LAMBDA (X) (LIST 'ANSWER X))
(f 'a) (g a)
(ANSWER A) (ANSWER (A))
(lexpr-funcall #'f '(a)) (lexpr-funcall #'g '(a))
(ANSWER A) (ANSWER A)
(apply #'f '(a)) (apply #'g '(A))
(ANSWER A) (ANSWER (A))
(lexpr-funcall (get 'f 'expr) '(a)) (lexpr-funcall (get 'g 'fexpr) '(A))
(ANSWER A) (ANSWER A)
(apply (get 'f 'expr) '(a)) (apply (get 'g 'fexpr) '(A))
(ANSWER A) (ANSWER A)

LEXPR-FUNCALL has a number of peculiar bits of trivia known about it which are of little or no practical value, but are included here for the reader's amusement. For example, it can be meta-circularly defined by:

(DEFUN LEXPR-FUNCALL (F &REST STUFF)  ;Meta-circular definition
  (LEXPR-FUNCALL #'LEXPR-FUNCALL F STUFF))

If you followed that, you might also enjoy noting that

(LEXPR-FUNCALL #'FUNCALL f x1 x2 ...)

is the same as

(LEXPR-FUNCALL f x1 x2 ...).

Perhaps surprisingly, so is

(LEXPR-FUNCALL #'FUNCALL #'FUNCALL #'FUNCALL f x1 x2 ...).

Multics users must (%include other_other) to use LEXPR-FUNCALL.


`SUBRCALL`	Special Form	`(SUBRCALL type subrobj arg₁ arg₂ ...)`

Like ARRAYCALL and LSUBRCALL. The type argument is not evaluated; it must be one of the symbols NIL, T, FIXNUM, or FLONUM. The other arguments are evaluated. The subrobj must evaluate to a subr object. It is called with an argument list made by evaluating arg₁, arg₂, etc. The subr should return an argument which matches the given type description. NIL and T mean type `any'. FIXNUM and FLONUM are apropriate only if the user guarantees the type of the return value of the subr will be correct and the subr object belongs to a subr which was appropriately declared FIXNUM or FLONUM when compiled. Because Lisp programs are not required to be type declared, most functions (even many system functions) which always return numbers are not appropriate for SUBRCALLing with the FIXNUM or FLONUM keyword. When unsure, be safe and use type NIL. Note also that any function of more than five arguments is an LSUBR even if it takes a fixed number of arguments (see LSUBRCALL).

Note: A common error is to assume that it follows from a guaranteed return value type that the function obeys the right calling convention for SUBRCALL or LSUBRCALL with a FIXNUM or FLONUM type; the function +$, for example, cannot be LSUBRCALL'd with a FLONUM type even though it always returns a flonum result.


`LSUBRCALL`	Special Form	`(LSUBRCALL type lsubrobj arg₁ arg₂ ...)`

Like SUBRCALL, but for lsubr objects (e.g., a compiled lexpr or a compiled expr which had more than 5 arguments).


`SUBRP`	Function	`(SUBRP q)`

[Multics Only] Predicate returns T if q is a subr, and NIL otherwise.

On PDP-10's subrs are of type RANDOM, and are indistinguishable from non-subr objects of the same datatype.

Examples:

(SUBRP 'CAR)			=>	NIL

(SUBRP (GET 'CAR 'SUBR))	=>	T

(SUBRP (GET 'QUOTE 'FSUBR))	=>	T


With an expr...	The same thing with a fexpr...
`;; Make a simple function`	`;; Make G be a fexpr form of F`
`(defun f (x) (list 'answer x))`	`(putprop 'g (get 'f 'expr) 'fexpr)`
`F`	`(LAMBDA (X) (LIST 'ANSWER X))`
`(f 'a)`	`(g a)`
`(ANSWER A)`	`(ANSWER (A))`
`(lexpr-funcall #'f '(a))`	`(lexpr-funcall #'g '(a))`
`(ANSWER A)`	`(ANSWER A)`
`(apply #'f '(a))`	`(apply #'g '(A))`
`(ANSWER A)`	`(ANSWER (A))`
`(lexpr-funcall (get 'f 'expr) '(a))`	`(lexpr-funcall (get 'g 'fexpr) '(A))`
`(ANSWER A)`	`(ANSWER A)`
`(apply (get 'f 'expr) '(a))`	`(apply (get 'g 'fexpr) '(A))`
`(ANSWER A)`	`(ANSWER A)`