Sunday, September 7, 2008

HList in Scala Revisited (or Scala Metaprogramming Works!)

The Scala compiler team listened to my request for supporting recursive type projections (ticket #1291) and has added experimental support for it. If you have a new build of the compiler (latest nightly or Eclipse plugin will do) you can enable it by add the compiler option "-Yrecursion x", where x is the maximum recursion depth allowed. Thanks to the EPFL team for the help, and particularly Geoffrey for implementing the fix.

The HList code I presented in my previous post now compiles without errors. I've setup a project at Assembla with the HList code and other metaprogramming constructs like booleans, natural numbers, integers, units etc. The library is in pre-alpha stage and there's lots of work to be done, for example the HList type is missing many methods found in the Scala List type.

Basically anything you can do with a normal List you can do with a HList, but all operations are type safe on an element by element basis. Here is some example code using HLists:

object HListExample {
import HLists._
import Nats._
import Utils._

// Create a HList of an Int, Boolean and a pair
val l1 = 10 :: true :: (10.1, "Hello") :: HNil

// Extract the second element, note that the element type
// information is preserved and we can safely perform a
// boolean and operation
l1.nth[_1] && false

// Create another HList, note the use of an operator in
// the type expression
val l2 : Double :: String :: Boolean :: HNil = 1.1 :: "string" :: false :: HNil

// Replace the second element in the list, it used to
// be a String, but now there's an Int inserted
val l3 = l2.remove[_1].insert(_1, 14)

// Type information is preserved, we can use an Int operation
// on the element
l3.nth[_1] * 10

// Append l2 to l1
val l4 = l1 ::: l2

// Statically check that the length of l4 is 6
type T = Equal[_6, l4.type#Length]

So, what are HLists useful for, besides being a fancy replacement for tuple types? Well, they can for example be used to implement a completely type safe object oriented programming language with support for delegation, subtyping etc. inside Scala. I will get back to that in a later blog entry.

The project code also contains a simple example of a type safe units library. Here's a usage example:

object UnitsTest {
import Units._
import Integers._

val dist : Length = measure(2.3) * m
val time : Time = measure(1.7) * s
val speed : Speed = dist / time

All units are checked at compile time, so you can't assign a length to a time variable for example.

There are lots of other use cases for metaprogramming and the library will continue to grow over time. However, there are some issues with metaprogramming in Scala, one being the speed of the compiler. Compiling types which expands to long paths can sometimes take a very long time. I have submitted a ticket about this too. Hopefully some optimizations are made to alleviate the problem. Meanwhile, I think certain applications of metaprogramming, for example compile time checked bounded integers, will put to much stress on the compiler and should probably be avoided.