Function Parameter Speculation #17168

Internals & Design
21

Note that ∘ is a law of composition on Function; it is always the case that (f::Function ∘ g::Function)::Function. The only difference between Function and Int64 is that Function is abstract.

It sounds like what you’re looking for is to be able to do composition, and be able to interchange results of such composition, in a performant and type stable way. This is a difficult problem in general, but a technique called “embedding” applies here. Note that I will ignore performance for simplicity; work done by Yichao Yu and other members of the core dev team is in place to make this kind of thing more performant.

The idea is to embed a particular space of functions into a single type. This enables the property that all objects inside this embedding have the same concrete type, which seems to be what you’re looking for.

Following is an example.

import Base: convert, show, ∘
struct Hom{D, R} <: Function
    f::Any  # performance is ignored here; this can be improved
end

show(io::IO, φ::Hom) = print(io, φ.f, " as ", typeof(φ))
show(io::IO, ::MIME"text/plain", φ::Hom) = print(io, φ.f, " as ", typeof(φ))
((φ::Hom{D, R})(x::D)::R) where {D, R} = φ.f(x)
convert(::Type{T}, f) where {T <: Hom} = T(f)
(φ::Hom{D, R} ∘ σ::Hom{R, W}) where {D, R, W} = Hom{D, W}(φ.f ∘ σ.f)
const sine = Hom{Number, Number}(sin)
const cosine = Hom{Number, Number}(cosine)

Then you can indeed have (sine ∘ cosine)::Hom{Number, Number}. We’ve embedded a variety of other types into the set Hom{D, R} that we’ve exhibited as a type.

2 Likes
22

If 1+"hi" is a type error, so is sin ∘ string

Yes, exactly!

Indeed, that is precisely what I’m looking for–function composition on concrete types.

This is very exciting! Would love to see methods automatically join the relevant Hom sets, as this would allow for strong typing of, say, the lt parameter in sort.

23

No, this doesn’t follow. sin ∘ string is a perfectly valid function: it applies string, then sin. It happens to be the case that the function will throw an error when called on any argument, but that’s allowed in Julia. The value "x" also throws an error when called on any argument: ("x")(...) is always a method error. That doesn’t mean it should be impossible to produce the value "x".

24

Another example of how functions are not first-class values: all composition is weakly typed. I’m sure this is for performance and simplicity reasons that are well-calibrated. But if we can choose, sure would be nice for function composition to be strongly typed, just like integer composition.

I’m probably too much on the FP side to understand why we would want to permit (“x”)(…).

25

There is no weak typing here. sin ∘ string means a function such that for all xs..., (sin ∘ string)(xs...) is the same as sin(string(xs...). That’s well-defined and meaningful.

We don’t want to permit ("x")(...). That throws an error. Similarly, we also don’t permit (sin ∘ string)(1), which also throws an error. But we permit "x", because there is no reason not to, and it might be useful for other purposes besides being called. Similarly, we permit sin ∘ string, because there is no reason not to, and it might be useful for other purposes besides being called.

26 
function ∘{A,B,C}(f::Tuple{typeof(f),B} --> C,
                  g::Tuple{typeof(g),A} --> B)
             --> ( A --> C)
    x->f(g(x))
end

Sorry should have clarified what I mean by compose.

27

Yes, this is understood. Indeed, aside from the types you want not actually existing, the current definition of ∘ satisfies this. sin ∘ string, and any function for that matter, can be considered to be composing Union{} --> Union{} with Union{} --> Union{}. So I don’t understand why it should be an error in any event.

28

Julia only gives “type errors” when you evaluate the code that exhibits the problem. The reason 1 + "hi" throws immediately is because when you evaluate that, it’s already a problem. When you evaluate sin ∘ string there’s no problem – the problem only occurs when you actually try to call that composite function on something. And the way Julia works, maybe it doesn’t – this is a perfectly valid if questionably useful program:

julia> ss = sin ∘ string
(::#55) (generic function with 1 method)

julia> Base.string(n::Int) = n

julia> ss(123)
-0.45990349068959124

You can’t generally know if a function composition is “well typed” when it occurs. You can only know that when it runs. We could potentially have a subset of behaviors which, if you follow them, allow compile-time checking that a problem doesn’t have any method errors, but that’s a project for some time in the future (post-1.0).

4 Likes
29

Glad to hear it’s on the radar for post-1.0. A natural candidate for such a subset seems to be ->. Would be great to see this as a value as fleshed out in this thread. I think this is what @fengyang.wang and @jameson referred to as an “arrow type” (as opposed to the Hughes arrow).