later-stage macros?

[timholy]

Would it be possible to have parametric macros whose evaluation is deferred until compile time?

This is treading on old ground (staged functions, etc), but perhaps with a slightly different twist. It's a bit of a continuation of the ideas I pursued in Cartesian.jl, but it has the potential for cartesian iteration without any kind of performance penalty.

The point behind this is (hopefully) illustrated in this gist. The "user-written" part of the code begins at #### User-written code ####, everything else above that is library code.

Most of that code works fine as-is; it's only the last example, the arbitrary-dimension version of showelements, that requires a new language feature. If we had "parametric macros", e.g., @genloops{N}, that are not evaluated until compile-time, this might be achievable.

Note that writing arbitrary-dimensional functions may always have some challenges, depending on the task, but perhaps a relatively small number of macros (illustrated by examples like @tuple and @sub) might suffice for many tasks.

I deliberately picked ispeak as an example of something harder, which may encourage us to think broadly. But even this might be achieved fairly simply, something along the lines of

@genloops{N} i d->2:size(x, d)-1 begin
    atpeak = true
    @genloops{N} j d->-1:1 begin
        atpeak = atpeak & @sub{N} i x > @sub{N} i+j x
    end
    @sub{N} i y = atpeak
end

although this is not identical to the other one (in 2d it checks 9 neighbors, not 4, and does not short-circuit). Thinking a variety of algorithms through might give us a sense of which, and how many, macros would be needed to cover many tasks.

(Note: @sub{N} has to be smart enough to look for an expression in its first argument, i.e., only a bit smarter than @sub in the gist.)

[JeffBezanson]

To me this syntax starts to explore the outer boundaries of readability. If a small number of features (genloops, tuple, sub) cover most cases, that raises hope that we could do this with a bit of new syntax as in #1917, and some compiler optimizations.

[timholy]

#1917 seems like cleaner syntax. If it can be generated cost-free, I'm all in favor of that variant. I was just trying to get there with what I know, and this seemed like it might be a small-ish change.

To explore more whether that syntax really will do what we want, I'll ask a couple of questions over at that other issue.

[timholy]

@JeffBezanson, as you may have seen I've started finding "cleaner syntax" applications of this feature. And I suspect there will be more, I just haven't invested much effort into this yet.

Today I realized another---very different---potential application of this idea: efficient operations when passing functions as arguments (see here, #3426, #3893 for a recent discussion). Consider a sorting operation with a comparison function:

function sort(x, cmp::Function)
    # lots of code here
    if @call{cmp} a b   # equivalent to cmp(a,b), except it's inlined!
        # do more stuff
    ...
end

If I'm thinking about this correctly, the key point is that having a late-stage macro lets you "trivially" generate a different version of sort for each cmp function supplied. This might mean we could implement this feature without a deep re-thinking of the whole meaning of functions in Julia.

Thoughts? Obviously not a Julia 0.2 feature :-).

[kmsquire]

+1

Inlining/specializing on functions would be great--that's the largest bottleneck in the sort() routines right now (and I'm sure has many other uses).

[StefanKarpinski]

FWIW, although it's an awful API and clearly transient, you can, if you really need to sort with specialization, define a custom Ordering type that uses the function customisless something like this:

immutable CustomOrder <: Sort.Ordering end
Base.isless(a,b) = customisless(a,b)

Then you can do things like sort!(v, order=CustomOrder()) and sortperm(v, order=CustomOrder()). I'm hoping that we can get rid of any need for this entirely in the future, so I don't particularly want to document this, but it is an option.

[lindahua]

Whereas I see the value of a later-stage macro, specializing and inlining function argument might not be the most appropriate application. I hope that function arguments can be inlined/specialized by the compiler -- without the need of using a macro do do this. In other words, people can just write cmp(a, b) and this gets properly inlined, instead of having to write @call{cmp} a b.

[StefanKarpinski]

Yes, that's really much preferable.

[timholy]

@lindahua, that's a separate issue. Whether cmp(a, b) gets inlined when you write it out explicitly is up to our inlining facilities. Here I'm talking specifically about passing a function as an argument:

function outerfunction(x, func::Function)
    func(x)
end

outerfunction(randn(10), max)

The issue is the following: compilation in Julia is determined by the input types. As soon as you call outerfunction(randn(10), max) the types are known: x is a Vector{Float64} and func is a Function. Function is a concrete type, so it compiles one version of outerfunction for any func::Function. That means that func cannot be inlined in the compiled outerfunction code.

Now that I think it through carefully like this, for this proposal to work you'd still need to introduce a unique type signature for each distinct compiled function (i.e., Function might need to become a parametric type, e.g., Function{N} where N is an integer). So even if we had late-stage macros, fixing #3426 wouldn't come entirely for free, although it would make the last part---the actual inlining---trivial.

[kmsquire]

@StefanKarpinski, I was mainly referring to the idea that by profiling, most of the time in sorting is in the comparison functions, and that manually inlining speeds things up about 30% (I just checked). Which is not amazing, but nothing to sneeze at.

Either way, I'm looking forward to some way to inline things like comparison functions, whether by the compiler or some other method.

[lindahua]

@timholy I understand the complexities here. To clarify, when I talked about specializing & inlining function argument, I mean the compiler treat function argument specially -- that is, to specialize based on what function is passed in (or in other words, assign unique type signature for each distinct function).

[lindahua]

So basically, every time a new function is passed into a higher level function, the compilation needs to be triggered again.

[timholy]

@lindahua, I misread something you'd written earlier. My apologies.

Upon reflection, this case isn't as clearly-related to late-evaluating macros as I initially felt. Most of the work is elsewhere. So cartesian iteration remains the best application for late-evaluating macros (that I've thought of, anyway).

I'm back to pecking at this issue in part because, in #1917, I just don't even know what I is (can you get the strides out? a linear index? what are the incrementing rules to address neighbors?), and so I've gotten to the point where I can no longer contribute usefully. In contrast, here at least I can imagine handling most scenarios that I care about. Just not as prettily.

[RauliRuohonen]

Late-stage macros seem like an orthogonal feature to specializing specific arguments. Specialization could work like e.g.:

function specializing_sort(x, specialize cmp::Function)
    if cmp(a, b)
        # do more stuff
end

where 'specialize' (or some other term) means "force this to always be a compile-time constant" (= compile for every new cmp value and stow the functions away in e.g. a hash table). You can do a lot of fun stuff with that, e.g. PyPy uses it to generate JIT compilers from interpreters (just specialize on the source code argument to an interpreter, e.g. "regex_interpreter(specialize rex::String, data::String)" is a JITted regex matcher).

Late-stage macros also seem useful for implementing any custom optimizations one wants. One could e.g. implement aggressive constant folding by defining ispure(f :: Function) and using a late-stage macro to recursively evaluate all pure subexpressions. This combines well with argument value specialization, as there are more constants available for folding. Like that regex code you just got interactively from the user.

[quinnj]

Superseded by #7311?

[JeffBezanson]

Yes I think so.