Project 1
Due: Sep 23 by 11:59p
Important Reminder: As per the course Academic Honesty Statement, cheating of any kind will minimally result in your letter grade for the entire course being reduced by one level.
This document first provides the aims of this project followed by the necessary background. It then lists the requirements as explicitly as possible. This is followed by a log which should help you understand the requirements. Finally, it provides some hints as to how those requirements can be met.
Aims
The aims of this project are as follows:
To ensure that you have set up your VM as specified in the VM Setup and Git Setup documents.
To get you to write a non-trivial JavaScript program.
To allow you to familiarize yourself with the programming environment you will be using in this course.
To make you design an in-memory indexing scheme.
To expose you to the power of recursive programming.
To introduce you to Test-Driven Development TDD.
Background
This project involves building the internals of a spreadsheet with all data stored entirely in memory.
The reasons spreadsheets are extremely popular include:
An intuitive GUI.
An intuitive model of computation which just works. This model is so intuitive that non-programmers use it without realizing that they are programming.
In this project, we will concentrate on (2).
Visually, a spreadsheet is identified by a grid of cells with each cell identified by its column and row coordinates. The column coordinate is specified by a letter a, b, \(\ldots\), z while the row coordinate is specified by an integer 1, 2, \(\ldots\), 99. So the first cell would have coordinates a1 and the last cell would have coordinates z99.
The model of computation behind spreadsheets is data-driven programming. The computation is driven entirely by the dependencies within the data rather than some predetermined order. So if a change is made to a particular spreadsheet cell \(c\), then that change is automatically propagated to all other cells which depend directly or indirectly on \(c\).
Assuming no cyclic dependencies, a spreadsheet can use a Directed Acyclic Graph or DAG to maintain the dependencies between its data cells. The use of a DAG will minimize the computation necessary to respond to a data change.
The following sequence of diagrams show how the DAG evolves in response to updates made to a spreadsheet:
A cell a1 is given a constant value.
We can add a formula referring to a cell b1 which has not yet been given a value because the value of a cell defaults to 0.
In the above figure, cell a2 is dependent on cells a1 and b1 while cells a1 and b1 are prerequisites for cell a2.
When we actually define b1, a2 is automatically updated because a2 is dependent on b1.
We can extend the dependency chains to a new cell a3:
When we change a1, those changes are propagated to all its direct and indirect dependencies.
Besides the underlying DAG, another aspect of spreadsheets worth noting is the location independence of formula; i.e. a formula can be copied from one cell to another and doing so will adjust the cell references in the formula. So for example, if the above formula a3 = a1 + a2 is copied over to cell c5, then it would be adjusted to c5 = c3 + c4.
In some situations, this adjustment is not desired. This can be specified by preceeding the corresponding coordinate by a $ to fix that coordinate. For example, if the formula f2 = e5 + $e3 + e$4 + $e$6 is copied over to g7, the copied formula would be g7 = f10 + $e8 + f$4 + $e$6,
Requirements
You must push a submit/prj1-sol directory to your master branch in your github repository such that typing ./index.mjs within that directory is sufficient to run your project.
You are being provided with an index.mjs and cli.mjs which provide the required input-output behavior. You are also being provided with a parser which can parse spreadsheet formulae. What you specifically need to do is add code to the provided spreadsheet.mjs source file as per the requirements in that file.
Additionally, your submit/prj1-sol must contain a vm.png image file to verify that you have set up your VM correctly. Specifically, the image must show an x2go client window running on your VM. The captured x2go window must show a terminal window containing the output of the following commands: