vavavoomy2 <vavavoomy2@yahoo.com> 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:http://www.cliki.net/CLHS>, especially the
part about downloading a copy for your local use]. In the above case,
the section you want is probably the following:

    <URL:http://www.lispworks.com/reference/HyperSpec/Body/03_ababc.htm>
    3.1.2.1.2.3 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":

    <URL:http://www.lispworks.com/reference/HyperSpec/Body/03_a.htm>
    3.1 Evaluation

perhaps starting with:

    <URL:http://www.lispworks.com/reference/HyperSpec/Body/03_ab.htm>
    3.1.2 The Evaluation Model

and then working upwards and outwards from that.


-Rob

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

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607