Assignment 3 (Phase 2, Sprint 1)

For each class in the hiearchy except the root class, add an explicit inheritance relation. For example, the Sin class is a unary function, so a kind of a unary expression meaning the Sin class is a subklass of Unary.

public class Sin extends Unary {

public%20class%20Sin%20extends%20Unary%20%7B%0A

Mark all abstract classes abstract. For example, the SymbolicExpression class is abstract:

public abstract class SymbolicExpression {

public%20abstract%20class%20SymbolicExpression%20%7B%0A

From the description above, it should be mostly clear what classes create objects with subtrees. Subtrees are stored in fields in the objects created from the expression classes. Because a subtree can be an arbitrary expression, we cannot statically know its exact type – for example in the binary expression 5 + 37, both subtrees are constants, but in x + y, both subtrees are variables.

Luckily, here is where inheriance and subtype polymorphism comes to the rescue. For example, both the Variable class and the Constant class are subclasses of the Atom class, meaning we could use Atom as a type of a field holding sometimes variables and sometimes classes.

However, 5 + (37 * x) is also legal and here, the left and right subtrees are of different kinds, and the right subtree is not an atom (it is some concrete subclass of Binary). Applying the same reasoning, we can see that there is a common superclass of both atoms and binary expression: SymbolicExpression. Now we have reached the root class of our expression tree and so any expression object can be stored in a variable whose type is SymbolicExpression.

So, concretely, as the Binary class represents expressions with a left and a right subtree we can write like this in the Binary class:

public class Binary extends ... {
    private SymbolicExpression lhs = null;
    private SymbolicExpression rhs = null;

public%20class%20Binary%20extends%20...%20%7B%0A%20%20%20%20private%20SymbolicExpression%20lhs%20%3D%20null%3B%0A%20%20%20%20private%20SymbolicExpression%20rhs%20%3D%20null%3B%0A

where lhs and rhs are common abbreviations for left-hand side and right-hand side respectively.

Note that this technically allows ill-formed expressions such as quit + vars, but the grammar of the calculator language excludes these, and a correct parser will give a parse error for this.

Further, note the use of the private access modifier above! This keyword means that only the binary class itself should be able to access its lhs and rhs fields. This may be overly restrictive, but it is better to start like that and lift this restriction when and if the need arises than the other way around.

Variable objects need to store the identifier of the variable, e.g., "x". For this, we can use the type String. A suitable name for the field is identifier and we start with private as always.

Similarly, Constant objects need to store their constant values. Since we have said that all values are floating point values, we can choose double as the type for this field, value as the name and make it private.

Make is not a good program to use for Java because make expects a 1-1 relation between code files and object-files. This might not be the case in Java, which makes it hard to use makefiles as elegantly as with C. Feel free to use somemthing more fancy, but for simplicity, we will stick with make.

The following makefile is going to sustain us for the rest of this assignment, unless you want to extend it to better fit your workflow (note that this makefile assumes all Java sources are in the same directory – it is otherwise quite common to have a directory structure that matches your package structure):

all:
    javac -d classes *.java

run:
    java -cp classes org.ioopm.calculator.Calculator

clean:
    rm -rf classes

all%3A%0A%20%20%20%20javac%20-d%20classes%20%2A.java%0A%0Arun%3A%0A%20%20%20%20java%20-cp%20classes%20org.ioopm.calculator.Calculator%0A%0Aclean%3A%0A%20%20%20%20rm%20-rf%20classes%0A

This makefile has three targets, which we discuss below. Note that the targets have no dependencies, so we will always recompile the entire program, not just the parts that have changed.

1. all – compile all Java source files in the current directory and store them in the directory classes which will be created unless it exists. Once you have compiled your program, take a peek inside the classes directory and explore the output of the Java compiler. If we did not specify the -d flag, the result of the compilation would end up in the current directory.
2. run – run the compiled program by loading the class org.ioopm.calculator.Calculator and execute its main() method. The -cp flag sets the classpath of the Java VM to the classes directory in the current directory. Thus, it will expect classes/org/ioopm/calculator/Calculator.class to exist (note how packages names map to directory structures).
3. clean – toss the entire classes directory and all its contents. The -rf flag stands for recursive (meaning class, and its subdirectories) and force (meaning don’t ask – just delete).

Now it is time to get this all to compile. Use the make file. Read the output of the compiler. Fix the bugs. Try again.

Once you get this to compile, there is no working program (yet), but a working class hieararchy that mostly consists of empty classes and their inheriance relations and some fields. Now that we have a system that compiles, we can extend it bit by bit and use the makefile to catch early bugs as we go.

1. Declare all the classes in the AST, one class per file. If you find switching between multiple buffers annoying, you can have all AST classes in a single file (only making one, e.g., SymbolicExpression public), and later splitting this file into multiple files and making all classes public.
2. Add the extends relation between the classes.
3. Make classes which do not correspond to expressions in the language abstract (e.g., SymbolicExpression and Binary).
4. Add the correct subtrees to the classes following the language of the calculator.
5. Add other variables needed to the classes. Make all instance variables private.
6. Create a basic makefile unless you haven’t already done so.
7. Make sure the code compiles correctly.

Constructors are special methods that are run only once when an object is created. Different programming languages treat constructors differently – in C we had to call them explicitly, but in Java they are called automatically. Moreover – it is not even possible to create an object without running at least one of its constructors. This means that constructors can be used to establish invariants, e.g. “this field is never null” or, “the sum of all fears always add up to 42”.

Constructors thus have special rules in Java that do not apply to normal methods. First, constructors must always be named exactly like the class in which they appear. Second, a class must always have a constructor, even if Java must add it itself. As a running example, consider the following class hierarchy:

class A {
    private int a;
}
class B extends A {
}
class C extends B {
}

...
C = new C(); // OK!

class%20A%20%7B%0A%20%20%20%20private%20int%20a%3B%0A%7D%0Aclass%20B%20extends%20A%20%7B%0A%7D%0Aclass%20C%20extends%20B%20%7B%0A%7D%0A%0A...%0AC%20%3D%20new%20C%28%29%3B%20%2F%2F%20OK%21%0A

Let’s say that the designer of A decides that when we create an A, we must set its a field to a positive number. This can be enforced by adding a constructor to A that raises an error if a < 0.

class A {
    private int a;
    public A(int a) {
        if (a < 0) {
            throw new IllegalArgumentException("a must be > 0");
        }
        this.a = a; /// this.a is the field, a is the argument!
    }
}

class%20A%20%7B%0A%20%20%20%20private%20int%20a%3B%0A%20%20%20%20public%20A%28int%20a%29%20%7B%0A%09if%20%28a%20%3C%200%29%20%7B%0A%09%20%20%20%20throw%20new%20IllegalArgumentException%28%22a%20must%20be%20%3E%200%22%29%3B%0A%09%7D%0A%09this.a%20%3D%20a%3B%20%2F%2F%2F%20this.a%20is%20the%20field%2C%20a%20is%20the%20argument%21%0A%20%20%20%20%7D%0A%7D%0A

Now we can write new A(42) (or new A(-42), which throws an exception), but we can no longer write new C() like before. Actually, we cannot even compile the classes B or C. The reason for this is that all B’s and C’s are A’s (because of the inheritance relation). This means that whenever we create a new B (or C), we are also creating a new A, which means we must call its constructor!

Solution (for B):

class B {
    public B(int a) {
        super(a); /// This calls A's constructor!
    }
}

class%20B%20%7B%0A%20%20%20%20public%20B%28int%20a%29%20%7B%0A%09super%28a%29%3B%20%2F%2F%2F%20This%20calls%20A%27s%20constructor%21%0A%20%20%20%20%7D%0A%7D%0A

With this class in place, we can do new B(x) and have the value of x be forwarded to the constructor of A so that we can establish the invariant a >= 0 in A. We must also do the same for C. However, we could imagine that the designer of C solves this differently:

class C {
    public C() {
        super(42); /// This calls B's constructor!
    }
}

class%20C%20%7B%0A%20%20%20%20public%20C%28%29%20%7B%0A%09super%2842%29%3B%20%2F%2F%2F%20This%20calls%20B%27s%20constructor%21%0A%20%20%20%20%7D%0A%7D%0A

Now, new C() works again, because its constructor now calls B’s constructor with the constant 42 get’s forwarded to A’s constructor. So, in this example every instance of C is an instance of A whose a field always has the value 42.

Note that the call to a superclass’ constructor using super() must always happen on the first line of the forwarding constructor. The reason for this is that Java tries to prevent you from operating on the object until it has been properly initialised. Thus, because the super calls always happen first, the constructor of A is guaranteed to have finished before the constructor of B runs etc.

Actually, when you leave out constructors from your classes, the Java compiler will add a so-called default constructor in. This is what the Java compiler actually compiles for the initial class hierarchy.

class A {
    private int a;
    public A() {}
}
class B extends A {
    public B() { super(); }
}
class C extends B {
    public C() { super(); }
}

class%20A%20%7B%0A%20%20%20%20private%20int%20a%3B%0A%20%20%20%20public%20A%28%29%20%7B%7D%0A%7D%0Aclass%20B%20extends%20A%20%7B%0A%20%20%20%20public%20B%28%29%20%7B%20super%28%29%3B%20%7D%0A%7D%0Aclass%20C%20extends%20B%20%7B%0A%20%20%20%20public%20C%28%29%20%7B%20super%28%29%3B%20%7D%0A%7D%0A

Now it is time to add constructors to our AST classes.

• Remember that a constructor for class C must be named C
• Always make constructors public until there is a reason not do so (we will see an example later)
• It is common to overload constructors to give different ways to create an object

When you are done with this step, it should be possible to create instances of all concrete (i.e., non-abstract) classes in the AST and have their fields properly initialised.

When we create objects from our AST classes, we are going to want to pass in values to initialise the fields. For example, here is a constructor for Constant:

public Constant(double value) {
    /// Does it need to call super?
    this.value = value;
}

public%20Constant%28double%20value%29%20%7B%0A%20%20%20%20%2F%2F%2F%20Does%20it%20need%20to%20call%20super%3F%0A%20%20%20%20this.value%20%3D%20value%3B%0A%7D%0A

Note how we distinguish the field named value from the argument named value by prefixing the former with this..

Technically, if the argument value was named differently, value would mean the field. In this course, I am going to write this. explicitly (except when I forget) to make it clear that an assignment changes or accesses the current object in some way.

1. Add constructors for all classes
2. Consider what classes do not need a constructor (when the default constructor is enough) and what classes’ constructors need to call their superclass’ constructor.
3. Make sure that the code compiles using your makefile

Later, when we evaluate expressions, we are going to want to know whether an expression is a constant or not. There are several ways to do this. First, the wrong way:

if (expr instanceof Constant) {
    ... /// We only come here is expr points to an object whose
        /// class C inherits from Constant (in 0 or more steps)
}

if%20%28expr%20instanceof%20Constant%29%20%7B%0A%20%20%20%20...%20%2F%2F%2F%20We%20only%20come%20here%20is%20expr%20points%20to%20an%20object%20whose%0A%09%2F%2F%2F%20class%20C%20inherits%20from%20Constant%20%28in%200%20or%20more%20steps%29%0A%7D%0A

This exemplifies something we could not do in C! We can ask an object about itself. In this case, we test if its class is a subclass of Constant (including Constant itself).

The reason why this is bad is because it is bad practise to hard code a class name into the source code. For example, there might be – perhaps as the result of a future addition – other classes in the hierarchy which are effectively constants too, without being subclasses of Constant. Thus, this test is to be avoided unless it is absolutely necessary.

A better, and much more flexible way, is to add a method isConstant() that returns true for constants and false otherwise. Any class in the AST can implement this method such that it returns true. We have now decoupled the concept of being a constant from the class Constant which is great.

Since we want to be able to ask any expression whether it is a constant or not, we should add isConstant() to the SymbolicExpression class, and give it a default implementation that returns false. This behaviour will be inherited by all its subclasses, meaning that we will have to override it for those classes where we want isConstant() to return true.

• Add at least two isConstant() methods, including one in SymbolicExpression that returns false and another one in a suitable place that returns true. Your end goal is that all objects that represent constant expressions (that do not need to be evaluated) should return true when asked if isConstant().
• Make the isConstant() methods public.

As part of printing expressions, we need to be able to get operator names from expressions. As before, we want to add this method to SymbolicExpression so we can call it on any expression, even if we do not know its type.

The method getName() should return the operator name as a string for expressions which have operators. For all other operators, calling this method is an error.

Here is an example of getName() for the Sin class:

public String getName() {
  return "sin";
}

public%20String%20getName%28%29%20%7B%0A%20%20return%20%22sin%22%3B%0A%7D%0A

and another one for the Addition class:

public String getName() {
  return "+";
}

public%20String%20getName%28%29%20%7B%0A%20%20return%20%22%2B%22%3B%0A%7D%0A

Since calling this method is an error for expressions which do not have operators, we can have those methods throw an exception. We will return to how exceptions work later, but for now, here is how to throw an exception and have the program crash nicely with a good stack trace and error message:

throw new RuntimeException("getName() called on expression with no operator");

throw%20new%20RuntimeException%28%22getName%28%29%20called%20on%20expression%20with%20no%20operator%22%29%3B%0A

Following the logic of before, add a default getName() behaviour in SymbolicExpression that throws an error and override this behaviour for the classes where an operator exists.

In the program, we are going to want to print expressions. When we do so, we only want to print parentheses where they are needed, to avoid cluttering the output, for example:

• (a + b) * (c - d) – here the parenthesis is needed, dropping it changes the meaning of the expression.
• (a * b) * (c / d) – here the parenthesis is not needed, so it should not appear in the printout of this expression.

The method getPriority() should return an integer number that represent precedense order. When printing a binary expression, we are going to check whether the priority of a subtree is lower than the priority of the current operator, and if so, put parenthesis around the subtree. For example, assume that multiplication and division have priority 100 and that addition and subtraction have priority 50. With these numbers, consider the printing of the following AST:

    *
   / \
  +   *
 /|   |\
a b   c d

Because 50 \(\lt\) 100, we are going to put parentheses around the left subtree, but because 100 \(\not\lt\) 100. So this will be printed like so: (a + b) * c * d.

We have two choices to implement getPriority():

1. Add a priority field to SymbolicExpression and give it a default value (what?) Add a single getPriority() method to SymbolicExpression that simply returns the value of the priority field. Then use the constructors of the expression classes for which you wish to alter the priority to set the priority number to a suitable value.
2. Add a getPriority() method to SymbolicExpression that returns a constant default priority value (what?). Then override that method in the classes classes for which you wish to alter the priority to set the priority number to return a suitable value.

The getValue() method returns a constant’s value. Calling this method on something which is not a constant causes an error. This implementation follows a similar pattern as a previous method.

This method is going to be instrumental to implement evaluating expressions. Evaluation is really reduction, i.e., we are reducing the expression to simpler expressions, to the extent possible. For example, we can reduce 5 + 37 to 42. If we reduce 3 * x to an expression for which isConstant() returns true, we can safely call getValue() to read its value.

1. Add the isConstant(), getName(), getPriority() and getValue() methods to the appropriate classes. Make them public. If you run into access problems due to your making all instance variables private consider adding methods in the super classes that allow “getting” the value of the variables, and if that is not enough, also “setting” their values. s
2. Think about whether there are cases where the implementation of a method should call the super class’ implementation of the method using the super.methodName(args) notation.
3. Make sure that the code compiles using your makefile

1. Implement the testPrinting() method following the instructions above and use it in a bunch of tests of your own choosing. This code should live in its own Test.java file so you will need to make imports and/or packages to work correctly.
2. Make sure that the code compiles using your makefile.
3. Make sure you can run the tests and that they all fail – working success criteria for the following steps. Actually, you can improve on the tests above by adding assert statements. They look a bit different in Java, and do not require any imports. However – they need to be enabled explicitly when the program is run. Time to edit the Makefile and make sure that there is a way to run the tests with assersions enabled. Write java -help on the command line to list the Java options. If your Java speaks Swedish, then you want to look for something like this: aktivera verifieringar med den angivna detaljgraden. There is a long and a short name for the flag that enables assersions, and as you can see from running java -help, you can turn them on and off for different packages or classes. Super nice! (The short name is -ea, but use the long name in the make file for enhanced readability.)
4. Note that it may not make sense to run with assertions on during test-driven development – now we are expecting tests to “blow up”.

1. Start by verifying that the assertion fails for the tests which are our success criteria for this step.
2. Implement the toString() method correctly for all classes.
3. Where possible/necessary, use super.toString() for printing – never make a field public to make this work.
4. Make sure that the code compiles using your Makefile.
5. Make sure that the tests from the previous step all pass!

1. Create a new set of tests isomorphic to the testPrinting() ones using the testEvaluating() method that you will also have to implement.
2. Implement the equals() method correctly for all classes. Again, not that equals() takes an Object as argument, not a SymbolicExpression or a subclass to that class.
3. Where possible/necessary, use super.toString() for printing – never make a field public to make this work.
4. Make sure that the code compiles using your Makefile.
5. Make sure that the new tests all fail which is to be expected since we have not implemented eval() yet.

Evaluation happens in postorder traversal in the tree, meaning from the leaves up. This should not come as a surprise at this point, given that’s how we have done most things with the AST.

An expression is evaluated by calling the eval() method on its top object (the root of the expression tree). What happens now is decided by that object – different types of nodes will behave differently. A constant is an atom and already knows its value. A binary expression like + will have to recurse and call eval() on its left and right subtrees before it can calculate its resulting value. There is however one exception: assignment will not evaluate its right subtree because that is always (in a correct tree – the parser takes care of this) a variable to be assigned, not to be evaluated.

Add a method public abstract SymbolicExpression eval(); to the SymbolicExpression class. This method is abstract and must be overridden in the subclasses. For commands, let eval() throw an exception with the message that commands may not be evaluated. The eval() method should attempt to reduce an expression maximally. Some examples follow:

• eval(new Constant(5)) should return new Constant(5)
• eval(new Variable("x")) should return new Variable("x")
• eval(new Addition(new Variable("x"), new Constant(37))) should return new Addition(new Variable("x"), new Constant(37)) (cannot be reduced)
• eval(new Addition(new Constant(5), new Constant(37))) should return new Constant(42)

You can look at Java’s Math class to see what functions are available for some of the operations, for example to calculate cos, we can use Math.cos().

Get this to work with your tests!

Here is an example of what eval() could look like in the Sin class:

public SymbolicExpression eval() {
    SymbolicExpression arg = this.arg.eval();
    if (arg.isConstant()) {
        return new Constant(Math.sin(arg.getValue()));
    } else {
        return new Sin(arg);
    }
}

public%20SymbolicExpression%20eval%28%29%20%7B%0A%20%20%20%20SymbolicExpression%20arg%20%3D%20this.arg.eval%28%29%3B%0A%20%20%20%20if%20%28arg.isConstant%28%29%29%20%7B%0A%09return%20new%20Constant%28Math.sin%28arg.getValue%28%29%29%29%3B%0A%20%20%20%20%7D%20else%20%7B%0A%09return%20new%20Sin%28arg%29%3B%0A%20%20%20%20%7D%0A%7D%0A

Now is the time to add variable support. We can keep track of variables and their values by using a hash table. Java has a very nice hash table implementation already in java.util.HashMap. You can do import java.util.HashMap; to import it into your program.

Hashmaps are parametrically polymorphic. The type of a hashmap that maps variables to symbolic expressions is this: HashMap<Variable, SymbolicExpression>. This restricts all keys to be of type Variable and all values to be of type SymbolicExpression.

Extend the signature for eval() with HashMap<Variable, SymbolicExpression> vars. This hashmap can be used as a simple store where we use vars.put(a, b) to store a value b inside a variable a and vars.get(a) to lookup the value for variable a. Note that we now add side-effects to these programs!

In your test program, add a hashmap that you can pass in as argument to all eval() calls. For example, you can do this: HashMap<Variable, SymbolicExpression> vars = new HashMap<>(); Now you need to extend eval() in Assignment so that the evaluated left-hand side is stored in the variable on right-hand side using vars.put(...). Furthermore, in eval() in Variable, you need to look up the variable’s value in vars. If it is there, the variable v evaluates to vars.get(v), otherwise it is as before. In all other cases, you will need to propagate vars to all eval() calls on all subtrees.

You should now be able to run your tests fully and pass them.

Revisiting the eval() example in the Sin class, extended with variables, here is what we could get:

public SymbolicExpression eval(HashMap<Variable, SymbolicExpression> vars) {
    SymbolicExpression arg = this.arg.eval(vars);
    if (arg.isConstant()) {
        return new Constant(Math.sin(arg.getValue()));
    } else {
        return new Sin(arg);
    }
}

public%20SymbolicExpression%20eval%28HashMap%3CVariable%2C%20SymbolicExpression%3E%20vars%29%20%7B%0A%20%20%20%20SymbolicExpression%20arg%20%3D%20this.arg.eval%28vars%29%3B%0A%20%20%20%20if%20%28arg.isConstant%28%29%29%20%7B%0A%09return%20new%20Constant%28Math.sin%28arg.getValue%28%29%29%29%3B%0A%20%20%20%20%7D%20else%20%7B%0A%09return%20new%20Sin%28arg%29%3B%0A%20%20%20%20%7D%0A%7D%0A

However, because HashMap<Variable, SymbolicExpression> is boring to write, and because that class name isn’t very informative, let us add a new name (and class!) to our program that improves on the explanation:

public class Environment extends HashMap<Variable, SymbolicExpression> {}

public%20class%20Environment%20extends%20HashMap%3CVariable%2C%20SymbolicExpression%3E%20%7B%7D%0A

This is an empty class that says that Environment is a hashmap whose keys are Variables and values are SymbolicExpressions. Think of this a bit like a typedef in C, except that whereas in C, typedefs insert type equivalences, there is no equivalence here – but an is a relation from Environment to HashMap<Variable, SymbolicExpression>, not in the other direction!

1. Implement the eval() method without support for variables as a first step. You can still use the tests to make this work.
2. Once you have a working eval() without variable support, it is time to move on to this step.
   1. First change the eval() method to take the additional Environment argument. Because we are using eval() in testEvaluating(), we are going to have to extend that method to also take an Environment argument.
   2. Make all the old tests running and passing again, by calling them with an empty environment. Note that you should creat a new Environment per call to testEvaluating() so that no side effects carry over between tests (once assignments start producing them!).
   3. Now, extend your tests so that we have a working test for eval() with support for variables. You most likely have a test from before that uses a variable, say something like (5 + x) * 2. If we evaluate this test using an environment in which the variable x is bound to 8, the whole expression should evaluate to 42.0. Write a test for this that creates a new Environment and sets x to 8 and uses this as the argument to testEvaluating(). This should fail initially, because the current eval() does not yet reduce variables to constants.
   4. Because Environment is a map with Variables as keys, we need to make sure that two different variable objects that both denote the same variable always return the same hashCode(). You can test this by printing the hash codes for two variables: System.out.println("a = " + a.hashCode() + "\nb = " + b.hashCode());. If your variable objecs hash differently when they should not, you can override the hashCode() method in the Variable class and return the hashCode() of the underlying strings that hold the variable names. Strings are part of the Java library and therefore should uphold the property mentioned in the previous link that If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
3. Change eval() so that the environment is propagated through evaluation. Importantly, change its definition in Assignment to insert or update variables’ values, and in Variable so that a variable evaluates to its value in the current environment.
4. Make sure that the code compiles using your Makefile.
5. Make sure that the new tests all pass.

If you suddenly get failing tests, it may be that you have tests that suddenly have side effects! Double-check for correctness, and update the tests if that is the case. Any test that defines a variable to the left of a use to that same variable on the right is a candidate for this happening.

Consider the quote above: /If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result./ Do we satisfy this? We did add new equals implementations so we may need to override the default hashCode() behaviour for other classes too. Note that nothing in the implementation other than variables are stored in hashmaps, so you could omit this step and hopefully never suffer.

1. Make all commands (Vars and Quit) singletons, so that there are only one object of each class for each program. If you want to be defensive, you can add an assert to the constructors that trigger the second time the constructor is run to capture bugs that could cause multiple instances of a command to be created.
2. Add the isCommand() method to the class hierarhy. Try to add it in as few places as possible.
3. Make sure the code compiles using your makefile, and that all the tests run and pass.
4. Make a commit and push it to GitHub. After the normal push, add a tag assignment3_stepB (be careful to spell it just like that) and push the tag to the server by adding --tags to the git push command. If your partner wants to pull the tag, he or she needs to add a --tags to the git pull command, but if you were careful to have a commit which was just a tag, then having that synced is not important.

To prevent constants from being redefined, we could extend eval() in assignment to check that its right-hand side is not a named constant, and if so, throw an exception “Error: cannot redefine named constant”. Alternatively, we could extend the parser to give a syntax error if the name of a known constant appears on the right hand side of an =. Because it lets us play around a little with exception handling, we are going to choose the first of these.

Given this design choice, we will need some way to check the right-hand side inside assignment. Maybe we can use isConstant() for that, or maybe not? You will have to figure that out. (You could also just add an isNamedConstant() along the same lines as isConstant() but it would be better not to if isConstant() works so that we reduce the amount of code that must be maintained.) When – during the evaluation – we find that we are about to reassign a named constant, we are going to throw an IllegalExpressionException exception. This is a new class that you are going to write. It will look like this:

public class IllegalExpressionException extends ... {
    ...
}

public%20class%20IllegalExpressionException%20extends%20...%20%7B%0A%20%20%20%20...%0A%7D%0A

…and you throw it like this (in eval()):

throw new IllegalExpressionException(...);

throw%20new%20IllegalExpressionException%28...%29%3B%0A

If you are unclear about the consequences for the code between checked exceptions and unchecked exceptions, I suggest that you make Exception the superclass of IllegalExpressionException and play along for a few minutes with what the compiler suddenly complains about with respect to eval() and all methods that call eval(). Think about whether this improves your code or not! Tip: commit just before so you can easily revert to the previous state if you feel the need.

If you change the superclass from Exception to RuntimeException, all these errors go away, and the compiler does not require any propagating changes to eval(). However, we are no longer forced to catch IllegalAssignment, or declare where they may appear and wreak havoc.

You decide: what should be the superclass of IllegalAssignment and why.

Obviously we need to extend the parser with support for named constants. A named constant can be added as a case in primary where we look for identifiers which are knowns strings (e.g., pi). However, we want to be able to extend the number of constants that we support in the program without having to change the parser. To that end, we are going to want to have a global set of known constants which the parser will access.

Let’s write a new class for this:

package ...

import ...

public class Constants {
    public static final HashMap<String, Double> namedConstants = new HashMap<>();

    static {
        Constants.namedConstants.put("pi", Math.PI);
        Constants.namedConstants.put("e",  Math.E);
        ... /// TODO: the rest of the constants, go wild!
    }
}

package%20...%0A%0Aimport%20...%0A%0Apublic%20class%20Constants%20%7B%0A%20%20%20%20public%20static%20final%20HashMap%3CString%2C%20Double%3E%20namedConstants%20%3D%20new%20HashMap%3C%3E%28%29%3B%0A%0A%20%20%20%20static%20%7B%0A%09Constants.namedConstants.put%28%22pi%22%2C%20Math.PI%29%3B%0A%09Constants.namedConstants.put%28%22e%22%2C%20%20Math.E%29%3B%0A%09...%20%2F%2F%2F%20TODO%3A%20the%20rest%20of%20the%20constants%2C%20go%20wild%21%0A%20%20%20%20%7D%0A%7D%0A

The static block will be run at load-time, that is when the JVM starts and loads this class into the program. This will add entries in the hashtable that maps strings (“pi” in our example above) to values (Math.PI above). Note that the Double above is not a misspelled double – Java does not support primitive types with parametric polymorphism. The solution is to use Double instead of double, which means use an object holding the double instead of a double itself. Java converts quietly between double and Double so you mostly do not need to care about this. Rule of thumb: use primitives when you can and their corresponding object types only when you must.

Following this addition, we have, in the specialisation of primary in the parser, a choice – either the identifier is in the set of keys in Constants.namedConstants, in which case it is a constant – or it is a variable name. Look in the Java API for the HashMap API for how to check if something is in the map – it should be familiar after Assigment 1.

For now, we want to support at least the following named constants:

• pi which evaluates to whatever Math.PI is defined as
• Answer which evaluates to 42
• L which evaluates to \(6.022140857 \times 10^{23}\).
• e which evaluates to whatever Math.E is defined as

Examples of uses of named constants:

$ Answer + Answer
84.0
$ 43 = Answer
Error: cannot redefine named constant 'Answer'

1. Add a NamedConstant class with the appropriate methods. For each method that it inherits from its superclass(es) – think about whether it makes sense to override it and provide a more specific implementation. If so, also think about whether it makes sense to call the overridden method in the superclass as part of the more specific behaviour.
2. Add the extra exception class.
3. Implement eval() so that an exception is thrown on an attempt to redefine a named constant.
4. Extend the parser so that it parses at least the named constants named above, using the NamedConstant class. Note that since we are using the name of the named constants, not the constant itself, as the key in the hash map, we avoid the issue with hashCode() in Variable that we had before, with respect to the Environment. An alternative (better?) implementation on NamedConstant would be to make the hashmap store instances of NamedConstant instead of doubles. That way, we could simply lookup our named constant objects from there, and also have to create fewer objects.
5. Add tests to your Test.java file – both for correct uses of named constants, and for attempts to reassign them that should result in exceptions being thrown.
6. Make a commit and push it to GitHub.

1. You don’t need instructions for this one. But don’t forget testing or committing!

Create the parser object and the hashmap (Environment) for holding the variables. They can be stored in a local variable on the stack. We should not create a new parser everytime we want to read a string, and the same variable store should be used throughout the program. To make this more explicit, designate the variables holding the parser and the variables as final. Final is reminiscent of C’s const and simply means that the variables cannot be reassigned.

(Note that you will need to do some import of classes for the variable store.)

The simplest way to get a handle to an object from which we can read strings from the terminal is this:

String input = System.console().readLine();

String%20input%20%3D%20System.console%28%29.readLine%28%29%3B%0A

That will work fine.

At least as a starting point, we can make this an infinite loop (you may dislike infinite loops and want to add other exit conditions, perhaps):

while (true) {
    /// Event loop code here!
}

while%20%28true%29%20%7B%0A%20%20%20%20%2F%2F%2F%20Event%20loop%20code%20here%21%0A%7D%0A

In the event loop, we want to do the following:

1. Read a string from the console
2. Feed this string into the parser and get back a SymbolicExpression object
3. Branch on this object
   1. If it is a command, we need to do whatever it wants (quit the program, clear the variable list, or print the variable list)
   2. Otherwise, we want to evaluate the SymbolicExpression object using the current variable list
4. Go back to 1. and start over

In our case, quitting the program means breaking out of the loop, which eventually terminates the main() method and we are done. To check whether a parsed expression is a command or not in 3. above, we can use the isCommand() method that you implemented in Step B8. To learn what type of command in 3.1., we can rely on identity comparison using the singleton instance() method on the command classes.

In the even loop we also want to watch out for exceptions that may arise. What parts of the system throw exceptions? How should they be handled? For example, an IllegalAssignment aborts evaluation and could probably be handled just by printing an error and going around in the loop again. A parse error, on the other end, means that we are not going to get an AST, so there is no point in going on with the subsequent steps (we can simply recurse).

We should really implement evaluation so that if an expression throws an exception during evaluation, no changes to or additions of variables should be visible afterwards. There are several ways to do this, and the simplest possible way is to make a backup copy of the old variable state at the start of each loop, and restore the copy if there is an error during evaluation.

Also ponder what should happen if we get an exception that is defensive in nature, like accidentally calling eval() on a command That should not happen, and unlike IllegalAssignment that is not an error on the user side that we cannot rule out – it is a bug that we inserted. We should catch them so that the program does not die with an ugly crash, but what should we do then? Quit the program because clearly something is amiss, or simply continue asking for a next expression?

When the user quits, a nice message should be written to the terminal, and statistics of how many expressions were entered, how many were successfully evaluated, and how many could be fully evaluated, e.g., down to 42.0 as opposed to 42.0 + a.

1. Go over your backlog of cheats and dodges and see which ones need taking care of. Ideally this stack should be empty.
2. Write up the documentation of your program, any extra documentation needed because of design decisions you took or deals made with the teachers. Put this in a README.md in the top-level directory for this assignment.
3. As the first section of README.md, add instructions for how to build and run the program. Ideally, this should be as easy as make followed by make run.
4. Prepare a demonstration of z103 to give at the next lab. In addition to z103, pick another 2-3 achievements to tick off, and include these in your demonstration preparation. To back up your presentation, present evidence like places in your code where relevant things show up, documentation, paper drawings, etc. – things that support your demonstration. Think carefully about what things fit together (ask for help if you feel uncertain after trying) and what achievements tell a good story together. Make sure that not one person dominates the demonstration or answers all questions to avoid someone failing the demonstration because there was no evidence of achievements mastery.
5. Send an email to ioopm@it.uu.se with your names and usernames, a link to the GitHub repository where the code can be checked out.
6. Create a final commit for the assignment and check it into GitHub. After the normal push, add a tag assignment3_done (be careful to spell it just like that) and push the tag to the server by adding --tags to the git push command. If your partner wants to pull the tag, he or she needs to add a --tags to the git pull command, but if you were careful to have a commit which was just a tag, then having that synced is not important.
7. Optional Please take time to feedback on the assignment.

Note: Don’t expect any feedback on your program over what you have got from the oral presentations. If you want more feedback on specific things, ask questions in conjunction with your presentations, or add your name to the help list.

Questions about stuff on these pages? Use our Piazza forum.

Want to report a bug? Please place an issue here. Pull requests are graciously accepted (hint, hint).

Nerd fact: These pages are generated using org-mode in Emacs, a modified ReadTheOrg template, and a bunch of scripts.

Ended up here randomly? These are the pages for a one-semester course at 67% speed on imperative and object-oriented programming at the department of Information Technology at Uppsala University, created by Tobias Wrigstad.