trustfall icon indicating copy to clipboard operation
trustfall copied to clipboard

Implement unlimited-depth directly-optimal recursion.

Open obi1kenobi opened this issue 2 years ago • 1 comments

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.

obi1kenobi avatar Oct 02 '22 03:10 obi1kenobi

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.

obi1kenobi avatar Apr 07 '23 03:04 obi1kenobi