Closing the loop: basic

In days of yore, a BASIC inter­preter would include a tiny “stan­dard library” of math oper­a­tions like SIN, TAN, INT, and LOG. All other oper­a­tions would need to be defined within the program as named func­tions.

We could reim­ple­ment these library func­tions in our own inter­preter. But two consid­er­a­tions.

First, it would be really boring.

Second, given that Racket has authen­ti­cally vast libraries of math func­tions, it would be nice to find a way to use them in our basic programs.

So let’s depart from tradi­tion and intro­duce a new import state­ment. It’ll work like require and make Racket func­tions avail­able within our program just like those created with def:

Pedaling uphill (again)

We can see that the main tasks will be:

The first task isn’t too hard. But we need to step gingerly when we add Racket iden­ti­fiers. BASIC supports infix nota­tion, and Racket doesn’t. There­fore, certain source strings that are valid BASIC expres­sions could also be read as Racket iden­ti­fiers or module names. If confu­sion ensues, programs will break:

Our lexer and parser are going to need some extra help distin­guishing these. So we’ll adopt a conven­tion that only a name in [square-brackets] will be treated as a Racket iden­ti­fier. Other­wise, it will be treated as an ordi­nary BASIC expres­sion. That way, we can mix them in our source code without risk of ambi­guity:

Next, we need to move our require forms at the top level of the module. Why do we need to do this at all? require has special status because it intro­duces bind­ings, and resolving bind­ings is a prereq­ui­site to expanding and eval­u­ating the program (see eval­u­a­tion). So Racket is picky about where require forms can appear. For instance, putting a require inside an expres­sion won’t work:

But moving the require ouside the let, to the top level, cures the problem:

“Can’t we just use a syntax lift, like we did in func­tions?” Unfor­tu­nately, no. Because require forms intro­duce bind­ings, these forms are resolved before deeper macro expan­sion begins. A syntax lift, by contrast, can only rearrange expres­sions during this deeper expan­sion. So lifts happen too late to help us with require.

Instead, we can adapt the tech­nique we used to imple­ment vari­ables. In that case, we needed to find all the unique vari­able refer­ences in the program so we could convert them into top-level define expres­sions. In the parser, we marked all the vari­ables with a special b-id rule. This rule was spliced, turning it into a syntax prop­erty that let us locate the right elements inside the parse tree.

This time, we’ll mark the import targets with a special parser rule called b-import-name. Then, in our #%module-begin, we’ll pull these names out of the parse tree and convert them to top-level require forms.

Before we finish, we’ll also need to smooth over the differ­ences between Racket and BASIC data types. BASIC can only handle inte­gers, deci­mals, and strings. Racket func­tions, by contrast, can return many other data types. To do this, we’ll update our b-func macro to reject any values that don’t have equiv­a­lents in BASIC.

Lexer updates

Our current lexer rule for BASIC iden­ti­fiers allows alphanu­meric strings that start with a letter (and might also contain $). We’re not going to change that.

But Racket iden­ti­fiers and module names aren’t as restricted, and frequently contain other char­ac­ters—for instance, ?, =, -, and /. So if we want to use the Racket names in our source code, we need a new lexing rule. To keep them distinct from BASIC expres­sions, we’ll also require that these names appear between square brackets.

To help with this, we intro­duce a new lexer abbre­vi­a­tion, racket-id-kapu, which will denote the char­ac­ters not allowed in a Racket iden­ti­fier.

To derive this abbre­vi­a­tion, we look in the Racket docu­men­ta­tion to see which char­ac­ters are permitted for symbols and iden­ti­fiers. It turns out that “any char­acter can appear directly in an iden­ti­fier, except for white­space and the following special char­ac­ters: ()[]{}",'`;#|\”. So we use :or to create a set of forbidden char­ac­ters, and assign this to racket-id-kapu.

Then we use this abbre­vi­a­tion to make the lexer pattern for our Racket iden­ti­fiers:

The lexer oper­ator :~ means “any char­acter but these”, so this pattern means “any sequence of char­ac­ters not in racket-id-kapu, between square brackets”.

On the right side of the rule, we trim the brackets from the matched lexeme using trim-ends and convert it to a symbol before pack­aging it as a new RACKET-ID token type.

In addi­tion to these changes, we also add our new import keyword to our list of reserved-terms. With these adjust­ments, our lexer looks like this:

Parser updates

Our parser updates are simpler. We add a new b-import rule to handle the import state­ment, and add b-import to the right side of the b-statement rule.

We also mark the import state­ment argu­ment with a spliced b-import-name rule. In the parse tree, this will be attached to the argu­ment as a syntax prop­erty:

The pattern for our b-import-name allows either a RACKET-ID or a STRING, because imported modules can be spec­i­fied with either an iden­ti­fier (e.g., math/number-theory) or a path name (e.g., "number-theory.rkt").

We also add RACKET-ID as a possi­bility in the func­tion posi­tion of the b-func rule.

Expander updates

First, we need to update "expander.rkt":

As promised at the outset, we extract our IMPORT-NAME argu­ments by searching through the parse tree for unique elements carrying the 'b-import-name syntax prop­erty.

To do this, we first update our find-unique-var-ids helper func­tion to take an argu­ment that deter­mines which prop­erty to find. Since we’re gener­al­izing the inter­face of this func­tion, we’ll also give it a more general name: find-property. We then replace our calls to find-unique-var-ids with calls to find-property, passing it a prop­erty name and a list of #'(LINE ...) syntax objects.  + In DrRacket, we could also right-click the name of our func­tion and use Rename …. This will update the vari­able name throughout the source file. In this case, we’re also changing the arity of the func­tion, which has to be updated manu­ally.

Having located the IMPORT-NAME objects, all we need to do is put them into a require at the top of the module.

Once we have Racket func­tions avail­able, we also need to smooth the differ­ences between Racket values and BASIC values. So let’s also update our b-func macro in "expr.rkt":

Here, we test the result of the func­tion expres­sion by passing it to the helper func­tion convert-result. If it’s a number, we hand it off to b-expr. If it’s a string, we pass it through. If it’s a Boolean, we convert it to an integer. Other­wise, we raise an error.  + We could’ve put the convert-result code inside the macro. But it’s good prac­tice to make the output of a macro as small as possible. See macros.

Finally, though we’ve hoisted our actual imports into require forms at the top level of the module, we still need to do some­thing with the b-import nodes that remain in the parse tree. So we just add a macro to "misc.rkt" that converts these nodes into (void):

Testing our imports

That should be all we need to make our orig­inal example work:

Let’s remove the first import state­ment and confirm that we get a sensible error:

Let’s also try calling a func­tion that returns an unus­able data type, in this case a list:

Looks good.

By the way