Thank you for your comment

Beau­tiful Racket / tuto­rials

Imagine a language: wires

Recall that in our jsonic language spec­i­fi­ca­tion, we had the idea to treat ordi­nary JSON as valid source code for our DSL.

We’ll take a similar approach here. Our puzzle input describes the wires in a circuit. But we could also think of it as the source code of a language that doesn’t yet exist. If we create that language, we can convert the puzzle input from an inert file to some­thing we can run with Racket. And then we can get the solu­tion to our puzzle ques­tion.

That language is wires.

Require­ments

The puzzle gives us a smaller working circuit that will also be a valid wires program. Let’s start there and see what we can figure out:

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
1
2
3
4
5
6
7
8
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
copy to clipboard

According to the puzzle, each line describes the input to a wire. The name of the wire is on the right end of the line. The input is on the left, sepa­rated by ->. A wire receives the result of one of six types of input:

  1. A constant value, like 123 or 456.

  2. A NOT oper­a­tion, which takes one other constant value or wire as its argu­ment.

  3. An oper­a­tion combining two other constant values or wires—either AND,

  4. OR,

  5. LSHIFT,

  6. or RSHIFT.

If we can handle these six kinds of input, we should be able to model any wire.

The puzzle also asks us to deter­mine the value on a wire. So we’ll print the value of every wire as demon­strated in the puzzle descrip­tion. We can see how this works now by running our sample circuit as a wires-demo program:

#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
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
copy to clipboard
d: 72
e: 507
f: 492
g: 114
h: 65412
i: 65079
x: 123
y: 456
1
2
3
4
5
6
7
8
d: 72
e: 507
f: 492
g: 114
h: 65412
i: 65079
x: 123
y: 456
copy to clipboard

Two wrin­kles:

First, a circuit descrip­tion is a flat list of wires (like a stacker program was a flat list of argu­ments). There­fore, the wires language won’t have a recur­sive struc­ture. This will let us simplify our reader. Specif­i­cally, we can avoid using a sepa­rate grammar-based parser.

Second, even though the circuit descrip­tion is a flat list, the depen­den­cies between wires might be in any order. For instance, in the circuit above, the first six wire defi­n­i­tions rely on values from wires x and y, which aren’t defined until the end.

Design

As a rule of thumb, we want to model each element of a domain-specific language using its closest equiv­a­lent in Racket. Why? Because we’re making a source-to-source compiler, so we’d like to avoid rein­venting wheels, or pounding round pegs into square holes. Wise modeling choices lead to simpler imple­men­ta­tions, because we’re dele­gating more of the heavy lifting to Racket.

For wires, our key insight is that each wire name can be thought of as an iden­ti­fier, and each wire descrip­tion as a define expres­sion binding that iden­ti­fier. Further­more, the bitwise oper­a­tions appearing on the left side of each wire descrip­tion—like NOT, OR, and LSHIFT—are just func­tions that take wires as their argu­ments.

In pseudocode, we could imagine trans­forming the sample circuit into a Racket program that looks like this (assuming for now that we’ve imple­mented the bitwise oper­a­tions):

(define d (AND x y))
(define e (OR x y))
(define f (LSHIFT x 2))
(define g (RSHIFT y 2))
(define h (NOT x))
(define i (NOT y))
(define x 123)
(define y 456)
1
2
3
4
5
6
7
8
(define d (AND x y))
(define e (OR x y))
(define f (LSHIFT x 2))
(define g (RSHIFT y 2))
(define h (NOT x))
(define i (NOT y))
(define x 123)
(define y 456)
copy to clipboard

This meets some of our require­ments. The big problem is that the wire defi­n­i­tions are out of order. So if we were to run this program, it would fail in the first line when eval­u­ating (AND x y), because x and y aren’t bound yet. We can trigger the same error with this anal­o­gous test program:

(define d (+ x y))
(define x 123)
(define y 456)
1
2
3
(define d (+ x y))
(define x 123)
(define y 456)
copy to clipboard
x: undefined;
 cannot reference an identifier before its definition
1
2
x: undefined;
 cannot reference an identifier before its definition
copy to clipboard

So we need a way of setting up rela­tion­ships between wires, while delaying the actual eval­u­a­tion until requested. The simplest fix is to instead model each wire as a func­tion (again in pseudocode):

(define (d) (AND (x) (y)))
(define (e) (OR (x) (y)))
(define (f) (LSHIFT (x) 2))
(define (g) (RSHIFT (y) 2))
(define (h) (NOT (x)))
(define (i) (NOT (y)))
(define (x) 123)
(define (y) 456)
1
2
3
4
5
6
7
8
(define (d) (AND (x) (y)))
(define (e) (OR (x) (y)))
(define (f) (LSHIFT (x) 2))
(define (g) (RSHIFT (y) 2))
(define (h) (NOT (x)))
(define (i) (NOT (y)))
(define (x) 123)
(define (y) 456)
copy to clipboard

Converting the wires into func­tions doesn’t change their under­lying values. But it does delay the eval­u­a­tion of each wire until we invoke that partic­ular wire func­tion. It also makes it possible to have refer­ences between wires that are out of order.

Again, we can see how this works by updating our test program and running it again:

(define (d) (+ (x) (y)))
(define (x) 123)
(define (y) 456)
1
2
3
(define (d) (+ (x) (y)))
(define (x) 123)
(define (y) 456)
copy to clipboard

This time, no error. And if we eval­uate (d) on the REPL:

(d)
1
> (d)
copy to clipboard

We get the right answer:

579
1
579
copy to clipboard

This gives us enough of a roadmap to start building the language.

We’ll also need to figure out how to imple­ment our bitwise oper­a­tions and our printing routine. We’ll deal with those as they arise.

Setup

Follow the instruc­tions in the master recipe to make a wires direc­tory and install it as a package. As with stacker, we’ll be able to build this language using one (hard-working) source file called "main.rkt".

wires/main.rkt
#lang br/quicklang
···
1
2
#lang br/quicklang
···
copy to clipboard

We’re building our language using a single source file. So the "main.rkt" module will contain both the reader and the expander.

← prev next →