# 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