Exercise 1: Design and Programming

This exercise will help you practice and demonstrate your ability to solve design problems using combinations of techniques based on polymorphism and composition. You will be presented with a small number of tasks to perform that involve interacting with existing code and implementing solutions in the face of design constraints. All tasks in this exercise use C++. A template including both the provided code and locations for your solutions can be found here. The template includes build instructions using cmake. You can clone the repository with:

git clone https://github.com/nsumner/se-design-template.git

Make sure that your build directory is not inside of the project directory before submitting. You should be using out of source builds.

Note: In performing these tasks you will modify libraries in very specific files of the exercise. Any modifications that you make to other files will be ignored during grading, so you should only modify the specified files. All solutions should be able to run in CSIL. In reality, any up to date Linux distribution (or WSL in Windows) should suffice, but CSIL is the standard. Use of external libraries and code other than the standard library is explicitly prohibited. You are expected to use CMake 3.19 or greater and should use a compiler supporting C++ 20.

Working in CSIL

The default software in the CSIL lab is older than what we want. I have made more recent versions of software used for assignments available in CSIL. You can get access to them by running the following before working:

source  /usr/shared/CMPT/faculty/wsumner/base/env745/bin/activate

This activates the underlying virtual environment thats makes more recent software for the course available. You can exit the virtual environment by running:

deactivate

You can add this first line to the end of your ~/.bashrc configuration file to enable the environment automatically when you log in (if you so choose).

Task 1

A simple tree data structure representing mathematical expressions over constants and named variables has been provided in the ExprTree.h header at the path lib/expr-tree/. An expression tree represents operations over values and recursive expressions. An internal node of the tree corresponds to a mathematical operator like + or -. Leaves in the tree correspond to either literal integral values like 3, 5, and 42. For instance, the expression (2 * 3) + 4 would have the tree:

Examine the provided tree API. Your first task is to add several new behaviors for expression trees without modifying the expression tree API. All behaviors should be implemented within the expr-ops library in lib/expr-ops/.

• Behavior 1. In a new function called evaluate, you should compute the value of the expression represented by the tree. Observe that the function takes as arguments a tree and an Environment. The value of a literal is its represented value. The value of a symbol is determined by the Environment. The value of an operation is computed by applying the respective operation on the values of the children. Note that a symbol may be undefined. Similarly, division by 0 is undefined. An operation involving undefined values is itself undefined. Undefined values can be represented by an empty std::optional.
• Behavior 2. In a new function called countSymbols, you should compute how many times each specific symbol name occurs in the tree. For the expression x * x + y, the resulting map should contain {x: 2, y: 1}.
• Behavior 3. In a new function called countOps, you should compute how many times each specific operator kind occurs within an expression.

Extra (not for credit, but pretty easy)

• Implement a new function canZero that returns true iff the underlying expression could evaluate to 0 for some environment. What could this be used for?
• Congratulations, you have written an interpreter. What is its performance like? Can you make it faster?

Task 2

Analyzing the content of data structures can aid in understanding their structure and even help in tasks like profiling that we will explore in the future. In this task, you will write a general function traverse that can take in graph data structures and traverse them via a preordered depth first search. The function should have the potential to work with any graph structure and should not require modifying that structure. You should specifically implement support for traversing a std::list linked list as well as the expression trees from the previous task.

A basic template has been provided for you in the Traversal.h header of the traversal library in lib/traversal/.

The traverse function should have one and only one definition in order to receive credit. It should take three arguments: (1) the graph in question, (2) a function called on each node in the graph, and (3) a function called on each edge of the graph (as denoted by the source and the target nodes of the edge). What a "node" is may differ from graph to graph but should be configurable. For std::list, a node may be the iterator to the exact contents of the list node, and for an ExprTree, a node may be an Expression node in the tree. You may assume that you can construct hashes in some way from nodes of graphs that are passed in.

Note the constraints at play in this problem. You may not modify the original graph structures. You also may not use inheritance (except perhaps to define a new visitor subclass for the ExprTrees).

Extra

Now that you have general purpose graph traversal, you can implement general purpose and automated visualization of data structures using the DOT language supported by systems like Graphviz. This can be invaluable when debugging complex systems or profiling data structure contents and behavior.

Testing Your Code

Some tests have been provided to you within the test/ directory of the project. The tests use the libraries that you wrote along with the doctest testing infrastructure in order to test some simple behaviors of your code. Additional/alternative tests may be used during grading. You may find it useful to write additional tests yourself. The tests that are provided to you should be able to pass with your implementations.

You can run tests in a Linux shell through the test target of build system, e.g. make test. You can get more detailed results from the doctest framework by running the individual test programs inside the tests/ subdirectory of the build directory.

Submitting

Upload your ExprOps.cpp and Traversal.h files to CourSys as respective submission components for Exercise 1.