Into the rapids: more basic

No self-respect­ing BASIC tuto­r­ial would be com­plete with­out two indis­pens­able con­trol-flow tools—sub­rou­tines made with gosub and return, and loops made with for and next.

To make these, we’re going to use a new tool: con­tin­u­a­tions. Con­tin­u­a­tions have a rep­u­ta­tion for being weird and com­pli­cated. They’re not. But it’ll be eas­ier to see why if we first under­stand why our other options won’t work.

Sub­rou­tines

gosub is short for “go to sub­rou­tine”. It’s meant to com­pen­sate for the less-than-stel­lar sup­port for named func­tions in BASIC. gosub starts out like goto, in that it takes a num­ber or numer­i­cal expres­sion as an argu­ment. When the pro­gram arrives at a gosub, it jumps to the line indi­cated.

The dif­fer­ence is that when the pro­gram encoun­ters a return state­ment, it jumps back to the most recent gosub and con­tin­ues nor­mally. So it’s like a round-trip ver­sion of goto, mak­ing it eas­ier to move through the pro­gram in a non-lin­ear fash­ion:

By com­bin­ing vari­able assign­ment with gosub, we can approx­i­mate the behav­ior of call­ing a func­tion:

We don’t actu­ally pass argu­ments to a gosub, nor does return pro­vide a value. They’re just con­trol-flow state­ments. The shar­ing of val­ues hap­pens via global BASIC vari­ables. Like any state­ment, gosub can appear among other state­ments in a line (includ­ing other gosub state­ments).

A gosub can also be invoked within a con­di­tional:

Loops

It’s pos­si­ble to make loops with if and goto:

But often, writ­ing the loop with for and next is sim­pler:

for defines the start­ing and end­ing val­ues of a loop vari­able. The pro­gram pro­ceeds until it reaches a next ref­er­enc­ing 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 end­ing value, the loop ends and the pro­gram con­tin­ues.

The state­ments between the for and next have no spe­cial sta­tus (e.g., they’re not rec­og­nized as a “block”). Con­trol 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:

Design­ing sub­rou­tines and loops

The key fea­ture shared by sub­rou­tines and loops is that they both jump back to an ear­lier point in the pro­gram. return jumps back to a cor­re­spond­ing gosub; next to a cor­re­spond­ing for.

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

For instance, in this pro­gram, 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 dif­fer­ent des­ti­na­tions.

With next, the pres­ence of the loop vari­able as an argu­ment pro­vides a clue where to go.  + In real BASIC, the loop vari­able can be omit­ted from next. We’re not going to imple­ment that ver­sion, though the dif­fer­ence is just a lit­tle extra house­keep­ing. In prin­ci­ple, at com­pile time, we could sift through the lines of the pro­gram to find the cor­re­spond­ing for state­ment, and stash it inside the next:

The prob­lem is that a loop vari­able can be used any num­ber of times, so match­ing next state­ments to for state­ments might get com­pli­cated:

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

So next needs to know not only the line num­ber of the cor­re­spond­ing for, but also the end value of its loop. We won’t nec­es­sar­ily be able to deter­mine this end value until the pro­gram is run­ning:

Here, the y loop runs three times, and next y tests for a dif­fer­ent max­i­mum value each time.

We’re back in the same sit­u­a­tion that we were with return, where the behav­ior of the next state­ment nec­es­sar­ily depends on con­text only avail­able at run time. So we can’t rely on fig­ur­ing out every­thing at com­pile time. Instead, we’d like to cap­ture cer­tain run-time con­text when we reach a gosub or for, and save it so that it’s avail­able when we encounter the cor­re­spond­ing return or next.

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

Intro­duc­ing con­tin­u­a­tions

A con­tin­u­a­tion in a Racket pro­gram is a spe­cial kind of func­tion that serves a sim­i­lar pur­pose as a line num­ber in BASIC: it marks a ref­er­ence point within the pro­gram that we can return to later. Of course, a Racket pro­gram is struc­tured around expres­sions, not lines. So a con­tin­u­a­tion can be cap­tured at the posi­tion of any expres­sion.

For exam­ple, if we have a pro­gram with four expres­sion posi­tions:  + Namely: a func­tion, two strings, and the result of apply­ing the func­tion to the strings.

We can cap­ture the con­tin­u­a­tion at the "foo" posi­tion by wrap­ping it in let/cc:

Here, let/cc cap­tures the cur­rent con­tin­u­a­tion (hence cc) and assigns it to this-cc (or what­ever name we choose).  + There are other func­tions that also cap­ture con­tin­u­a­tions, but let/cc will suf­fice for every­thing we need to do.

let/cc oth­er­wise works like ordi­nary let: after cap­tur­ing the con­tin­u­a­tion, it eval­u­ates the expres­sions within and returns the last as its result. So both these pro­grams eval­u­ate to "foobar".

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

OK, we’ve cap­tured a con­tin­u­a­tion. What can we do with it? The con­tin­u­a­tion is a func­tion that takes one argu­ment. When we call the con­tin­u­a­tion, it returns us to the posi­tion in the pro­gram where the con­tin­u­a­tion was cap­tured (that is, the posi­tion of the let/cc). The argu­ment to the con­tin­u­a­tion is used as the new value at that posi­tion (that is, it “replaces” the let/cc). If the con­tin­u­a­tion leaves us in the mid­dle of a larger expres­sion, the sur­round­ing 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 sec­ond time with "zam" instead of "foo" as the first argu­ment:

If we cap­ture a con­tin­u­a­tion at the string-append instead, every­thing works the same way, but now we can use the con­tin­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 con­tin­u­a­tion as a way of con­vert­ing 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:

Con­tin­u­a­tion caveats

Hav­ing drawn a par­al­lel between con­tin­u­a­tions and BASIC line num­bers, we should be care­ful not to press the anal­ogy too far. Con­tin­u­a­tions have a cou­ple impor­tant dif­fer­ences from line num­bers:

Still, though they’re not a tool of first resort, con­tin­u­a­tions are use­ful in sit­u­a­tions that require unusual kinds of con­trol flow. For exam­ple, we used excep­tions to imple­ment our pro­gram-end sig­nal for the end state­ment, and the change-line sig­nal for goto. Under the hood, excep­tions are imple­mented with con­tin­u­a­tions. This works because an excep­tion is a way of jump­ing back through the call­ing chain.

Like­wise, our return and next state­ments need to jump back to a pre­vi­ously vis­ited point in a BASIC pro­gram. This time, we can’t use excep­tions. Unlike end and goto, the places we want to revisit are not in the call­ing chain. But we can imple­ment these state­ments directly with con­tin­u­a­tions.

Lexer updates

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

Oth­er­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 exist­ing "go.rkt" mod­ule. Every time we reach a b-gosub, we save a con­tin­u­a­tion onto a stack. When we reach a b-return, we get the most recent con­tin­u­a­tion off the stack and invoke it. So the imple­men­ta­tion looks like this:

We make new stack called return-ccs. Within b-gosub, we use let/cc to cap­ture the con­tin­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 pro­gram reached a b-return that didn’t have a cor­re­spond­ing b-gosub, so we use raise-line-error (which, pre­sciently, we made in bet­ter line errors) to sig­nal the prob­lem.

Oth­er­wise, we pop! the top­most con­tin­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 con­tin­u­a­tion was cap­tured, and replace the let/cc expres­sion with (void). This is equiv­a­lent to a state­ment that does noth­ing. The pro­gram will con­tinue nor­mally from that point.

Test­ing sub­rou­tines

We can quickly test that our gosub and return are work­ing with our ear­lier test pro­gram:

We can also check that our return error works cor­rectly:

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

Expander updates: for and next

Ear­lier, we noticed that for and next have to coop­er­ate at a dis­tance:

Let’s start by fram­ing out an ini­tial ver­sion 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 sec­ond case. We know at least that we have to assign a start­ing value to the LOOP-ID. So let’s call b-let with LOOP-ID and the START value.

Now what? We know from imple­ment­ing gosub and return that we can use a con­tin­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 con­tin­u­a­tion to fill in a new value at the posi­tion where the con­tin­u­a­tion is cap­tured. 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 cap­ture a con­tin­u­a­tion around the assign­ment value:

We’re not sav­ing loop-cc any­where yet. But what’s going to hap­pen if we call (loop-cc 42)? We’d be jump­ing into the mid­dle of a b-let expres­sion with a new value, which will cause the b-let to be eval­u­ated again, thereby assign­ing 42 to the LOOP-ID. Invok­ing the con­tin­u­a­tion will also move us back to the top of loop. So call­ing loop-cc with a new value is equiv­a­lent to restart­ing the loop with that value.

Now that we have a means of trav­el­ing back to the top of the loop with a new value, the path for­ward reveals itself:

The gim­mick here is that although for and next appear to be coop­er­at­ing, under the hood, b-for will be doing all the heavy lift­ing, by set­ting 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 muta­ble but it will use sym­bols 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 sig­nal an error if our next-funcs hash table has no cor­re­spond­ing key. Oth­er­wise, we fetch the func­tion and exe­cute it.

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

Inside the lambda, we’re imple­ment­ing 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 val­ues. If so, we con­tinue the loop with next-val—mean­ing, we call our con­tin­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 val­ues. We need to take a lit­tle care because the end value is not nec­es­sar­ily greater than the start value (for instance, when the step value is neg­a­tive).

Test­ing loops

With those changes, our #lang basic should be able to han­dle loops that go up or down, with or with­out a step value. For good mea­sure, let’s throw in gosub and return too:

Exactly right.

Let’s also try a pro­gram with a miss­ing for state­ment: