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

• Complete the function find-ids that scans an WAE expression for all identifiers in binding position. Your function should pass the given tests.

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

• Fill in a valid type for the function alpha

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

• Give formal substitution rules (pseudocode) for the With* construct from Homework 4.

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

• Convert the following example to de Bruijn index form. Explain your answer.

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

• Consider the following FLANG expression

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

• What does this evaluate to?

• What does it evaluate to if you replace let with let* (i.e. with with with*)?

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

Y-combinator, make-rec, and related

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

• Given the join construct discussed above, 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 If0

    [(If0 test-expr then-expr else-expr)
       (if (equal? (NumV 0) (eval test-expr env))
            (eval then-expr env)
            (eval else-expr env))]

• Complete the type rule for if0

_________________________________________________
Γ ⊢ { if0 e₁ e₂ e₃ } : __________________________

• Complete the racket code to type check if0

(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

• Give a tag scheme that allows representing the heap above as a vector of numbers in the style of gc.rkt

• Show the corresponding vector of integers. What do you have to change to make this work?

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)

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

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

• Can the function sumL be eliminated? How?

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)

Background

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

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.

Step 2

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

Add the following tests to your interpeter.

  (test (eval
         (With
          'add3
          (Fun 'x (GuessTE) (Add (Id 'x) (Num 3)))
          (With
           'add1
           (Fun 'x (NumTE) (Add (Id 'x) (Num 1)))
           (With 'x (Num 3) (Call (Id 'add1) (Call (Id 'add3) (Id 'x))))))
         (mtSub))
        (NumV 7))

  (test (eval
         (With 'identity (Fun 'x (GuessTE) (Id 'x))
          (With 'foo (Fun 'x (NumTE) (Add (Id 'x) (Num 1)))
                (Call (Call (Id 'identity) (Id 'foo)) (Num 123))))
         (mtSub))
        (NumV 124))

  (test (eval (With 'x  (Num 3)
                    (With
                     'f (Fun 'y (GuessTE) (Add (Id 'x) (Id 'y)))
                     (With 'x (Num 5) (Call (Id 'f) (Num 4)))))
              (mtSub))
        (NumV 7))

  (test (eval
         (Call (With 'x (Num 3) (Fun 'y (GuessTE) (Add (Id 'x) (Id 'y)))) (Num 4))
         (mtSub))
        (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
    (typecheck
     (With
      'add3
      (Fun 'x (GuessTE) (Add (Id 'x) (Num 3)))
      (With
       'add1
       (Fun 'x (NumTE) (Add (Id 'x) (Num 1)))
       (With 'x (Num 3) (Call (Id 'add1) (Call (Id 'add3) (Id 'x))))))
     (mtEnv)))
   (NumT))

  (test
   (resolve
    (typecheck
     (With 'identity (Fun 'x (GuessTE) (Id 'x))
           (With 'foo (Fun 'x (NumTE) (Add (Id 'x) (Num 1)))
                 (Call (Call (Id 'identity) (Id 'foo)) (Num 123))))
     (mtEnv)))
   (NumT))

  (test
   (resolve
    (typecheck (With 'x  (Num 3)
                     (With
                      'f (Fun 'y (GuessTE) (Add (Id 'x) (Id 'y)))
                      (With 'x (Num 5) (Call (Id 'f) (Num 4)))))
               (mtEnv)))
   (NumT))

  (test
   (resolve
    (typecheck
     (Call (With 'x (Num 3) (Fun 'y (GuessTE) (Add (Id 'x) (Id 'y)))) (Num 4))
     (mtEnv)))
   (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)?

Background

The example interpreter from Lecture 16 uses several new (to us) techniques including continuations

Roughly speaking, the Continuation Passing Style (CPS) takes a function call like

  (...stuff... (f ...args...) ...more-stuff...)

into

  (f/k ...args...
       (lambda (<*>)
         (...stuff... <*> ...more-stuff...)))

We'll learn more about continuations in the lectures, but today I want to take hands-on approach and modify an interpreter that uses CPS. This interpreter is higher level version of the one from Lecture 16, but uses CPS in the same way. This has several benefits, most obviously that the final eval function is tail-recursive. This is part of what lets our low-level interpreter work without a stack.

The overall goal of the lab is to add several arithmetic operations to the language.

Step 1

To get started, let's add support for a single argument decrement function. I've written it here as --, even though it doesn't mutate like -- does in most languages. Note that the parser already generates Sub1 abstract syntax for you.

In this "inside out" style, we need to call eval on the argument, with a last argument of "what to do next". The function continue will then handle processing the evaluated argument.

a. Define a variant doSub1K of the FAE-Cont type. Unlike the doSubK variant, it has no need to store a value for one of the arguments, because the only argument will be the parameter v of continue. So doSub1K needs only one field, which is an FAE-Cont (i.e. the next step).

At the same time add a dummy case to continue using ...., so your code compiles.

b. Mimic doSubK to define doSub1K. You can re-use num- by supplying a constant for one of it's arguments.

c. Fill in the case for Sub1 in eval, using (doSub1K k) as the third argument of your recursive call.

d. Your finished code should pass the following tests.

  (test (eval (parse `{-- 2}) (mtEnv) init-k) (NumV 1))
  (test (eval (parse `{{fun {x} {-- x}} 3}) (mtEnv) init-k) (NumV 2))
  (test (eval (parse `{{fun {y} {+ {-- y} {-- y}}} 10}) (mtEnv) init-k) (NumV 18))
  (test (eval (parse `{{fun {f} {f 4}} {fun {x} {-- x}}}) (mtEnv) init-k) (NumV 3))

2. Add Mul

The second part of the tutorial is to complete the definition for Mul. Since there are two arguments, we need to add two continuation steps. Luckily this works almost exactly the same as Add, and Sub, so you can copy and modify one of those cases. Note that you will probably want to define num*.

Your completed code (both parts) should pass the following test.

  (define fact-prog (parse
                 `{{fun {mkrec}
                        {{fun {fact}
                              ;; Call fact on 5:
                              {fact 5}}
                         ;; Create recursive fact
                         {mkrec
                          {fun {fact}
                               {fun {n}
                                    {if0 n
                                         1
                                         {* n {fact {-- n}}}}}}}}}
                   ;; mkrec:
                   {fun {body-proc}
                        {{fun {fX}
                              {fX fX}}
                         {fun {fX}
                              {body-proc {fun {x} {{fX fX} x}}}}}}}))
  (test (eval fact-prog (mtEnv)  init-k) (NumV 120))

• Move the definition of fact-prog to the top level of your program, and add the following as top level forms

(trace eval)
(trace continue)

(eval fact-prog (mtEnv) init-k)

This will produce lots of output, but see if you can make some educated guesses about the program flow.

• How deep does the recursion get?

• The last call to eval looks like (eval (Num 1) env k).

  • Write a human friendly representation of the environment env (you can shorten or leave out the function bodies)
  • What is the value of the continuation k?
  • How does this relate to a stack based evaluation of fact? I.e. at what stage do we have something very similar to this continuation on the stack?

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. I already had a solution for Homework 10 written in typed/racket and using the set operations. Rather than importing them (as we did with number? and procedure?), I decided to write them in plait, based on Hash Tables, which are provided in plait.

Types.

In general I have over-annotated the code in this tutorial, to help you think about polymorphic typechecking (to come in a later lecture), 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)))

Background

We have talked a bit about how to impliment objects using lambda. In this tutorial we're going to have a look at the Racket object system and in particular how it's used in the Racket gui library.

We will use the dialect racket/gui in our examples today, so start your file with

#lang racket/gui

Creating objects

Like many languages, objects are created using new. In Racket, this looks just like a function

#lang racket/gui
(define frame (new frame% [label "I've been Framed"]))

There's a lot going on in that one line, but not much to look at when we run it. In Java and Python it's easy to forget the original metaphor of sending messages to objects, but Racket in it is explicit with

(send <object> message <arg1> <arg2> ...)

Your turn

Steal the appropriate send form from the first example in the gui manual to get a window popping up.

Analysis

Now that we know that does something, let's look at it a bit from a language perspective. For each of the following, try to classify it as a value (like (lambda () 3)), or syntax (like if).

• new
• frame%
• send

Even syntax (sometimes called special forms) mostly defines expressions.

• What's one glaring exception?
• What do new and send evaluate to as expressions? The return value send is kindof a trick question.

The event loop

It turns out we just wrote a concurrent program: multiple things are happening at the same time. We get a hint that this is the case because we are returned to the REPL with our window still showing.

In the lower REPL window of DrRacket (or Emacs), type

(send frame show #f)

Notice the window goes away. The concurrency here is managed internally by an event loop. In order to really understand the difference with sequentially executing a sequence of functions or method calls, let's handle some user generated events.

Add the following code to your example

(define msg (new message% [parent frame] [label ""]))
(new button% [parent frame]
             [label "Panic"]
             [callback
              (lambda (button event)
                (send msg set-label "Don't Panic"))])
              

Analysis

We've been using, but ignoring, something Racket calls initialization arguments e.g. label and parent. These are conceptually very similar to constructor arguments in object oriented languages. Unlike Java they use a named argument syntax rather than a positional one (Python also has optional named arguments).

The most important initialization argument here is callback. This gives a function to run when the button is pressed. It's clear now that the control flow is not totally under the control of our code: like most gui frameworks, the runtime waits for an event and then hands us back control temporarily.

Some more things to notice from a programming language perspective

• We're actually discarding the return value of (new button% ...)
• What happens if we switch the order of (define msg ...) and (new button% ...). This seemingly relies on using msg before it is defined. What do conclude (or remember) about the top level in a racket module (cf. our long discussion about recursion).

Your turn

• combine what we saw so far to make the button kill the window.

Drawing

Let's add a drawing area to our UI, so we can print more reassuring text

Here's some sample code to set up a canvas and print some text in it.

(define canvas (new canvas% [parent frame]))
(define (panic)
  (let ([dc (send canvas get-dc)])
    (send dc set-scale 5 5)
    (send dc set-text-foreground "blue")
    (send dc draw-text "Don't Panic!" 0 0)
    (send dc set-scale 1 1)))

Nothing happens until you call the function (panic) from the REPL.

Your turn

• Make the callback for the button draw the big blue text.
• If you have time, add some state so that each press of the button draws the text in a different place

Subclassing

A common way to reuse a class is to subclass it. In Racket this is done by using the class form.

Let's start with the following modification, which should not break anything.

(define my-canvas%
  (class canvas%
    (super-new)))
(define canvas (new my-canvas% [parent frame]))

Things to observe:

• We've define a new class, inheriting from canvas%
• We've explicitly called '(super-new)' to do the superclass initialization. This allows control over how initialization arguments are processed, i.e. before or after the superclass is initialized.
• Perhaps most interestingly from a programming language point of view, classes are values in the language, and we can bind them to identifiers just like numbers and functions.

In order to overide a method in a subclass, we use define/override like follows

(define my-canvas%
  (class canvas%
    (super-new)
    (define/override (on-event event)
      (when (send event button-down? 'any)
        (panic)))))

Your turn

Modify the definition of my class so that button clicks cause diameter 10 circles to be drawn at the appropriate place. You can either use this to send messages to the current object, or use the inherit to make the methods you need available as regular functions.

Background

We have mainly been using the racket dialect plait this term. This dialect uses a typed system modelled on that of ML. This has some advantages, including allowing quite good type inference. Unfortunately it is unable to type several constructs that are fairly natural in dynamically typed languages. One interesting and practical idea in programming languagues is so called Gradual typing. In a gradually typed language some expressions have static types checked at compiled time while others are checked at run time. In this tutorial we will explore the idea of union types used by the gradually typed language typed/racket.

Type inference versus gradual typing

One subtlety to understand right away is that lack of type annotations is much different from gradual typing.

Conside the following function.

#lang plait

(define (fun arg)
    (if arg
        'foo
        'bar))

• Type fun in the REPL to see what the infered type of this function is.

• To convince yourself that this checking happens at compile time, add the following

(define (bar)
  (fun "hello"))

Notice that the "bad" code is never run, but we still get a typecheck error.

• Try changing

    #lang plait
  

  to

    #lang plait #:untyped
  

  Not only does it quiet the typechecker, but you can run the function (bar). Why is this?

• Try changing the #lang to typed/racket. What is the inferred type of fun?

  • To help understand this, note that typed/racket reports function type A B -> C as (-> A B C). This is no loss of information because the arrow is always in the same place in our usual form.

  • the (U … ) form defines a union type, which here looks a bit like dodging the question, by listing all possible return values.

  • the Any marks a dynamically typed identifier

• Write a type annotation for the function fun by copying the inferred type.

• Modify your type annotation to look more like the familar (A -> B) form

• Modify your type annotation to avoid the use union types. Note that your new type will be less precise than before, but possibly more meaningful for humans. You may want to drop or modify the function bar so you can get rid of the Any.

• Modify the actual function definition to

(define (fun arg)
    (if arg
        'foo
        "bar"))

• comment out the type annotation
• verify this no longer typechecks in plait (comment out the type annotation)
• verify that it does typecheck in typed/racket, and put back a "human friendly" type annotation.

Typing "Lambda Lists"

Let's look back at our example from implimenting data structures with functions.

#lang plait #:untyped
(define (_cons x y) (lambda (s) (s x y)))
(define (_first x) (x (lambda (x y) x)))
(define (_rest x) (x (lambda (x y) y)))
(define a (_cons 1 'alpha))
(define b (_cons 'beta 4))
;
(test (_first a) 1)
(test (_rest b) 4)
(test (_rest a) 'alpha)

It turns out that the test form is not available in typed/racket, but similar functionality is available from rackunit.

Let's convert our example to typed/racket and rackunit. Notice we leave the type-checker off at first.

#lang typed/racket/no-check
(define (_cons x y)
  (lambda (s)
    (s x y)))
(define (_first x) (x (lambda (x y) x)))
(define (_rest x) (x (lambda (x y) y)))

(module+ test
  (require rackunit)
  (define a (_cons 1 'alpha))
  (define b (_cons 'beta 4))
  (check-equal? (_first a) 1 "furst")
  (check-equal? (_rest b) 4 "rust")
  (check-equal? (_rest a) 'alpha))

• Try switching to #lang typed/racket. Unlike our previous example, this one doesn't typecheck without annotations.

  • The main point of the remaining error messages seems to be that typed/racket can't seem to infer when things are functions. Although plait can't typecheck some things, it is actually better at inferring what is a function.

• Comment out everything but the definition of _cons, and try to find an annotation for parameter s that lets typed/racket typecheck it. Be as vague as you can get away with. You'll need to replace lambda with lambda:

• Define a type alias using (define-type-alias BinOp (Any Any -> Any))

• Use this type alias to give a type-annotation (using (: … )) for _cons. Can you get rid of your previous type annotation on s? Why or why not?
• Define a second type alias _Pair for the return type of _cons, and use this in your type annotation. Also use _pair to annotate _first and _rest, as follows:

(define (_first [x : _Pair]) (x (lambda (x y) x)))
(define (_rest [x : _Pair]) (x (lambda (x y) y)))

• At this point, you should be able to change (require rackunit) to (require typed/rackunit) and have all tests pass.

• You might think we're not using union types at all, except that Any is really the biggest union type of all. Define a third type alias Thing and replace the use of Any with Thing. Make your definition of Thing general enough, but less general than Any. Your final set of type-aliases will be mutually recursive.

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

The exam will cover lectures 1 to 9, and homework 1 to 5.

To help you get a feel for the style of questions to expect, I have included some questions from previous midterms and finals below. Note that this is a sample of questions that might be asked on a midterm or final. Not all of them would necessarily be on one midterm. You should feel free to check your answers with DrRacket, but keep in mind you won't have a computer on the exam.

1 Types

1.1 Basic Types

Fill in a valid plait type for each of the following functions.

#lang plait
(define (f) 8)
(has-type f : ....)
(define h  (lambda (x y)
         (string-length (string-append x y))))

(has-type h : ....)

1.2 More complicated types

Give a valid type declaration for the following function

(define (glonk f g)
  (lambda (x)
    (let* ((h (g x))
           (i (f h)))
      i)))
(has-type glonk : ....)

2. Ragg Grammars

• Write a ragg format grammar that parses the following emoticons, assuming the lexer returns each character as a string token and ignores whitespace.

O_O o-o O_o o_O o_o O-O :-) :) :o) :] :c

• Explain the difference between the following two ragg grammars.

;; Grammar 1
ae: NUMBER
    | NUMBER "+" ae
    | NUMBER "-" ae

;; Grammar 2
ae: NUMBER
    | ae "+" ae
    | ae "-" ae

3. Substitution rules

• Complete the following substitution rules for eager substitution

{call f arg}[y/x] =

{fun {id} body}[y/x] =

• repeat the exercise for lazy substitution

4. Higher Order Functions

4.1 pair

Consider the tests

(test ((pair 1 3) +) 4)
(test ((pair 1 3) -) -2)
(test ((pair 2 3) *) 6)

1. Give a valid type for pair

2. Write the function pair to pass these tests.

4.2 map

Fill in a definition for the function map. A test is given to remind you how it works.

(define (map [fun : ('a -> 'b)] [lst : (Listof 'a) ]) : (Listof 'b)
    ....)
(test
 (map add1 (list 1 2 3 4 5))
 (list 2 3 4 5 6))

5. Environments

In the following questions, you can use any reasonable notation for the environments.

Consider the plait code:

(run `{with {x 1} {with {x {+ x 2}} x}})

• Evaluate the given FLANG code using the so-called "formal" evaluation rules.

• The following shows the code running in the (dynamically scoped) FLANG interpreter from Lecture 7 with (trace eval) added. Fill in the missing environments.

>(eval (With 'x (Num 1) (With 'x (Add (Id 'x) (Num 2)) (Id 'x))) ________)
> (eval (Num 1) _______)
< (Num 1)
>(eval (With 'x (Add (Id 'x) (Num 2)) (Id 'x)) ________________))
> (eval (Add (Id 'x) (Num 2)) _________________)
> >(eval (Id 'x) ________________))
< <(Num 1)
> >(eval (Num 2) ________________________)
< <(Num 2)
< (Num 3)
>(eval (Id 'x)  __________________________________))
<(Num 3)
3

Consider the FLANG code

{call {with {x 3} {fun {y} x}} 4}

The following is a trace of evaluating it with the statically scoped interpreter of Lecture 8. Fill in the missing environments.

>(eval (Call (With 'x (Num 3) (Fun 'y (Id 'x))) (Num 4)) (EmptyEnv))
> (eval (With 'x (Num 3) (Fun 'y (Id 'x))) __________)
> >(eval (Num 3) __________)
< <(NumV 3)
> (eval (Fun 'y (Id 'x)) _______________________________)
< (FunV 'y (Id 'x) _______________________________)
> (eval (Num 4) __________)
< (NumV 4)
>(eval (Id 'x) ____________________________________________________)
<(NumV 3)
3

6 Evaluators

6.1 With

Complete the following eager substition based evaluator for a simplified version of WAE with only addition. You may assume a function subst is defined.

(define (eval expr)
  (type-case WAE expr
    [(Num n) n]
    [(Add l r) ____________________)]
    [(With bound-id named-expr bound-body)
     ________________________]
    [(Id name) (error 'eval (string-append "free identifier: " (to-string name)))]))

• repeat the exercise for a lazy substitution based evaluator

• repeat the exercise for an eager environment based evaluator

6.2 Extending to multiple arguments

In the following, the Mul constructor is extended to allow an arbitrary number of arguments, e.g. from parsing {* {+ 1 2} 3 4}. Fill in the definition of mul-helper to support this change. For full marks use either foldl or tail recursion. For simplicity the parser is omitted here, and the test works directly on the abstract syntax tree.

(define-type AE
  [Num  (val : number)]
  [Add  (l : AE) (r : AE)]
  [Sub  (l : AE) (r : AE)]
  [Mul  (args : (listof AE))]
  [Div  (l : AE) (r : AE)])

(define (eval expr)
  (type-case AE expr
    [Num (n) n]
    [Add (l r) (+ (eval l) (eval r))]
    [Sub (l r) (- (eval l) (eval r))]
    [Mul (args) (mul-helper args 1)]
    [Div (l r) (/ (eval l) (eval r))]))

(define (mul-helper args acc) ....)

(test (eval (Mul (list (Add (Num 1) (Num 2)) (Num 3) (Num 4)))) 36)

7 mutation and recursion

Consider the following code for setting up a recursive environment

(define (extend-rec id expr rest-env)
  (let* ([new-cell (box (NumV 42))]
         [new-env  (Extend id new-cell rest-env)]
    (begin (set-box! new-cell (eval expr new-env)) new-env)))

• Draw a diagram of the resulting environment:

  (extend-rec 'f (Fun 'x (Call (Id 'f) (Id 'x))) (EmptyEnv)))

In class we defined a rec construct, evaluated by

[Rec (bound-id named-expr bound-body)
  (eval bound-body (extend-rec bound-id named-expr env)]

• What is the result of (eval `{rec {x x} x},[]). How would you fix this?

8. Recursion, define-type

Fill in a definition for the function sumtree so that it sums up all the numbers in a numtree.

(define-type numtree
  [leaf (n : Number)]
  [tree (l : numtree) (r : numtree)])

(define (sumtree t) ....)

(test (sumtree (tree
                (tree (leaf 3) (leaf 4))
                (tree (leaf 5) (tree (leaf 6) (leaf 7)))))
       25)