Stacked interpreters (exponential time and byte allocations)

Question

Why is it that when you stack interpreters onto one another, the elapsed real time and byte allocations grow exponentially?

Answer 1

If you do (+ 1 2) in your scheme implementation it will first evaluate the list, then the operand (symbol to value), then it knows if it's a primitive or not so it evaluate the arguments and last it applies the primitive procedure.

Now eval looks something like this (taken from a SICP class handout):

(define (mc-eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
    ((and? exp) (eval-and exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp) (lambda-body exp) env))
        ((begin? exp) (eval-sequence (begin-actions exp) env))
        ((cond? exp) (mc-eval (cond->if exp) env))
        ((application? exp)
         (mc-apply (mc-eval (operator exp) env)
        (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- MC-EVAL"))))

When you call (mc-eval '(+ 1 2) null-environment) you can use substitution rules so you see that after 9 case analysis terms it applies it run apply to the mc-eval of all the sub-expressions:

(mc-eval '(+ 1 2) env) ; ==>

(apply (mc-eval + env) (list (mc-eval 1 env) (mc-eval 2 env))) ; ==>

(apply (cond ((self-evaluating? '+) '+)
             ((variable? '+) (lookup-variable-value '+ env))
             ((quoted? '+) (text-of-quotation '+))
             ((assignment? '+) (eval-assignment '+ env))
             ((definition? '+) (eval-definition '+ env))
             ((if? '+) (eval-if '+ env))
             ((and? '+) (eval-and '+ env))
             ((lambda? '+)
              (make-procedure (lambda-parameters '+) (lambda-body '+) env))
             ((begin? '+) (eval-sequence (begin-actions '+) env))
             ((cond? '+) (mc-eval (cond->if '+) env))
             ((application? '+)
              (mc-apply (mc-eval (operator '+) env)
                        (list-of-values (operands '+) env)))
             (else (error "Unknown '+ression type -- MC-EVAL")))
       (list (cond ((self-evaluating? 1) 1)
                   ((variable? 1) (lookup-variable-value 1 env))
                   ((quoted? 1) (text-of-quotation 1))
                   ((assignment? 1) (eval-assignment 1 env))
                   ((definition? 1) (eval-definition 1 env))
                   ((if? 1) (eval-if 1 env))
                   ((and? 1) (eval-and 1 env))
                   ((lambda? 1)
                    (make-procedure (lambda-parameters 1) (lambda-body 1) env))
                   ((begin? 1) (eval-sequence (begin-actions 1) env))
                   ((cond? 1) (mc-eval (cond->if 1) env))
                   ((application? 1)
                    (mc-apply (mc-eval (operator 1) env)
                              (list-of-values (operands 1) env)))
                   (else (error "Unknown 1ression type -- MC-EVAL")))
             (cond ((self-evaluating? 2) 2)
                   ((variable? 2) (lookup-variable-value 2 env))
                   ((quoted? 2) (text-of-quotation 2))
                   ((assignment? 2) (eval-assignment 2 env))
                   ((definition? 2) (eval-definition 2 env))
                   ((if? 2) (eval-if 2 env))
                   ((and? 2) (eval-and 2 env))
                   ((lambda? 2)
                    (make-procedure (lambda-parameters 2) (lambda-body 2) env))
                   ((begin? 2) (eval-sequence (begin-actions 2) env))
                   ((cond? 2) (mc-eval (cond->if 2) env))
                   ((application? 2)
                    (mc-apply (mc-eval (operator 2) env)
                              (list-of-values (operands 2) env)))
                   (else (error "Unknown 2ression type -- MC-EVAL")))))

Now. This is one layer.. If you evaluate the interpreters evaluation of (+ 1 2) it 's similar (actually a little more since I jump over the initial case analysis) as giving the code above to the underlying Scheme implementation instead of (+ 1 2). A second second layer (cond ((self-evaluating? 1) 1)) is more complex than (+ 1 2)) so it alone turns into larger code to the underlying scheme implementation than the first interpreters expansion of (+ 1 2) and since the very first expression need 9 case terms all larger than the original expression not strange to understand it's exponential when stacking.