dillog
@gmail.com writes:
> why nested interpreter runs so slow? at the fourth layer, it takes
> forever for apply to return. what is going on?
What do you think?
Let's have a look at how you'd interpret (quote x)
(define (eval f e)
(cond
((atom? f) ...)
((eq? 'quote (car f)) (cadr f))
... some other tests for special operators
(else (apply (eval (car f)) (mapcar (lambda (arg) (eval arg e)) (cdr f))))))
So when you call (eval '(quote x) env)
you must test (atom? f), (eq? 'quote (car f)) and finally evaluate (cadr f).
Now, if you do it from another layer of intepretation, you have to do all that.
For (atom? f), you have to test (atom? g), (eq? 'quote (car g)), (eq?
'if (car g)), etc and finally (apply (car g) ...)
For (eq? 'quote (car f)) idem.
For (cadr f) idem.
And if you add another layer...
Assume that to interpret a form you need to execute N interpreter
instructions, if you interpret the interpreter, then to interpret
that form, you'll need to run N*N interperter interpreter
instructions.
Every time you add a layer, you multiply the complexity. To
interpeter a form with L layers of interpreters, you get a complexity
of O(N^L).
--
__Pascal Bourguignon__
http://www.informatimago.com
http://pjb.ogamita.org