Does Racket Have a Continue Function
Beautiful Racket / tutorials
Into the rapids: more basic
- 1 intro
- 2 specification and setup
- 3 the syntax colorer
- 4 better line errors
- 5 variables and input
- 6 expressions
- 7 conditionals
- 8 subroutines and loops
- 9 recap
- 10 source listing
No self-respecting BASIC tutorial would be complete without two indispensable control-flow tools—subroutines made with gosub and return, and loops made with for and next.
To make these, we're going to use a new tool: continuations. Continuations have a reputation for being weird and complicated. They're not. But it'll be easier to see why if we first understand why our other options won't work.
gosub is short for "go to subroutine". It's meant to compensate for the less-than-stellar support for named functions in BASIC. gosub starts out like goto, in that it takes a number or numerical expression as an argument. When the program arrives at a gosub, it jumps to the line indicated.
The difference is that when the program encounters a return statement, 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:
#lang basic-demo-2
10 gosub 50
20 gosub 70
30 print "third"
40 end
50 print "first"
60 return
70 print "second"
80 return
#lang basic-demo-2 10 gosub 50 20 gosub 70 30 print "third" 40 end 50 print "first" 60 return 70 print "second" 80 return |
first
second
third
By combining variable assignment with gosub, we can approximate the behavior of calling a function:
#lang basic-demo-2
10 x = 11 : gosub 30 : gosub 30 : gosub 30
20 end
30 print x : x = x + 1
40 return
#lang basic-demo-2 10 x = 11 : gosub 30 : gosub 30 : gosub 30 20 end 30 print x : x = x + 1 40 return |
11
12
13
We don't actually pass arguments to a gosub, nor does return provide a value. They're just control-flow statements. The sharing of values happens via global BASIC variables. Like any statement, gosub can appear among other statements in a line (including other gosub statements).
A gosub can also be invoked within a conditional:
#lang basic-demo-2
10 x = 2 : y = 4
20 if x < y then gosub 40
30 end
40 print "less"
50 return
#lang basic-demo-2 10 x = 2 : y = 4 20 if x < y then gosub 40 30 end 40 print "less" 50 return |
less
It's possible to make loops with if and goto:
#lang basic-demo-2
10 if x < 4 then print x else 30
20 x = x + 1 : goto 10
30 end
#lang basic-demo-2 10 if x < 4 then print x else 30 20 x = x + 1 : goto 10 30 end |
0
1
2
3
But often, writing the loop with for and next is simpler:
#lang basic-demo-2
10 for x = 0 to 3
20 print x
30 next x
#lang basic-demo-2 10 for x = 0 to 3 20 print x 30 next x |
0
1
2
3
for defines the starting and ending values of a loop variable. The program proceeds until it reaches a next referencing the same loop variable. Then it increments the loop variable, returns to the top of the loop, and keeps going. When the loop variable exceeds the ending value, the loop ends and the program continues.
The statements between the for and next have no special status (e.g., they're not recognized as a "block"). Control can leave the loop and come back:
#lang basic-demo-2
10 for x = 0 to 3
20 gosub 50
30 next x
40 end
50 print x
60 return
#lang basic-demo-2 10 for x = 0 to 3 20 gosub 50 30 next x 40 end 50 print x 60 return |
0
1
2
3
By default, the loop variable is incremented by 1 on each pass. This can be adjusted with an optional step value at the top of the loop:
#lang basic-demo-2
10 for x = 0 to 3 step .5
20 print x
30 next x
#lang basic-demo-2 10 for x = 0 to 3 step .5 20 print x 30 next x |
0
0.5
1
1.5
2
2.5
3
The key feature shared by subroutines and loops is that they both jump back to an earlier point in the program. return jumps back to a corresponding gosub; next to a corresponding for.
"OK, then we can model them as variants of goto." Good idea, but there's more to the story. goto gets its destination from an explicit value passed as an argument. return and next, by contrast, have to infer their destinations. 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 beginning.
For instance, in this program, gosub is called twice, so the return first sends us back to line 10, and then to line 20:
#lang basic-demo-2
10 x = 10 : gosub 40
20 x = 20 : gosub 40
30 end
40 print x
50 return
#lang basic-demo-2 10 x = 10 : gosub 40 20 x = 20 : gosub 40 30 end 40 print x 50 return |
10
20
In this case, the same return statement sends us to two different destinations.
With next, the presence of the loop variable as an argument provides a clue where to go. +In real BASIC, the loop variable can be omitted from next. We're not going to implement that version, though the difference is just a little extra housekeeping. In principle, at compile time, we could sift through the lines of the program to find the corresponding for statement, and stash it inside the next:
#lang basic-demo-2
10 for x = 0 to 3
20 print x
30 next x rem we could make this mean `goto 10`
#lang basic-demo-2 10 for x = 0 to 3 20 print x 30 next x rem we could make this mean ` goto 10 ` |
The problem is that a loop variable can be used any number of times, so matching next statements to for statements might get complicated:
#lang basic-demo-2
10 for x = 0 to 3 : print x : next x
20 for x = 4 to 6
30 print x
40 next x
50 for x = 7 to 9
60 print x
70 next x
#lang basic-demo-2 10 for x = 0 to 3 : print x : next x 20 for x = 4 to 6 30 print x 40 next x 50 for x = 7 to 9 60 print x 70 next x |
But wait—there's more. A next statement doesn't just jump back to the for. It acts as a conditional: it increments the loop variable, 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 corresponding for, but also the end value of its loop. We won't necessarily be able to determine this end value until the program is running:
#lang basic-demo-2
10 for x = 1 to 3
20 for y = 1 to x
30 print x ; y
40 next y : next x
#lang basic-demo-2 10 for x = 1 to 3 20 for y = 1 to x 30 print x ; y 40 next y : next x |
11
21
22
31
32
33
Here, the y loop runs three times, and next y tests for a different maximum value each time.
We're back in the same situation that we were with return, where the behavior of the next statement necessarily depends on context only available at run time. So we can't rely on figuring out everything 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 available when we encounter the corresponding return or next.
That's exactly what continuations are for.
A continuation in a Racket program is a special kind of function that serves a similar purpose as a line number in BASIC: it marks a reference point within the program that we can return to later. Of course, a Racket program is structured around expressions, not lines. So a continuation can be captured at the position of any expression.
For example, if we have a program with four expression positions: +Namely: a function, two strings, and the result of applying the function to the strings.
(string-append "foo" "bar")
We can capture the continuation at the "foo" position by wrapping it in let/cc:
(string-append (let/cc this-cc
"foo") "bar")
Here, let/cc captures the current continuation (hence cc) and assigns it to this-cc (or whatever name we choose). +There are other functions that also capture continuations, but let/cc will suffice for everything we need to do.
let/cc otherwise works like ordinary let: after capturing the continuation, it evaluates the expressions within and returns the last as its result. So both these programs evaluate to "foobar".
If we want to save the continuation for later use, we can stash it inside another variable:
(define my-cc #f)
(string-append (let/cc this-cc
(set! my-cc this-cc)
"foo") "bar")
(procedure? my-cc) ; #t
(continuation? my-cc) ; #t
OK, we've captured a continuation. What can we do with it? The continuation is a function that takes one argument. When we call the continuation, it returns us to the position in the program where the continuation was captured (that is, the position of the let/cc). The argument to the continuation is used as the new value at that position (that is, it "replaces" the let/cc). If the continuation leaves us in the middle of a larger expression, the surrounding expression is re-evaluated. So if we call my-cc with "zam" as the argument:
(define my-cc #f)
(string-append (let/cc this-cc
(set! my-cc this-cc)
"foo") "bar")
(my-cc "zam")
We cause string-append to be evaluated a second time with "zam" instead of "foo" as the first argument:
"foobar"
"zambar"
If we capture a continuation at the string-append instead, everything works the same way, but now we can use the continuation to change the function applied to the arguments, rather than one of the arguments:
(define my-cc #f)
((let/cc this-cc
(set! my-cc this-cc)
string-append) "foo" "bar")
(my-cc (λ strs (apply string-append
(reverse (map string-upcase strs)))))
"foobar"
"BARFOO"
If this still seems weird, we can think of the continuation as a way of converting an ordinary expression into a function of an argument x, where x goes in the position marked by let/cc. Below, the function cc-ish roughly approximates how let/cc works:
(define my-cc #f)
(string-append (let/cc this-cc
(set! my-cc this-cc)
"foo") "bar") ; "foobar"
(my-cc "zam") ; "zambar"
(define (cc-ish [x "foo"]) (string-append x "bar"))
(cc-ish) ; "foobar"
(cc-ish "zam") ; "zambar"
Having drawn a parallel between continuations and BASIC line numbers, we should be careful not to press the analogy too far. Continuations have a couple important differences from line numbers:
-
Line numbers are hard-coded into a BASIC program, so it's a reference system that exists at compile time. By contrast, continuations can only be captured at run time. In practice, this means that we can't use a continuation until we've actually evaluated the corresponding let/cc during the program run.
-
In turn, this implies that we can only use continuations to jump backward to points in the program already visited. Whereas in BASIC, we can use line numbers to jump to previously visited lines, or lines not yet visited. So continuations are inherently more limited than goto with line numbers.
Still, though they're not a tool of first resort, continuations are useful in situations that require unusual kinds of control flow. For example, we used exceptions to implement our program-end signal for the end statement, and the change-line signal for goto. Under the hood, exceptions are implemented with continuations. This works because an exception is a way of jumping back through the calling chain.
Likewise, our return and next statements need to jump back to a previously visited point in a BASIC program. This time, we can't use exceptions. Unlike end and goto, the places we want to revisit are not in the calling chain. But we can implement these statements directly with continuations.
To our list of reserved-terms, we add six new ones: gosub, return, for, to, step, and next. These rules follow the statement syntax described above:
basic/lexer.rkt
#lang br
(require brag/support)
(define-lex-abbrev digits (:+ (char-set "0123456789")))
(define-lex-abbrev reserved-terms (:or "print" "goto" "end" "+" ":" ";" "let" "=" "input" "-" "*" "/" "^" "mod" "(" ")" "if" "then" "else" "<" ">" "<>" "and" "or" "not" "gosub" "return" "for" "to" "step" "next"))
(define basic-lexer
(lexer-srcloc
["\n" (token 'NEWLINE lexeme)]
[whitespace (token lexeme #:skip? #t)]
[(from/stop-before "rem" "\n") (token 'REM lexeme)]
[reserved-terms (token lexeme lexeme)]
[(:seq alphabetic (:* (:or alphabetic numeric "$")))
(token 'ID (string->symbol lexeme))]
[digits (token 'INTEGER (string->number lexeme))]
[(:or (:seq (:? digits) "." digits)
(:seq digits "."))
(token 'DECIMAL (string->number lexeme))]
[(:or (from/to "\"" "\"") (from/to "'" "'"))
(token 'STRING
(substring lexeme
1 (sub1 (string-length lexeme))))]))
(provide basic-lexer)
Otherwise, our lexer remains the same.
We add four new rules to cover our new statements: b-gosub, b-return, b-for, and b-next. We also add them to the right side of the b-statement rule:
basic/parser.rkt
#lang brag
b-program : [b-line] (/NEWLINE [b-line])*
b-line : b-line-num [b-statement] (/":" [b-statement])* [b-rem]
@b-line-num : INTEGER
b-rem : REM
@b-statement : b-end | b-print | b-goto
| b-let | b-input | b-if
| b-gosub | b-return | b-for | b-next
b-end : /"end"
b-print : /"print" [b-printable] (/";" [b-printable])*
@b-printable : STRING | b-expr
b-goto : /"goto" b-expr
b-let : [/"let"] b-id /"=" (STRING | b-expr)
b-if : /"if" b-expr /"then" (b-statement | b-expr)
[/"else" (b-statement | b-expr)]
b-input : /"input" b-id
@b-id : ID
b-gosub : /"gosub" b-expr
b-return : /"return"
b-for : /"for" b-id /"=" b-expr /"to" b-expr [/"step" b-expr]
b-next : /"next" b-id
b-expr : b-or-expr
b-or-expr : [b-or-expr "or"] b-and-expr
b-and-expr : [b-and-expr "and"] b-not-expr
b-not-expr : ["not"] b-comp-expr
b-comp-expr : [b-comp-expr ("="|"<"|">"|"<>")] b-sum
b-sum : [b-sum ("+"|"-")] b-product
b-product : [b-product ("*"|"/"|"mod")] b-neg
b-neg : ["-"] b-expt
b-expt : [b-expt ("^")] b-value
@b-value : b-number | b-id | /"(" b-expr /")"
@b-number : INTEGER | DECIMAL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #lang brag b-program : [b-line] (/NEWLINE [b-line])* b-line : b-line-num [b-statement] (/":" [b-statement])* [b-rem] @b-line-num : INTEGER b-rem : REM @b-statement : b-end | b-print | b-goto | b-let | b-input | b-if | b-gosub | b-return | b-for | b-next b-end : /"end" b-print : /"print" [b-printable] (/";" [b-printable])* @b-printable : STRING | b-expr b-goto : /"goto" b-expr b-let : [/"let"] b-id /"=" (STRING | b-expr) b-if : /"if" b-expr /"then" (b-statement | b-expr) [/"else" (b-statement | b-expr)] b-input : /"input" b-id @b-id : ID b-gosub : /"gosub" b-expr b-return : /"return" b-for : /"for" b-id /"=" b-expr /"to" b-expr [/"step" b-expr] b-next : /"next" b-id b-expr : b-or-expr b-or-expr : [b-or-expr "or"] b-and-expr b-and-expr : [b-and-expr "and"] b-not-expr b-not-expr : ["not"] b-comp-expr b-comp-expr : [b-comp-expr ("="|"<"|">"|"<>")] b-sum b-sum : [b-sum ("+"|"-")] b-product b-product : [b-product ("*"|"/"|"mod")] b-neg b-neg : ["-"] b-expt b-expt : [b-expt ("^")] b-value @b-value : b-number | b-id | /"(" b-expr /")" @b-number : INTEGER | DECIMAL |
We'll build our expander functions for b-gosub and b-return into our existing "go.rkt" module. Every time we reach a b-gosub, we save a continuation onto a stack. When we reach a b-return, we get the most recent continuation off the stack and invoke it. So the implementation looks like this:
basic/go.rkt
#lang br
(require "struct.rkt" "line.rkt")
(provide b-end b-goto b-gosub b-return)
(define (b-end) (raise (end-program-signal)))
(define (b-goto num-expr)
(raise (change-line-signal num-expr)))
(define return-ccs empty)
(define (b-gosub num-expr)
(let/cc here-cc
(push! return-ccs here-cc)
(b-goto num-expr)))
(define (b-return)
(when (empty? return-ccs)
(raise-line-error "return without gosub"))
(define top-cc (pop! return-ccs))
(top-cc (void)))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
We make a new stack called return-ccs. Within b-gosub, we use let/cc to capture the continuation as here-cc and push! it onto the stack. We then pass our b-gosub argument 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 corresponding b-gosub, so we use raise-line-error (which, presciently, we made in better line errors) to signal the problem.
Otherwise, we pop! the topmost continuation from the stack, and invoke it with a (void) argument. The effect is to jump back to the b-gosub where the continuation was captured, and replace the let/cc expression with (void). This is equivalent to a statement that does nothing. The program will continue normally from that point.
We can quickly test that our gosub and return are working with our earlier test program:
#lang basic
10 gosub 50
20 gosub 70
30 print "third"
40 end
50 print "first"
60 return
70 print "second"
80 return
#lang basic 10 gosub 50 20 gosub 70 30 print "third" 40 end 50 print "first" 60 return 70 print "second" 80 return |
first
second
third
We can also check that our return error works correctly:
#lang basic
10 gosub 50
20 return
50 print "hello"
60 return
#lang basic 10 gosub 50 20 return 50 print "hello" 60 return |
hello
error in line 20: return without gosub
hello error in line 20: return without gosub |
When we pick the right tool for the job, the rest is easy.
Earlier, we noticed that for and next have to cooperate at a distance:
-
for marks the top of the loop, sets the initial value of the loop variable, its maximum value, and optionally a step value (which defaults to 1).
-
next increments the variable by the step value and checks if the new value is less than or equal to the maximum value established by for. If it is, we return to the top of the loop with the new value. Otherwise, the loop ends and the program continues after the next.
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:
(define-macro-cases b-for
[(_ LOOP-ID START END) #'(b-for LOOP-ID START END 1)]
[(_ LOOP-ID START END STEP) #'(b-let LOOP-ID START)])
( define-macro-cases b-for [( _ LOOP-ID START END ) #' ( b-for LOOP-ID START END 1 )] [( _ LOOP-ID START END STEP ) #' ( b-let LOOP-ID START )]) |
That brings everything 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 implementing gosub and return that we can use a continuation to jump backward. Unsurprisingly, that's how we travel from next back to for.
We also learned that we can use a continuation to fill in a new value at the position where the continuation is captured. Among other things, next restarts the loop with a new value assigned to our loop variable. So it might not be a bad idea to capture a continuation around the assignment value:
(define-macro-cases b-for
[(_ LOOP-ID START END) #'(b-for LOOP-ID START END 1)]
[(_ LOOP-ID START END STEP) #'(b-let LOOP-ID (let/cc loop-cc
START))])
( define-macro-cases b-for [( _ LOOP-ID START END ) #' ( b-for LOOP-ID START END 1 )] [( _ LOOP-ID START END STEP ) #' ( b-let LOOP-ID ( let/cc loop-cc START ))]) |
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 expression with a new value, which will cause the b-let to be evaluated again, thereby assigning 42 to the LOOP-ID. Invoking the continuation will also move us back to the top of loop. So calling loop-cc with a new value is equivalent to restarting the loop with that value.
Now that we have a means of traveling back to the top of the loop with a new value, the path forward reveals itself:
-
With gosub and return, we kept a stack of continuations in the order we found them. This time, we make a hash table that stores the continuation associated with each for loop. We use the LOOP-ID as the key. For the value, we store a lambda function that handles the loop housekeeping, including the continuation.
-
When we reach a next, we'll use its argument to get the corresponding function out of the hash table, and run it.
The gimmick here is that although for and next appear to be cooperating, under the hood, b-for will be doing all the heavy lifting, by setting up a function that can be called by b-next.
Let's frame out that much:
(define next-funcs (make-hasheq))
(define-macro-cases b-for
[(_ LOOP-ID START END) #'(b-for LOOP-ID START END 1)]
[(_ LOOP-ID START END STEP)
#'(b-let LOOP-ID
(let/cc loop-cc
(hash-set! next-funcs
'LOOP-ID
(λ () ···))
START))])
(define-macro (b-next LOOP-ID)
#'(begin
(unless (hash-has-key? next-funcs 'LOOP-ID)
(raise-line-error
(format "`next ~a` without for" 'LOOP-ID)))
(define func (hash-ref next-funcs 'LOOP-ID))
(func)))
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 corresponding key. Otherwise, we fetch the function and execute it.
Now we just need to fill in the lambda. The finished "go.rkt" looks like this:
basic/go.rkt
#lang br
(require "struct.rkt" "line.rkt" "misc.rkt")
(provide b-end b-goto b-gosub b-return b-for b-next)
(define (b-end) (raise (end-program-signal)))
(define (b-goto num-expr)
(raise (change-line-signal num-expr)))
(define return-ccs empty)
(define (b-gosub num-expr)
(let/cc this-cc
(push! return-ccs this-cc)
(b-goto num-expr)))
(define (b-return)
(when (empty? return-ccs)
(raise-line-error "return without gosub"))
(define top-cc (pop! return-ccs))
(top-cc (void)))
(define next-funcs (make-hasheq))
(define-macro-cases b-for
[(_ LOOP-ID START END) #'(b-for LOOP-ID START END 1)]
[(_ LOOP-ID START END STEP)
#'(b-let LOOP-ID
(let/cc loop-cc
(hash-set! next-funcs
'LOOP-ID
(λ ()
(define next-val
(+ LOOP-ID STEP))
(if (next-val
. in-closed-interval? .
START END)
(loop-cc next-val)
(hash-remove! next-funcs
'LOOP-ID))))
START))])
(define (in-closed-interval? x start end)
((if (< start end) <= >=) start x end))
(define-macro (b-next LOOP-ID)
#'(begin
(unless (hash-has-key? next-funcs 'LOOP-ID)
(raise-line-error
(format "`next ~a` without for" 'LOOP-ID)))
(define func (hash-ref next-funcs 'LOOP-ID))
(func)))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
Inside the lambda, we're implementing the steps we already set out. We increment 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 continuation loop-cc with next-val as the argument. 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 function that checks whether a value is between two other values. We need to take a little care because the end value is not necessarily greater than the start value (for instance, when the step value is negative).
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:
#lang basic
10 for h = 1 to 2
20 for t = 2 to 4 step 2
30 for d = 9 to 8 step -1
40 gosub 60
50 next d : next t : next h : print "done" : end
60 print h ; t ; d
70 return
#lang basic 10 for h = 1 to 2 20 for t = 2 to 4 step 2 30 for d = 9 to 8 step -1 40 gosub 60 50 next d : next t : next h : print "done" : end 60 print h ; t ; d 70 return |
129
128
149
148
229
228
249
248
done
129 128 149 148 229 228 249 248 done |
Let's also try a program with a missing for statement:
#lang basic
10 for x = 1 to 3
20 print x
30 next x
40 next x
#lang basic 10 for x = 1 to 3 20 print x 30 next x 40 next x |
1
2
3
error in line 40: `next x` without for
1 2 3 error in line 40: `next x` without for |
- 1 intro
- 2 specification and setup
- 3 the syntax colorer
- 4 better line errors
- 5 variables and input
- 6 expressions
- 7 conditionals
- 8 subroutines and loops
- 9 recap
- 10 source listing
Source: https://beautifulracket.com/basic-2/subroutines-and-loops.html
0 Response to "Does Racket Have a Continue Function"
Post a Comment