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

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.

• The Ahl book was originally published by DEC in 1973, predating Microsoft BASIC by two years. The programs would probably have been done in RT-11 BASIC or BASIC-PLUS. Other than system-specific extensions, most dialects were compatible, and I ran of programs from the DEC version of the book on several systems with little or no difficulty. You might find the disassembled, documented sources of the Applesoft BASIC ROM enlightening. The code that implementes the `NEXT` statement starts at \$DCF9. – Blrfl Feb 17 '14 at 0:28
• Don't know about BASIC-80, but I am 100% sure that Commodore Basic (which was Microsoft BASIC V2) always executes the loop once, and the order of the statements in the source does not matter - just like you suspect. – Doc Brown Feb 17 '14 at 7:43

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.

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...

• This is very helpful, thank you. The book has a DEC version, a TRS-80 version, and a microcomputer version. The programs in the microcomputer version are in Microsoft 8080 basic (MITS Altair Basic Rev 4.0); that is my interpreter's target. – Wayne Conrad Feb 17 '14 at 16:53
• I used MBASIC on CP/M in around 1980, but none of those earlier hobbyist machines. You need a file system! In many ways I would find a reincarnation of a DEC/DG/HP/CAI/Prime/Interdata/Tektronix Basic more interesting, but I can understand why you might not. Best of luck! Contact me if I can be of help. – david.pfx Feb 17 '14 at 22:07

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
``````

• Yes, if the loop variable is within range of the FOR.
• Yes, to my knowledge, that is the case.
• "the BASIC interpreter will not execute a NEXT on a FOR loop that doesn't belong to it" - I know at least one family of old BASIC interpreters where this statement is wrong, you cannot generalize this to "all ancient BASIC interpreters". – Doc Brown Feb 17 '14 at 8:45
• The spec exists. Search for PDP-11 BASIC. – david.pfx Feb 18 '14 at 13:58
• Thank you for taking a stab at this odd question. I have now confirmed that the BASIC used in the book, when encountering the second FOR statement having the same counter variable, forgets about the first FOR statement and restarts the loop from the second one. This contradicts your stab in the dark. It's an odious way to write loops, but BASIC is smelly stuff anyway. – Wayne Conrad Feb 18 '14 at 14:03

# 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.