Implementing type widening

type systems
sql
hive
scala
type coercions
Published

August 19, 2014

In this installment of our series on type coercions, we’re going to introduce a way to support type widening in a language interpreter. We’ll present a general approach based on semilattices of types and a particular implementation of this approach that uses a straightforward encoding in Scala’s type system. We’ll work from a simple interpreter to allow for a clear exposition, but our general techniques will be applicable to more involved languages as well.

Widening functions

A widening function maps values from some type T to a wider type U. We can implement a trivial but generic type-widening method based on the partial ordering of types encoded in Scala’s type system:

scala> def widen[T,U](t: T)(implicit w: T => U): U = w(t)

scala> val longFive = widen[Int,Long](5)
longFive: Long = 5

scala> val doubleFive = widen[Int,Double](5)
doubleFive: Double = 5.0

scala> val arbitraryFive = widen[Int,BigDecimal](5)
arbitraryFive: BigDecimal = 5

Invoking widen[A,B] on an argument of type A will succeed if there is a witness object for A => B. By default, we’ll be able to see the predefined widenings in Scala, including reflexive widenings. Note that there are no implicitly defined narrowings, though:

scala> implicitly[Int => Double]
res0: Int => Double = <function1>

scala> implicitly[Int => Int]
res1: Int => Int = <function1>

scala> implicitly[Double => Int]
<console>:8: error: No implicit view available from Double => Int.
              implicitly[Double => Int]
                        ^

It’s important to note that we could declare other witnesses to A => B for other A and B types and have them in scope; we aren’t constrained by Scala’s predefined definitions or by static relationships between implementation types. (We’ll come back to this point later, when we’re thinking about how to model types in the interpreted language.)

A simply-typed interpreter

We’ll start with a simple interpreter with four kinds of values (integers, doubles, strings, and nulls) and one kind of expression representing numeric addition or string concatenation, depending on the types of its operands. It is a stretch to call the language embodied in this interpreter “typed” (since it has only literal values and expressions but no variables). However, because of the way we’ve encoded the interpreter in Scala, it is impossible to express programs with runtime errors. In particular, it is only possible to create an AddExpression with two arguments that evaluate to values of the same type.

trait SimpleInterpreter {

  trait Addable[T] {
    def plus(self: T, other: T): Value[T]
  }

  implicit object IntAddable extends Addable[Int] {
    def plus(self: Int, other: Int) = IntValue(self + other)
  }

  implicit object DoubleAddable extends Addable[Double] {
    def plus(self: Double, other: Double) = DoubleValue(self + other)
  }

  implicit object StringAddable extends Addable[String] {
    def plus(self: String, other: String) = StringValue(self + other)
  }

  abstract class Expression[T] {
    def eval: Value[T]
  }

  abstract class Value[T](v: T) extends Expression[T] {
    def eval: Value[T] = this
    def get: T = v
  }

  case class IntValue(v: Int) extends Value(v) {}
  case class DoubleValue(v: Double) extends Value(v) {}
  case class StringValue(v: String) extends Value(v) {}
  case object NullValue extends Value(null) {}

  case class AddExpression[T](lhs: Expression[T], rhs: Expression[T])(implicit ev: Addable[T]) extends Expression[T] {
    def eval: Value[T] = {
      val lv = lhs.eval
      val rv = rhs.eval
      ev.plus(lv.get, rv.get)
    }
  }
}

object SimpleInterpreter extends SimpleInterpreter { }

Adding widening

If we have an expression of the form t1 • t2, where the left-hand side is of type T1 and the right-hand side is of type T2, we will be able to convert this to an expression in which both operands have the same type if the following conditions are met:

  1. There must exist some type U such that T1 ⊆ U ⋀ T2 ⊆ U, and
  2. There must exist widening functions with the signatures T1 ⇒ U and T2 ⇒ U.

Finding U is simply finding the least upper bound of T1 and T2 on a semilattice of types. Once we have this least upper bound, if we also have appropriate widening functions, we can convert both t1 and t2 to values of the same type. In the following code, we extend our simple interpreter by modeling interpreter types in Scala, making types properties of values, and adding widening conversions to AddExpression by explicitly encoding the partial ordering of types – in this case, based on a relationship between the nativeType type member of each Type class. (We’re doing widening statically through Scala’s type system in this case, but there’s no reason why we couldn’t take a similar approach dynamically, handling errors by raising exceptions at runtime.)

object WideningInterpreter {
  import scala.language.implicitConversions

  sealed abstract class Type {
    type nativeType <: Any
  }
  class IntType extends Type {
    override type nativeType = Int
  }
  class DoubleType extends Type {
    override type nativeType = Double
  }
  class StringType extends Type {
    override type nativeType = String
  }
  
  abstract class Expression[K <: Type] {
    def eval: Value[K]
  }
  
  class Value[K <: Type](v: K#nativeType) extends Expression[K] {
    def eval: Value[K] = this
    def get: K#nativeType = v
  }
  
  case class IntValue(v: Int) extends Value[IntType](v) {}
  case class DoubleValue(v: Double) extends Value[DoubleType](v) {}
  case class StringValue(v: String) extends Value[StringType](v) {}
  
  sealed trait Addable[K <: Type] {
    def plus(self: K#nativeType, other: K#nativeType): Value[K]
  }
  
  implicit object IntAddable extends Addable[IntType] {
    def plus(self: Int, other: Int) = IntValue(self + other)
  }

  implicit object DoubleAddable extends Addable[DoubleType] {
    def plus(self: Double, other: Double) = DoubleValue(self + other)
  }

  implicit object StringAddable extends Addable[StringType] {
    def plus(self: String, other: String) = StringValue(self + other)
  }
  
  // We need some way to constrain our generic widening operators so
  // that an expression with identical operand types won't have an
  // ambiguous implicit argument.  One way to do this is to make sure
  // that one of the widening functions will only apply if the arguments
  // are of different types.  

  // These type inequality instances are taken from an answer Miles Sabin 
  // gave on StackOverflow:  http://stackoverflow.com/a/6944070

  trait =!=[A, B]
  implicit def neq[A, B] : A =!= B = null
  implicit def neqAmbig1[A] : A =!= A = null
  implicit def neqAmbig2[A] : A =!= A = null
  
  implicit def leftWiden[T <: Type, U <: Type](v1: Value[T], v2: Value[U])
      (implicit conv: (T#nativeType => U#nativeType)): (Value[U], Value[U]) =
    (new Value[U](conv(v1.get)), v2)

  implicit def rightWiden[T <: Type, U <: Type](v1: Value[U], v2: Value[T])
      (implicit neq: T =!= U,
                conv: (T#nativeType => U#nativeType)): (Value[U], Value[U]) =
    (v1, new Value[U](conv(v2.get)))

  case class AddExpression[T <: Type, U <: Type, V <: Type]
      (lhs: Expression[T], rhs: Expression[U])
      (implicit widen: (Value[T], Value[U]) => (Value[V], Value[V]), adder: Addable[V]) extends Expression[V] {
    def eval = {
      val lv = lhs.eval
      val rv = rhs.eval
      val args = widen(lv, rv)
      adder.plus(args._1.get, args._2.get)
    }
  }
}

In WideningInterpreter we extend AddExpression to allow it to have two potentially distinct argument types (Value[T] and Value[U]) and by requiring evidence of an implicit conversion from a pair of values with distinct types to a pair of values with the same type.1 We define two witness functions, leftWiden for the case in which the left element of the pair is narrower than the right, and rightWiden for the case in which the right element of the pair is narrower than the left. In both cases, we determine that a type T is narrower than another type U if Scala knows how to widen values of the representation type (Type#nativeType) of T to the representation type of U; this is the case if an implicit resolution exists for the conv argument.

The problem we might encounter is that, because our partial ordering is reflexive, if T and U are the same type, then there will be witnesses both for T#nativeType => U#nativeType and U#nativeType => T#nativeType. So if we were to have naive implementations of leftWiden and rightWiden that only depended on evidence of such a conversion, Scala would be unable to unambiguously resolve which would apply in the case of monomorphic AddExpressions. We resolve this problem by adding a test for type inequality (due to Miles Sabin) to the implicit argument list of rightWiden, so that it will not apply if the arguments are of the same type.2

Note that the partial ordering among interpreter types (IntType, DoubleType, and StringType) does not depend on Scala-level subtyping relationships between interpreter types. This is important because in a more realistic language we will want the flexibility to model data types independently of properties of our object-language implementation. Instead, we have a generic partial ordering in this example based on predefined relationships between representation types, and we could extend the partial ordering to other types by adding other instances of =>[A,B] for other types of interest.

For a small number of interpreter types, we could also explicitly encode the partial ordering, as in the example below:

implicit def intDoubleWiden(v1: Value[IntType], v2: Value[DoubleType]): (Value[DoubleType], Value[DoubleType]) =
  (DoubleValue(v1.get.toDouble), v2)

implicit def doubleIntWiden(v1: Value[DoubleType], v2: Value[IntType]): (Value[DoubleType], Value[DoubleType]) =
  (v1, DoubleValue(v2.get.toDouble))

Since in this example we have a total ordering among types, we can also easily widen one argument at a time by adding a witness object for the least upper bound of T and U,3 as in the example below:

implicit def widen[T <: Type, U <: Type](v1: Value[T])
    (implicit conv: (T#nativeType => U#nativeType)): (Value[U]) =
  new Value[U](conv(v1.get))

implicit def reflexiveWiden[T <: Type](v1: Value[T]): Value[T] = v1

trait LT[T <: Type, U <: Type] {}
implicit def intDoubleLT: LT[IntType, DoubleType] = null

trait WiderThan[T <: Type, U <: Type, V <: Type] {}
implicit def rightWider[T <: Type, U <: Type, V <: Type]
  (implicit rw: LT[T, U], 
            conv2: (U#nativeType => V#nativeType),
            conv1: (T#nativeType => V#nativeType)): WiderThan[T,U,V] = null

implicit def leftWider[T <: Type, U <: Type, V <: Type]
  (implicit rw: LT[U, T], 
            conv2: (T#nativeType => V#nativeType),
            conv1: (U#nativeType => V#nativeType)): WiderThan[T,U,V] = null

implicit def reflWider[T <: Type]: WiderThan[T, T, T] = null

case class AddExpression[T <: Type, U <: Type, V <: Type]
    (lhs: Expression[T], rhs: Expression[U])
    (implicit lub: WiderThan[T, U, V],
              widenLeft: Value[T] => Value[V], 
              widenRight: Value[U] => Value[V],
              adder: Addable[V]) extends Expression[V] {
  def eval = {
    val lv = widenLeft(lhs.eval)
    val rv = widenRight(rhs.eval)
    adder.plus(lv.get, rv.get)
  }
}

Again, a similar approach would be applicable in an untyped Scala representation of interpreter-language types: we could represent types as terms, implement the least-upper-bound relation as a partial function mapping from a pair of terms to the least upper bound of the pair, and implement widenings as functions taking a value and a term representing the type to widen to.

Footnotes

  1. See the signature for the widen implicit argument to AddExpression: (Value[T], Value[U]) => (Value[V], Value[V])↩︎

  2. This type-inequality test will fail if it is given two identical types because both neqAmbig1 and neqAmbig2 will both be applicable.↩︎

  3. It occurred to me while developing these examples that using witness objects in this way is a lot like forward-chaining logic programming. (Note that we use negation-as-failure in implicit resolution when testing for type inequality and we use implicit arguments to guide further implicit resolution with the WiderThan witness.) Unsurprisingly, it turns out that other people have had the same idea! See the discussion on this post or this talk for two examples.↩︎