[Nomen-dev] Fwd: Backtracking in INTERCAL

[Brian H. <bh...@sp...>]

This hurt my brain.  I decided to share the joy.

---------- Forwarded message ----------
Date: Tue, 30 Jul 2002 10:05:03 -0500
From: Melissa Reid <mr...@po...>
To: bri...@ql...
Subject: Fwd: Backtracking in INTERCAL

> From: mal...@cs... (Malcolm Ryan)
> Subject: Backtracking in INTERCAL
> Date: 28 Jul 2002 21:51:43 -0700
> Newsgroups: alt.lang.intercal
> Message-ID: <e6f...@po...>
> 
> I've been doing a lot of programming in Prolog recently, and realised
> that it has one powerful means of obfuscation that Intercal sorely
> lacks, namely: backtracking.
> 
> For those unfamiliar with Prolog, it basically allows several possible
> execution paths from each statement. When one fails, then it
> backtracks, undoing each statement until it comes to a path that it
> has not which it then takes.
> 
> What I am considering for intercal is this: a new command "BACKTRACK"
> and a new line label "MAYBE". I'll give an example:
> 
>     PLEASE DO .1 <- #0
>            DO .2 <- #0
> (10) MAYBE DO .1 <- #1
> (20) MAYBE DO .2 <- #1
>     PLEASE READ OUT .1
>     PLEASE READ OUT .2
> (30)    DO BACKTRACK
> 
> The "MAYBE" label creates a choice-point. The first time it is
> executed it acts as a "DO", but on backtracking it acts as a "DO NOT".
> So this program will initially execute lines (10) and (20) normally,
> setting both .1 and .2 to #1, and printing:
> 
> ONE
> ONE
> 
> Then it hits the BACKTRACK statement. Backtracking undoes all
> statements back to the most recent choice-point, which is line (20).
> It undoes the earlier effect of this line, restoring .2 to #0 and then
> proceeds in the forward direction again, this time treating the MAYBE
> as a DO NOT. So .2 is not changed, and the program prints:
> 
> ONE
> ZERO
> 
> It hits the BACKTRACK statement again. The alternatives at line (20)
> have been exhaustred, so it backtracks all the way to line (10), and
> this time treats that line as a DO NOT. Executing again in the forward
> direction, it encounters line (20) for a third time. As it is
> executing in the forward direction, the MAYBE on line (20) is treated
> as a DO. So the program prints:
> 
> ZERO
> ONE
> 
> It it backtracks again, this time to the choice point at line (20)
> which has another alternative to try. This time it prints:
> 
> ZERO
> ZERO
> 
> On hitting the BACKTRACK statement this time, there are no
> choice-points remaining, so it is ignored and execution continues.
> 
> If you wanted a command to be ignored on the first pass and then
> executed on backtracking you could use "MAYBE DO NOT".
> 
> There is some interesting potential interaction with COME FROM:
> 
> (10) DO SOMETHING
> (20) DO SOMETHING ELSE
>      ....
> 
> (30) MAYBE COME FROM (10)
>      PLEASE BACKTRACK
> 
> The first pass through, the MAYBE in line (30) would be treated as a
> DO and so execution would continue from line (30). Once it
> backtracked, it would undo line (30) and treat is as DO NOT, so
> execution would continue from line (10).
> 
> On the other hand:
> 
> (10) DO SOMETHING 
> (20) PLEASE BACKTRACK
> 
> (30) MAYBE DO NOT COME FROM (10)
> 
> would ignore (30) on the first pass, and only execute the COME FROM on
> backtracking.
> 
> With Threaded Intercal you could have:
> 
> (10) DO SOMETHING
> (20) DO SOMETHING ELSE
> 
> (30) MAYBE COME FROM (10)
>      DO BACKTRACK
> 
> (40) MAYBE COME FROM (10)
>      PLEASE BACKTRACK
> 
> After executing 10, the thread would split in two, one executing at
> line (30) and one at line (40). What happens when they backtrack? It
> seems to me that  the first thread to backtrack should just be
> destroyed, and the second should continue executing from line (20).
> 
> Here's a puzzler. What would this code do?
> 
> (10) DO SOMETHING
> (20) DO SOMETHING ELSE
> 
> (30) MAYBE COME FROM (10) 
>      DO BACKTRACK
> 
> (40) MAYBE DO NOT COME FROM (10)
>      DO BACKTRACK 
> 
> What about this?
> 
>      MAYBE DO SOMETHING ONCE
>      PLEASE BACKTRACK
> 
> Or this?
>      
>      PLEASE COME FROM (20)
> (10) MAYBE DO SOMETHING
>      PLEASE ABSTAIN FROM (10)
> (20) DO BACKTRACK
>   
> Lots to think about.
> 
> Malcolm