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

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.


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

Typechecking


Typechecking the join construct

    {join
     {fun {x : num} {+ x x}}
     {fun {y : num} {- y 1}}}
    [(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)

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

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

Choice of algorithm