Structural lambdas for generic code and delayed evaluation
2021-07-28, 12:50–13:00 (UTC), Purple

We describe an experimental package that reifies lambda functions as a Lambda(args, body) and function calls as Call(function, args), giving a new way to "quote" expressions. It generalizes types like Base.Fix2, Base.Generators, Iterators.Filter and possibly many others. It might be well-suited for the recurring pattern of deferred computation in Julia code.


Pervasive and performant multiple dispatch in Julia has led to the development of functions that convey generic meaning. Deciding on a name and settling on the meaning of these generic functions is challenging work, but it is essential for generic programming.

Functions can be used to direct dispatch. e.g.

reduce(vcat, [[1,2,3], [4,5], [6,7,8,9]])

There is a fallback method of reduce that works for any binary operation, not just vcat. However, there is also a method specific to vcat that preallocates the result. Both the fallback and the specialization produce the same result, but the specialization is likely to perform better since it is inexpensive to calculate the size of the result.

Consider e.g. Base.filter and Base.Iterators.filter. The second simply constructs a Base.Iterators.Filter, which is in essence nothing more than a lazy representation of Base.filter(f, itr). We developed an experimental package FixArgs.jl to represent this:

julia> @xquote filter(iseven, $(1:5))
Call(Some(filter), FrankenTuple((Some(iseven), Some(1:5)), NamedTuple()))

Suppose we want to define eltype, the same way it is defined for Base.Iterators.Filter. We can define an eltype method for Call for the specific parameter filter. FixArgs.jl defines a macro to help (but the ergonomics should still be improved):

julia> Base.eltype(filt::(@xquoteT filter(::F, ::I))) where {F, I} = eltype(something(filt.args[2]))

julia> eltype(@xquote filter(iseven, $(1:5)))
Int64

FixArgs.jl began as a generalization of Base.Fix1 and Base.Fix2, but identifies a common pattern that could systematically replace many existing types and methods. e.g. Broadcasting relies on types to represent lazy function calls, and materialize to perform the computation (with e.g. dot fusion). Base.Generator and collect are analogous.

Instead of generating a new name for a type, and attaching meaning to it, one can meaningfully compose a name from existing meaningful names. One straightforward example is to define Rational{T} as

julia> (@xquoteT ::T / ::T) where T
FixArgs.Call{Some{typeof(/)}, FrankenTuples.FrankenTuple{Tuple{Some{T}, Some{T}}, (), Tuple{}}} where T

Note that Rational{Int} and (@xquoteT ::Int / ::Int) have identical memory layouts!
(Also, occasionally, there is a need for a Rational-like type that does not constrain the numerator and denominator to have the same type. The type above would fit the bill).

In this case, Rational is in Base, but more generally packages have to depend on a common package (usually called *Base.jl) that defines types. If it is possible to define new types terms of existing types, then in a sense the types are structural and not nominal. This may reduces the need for these common packages and enable better package interoperability.

As another example, the type Base.Generator(f, itr) could be identical to @xquote map(f, itr) (though not exactly since the meaning of map and collect are currently conflated (https://github.com/JuliaLang/julia/issues/39628)

There are many other examples in the ecosystem, such as in LazySets.jl, LazyArrays.jl, MappedArrays.jl, StructArrays.jl, ... where types are defined to essentially represent lazy function calls ad-hoc. They each have a version of "materialize". Note that in most cases, these cannot be replaced directly since Call cannot e.g. subtype AbstractArray and AbstractSet.

Base.Fix1, etc. is useful, even though one can already define a lambda function with the same behavior, because it is possible to dispatch on the structure of this lambda function as opposed to having an opaque name:

julia> x -> x > 2
#3 (generic function with 1 method)

julia> >(2)
(::Base.Fix2{typeof(>),Int64}) (generic function with 1 method)

FixArgs.jl (which really should be called e.g. StructuralLambdas.jl) allows one to easily define these structural lambdas:

julia> @xquote x -> x > 2
Fix2(>,2)

julia> typeof(@xquote x -> x > 2)
Fix2{typeof(>), Int64} (alias for FixArgs.Lambda{FixArgs.Arity{1, Nothing}, FixArgs.Call{Some{typeof(>)}, FrankenTuples.FrankenTuple{Tuple{FixArgs.ArgPos{1}, Some{Int64}}, (), Tuple{}}}})

(Better aesthetics would be necessary for usability.)

See https://goretkin.github.io/FixArgs.jl/dev/ for more motivation and details, including examples for replacing Complex and generalizing FixedPointNumbers.jl.

Please note that this talk is about an idea, not FixArgs.jl itself. It may turn out that the idea is not practical; e.g. it might pose immense challenges for compilation, or it might be too confusing to marry the meaning of functions and Call, or package interoperability will fail due to subtle differences. I hope the idea holds promise. A great way to find out is at JuliaCon 2021.

I am a late-stage Ph.D. student in Robotics at MIT CSAIL, and I first used "Julia" in 2012!