Into the rapids: more basic

No self-respecting BASIC tuto­rial would be complete without two indis­pens­able control-flow tools—subrou­tines made with gosub and return, and loops made with for and next.

To make these, we’re going to use a new tool: contin­u­a­tions. Contin­u­a­tions have a repu­ta­tion for being weird and compli­cated. They’re not. But it’ll be easier to see why if we first under­stand why our other options won’t work.

Subrou­tines

gosub is short for “go to subrou­tine”. It’s meant to compen­sate for the less-than-stellar support for named func­tions in BASIC. gosub starts out like goto, in that it takes a number or numer­ical expres­sion as an argu­ment. When the program arrives at a gosub, it jumps to the line indi­cated.

The differ­ence is that when the program encoun­ters a return state­ment, it jumps back to the most recent gosub and continues normally. So it’s like a round-trip version of goto, making it easier to move through the program in a non-linear fashion:

By combining vari­able assign­ment with gosub, we can approx­i­mate the behavior of calling a func­tion:

We don’t actu­ally pass argu­ments to a gosub, nor does return provide a value. They’re just control-flow state­ments. The sharing of values happens via global BASIC vari­ables. Like any state­ment, gosub can appear among other state­ments in a line (including other gosub state­ments).

A gosub can also be invoked within a condi­tional:

Loops

It’s possible to make loops with if and goto:

But often, writing the loop with for and next is simpler:

for defines the starting and ending values of a loop vari­able. The program proceeds until it reaches a next refer­encing the same loop vari­able. Then it incre­ments the loop vari­able, returns to the top of the loop, and keeps going. When the loop vari­able exceeds the ending value, the loop ends and the program continues.

The state­ments between the for and next have no special status (e.g., they’re not recog­nized as a “block”). Control can leave the loop and come back:

By default, the loop vari­able is incre­mented by 1 on each pass. This can be adjusted with an optional step value at the top of the loop:

Designing subrou­tines and loops

The key feature shared by subrou­tines and loops is that they both jump back to an earlier point in the program. return jumps back to a corre­sponding gosub; next to a corre­sponding for.

“OK, then we can model them as vari­ants of goto.” Good idea, but there’s more to the story. goto gets its desti­na­tion from an explicit value passed as an argu­ment. return and next, by contrast, have to infer their desti­na­tions. Also, recall that a gosub can appear in the middle of a line, or even multiple times in a line. That means we might have to return to the middle of a line. But goto can only send us to the begin­ning.

For instance, in this program, gosub is called twice, so the return first sends us back to line 10, and then to line 20:

In this case, the same return state­ment sends us to two different desti­na­tions.

With next, the pres­ence of the loop vari­able as an argu­ment provides a clue where to go.  + In real BASIC, the loop vari­able can be omitted from next. We’re not going to imple­ment that version, though the differ­ence is just a little extra house­keeping. In prin­ciple, at compile time, we could sift through the lines of the program to find the corre­sponding for state­ment, and stash it inside the next:

The problem is that a loop vari­able can be used any number of times, so matching next state­ments to for state­ments might get compli­cated:

But wait—there’s more. A next state­ment doesn’t just jump back to the for. It acts as a condi­tional: it incre­ments the loop vari­able, checks whether it exceeds the maximum allowed value, and if so, allows the loop to exit.

So next needs to know not only the line number of the corre­sponding for, but also the end value of its loop. We won’t neces­sarily be able to deter­mine this end value until the program is running:

Here, the y loop runs three times, and next y tests for a different maximum value each time.

We’re back in the same situ­a­tion that we were with return, where the behavior of the next state­ment neces­sarily depends on context only avail­able at run time. So we can’t rely on figuring out every­thing at compile time. Instead, we’d like to capture certain run-time context when we reach a gosub or for, and save it so that it’s avail­able when we encounter the corre­sponding return or next.

That’s exactly what contin­u­a­tions are for.

Intro­ducing contin­u­a­tions

A contin­u­a­tion in a Racket program is a special kind of func­tion that serves a similar purpose as a line number in BASIC: it marks a refer­ence point within the program that we can return to later. Of course, a Racket program is struc­tured around expres­sions, not lines. So a contin­u­a­tion can be captured at the posi­tion of any expres­sion.

For example, if we have a program with four expres­sion posi­tions:  + Namely: a func­tion, two strings, and the result of applying the func­tion to the strings.

We can capture the contin­u­a­tion at the "foo" posi­tion by wrap­ping it in let/cc:

Here, let/cc captures the current contin­u­a­tion (hence cc) and assigns it to this-cc (or what­ever name we choose).  + There are other func­tions that also capture contin­u­a­tions, but let/cc will suffice for every­thing we need to do.

let/cc other­wise works like ordi­nary let: after capturing the contin­u­a­tion, it eval­u­ates the expres­sions within and returns the last as its result. So both these programs eval­uate to "foobar".

If we want to save the contin­u­a­tion for later use, we can stash it inside another vari­able:

OK, we’ve captured a contin­u­a­tion. What can we do with it? The contin­u­a­tion is a func­tion that takes one argu­ment. When we call the contin­u­a­tion, it returns us to the posi­tion in the program where the contin­u­a­tion was captured (that is, the posi­tion of the let/cc). The argu­ment to the contin­u­a­tion is used as the new value at that posi­tion (that is, it “replaces” the let/cc). If the contin­u­a­tion leaves us in the middle of a larger expres­sion, the surrounding expres­sion is re-eval­u­ated. So if we call my-cc with "zam" as the argu­ment:

We cause string-append to be eval­u­ated a second time with "zam" instead of "foo" as the first argu­ment:

If we capture a contin­u­a­tion at the string-append instead, every­thing works the same way, but now we can use the contin­u­a­tion to change the func­tion applied to the argu­ments, rather than one of the argu­ments:

If this still seems weird, we can think of the contin­u­a­tion as a way of converting an ordi­nary expres­sion into a func­tion of an argu­ment x, where x goes in the posi­tion marked by let/cc. Below, the func­tion cc-ish roughly approx­i­mates how let/cc works:

Contin­u­a­tion caveats

Having drawn a parallel between contin­u­a­tions and BASIC line numbers, we should be careful not to press the analogy too far. Contin­u­a­tions have a couple impor­tant differ­ences from line numbers:

Still, though they’re not a tool of first resort, contin­u­a­tions are useful in situ­a­tions that require unusual kinds of control flow. For example, we used excep­tions to imple­ment our program-end signal for the end state­ment, and the change-line signal for goto. Under the hood, excep­tions are imple­mented with contin­u­a­tions. This works because an excep­tion is a way of jumping back through the calling chain.

Like­wise, our return and next state­ments need to jump back to a previ­ously visited point in a BASIC program. This time, we can’t use excep­tions. Unlike end and goto, the places we want to revisit are not in the calling chain. But we can imple­ment these state­ments directly with contin­u­a­tions.

Lexer updates

To our list of reserved-terms, we add six new ones: gosub, return, for, to, step, and next. These rules follow the state­ment syntax described above:

Other­wise, our lexer remains the same.

Parser updates

We add four new rules to cover our new state­ments: b-gosub, b-return, b-for, and b-next. We also add them to the right side of the b-statement rule:

Expander updates: gosub and return

We’ll build our expander func­tions for b-gosub and b-return into our existing "go.rkt" module. Every time we reach a b-gosub, we save a contin­u­a­tion onto a stack. When we reach a b-return, we get the most recent contin­u­a­tion off the stack and invoke it. So the imple­men­ta­tion looks like this:

We make a new stack called return-ccs. Within b-gosub, we use let/cc to capture the contin­u­a­tion as here-cc and push! it onto the stack. We then pass our b-gosub argu­ment to b-goto, which will send us where we need to go.

Then, in b-return, we unwind the process. If the return-ccs stack is empty, it means our program reached a b-return that didn’t have a corre­sponding b-gosub, so we use raise-line-error (which, presciently, we made in better line errors) to signal the problem.

Other­wise, we pop! the topmost contin­u­a­tion from the stack, and invoke it with a (void) argu­ment. The effect is to jump back to the b-gosub where the contin­u­a­tion was captured, and replace the let/cc expres­sion with (void). This is equiv­a­lent to a state­ment that does nothing. The program will continue normally from that point.

Testing subrou­tines

We can quickly test that our gosub and return are working with our earlier test program:

We can also check that our return error works correctly:

When we pick the right tool for the job, the rest is easy.

Expander updates: for and next

Earlier, we noticed that for and next have to coop­erate at a distance:

Let’s start by framing out an initial version of the b-for macro. We use two cases. In the first case, if we don’t get a step value, we stick the default value of 1 on the end and call b-for again:

That brings every­thing to the second case. We know at least that we have to assign a starting value to the LOOP-ID. So let’s call b-let with LOOP-ID and the START value.

Now what? We know from imple­menting gosub and return that we can use a contin­u­a­tion to jump back­ward. Unsur­pris­ingly, that’s how we travel from next back to for.

We also learned that we can use a contin­u­a­tion to fill in a new value at the posi­tion where the contin­u­a­tion is captured. Among other things, next restarts the loop with a new value assigned to our loop vari­able. So it might not be a bad idea to capture a contin­u­a­tion around the assign­ment value:

We’re not saving loop-cc anywhere yet. But what’s going to happen if we call (loop-cc 42)? We’d be jumping into the middle of a b-let expres­sion with a new value, which will cause the b-let to be eval­u­ated again, thereby assigning 42 to the LOOP-ID. Invoking the contin­u­a­tion will also move us back to the top of loop. So calling loop-cc with a new value is equiv­a­lent to restarting the loop with that value.

Now that we have a means of trav­eling back to the top of the loop with a new value, the path forward reveals itself:

The gimmick here is that although for and next appear to be coop­er­ating, under the hood, b-for will be doing all the heavy lifting, by setting up a func­tion that can be called by b-next.

Let’s frame out that much:

Our next-funcs hash table needs to be mutable but it will use symbols as keys, so our fastest option is make-hasheq. Within the let/cc, we use hash-set! to store an (as yet empty) lambda with the key 'LOOP-ID.

On the other side, in b-next, we use raise-line-error to signal an error if our next-funcs hash table has no corre­sponding key. Other­wise, we fetch the func­tion and execute it.

Now we just need to fill in the lambda. The finished "go.rkt" looks like this:

Inside the lambda, we’re imple­menting the steps we already set out. We incre­ment the value of LOOP-ID by the STEP value, store it in next-val, and check if it’s between the START and END values. If so, we continue the loop with next-val—meaning, we call our contin­u­a­tion loop-cc with next-val as the argu­ment. If not, the loop is done, so we delete its entry from the next-funcs hash table.

By the way, in-closed-interval? is a helper func­tion that checks whether a value is between two other values. We need to take a little care because the end value is not neces­sarily greater than the start value (for instance, when the step value is nega­tive).

Testing loops

With those changes, our #lang basic should be able to handle loops that go up or down, with or without a step value. For good measure, let’s throw in gosub and return too:

Exactly right.

Let’s also try a program with a missing for state­ment: