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.

1. The exam will be open book, and you can use any reference material you like.
2. In particular you are welcome to use DrRacket to work on your exam.
3. 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

1. 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.

2. 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.

3. 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}}

1. Explain how and why evaluation fails with a substition based evaluator.
2. Explain how and why evaluation fails with an environment based evaluator.
3. 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 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 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.