## Background

This will be another review session for the midterm. To get maximum benefit, you should probably attempt the questions before the tutorial.

## Substitution

- Evaluate the following by substitution.

```
{with {x {+ 4 2}}
{with {x {+ x 1}}
{* x x }}}
```

Identify the problem with this definition of substitution semantics:

To substitute an identifier

`i`

in an expression`e`

with an expression`v`

, replace all instances of`i`

that are not themselves binding instances, and that are not in any nested scope, with the expression`v`

.Consider the following two different substititution rules for

`with*`

** Version 1 **

```
{with* {{x1 e1[E/y]} {x2 e2[E/y]} ... {x_k e_k}[E/y]}[E/y] newbody}
where
newbody = body if y in x1..xk
else
newbody = body[E/y]
```

** Version 2 **

```
{with* {} E2}[v/z] = E2[v/z]
{with* { {x1 E1} bindings } E3}[v/z] = {with {x1 E1}
{with* bindings E3}}[v/z]
```

Evaluate the following substitution under both versions.

`{with* {{y x} {x 2} {x x}} {+ x y}}[1/x]`

Explain the differing results in terms of scope.

## Lazy evaluation

- Evaluate the following using purely lazy substitution and purely eager substitution

```
{with {x 1}
{with {x {+ x 1}}
x}}
```

- Give an example of WAE code exhibiting
*name capture*

## de Bruijn Indices

- Convert the following WAE expression to deBruijn form.

```
{with {x 1}
{with {x {+ x 1}}
{with {y x} x}}}
```

- Convert the following FLANG expression to deBruijn form.

```
{with {f {fun {x} {+ x 1}}}
{with {y 2}
{call f y}}}
```

## Substitution Caches

- Write a lookup function with this type signature to look up a symbol in a substitution cache / environment.

```
(define-type BindingPair
[pair (name : symbol) (val : s-expression)])
(define-type-alias ENV (listof BindingPair))
(define (lookup [name : symbol] [env : ENV]) : s-expression
)
```

Here are some sample tests:

```
(define test-env
(list
(pair 'f '(lambda (x) (+ x 1)))
(pair 'x '1)))
(test/exn
(lookup 'y test-env) "free identifier")
(test
(lookup 'x test-env) '1)
(test
(lookup 'f test-env)
'(lambda (x) (+ x 1)))
```

- Explain why environments use a list or list-like structure, rather than something with a faster search time like a hash table.

## Dynamic and Lexical Scope

Explain why the following evaluation rule guarantees the corresponding interpreter will not have lexical scope.

eval ({fun { x } E} , sc ) = {fun { x } E}

Evaluate the following dynamically scoped racket code using environments.

```
#lang plai
(require plai/dynamic)
(let ([blah (lambda (func x) (func x))])
(let ((x 7))
(let ((f (lambda (y) (+ x y))))
(let ((x 6))
(blah f 5)))))
```

Evaluate the same code using substitution semantics (this will get a different answer, matching racket without the the

`(require plai/dynamic)`

. Note that this is worth doing in racket by copying and modifying the expression for each substitution.Modify the following evaluation rules so that they make sense for the limited dialect of racket used in the preceding example.

```
eval(N,env) = N
eval({+ E1 E2},env) = eval(E1,env) +
eval(E2,env)
; ...
eval(x,env) = lookup(x,env)
eval({with {x E1} E2},env) = eval(E2,extend(x,eval(E1,env),env))
eval({fun {x} E},env) = <{fun {x} E}, env>
eval({call E1 E2},env1) =
if eval(E1,env1) = <{fun {x} Ef}, env2> then
eval(Ef,extend(x,eval(E2,env1),env2))
else
error!
```

Evaluate the previous example using your new environment based evaluation rules.

Compare the behaviour of the following code under dynamic scope, substitution, and environment based evaluation. This question does not need a complete trace to answer.

```
{with {f {fun {y} {+ x y}}}
{with {x 7}
{call f 1}}}
```

## Functions as data structures

Fill in the definition of `tree-max`

so that it computes the maximum
number stored in a non-empty tree.

```
#lang plai
(define (make-tree left value right)
(lambda (key)
(case key
[(getLeft) left]
[(getValue) value]
[(getRight) right])))
(define empty-tree 'emptyTree)
(define (empty-tree? val) (eq? val 'emptyTree))
(define (make-leaf num)
(make-tree empty-tree num empty-tree))
(define (tree-max tree)
(let [(l _______________)
(r _______________)
(v _______________)]
(cond
[__________________________________________ v]
[_____________________________(max v (tree-max r))]
[_____________________________(max v (tree-max l))]
[else____________________________________________ ])
(define test-tree-1
(make-tree (make-leaf 1) 2 (make-leaf 3)))
(test (tree-max test-tree-1) 3)
```

## Curried Functions

One annoying feature of working with curried functions in racket is
the need to explicitely call them repeatedly once per argument. Write
a function `call`

that takes a curried function and a list of
arguments, and evaluates the appropriate number of calls.

```
#lang plai
(define plus
(lambda (x) (lambda (y) (+ x y))))
(test ((plus 1) 2) 3)
(define plus3
(lambda (x) (lambda (y) (lambda (z) (+ x (+ y z))))))
(test (((plus3 1) 2) 3) 6)
(define (call f l)
___________________________________________________
___________________________________________________
___________________________________________________)
(test (call plus '(1 2)) 3)
(test (call plus3 '(1 2 3)) 6)
```