UNB/ CS/ David Bremner/ teaching/ cs3613/ tutorials/ CS3613 Tutorial 8

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