Julep: Taking multiple dispatch,export,import,binary compilation seriously


#1

I want to formalize a julep for a design idea, I am asking the help of the community , please read and criticise
freely.

The problems it is addressing:

  1. Type piracy: It is too easy to break code in module M, even without directly evaluating code into it, by adding methods to Base functions or any other modules that module M depends upon.

exmaple:

import Base: +
+(a::Float64,B::Float64) = 0.0
sum(rand(5))
0.00
  1. Conflicting names: if both module M and module N export the same function name f , along with other useful stuff. Then usage of function f must be qualified even though there is a good chance that it is distinguished by its argument types(different modules usually handle different types)

Julia issues a warning in this case , even if there is no usage of f in the enclosing module.

  1. Binary compilation of Modules: due to the way multiple dispatch currently works , it is impossible to compile module M to a useful encapsulated binary since any subsequent module import or loading may change one or more of its functions, this is specially true for Base , as the current state of affairs encourages changes to it

As a consequence Julia is just eventually fast, in practice most of the time when developing is spent on recompiling old code. Revise solves this issue per a running session, I believe it can be solved globally so that Julia will be slow the first time , but just the first time … ever.

Background
Recall that there are two types of method calls, invoke which invokes a specific function
in a specific module for the specific argument types , and call which dispatches to the most appropriate method
to call based on the argument types.
Most of the time the compiler is able to infer the argument types in compile time , and the choice has zero cost since it is replaced by an invoke statement.
If it is not ,then the function call is more expensive but on par with function calls in Python and R.
To speed things up, once the appropriate method is compiled , it is cached and a pointer to it is saved in the method table for faster access.

This julep introduces a direction that can keep 99% of Base as it is, while solving the 3 issues mentioned above.

Design idea
I propose to handle multiple dispatch (and only multiple dispatch) differently.

A. remove the notion of “extending” functions in Base or any other Module

B. given a module M which defines a function f , and using module N which exports function f
will cause fusing both function signatures into f in M
calling M.f will dispatch either to f in M or N according to standard dispatch rules(most concrete signature)
calling N.f will invoke N.f

just having A and B would break the concept of interfaces, at least the more complex ones where part of the implementation of the interface is broken into several sub-functions.
Therefore:

Resolving dispatch can be defined recursively upwards in the AST (toward the caller) as follows:
if func is not an exported function it is resolved in its Module (according to B).
If it is an exported function it is resolved in its module ,and in its calling function scope … if the calling function have it imported( using the keyword using or trivially if they are in the same module ).

The most concrete implementation is chosen. If there is more then one implementation with the same concreteness then
the “closest” module in terms of AST distance is chosen.
if the are 2 equally close then and only then a warning
is issued that use of function must be qualified.

example: given the following AST ( capital letters denote the Module containing the function, prefix _ denotes it is an exported function).

(M) f -> (B) _sum -> imp -> _start

function start will resolve to a method in B , then in imp(trivially) , then in sum(trivially again since it is the same Module) then in M since sum is an exported function. the most concrete method will be used.

Criticism
All criticism is accepted , this thread is intended for discussion and exchange of opinions and ideas.

The best way would be to give an example that works in the current design which breaks in the proposed design
and possibly what would it take to make it work in the proposed design, I will give an example in the first comment for this thread

Binary compilation
An exported function will cache in the top most module that resolved it.

The proposed design guarantees that resolving a method call in module M is fixed if M and its imports does not change. This in turns allows binary caching (.o files) and potentially making the task of building an executable
or compiling a function to be reduced to just linking (given that all methods were previously compiled).

Of course dynamic code can invalidate a binary cache , so some Revise mechanism is still needed

Thats it for now , waiting for your input!!


"Meaning", type-piracy, and method merging
#2
baremodule N #just for verbosity
    using Base
    using StaticArrays
    f() = (SVector{3,Float64}(0,0,0),SVector{3,Float64}(1,1,1))
    g() = sum(f())
    export f
end

baremodule M
    using Base
    using N
    g() = sum(f())
end

in the example above M.g() resolves correctly , but it will fail in the proposed design
due to no method found for +(::SVector,::SVector)

The proposed design forces the programmer to declare what types/modules he intend to handle.

This works in both designs.


baremodule M
    using Base
    using N
    using StaticArrays
    
    g() = sum(f())
end

#3

It is not true that the ability to add new methods prevents static compilation. In fact, the current version of Julia already has static binary compilation (i.e. caching compiled code) in the form of the system image. Future versions of Julia will make it possible to do something similar for individual modules etc. We already have compiled code in memory, it’s “just” a matter of saving it.

Note also that other languages with similar extensible generic-function semantics have also supported static compilation, notably the Dylan language.

remove the notion of “extending” functions in Base or any other Module

What you are proposing (even if it is possible, and I don’t think you have thought through the implications of your “fusing function signatures” notion) is a completely different language.

For example, think about what happens when a module A defines a new type T and extends the iterator functions Base.start etcetera to work on T. Then module B calls module A to create a x = T() and then calls Base.sum(x), which calls Base.start(x) etcetera — this works because Base.start has been extended to work on T, regardless of where it is called from. How does Base.sum call A’s iterator methods if A.start and Base.start are entirely distinct?

Honestly, I don’t think this sort of “armchair language design” is very productive. If you think your proposal is implementable in Julia without being too disruptive, come up with at least a toy implementation and submit a PR for consideration.

(“Taking X seriously” threads are usually even less productive. We are already serious.)


#4

But this is not 100% conforms to the language itself, functions which are “baked” into the sysimg don’t see changes made to their underlying code….or secondary changes to their code due to adding methods to Base.
so currently this is useful only as a “final” static compilation.
It is not useful as binary cache for stuff you actually develop.

if module M is statically compiled into the sysimg, you cannot guarantee that

using M
using N

will behave the same if module M wasn’t and it would load regularly.

I have extensive experience with PackageCompiler as it became crucial to our work: I have a team of 6 engineers developing an AR Head Mounted Display for neurosurgery, and we do it with Julia, because it is easier for me to think and iterate in Julia, and because eventual performance is critical.
We started on Julia 0.5, my team would gladly switch to Rust or GO or anything that feels stable to them, but they still trust me that we can make it with Julia.

Our setup involves a couple of parallel processes in two or more computers … so restarts are frequent: Revise helps a lot of course, but still, frequent restarts are un-avoidable.
It takes over 2 minutes to load from a “cold” sysimg , 5-10 seconds when “hot”.

The solution we found (PR issued to PackageCompiler repo) was, we put the code we develop in modules outside the standard package dir. Start our application while logging calls to the compiler(borrowed from SnoopCompile), when the application finishes, build a sysimg with all the logged calls surrounded with try-catch clause.
Since the build script does not “see” our code, it fails to compile our code , so the end result is a sysimg
that is as “warm” as we can get without interfering with the development process.
This is a semi stable solution for development , since when packages update … everyone needs to build a new sysimg, and this process is lengthy and not hiccup-free.

I am afraid that true binary cache is just not possible the way things are now. I hope I am wrong…

I think I have thought through the implications, and found them no more complicated than the current state.
“fusing function signatures” is what extending function in Base does, it adds methods from different places into
one “multimethod”

And I don’t propose a different language, Base will be largely(or maybe completely even) unaffected.
The only difference for the end-user will be that instead of extending lets say start(x::MyType)
It would need to export it specifically in order for it to be visible in the scope it is used.

This is better explained in the first thread.

if module B does using A then
start is a qualified name in B.as well as sum (since Base is also used)
dispatch on the interface methods start done next resolves “upwards” in the AST in module B to the right method. the end result after resolving dispatch is the same behaviour you expect.

I am unfamiliar with this term, can you please be more specific as to what makes this design an “armchair”?

I was referencing “taking matrix transpose seriously” , figuring out it is a synonymous with: carefully analysing
and pondering the nuances, overlooked implications etc… anyway

Its on my list once we launch the product and once the twins grow a little bit.


#5

There’s often a bigger shortage of people to do the work than there are ideas. It takes quite a bit of time and energy to read, understand, evaluate, and respond to proposals. In an open source community, the best way to get folks to take your ideas seriously is through your ongoing contributions to the language and packages.

Armchair language design is an extension of the “armchair critic” idiom: https://www.usingenglish.com/reference/idioms/armchair+critic.html


#6

Oh quite insulting I would say…
I contribute whenever I can , StaticArrays, PackageCompiler,GLVisualise,Signals.

I am defenitley not sitting in my arm chair.

More like devoting long hours, on expense of my work and on the expense of my family.

And now this: as on my opinion it is crucial that the clever people behind language will at-least put their mind in this direction to grok it and discuss. Or we will hit an iceberg.

Instead I find that anything that is not a sheer praise is considered by the regulars as an “attack” and is taken quite personally… and gets responses like “armchair”


#7

As an outsider, I think it’s not meant to be an attack! In particular, everyone’s code contributions are always appreciated. But it’s more complicated for idea contributions — there is probably a tension between people wanting to take seriously and respond to and use proposals, and wanting to be as productive as possible. Idea proposals are simply not as productive in general — and, as others have said, the supply and demand of ideas and code is very skewed.

I think the “normal” result of an idea proposal is nothing, including no response. That you got a real, serious response already represents people taking you and your idea seriously, by investing time about thinking about it and writing a reply.

But part of the response is the (honest and realistic) point that idea proposals are not as useful to the community as fully coded pieces of work. Maybe “armchair” is a loaded term, but it’s not offensive.


#8

This sounds doable to me, at least in theory, if there was a local methods table per module instead of a single global methods table, but it sounds like it would take a lot of time to get right (I’m just speculating… someone who actually knows the details of this part of the language would have to comment).

But, this behavior change is hugely breaking (a lot more export statements would be required by most packages) and missed the v1.0 cutoff by a long shot, so it would have to wait for v2.0.


#9

Interesting points.

I have also been struggling to see how widespread binary compilation could be possible while keeping method overloading as flexible as it currently is. Its my biggest concern and uncertainty about Juia in the long term, although still really at an instinctual more than rational level.

The time and amount of restarts required, even using Revise, are the most painful thing about working in Julia (almost the only thing). I don’t understand the full potential for compiler optimisation, but it doesn’t seem like enough to resolve restart time without a cleaner binary cache.

Although I would really like to understand why not, if this is not the case!


#10

I have tremendous respect for the posters on this thread, but I have to say that I also find the responses overly dismissive.


#11

I’ve been reorganizing my strings code around a new principle, which is to have people pull in the names they want, via metaprogramming fun, instead of depending on what I also see as an overly simplistic model of export / import / using.

I just started this, so I haven’t fleshed out all the possibilities, but I think that one could achieve a lot of what @TsurHerman wants with no changes to the language.

If anybody is interested, please check out APITools (which I hope will get registered today :grinning: )


#12

My advice would be to look to the possibilities that the power of Julia’s metaprogramming can give you.
In the past, when I’ve had serious frustrations with the language, it’s frequently been able to come to the rescue (although with a serious amount of work, because my macro fu is not so great :wink:) and allow me to craft a nice alternative (such as adding Swift style interpolation and hex/Unicode constants, Python and C style formatting, and REPL style LaTeX / Emoji entities, in addition to HTML and Unicode entities, all to string literals).


#13

Assume you are actually open to criticism, every single issues I’ve brought up in Possibility of `local import` statements in future? still hold. Namely,

  1. The additional dispatch rule complexity can only work if it essentially makes it the same as the dispatch rule now, i.e. even though it may not see all the definitions on all methods, it has to see all the definitions on the methods it use.
  2. It’s solving none issue. In fact, it makes binary compilation completely useless. The toplevel module is basically always user code (or even if it is not what you mean by toplevel, having to resolve the function at this level is at least something you have to support and not something that compilation can possibly handle) so you’ll have to compile everything when the user calls it.

Just to be more concrete, I’ll copy my example over, with changes so that the implementation details are hidden,

# All modules are using all other modules that the module is aware of (either because it's the user's choise to use them together or because it's an implementation detail) so no new using/import can be added.
module IfaceDefAndUse
# This module cannot be aware of any other modules
export g, f
function g end
f(a, b) = g(a, b)
end

module WrapperOfIfaceUse
using IfaceDefAndUse
export k
k(a, b) = IfaceDefAndUse.f(a, b)
end

module IfaceImpl
using IfaceDefAndUse
export T, f
struct T end
IfaceDefAndUse.f(::T, ::T) = 1
end

module Factory
using IfaceImpl

export l
l() = IfaceImpl.T()
end

module User
using Factory
using WrapperOfIfaceUse

m() = WrapperOfIfaceUse.k(Factory.l(), Factory.l())
m()
end

Now in the call chain, User.m -> WrapperOfIfaceUse.k -> IfaceDefAndUse.f no one is aware of IfaceImpl since that is an implementation detail as far as the user, who put them together, is concerned.


#14

In my example, B isn’t calling A.start directly, it is calling Base.sum, and Base.sum (which knows nothing about A or B) is calling Base.start (which now needs to call A’s version if you want sum to be generic). As @yuyichao says, the only way to make this kind of thing work is if Base.sum “knows” about all start methods including A.start, which leads you back to essentially the current dispatch rules.

You are proposing vast changes in the language on the eve of Julia 1.0. There was just a long thread explaining why a closely related proposal is unworkable. We’ve told you that such changes are not needed to enable static compilation in the future, and that in fact static compilation has already been proved to work in other languages with similar generic-function semantics (and already happens in the Julia sysimg). You haven’t worked through even an example as simple as Base.sum — and despite decades of study on the semantics of generic functions in multiple-dispatch languages, you haven’t pointed to any work that models the semantics that you want. You begin the thread by suggesting that we don’t currently take dispatch “seriously.” Is it so surprising that we don’t want to spend a lot of time debating you, trying to convert your proposal into a concrete algorithm and arguing its weak points?

By “armchair design” I’m referring to the practice of suggesting far-reaching changes and asking others to work out the details and the implementation. This is rarely successful.


#15

This is what I’ve been saying since last winter already, that’s also why I created ForceImport.jl, my goal was to have a “local import”, which people thought was a completely useless and silly concept. It’s actually quite important of a concept for the language, but at this point I was able to resolve my issues with it by the @force macro.

The workflow with that macro actually helped me improve the precompile performance by 2x since I was extending so many methods, and was now able to start with a clean-slate method table for each method, hugely cutting down on the binary cache.

So as far as I am concerned, it is already possible to achieve the local import effect and its advantages without making any huge changes.


#16

And just to set it straight since this seems to be a major misconception. The binary compilation does NOT care at all about dispatch (thanks to Jameson)!

The only part of the compiler that is sensitive to dispatch is type inference (it’s not the only part dispatch happens but it’s the only part static dispatch, or dispatch in the compiler, happens). The mapping from inferred code all the way down to binary code is completely julia dispatch independent.

The inferred code is already included in the package precompilation and from the julia dispatch perspective the next step to binary code is trivial. The main if not the only reason binary compilation is not widely used for packages is the availability of linkers or in general getting the low level library generation and loading logic straight. It’s not actually trivial or easy to implement but it has absolutely nothing to do with dispatch.


#17

I think you are misrepresenting things. What was said was that this did not require a change in the language itself, nor that it required to have some extra support in Base. You got a lot of guidance on how to implement this and where to look for previous implementations of similar things. Taking the position that no one is listening to your great ideas is a bit unfair.


#18

And I do appreciate all the guidance and support that was given recently, but I was initially ridiculed for it, so that memory had a lasting effect on me.


#19

No one thinks that namespaces are useless and silly. And, of course, Julia already supported methods like Foo.+ that shadow (rather than extend) Base.+, and already supported importing them — that is what namespaces and other local scopes are all about. Your ForceImport package provides some syntactic sugar to import shadowed methods implicitly rather than explicitly, which no doubt is convenient in some cases, but does not change the dispatch or namespace semantics.

The problem comes if you want to extend (not just replace) Base.+, but only in a local context. That is what you initially said you wanted, and that is what the current thread tried to propose also. The difficulty arises because the whole point of extending (not replacing) a method is that one wants to extend the behavior of functions like Base.sum that call + outside the context of your local module. This is what is problematic, represents a complete upheaval of the language if it is even possible (without ending back at something equivalent to the current semantics), and is not provided by ForceImport.


#20

I asked about being able to do that when I first started with Julia (i.e. extending a function in a way that only affects the function within the current module).
Since then, I’ve learned how to make a local definition and manually make it use the types local to the module, and otherwise fall back to the external (usually Base) definition.
I do wish that there had been some syntactic sugar for doing that, so now I’m looking at having macros take care of it for me, as much as possible, but I do agree with a number of the other people here, that there doesn’t need to be any real changes to the current dispatching model achieve that.