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[ _5#Add[_7] ] == 12 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

Pingback: Type-Level Programming in Scala « Apocalisp

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?

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

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..?