This feed contains pages with tag "cs3613".

# 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

- The
`subst`

function (i.e. a substitution based eval) - 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 ruleTypecheck the following expression using your rule and any others needed

```
{join
{fun {x : num} {+ x x}}
{fun {y : num} {- y 1}}}
```

- Fill in the typechecking case for
`join`

(assume a suitable modified version of tfae.rkt)

```
[(Join fun1 fun2)
(let* ([type1 (typecheck fun1 env)]
[type2 (typecheck fun2 env)])
(type-case Type type1
[(ArrowT a b)
(type-case Type type2
[(ArrowT c d) ....]
[else (type-error fun2 "function")])]
[else (type-error fun1 "function")]))]
```

Here are some tests

```
(define join-ex1
(Join (Fun 'x (NumTE) (Add (Id 'x) (Id 'x)))
(Fun 'y (NumTE) (Sub (Id 'y) (Num 1)))))
(test (eval (Call join-ex1 (Num 3)) (mtSub)) (NumV 5))
(test (typecheck join-ex1 (mtEnv)) (ArrowT (NumT) (NumT)))
(define join-ex2
(Join (Fun 'x (NumTE) (Add (Id 'x) (Id 'x)))
(Fun 'y (BoolTE) (Id 'y))))
(test/exn (typecheck join-ex2 (mtEnv)) "not bool"))
```

### Typechecking `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?

- Write a human friendly representation of the environment

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

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

- The main point of the remaining error messages seems to be that
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)
```

Give a valid type for

`pair`

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