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:

```
> def widen[T,U](t: T)(implicit w: T => U): U = w(t)
scala
> val longFive = widen[Int,Long](5)
scala: Long = 5
longFive
> val doubleFive = widen[Int,Double](5)
scala: Double = 5.0
doubleFive
> val arbitraryFive = widen[Int,BigDecimal](5)
scala: BigDecimal = 5 arbitraryFive
```

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:

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

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
.plus(lv.get, rv.get)
ev}
}
}
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:

- There must exist some type
*U*such that*T1*⊆*U*⋀*T2*⊆*U*, and - 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,
: (T#nativeType => U#nativeType)): (Value[U], Value[U]) =
conv(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)
.plus(args._1.get, args._2.get)
adder}
}
}
```

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],
: (U#nativeType => V#nativeType),
conv2: (T#nativeType => V#nativeType)): WiderThan[T,U,V] = null
conv1
implicit def leftWider[T <: Type, U <: Type, V <: Type]
(implicit rw: LT[U, T],
: (T#nativeType => V#nativeType),
conv2: (U#nativeType => V#nativeType)): WiderThan[T,U,V] = null
conv1
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],
: Value[T] => Value[V],
widenLeft: Value[U] => Value[V],
widenRight: Addable[V]) extends Expression[V] {
adderdef eval = {
val lv = widenLeft(lhs.eval)
val rv = widenRight(rhs.eval)
.plus(lv.get, rv.get)
adder}
}
```

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

See the signature for the

`widen`

implicit argument to`AddExpression`

:`(Value[T], Value[U]) => (Value[V], Value[V])`

↩︎This type-inequality test will fail if it is given two identical types because both

`neqAmbig1`

and`neqAmbig2`

will both be applicable.↩︎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.↩︎