Semantics of FOR-NEXT Loops

Posted on by

I’ve been implementing the FOR-NEXT loop in a BASIC interpreter I’m building. It brings up some issues of programming language semantics.

10 FOR X = e1 TO e2 [STEP e3]
20   -- body
30 NEXT X

Expectations Shattered

I had expected this would correspond to a while loop, something like this:

X = e1
while x <= e2 do 
  -- body
  x = x + e3
end

From two descriptions of BASIC (the original paper and the C64 documentation), I learned that it just didn’t work that way – and they differ on how it should work.

Original BASIC FOR-NEXT

“The FOR statement goes into the body of the loop if the variable has a value <= the final value (in case of positive step size)… Upon leaving the loop, … the variable used in the FOR statement has the value it had during the last passage through the loop…”

and a surprise:

FOR Z = 2 TO -2
“The body of the loop will not be performed… Instead, the computer will proceed to the statement immediately following the corresponding NEXT. The value of Z will then be 1, which is the initial value (2) minus the step size (1).”

C64 FOR-NEXT

The C64 description doesn’t explain the value the variable has outside the loop, but it does have this boxed note:

NOTE: A loop always executes at least once.

(This directly contradicts the other version!)

Diving deeper into the semantics made me wonder something else – when are the limit and step size determined? Can they change while the loop runs?

I found a C64 emulator, so I can answer for that version: they’re calculated only before the loop starts. (Visual BASIC explicitly notes this.) I assume original BASIC is the same.

Informal Semantics

These discrepancies make life hard for users of the language (and implementors!) Portable programs are hard to write.

In fact, it’s hard for a natural-language description to cover everything. I’d be happier if they’d taken either of these approaches:

  1. Explicitly describe the semantics of more complex constructs in terms of simpler constructs (e.g., describe FOR-NEXT using IF and GOTO).
  2. Describe the semantics in a formal way (e.g., denotational semantics).

FOR-NEXT Implementation for Original BASIC

The template below assumes a stack with the variable, limit, step size, and start address of the body. (The stack allows nesting of FOR loops.) However, there are many ways to implement a construct; you could also do it by introducing a hidden line to be the top of the actual loop.

Translation of FOR X = e1 TO e2 STEP e3  ;  body  ;  NEXT X:

start = e1       -- temporary variable, unique to each loop
limit = e2       -- same
step = e3        -- same
X = start - step
bodyStart = nextLineNumber()
forStack.push("X", limit, step, bodyStart)
goto(line_number_of_NEXT)

body_line_number:   -- this is what's in bodyStart
  -- body contents

line_number_of_NEXT:
  forStack.peek(variable, limit, step, body_line_number) -- load variables
  
  if variable + step <= limit {    -- we know variable is "X"
    variable = variable + step
    goto body_line_number
  } else {
    pop forStack  
    // fall through to line after NEXT
  }

By not incrementing until we know it’s safe, we reproduce the behavior described with the “FOR Z = 2 TO -2” loop – not executing the body, and leaving the loop with Z = 1.

FOR-NEXT Implementation for C64

This implementation is different because it doesn’t check before executing the loop the first time. 

Translation of FOR X = e1 TO e2 STEP e3  ;  body  ;  NEXT X:

X = e1
limit = e2
step = e3
forStack.push("X", step, limit, body_line_number)

body_line_number:
  -- body

line_number_of_NEXT:
  forStack.peek(variable, step, limit, body_line_number)
  variable = variable + step
  if variable <= limit { 
    goto body_line_number
  } else {
    pop forStack()
    -- fall through to following line
  }

With this scheme, we don’t need to know the location of the NEXT while we’re processing the FOR.

You could make an alternative translation as for original BASIC, using a hidden statement with the increment and testing code at the top of the loop.

Conclusion

Unless you become a compiler writer, I doubt you’d ever need this level of detail on FOR-NEXT loops.

However, there’s a mindset that applies for APIs and objects: What is the meaning of an interface? What burdens are you putting on objects to remember things for you? Will a calling object have to do expensive operations to support you?

Take some time to read the formal definition of a language you use – are there any subtleties in a feature that you never knew were there? Have you run across any variations in implementations?

References

Dartmouth University. BASIC. 1964.

“For…Next Statement (Visual Basic)“. Retrieved 2022-09-04.

Ohio Scientific, Inc. The 8K BASIC-in-ROM Reference Manual. 1978. 

A practical introduction to denotational semantics. Lloyd Allison. ISBN 978-0521306898. 1987.

“Transliterating Old-School BASIC“, by Bill Wake. Retrieved 2022-09-04.