The midterm, worth 25% of your mark, will be held in class on Feb. 21, 2019.

The exam will cover lectures 1 to 9, and homework 1 to 5.

To help you get a feel for the style of questions to expect, I have included some questions from previous midterms and finals below. Note that this is a sample of questions that might be asked on a midterm or final. Not all of them would necessarily be on one midterm. You should feel free to check your answers with DrRacket, but keep in mind you won't have a computer on the exam.

# 1 Types

## 1.1 Basic Types

Fill in a valid `plait`

type for each of the following functions.

```
#lang plait
(define (f) 8)
(has-type f : ....)
(define h (lambda (x y)
(string-length (string-append x y))))
(has-type h : ....)
```

## 1.2 More complicated types

Give a valid type declaration for the following function

```
(define (glonk f g)
(lambda (x)
(let* ((h (g x))
(i (f h)))
i)))
(has-type glonk : ....)
```

# 2. Ragg Grammars

- Write a
`ragg`

format grammar that parses the following emoticons, assuming the lexer returns each character as a string token and ignores whitespace.

```
O_O o-o O_o o_O o_o O-O :-) :) :o) :] :c
```

- Explain the difference between the following two
`ragg`

grammars.

```
;; Grammar 1
ae: NUMBER
| NUMBER "+" ae
| NUMBER "-" ae
;; Grammar 2
ae: NUMBER
| ae "+" ae
| ae "-" ae
```

# 3. Substitution rules

- Complete the following substitution rules for
*eager*substitution

```
{call f arg}[y/x] =
{fun {id} body}[y/x] =
```

- repeat the exercise for
*lazy*substitution

# 4. Higher Order Functions

## 4.1 pair

Consider the tests

```
(test ((pair 1 3) +) 4)
(test ((pair 1 3) -) -2)
(test ((pair 2 3) *) 6)
```

Give a valid type for

`pair`

Write the function

`pair`

to pass these tests.

## 4.2 map

Fill in a definition for the function `map`

. A test is given to remind you how it works.

```
(define (map [fun : ('a -> 'b)] [lst : (Listof 'a) ]) : (Listof 'b)
....)
(test
(map add1 (list 1 2 3 4 5))
(list 2 3 4 5 6))
```

# 5. Environments

In the following questions, you can use any reasonable notation for the environments.

Consider the `plait`

code:

```
(run `{with {x 1} {with {x {+ x 2}} x}})
```

Evaluate the given FLANG code using the so-called "formal" evaluation rules.

The following shows the code running in the (dynamically scoped) FLANG interpreter from Lecture 7 with

`(trace eval)`

added. Fill in the missing environments.

```
>(eval (With 'x (Num 1) (With 'x (Add (Id 'x) (Num 2)) (Id 'x))) ________)
> (eval (Num 1) _______)
< (Num 1)
>(eval (With 'x (Add (Id 'x) (Num 2)) (Id 'x)) ________________))
> (eval (Add (Id 'x) (Num 2)) _________________)
> >(eval (Id 'x) ________________))
< <(Num 1)
> >(eval (Num 2) ________________________)
< <(Num 2)
< (Num 3)
>(eval (Id 'x) __________________________________))
<(Num 3)
3
```

Consider the FLANG code

```
{call {with {x 3} {fun {y} x}} 4}
```

The following is a trace of evaluating it with the statically scoped interpreter of Lecture 8. Fill in the missing environments.

```
>(eval (Call (With 'x (Num 3) (Fun 'y (Id 'x))) (Num 4)) (EmptyEnv))
> (eval (With 'x (Num 3) (Fun 'y (Id 'x))) __________)
> >(eval (Num 3) __________)
< <(NumV 3)
> (eval (Fun 'y (Id 'x)) _______________________________)
< (FunV 'y (Id 'x) _______________________________)
> (eval (Num 4) __________)
< (NumV 4)
>(eval (Id 'x) ____________________________________________________)
<(NumV 3)
3
```

# 6 Evaluators

## 6.1 With

Complete the following eager substition based
evaluator for a simplified version of WAE with only addition.
You may assume a function `subst`

is defined.

```
(define (eval expr)
(type-case WAE expr
[(Num n) n]
[(Add l r) ____________________)]
[(With bound-id named-expr bound-body)
________________________]
[(Id name) (error 'eval (string-append "free identifier: " (to-string name)))]))
```

repeat the exercise for a lazy substitution based evaluator

repeat the exercise for an eager environment based evaluator

## 6.2 Extending to multiple arguments

In the following, the Mul constructor is extended to
allow an arbitrary number of arguments, e.g. from parsing
`{* {+ 1 2} 3 4}`

. Fill in the definition of `mul-helper`

to support
this change. For full marks use either `foldl`

or tail
recursion. For simplicity the parser is omitted here, and the test
works directly on the abstract syntax tree.

```
(define-type AE
[Num (val : number)]
[Add (l : AE) (r : AE)]
[Sub (l : AE) (r : AE)]
[Mul (args : (listof AE))]
[Div (l : AE) (r : AE)])
(define (eval expr)
(type-case AE expr
[Num (n) n]
[Add (l r) (+ (eval l) (eval r))]
[Sub (l r) (- (eval l) (eval r))]
[Mul (args) (mul-helper args 1)]
[Div (l r) (/ (eval l) (eval r))]))
(define (mul-helper args acc) ....)
(test (eval (Mul (list (Add (Num 1) (Num 2)) (Num 3) (Num 4)))) 36)
```

# 7 mutation and recursion

Consider the following code for setting up a recursive environment

```
(define (extend-rec id expr rest-env)
(let* ([new-cell (box (NumV 42))]
[new-env (Extend id new-cell rest-env)]
(begin (set-box! new-cell (eval expr new-env)) new-env)))
```

- Draw a diagram of the resulting environment:

```
(extend-rec 'f (Fun 'x (Call (Id 'f) (Id 'x))) (EmptyEnv)))
```

In class we defined a `rec`

construct, evaluated by

```
[Rec (bound-id named-expr bound-body)
(eval bound-body (extend-rec bound-id named-expr env)]
```

- What is the result of
`(eval `{rec {x x} x},[])`

. How would you fix this?

# 8. Recursion, `define-type`

Fill in a definition for the function `sumtree`

so that it sums up all the numbers in a `numtree`

.

```
(define-type numtree
[leaf (n : Number)]
[tree (l : numtree) (r : numtree)])
(define (sumtree t) ....)
(test (sumtree (tree
(tree (leaf 3) (leaf 4))
(tree (leaf 5) (tree (leaf 6) (leaf 7)))))
25)
```