Problem Set 2
Home Syllabus Lecture Slides Learning Haskell Problem Set 1 Problem Set 2 Problem Set 3 Problem Set 4 Problem Set 5 Problem Set 6 Problem Set 7 Problem Set 8 Problem Set 9

 

Due on Friday, September 30, 5pm.

The Simple Imperative Language

  1. Complete this denotational semantics of SIL in Haskell, in which I have provided the syntax, and you must fill in the semantics.  To make the syntax look as much like Reynolds as possible, note that I used "fixity" declarations to the get precedence and associativity right.  To make the semantics look as much like Reynolds as possible, you should use the following ideas:
     
    bulletThe fixpoint operator Y can be defined as:
     
        y :: (a -> a) -> a
        y f = f (y f)
     
    bulletEvery domain is automatically lifted in Haskell, meaning that each of them already has a bottom
    element.  Furthermore, all Haskell functions are continuous, but are not (necessarily) strict.
    Therefore the extension of a function
    f to a function f subscripted with the "double bottom" symbol,
    amounts to simply making the Haskell function strict.  This is easily done by the predefined Haskell
    function
    ($!), which behaves as follows:
     
        f $! _|_ = _|_
        f $!  e  = f e, if e /= _|_
     
    This is not valid Haskell code, but shows how ($!) behaves semantically.
     
    bulletEquations such as this:
     
                  / a, if p1
        [[ e ]] = | b, if p2
                  \ c, if p3
     
    where p1, p2, and p3 are arbitrary predicates, can be written as:
     
        meaning e | p1 = a
        meaning e | p2 = b
        meaning e | p3 = c
     
  2. Do problem 2.1 in Reynolds.  Also add the "double assignment" construct to your interpreter above, with test cases.
     
  3. Do Exercise 2.4 in Reynolds.
     
  4. Do Exercise 2.6 in Reynolds.

 

Solution.