VisiCalc reconstructed

Spreadsheets rule the world for almost half of a century. I strongly believe that it’s one of the best UXs ever created. Being fairly minimal and easy to learn, it allows users to quickly manipulate data, describe logic, visualise results, or even create art and run GameBoy games.

It all started in 1979 when Dan Bricklin and Bob Frankston created VisiCalc, the first spreadsheet software. With a few thousand lines of hand-written 6502 assembly, VisiCalc could successfully run on 16K RAM machines. It quickly became a “killer app” for Apple ][, selling over 1 million copies and turning early personal computers into serious business tools.

I thought it would be an interesting exercise trying to rebuild minimal VisiCalc clone from scratch. All we need is a data model, formula evaluator, and a simple UI to display the cells.

Cells

Like almost everything in life, a spreadsheet is made of cells. Each cell can contain a value, a formula, or be empty. Values can be numbers or text. Formulas are basic mathematical expressions that can reference other cells. You all know it from Excel, but in VisiCalc formula prefix was usually + instead of =, for example +A1+A2*B1 is a formula, while A1 is a text value.

#define MAXIN 128 // max cell input length
enum { EMPTY, NUM, LABEL, FORMULA }; // cell types
struct cell {
    int type;
    float val;
    char text[MAXIN]; // raw user input
};

A spreadsheet itself is a grid of cells. Excel has limits of 1,048,576 rows and 16,384 columns, VisiCalc had 256 rows and 64 columns. We can start even smaller:

#define NCOL 26 // max number of columns (A..Z)
#define NROW 50 // max number of rows
struct grid {
    struct cell cells[NCOL][NROW];
};

Formulas

Now we need to implement formula evaluator. We can use a simple recursive descent parser that calculates the formula on the fly. Since formulas might contain references, a parser should be aware of the grid and be able to fetch values from it.

We start with a classical top-down parser structure: top-level expressions are parsed as terms separated by + or -, terms are parsed as factors separated by * or /, and factors are parsed as primitives, such as numbers, cell references, function calls, or parenthesised expressions:

float primary(struct parser* p) {
    skipws(p);
    if (!*p->p) return NAN;
    if (*p->p == '+') p->p++;
    if (*p->p == '-') {
        p->p++;
        return -primary(p);
    }
    if (*p->p == '@') {
        p->p++;
        return func(p);
    }
    if (*p->p == '(') {
        p->p++;
        float v = expr(p);
        skipws(p);
        if (*p->p != ')') return NAN;
        p->p++;
        return v;
    }
    if (isdigit(*p->p) || *p->p == '.') return number(p);
    return cellval(p);
}

We use NAN to indicate errors. Cell references are parsed using a simple function that converts column letters to numbers and row digits to numbers.

Recalculation

Having expression evaluator brings the core functionality to the spreadsheet, but it’s not enough due to reactive nature of calculations. A cell may contain a formula that references other cells, and when those cells change, the formula should be re-evaluated.

VisiCalc made it work for 16K RAM machines using a simpler trick. On every cell update it re-evaluated the whole spreadsheet. User was free to choose row-first or column-first evaluation order. VisiCalc manual suggested to run it a few times, until all the dependencies are resolved.

We can afford automating it, running evaluation for a few iterations, until no new changes are detected:

void recalc(struct grid* g) {
    for (int pass = 0; pass < 100; pass++) {
        int changed = 0;
        for (int r = 0; r < NROW; r++)
            for (int c = 0; c < NCOL; c++) {
                struct cell* cl = &g->cells[c][r];
                if (cl->type != FORMULA) continue;
                struct parser p = {cl->text, cl->text, g};
                float v = expr(&p);
                if (v != cl->val) changed = 1;
                cl->val = v;
            }
        if (!changed) break;
    }
}

Now we can add a setter function that updates the cell value and triggers recalculation, determining if the input is a formula, a number, or a label based on the first character.