Previous: Multithreading using WHILE, Up: Multithreading and Backtracking [Index]
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 ABSTAIN
ed or REINSTATE
d 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: Multithreading using WHILE, Up: Multithreading and Backtracking [Index]