COMPSCI 220 Programming Methodology

Project Assignment 04: Boolean Expression Evaluation

Overview

The goal of this assignment is to better understand scala pattern matching and functional evaluation of expressions by implementing a boolean expression language and an evaluation function that will evaluate your boolean expression representation. In addition, this assignment will futher solidify your understanding of scala traits and how they are implemented as well as exercise your understanding of pattern matching over case classes.

In particular, you will implement a set of case classes that represent boolean expressions such as true, false, &&, ||, !, and if. From your implementation you will be able to construct arbitrary boolean expressions from these building blocks. For example, using your case classes you will be able to create a data structure that represents this boolean expression exp:

if (!true) then true && false else true

In addition, you will be able to evaluate exp by implementing an evaluation function that will interpret your boolean expression to produce a final false or true value:

eval(exp) == true

Your evaluation function will be based on a small set of rules that you will use to properly evaluate your boolean expressions.

Learning Goals

To understand and apply case classes/objects.
To understand and apply pattern matching.
To understand and apply expression evaluation.
To understand and apply traits.
To learn, understand, and apply s-expressions.

General Information

Read this entire document. If, after a careful reading, something seems ambiguous or unclear to you, then communicate to the course staff immediately. Start this assignment as soon as possible. Do not wait until 5pm the night before the assignment is due to tell us you don’t understand something, as our ability to help you will be minimal.

Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty. Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what constitutes academic dishonesty you should re-read the course syllabus and policies. We assume you have read the course information in detail and by submitting this assignment you have provided your virtual signature in agreement with these policies.

You are responsible for submitting project assignments that compile and are configured correctly. If your project submission does not follow these policies exactly you may receive a grade of zero for this assignment.

Policies:

For many assignments, it will be useful for you to write additional Scala files. Any Scala file you write that is used by your solution MUST be in the provided src/main directory you submit to Moodle.
The course staff are here to help you figure out errors (not solve them for you), but we won’t do so for you after you submit your solution. When you submit your solution, be sure to remove all compilation errors from your project. Any compilation errors in your project will cause the auto-grader to fail your assignment, and you will receive a zero for your submission. No Exceptions!

Test Files

In the src/test/scala directory, we provide ScalaTest test suites that will help you keep on track while completing the assignment. We recommend you run the tests often and use them to help create a checklist of things to do next. But, you should be aware that we deliberately do not provide you the full test suite we use when grading.

We recommend that you think about possible cases and add new test cases to these files as part of your programming discipline. Simple tests to add will consider questions such as:

Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero? Many methods only accept arguments that are in a particular range.
Does your code handle unusual cases, such as empty or maximally-sized data structures?

More complex tests will be assignment-specific. To build good test cases, think about ways to exercise functions and methods. Work out the correct result for a call of a method with a given set of parameters by hand, then add it as a test case. Note that we will not be looking at your test cases (unless otherwise specified by the assignment documentation), they are just for your use and will be removed by the auto-grader during the evaluation process.

If you modify the test cases we provided or you added your own it is important to know that they will not be used. The auto-grader will use its own copy of the public and private tests. If you modify any source files in the src/test/scala directory your changes will not be reflected in the grading of your submission.

Before submitting, make sure that your program compiles with and passes all of the original tests. If you have errors in these files, it means the structure of the files found in the src directory have been altered in a way that will cause your submission to lose some (or all) points.

Project Structure

The project should normally contain the following root items:

src/main/scala: This is the source folder where all code you are submitting must go. You can change anything you want in this folder (unless otherwise specified in the problem description and in the code we provide), you can add new files, etc.
src/instructor/scala: This folder contains support code that we encourage you to use (and must be used to pass certain tests). You must not change or add anything in this folder. The auto-grader will replace your submitted src/instructor directory with the original during the evaluation process. If you make changes or add/remove anything it can lead to problems in your submission and will result in a 0 for the assignment.
src/test/scala: The test folder where all of the public unit tests are available.
tools/grading-assistant.jar: This is the grading assistant that you can run to give you an estimate of your score as well as package your project to be submitted to Moodle. More on this later. Do not remove.
activator: This is a Unix helper script that can be used to run the activator interactive build tool. You can use this on Linux and Mac OSX. Do not remove.
activator.bat: This is a Windows helper script that can be used to run the activator interactive build tool. You can use this on Windows. Do not remove.
activator-launch-1.3.2.jar: This is a Scala/Java library that runs the activator tool and is used by the previously mentioned scripts. Do not remove.
build.sbt: This is the build definition file. It provides build information to activator to build your project. Do not remove.
.gitignore: This is a special file used by git source control to ignore certain files. You should not touch this file and please do not remove. This file may not be present if the assignment does not call for git usage.

Testing, Grading Assistant, and Console

As mentioned previously, you are provided a set of unit tests that will test various aspects of your implementation. You should get in the habit of running the tests frequently to see how you are doing and to understand where you might be going wrong. The ScalaTest testing framework is built-in to the activator tool and you can easily run the tests by issuing the following command from the command line (Mac/Linux):

./activator test

For Windows users you would issue the following command from the command window:

activator.bat test

This will compile your code and run the public ScalaTest unit tests. After you compile and run the tests you will notice that a target directory has been created. The target directory contains the generated class files from your source code as well as information and results of the tests. Activator uses this directory so it must not be removed. After you run the tests you can get a grade report from the Jeeves tool by issuing this command from the command line (Mac/Linux):

scala -cp tools/grading-assistant.jar autograder.jeeves.Jeeves

For Windows users you would issue the following command from the command window:

scala -cp tools\grading-assistant.jar autograder.jeeves.Jeeves

Note, issuing the above command from the activator console will not work! This will print a report to the console showing you the tests you passed, tests you failed, and a score based on the public tests. Although this gives you a good estimate as to what your final score might look like, it does not include points from our private tests. You may run Jeeves as often as you like, however, you must run the tests before your run Jeeves to give you an updated result.

Another very useful approach to test and play with the code you write is the activator/Scala console. You can run the console with this command (Mac/Linux):

./activator console

For Windows users you would issue the following command from the command window:

activator.bat console

This will load up the Scala REPL (read-eval-print-loop). You can type code directly into the console and have it executed. If you want to cut and paste a larger segment of code (e.g., function declaration) you simply type :paste in the console, then paste in your code, then type control-D.

In addition, you can run activator without any commands and you will be presented with the following prompt:

./activator
>

Or on Windows:

activator.bat
>

From the activator prompt you can type in any of the following commands:

compile: this will compile your code
~compile: this will watch your files for changes and compile them when a change is detected.
test: this will compile your code, the test code, and run the tests
console: runs the scala console.

Editors and IDEs

You are welcome to use any editor or IDE you choose. We recommend using a basic text editor such as Atom, SublimeText, Notepad++, emacs, or vim.

If you use a text editor you should use activator in a separate terminal window to compile, run, and test your code.

If you have successfully installed and imported your project into IntelliJ you are welcome to continue using it.

Part 1: Understand The Code

Before you start implementing any part of this project you should become familiar with what you are provided. In particular, we give you two files in the src/instructor/scala/sexpr directory. You should read and explore these files to understand what you are working with.

sexpr.SExprLanguage: This file defines the SExprLanguage trait. This trait implements the s-expression language. The s-expression language, or sexpr for short, is a simple language of lists and symbols. It was, and still is, the syntax used for languages such as lisp, scheme, and more modern dialects such as clojure. Although we are not using sexprs to implement a language such as lisp, we are using it in this assignment to represent boolean expressions.

This trait defines sexprs as either a symbol or a list of sexprs. It also defines a few helper functions that make it easier to construct sexprs. For example, in traditional sexpr form we might define a boolean expression for true && (true || false) like this:

(&& true (|| true false))

Using the functions provided in this trait we can create a representation of this expression like so:

l(s("&&"), s("true"), l(s("||"), s("true"), s("false")))

Although a little more verbose than the lisp form - it serves its purpose here as a data structure for representing a language - in particular, a boolean expression language.

Make sure you read the documentation in this file for additional details.

sexpr.BooleanLanguage: This file defines the BooleanLangage trait. It uses the SexprLanguage trait to define additional symbols and functions that make it easier to build boolean expressions in s-expression form. You should take a moment to read through the documentation and code to get a better understanding.

As you will notice it defines important symbols for the boolean language such as T for true and F for false. It also defines functions that allow us to easily construct boolean expressions in s-expression form. For example, for the boolean expression:

if (true) false && true else false || true

We would use our boolean language form to create an s-expression to represent this boolean expression as:

ifs(T, &&(F,T), ||(F,T))

If you execute this from the scala console it will evaluate to an SExpr object.

Part 2: Implementing Boolean Expressions

In addition to the instructor files, we give you two files in src/main/scala/expr/boolean. The Driver.scala file shows you an example of using the sexpr boolean expression language and the BooleanLanguage.scala file defines the BooleanExpr object. The later is where you will be adding your work.

You should take a moment to read through this file to become familiar with the documentation. For this part you need to implement the case classes for representing boolean expressions. This includes the following:

True
False
Not(e)
And(e1,e2)
Or(e1,e2)
If(c,e1,e2)

Where e, e1, e2, and c represent any boolean expression. The case classes/objects you implement must extend the sealed trait Expr. This will ensure that only case classes defined in this file may extend the Expr trait. You should use case classes for boolean expressions that may have multiple instances and case objects for expressions that only have a single instance (singleton pattern).

Part 3: Implementing Parsing

In order for us to communicate to your code the type of boolean expressions that we want created we use our boolean s-expression language to represent a boolean expression. You must implement the parse method found in BooleanExpr to translate a SExpr (an s-expression boolean expression) into a Expr - your representation of boolean expressions that you implemented in Part 2.

For example, given the boolean sexpr &&(T,F) the parse function would work as follows:

scala> parse(&&(T,F))
And(True,False)

The former is our boolean s-expression form and the later is your representation of boolean expressions as case classes/objects.

You will need to pay attention to the structure of the SExpr object for proper translation. You must use pattern matching and recursion in your implementation. If you are given an improperly formatted boolean s-expression you must throw an IllegalArgumentException.

Part 4: Implementing Evaluation

We will use your parse function you implemented in Part 3 to build arbitrary boolean expressions to feed to the eval function that you need to implement in this part. The eval function takes an Expr object, evaluates it, and returns the result as a Expr. You should use the following rules to implement your eval function:

1.  true                 => true
2.  false                => false
3.  !true                => false
4.  !false               => true
5.  true && e            => e
6.  false && e           => false
7.  true || e            => true
8.  false || e           => e
9.  if(true) e1 else e2  => e1
10. if(false) e1 else e2 => e2

Here are some things to consider in your implementation:

Where you see an expression e on the right-hand side of a rule you will need to recursively evaluate e.
Although we have given you most rules above, there are other rules that you will need to implement for proper evaluation. That is, you must adhere to (4) below for your implementation to be correct.
You need to consider commutativity of operators.
Your eval function will always evaluate the given expression to either the true or false boolean expressions. If it did not - it means that you are missing a rule.

Part 5: Documentation and Comments

You must provide scaladoc documentation for each of the methods you implement. In addition, you should provide comments to explain code that may require clarity. That is, you should not comment the obvious, but you may want to provides comments to parts of your implementation that may not be entirely clear. Note: scaladoc and comments are different.

Grading

Your submission will be scored on the number of tests that are successfully passed. In addition, the course staff will be reviewing each submission for proper scaladoc documentation, comments, and style. All categories will contribute to your final score for this assignment.

Submission

When you have completed the changes to your code, you must run the following command to package up your project for submission (Mac/Linux):

scala -cp tools/grading-assistant.jar submission.tools.PrepareSubmission

On Windows:

scala -cp tools\grading-assistant.jar submission.tools.PrepareSubmission

This will package up your submission into a zip file called submission-DATE.zip, where DATE is the date and time you packaged your project for submission. After you do this, log into Moodle and submit the generated zip file.

After you submit the file to Moodle you should ensure that Moodle has received your submission by going to the activity page for the assignment and verifying that it has indeed been uploaded to Moodle. To further ensure that you have uploaded the correct zip file you should download your submission from Moodle and verify that the contents are what you expect.

We do not allow re-submissions after the assignment due date even if you failed to submit the proper file or forgot. There are no exceptions so be very sure that you have submitted properly.

You should test that you can run the PrepareSubmission tool early so you do not have trouble packaging your assignment up for submission minutes before the deadline.