EECS 662

Programming Languages


Project 2 - Booleans, Identifiers, and Lists

Mini Project 2 - Booleans and Identifiers
EECS 662 - Programming Languages

The objective of this mini-project is to add Booleans, print and sequence, and untyped lists to our existing language.

Exercise 1 - Adding Booleans

Our first task is to add a print statement and a sequence operator to our language with bind. Here is the new abstract syntax:

data BBAE where
  Num :: Int -> BBAE
  Plus :: BBAE -> BBAE -> BBAE
  Minus :: BBAE -> BBAE -> BBAE
  Bind :: String -> BBAE -> BBAE -> BBAE
  Id :: String -> BBAE
  Boolean :: Bool -> BBAE
  And :: BBAE -> BBAE -> BBAE
  Leq :: BBAE -> BBAE -> BBAE
  IsZero :: BBAE -> BBAE
  If :: BBAE -> BBAE -> BBAE -> BBAE
  Seq :: BBAE -> BBAE -> BBAE
  Print :: BBAE -> BBAE
  deriving (Show,Eq)

There are two new operations, Seq and Print required for this exercise. Together, Print and Seq allow printing things to the screen during execution rather than simply dumping a value at the end. Seq takes two BBAE expressions, evaluates the first, evaluates the second, and returns the result of evaluating the second. The result of evaluating the first BBAE expression is effectively ignored. This operation is called a sequence and is at the heart of imperative languages like Java and C. The concrete syntax for Seq t1 t2 is:

seq t1 t2

Print takes one BBAE, evaluates it, prints the result of evaluation, and returns (Num 0). You may use the Haskell print function or any other printing routine to implement Print in BBAE. Do not try to do anything fancy. Just print the AST to the screen. The concrete syntax for Print t is:

print t

Please start with the interpreter provided in the Adding Booleans Redux section of our text for these exercises. Note that the interpreter provided in the book returns an BBAE and this exercise requires (Either String BBAE).

  1. Define an evaluation function, evals :: BBAE -> (Either String BBAE) that uses substto handle replacement of identifiers with their values. Integrate evals with a BBAE parser to define interps :: String -> (Either String BBAE).
  2. Define an evaluation function, eval :: Env -> BBAE -> (Either String BBAE) that uses an environment to implement replacement of identifiers with their values. Integrate eval with a BBAE parser to define interp :: String -> (Either String BBAE).

Exercise 2 - Adding Lists

As of now the only data types available in BBAE are numbers and Booleans. Let’s extend the language to add untyped listed like Scheme or Lisp. Do do this, we’ll add the following language constructs to the original BBAE syntax above:

Here are some examples using our new list functions:

Our new language will be called BBAEL (BBAE with Lists) and will add these AST definitions to BBAE:

  First :: BBAE -> BBAE
  Rest :: BBAE -> BBAE
  Cons :: BBAE -> BBAE -> BBAE
  Empty :: BBAE
  IsEmpty :: BBAE -> BBAE
  1. Define an evaluation function, eval :: Env -> BBAEL -> (Either String BBAEL) that evaluates a BBAEL construct using an environment. Do not implement an interpreter that uses subst.

I’m going to give you a friendly hint. Do not try to use Haskell’s built in list type to represent lists in your interpreter. (Why would that be?)

You need not implement a parser for this exercise unless you feel it would be fun to do. It’s not hard, but it is busywork we don’t need right now.


Start with the BBAE eval and subst functions can be found in our text. You will need to update both for Exercise 1.

proj2Utils contains a parser and AST data structure that will work for both Exercise 1 and Exercise 2.

The easiest way to complete Exercise 2 is to start from your Exercise 1 result. However, the functions in Exercise 2 do not depend on Exercise 1. If you have difficulties with Exercise 1 it will not impact your ability to complete Exercise 2.

I have implemented this project both with and without using Either as a monad. The monadic version is a bit shorter, but not dramatically so. You should have no difficulties if you choose to use case or let rather than the do notation. Having said that, this might be a good project to try using Either as a monad for the first time. You are not required to do so.

Exercise 2 may seem like an odd way to implement lists, but it is exactly what Haskell and Scheme both do. cons effectively creates a pair while first and rest return the first and second values from the pair respectively. If the second element of the pair is another pair, you are creating a structure with three elements. If the second element of the second element is a pair, you’re creating a structure with four elements. The use of Empty is a special construction that has no elements.

To give you an idea of the effort required for this mini-project, my code is about 200 lines long and took me roughly an hour to write and debug starting from the examples provided in the text. This is the most challenging project so far this semester. Do not put it off and please ask questions in class.