Monday, February 17, 2014

Two Thirds

This is not my usual programming-related blog post. I decided to blog about books I have been reading.

I'm a long time fan of the Honor Harrington Series, a military science fiction series that draws on the spirit of 17~19 century naval series such as Horatio Hornblower or Aubrey-Maturin (from which sprang the movie Master and Commander: The Far Side of the World ) . These days, however, there are enough secondary stories in that universe that stories advancing the main plot are rather hard to come by. Though, on the other hand, one could say that the original story has finally concluded, and what's going on now is a new story.

For a bit, I tried to turn to a follow up on what is possibly my favorite fantasy trilogy of books, The Deed of Paksenarrion. Elizabeth Moon returned to the series with Oath of Fealty, followed by other books, but they pale in comparison with the original, which was a quite believable, and somewhat moving, story of the daughter of a sheep farmer on the back beyond who becomes a paladin.

So, in despair, I tried searching for other stuff. First I came upon The Kingkiller Chronicles, feeling somewhat like the last one to know of it (and if you didn't know of it you should immediately get The Name of the Wind and The Wise Man's Fear ). So, that's three books of which only two are written. This is fantasy, but, honestly, that's beside the point -- it is the prose and the attention to detail that make these books great reading.

Back to waiting, I looked around and found The Golden Threads Trilogy, a mix of fantasy and science fiction (though the latter mainly from the second book) story that's quite clever. I particularly love how everyone in the first book, Thread Slivers, has a different conception of what's going on and what other people want. It's highly amusing. The second book, Thread Strands, sadly decreases the fog of war factor, and leads to... well, I'll have to wait for the third book to get published to find out. Again.

As I waited, I noticed that the March Upcountry series by John Ringo was getting combo-treatment, with March Upcountry and March to the Sea being bundled in Empire of Man. It seems March to the Stars and We Few, the fourth and final book, will be out in a combo soon as well. Anyway, this is military science fiction pitting commandos against dinosaurs and spear-wielding aliens. What's not to like? :)

Now, after I re-read these books, I decided to search for other stuff by John Ringo, and came upon Black Tide Rising, a zombie series. This is one of the "realistic zombies" kind of series, where people aren't really zombies, just infected with a rabies-like virus. It tries to be realistic in the portrayal of how people survive and fight back as well, though its world is rather lighter than I feel is realistic. I don't mind though: I prefer more cheerful worlds, even in a zombie apocalypse, than what I think is realistic. :)

Anyway, I read Under a Graveyard Sky in a single day, then followed up with To Sail a Darkling Sea a little slower... but only because, damn!, that's it for now. And it's not even going to be a trilogy! As a bonus, the first book comes with a "zombie clearance playlist" -- nice! :)

Wednesday, February 13, 2013

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)
}

Friday, January 18, 2013

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.

Tuesday, December 11, 2012

Bugs and dynamically vs statically typed languages

Something occurred to me that, unfortunately, was just a little bit too big for a tweet, so I decided to blog instead, and add more context.

While thinking about the perennial question of whether static typing help reduce the number of bugs in an otherwise well tested code base, I was reminded of how many bugs I saw tagged by newer versions of Scala with improved static analysis and correctness, or how damn hard it is to do variance right when you start using it.

I was then struck by a thought: the "bugs" I was thinking of were not caught by tests because no feature in the code actually used the buggy class in a way that revealed the bug. This also relates to variance, because variance in Java is defined at the usage site, instead of definition site. The definitions are all invariant in Java (aside from arrays).

So, thinking about it, I came up with the following hypothesis:

Dynamically typed language proponents consider "bugs" to be things that the user of the software can cause it to do, while statically typed language proponents consider "bugs" to be things that users of the code can cause it to do.

That would certainly account for some differences in attitude and beliefs I perceive. On the other hand, it might just be my imagination.