# Constructions on Annotations

In the last chapter, we built the `Snap*`

machine – a memory cell which “captures” some polymorphic input, and continuously outputs it until a signal comes in telling it to capture something new. This is exactly how your computer remembers the contents of a file when you save it, albeit our `Snap*`

machinery is at a smaller scale. The goal of the next chapter is to fix that and build real memory blocks for ourselves. The goal for *this* chapter, however, is to build some abstractions *on top of our multiwire annotations* in order to do that.

Conceptually, the way we will do this is by putting a bunch of `Snap*`

machines side by side, routing the same polymorphic input into them, and then use the value of a nybble to help “route” our `S`

napshot wire into “the correct machine.” This should somewhat remind you of the work we did on `Demux2`

, where we fed the same input into our `and`

games, and used a `Split`

machine to route a switching signal to the correct `and`

gate that we wanted. If the details of this construction aren’t fresh in your memory, it might be helpful to review Chapter 7 on Multiplexing again before continuing.

In effect, what we want is a demuxer that is *polymorphic* in its `D`

estination wire as well as its value wire. If this were the case, we’d be able to route an input between \(2^n\) destinations (where `:n`

is our wire annotation), rather than just the two (\(2^1=2\) when our `D`

*isn’t* polymorphic) that `Demux2`

gives us.

The black-box machine diagram we want is this:

Black-box machine diagrams do little more than to tell us the *interface* we want our machine to have. More specifically, they are useful primarily to give annotations to any multiwires in our diagram. Here, `Demux`

takes an input `A:n`

and another input `D:d`

. The output has this weird `:(2^d,n)`

annotation, which we’ll discuss shortly.

## Constructions on Annotations

Annotations are interesting beasts – they describe the general “shape” of what a multiwire must look like. Of course, at the end of the day, multiwires are nothing but lots of wires side-by-side, with no real structure for them. These annotations describe a pattern that exists mostly in our brains.

Whenever you see the word “pattern” in this book (and more generally, whenever you see patterns in real life), you should immediately begin asking yourself “how can we abstract this pattern?” How can we describe the same-ness or different-ness of one pattern compared to another? What are the defining characteristics of this pattern, that we could use to spot another one?

Once these questions are answered, you begin to be capable of describing all the *specific instances* of a pattern (eg. train, car, boat, plane, dog sled) as *instances of the pattern itself* (eg. vehicles). In doing so, you have lost some specificity, but gained the ability to manipulate and think larger thoughts about the specific instances that this pattern represents.

And so we find ourselves looking at multiwire annotations as a pattern, because we’d like to manipulate them. We want to find a means of describing one annotation in terms of some other one.

The simplest way to do this is to acknowledge that our annotations can be interpreted as *numbers*, and indeed, this is what they have been so far. Our nybbles are annotated as `:4`

, for example. This suggests we should be able to perform *algebra* on our annotations. A nybble with an extra wire to store some auxiliary information might have the annotation `:4+1`

, which of course is just `:5`

. More interestingly, our *polymorphic* wire annotated as `:n`

might go through a machine which equips it with a similar auxiliary wire – the output to such a machine might be `:n+1`

.

If we can add wires, we can probably multiply them too. And indeed, we can. However, there are two interpretations of what it means to multiply annotations together. The first is in terms of *numbers*, so `:2*3`

is just the annotation `:6`

. The other interpretation is more *structural*. Consider this table:

While this table has \(6\) cells, it equivalently has \(2\) rows of \(3\) columns. In an annotation context, this interpretation would be labeled `:(2,3)`

. It’s an interesting construction to think about, because this table metaphor generalizes pretty well. Instead of thinking of *multiplication*, we can instead think of *replacement*. `:(2,3)`

can be thought of an annotation where each of the *single wires* in `:2`

are replaced with *multiwires* with annotation `:3`

.

In short, this diagram, the expanded form of a multiwire `:2`

:

becomes this diagram, where we’ve replaced each of the single wires with multiwires:

which, of course, is the same as this *expanded* multiwire:

While `:(2,3)`

is *syntactically* equivalent to `:6`

, they have very different *semantics* when viewed under this light. `:6`

has no structure to it, while `:(2,3)`

indicates a structure of two multiwires, each with annotation `:3`

.

Therefore, these structural `:(x,y)`

annotations can be thought of as *multi-multiwires*. We will refer to this structure as a **product annotation**.

Takeaway: A product annotation

`:(x,y)`

is a replacement of each of the individual wires in a multiwire`:x`

themselves with a multiwire`:y`

.

In this sense, multiwire annotations are *algebraic*, because we can perform *algebra* on them. Don’t worry, just because we’re doing algebra on multiwire annotations doesn’t mean we ever need to actually *solve* that algebra. We leave that work to the plebes responsible for actually implementing these wonderful designs of ours.

## Back to Sanity

Returning to our `Demux`

black-box, we see that it has inputs `A:n`

and `D:d`

, and an output `:(2^d,n)`

. Here `2^d`

is a barbaric rendering of \(2^d\), which as we remember, is equivalent to the count of the unique numbers we can describe in a multiwire with `d`

bits. `Demux`

is thus creating a multiwire for every possible number we can describe in `d`

bits, and each of them is of size `:n`

. This is the big bubba great granddaddy of our old `Demux2`

machine.

Notice that the annotations on our inputs and outputs tell us a huge amount of what this machine must do, despite the fact that we don’t actually know what’s inside of it.

We’ll start with a simple example to help drive the point home. Consider the following machine:

There’s really only one “honest” implementation for this machine, in the sense that these are the true (most parsimonious) annotations for the inputs and outputs. The only *obvious* implementation of this machine is to output a 1 on the wire equivalent to the value of input multiwire. Why? Well the only relationship that we know between `:x`

and `:2^x`

is that we can represent \(2^x\) different numbers with `x`

bits. This implies we are probably expanding out the number we’ve encoded in the input multiwire. This expansion is only ever going to be *one* of the \(2^x\) possibilities, implying we should probably put a 1 on that line.

Note that this isn’t the only implementation we could have made, but it’s the most likely based on what we know.

Back to `Demux`

, due to our previous argument, it’s almost certainly evaluating the number stored in our `:d`

multiwire, since our output is a product of `2^d`

and `n`

. Recall that a product is the replacement of the single wires in a multiwire each with a multiwire, so `:(2^d,n)`

is, by the same argument, some way of moving `n`

into the number described by `d`

.

That’s as far as our analysis can get, since we don’t know what that means of moving `n`

into `2^n`

is, but we’ve already come quite some distance, analytically.

Enough chatting. Let’s build the dang thing. But first, a lemma from above:

We leave the implementation of this machine as an exercise to the reader, but as our analysis showed earlier, the annotations here are powerful enough for us to reason about this machine without knowing exactly how it might work. Of course, that might not be satisfactory to you, and you are welcome to work out the function table for this as a first step to implementing it. It’s really not that hard!

Anyway, we now present `Demux`

:

The jankiness at the first input to the `and`

gate is unfortunate, but necessary. It’s to indicate we’re expanding all of the `:2^d`

multiwire and piping each of them into a copy of the `and`

gate. We need that extra single wire going directly into the `and`

gate to distinguish from the syntax we established earlier where we wanted to “zip” the wires in two multiwires together. See the implementation for `Add4`

if you don’t remember this concession.

There’s a growing trend that our machine diagrams get simpler and simpler as our diagram language becomes more and more powerful, and as we build more powerful machines to harness. `Demux`

would have been literally impossible to build without polymorphic multiwires (although you could build `Demux`

for any *particular* annotation).

Given `Demux`

, we’re now set to build that memory block we’ve been discussing seemingly *ad infinitum*, but we’ll have to do it in the next chapter.

## Exercises

- Flesh out the implementation for the
`Eval`

machine. - What’s the difference between “zipping” two multiwires like we did in
`Add4`

, vs multiplying them like we are in our`and`

gate in`Demux`

? When are you capable of zipping multiwires? How about multiplying?