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.
Our first task is to add a print statement and a sequence operator to our language with
bind. Here is the new abstract syntax:
There are two new operations,
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:
(Num 0). You may use the Haskell
Print t is:
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).
evals :: BBAE -> (Either String BBAE)that uses
substto handle replacement of identifiers with their values. Integrate
evalswith a BBAE parser to define
interps :: String -> (Either String BBAE).
eval :: Env -> BBAE -> (Either String BBAE)that uses an environment to implement replacement of identifiers with their values. Integrate
evalwith a BBAE parser to define
interp :: String -> (Either String BBAE).
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:
firsttakes a list and returns the first element
resttakes a list and returns everything but the first element
constakes an element and adds it to a list
emptythe empty list
isEmptytakes a list and returns
trueif it is empty and
Here are some examples using our new list functions:
first (cons 1 empty) = 1
rest (cons 1 (cons 2 empty)) = cons 2 empty
isEmpty empty = true
isEmpty cons 1 empty = false
Our new language will be called BBAEL (BBAE with Lists) and will add these AST definitions to BBAE:
eval :: Env -> BBAEL -> (Either String BBAEL)that evaluates a BBAEL construct using an environment. Do not implement an interpreter that uses
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
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
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
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.