Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

Scheme Programming Language

why nested interpreter runs so slow?


hi

why nested interpreter runs so slow? at the fourth layer, it takes
forever for apply to return. what is going on?

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

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc