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

Details about topics will be added to this page closer to the date of the test.

Garbage Collection

Consider the following definitions in the format of Homework 2; the vector represents a heap, with each heap location either being a primitive or an object to other heap locations.

(define-type Object
  [object (Listof Index)]
  [primitive])

(define example-heap
  (vector
   (primitive)          ; 0
   (object (list 8))    ; 1
   (object (list 1))    ; 2
   (object (list 7))    ; 3
   (object (list 0 3))    ; 4
   (primitive)          ; 5
   (object (list 0))    ; 6
   (object (list 4 6)) ; 7
   (object (list 2)))) ; 8

• (1) Give a minumum (smallest possible) set of roots so that a marking phase will find no garbage in the heap.

• (2) Suppose the set of roots is empty. How much of the heap will be marked as live by reference counting? Suppose the value at location 7 is a primitive, how does this change your answer?

rewrite rules

-( 1) Give a rewrite rule (in the #lang pl broken dialect) for a short circuiting nand (negated and) by transforming it to not and.

(test (nand #f) => #t)
(test (nand #f (/ 1 0)) => #t)
(test (nand #t #f (eq? (/ 1 0) 0)) => #t)

• (2) Give a rewrite rule for and (here called and2 to reduce confusion) that uses andmap to implement it. You will probably need a computer to get the details right here. The real issue is quoting or delaying evaluation.

(test (and2 #f) => #f)
(test (and2 #f (/ 1 0)) => #f)
(test (and2 #t #f (eq? (/ 1 0) 0)) => #f)

All of the examples are either the course language "PL", or the toy language "FLANG". It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

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 pl broken
(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 pl broken
(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 pl broken
(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 pl broken

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

((lambda (x) (x x)) (lambda (x) 
                      (begin 
                        (display "hi!\n")
                        (x x))))

• (2) Given the following definitions, trace the evalutation of (test #f) Use a computer for this one.

#lang pl broken

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

All of the examples are either the course language "PL", or the toy language "FLANG". It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

Data structures with functions

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

(define-type Map = String -> Number)

; stuff

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

(test (test-map "bob") => 2)
(test (test-map "mary") => 1)
(test (test-map "happiness") =error> "empty map!")

Embedding

• (1) Given the syntactic (i.e. not using racket procedures) definition of an FLANG function, write the funcall function that allows calling FLANG functions from Racket. This one you probably will need a computer to get the details right, but try to get the main idea on paper.

(define-type VAL
   [NumV Number]
   [FunV Symbol FLANG ENV])

(define foo (eval (parse "{fun {x} {+ x 1}}") (EmptyEnv)))
(define bar (eval (parse "41") (EmptyEnv)))
(: funcall : VAL VAL -> VAL)
; define funcall
(test (funcall foo bar) => (NumV 42))

• (2) Now consider the FLANG interpreter that uses union types to represent FLANG values. Write funcall for this intepreter.

  (define-type VAL = (U Number (VAL -> VAL)))
  
  ; write funcall; don't forget a type signature.
  
  (test (funcall f 41) => 42)

All of the examples are either the course language "PL", or the toy language "FLANG". It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

Substitution Caches

• (1) Write a lookup function with this type signature to look up a symbol in a substitution cache / environment. For extra practice, use match.

    (: lookup : Symbol (Listof (List Symbol Sexp)) -> Sexp)
    

• (2) Explain why environments use a list or list-like structure, rather than something more efficient like a hash table.

Dynamic and Lexical Scope

• (1) Explain why the following evaluation rule guarantees our the corresponding interpreter will not have lexical scope.

  eval ({fun { x } E} , sc ) = {fun { x } E}

• (2) Evaluate the following dynamically scoped racket code.

#lang pl dynamic

(define (blah func x)
  (func x))
;
  (let ((x 7))
    (let ((f (lambda (y) (+ x y))))
      (let ((x 6))
        (blah f 5))))

• (3) Evaluate the same code using substitution semantics.

• (4) Modify the following evaluation rules so that they make sense for the limited dialect of racket used in the preceding example.

  eval(N,env)         = N
  eval({+ E1 E2},env) = eval(E1,env) + 
                        eval(E2,env)
  ; ...
  eval(x,env)                = lookup(x,env)
  eval({with {x E1} E2},env) = eval(E2,extend(x,eval(E1,env),env))
  eval({fun {x} E},env)      = <{fun {x} E}, env>
  eval({call E1 E2},env1)  =
          if eval(E1,env1) = <{fun {x} Ef}, env2> then
                eval(Ef,extend(x,eval(E2,env1),env2))
          else 
                error!

• (5) Evaluate the previous example using your new environment based evaluation rules.

• (6) Compare the behaviour of the following code under dynamic scope, substitution, and environment based evaluation.

    {with {f {fun {y} {+ x y}}}
          {with {x 7}
            {call f 1}}}
  

There will be one midterm, worth 25% of your mark, on March 20, 2014.

Details about topics will be added to this page closer to the date of the test.

All of the examples are either the course language "PL", or the toy languages "WAE" or "FLANG" (WAE with functions). It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

Lazy evaluation

1. Evaluate the following using purely lazy substitution and purely eager substitution

 {with {x 1}
       {with {x {+ x 1}}
         x}}

1. Give an example of WAE code exhibiting name capture,

de Bruijn Indices

Convert the following WAE expression to deBruijn form.

{with {x 1}
      {with {x {+ x 1}}
        {with {y x} x}}

All of the examples are either the course language "PL", or the toy languages "WAE" or "FLANG" (WAE with functions). It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

BNF and Parsing

Consider the subset of Racket consisting of define, +,-,*, and numbers and identifiers. Complete the following BNF for this language, to include defining and calling functions. If you want to experiment, you may find lexer.rkt and driver.rkt helpful.

expr: arith | define | IDENT | NUMBER
arith: "(" op NUMBER+ ")"
op: "+" | "-" | "*"
define: "(" "define" IDENT expr ")"

Using BNF

The following expression reveals at least one error in the grammar given above. Correct it.

(define (glug x) (if (zero? x) 1 (* x (glug (- x 1)))))

Using match

Fill in the following match based parser for lists of as and bs

(define-type ABList
  [Empty]
  [A ABList]
  [B ABList])

(: parse-sexpr : Sexpr -> ABList )
(define (parse-sexpr sexpr)
  (match  sexpr
;; stuff
  ))
  
(test (parse-sexpr '(a b a)) => (A (B (A (Empty)))))
(test (parse-sexpr '(a)) => (A  (Empty)))

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

Substitution

• Evaluate the following by substitution.

{with {x {+ 4 2}}
      {with {x {+ x 1}}
            {* x x }}}

• Identify the problem with this definition of substitution semantics:

  To substitute an identifier i in an expression e with an expression v, replace all instances of i that are not themselves binding instances, and that are not in any nested scope, with the expression v.

More Higher Order Functions

For each of the function type declarations below, write a PL Racket function with that type declaration. Each function should do something "sensible"; describe what that is in a few words.

(define-type UnaryFun  = (Real -> Real))
(define-type BinaryFun = (Real Real -> Real))

(: a : UnaryFun Real -> Real )

(: b : BinaryFun Real -> UnaryFun )

(: c  : BinaryFun UnaryFun UnaryFun -> BinaryFun)

(: d  : UnaryFun UnaryFun -> UnaryFun)

All of the examples are either the course language "PL", or the toy languages "WAE" or "FLANG" (WAE with functions). It's fine (and recommended) to use a computer to check your answers, but remember that you won't have a computer on the exam.

Racket

For each of the following untyped racket expressions, write what it evaluates to (if valid) or explain what the error is.

#lang pl

(if "true" 0 1)

(first (rest '(a b)))

(cond
 [(> 3 1) 0]
 [(< 3 1)  1])

(+ 1 2 3)

(and #f (/ 1 0))

(cons 3 (list 1 2))

(let ([ x -1]) 
  (let ([ x (+ 10 x)] 
    [ y (+ x 1) ]) 
    (+ x y))) 

Types

Give a valid type declaration for each of the following functions. Don't worry too much about the subtleties of different kinds of numbers.

(define (f) 8)

(define (g x)
  (cond
   [(string? x) x]
   [(number? x) x]
   [else #f]))

(define h  (lambda (x y) 
         (string-length (string-append x y))))

Variant types

Given the following variant type declaration, define a function to test two shapes for equality (never mind the built-in equal? predicate does this perfectly well).

(define-type Shape
  [Square  Number] ; Side length
  [Circle  Number] ; Radius
  [Triangle Number Number]) ; height width

Higher order functions

Consider the tests

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

1. Write the function pair to pass these tests.

2. Give a valid type declaration for pair

Tail recursive functions

In the following tail recursive function, what should <if-expr> and <second-argument> be?

(: sum : (Listof Number) Number -> Number )
(define (sum list acc)
  (if (null? list) 
      ; <if-expr>
      (sum (rest list) 
       ; <second-argument>
       )))

( test (sum '(4 5 6) 0) => 15)