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

(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) ....]
    [(Add left right) ....]
    [else ....]))

(test (find-ids (Num 3)) '())
(test (find-ids (Id 'x)) '())
(test (find-ids (With 'x (Num 3) (Id 'x))) '(x))
(test (find-ids (Add
                 (With 'x (Num 3) (Id 'x))
                 (With 'y (Num 3) (Id 'y)))) '(x y))
(test (find-ids (Add
                 (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))

#lang plait
(define (alpha f g)
  (lambda (x)
    (g (f x))))
(has-type  alpha : ....)
(test ( (alpha add1 add1) 1) 3)
(test ( (alpha add1 to-string) 42) "43")

{with* {{x1 v1} ... {x_k e_k}} body}[E/y] = ....

    {with {x 1}
      {with {y x}
            {with {x x}
                  {+ x y}}}}
=>
{with ....
      {with ....
            {with ....
                  {+ ....}}}}

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

#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)]
  [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))

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)
(define-type Answer
  [num (n : Number)]
  [bool (b : Boolean)])

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

(define (circle radius)
    ....)

(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

    {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 If0

    [(If0 test-expr then-expr else-expr)
       (if (equal? (NumV 0) (eval test-expr env))
            (eval then-expr env)
            (eval else-expr env))]
_________________________________________________
Γ ⊢ { if0 e₁ e₂ e₃ } : __________________________
(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


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)

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

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)