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.
(1) MAYBE DO .1 <- #0Now 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 <- #0is 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)".
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 BACKwill print:
ONE ZEROThe 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 BACKwill print:
ZERO ONEOn 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 BACKwhich 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 NOTHINGas 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!
(100) DO SOMETHING ... (199) PLEASE GO BACK (200) MAYBE COME FROM (100) ... (299) PLEASE GO BACKwill 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 BACKAs 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 SOMETHINGwill 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 BACKThe 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 BACKis a complete nightmare to analyse.
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 BACKwill print:
ONE THREE ZERO THREEOnly 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.
DO .1 <- #1 MAYBE DO .1 <- #2 (10) PLEASE READ OUT .1 DO ABSTAIN FROM (10) PLEASE DO GO BACKwill only print:
TWOLine (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 BACKThis 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 BACKWill output ONE twice.
(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:
(10) PLEASE READ OUT #1 ... MAYBE COME FROM (10) ... PLEASE GO BACK MAYBE COME FROM (10) ... PLEASE GO BACK
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 BACKExecution happens in this order: