Output type from input function handle output type?

General Usage
1

I have a recursive function that takes in a function handle, and eventually calls that function. It’s causing some allocations because the compiler can’t work out the output type of my recursive function. Is there a way to give the compiler a hint that the output type of the recursive function is the same of the output type of the function being passed in. For example, if I have a function declaration function recursivefunc(myfunchandle)::outputtype, can I somehow define outputtype using myfunchandle?

EDIT: Is there something I can do with parameterization? Something along the lines of:

function recursivefunc(myfunchandle::(Tuple{Any, Any})::T)::T where T
...
end
2

you can do this at call site

function f()
    a = recur_f() :: outputtyle
    ...
end
3

Thanks. Unfortunately this doesn’t work. Because the function is recursive, you’re only annotating the first call, and not all the following ones, so the output type isn’t passed on.

4

Is there something I can do with parameterization? Something along the lines of:

function recursivefunc(myfunchandle::(Tuple{Any, Any})::T)::T where T
...
end
5

I thought you have instability in a function you use this function.

if you want stability inside recursive function itself, well, tough life, you can’t unless you make it stable

or just don’t use a recursive function

6

Can’t you do likewise with the recursive calls inside your recursive function?

7

Sorry, not sure what you mean by stability/instability. Can you explain? If I understand it correctly I believe I want to make the output type stable by giving the compiler a hint to look at the function handle being passed in. Theoretically that seems possible to me if the output of the function I’m passing in is also type stable.

8

The return type should be known before calling the function, which might not be possible if you are planning to use it in a generic way.

9

Type stability refers to the property of a function to be type-inferable, i.e., the return type does not depend on the values being passed, but on the types. It is mentioned in the performance tips. Sorry, I jumped too early to answer this.

You’re spot on, you want to give the compiler a hint, so it can propagate the type information to the functions being called, including itself (the recursive call). If the recursive function is not type stable, it does not matter that the function being passed is type stable, as the compiler might not be able to deduce which methods of the function being passed are going to be called, because of the type stability in the recursive function.

1 Like
10

I’m hoping to use my recursive function for any myfunchandle, which can return any kind of output. How do you see it working?

11

Do you have MWE? It would be easier to answer the question about the specific implementation rather than in a general case (which might not be even possible).

12

Note that annotations of output types only convert the output to the desired type, whenever possible, they do not provide further information for the compiler to improve the function itself. They are useful to prevent a type instability from propagating. That can help sometimes, but won’t solve the problem of dynamic dispatch in your case, I think.

For example:

julia> function s(x)
           s = 0.0
           for el in x
               s += f(el)    
           end
           return s
       end
s (generic function with 1 method)

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

julia> x = Real[1,2.0,3.f0,4,5];

julia> @btime s($x)
  48.732 ns (4 allocations: 64 bytes)
15.0
1 Like
13

I see. Here’s the recursive function:

function valuedispatch(::Val{lower}, ::Val{upper}, fun, val) where {lower, upper}
    if lower >= upper
        return fun(Val(upper))
    end
    midpoint::Int = lower + div(upper - lower, 2)
    if val <= midpoint
        return valuedispatch(Val(lower), Val(midpoint), fun, val)
    else
        return valuedispatch(Val(midpoint+1), Val(upper), fun, val)
    end
end

But actually, I no longer think this approach will be any better than generating a single (non-recursive) function, using the approach here.

14

Thanks. I think in the situation I’m trying to improve, I’m not using dynamic dispatch. Rather, there is some type instability that is causing allocations. I’m not entirely sure. But as I say, thinking about it more, I doubt I’ll be able to do better (in terms of simplicity) than the solution proposed here.

2 Likes