Imagine a language: wires

We’ll write our expander by adding to the same "main.rkt" that already contains our reader. Here’s where we left it:

Starting the expander

We recall that Racket starts the expander by calling a macro named #%module-begin. In wires, our #%module-begin is just going to pass every­thing through untouched, so it suffices to write this:

But since we’re going for style points in this language, we can take a shortcut. Our wires-module-begin macro is just passing its argu­ments to the parent #%module-begin imported from br/quicklang. In other words, our macro is doing nothing.

So let’s elim­i­nate it. Instead, we can just provide the #%module-begin imported from br/quicklang:

Remember, we’re not violating any language rules here. Racket expects our language to provide a macro called #%module-begin. But Racket neither knows nor cares where we get that macro. In most cases, we’ll want to write our own. But in this case, we can reuse an existing one.

The wire macro

Our first full macro will handle the (wire ···) datums that are emitted from the reader, each of which defines a wire. For instance, our sample wires source:

Will be converted by our reader into a module expres­sion that looks like this:

We can see from this sample that our wire macro will need to handle three types of wire defi­n­i­tions:

We also see that an argu­ment on the left side of a wire defi­n­i­tion can be either a wire or a number.

When we come across a macro that needs to handle multiple cases, we should think of define-macro-cases. Here, we’ll define our wire macro with three patterns that corre­spond to those listed above: the first case for a single value, the second for a one-argu­ment oper­a­tion, and the third for a two-argu­ment oper­a­tion. We’ll also add an else case to catch anything unex­pected:

Let’s start with the second and third cases. We make a simpli­fying obser­va­tion: that OP ARG needs to be eval­u­ated as the expres­sion (OP ARG), and ARG1 OP ARG as the express­sion (OP ARG1 ARG2). This means we can design our macro in a recur­sive way. The results of the second and third cases can become new invo­ca­tions of wire that match the first case:

In prin­ciple, there’s no problem with macros calling other macros (or them­selves). Recur­sive macros can often be more compact. In prac­tice, however, as with recur­sive func­tions, we still need to be careful not to create infi­nite recur­sion loops. Here, we can see that we’re safe, because each case of the macro matches a different number of argu­ments between wire and ->.

To make our recur­sion work, we wrap our argu­ments in a helper func­tion called val (which we’ll write in a moment). We need val because our argu­ments might be wire func­tions or numbers. If ARG is a number, val will pass it through; if it’s a wire func­tion, val will call the func­tion.

Now we can fill in the first case. We’ll use a helper macro called define/display (also to be written in a moment). This macro will work like an ordi­nary define to create the wire func­tion. But will also print its name and value at the end. So the body of define/display will be like that of define: we’ll write (ID) to signal that we’re making a func­tion called ID. As we did in the other cases, we also wrap ARG with val.

Finally, the else branch simply returns #'(void), so the full macro looks like this:

Now let’s write our helpers for our core wire macro: define/display and val.

Helper: define/display

define/display is another macro. First, it takes (ID) and BODY and puts them into a stan­dard define form:

Then it needs to print the name and value of the wire func­tion. For this, we’ll use the special main submodule. When Racket runs a module directly (as opposed to importing it into another module), it will load the module and then run its main submodule, if it exists. Because the main submodule runs after the rest of the module has been loaded, it’s useful for any tasks that need to be deferred. In this case, we need to define all our wire func­tions before we can print their values. So we’ll put the printing routine inside a main submodule.

To define the main submodule, we’ll use module+ again, which we also used to make the reader. We saw how a submodule made with module+ auto­mat­i­cally picks up the defi­n­i­tions of the surrounding code. But module+ has another handy feature: when multiple module+ decla­ra­tions for the same submodule appear in a source file, they’re concate­nated into a single submodule. Thus, module+ lets us build up a submodule piece by piece.

We’ll apply this tech­nique to our main submodule and finish our define/display macro like so:

What’s happening here? After we define the wire func­tion with (define (ID) BODY), we intro­duce a chunk of the main submodule with (module+ main ···). Inside this expres­sion, we use 'ID to repre­sent the quoted name of the wire func­tion, and (ID) to get its run-time value. Even though the define and module+ appear next to each other in the code gener­ated by this macro, the main submodule won’t run until this define—and the ones for the other wire func­tions—have all been eval­u­ated.

Helper: val

We also need to write our other helper, val. Recall that val takes one argu­ment, which may be a number or a wire func­tion. If the argu­ment is a number, val will pass it through. If it’s a wire func­tion, val will call the func­tion. Very easy:

Easy, but also wildly inef­fi­cient. The way the puzzle is designed, every wire in our circuit will end up holding a single value. But the way val is written, calling a wire func­tion will mean calling other wire func­tions, which in turn will call other wire func­tions ... leading to lots of redun­dant recom­pu­ta­tion of inter­me­diate wire values.

The better approach is to cache the value of a wire func­tion after it’s computed the first time. Then, later calls will be much faster. We can imple­ment a cache with a hash table:

Here, we use make-hash to create a mutable hash table called val-cache. Then, in the body of val, we write into this cache with hash-ref!.  + By Racket conven­tion, hash-ref! ends with ! to signal that it mutates data (like set!). The first argu­ment of hash-ref! is the hash table. The second is the key for the hash value. We’ll just use num-or-wire, the argu­ment to val. The third argu­ment is used to fill in the value if it’s missing from the hash table. Because this fill-in argu­ment can be either a plain value or a func­tion that computes the value, we use num-or-wire here as well. In sum, this means that the first call to val for a partic­ular num-or-wire will cause its value to be computed. Every subse­quent call to val for that argu­ment will rely on the cache.

The code above will work just fine. Some­times, however, we’d rather make a func­tion-support value like val-cache private to the func­tion itself. The approach shown in the code below won’t work—though it makes val-cache private, it also makes a new val-cache on each call to val, which amounts to no cache at all:

Again, since we’re picking up some slick nota­tion, this is a job for the famous “let over lambda” maneuver. What we do is write our func­tion as a lambda expres­sion, and then wrap a let around it to intro­duce val-cache.  + A lambda expres­sion can always be substi­tuted for conven­tional func­tion nota­tion. See func­tions. Because val-cache is outside the lambda, it will only be created once, and persist for every call to val. But because it’s still inside the define, it won’t be visible anywhere else in the module:

By the way, why did we write define/display as a macro, and val as a func­tion? As a rule of thumb, we want to use func­tions where we can, and macros only where we must. val can be a func­tion because it relies only on the run-time values of its argu­ments. define/display, by contrast, is building a submodule (which happens at compile time), and wanting to use the ID argu­ment both as a raw name and as a run-time value. There­fore, it has to be a macro.

Also, why didn’t we provide our helper func­tions? Our expander only needs to provide bind­ings for iden­ti­fiers that are used in the module code produced by the reader. wire appears in that code, so we have to provide it. But define/display and val are used only within the expander, so they can remain private.

The 16-bit oper­a­tions

Last, we need to imple­ment our 16-bit oper­a­tions: AND, OR, NOT, LSHIFT, and RSHIFT. As we did in jsonic, this is a good moment to peek at the Racket docu­men­ta­tion to see if there’s some­thing in the library we can build on. Indeed there is: Racket’s bitwise oper­a­tions.

While these func­tions are nearly what we need, they work on inte­gers of any size. As we remember from the puzzle descrip­tion, our wires can only carry a 16-bit signal. So we need to make versions of these bitwise oper­a­tions that roll over when they exceed the maximum 16-bit value of 65536.

To do this—again, with the most stylish possible nota­tion—we’ll make helpers called mod-16bit and define-16bit:

mod-16bit is a func­tion that converts any integer to a 16-bit value by applying modulo with the maximum 16-bit value of 65536.

We use this conver­sion func­tion within the define-16bit macro. This macro takes two argu­ments: the name of a new func­tion (ID), and the name of an existing func­tion (PROC-ID). Then we use compose1 to combine our mod-16bit with PROC-ID. So when we say:

We’re making a new func­tion where each compo­nent func­tion is applied in order from right to left:

There’d be nothing wrong with writing our macro using this explicit lambda expres­sion; compose1 is just the sleeker nota­tion.  + The 1 in compose1 refers to the number of argu­ments the composed func­tion accepts. If we needed to accept more argu­ments, we could use compose.

With this helper macro in hand, we can make short work of our 16-bit oper­a­tions:

Checking the expander

Here’s what our expander should look like after adding it to our existing "main.rkt" that already contained our reader:

Now we’re ready to test the language.