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:

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:

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.

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 T1UT2U, 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.)

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:

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:

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.

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.

type systemssqlhivescalatype coercions • You may reply to this post on Twitter or