UNB/ CS/ David Bremner/ teaching/ cs3613/ tests/ CS3613 Midterm

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)
```
1. Give a valid type for `pair`

2. 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]
[(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)
```