As simple as possible, but not simpler

The simplicity being alluded to in the title, is not some aesthetic measure of code brevity inspired by Martin Odersky’s keynote in ScalaDays. It actually refers to simplifying arithmetic conditions, with the specific goal of proving whether the intersection of two sets, defined intensionally, is empty or not. This problem is actually very hard, but the case I’m interested in is where atomic conditions are linear inequalities involving single variables, which you have to imagine as referring to properties of a type, instances of which you define sets of. I can hear your enthusiasm winding down, because I’ve now simplified the problem a millionfold. One would think that this would be a toy problem for which there would be many solutions and yet, I couldn’t find any that didn’t involve finding concrete solutions and, all I needed was a simplified expression of the condition for the set intersection (for example, I looked at JSR 331). So, I decided to tackle it myself; why not have a little fun, huh?

Digging through the pits of my school-days memory, my first hunch was that some kind of normalization would be in order, and I settled on disjunctive normal form. Please don’t write me that all SAT and SMT solvers use conjunctive normal form and that I probably dug through the armpits of my school-days memory. Hear me out, first.

Each conjunction in DNF can have all its constituent atomic conditions on same variables be merged together, which results in either false, or another atomic condition. Consequently, each conjunction in DNF can be brought to, what can be described as, a simplified form where each variable is mentioned only once. And disjunctions will be fairly uncommon in the use case I was envisioning, which is some query builder interface (but not absent).

I’m going to walk you through my code and thought process. You’ll have to imagine the former being enclosed in a Scala object and the latter enclosed inside that glass display case for brains, that you see in movies. You’ll also have to imagine what role various types and case classes/enums play, because their names are evocative enough.

def toFlatDNF(c: ICriterion) : ICriterion = simplify(toDNF(c))

In a top-down fashion, I’m going first to transform the expression to DNF, then simplify it.

def flatten(c: ICriterion) : List[ICriterion] = {
    c match {
        case Composite(_, li2) => li2
        case _ => List(c)
    }
}

def cartesianProduct[T](xss: List[List[T]]): List[List[T]] = xss match {
   case Nil => List(Nil)
   case h :: t => for(xh <- h; xt <- cartesianProduct(t)) yield xh :: xt
}

def distributeOrOver(ors: List[ICriterion], ands: List[ICriterion]): List[ICriterion] = {
    val andsInOrs = ors.map(flatten)
    val product = cartesianProduct(andsInOrs)
    val allEnds = product.map(_ ++ ands)
    allEnds.map({
        case List(c) => c
        case li => Composite(AND,li)
    })
}

def toDNF(c: ICriterion) : ICriterion = {
    c match {
        case Composite(op,li) => {
            val li2 = li.map(toDNF).toList 
// each might be an OR of up to depth 2 or an AND of depth up to 1
            val (ands, ors) = li2.partition {
                case Composite(AND, c) => true
                case Composite(OR, c) => false
                case _ => true
            }
            op match {
                case OR => {
                    val flators = ors.flatMap(flatten)
                    Composite(OR, flators ++ ands)
                }
                case AND => {
                    val flatands = ands.flatMap(flatten)
                    if (ors.length == 0)
                         Composite(AND, flatands)
                    else {
                        val over = distributeOrOver(ors, flatands)
                        Composite(OR, over)
                    }
                }
            }

        }
        case _ => c
    }
}

What this (supposedly) does is to distribute OR over AND in order to arrive to DNF.

Now, the simplification that follows is based on extending the domain of all values to add a global MIN and a global MAX value, and on rephrasing all equalities and inequalities as interval conditions, whose either limit can be open or closed (methods left() and right() return the corresponding comparisons to the corresponding limit). A special comparison function, cmp arranges for MIN/MAX-aware comparisons.

The expression is normalized, in that way, then merged, then denormalized again to simple equalities and inequalities.

def groupByParameterEvaluable(liFinal: List[ICriterion]): Map[ParameterEvaluable,List[ICriterion]] = {
    liFinal.groupBy({case ParamOpVal(p,_,_) => p})
}

def normalize(c: ICriterion) : List[ICriterion] = c match {
    case ParamOpVal(p, op, values) =>
        op match {
            case EQ => List(ParamOpVal(p, BTW_E, List(values(0), values(0))))
            case LT => List(ParamOpVal(p, BTW_NE, List(MIN, values(0))))
            case GT => List(ParamOpVal(p, BTW_NE, List(values(0), MAX)))
            case LE => List(ParamOpVal(p, BTW_GE, List(MIN, values(0))))
            case GE => List(ParamOpVal(p, BTW_LE, List(values(0), MAX)))
            case NE => List(
                ParamOpVal(p, BTW_NE, List(MIN, values(0))),
                ParamOpVal(p, BTW_NE, List(values(0), MAX))
            )
            case _ => List(c)
        }
}

def denormalize(c: ICriterion) : List[ICriterion] = c match {
    case ParamOpVal(p, BTW_E, List(x, y)) if x == y => List(ParamOpVal(p, EQ, List(x)))
    case ParamOpVal(p, BTW_NE, List(MIN, x)) => List(ParamOpVal(p, LT, List(x)))
    case ParamOpVal(p, BTW_GE, List(MIN, x)) => List(ParamOpVal(p, LE, List(x)))
    case ParamOpVal(p, BTW_NE, List(x, MAX)) => List(ParamOpVal(p, GT, List(x)))
    case ParamOpVal(p, BTW_LE, List(x, MAX)) => List(ParamOpVal(p, GE, List(x)))
    case _ => List(c)
}

def merge(li: List[ICriterion]) : ICriterion = li.reduceLeft(combine)

def simplifyCriteria(criteria: List[ICriterion]): List[ICriterion] = {
    var normalized = criteria.flatMap(normalize)
    var merged = merge(normalized)
    denormalize(merged)
}

def simplify(cDnf: ICriterion): ICriterion = {
    cDnf match {
        case Composite(OR, liConj) => Composite(OR, liConj.map(simplify))
        case Composite(AND, liFinal) => {
            val grouped = groupByParameterEvaluable(liFinal)
            val groupedMerged = grouped.iterator.map({
                case (_, v) => simplifyCriteria(v)
            })
            val merged = groupedMerged.flatten.toList
            Composite(AND, merged)
        }
        case _ => cDnf
    }
}

The most complicated operation in all that is how to combine too intervals (one step of the merging process). Notice that, in order for two intervals to stand a chance of being able to combine, their closed-closed analogs should intersect and the easiest way to express that is as a negation of the condition that they not intersect: either one is before the other, or vice versa.

def fuseBetweenOperator(op1: CriteriaOperator, op2: CriteriaOperator) : CriteriaOperator =
    (op1, op2) match {
        case (GE, LE) => BTW_E
        case (GT, LE) => BTW_GE
        case (GE, LT) => BTW_LE
        case (GT, LT) => BTW_NE
        case _ => throw new Error(s"fuseBetweenOperator cannot be used on $op1 and $op2")
    }

//This combines two comparisons with conjunction
def combine(ic1: ICriterion, ic2: ICriterion) : ICriterion = {
    val FALSE = new FalseCriterion
    if(ic1.isInstanceOf[FalseCriterion]) return FALSE
    val c1 = ic1.asInstanceOf[SimpleCriterion]
    val c2 = ic2.asInstanceOf[SimpleCriterion]
    (c1,c2) match {
        case (ParamOpVal(p,op1,List(v1,v2)),ParamOpVal(_,op2,List(w1,w2))) if cmp(w1,v2)<=0 =>
            if(cmp(w1,v2)==0 && (op1.right()==LT || op2.left()==GT))
                FALSE
            else {
                val (lowerBound, leftop) = if(cmp(w1,v1)<=0) (v1,op1.left()) else (w1,op2.left())
                val (upperBound, rightop) = if(cmp(v2,w2)<=0) (v2,op1.right()) else (w2,op2.right())
                val operator = fuseBetweenOperator(leftop, rightop)
                if(cmp(lowerBound,upperBound)==0 && operator!=BTW_E)
                    FALSE
                else
                    ParamOpVal(p, operator, List(lowerBound, upperBound))
            }
        case (ParamOpVal(p,op1,List(v1,v2)),ParamOpVal(_,op2,List(w1,w2))) if cmp(w1,v2)<=0 =>
            if(cmp(v1,w2)==0 && (op2.right()==LT || op1.left()==GT))
                FALSE
            else {
                val (lowerBound, leftop) = if(cmp(w1,v1)<=0) (v1,op1.left()) else (w1,op2.left())
                val (upperBound, rightop) = if(cmp(v2,w2)<=0) (v2,op1.right()) else (w2,op2.right())
                val operator = fuseBetweenOperator(leftop, rightop)
                if(cmp(lowerBound,upperBound)==0 && operator!=BTW_E)
                    FALSE
                else
                    ParamOpVal(p, operator, List(lowerBound, upperBound))
            }
        case _ => FALSE
    }
}

Having all that implemented, testing for intersection is as simple as forming the conjunction of the conditions that define the sets involved, performing toFlatDNF, and seeing if the result is the false expression. If it isn’t, you have it as an expression to inspect and maybe think about how to change the set definitions so that they not intersect.

Advertisements

Let’s get physical

I’m a mechanical engineer and, although I studied for software engineering degrees right after I graduated, I did my fair share of numerical calculations during my five years of studies in engineering. Some of it in Turbo Pascal, but most of it in the recommended language, which was Fortran. It was very spartan but, one thing it did well, was get out of the way between engineers and their calculations. Around 2007, 17 full years away from purely numerical computing, I turned around to see what had changed in the domain of calculating with physical quantities. Believe me, any new version of Fortran that has come out was a huge improvement over Fortran 77, but I found that not much had changed in the calculations themselves. In particular, regarding calculations with physical units and proper dimensional analysis. The kind that could avoid disasters like these.

Before I tell you what I concocted in 2007 and then in 2014, let me stay a little longer on Fortran, or rather what was designed to be a modern-day Fortran: Fortress.

Fortress

Fortress, the brainchild of Guy Steele, was an experimental project in Sun to answer the HPCS challenge (cf. “Fwd: HPCS recap”). After it was not selected in subsequent rounds of the challenge, the project persisted for a total of ten years, before being axed by Oracle. People explain things like that because of the “pragmatic” approach of Oracle towards Java. Which is a polite way to say that Oracle makes Java walk the streets for money, and probably gives her a good beatin’ whenever she comes back with low earnings.

Fortress had nailed the dimension thing, offering dimensions (decribed as “type-like constructs that are separate from other types”) and units (described as “special constructs that modify types and values […] that are instances of dimensions”). Dimensionless and dimensioned numbers can use the whole gamut of language constructs. In addition to standard SI dimensions and units, many more are available in the standard library and more can be added.

Here is what some dimension-aware calculations would look in Fortress (Fortress is a language written to be read back as close to mathematics as possible, so this is how Fortress code would look like).

x:ℝ64 Length = 1.3m
t:ℝ64 Time = 5 s
v:ℝ64 Velocity = x/t
w:ℝ64 Velocity in nm/s = 17nm/s

Standard SI prefixes like (nano, micro etc) and their abbreviations (n, μ etc) can be used. In order to avoid misunderstandings, these prefixes cannot be used in front of units of dimension Information (bit and byte).

Both dimensions and units can be multiplied, divided, and raised to rational powers to produce new dimensions and units. Multiplication can be expressed using juxtaposition or · (yes, Fortress actually gives the natural meaning of multiplication to juxtaposition!) Division can be expressed using / or per. The syntactic operators square and cubic (or the special postfix syntactic operators squared and cubed) may be applied to a dimension or unit in order
to raise it to the second power, third power, respectively. The syntactic operator inverse may be applied to a dimension or unit to divide it into 1. Ex. grams per cubic centimeter, meter per second squared, inverse ohms.

All in all, a pretty solid treatment. Unfortunately, none of this was actually implemented… However, there is one existing language which does support dimensioned calculations in a very real way.

F#

F# is the only mainstream language, as far as I know, that contains specific constructs for working with units (Curl supposedly does also, but I’m not familiar with it and it’s a long stretch to call it mainstream).

It is not entirely pleasing as, there is no concept of dimension, only the concept of unit of measure, but all the machinery needed for safe dimensional calculations is there. As is common in the .Net and Java world, the units of measure are defined using an attribute (annotation in Java-speak). SI predefined “measures” can be found in the PowerPack.

[<Measure>] type kg
[<Measure>] type s
[<Measure>] type m
[<Measure>] type cm = m / 100
[<Measure>] type ml = cm^3

let gravityOnEarth = 9.81<m/s^2>
let heightOfFall = 15<m>
let speedOfImpact = sqrt(2.0 * gravityOnEarth * heightOfFall)
let someForce = 10<kg m s^-2>

As you see in the example, units can be defined by their own (in which case they can be thought as defining a dimension) or as derived from some unit expression. Such expressions can be suffixed to numeric literals between angle brackets (without any intervening space). As a nod to Fortress, who knows?, juxtaposition stands for multiplication in the numerator of unit expressions. A dimensionless quantity is denoted by the unit expression <1>. One can even have generic units! And, you know, .Net has real multidimensional array types, and value types and also arrays of value types. The whole makes a compelling proposal for a scientist or an engineer.

Dimenso
Back in 2007, none of that was there. So I set myself a goal of experimenting in that domain, leading to the open-source project Dimenso. I focused on just SI quantities and then, just the MKS part together with current (no temperature, no amount of substance and no luminous intensity).

Dimenso: C++

The prototypical implementation was in C++. Believe it or not, the template language in C++ is pretty advanced, even with today’s standards. One could really make a case that C++ template metaprogramming is akin to using dependent types. Because templates in C++, unlike generics in the likes of Java or .Net, can actually be parameterized by integers, in addition to types. Here’s how the definition of the class that embodies dimensioned values would start: template<int L, int M, int T, int C> class DimensionedValue.

Defining what it means to multiply two dimensioned values together is this simple operator (yes! Java-lovers, most other languages do have operator overloads!).

template<int L2, int M2, int T2, int C2>
 DimensionedValue<L+L2,M+M2,T+T2,C+C2> operator*(DimensionedValue<L2,M2,T2,C2> other) {
     return DimensionedValue<L+L2,M+M2,T+T2,C+C2>(magnitude()*other.magnitude());
}

Given all the machinery available in C++, one can really make these objects look and behave like plain numbers. The challenge, then, was to go as close to that in C# and Java, which lacked support for dependent types.

Dimenso: C# and Java

The way I followed was: code generation. I generated all dimension combinations within specific bounds (but I also provided the Python script if one would need a more extended set). These combinations were named after the corresponding exponents (for example, type m_2k0s1a0 represents dimension L-2T) but actual names from physics were used, when available (but not in a right way… if you try to use Dimenso, stick to the ugly names).

This is how an arithmetic operation on “length” would look like in Java, if I hadn’t messed up the name thing.

public velocity divide(time v2) {
    velocity ret = new velocity(this.value/v2.getValue());
    return ret;
}

In C#, which does have operator overloads and value types, the whole is a little more palatable. But still, generating hundreds of classes feels… kind of wrong. Let’s see what the Java of today has to say on the matter.

JSR-275, JSR-363 and JScience
To make a long story short, JSR-275 “Measures and Units” was finally rejected and, its successor, JSR-363 “Units of Measurement API” has not really formed yet but, abandoning at that point would make it really short. That’s why I’m going to look at support for units in JScience, which claims support for such.

Let’s look at some sample code, which will highlight the point I was trying to make with Dimenso.

// Compiler Warnings
Unit<Acceleration> mps2 = Unit.valueOf("m/s²"); // Compiler Warning.
Unit<Power> WATT = JOULE.divide(SECOND); // Compiler Warning.

// Adding run-time check of dimension consistency removes the warning.
Unit<Acceleration> mps2 = Unit.valueOf("m/s²")
    .asType(Acceleration.class); 
Unit<Power> WATT = JOULE.divide(SECOND).asType(Power.class);

// Use wildcard parameterized type (no warning and no check).
Unit<?> kelvinPerSec = KELVIN.divide(SECOND);

JScience has a lot of capabilities for units, including arbitrary systems of dimensions, localizable unit parsing and output and compound units, like those for common time. But there is no way to have the compiler figure out what units two quantities multiplied or divided among themselves have. This is a shortcoming of Java, not of JScience. And, unless you’ve been ruined by too many years of Java, you can tell that no scientist or engineer would put up with so much unwarranted verbosity to do his job.

Do not despair, as Java is not the only choice you have on the JVM.

Scala

Let’s see what I’ve been able to do with some typelevel hacking in Scala. First of all, I’d like to point you to a better solution, Metascala Units, which did come up in my Google search, and a tab in my browser was open, waiting patiently for me to have a look at them, which I did, but after the fact. No matter, because what I really wanted was some practical experience with typelevel programming, with dimension-aware calculations as a good case to work on. The way that Metascala encodes integers in the typesystem is a lot more concise and a lot more elegant than my own, which is based on Shapeless’ encoding of naturals.

Here is some safe code using Metascala Units:

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

I hope you can appreciate the fact that this looks like using built-in features. It is as concise as it can get and offers full compile-time checking.

And here’s my own stab at this. It’s not part of Dimenso yet, because it’s not fully tested, I believe that if I build stronger typelevel kung-fu, I’ll be able to handle output of units at compile-time, as well, and there is probably some more magic to add with implicit value classes.

case class DimVal[M1 <: ZInt, K1 <: ZInt, S1 <: ZInt, A1 <: ZInt](val value : Double) {
    type T = DimVal[M1,K1,S1,A1]
    def +(b: DimVal[M1,K1,S1,A1]) = new DimVal[M1,K1,S1,A1](value + b.value)

    def -(b: DimVal[M1,K1,S1,A1]) = new DimVal[M1,K1,S1,A1](value - b.value)

    def *[M2 <: ZInt, M <: ZInt, K2 <: ZInt, K <: ZInt, S2 <: ZInt, S <: ZInt, A2 <: ZInt, A <: ZInt]
    (b: DimVal[M2,K2,S2,A2])
    (implicit ev: ZSumAux[M1,M2,M], ev2: ZSumAux[K1,K2,K], ev3: ZSumAux[S1,S2,S], ev4: ZSumAux[A1,A2,A]) : DimVal[M,K,S,A] =
        new DimVal[M,K,S,A](value * b.value)

    def /[M2 <: ZInt, M <: ZInt, K2 <: ZInt, K <: ZInt, S2 <: ZInt, S <: ZInt, A2 <: ZInt, A <: ZInt]
    (b: DimVal[M2,K2,S2,A2])
    (implicit ev: ZDiffAux[M1,M2,M], ev2: ZDiffAux[K1,K2,K], ev3: ZDiffAux[S1,S2,S], ev4: ZDiffAux[A1,A2,A]) : DimVal[M,K,S,A] =
        new DimVal[M,K,S,A](value / b.value)

    def asString () (implicit i1: ToZInt[M1], i2: ToZInt[K1], i3: ToZInt[S1], i4: ToZInt[A1]) = {
        val x1 = i1.apply()
        val x2 = i2.apply()
        val x3 = i3.apply()
        val x4 = i4.apply()
        val u =
        (x1,x2,x3,x4) match {
            case (0,0,1,1) => " C"
            case (1,1,-2,0) => " N"
// ... more special cases to handle derived units elided ...
            case _ => {
                val sb = new StringBuilder
// ... ugly, imperative code elided ...
                if(sb.length > 0) " "+sb else ""
            }
        }
        value.toString + u
    }

}

The dimension calculations are done at the type level, using types ZSumAux and ZDiffAux, and type ToZInt handles conversion to language-level integers. Like I said, not all induction cases are tested, but here’s what they look like now.

import shapeless._
import shapeless.Nat._0

trait ZInt

case class ZPos[T <: Nat]() extends ZInt
case class ZNeg[T <: Nat]() extends ZInt

trait ZSumAux[A <: ZInt, B <: ZInt, C <: ZInt]
trait ZDiffAux[A <: ZInt, B <: ZInt, C <: ZInt]

object ZSumAux {
    implicit def sum3[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : SumAux[A, B, C]) = new ZSumAux[ZPos[A], ZPos[B], ZPos[C]] {}

    implicit def sum4[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : SumAux[A, B, C]) = new ZSumAux[ZNeg[A], ZNeg[B], ZNeg[C]] {}

    implicit def sum5[A <: Nat] = new ZSumAux[ZPos[A], ZNeg[A], ZPos[_0]] {}

    implicit def sum6[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[A, B, C], ev2: LT[B,A]) = new ZSumAux[ZPos[A], ZNeg[B], ZPos[C]] {}

    implicit def sum7[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[B, A, C], ev2: LT[A,B]) = new ZSumAux[ZPos[A], ZNeg[B], ZNeg[C]] {}

    implicit def sum8[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[A, B, C], ev2: LT[B,A]) = new ZSumAux[ZNeg[A], ZPos[B], ZNeg[C]] {}

    implicit def sum9[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[B, A, C], ev2: LT[A,B]) = new ZSumAux[ZNeg[A], ZPos[B], ZPos[C]] {}
}

object ZDiffAux {
    implicit def diff3[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[A, B, C], ev2: LT[B,A]) = new ZDiffAux[ZPos[A], ZPos[B], ZPos[C]] {}

    implicit def diff3b[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[B, A, C], ev2: LT[A,B]) = new ZDiffAux[ZPos[A], ZPos[B], ZNeg[C]] {}

    implicit def diff4[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[A, B, C], ev2: LT[B,A]) = new ZDiffAux[ZNeg[A], ZNeg[B], ZNeg[C]] {}

    implicit def diff4b[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : DiffAux[B, A, C], ev2: LT[A,B]) = new ZDiffAux[ZNeg[A], ZNeg[B], ZPos[C]] {}

    implicit def diff5[A <: Nat] = new ZDiffAux[ZPos[A], ZPos[A], ZPos[_0]] {}

    implicit def diff5b[A <: Nat] = new ZDiffAux[ZNeg[A], ZNeg[A], ZPos[_0]] {}

    implicit def diff6[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : SumAux[A, B, C], ev2: LT[B,A]) = new ZDiffAux[ZPos[A], ZNeg[B], ZPos[C]] {}

    implicit def diff7[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : SumAux[B, A, C], ev2: LT[A,B]) = new ZDiffAux[ZPos[A], ZNeg[B], ZNeg[C]] {}

    implicit def diff8[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : SumAux[A, B, C], ev2: LT[B,A]) = new ZDiffAux[ZNeg[A], ZPos[B], ZNeg[C]] {}

    implicit def diff9[A <: Nat, B <: Nat, C <: Nat]
    (implicit ev : SumAux[B, A, C], ev2: LT[A,B]) = new ZDiffAux[ZNeg[A], ZPos[B], ZPos[C]] {}
}

trait ToZInt[Z <: ZInt] {
    def apply() : Int
}

object ToZInt {
    implicit def toPosInt[N <: Nat] (implicit i: ToInt[N]) = new ToZInt[ZPos[N]] {
        def apply() = i.apply()
    }
    implicit def toNegInt[N <: Nat] (implicit i: ToInt[N]) = new ToZInt[ZNeg[N]] {
        def apply() = - i.apply()
    }
}

Some useful definitions are in object DimValOps.

object DimValOps {
    type Z0 = ZPos[_0]
    type Z1 = ZPos[Succ[_0]]
    type Z2 = ZPos[Succ[Succ[_0]]]
    type Z3 = ZPos[Succ[Succ[Succ[_0]]]]
    type Z4 = ZPos[Succ[Succ[Succ[Succ[_0]]]]]
    type Z_1 = ZNeg[Succ[_0]]
    type Z_2 = ZNeg[Succ[Succ[_0]]]
    type Z_3 = ZNeg[Succ[Succ[Succ[_0]]]]

    type length = DimVal[Z1, Z0, Z0, Z0]
    type mass = DimVal[Z0, Z1, Z0, Z0]
    type time = DimVal[Z0, Z0, Z1, Z0]
    type current = DimVal[Z0, Z0, Z0, Z1]
    type charge = DimVal[Z0, Z0, Z1, Z1]
    type area = DimVal[Z2, Z0, Z1, Z0]
    type volume = DimVal[Z3, Z0, Z1, Z0]
    type velocity = DimVal[Z1, Z0, Z_1, Z0]
    type acceleration = DimVal[Z1, Z0, Z_2, Z0]
    type momentum = DimVal[Z1, Z1, Z_1, Z0]
    type angular_momentum = DimVal[Z2, Z1, Z_1, Z0]
    type frequency = DimVal[Z0, Z0, Z_1, Z0]
    type force = DimVal[Z1, Z1, Z_2, Z0]
    type pressure = DimVal[Z_1, Z1, Z_2, Z0]
    type viscosity = DimVal[Z_1, Z1, Z_1, Z0]
    type energy = DimVal[Z2, Z1, Z_2, Z0]
    type power = DimVal[Z2, Z1, Z_3, Z0]
    type potential = DimVal[Z2, Z1, Z_3, Z_1]
    type capacitance = DimVal[Z_2, Z_1, Z4, Z2]
    type resistance = DimVal[Z2, Z1, Z_3, Z_2]
    type conductance = DimVal[Z_2, Z_1, Z3, Z2]
    type magnetic_flux = DimVal[Z2, Z1, Z_2, Z_1]
    type magnetic_flux_density = DimVal[Z0, Z1, Z_2, Z_1]
    type inductance = DimVal[Z2, Z1, Z_2, Z_2]

    val m = new length(1) //meter
    val kg = new mass(1) //kilogram
    val s = new time(1) //second
    val A = new current(1) //Ampere
    val C = new charge(1) //Coulomb
    val N = new force(1) //Newton
    val Hz = new frequency(1) //Hertz
    val Pa = new pressure(1) //Pascal
    val ohm = new resistance(1)
    val V = new potential(1) //Volt
    val S = new conductance(1) //Siemens
    val W = new power(1) //Watt
    val J = new energy(1) //Joule
    val F = new capacitance(1) //Farad
    val H = new inductance(1) //Henry
    val Wb = new magnetic_flux(1) //Weber
    val T = new magnetic_flux_density(1) //Tesla

    implicit def numToDim(d : Double) : DimVal[Z0,Z0,Z0,Z0] = new DimVal[Z0,Z0,Z0,Z0](d)
}

On the one hand, it looks frightening. On the other hand, it’s just a few lines of code to add a capability that is missing since forever. Here is some putting it through its paces.

    val c0 = new charge(4)
    println("c0="+c0.asString())

    val v = 3 * m / s
    println("v="+v.asString)

    val mom = 10 * kg * v
    println("mom="+mom.asString())

    val e = mom * v
    println("e="+e.asString())

    val p = e / (3 * s)
    println("p="+p.asString())

Which outputs:

c0=4.0 C
v=3.0 m·s-1
mom=30.0 m·kg·s-1
e=90.0 J
p=30.0 W

Look what happens when you try to compile an assignment with mismatched dimensions.

    val p : pressure = e / (3 * s)
Error:(37, 26) type mismatch;
 found   : ShapelessExperiment.DimVal[ShapelessExperiment.ZPos[shapeless.Succ[shapeless.Succ[shapeless.Nat._0]]],ShapelessExperiment.ZPos[shapeless.Succ[shapeless.Nat._0]],ShapelessExperiment.ZNeg[shapeless.Succ[shapeless.Succ[shapeless.Succ[shapeless.Nat._0]]]],ShapelessExperiment.ZPos[shapeless.Nat._0]]
 required: ShapelessExperiment.DimValOps.pressure
    (which expands to)  ShapelessExperiment.DimVal[ShapelessExperiment.ZNeg[shapeless.Succ[shapeless.Nat._0]],ShapelessExperiment.ZPos[shapeless.Succ[shapeless.Nat._0]],ShapelessExperiment.ZNeg[shapeless.Succ[shapeless.Succ[shapeless.Nat._0]]],ShapelessExperiment.ZPos[shapeless.Nat._0]]
    val p : pressure = e / (3 * s)
                         ^

Ok, the message is not entirely simple but, if you understand the type signatures, it is clear how to read it. In conclusion, even though Scala’s compile-time metaprogramming has been said to imitate, rather than implement, dependent types, you can see it is able to quack like a duck and walk like a duck. And it is perfectly capable of stepping in when Java proves too little, even though it cannot overcome fundamental limitations of the JVM.

Generics Face-Off, Nugget #1

My last post was a bit overly enthusiastic about Scala. To counterbalance it, I present another “nugget” in this post, inspired by my slim experience on using Scala together with Java. You see, Scala aims to remedy some shortcomings of the Java typesystem, in particular its generics, which makes it somewhat uncomfortable, at times, to bridge the two. And the face-off you read in the title, will be between Scala and another JVM language, Kotlin, which aims more towards being a better Java than providing a wholly different solution. Let’s see how they do, using the scale used by Catch-22‘s Colonel Cathcart.

Java’s wacky use of Generics

Suppose there’s a generic Java class, named Something, presented here as a bare-bones example.

public class Something<T> {
    @Override
    public String toString() {
        return "Something";
    }
}

And here’s the rub. Java allows you to “cop out” of Generics and use either the erased type, or an existential type, in the following meaningless way (and I’m not making this up).

public class JTest {
    public static Something<?> getSomething() {
        return new Something<String>();
    }
}

Here’s some Scala code to process an instance of Something<String>.

class STest {
    def workWithSomethingString(s : Something[String]) {
        print(s)
    }
}

Suppose you know that the particular instance is a Something<String> (the way you know it lies certainly outside of the type system). Going from Java to Scala produces an unchecked warning, as it should.

    public static void scalaDriver() {
        STest sTest = new STest();
        sTest.workWithSomethingString((Something<String>)getSomething()); 
        //flagged as unckecked
    }

Enter Kotlin.

class KTest {
    fun workWithSomethingString(s:Something<String>) {
        print(s)
    }
}

Same thing here.

    public static void kotlinDriver() {
        KTest ktest = new KTest();
        ktest.workWithSomethingString((Something<String>) getSomething());
        //flagged as unckecked
    }

Both fail to cope with Java’s incongruent use of Generics. Hence, a black eye for both, in that regard. Hint: at the call site, it’s the Java compiler that runs the show. There’s really no way to win. Let’s see what we get if we give full control of the calling site to the other compilers.

Reified generics

If we disregard direct interconnection with Java, for a moment, both Scala and Kotlin want to provide some solution to being able to recover type information that is lost by erasure.

Scala does it using TypeTags and such, in various ways which employ the compiler to supply information about generic types from the calling site to the called method.

Below is one way to do it. The first call to workWithSomething delegates correctly to workWithSomethingString.

    def passTheBuck() {
        workWithSomething(new Something[String])
        workWithSomething(new Something[Int])
    }

    def workWithSomething[T](s : Something[T])(implicit t : TypeTag[T]) {
        if( t.tpe.typeConstructor =:= typeOf[String] ) {
            workWithSomethingString(s.asInstanceOf[Something[String]])
        } else {
            print("\nCannot handle\n")
        }
    }

How about Kotlin? Kotlin has promised reified generics, but it’s still in the roadmap. Black eye for Kotlin, feather in Scala’s cap.

Things don’t look so good for Kotlin, so far. In the next nugget, let’s see if it manages to recoup, using its distinguishing feature of mixed-site variance.

It may quack like a duck

This post comes after a long hiatus. I have family matters to attend to and a new job, to boot. And I made a promise to myself to not let this blog devolve to rants without substance. I was hoping to have something interesting to say on the subject of working with column constraints that Higher Order Sql will produce, at least for the usual case of constraints defined using literal values, but I don’t have anything ready yet. So I devised a new category, “Nugget”, for small posts in which I will try to convey interesting information, nevertheless.

For this one, I will draw upon my recent studies to focus on a Scala feature which, I have seen, is not given much attention. You see, my new job is in a Java shop. And I have found that adding a little Scala makes using Java almost bearable, even before moving to Scala wholesale. You might find my words too scornful but the truth of the matter is that Java was, well, the Java of the 90s, but is now the Cobol of the 00s. It is progressing at a glacial pace, to the point that I found it practically unchanged after I spent seven years working with .Net. Its signal-to-noise ratio is very low (really? after all these years I still have to Alt-Ins to produce thousands of getters and setters that clobber the rest of my code?) and it’s fallen behind after all other modern languages. It does have the most complete ecosystem, but this is a property of running in the JVM, it makes no difference whether the many useful libraries have been written in Java. Except that, since most of them have been written in Java, they make too much use of mutation, practically blocking Java from leaping to the multicore era.

Enough with the ranting. The subject of this post is Scala structural types (BTW, you can read a nice exposé on the Scala typesystem in this article). Structural types are not used much, but they enable type-safe Duck Typing, as in the following example.

import scala.language.reflectiveCalls

class Foo(val x:Int) {
    def addToMe(i:Int) = i+x
}

class Bar(val x:Int) {
    def addToMe(i:Int) = i+x
}

object test {
    def test(o : { def addToMe(i:Int) }) = {
        o.addToMe(42)
    }
}

The { def addToMe(i:Int) } part is where one describes a type that has an addToMe method that takes an Int. Why would anyone want to do that? Why, to show it to their friends who use Python or Ruby! I’m kidding… A case I found recently is the following: in QueryDsl, NumberExpression and ComparableExpression both implement the same API methods for generating comparisons (e.g, goe(), gt() ) and they don’t inherit them from some common ancestor, so, in Java, one needs to duplicate code to deal with both of them, code which is absolutely the same except for the type of the expression.

It is very instructive to look at how Scala does it (spoiler: the same way you’d do it youself, only without the grief). Class test$ (Scala makes it for the singleton object) has the following contents.

public final class test$ {
  public static final test$ MODULE$;
  public static {};
  public static java.lang.reflect.Method reflMethod$Method1(java.lang.Class);
  public void test(java.lang.Object);
} 

Method reflMethod$Method1 is used to find the addToMe method of the target, and method test calls it.

 
  public static java.lang.reflect.Method reflMethod$Method1(java.lang.Class);
    Code:
       0: getstatic     #35                 // Field reflPoly$Cache1:Ljava/lang/ref/SoftReference;
       3: invokevirtual #42                 // Method java/lang/ref/SoftReference.get:()Ljava/lang/Object;
       6: checkcast     #44                 // class scala/runtime/MethodCache
       9: astore_1      
      10: aload_1       
      11: ifnonnull     33
      14: new           #25                 // class scala/runtime/EmptyMethodCache
      17: dup           
      18: invokespecial #28                 // Method scala/runtime/EmptyMethodCache."<init>":()V
      21: astore_1      
      22: new           #23                 // class java/lang/ref/SoftReference
      25: dup           
      26: aload_1       
      27: invokespecial #31                 // Method java/lang/ref/SoftReference."<init>":(Ljava/lang/Object;)V
      30: putstatic     #35                 // Field reflPoly$Cache1:Ljava/lang/ref/SoftReference;
      33: aload_1       
      34: aload_0       
      35: invokevirtual #47                 // Method scala/runtime/MethodCache.find:(Ljava/lang/Class;)Ljava/lang/reflect/Method;
      38: astore_2      
      39: aload_2       
      40: ifnull        45
      43: aload_2       
      44: areturn       
      45: getstatic     #52                 // Field scala/runtime/ScalaRunTime$.MODULE$:Lscala/runtime/ScalaRunTime$;
      48: aload_0       
      49: ldc           #54                 // String addToMe
      51: getstatic     #21                 // Field reflParams$Cache1:[Ljava/lang/Class;
      54: invokevirtual #58                 // Method java/lang/Class.getMethod:(Ljava/lang/String;[Ljava/lang/Class;)Ljava/lang/reflect/Method;
      57: invokevirtual #62                 // Method scala/runtime/ScalaRunTime$.ensureAccessible:(Ljava/lang/reflect/Method;)Ljava/lang/reflect/Method;
      60: astore_2      
      61: new           #23                 // class java/lang/ref/SoftReference
      64: dup           
      65: aload_1       
      66: aload_0       
      67: aload_2       
      68: invokevirtual #66                 // Method scala/runtime/MethodCache.add:(Ljava/lang/Class;Ljava/lang/reflect/Method;)Lscala/runtime/MethodCache;
      71: invokespecial #31                 // Method java/lang/ref/SoftReference."<init>":(Ljava/lang/Object;)V
      74: putstatic     #35                 // Field reflPoly$Cache1:Ljava/lang/ref/SoftReference;
      77: aload_2       
      78: areturn       

  public void test(java.lang.Object);
    Code:
       0: aload_1       
       1: astore_2      
       2: aload_2       
       3: invokevirtual #80                 // Method java/lang/Object.getClass:()Ljava/lang/Class;
       6: invokestatic  #82                 // Method reflMethod$Method1:(Ljava/lang/Class;)Ljava/lang/reflect/Method;
       9: aload_2       
      10: iconst_1      
      11: anewarray     #4                  // class java/lang/Object
      14: dup           
      15: iconst_0      
      16: bipush        42
      18: invokestatic  #88                 // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
      21: aastore       
      22: invokevirtual #92                 // Method java/lang/reflect/Method.invoke:(Ljava/lang/Object;[Ljava/lang/Object;)Ljava/lang/Object;
      25: pop           
      26: getstatic     #98                 // Field scala/runtime/BoxedUnit.UNIT:Lscala/runtime/BoxedUnit;
      29: pop           
      30: return        
      31: astore_3      
      32: aload_3       
      33: invokevirtual #102                // Method java/lang/reflect/InvocationTargetException.getCause:()Ljava/lang/Throwable;
      36: athrow        
    Exception table:
       from    to  target type
           2    25    31   Class java/lang/reflect/InvocationTargetException

There you go, my first “Nugget”, until I can get back on track and produce more substantial content. Scala has a lot more where this came from, and I can’t urge you strongly enough to have a look at it, particularly if you work with Java. Make no mistake. Scala is not F#. It is a modern, object-oriented language with a strong functional inclination, but it’s not a functional language (although Scalaz tries to make it more of one). So I won’t be abandoning F#, but Scala is definitely the best language on the JVM at this time (it’s the only strongly-typed of the non-Javas), having very advanced interoperability with Java (you can actually have mixed-language projects). And, guess what! I already know two people who have enrolled for Martin Odersky’s course on learning FP using Scala. What are you waiting for?