Interpreters Solutions

Problems

What does lexer turn these into?

1.  
   (1 2 4)
   

   Solution: ['(', 1, 2, 4, ')']

2.  
   xxxxxxxxxx
   (define (f x) 5)
   

   Solution: ['(', 'define', '(', 'f', 'x', ')', 5, ')'],

   • Importantly, 'define' is not broken up into ['d','e','f','i','n','e'] this is because variable names are tokens in scheme so the smallest you can break it apart is into 'define'

What does the parser turn these into?

1.  
   xxxxxxxxxx
   ['(', '+', 1, 2, ')']
   

   Solution: Pair('+', Pair(1, Pair(2, nil)))

2.  
   xxxxxxxxxx
   ['(', 1, '(', 2, ')', 3, ')']
   

   Solution: Pair(1, Pair(Pair(2, nil), Pair(3, nil)))

   • Writing this out without the quotes and commas gives: (1 (2) 3), if we remember the notation for scheme Pair's then we see translate this into calls to cons to construct this list which gives the corresponding Pair structure.
   • (1 (2) 3) -> (cons 1 '((2) 3) ) -> (cons 1 (cons '(2) '(3)) )
   • -> (cons 1 (cons (cons 2 nil) (cons 3 nil)))
   • -> Pair(1, Pair(Pair(2, nil), Pair(3, nil)))

How many calls to scheme_eval/scheme_apply?

For problems 1-3 in this section refer to slides 92-96 of the review slides from Friday for further assistance

1.  
   xxxxxxxxxx
   (define (f x) (* ((lambda () x)) 2))
   

   Solution: 1 eval, 0 apply (function define statements don't evaluate the body so the only eval is the entire statement itself)

2.  
   xxxxxxxxxx
   ((lambda (x y) (+ (y 2) x)) 3 f)
   

   Solution: 16 eval, 5 apply

   • 1 eval for entire line: ((lambda (x y) (+ (y 2) x)) 3 f)

     • 1 eval for operator: (lambda (x y) (+ (y 2) x))

     • 2 evals for operands: 3 and f

     • 1 apply for applying (lambda (x y) (+ (y 2) x)) to 3 and f

       • 1 eval for body: (+ (y 2) x)

         • 1 eval for operator: +

         • 1 eval for operand: (y 2)

           • 1 eval for operator: y

           • 1 eval for operand: 2

           • 1 apply for applying y to 2 (note: y is f from problem 1)

             • 1 eval for body: (* ((lambda () x)) 2)

               • 1 eval for operator: *

               • 1 eval for operand: ((lambda () x))

                 • 1 eval for operator: (lambda () x)

                 • 1 apply for calling (lambda () x)

                   • 1 eval for: x (this is 2)

               • 1 eval for operand: 2

               • 1 apply for applying * to 2 (what ((lambda () x)) evaluated to) and 2

         • 1 eval for operand: x

         • 1 apply for applying + to (y 2) and x

3.  
   xxxxxxxxxx
   (let ((f 4)
         (g f))
        (g (+ f (eval (define h ((lambda (a b) (* a b)) f 5)))))
   )
   

   Solution: 26 eval, 7 apply

   • Important note: eval is an ordinary operator not a special form (eval it like any normal function)

   • 1 eval for entire statement (we notice let is special form so we must evaluate according to the way let works)

     • Assignment part:

       • 1 eval for 4 (which we assign to f)
       • 1 eval for f (which we assign to g)

     • Body (1 eval for entire body):

       • 1 eval for operator: g

       • 1 eval for operand: (+ f (eval (define h ((lambda (a b) (* a b)) f 5))))

         • 1 eval for operator: +

         • 1 eval for operand: f

         • 1 eval for (eval (define h ((lambda (a b) (* a b)) f 5)))

           • 1 eval for operator: eval

           • 1 eval for operand: (define h ((lambda (a b) (* a b)) f 5)) (Define is special form!)

             • 1 eval for: ((lambda (a b) (* a b)) f 5)

               • 1 eval for operator: (lambda (a b) (* a b))

               • 2 eval for operands: f and 5

               • 1 apply for applying (lambda (a b) (* a b)) to f and 5

                 • 1 eval for operator: *
                 • 2 evals for operands: a and b
                 • 1 apply for applying * to a and b

             • *Note: here the expression resembles: `h = (lambda a, b: a * b)(f, 5)in python. In order to sethto the value of the right side we have to evaluate it to figure out what to assignh` to*

             • In contrast, with function definitions we more closely resemble def f(x): return x importantly we don't evaluate the interior until it is called

           • 1 apply for applying eval to (define h ((lambda (a b) (* a b)) f 5)) which evaluated to just h since define returns th variable just assigned. eval calls scheme_eval on the operand so we also have 1 eval in this part

         • 1 apply for applying + to f and (define h ((lambda (a b) (* a b)) f 5)) which evaluates to 20

       • 1 apply for applying g, which evaluates to f from prob 1, onto (+ f (eval (define h ((lambda (a b) (* a b)) f 5)))), which evaluates to 24

         • 1 eval for function body: (* ((lambda () x)) 2)

           • 1 eval for operator: *

           • 1 eval for operand: ((lambda () x))

             • 1 eval for operator: (lambda () x)

             • 1 apply for calling (lambda () x)

               • 1 eval for: x which is 24

           • 1 eval for operand: 2

           • 1 apply for applying * to 2 and x or 24

4.  
   xxxxxxxxxx
   (+ (* (if (and #t) 1 2) 4) (begin (+ 1 2) (+ 3 4)))
   

   Solution: 17 eval, 4 apply

   • 1 eval for entire line

     • 1 eval for operator: +

     • 1 eval for operand: (* (if (and #t) 1 2) 4)

       • 1 eval for operator: *

       • 1 eval for operand: (if (and #t) 1 2)

         • if is special form so we follows the if eval process

         • 1 eval for (and #t)

           • and is special form so it will short circuit after the first true
           • 1 eval for: #t and and ends due to short circuiting

         • because the condition eval'd to true we only eval 1 in the then case

       • 1 eval for operand: 4

       • 1 apply for applying * to 1 (from if statement) and 4

     • 1 eval for operand: (begin (+ 1 2) (+ 3 4))

       • begin is special form so we follow begin's evaling process (evaluate each then return last)

       • 1 eval for (+ 1 2)

         • 1 eval for operator: +

         • 2 evals for operand: 1 and 2

           • 1 apply for applying + to 1 and 2

       • 1 eval for (+ 3 4)

         • 1 eval for operator: +

         • 2 evals for operand: 3 and 4

           • 1 apply for applying + to 3 and 4

     • 1 apply for applying + to (* (if (and #t) 1 2) 4) and (begin (+ 1 2) (+ 3 4))

Generalized counting Eval/Apply

Given these general forms, write the number of Eval/Apply calls in terms of the expressions $a,b,c,d,e$ (for these problems assume these can be anything so we'll generalize by using $\texttt{eval_count}$ and $\texttt{apply_count}$):

1.  
   xxxxxxxxxx
   (define a (+ b c))
   

   Solution:

   • $2+\texttt{eval_count}(b)+\texttt{eval_count}(c)$ evals
   • $1+\texttt{apply_count}(b)+\texttt{apply_count}(c)$ applies

2.  
   xxxxxxxxxx
   (if a b c)
   

   Solution:

   • if $a$ evals to True then:

     • $\texttt{eval_count}(a) +\texttt{eval_count}(b)$ evals
     • $\texttt{apply_count}(a) + \texttt{apply_count}(b)$ applies

   • otherwise then:

     • $\texttt{eval_count}(a)+\texttt{eval_count}(c)$ evals
     • $\texttt{apply_count}(a)+\texttt{apply_count}(c)$ applies

3.  
   (define (fn a b) c)
   

   Solution: 1 eval, 0 apply (we don't evaluate the interior of a function ever)

4.  
   xxxxxxxxxx
   (let ((a b) (c d)) e)
   

   Solution:

   • $\texttt{eval_count}(b)+\texttt{eval_count}(d)+\texttt{eval_count}(e)$ evals
   • $\texttt{apply_count}(b)+\texttt{apply_count}(d)+\texttt{apply_count}(e)$ applies

5.  
   xxxxxxxxxx
   ((lambda (a) b) c)
   

   Solution:

   • $2+\texttt{eval_count}(c)+\texttt{eval_count}(b)$ evals
   • $1+\texttt{apply_count}(c)+\texttt{apply_count}(b$) applies

6.  
   (and a b c)
   

   Solution: The number of evals and applies is dependent on $a,b,c$ (because of short circuiting)

   • If $a$ evals to False then we have the minimum number of evals and applies (and short circuits on the first False value)

     • $\texttt{eval_count}(a)$ evals
     • $\texttt{apply_count}(a)$ applies

   • If $a,b$ both eval to True then we have a maximum number of evals and applies

     • $\texttt{eval_count}(a)+\texttt{eval_count}(b)+\texttt{eval_count}(c)$ evals
     • $\texttt{apply_count}(a)+\texttt{apply_count}(b)+\texttt{apply_count}(c)$ applies

7.  
   xxxxxxxxxx
   (begin a b c)
   

   Solution:

   • $\texttt{eval_count}(a)+\texttt{eval_count}(b)+\texttt{eval_count}(c)$ eval
   • $\texttt{apply_count}(a)+\texttt{apply_count}(b)+\texttt{apply_count}(c)$ apply