Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

WIP: redesign closures, then generic functions #13412

Merged
merged 46 commits into from
Jan 29, 2016
Merged

Conversation

JeffBezanson
Copy link
Member

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
Copy link
Contributor

yuyichao commented Oct 1, 2015

julia> f.a
6

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

Edit: sorry, press Ctrl-Enter too early

@ScottPJones
Copy link
Contributor

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
Copy link
Member Author

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
Copy link
Member

timholy commented Oct 1, 2015

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 JeffBezanson mentioned this pull request Oct 3, 2015
@JeffBezanson
Copy link
Member Author

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
Copy link
Member Author

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

@sjkelly
Copy link
Contributor

sjkelly commented Oct 28, 2015

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
Copy link
Contributor

tkelman commented Oct 29, 2015

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
Copy link
Contributor

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
Copy link
Member Author

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
Copy link
Contributor

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

@JeffBezanson
Copy link
Member Author

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

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

works.

@StefanKarpinski
Copy link
Member

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
Copy link
Member Author

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

@StefanKarpinski
Copy link
Member

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
Copy link
Member Author

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
Copy link
Contributor

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
Copy link
Member Author

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
Copy link
Member Author

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

@quinnj
Copy link
Member

quinnj commented Oct 29, 2015

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

@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.

@@ -1,6 +1,6 @@
LLVM_VER = 3.3
LLVM_LIB_SUFFIX =
PCRE_VER = 10.20
PCRE_VER = 10.10
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

@RauliRuohonen
Copy link

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
Copy link
Contributor

jgoldfar commented Mar 8, 2016

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 jump-dev/NLopt.jl#7). Is there an issue open somewhere tracking progress on this? Is #13984 a way forward?

@JeffBezanson
Copy link
Member Author

#1096

@glesica
Copy link

glesica commented Mar 26, 2016

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
Copy link
Member Author

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
Copy link
Contributor

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
Copy link
Contributor

@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
Copy link
Contributor

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

@tlnagy tlnagy mentioned this pull request Apr 29, 2016
@JeffBezanson JeffBezanson mentioned this pull request Jun 24, 2016
65 tasks
@aaronsheldon
Copy link

aaronsheldon commented Aug 8, 2016

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

houtanb added a commit to houtanb/dynare that referenced this pull request Jul 27, 2017
…d in julia v0.5

See: JuliaLang/julia#13412

Can possibly improve this by storing V as an Expression instead of a String

NB: To create the sparse matrix, V must be a single expression containing an array, hence :([expr; expr; …]). Otherwise, the previous way, storing an array of expressions: [:(expr); :(expr); …] required that the variables endo, exo, and param be defined in the space where the function was going to be called, which was less than ideal. If I can figure out a way to pass the value to the function, then this would be ideal.

NB: Also that the solution outlined here: https://groups.google.com/forum/#!topic/julia-users/87_BMRY7Du4 does not work when ex is an array of expressions: [:(expr); :(expr); …]
houtanb added a commit to houtanb/dynare that referenced this pull request Sep 27, 2017
…d in julia v0.5

See: JuliaLang/julia#13412

Can possibly improve this by storing V as an Expression instead of a String

NB: To create the sparse matrix, V must be a single expression containing an array, hence :([expr; expr; …]). Otherwise, the previous way, storing an array of expressions: [:(expr); :(expr); …] required that the variables endo, exo, and param be defined in the space where the function was going to be called, which was less than ideal. If I can figure out a way to pass the value to the function, then this would be ideal.

NB: Also that the solution outlined here: https://groups.google.com/forum/#!topic/julia-users/87_BMRY7Du4 does not work when ex is an array of expressions: [:(expr); :(expr); …]
houtanb added a commit to houtanb/dynare that referenced this pull request Sep 28, 2017
…d in julia v0.5

See: JuliaLang/julia#13412

Can possibly improve this by storing V as an Expression instead of a String

NB: To create the sparse matrix, V must be a single expression containing an array, hence :([expr; expr; …]). Otherwise, the previous way, storing an array of expressions: [:(expr); :(expr); …] required that the variables endo, exo, and param be defined in the space where the function was going to be called, which was less than ideal. If I can figure out a way to pass the value to the function, then this would be ideal.

NB: Also that the solution outlined here: https://groups.google.com/forum/#!topic/julia-users/87_BMRY7Du4 does not work when ex is an array of expressions: [:(expr); :(expr); …]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.