Assignment U2

Assignment U2#

This assignment is restricted to using the Functional Java libraries. Please note the required minimal library version above! In everything you do, you must follow the Design Recipe. To see roughly how this assignment will be marked, check out the Skeleton Rubric.

You really really need to stick to the restrictions of Functional Java. Don’t just write Java code simply because you already know Java. The penalties in the rubric for doing so are quite harsh.

Formalities#

This assignment is submitted via GitLab.

Access to Your Repository#

In order for us to be able to collect and mark it, you need to satisfy the following conditions:

• Your repository’s name must be comp1110-2025s1-u2 (exactly), placed directly in your user namespace (the default). That is, if your uid is u1234567, the address of your GitLab project should read as https://gitlab.cecs.anu.edu.au/u1234567/comp1110-2025s1-u2.
• Your repository must have our marker bot (comp1110-2025-s1-marker) added as a Maintainer.

You can achieve both these points by creating your project through forking our template repository and not changing the name, or by just using the correct name when creating the project and then manually adding the bot.

Notebooks and Push Requirement#

You need to keep a notebook file as explained on the Git and Notebooks page. You need to commit and push the current state of your files:

• at the end of every session where you work on the assignment
• at least once per hour (our checks implement this that no two pushes during sessions recorded in the notebook are more than 70 minutes apart).
• at least once per major part of the assignment (i.e. for this assignment, at least five times). You are absolutely free to commit and/or push more often than that.

You need to write informative commit messages, and informative notes for each session in your notebook, which describe what it is that you did for this particular commit or session, respectively.

Statement of Originality#

Your submission (and therefore your git repository) needs to include a signed statement of originality. This must be a text file named soo.txt. That file must contain the following text, with the placeholders [your name here] and [your UID here] replaced with your name and UID, respectively:

I declare that this work upholds the principles of academic
integrity, as defined in the University Academic Misconduct
Rule; is entirely my own work; is produced for the purposes
of this assessment task and has not been submitted for
assessment in any other context, except where authorised in
writing by the course convener; gives appropriate
acknowledgement of the ideas, scholarship and intellectual
property of others insofar as these have been used; in no part
involves copying, cheating, collusion, fabrication, plagiarism
or recycling.

I declare that I have not used any form of generative AI in
preparing this work.

I declare that I have the rights to use and submit any assets
included in this work.

[your name here]
[your UID here]

Files Summary#

Your repository must be accessible to us and must contain the following files in its root directory:

• notebook.yml - your Notebook
• soo.txt - your signed Statement of Originality
• Recursion.java - containing your work for part 1
• Expressions.java - containing your work for parts 2-5

Code-Walk Registration#

Please use CWAC to register for a code walk. You can also use it to give time preferences for scheduling your code walk.

The deadline for registering to participate in code walks is Friday, 21 March 2025, 18:00. You need to do this in order for your assignment submission to get marked!

Tasks#

Part 1#

In a file called Recursion.java

Design the following functions:

/** 
 * Flattens a list of lists into a single list that contains
 * all the elements in the same order.
 * Examples:
 * - Given: [[1,2], [3], [], [4,5]]
 *   Expect: [1,2,3,4,5]
 */
ConsList<Integer> flattenInts(ConsList<ConsList<Integer>> lists)

/**
 * Applies a function that maps elements of a list to
 * lists themselves, and returns the flattened results
*/ 
ConsList<String> flatMapStrings(Function<String, ConsList<String>> mapper,
                                ConsList<String> strings)

/**
 * The fibonacci sequence is a sequence of natural numbers, starting
 * with 0 and 1 at indices 0 and 1, respectively. Every fibonacci
 * numbers at any successive index i is defined as follows:
 * F(i) = F(i-1) + F(i-2)
 * fibonacci(i) should return the fibonacci number for any index
 * i >= 0.
 */
int fibonacci(int i)

Follow the Design Recipe!

Common Definitions for Parts 2-5#

We know this part seems long! This is because we are giving you explicit hints for how to stage your work on it. If you want to, you can start with parts 4 and 5 right away, and implement the evaluators for parts 2 and 3 by calling the evaluator from part 4. We have also given you hints on how to significantly reduce the effort of writing tests.

In the rest of this assignment, we model extended arithmetic expressions, boolean expressions, and their evaluation to int values. The underlying data is rather complicated, but the assignment is staged, so you do not need to deal with everything at once. You will still use the same data type in parts 2-5, but you will be able to ignore many of the cases in the first two parts.

While you should use only one data definition each for all kinds of arithmetic expressions and boolean expressions, ignoring additional cases where appropriate, we will define the simplified kinds on their own first. In all definitions, we will describe their notations in examples. We/you may use the following placeholders: e for arithmetic expressions (of all kinds, which kind it is is inferred from context), b for boolean expressions, n for integer constants, and x for variable names. Each placeholder may optionally have a number attached, as in e1 or b5, to distinguish several distinct expressions/constants/names occurring in the same example. You must follow this notation in examples, and in particular, you must not forget to include the parentheses, which are important to distinguish, say ((e1 + e2) + e3) from (e1 + (e2 + e3)).

Simple Arithmetic Expressions#

A simple arithmetic expression e describes a combination of simple arithmetic operations on constant integers, and is one of:

• An integer, written 43
• A negation expresion, written (- e)
• An addition expression, written (e1 + e2)
• A subtraction expression, written (e1 - e2)
• A multiplication expression, written (e1 * e2)

The result value of evaluating such an expression is based on their regular meaning in standard arithmetic.

Boolean Expressions#

A boolean expression b describes a calculation on truth values. It may contain comparison operations on arithmetic expressions - the kind of arithmetic expressions allowed here depends on context: they are either intermediate or extended arithmetic expressions, depending on where the boolean expression is used. They are always one of:

• A value indicating truth, written as true.
• A value indicating falsity, written as false.
• A not-expression, written (! b)
• An and-expression, written (b1 && b2)
• An or-expression, written (b1 || b2)
• An equality expression, written (e1 = e2)
• A less-than expression, written (e1 < e2)

In the context of intermediate arithmetic expressions, the result value of evaluating such an expression is based on the regular rules of boolean arithmetic, and the rules of evaluation for intermediate expressions. For extended arithmetic expressions, see below.

Intermediate Arithmetic Expressions#

An intermediate arithmetic expression extends the simple expressions from before with conditional expressions, and therefore also includes boolean expressions. It is one of:

• An integer, written 43
• A negation expresion, written (- e)
• An addition expression, written (e1 + e2)
• A subtraction expression, written (e1 - e2)
• A multiplication expression, written (e1 * e2)
• A conditional expression, written (b ? e1 : e2)

The result value of evaluating such an expression is based on the regular rules of standard arithmetic and boolean arithmetic, and for conditional expressions matches the meaning of if-expressions in Java: if the boolean expression evaluates to true, then the value of the conditional expression is whatever e1 evaluates to, else it is whatever e2 evaluates to.

Extended Arithmetic Expressions#

An extended arithmetic expression is like an intermediate expression, but additionally with ways to assign variables, refer to variables, and sequence several independent expressions. It is one of:

• An integer, written 43
• A negation expresion, written (- e)
• An addition expression, written (e1 + e2)
• A subtraction expression, written (e1 - e2)
• A multiplication expression, written (e1 * e2)
• A conditional expression, written (b ? e1 : e2)
• A variable expression, written x
• An assignment expression, written (x = e)
• A sequencing expression, written (e1; e2; ... ; eN) for some N > 0

The result value of evaluating such an expression is a bit more tricky to define, because assignment expressions have effects. Intuitively, standard arithmetic expressions and boolean expressions still have the normal meaning, but evaluation order needs to follow Java’s rules: left-to-right, inside-out. This is because the value of a variable expression depends on the most recent assignment expression for the same variable in this evaluation order. If no value for a variable expression is available when we come to its turn in the evaluation order, you should return DefaultCaseError. Sequencing expressions return the value that their last expression evaluates to. All other expressions are still evaluated in order, but matter only for their effects, if any. Finally, there are exceptions from the left-to-right, inside-out scheme:

• conditional expressions first evaluate their boolean expression, and then depending on that, only evaluate the then-case or the else-case. The effects and value of the the other case are ignored.
• and-expressions are “short-circuited”, meaning that we start by evaluating the first boolean expression b1, and if it evaluates to false, then the result of the and-expression is false, and the second boolean expression does not get evaluated, and its effects and value are ignored.
• or-expressions are “short-circuited”, meaning that we start by evaluating the first boolean expression b1, and if it evaluates to true, then the result of the or-expression is true, and the second boolean expression does not get evaluated, and its effects and value are ignored.

Remember that any functions you need for the testing interface are just for us. If you do not use them anywhere, including in your tests, you do not have to write tests or documentation for them. They just need to do what they are supposd to do. We have some suggestions on how you can make writing your tests be less effort - these include uses of the testing interface to express what should happen there. You will likely want to replace those uses with your own way of doing those things, to avoid having to test and document the functions in your testing interface.

Part 2#

In a file called Expressions.java

You may not use stateful constructs for this part of the assignment!

A simple arithmetic expression is an extended arithmetic expression that only contains integers and negation, addition, subtraction, and multiplication expressions.

Design the following functions:

// [E] represents whatever data type you use to represent extended
//     arithmetic expressions

/**
 * Evaluates a simple arithmetic expression according to standard
 * rules of arithmetic. May cause a DefaultCaseError when
 * encountering any kinds of arithmetic expression that are not
 * simple, but may also return arbitrary results in those cases.
 * Evaluation should follow the same order as Java: 
 * left-to-right, inside-out
 */
int evaluateSimple([E] expr)

/**
 * Returns a String representation of the given extended arithmetic
 * expression. This follows the example notation described above,
 * and includes all cases, not just the simple ones.
 * Examples:
 * - Given: (x + 4)  Expect: "(x + 4)"
 * - Given: ((x < (y + 2)) ? x : (y + 2))  
 *   Expect: "((x < (y + 2)) ? x : (y + 2))"
 */
String toString([E] expr)

Follow the Design Recipe!

Provide the following testing interface:

/** creates an integer expression*/
[E] makeIntegerExpression(int value)
/** creates negation expression */
[E] makeNegationExpression([E] expr)
/** creates an addition expression */
[E] makeAdditionExpression([E] expr1, [E] expr2)
/** creates a subtraction expression */
[E] makeSubtractionExpression([E] expr1, [E] expr2)
/** creates a multiplication expression */
[E] makeMultiplicationExpression([E] expr1, [E] expr2)

Your own tests#

Since you are going to be writing several evaluators that are all functions from extended arithmetic expressions to integers, we recommend that you use functional abstraction for your test functions. That is, for a simple test for an arithmetic addition expression, you might write:

/** tests that the addtition expression (2 + 3) evaluates to 5 */
void testSimpleAddition(Function<[E], Integer> evaluator) {
    testEqual(5, 
      evaluator.apply(
        makeAdditionExpression(makeIntegerExpression(2), 
                               makeIntegerExpression(3))));
}

void test() {
    runAsTest(() -> testSimpleAddition(this::evaluateSimple));
}

This way, you will be able to re-use your tests for the more complex evaluation functions later.

Part 3#

In a file called Expressions.java

You may not use stateful constructs for this part of the assignment!

An intermediate arithmetic expression is an extended arithmetic expression that does not contain variable expressions, assignment expressions, or sequencing expressions. This means that conditional expressions and boolean expressions are now included.

Design the following functions:

// [E] represents whatever data type you use to represent extended 
//     arithmetic expressions
// [B] represents whatever data type you use to represent boolean
//     expressions

/**
 * Evaluates and intermediate arithmetic expression according to
 * standard rules of arithmetic and boolean arithmetic. May cause a 
 * DefaultCaseError when encountering any kinds of arithmetic
 * expression that are not intermediate, but may also return arbitrary
 * results in those cases.. Evaluation should follow  the same order
 * as Java: left-to-right, inside-out, with the exceptions of 
 * conditional expressions and and- and or-expressions.
 */
int evaluateIntermediate([E] expr)

Follow the Design Recipe!

Provide the following additional parts of the testing interface:

/** creates a conditional expression */
[E] makeConditionalExpression([B] condExpr,
                              [E] thenExpr,
                              [E] elseExpr)
/** creates a "true" boolean expression */
[B] makeTrueBoolExpression()
/** creates a "false" boolean expression*/
[B] makeFalseBoolExpression()
/** creates a negation boolean expression */
[B] makeNotBoolExpression([B] boolExpr)
/** creates an equality comparison boolean expression */
[B] makeEqualBoolExpression([E] expr1, [E] expr2)
/** creates a less-than comparison boolean expression */
[B] makeLessThanBoolExpression([E] expr1, [E] expr2)
/** creates an and-expression */
[B] makeAndBoolExpression([B] boolExpr1, [B] boolExpr2)
/** creates an or-expression */
[B] makeOrBoolExpression([B] boolExpr1, [B] boolExpr2)

Your own tests (continued)#

To illustrate what we were suggesting about tests above, here is how you would reuse the addition test from before for evaluateIntermediate.

/** tests that the addtition expression (2 + 3) evaluates to 5 */
void testSimpleAddition(Function<[E], Integer> evaluator) {
    testEqual(5, 
      evaluator.apply(
        makeAdditionExpression(makeIntegerExpression(2),
                               makeIntegerExpression(3))));
}

void test() {
    runAsTest(() -> testSimpleAddition(this::evaluateSimple));
    runAsTest(() -> testSimpleAddition(this::evaluateIntermediate));
}

Note that you will still need to write some new tests for evaluateIntermediate that test the behavior of the new constructs.

Part 4#

In a file called Expressions.java

You may not use stateful constructs for this part of the assignment!

Now we get to the full power of our expressions, by expanding evaluation to the last:

• Variable expressions evaluate to the current value that the given variable is assigned to. If a variable expression is evaluated when the variable has not been assigned a value, then a DefaultCaseError should be returned.
• Assignment expressions change that value for any subsequently evaluated expressions - as such, they have effects. The result of an assignment expression is the new value of the given variable, i.e. the result of evaluating the inner expression.
• Sequencing expressions evaluate all expressions in a non-empty list in order. While the effects of those expressions matter, their results are ignored, except for the last expression. The result of the last expression becomes the result of the sequencing expression.

In a first attempt, you will model state explicitly, via a ConsList-based Map that associates variables with their currently assigned values. Your evaluation function may be called with a dictionary that already has some variables assigned - this is fine, and you can use those values. For testing, we suggest to always call the evaluation function with an empty dictionary. We give details on how to best call your testing functions below.

Design the following function:

/**
 * Evaluates the given arithmetic expression under the given
 * variable assignments, and returns a pair of the result
 * of the arithmetic expression and the variable assignments
 * after evaluating any assignment expressions contained
 * within the given expression.
 */
Pair<Integer, ConsList<Pair<String, Integer>>> evaluateFunctional(
    [E] expr, ConsList<Pair<String, Integer>> variableAssignments)

Follow the Design Recipe!

The dictionary passed as an argument and returned as the second item of the returned pair represents variable assignments. The dictionary that is returned should be based on the one that was given as an argument, but may be a new version with updated (or newly inserted) values for variables that were assigned some new value as part of evaluating the given expression.

Don’t try to do everything in one complex function! Write helper functions!

Provide the following additional parts of the testing interface:

/** creates a variable expression */
[E] makeVariableExpression(String name)
/** creates an assignment expression */
[E] makeAssignmentExpression(String variableName, [E] expr)
/** creates sequencing expression */
[E] makeSequencingExpression(ConsList<[E]> exprs)

Your own tests (continued)#

Since evaluateFunctional now has an extra argument and return value, for using our old testing functions, we need to abstract them away. This is easily done with another lambda expression:

/** tests that the addtition expression (2 + 3) evaluates to 5 */
void testSimpleAddition(Function<[E], Integer> evaluator) {
    testEqual(5, 
      evaluator.apply(
        makeAdditionExpression(makeIntegerExpression(2),
                               makeIntegerExpression(3))));
}

void test() {
    runAsTest(() -> testSimpleAddition(this::evaluateSimple));
    runAsTest(() -> testSimpleAddition(this::evaluateIntermediate));
    runAsTest(() -> 
      testSimpleAddition(
        expr -> evaluateFunctional(expr, MakeConsMap()).first()));
}

Note that you will still need to write some new tests for evaluateFunctional that test the behavior of the new constructs.

Part 5#

In a file called Expressions.java

You must use appropriate stateful constructs for this part of the assignment!

Having to always return a pair of the result of the evaluation with the new variable state is somewhat cumbersome. Since we clearly have a shared variable here, let’s make it explicit in a variant of evaluateFunctional that instead uses a stateful map.

Design the following function:

/**
 * Evaluates the given arithmetic expression under the given
 * variable assignments, and returns the result of the
 * evaluation, having modified the given map according to
 * any variable assignments contained in the expression.
 */
int evaluateStateful([E] expr, 
                     Map<String, Integer> variableAssignments)

Follow the Design Recipe!

The testing interface is the same as for the previous part, as is the trick to re-use your tests from before, with the slight twist that you do not need to access a value of a pair:

/** tests that the addtition expression (2 + 3) evaluates to 5 */
void testSimpleAddition(Function<[E], Integer> evaluator) {
    testEqual(5, 
      evaluator.apply(
        makeAdditionExpression(makeIntegerExpression(2),
                               makeIntegerExpression(3))));
}

void test() {
    runAsTest(() -> testSimpleAddition(this::evaluateSimple));
    runAsTest(() -> testSimpleAddition(this::evaluateIntermediate));
    runAsTest(() -> 
      testSimpleAddition(
        expr -> evaluateFunctional(expr, MakeConsMap()).first()));
    runAsTest(() -> 
      testSimpleAddition(
        expr -> evaluateStateful(expr, MakeHashMap())));
}

Updates#