# Type-Level Programming in Scala, Part 5a: Binary numbers

The Nat operations are generally limited to results under 10,000. Compilation time gets quite long or the stack overflows beyond that. An alternative is to use a binary representation of numbers, called Dense here after the implementation in Okasaki’s Purely Functional Data Structures. We will use this representation to solve a simplified Project Euler problem in the type system in the next post.

Only the basic form and the implementations of increment and shift are shown here. See the full source for Add, Mult, and Exp.

First, we need a Digit type to represent a bit. It has two subtypes, One and Zero. We define a type member to Match on the subtype and a Compare member for comparing digits.

```sealed trait Digit {
type Match[ IfOne <: Up, IfZero <: Up, Up] <: Up
type Compare[D <: Digit] <: Comparison
}
sealed trait Zero extends Digit {
type Match[ IfOne <: Up, IfZero <: Up, Up] = IfZero
type Compare[D <: Digit] = D#Match[ LT, EQ, Comparison]
}
sealed trait One extends Digit {
type Match[ IfOne <: Up, IfZero <: Up, Up] = IfOne
type Compare[D <: Digit] = D#Match[ EQ, GT, Comparison]
}
```

For example:

```  type Is0[D <: Digit] = D#Match[ False, True, Bool ]
implicitly[ Is0[Zero] =:= True ]
implicitly[ One#Compare[Zero] =:= GT ]
```

Next, we create the Dense type. It is a type level heterogeneous list with element types constrained to be Digits. The head of the list is the least significant bit. The last element of a non-empty list is always One and is the most significant bit. An empty list represents zero.

```sealed trait Dense {
type digit <: Digit
type tail <: Dense
type Inc <: Dense
type ShiftR <: Dense
type ShiftL <: Dense
}
sealed trait DCons[d <: Digit, T <: Dense] extends Dense {
type digit = d
type tail = T
type Inc = d#Match[ Zero :: T#Inc, One :: T, Dense ]
type ShiftR = tail
type ShiftL = Zero :: DCons[d, T]
}
sealed trait DNil extends Dense {
type tail = Nothing
type digit = Nothing
type Inc = One :: DNil
type ShiftR = DNil
type ShiftL = DNil
}
```

We see that shifts come easily with Dense (compared to Nat). It is just the tail of the list (shift right) or prepending a zero (shift left).

We can predefine some integers (using the alias :: for DCons):

```   type ::[H <: Digit, T <: Dense] = DCons[H, T]

type _0 = DNil
type _1 = One :: DNil
type _2 = Zero :: One :: DNil
type _3 = One :: One :: DNil
type _4 = Zero :: Zero :: One :: DNil
type _5 = One :: Zero :: One :: DNil
...
```

As usual, we define a conversion to values:

```   def toInt[ D <: Dense](implicit drep: DRep[D]): Int = drep.value

final class DRep[D <: Dense](val value: Int)

implicit def dnilToRep = new DRep[DNil](0)
implicit def dcons0ToRep[D <: Dense](implicit tailRep: DRep[D]): DRep[DCons[Zero, D]] = new DRep(tailRep.value * 2)
implicit def dcons1ToRep[D <: Dense](implicit tailRep: DRep[D]): DRep[DCons[One, D]] = new DRep(tailRep.value * 2 + 1)
```

See Dense.scala for the implementation of other operations, like addition and multiplication. Example usage:

```  toInt[ _14 ] == 14
toInt[ _5#Inc ] == 6
toInt[ _12#Mult[_8]#Mult[_13] ] == 1248
toInt[ _4#Exp[_15] ] == 1073741824
```

The last line compiles in under a second, which shows that higher numbers are handled better using this representation and converting them to actual integer values is not a problem. (Ok, it helped that 4 is a power of two. _3#Exp[_8] is actually more problematic for Dense than Nat.)

Dense will make a good example for keys in a type-level map later. Next, we’ll solve a (much) smaller version of a Project Euler problem using these type-level binary numbers. We will need Match and Compare defined on Dense for that (implementations on github):

```  type Match[ NonZero <: Up, Zero <: Up, Up] <: Up
type Compare[B <: Dense] <: Comparison
```

## 4 thoughts on “Type-Level Programming in Scala, Part 5a: Binary numbers”

1. This is awesome, amazing technology. And already presented in a fairly polished, easy-to-consume package.

I was mucking around with it and it appears (as you hinted), that _3#Exp[_8] is massively slower to compile than _4#Exp[_8]. Why is this?

2. Mark says:

Because the base (4) is a power of 2, there is a single 1 digit in the binary representation. Roughly, work has to be done for exponentiation and multiplication when a digit is 1 and nothing or very little has to be done when a digit is 0.

You can see the details in the definitions for ReceiveMult and ReceiveExp, where you’ll see digit#Match[ … ]. The first argument is what to do if digit is 1 and the second is for when it is 0. In both ReceiveMult and ReceiveExp, a simple value is returned when the digit is 0.

https://github.com/harrah/up/blob/master/Dense.scala#L51

3. To follow up my earlier comment on sloooow compile speed of _3#Exp[_8]. I revisited this project today, with compiler from a 2.10 trunk nightly build, and measured average compile times over 3 repeated trials each.

_3#Exp[_8]: 21 seconds
_4#Exp[_8]: 4 seconds

The massive difference suggests there something going wrong, ie more than just a few more bit operations..?