## Hyperspecialize.jl

Simple ambiguity resolution.
Author willow-ahrens
Popularity
3 Stars
Updated Last
1 Year Ago
Started In
February 2018

# Hyperspecialize

Hyperspecialize is a proud hack of a Julia package designed to resolve method ambiguity errors by automating the task of redefining functions on more specific types!

## Problem

It is best to explain the problem (and solution) by example 1. Suppose Peter and his friend Jarrett have both developed eponymous modules `Peter` and `Jarrett` as follows:

```module Peter
import Base.+

struct PeterNumber <: Number
x::Number
end

Base.:+(p::PeterNumber, y::Number) = PeterNumber(p.x + y)

export PeterNumber
end

module Jarrett
import Base.+

struct JarrettNumber <: Number
y::Number
end

Base.:+(x::Number, j::JarrettNumber) = JarrettNumber(x + j.y)

export JarrettNumber
end```

Peter and Jarrett have both defined fun numeric types! However, look what happens when the user tries to use Peter's and Jarrett's numbers together...

```julia> using .Peter

julia> using .Jarrett

julia> p = PeterNumber(1.0) + 3
PeterNumber(4.0)

julia> j = 2.0 + JarrettNumber(2.0)
JarrettNumber(4.0)

julia> friends = p + j
ERROR: MethodError: +(::PeterNumber, ::JarrettNumber) is ambiguous. Candidates:
+(x::Number, j::JarrettNumber) in Main.Jarrett at REPL[2]:8
+(p::PeterNumber, y::Number) in Main.Peter at REPL[1]:8
Possible fix, define
+(::PeterNumber, ::JarrettNumber)```

Oh no! Since a `PeterNumber` is a `Number` and a `JarrettNumber` is a `Number`, both `+` methods are applicable, and neither method is more specific. Julia has no way to decide which method to use, and asks the user to decide by defining a more specific method.

There is a question of what role developers should play in the resolution of this ambiguity.

• All developers can coordinate their efforts to agree on how their types should interact, and then define methods for each interaction. This solution is unrealistic since it poses an undue burden of communication on the developers and since multiple behaviors may be desired for an interaction between types. In the above example, the two definitions of `+` have different behavior and either may be desired by the user.

• The developer can write their library to run in a modifed execution environment like Cassette. This solution creates different contexts for multiple dispatch.

• A single developer can define their ambiguous methods only on concrete subtypes in `Base`, and provide utilities to extend these definitions. For example, Peter could define `+` on all concrete subtypes of `Number` in Base. In cases of ambiguity, `+` would then default to Jarrett's definition unless the user asks for Peter's definition.

Hyperspecialize is designed to standardize and provide utilities for the latter approach.

Peter decided to use Hyperspecialize, and now his definition looks like this:

`  @replicable Base.:+(p::PeterNumber, y::@hyperspecialize(Number)) = PeterNumber(p.x + y)`

This solution will replicate this definition once for all concrete subtypes of `Number`. This list of subtypes depends on the module load order. If Peter's module is loaded first, we get the following behavior:

```julia> friends = p + j
JarrettNumber(PeterNumber(8.0))```

If Jarrett's module is loaded first, we get the following behavior:

```julia> friends = p + j
PeterNumber(JarrettNumber(8.0))```

## Explicit Solution

Peter doesn't like this unpredictable behavior, so he decides to explicitly define the load order for his types. He asks for his code to only be defined on the concrete subtypes of `Number` in `Base`. He uses the `@concretize` macro to define which subtypes of `Number` to use. Now his definition looks like this:

```  @concretize myNumber [BigFloat, Float16, Float32, Float64, Bool, BigInt, Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8]

@replicable Base.:+(p::PeterNumber, y::@hyperspecialize(myNumber)) = PeterNumber(p.x + y)```

Since Peter has only defined `+` for the concrete subtypes of Number, the user will need to ask for a specific definition of `+` for a type they would like to use. Consider what happens when Peter's package and Jarrett's package are loaded together.

```julia> friends = p + j
JarrettNumber(PeterNumber(8.0))

julia> using Hyperspecialize

julia> @widen Peter.myNumber JarrettNumber
Set(Type[BigInt, Bool, UInt32, Float64, Float32, Int64, Int128, Float16, JarrettNumber, UInt128, UInt8, UInt16, BigFloat, Int8, UInt64, Int16, Int32])

julia> friends = p + j
PeterNumber(JarrettNumber(8.0))```

Before the `myNumber` type tag in the `Peter` module is widened, there is no definition of `+` for `PeterNumber` and `JarrettNumber` in the `Peter` package, but since the `Jarrett` module defines a more generic method, that one is chosen. After the user widens Peter's definition to include a JarrettNumber (triggering a specific definition of `+` to be evaluated in Peter's module), the more specific method in Peter's package is chosen.

## Opt-In, But Everyone Can Join

Suppose Jarrett has also been thinking about method ambiguities with Peter's package and decides he will also use `Hyperspecialize`.

```  @concretize myNumber [BigFloat, Float16, Float32, Float64, Bool, BigInt, Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8]

@replicable Base.:+(x::@hyperspecialize(myNumber), j::JarrettNumber) = JarrettNumber(x + j.y)```

to his module, and the behavior is as follows:

```julia> p + j
ERROR: no promotion exists for PeterNumber and JarrettNumber
Stacktrace:
[1] error(::String, ::Type, ::String, ::Type) at ./error.jl:42
[2] promote_to_supertype at ./promotion.jl:284 [inlined]
[3] promote_result at ./promotion.jl:275 [inlined]
[4] promote_type at ./promotion.jl:210 [inlined]
[5] _promote at ./promotion.jl:249 [inlined]
[6] promote at ./promotion.jl:292 [inlined]
[7] +(::PeterNumber, ::JarrettNumber) at ./promotion.jl:321
[8] top-level scope```

There is now no method for adding a PeterNumber and a JarrettNumber! The user must ask for one explicitly using `@widen` on either Peter or Jarrett's `myNumber` type tag. If the user chooses to widen Jarrett's definitions, we get

```julia> @widen Jarrett.myNumber PeterNumber
Set(Type[BigInt, Bool, UInt32, Float64, Float32, Int64, Int128, Float16, PeterNumber, UInt128, UInt8, UInt16, BigFloat, Int8, UInt64, Int16, Int32])

julia> p + j
JarrettNumber(PeterNumber(8.0))```

If the user instead chooses to widen Peter's definitions, we get

```julia> @widen Peter.myNumber JarrettNumber
Set(Type[BigInt, Bool, UInt32, Float64, Float32, Int64, Int128, Float16, UInt128, UInt8, UInt16, BigFloat, Int8, UInt64, JarrettNumber, Int16, Int32])

julia> p + j
PeterNumber(JarrettNumber(8.0))```

# Getting Started

This library provides several functions for managing the defintions to replicate and the types they are replicated over.

## Concretization

The user must enumerate the types that a definition is to replicated over. We use type tags to describe a particular set of types. The type tag arguments to macros are interpreted literally as symbols. The set of types is referred to as the concretization.

You may specify the concretization of a type tag using the `@concretize` macro like this:

`@concretize Key Int`

You may specify more than one type:

`@concretize Key (Int, Float64, Float32)`

If you would like to expand the concretization of a type tag, use the `@widen` macro.

`@widen Key (BigFloat, Bool)`

You may query the concretization of a type tag with the `@concretization` macro.

`@concretization Key`

Type tags always have module-local scope and if no module is specified, they are interpreted as belonging to the module in which they are expanded. You may use the type tag form `mod.Key` to specify a module anywhere a type tag is an argument to a macro.

`@concretization(mod.Key)`

If no concretization is given for a type tag `Key` in module `mod`, the tag is given the default concretization corresponding to all the concrete subtypes of whatever the symbol `Key` means when evaluated in `mod` (so if you are making up a tag name, please define a concretization for it).

## Replicable

The heart of the Hyperspecialize package is the `@replicable` macro, which promises to replicate a definition for all combinations of types in the concretization of type tags that appear in the definition. `@replicable` takes only one argument, the code to be replicated at global scope in the current module. To specify type tags, use the @hyperspecialize macro where the types in the concretization of a tag should be substituted.

Thus, the following example

```module Foo
@concretize MyKey (Int, Float32)
@replicable bar(x::@hyperspecialize(MyKey), y::(@hyperspecialize MyKey)) = x + y
end```

will execute the following code at global scope in `Foo`.

```bar(x::Int, y::Int) = x + y
bar(x::Float32, y::Int) = x + y
bar(x::Int, y::Float32) = x + y
bar(x::Float32, y::Float32) = x + y```

If someone has loaded the `Foo` module and calls

`  @widen Foo.MyKey Float64`

then the following code will execute at global scope in `Foo`.

```bar(x::Float64, y::Float64) = x + y
bar(x::Int, y::Float64) = x + y
bar(x::Float32, y::Float64) = x + y
bar(x::Float64, y::Int) = x + y
bar(x::Float64, y::Float32) = x + y```

Notice that the earlier definitions are not repeated.

# The Fine Print

This is an example of a module where the idea is simple and the details are not.

## Data And Precompilation

Data is stored in `const global` dictionaries named `__hyperspecialize__` in every module that calls `@concretize` (Note that this can happen implicitly if other methods are called that expect a concretization to exist already).

For this reason (and to keep things simple), you cannot concretize a type tag in a module that is not your own.

Since this package works by calling "eval" on different modules to widen types, if you want to call `@widen` on a type key in another module, you must do so from the `__init__()` function in your module. See the documentation on `__init__()`.

## When Is Hyperspecialize Right For Me?

There are three main drawbacks to the Hyperspecialize package.

• These macros may generate a very large number of definitions if the function definition includes many hyperspecialized type tags. For mathematical operators this can be alleviated using Julia's promotion rules, but the problem of how to define an unambiguous `promote_type` still stands. To further reduce the number of methods that are defined, in some situations it may be sufficient to only concretize the type tag to be a union of concrete types in Base. This strategy works best if it is unlikely that the method will be redefined using those types.

• The second drawback is that the user must manually choose desired behavior, so if the ambiguity is related to an internal type, the user may not know how to resolve it.

• The third drawback is that both methods that create an ambiguity may be desired by a user, and they are forced to choose one global behavior. This can be problematic if a different library has widened the same type tag and made that choice for them already.

In short, Hyperspecialize works best when the user knows which types are being concretized, and when the resolution to method ambiguities is clear. A major benefit to using Hyperspecialize is that you may keep your type-based API, you are not forced to adopt a function-based API. If this is not something that is important to you and you cannot work around difficulties involved in using Hyperspecialize, you will likely be better off using a contextual dispatch solution such as Cassette.

1: I have chosen `+` as an example function, but it would be possible to define promotion rules to avoid some ambiguities. However, it is possible that type ambiguities may occur in the definition of the `promote_type` function.