What do you think?
> why nested interpreter runs so slow? at the fourth layer, it takes
> forever for apply to return. what is going on?
Let's have a look at how you'd interpret (quote x)
(define (eval f e)
((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
Every time you add a layer, you multiply the complexity. To
interpeter a form with L layers of interpreters, you get a complexity