Subject: Re: order of evaluation (newbie)
From: (Rob Warnock)
Date: Sun, 18 Jul 2004 21:09:33 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
vavavoomy2 <> wrote:
| When you have something like:
|   (car (cdr (cdr '(1 2 3 4))))
| What is happening with the interpreter?

As Pascal Bourguignon noted, Common Lisp does not require that there
even *be* an "interpreter" -- everything might always be compiled.[1]
(Or not.)

| Does it have the structure of that line into a tree, and then it
| evaluates from the bottom up?    So is every leaf list evaluated
| before its parent?

Yes, in general (ignoring many details on permitted compile-time
optimizations). Common Lisp (like Scheme, or for that matter, C)
is a "call-by-value" language, which implies that all of the arguments
to a function must have been evaluated before the function is called.

But moreover, Common Lisp requires left-to-right evaluation of function
arguments (again, ignoring some details about non-function-call forms,
such as macros and special forms).

For details of the required ordering [and many, many other questions
you're probably going to have eventually], see the Common Lisp HyperSpec
(CLHS) [see pointers at <URL:>, especially the
part about downloading a copy for your local use]. In the above case,
the section you want is probably the following:

    <URL:> Function Forms
    The subforms in the cdr of the original form are evaluated in
    left-to-right order in the current lexical and dynamic environments.
    The primary value of each such evaluation becomes an argument to the
    named function...

| Does it substitute the arguments like a macro, into the function? 

Given the simple example you ask about above [especially given
that the innermost argument is literal quoted data, and therefore
may be presumed to be an immutable constant (see CLHS "Special
Operator QUOTE")], a "sufficiently-smart compiler" might, if CAR
and CDR were inlineable in that context, reduce the entire form
to the constant 3 at compile time. Or not.

| I am so curious, hope someone here knows and wishes to explain.  

You would do well to read the entire section of the CLHS on "Evaluation":

    3.1 Evaluation

perhaps starting with:

    3.1.2 The Evaluation Model

and then working upwards and outwards from that.


[1] But CLHS "3.1 Evaluation" and "3.2 Compilation" (particularly
    " Minimal Compilation") contain the precise specification
    of the minimum an implementation is required to do.

Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607