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 midterm, worth 25% of your mark, will be held in class on Feb. 21, 2019.

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

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

1 Types

1.1 Basic Types

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

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

(has-type h : ....)

1.2 More complicated types

Give a valid type declaration for the following function

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

2. Ragg Grammars

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

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

• Explain the difference between the following two ragg grammars.

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

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

3. Substitution rules

• Complete the following substitution rules for eager substitution

{call f arg}[y/x] =

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

• repeat the exercise for lazy substitution

4. Higher Order Functions

4.1 pair

Consider the tests

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

1. Give a valid type for pair

2. Write the function pair to pass these tests.

4.2 map

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

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

5. Environments

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

Consider the plait code:

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

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

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

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

Consider the FLANG code

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

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

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

6 Evaluators

6.1 With

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

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

• repeat the exercise for a lazy substitution based evaluator

• repeat the exercise for an eager environment based evaluator

6.2 Extending to multiple arguments

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

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

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

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

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

7 mutation and recursion

Consider the following code for setting up a recursive environment

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

• Draw a diagram of the resulting environment:

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

In class we defined a rec construct, evaluated by

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

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

8. Recursion, define-type

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

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

(define (sumtree t) ....)

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