This feed contains pages with tag "cs3613".

**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?

Lecture 20 introduced racket dialects plai/gc2/collector and plai/gc2/mutator. We also looked at the API required to be provided by a collector. Somewhat suprisingly, that does not include actual garbage collection. In this tutorial we'll get a bit more familiar with the API by writing tests for the null collector discussed in Lecture 20.

# 1 Error cases

Start by writing tests to exercise each of the error calls in null-gc.rkt Use with-heap and test/exn.

## Hints

- It should only take 5 new tests (each wrapped in its own
`with-heap`

). - You'll likely want to use
`let`

to locations returned by allocation routines. - Don't forget to call
`init-allocator`

, or things will fail mysteriously.

## 2 Atomic / flat data

Add any tests needed for the flat data part of the API.

## Hints

- Here it might make sense to wrap multiple tests inside a single
`with-heap`

. - Two tests did it for me.

# 3 Cons / Pairs

Add tests to cover the `cons`

related code.

## Hints

- Testing the
`set-`

functions is a bit trickier; I used a begin block inside the test to call the`set-`

function then retrieve the result. - Don't forget you need to create roots when calling cons.
- You may also want to use
`gc:deref`

on the location returned by e.g.`gc:first`

.

# 4 Closures

Add tests to cover the remaining closure related code.

## Hints

keep in mind that the code pointer is opaque, so you can pass whatever you want, a symbol, the number 42, your favourite colour.

There are a lot of similarities between the management of closures and the already tested management of

`cons`

pairs. In particular you need to use roots for both.two tests in one

`with-heap`

did it for me.

# 5 Reflection, test design

Unlike the tests we looked at in Lecture 20,
none of my tests for this tutorial used `current-heap`

to look at the
exact state of the heap, but rather just API calls to look at at
single elements of the heap. Can you think of arguments in favour of
both approaches?

Solution to Tutorial 8 is available on the handin server.

Tutorial 9 is available. I'll post solutions on the handin server sometime after Thursday.

Choice of CR/NCR was finalized on April 9, per UNB guidance.

Slides for Lecture 21 are available. Video is on teams

Slides for Lecture 22 are available. Video is on teams

Solutions for Homework 9 and and Tutorial 9 are available on the handin server.

Review questions for the final exam are available at T2. at the usual URL at 13:00 on Friday April 17th.

# Background

Racket and Typed/Racket provide a set datatype with a fairly convenient syntax.

```
#lang typed/racket
(define S (list->set '(1 2 3)))
(define S* (set 1 2 3))
(equal? S S*)
(set-member? S 1)
(define T (set-add S 4))
(set-union S T)
```

Unfortunately these forms are not provided in `plait`

. Since sets are
a useful data structure, in particular for thinking about garbage
collection, we're going to impliment something similar to the
`typed/racket`

set API using `plait`

hash tables.

## Types.

In general I have over-annotated the code in this tutorial, to help you think about polymorphic typechecking (which we discussed in ), and to make it clearer what the functions should do. The original code works fine without any annotations.

# Questions

## Making sets

Complete the definition of `list->set`

. The type annotation and second
test should give you the idea of how to impliment it using e.g. `map`

.
If you examine the type of `list->set`

, you will see that our
type-alias is not **opaque**; the underlying implimentation as a hash
table is visible.

```
#lang plait
(define-type-alias (Setof 'a) (Hashof 'a Boolean))
(define (list->set [ items : (Listof 'a) ]) : (Setof 'a)
....)
(module+ test
(test (list->set empty) (hash empty))
(define S123 (list->set '(1 2 3)))
(test S123 (hash (list (pair 1 #t) (pair 2 #t) (pair 3 #t)))))
```

## Providing some prettier syntax

One of my main motivations in reimplimenting these primitives was not
having to change all of the places my code writes `(set ....)`

to some
clunkier syntax (like the `list->set`

we just wrote. Write an
appropriate syntax rule, using `...`

to collect arguments to provide a
`set`

macro. This is a very common development pattern in languages
with macros: debug the code first as a function, then make a minimal
macro wrapper for that function that makes it nicer to use.

```
(define-syntax-rule (set ....)
....)
(module+ test
(test (set) (list->set empty))
(test (set 1 2 3) S123))
```

## Define `set-member?`

One of the defining characteristics of set data structures (compared
to e.g. lists or arrays) is fast membership testing. Define a
`set-member?`

function. You will most likely want to use `hash-ref`

,
but note the return type in `plait`

uses `Optionof`

.

```
(define (set-member? [set : (Setof 'a)] [thing : 'a]) : Boolean
....)
(module+ test
(test (set-member? S123 1) #t)
(test (set-member? S123 10) #f))
```

# Define `set-add`

Our sets are immutable (hence `hash`

rather than `make-hash`

above),
but we still want to be able to extend them by a single element. We
want `set-add`

to be like `cons`

. The input is not modified but a new
set with one more element is returned.

```
(define (set-add [set : (Setof 'a)] [thing : 'a]) : (Setof 'a)
....)
(module+ test
(test (set-add (set 1 2 3) 0) (set 0 1 2 3)))
```

## Set union

Finally, define a way to take the union of two sets. This can either
use `set-add`

, or (probably easier), underlying hash-table
operations. Note in particular the function `hash-keys`

.

```
(define (set-union [the-set : (Setof 'a)] [other-set : (Setof 'a)])
....)
(module+ test
(test (set-union (set 0 1 2 3) (set -1 2 7)) (set -1 0 1 2 3 7)))
```

# Introduction

Many garbage collection algorithms start with a *marking* phase where
they traverse the heap and find which objects which are reachable from
some set of *roots*. Examples of roots include global variables and
local variables in the current scope. In this tutorial you will
write a simple simulation of marking a heap.

# Data Structures

In addition to lists, this tutorial uses

*vectors*, and*sets*.If you're feeling keen, you can follow the set tutorial to develop the set functionality. Otherwise you can use my solution

One of the points of this tutorial is to practice with immutable data structures. A natural technique is to pass an extra parameter and provide an updated version of a value to recursive calls (i.e. like we do for tail recursion).

# The Heap

Use the following type declarations to define an abstract representation of a heap. Each heap location either has a list of indices (locations of referenced objects) or is a primitive value. This is similar to the model of lecture18 and homework 9, but a slightly higher level. Also, since we only care about simulating GC here, we drop any parts of heap containing actual data (hence primitive here might correspond to an integer value or an empy list in the model of homework 9.

```
(define-type Object
[object (refs : (Listof Number))]
[primitive])
(define-type-alias Heap (Vectorof Object))
(define-type-alias LocSet (Setof Number))
```

# Finding objects reachable from a single root.

Complete the definition of `search-one-root-unknown`

to use Depth
First Search to
find the set of (locations of) objects reachable from the given root.
In terms of the *tricolour abstraction* discussed in Lecture
18, the `known`

parameter contains those
locations marked gray or black, while the returned `LocSet`

is the black nodes.

```
(define (search-one-root [root : Number] [heap : Heap]) : LocSet
(search-one-root-unknown root heap (set)))
(define (search-one-root-unknown [root : Number] [heap : Heap] [known : LocSet]) : LocSet
....)
(define heap1
(vector
(object (list 1 2))
(primitive)
(object (list 2))))
(define heap2
(vector
(object (list 0 1))
(object (list 2))
(object (list 0))))
(test (search-one-root 0 heap1) (set 0 1 2))
(test (search-one-root 1 heap1) (set 1))
(test (search-one-root 0 heap2) (set 0 1 2))
(test (search-one-root 1 heap2) (set 0 1 2))
```

# Working with a set of roots

Write a function `find-live`

is to find the locations of all objects
reachable from a given set of roots. The function `find-live`

has the
following type signature

```
(has-type find-live : ((Listof Number) Heap -> LocSet))
```

Use the same idea of an auxilary function with an accumulator as for `search-one-root`

, and call `search-one-root`

to do the traversal for a given root. Don't worry about neccesarily being tail-recursive here.

```
(define (find-live [roots : (Listof Number)] [heap : Heap]) : LocSet
(find-live-unknown roots heap (set)))
(define (find-live-unknown [roots : (Listof Number)] [heap : Heap] [known : LocSet]) : LocSet
....)
(test (find-live '(1) heap1) (set 1))
(test (find-live '(0) heap1) (set 0 1 2))
(test (find-live '(1 2) heap2) (set 0 1 2))
```

Solutions to Tutorial 7 are available on the handin server.

Tutorial 8 is available. I'll post solutions on the handin server sometime after Friday.

Slides for Lecture 19 are available. Lecture video is on MS Teams

Slides for Lecture 20 are available. Video is posted on MS Teams

Homeworks 7 and 8 are graded and available on the handin server.

# Introduction

In this tutorial we will work through how to add generators to a language by using language level continuations. This continues (har har) the second half of Lecture 16. The generators are based on those discussed in Chapter 14 of PLAI. The approach here (as in Lecture 16) relies on parameters (dynamic scope), rather than on macros (as the version in PLAI).

# Step 0: What's a generator?

Some of you may be familiar with generators e.g. from Python. The racket standard library includes a generator module. The following is an example from the manual, translated to use more familiar (to us) idioms.

```
#lang racket
(require racket/generator)
(define g
(generator ()
(define (loop lst)
(if (empty? lst) 0
(begin
(yield (first lst))
(loop (rest lst)))))
(loop '(a b c))))
(module+ test
(require rackunit)
(check-equal? (g) 'a)
(check-equal? (g) 'b)
(check-equal? (g) 'c)
(check-equal? (g) 0)
(check-equal? (g) 0)
)
```

Fill in the definition to make a `counter`

generator that counts up from the initial value.

```
(define counter
(generator (initial)
;; definition goes here
))
(module+ test
(check-equal? (counter 10) 10)
(check-equal? (counter 10) 11)
(check-equal? (counter 10) 12)
(check-equal? (counter 10) 13)
)
```

Roughly speaking, generators require two control flow features: early return, and resuming execution. We'll work through how to implement each of these features using continuations.

# Early return

Recall that racket (and in particular `#lang plait`

provides `let/cc`

.
Early return is a simplified version of the exception example from
Lecture 16. Complete the definition of the
following by rebinding `return-k`

appropriately.

```
#lang plait
(define return-k (make-parameter (lambda (v) (error 'return "outside with-return"))))
(define (return v) ((parameter-ref return-k) v))
(define (with-return thunk)
(let/cc calling-context
(parameterize
(.... )
(thunk))))
(with-return
(lambda ()
(begin
(return 42)
(/ 1 0))))
```

We can tidy up the syntax by defining a syntax rule. The missing part
here is the same as above. Note that `...`

is very different from
`....`

in racket.

```
#lang plait
(define return-k (make-parameter (lambda (v) (error 'return "outside with-return"))))
(define (return v) ((parameter-ref return-k) v))
(define-syntax-rule (with-return exprs ...)
(let/cc calling-context
(parameterize
(....)
(begin exprs ...))))
(with-return
(return 42)
(/ 1 0))
```

# Resuming execution

Early return is familiar to us from imperative programming languages like Java, C and JavaScript. Resuming execution is a bit more exotic. Suppose we are given the following code:

```
(define printer
(with-checkpoint
(lambda ()
(begin
(display "first\n")
(checkpoint!)
(display "second\n")))))
```

We want to define a form `with-checkpoint`

and a function
`checkpoint!`

so that

```
(printer)
(printer)
(printer)
```

prints

```
first
second
second
second
```

i.e. that execution restarts at the last `(checkpoint!)`

reached.

As a warmup, let's figure out how to have functions with state. We
could combine boxes with closures for this, but since we don't need
the pass-by-reference features of boxes, we will use the
usually-forbidden `set!`

instead. The goal is to define a function
`last-call`

that remembers the last value of it's parameter, and
returns that. The "tricky" bit is the use of `let`

to define a
variable to preserve the state in. This variable is visible only
inside the `define`

(note also the use of the plait `Option`

type).

```
#lang plait
(define last-call
(let ([state (none)])
(lambda (n)
(....))))
(test (last-call 1) (none))
(test (last-call 2) (some 1))
(test (last-call 3) (some 2))
(test (last-call 3) (some 3))
```

Now that we know how to store store things for future invocations of a
function, we can use a combination of `let`

and `set!`

to store a
continuation.

In the following we need to use `let/cc`

*inside* `checkpoint`

to capture the continuation where it is called
(we might loosely call this the *call site*)

```
#lang plait
(define checkpoint-param (make-parameter (lambda () (error 'checkpoint! "outside with-checkpoint"))))
(define (checkpoint!) ((parameter-ref checkpoint-param)))
(define with-checkpoint
(let* ([last-checkpoint (none)])
(lambda (thunk)
(lambda ()
(parameterize ([checkpoint-param ....])
(type-case (Optionof (Void -> 'a)) last-checkpoint
[(none) (thunk)]
[(some k) (k (void))]))))))
```

# Generators

To make a generator we need to combine the two ideas from above. We
have two continuations: `dyn-k`

is the call site for the generator,
and `gen-k`

is the "checkpoint" where we will resume the the execution
of the generator the next time we call it (i.e. call site of `yield`

).

```
#lang plait
(define yield-param (make-parameter (lambda (v) (error 'yield! "outside generator"))))
(define (yield v) ((parameter-ref yield-param) v))
(define generator
(lambda (fun)
(let* ([last-checkpoint (none)])
(lambda (v)
(let/cc dyn-k
(parameterize ([yield-param
(lambda (v)
(let/cc gen-k
....))])
(type-case (Optionof ('a -> 'b)) last-checkpoint
[(none) (fun v)]
[(some k) (k v)])))))))
```

Here some (more ) sample generators taken from PLAI.

```
(define g1
(generator
(lambda (v)
(letrec ([loop (lambda (n)
(begin
(yield n)
(loop (+ n 1))))])
(loop v)))))
(g1 10)
(g1 10)
(g1 10)
(define g2
(generator
(lambda (v)
(letrec ([loop (lambda (n)
(loop (+ (yield n) n)))])
(loop v)))))
(g2 10)
(g2 10)
(g2 10)
```

The identifier names are different, but my generator solution is based
on the following macro based solution from Chapter 14 of
PLAI.
If you're interested in macros, notice the tricky way the macro
parameter `yield`

is being used here.

```
#lang plait
(define-syntax (generator e)
(syntax-case e ()
[(generator (yield) (v) b)
#'(let ([where-to-go (lambda (v) (error 'where-to-go "nothing"))])
(letrec ([resumer (lambda (v)
(begin b
(error 'generator "fell through")))]
[yield (lambda (v)
(let/cc gen-k
(begin
(set! resumer gen-k)
(where-to-go v))))])
(lambda (v)
(let/cc dyn-k
(begin
(set! where-to-go dyn-k)
(resumer v))))))]))
(define g1
(generator (yield) (v)
(letrec ([loop (lambda (n)
(begin
(yield n)
(loop (+ n 1))))])
(loop v))))
(define g2
(generator (yield) (v)
(letrec ([loop (lambda (n)
(loop (+ (yield n) n)))])
(loop v))))
```

Finally, we can define a syntax rule to make it slightly nicer to define generators in our solution. In my humble opinion this is a more programmer friendly syntax than the text's.

```
#lang plait
(define yield-param (make-parameter (lambda (v) (error 'yield! "outside generator"))))
(define (yield v) ((parameter-ref yield-param) v))
(define-syntax-rule (generator (v) exprs ...)
(let ([last-checkpoint (none)]
[fun (lambda (v) exprs ...)])
(lambda (v)
(let/cc dyn-k
(parameterize ([yield-param
(lambda (v)
(let/cc gen-k ....))])
(type-case (Optionof ('a -> 'b)) last-checkpoint
[(none) (fun v)]
[(some k) (k v)]))))))
(define g1
(generator (v)
(letrec ([loop (lambda (n)
(begin
(yield n)
(loop (+ n 1))))])
(loop v))))
(g1 10)
(g1 10)
(g1 10)
(define g2
(generator (v)
(letrec ([loop (lambda (n)
(loop (+ (yield n) n)))])
(loop v))))
(g2 10)
(g2 10)
(g2 10)
```

Homework 8 is due this Friday at 16:00.

Tutorial 7 is available. I'll post solutions on the handin server sometime after Friday.

Everyone in both undergrad and grad sections should now be in one "team" on Microsoft Teams. So far I only plan to share videos there. Please let me know if you cannot access this via myUNB.

Slides for Lecture 17 are available. We met at https://meet.jit.si/cs3613 . Video is available on Teams.

Slides for Lecture 18 are available. We will meet at 11:30 ADT in https://meet.jit.si/cs3613 . Video will be recorded.

Homework 9 is posted. This will be the final assignment of this term. We lost a week, so I dropped one assignment. It is a bit longer than some of the others, so you have almost two weeks to do it.

This page will collect the evolving plan for how we are going to finish this course.

This website, and email will remain the main source for course information, both meta information like this page, and actual course content like slides and assignments.

Because of lack of responsiveness of the ClassMail web tool, I've copied the emails for the class to a private alias. If your UNB email is not working for some reason, please send me an alternate address.

I have created a course channel/room

`unb-cs3613`

on https://riot.im . You can join via a browser or various applications (Android / iOS / macOS / Windows / Mac / Linux). My riot username is`bremner`

. The room is currently invite only, if you tell me your username I can invite you.Office hours will be replaced by asynchronous monitoring of the

`unb-cs3613`

channel. Just ask your questions, and I (or someone else) will answer when we can.Tutorials will be transition to self-directed exercises. You don't have to do them at 8:30 Monday morning, but try to do them the week they are posted. Material on the tutorials after the midterm will be considered testable for the final exam.

Assignments will be handed in via the handin server as usual. It's not clear at this point if there will be 1 or 2 more assignments.

My current plan is to have video lectures (probably a bit shorter) in https://jitsi.tethera.net/cs3613 in our regular timeslot, starting on March 24. I will make the recording of those lectures available to the class on UNB's MS teams instance.

There will be an open book final exam. It will be completed in a normal 3 hour timeslot, with answers handed in via the handin server. You can expect similar "fill in the blanks" programming exercises to some of the the midterm questions, as well as more "theoretical" questions.

In recognition of the extra strain we're all under, the project component of the course for grad students is dropped, with the marks from other components redistributed evenly.

# Background

In this tutorial you will get more familiar with typechecking and (in particular) the unification based interpreter discussed in Lecture 14.

# Step 0

Download the unification based TIFAE interpreter. You will modify this interpeter in the remaining steps of this tutorial.

# Step 1

Add a `With`

variant to the `FAE`

type, and add dummy clauses (using
`....`

) to the `type-case`

statements in `eval`

and `typecheck`

. Extend the parser for with using e.g.

```
[(s-exp-match? `(with (SYMBOL ANY) ANY) sx)
(let* ([def (sx-ref sx 1)]
[id (s-exp->symbol (sx-ref def 0))]
[val (parse (sx-ref def 1))]
[expr (px 2)])
(With id val expr))]
```

# Step 2

If needed, consult your notes for some of the previous interpreters
(e.g. the one discussed in Lecture 8
to implement the `eval`

functionality for `With`

.

Add the following tests to your interpeter.

```
(test (run `{with {add3 {fun {x : ?} {+ x 3}}}
{with {add1 {fun {x : ?} {+ x 1}}}
{with {x 3}
{add1 {add3 x}}}}})
(NumV 7))
(test (run `{with {identity {fun {x : ?} x}}
{with {foo {fun {x : ?} {+ x 1}}}
{{identity foo}
123}}})
(NumV 124))
(test (run `{with {x 3}
{with {f {fun {y : ?} {+ x y}}}
{with {x 5}
{f 4}}}})
(NumV 7))
```

# Step 3

Consider the following typechecking rule for `with`

.

```
Γ ⊢ e₁ : τ₁, Γ[x←τ₁] ⊢ e₂ : τ₂
——————————————————————————————–
Γ ⊢ {with {x e₁} e₂} : τ₂
```

Impliment this rule in your `typecheck`

function. It is possible to do
this without explicitly calling `unify!`

. The skeleton of my solution is as follows:

```
[(With id bound-exp body)
(let* ([id-type ....]
[new-env ....])
(typecheck ....))]
```

Your completed interpreter should pass the following tests

```
(test
(resolve
(check
`{with {add3 {fun {x : ?} {+ x 3}}}
{with {add1 {fun {x : ?} {+ x 1}}}
{with {x 3}
{add1 {add3 x}}}}}))
(NumT))
(test
(resolve
(check
`{with {identity {fun {x : ?} x}}
{with {foo {fun {x : ?} {+ x 1}}}
{{identity foo}
123}}}))
(NumT))
(test
(resolve
(check `{with {x 3}
{with {f {fun {y : ?} {+ x y}}}
{with {x 5}
{f 4}}}}))
(NumT))
```

Notice the use of

`resolve`

in the tests. What happens if that wrapping is removed?Why do we not need to specify a type annotation for

`x`

in the`with`

form? Compare with`fun`

in the same language.

# Step 4 (Optional)

- If you have extra time, try implimenting
`with`

using the equivalence

```
{with {x e₁} e₂}
;; is equivalent to
{call {fun {x} e₂} e₁}
```

- Here you have to specify a type for
`x`

,`?`

or`(GuessTE)`

should work. What would you do in the typed interpreter without`(GuessTE)`

?

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