Module 12 Project
In this PA you will implement some analysis routines over a data structure called an expression tree. You will implement similar projects in Ruby, Haskell, and Prolog, and the goal is to explore the differences between the three languages.
In Ruby, you will extend existing Ruby classes to practice dynamic object-oriented programming. In Haskell, you will write pattern-matching routines to practice functional programming. In Prolog, you will write rules to practice logical programming.
Project starter files:
You may ignore
Parser.hs. They were auto-generated from grammar
specification files using utilities called Alex
and Happy, and they provide the backend code
for parsing simple mathematical expressions. Here is a context-free grammar
describing the language that this parser can recognize:
E -> <int> | E + E | E - E | E * E | ( E )
You may also ignore the definition of
Defs.hs, although you will
need to use the definition of the
Expr data type:
data Expr = EInt Int | EAdd Expr Expr | ESub Expr Expr | EMul Expr Expr deriving (Show,Eq)
This data type represents nodes in the expression parse tree. For instance, the
(2+3)*4 will be parsed into the following tree:
EMul are all data value constructors, used to
build or pattern match against an expression tree.
EInt represents an integer
terminal node, while the other three represent non-terminal arithmetic operation
nodes. The last line of the
Expr definition specifies that we wish to be able
to convert the expressions to strings and compare them using Haskell built-in
Using these value constructors, we could represent the parse tree shown above with the following Haskell expression:
EMul (EAdd (EInt 2) (EInt 3)) (EInt 4)
Your task in this PA will be to write various functions to analyze expression trees. You will do this by writing functions that recurse over an expression tree based on data patterns.
You can see an example of a pattern-based function in
This function takes a tree and matches it against one of the four different
patterns possible using the value constructors, returning a different form of
string for each different pattern.
Most of the functions you write for this PA will have this general form. The function’s input will be an expression tree, and you will specify the output of the function for each pattern that the input could be matched against. You will likely want to make recursive calls in the non-terminal cases.
Below are descriptions of the functions you need to implement. You can also look
at the test cases (in
Test.hs) to see what they are supposed to do. You should
think about what the definition of each function means for each
Unlike in the Ruby implementation, there are no “abstract” classes and so you
will need to write patterns for each value constructor.
eval :: Expr -> Int- Calculates the result of evaluating the mathematical expression. All operations should be done using integer arithmetic.
countOps :: Expr -> Int- Counts the total number of arithmetic operations in an expression. All three operations (addition, subtraction, and multiplication) count for this process.
height :: Expr -> Int- Calculates the height of the expression tree, where the height of a single-node tree is defined as being 1.
postfix :: Expr -> String- Returns a flattened postfix string representation. For example,
(2+3)*4in postfix notation would be
"2 3 + 4 *". You should use the
showfunction to convert integers to strings.
uniqInts :: Expr -> [Int]- Extract a sorted list of all unique integers in an expression. Each integer should appear in the resulting list only once.
For the last function (
uniqInts), you may find it helpful to
write two helper functions:
uniq :: Eq t => [t] -> [t]- Returns a copy of the given list with duplicates removed.
sort :: Ord t => [t] -> [t]- Returns a sorted copy of the given list.
Alternatively, you could adapt the
quicksort function you wrote in this week’s
Some test routines are included in
Test.hs. However, your submission will be
graded based on additional tests not provided to you, so you should write your
own test cases as well. You can also test your routines via the provided REPL
(read/eval/print loop) by running
For this assignment, you may NOT use any classes or methods that are not in the Haskell Prelude. If you are unsure about a particular class or method, you can consult the documentation.
Your program must contain implementations as described above. You must name your
Haskell script file
P4.hs. You must put your name in a comment at the top of
the file. As usual, decompose your methods to make them more readable, use good
names, indent properly, and so on. You will partly be graded on the readability
of your code but mostly on whether it works.
P4.hs to the appropriate assignment on Canvas by the deadline.