Julia: Generalize `Base.Fix1` and `Base.Fix2`

[goretkin]

Fix1 and Fix2 are, as far as I can tell, intended to be used internally. I think these types can be extremely useful for some APIs and I think they should be generalized and given elevated status. In addition to being useful in the same places as Fix1 and Fix2 are used in Base, by binding _some_ of the arguments, it allows encoding some symbolic manipulation rules in terms of other operations by binding _all_ the arguments.

Here's a possible implementation:

using Base: tail
interleave(bind::Tuple{}, args::Tuple{}) = ()
interleave(bind::Tuple{}, args::Tuple) = error("more args than positions")
interleave(bind, args) = _interleave(first(bind), tail(bind), args)

# `nothing` indicates a position to be bound
_interleave(firstbind::Nothing, tailbind::Tuple, args::Tuple) = (
  first(args), interleave(tailbind, tail(args))...)

# allow escaping of e.g. `nothing`
_interleave(firstbind::Some{T}, tailbind::Tuple, args::Tuple) where T = (
  something(firstbind), interleave(tailbind, args)...)

_interleave(firstbind::T, tailbind::Tuple, args::Tuple) where T = (
  firstbind, interleave(tailbind, args)...)

struct Bind{F, A}
  f::F
  a::A
end

function (c::Bind)(args...)
  c.f(interleave(c.a, args)...)
end

# for backwards compatibility, and succinctness

const Fix1{F, X} =  Bind{F, Tuple{Some{X}, Nothing}}
const Fix2{F, X} =  Bind{F, Tuple{Nothing, Some{X}}}
Fix1(f, x) = Bind(f, (Some(x), nothing))
Fix2(f, x) = Bind(f, (nothing, Some(x)))

getx(f::Fix1) = something(f.a[1])
getx(f::Fix2) = something(f.a[2])

# should probably be a deprecated: 
getproperty(f::Fix1, s::Symbol) = s === :x ? getx(f) : getfield(f, s)
getproperty(f::Fix2, s::Symbol) = s === :x ? getx(f) : getfield(f, s)

e.g.

is3 = Bind(==, (3, nothing))
isnothing2 = Bind(===, (Some(nothing), nothing)) # demonstrate how to escape `nothing`

seems to generate efficient code:

julia> @code_llvm is3(4)

;  @ /Users/goretkin/projects/julia_scraps/curry2.jl:22 within `Bind'
define i8 @julia_Bind_19023({ { i64 } } addrspace(11)* nocapture nonnull readonly dereferenceable(8), i64) {
top:
; ┌ @ /Users/goretkin/projects/julia_scraps/curry2.jl:3 within `interleave'
; │┌ @ tuple.jl:96 within `first'
; ││┌ @ tuple.jl:24 within `getindex'
     %2 = getelementptr inbounds { { i64 } }, { { i64 } } addrspace(11)* %0, i64 0, i32 0, i32 0
; └└└
; ┌ @ promotion.jl:398 within `=='
   %3 = load i64, i64 addrspace(11)* %2, align 8
   %4 = icmp eq i64 %3, %1
   %5 = zext i1 %4 to i8
; └
  ret i

I made a gist trying to demonstrate the benefits I perceive of this proposal. The first example is about replacing Rational{A, B} with Bind{typeof(/), A, B}. This probably shouldn't actually be done, and it at least serves as an illustration:
https://gist.github.com/goretkin/0d86957dd3279ce9d55993467f872794#file-curry-jl-L47-L58

The second example is about deferring the evaluation of union(1:3, 5:7) and carrying a symbolic representation of it to allow more efficient operations downstream.
https://gist.github.com/goretkin/0d86957dd3279ce9d55993467f872794#file-curry-jl-L65-L79

I tried to see if this change would wreak havoc in Base, but I was not able to test it out: https://github.com/JuliaLang/julia/pull/36180

Related:
https://www.cplusplus.com/reference/functional/bind/
PR #36094 Document Fix1 and Fix2
https://github.com/c42f/Underscores.jl

[rapus95]

I'd primarily love it as a foundation for arbitrary partial evaluation.
E.g. f(a,b,c) = 2a + b^3 - c
Having a and b bound to constants (and f known to be pure) allows partial preevaluation of that function resulting in a single subtraction on application of the bound variant. In some sense that would be the most eager evaluation possible.
Given that, I'd use it the opposite way than you proposed it since you'd use it as a lazy evaluation object

[tkf]

I think it'd be better to have this as an external package. It helps to evolve the API. For example, the current implementation of Bind does not seem to handle keyword arguments. Polishing the best API for something like this would be very painful to do in Base.

[goretkin]

I think having a package is a great idea (I hope someone can help write the macro @bindbecause I had to special-case it to 2 arguments)

At the same time I think it's undesirable to have three types Fix1 and Fix2 and a more general option in an external package since the great power of these types is that you can dispatch on them. And Base already has convenience definitions like ==(3). But a package is probably a good step towards eradicating Fix1 and Fix2.

[tkf]

At the same time I think it's undesirable to have three types Fix1 and Fix2 and a more general option in an external package since the great power of these types is that you can dispatch on them.

I think that's a fair argument but workarounds exist. For example, you can export something like

const Fix2Like{F, X} = Union{Fix2{F, X}, Bind{F, Tuple{Nothing, Some{X}}}}

Also, if you start supporting more complex API like call chains like @rapus95 suggesting, it might be better idea to go with traits-based dispatch rather than doing everything in the method signature (e.g., functions like nargs(f), isbound(f, i), etc.).

By the way, I think https://github.com/Tokazama/ChainedFixes.jl is related to your use-case.

[goretkin]

I made a package here: https://github.com/goretkin/Curry.jl

@tkf thanks for pointing me to ChainedFixed.jl. Specifically what I want to avoid is needing to give a name like LessThanOrEqual, and spell it out in a more generalized way. I don't exactly understand the connection.

[tkf]

I thought NFix was close to Bind.

[andyferris]

Personally I think having Base provide generalizations of Fix1 and Fix2 is going to make it easier for the package ecosystem to interact with these mechanisms.

As a package author I really don’t want to support Base.Fix1 and Base.Fix2 and NFix and Bind and whatever else is out there. I feel basic manipulation of functions (like composition and currying) needs to be a Base feature for everyone to share. The Base.Bind thing in the PR (#36180) seems suitable.

[tkf]

There is no technical difference if it is in Base or not. On the other hand, an oversight like missing keyword argument support (for example) as pointed out above would be bad when Base has a firm commitment to the stability in the 1.x series. I think it is better to experiment with this outside Base at least for now.

As a package author I really don’t want to support Base.Fix1 and Base.Fix2 and NFix and Bind and whatever else is out there.

If there are multiple solutions it means that the API is not consolidated yet. I think it indicates that this is not the right time to put it in Base.

[andyferris]

Sure - I really wasn’t implying you shouldn’t experiment in a package first. :) And yes keyword arguments are important.

I’m only saying that the goal should be to _eventually_ have something in Base for the (non-technical) benefits of community cohesion. (In the extreme case it could even be the target of lowering, in certain circumstances).

[tkf]

Yeah, it'd be great if it is eventually integrated into Base or even in the language (e.g., lowering). I totally agree that manipulating function is a very important feature.

[goretkin]

On the other hand, an oversight like missing keyword argument support (for example) as pointed out above would be bad when Base has a firm commitment to the stability in the 1.x series.

I didn't understand the problem with this. The missing keyword argument support means that

1. the behavior is still a generalization of Fix1 and Fix2
2. keyword argument support can be added in the future without compromising backwards compatibility. Keyword arguments would just be an error now, which is fine, right?

In any case, see https://github.com/goretkin/Curry.jl/pull/1 for keyword argument support.

[tkf]

If you document that Bind{F, A} is the public API, it allows people to write

struct MyStruct
    b::Bind{typeof(f), Tuple{Nothing, Some{T}}}
end

with the expectation that the field b is concrete (although it depends on how you phrase it in the API).

However, adding keyword arguments like Bind{F, A, K} (where K <: NamedTuple) breaks this user code.

[andyferris]

Well, it doesn’t break that code, it just may make it slower, and we could use a type alias to a new type to work around that too.

[tkf]

Right. I meant to say that it breaks "the expectation that the field b is concrete."

[tkf]

Another API to consider is a vararg function. For example, Base has:

https://github.com/JuliaLang/julia/blob/35c1f87176fecab5a8e8077fb3a62275363a5aa5/base/abstractdict.jl#L350

It'd be nice to cover this in Bind which ATM fixes the arity when it is created.

Dispatching to the type returned from this function is very important because the closure is an associative operator. That's why in BangBang.jl mergewith!!(combine) returns a dedicated Function object that is later used for defining InitialValues.jl interface.

Another vararg function that makes sense to curry is Iterators.map(f) = (itrs...) -> Iterators.map(f, itrs...).

[tkf]

If we could reliably know that Fix2 is going to be returned

Isn't this already true? contains(needle) already documents that it returns Fix2:

https://github.com/JuliaLang/julia/blob/b07594dac02dc5a8e01c14444d63a27a131ebe7d/base/strings/util.jl#L130-L139

This issue is about generalizing Fix1 and Fix2. In terms of API guarantee of already existing Fix1 and Fix2, I think #36094 is more appropriate.

[mcabbott]

A much more modest extension of Fix1 would be this:

(f::Base.Fix1)(ys...) = f.f(f.x, ys...)

See #37196 for a use case. Would this create any obvious problems?