mutation and pass-by-value

• (1) Write the postinc! and preinc! procedures (modelled on x++ and ++x)

(: postinc! : (Boxof Integer) -> Integer)
; stuff

(define foo (box 3))

(test (postinc! foo) => 4)
(test (unbox foo) => 4)

(: preinc! : (Boxof Integer) -> Integer)
; stuff

(test (preinc! foo) => 4)
(test (unbox foo) => 5)

• (2) What happens if you try to write procedures using set! instead of set-box!

(: postinc! : Integer -> Integer)
(: preinc! :  Integer -> Integer)

• (3) Use #lang pl broken and rewrite rules to implement postinc! and preinc! that operate "directly" on integers.

(define foo 3)

(test (postinc! foo) => 4)
(test foo => 4)

(test (preinc! foo) => 4)
(test foo => 5)

closures with state

• (1) Write the function guess-maker to produce a "guessing game object"

(: guess-maker : Integer -> (Integer -> String) )
; stuff

(define game1 (guess-maker 17))

(test (game1 1) => "Wrong")
(test (game1 2) => "Wrong")
(test (game1 3) => "Wrong")
(test (game1 2) => "Too Slow!")
(test (game1 17) => "Too Slow!")

(define game2 (guess-maker 42))
  
(test (game2 2) => "Wrong")
(test (game2 3) => "Wrong")
(test (game2 42) => "Correct!")

• (2) Some behaviour is unspecified by these tests. What is it?

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)

Boxes and cyclic structures.

• (1) What are the values of foo and foo2 after the following code is executed? Explain the difference.

(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

• (2) For the following sample code, give an appropriate recursive type for Node, to represent a linked list using boxes.

(: set-next! : Node Node -> Void )

(: node1 : Node)
(define node1 (box #f))

(: node2 : Node)
(define node2 (box #f))

(: node3 : Node)
(define node3 (box #f))

(set-next! node1 node2)
(set-next! node2 node3)
(set-next! node3 node1)

(3) Give a definition for set-next!. Why can't straight set-box! be used here?

(4) Draw a diagram of the defined data structure, indicated node1, node2, and node3.

Box based environments.

• (1) Consider the following definitions for FLANG values and environments

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

  (define-type ENV
    [EmptyEnv]
    [Extend Symbol (Boxof VAL) ENV])

Given the following FLANG+rec code, draw a diagram of the value of fact (as a FunV)

{rec {fact {fun {n} {if n 
                        {* n {call fact {- n 1}}}
                        1}}}
                {call fact 5}}
                

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)

#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 preceeding 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 evironment based evaluation.

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

The midterm will be held in class, March 15. The test will be closed book, and cover material presented in lectures up to March 2.

There are some sample questions, and more sample questions.

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. What is the connection between name capture and dynamic vs. static scope?

de Bruijn Indices

Convert the following WAE expression to deBruijn form.

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

Implementing First Class Functions

• Consider the following part of of FLANG evaluator we discussed in class. Based only on this code would you conclude the evaluator was eager, lazy, or you can't tell? Explain your answer.

[(Call fun-expr arg-expr)
 (let ([fval (eval fun-expr)])
   (cases fval
      [(Fun bound-id bound-body)
       (eval (subst bound-body
            bound-id
            (eval arg-expr)))]
      [else (error 'eval "not a function: ~s"
               fval)]))]

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)

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

Defining BNF

Consider the subset of Racket consisting of define, +,-,*, and numbers. Give a BNF for this language, including defining functions. You maybe assume terminals exist for numbers and identifiers.

Using BNF

Use your grammar to (almost) derive the following expression

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

What part of the expression is not covered by your grammar?

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

Evaluation Rules

1. Thinking back to the assignment question on converting lists of 0 and 1 into a number (with the digits ordered from the least to the most significant). Write a set of 'eval' rules for this "language".

2. Write the corresponding Racket function. Mimic your eval rules as closely as possible.

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.

• Suppose we want to support binding more than one variable in a with form, and we want earlier bindings to be usable in later ones. For example, the following form evaluates to 3.

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

1. . Give a translation of this syntax of this into standard WAE. For part credit, translate the given example.

2. . Give eval rules to evaluate such with forms directly.

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] 
    [ 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 compute the area of a Shape. Make sure you give a valid type declaration for the function.

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