**Questions file**: final-questions.rkt

# Overview

The final exam, worth 50% of your mark, will be held online, April 22 2020, 14:00-17:00. The exam is cumulative, covering all lectures, assignments, and tutorials after the midterm. Roughly speaking, the exam will weight topics according to how many lectures/tutorials covered them. There may be somewhat more emphasis on topics from after the midterm.

# Rules

Due to the COVID-19 emergency, this year's exam will be online.

- The exam will be open book, and you can use any reference material you like.
- In particular you are welcome to use DrRacket to work on your exam.
- You may not consult get help from any other person, whether a student in this class or not. I will be marking the exams carefully, and treating any cases of apparent plagiarism seriously. Both a student asking for help from another person and a student helping someone else in the course on the final exam will be reported to the UNB Senate Student Standings and Promotion Committee. For possible (bad) outcomes see the UNB plagiarism rules.

# Logistics

Exam papers will be emailed to your UNB email account just before the start of the exam. I will also make the exam questions available linked from this page.

Clarifications of exam questions will be available via email, or via the class riot.im channel. You are strongly encouraged to use the latter, as I don't promise to check my email constantly, and UNB/Microsoft sometimes locks me out of my email.

You must hand in your answers via the handin server before 17:01. You can hand in as many times as you want, as usual. In case of emergency, you can send your completed exam to me via email, or via direct message on riot.im

# Format

The exam will be single racket file with multiple modules, one per question. The following *only* illustrates the format, not the number or content of the questions.

```
#lang racket/base
(module question1 plait
;; MARKS: 25
;; QUESTION: Complete the definition for 'name' so that the given
;; test passes
(define (name) : String ....)
(test (name) (name))
)
(module question2 plait
#:untyped
;; MARKS: 25
;; QUESTION: Complete the following function
(define (favourite-colour day)
(case day
[(Monday) #f]
[else ....]))
(test (favourite-colour 'Tuesday) 'blue))
;; Uncomment the questions you want to run
#;(require 'question1)
#;(require 'question2)
```

# Sample Questions

See also the review questions for tutorial 5 (solutions for tutorial 5 are available on the handin server)

**Sample Questions are currently work in progress, and subject to change**

## Evaluation

### Evaluating cond

The new trcfae form `cond`

is
similar to the one in `plait`

, with a recursive abstract syntax
similar to `Env`

and `TypeEnv`

. Complete the helper function
`eval-cond`

to evaluate a `Cond`

`FAE`

variant.

```
(define-type FAE
[Cond (clauses : ClauseList)]
....)
(define-type ClauseList
[Else (expr : FAE)]
[Clause (test-expr : FAE) (expr : FAE) (tail : ClauseList)])
(define (eval a-fae env)
(type-case FAE a-fae
....
[(Cond clauses) (eval-cond clauses env)]))
(define (eval-cond clauses env)
(type-case ClauseList clauses
....)
```

Your code should pass the following test

```
(define the-env
(BindValue 'x (NumV 5)
(EmptyValueEnv)))
(test
(eval
(parse
`{cond
{{<= x 3} true}
{{<= 7 x} true}
{else false}})
the-env)
(BoolV #f))
(test
(eval
(Cond
(Clause
(Leq (Id 'x) (Num 3))
(Bool #t)
(Clause
(Leq (Num 7) (Id 'x))
(Bool #t)
(Else (Bool #f)))))
the-env)
(BoolV #f))
```

### Evaluating call-with

The new `trcfae`

form `{call-with {id v1} fex v2}`

is
like

```
{call {with {id v1} fex} v2}
```

except that the call is dynamically scoped with respect to `id`

(and
only `id`

). Complete the `eval`

clause to evaluate a `call-with`

form.

```
(define-type FAE
...
[CallWith (with-id : Symbol) (with-arg-exp : FAE)
(fun-exp : FAE) (fun-arg-exp : FAE)])
(define (eval a-fae env)
(type-case FAE a-fae
[(CallWith with-id with-arg-exp fun-exp fun-arg-exp)
(type-case FAE-Value (eval fun-exp env)
[(ClosureV fun-param body-exp def-env) ....]
[else (error 'eval "not function")])]
```

Your code should pass the following tests

```
(test (run `{call-with {y 7} {fun {x : num} {+ x y}} 3})
(NumV 10))
(test/exn (run `{call-with {x 7} {fun {x : num} {+ x y}} 3}) "free variable")
(test (run `{call-with {x 7} {fun {x : num} {+ x x}} 3})
(NumV 6)))
(test (parse `{call-with {y 7} {fun {x : num} {+ x y}} 3})
(CallWith 'y (Num 7)
(Fun 'x (NumTE) (Add (Id 'x) (Id 'y))) (Num 3))))
```

## Recursion

### With and recursion

Consider the following erroneous FLANG code.

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

- Explain how and why evaluation fails with a substition based evaluator.
- Explain how and why evaluation fails with an environment based evaluator.
- How would you define
`rec`

(the recursive version of`with`

) using substition?

### Recursion and boxes

Explain why the circular environment based approach to recursion needs
boxes. Could `set!`

be used in place of `set-box!`

? Why or why not.

## Y-combinator and related topics

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

### 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)]
[add (l : Expr)
(r : Expr)])
(let ([interp
(lambda (ex)
(let ([worker ....])
(worker worker ex)))])
(test (interp (add (add (num 1) (num 2)) (num 3))) 6))
```

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

### Scanning a list

Complete the tail-recursive function `rev-odds`

that
returns (in reverse order) the odd numbers in a list. Do not use
`define`

.

```
#lang plait #:untyped
(let ([rev-odds
(lambda (self lst acc)
...)])
;; Body of let
(test (rev-odds rev-odds '(1 2 3 4 5 6 7 8) '()) '(7 5 3 1)))
```

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

- Repeat the exercise with boxes, replacing the use of
`set!`

with`set-box!`

## Typechecking

### Typechecking the `join`

construct

Given the

`join`

construct discussed in [[tutorials/tutorial5], give an appropriate typing ruleTypecheck 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 Leq

Suppose we add a `<=`

operator to
trcfae, such that the following passes:

```
(test (run `{<= 2 3}) (BoolV #t))
```

#### Typechecking rule

Complete the type rule.

```
E₁: E₂:
_______________________________________________________
Γ ⊢ {<= E₁ E₂ } :
```

#### Typechecker implementation

Complete the typechecker for the `Leq`

abstract syntax
parsed from `<=`

). For full marks, use only functions built-in to
`plait`

and definitions from trcfae

```
(define (typecheck [fae : FAE] [env : TypeEnv]) : Type
(type-case FAE fae
[(Leq l r) ...])
```

## Continuation Passing Style

### CPS Fib I

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

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

```
(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) ....)))
(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?

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

## Byte code interpretation

You are given a skeleton which has *mostly*
implemented the error primitive from lecture16 in a byte code interpreter.
In order to simplify things, we return error *numbers* instead of error strings.
Update the functions `interp`

and/or `continue`

so that the following test passes

```
(define ret-loc (run `{+ 1 {error 7}}))
(test (ref ret-loc 0) tag:ErrorV)
(test (ref ret-loc 1) 7))
```

## Memory management

### Mark sweep with free list

Complete the following test for mark-sweep-free-list.rkt so the the given heap states are generated.

```
(with-heap (make-vector 10 'free)
(init-allocator)
....
(test (current-heap) #(3 flat garbage free-n #f 7 free free free free))
(define alive (....))
....
(test (read-root alive) 3)
(test (current-heap) #(1 free-2 5 flat alive free-n #f 5 free free))))
```

- Describe the free list at the end of the preceeding test; i.e. how many nodes, how big are they, etc...

### Choice of algorithm

- Describe two advantages of the two space collector relative to mark and sweep
- Describe an advantage of mark and sweep over the two space collector
- What are the most important design decisions when implementing a generational two space collector?