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.

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

#lang plai
(test 
 (let (
; ...
)
   (len len  '(a b c d e)))  5)
#lang plai
(test 
 (let 
;...
   ((len len)  '(a b c d e))) 5)
#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

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

Y combinator

#lang plai
((lambda (x) (x x)) (lambda (x) 
                      (begin 
                        (display "hi!\n")
                        (x x))))
#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

(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

(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

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

Substitution rules

{call f arg}[y/x] =

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

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

    )))
(define (circle radius)
  (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)