Previous: , Up: Multithreading and Backtracking   [Index]


10.3 Backtracking

INTERCAL-72 C-INTERCAL CLC-INTERCAL J-INTERCAL
no version 0.25+ no no

A somewhat unusual threading construct that’s available is backtracking. In case you haven’t come across it before (the concept exists in other languages but is implemented differently and usually in a less general way), the basic idea is that instead of executing or not executing a command, you can MAYBE execute a command. This causes the command to be executed, but also creates a dormant thread in which the command wasn’t executed; at any time later, the program can either decide that it liked the consequences of the command and GO AHEAD and get rid of the dormant thread, or decide that it didn’t like the consquences of the command and GO BACK to the dormant thread, discarding the current one. The dormant thread is more commonly called a ‘choicepoint’, that is, a point at which a choice was made but a different choice can still be made, and is generally not thought of as a thread at all by most programmers. (In case you’re wondering: dormant threads are always unwoven.)

To create a choicepoint, the statement identifier MAYBE is used, rather than the more usual DO or PLEASE. (Combination statement identifiers are still allowed, but must be in the order MAYBE PLEASE DO NOT with optionally some parts omitted, or different versions of NOT used, or both.) Here’s an example:

MAYBE DON'T GIVE UP

When a command whose statement identifer contains MAYBE is reached, it is executed or not executed as normal, but in addition a choicepoint is created containing the program as it is at that time. Only ABSTAIN and REINSTATE, which always affect all threads in a program (even choicepoints), can alter the values stored in the choicepoint; so in this way, a choicepoint is also somewhat similar to the concept of a continuation in other languages. The choicepoint is placed on a choicepoint stack, which is maintained separately for each thread in much the same way that stashes and the NEXT stack are.

The choicepoint does not actually do anything immediately, but if the program doesn’t like the look of where it’s ended up, or it decides to change its mind, or just wants to try all the possibilities, it can call the GO BACK command (which has no arguments, and is just the statement identifier, optional execution chance, GO BACK, and optional ONCE or AGAIN). This causes the current thread to unweave from all other threads and then replace itself with the thread created by the choicepoint on top of the choicepoint stack. The difference is that this time, the abstention or reinstatement status of the command that was modified with MAYBE is temporarily reversed for determining whether it runs or not (this reversal only lasts immediately after the GO BACK, and does not affect uses of the command in other threads or later in the same thread), so unless it has been ABSTAINed or REINSTATEd in the meantime it will run if and only if it wasn’t run the first time. The choicepoint stack’s top entry is replaced by a ‘stale’ choicepoint that definitely isn’t a thread; attempting to GO BACK to a stale choicepoint instead causes the stale choicepoint to be deleted and the program to continue executing. (This is what gives INTERCAL’s backtracking greater flexibility in some ways than some other languages; to get backtracking without the stale choicepoints having an effect, simply run COME FROM the GO BACK as the previous statement.)

Note that, though, when a thread splits into separate threads (whether woven or unwoven), the choicepoint stack doesn’t split completely, but remains joined at the old top of stack. The two choicepoint stacks can add and remove items independently, but an attempt to GO BACK to before the current thread split off from any other threads that are still running instead causes the current thread to end, although it will GO BACK as normal if all other threads that split off from it or that it split off from since the top choicepoint of the stack was created have ended since. This means that it’s possible to backtrack past a thread splitting and get the effect of the thread unsplitting, as long as both resulting threads backtrack; this is another way in which INTERCAL’s backtracking is more flexible than that of some other languages.

If, on the other hand, a program decides that it likes where it is and doesn’t need to GO BACK, or it wants to GO BACK to a choicepoint lower down the stack while skipping some of the ones nearer the top of the stack, it can run the GO AHEAD command, which removes the top choicepoint on the stack, whether it’s a genuine choicepoint or just a stale one.

Both GO AHEAD and GO BACK cause errors if an attempt is made to use them when the choicepoint stack is empty.


Previous: , Up: Multithreading and Backtracking   [Index]