UNB/ CS/ David Bremner/ teaching/ cs3613/ tests/ CS3613 Final Exam

# Overview

The final exam, worth 50% of your mark, has been scheduled by the registrar at 09:00AM on April 24.

The exam is cumulative, covering all of the lectures, assignments, and all tutorials after the midterm.

The main "toy language" for the final will be trcfae.

# Sample Questions

## From the midterm

• Complete the function `find-ids` that scans an WAE expression for all identifiers in binding position. Your function should pass the given tests.
```(define-type WAE
[With (id : Symbol) (bound-expr : WAE) (body : WAE)]
[Add (left : WAE) (right : WAE)]
[Id (id : Symbol)]
[Num (n : Number)])

(define (find-ids expr)
(type-case WAE expr
[(With id exp1 exp2) ....]
[else ....]))

(test (find-ids (Num 3)) '())
(test (find-ids (Id 'x)) '())
(test (find-ids (With 'x (Num 3) (Id 'x))) '(x))
(With 'x (Num 3) (Id 'x))
(With 'y (Num 3) (Id 'y)))) '(x y))
(With 'x (Num 3) (Id 'x))
(With 'x (Num 3) (Id 'y)))) '(x x))
(test (find-ids (With 'y (With 'x (Num 3) (Id 'x))
(With 'x (Num 3) (Id 'y)))) '(y x x))
```

• Fill in a valid type for the function `alpha`
```#lang plait
(define (alpha f g)
(lambda (x)
(g (f x))))
(has-type  alpha : ....)
(test ( (alpha add1 to-string) 42) "43")
```

• Give formal substitution rules (pseudocode) for the `With*` construct from Homework 4.
```{with* {{x1 v1} ... {x_k e_k}} body}[E/y] = ....
```

• Convert the following example to de Bruijn index form. Explain your answer.
```    {with {x 1}
{with {y x}
{with {x x}
{+ x y}}}}
=>
{with ....
{with ....
{with ....
{+ ....}}}}
```

• Consider the following `FLANG` expression
```{with {n 1}
{with {f {fun {x} {+ x n}}}
{with {n 3}
{call f 7}}}}
```

Complete the evaluation for the two specified scope (evaluation) rules

```;; dynamic scope
eval({call f 7}, [n=3, f=...., n=1]) =
eval({+ x n}, [....]) = ....

;; static/lexical scope
eval({call f 7}, [n=3, f=...., n=1]) =
eval({+ x n}, [....]) = ....
```

## Types

Give the type of function `yo`

```#lang plait
(define (yo dawg herd)
(lambda (u)
(herd (u dawg))))
```

## Scope

In following some WAE/FLANG code is given in a comment, along with the equivalent racket code.

• What does this evaluate to?

• What does it evaluate to if you replace `let` with `let*` (i.e. `with` with `with*`)?

```#lang plait
#|
{with {{x 1}}
{with {{x 2} {y x}}
{+ x y}}}
|#
(let ((x 1))
(let ((x 2) (y x))
(+ x y)))
```

## Tail Recursion

### Summing a list

Complete the following tail recursive function to sum a list of numbers.

```(define (sum list acc)
....)

(test (sum (list 4 5 6) 0) 15)
```

### Finding odds and evens

Complete the function helper to provide a tail recursive function to count the odd and even entries in a list of numbers.

```(define  (helper lst odds evens) ....)

(define (odds-evens lst)
(helper lst 0 0))

(test (odds-evens (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
```

### Multiplication

Write the tail recursive function `mul-helper` to implement multiplication with addition (and subtraction). You only need to handle non-negative integers.

```(define (mul a b)
(mul-helper a b 0))
(test (mul 6 7) 42)
(test (mul 3 4) 12)
(test (mul 3 0) 0)
```

## Substitution function

Complete the following substitution function (not a full evaluator) for a simple language having only `Zero`, `One`, and `With` in its abstract syntax.

```#lang plait
(define-type WE
[Zero]
[One]
[With (id : Symbol) (bound-expr : WE) (body : WE)]
[Id (id : Symbol)])

(define (subst expr from to)
(type-case WE expr
[(Zero) (Zero)]
[(One) (One)]
[(Id name) (if (eq? name from) to expr)]
[(With bound-id named-expr bound-body) ....]))

(test (subst (With 'x (Zero) (Id 'x)) 'x (One))
(With 'x (Zero) (Id 'x)))

(test (subst (With 'x (Zero) (Id 'y)) 'y (One))
(With 'x (Zero) (One)))
```

### Delay

The following code has a bug in the definition of `fun`.

```#lang plait #:untyped

(define (make-fun self)
(let ([fun (self self)])
(lambda (arg)
(if arg
arg
(fun (not arg))))))
(display "after define make-fun\n")

(define fun (make-fun make-fun))

(display "after define fun\n")

(display (fun #f))
```

Use `lambda` to delay the call to `(self self)` so that the code runs and produces the following output.

```after define make-fun
after define fun
#t
```

### Passing functions to themselves

#### Factorial

Complete the definition of this recursive factorial function so that the give test passes.

```#lang plait #:untyped
(let ([fac
(lambda (m)
(let ([facY
(lambda (facX n)
(if (zero? n)
1
(* n (....))))])
(facY facY m)))])
(test (fac 7) 5040))
```

#### List length

Complete the given list length function so that the given test passes.

```(test
(let
((len
(lambda (self list)
(if (empty? list)
0
(....)))))
(len len  '(a b c d e))) 5)
```

### Evaluating expressions

Complete the definition of worker using `lambda` so that the given test passes. Your answer should not use `define`.

```#lang plait #:untyped
(define-type Expr
[num (n : Number)]
(r : Expr)])
(let ([interp
(lambda (ex)
(let ([worker ....])
(worker worker ex)))])
```

## Evaluators

### Evaluating `Call`

Complete the following case of an evaluator using

1. The `subst` function (i.e. a substitution based eval)
2. An environment based evaluator (with lexical scope).
```[(Call fun-expr arg-expr)
(let ([fval (eval fun-expr)])
....)]
```

### Optional Dynamic Scope

Modify your evaluator for `Call` to provide an evaluator for `DCall` that does a call with dynamic scope.

```(define (eval expr env)
(type-case FLANG expr

[(DCall fun-expr arg-expr)
(let ([fval (eval fun-expr env)])
....)]))

(test
(run `{with {f {fun {x} {+ 3 y}}}
{with {y 7}
{dcall f 7}}})
10)
```

### Evaluating a new construct I: join

Suppose for some reason we want to add a `join` primitive to our language that does function composition, e.g:

```(test
(run
`{call
{join
{fun {x} {+ x x}}
{fun {y} {- y 1}}}
3})
5)
```

Complete the `eval` case for `Join` (suppose that the FLANG type and the parser have already been extended).

```    [(Join fun-1 fun-2) ....]
```

### Evaluating a new construct II: switch

Complete the definition for an evaluator for a `switch` expression. This evaluates an expression (called `switch-on` here) and uses it to index into a list of other expressions (e.g. using `list-ref`)

```(define-type FLANG
; ...
[Switch (switch-on : FLANG) (expr-list : (Listof FLANG))])

(define (eval expr env)
(type-case FLANG expr
; ...
[(Switch switch-on expr-list) ....])

(test (eval (Switch (Num 1) (list (Num 3) (Num 4) (Num 5)))
(EmptyEnv))
(NumV 4))
```

### Substitution and recursion

Evaluate the following code as far as possible via substitution. You should expect an error as your final result. See below for semantics of `if0`.

```{with {foo {fun {n} {if0 n 1 {call foo {- n 1}}}}}
{call foo 1}}
```

### Tracing eval

Consider the following initial part of a trace of of trcfae.rkt. Fill the resulting closure values, paying particular attention to the environments. The constructor `aRecSub` is introduced by `Rec` and creates a mutable binding.

```(define prog
(Rec 'fub (ArrowTE (NumTE) (NumTE))
(Fun 'x (NumTE)
(If0 (Id 'x)
(Num 1)
(Call (Id 'fub) (Sub (Id 'x) (Num 1)))))
(Call (Id 'fub) (Num 1))))

(trace eval)
(eval prog (EmptyEnv))

>(eval
(Rec
'fub
(ArrowTE (NumTE) (NumTE))
(Fun ....)
(Call (Id 'fub) (Num 1)))
(mtSub))
> (eval
(Fun ....)
(RecBind 'fub (box (NumV 42)) (mtSub)))
< (ClosureV ....)
(RecBind 'fub (box (NumV 42)) (mtSub)))
>(eval
(Call (Id 'fub) (Num 1))
#0=(RecBind
'fub
(box
(ClosureV _____________________________))
(mtSub)))
> (eval
(Id 'fub)
#0=(RecBind
'fub
(box
(ClosureV ____________________________))
(mtSub)))
< #0=(ClosureV ________________________)
```

### Eval and environments

Complete the environments in the following evaluation. Use lexical/static scope. Assume environments are searched from left to right, and `[]` denotes the empty environment.

```eval({with {f {with {x 3}
{fun {y} {+ x y}}}}
{with {x 5} {call f 4}}}, [])
eval({with {x 3} {fun {y} {+ x y}}}},______________)
eval({fun {y} {+ x y}},______________________________)
eval({with {x 5} {call f 4}}, ___________________________
____________________________________________________)
eval({call f 4},___________________________
__________________________)
eval({+ x y},______________________________________________)
```

### With and recursion

Explain why the following fails to evaluate in an WAE interpreter with `if0`.

```{with {flop {fun {n}
{if0 n 1
{call flop {- 1 n}}}}}
{call flop 1}}
```

The following does evaluate correctly (to 1).

```(run
`{rec {flop {fun {n}
{if0 n 1
{call flop {- 1 n}}}}}
{call flop 1}})
```

The first recursive call to `eval` looks like

```(eval
(Call (Id 'flop) (Num 1))
#0=(Extend .... ))
```

Draw a diagram of the environment passed in as the second argument, keeping in mind that this intepreter using mutation and circular environments.

## Fun with closures

### Counters and state

In the game `Nim` the two players take turns removing 1 to 3 sticks from a pile. The person to remove the last stick loses. Complete the definition of `nim` so that it preserves state between calls.

```#lang plait

(define nim
(let ((sticks 5))
(lambda (n)
(begin ....))))

(test (nim 2)  "OK")    ; player 1 takes 2
(test (nim 2)  "OK")    ; player 2 takes 2
(test (nim 1)  "Lose")  ; player 1 loses
```

### Class definitions

Fill in the definitions for `circle` and `triangle` so that the give tests pass. Note that you have to override the "method" `round?` in one case.

```#lang plait
(define pi 3.141592653589793)
[num (n : Number)]
[bool (b : Boolean)])

(define (shape% method)
(case method
[(round?) (bool #f)]
[else (error method "unknown method")]))

....)

(define (square side-length)
....)

(define a-square (square 1))
(define a-circle (circle 1))
(test (a-square 'area) (num 1))
(test (a-circle 'area) (num pi))
(test (a-square 'round?) (bool #f))
(test (a-circle 'round?) (bool #t))
```

### Implementing lookup

Fill in the definitions of `empty-env` and `extend` to provide a implimentation of environments (similar to e.g. what we used to look up bindings for identifiers).

```#lang plait

(define-type-alias Env  (Symbol -> Number))

(define (empty-env) : Env ....)

(define (extend key val the-env) : Env .... )

(module+ test
(test/exn ((empty-env) 'bob)  "empty env!")

(define test-env
(extend 'mary 1
(extend 'bob 2
(empty-env))))

(test (test-env 'bob)  2)
(test (test-env 'mary) 1)
(test/exn (test-env 'happiness) "empty env!"))
```

## Union types

Consider the following definitions for an `FLANG` interpreter that impliments FLANG values as racket procedures and numbers. Complete the `eval` function for `Fun` and `Call`. This only works in ```#lang plait #:unchecked```

```(require (typed-in racket/base
[number? : ('a -> Boolean)]
[procedure? : ('a -> Boolean)]))

(define-type FLANG
[....]
[Fun  (param : Symbol) (body : FLANG)]
[Call (fun : FLANG) (val : FLANG)])

(define (VAL? v) (or (number? v) (procedure? v)))
; VAL is a lie
(define-type ENV
[EmptyEnv]
[Extend (id : Symbol) (binding : VAL) (rest : ENV)])

(define (evalF e)
(let ([f (eval e env)])
(if (procedure? f)
f
(error 'eval "got a non-function: ~s" f))))]
(define (eval expr env)
(type-case FLANG expr
[....]
[(Fun bound-id bound-body)
(lambda (arg-val)
(....))]
[(Call fun-expr arg-expr)
....)))
```

### Typing `if`

Fill in a valid union type for the function `fun`.

```#lang typed/racket

(define (fun arg) : (....)
(if arg
(lambda (x) 'foo)
"bar"))
```

## Typechecking

### Typechecking the `join` construct

• Given the `join` construct discussed above, give an appropriate typing rule

• Typecheck the following expression using your rule and any others needed

```    {join
{fun {x : num} {+ x x}}
{fun {y : num} {- y 1}}}
```
• Fill in the typechecking case for `join` (assume a suitable modified version of tfae.rkt)
```    [(Join fun1 fun2)
(let* ([type1 (typecheck fun1 env)]
[type2 (typecheck fun2 env)])
(type-case Type type1
[(ArrowT a b)
(type-case Type type2
[(ArrowT c d) ....]
[else (type-error fun2 "function")])]
[else (type-error fun1 "function")]))]
```

Here are some tests

```  (define join-ex1
(Join (Fun 'x (NumTE) (Add (Id 'x) (Id 'x)))
(Fun 'y (NumTE) (Sub (Id 'y) (Num 1)))))
(test (eval (Call join-ex1 (Num 3)) (mtSub)) (NumV 5))

(test (typecheck join-ex1 (mtEnv)) (ArrowT (NumT) (NumT)))
(define join-ex2
(Join (Fun 'x (NumTE) (Add (Id 'x) (Id 'x)))
(Fun 'y (BoolTE) (Id 'y))))

(test/exn (typecheck join-ex2 (mtEnv)) "not bool"))
```

### Typechecking `If0`

```    [(If0 test-expr then-expr else-expr)
(if (equal? (NumV 0) (eval test-expr env))
(eval then-expr env)
(eval else-expr env))]
```
• Complete the type rule for `if0`
```_________________________________________________
Γ ⊢ { if0 e₁ e₂ e₃ } : __________________________
```
• Complete the racket code to type check `if0`
```(define (typecheck fae env)
(type-case FAE fae
[If0 (test-expr then-expr else-expr) ....]))
```

### Tracing a typechecker

Complete the type environments in the following trace of trcfae.rkt. `BindType` introduces a type binding (like `extend`, but for types).

```(define prog
(Rec 'fub (ArrowTE (NumTE) (NumTE))
(Fun 'x (NumTE)
(If0 (Id 'x)
(Num 1)
(Call (Id 'fub) (Sub (Id 'x) (Num 1)))))
(Call (Id 'fub) (Num 1))))

(trace typecheck)
(typecheck prog (mtEnv))

>(typecheck
(Rec
'fub
(ArrowTE (NumTE) (NumTE))
(Fun ....)
(Call (Id 'fub) (Num 1)))
(mtEnv))
> (typecheck
(Call (Id 'fub) (Num 1))
(BindType 'fub ______________________________))
> >(typecheck (Id 'fub) (BindType 'fub (ArrowT (NumT) (NumT)) (mtEnv)))
< <(ArrowT (NumT) (NumT))
> >(typecheck (Num 1) (BindType 'fub _____________________ (mtEnv)))
< <(NumT)
< (NumT)
> (typecheck
(Fun ....)
(BindType 'fub ______________________ (mtEnv)))
> >(typecheck
(If0 (Id 'x) (Num 1) (Call (Id 'fub) (Sub (Id 'x) (Num 1))))
(BindType 'x ______ (BindType 'fub _____________________ (mtEnv))))
> > (typecheck
(Id 'x)
(BindType 'x ______ (BindType 'fub _____________________ (mtEnv))))
< < (NumT)
```

## Memory Management

### Heap Structure

Draw the heap structure simulated by the following definitions

```(define-type Object
[object (refs : (Listof Number))]
[integer (n : Number)])

(define-type-alias Heap (Vectorof Object))
(define example-heap
(vector
(integer 1)          ; 0
(object (list 8))    ; 1
(object (list 1))    ; 2
(object (list 7))    ; 3
(object (list 0 3))    ; 4
(integer 2)          ; 5
(object (list 0))    ; 6
(object (list 4 6)) ; 7
(object (list 2)))) ; 8
```

### Tagging objects

• Give a tag scheme that allows representing the heap above as a vector of numbers in the style of gc.rkt

• Show the corresponding vector of integers. What do you have to change to make this work?

## Continuation Passing Style

### CPS Fib I

Complete the following continuation passing style Fibonacci function (based on tutorial8)

```#lang plait
(define-type Fib-Cont
[mtK]
[fibSecondK (val : Number) (k : Fib-Cont)]
[sumK (val : Number) (k : Fib-Cont)])

(define (fib/k n k)
(cond
[(<= n 1) (continue k 1)]
[else (fib/k ....)]))

(define (continue [k : Fib-Cont] [val : Number])
(type-case Fib-Cont k
[(mtK) val]
[(fibSecondK n next-k) (fib/k ....)]
[(sumK first-val next-k) (continue next-k (+ first-val val))]))

(test (fib/k 5 (mtK)) 8)
```
• How deep does the call stack get during the execution of ```(fib/k 10 (mtK))```?

• How big does the `k` argument to `fib/k` get during the same execution.

### CPS Fib II

Complete the following continuation passing style Fibonacci function (more in the style of lecture17)

```(define (fib/l n l)
(cond
[(<= n 1) (l 1)]
[else (fib/l (- n 1)
(lambda (v) ....))]))

(define (fibSecondL v n next-l)
(fib/l (- n 2) (lambda (second-v) ....)))

(define (sumL first-val second-val next-l)
(next-l (+ first-val second-val)))

(fib/l 5 (lambda (n) n))
```
• How deep does the call stack get during the execution of `(fib/l 10 (lambda (n) n))`?

• Compared with naive recursive Fibonacci, where is the storage used?

• Can the function `sumL` be eliminated? How?

## Syntax rules

### nand

Add a syntax rule for `nand` (negated and) that supports short circuiting.

```(define-syntax nand
(syntax-rules ()
....)

(test (nand #f) #t)
(test (nand #t (begin (/ 1 0) #t)) #f)
(test (nand #f #t (eq? (/ 1 0) 0)) #f)
```