The kind of comments I keep getting on my static meta-programming with Scala blogs are often along the lines of: “The ability to encode Church Numerals in Scala still seems uselessly academic to me, but cool none-the-less”. In this blog I will show how meta-programming can be applied in practice – at least theoretically.
In my previous blogs I introduced a technique for static meta-programing with Scala. This technique uses Scala’s type system to encode values and functions on these values. The Scala compiler acts as interpreter of such functions. That is, the type checking phase of the Scala compiler actually carries out calculations like addition and multiplication.
In this post I show how to apply meta-programming for two practical problems: conditional compilation and loop unrolling. The examples make use of type level encoding for booleans and natural numbers. While I introduced an encoding for natural numbers before, I use an alternative method which is more powerful in this post. Previously it was not possible to build nested expressions having expressions as operands themselves. The new encoding supports such expressions. However, in general the new encoding depends on the -Yrecursion compiler flag which is experimental and as of now only available in the Scala trunk. The type level encoding for booleans is along the same lines as the one for natural numbers.
Conditional Compilation
Conditional compilation is useful for example for enabling or disabling debugging or logging statements. Ideally code which is excluded by a compile time condition does not have any effect on the run-time behavior of the rest of the code. That is, the rest of the code behaves exactly as if the excluded code were not there at all. Optimizing compilers generally remove code which is unreachable. This is where meta-programming fits in: type level encoded functions (meta-functions) are evaluated at run-time. The result of the evaluation is a type. Now we only need to trick the compiler into compiling a block of code or not compiling it depending on that type.
Lets first define meta-booleans and some operations on them (full code here):
object Booleans {
trait BOOL {
type a[t <: BOOL, f <: BOOL] <: BOOL
type v = a[TRUE, FALSE]
}
final class TRUE extends BOOL {
type a[t <: BOOL, f <: BOOL] = t
}
final class FALSE extends BOOL{
type a[t <: BOOL, f <: BOOL] = f
}
trait IF[x <: BOOL, y <: BOOL, z <: BOOL] extends BOOL {
type a[t <: BOOL, f <: BOOL] = x#a[y, z]#a[t, f]
}
trait NOT[x <: BOOL] extends BOOL {
type a[t <: BOOL, f <: BOOL] = IF[x, FALSE, TRUE]#a[t, f]
}
trait AND[x <: BOOL, y <: BOOL] extends BOOL {
type a[t <: BOOL, f <: BOOL] = IF[x, y, FALSE]#a[t, f]
}
trait OR[x <: BOOL, y <: BOOL] extends BOOL {
type a[t <: BOOL, f <: BOOL] = IF[x, TRUE, y]#a[t, f]
}
// aliases for nicer syntax
type ![x <: BOOL] = NOT[x]
type ||[x <: BOOL, y <: BOOL] = OR[x, y]
type &&[x <: BOOL, y <: BOOL] = AND[x, y]
}
The following pre-processor object contains an implicit method for converting a value of type TRUE to an Include object whose apply method executes a block of code. Similarly it contains an implicit method for converting a value of type FALSE to an Exclude object whose apply method simply does nothing. The strange line where null is being cast to B is a trick for getting a witnesses of a value of type B.
object PreProc {
def IF[B] = null.asInstanceOf[B]
object Include {
def apply(block: => Unit) {
block
}
}
object Exclude {
def apply(block: => Unit) { }
}
implicit def include(t: TRUE) = Include
implicit def exclude(f: FALSE) = Exclude
}
Using these definitions is quite convenient now:
object IfDefTest {
import PreProc._
type LOG = TRUE
type ERR = TRUE
type WARN = FALSE
def errTest() {
IF[(LOG && ERR)#v] {
println("err")
}
}
def warnTest() {
IF[(LOG && WARN)#v] {
println("warn")
}
}
def main(args: Array[String]) {
errTest()
warnTest()
}
}
Running the above code will print err but wont print warn to the console.
Loop Unrolling
Another application for static meta-programming is loop unrolling. When the number of iterations of a loop is small and only depends on quantities known at compile time, run time performance might profit from unrolling that loop. Instead of resorting to copy paste, we can use similar techniques like above.
Again let’s first define meta-naturals and their operations (full code here):
object Naturals {
trait NAT {
type a[s[_ <: NAT] <: NAT, z <: NAT] <: NAT
type v = a[SUCC, ZERO]
}
final class ZERO extends NAT {
type a[s[_ <: NAT] <: NAT, z <: NAT] = z
}
final class SUCC[n <: NAT] extends NAT {
type a[s[_ <: NAT] <: NAT, z <: NAT] = s[n#a[s, z]]
}
type _0 = ZERO
type _1 = SUCC[_0]
type _2 = SUCC[_1]
type _3 = SUCC[_2]
type _4 = SUCC[_3]
type _5 = SUCC[_4]
type _6 = SUCC[_5]
trait ADD[n <: NAT, m <: NAT] extends NAT {
type a[s[_ <: NAT] <: NAT, z <: NAT] = n#a[s, m#a[s, z]]
}
trait MUL[n <: NAT, m <: NAT] extends NAT {
trait curry[n[_[_], _], s[_]] { type f[z] = n[s, z] }
type a[s[_ <: NAT] <: NAT, z <: NAT] = n#a[curry[m#a, s]#f, z]
}
// aliases for nicer syntax
type +[n <: NAT, m <: NAT] = ADD[n, m]
type x[n <: NAT, m <: NAT] = MUL[n, m]
}
The pre-processor object defines a trait Loop having an apply method which takes a block of code as argument. Again there are two implicit conversion methods. One which converts the zero type to a Loop with an empty apply function. An another one which convert the type N + 1 to a a Loop with an apply function which executes the block once and then applies itself to the type N.
object PreProc {
def LOOP[N] = null.asInstanceOf[N]
trait Loop[N] {
def apply(block: => Unit)
}
implicit def loop0(n: ZERO) = new Loop[ZERO] {
def apply(block: => Unit) { }
}
implicit def loop[N <: NAT](n: SUCC[N])(implicit f: N => Loop[N]) = new Loop[SUCC[N]] {
def apply(block: => Unit) {
block
null.asInstanceOf[N].apply(block)
}
}
}
Again using this is easy and convenient:
object LoopUnroll {
import PreProc._
def unrollTest() {
// The following line needs the -Yrecursion 1 flag
// LOOP[(_3 x _2)#v] {
LOOP[_6] {
println("hello world")
}
}
def main(args: Array[String]) {
unrollTest()
}
}
The above code prints the string “hello word” six times to the console.
Conclusion
Scala’s type system is powerful enough for encoding commonly encountered functions. Together with Scala’s strong capability for creating internal DSLs, this results in convenient techniques for static meta-programming. Such techniques can be applied to practical problems – at least in theory. In practice Scala’s support is not (yet?) there. For one the technique presented here depends on an experimental compiler flag (-Yrecursion). Further the types required for meta-programming might causes an exponential growth in compilation time which is not desirable. And finally an analysis with c1visualizerwith showed, that the compiler seems not to remove all unnecessary calls.
stands for the n-fold application of s. Think of s standing for successor and z for zero. Then the number n is simply the n-fold successor of zero.
.
