We’ll write our expander by adding to the same "main.rkt" that already contains our reader. Here’s where we left it:
1 2 3 4 5 6 7 8 9 10 11 12 | #lang br/quicklang (module+ reader (provide read-syntax)) (define (read-syntax path port) (define wire-datums (for/list ([wire-str (in-lines port)]) (format-datum '(wire ~a) wire-str))) (strip-bindings #`(module wires-mod wires/main #,@wire-datums))) |
We recall that Racket starts the expander by calling a macro named #%module-begin. In wires, our #%module-begin is just going to pass everything through untouched, so it suffices to write this:
1 2 3 4 | (define-macro (wires-module-begin WIRE-DATUM ...) #'(#%module-begin WIRE-DATUM ...)) (provide (rename-out [wires-module-begin #%module-begin])) |
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 arguments to the parent #%module-begin imported from br/quicklang. In other words, our macro is doing nothing.
So let’s eliminate 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.
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:
1 2 3 4 5 6 7 8 9 | #lang wires-demo x AND y -> d x OR y -> e x LSHIFT 2 -> f y RSHIFT 2 -> g NOT x -> h NOT y -> i 123 -> x 456 -> y |
Will be converted by our reader into a module expression that looks like this:
1 2 3 4 5 6 7 8 9 | (module wires-mod wires/main (wire x AND y -> d) (wire x OR y -> e) (wire x LSHIFT 2 -> f) (wire y RSHIFT 2 -> g) (wire NOT x -> h) (wire NOT y -> i) (wire 123 -> x) (wire 456 -> y)) |
We can see from this sample that our wire macro will need to handle three types of wire definitions:
A wire holding a single value, like (wire 123 -> x).
A wire holding the result of an operation with one argument, like (wire NOT x -> h).
A wire holding the result of an operation with two arguments, like (wire x AND y -> d).
We also see that an argument on the left side of a wire definition 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 correspond to those listed above: the first case for a single value, the second for a one-argument operation, and the third for a two-argument operation. We’ll also add an else case to catch anything unexpected:
1 2 3 4 5 | (define-macro-cases wire [(wire ARG -> ID) ···] [(wire OP ARG -> ID) ···] [(wire ARG1 OP ARG2 -> ID) ···] [else ···]) |
Let’s start with the second and third cases. We make a simplifying observation: that OP ARG needs to be evaluated as the expression (OP ARG), and ARG1 OP ARG2 as the expression (OP ARG1 ARG2). This means we can design our macro in a recursive way. The results of the second and third cases can become new invocations of wire that match the first case:
In principle, there’s no problem with macros calling other macros (or themselves). Recursive macros can often be more compact. In practice, however, as with recursive functions, we still need to be careful not to create infinite recursion loops. Here, we can see that we’re safe, because each case of the macro matches a different number of arguments between wire and ->.
To make our recursion work, we wrap our arguments in a helper function called val (which we’ll write in a moment). We need val because our arguments might be wire functions or numbers. If ARG is a number, val will pass it through; if it’s a wire function, val will call the function.
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 ordinary define to create the wire function. 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 function 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.
define/display is another macro. First, it takes (ID) and BODY and puts them into a standard define form:
1 2 3 4 | (define-macro (define/display (ID) BODY) #'(begin (define (ID) BODY) ···)) |
Then it needs to print the name and value of the wire function. 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 functions 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+ automatically picks up the definitions of the surrounding code. But module+ has another handy feature: when multiple module+ declarations for the same submodule appear in a source file, they’re concatenated into a single submodule. Thus, module+ lets us build up a submodule piece by piece.
We’ll apply this technique to our main submodule and finish our define/display macro like so:
What’s happening here? After we define the wire function with (define (ID) BODY), we introduce a chunk of the main submodule with (module+ main ···). Inside this expression, we use 'ID to represent the quoted name of the wire function, and (ID) to get its run-time value. Even though the define and module+ appear next to each other in the code generated by this macro, the main submodule won’t run until this define—and the ones for the other wire functions—have all been evaluated.
We also need to write our other helper, val. Recall that val takes one argument, which may be a number or a wire function. If the argument is a number, val will pass it through. If it’s a wire function, val will call the function. Very easy:
Easy, but also wildly inefficient. 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 function will mean calling other wire functions, which in turn will call other wire functions ... leading to lots of redundant recomputation of intermediate wire values.
The better approach is to cache the value of a wire function after it’s computed the first time. Then, later calls will be much faster. We can implement 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 convention, hash-ref! ends with ! to signal that it mutates data (like set!). The first argument of hash-ref! is the hash table. The second is the key for the hash value. We’ll just use num-or-wire, the argument to val. The third argument is used to fill in the value if it’s missing from the hash table. Because this fill-in argument can be either a plain value or a function that computes the value, we use num-or-wire here as well. In sum, this means that the first call to val for a particular num-or-wire will cause its value to be computed. Every subsequent call to val for that argument will rely on the cache.
The code above will work just fine. Sometimes, however, we’d rather make a function-support value like val-cache private to the function 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 notation, this is a job for the famous “let over lambda” maneuver. What we do is write our function as a lambda expression, and then wrap a let around it to introduce val-cache. + A lambda expression can always be substituted for conventional function notation. See functions. 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 function? As a rule of thumb, we want to use functions where we can, and macros only where we must. val can be a function because it relies only on the run-time values of its arguments. define/display, by contrast, is building a submodule (which happens at compile time), and wanting to use the ID argument both as a raw name and as a run-time value. Therefore, it has to be a macro.
Also, why didn’t we provide our helper functions? Our expander only needs to provide bindings for identifiers 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.
Last, we need to implement our 16-bit operations: AND, OR, NOT, LSHIFT, and RSHIFT. As we did in jsonic, this is a good moment to peek at the Racket documentation to see if there’s something in the library we can build on. Indeed there is: Racket’s bitwise operations.
While these functions are nearly what we need, they work on integers of any size. As we remember from the puzzle description, our wires can only carry a 16-bit signal. So we need to make versions of these bitwise operations that roll over when they exceed the maximum 16-bit value of 65536.
To do this—again, with the most stylish possible notation—we’ll make helpers called mod-16bit and define-16bit:
1 2 3 | (define (mod-16bit x) (modulo x 65536)) (define-macro (define-16bit ID PROC-ID) #'(define ID (compose1 mod-16bit PROC-ID))) |
mod-16bit is a function that converts any integer to a 16-bit value by applying modulo with the maximum 16-bit value of 65536.
We use this conversion function within the define-16bit macro. This macro takes two arguments: the name of a new function (ID), and the name of an existing function (PROC-ID). Then we use compose1 to combine our mod-16bit with PROC-ID. So when we say:
We’re making a new function where each component function is applied in order from right to left:
There’d be nothing wrong with writing our macro using this explicit lambda expression; compose1 is just the sleeker notation.
With this helper macro in hand, we can make short work of our 16-bit operations:
1 2 3 4 5 6 7 8 9 10 | (define (mod-16bit x) (modulo x 65536)) (define-macro (define-16bit ID PROC-ID) #'(define ID (compose1 mod-16bit PROC-ID))) (define-16bit AND bitwise-and) (define-16bit OR bitwise-ior) (define-16bit NOT bitwise-not) (define-16bit LSHIFT arithmetic-shift) (define (RSHIFT x y) (LSHIFT x (- y))) (provide AND OR NOT LSHIFT RSHIFT) |
Here’s what our expander should look like after adding it to our existing "main.rkt" that already contained our reader:
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 | #lang br/quicklang (module+ reader (provide read-syntax)) (define (read-syntax path port) (define wire-datums (for/list ([wire-str (in-lines port)]) (format-datum '(wire ~a) wire-str))) (strip-bindings #`(module wires-mod wires/main #,@wire-datums))) (provide #%module-begin) (define-macro-cases wire [(wire ARG -> ID) #'(define/display (ID) (val ARG))] [(wire OP ARG -> ID) #'(wire (OP (val ARG)) -> ID)] [(wire ARG1 OP ARG2 -> ID) #'(wire (OP (val ARG1) (val ARG2)) -> ID)] [else #'(void)]) (provide wire) (define-macro (define/display (ID) BODY) #'(begin (define (ID) BODY) (module+ main (displayln (format "~a: ~a" 'ID (ID)))))) (define val (let ([val-cache (make-hash)]) (lambda (num-or-wire) (if (number? num-or-wire) num-or-wire (hash-ref! val-cache num-or-wire num-or-wire))))) (define (mod-16bit x) (modulo x 65536)) (define-macro (define-16bit ID PROC-ID) #'(define ID (compose1 mod-16bit PROC-ID))) (define-16bit AND bitwise-and) (define-16bit OR bitwise-ior) (define-16bit NOT bitwise-not) (define-16bit LSHIFT arithmetic-shift) (define (RSHIFT x y) (LSHIFT x (- y))) (provide AND OR NOT LSHIFT RSHIFT) |
Now we’re ready to test the language.