Better accommodations for recursive time-traveling algorithms?

[benburrill]

Currently, preempt can be used in defeat functions, but this is a quirky feature that is not really an ideal fit for its intended purpose in recursive algorithms (like the time-traveling mergesort).

This issue proposes some potential alternatives to the current behavior.

One question is whether the runtime restrictions of preemptive defeat functions should be loosened. Currently, HiD takes a conservative approach, disallowing preemptive defeat functions from being called under any circumstance without being provided safety. However, this is more restrictive than it needs to be. To ensure consistent behavior of the function, safety really only needs to be guaranteed if there is a preempt within the function that would be skipped if provided safety -- if all encountered preempt blocks would be run regardless, there is no more need for safety. This is a more complicated restriction to explain than simply "preemptive defeat functions always need to be provided safety by their caller", but it could be an alternative if the current restrictions prove to be too annoying to work with.

Another alternative would be to get rid of the restrictions altogether. This could cause functions to silently behave incorrectly if they expect safety. Making bugs like that impossible was one of the goals for HiD, so I do not want to completely eliminate the runtime checks unless there is a compelling use case for doing so, and I can't really think of one.

The other approach would be to find alternative constructs which are a better fit for recursive time-traveling algorithms, but which eliminate the need for awkward runtime errors. Basically, it seems as though we want something similar to a try, but with some sensible form of nestability. A flawed, but somewhat interesting construct would be an optional block. The optional block is run if it would become required, otherwise it is skipped, sort of like the inverse of try/undo. The required statement causes an optional block, and all of its parent optional blocks (but not siblings) to become required. This is a bit problematic in a few ways, such as that infinite loops within the optional block would also cause the block to become required, and it would require a 4th type of function if it were added to HiD (though arguably preemptive defeat functions are already a 4th function type).

Any code written with these "optional" blocks could be rewritten to use the current restricted preemptive defeat functions instead (see examples/optional_max.hid for how), but it can require splitting functions up awkwardly. The optional blocks do seem to have a nice sort of expressiveness for recursive functions.

Feel free to share other ideas for alternatives, or algorithms that would benefit from one of these options here.