General partial application in Base?

We already have Base.Fix1 and Base.Fix2 for partial function application. It seems that it would be nice and probably often useful to define a similar facility for the general case, available upon request. Is this something that would be considered for inclusion in Base?

I mocked up a quick prototype for myself (see the end of the post). This creates efficient code for the 1 or 2 arguments fixed case at least:

   julia> f = bind(+, (Val(1), Val(2)), 1, 2)
  (::Main.Bindings.Bind{1,Main.Bindings.Bind{1,typeof(+),Int64},Int64}) (generic function with 1 method)

  julia> @code_llvm f(3, 4)

  ;  @ /Users/mcbane1/Desktop/Bindings.jl:15 within `Bind'
  define i64 @julia_Bind_15981({ { i64 }, i64 } addrspace(11)* nocapture nonnull readonly dereferenceable(16), i64, i64) {
  top:
  ; ┌ @ Base.jl:20 within `getproperty'
     %3 = getelementptr inbounds { { i64 }, i64 }, { { i64 }, i64 } addrspace(11)* %0, i64 0, i32 1
  ; └
  ;  @ /Users/mcbane1/Desktop/Bindings.jl:15 within `Bind' @ /Users/mcbane1/Desktop/Bindings.jl:15
  ; ┌ @ Base.jl:20 within `getproperty'
     %4 = getelementptr inbounds { { i64 }, i64 }, { { i64 }, i64 } addrspace(11)* %0, i64 0, i32 0, i32 0
  ; └
  ; ┌ @ operators.jl:529 within `+' @ int.jl:53
     %5 = load i64, i64 addrspace(11)* %4, align 8
     %6 = load i64, i64 addrspace(11)* %3, align 8
     %7 = add i64 %2, %1
     %8 = add i64 %7, %5
  ; │ @ operators.jl:529 within `+'
  ; │┌ @ operators.jl:516 within `afoldl'
  ; ││┌ @ int.jl:53 within `+'
       %9 = add i64 %8, %6
  ; └└└
  ;  @ /Users/mcbane1/Desktop/Bindings.jl:15 within `Bind'
    ret i64 %9
  }

And I have included the feature that an argument may be bound to a Val in the case that it is known at compile-time; this results in the desired optimization as well:

julia> f = bind(+, (Val(1), Val(2)), Val(1), Val(2))
(::Main.Bindings.Bind{1,Main.Bindings.Bind{1,typeof(+),Val{1}},Val{2}}) (generic function with 1 method)

julia> f(3, 4)
10

julia> @code_llvm f(3, 4)

;  @ /Users/mcbane1/Desktop/Bindings.jl:16 within `Bind'
define i64 @julia_Bind_15994(i64, i64) {
top:
;  @ /Users/mcbane1/Desktop/Bindings.jl:16 within `Bind' @ /Users/mcbane1/Desktop/Bindings.jl:16
; ┌ @ operators.jl:529 within `+' @ int.jl:53
   %2 = add i64 %0, 3
; │ @ operators.jl:529 within `+'
; │┌ @ operators.jl:516 within `afoldl'
; ││┌ @ int.jl:53 within `+'
     %3 = add i64 %2, %1
; └└└
;  @ /Users/mcbane1/Desktop/Bindings.jl:16 within `Bind'
  ret i64 %3
}

It seems to me that for as few lines of code as are needed to implement this feature there is no reason it should not be included. Below is the full implementation.

    module Bindings                                                                  
                                                                                     
    struct Bind{N, F, T} <: Function                                                 
        f::F                                                                         
        x::T                                                                         
                                                                                     
        function Bind{N}(f::Function, x) where N                                     
            if !(N isa Int)                                                          
                throw(TypeError(:Bind, "Bind{N}(f, x)", Int, typeof(N)))             
            end                                                                      
            new{N, typeof(f), typeof(x)}(f, x)                                       
        end                                                                          
    end                                                                              
                                                                                     
    (b::Bind{N})(xs...) where N = b.f(arg_list_(b.x, xs, Val(N))...)                 
    (b::Bind{N, F, Val{X}})(xs...) where {N, F, X} = b.f(arg_list_(X, xs, Val(N))...)
                                                                                     
    function arg_list_(x, xs::Tuple, ::Val{N}) where N                               
        if N == 1                                                                    
            (x, xs...)                                                               
        else                                                                         
            (xs[1], arg_list_(x, Base.tail(xs), Val(N-1))...)                        
        end                                                                          
    end                                                                              
                                                                                     
    bind(f::Function, ::Val{N}, x) where N = Bind{N}(f, x)                           
                                                                                     
    function bind(f::Function, t::Tuple{Vararg{Val}}, xs...)                         
        if length(t) != length(xs)                                                   
            throw(ArgumentError("In bind: specified $(length(xs)) arguments to bind but $(length(t)) binding indices"))
        end                                                                          
                                                                                     
        # Early return for the trivial case.                                         
        if length(t) == 1                                                            
            return bind(f, t[1], xs[1])                                              
        end                                                                          
                                                                                     
        if !issorted(unwrap_val_.(t))                                                
            throw(ArgumentError("In bind: binding indices are required to be specified in ascending order"))
        elseif !allunique(t)                                                         
            throw(ArgumentError("In bind: binding indices must be unique"))          
        end                                                                          
                                                                                     
        # Bind the first value.                                                      
        g = bind(f, t[1], xs[1])                                                     
        # Reduce the index of each trailing parameter by 1                           
        Ns = subtract_one_.(Base.tail(t))                                            
        bind(g, Ns, Base.tail(xs)...)                                                
    end                                                                              
                                                                                     
    Base.@pure unwrap_val_(::Val{X}) where X = X                                     
    subtract_one_(::Val{X}) where X = Val(X-1)                                       
                                                                                     
    end # module

What do you see as the benefit over general anonymous functions? I am not sure that I see a benefit to:

f = bind(+, (Val(1), Val(2)), 1, 2)

over the existing (and shorter):

g = (x...) -> +(1, 2, x...)
3 Likes

If you’ve not seen it yet, you may find this proposal compelling as it’s a quick and convenient way to create these anonymous functions:

https://github.com/JuliaLang/julia/pull/24990

2 Likes

Hmm, yes, I suppose I may have gotten a little bit code blind. I’d still rather write Fix1(f, x) than (ys...) -> f(x, ys...) though, so there’s that. But my syntax isn’t any better.

The only area where I’d actually use this after thinking about it some more is in distributed code where I can’t send an ordinary anonymous function since it’s not defined on the receiving process.

@mbauman I have seen the underscore proposal and I can’t wait for that to eventually land!

1 Like

I think there’s value in cases where the positions aren’t known ahead of time. We have a similar case in Surrogates.jl where we need to fix arbitrary arguments.

1 Like

Necropost!! :wink:

That’s an interesting application, I never thought of it. I use the NamedTuple constructor for similar reasons, to programmatically manipulate field names, types, and values.

These are some additional benefits I see to using a partial application type over constructing on-the-fly lambdas:

Benefits:

  1. Every place in your code that you write a lambda, it causes a new function to be compiled. For example, map(Fix2(^, 2), arr) is preferable to map(x->x^2, arr) because the Fix2{typeof(^), Int64} type has undoubtedly been used elsewhere in the codebase and has been compiled already. It’s wasteful to compile lots of code that does exactly the same thing over and over and over and over and over.
  2. Frequently, this use of a lambda to satisfy partial application will cause a variable to be captured from its environment. (Take map(k->o[k], ks) for example; o is a capture.) As discussed here, if you’re not careful to avoid reassigning the identifier of the captured variable at its parent scope, this can result in substantial performance loss and potentially type instability. The act of passing the capture as an argument to a partial application constructor, e.g. map(Fix1(getindex, o), ks), provides a function barrier that prevents such behavior.
  3. A type dedicated to partial application allows type-specialization. An obvious use is for Base.show, but InverseFunctions.jl provides an interesting use case too (here’s an example). I can also imagine a world in which autocomplete would automatically show the argument names and types as they have been passed through the partial applicator.

Then, if PR#24990 is accepted to use _ underscores for partial application, all of these problems would be solved in a very ergonomic way. The example from #1 could be written map(_^2, arr), and the example from #2 would be map(o[_], ks).

Very, very nice.

I’ve also made a generalized partial application type which the syntax could lower to, which I describe here. In Julia 1.9, we will be getting a currying filter(f::Function) function (which uses Base.Fix1), but no comparable map(f::Function) (which would need a more general partial applicator, which my code satisfies with a FixFirst type).

What has prevented PR#24990 from being accepted has been a desire to get more than just one function call out of the syntax—to define a lambda instead of a partial applicator, so that e.g. you could write filter(_%3==0, arr). At the parser level, this is generally impossible to get right, and moreover, yet another way to write a lambda isn’t all that interesting.

However, as suggested here, a function composition fallback could satisfy this desire. I’ve also explored this idea, and it works very well. (although I don’t have the option to change the fallback behavior so I used dispatch.) Of course, such a fallback would require a generalized partial applicator type.

As I’ve stated at the bottom of this comment, I believe having a general partial applicator type and PR#24990 as syntax sugar to construct it would be part of a more perfect Julia.

1 Like