I also implemented a spreadsheet last year [0] in pure TypeScript, with the fun twist that formulas also update backwards. While the backwards root finding algorithm was challenging, I also found it incredibly humbling to discover how much complexity there is in the UX of the simple spreadsheet interface. Handling selection states, reactive updates, detecting cycles of dependency and gracefully recovering from them is a massive state machine programming challenge! Very fun project with a lot of depth!
I myself didn't hand roll my own parser but used Ohm-js [1] which I highly recommend if you want to parse a custom language in Javascript or TypeScript.
> One way of doing this is to keep track of all dependencies between the cells and trigger updates when necessary. Maintaining a dependency graph would give us the most efficient updates, but it’s often an overkill for a spreadsheet.
On that subject, figuring out the efficient way to do it is also a large engineering challenge, and is definitely not overkill but absolutely required for a modern spreadsheet implementation. There is a good description of how Excel does it in this famous paper "Build systems a la carte" paper, which interestingly takes on a spreadsheet as a build system [2].
#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
};
#define NCOL 26 // max number of columns (A..Z)
#define NROW 50 // max number of rows
struct grid {
struct cell cells[NCOL][NROW];
};
I doubt that 171 KB of static allocation would fly on an Apple II! I do wonder how they did memory allocation, it must have been tricky with all the fragmentation.
According to Bob Frankston, Bricklin's co-founder[1]:
> The basic approach was to allocate memory into fixed chunks so that we wouldn't have a problem with the kind of breakage that occurs with irregular allocation. Deallocating a cell freed up 100% of its storage. Thus a given spreadsheet would take up the same amount of space no matter how it was created. I presumed that the spreadsheet would normally be compact and in the upper left (low number rows and cells) so used a vector of rows vectors. The chunks were also called cells so I had to be careful about terminology to avoid confusion. Internally the term "cell" always meant storage cell. These cells were allocated from one direction and the vectors from the other. When they collided the program reorganized the storage. It had to do this in place since there was no room left at that point -- after all that's why we had to do the reorganization.
> The actual representation was variable length with each element prefixed by a varying length type indicator. In order to avoid having most code parse the formula the last by was marked $ff (or 0xff in today's representation). It turned out that valid cell references at the edges of the sheet looked like this and created some interesting bugs.
It leaves out a lot of details - if you're skimping enough you could allocate variable length row vectors, but it seems they wanted to avoid variable length allocations, in which case you could start with a 255 byte array pointing to which subsequent equal-sized chunk represents each in-use row. You'd need at most 126 bytes per row in actual use to point into the chunks representing the cell contents. But this is just guesses.
> Since the formulas did depend on each other the order of (re)calculation made a difference. The first idea was to follow the dependency chains but this would have involved keeping pointers and that would take up memory. We realized that normal spreadsheets were simple and could be calculated in either row or column order and errors would usually become obvious right away. Later spreadsheets touted "natural order" as a major feature but for the Apple ][ I think we made the right tradeoff.
It would seem that the creators of VisiCalc regarded this is a choice that made sense in the context of the limitations of the Apple ][, but agree that a dependency graph would have been better.
Edit: It's also interesting that the tradeoff here is put in terms of correctness, not performance as in the posted article. And that makes sense: Consider a spreadsheet with =B2 in A1 and =B1 in B2. Now change the value of B1. If you recalc the sheet in row-column OR column-row order, B2 will update to match B1, but A1 will now be incorrect! You need to evaluate twice to fully resolve the dependency graph.
Even LaTeX just brute-forces dependencies such as building a table of contents, index, and footnote references by running it a few times until everything stabilizes.
Is anyone using visicalc today? I'm not sure how its past success, however fantastic, can be translated into "a dependency graph is often an overkill for a spreadsheet"
A still-very-common use case for spreadsheets is just to manage lists of things. For these, there are no formulas or dependencies at all. Another is simple totals of columns of numbers.
There are many common spreadsheet use cases that don't involve complicated dependency trees.
It's a common CPU vs RAM decision to make. Dependency graph consumes memory, while recalculating everything for a number of iterations could happen on stack one formula at a time in a loop. On 6502 it mattered. On modern CPUs, even with RAM crisis I'm sure for 99.9% of spreadsheets any options is good enough. Say, you have 10K rows and 100 columns - it's 1M calculations to make.
Are there good command-line interfaces for spreadsheets? I don't do anything super financially-important and I'd prefer to stay in the terminal for quick editing of things, especially if I can have Vi keybindings.
Neat, thank you! sc-im looks amazing, and it's even in the Fedora repos (though the repo version doesn't support xlsx, so I'll compile myself and try it out)
Edit: Quite painless! Opened some test xlsx files without issue. Did get a stack trace on a very complicated one, so when I have time I'll try and dig in deeper. Added a doc to the wiki in case it's helpful to other: https://github.com/andmarti1424/sc-im/wiki/Building-sc%E2%80...
A slightly larger implementation at the end of the post does that to some extent - https://github.com/zserge/kalk (CSV import export, Excel-like "locking" of rows/columns like $A$1). If there's a need for such a project - I'm happy to add ODF or XLSX, more compatibility with Excel formulas etc. I'm not sure about Vi keybindings, I personally find spreadsheets easier to use in a non-modal manner.
Pretty sure I can build one based on code I already have. If others are interested in this, please let me know and I'll bang it out in the next couple of weeks.
All kinds of operational departments. I'm sure it was used for accounting, payroll and commissions, inventory tracking, I know that teachers used it for gradebooks as I helped set them up when I was in high school (early 1980s).
Pretty much anything that you used to do on paper with a columnar notebook or worksheet and a calculator, or anything that could be represented in tabular form could probably be implemented in VisiCalc, Lotus 123, and others. Spreadsheets are probably the most successful software application that was ever invented. Certainly one of the most.
Kinda cool to see... TBH, I'd be more inclined to reach for Rust and Ratatui myslf over C + ncurses. I know this would likely be a much larger executable though.
With MS Edit resurrected similarly, I wonder how hard it would be to get a flushed out text based spreadsheet closer in function to MS Excel or Lotus 123 versions for DOS, but cross platform. Maybe even able to load/save a few different formats from CSV/TSV to XLSX (without OLE/COM embeds).
I’m genuinely worried that we’re the last generation who will study and appreciate this craft. Because now a kid learning to program will just say “Write me a terminal spreadsheet app in plain C.”
Very cool article!
I also implemented a spreadsheet last year [0] in pure TypeScript, with the fun twist that formulas also update backwards. While the backwards root finding algorithm was challenging, I also found it incredibly humbling to discover how much complexity there is in the UX of the simple spreadsheet interface. Handling selection states, reactive updates, detecting cycles of dependency and gracefully recovering from them is a massive state machine programming challenge! Very fun project with a lot of depth!
I myself didn't hand roll my own parser but used Ohm-js [1] which I highly recommend if you want to parse a custom language in Javascript or TypeScript.
> One way of doing this is to keep track of all dependencies between the cells and trigger updates when necessary. Maintaining a dependency graph would give us the most efficient updates, but it’s often an overkill for a spreadsheet.
On that subject, figuring out the efficient way to do it is also a large engineering challenge, and is definitely not overkill but absolutely required for a modern spreadsheet implementation. There is a good description of how Excel does it in this famous paper "Build systems a la carte" paper, which interestingly takes on a spreadsheet as a build system [2].
[0] https://victorpoughon.github.io/bidicalc/
[1] https://ohmjs.org/
[2] https://www.microsoft.com/en-us/research/wp-content/uploads/...
The idea of backward updating is fascinating but is not generally feasible or computable. What kind of problems can you solve backwardly?
Quote:
I doubt that 171 KB of static allocation would fly on an Apple II! I do wonder how they did memory allocation, it must have been tricky with all the fragmentation.According to Bob Frankston, Bricklin's co-founder[1]:
> The basic approach was to allocate memory into fixed chunks so that we wouldn't have a problem with the kind of breakage that occurs with irregular allocation. Deallocating a cell freed up 100% of its storage. Thus a given spreadsheet would take up the same amount of space no matter how it was created. I presumed that the spreadsheet would normally be compact and in the upper left (low number rows and cells) so used a vector of rows vectors. The chunks were also called cells so I had to be careful about terminology to avoid confusion. Internally the term "cell" always meant storage cell. These cells were allocated from one direction and the vectors from the other. When they collided the program reorganized the storage. It had to do this in place since there was no room left at that point -- after all that's why we had to do the reorganization.
> The actual representation was variable length with each element prefixed by a varying length type indicator. In order to avoid having most code parse the formula the last by was marked $ff (or 0xff in today's representation). It turned out that valid cell references at the edges of the sheet looked like this and created some interesting bugs.
It leaves out a lot of details - if you're skimping enough you could allocate variable length row vectors, but it seems they wanted to avoid variable length allocations, in which case you could start with a 255 byte array pointing to which subsequent equal-sized chunk represents each in-use row. You'd need at most 126 bytes per row in actual use to point into the chunks representing the cell contents. But this is just guesses.
[1] https://www.landley.net/history/mirror/apple2/implementingvi... and https://news.ycombinator.com/item?id=34303825
Reminds me of spreadsheet-fortran (https://github.com/lwsinclair/spreadsheet-fortran), a project creating a VisiCalc lookalike in FORTRAN 66, which even runs on a PDP-11.
> Maintaining a dependency graph would give us the most efficient updates, but it’s often an overkill for a spreadsheet.
It's not overkill at all. In fact, it's absolutely necessary for all but the simplest toy examples.
Isn’t the existence & success of visicalc a direct counter to this?
> Since the formulas did depend on each other the order of (re)calculation made a difference. The first idea was to follow the dependency chains but this would have involved keeping pointers and that would take up memory. We realized that normal spreadsheets were simple and could be calculated in either row or column order and errors would usually become obvious right away. Later spreadsheets touted "natural order" as a major feature but for the Apple ][ I think we made the right tradeoff.
It would seem that the creators of VisiCalc regarded this is a choice that made sense in the context of the limitations of the Apple ][, but agree that a dependency graph would have been better.
https://www.landley.net/history/mirror/apple2/implementingvi...
Edit: It's also interesting that the tradeoff here is put in terms of correctness, not performance as in the posted article. And that makes sense: Consider a spreadsheet with =B2 in A1 and =B1 in B2. Now change the value of B1. If you recalc the sheet in row-column OR column-row order, B2 will update to match B1, but A1 will now be incorrect! You need to evaluate twice to fully resolve the dependency graph.
Even LaTeX just brute-forces dependencies such as building a table of contents, index, and footnote references by running it a few times until everything stabilizes.
VisiCalc didn't do this, though. It just recalculated once, and if there were errors you had to notice them and manually trigger another recalc.
Is anyone using visicalc today? I'm not sure how its past success, however fantastic, can be translated into "a dependency graph is often an overkill for a spreadsheet"
A still-very-common use case for spreadsheets is just to manage lists of things. For these, there are no formulas or dependencies at all. Another is simple totals of columns of numbers.
There are many common spreadsheet use cases that don't involve complicated dependency trees.
It's a common CPU vs RAM decision to make. Dependency graph consumes memory, while recalculating everything for a number of iterations could happen on stack one formula at a time in a loop. On 6502 it mattered. On modern CPUs, even with RAM crisis I'm sure for 99.9% of spreadsheets any options is good enough. Say, you have 10K rows and 100 columns - it's 1M calculations to make.
Keeping a dependency tree is not complicated
It's more complicated than not keeping one, at least.
Reminds me of https://tomasp.net/blog/2018/write-your-own-excel/
Are there good command-line interfaces for spreadsheets? I don't do anything super financially-important and I'd prefer to stay in the terminal for quick editing of things, especially if I can have Vi keybindings.
There is SC and now sc-im: https://github.com/andmarti1424/sc-im
You can also literally run Lotus 123 if you want. Someone has binaries to make it work on linux. or under dosemu
Neat, thank you! sc-im looks amazing, and it's even in the Fedora repos (though the repo version doesn't support xlsx, so I'll compile myself and try it out)
Edit: Quite painless! Opened some test xlsx files without issue. Did get a stack trace on a very complicated one, so when I have time I'll try and dig in deeper. Added a doc to the wiki in case it's helpful to other: https://github.com/andmarti1424/sc-im/wiki/Building-sc%E2%80...
Visidata[0] is a killer data swiss army knife. It's even inspired off Visicalc
[0] https://www.visidata.org/
I actually created one for some time ago. It's nothing special but it has Vi keybindings.
https://github.com/RauliL/levite
This is brilliant! Thank you for creating it
Oh man, a TUI spreadsheet application that can edit ODF or XLSX format would be absolutely killer. Would love to hear if anyone knows of such a tool
A slightly larger implementation at the end of the post does that to some extent - https://github.com/zserge/kalk (CSV import export, Excel-like "locking" of rows/columns like $A$1). If there's a need for such a project - I'm happy to add ODF or XLSX, more compatibility with Excel formulas etc. I'm not sure about Vi keybindings, I personally find spreadsheets easier to use in a non-modal manner.
https://github.com/zaphar/sheetsui
Pretty sure I can build one based on code I already have. If others are interested in this, please let me know and I'll bang it out in the next couple of weeks.
I would be interested! Clixel
vibe one. ;-)
Emacs with org-mode and evil-mode seems to be up your alley.
sc has been around for quite a while: https://github.com/robrohan/sc there are several versions floating around.
Anyone know what kind of departments/parts of business were the first adopters of visicalc?
All kinds of operational departments. I'm sure it was used for accounting, payroll and commissions, inventory tracking, I know that teachers used it for gradebooks as I helped set them up when I was in high school (early 1980s).
Pretty much anything that you used to do on paper with a columnar notebook or worksheet and a calculator, or anything that could be represented in tabular form could probably be implemented in VisiCalc, Lotus 123, and others. Spreadsheets are probably the most successful software application that was ever invented. Certainly one of the most.
I would guess anybody doing bookkeeping or accounting.
Back then it was common for people to buy a whole system for their requirements. Hardware and software.
Accountants, and individuals within all kinds of businesses (what we today would call shadow IT). Imagine something like this:
* Person who deals with numbers all day goes to a computer store to browse.
* He sees VisiCalc, and immediately understands what it can do. It *blows his mind*.
* He wants to buy it right away. Pays for $2000 Apple II computer with disk drives to run $100 software; price is no object.
* Shows friends and colleagues.
* They rush to computer store. Repeat.
Kinda cool to see... TBH, I'd be more inclined to reach for Rust and Ratatui myslf over C + ncurses. I know this would likely be a much larger executable though.
With MS Edit resurrected similarly, I wonder how hard it would be to get a flushed out text based spreadsheet closer in function to MS Excel or Lotus 123 versions for DOS, but cross platform. Maybe even able to load/save a few different formats from CSV/TSV to XLSX (without OLE/COM embeds).
I’m genuinely worried that we’re the last generation who will study and appreciate this craft. Because now a kid learning to program will just say “Write me a terminal spreadsheet app in plain C.”
Other open source command line spreadsheets: