Adding numbers the hard way

I finally got to read the second part of Robey Pointer "How to add numbers" blog posts. Thinking about hardware "algorithms" can be interesting because distributed systems face similar problems sometimes. Below is my implementation of Kogge-Stone addition for 32 bits integers. Brent-Kung hybrid is very clever, but I couldn't figure out an obvious "step" for Brent-Kung that could be recursed into.

def add(x: Int, y: Int, cin: Boolean) = {
  def intToBooleanArray(n: Int): Array[Boolean] = {
    (0 until 32 map ((1).<<) map (n.&) map (0.!=)).toArray
  }

  val xs: Array[Boolean] = intToBooleanArray(x)
  val ys: Array[Boolean] = intToBooleanArray(y)

  // P means cout depends on cin
  // G means cout is 1 regardless of cin
  case class PG(p: Boolean, g: Boolean)
  def p(a: Boolean, b: Boolean) = a ^ b
  def g(a: Boolean, b: Boolean) = a & b

  // initial PG from input alone
  val pg0 = (xs, ys).zipped map ((a, b) => PG(g = g(a, b), p = p(a, b)))

  // Execute combine step until all PGs are final
  def combStep(lastPGs: Array[PG], finalPGs: Array[PG], step: Int): Array[PG] = {
    // Combines PGs formed by adjacent block of bits
    def comb(pga: PG, pgb: PG): PG = PG(p = pgb.p & pga.p, 
                                        g = pgb.g | (pgb.p & pga.g))

    if (lastPGs.isEmpty) finalPGs
    else {
      val (newFinalPGs, tempPGs) = lastPGs splitAt (step - step / 2)
      val nextPGs = (finalPGs ++ lastPGs, tempPGs).zipped map comb

      combStep(nextPGs, finalPGs ++ newFinalPGs, step << 1)
    }
  }

  val pgs = combStep(pg0, finalPGs = Array.empty, step = 1)

  // Carry for each bit
  def cout(cin: Boolean)(pg: PG): Boolean = pg.g | (pg.p & cin)
  val cn = pgs map cout(cin)

  // Final result for each bit
  val sn = (pg0 map (_.p), cin +: (cn take 31)).zipped map ((p, c) => p ^ c)

  // Convert boolean array back into an int
  val result = (sn.zipWithIndex map { 
    case (s, i) => if (s) 1 << i else 0
  }).sum
  (result, cn.last)
}

Pattern matching on abstract types with Scala 2.10.0

Scala 2.10.0 is out, and one of its greatest improvements is a completely new pattern matching algorithm on the compiler. That algorithm fixes lots of bugs that have existed all the way up to 2.9.x and adds more and better static checks.

One interesting thing that has probably gone unnoticed by most, however, is that it can do more than what the old pattern matcher did, in at least one respect: it can match against abstract types, provides a ClassTag.

To understand that better, consider this REPL session on Scala 2.9.2:

scala> def f[T: ClassManifest](l: List[Any]) = l collect {
     |   case x: T => x
     | }
<console>:8: warning: abstract type T in type pattern T is unchecked sin
ce it is eliminated by erasure
         case x: T => x
                 ^
f: [T](l: List[Any])(implicit evidence$1: ClassManifest[T])List[T]

scala> f[String](List(1, 2.0, "three"))
res0: List[String] = List(1, 2.0, three)

Now let's look at what can be done with Scala 2.10.0:

scala> import scala.reflect.ClassTag
import scala.reflect.ClassTag

scala> def f[T: ClassTag](l: List[Any]) = l collect {
     |   case x: T => x
     | }
f: [T](l: List[Any])(implicit evidence$1: scala.reflect.ClassTag[T])List
[T]

scala> f[Int](List(1, 2.0, "three")) // It can't find Int because they are boxed
res0: List[Int] = List()

scala> f[String](List(1, 2.0, "three")) // But AnyRefs are ok
res1: List[String] = List(three)

Note that it doesn't reify types -- that is, it can't tell whether your List[Any] is a List[String], but it does go a bit further than what was possible before.