Assignment 5: Type Classes (255 points)

Overview

The overall objective of this assignment is to get some experience with different type-classes, in particular to learn about:

• Property-based testing, and
• Monads.

by modifying and extending your nano-interpreter.

The assignment is in the files:

• BST.hs
• Eval.hs
• Repl.hs
• Main.hs
• tests/Test.hs

As before Test.hs has some sample tests, and testing code that you will use to check your assignments before submitting.

You should only need to modify the parts of the files which say:

error "TBD: ..."

with suitable Haskell implementations.

Assignment Testing and Evaluation

All of the points, will be awarded automatically, by evaluating your functions against a given test suite.

Tests.hs contains a very small suite of tests which gives you a flavor of of these tests. When you run

$ make test

Your last lines should have

All N tests passed (...)
OVERALL SCORE = ... / ...

or

K out of N tests failed
OVERALL SCORE = ... / ...

If your output does not have one of the above your code will receive a zero

If for some problem, you cannot get the code to compile, leave it as is with the error ... with your partial solution enclosed below as a comment.

The other lines will give you a readout for each test. You are encouraged to try to understand the testing code, but you will not be graded on this.

Submission Instructions

Submit your code via the HW-5 assignment on Gradescope. Connect your Github account to Gradescope and select your repo. If you're in a group, don't forget to add your partner to the submission!

Detailed instructions on how to submit your code directly from the Git repo can be found on Piazza.

Problem 1: Sets via Binary Search Trees

For this problem, you will use Haskell's data types to implement an Abstract Set datatype that implements the following API:

-- | The Set data type
data Set a

-- | `contains x ys` returns `True` if and only if `x` is a member of the set `ys`
contains :: (Ord a) => a -> Set a -> Bool

-- | `add x xs` returns the (new) set obtained by inserting `x` into the set `xs`
add :: (Ord a) => a -> Set a -> Set a

-- | `remove x xs` returns the (new) set obtained by deleting `x` from the set `xs`
remove :: (Ord a) => a -> Set a -> Set a

Data Type

The sets will be represented as Binary Search Trees that support efficient addition and removal of elements. We represent the datatype as:

data BST a
  = Leaf                      -- ^ empty tree
  | Node a (BST a) (BST a)    -- ^ node with left and right subtrees
  deriving (Show)

Thus, values of type BST a are of the form

• Leaf or
• Node e l r where e is an element of type a and l and r are left and right subtrees of type BST a.

The isOrdered Invariant

We will only use trees that are Binary-Search Ordered, which is to say, where the element in each node is greater than any element in the left subtree and smaller than any element in the right subtree. We have provided a Boolean function isOrdered t that evaluates to True iff t is binary-search ordered. Make sure you understand what the isOrdered function is doing!

(10 points): Build

Fill in the definition of build that converts the input [a] into a BST a by recursively splitting the list into sub-lists, similarly to QuickSort converting the sub-lists to trees. Make sure that the resulting BST a is binary-search-ordered. When you are done you should get the following behavior:

λ> build [5,10,20,30]
Node 5 Leaf (Node 10 Leaf (Node 20 Leaf (Node 30 Leaf Leaf)))

λ> build [20,10,30,5]
Node 20 (Node 10 (Node 5 Leaf Leaf) Leaf) (Node 30 Leaf Leaf)

Property-based testing

Writing tests by hand is tedious! Instead we will write a property called prop_build that checks that a tree generated with build is ordered. A property is just a Boolean function:

prop_build :: [Int] -> Bool
prop_build xs = isOrdered (build xs)

Now we will use a property-based testing tool called QuickCheck to test our property on a bunch of random inputs:

λ> quickCheck prop_build
+++ OK, passed 100 tests.

Make sure that you get this result. Otherwise, debug your build function.

(10 points): Contains

Next, fill in the definition of the function

contains :: (Ord a) => a -> BST a -> Bool

so that contains x t evaluates to True iff the element x is in the tree t. When you are done, you should see the following behavior:

λ> t2
Node 5 Leaf (Node 20 (Node 10 Leaf Leaf) (Node 30 Leaf Leaf))

λ> [ contains x t2 | x <- [5,6,10,11,20,21,30,31] ]
[True,False,True,False,True,False,True,False]

The property prop_contains_elt states that a tree built from a list xs contains any x that is in xs:

λ> quickCheck prop_contains_elt
+++ OK, passed 100 tests.

(15 points): Fold

Now, write a fold function that performs an in-order traversal of the tree.

fold :: (b -> a -> b) -> b -> BST a -> b

Why is there no Ord in the type for fold?

By in-order we mean that fold (+) 0 t would execute in the folloiwng order:

-- Tree `t` looks like this:
--   5
--  / \
-- 1   20
--    /  \
--   10  30

-- `fold (+) 0 t` executes like this:
((((0 + 1) + 5) + 10) + 20) + 30

When you are done, various bonus properties get unlocked thanks to the toList function that we have supplied that uses fold. In particular, you should get the following behavior:

λ> toList t2
[5,10,20,30]

λ> toString t2
"build [5,10,20,30]"

You should also check the property that the trees you build actually contain all the elements from the source list.

λ> quickCheck prop_contains_elts
+++ OK, passed 100 tests.

(15 points): Add

Next, fill in the definition for

add :: (Ord a) => a -> BST a -> BST a

such that add x t returns a (new) BST which has the same elements as t plus the new element x. Of course, the new tree should satisfy the binary-search-ordering invariant.

When you are done, you should see the following behavior

λ> t2
Node 5 Leaf (Node 20 (Node 10 Leaf Leaf) (Node 30 Leaf Leaf))

λ> add 12 t2
Node 5 Leaf (Node 20 (Node 10 Leaf (Node 12 Leaf Leaf)) (Node 30 Leaf Leaf))

λ> let tnew = add 12 t2

λ> isOrdered tnew
True

λ> contains 12 tnew
True

Lets also check the property that the new set if ordered and the added elements are indeed in the new set. (Make sure you understand the properties!)

λ> quickCheck prop_add_elt
+++ OK, passed 100 tests.

λ> quickCheck prop_add_elts_old
+++ OK, passed 100 tests.

λ> quickCheck prop_add_isOrd
+++ OK, passed 100 tests.

(5 points): Debug the Property

We’ve seen a bunch of properties go sailing through. But consider this:

λ> quickCheck prop_multiset
*** Failed! Falsifiable (after 6 tests):
[1,1]

Uh oh. Lets try to debug the code and property to see why the test fails.

Of course, your failing input may be slightly different, because QuickCheck finds them by random sampling. Well, lets see why the property failed, by running the test on the failing input that QuickCheck has automatically found for us!

Lets run the property on the failing input. How? Well the property is just a function

prop_multiset :: [Int] -> Bool
prop_multiset xs = toList (build xs) == L.sort xs

so you can run it, by calling that function with the failing input:

λ> prop_multiset [1,1]
False

The property says for any list xs the result of building a BST from xs and converting it to a list, should be identical to just sorting the list xs.

Lets see if that equality really is true, for the particular xs that we have above. The left hand side is:

λ> toList (build [1,1])
[1]

and the right hand side is:

λ> :m +Data.List
λ> sort [1,1]
[1,1]

whoops! The BST does not keep duplicates (no duplicates on the LHS), but vanilla sorting does keep duplicates! So the property is broken, we want to check only that the BST has all the elements from xs but excluding any duplicates.

Fix the property so that it passes. Do this in a meaningful way -- don’t just replace it with True.

Note: Use the above strategy to fix your code when there are other failing tests too.

(10 points): Remove Minimum

We also want to remove elements from the set. As a first step, write a function

removeMin :: (Ord a) => BST a -> (a, BST a)

that returns a tuple of the minimum element in the tree, and the tree containing all elements except the minimum. When you are done you should see this behavior

λ> removeMin t2
(5,Node 20 (Node 10 Leaf Leaf) (Node 30 Leaf Leaf))

λ> quickCheck prop_remove_min
+++ OK, passed 100 tests.

removeMin should throw an error if given an empty tree.

(20 points): Remove

Finally, use removeMin to fill in the definition of

remove :: (Ord a) => a -> BST a -> BST a

such that remove x t returns the tree containing all elements except x. Of course, the new set should satisfy the binary-search-ordering property.

remove x t should return t unchanged if x is not in t.

When you are done, you should see the following behavior.

λ> remove 12 t2
Node 5 Leaf (Node 20 (Node 10 Leaf Leaf) (Node 30 Leaf Leaf))

λ> remove 20 t2
Node 5 Leaf (Node 30 (Node 10 Leaf Leaf) Leaf)

λ> quickCheck prop_remove
+++ OK, passed 100 tests.

λ> quickCheck prop_remove_old
+++ OK, passed 100 tests.

λ> quickCheck prop_remove_isOrd
+++ OK, passed 100 tests.

Problem 2: Exceptions

Next, we will add exceptions to the nano language, in several steps.

Exceptional Expressions

We have extended the representation of Expressions by adding two new constructs:

data Expr
  = ...
  | EThr Expr           -- ^ throw e
  | ETry Expr Id Expr   -- ^ try e1 catch z => e2

Exceptional Values

We will represent the result of evaluation via the type:

data Either a b = Left a | Right b

The key idea is that when we evaluate an expression e we get:

1. Left exn when e "throws" an (uncaught) exception;
2. Right val when e "finishes" normally, without an exception.

To do so, note that the top-level eval function is defined as:

eval :: Env -> Expr -> Value
eval env e = case evalE env e of
  Left exn  -> exn
  Right val -> val

The helper function evalE has the type:

evalE :: Env -> Expr -> Either Value Value

Note: You should not change your type errors from HW4, those should still be throwing a type error with the throw method. This new mechanism only occurs when an expression explicitly has an EThr.

(55 points): Copy and Update

First, we'll copy and update your old code from HW4 into HW5.

• Lexer.x can be copied entirely.
• For Parser.y, only copy the parts you wrote (Expr and any other nonterminals you added) - some of the other starter code has changed.
  • Most notably, this homework has new definitions for Top and Def - do not replace them with the HW4 definitions.
• For Eval.hs, copy evalOp, lookupId, and prelude, and adapt your eval implementation to become the first 10 cases of evalE.

evalE :: Env -> Expr -> Either Value Value
evalE env (EInt i)                = error "TBD"
evalE env (EBool b)               = error "TBD"
evalE env (EVar x)                = error "TBD"
evalE env (EBin o e1 e2)          = error "TBD"
evalE env (EIf c t e)             = error "TBD"
evalE env (ELet f (ELam x e1) e2) = error "TBD"
evalE env (ELet x e1 e2)          = error "TBD"
evalE env (EApp e1 e2)            = error "TBD"
evalE env (ELam x e)              = error "TBD"
evalE env ENil                    = error "TBD"

When you are done, your old tests should pass, that is the command

$ stack test --test-arguments "-p Eval" --allow-different-user
...
OVERALL SCORE = 55 / 55

(30 points): Throw

Next, complete the implementation of

evalE env (EThr e)       = error "TBD"

When you are done, you should see the following behavior:

λ> eval [] (EBin Plus (EInt 1) (EInt 2))
3
λ> eval [] (EBin Plus (EThr (EInt 1)) (EInt 2))
1
λ> eval [] (EBin Plus (EInt 1) (EThr (EInt 2)))
2
λ> eval [] (EBin Plus (EThr (EInt 1)) (EThr (EInt 2)))
1
λ> eval [] (EThr (EBin Plus (EInt 1) (EInt 2)))
3
λ> eval [] (EThr (EBin Plus (EInt 1) (EThr (EInt 2))))
2

Implementing the EThr case itself is not difficult, the challenge is to update the old cases so that an exception is always propagated through the evaluator (e.g. so that the second test case above returns 1 and not 3). Remember that Either is a monad, and use monad operations (not case expressions!) to implement this.

(30 points): Catch

Finally, complete the implementation of

evalE env (ETry e1 x e2) = error "TBD"

when you are done, you should see the following behavior:

λ> let tryZ e = ETry e "z" (EBin Plus (EVar "z") (EInt 10))

λ> eval [] (tryZ (EBin Plus (EInt 1) (EInt 2)))
3
λ> eval [] (tryZ (EBin Plus (EThr (EInt 1)) (EInt 2)))
11
λ> eval [] (tryZ (EBin Plus (EInt 1) (EThr (EInt 2))))
12
λ> eval [] (tryZ (EBin Plus (EThr (EInt 1)) (EThr (EInt 2))))
11
λ> eval [] (tryZ (EThr (EBin Plus (EInt 1) (EInt 2))))
13
λ> eval [] (tryZ (EThr (EBin Plus (EInt 1) (EThr (EInt 2)))))
12

Problem 3: Nano REPL

For this problem, you will get some experience building a standalone "app" in Haskell, by implementing a "shell" for nano, that will let you:

• quit :-)
• run a file,
• eval an expression passed in as a String
• load a file and then evaluate expressions that can refer to the top-level definitions of the file.

This time, we're giving you almost no scaffolding. Your task is simply to implement the code in src/Main.hs, specifically, to fill in the implementation of the function

main :: IO ()
main = error "TBD:main"

which is the top-level IO recipe that Haskell runs as an "app".

However, there are lots of very useful functions in Repl.hs that we suggest you understand (and complete the implementation of where necessary.)

We've also provided the hex representation of the "λ" character as the String lambda in Main.hs. If you are running into issues with the "λ", please make sure you have not modified the line setLocaleEncoding utf8 from the starter code - this must be the first line that runs in main. If you are still having issues, you can use "\" instead of the lambda.

(5 points): Quit

First, hook up your shell so that it starts up thus:

$ make repl
...
------------------------------------------------------------
-------- The NANO Interpreter v.0.0.0.0 --------------------
------------------------------------------------------------

λ [0]

The [0] is a "prompt" at which the user can type a command.

Specifically, if the user types :quit then the shell should exit!

------------------------------------------------------------
-------- The NANO Interpreter v.0.0.0.0 --------------------
------------------------------------------------------------

λ [0] :quit
Goodbye.

HINT: The function doQuit may be useful.

(15 points): Evaluating Expressions

Next, extend your REPL so that the user can (repeatedly) enter expressions that then get parsed and evaluated, with the results printed back.

Don't worry about parsing throw and try-catch -- just the older constructs.

When you are done you should see the following behavior:

polikarn@lena ~/t/1/a/05-classes (master)> make repl
...
------------------------------------------------------------
-------- The NANO Interpreter v.0.0.0.0 --------------------
------------------------------------------------------------

λ [0] 2 + 3
5
λ [1] let x = 2 in x + 3
5
λ [2] let add x y = x + y in ((add 10) 20)
30
λ [3] quit
unbound variable: quit
λ [4] :quit
Goodbye.

HINT: The function doEval may be useful.

(10 points): Running Files

Next, extend your REPL so that you can run a particular file, that is,

• read the file,
• parse its contents into an Expr
• evaluate the expr to get a Value.

When you are done, you should see the following behavior

$ make repl
...
------------------------------------------------------------
-------- The NANO Interpreter v.0.0.0.0 --------------------
------------------------------------------------------------

λ [0] :run tests/input/t1.hs
45
λ [1] :run tests/input/t2.hs
0
λ [2] :run tests/input/t3.hs
2
λ [3] :quit
Goodbye.

HINT: The function doRun may be useful.

(25 points): Loading Files

Finally, extend the REPL so that you can load a file's definitions into the environment, and then write expressions that refer to those expressions. For example, consider the file: tests/input/tAdd.hs which has two definitions:

add =
  let add1 x y = x + y in
      add1
,

sub = 
  let sub1 x y = add x (0 - y) in
      sub1

You should be able to do:

$ make repl
...
------------------------------------------------------------
-------- The NANO Interpreter v.0.0.0.0 --------------------
------------------------------------------------------------

λ [0] :load tests/input/tAdd.hs
definitions: tail head add sub
λ [1] ((sub ((add 10) 20)) 5)
25
λ [2] :quit
Goodbye.

That is, typing :load tests/input/tAdd.hs adds the definitions for add and sub into the top-level environment (which already had tail and head).

As with "evaluating expressions" you can then enter the expression

((sub ((add 10) 20)) 5)

which should get evaluated and the result 25 is printed out.

You can assume that each load wipes out all previous definitions, except those in prelude.

HINT: The function doLoad may be useful, but to use it you will have to **complete the implementation of defsEnv.