Is it possible in Julia?: Support a limited type inference version in order to decide whether a function is defined or not

General Usage
1

I think it would be a super helpful addition to the julia ecosystem if we could check whether some function is defined for certain arguments or not.

To be precise, I don’t refer to applicable or hasmethod. They only check whether the FIRST LAYER is defined. Introducing an additional wrapper layer wrapper(args...; kwargs...) = original(args...; kwargs) will let this approach fail very quickly. MethodErrors raised by internal functions won’t be recognized by applicable or hasmethod.

What I would really like to have is a method which I call isdef(f, args...) / isdef(f, ArgTypes...) (it should work on types), which checks whether the given function does not return an error for the given args.

This requires typeinference, but maybe, I am not sure on this, it does not require full-fledged typeinference and hence may be easier supported.

Core.Compiler.return_type is already a function which somehow supports this kind of type-inference, however it does not belong to the stable julia API and also has another goal: It tries to approximate the return type in an unpredictable manner.
For the wishes isdef feature it would be really nice to implement a similar method which [EDIT: I added some further remarks in the following list, as it was mentioned that this wish-list is not as well-defined as it could be, I hope it is slightly better now]

  1. approximate the result in a predictable and documentable manner
    (of course in best case can even infer the correct result all the time, but if it would overestimate, e.g. saying some method is defined while it is not, that is also very useful. But it should only overestimate in one direction, either always to restrictive or always too permissive, but not random once these once this)
  2. works on compile time (so that it can be used for dispatch to create specialized method implementations without performance drawback)
  3. can be made part of a stable API (as part of a package, or even as part of Julia itself, don’t mind, just stable)

My key question is whether something like this is possible to be implemented in Julia.

I tried a couple of approaches:

  • Cassette.jl seems quite tedious for this and it seems that with it you need to reimplement almost all of Julia’s standard functions to work on type level. Doesn’t look promising.
  • Just define the interface and let everyone implement the interface itself. It is also super tedious and prone to not be adopted because it is very time demanding to implement a type-inference version of your methods for every method.
  • Looking into Core.Compiler._return_type quickly fails as methods are no longer able to be lookup by IDE (e.g. inf_for_methodinstance or InferenceResult), but still my guess is that this is the most promising approach, I only don’t know how to go forward.

Any help is highly appreciated. To add: I also would be willing to spend my free time to implementing it if it is possible.

best,
Stephan

2

No this is impossible without explicitly support from the author if the method, e.g. define an type traits like interface to propagate this info. The method itself does not contain enough information.

The question is not well-defined and is in general undecidable even if you make up some more precise rules for it like no method error (it requires an exact type inference).

3 Likes
3

I think MethodAnalysis.jl might be getting close to being able to do this almost as a “linter,” i.e., not something that affects the actual compiled code at all but which you can use to enforce code-quality. The steps would be:

  • for each method in a package, infer it using its signature argument types (i.e., the widest set of types that it can be called with)
  • iterate through the ssavaluetypes and see if any might be Union{}.

You could add this to your package’s tests to make sure all calls succeed.

MethodAnalysis doesn’t do this yet, but it’s probably another 50 lines of code to add it. Want to take a stab at it?

https://github.com/timholy/MethodAnalysis.jl

4 Likes
4

thank you very much for the optimistic response

I never heard about ssavaluetypes, and trying to find a reference for them, I was surprised to find them official documented and hence officially supported by Julia itself at Julia ASTs · The Julia Language. I don’t understand anything yet, as I never used this part of the language, but I am surprised it also shows rettype a couple of times, something I thought would not be officially supported at all. Here at the ast documentation it seems to be and MethodAnalysis.jl seems to give a nice interface to get access to these details.

That is definitely a bit more work for me, because of these many new APIs I never worked with, but I am curious to try it out and see what all information Julia officially provides.
If an isdef gets possible with it, it would be the more motivating for me for sure :wink:

2 Likes
5

The issue still remains that

  1. the requirement is not well defined
  2. it cannot be robust

These are certainly not as much an issue for a linter. If you just want that it’s certainly doable. Just make sure your code behave exactly the same no matter what result you get from this.

That’s just a result that’s correlated with whether the code may throw an error though… It does not necessarily mean bad code and certainly doesn’t mean method missing…

6

@yuyichao

I gave some effort to try to specify my requirements. Please, if you can be more precise on what concretely is not well-defined (apart from me not knowing the possibilities which can lead to a solution), I would welcome it very much.

I think this one is not super decisive, as in Julia we can add robustness manually by overwriting the general method with more specialized implementations for those cases where it does not work. I also have no doubt that this could be safe to be used in production, as you should anyway always test your interfaces. And if turns out that for your precise interface the general fallback does not work, then you just define the manual fix.
Still the crucial point is addressed, that not everyone has to maintain two sets of functions - the function itself and the isdef-version of it which checks whether the function is defined for certain inputs.

To illustrate this a bit more, if I could have a Core.Compiler.return_type variant which just is stable and always overestimates in one direction (e.g. always more general type), that would already solve my problems. However, this part of the language is not stable to the best of my knowledge, and neither are the type-inference methods which underly it… That is actually the way I went until I posted this issue here. I first relied on Core.Compiler.return_type, which gives lovely results and very handy interface, however people convinced me that it is not good to rely on undocumented instable part of the language… Hence I am searching for an alternative now.

7

If you want to follow an example, the findcallers method is the closest: it scans your type-inferred code for calls to a particular function with particular argument types. Currently it only loads on Julia 1.6, because I’ve been using it to find sources of poorly-inferred calls in Julia’s own code base, but if you care about earlier Julia versions I’d be happy to help get it supported.

There are other AST docs at JuliaInterpreter, in case you want a gentle introduction.

1 Like
8

I realized I failed to respond to this and that I should shortcut any misunderstandings: while documented, anything in the devdocs section is not guaranteed to be backwards-compatible throughout the 1.x development cycle. The stability guarantee applies to “using Julia as a programming language” and once you start delving into how Julia is implemented internally, there are no such guarantees. This is necessary because most of the big improvements in Julia during the 1.x cycle have required changes to the internals, and while the developers go to great pains to ensure that this doesn’t cause changes in “surface” Julia, any packages that address Julia’s internals (like JuliaInterpreter/Debugger/Revise/Cthulhu/MethodAnalysis) are definitely subject to breakage. That’s just the price you pay for the privilege of being able to introspect into and modify the internals.

3 Likes
9

The point is that what you defined (whether some function can throw) has nothing to do with “whether a function is defined or not” so I was not treating it as your definition. I did use that or sth similar as examples of what can be defined and that’s what I said cannot be done.

That is exactly what I said you must do. In fact there cannot be a reasonable fallback for you to improve manually. You have to only rely on the manual information.

No you can’t possibly test this in any meaningful way. There is absolutely no guarantee what so ever about type inference give you the correct result here. Just because you did some test means nothing regarding if it works. The compiler is fully free to give you a different result the next time. Also even when not considering the absence of result stability from type inference, you still have to test all input cases to make sure it works under a single condition. That of itself is already strictly harder than defining the rules manually.

Well it will always over estimate now. Which also means that it’ll give you no information about errors.

10

this is exactly why I required isdef it to be “predictable”. If Core.Compiler.return_type is not predictable like that, still it might be possible to define something similar which is. As said, building a version of Core.Compiler.return_type for the specific needs of isdef was my envisioned most promising approach. You said that it would be impossible to do so, but seeing that Core.Compiler.return_type is almost there makes it hard for me to understand the reason why the remaining steps are impossible.

Core.Compiler.return_type is impressively powerful already in order to detect whether some function is defined in the sense of throwing an Error. I would use it straight away if not so many people strongly advise against using it (because of the instability and unreliability of the function, and because it is not officially supported by Julia, which is the reason I opened this discourse question to address it). Core.Compiler.return_type will infer Union{} in many cases where the method is either not defined (MethodError) or raises other inferrable Errors. Not always, but still impressively often this just works.
I would like to have something similar in power, just officially supported.

11

It’s impossible because that requires making no change of any kind to the compiler.

12

And it also depends on what is the “remaining steps” you are talking about.

If you mean to make the result accurate, then that’s theoretically impossible (it’s undecidable I believe).
If you mean to tell you “whether a function/method is defined or not”, then that’s simply because this is not a property that’s encoded in the code but a conceptual one.
If you mean to have predictable result, then that requires no change to the compiler as mentioned above.

13

just whatever would be needed to get from Core.Compiler._return_type to the desired isdef function.

I never thought to inflict such a requirement. My hope was that the code underlying Core.Compiler._return_type, or something similar, could be put into a separate package, without relying on too many dangerous julia internals, making it safe for use as isdef.

14

I think the point @yuyichao is making is that inference is not guaranteed to be correctprecise, and changes in how inference is implemented will doubtlessly change the results you get. Inference changes frequently, sometimes to become more accurateprecise for a subset of problems, sometimes to reduce the latency of compiling code. Sometimes these improvements in one domain have the tradeoff of introducing regressions in other domains; often, the devs know about these but decide that the tradeoff is overall advantageous.

What this means is that if you’re counting on inference to make important runtime decisions or to provide some other kind of guarantee, you need to be aware that you’re relying on it to do something that’s not really its core purpose. Inference is fundamentally there to improve the quality of generated code without changing the results it returns, and it doesn’t really pledge to deliver particular results in particular circumstances. In practice it’s pretty darn good, but @yuyichao is exactly right that you need to be aware that you should view inference as an optimization pass and not a truth-decider.

5 Likes
15

Correct → precise.

And the fundamental reason the trade offs exists is that obtaining a precise answer is an undecidable problem…

3 Likes
16

True, precise is the right word, not correct. Returning Real is correct but perhaps not as narrow as it could be if the object is actually a Float64. And of course often inference returns Any when it just can’t (or chooses not to) figure out what will happen.

3 Likes
17

okay, so inference is apparently out

what about doing something along the approach Zygote takes? Providing a sensible generic default with the possibility to overload your own adjoints. And with a set of basic adjoints. There are known limitations as array-mutation and try/catch, but at least the limitations are well known and it works 100% on the supported subset.

I guess the fact is that you cannot do such for isdef alone, what you really need for such a recursive approach is to have type-inference. But okay, if it makes things simpler, I also opt for full semi-hand-crafted type-inference.

So for some basic methods one could define the type-inference-version manually, and for general methods infer it by just using the submethods it uses.

Do you think this is a possible alternative?

18

I don’t think it’s out at all; just because it doesn’t return the tightest bound possible in all circumstances doesn’t mean it’s not an incredibly useful tool. You should be able to catch most of the class of bugs you describe in the OP with it, using the “linter” strategy I described. You just have to make sure you analyze the results of inference properly. Here’s an example:

julia> f(::Int) = 1
f (generic function with 1 method)

julia> applyf(container) = f(container[1])
applyf (generic function with 1 method)

julia> container = Any[100]
1-element Vector{Any}:
 100

julia> Base.return_types(applyf, (typeof(container),))
1-element Vector{Any}:
 Int64

OK, so Base.return_types tells us that it returns an Int, which is not wrong:

julia> applyf(container)
1

but we know we can also trigger a MethodError:

julia> applyf(Any[true])
ERROR: MethodError: no method matching f(::Bool)
Closest candidates are:
  f(::Int64) at REPL[1]:1
Stacktrace:
 [1] applyf(container::Vector{Any})
   @ Main ./REPL[2]:1
 [2] top-level scope
   @ REPL[7]:1

However, if you’re a bit more thorough about how you use inference, you can figure this out too:

julia> @code_typed applyf(container)
CodeInfo(
1 ─ %1 = Base.arrayref(true, container, 1)::Any
│   %2 = (isa)(%1, Int64)::Bool
└──      goto #3 if not %2
2 ─      goto #4
3 ─ %5 = Main.f(%1)::Core.Const(1, false)
└──      goto #4
4 ┄ %7 = φ (#2 => 1, #3 => %5)::Core.Const(1, false)
└──      return %7
) => Int64

See that statement marked %5? That’s looking for a call to f that it can’t figure out ahead of time. If you scan the method tables and discover that there isn’t another one other than the case for Int that it already used (split between %2 and %7, that #2 => 1 is hard-wiring the return value when it is an Int), then you know the call will fail.

3 Likes
19

As I said, using it for linting is totally fine. Definitely not in any way that affects execution.

20

I would like to have this feature for execution. Something like isdef could become the idiomatic way of defining traits in julia. No longer the need for forcing everyone to define IteratorSize if you actually only want to check whether length or size are defined. (okay, IteratorEltype might still be needed, but this is only because eltype defaults to Any).

I am defining a couple of traits where I am currently hesitating to force my users to define these extra traits-interfaces, because the intuition is big that this can be done better, more general, more flexible, with something like isdef.

Let me summarize what I understood why using something like Core.Compiler.return_type for such an approach is not feasible:

  • you apparently cannot separate the definition of Core.Compiler.return_type from Julia Core.Compiler, so wanting to make a stable and reliable return_type would necessarily need to fix the Julia Compiler itself. I don’t understand the details of this tight relationship, but it seems that this type-inference is not (yet) packagable.

So if we cannot use something among Core.Compiler.return_type, then the fallback is to define your own kind of type inference. As said, for me it is already quite good if I could have a generic fallback, so that not for every function the respective type-inference version need to be defined, but only for somehow leaf functions (or for some others for performance improvements).

I shortly looked into Zygote and, amazingly, they support all Julia versions, starting from 1.0. I am not sure about the details how they achieved that, but first glimps seems to indicate that their own IR package https://github.com/FluxML/IRTools.jl is the answer. Does someone know more about this and could help finding out whether type-inference can be defined with it?