bidicalc: a bidirectional calculator
56 points by victorpoughon
56 points by victorpoughon
You might be interested in an abstraction called "propagators". They're like hypergraphs where the nodes are bounded join semilattices holding information, and the edges are monotone functions from the input nodes to an output node. If you're careful you can make e.g. your arithmetic operations build propagator networks so you have a shot at running computations "backwards" and deriving "inputs" from "outputs".
That's so interesting because propagators are a big part of how bidicalc works already, but I had never heard of them. This is because I read about them not in a functional programming context, but in a math book where they are called "contractors" instead. I suspect there is a lot of overlap but also subtle differences!
It's always fascinating when this happens. There might even be entire research groups out there that don't know about each other but are working on the same thing!
For some useful prior art in this space, see relational language( familie)s like miniKanren.
“Hello, declarative world,” by Tom Stuart is a pretty useful introduction, and includes a reasonably-complete implementation of microKanren.
All the best,
-HG
Excel has Goal Seek and Solver which work similarly, with a variable recalculation iteration limit.
I remember using Excel in university to design a glow stick factory, where the goal was to recycle unused reactants to maximise efficiency - you could route the “byproduct” cells back into the “input” cells and recursively calculate the maximal output!
Was my first introduction to “constraint” programming (later got introduced to MiniZinc) and never looked back :)
Interesting, I wonder if I can use this to solve this year's Advent of Code puzzle for day 10...
Yes, day10 was very well suited for solving with constraint programming. I did my solutions in MiniZinc, solving the problem for each instance and then summing the results separately.
The "standard" MIP/CP style formulation for day 2 is short, and is solved quite quickly. Solve times per instance are on the order of 0.01s for Gecode, OR-Tools CP-SAT and HiGHS, while the MiniZinc translation took around 0.1s per instance.
I find this really cool but can’t think of a case where it’d be useful to me. Tell me your ideas!
I was curious how it handled trigonometric functions, as they're periodic so anything propagated backward has infinite possible values. But they seem to almost immediately break, Set:
A1 = anything
B1 = cos(A1)
Then update B1. It will display "No solution".
It should work if you set B1 to something between -1 and 1, which is the range of cos. But you are right that trigonometric functions are an edge case. I debated even including them at all because of this. Currently the implementation is sketchy and you can definitely break it with trigonometry functions in funny ways. Still it works for simple cases so I've decided to leave it in for fun.
Ah, I was mistaken in the bug.
It breaks if A1 is an expression more complicated than a simple constant. I was using multiples of pi(), and had assumed it would simplify it to a floating point number.
Try this though:
A1 = 1 + 1
B1 = cos(A1)
Then modify B1.
Yes this intended. Your example doesn't have any free variables so it can't be solved.
Neither does A1 = 1, B1 = cos(A1). But that works fine.
Rather than free variables being the problem, it's that constants aren't being simplified. I found this confusing as because it certainly looks like they are being treated as floating points during evaluation. cos(pi()/2) evaluated to 6.12323e-17 rather than 0.