Working on a pattern for interface-based dispatch that uses code-generation. Is this efficient?

#1

I’m not a super fan of inheritance-based polymorphism. I tend to like interface-based polymorphism like Go’s interfaces and Haskell’s type classes, et al.

I realize retrofitting these features in Julia is thought to be problematic because Julia’s dispatch resolver goes by specificity and it’s not clear how type classes could be seen as more or less specific than other abstract types. Anyway, I’ve been playing with Holy traits as a poor-man’s alternative, and I thought I’d try to generate some trait code based on interfaces, so I just need to do the (presumably) expensive method checks the first time it’s run with a given type.

struct HasPlus end
struct NoPlus end

@generated HasPlus(T) =
    hasmethod((+), (T,)) ? :(HasPlus()) : :(NoPlus())

This seems to work properly, but I’m not sure if there is a penalty for doing this. I’m paranoid because of this blog post, which contains these words:

Generated (aka staged) functions cannot be statically compiled. These functions are equivalent to calling eval on a new anonymous function computed as a function of the input types (a JIT-parsed lambda, if you will), and optionally memoizing the result. Therefore, it is possible to statically compile the memoization cache. This makes them, in this regard, superior to an unadorned eval call. But in the general case, generated functions are black boxes to the compiler and thus cannot be analyzed statically.

The words “cannot be statically analyzed” are what’s troubling me here. My assumption is that once the method is generated, it goes into dispatch tables in the normal way and the compiler handles things efficiently, but I’m not totally sure how all that works.

The other thing that bugs me about this solution for interface dispatches is that, as the blog post indicates, it can’t be used with AOT compilation.

The Julia compiler has enough type information that calls to hasmethod could theoretically be resolved at compile time an things like dead branch elimination could be applied, but I don’t know enough about Julia to know if this actually happens. Compile-time hasmethod would be really helpful for implementing interface polymorphism on top of Holy traits.

#2

hasmethod can not really be resolved at compile time as methods can be added to a function at any time, in particular after your code including hasmethod was compiled.

2 Likes
#3

x-ref to a recent thread: Eval cannot be used in a generated function. TL;DR: you probably shouldn’t use hasmethod (or other functions depending on global state) in a generated function.

4 Likes
#4

Hm. It seems like this should be possible with static analysis before anything is actually compiled, though I realize that this case in particular is circular… since I’m defining dispatches based on the results of hasmethod… hm…

#5

Dangit. Back to the drawing board. Thanks for the link.

#6

But you’re right in that hasmethod should in principle be inferable, Jameson shares that opinion: https://github.com/mauro3/SimpleTraits.jl/issues/40#issuecomment-293633610

2 Likes
#7

Looking more at this, I see that applicable is a built-in and it’s apparently a tfunc in Julia 1.1, at least.

Does that mean it’s now efficient? I can just do this with a simple test?

(I have no idea what tfuncs are, but my impression is that they are functions for which only type information is needed to calculate the result)

#8

I don’t think so. This is how an inferred check looks like:

julia> hh(a) = isimmutable(a) ? 1 : 2.0
hh (generic function with 1 method)

julia> @code_warntype hh(1)
Body::Int64
1 ─     return 1

julia> @code_warntype hh(:(1+1))
Body::Float64
1 ─     goto #3 if not false
2 ─     nothing
3 ┄     return 2.0

this is applicable:

julia> ff(fn) = applicable(fn, 1) ? 1 : 2.0
ff (generic function with 1 method)

julia> @code_warntype ff(sin)
Body::Union{Float64, Int64}
1 ─ %1 = (Main.applicable)(fn, 1)::Bool
└──      goto #3 if not %1
2 ─      return 1
3 ─      return 2.0

so it is not inferred.

2 Likes