Backtracking in Intercal

INTERCAL is a fine language that introduced many of the powerful obfuscatory features that are now widespread among programming languages today. So it was with some dismay that I recently discovered a language which contained a new and powerful means of confusion that INTERCAL lacked. And what's more, this language has been distributed undercover, as it were, throughout our universities, under the disguise of a useful high-level language for AI research.

I speak, of course, of Prolog, and its marvellous facilities for backtracking and variable binding, which allows so much room for strangeness, that many reserachers have given up writing it themselves and are now trying to build super-intelligent AIs to do the job for them.

Such a feature can hardly be left out of INTERCAL. If any language is going to produce super-intelligence, surely it must be our beloved. So, with the aim of providing the power of INTERCAL to the AI community, I present my proposal for backtracking Intercal, or Prontercal, um, Introlog... Princallog... Logercal... whatever.

Choice points

The heart of backtracking is the ability to make choice-points in the code, which have more than one way in which they can be executed. In INTERCAL this is achieved with the MAYBE tag: 
        (1) MAYBE DO .1 <- #0
Now the obvious immediate effect of this line is no different than if the MAYBE tag was not present. The value of .1 is set to #0. However there is an important additional effect: immediately before the statement is executed a choice point is created and added to a stack. The choice point contains the entire state of the program: the program counter and the values of variables, (but importantly NOT the abstained or reinstated status of the code). It is important to note that this is the state of the program before the line was executed. Note that an abstained statement with a MAYBE tag still creates a choice point. Thus: 
        (1) MAYBE DO NOT .1 <- #0
is a legitimate statement which adds a choice point to the stack and does nothing further.

For linguistic elegance, lines with the MAYBE tag do not need an extra "PLEASE" or "DO" tag. So "MAYBE ABSTAIN FROM (10)" is the same as "MAYBE DO ABSTAIN FROM (10)".

GO BACK

This stack has no effect on execution, until the program reaches a GO BACK (previously RECONSIDER) statement, which is a new kind of statement added by this proposal. The GO BACK statement causes the program to backtrack, restoring the state of the program to the most recent choice point on the stack. That is, unless the choice point has already been reconsidered. If the choice point has already been reconsidered once, then executing a second GO BACK statement will cause the choice point to be removed from the stack. A choice point which has already been reconsidereed once is called "stale".

When a choice point is reconsidered, the statement which created it is treated as being negated (abstained it if it was originally active, reinstated it if was inactive). Note that this does not effect the actual abstained/reinstated status of the line in question. So for example: 

                 DO .1 <- #0
             (1) MAYBE DO .1 <- #1
                 PLEASE READ OUT .1
             (2) DO GO BACK
will print: 
ONE
ZERO
The first time line (1) is executed, it creates a choice point, saves the state (with .1 equal to #0) and then sets .1 to #1. This value is read out. Then line (2) causes the program to backtrack. The saved choice point is restored. The value of .1 is restored to #0, and execution continues from line (1), but this time the line is treated as DO NOT .1 <- #1. The number ZERO is printed out, and the second GO BACK statement discards the (now stale) choice point from the stack, and continues executing at the next line. Alternatively: 
                 DO .1 <- #0
             (1) MAYBE DO NOT .1 <- #1
                 PLEASE READ OUT .1
             (2) DO GO BACK
will print: 
ZERO
ONE
On the first pass through, line (1) will not be executed, but will still create a choice-point. The value ZERO will be printed out, and then the program will GO BACK. Backtracking to the choice point at line (1), the line will now be treated as DO .1 <- #1, and the value of .1 will be changed. The value ONE will be printed, and the second execution of the GO BACK statement will remove the choice point from the stack.

The use of a stack allows choices to be nested, as in: 

                 DO .1 <- #0
                 DO .2 <- #2
             (1) MAYBE DO .1 <- #1
             (2) MAYBE DO .2 <- #3
                 PLEASE READ OUT .1
                 PLEASE READ OUT .2
             (3) DO GO BACK
             (4) DO GO BACK
which will print: 
ONE
THREE
ONE
TWO
ZERO
THREE
ZERO
TWO

Note that there does not need to be a one-to-one correspondance between MAYBE tags and GO BACK statements. For example the following is valid: 

                 DO .1 <- #0
                 DO .2 <- #2
             (1) MAYBE DO .1 <- #1
             (2) MAYBE DO .2 <- #3
                 PLEASE READ OUT .1
             (3) PLEASE READ OUT .2
                 PLEASE GIVE UP                          

             (4) DO COME FROM (5)
                 PLEASE ABSTAIN FROM (4)
                 DO COME FROM (3)
                 DO GO BACK
             (5) DO NOTHING
as also is this: 
                 DO .1 <- #1
             (1) MAYBE DO .1 <- #2
                 PLEASE READ OUT .1

                 DO (2) NEXT
                 PLEASE NOTE THE SECOND TIME THROUGH
                 PLEASE GO BACK

             (2) DO (3) NEXT
                 PLEASE NOTE THE FIRST TIME THROUGH 
                 PLEASE GO BACK

             (3) DO RESUME .1

Trying to execute a GO BACK statement when the choice-point stack is empty will give the error: 

 ICL404I I'M ALL OUT OF CHOICES!

COME FROM

The interaction between backtracking and the COME FROM statement needs to be carefully outlined. The COME FROM statement operates after the agent executes the command at the suck-point. A MAYBE COME FROM statement only creates a choice point after the statement at the choice point is executed. So the piece of code: 
            (100) DO SOMETHING
                  ...
            (199) PLEASE GO BACK

            (200) MAYBE COME FROM (100)
                  ...
            (299) PLEASE GO BACK
will do pretty much what is expected. After line (100) has been executed the program jumps to line (200). A choice-point is added to the stack. Execution continues until line (299) which reverts the program state to before the COME FROM was executed. This time through the COME FROM is ignored, and the program continues from just after line (100). When it reaches line (199) the stale choice point is discarded from the stack.

Things get less obvious when we consider the code: 

            (100) DO SOMETHING
                  ...
            (199) PLEASE GO BACK

            (200) MAYBE DO NOT COME FROM (100)
                  ...
            (299) PLEASE GO BACK
As line (200) now says DO NOT, the code will not jump to line (200) after line (100) was executed, but the choice point will be created. When the GO BACK statement in line (199) is reached, the choice point will be activated and this time the program will jump to line (200). The second GO BACK statement in line (299) will discard the choice point from the stack.

On the other hand, the following code: 

            (100) MAYBE COME FROM (200)
                  PLEASE GO BACK

            (200) DO SOMETHING
will cause an error. Executing line (100) will not create a choice-point, unless it is coming from line (200). So the GO BACK statement will attempt to read an empty stack and will fail.

The other case to be careful of is when the suck point for a COME FROM statement is a GO BACK statement. The COME FROM will only cause a jump when the GO BACK statement is removing a stale choice point, not when it is backtracking. So, for instance: 

                 DO .1 <- #0
             (1) MAYBE DO NOT .1 <- #1
                 PLEASE READ OUT .1
             (2) DO GO BACK
                 DO GIVE UP

             (3) PLEASE COME FROM (2)
                 ...
The first time line (2) is executed, execution will revert to the choice point at line (1). The second time it reaches line (2) the stale choice point will be discarded, and the COME FROM statement will cause execution to continue from line (3).

Combining the above: 

                 DO .1 <- #0
             (1) MAYBE DO NOT .1 <- #1
                 PLEASE READ OUT .1
             (2) DO GO BACK
                 ...
             (3) DO GO BACK

             (4) MAYBE DO NOT COME FROM (2)
                 ...
                 DO GO BACK
The choice point in line (4) will not be pushed onto the stack until after line (2) has executed twice. As line (4) says "MAYBE DO NOT" the execution will continue from line (2) until it reaches line (3) and GO BACKs. Then it will jump to (4).

On the other hand, the code: 

                 DO .1 <- #0
             (1) MAYBE DO NOT .1 <- #1
                 PLEASE READ OUT .1
             (2) DO GO BACK
                 ...
             (4) MAYBE DO NOT COME FROM (1)
                 ...
                 DO GO BACK
             (3) DO GO BACK
is a complete nightmare to analyse.

GO AHEAD

Sometimes you want to eliminate a choice point without GOing BACK to it. This is the role of the GO AHEAD (previously COMMIT) statement. This statement discards the most recent choice point from the stack, regardless of whether or not it is stale. So for example: 
                 DO .1 <- #0
                 DO .2 <- #2
             (1) MAYBE DO .1 <- #1
             (2) MAYBE DO .2 <- #3
                 PLEASE READ OUT .1
                 PLEASE READ OUT .2
             (3) DO GO AHEAD
             (4) DO GO BACK
will print: 
ONE
THREE
ZERO
THREE
Only the first alternative of the choice-point at line (2) is executed. The GO AHEAD statement in line (3) then discards the choice-point without re-executing it, and proceeds to line (4). The choice point from line (1) is now at the top of the stack, so line (4) reconsiders this choice and goes back to line (1).

As with the GO BACK statement, it is an error to try to GO AHEAD when the choice point stack is empty. The same error message will result.

ABSTAINING & REINSTATING

Just as Prolog makes things confusing when combining the semantics of backtracking with asserting and retracting fluents, so also the opportunity exists for muddling the semantics of intercal backtracking with ABSTAIN and REINSTATE. So in the spirit of Prolog, backtracking does NOT restore the abstention status of lines of code.

So example: 

                 DO .1 <- #1
                 MAYBE DO .1 <- #2
            (10) PLEASE READ OUT .1
                 DO ABSTAIN FROM (10)
                 PLEASE DO GO BACK
will only print: 
TWO
Line (10) will be abstained from on the first pass and will NOT be reinstated on backtracking.

This is even the case if the ABSTAIN statement is in the MAYBE clause itself: 

                 MAYBE DO ABSTAIN FROM (10)
            (10) PLEASE READ OUT #1
                 DO GO BACK
This code will not print anything. Line (10) will be abstained on the first pass. After backtracking, the ABSTAIN FROM (10) line will not be executed again, but the line will remain abstained from the first pass.

Notice also that this means the abtention status of the MAYBE statement can itself be different on backtracking. When a statement is reconsidered, it is the abstention status of the line at the time of reconsidering which is taken into account. So, for example the code: 

            (10)  MAYBE READ OUT #1
                  DO ABSTAIN FROM (10)
                  PLEASE GO BACK
Will output ONE twice.

Backtracking in Threaded INTERCAL

We are now able to describe how backtracking works in Threaded Intercal. There are two important considerations: 1) How backtracking interacts with thread creation via multiple COME FROMs, and 2) How backtracking interacts with the DO ... ONCE modifier.

Backtracking and Thread Creation

When multiple threads are created via multiple COME FROM statements, they all inherit the choice point stack from the parent thread. If a thread attempts to GO BACK to a choice point which occured before the creation of the thread, it will be destroyed, unless all other thread descended from this COME FROM have already GONE BACK, it which case backtracking procedes as usual. In this way, backtracking over the splitting of a thread will result in the recombination of that thread.

Example: 

             (10) MAYBE READ OUT #1
                  ...

                  DO COME FROM (10)
                  PLEASE READ OUT #2
                  DO GO BACK
                  ....

                  DO COME FROM (10)
                  PLEASE READ OUT #3
                  DO GO BACK
                  ....
Execution happens in this (possible) order:
  1. A choice point is created before line (10)
  2. READ OUT #1 is executed.
  3. Two threads are created, one at each COME FROM
  4. Thread 1 executes PLEASE READ OUT #2
  5. Thread 1 executes DO GO BACK and is is destroyed.
  6. Thread 2 executes PLEASE READ OUT #2
  7. Thread 2 executes DO GO BACK and reconsiders the choice point
  8. READ OUT #1 is reconsidered and ignored.
  9. Two threads are created, one at each COME FROM
  10. Thread 1 executes PLEASE READ OUT #2
  11. Thread 1 executes DO GO BACK and discards the stale choice point
  12. Thread 2 executes PLEASE READ OUT #2
  13. Thread 2 executes DO GO BACK and discards the stale choice point
  14. Both threads continue executing...
A puzzle for the reader: What happens in the following case? 
             (10) PLEASE READ OUT #1
                  ...

                  MAYBE COME FROM (10)
                  ...
                  PLEASE GO BACK

                  MAYBE COME FROM (10)
                  ...
                  PLEASE GO BACK

Backtracking and DO ... ONCE

Since backtracking does not affect the abstention of lines of the code base, backtracking over a DO ... ONCE statement does not undo the self-abstention or self-reinstatement of such a line.

Furthermore, in the combination MAYBE DO ... ONCE the choice point is created before the statement is executed, whereas the self-abstention or reinstatement happens after the execution.

So consider the example: 

                  MAYBE READ OUT #1 ONCE
                  DO GO BACK
Execution happens in this order:
  1. A choice point is created.
  2. READ OUT #1 is executed
  3. The line self-abstains. It is now MAYBE DO NOT READ OUT #1 AGAIN
  4. DO GO BACK is executed
  5. The first line is reconsidered. It is "mentally" negated (not affecting the actual code-base) to DO READ OUT #1 ONCE
  6. DO READ OUT #1 is executed
  7. The line self-abstains again.
  8. DO GO BACK is executed again, discarding the stale choice point.
Confusing, eh?

History:

Version 0.3 - 11/4/06

Changed semantics for ABSTAIN and REINSTATE, following the recommendation of Alex Smith.

Version 0.2 - 8/6/04

Changed commands from RECONSIDER and COMMIT to GO BACK and GO AHEAD

Version 0.1 - 28/7/02

Original standard authored by Malcolm Ryan.

Other Intercal extensions
Malcolm Ryan - malcolmr@cse.unsw.edu.au
Last updated: Tuesday, 11-Apr-2006 18:12:08 EST