A few months ago, I noticed the following paragraph while reading Swift’s Type Checker documentation:

Swift’s type inference allows type information to flow in two directions. As in most mainstream languages, type information can flow from the leaves of the expression tree up to the root. However, Swift also allows type information to flow from the context at the root of the expression tree down to the leaves. This bi-directional type inference is common in languages that use ML-like type systems, but is not present in mainstream languages like C++, Java, C#, or Objective-C.

At that time, I had never heard the term bi-directional type inference before. While I did know about certain language features (e.g., closures, implicit member expressions) that rely on this kind of type inference, I didn’t realize that it also impacts things like overload resolution.

In this blog post, I show a few examples of bottom-up type inference and top-down type inference which can be subsumed under the term bi-directional type inference. Knowing how Swift uses bi-directional type inference can give you a better understanding of its type system.

Bottom-up Type Inference

Bottom-up type inference is the kind of type inference where the type information flows from the bottom of the abstract syntax tree (AST) to the top. It is the more common kind of type inference and is used in many statically-typed programming languages. The following code snippet shows a few examples of bottom-up type inference in Swift:

let age = 26              // age is of type Int
let name = "Toni"         // name is of type String
let pair = (age, name)    // pair is of type (Int, String)

The type of pair is inferred from its initial value (age, name). The following picture shows the AST for that expression:

The type of each identifier expression is determined by performing a name lookup. For example, for the name age, the type checker finds a constant that has the type Int. Similarly, for the name name it finds a constant of type String. Finally, the type of the tuple expression at the root of the AST is a tuple type that is composed of the types of the two tuple elements, resulting in the type (Int, String). Thus, the type information flows from the leaves of the tree up to the root.

With bottom-up type inference, leaf nodes have an intrinsic type. For example, integer literals default to the type Int and string literals default to the type String which is what happens when the compiler infers the types of the constants age and name. Similarly, an identifier expression references some entity (e.g., a variable or a function) that also has a type.

Top-down Type Inference

As mentioned above, Swift also allows type information to flow in the other direction; from top to bottom. This can be seen with various kinds of expressions such as literals, implicit member expressions, closures and function call expressions.

Literals

First, let’s look at Swift’s literals:

let x = 2             // x is of type Int
let y: Double = 2     // y is of type Double

This code illustrates that integer literals can be used to initialize constants / variables of type Int as well as ones that are of type Double. By default, an integer literal is of type Int. With an explicit type annotation we can change it to be of type Double instead.

The type annotation in a constant / variable declaration acts as a contextual type for the initial value. There are other language constructs where there is a contextual type for an expression, but I will talk about that in a different blog post. Integer literals can be used wherever the contextual type conforms to the ExpressibleByIntegerLiteral protocol. Types such as Int, UInt, Double and Float all conform to this protocol.

Note that the above example only works, because an integer literal is not the same as an instance of type Int. In contrast, the following code does not compile, because x is an instance of type Int and there is no implicit conversion from Int to Double:

let x = 2             // x is of type Int
let y: Double = x     // error: cannot convert value of type 'Int' to specified type 'Double'

If we really wanted to convert x into a Double, we would have to write let y = Double(x) in order to explicitly convert it by calling one of Double‘s initializers.

Other literals work in the same vein. For example, array literals default to the type Array<T> but they can also be used to initialize constants / variables of type Set<T> because the type Set conforms to the ExpressibleByArrayLiteral protocol:

let arr = [1, 2, 3]                 // arr is of type Array<Int>
let set: Set<Int> = [1, 2, 3]       // set is of type Set<Int>

Implicit Member Expressions

Implicit member expressions are often used to abbreviate references to enum cases, when the enum type is known from the context:

enum Season {
    case spring
    case summer
    case fall
    case winter
}

var season = Season.summer          // season is of type Season
season = .fall

In this example, the variable season is first initialized with the explicit member expression Season.summer, which means that its inferred type is Season. Since the variable season now has a fixed type, we can use the implicit member expression .fall to change its value. In other words, the type of the variable acts as a contextual type for the expression .fall.

Closures

Closures are another one of Swift’s language features that heavily relies on top-down type inference. The parameter types and return types of closures are often not specified explicitly but instead inferred from the closure’s context:

let numbers = [1, -2, 3]            // numbers is of type Array<Int>
let positiveNumbers = numbers.filter { n in n >= 0 }
print(positiveNumbers)              // [1, 3]

In this example, the filter() method expects a single argument of type (Int) -> Bool. This is also the contextual type for the closure that is passed as argument, which in turn means that the inferred type for n is Int.

Let’s change this example a little bit by using floating point literals instead of integer literals in the initial value of the constant numbers:

let numbers = [1.0, -2.0, 3.0]      // numbers is of type Array<Double>
let positiveNumbers = numbers.filter { n in n >= 0 }
print(positiveNumbers)              // [1.0, 3.0]

Now the inferred type of numbers is Array<Double> instead of Array<Int> which also means that the filter() method now expects an argument of type (Double) -> Bool. Additionally, the type of n has changed to Double as well.

Overload Resolution

In Swift, functions can be overloaded. At compile time, the type checker needs to determine, which of the overloads is called in a particular function call. In contrast to many other programming languages, overload resolution in Swift not only depends on the argument types but also on the contextual type of a function call:

func f() -> Int {
    return 2
}

func f() -> String {
    return "test"
}

let x = f()                   // error: ambiguous use of 'f()'
let y: Int = f()              // Overload Resolution picks f: () -> Int
let z: String = f()           // Overload Resolution picks f: () -> String

In the declaration of x there is no contextual type, which makes the function call f() ambiguous, because the type checker doesn’t know which overload to pick. In the declarations of y and z there is an explicit type annotation, which allows the type checker to choose the correct overload with the matching return type. Note that in many programming languages it is not possible to declare two functions that only differ in their return type.

This kind of top-down type inference works through multiple levels of indirection as shown in the following example:

func f() -> Int {
    return 2
}

func f() -> String {
    return "test"
}

func id<T>(_ value: T) -> T {
    return value
}

let x = id(id(f()))           // error: ambiguous use of 'f()'
let y: Int = id(id(f()))      // Overload Resolution picks f: () -> Int
let z: String = id(id(f()))   // Overload Resolution picks f: () -> String

Here the result of the function call f() is passed through two invocations of the generic identity function id(). The declaration of x is still ambiguous, since there is no explicit type annotation. For the constants y and z the explicit type annotation determines the type that should be used as the argument for the generic parameter T of the outer id() call. The generic parameter T of the outer id() call is then used as the argument for the generic parameter T of the inner id() call. Finally, the generic parameter T of the inner id() call constrains the call to f() and allows the type checker to choose the correct overload with the matching return type.

Conclusion

This blog post has shown several examples of bottom-up and top-down type inference. Swift’s type checker uses a constraint-based system to implement this kind of bi-directional type inference. I will write more about these implementation details in future blog posts.