CSE 373, Spring 2019: HW2 Part 2

Summary

Due Wednesday, April 24 at 11:59pm.

Submit by pushing your code to GitLab. If you intend to submit late, fill out this late submission form when you submit.

In this half of the project, you will help implement a part of a symbolic algebra calculator. A symbolic algebra calculator is a kind of calculator that does not immediately evaluate the expressions you type in but instead lets you manipulate them symbolically.

You will be responsible for implementing the logic for manipulating and evaluating mathematical expressions.

Note that this assignment uses your data structures from part 1 extensively, so you should fix any issues listed in your feedback for part 1 as soon as possible to prevent strange issues from occurring in this part. The course staff will not help you debug issues in part 2 if you have not fixed your issues from part 1.

You will be modifying the following files:

  • src/main/java/calculator/ast/operators/ExpressionOperators.java
  • src/main/java/calculator/ast/operators/GuiOperators.java

Additionally, here are a few more files that you might want to review while completing the assignment (note that this is just a starting point, not necessarily an exhaustive list):

  • src/test/java/calculator/TestCalculator.java
  • src/main/java/datastructures/interfaces/IList.java
  • src/main/java/datastructures/interfaces/IDictionary.java
  • src/main/java/calculator/ast/AstNode.java
  • src/main/java/calculator/gui/ImageDrawer.java
  • src/main/java/calculator/Calculator.java
  • src/main/java/calculator/Interpreter.java

We recommend reading through this entire assignment page before you begin writing code.

Objectives

  • Practice using your recently-implemented data structures.

    All of the programming projects in CSE 373 involve either implementing data structures or applying them in context. Part 1 had you implement DoubleLinkedList and ArrayDictionary, and in part 2, you'll be utilizing those data structures to solve a realistic problem. By using your own code, you'll gain real-life experience working with code that persists, along with all the benefits and annoyances brought about by your code quality and comments.

    And for reference, in most non-academic programming, you'll use pre-implemented data structures to make something even cooler than plain old data structures (sorry, data structures) just like you will in this project. While understanding the inner workings of data structures has its benefits, it's also important to be able to think at a higher level and use those data structures as tools to build a complex program.

  • Navigate and work in an unfamiliar codebase.

    Oftentimes, programmers are thrown into code that they didn't write themselves and told to implement or fix something in it. Congratulations! You're now getting more of that real developer experience.

    The goal here is not only to experience working with a new code base, but also to learn how to effectively navigate and learn about it. The next section includes some resources for learning to use the debugging tools built into IntelliJ (and other modern IDEs) to help with this.

  • Gift you a project to talk about with future employers

    Many students take this class with the intention of pursuing a career in the tech industry. If this is you, you can use these projects to fill some gaps in the experience section of your résumé—our projects offer many experiences worth mentioning: working with other people, navigating a new codebase, developing persistent code, using external libraries such as ANTLR (if you do some more research), etc. If you're talking in person, you can even demo the project GUIs.

    And don't forget that the specifications for these projects are scoped for our grading, but after this class is over, you're free to add on as many extra features as you wish. There are plenty of extra fun and useful optimizations and add-ons you could add to our application projects.

Debugging resources

(These may not be immediately useful as you're reading the spec, but keep these in mind, since you'll probably want to come back to this section later.)

IntelliJ has a great debugger with a lot of cool features—probably too many to master in a quarter's worth of time. Luckily, using just some of the many features of the debugger can help us understand our code in new ways and solve our programming problems. As the projects in this class get more complex and you write more code in general, you may find these debugging tips and skills very helpful to save you time.

  1. Start with these slides if you're new to debugging in IntelliJ. The debugging slides are a great basic manual for debugging in general and in IntelliJ. They'll walk you through debugging a specific piece of code and include tips, examples, and thorough instructions.
  2. Also check out this video that explains some basics in exploring this hw2p2 code base with the debugger, and some quirks about TestCalculator.java
  3. If you want to learn about additional (more advanced) useful debugging features, check out this video, and/or feel free to do more Googling on your own. These might not be directly applicable to this project, but are certainly useful for many other occasions. You can watch the whole video if you have time, but here are some particularly cool features:
    • advanced breakpoints and customization (14:39–18:20)
    • evaluate expressions (9:31–10:19)
    • overview of the remaining step buttons (12:50–14:22)
    • setting values at runtime (11:46–12:50)
    • watches (10:20–11:15)

Overview

This video (from 19wi so some file names and locations are outdated) walks through a high-level overview and demo for this assignment.

Here's another screenshot of the finished program:

Screenshot of calculator

The user can interactively enter commands in the bottom pane. These commands can do different things, ranging from just evaluating expressions to graphing actual output. The lines that start with>>> are lines where the user typed in input; the following lines are the output of that operation.

Our code will manage most of the logic in this pane for you. Your job is to simply focus on evaluating expressions.

Example 1: Basic usage and variables

Let's take a closer look at an example run:

>>> 3 + 2 * 7
17

>>> x + y
x + y

>>> x := 1
1

>>> x + y
1 + y

>>> y := 2
2

>>> x + y
3

The users type input into the lines that start with>>>. The line that follows immediately after is the output.

This example demonstrates the two core features we can perform using this calculator: evaluate math expressions (line 1) and symbolically work with variables (lines 7–17).

When we first typed in x + y, we were unable to evaluate or simplify the expressions because the variables xand y are currently unknown. Once both variables are defined, we can evaluate this function.

To assign variables, we do varName := expression. This differs from how we assign variables in Java: we use :=instead of =, and we don't need to assign a type to this variable. (All variables in our language are just mathematical expressions, so there's no need).

Example 2: Variable redefinition

Here is another example run:

>>> y := x + 3
x + 3

>>> y
x + 3

>>> x := 4
4

>>> y
7

>>> x := 8
8

>>> y
11

We define y to be equal to the expression x + 3. What exactly that expression evaluates to depends on the exact definition of x.

Example 3: Symbolic evaluation

Here is another example:

>>> y := x + 2 + 3 * sin(x) + (20 + 30)/70
x + 2 + 3 * sin(x) + 50 / 70

>>> y
x + 2 + 3 * sin(x) + 50 / 70

>>> x := 4
4

>>> y
6 + 3 * sin(4) + 50 / 70

>>> toDouble(y)
4.44387822836193

Notice that when we define y and display it, we don't evaluate the expression fully. By default, our calculator will perform simplification only if it can get an exact result. For example, we know evaluating sin and division generally does not produce exact results, so do not attempt to simplify those particular expressions.

In this case, we could have simplified 50 / 70 further. However, for the sake of simplicity, we will follow a simpler rule: we do not attempt to simplify division.

To get back an exact result, we need to use the toDouble(y) expression.

More specifically, we attempt to simplify expressions involving addition, subtraction, and multiplication of two numbers.

Example 4: AST transformation

Finally, the payoff: by deferring evaluation of the expression, we can manipulate expressions in interesting ways that would otherwise be impossible. For example:

>>> y := x^2 + 7*x + 10
x ^ 2 + 7 * x + 10

>>> plot(y, x, 0, 10, 0.5)  // Plot y by varying x from 0 to 10 in steps of 0.5
// Output plot omitted

These functions all work by taking the underlying expressions and manipulating them in some way.

Notes about implementation

Representing expressions as data structures

So, how do we go about actually representing expressions like x + 2 * sin(y) in our code?

It turns out the most convenient representation is to store this as a tree:

AST representation

This lets us easily preserve things like nesting and order-of-operations. We can also evaluate or manipulate this tree using the same kind of tree-manipulation algorithms you studied in CSE 143!

We call this sort of data structure an abstract syntax tree (AST). Each individual node in this tree is anAST node. An abstract syntax tree is similar to the binary trees that you've studied in CSE 143, with a few key differences:

  1. We store a list of children, rather than points to the left and right children. This is because AST nodes might have 0, 1 or 2 children.
  2. We store extra metadata on whether a node is meant to represent a number, variable, or an operation. An "operation" node is a node that represents any kind of function call (like sin(...)) or any node that contains children (like a + b).

You should read the source code of AstNode.java for more information on what methods are available for you to use.

Example: Creating and using AST nodes

You are not required to know how to build an AST expression to complete this assignment. However, if you're curious, here's how we would build the AST representing the expression x + 2 * sin(y):

// Create 'sin' node
IList<AstNode> sinParams = new DoubleLinkedList<>();
sinParams.add(new AstNode("y"));
AstNode sinNode = new AstNode("sin", sinParams);

// Create the 'multiply' node
IList<AstNode> multiplyParams = new DoubleLinkedList<>();
multiplyParams.add(new AstNode(2.0));
multiplyParams.add(sinNode);
AstNode multiplyNode = new AstNode("*", multiplyParams);

// Create the final 'add' node:
IList<AstNode> addParams = new DoubleLinkedList<>();
addParams.add(new AstNode("x"));
addParams.add(multiplyNode);
AstNode finalNode = new AstNode("+", addParams);

Background: Converting a string into an AST

You may be wondering how exactly we go about converting arbitrary strings into an AST.

We've provided you the code to do this, and understanding how this process works is beyond the scope of this class, but if you're curious, this process is known as "lexing" and "parsing". A "lexer" takes a string and outputs a list of distinct "tokens" in it. A parser takes this list of tokens and figures out how to convert it into a tree form.

We use a library called ANTLR which will automatically generate a lexer and a parser for us based on a grammar that describes what our language looks like. See the files in src/main/antlrif you want to know what our grammar looks like.

If you'd like to learn more about this whole process, feel free to ask the course instructor.

Types of AstNodes

So, we can represent expressions as a tree of AstNodes, but what exactly does an AstNode look like?

There are three types of AstNodes:

  1. Numeric nodes
  2. Variable nodes
  3. Operation nodes

Numeric nodes and variable nodes ought to be self-explanatory: they represent numbers and variables respectively. These types of nodes are guaranteed to always be leaf nodes.

Operation nodes are a little more abstract: they represent any kind of node that might have one or more children. For example, something like 3 + x would be represented as an operation node (+) with two children: a numeric node (3) and a variable node (x).

Another way of looking at operation nodes would be to consider them exactly equivalent to function calls. So, the expression sin(3) would be represented as an operation node—as a function call—with one argument.

(This means doing (3 + 2) is really equivalent to calling a function named +, passing in two arguments! This trick of treating everything as function calls helps us simplify our overall language.)

The AstNode class contains methods you can call to determine what type of node it is and to extract relevant pieces of information.

Storing variables

We can represent expressions using abstract syntax trees, but how do we store variables?

We use a dictionary! Whenever the user defines a variable, we store that variable name as a string and the corresponding expression in your ArrayDictionary. If a variable does not exist in that dictionary, we say it's an unknown variable.

Our provided code already handles the assignment operation, so most of your code should just need to read from the pre-populated dictionary of variables.

Side effects

None of the handler methods you implement should have any other side effects on their inputs. This means that the node and dictionary of variables that your methods receive as input should be left exactly as they were initially when your method finishes.

To enforce this, all of the fields of AstNode are final, and the list of children it gives you is a ReadOnlyList that you cannot change. Your methods will need to return new AstNodes instead of mutating the values in the existing nodes.

Part 2a: Implement handleToDouble(...)

Task: Implement ExpressionOperators.handleToDouble(...).

(Note: you can find ExpressionOperators in the calculator.ast.operators package.)

First, you will implement handleToDouble(...), a function that attempts to fully evaluate the given AST into just a single double.

This method will receive an operation node named "toDouble". This node will contain a single child, which is the expression you are to convert into a double. (So, this method might receive the AST node corresponding to toDouble(3.0 + 4.0). You would then return the AST node corresponding to 7.0).

For more details about the expected behavior of this function, see the comments in the method you need to implement.

Furthermore, you may assume that the expression AST you must convert to a double will consist only of the following types of nodes:

  • Numeric nodes
  • Variable nodes
  • The following operation nodes:
    • Basic math operators: +, -, *, /, and ^ (addition, subtraction, multiplication, division, and exponentiation).
    • The negate operator. The "negate" operator is used to represent expressions like -(x + 3) (here, we negate x + 3). We use the string "negate" in these cases instead of "-" to avoid clashing with the subtraction operation.
    • Two basic trig functions: sin and cos.

For example, the input to represent toDouble(3 + 4) would be:

AST representation of toDouble(3 + 4)

Which would return a new node containing the value 7.0. The representation of toDouble(-(a + b)) would be:

AST representation of toDouble(-(a + b))

Which would return a node with the numeric value -(a + b), if a and b are defined.

Part 2b: Implement simplification

Task: Implement ExpressionOperators.handleSimplify(...).

This method is responsible for simplifying an AST node. For more implementation details, see the comments in the handleSimplify(...) method as well as the tests you have been provided.

You may make the same assumptions about the AST as you did in part 2a—the only difference is that instead of being given an operation node named "toDouble" that contains a single child, you will be given an operation named "simplify" that contains a single child.

Notes:

  • The calculator automatically wraps all input in a simplify call when evaluating it, so any output returned will automatically get simplified. This means that all of our provided tests depend on your handleSimplify method, and that our tests for this method do not explicitly use simplify nodes.
  • The calculator may call your handleSimplify(...) function multiple times while evaluating a single expression, so make sure it's relatively efficient.
  • You are required to simplify only expressions of the form NUM + NUM, NUM * NUM, and NUM - NUM.

For example, to evaluate simplify((5 + 6) + (7 - a)) with no variables defined, we would pass in simplify in the following diagram to handleSimplify(...):

AST representation of simplify((5 + 6) + (7 - a))

Which will simplify the expression to a new tree containing the following:

AST representation of simplify(11 + (7 - a))

Note that the method was not required to simplify the expression further down to 18 - a.

Part 2c: Implement handlePlot(...)

Task: Implement GuiOperators.handlePlot(...).

As before, see the source code for additional implementation nodes. Similar to before, you will receive an AST operation node named "plot". However, this time, the node will have five children—see the comments associated with plot(...) for more details. The representation of the node produced by plot(3 * x, x, 2, 5, 0.5 + a)is shown below (this would necessitate that the variable a has been previously defined):

AST representation of plot(3 * x, x, 2, 5, 0.5 + a)

You may make the same assumptions about each child as you did in parts 2a and 2b.

Note: you are not responsible for drawing the actual chart yourself. Instead, you should call the drawScatterPlot(...) method (see ImageDrawer).

Background: Drawing custom visualizations and charts

If you want to try implementing extra visualizations or charts, here are some additional pieces of information that may help.

The calculator itself is built on top of Java Swing, which is the same library that the DrawingPanel class from CSE 142 uses. This means that fundamentally, the way we draw things is the same: we get and use a Graphics object. See ImageDrawer.getGraphics() for more details.

We use a library called "JFreeChart" to draw our different charts. You can find documentation on how to use this library online, and an example in the ImageDrawer class.

Part 2d: Complete individual feedback

Task: Submit the Canvas survey.

Each group member should answer and submit these questions independently on this Canvas survey. As a general rule of thumb, a good survey should take around 5 minutes to complete, but feel free to include as much detail as you want. Points will only be deducted for very short answers.

Deliverables

The following deliverables are due on Wednesday, April 24 at 11:59pm.

Submit by pushing your code to GitLab. If you intend to submit late, fill out this late submission form when you submit.

Submission checklist:

  • Completed the ExpressionOperators.java and GuiOperators.java classes.
  • Ran Checkstyle and fixed all issues it reported with the files you edited.
  • Completed individual feedback on Canvas.

Remember that we may grade using some secret tests in addition to our provided tests, so it may be in your best interest to double check that your code handles all cases correctly (or to write additional test cases to test your own code on cases missing from our provided tests).