Building a Spreadsheet Engine from Scratch

When my university group project for the PROP (Programming Projects) subject landed on "implement a spreadsheet", my first reaction was how hard can it be? You have cells, you have formulas, you click and stuff updates. Right?

Four weeks later I had a working spreadsheet engine with its own formula language, a dirty-propagation dependency graph, a JFlex/Bison-generated parser, and a standard library that included fold, covariance, and a pipe operator that looked suspiciously like Unix. So: harder than I thought, and also much more interesting.

This post is about how that engine worked under the hood.

What we were building

The project (internally called subgrup-prop2-4) is a Java spreadsheet application — a simplified Excel. You get a grid of cells, you can type values or formulas into them, and when a cell changes all the cells that depend on it automatically recompute.

On top of that we wrote our own formula language — not Excel's =SUM(A1:A5) dialect, but something more like a tiny functional language with first-class functions, vectors, and an operator system that compiles operators down to function calls.

Here is the high-level architecture, split into the classic three layers Java university projects always end up with (domain, data, presentation):

┌──────────────────────────────────────────────────────┐
│  Presentation (Swing GUI + script editor)            │
├──────────────────────────────────────────────────────┤
│  Domain: Full (sheet) → Cella (cell) → Expressio     │
│           ExprEvaluator + CallServer chain           │
├──────────────────────────────────────────────────────┤
│  Data: serialisation to .zip archives (JSON)         │
└──────────────────────────────────────────────────────┘

The interesting part is the domain layer, so that's mostly what we'll look at.

Step 1: Parsing the formula

Every cell stores a string — what the user typed. When the user writes =A1+B2*3 and presses Enter, that string has to become something the engine can evaluate. The classic tool for this is a lexer + parser pair.

We used JFlex for the lexer and GNU Bison (in Java output mode) for the parser. The lexer (lang.l) tokenises the input into numbers, identifiers, operators, and string literals:

NUM        = [0-9]+ ("." [0-9]+)?
IDENTIFIER = [:jletter:] [:jletterdigit:]* ("." [:jletterdigit:]+)?

The grammar (lang.y) then describes how tokens combine into an expression tree. The core rule is that everything is either a constant, a variable, a cell reference, a function call, or a vector:

expression: constant
          | variable
          | reference
          | function
          | vector
          | '(' expression ')'

A reference is any cell address prefixed with #. The # is the grammatical signal that says "I want the value from the grid, not a local variable":

reference : '#' IDENTIFIER            -- single cell, e.g.  #A1
reference : '#' IDENTIFIER ':' IDENTIFIER  -- range, e.g.  #A1:B5

A function call is just a name followed by a tuple of arguments in parentheses:

function: functionName svector          -- e.g.  avg(#A1:A5)
        | expression '+' expression     -- e.g.  3 + #B2
        | expression IDENTIFIER expression  -- infix operator syntax

That last rule is where things get interesting.

Step 2: Operators are just functions in disguise

In most languages, + is a built-in primitive. In our formula language, + is syntax sugar for a function call. The standard library file (lib.expr) defines what each operator means:

x + y = x sum y
x * y = x mul y
x / y = x div y
x - y = x sub y
x > y = x gt y

So when the parser sees A + B, it produces a Funcio node (function call node) with name "+" and arguments [A, B]. At evaluation time, "+" gets looked up in the function registry, and the engine finds the definition x + y = x sum y — so it calls sum(x, y), which is a native Java operation.

This means adding new infix operators is just adding a line to lib.expr. The parser never needs to change. The pipe operator, for example:

in | out = out $ in

This makes value | functionName work like a Unix pipe: it calls functionName(value). You can chain them:

write("A1:A5", between(5)) -> write("B1:B5", between(5))

The -> operator means "evaluate left, if it didn't error then evaluate right" — essentially sequencing side effects. The <- operator goes the other way and returns the left side after writing:

A <- B = (B write A) ; A

It reads like assignment: A gets B. What it actually does is call write(A, B) (which updates the grid) and then evaluates A as the result.

Step 3: The expression tree

After parsing, the formula lives as an abstract syntax tree (AST). Every node is a subclass of Expressio:

public abstract class Expressio {
    public abstract Constant eval(ExprEvaluator ctx, TVector args);
    public abstract Expressio[] getChildren();
    // ... serialisation, reference traversal, etc.
}

The concrete subclasses are:

To evaluate the tree you call root.eval(ctx, args). Each node evaluates its children recursively and combines the results. A Funcio node evaluates all its arguments first, then looks up the function name in a chain of call servers:

public Constant eval(ExprEvaluator ctx, TVector args) {
    if (name.equals("if")) {
        // special case: lazy evaluation (only evaluate one branch)
        boolean cond = ((TBool) arguments.get(0).eval(ctx, args)).isTrue();
        return cond
            ? arguments.get(1).eval(ctx, args)
            : arguments.get(2).eval(ctx, args);
    }
    return ctx.callFunction(name, (TVector) arguments.eval(ctx, args));
}

The if function is the only one hardcoded like this, because both branches can't be evaluated eagerly (imagine if(x > 0, x, error()) — you don't want to evaluate error() when x = 5). Every other language with this problem punts to macros or special forms. We just added an if-check inside Funcio.eval. It works fine for a spreadsheet.

Step 4: The function call chain

When ctx.callFunction("avg", args) is called, the evaluator tries a chain of CallServer implementations in order until one returns a non-error result:

NullFunctionServer       ← always returns error (terminal)
ExprFunctionServer       ← functions defined in lib.expr or by the user
InternalFunctionServer   ← Java reflection: calls methods on the first argument
JavaFunctionServer       ← manually registered Java lambdas
ReflectionFunctionServer ← registered Java types exposed to the language
ZipFunctionServer        ← element-wise application over two vectors
MapFunctionServer        ← apply a function to each element of a vector
UnaryMapFunctionServer   ← apply to a single vector

The InternalFunctionServer is sneaky — it uses Java reflection to check whether the first argument has a method named after the function being called. So if you call sort(someVector), it calls TVector.sort() automatically. This is how all the built-in vector/string operations work without being explicitly registered: the method just needs to exist on the Constant class.

The ExprFunctionServer is where lib.expr lives. Every function defined there is parsed at startup and registered as a FunctionDefinition:

avg(X) = fold("+", X) / count(X)

This stores the expression fold("+", X) / count(X) as a Funcio tree, with X mapped to argument index 0. When avg is called with a vector, X in the tree is substituted for the actual argument before evaluation.

Step 5: The dependency graph

Here is the part that makes spreadsheets feel live: when you change a cell, every cell that references it — directly or transitively — needs to recompute.

Each Cella (cell) maintains two lists:

private ArrayList<CellCoord> watchCells;      // cells I depend on
private ArrayList<CellCoord> watchedByCells;  // cells that depend on me

When a cell's formula is updated, the engine first unregisters all old watchers (in case the formula changed and now references different cells), then walks the new expression tree to collect all Reference nodes, and registers the new watchers:

// Unregister old
for (CellCoord old : cell.getRegisteredCells())
    getCellaAt(old).unregisterWatch(cell);

// Set the new expression
cell.modificarExpressio(newExpr);

// Register new — traverse the expression tree for #CellRef nodes
for (CellCoord dep : newExpr.getReferenceCoordinates())
    getCellaAt(dep).registerWatch(cell, myCoord, dep);

After updating, sendModifyNotification propagates a dirty flag upward through the watchedByCells graph:

private void sendModifyNotification(CellCoord coord) {
    Cella cell = getCellaAt(coord);
    cell.setDirty();
    pendingForUpdate.add(coord);
    for (CellCoord parent : cell.getWatchedByCells()) {
        sendModifyNotification(parent);  // recursive
    }
}

A dirty cell's cached value is thrown away. The next time the view asks for updates, every cell in pendingForUpdate is re-evaluated and a CellaUpdate event is sent to the GUI. The evaluation is lazy in the sense that cells only recompute when queried, not immediately on every keystroke.

Live demo: see the graph in action

Here is an interactive version of the dependency graph. The left side is a tiny 4x4 spreadsheet (use cell names like A1, B2, formulas start with =). The right side draws the dependency graph — blue nodes have formulas, plain nodes have raw values. When you change a cell, its dependents flash red to show the dirty propagation.

Try the presets to load some interesting dependency patterns. The Stats preset shows a mean + variance calculation — the kind of thing where you have a column of data, one cell computes the mean, four cells compute squared deviations from that mean, and a final cell sums and divides. Change one data point and watch the whole chain cascade.

The standard library

Once the language exists, you can bootstrap a lot of functionality purely inside lib.expr without touching Java. The most useful trick is fold, which reduces a vector with a binary operator:

foldi(op, X, n) = if((count(X) - 1) > n,
                     op $ (X get n, foldi(op, X, n + 1)),
                     X get (count(X) - 1))

fold(op, X) = if(count(X) equals 0, X, foldi(op, X, 0))

$ is the function application operator (f $ args = call f with args). With fold you get the rest for free:

vsum(x) = fold("+", x)       -- sum of a vector
avg(X)  = fold("+", X) / count(X)

Boolean logic is also entirely bootstrapped. true and false are just numbers:

true()  = 2 gt 0    -- 2 > 0, evaluates to true
false() = 0 gt 2    -- 0 > 2, evaluates to false
not(T)  = if(T, false(), true())
or(A,B) = if(A, true(), if(B, true(), false()))
and(A,B) = nor(nor(A,A), nor(B,B))   -- De Morgan's law encoded in combinators

This is basically how early LISP worked — and it's the same reason LISP functions look the way they do.

Statistics functions build on avg and fold:

variance(X) = fold("+", pow(Math.abs(X - avg(X)), 2)) / (count(X) - 1)
sd(X)       = sqrt(variance(X))
covariance(X,Y) = fold("+", (X - avg(X)) * (Y - avg(Y))) / (count(X) - 1)
corr(X,Y)   = covariance(X,Y) / (sd(X) * sd(Y))

That X - avg(X) expression works on an entire vector because the ZipFunctionServer and MapFunctionServer in the call chain automatically lift binary operations to element-wise vector operations. So (X - avg(X)) maps subtraction across all elements of X, each minus the scalar avg(X). No special syntax needed.

The Fibonacci trick

One of the test cases was computing Fibonacci numbers using matrix-vector multiplication. The script stored in the spreadsheet file looked roughly like this:

write("D3:D4", ((1,1),(0,1)) matmul (#D3,#D4))

Where matmul was a user-defined function in the script pane. Running the script once advances the Fibonacci sequence by one step. Running it 50 times gives you F(51) and the golden ratio D3/D4 converges to (sqrt(5)+1)/2 within 1e-8.

This wasn't a planned feature — it emerged naturally because the language happened to be expressive enough to encode it. Functions can be defined in a script panel and called from cell formulas. The spreadsheet doubles as a REPL for a small functional language, which is both useful and slightly alarming.

What I learned

The three things I would not have guessed going in:

Parsing is the easy part. JFlex + Bison generates a working parser in a day. The hard parts are: what happens when the user types garbage (error recovery), making sure function arity is checked at the right layer, and keeping the serialisation format stable when you add new expression types.

Dependency tracking is subtle. The obvious approach is "when any cell changes, recompute everything". That works for small grids but falls apart at scale. The register/unregister watcher pattern is more complex to implement but it means only the actually-affected cells get touched. The tricky case is when a formula changes and references different cells than before — you need to unregister the old edges first or you end up with stale dependencies.

Bootstrapping functions in the language itself is addictive. Once fold existed, I kept finding things I could build on top of it without writing Java. avg led to variance, which led to covariance and corr. The language became genuinely useful for data analysis — which was not the original goal. I now understand why Lisp programmers keep insisting their language is extensible: once the primitives are right, you can grow the language from inside itself.

The project lives at the usual university archive level of polish (some Catalan comments, a few TODO stubs, a class literally named Cella), but the expression evaluator and dependency graph are solid. If I were to build it again I'd look at something like Topological sort for directed acyclic graphs to replace the brute-force multi-pass evaluation, and I'd add cycle detection — circular references (A1 = =A1 + 1) currently loop until the stack overflows, which is one of those bugs you find by accident.

The code for this project (along with five others from PROP) is available in the research archives linked on the Academic page.