UNB/ CS/ David Bremner/ teaching/ cs3613/ tests/ CS3613 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

O_O o-o O_o o_O o_o O-O :-) :) :o) :] :c
;; Grammar 1
ae: NUMBER
    | NUMBER "+" ae
    | NUMBER "-" ae

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

3. Substitution rules

{call f arg}[y/x] =

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

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

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

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)