UNB/ CS/ David Bremner/ tags/ cs3613

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) ....]
[else ....]))

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

### 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)]
(r : Expr)])
(let ([interp
(lambda (ex)
(let ([worker ....])
(worker worker ex)))])
```

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

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

....)

(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)
```
Posted Wed 24 Apr 2019 09:00:00 AM ADT Tags: /tags/cs3613

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

```  (test (eval
(With
(Fun 'x (GuessTE) (Add (Id 'x) (Num 3)))
(With
(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
(Fun 'x (GuessTE) (Add (Id 'x) (Num 3)))
(With
(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)`?
Posted Mon 08 Apr 2019 08:30:00 AM ADT Tags: /tags/cs3613

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

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?
Posted Mon 01 Apr 2019 08:30:00 AM ADT Tags: /tags/cs3613

# 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)
(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)))
```
Posted Mon 25 Mar 2019 08:30:00 AM ADT Tags: /tags/cs3613

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

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.

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

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

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

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

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.

Posted Mon 18 Mar 2019 08:30:00 AM ADT Tags: /tags/cs3613

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

Posted Mon 11 Mar 2019 08:30:00 AM ADT Tags: /tags/cs3613

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]
[(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)
```
Posted Thu 21 Feb 2019 11:30:00 AM AST Tags: /tags/cs3613