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

## Overview

The final exam, worth 50% of your mark, is tentatively scheduled for 2PM on April 19.

The exam is cumulative, covering all of the lectures, assignments, and tutorials.

• See tutorial5 and tutorial8 for practice questions for the two midterms. Solutions are available on the handin server.

## More sample Questions

### Types

Fill in a valid `plai-typed` type for each of the following functions.

```#lang plai-typed
(define (f) 8)
(has-type f :              )
(define h  (lambda (x y)
(string-length (string-append x y))))

(has-type h :                   )
```

### Higher order functions

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.

### More types

Give a valid type declaration for the following function

```(define (glonk f g)
(lambda (x)
(let* ((h (g x))
(i (f h)))
i)))
```

### Data structures with functions

Fill in the definitions of `empty-map` and `extend` such that the given tests pass.

```#lang plai-typed

(define-type-alias Map  (string -> number))

(define (empty-map) : Map

)

(test/exn ((empty-map) "bob")  "empty map!")

(define (extend key val the-map) : Map

)

(define test-map
(extend "mary" 1
(extend "bob" 2
(empty-map))))

(test (test-map "bob")  2)
(test (test-map "mary") 1)
(test/exn (test-map "happiness") "empty map!")
```

### Recursion

• (1) Use `let` and `lambda` to define a recursive list length function that takes itself as a parameter, so that the following test passes.
```#lang plai
(test
(let (
; ...
)
(len len  '(a b c d e)))  5)
```
• (2) Write the curried version of `len`, (still using `let` and `lambda`) that makes the following test pass.
```#lang plai
(test
(let
;...
((len len)  '(a b c d e))) 5)
```
• (3) fill in the definition of make-len to make the following test pass.
```#lang plai
(test
(let
((make-len
; stuff
(if (null? list)
0
(+ 1 (len (rest list)))))))))
(let ([len (make-len make-len)])
(len '(a b c d e)))) 5)
```

### Evaluation Delay

• (1) What is the output of running this racket code?
```#lang plai

(define (make-test self)
(let ([test (self self)])
(lambda (arg)
(if arg
arg
(test (not arg))))))
(display "after define make-test\n")

(define test (make-test make-test))

(display "after define test\n")

(display (test #f))
```
• (2) Modify the let statement in the above code so that it runs to completion.

### Y combinator

• (1) What is the output from the following code? Explain your answer.
```#lang plai
((lambda (x) (x x)) (lambda (x)
(begin
(display "hi!\n")
(x x))))
```
• (2) Given the following definitions, trace the evalutation of `(test #f)` I recommend using the debugger, then writing down your trace.
```#lang plai

(define (make-recursive f)
((lambda (x) (f (lambda (n) ((x x) n))))
(lambda (x) (f (lambda (n) ((x x) n))))))

(define test
(make-recursive
(lambda (test)
(lambda (arg)
(if arg
arg
(test (not arg)))))))
```

### syntax rules

• Give a syntax rule for a short circuiting `nor` (negated or).
```(test (nor #f) #t)
(test (nor #t (/ 1 0)) #f)
(test (nor #f #t (eq? (/ 1 0) 0)) #f)
```

### Union types

```(define (fun arg)
(if arg
(lambda (x) 'foo)
"bar"))
```

### Typechecking

Given the following definitions for a join construct (and assuming the test passes)

1. Given an appropriate typing rule.
2. Typecheck the expression in the test using your rule, and any others needed.
3. Give Racket code to define the `join` case of a typechecking function `typecheck` To test your answer, you can start with trcfae-t.rkt.
```(define-type FAE
⋮
[join (fun-1 : FAE) (fun-2 : FAE)])

(define (interp a-fae env)
(type-case FAE a-fae
⋮
[join (fun-1 fun-2)
(closureV 'x
(call fun-2
(call fun-1 (id 'x))) env)]))

(test (interp (call
(join (fun 'x (add (id 'x) (id 'x)))
(fun 'y (sub (id 'y) (num 1))))
(num 3))
(mtSub))
(numV 5))

(test (typecheck
(join (fun 'x (numTE) (add (id 'x) (id 'x)))
(fun 'y (numTE) (sub (id 'y) (num 1))))
(mtEnv))
(arrowT (numT) (numT)))
```

### Boxes and mutation

• What is the result of the following two code snippets. Explain the difference.
• Will this code typecheck in `plai-typed`? Why or why not?
• Will this code typecheck in `typed/racket`? Why or why not?
```(define foo (list 1 3))
(define bar (second foo))
(set! bar 2)
foo

(define foo2 (list 1 (box 3)))
(define bar2 (second foo2))
(set-box! bar2 2)
foo2
```

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

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

### Environments

Fill in the type environments in the following output from the typechecker in trcfae-t.rkt. You can use whatever environment notation you find convenient.

```>(typecheck
(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)))
(mtEnv))
> (typecheck
(fun 'x (numTE)
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1)))))
___________________________________________________________)
> >(typecheck
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
___________________________________________________________)
> > (typecheck (id 'x)
___________________________________________________________)
< < (numT)
> > (typecheck (num 1)
____________________________________________________________)
< < (numT)
> > (typecheck
(call (id 'fub) (sub (id 'x) (num 1)))
__________________________________________________________)
> > >(typecheck
(id 'fub)
__________________________________________________________)
< < <(arrowT (numT) (numT))
> > >(typecheck
(sub (id 'x) (num 1))
__________________________________________________________)
> > > (typecheck
(id 'x)
__________________________________________________________)
< < < (numT)
> > > (typecheck
(num 1)
_________________________________________________________)
< < < (numT)
< < <(numT)
< < (numT)
< <(numT)
< (arrowT (numT) (numT))
>(typecheck (call (id 'fub) (num 1))
_______________________________________________________________)
> (typecheck (id 'fub)
_______________________________________________________________)
< (arrowT (numT) (numT))
> (typecheck (num 1)
_______________________________________________________________)
< (numT)
<(numT)
(numT)
```
• Fill in the value environments in the following output from the the interpreter in trcfae-t.rkt. You can use whatever environment notation you find convenient, but note that in this case the environments have to be recursive
```>(interp
(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)))
(mtSub))
> (interp
(fun 'x (numTE)
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1)))))
______________________________________________________________
______________________________________________________________)

< (closureV
'x
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
(aRecSub 'fub (box (numV 42)) (mtSub)))
>(interp
(call (id 'fub) (num 1))
______________________________________________________________
______________________________________________________________)
> (interp
(id 'fub)
______________________________________________________________
______________________________________________________________)
< #0=(closureV
'x
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
(aRecSub 'fub '#&#0# (mtSub)))
> (interp
(num 1)
______________________________________________________________
______________________________________________________________)

< (numV 1)
>(interp
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
______________________________________________________________
______________________________________________________________)
> (interp
(id 'x)
______________________________________________________________
______________________________________________________________)
< (numV 1)
>(interp
(call (id 'fub) (sub (id 'x) (num 1)))
______________________________________________________________
______________________________________________________________)
> (interp
(id 'fub)
______________________________________________________________
______________________________________________________________)
< #0=(closureV
'x
(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
(aRecSub 'fub '#&#0# (mtSub)))
> (interp
(sub (id 'x) (num 1))
______________________________________________________________
______________________________________________________________)
> >(interp
(id 'x)
______________________________________________________________
______________________________________________________________)
< <(numV 1)
> >(interp
(num 1)
______________________________________________________________
______________________________________________________________)

< <(numV 1)
< (numV 0)
>(interp
#0=(if0 (id 'x) (num 1) (call (id 'fub) (sub (id 'x) (num 1))))
(aSub 'x (numV 0) #1=(aRecSub 'fub (box (closureV 'x #0# #1#)) (mtSub))))
> (interp
(id 'x)
______________________________________________________________
______________________________________________________________)
< (numV 0)
>(interp
(num 1)
______________________________________________________________
______________________________________________________________)
<(numV 1)
(numV 1)
```

### Objects

Fill in the definitions of `square`, `circle`, and `triangle` to define a simple object hierarchy, where `area` is implimented in each subclass, and `round?` is overridden (i.e. everything should inherit from `shape%`.

```#lang plai

(define pi 3.141592653589793)

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

(define (square side)
(lambda (method)
(case method

)))
(lambda (method)
(case method

)))
(define (triangle height width)
(lambda (method)
(case method

)))

(define a-square (square 1))
(define a-circle (circle 1))
(define a-triangle (triangle 1 2))
(test (a-square 'area) 1)
(test (a-circle 'area) pi)
(test (a-triangle 'area) 1)
(test (a-square 'round?) #f)
(test (a-circle 'round?) #t)
(test (a-triangle 'round?) #f)
```