Milestone 1: Model

In this first milestone, you'll develop the model of your spreadsheet. A model is the set of abstractions that represent the core structures of an application. Models are meant to be separate from any particular user interface, making them reusable and easy to test. In the case of your spreadsheet, your model is a set of abstractions representing a two-dimensional grid of cells and formulas and data that can go in the cells.

Your spreadsheet will eventually have its own programming language for expressing formulas. Milestone 2 is about lexing, parsing, and translating that language into an executable form. This milestone doesn't touch on the language itself, but it does have you build the abstractions that your someday interpreter will use to build and evaluate abstract syntax trees. You'll design the interface for this grid in milestone 3—with hopefully no changes to the model.

Expression Hierarchy

A model of a program is built out of abstractions for assignment statements, conditionals, loops, the many different kinds of expressions, and so on. For this milestone, write abstractions for these expression structures:

• Five primitives: integer, float, boolean, string, cell address, and null.
• Seven arithmetic operations: addition, subtraction, multiplication, division, modulo, exponentiation, negation.
• Three logical operations: and, or, not.
• Cell lvalues: a pair of column and row expressions that yields an address primitive when evaluated.
• Cell rvalues: a pair of column and row expressions that yields the value at its address when evaluated.
• Six bitwise operations: and, or, xor, not, left shift, and right shift.
• Six relational operations: equals, not equals, less than, less than or equal to, greater than, and greater than or equal to.
• Two casting operators: float-to-int, to int-to-float.
• Four statistical functions: max, min, mean, and sum.

Implement these following the pattern discussed in lecture.

Translater

Implement a visitor that translates an AST into some other language. Follow the pattern shown in lecture.

Evaluator

Implement a visitor that evaluates an AST down to a primitive node. Follow the pattern shown in lecture. Typecheck each operation and raise exceptions when the operation cannot be performed.

Grid

Some of the operations, like cell rvalues and statistical functions, need to access other cells. That means you need to store the cells in some sort of collection. Define a grid abstraction that manages all the cells. Choose a data structure that makes sense to you. Model each cell as a bundle of three pieces of state:

• a string representing the cell's source code (which will only be used in later milestones)
• an abstract syntax tree of the cell's program
• the model primitive that the tree most recently evaluated to

Give the grid the following operations:

• A setter that accepts a cell address and an abstract syntax tree to store at that cell. It evaluates the tree and stores its model primitive.
• A getter that accepts an address and returns the cell's model primitive.

Runtime

Define a Runtime abstraction to manage an executing program's runtime environment, as discussed in lecture. Have it hold also hold a reference to the grid so that you can evaluate cell rvalues. If an cell is reference, raise an error that you can catch later on.

Submission

To submit your milestone, follow the instructions. In particular, do these three things:

• Submit your project to the official GitHub repository that your instructor made for you.
• Record a 3–5 minute screencast of you walking through your code and commenting on it. Do not exceed 5 minutes. Your instructor has many videos to watch. Post it to Canvas Studio according to the instructions.
• Complete the ready date submission form on Canvas.

In your video, demonstrate adding several expressions to a grid and serializing and evaluating them. Include at least these expressions that are expressed in a hypothetical syntax:

• Arithmetic: (7 * 4 + 3) % 12
• Arithmetic negation and cell rvalues: #[3, 1] * -#[2, 1]
• Rvalue lookup and shift: #[1 + 1, 4] << 3
• Rvalue lookup and comparison: #[0, 0] < #[0, 1]
• Logic and comparison: !(3.3 > 3.2)
• Double negation: --(6 * 8)
• Bitwise operations: ~5 | ~8
• Sum: sum([1, 2], [5, 3])
• Mean: mean([1, 2], [5, 3])
• Min: min([1, 2], [5, 3])
• Max: max([1, 2], [5, 3])
• Casting: float(7) / 2

The syntax is just an example. You'll be building trees manually out of your model classes. #[...] is a cell rvalue, and [...] is a cell lvalue. Ensure that evaluating these produces the correct results. Show also some expressions that fail to typecheck.

Show also some programs that fail to typecheck. Include these three expressions and others of your own crafting:

• 7.5 << 2
• true >= 10
• "fooo" / 3

In your video, don't comment on or show every single line of code in your video. Select a few representative snippets. Do comment on programming language ideas that interest you or challenged you. If you use a language feature, algorithm, or data structure not discussed in class, as is likely if you use an LLM for assistance, you must explain how each deviation works and why it is better. If you do not include these explanations, your submission will not be accepted.

Be prepared to explain any code that you submit during the code review.