The following questions refer to the MFAE language discussed in class

Here is a BNF , (restricting to single argument functions).

<MFAE> ::=
    <num> |
    true |
    false |
    {+ <MFAE> <MFAE>} |
    {- <MFAE> <MFAE>} |
    {= <MFAE> <MFAE>} |
    <id> |
    {fun {<id>} <MFAE>} |
    {<MFAE> <MFAE>} |
    {if <MFAE> <MFAE> <MFAE>}

Here are the type inference rules

  Γ  ⊢ <num> : num
  Γ  ⊢ true : bool
  Γ  ⊢ false : bool

  Γ ⊢ <MFAE>₁ : num   Γ ⊢ <MFAE>₂ : num
  -------------------------------------
  Γ  ⊢ {+ <MFAE>₁ <MFAE>₂} : num

  Γ ⊢ <MFAE>₁ : bool    Γ ⊢ <MFAE>₂ : <type>₀    Γ ⊢ <MFAE>₃ : <type>₀
  --------------------------------------------------------------------
  Γ ⊢ {if <MFAE>₁ <MFAE>₂ <MFAE>₃} : <type>₀
   
   
  [ ... <id>←τ₁, ...] ⊢ <id>:τ₁    Γ[ <id>←τ₁ ] ⊢ e : τ₀
  ------------------------------------------------------
  Γ ⊢ {fun {<id> : τ₁} e} : (τ₁ → τ₂)

  Γ ⊢ e₁ : (τ₂ → τ₃)    Γ ⊢ e₂ : τ₂
  ---------------------------------
  Γ ⊢ {e₁ e₂} : τ₂

Defining inference rules I

Consider adding a begin form

{begin <MFAE> <MFAE*>}

This form evaluates all of the expressions and returns the last.

Ignoring the fact that this from is useless in a language without side-effects:

1. Give a type inference rule for this form.
2. Explain why allowing empty {begin} forms would complicate the type system.

Defining inference rules II

Consider adding a with form

{with {<id> <MFAE>} <MFAE>}

1. Give a type inference rule for this form.

2. Explain the effects, if any, of changing the binding semantics so that is bound in body (what we called rec), i.e. does this change the type inference rule?

Doing type inference

Use the type inference rules above to construct a proof for the type of

 {fun {x}
   {fun {y}
    {fun {f}
        {if {y} 
          0
          {+ x {f x}}}}}}

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

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

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

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)

(: d  : UnaryFun UnaryFun -> UnaryFun)

With and Call

Write an eval rule for the FLANG with

    {with {<id> <named-expr>} <body>}

that reduces it to eval of an FLANG expression using call and fun without doing substitution.

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)

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.

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