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].
You'd be surprised. It really depends on how you define the problem and what your goal is. My goal with bidicalc what to find ONE solution. This makes the problem somewhat possible since when there are an infinity of solution, the goal is just to converge to one. For example solving 100 = X + Y with both X and Y unknown sounds impossible in general, but finding one solution is not so difficult. The idea is that any further constraint that would help choose between the many solutions should be expressed by the user in the spreadsheet itself, rather than hardcoded in the backwards solver.
> What kind of problems can you solve backwardly?
This is the weakness of the project honestly! I made it because I was obsessed with the idea and wanted it to exist, not because I was driven by any use case. You can load some premade examples in the app, but I haven't found any killer use case for it yet. I'm just glad it exists now. You can enter any arbitrary DAG of formulas, update any value, input or output, and everything will update upstream and downstream from your edit and remain valid. That's just extremely satisfying to me.
Have you looked into prolog/datalog? You're dancing around many of the same ideas, including backwards execution, constraint programming, stratification, and finding possible values. Here's a relevant example of someone solving a problem like this in prolog:
You might dig into an operations research textbook, there are a number of problems solved with linear programming techniques which might make sense for your interface... In fact might be more intuitive for people that way and with commercial potential.
I am not sure if I know what I am talking about or if it counts in this scenario but constraint solvers come to mind. I am mainly familiar with them in a CAD context so I am struggling to think of a use for them in a spreadsheet context. But I think being able to say given these endpoints find me some values that fit could be a very valuable tool.
But like I said I am not sure that I know what I am talking about and I may be confusing backwards calculation with algebraic engines. I would love for algebra solvers to be a first class object in more languages.
I implemented bi-directional solving in a very simple "Proportion Bar" app --- sort of --- one side would calculate at the specified scaling factor (so 100% could do unit conversions), the other would calculate the scaling factor necessary to make the two sides agree.
#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.
Cool article but I think the write-up no longer matches the actual code. Snippets in the article use *p->p a lot. The *p is a parser struct defined above as
So there's the missing p, even though it's no longer an int. So I presume the member variable was once known as pos but got renamed at some point. Some of the snippets did not get updated to match.
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.
This was one of the projects students did when I helped teach APCS to high schoolers as a TEALS volunteer (FracCalc).
Some of the implementations went way overboard and it was so much fun to watch and to play a part.
Even as a “seasoned” developer I learned some tidbits talking through the ways to do (and not do) certain parts. When to store input raw vs processed, etc.
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.”
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).
80 comments
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/...
> not generally feasible or computable
You'd be surprised. It really depends on how you define the problem and what your goal is. My goal with bidicalc what to find ONE solution. This makes the problem somewhat possible since when there are an infinity of solution, the goal is just to converge to one. For example solving 100 = X + Y with both X and Y unknown sounds impossible in general, but finding one solution is not so difficult. The idea is that any further constraint that would help choose between the many solutions should be expressed by the user in the spreadsheet itself, rather than hardcoded in the backwards solver.
> What kind of problems can you solve backwardly?
This is the weakness of the project honestly! I made it because I was obsessed with the idea and wanted it to exist, not because I was driven by any use case. You can load some premade examples in the app, but I haven't found any killer use case for it yet. I'm just glad it exists now. You can enter any arbitrary DAG of formulas, update any value, input or output, and everything will update upstream and downstream from your edit and remain valid. That's just extremely satisfying to me.
https://mike.zwobble.org/2013/11/fun-with-prolog-write-an-al...
> I haven't found any killer use case for it yet
You might dig into an operations research textbook, there are a number of problems solved with linear programming techniques which might make sense for your interface... In fact might be more intuitive for people that way and with commercial potential.
But like I said I am not sure that I know what I am talking about and I may be confusing backwards calculation with algebraic engines. I would love for algebra solvers to be a first class object in more languages.
Take, for example, backprop in machine learning. The model operates forwards. Then you solve backwards to figure out how to update the terms.
It's not overkill at all. In fact, it's absolutely necessary for all but the simplest toy examples.
*p->pa lot. The *p is a parser struct defined above as Notice there is nopmember within. Assume the author meant*p->pos? And indeed if you look at the code in github the parser struct is defined as So there's the missingp, even though it's no longer an int. So I presume the member variable was once known asposbut got renamed at some point. Some of the snippets did not get updated to match.Some of the implementations went way overboard and it was so much fun to watch and to play a part.
Even as a “seasoned” developer I learned some tidbits talking through the ways to do (and not do) certain parts. When to store input raw vs processed, etc.
Though I think the definition of the parser struct should be
based on the rest of the code.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).