-
Notifications
You must be signed in to change notification settings - Fork 46
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Automatic currying support #74
Comments
I've been hacking in the typer and my initial impression is that it's going to be tricky to take the approach of getting the typer to understand curried applications. Not impossible, but there might be an easier way. What if, when a given function has a single version defined, we auto-generated the other versions of the function? We could do that at the AST stage and then everything else should just 'work', i.e. -- human defined a_fun/3
let a_fun x y z = (x, y, z)
-- autogenerated a_fun/1 and a_fun/2 variants
let a_fun x =
let curried y z = a_fun x y z in curried
let a_fun x y =
let curried z = a_fun x y z in curried Obviously, we'd need to constrain it so that the curried functions aren't generated if you defined other variants. We could track which ones are actually used and strip unused ones at the codegen stage, or we could let these be 'opt-in' or 'opt-out' with some sort of sigil like -- Curried
let ~my_fun x y z = (x, y, z)
-- Not curried
let my_other_fun x y z = (x, y, z) (In traditional ML it's easier as you can always assume that an application involves exactly one argument, but as we have multiple arity we don't have that option) |
So if a module had only Regardless the generation approach does solve the problem of the typer and codegen stages both needing to understand automatic currying which is pretty nice. |
I think we'd previously discussed the second approach. I think it might get confusing - I'd have a slight preference for saying that we either have currying or multi-arity, but not on the same function at the same time, but I'm not really sold either way. I managed to get the ast gen approach working (naively, messily, very untested and in a way that breaks multi-arity funs) https://github.com/alpaca-lang/alpaca/compare/master...lepoetemaudit:dj/autocurry-exp?expand=1 - initial signs are promising, though. I believe some of ast_gen stuff is changing in your upcoming PR, so I'll wait until that is merged and then reimplement based on your decision re: trying to generate as many curried funs as possible or only when there is a single version of the function. |
Thinking about this some more, your suggestion for an annotation/symbol approach to enable currying is maybe best here. I like the explicitness of it and it gives a better way to report on conflicts. Maybe exactly what you're saying where if there's multiple arity then a curried version is simply not allowed. Strikes me as cleaner. What do you think? |
You could just make the non-curried / multi-arity version be a single-arg tuple to return type instead of a curried function type. Basically like this: let non_curried_fn (a, b) = a + b
let curried_fn a b = a + b
let combined_fn (a, b) c = a + b + c There the equivalent Erlang syntax's would be: non_curried_fn(A, B) = A + B
curried_fn(A) = fun(B) -> A + B end
combined_fn(A, B) = fun(C) -> A + B + C end Therefor currying is entirely explicit. Basically this is just automatic expansion of an N-Tuple to make an N-arity function call. I would also be very much for a single function definition per name instead of erlang's single function definition per name/arity, but this method would let you support a single function definition per name/arity fine. Unpacking tuples for function calls would not be terribly costly either, but you can always make a new type instead of overloading tuples in this way too. |
👍 to the general idea, @OvermindDL1, but what happens when you want to write a unary function that takes a tuple? let snd (a, b) = b snd({_A, B}) -> B. |
Yet another idea - what if we had 'let' defines be always curried, and use 'fun' for the Erlang style ones where multiple definitions would be allowed? |
That is precisely the thing I was thinking about when I mentioned possibly making it a new type instead of overloading a tuple. :-) You 'could' work around it surrounding a matched tuple-arg in two sets of parenthesis perhaps: let snd ((a, b)) = b Or give a multi-arity functions a different syntax like: let non_curried_fn (|a, b|) = a + b
(* or *)
let non_curried_fn ~(a, b) = a + b
(* or *)
let non_curried_fn !(a, b) = a + b Or something like that. Honestly I'd think that de-constructing a tuple-arg in a function header will not be common, or not as common as using N-arity{N>1} function calls, so I would opt for the first construct for tuples.
How would you do something like the third example I gave where it mixed them of: let combined_fn (a, b) c = a + b + c EDIT: I guess you could be explicit: fun combined_fn a b =
let aux c = a + b + c in
aux But ick, plus how'd you type this overall |
Edit: Updated to reflect this proposal. Update: heavily edited since first posting. 👍 for alternate syntax. My favorite at first glance is With that in mind, I propose the following:
|
Wouldn't that one actually not compile because it is a function of arity 1 where the argument is a 2-tuple (the first element being invalid syntax though)?
Actually this one is valid and would translate into: combined_fn({A, B}, C) = A + B + C end. By being a 2-arity function where the first argument is a tuple. But yes, I do quite like this syntax, and it seems fully powerful as much as you need it to be. Convoluted example: let blah a !(b, c, (d, e)) (f, g) !(h, i) = a + b + c + d + e + f + g + h + i Converts to: blah(A) ->
fun(B, C, {D, E}) ->
fun({F, G}) ->
fun(H, I) ->
A + B + C + D + E + F + G + H + I
end
end
end Where the type could be (in OCaml syntax, I do not have alpaca's memorized): val blah : int -> (int * int * (int * int)) fun -> int * int -> (int * int) fun Where |
@OvermindDL1. Check my edits? I changed quite a bit. |
Edit: This is backwards. See this comment. So I think we've got different understandings of the proposed syntax. The way I see it:
|
Edit: This is bad. See this comment. So your let blah a !(b, c, (d, e)) (f, g) !(h, i) = a + b + c + d + e + f + g + h + i blah(A) ->
fun({B, C, {D, E}}) ->
fun(F, G) ->
fun({H, I}) ->
A + B + C + D + E + F + G + H + I
end
end
end. |
Ahh, yeah I stated it to be the other way in my post that introduced that syntax, that works too though however unless |
👍 for unified syntax. For posterity:
|
Not at all, first even if the EDIT:
Precisely! :-) |
I caught that and edited again. /me needs to read before pressing |
Lol, does not help that we are both here in real-time. ^.^ |
@OvermindDL1: How does this look now? |
I'm coming to the end of a fairly heavy work day so what follows may not be nearly as open minded as it should be and I'll commit to reviewing all of this a few more times :) Having said that, my rough opinion here is: We seem to be arguing towards more complexity in the syntax/some overloading. This makes me think we need to do one of two things in the service of simplicity:
I suspect interoperating with Erlang might actually lead us to destructure tuples in function arguments a fair bit but it's entirely possible I'm wrong :) |
Looks good in syntax however the output generates multiple function arities, which can make it really difficult to fulfill certain erlang behaviours, I'd take out that auto-generating multiple arities from a single function definition. The
Actually the syntax requires no lookahead so it remains simple and the overloading was removed, N-arity functions are now representable by their own type.
Honestly I'd be up for that.
I'm less up for this because it does not fit the erlang world as well, some behaviours require different arity functions of the same name to be called with different things, and this would make fulfilling this impossible or difficult.
Not really in my experience. The main use of tuple de-structuring in a function head was for state records, and those are both internal to a module (so would not affect users of alpaca) and are phasing out for maps instead. Personally I'd probably drop automatic currying, instead make it so you can curry on-site rather than at-definition. Although this |
You could keep the let blah !(a, b) c = a + b + c
let 6 = blah !(1, 2) 3 That way everything remains unified in syntax and very easy to statically type. :-) It literally would just be a type in the system, no different than any other, except it gets optimized to the EVM as N-arity calls instead of 1-arity calls. :-) |
👍 for dropping automatic currying. I destructure tuples all the time in Erlang (e.g. What if we had special syntax for currying and then the compiler failed upon any collisions? |
As in... let blah !(a, b) c = a + b + c blah(A, B, C) -> A + B + C.
blah(A, B) -> fun(C) -> A + B + C. such that if I then define a let blah a b = a - b the compiler fails, because I've introduced ambiguity. |
and let blah a b c = a + b + c translates to only blah(A, B, C) -> A + B + C. |
The Ambiguity things could work but seems messy to me. I'm of the 'explicit is better than implicit' train of thought, so I'd like the functions to only have the arities that I tell them to have. But it would be a work-around, 'if' there is a way to over-ride it. Remember that erlang can have behaviours that an alpaca module might need to implement like this: -callback handle(Args :: list(term())) -> 'ok'|tuple('error', Reason :: string()).
-callback handle(Msg :: term(), Args :: list(term())) -> 'ok'|tuple('error', Reason :: string()).
-callback handle(Msg :: term(), Args :: list(term()), Opts :: list(term())) -> 'ok'|tuple('error', Reason :: string()). And I've seen ones that swap arguments while adding more as well. Yes ugly, but needs to be supported. :-) EDIT: Also I can get a category created on the elixirforums.com website for Alpaca if you want a dedicated section for Alpaca discussion |
Right. I'm suggesting no auto-currying and explicit currying via "bang patterns." So then the onus is on the user not to mess it up. I see what you're saying though. If I define a curried I'm actually fine with that tradeoff. "With great power comes great responsibility." 😉 |
Hmm, if the autogenerated functions had a new name instead of the original, an entirely internal name, then that could work around the issue as well. I'm still unsure about: let blah !(a, b) c = a + b + c Generating into: blah(A, B, C) -> A + B + C.
blah(A, B) -> fun(C) -> A + B + C. Because that seems like it would still conflict at times, at times impossible to work around, plus it does not match the full contract of the function (which is asking for a 2-arity function only, that returns a closure that takes another). The user could do that explicitly if they want via: let blah !(a, b, c) = a + b + c
let blah !(a, b) c = blah !(a, b, c) Just like they would do in erlang now (and of course you can make helper functions to auto-curry an argument or so to add to the core function set). |
Gah, I keep switching back to my intuition of bang patterns. I need to step away and think on this a bit. |
I don't think auto-currying makes sense on the BEAM. As @OvermindDL1 mentioned, behaviours often expect functions of multiple artities with the same name. What's more, in Erlang, the convention of e.g. I understand your aversion to more punctuation, @j14159, but I feel quite strongly that currying, while convenient in certain (read: many) cases, should be explicitly demanded, rather than automatic. |
@j14159 I broadly agree with you, and I still prefer the solution you describe as being "pretty ok with". I can however understand the argument about not wanting to autogenerate variants of functions. I like @OvermindDL1's idea of generating internal, aliased functions. This way, the typer and codegen would try the 'real' function name first, and the curried name secondly, so you'd get something like this: let f x y z = x + y + z
-- autogenerates something like:
let _curried_2_ghzkp_f x y = let curry z = f x y z in curry
let _curried_1_ghzkp_f x = let curry y z = f x y z in curry
-- 'f' here would actually resolve to '_curried_2_ghzkp_f' by the Alpaca compiler
let main () = f 10 20 I can't think how this would be limiting in any way. If you want to just define your functions with multiple arity like in Erlang, you're not prevented from doing so and interop with other things on the BEAM will be fine. If you are coming from an ML, where (sorry to hammer the point!) autocurrying is a sine qua non, everything will also meet your expectations. |
@lepoetemaudit I think that method is the best compromise yeah, internal names should not cause issues as long as they are always truly unique, and you can create some dang weird function names in erlang, you are not restricted to just underscores for example (as it really might be best to try to make it as difficult for a human to type out as possible), you could generate this on the erlang side for your above example: let f x y z = x + y + z -> -export([f/3, 'f$$curried`/2, `f$$curried`/1]).
f(X, Y, Z) -> X + Y + Z.
'f$$curried'(X, Y) -> fun(Z) -> f(X, Y, Z) end.
'f$$curried'(X) -> fun(Y) -> fun(Z) -> f(X, Y, Z) end end. Any function name can be any valid atom, which is anything inside |
I can get behind this compromise. It seems slightly more work to implement, but it's also well worth it imo. |
Seems pretty sensible to me too. |
Sounds like consensus. I'll work on a PR based on the above. |
This has been sitting as a draft since last weekend, so it's a bit stale at this point. Regardless, @j14159 asked me to post it nonetheless. This has had me thinking about some limited forms of dependent typing, specifying type signatures/partial signatures to indicate which function is intended, have the compiler scream if params don't line up. Sorry, I really don't mean this to come off as coming late to the party, and being a jerk about things. I think that the user is the only one that knows whether something should be curried or not, and having auto-currying as a default makes the most sense (to me at least). Thinking further from @lepoetemaudit original suggestion about generating curried versions of functions, I started to wonder about another approach. Bear with me, as I barely know Alpaca/Erlang, so I'm going to go slowly mostly for my benefit. Starting with the first example, which broke
First example, but we want (imply) the second function
First example, but we want (enforce) the second function
What if the types don't line up =(
|
You make a very valid point, @saem. Thank you. I think we should handle such cases. I think it's reasonable to expect the typer to figure out not Example (typed on my phone, so probably not entirely correct, but it should get the point across): half :: Num a => a -> Float
half x = (fromInteger x) / (2 :: Float) -- <~ term-level annotation |
@saem, thanks for this. I'm very concerned about ambiguity (both for the compiler and the programmer!) and in my head I have some very simple rules to mitigate this:
This is somewhat restrictive, but to my mind it prevents any surprising behaviour or undue complexity for the compiler. Perhaps this isn't the general feeling, but to my mind most of the time you'll be declaring functions either with multiple arity (for BEAM/OTP interop or for some particular idiom) or for general use in ML-style code, you'll be declaring a single function per name most of the time. If at some point a programmer REALLY needed to wrap a multiple arity function where currying wasn't operating due to the rules above, they could just manually curry with an anonymous function or whatever. What I'm hoping for is that we can allow programmers to freely define multiple arity funs, and also benefit from autocurrying, but have them be aware that mixing both for the same function name comes with restrictions that are apparent and easy to reason about, without unintended side-effects. I might have misunderstood what you mean by ambiguities in relation to types; if so my apologies. I might be wrong but I think these restrictions as I've set them out side-step all of the ambiguity issues. |
Warning: lots of opinion :) I'd like to suggest inverting our approach a bit. I think we have two distinct problems:
These definitely have some odd interplay but I think we can treat them separately and win. OverloadingTo be perfectly honest I'm not a fan of automatically resolving things with overloading and solving the dispatch problem for the user. I think if we add type guards to function definitions we give users enough tools to express and be explicit about what looks like an overload in terms of a match (this sort of links up with @yurrriq's point about Haskell and type annotations as well). Should fail because
Should pass because there's a sum/union type that allows
Note that the guards are actually required for this to dispatch correctly as well since the VM needs to use the type-tests for dispatch at runtime. Different Arity, Same NameUnfortunately we can't avoid this and still have OTP interop without a lot of additional weird constructs (specifically in the case of Erlang calling into Alpaca, e.g.
To borrow from @saem again but this time the conflicting return type:
I think the above should be a type error because the same name has two fundamentally incompatible types in the absence of a sum/union type to allow them both to coexist. To strip it down, given:
I think Borrowing again, this should pass:
And @danabr's work in PR #92 will help by checking the exhaustiveness of matches/functions leveraging these two. Thoughts? |
@j14159 - this is really interesting. I didn't understand that this: type make_it_work = int | string
let f x, is_int x = x + 1
let f x, is_string s = string_append "hello, x" Was possible in Alpaca. In OCaml/Elm, you'd have to do something like type make_it_work = Int int | String string And then pattern match. (Neither Ocaml/Elm has function overloads though). I'm not confident with Haskell, but I believe achieving the above would need type classes there. This is also seems like we'd be limited to the primitive types supported by Erlang's guards. Would it not be preferable to strip this in favour of one of the future polymorphism strategies discussed? (I think implicit modules as is upcoming in OCaml has been floated before - http://www.lpw25.net/ml2014.pdf) Would we, given f/1, f/3, and f/5, still want to generate f/2 as a curry? My approach was to say that f/5 is the canonical definition for currying, and to avoid generating any ambiguous curries (i.e. would f/2 curry f/3, or f/5?) As an aside, the Purescript port to Erlang seems to take a different approach - https://github.com/purerl/purescript#types - there, multi-arity functions are special cased. I think our philosophy is to integrate more neatly with Erlang/OTP and the BEAM, but it's interesting seeing how others have approached this. |
@lepoetemaudit thanks for linking the modular implicits paper. I haven't read it yet and it's interesting they reference Scala's implicits as they're one of the features I actually dislike about Scala on bad days ;) Having said that, I'll definitely read the paper and appreciate you mentioning it! Side note, I was actually trying to avoid making
I think this is problematic again for Erlang interop but I'm open to being wrong here (and I'm mostly speaking to requiring type annotations for removing ambiguity, not signatures and modules). If we try do do some automatic overloading with rewriting (compiler-mediated, static dispatch) I think we're going to make it pretty hard for Erlang to use Alpaca stuff and I'd prefer to keep things as obvious as possible. Since all of our types ultimately do reduce to being defined by base Erlang types, the type check guard functions strike me as a way to just refine the matches where necessary. It did occur to me at one point to allow annotations for these in a match which would cause the addition of a guard, e.g.
would automatically be expanded to
but this would fall apart/be inconsistent with any other user defined type I think? With respect to Thoughts? PS - I've eyeballed purerl a little here and there and it's definitely interesting to see their approach as well! I'm quite curious to see how it develops but you're right, I'm quite keen to keep Erlang/OTP interop as simple as possible though it's increasingly a tricky balance with safety :) |
I think I'm fine with all of that. I suspect we won't uncover all the corner cases with this or really understand what is obvious or not to newcomers until we start building more stuff in Alpaca itself, and actual usage might well point the way towards what we should keep and what we should remove (if you look at Elm's evolution, it's often been brutal even at a syntactic level - removing infix invocation with backticks in Elm 0.18 for example). |
Sorry for the slow replies, life is exceptionally hectic. @yurrriq I have been thinking that ambiguity shouldn't "leave" a module, mostly just to avoid the concern of how would this look inside the documentation. So whichever module within which an "ambiguous" call is started, it must be resolved within it before the module will compile without error. Term level type annotations, first off, your phone typing is amazing! Second, wouldn't a literal, or the type of another variable/expression resolve the ambiguity (especially, with the above, module only, limitation)? @lepoetemaudit Thanks for really making it succinct, and providing an easy to follow rules. My concern here is that introduction of a higher airity function is now a breaking change for all of the an author's library's users. I really apologize for making it a one-liner like that, but that hit me hard. Currently, my mental test for this feature is what's author's experience when they have to change existing code, and what happens to the user of said authors code on the consuming end.
I'm of the opinion that any approach should be with minimal burden to author (outside "consuming" an airity), and minimal code changes for the user if author makes a change. Does that make sense? As an aside, I think it might be worth while having a check list of "mental tests" that language features proposed should "pass". Specifically, thinking about how every feature handles changes on the library writer side, and the library user side, might be a reasonably general check. Not just for this feature, but others. It would make thinking of edge cases a little easier, or at least help prime thinking in the right direction?
^^ these will improve when I'm less tired, and they've gone through a few more use cases, and as we'll probably end up with some sort of taxonomy of feature classes, and associated tests. |
@saem - that's an excellent point. Adding another higher arity function to an existing set would break anywhere else that was relying on currying from the function name. However, I'm not all that worried, because:
(Progress update on the implementation, I mostly have it working, I'm just chasing down a few failing tests and adding more test coverage) |
It seems like supporting both currying and multi-arity functions adds quite a bit of complexity, both for the end user and the implementation. Personally, I would:
A question regarding currying: |
But it is a hassle and gets us out of the world we prefer to stay in just for the sake of implementing a behaviour for example... I still think it is best to have something like |
@danabr this is a really nice and simple solution but my issue with it is that we then can't type the implementation of a behaviour :) Here's what I think the basic problems are:
Can we clean all this up with some simple feedback from the compiler to the user? E.g. if one were to define both Frankly, if forced to choose between:
then I'd probably choose multiple-arity in the service of utility. Having said that, I think the compiler's job is to help the user and a warning that can be flipped to an error seems like that helps in concert with @lepoetmaudit's work. Like match exhaustiveness failures as errors in other languages (and hopefully Alpaca soon), this gives the user or a team the ability to choose what matters to them and only restricts what they expose, not what they can use. I'm also still curious about where @saem's points might lead us. Thoughts? |
There is another option, drop currying on functions and make all functions multi-arity, and instead to automatic currying at the call-site, which is the standard erlang/elixir way as well (though via anonymous function wrapping, you could make that more streamlined here anyway), perhaps something like (in OCaml'y syntax, that is still where I come from ^.^): let f0 x y = x + y (* A 2-arity function taking 2 integers that returns an integer *)
(* A 2-arity function taking 2 integers that returns a 1-arity function that takes an integer
that returns an integer *)
let f1 x y =
let aux z = x + y + z in
aux
(* To curry on-site you just need some syntax to state which-arity function you want to
use then just partially apply it like normal *)
(* a 1-arity int function that returns a 1-arity int function that returns an int *)
let f2 x = f0$2 x
(* Possible other syntax's: *)
(* Like an OCaml object call, but no objects here so # could be used for this then *)
let f2 x = f0#2 x
(* I don't like this, overloading the /, although it is erlang'y *)
let f2 x = f0/2 x
(* Requires special compiler support for a 'curry' keyword, but it is wonderfully explicit,
I might like this most of all although it is wordy *)
let f2 x = curry 2 f0 x I'd probably pick |
I also think that the currying should take place at the call site, by having the compiler automatically generating an anonymous function. That would avoid polluting the source module of a function unnecessarily. (Thinking of that, wouldn't xref complain about a lot of those auto-generated functions being unused?). |
@OvermindDL1 I guess I'm resistant to anything that makes the syntax heavier. Anonymous functions would make dropping currying bearable, as would your special curry keyword, but I'm still not convinced that the tradeoffs of automatically currying are going to be particularly severe. @j14159 I'm wholly in favour of warnings - something like a comment (not a full blown annotation) could be used to silence warnings when you were certain you wanted to have multi-arity functions and weren't concerned that they couldn't be curried. @danabr I'm also not against currying happening at the call site, but it's perhaps a little trickier to pull off. I guess my ultimate plan was to try and track and strip unused curry functions to avoid pollution, but that's a little tough to handle right now as well. One major advantage to this approach is that you could potentially curry even multi-arity funs that are declared in another module as long as you only import one of them. @j14159 do you think this might be a preferable way of handling it? If so I'll explore this approach some more. |
So, disable currying of multi-arity functions, and:
I realize doing currying at the call site is more complicated, but I think its worth it. |
@danabr you beat me to it - I was just thinking about this and I think it solves our problem nicely. If say f/3 and f/5 are both declared, and at the call site the user tries to use f/1, the compiler prints an Elm-style friendly error to the tune of:
This way, it's totally unambiguous, library writers are happy, users are happy (and hopefully we are too). |
@lepoetemaudit @danabr this is broadly making sense to me. FWIW we're already able to specify functions with module and arity for values e.g.
This is the equivalent in Erlang of I think it's a short jump to being able to specify arity at the call site when it's desired if that helps and without the module qualifier. |
@j14159 I didn't realise we could reference specific versions of functions like that (although it's the same as Erlang) - that seems a really obvious way of 'picking' a function in case of ambiguity and it doesn't introduce new syntax. I'm feeling cautiously optimistic about of all this :) I've been experimenting and I've managed to get the typer to select suitable candidates for currying and unify correctly. It'll take a fair bit of cleaning up and I have to do the codegen part (that latter bit should be easier though!). Overall the approach is definitely solid so I'm going to persist with it. |
Sounds good to me, I appreciate all the effort you're putting into it! In fairness the specific arity selection stuff isn't yet complete enough for what we're talking about here but I don't think it would be very difficult to make it so. |
Closing per PR #177 |
Taken from the discussion in issue #56 with @danabr and @lepoetemaudit
Single versions of a function will be automatically curried so the following will work:
When there are different versions of the same named function (differing in arity), we will halt typing with an error in any ambiguous case. For example the following would generate an error along the lines of {error, {ambiguous_application, foo/1, foo/2}} - but maybe less hostile than that :)
While the following would not:
Feedback and differing opinions welcome. I think basic expression application as discussed in #56 has to be addressed before this issue is.
The text was updated successfully, but these errors were encountered: