When you have something like:
(car (cdr (cdr '(1 2 3 4))))
What is happening with the interpreter?
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?
Does it substitute the arguments like a macro, into the function?
I am so curious, hope someone here knows and wishes to explain.
Thanks,
Vera
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.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
··········@yahoo.com (vavavoomy2) writes:
> When you have something like:
>
> (car (cdr (cdr '(1 2 3 4))))
>
> What is happening with the interpreter?
>
> 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?
>
> Does it substitute the arguments like a macro, into the function?
>
> I am so curious, hope someone here knows and wishes to explain.
>
> Thanks,
> Vera
It really depends on the implementation.
Some implementations don't have an interpreter at all. They compile
all expressions to native binary code and let the processor run it.
Some implementations compile to some intermediary code that is
interpreted by a virtual machine. Well, we cannot really say
interpreted in that case: it's really compiled like above, only that
it's not target to the native processor but to a virtual processor.
Some implementations just interpret the sexp tree. That's not
difficult at all:
(defmacro my-defun (name arg-list &body body)
`(progn (setf (symbol-function ',name) (lambda ,arg-list (progn ,@body)))
',name))
(defun my-apply (fun &rest effective-arg-list)
(let* ((lambda-exp (function-lambda-expression fun))
(formal-arg-list (cadr lambda-exp))
(sexp (caddr lambda-exp)))
(if (eq 'lambda (car lambda-exp))
;; let's skip the argument binding
(my-eval sexp)
;; a primive function
(funcall (function apply) fun effective-arg-list))));;my-apply
(defun my-eval (sexp)
(cond
((symbolp sexp) (symbol-value sexp))
((atom sexp) sexp)
(t (case (car sexp)
;; you only need here the code for the special operators
;; and the primitive functions.
((car) (car (my-eval (cadr sexp))))
((cdr) (cdr (my-eval (cadr sexp))))
((cons) (cons (my-eval (cadr sexp)) (my-eval (caddr sexp))))
((eq) (eq (my-eval (cadr sexp)) (my-eval (caddr sexp))))
((quote) (cadr sexp)) ;; no eval!
((if) (if (my-eval (cadr sexp))
(my-eval (caddr sexp)) ;; evals only the
(my-eval (cadddr sexp)))) ;; selected branch!
((setq) (setf (symbol-value (cadr sexp)) (my-eval (caddr sexp))))
((rplaca) (rplaca (my-eval (cadr sexp)) (my-eval (caddr sexp))))
((progn)
(my-eval (cadr sexp))
(if (cddr sexp) (my-eval (cons 'progn (cddr sexp)))))
;; the rest is standard function call
;; (code for macro expansion left as an exercise to the reader).
(otherwise
(my-apply (symbol-function (car sexp))
(mapcar (function my-eval) (cdr sexp))))))));;my-eval
Now, try:
(trace my-eval my-apply)
(my-eval '(car (cdr (cdr (quote (1 2 3 4))))))
(my-eval '(if (eq (quote a) (car (cons (quote a) (quote b))))
(car (quote (1 2 3))) (cdr (quote (a b c)))))
(my-eval '(if (eq (quote a) (quote b))
(car (quote (1 2 3))) (cdr (quote (a b c)))))
--
__Pascal Bourguignon__
vavavoomy2 asked: What is happening with the interpreter?
One of the irritating things about PRINT is that it prints
everything out twice:
* (print "foo")
"foo"
"foo"
Later you realise that that is not what is happening. PRINT
is printing the first "foo", and returning "foo" as its
values. The REPL is printing the second "foo" because its
job is to print the returned value.
So this double printing turns out to be a feature not a bug.
You can wrap forms in PRINT to see what they do, without
consuming their value.
(+ 1 (* 2 3)) => 7
(print (+ (print 1)
(print (* (print 2)
(print 3)))))
1
2
3
6
7
=> 7
(car (cdr (cdr '(1 2 3 4)))) => 3
(car (print (cdr (print (cdr (print '(1 2 3 4)))))))
(1 2 3 4)
(2 3 4)
(3 4)
=> 3
For a more sophisticated example, imagine that you are
taking your first steps in writing macros
(defmacro my-dotimes ((loop-var count) &body code)
`(prog((,loop-var 0))
top-of-loop
(when (= ,loop-var ,count) (return 'done))
,@code
(incf ,loop-var)
(go top-of-loop)))
You try it out (my-dotimes (i 5)(print (expt 2 i)))
1
2
4
8
16
DONE
Looks OK
Second try (my-dotimes (i (print 5))(print (expt 2 i)))
5
1
5
2
5
4
5
8
5
16
5
DONE
Hmm, where did all those five's come from, the built in
dotimes doesn't do that.
* (macroexpand-1 '(my-dotimes ((i (print 5))
(print i))))
(PROG (((I (PRINT 5)) 0))
TOP-OF-LOOP
(WHEN (= (I (PRINT 5)) (PRINT I)) (RETURN))
(INCF (I (PRINT 5)))
(GO TOP-OF-LOOP))
Ah ha! It is clear in the macroexpansion what went wrong,
but what to do about it?
Back to the book to study the section on multiple
evaluation.
--------oOo----------
If you want to instrument your code to see what is
happening when, you could use a function defined to act as
a wrapper on a variable. You set it up like this:
(defvar *x*)
(defun f ()
(format t "Reading ~A from x~%" *x*)
*x*)
(defun (setf f)(value)
(format t "Setting x to ~A~%" value)
(setf *x* value))
* (setf (f) 6)
Setting x to 6
6
* (incf (f))
Reading 6 from x
Setting x to 7
7
One can go a little further
(define-symbol-macro x (f))
Then
* (setf x 10)
Setting x to 10
10
* (setf x (/ x 2))
Reading 10 from x
Setting x to 5
5
* (setf x '(1 2 3 4))
Setting x to (1 2 3 4)
(1 2 3 4)
* (setf x (car (cdr (cdr x))))
Reading (1 2 3 4) from x
Setting x to 3
3
* (prog2 (setf x 2)
(sqrt x)
(incf x))
Setting x to 2
Reading 2 from x
Reading 2 from x
Setting x to 3
1.4142135
Learning CL suffers from a boot strapping problem. If you
already know it, you have access to a variety of cool
features that make it easy to learn :-)
Alan Crowe
Edinburgh
Scotland
From: ··········@YahooGroups.Com
Subject: Re: order of evaluation (newbie)
Date:
Message-ID: <REM-2004jul22-006@Yahoo.Com>
> From: ··········@yahoo.com (vavavoomy2)
> When you have something like:
> (car (cdr (cdr '(1 2 3 4))))
> What is happening with the interpreter?
Do you perhaps mean the Read-Eval-Print loop, if you manually type in
that line of text, or copy&paste that text as if typed in? If so:
(1) That text, a stream of characters, is passed through READ, which
parses it and returns a hierarchial structure.
(2) That heirarchial structure is passed to EVAL, which returns something.
(3) Whatever EVAL returned, is now passed to PRINT, which converts that
into a stream of characters which is emitted to your computer screen.
You are interested in what EVAL does: It starts at the trunk of the
hierarchial structure, and descends into it deeper and deeper so long
as it sees things that need to be evaluated. Then it returns results
back upward and uses APPLY to pass them as arguments to functions (CAR
and CDR in your example) and passes the returned values back up.
Whatever the toplevel APPLY returns, that's what EVAL returns.
In your example, note that '... is a reader macro that generates
(quote ...), so your example really reads:
(car (cdr (cdr (quote (1 2 3 4)))))
So here's what happens:
- (car ...) - That's a function call form, so it goes deeper.
- ... (cdr ...) ... - That's another function call form, so it goes deeper.
- ...... (cdr ...) ...... - That's another fcf, so it goes deeper.
- ........ (quote (1 2 3 4)) ........ - That's a special form which
simply returns the first argument as-is without evaluating, so (1 2 3
4) gets returned at this point.
- APPLY is used to call the function cdr with argument (1 2 3 4), and
cdr returns (2 3 4) so APPLY returns (2 3 4) so EVAL at that level
returns (2 3 4).
- APPLY is used to call the function cdr with argument (2 3 4), and cdr
returns (3 4), so APPLY returns (3 4), so EVAL at that level returns
(3 4).
- APPLY is used to call the function car with argument (3 4), and car
returns 3, so APPLY returns 3, so EVAL at that level returns 3, but
that was the top level of EVAL, so 3 is what will be printed.
Now your particular ReadEvalPrint loop is permitted to make
optimizations so it doesn't have to go to exactly all that work, but
the result must be the same as if it had done it that way.
> 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?
The time-sequence of calls to APPLY are bottom-upward, and likewise the
calls to car and cdr that occur inside the calls to APPLY, whatever
functions you express in the form you typed in, are called
bottom-upward, but the calls to EVAL are recursive, i.e. the topmost
EVAL is called first but returns last, the second level EVAL is called
second but returns next-to-last, etc. And if you type a form that
mentions functions with more than one argument, such as if you type:
(+ (car '(1 2)) (car (cdr '(3 4))))
everything within the first argument is completed before anything in
the second argument is done and finally the APPLY is done (in this case
in regard to the function + which takes two arguments here). So the
toplevel EVAL starts first, then the second level EVAL for the first
argument to + starts and does a bunch of stuff and returns, then the
second level eval for the second argument to + starts and does a bunch
of stuff and returns, and then the APPLY of + to those two evaluated
arguments happens, and finally the toplevel EVAL returns.
If you've never written a recursive function, you probably won't really
understand how EVAL works. If that's the case, try writing your first
recursive function, something that traverses a heirarchial (tree)
structure, accumulating things it sees in the leaves and returning the
accumulation to the next higher level to be accumulated there. For
example, write this in Lisp, or write the equivalent in C or your
favorite language:
(defun addleaves (foo)
(cond ((numberp foo) foo)
((consp foo) (+ (addleaves (car foo)) (addleaves (cdr foo))))
(t 0)))
Then test it like this:
* (setq x '(1 10 (1000 100) (2 . 4)))
(1 10 (1000 100) (2 . 4))
* (addleaves x)
1117
Heck, just type in the above without thinking, but after defining the
function but before calling it, trace it. In CMUCL, just say (trace
addleaves), not sure if same in other CLs. When you then call the
function on the value of x, you'll get a nicely indented listing
showing every time APPLY is called and every return result from APPLY.
When I did it here, the first few trace lines came out like this:
0: (ADDLEAVES (1 10 (1000 100) (2 . 4)))
1: (ADDLEAVES 1)
1: ADDLEAVES returned 1
1: (ADDLEAVES (10 (1000 100) (2 . 4)))
2: (ADDLEAVES 10)
2: ADDLEAVES returned 10
2: (ADDLEAVES ((1000 100) (2 . 4)))
and the last few trace lines came out like this:
2: ADDLEAVES returned 1106
1: ADDLEAVES returned 1116
0: ADDLEAVES returned 1117
If you can understand how a simple recursive function like addleaves
works from that trace, then you're ready to understand how the more
complicated recursive function EVAL works. You wouldn't want to
actually trace EVAL or APPLY or CAR or CDR, disaster! But if you wrote
your own version of EVAL and APPLY, call them MY-EVAL and MY-APPLY, you
could trace those functions without problem. Maybe one of the experts
can point you to such toy versions of EVAL and APPLY which you could
play with in that way?
Disclaimer: Perhaps FUNCALL rather than APPLY is used to apply the
function to the already-evaluated arguments. I'm not sure. It doesn't
matter for the purpose of this explanation.
> Does it substitute the arguments like a macro, into the function?
No. Although if this is part of code inside a function being compiled,
and the entire expression is a constant at compile time, it might
generate code that simply returns the constant result without needing
to compute it at runtime, which seems a bit like macro expansion.