trustfall
trustfall copied to clipboard
Implement unlimited-depth directly-optimal recursion.
Implement a new directly-optimal recursion execution algorithm that can support unlimited-depth recursion, developed in collaboration with @bojanserafimov as part of the HYTRADBOI'22 Jam: https://www.hytradboi.com/jam
Traces show that the new implementation produces the first result in less than half as many steps on even the shallowest of recursion situations. The more steps previously involved in getting the first result from the recursion, the more significant the improvement will be.
After this merges, we'll still need to update the front-end to make the @recurse
depth parameter nullable and plumb that change throughout Trustfall to enable unlimited-depth recursion.
Unlimited-depth recursion makes adapters even more likely to accidentally trigger the same re-entrancy bug as in #205.
The best way I can see is making a change to the Adapter
trait to take &self
instead of &mut self
, and removing RefCell
throughout. If users need mutability, they can use their own RefCell
and will need to take care to avoid re-entrancy issues.