`(1 2 4)`

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

`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'`

- Importantly, 'define' is

`xxxxxxxxxx`

`['(', '+', 1, 2, ')']`

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

`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)))`

- Writing this out without the quotes and commas gives:

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

`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)`xxxxxxxxxx`

`((lambda (x y) (+ (y 2) x)) 3 f)`

**Solution:**16 eval, 5 apply1 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:

1 eval for operand:

*2*1 apply for applying

`*`

to`2`

*(what*and`((lambda () x))`

evaluated to)`2`

1 eval for operand:

`x`

1 apply for applying

`+`

to`(y 2)`

and`x`

`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`

)

- 1 eval for
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`

- 1 eval for operator:

*Note: here the expression resembles: `h = (lambda a, b: a * b)(f, 5)

`in python. In order to set`

h`to the value of the right side we have to evaluate it to figure out what to assign`

h` 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 241 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:

1 eval for operand:

`2`

1 apply for applying

`*`

to`2`

and`x`

or 24

`xxxxxxxxxx`

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

**Solution:**17 eval, 4 apply1 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 process1 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 apply for applying

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

1 apply for applying

`+`

to`(* (if (and #t) 1 2) 4)`

and`(begin (+ 1 2) (+ 3 4))`

Given these general forms, write the number of Eval/Apply calls in terms of the expressions (for these problems assume these can be anything so we'll generalize by using and ):

`xxxxxxxxxx`

`(define a (+ b c))`

**Solution:**- evals
- applies

`xxxxxxxxxx`

`(if a b c)`

**Solution:**if evals to

`True`

then:- evals
- applies

otherwise then:

- evals
- applies

`(define (fn a b) c)`

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

`(let ((a b) (c d)) e)`

**Solution:**- evals
- applies

`xxxxxxxxxx`

`((lambda (a) b) c)`

**Solution:**- evals
- ) applies

`(and a b c)`

**Solution:**The number of evals and applies is dependent on (because of short circuiting)If evals to

`False`

then we have the minimum number of evals and applies (`and`

short circuits on the first`False`

value)- evals
- applies

If both eval to

`True`

then we have a maximum number of evals and applies- evals
- applies

`xxxxxxxxxx`

`(begin a b c)`

**Solution:**- eval
- apply