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/...

▲

wslh 3 hours ago | parent [-]

The idea of backward updating is fascinating but is not generally feasible or computable. What kind of problems can you solve backwardly?

▲

fouronnes3 3 hours ago | parent | next [-]

> 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.

	▲	AlotOfReading 19 minutes ago \| parent [-]
		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: https://mike.zwobble.org/2013/11/fun-with-prolog-write-an-al...

▲

somat 2 hours ago | parent | prev | next [-]

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.

▲

btilly 2 hours ago | parent | prev | next [-]

While the general problem is not always tractable, some of the special cases are pretty important.

Take, for example, backprop in machine learning. The model operates forwards. Then you solve backwards to figure out how to update the terms.

▲

WillAdams 3 hours ago | parent | prev [-]

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.