Implementing an ALU in TypeScript’s Type System

Compute a Fibonacci number using your own type

Generated with StableDiffusion

In this article, we are giving an example implementation of an ALU. Some of the operations that we will implement are bitwise operations like shifts and arithmetic operations like addition and subtraction.

In the end, we’ll see how we can use most of these operations to implement a type that can compute a fibonacci number.

All the constructs we’re using are TS types, and all the computation is done at build time. There is no JS running our types. We are relying on the typing system to do the computation.

With that in mind, let’s get started.

The Base Types

We need a way to represent a bit. For this, we start with representing the two states a bit can have (0 or 1).

The next step is to define a bit as being a union type of the two states.

Type declaration for a bit

With this in place, we can move on to define a byte. For this, we are gonna use tuples.

type Byte = [Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit];

This is a very simple representation of a byte in the TS type system, but it is enough to start working on our ALU operations.

We can now define a few helper types we can use down the line.

type ZERO_BYTE = [Zero, Zero, Zero, Zero, Zero, Zero, Zero, Zero]
type ONE_BYTE  = [Zero, Zero, Zero, Zero, Zero, Zero, Zero, One]

Bitwise Operations

By having a type for bit, let’s see how we can implement not , and , or and xor for bits.

For this will be heavily using constrained generics and conditional types.

Bitwise operations

Let’s look a bit over the implementation details:

Bit negation is the simplest one. We constraint T to be a Bit, and then we check if it’s Zero. If that’s the case, we define the type as being One. Otherwise, we define the type as being Zero.

This means that we can now use BitNot like this.

type OneNegated = BitNot<One>

And that type will actually be Zero.

We do something similar to BitAnd, but this time we need to define it as having two generic types: LHS and RHS. We are using conditional types to be able to implement branching inside the typing system. The simplest way to define AND is to check if both of them extend One and return One in that case.

This is very similar to the following code:

if (LSH === One) {
 if (RHS === One) {
   return One 
 } else {
   return Zero
 }
} else {
 return Zero
}

Because of the nature of conditional types, all branches must resolve to a type. This is the reason why we have Zero appearing two times. This makes this implementation more verbose.

We do something similar for BitOr .

BitXor is a bit more verbose because there’s no way to short-circuit the evaluation, so we have to consider all four possibilities.

Byte-Wise Operations

We now have all that we need to implement byte-wise operations.

From now on, we will heavily rely on inferring within condition types. We need a way to walk a tuple and apply the operations to each component. A way of achieving this is by using generic with conditional types and inferring only part of the tuple. We can do something similar to this:

type Walkable<T extends Byte> = T extends [infer U extends Bit, ...infer R extends Bit[]] ? U : []

This is a lot to grok in one sitting, so let’s look a bit over it.

We are specifying that T extends Byte. This means that it is a tuple composed of 8 Bit .

The next step is to use conditional with extends to split the tuple and be able to refer to the head of the tuple. In this context the head of the tuple means the first Bit in the Byte.

We can reference that type U on the true branch of the conditional. The same applies to R which is a tuple type with all of the remaining Bits .

The simplest operations that we can implement now are ShiftLeft and ShiftRight.

ShiftLeft and ShiftRight

Let’s take a close look at what’s going on with ShiftLeft. We are inferring the type for the left most Bit, and then we create a new type that ignores it and unpacks Rand adds Zero. This essentially moves the least most significant 7 bits to the left.

Now we can use it like this:

ShiftLeft<[Zero, Zero, Zero, One, Zero, Zero, Zero, One]>

or using the helpers that we defined early on:

ShiftLeft<ONE_BYTE>

and that will end up being:

[Zero, Zero, One, Zero, Zero, Zero, One, Zero]

Something very similar is done for ShiftRight.

Byte Not and Xor

Implementing not and xor for bytes uses a similar technique, but it’s a bit more involved.

The reason why not and xor are more involved is related to the fact that after the split of head and tail of a byte, we need to apply the same rule again for the tail . The problem with this is that tail is not a Byte any more, as it a tuple with only 7 elements. The way out of this is to use another type definition that allows for any Bit[] .

Here’s a small implementation for Not:

ByteNot implementation

What happens here is that we’re using BitNot to flip the head bit. Then we apply the type again, but this time on the remaining bits in the byte. This is actually a form of tail-recursion, and we’ll use it more in future operations.

We can use it like this:

type Flipped = ByteNote<[Zero, One, One, Zero, One, One, One, Zero]>

And Flipped will actually be:

[One, Zero, Zero, One, Zero, Zero, Zero, One]

XOR is a bit more complicated as we need 2 Byte to create the operation. But we can use the same concepts as before:

• constrained generics
• conditional types
• using inferring and tail recursion to walk the byte

Because we have two operators and the fact that we need conditional types for the inference of head and tail of the Byte the code is harder to read. But the techniques used are the same.

XOR

One thing to notice about the implementation is that we’re stopping the recursion by returning an empty array [] . The reason why this works is that if TS cannot make the inference anymore in the extends clauses it will take the alternative route. In this case, using the empty tuple as a type.

Arithmetic Operation

We now have all the pieces to start implementing arithmetic operations. Our goal is to be able to add and subtract bytes.

Increment

The first thing we can build is the ability to increment . This means that we want to add 1 to a Byte .

This is something that you’ll see a lot while implementing these operations:

T extends [...infer U extends Bit[], infer R extends Bit]

This time around, we need to start processing the Byte from the tail, so we’ll use the same infer technique, but instead of capturing the first Bit we will capture the last and then use recursion on the remaining bits.

Now we need to check if R has the value One or not.

Why is this important?

If R is Zero then we change it to One , unpack U and we’re done. On the other hand, if R is One then we need to change it to Zero and then continue adding One to the next Bit . This is the recursion part.

T extends [...infer U extends Bit[], infer R extends Bit] ? R extends One ? [...PartialAddOne<U>, Zero] : [...U, One] : []

The complete implementation is this:

Increment

We can now use it like this:

type ONE = AddOne<[Zero, Zero, Zero, Zero, Zero, Zero, Zero, Zero]>

The result will be:

[Zero, Zero, Zero, Zero, Zero, Zero, Zero, One]

Notice that the number we end up with is the Byte representation of it and not a number in the sense we’re used to.

We can now generate a positive number (actually, we can generate any Byte representation, as the fact that it is positive or not, is a semantic problem).

All of these are valid operations now:

type ZERO = [Zero, Zero, Zero, Zero, Zero, Zero, Zero, Zero]
type ONE = AddOne<ZERO>
type TWO = AddOne<ONE>
type THREE = AddOne<AddOne
type FOUR = AddOne<THREE>

Add with carry

Before we can move to implementing a full add between 2 Bytes we need to be able to keep the carry between bits addition.

ALUs usually have to carry flag (CF) that can be used for this. But from this point of view, TS doesn’t have a global state. So we cannot just store that somewhere and use it later. We need to always be able to pass it around.

To accomplish this, we create a few types that will help us:

type CarryFlag = Bit;
type BitWithCarry = {
    cf: CarryFlag
    value: Bit
}

Now we can refer to the BitWithCarry flag when needed.

Just like we did with implementing Bit logical operations so we can use them on the Byte later by using tail recursion , we’ll do the same now.

We need to implement the ability to add 2 bits together, store the value of the resulting Bitand also the carry value.

We can look over the truth table of this operation to guide us in the implementation:

+------+------+------+------+------+
| Bit1 | Bit2 |  CF  | BitR |  CR  |
+------+------+------+------+------+
| 1    | 1    | 1    | 1    | 1    |
+------+------+------+------+------+
| 1    | 1    | 0    | 0    | 1    |
+------+------+------+------+------+
| 1    | 0    | 1    | 0    | 1    |
+------+------+------+------+------+
| 1    | 0    | 0    | 1    | 0    |
+------+------+------+------+------+
| 0    | 1    | 1    | 0    | 1    |
+------+------+------+------+------+
| 0    | 1    | 0    | 1    | 0    |
+------+------+------+------+------+
| 0    | 0    | 1    | 1    | 0    |
+------+------+------+------+------+
| 0    | 0    | 0    | 0    | 0    |
+------+------+------+------+------+

We now need to implement this in TS using conditional types. This is a daunting task, but we end up with something similar to this:

With this in hand, we can start implementing the add operation for bytes .

We’ll use the same techniques as before:

• infer the last bit
• use AddBitsWithCarry on the last bits
• use an auxiliary type for the head bits
• pass the value of cf to the auxiliary type, as that’s needed for the rest of the bits

We end up with something similar to this:

ByteAdd implementation

A few things to notice:

• We used a default value for a generic param here CH extends CarryFlag = Zero . This is mandatory in our case, but it does make PartialAdd more flexible.
• When recursively referencing the type, we call AddBitsWithCarry twice. First, to get the value and then to get cf even if we are passing the same params. This is again because there is no global state in the TS type system.

Subtracting and multiplying

Now that we have the groundwork done, implementing other operations is a lot easier.

For subtraction, we are gonna use the 2’s complement. In short, we need to negate the Byte and then add one to it. This is extremely easy to do with all the types we have:

type Byte2Complement<T extends Byte> = AddOne<ByteNot<T>>

Subtracting now becomes very easy. We need to compute the 2’s complement of the RHS and then add it to the LHS:

type Subtract<LHS extends Byte, RHS extends Byte> = Add<LHS, Byte2Complement<RHS>>

As a convenience operation, we can implement decrement:

type SubtractOne<LHS extends Byte> = Subtract<LHS, ONE_BYTE>

We’re now in a place where we can tackle implementing multiply . We need to think of multiplication as a repeated addition . We are gonna do recursion again and decrement the LHS until it reaches One.

LHS reaching One is our stopping condition from this recursion.

We also need to cater to the case when LHS is actually Zero so we have a special condition for this. In the end, we end up with this:

type Mul<
  LHS extends Byte,
  RHS extends Byte,
  Result extends Byte = RHS
> = ONE_BYTE extends LHS
  ? Result
  : ZERO_BYTE extends LHS
  ? ZERO_BYTE
  : Mul<SubtractOne<LHS>, RHS, Add<Result, RHS>>;

Notice how Result defaults to RHS . This is so we cover both the case when we stop because of the recursion or when LHS is actually One .

Now we can use it like this:

Mul<ONE_BYTE, ZERO_BYTE>
Mul<[Zero, Zero, Zero, Zero, Zero, Zero, One, Zero], [Zero, Zero, Zero, Zero, Zero, Zero, One, Zero]>

Which, in the second case, will end up:

[Zero, Zero, Zero, Zero, Zero, One, Zero, Zero]

Comparison Implementation

Our ALU wouldn’t be complete without some comparison implementations (actually, we could also use some division, but we’ll do this later).

Note: all comparison operations are done in an unsigned manner.

EQ

The first comparison that we can implement, and the easiest, is EQ . We want to see if 2 Bytes are equal. We can easily do this by subtracting one Byte from another and checking if that’s zero. In our language, we can write it like this:

type EQ<LHS extends Byte, RHS extends Byte> = ZERO_BYTE extends ByteXOR<LHS, RHS> ? true : false

LT (less than)

For implementing LT we need a bit of help first. The main idea behind implementing this is to walk the bytes from left to right (from the most significant to the least significant) and decide on the different first bit.

While the bits are the same, the current operation is undecided . This means that we need to move to the next pair.

To help with this step will create a helper type that will return true , false or undecided . This will help a lot with typing down the road. For now, let’s see this in action:

type BitLTB<LHS extends Bit, RHS extends Bit> = Zero extends LHS
  ? One extends RHS
    ? true
    : "undecided"
  : One extends RHS
  ? "undecided"
  : false;

Now we can move with the complete implementation. The idea is the same as before:

• infer the Head and Tails from both operands
• use BitLTB to see if we can dedice, if we can then return that value
• if the value is undecided then go to the next bit

As before, the implementation is a bit hard to look at:

LT implementation

Once again, because we have no global state, we need to call BitLTB multiple times. We could probably make this a bit shorter if we check for boolean extends BitLTB .

Now we can use it like this:

LT<ZERO_BYTE, ONE_BYTE> // will result in true
LT<ONE_BYTE, ZERO_BYTE> // will result in false

With LT implemented, the rest of the comparison operations are pretty easy to implement:

LTE

Nothing more than LTE or EQ

type LTE<LHS extends Byte, RHS extends Byte> = true extends LT<LHS, RHS> ? true : EQ<LHS, RHS>

GT

Is just LT , but with the operands swapped.

type GT<LHS extends Byte, RHS extends Byte> = LT<RHS, LHS>

GTE

The same but with the help with LTE.

type GTE<LHS extends Byte, RHS extends Byte> = LTE<RHS, LHS>

Division

The last operation that we’ll implement is division with remainder.

We’ll use LT and Subtraction to accomplish this. We will return a type that has two quantities:

• quotient
• remainder

We do need to take into account division by zero. So, we’ll use an internal type for the successive subtraction and use the main type just for the zero check. We end up with something like this:

type DivInternal<LHS extends Byte, RHS extends Byte, Q extends Byte = ZERO_BYTE> = true extends LT<LHS, RHS> ? {
    q: Q,
    r: LHS
} : DivInternal<Subtract<LHS, RHS>, RHS, AddOne<Q>>
type Div<LHS extends Byte, RHS extends Byte> = ZERO_BYTE extends RHS ? "Division by 0" : DivInternal<LHS, RHS>

The main Div type checks if RHS is Zero and returns an "Division by 0" string.

In the case when RHS is not 0 we defer to DivInternal . It subtracts RHS from LHS until LHS is less than RHS . We know that this can be accomplished as RHS is not zero. We can now use it like this:

Div<TWO, ONE> // we get {q: TWO, r: ZERO_BYTE}
Div<ONE, ZERO_BYTE> // we get "Division by 0"
Div<[Zero, Zero, Zero, Zero, One, Zero, One, Zero], TWO> // we get {q:[Zero, Zero, Zero, Zero, Zero, One, Zero, One], r: ZERO_BYTE}

Fibonacci Implementation

All of this took us to the point where we can implement the fibonacci numbers.

The idea of this implementation builds on the same principles as before:

• generic constrained types
• conditional types

We define a FIBONACCI type that has three generic arguments

• C the current index in the computing
• A the current number in the sequence
• B the previous number in the sequence

Then we just decrement C compute a new A as the sum of A and B , change the new B as the old A . We also need to have a stop condition. This is represented if C is 1 or 2. Let’s see this in action:

Fibonacci

With all of this, we can compute fibonacci sequence numbers by passing the binary representation for the number.

FIBONACCI<[Zero, Zero, Zero, Zero, Zero, One, One, One]>

It will compute the 7th value in the Fibonacci sequence, which is:

[Zero, Zero, Zero, Zero, One, One, Zero, One] // 13

Closing Thoughts

We showed a way to implement a simple ALU using TypeScript’s type system.

The main techniques we’ve used are:

• generic constrained types
• conditional generics to achieve branching
• conditional generics that reference themselves to achieve loops (recursion)

A complete implementation of this can be found in this GitHub repo. The repo also has a battery of tests used to validate the operations.

I hope you enjoyed reading this. See you in the next article.