Arithmetic on types?

[timholy]

We've had quite a few issues crop up about how to define types of outputs given inputs. My view is that this is revealing limitations in the promotion system. A proposal to deal with this might be to define arithmetic on types.

For example, here would be some rules:

Int*Int == Int
Int+Int == Int
Meter{Float64}+Meter{Float64} == Meter{Float64}
Meter{Float64}*Meter{Float64} == Meter{Float64}^2
Meter{Float64}/Meter{Float64} == Float64
Matrix{Int}+Matrix{Float64} == Matrix{Float64}

and so on.

[JeffBezanson]

Now this gets into some interesting territory.

Currently julia's domain has two "levels": values and types. You go from values to types via a typeof relation, and among types via a subtype relation. x => Type{x} is also a typeof relation. subtype is a partial order, so the types form a lattice and this is where all the analysis takes place. Unfortunately typeof is not an order relation, so it is a bit difficult to account for in this framework. But the advantage is that "real values" are neatly separated.

An alternate formulation would be to insist that everything be part of the lattice. There would be no typeof relation. We would have 5 <: Int. In that world, the call Int + Int would actually match the method definition +(a::Int, b::Int). The implementation of this call would use "approximate" computation (type inference), instead of actual computation. This system has an appealing elegance; it would be very interesting to try. However it has complementary problems to our current system. Given the information (a<:Int + b<:Int)<:Int, you cannot tell if it can be implemented with an add instruction. It seems you inherently need another "level" to talk about whether a will be a "real" integer. I.e. a "kind" system that tells you what is a real value. But then you'd need to infer the kinds as well, which seems to put you back at the first design above.

I believe this second design is the only reasonable way to support Int + Int. Having separate definitions for ::Int + ::Int and ::Type{Int} + ::Type{Int} is a non-starter. I really think you'd need to support running all code implicitly on types; it wouldn't be enough just to support some class of functions via f(xs::Type...) definitions.

Ultimately we need approaches that will work for e.g. #7258 (comprehensions). An example is

julia/base/abstractarray.jl

Line 1298 in 3af5019

function map_to!{T}(f::Callable, offs, dest::AbstractArray{T}, A::AbstractArray)

(map).

This is a hard problem, but I'm not yet in favor of actually writing Int + Int. It also seems to have a code duplication problem; you have to write your computation once for the value domain and again for the type domain.

[timholy]

Having separate definitions for ::Int + ::Int and ::Type{Int} + ::Type{Int} is a non-starter.

I'm not disagreeing exactly, but I think it's worth asking seriously: why is this so bad? Compared, say, to fixing code like this and heroics like this? It would be nice to be able to define map like this:

function map(f::Function, A::AbstractArray{T})
    output = similar(A, f(T))
    for i = 1:length(A)
        output[i] = f(A[i])
    end
    output
end

We could have macros like @hasone, which would be used like this

@hasone +(a::Int, b::Int) = low_level_stuff

and get expanded to

+(a::Int, b::Int) = low_level_stuff
+(::Type{Int}, ::Type{Int}) = typeof((+)(one(Int), one(Int)))

With a few other similar tricks to handle cases where one doesn't exist, most of the time you probably wouldn't have to write any more code.

[JeffBezanson]

I agree output = similar(A, f(T)) is a nice notation, but it has the problem of needing to work for all functions, and that you have to write f( ) twice.

A requirement that every definition also need or imply some other definition can only be a language feature; I don't want to tack it on with macros.

We could possibly add notations for explicitly computing in the type domain, e.g. writing f(::T) to get return_type(f, (T,)).

[toivoh]

That is indeed an interesting and very different alternative, but I'm not
so sure that it's workable either.

Monotonicity constraints on function return types as discussed in e.g.
#1090 (comment) would
be another way to encode the arithmetic (and more) on types in line with
the actual methods. I guess that it would not be expressed as e.g. Int + Int but using some other syntax, but I think that's ok.

Btw: I implemented some arithmetic on types explicitly in broadcast.jl just
to be able to give reasonable result types to ./ etc., though that felt
pretty clunky.

[timholy]

We could possibly add notations for explicitly computing in the type domain, e.g. writing f(::T) to get return_type(f, (T,))

That's a really interesting idea. I like it. We could probably already be using return_types to better effect in Base, if we make it run at compile time.

@toivoh, I agree this interacts closely with type declarations on function outputs.

[andreasnoack]

I really like this idea, as you already know.

@JeffBezanson, I think that you already have to write f twice for array code. Much of the code in the linalg directory has lines of the type

S = typeof(one(T)/one(T))
S = typeof(one(T)/norm(one(T)))

and matmul.jl has the famous

TS = promote_type(arithtype(T),arithtype(S))

The last one has the advantage of avoiding the value level which is useful because one is not defined for matrices. I'm not the right person to suggest how to implement this functionality. I can only point to the usefulness of it and that I don't see a big difference in defining

arithtype(T) = T
arithtype(::Type{Bool}) = Int

and

+(T::Type, S::Type) = promote_type(T,S)
*(T::Type, S::Type) = promote_type(T,S)
+(::Type{Bool},::Type{Bool}) = Int

[timholy]

@andreasnoackjensen, promote_type(S, T) and similar are broken: if T and S are both Meter, then the correct type depends on the operation: schematically, Meter+Meter->Meter, Meter*Meter->Meter^2, Meter{Float64}/Meter{Float64}->Float64.

At a bare minimum, we need it to be promote_type(operation, T, S).

[andreasnoack]

It was not meant as a defense for promote_type, but more as an example showing that we already do things like this for array operations.

Generally, I think we agree pretty much on this issue and in particular I think it makes really good sense to do promotion with respect to some operation. However, @StefanKarpinski and @JeffBezanson seemed to disagree when I proposed that, so it might be that my understanding of promotion is wrong.

[JeffBezanson]

The argument that there is already duplication, and so we can/should do more, does not work for me. The ultimate goal should be to remove the duplication.

The second best option is for the duplication to be very obvious, e.g.

T = @typeof f(x) + g(y)
A = Array(T,n)
A[i] = f(x) + g(y)

Adding definitions to + is totally non-scalable. Taken to its logical conclusion, this implies adding an extra definition for every single existing definition in the ecosystem. If we don't add that many definitions, we will be left with second-class functions/types that "don't work with matmul".

I agree there is not a big difference between that and arithtype. They are equally unacceptable.

promote_type was not really meant to solve this problem. I think it should remain a low-level building block that can be called by implementations of f where needed, and discovering the overall behavior of f is a separate problem.

[timholy]

I'm happy with whatever solution allows one to allocate instances of output arrays with the appropriate type even if:

• inputs are empty arrays (don't actually have instances to pass to T = @typeof A[1] + B[1])
• one/zero etc don't exist
• works for any operation

I do like the idea of leveraging Base.return_types at compile-time.

[andreasnoack]

@JeffBezanson, I don't understand the consequences of your first idea well enough to see how many new duplicates are needed. I'm only saying that duplication is already necessary for a lot of the array code.

The ultimate goal should be to remove the duplication.

Yes. That would be great.

The second best option is for the duplication to be very obvious

I think this the purpose of type arithmetic

Adding definitions to + is totally non-scalable

It wasn't meant as an idea for implementing this, so I should probably have skipped that part.

@timholy, Isn't it a problem that Base.return_types works for a single function, e.g. matrix multiplication is the composition T*S+T*S and LU is something like (T-T)/T?

[JeffBezanson]

That is a good summary of requirements. I think we could have a @typeof that evaluates its argument in the type domain (i.e. not for real). I'm fairly sure this was discussed in another thread somewhere but finding it appears hopeless (so far I can't get github to search for a literal @ character).

Once code is in the form

T = @typeof f(x)
...
A[i] = f(x)

There seems to be some hope of making the snake eat its tail, and folding the two f(x)s together.

[andreasnoack]

I think this is the discussion

1257643

It never became a pull request so it is a bit hidden.

[timholy]

@andreasnoackjensen, yes, we'd need a version that works on expressions, too. But I think it's the same basic idea: leverage the type-inference machinery.

I had forgotten about that previous discussion, thanks for the link.

[simonster]

There's also #5588 (comment), #6114 (comment), and my PR #6692, although I closed that recently because I thought we were trying to move away from having return types depend on type inference. But in this case, maybe there is not a tractable alternative?

[JeffBezanson]

Yes, we do want to avoid it as much as possible. But there seem to be cases where you really do need a good guess for the element type before computing anything.

[toivoh]

The whole point of the monotonic return types idea (see the thread and discussion in #1090) was that it would provide upper bounds on return types that would be more predictable and not depend on type inference. Of course, adding return type annotations on methods could be seen as a slight duplication, and I know it's probably a bit complex to implement.

Still, anyone care to comment on this alternative?

[StefanKarpinski]

I still like the idea of monotonic return types, but I worry that it has an extreme non-locality property: you write a new method and it returns a value of a type that is completely unrelated to the code you wrote. By the same token, behavior of code you write can change when someone else changes their code. One possibility to deal with that if a "supermethod" has a type annotation, then all its "submethods" must have a type annotation or a warning is printed; if the type annotation of submethod is not a subtype of its supermethods, that should also be a warning (or maybe an error). That lets you hack things out without bothering with type annotations, getting a few warnings, but means that you get early warning if a non-local interaction between supermethods and submethods changes.

[toivoh]

Completely agree, there should at least be a warning if there is a submethod that has a less strict return type annotation than its supermethods, otherwise this could lead to lots of unintended breakage. That will cause some inertia in the return type annotations, especially in deep hierarchies, but I think most hierarchies will not be that deep. I guess an absent return type annotation would be the same as ::Any.

[StefanKarpinski]

That seems good. Having supermethod(args...)::Integer and submethod(args...) would be equivalent to submethod(args...)::Any, which would generate a warning since Any ⊈ Integer. The nice thing about that is that there's only one rule: submethods must have a return type annotation – explicit or implicit – which is a subtype of any supertype annotations. Since Any is the default return type – as it is for everything – the requirement that submethods of methods which are annotated with something stricter than ::Any also be annotated just falls out naturally.

[StefanKarpinski]

Let's move this part of the conversation over there for posterity.

[quinnj]

For my own clarification, what's the difference between a "supermethod" and a "submethod"? Does it have to do with generality of the method arguments? (i.e. more abstract args = supermethod?)

[StefanKarpinski]

If the tuple of argument types of method A is TA and the tuple of argument types of B is TB then A is a submethod of B if and only if TA <: TB.

[StefanKarpinski]

The most general argument signature is (Any...) while any concrete set of arguments with fixed number is maximally specific (only unsatisfiable signatures are more specific).

[JeffBezanson]

Unless we support general singleton types, in which case f(::Int) is concrete, but f(::Type{5}) is more specific. Which should be doable, but scares me. Maybe we want some restrictions around that. For example, we could disallow specializing the same argument slot of the same function for both a concrete type and strict subtypes of it. So Int and Type{5} would be disallowed, but Integer and Type{5} would be ok. Hard to say how necessary this is though.

[rfourquet]

A C++'s integral_constant-like type can mostly be used for singleton types:

type Value{v} end
typealias VType{v} Type{Value{v}}
f(::VType{5}) = 0
f{v}(::VType{v}) = v
f(v::Int) = f(Value{v}) # for user convenience

Is it the case that a call to f(5) would then be less efficient than if f(::Type{5}) existed? Do singleton types for values solve more problems than Value above?

[JeffBezanson]

Yes, currently f(5) with that code requires constructing the Value{5} type at run time. With this built-in, f(5) could directly (or in-line) call the definition that returns 0.

However things get worse when the f(v::Int) definition does an important computation, and is not just a convenience wrapper for f{v}(::VType{v}). For example

f(::Type{1}) = 0  # special case
f(x::Int) = x^2

Here a "typical" call to f with an arbitrary integer will be really slow unless we are smart enough to generate if x==1; 0; else x^2; end.

[rfourquet]

The "convenience" syntax is only optional. For "internal" functions called with compile time values, usage of Value seems acceptable. For functions used mainly with runtime values, specialization on values amounts to a runtime dispatch, then why not (simple) pattern matching:

# sugar for: f(x::Int) = if x==1; 0; else x^2; end
f(x::Int) = x^2
f(1) = 0

I just mean to say that ::Type{5} looks more like an implementation detail than a useful type for the user (but I'm probably missing important use cases).

[lindahua]

Any new progress along this? I often find the need of a way to get the return type.

[ViralBShah]

@lindahua Does stagedfunction not help for your use case?

[timholy]

Can you give an example of how you'd use a stagedfunction for this?

[ViralBShah]

I will work out an example for myself - which will probably answer my own question, or have me ask more questions about staged functions.

[timholy]

Working on solving the ambiguity warnings caused by #12115 by exploiting generic fallbacks, I've come to think that promote_type should only be used for containment operations like vcat(a,b). We probably need some other rule for a+b that takes the operator into account. As always, SIUnits is a good example: vcat(1m, 1m) should give an array of eltype Meter but 1m*1m has type Meter^2.

This issue fits "Arraymagedon" very well, since it invariably crops up whenever one wants to define arithmetic on weird types and support such operations for arrays of such types. So I'm giving this a 0.5 milestone.