WIP: redesign closures, then generic functions

[JeffBezanson]

This is a very early preview of the likely future direction for how functions work. It's very much pre-alpha quality but does have a working REPL. This is now essentially done! I have one cool demo:

julia> function foo()
       a = rand(2000,2000);
       @time 2*a
       @time map(x->2x, a)
       end
foo (generic function with 1 method)

julia> foo();
  0.011471 seconds (2 allocations: 30.518 MB, 44.34% gc time)
  0.009771 seconds (2 allocations: 30.518 MB)

julia> foo();
  0.007800 seconds (2 allocations: 30.518 MB, 23.52% gc time)
  0.006837 seconds (2 allocations: 30.518 MB)

Ok, maybe two cool demos:

julia> function inner(a)
        x->a*x
       end
inner (generic function with 1 method)

julia> f = inner(6)
#2#g0(6)

julia> f(2)
12

julia> f.a
6

FastAnonymous.jl, you are in my sights and your days are numbered.

My full plan has three stages, the first of which is now almost complete:

1. Rewrite closures (inner functions) to new types that define call.
2. Deprecate the call function, and instead put method tables inside TypeName. Remove the Function concrete type. All generic functions use the same basic design as closures in stage 1.
3. Fix various problems and redesign parts of Base to exploit this change.

Some next steps:

• Improve typing of closure fields
• Remove some unnecessary Boxes
• Propagate static parameters to closure types
• jl_instantiate_staged is probably a bit buggy

Some problems to solve:

1. The situation with some kind of Callable type is now more urgent. I'd propose making Function an abstract type, and making anonymous functions subtypes of it by default. That will at least handle all the cases in Base where function arguments had ::Function, and will also handle "functors" that had nothing to subtype from before.
2. How to serialize closures? If all code is present on all nodes, then sending closures is actually way more efficient than ever, since you only need to send the (small) environment object. However we need to decide when to send the whole type definition as well.
3. Decide how to deal with inner functions with multiple definitions. Currently they work fine assuming (1) all definitions are in the same basic block, (2) the type signatures can be evaluated at the top level. These are reasonable restrictions, but we need to solidify them and add good error messages etc.
4. This uses way too many gensyms, and the generated names are horrible, as in the type of f above, #2#g0. There should be a nice standard name mangling, e.g. __hidden__.inner_1.
5. Figure out how to pass static parameters for --compile=all mode. This currently depends on the old implementation of closures.
6. Figure out how (if at all) to mitigate the additional excess code specialization. So far it's actually not too bad; the system image is maybe 10% bigger and the build takes a bit longer, but it's nothing horrible. However after stage 2 this will probably get worse.

[yuyichao]

julia> f.a
6

What's fieldtype(typeof(f), :a) ?

Edit: sorry, press Ctrl-Enter too early

[ScottPJones]

That looks very interesting - since in the first example, using map and the x->2x function was actually faster than scalar * array, would you want to in general rewrite scalar * array & array * scalar to use map?

[JeffBezanson]

What's fieldtype(typeof(f), :a) ?

Currently just Any, but that's the target of the first of my "next steps" listed above. For immutable bindings it's easy; we can just make the field type a type parameter and everything falls through automatically.

using map and the x->2x function was actually faster

I think that's mostly due to when GC happened to run. However (1) map would be faster if you used it to fuse loops (i.e. doing a single map instead of a sequence of elementwise functions), (2) I do want to use something like map in preference to "vectorized" functions (#8450).

[timholy]

FastAnonymous.jl, you are in my sights and your days are numbered.

FA is going to duck, dive, and dodge just to make it more sporting. Then happily roll over and join the party.

[JeffBezanson]

I'd like to get a head start on some syntax bikeshedding here. The call function and call overloading as we know it will go away (but the capabilities, and more, will remain). So we will need new syntax for specifying the type of the called function (what is now the first argument to call). The basic idea is obvious and uncontroversial. What is currently written as

call(::AddFun, x, y) = x + y

will become

(::AddFun)(x, y) = x + y

Of course, if you want to refer to the function and its fields in the body, you can also give it a name:

(f::AddFun)(x, y) = x + y

This means that plain old f(x, y) = x + y will be lowered to (::typeof(f))(x, y) = x + y.

Things get trickier when you add static parameters. Obviously we need to take the opportunity to solve #11310 at the same time. A simple translation of call{T}(::Type{Foo{T}}) = 0 would be

(::Type{Foo{T}}){T}() = 0

but that's a bit strange. Using my proposal #10146 (comment), we get

Foo{T}{T}() = 0

which is nicer, but strange in that the second T introduces the variable, and the first instance is a use of it. With the function keyword, a good solution would be

function {T,S} Foo{T}(x::Bar{S})
  ...
end

since then it's clear that the static parameters wrap the whole signature. However this doesn't seem to be usable with short-form definitions, which is unfortunate.

[JeffBezanson]

cc @one-more-minute @IainNZ @yuyichao @StefanKarpinski

[sjkelly]

What about something like:

function {T,S}(x::Bar{S})::Foo{T}
...
end

I dunno how this would be enforced. Regular function calls would be unchanged.
And with (hypothetical) return types they could be a combination of both:

function func{S}(x::Bar{S})::Foo{Int}
...
end

[tkelman]

Double curly parameters would never cease to confuse me. I'd always have to have the doc page that explains which does what open any time I read or write code that needs them. Maybe losing out on the short form convenience for parameterized call methods wouldn't be a huge loss and worth using syntax with more of a distinction.

[ScottPJones]

Slightly different syntax to set it off? your mention of "double curly" made me wonder if {{...}} could distinguish it better.
i.e. Foo{{T}}{T}() = 0 and

function {{T,S}} Foo{T}(x::Bar{S})
  ...
end

[JeffBezanson]

Switching to the "just try it and see what happens" approach, it turns out that

{T}f(x::T) = 0

and

{T}f{T}(x::T) = 0

parse just fine (to an implicit multiplication of {T} and f(x)) but give an error later. That means this syntax is fully available. We don't want to allow this implicit multiplication anyway. Minor issue is that it's space sensitive; {T} f(x) = 0 doesn't work.

[yuyichao]

{T} f(x) = 0 seems to be a parse error so it is also "available"?

[JeffBezanson]

Maybe, but it's recognized as two expressions, i.e.

julia> parse("{T} f(x) = 0", 1, greedy=false)
(:(Any[T]),4)

works.

[StefanKarpinski]

Do we need a single-line syntax for this? Couldn't the function keyword syntax be the only one with the full flexibility? That way you'd only be able to do parametric call overloading with the long form but that seems acceptable.

[JeffBezanson]

I agree it's acceptable, just slightly half-assed.

[StefanKarpinski]

Perhaps but this is turning into a bit of a syntax trainwreck. Don't get me wrong, I love the new design but I don't care for any of the syntax options proposed here. I would be happy if we could deobfuscate the dreaded parametric inner constructor business while we're at it, so I think that should be considered too.

[JeffBezanson]

As I already said, we should definitely fix #11310 at the same time. All of the options here would in fact fix the constructor syntax issue. Calling it a trainwreck isn't very productive. This is how the sausage is made.

[mweastwood]

I'm just following along at the periphery, but I have a suggestion that makes sense to me as a user and won't have people scrambling to find the manual every time they encounter two sets of curly braces.

The two sets of curly braces serve two different purposes. One is the tuple of type parameters belonging to the type. The other declares the type parameters. I was under the impression that {...} was eventually going to be reserved for tuples of types, so use of curly braces to declare type parameters seems a little inconsistent regardless of whether it comes before or after.

Instead, I think the following syntax is very intuitive and doesn't confuse the meaning of {...}, but it unfortunately requires another keyword (and is hugely breaking...).

function Foo{T}(bar::S)
where T <: AbstractBar, S
    ...
end

Foo{T}(bar::S) = ... where T <: AbstractBar, S

This short form syntax is analogous to the comprehension syntax where variables are declared after they are used ([foo(x) for x in y] vs Foo{T}(x) = ... where T <: AbstractBar)

[JeffBezanson]

That's not a bad idea at all. Though a bit more verbose, I definitely see the appeal over a salad of curly braces.

[JeffBezanson]

Also, as some might already know, when this form of polymorphism was first invented the feature was called "where clauses" (http:https://www.pmg.lcs.mit.edu/papers/where-clauses.pdf).

[quinnj]

I do like that suggestion, but I'd tweak the short-form to be

Foo{T}(bar::S) where T <: AbstractBar, S = ...

"explaining the type parameters" feels like it should be sooner after their usage.

[ScottPJones]

What about something like:

function Foo{T,S where T <: AbstractBar}(bar::S)
...
end
Foo{T,S where T <: AbstractBar}(bar::S) = ...

This has a few advantages: I think it could be compatible with the current form
(i.e., if there is no where clause, the syntax works exactly as now),
it keeps the declaration and parameterization together,
and the short and long forms show exactly the same pattern as now: function Foo{xxx} ; yyy ; end
means the same as Foo{xxx} = yyy

[lstagner]

Sorry if I am misunderstanding the problem but would it be possible to use a separator in the parameter declaration (curly bit after the function/constructor name) to differentiate function-like types and argument-like types. Everything before the separator would refer to the type of the function and everything after would refer to the types of the function's arguments.

Something like

function Foo{T <: AbstractBar; S}(bar::S)
...
end
Foo{T <: AbstractBar; S)(bar::S) = ...

with ; as the separator

[ScottPJones]

@lstagner I like your suggestion as well, it has the same advantages as my suggestion, and furthermore it eliminates having T twice, in declaraction & constraint.

[tkelman]

?

[JeffBezanson]

Sorry -- just accidentally pushed something I need in my local build (#12038 (comment)). Will be edited out.

[tkelman]

Ah right, that bizarre one. Carry on, just making sure this gets noted.

[RauliRuohonen]

Figure out how (if at all) to mitigate the additional excess code specialization. [...] However after stage 2 this will probably get worse.

Just as Any has ANY, add FUNCTION for Function. You might want to use e.g. optimize(f::FUNCTION) instead of optimize(f::Function) when f is relatively expensive to evaluate and the optimizer is some enormously complicated black box optimizer bending over backwards to minimize function evaluations.

[jgoldfar]

This is a great improvement in many ways (anonymous functions are fast!), but I'm hoping that c-callable closures is on the horizon; passing closures to C libraries for optimization etc. are a natural use-case (see JuliaOpt/NLopt.jl#7). Is there an issue open somewhere tracking progress on this? Is #13984 a way forward?

[JeffBezanson]

#1096

[glesica]

I'm not sure if this constitutes expected behavior (it wasn't clear to me how things ended up based on the discussion above), but it definitely appears to be a rather subtle change from 0.4 to 0.5 and I think it is related to this change.

The snippet below runs fine, and produces a vector of dictionaries on 0.4.3, but results in a stack overflow on 0.5:

typealias A Vector{Dict{Int, Float64}}
A(n::Int) = [Dict{Int, Float64}() for _ = 1:n]
a = A(3)
println(a)

There might be a simpler example, but this is what I came up with because it is similar to some code I actually have. A similar snippet works as expected (by me) on 0.4.3 but results in a segfault on 0.5:

typealias A Vector{Float64}
A(n::Int) = [Float64(1.0) for _ = 1:n]
a = A(3)
println(a)

It appears that the code defines a function called A in 0.4.3, but adds a method to the type A, which resolves to Vector{...}, on 0.5. If this is by design, that's fine, I just want to clarify that I understand what's going on and why and make sure that this is actually what is supposed to happen now in 0.5.

[JeffBezanson]

It actually does the same thing in both versions, which is add a method to the type. This overrides constructors for the Array type, so the results can be unpredictable. The result seems to have changed due to the implementation of the low-level Array constructors being rearranged slightly.

[papamarkou]

Although the following is a very contrived toy example, it works with v0.4 but not with v0.5; I am still trying to get used to the new syntax for closures - how can I recode the following so that it works on v0.5?

g{N<:Real}(y::Vector{N}) = (x::Vector{N} -> x+y)

[jgoldfar]

@scidom Isn't that #15068 (not that I know the answer to your question, but it looks like it will eventually work on v0.5)

[papamarkou]

Thanks @jgoldfar, I haven't noticed #15068, you are right, it is the same issue.

[aaronsheldon]

Stealing from Concurrent Clean, recognizing that a function is typed by both its domain and range we could differentiate the parameters for the input from the output by over using the mapping symbol "->" in the parameter list:

myfoofunction{P,Q,R,...->S,TU,...}(x::P, y::Q, z::R,...)::myfootype{S,T,U,...} = do stuff...

In rough syntax:

function name{input type parameters -> output type parameters}(argument list::argument types{input parameters})::outputtype{output parameters} = do stuff...

Of course we would also want to allow linking the parameters:

myotherfunction{T->T}(x::T)::T = do stuff...

But it seems it might be a bit late in the game to propose this syntax, and I don't know if that will catch all the use cases properly.

Also, could it be possible to parameterize the type "Function", so that it is Function{InType,OutType}? Yielding:

Function{In,Out}<:Function{In}<:Function

We could then have

foo(x::Int, y::Int)::Float = convert(Float, x+y)
f=foo

isa(f, Function{Tuple{Int,Int},Float}) == true

and for closures, with all the options:

g{T->S,U}(y::T)::Function{S,U} = (x::S -> y...)::U

reading in long form:

"g" is a function with input types parameterized by "T" and output types parameterized "S" and "U", that returns a function with input type parameterized by the "S" from "g" and output type parameterized by the "U" from "g". Where the return of "g" equals the mapping "x" of type "S" from "g" to an output of type "U" from "g".

Finally in the long run I would like to see function argument patterns, particularly with constants, handled by a mechanism a bit more transparent than the current Val{}() ::Type{Val{}} pairing. Currently a syntax like:

f(x::{Int64})=x+1

Throws a type error. So again is there a possibility of introducing the syntax

f(x::{0}) = 1
f(x::Int64) = x * f(x-1)

For detecting a specific constant? The meaning of "x::{a}" is "x" is exactly literal "a"; with anything other than a literal being forbidden. Of course this leads to interesting conundrums like:

f(x::{eval(:(some expression))}) = ...

This would allow f(x::{0}) = ... to become a fixed look up behind the scenes