How does BASIC locate an out-of-order NEXT statement when the loop body is skipped

Question

Set the WABAC machine, Sherman. This question is about BASIC in general, and Microsoft's BASIC-80 in particular. Old school basic. With line numbers.

How do (or, rather, did) old-school BASIC interpreters handle FOR...NEXT loops when the loop body was not executed, and the NEXT statement appeared out of order?

An out-of-order NEXT statement from the before time:

Here's a subroutine from the game Awari out of David H. Ahl's "101 Basic Computer Games":

200 K=M:GOSUB 600
205 E=0:IF K>6 THEN K=K-7
210 C=C+1:IF C<9 THEN F(N)=F(N)*6+K
215 FOR I=0 TO 5:IF B(I)<>0 THEN 230
220 NEXT I
225 RETURN
230 FOR I=7 TO 12:IF B(I)<>0 THEN E=1:RETURN
235 GOTO 220

and here it is with everything except the flow control redacted:

200 GOSUB 600
215 FOR I=0 TO 5:IF ... THEN 230
220 NEXT I
225 RETURN
230 FOR I=7 TO 12:IF ... THEN RETURN
235 GOTO 220

Does that bring back not-so-fond memories? Can you hear Dijkstra rolling over in his grave?

Here are the interesting part of what's happening in this fragment:

• The second FOR loop, since it uses the same loop variable, replaces the first FOR loop
• The two FOR loops share the same NEXT statement
• The second FOR loop's NEXT statement comes before it, in source order, but after it, in execution order

You might suppose, then, that the interpreter, having started a FOR loop, simply runs statements until it happens across the NEXT loop. The order of the statement in the source does not matter in this case. But let's see what the basic80 manual has to say about FOR loops:

The basic-80 manual says "moo..."

The body of the loop is skipped if the initial value of the loop times the sign of the step exceeds the final value times the sign of the step.

So, the loop body can be skipped entirely.

We have evidence, in the form of published programs, that at least some versions of BASIC were dynamically locating their NEXT statements. This is easy enough to do when the loop body is being executed. However, in the case where the body of the FOR statement should be skipped, as BASIC-80 permits, how did BASIC locate the NEXT statement, given that it might be before the FOR statement in source order?

• Did the version of BASIC used in "101 Basic Computer Games" always execute the loop body at least once?
• Did BASIC-80 require a FOR loop's NEXT statement to occur after the FOR statement, in source order?

PS: Yes, I'm writing a BASIC interpreter for old school BASIC. It's a sickness.

Answer 1

This brings back the old times...

I have a copy of the book, 3rd printing, 1975. I checked your listing and it's non-original. In the original source code the statements have no spaces and assignments have the keyword LET. For example

200 LETK=M:GOSUB600

The dialect is DIGITAL PDP-11 BASIC (not Basic-plus or BASIC-80). From experience, not all of these games worked on all dialects of BASIC. I have a vague recollection of having to recode several of these games to get them to work on other dialects. This kind of horrible loop structure was definitely a problem.

I had experience with over 20 different dialects of BASIC and I can tell you that this was a vexed question at the time. There were 2 main camps.

In one camp there were the full interpreters, which parsed each line afresh each time it was seen. They handled a FOR loop by pushing it on a stack, identified by its variable, and then scanning the stack for a match with each NEXT. If they skipped a loop, they would have to scan the source for the NEXT. Some did, some didn't.

The other camp was the tokenizers or semi-compilers. They would scan all the lines before execution and convert them to some kind of internal format. They also matched up FOR/NEXT loops and checked for missing GOTO and GOSUB targets. DEC and BASIC-80 were in this camp, as I recall, but it is a long time ago.

In answer to your questions,

1. Yes, the dialect of BASIC does skip a loop if initially satisfied
2. No, sequencing of FOR NEXT was not a documented requirement, but the behaviour was undefined. As a professional, obviously I never did it. :)

Hope this helps. These are horrible languages, but if you gotta do it...

Answer 2

I don't have a copy of the specification for one of these ancient BASIC interpreters in front of me (it may not even exist), but I'm going to go out on a limb and say that the BASIC interpreter will not execute a NEXT on a FOR loop that doesn't belong to it, even if the loop variable has the same name.

So, in other words, in your example

200 K=M:GOSUB 600
205 E=0:IF K>6 THEN K=K-7
210 C=C+1:IF C<9 THEN F(N)=F(N)*6+K
215 FOR I=0 TO 5:IF B(I)<>0 THEN 230
220 NEXT I
225 RETURN
230 FOR I=7 TO 12:IF B(I)<>0 THEN E=1:RETURN
235 GOTO 220

when line 235 executes and goes to line 220, line 220 will NEXT the top FOR loop, not the bottom.

This is evident in the "NEXT without FOR" error message; the BASIC interpreter rejects any NEXT for which it did not find a corresponding FOR. This typically happens when you get your NEXT's out of order, as in

100 FOR I = 1 to 10
110 FOR J = 1 to 10
120 ...
130 NEXT I
140 NEXT J

So to answer your bulleted questions:

• Yes, if the loop variable is within range of the FOR.
• Yes, to my knowledge, that is the case.

Answer 3

What the "101 Computer Games" BASIC does

The dialect of BASIC used in the Microcomputer edition of "101 Computer Games" will execute the body of a FOR...NEXT loop at least once. This does differ from BASIC-80 v. 5.

From p. i12, listing exceptions to "normal" BASIC:

FOR...TO...STEP

As in standard BASIC, except that the test for ending the loop is made after it h as been executed. That is, when this program is run:

10 FOR X=2 TO 1
20 PRINT "HI"
30 NEXT X
40 END

"HI" will be printed...

Because of that, this dialect of BASIC has no trouble locating the NEXT statement, or sharing the same next statement with multiple FOR statements. No static analysis is required. Simply execute every statement as it occurs, and you'll eventually get to the NEXT statement, wherever it is.

Is it possible for BASIC-80 to handle an out-of-order NEXT?

It is possible for a FOR statement to skip the loop body, as BASIC-80 v.5 allows, and still allow out-of-order NEXT statements in most cases. Here's how:

• The interpreter gets two states, "running," and "skipping to NEXT"
• When in the "running" state, the interpreter executes every statement normally.
• When evaluating a FOR statement, if the loop body is to be skipped, the state is changed to "skipping to NEXT"
• When in the "skipping to next" state, the interpreter skips every statement except NEXT and unconditional GOTO.
  • An unconditional GOTO statement is followed
  • A NEXT statement, if its variable matches that of the FOR statement (or if the variable is not specified), switches back to the "running" state. If the variable does not match, the interpreter remains in the "skipping to NEXT" state.

This would handle simple pathological sequences such as that in the question. It would not handle cases where the NEXT was reached by an IF...GOTO statement, or a GOSUB. Code that does that is so much worse than the already bad code in the question that it's not unreasonable to simple declare that the interpreter will not support such cases. It might even be permissible for the interpreter to set such code on fire.