Functional application, reconciling currying with multiple dispatch

Good evening alltogether!
I’m very new to Julia and I read several discussions and I thought about the conflicts and making language usage even more attractive. Unfortunately I could not register in GitHub hence here is what I want to share.

I know there already has been heaty discussions about the philosophy clash of currying and dynamic dispatch and problems which seem to arise (if the dispatch concept is violated or undermined). However, I tend to disagree that currying and multiple dispatch can’t cooperate together and I think, it still will enrich JuliaLang using well-defined behaviour and observations which I want to propose here.

So where to start? The key feature for common multiple dispatch is (runtime) knowledge about the calling argument list which I imagine like a list of argument properties, being mostly argument types I guess, which have to be provided for unambiguous (and comprehensible) evaluation (i.e. to choose the proper implementation based on the arguments). One conflict mentioned by developer(s) was the uncertainty how to distinguish partial application from dispatching a function with fewer arguments, for example:

func a b #is this a call to func(a,b) or is it partial application for func(a,b,c)??

However this conflict can be resolved by choosing a new operator compatible and similar to Julia.

My solution:

Introduce |-> (or \mapsto) as postfix application operator and <-| (or \mapsfrom) as prefix application operator which btw will look like generalizing the pipe operator |> at the same time. As you will see, no foreign or untypical syntax will be required here since the application operators are normal infix binary operators.

The best thing of choosing the aforementioned tokens is: the operator looks and behaves quite like the math arrow \mapsto for defining functions. And the implementation must not be difficult, could be compared to the ~ operator which is (or was) replaced by a @tilde. This could be done in the same way for my idea. Maybe this even could be implemented in a package.

Other alternatives could be $>, +> or &> for |->
So now coming to demonstrate the operator:

(x!, a, y!, b, c) |-> func
#= which is just a convenient lambda abbreviation for
> x -> (y -> func(x,a,y,b,c)),
the operator order of the argument list is preserved =#

a |-> func = func(a)
x! |-> func = x -> func(x)
() |-> func = func()

I’d even like to generalize the argument list in parens to any kind of iterator object (even lazily evaluated iterators) but the simple-list-only approach appears to my imagination as much easier to add at first.

Explanation: The application operator acts like the functional primitive “reduce” on the bar side of the operator (more examples below). The argument list is applied to the function and every !-tagged argument creates a new level of lambda nesting returning the accumulated lambda. As to be seen the ! could be used for currying “tagged” arguments providing extra flexibility. The exclamation mark could be a postfix operator producing a container which is parametrized with the type of the tagged var name. Alternatives are possible but should not be longer than two characters. It could also be nice to replace the name with underscore (which someone already mentioned somewhere), so that a::Int32! becomes _::Int32 or @:: Int32, @_ ::Int32 which might look better than the ‘!’. For consistency I kept the !-tag-notation.

By having to list all arguments for the final function call it is clearly defined using the operator how the dispatch will look like. The arguments can be anything, even type-annotated (see below). Note that compilation even gives you an error if the given arguments don’t match the function!

My perspective is an easy notation which allows to determine “curried lambdas” and full-featured partial application.
I also think of something like:

	:opname <-| [a!,b::Int32,c::Float64] =
	[a!,b::Int32,c::Float64] |-> :opname = #variant 1
	:opname <(a, !, b::Int32, c::Float64) = #variant 2 or maybe even just normal (...) by using only '!'
	curry(opname,a!,b::Int32,c::Float64) = #variant 3 replacing |-> by the word "curry" or "@curry"
	a -> b::Int32 -> c::Float64 -> *opname* (a,b::Int32,c::Float64)

Probably the best notation is

f(a, ::Int32, b, c, ) = _2::Int32 -> _5 -> f(a,_2,b,c,_5)

(Edit: I didn’t know that ::Int32 is a valid type parameter of a fuction when I wrote this.)
but empty arguments would take effort and change to the core language I guess.
infix application:

(a,b) |-> :func <-| (c,d) = :func(a,b,c,d)
(a,x!) |-> :func <-| (y!,b,z!) = x -> (y -> (z -> :func(a,x,y,b,z)))

At first the infix application seems mismatched needing to temper with the natural order of evaluation because actually:

(a,x!) |-> :func <-| (y!,b,z!) =
(a,x!) |-> (y -> (z -> :func (y,b,z))) =
x -> (y -> (z -> :func(y,b,z)))(a,x)

which would not be desirable.
So as suggested above, maybe f <-| (...) should internally by rewritten to (...) |-> f and then (a...) |-> (b...) becomes (a...,b...) which turns |-> into an additional concatenation operator.
|-> must be left-associative and have lower precedence than <-|.
Note that this detail of concatenation (needed for proper infix notation interpretation) distinguishes |-> from a pure generalization of |>. Here |-> is not a mere extension of |> since

a |-> sin |-> :func = a |> sin |> :func = :func(sin(a))
#BUT
a |-> [sin] |-> :func = :func(a,sin)

You can go even further with some sort of longhand lambda

(a,x!) |-> do
	if x < 0 x = 0 end
	... #other instructions
	:func
#= lambda created with |-> must return a function which takes exactly the arguments found left to |->, in this case :func(a,x) must be valid from the returned :func. =#
end

And now even imagine chaining partially applied functions:

#create a curried sum of 4 operands
myfunc = (a::Int32!,b::Int32!,c::Int32!,d::Int32!) |-> +
#maybe also chaining equal wildcards with "myfunc = (4*@_ ::Int32) |-> +"
#apply (1+2+sum(1:5)) = 18+x to every element of 2:2:10
map( (1)(2) |-> + <-| sum(1:5),  2:2:10 )
#which is
map( +(1)(2)(sum(1:5)), 2:2:10 )
#> [20,22,24,26,28]
#or suppose a sort((y,x)->cmp(x,y),array) function 
weirdsort = (x::Int32!, "<", y::Int32!, foo, bar) |-> weirdcmp |-> sort <-| array::Array{Int32}!
#which is another writing style for sort <-| (weirdcmp <-| (...), array!)
weirdsort(array1)
weirdsort(array2)
#...

Edit:

I noticed that another weakness is the fixed order of lambda arguments with this operator which means that in (x!,y!), x comes always before y. To overcome this shortage I had another idea to create simple predefined placement macros @0 to @9 which give some sort of priority wildcard. Wildcards with equal priority are treated as before sequentially. Alternatively, the priority could be mentioned behind the wildcard macro @_ and if the leaving-out-notation should be used, an empty argument would just generate a @_ wildcard macro which has the same priority than the last wildcard.

f(@2,@1) = _2 -> _1 -> f(_1,_2) #@2 = _1 and @1 = _2
f(a,@1,b,@0, c, @0) = _4 -> _6 -> _2 -> f(a, _2, b, _4, c, _6)
f(d,@_,@_ 2 ::Float64, @_ 1 ::UInt32, e) = _2 -> _4 -> _3 -> f(d, _2, _3, _4, e)

However this sort of macro seems to need language changes as well. Maybe even, if instead of an operator or no operator a macro @|->, @<-| is used, however @|->(iter_obj,f) could probably be impemented by walking through the iterator object and looking for wildcards. Though, without language support it would be quite slow because the macro would be executed at runtime instead of at compile time and macros are bad for optimization.

BTW: Is it possible that static metaprogramming pieces of the program are executed during compilation to produce output code? That would not only solve this problem but drastically help fixing performance problems of macros in general.

EDIT END

Using this feature allows Julia to have a more flexible notation. And even if you don’t like my application operators (you could also use the unicode variant), all of this issue amounts eventually to just syntax or an operator being sugar for this specific gimmick:

gimmecurry = a1 -> a2 -> ... -> an -> do #=any instructions =#; func(a1,...,an) end
gimmecurry(a1)(a2)...(an)   #function evaluation

Pointing that out, Julia already even supports currying (and thus theoretically partial application) to its fullest in a haskell like manner, however not necessarily Juliesque at the moment. This is not an additional language feature but a question of language style.

At last, I found out that my idea isn’t even totally new. One developer had a similar idea
[similar idea]{https://github.com/JuliaLang/julia/issues/16985#issuecomment-227014300}
which had just not my amount of detail (I guess).

And not only that it is compatible to the idea of jamesonquinn it would even magically fit to [another idea]{https://github.com/JuliaLang/julia/issues/16985} which proposed a |>f<| for infix notation.

With the proper interpretation of <| it would be possible to replace |-> with |> by only generalizing |> to allow multiple arguments, even if only written like:

|>(func, arg1, arg2!, arg3, arg4!) = arg2->arg4->f(arg1,arg2,arg3,arg4)`.

The whole prefix application operator <-| thing could also be defined only for iterator arguments on the LHS and if only a normal argument list in parens is required, the operator can be left away.

Summing up the pros:

  • readability (maybe depends on taste),
  • intuitive arrow interpretation
  • typing effort high of operator is enough to prevent overuse or misuse for unsuitable situations but good enough for a gain (I’d say)
  • implementation for the iterator argument version with @_ macro might be even possible as Julia package
  • operating with powerful iterators instead of simple parameter lists only which allows to generate curry arguments (however generation of ! behind iterator lists is still not clear though, using a functor macro like @!(a) to containerize a with a specific recognized type looks ugly)

I think the convenience delivered by such an operator would make Julia even more attractive to new programmers and increase development support which I’d be interested in for myself in future.

Also, people will stop complaining and asking when easy currying notation finally is integrated and documented properly and is shown as trick in a tutorial. I don’t know if Julia is the first language supporting multiple dispatch along with currying/partial application but if so then it would be an interesting novum!

Cons which come to my mind:

  • little bit more complicated implementation, operator dispatching overhead for list concatenation, due to chaining of application operators

  • confusing similarity to |>

  • it hides what is going on (which could also be a good thing) and does not save a lot of characters (which also could be an advantage as mentioned above), at most almost the half, e.g.:

    (a1!,a2!,a3!,a4!,a5!,a6!)|->func =
    a1->a2->a3->a4->a5->a6->func(a1,a2,a3,a4,a5,a6)
    
  • many notation-variants might need specific language changes

  • a list which is supposed to be one argument to an application operator must be put in an extra list to count as one single argument

  • implemented features as macros are quite slow when executed at compile time (possible solution would be the ability to execute static metaprogramming parts at compile time as mentioned in the EDIT section)

I’d like to hear your opinions on the idea, improvements, rejections? Or is further feature discussion to this topic useless?

The only remaining is support/openness by the community/developers for the feature. It doesn’t make sense to create a feature which is not well received at all. I’m still busy with studying but if I find time learning Julia properly, later I might come back on this idea if noone else is interested in implementing it.

6 Likes

I’m afraid there is a bigger shortage or misunderstanding in my proposed concept which is that currying, even if possible, barely is ever used or required by Julia code by now – maybe because not found Juliesque or untypical or whatever – and would not give much benefit at the moment, even if useful later when the feature is more commonly used.

If I understand correctly, the common idiom for function arguments is rather (a,b) -> func(a,b,c) than a->b->func(a,b,c) for common Julia packages, so that you can’t do much with curried functions alone, though that’s just a guess of mine.

My proposed application operators work only on uncurried functions which means – in order to complete the concept – there would even be a need for an operator version which works on curried functions like |+> and <+|, or |~> and <~| maybe looks nicer.

In that sense, I correct a mistake made in one of my code examples:

(1,2) |-> + <-| sum(1:5) can’t work because in the example, + is a curried operator which is applied like + (1) (2) (sum(1:5)) (the parentheses can’t be left away).
A question would be, whether a construct like (1,2) |~> + <~| sum(1:5) could work out at all.

The question also is what the additional application operator actually should mean.

Variant 1
(a,b,c) |~> curFunc = curFunc(a)(b)(c)
(a,@_,c,@_) |~> curFunc = (_2,_4) -> curFunc(a)(_2)(c)(_4)
#or this?
(a)(b)(c) |~> curFunc

But what is with curried to curried application and uncurried to uncurried application? Do we again need 4 new operators for that? That would give us a hard time, no. There should be a much simpler way to determine the output function format (curried, uncurried) while being agnostic to the input format (curried, uncurried).

Variant 2

Maybe |-> and |~> take either a curried or uncurried function and |-> generates a curried lambda from it when |~> generates uncurried lamda from it. The arguments to the operator determine the format However, likely it would be better to switch the meaning between both operators since curried functions might be less present up to now and |-> looks like more common use and easier to type than |~>.

It could look like this:

#uncurried to uncurried
(a,b,@_, @_) |-> func = (_3,_4) -> func(a,b,_3,_4)
#uncurried to curried
(a,b,@_, @_) |~> func = _3->_4 -> func(a,b,_3,_4)
#curried to uncurried
(a)(b)(@_)(@_) |-> func = (_3,_4) -> func(a)(b)(_3)(_4)
#curried to curried
(a)(b)(@_)(@_) |~> func = _3->_4 -> func(a)(b)(_3)(_4)
#brave melange
(a)(b,@_)(@_, @_)(c) |-> func = (_3,_4,_5) -> func(a)(b,_3)(_4,_5)(c)
Variant 3

Or you could even say, |-> does not change the currying-format but |~> does so

  • curry-to-curry, uncurry-to-uncurry: |->
  • curry-to-uncurry, uncurry-to-curry: |~>

However combining the mix of curried and uncurried arguments with the custom argument order idea from my first post, that seems to make difficulties for this variant:

#keep the lambda format
(@_)(@_,@_) |-> func = _1 -> (_2,_3) -> func(_1)(_2,_3)
#but does this work out? (just changing the order of lambda parameters by keeping the format
(a)(@_ 1)(@_0, @_2)(c,d) |-> func = _3 -> (_2,_4) -> func(a)(_2)(_3,_4)(c,d) #??
#but the actual problem is what should happen with |~> :
(a)(@_ 1)(@_0, @_2)(c,d) |~> func
= (_3,_2,_4) -> func(a)(_2)(_3,_4)(c,d) #this?
= _3 -> _2 -> _4 -> func(a)(_2)(_3,_4)(c,d) #or this?
= (_3,_2) -> _4 -> func(a)(_2)(_3,_4)(c,d)
#= or even this, turning each ')' into ',' and ',' into ')'? Even if I like the possibility and it seems to extend the principle of |~> more genuinely, this use case seems not very common, so that falling back to another solution could be useful =#

Maybe someone has the time to think about whether currying-sensitive application notation should be integrated in future or not. After I’m done with studying, I could try to read more into Julia ad make a macro prototype for demonstration.

Hey @christophE! Welcome to the community. I haven’t yet read your full post, but are you aware of this RFC here about this topic? It summarizes many existing views quite nicely. If you can relate your own thoughts to the existing discussions, you’ll have a better chance of being engaged with and of your efforts having results.

Hope that helps :slight_smile:

The Julia community has a pervasively practical attitude about these things: the focus is on solving existing problems and challenges. Unless your proposal does something like that, it is very unlikely that a lot of resources will be devoted it, especially if it is not fleshed out in detail (eg as an actual pull request for proof of concept).

It is unclear why you cannot use Github, but there are a few discussions about currying and arrow types in the issues. My understanding is that Haskell-style currying does not mesh well with Julia since functions can have methods with different arity, eg f(a) and f(a, b), and then the semantics are not clear. The current interest is in providing syntactic sugar for closures, and the discussion is in the issue linked by @tkluck.

If you are otherwise new to Julia, please use the language for a while before proposing major changes. It is not that they are unwelcome, but making good ones requires a feel for the language that comes with use.

1 Like

@tkluck @Tamas_Papp Thank you both for taking your time to answer :slight_smile: . I don’t know why Github registration failed twice, maybe my Firefox. I can respect your pragmatic nature of development which is important to create a stable language base. Also thanks for pointing out the discussion, that’s the right place I think. I also should try something by myself when I get the time.

(PS: I would have some more – in my view – interesting contributions based on Julia discussions which I read, but I understand the point of Tamas.)

1 Like

This is a pretty hefty proposal. I do think we need better ways to succinctly express partial evaluation of functions, but honestly to my eye, I don’t really like any of the proposed options here. I find nearly all of them pretty hard to read. Honestly, I think julia already has a gigantic amount of syntactic forms so my default position is one of being skeptical of adding more.

I think the main difficulty I have with your proposal is that one specifies that they want currying at the call-site, meaning that these special syntactic forms are required each time we want to call a curried function, which leads to a big bloat of arcane symbols all over the place.

An alternative approach is just to annotate a function definition (instead of call) to say that we want that function to have currying behaviour.

For instance, we could imagine creating a macro @curried such that

@curried foo(x, y, z) = (x^2 + y^2)/(x^2 + y^2 +z^2)

will define extra methods such that foo(x)(y)(z) is equivalent to foo(x, y, z).

The macro could be written as follows:

struct FullyCurried end

macro curried(fdef)
    f = fdef.args[1].args[1]
    fargs = fdef.args[1].args[2:end]
    arity = length(fargs)
    body = fdef.args[2]
    err_str = "Too many arguments. Function $f only takes $arity arguments"
    quote 
        begin 
        function $f(args...)
            if length(args) < $arity
                x -> $f((args..., x)...)
            elseif length(args) == 3
                $f(FullyCurried(), args...)
            else
                throw($err_str)
            end
        end
        $f(::FullyCurried, $(fargs...)) = $body
        end
    end |> esc
end

With that, we can do

julia> @curried foo(x, y, z) = (x^2 + y^2)/(x^2 + y^2 +z^2)
foo (generic function with 2 methods)

julia> foo(1)(2)(3)
0.35714285714285715

julia> foo(1, 2, 3)
0.35714285714285715

and some benchmarking / looking at LLVM code confirms that there is no runtime overhead to the curried form versus the non-curried form. This approach requires no modifications to julia’s parser which I quite like.

13 Likes

Wow, that’s very nice and I will remember this.

Also I noticed that we are actually speaking of various concepts not only one. While your suggestion is for defining a natively curried function, I targeted conversion between different function formats, or an “anonymous dispatch” method (partially applied currying/uncurrying of an arbitrary function), if that is useful at some place. Additionally, the push request discussion linked above concerns still another feature which seems to be more relevant currently: a short notation for lambdas (not just function conversion) which actually covers two different concepts that should be separated (“tight” and “+operator”). Problems arise because in my understanding it is tried to use the same notation for both concepts or by neglecting one concept in favor to keep the simple notation. I might contribute to that later on Github when registration succeeds. Edit: I think they need a separate notation for the more complex non-tight case with operators (the _ notation would be too simple to fit or be interpreted well. f(_,_) seems to me like x->f(x,x). I directly thought of a slightly more flexible version of that: https://github.com/JuliaLang/julia/pull/24990#issuecomment-439708350 ).

1 Like