Applicative APIs and partial application with f(a, b, ..)
#1852
Replies: 6 comments 27 replies
-
|
This is a really good write up, thank you! I think the partial function application is the best approach we've seen to this so far. Let's think about this more |
Beta Was this translation helpful? Give feedback.
-
|
A question from nth on Discord
We would at least need to paramertise the type, but I'm not sure it's quite right still type SchemaBuilder(a, t) = fn(..a) -> Schema(t) |
Beta Was this translation helpful? Give feedback.
-
I agree, I think. Especially if the following: would not type check if |
Beta Was this translation helpful? Give feedback.
-
|
I think |
Beta Was this translation helpful? Give feedback.
-
|
I do not think there is a good way to allow The basic problem with I also have some concerns regarding side-effects, but I think this is the meat of the issue. |
Beta Was this translation helpful? Give feedback.
-
|
edit: to expand Or if you don't like the look of that you could pipe it to something like I hope I'm not just talking rubbish haha 😅 |
Beta Was this translation helpful? Give feedback.
-
|
That all makes sense, and I guess the API is a bit cleaner. It seems like we won't be able to escape needing a final invocation to break out of partial-application, but you are right that having it require no arguments looks a bit nicer and maybe requires less duplicate code. And you are also right that this lines up better with the list spread semantics. |
Beta Was this translation helpful? Give feedback.
-
|
I don't have much experience on the PL design side of things, but I wanted to chime in and voice my support for this proposal. Clean yet super expressive. I love it. Using this feature, the following example ORM-like-thing can be fully implemented in about 150 lines of pure gleam (save for four external encoding/decoding functions). pub type City {
City(name: String, latitude: Float, longitude: Float, metadata: Metadata)
}
fn main() {
let city_schema = schema(table: "city", is: City)
|> field("name", string, fn(city) { city.name })
|> field("lat", float, fn(city) { city.latitude })
|> field("lng", float, fn(city) { city.longatude })
|> construct()
let cities = [
City(name: "New York", latatude: 40.71, longatude: 74.00, metadata: metadata()),
City(name: "Berlin", latatude: 52.52, longatude: 13.40, metadata: metadata()),
City(name: "London", latatude: 51.50, londatude: 00.12, metadata: metadata()),
];
// A stack is a collection of rows from multiple SQL tables
// type Stack = Map(String, Frame), where a frame represents some rows from a single table
// type Frame = Map(String, Series), where `Series` is a vector version of `Dynamic` representing a column
let stack: Stack = city_schema.encode(cities)
// Select just the cities frame
// Encoders return multile frames because objects can contain loaded assoceations
let frame = map.get(stack, "city")
// If we decode the frame, it should return the same values we started with!!!
assert Ok(cities) = city_schema.decode(frame)
}Here fn construct(schema: Schema(fn(Metadata) -> t)) -> Schema(t)instead of fn construct(schema: Schema(fn(a) -> t), a: a) -> Schema(t)we can require that the last field for any type used in the ORM is of type Metadata. Anything else is a type error when they try to write a schema. Neat, right? More generally, the separation of The row-poly syntax is perfectly inline with the behavior of the spread operator as defined on lists. Only one "spread" is allowed, and only after all the other arguments. The partial application syntax also seems great. I think if you bill it as "argument spreading" rather than "currying", new users will probably pick it up pretty quickly (if they have to touch it at all). Comments
Questions
|
Beta Was this translation helpful? Give feedback.
-
|
Also with noting: I think this proposal might not mesh well with the proposed optional arguments. We can make it work, because basically |
Beta Was this translation helpful? Give feedback.
-
|
I hope we can do optional args with defaults first then to not block the path forward? |
Beta Was this translation helpful? Give feedback.
-
|
I think optional arguments would would statically in a fashion to labels so they would not be available with functions as values like this. |
Beta Was this translation helpful? Give feedback.
-
|
Would you elaborate on this? |
Beta Was this translation helpful? Give feedback.
-
|
You can only use labels when directly calling module functions, function degrade when you use them as a value so you can no longer use labels with them. pub fn fun(label arg) {
arg
}
pub fn main() {
fun(label: 1) // This works
let x = fun
x(label: 1) // This does not work
} |
Beta Was this translation helpful? Give feedback.
-
|
How would the code generation work for this? pub fn main(f: fn(Int, ..b) -> c) {
f(1, ..)
}I don't know what code we would generate for this. Don't we need to know the arity of |
Beta Was this translation helpful? Give feedback.
-
|
For future readers: There was a big discussion in discord and everybody seemed to come to the conclusion that, yep, this is a serious issue. Getting around it would seem to require either runtime reflection or full program compilation, and would likely complicate long-term plans for a native compile target. (I didn't figure any of this stuff out myself). I've been thinking about it since, and I have come to the conclusion that we are doing row-polymorphism backwards. Instead of having row-polymorphic arguments that accept a range of normal functions, we need to have row-polymorphic functions that can be passed to a range of normal arguments. Flipping this around also means we need to add information to function calls rather than function definitions, so this is maybe going to feel a little closer to the curry keyword. Here is the basic sketch of this idea: do type inference on the structure of functions. Suppose we are working with a function fn foo(f: fn(Int, Int, ..b) -> c, arg: Int) -> fn(..b) -> c {
f(arg + 1, arg - 1, ..b)
}
fn main() {
let b = foo(bar(1, ..), 2)
}The type annotation for fn foo(f: fn(Int, Int) -> k, arg: Int) -> k {
f(arg + 1, arg - 1)
}
fn main() {
let b = foo(bar(1, ..), 2)
}which should be equivalent to the following fn main() {
let b = foo(
fn (arg1, arg2) {
fn (arg3) {
bar(1, arg1, arg2, arg3)
}
}, 2)
}Basically, we don't need to be able to specify greater-than-arity function types if we use a souped-up version of the curry keyword. We just need to be able to automatically break a function into a nested sequence of wrapper functions, each with arbitrary arity. As an bonus, this syntax leaves room for partial application. Is this more tractable? Again, I'm a little weak on theory, so I don't know. I think what I am proposing is upgrading If this works out, applicative-style pipelines could be as simple as fn main(dyn: Dynamic) {
succeed(Person(..))
|> and_map(field("name", string))
|> and_map(field("age", int))
|> and_map(field("address", string))
}I am having trouble working out if this works with more complex arrangements of higher-order-functions, and that worries me a little. It seems like once you start passing these polymorphic types around between multiple functions, it might still require monomorphization somewhere. Would love to hear from the more theory-minded folks weather they think this is true. Edit: Pretty sure this is easily broken by conditionally passing a row-polymorphic function to one of two different functions, each expecting different arty -_-. We could throw a compiler error but it seems like maybe we just should curry things. |
Beta Was this translation helpful? Give feedback.
-
|
Just to write this down here as well: It was also bespoken, how the curring would be introduced to into the language One important point here is, that people coming from cough old, traditional languages do not flee in masses, upon hearing about traditional indian food in the language. Louis suggested to create a syntax to avoid naming the feature with a keyword. I would suggest, to call the keyword simply In both of those ways is it be fine to speak about partial application, in case somebody asks about the feature, without confusing people about cardamom and its relationship to a dead mathematician. |
Beta Was this translation helpful? Give feedback.
-
|
I hope to write down a more theoretical description of the ideas you described @hayleigh-dot-dev and @NthTensor. Did not read along the discussion on Discord though. |
Beta Was this translation helpful? Give feedback.
-
|
TL;DR;
Oké, it took me some time to sit down and write about this. Let me first try to summarise the problem stated by @hayleigh-dot-dev and @NthTensor, and then try to formalise it and pose a solution. Please let me know if anything is unclear or, even more importantly, if I’m describing a solution that doesn’t fit the posed problem. Problem@hayleigh-dot-dev starts describing the problem of decoding pipelines, which in Gleam currently need to be written like this: import gleam/function
let decoder: Decoder(Person) =
succeed(function.curry3(Person))
|> and_map(field("name", string))
|> and_map(field("age", int))
|> and_map(field("address", string))The pain point here is that the From here, the discussion started for syntax to partially apply functions and for syntax to denote some sort of currying. TermsLet me introduce some terms, to make clear what we’re talking about. CurryingIn general, currying is turning a function of arity import function
let calc = fn(a, b, c) {
a * b * c
}
// calc : fn(Int, Int, Int) -> Int
let calc_curried = function.curry3(calc)
// calc_curried : fn(Int) -> fn(Int) -> fn(Int) -> IntAs you can see, we spread all 3 parameters of let calc_always_curried = fn(a) { fn(b) { fn(c) {
a * b * c
} } }or enforce all functions are curried by default (as Haskell, OCaml, Elm, PureScript, etc. do) but there are reasons not to do this, like performance. This is what Gleam and Erlang choose to do. Note the difference in calling the functions: let result = calc(1, 2, 3) // all arguments need to be supplied
let result = calc_curried(1)(2)(3) // all arguments are provided separatelyPartial applicationPartial application is when a function gets supplied fewer arguments than needed to execute. So, if we have a curried function let calc_double = calc_curried(2)
// calc_double : fn(Int, Int) -> IntNote that currying is something that can make partial application possible. The proposition is to add syntax so that we can supply only the first parameter to the uncurried function let calc_double = calc(2, ..)
// calc_double : fn(Int, Int) -> IntThe result is a function which only needs 2 arguments (now really 2). Similarly, we can provide the first two arguments and get a function taking just one argument: let calc_quadruple = calc(1, 4, ..)
// calc_quadruple : fn(Int) -> IntCurried function typeThen, there is another proposal to add some kind of curried function type (not an official term as far as I’m aware of, invented it myself). Note that this is something different from partial application and currying! It is about changing the contract a function exposes to the outer world by giving it another type signature. Take for example, using the proposed syntax, a function which needs a let use_two = fn(f: fn(Int, Int, ..r) -> a, x) {
f(x + 1, x - 1)
}
// use_two : fn(fn(Int, Int, ..r) -> a, Int) -> fn(..r) -> aThe usage of this function would be something like this: let g = use_two(calc, 6)
// g : fn(Int) -> Int
let g = fn(x) { calc(6 + 1, 6 - 1, x) }ProposalLanguageOké, let’s set up our language. We’re using Gleam. All Gleam programs can be simplified to the following grammar: e ::= // Expressions
| x // variables
| let x = e_1; e_2 // let-binding
| fn(x^k) { e } // function abstraction
| f(e^k) // function application
| l // literal
t ::= // Types
| fn(t^k) -> t_0 // function type
| p // primitive typeFirst a note on my grammar. The proposal is to add two pieces to the syntax, one new expression and one new type form. I’ll call the first one partial application and the second one auto currying (also not an official term). I’ll explain why in a minute. e ::= ...
| f(e^n, ..) // partial application
t ::= ...
| fn(t^n, ..t) -> t_0 // auto curryingHere HelpersNext, let me introduce two functions (or actually two family of functions) called
You can think of We can define these functions in pseudo Gleam like this: // partial_n_k takes
// * a function f of arity k
// * n arguments e_1, ..., e_n
// it returns a function of
// * the remaining k-n arguments y_n+1, ..., y_k
// and applies the first k to f
fn partial_n_k(f, e^n) {
fn(y^k-n) { f(e^n, y^(k-n) }
}
// curry_n_k takes
// * a function f of arity k
// it returns a function which
// * first takes n arguments x_1, ..., x_n
// * then the remaining arguments x_n+1, ..., x_k
fn curry_n_k(f) {
fn(x^n) { fn(y^k-n) { f(x^n, y^(k-n) } }
// this is actually equivallent to:
// fn(x^n) { partial_n_k(f, x^n) }
}Now, my hypothesis is that, after type inference, we can automatically insert ExamplesPartial applicationWhen we have the partial application from the example above: let calc_quadruple = calc(1, 4, ..)we know that:
So calc(1, 4, ..) ~~> partial_2_3(calc, 1, 4)(Read Auto curryingFrom the example above: let use_two = fn(f: fn(Int, Int, ..r) -> a, x) {
f(x + 1, x - 1)
}
let g = use_two(calc, 6)We know that:
So calc ~~> curry_2_3(calc)And therefore use_two(calc, 6) ~~> use_two(curry_2_3(calc), 6)The signature of fn(fn(Int, Int, ..r) -> a, Int) -> fn(..r) -> a
~~>
fn(fn(Int, Int) -> k, Int) -> kEdge casesMaybe you’ll already have the feeling that some laws should apply to What if
|
Beta Was this translation helpful? Give feedback.
-
|
Great write up! Thank you very much @timjs ! One thing to consider which hasn't been touched on here is that one of our main goals is to have good interop with Erlang etc in both directions, so Gleam APIs should always be easy to use from those languages. The general rule is that the generated Gleam code should not be easily distinguishable from hand-written Erlang or Elixir. This would be the first feature where the caller needs to do some extra contextual work order to call the Gleam function, which would make it a lot harder to use without the Gleam compiler automatically doing this housekeeping, and it would very clearly not be normal Erlang code. This might be acceptable, but we need to think about how we would communicate to Erlang/Elixir/etc users how to call these functions, and anything else we need to do in order to provide them with a good UX. On use + pipes
It should not do that, at least not now. We always introduce the minimal useful version of a feature so that we can learn about it. It is easy to add, it is had to subtract. It's possible that we may add more a sophisticated I'm not yet convinced that making it more complex in this way will result in Gleam code being easier to work with. There is a nice property with the current design that the function to which control is yielded is the one closest to the |
Beta Was this translation helpful? Give feedback.
-
|
Lets look at some examples of erlang as generated by this proposal. I will assume Partial application list.map(foo("test", ...), list)
>> list.map(partial_1_2(foo, "test"), list)ultimately generates something like this, right? lists:map(fun (V) -> foo("test", V) end, List).I've had cause to write stuff like that once or twice in my limited time with Erlang. Its always pretty simple. In my mind, partial application fits with hand-written Erlang. I also don't see a situation where someone could be forced to use partial application, so I don't think it can 'infect' non-gleam code with foreign patterns either. Currying is not as nice. Using your example pub fn main(f: fn(Int, ..b) -> c) {
f(1)
}should translate into something as simple as main(F) ->
F(1).but its up to non-gleam users to ensure pub fn succeed(a: a) -> Decoder(a) {
fn(_dynamic) {
Ok(a)
}
}
pub fn then(decode: Decoder(a), f: fn(a) -> Decoder(b)) -> Decoder(b) {
fn(dynamic) {
case decode(dynamic) {
Ok(a) -> f(a)(dynamic)
err -> err
}
}
}
pub fn and_map(decode_f: Decoder(fn(a, ..b) -> c), decode_a: Decoder(a)) -> Decoder(fn(..b) -> c) {
use f <- then(decode_f)
use a <- then(decode_a)
succeed(f(a))
}
pub fn and_finally(decide_f: Decoder(fn(a) -> b), decode_a: Decoder(a)) -> Decoder(b) {
use f <- then(decode_f)
use a <- then(decode_a)
succeed(f(a))
}We might use this to parse a dynamically typed object fn decoder() -> Decoder(Person) {
succeed(Person)
|> and_map(field("name", string))
|> and_map(field("age", int))
|> and_finally(field("address", string))
}and this should (ideally, using some hand wavy type unification) de-sugar to the following fn decoder() -> Decoder(Person) {
and_finally(
and_map(
and_map(
succeed(
curry_1_2(
curry_2_3(Person)
)
),
field("name", string)
),
field("age", int)
),
field("address", string)
)
}and translate (I believe) to decoder() ->
and_finally(
and_map(
and_map(
succeed(
fun (A1) ->
fun (A2) ->
(fun (B1, B2) ->
fun (B3) ->
{person, B1, B2, B3}
end
end)(A1, A2)
end
end),
field("name", string)),
field("age", int)),
field("address", string)).This is not sane or normal Erlang, which is unfortunate. I still don't think this would often end up preventing erlangists from writing idomatic code, as you mostly need currying to do type shenanigans. I mean, there's really no reason to use the By the way, as you can see from this example, currying the same function multiple times results in a redundant function call, similar to what @inoas and @timjs discussed with ...
fun (A1) ->
fun (A2) ->
fun (B3) ->
{person, A1, A2, B3}
end
end
endEdit: Fixed the code for the currying example. |
Beta Was this translation helpful? Give feedback.
-
|
Sorry for me being absent for a long time. Still had on some list to reply on this!
You're very welcome :-)
I think this feature exactly matches the needs for good interoperability with Erlang, as the resulting Erlang code for functions using auto currying would be the same. For example, the functions So, the current Gleam code: pub fn and_map(decode_f: Decoder(fn(a) -> b), decode_a: Decoder(a)) -> Decoder(b) {
use f <- then(decode_f)
use a <- then(decode_a)
succeed(f(a))
}now generates the following Erlang (generated with Gleam 0.28.3): and_map(Decode_f, Decode_a) ->
then(Decode_f, fun(F) -> then(Decode_a, fun(A) -> succeed(F(A)) end) end).and this would not be different when changing the signature of Only Gleam itself will make use of the special signature with auto currying when calling such a function from the Gleam side. Going back to the implementation @hayleigh-dot-dev gave as motivation for this feature, currently one should write in Gleam: fn decoder() -> Decoder(Person) {
succeed(function.curry3(fn(name, age, address) { Person(name, age, address) })
|> and_map(field("name", string))
|> and_map(field("age", int))
|> and_map(field("address", string))
}which generates the following Erlang code (also generated with Gleam 0.28.3): decoder() ->
_pipe = succeed(
gleam@function:curry3(
fun(Name, Age, Address) -> {person, Name, Age, Address} end
)
),
_pipe@1 = and_map(_pipe, field(<<"name"/utf8>>, fun string/1)),
_pipe@2 = and_map(_pipe@1, field(<<"age"/utf8>>, fun int/1)),
and_map(_pipe@2, field(<<"address"/utf8>>, fun string/1)).So the generated Erlang code would not be non-idiomatic because of auto currying. One could say it already is non-idiomatic because of using pipes and because of enforcing currying by the API. That is, because Using the auto currying feature and the API @NthTensor gave in the previous post, in Gleam, instead of manually adding the fn decoder() -> Decoder(Person) {
succeed(Person) // magic happens here!!
|> and_map(field("name", string))
|> and_map(field("age", int))
|> and_finally(field("address", string))
}and Gleam would automagically insert the appropriate amount of curried function parameters. With the optimisation of folding -spec decoder() -> fun((binary()) -> {ok, person()} | {error, failure()}).
decoder() ->
_pipe = succeed(
fun(Name) -> fun(Age) -> fun(Address) -> % magic happens here!!
{person, Name, Age, Address}
end end end
)
),
_pipe@1 = and_map(_pipe, field(<<"name"/utf8>>, fun string/1)),
_pipe@2 = and_map(_pipe@1, field(<<"age"/utf8>>, fun int/1)),
and_map(_pipe@2, field(<<"address"/utf8>>, fun string/1)).which is hardly different from the previously generated code. Btw. One can already write: fn decoder() -> Decoder(Person) {
succeed(function.curry3(Person))
|> and_map(field("name", string))
|> and_map(field("age", int))
|> and_map(field("address", string))
} |
Beta Was this translation helpful? Give feedback.
-
|
I've been playing around with this, and one thing that dosn't seem to have been talked about is how what we are calling "auto-currying" can be unexpectedly permanent when returning functions. The following example wraps fn curry_n(num: Int, fun: fn(a, ..r) -> k) -> fn(a) -> fn(..r) -> k {
case num {
0 | 1 | 2 -> fun
n -> f(x) { curry(n-1, fun(x)) }
}
}(This would probably raise a pretty confusing type error if fn curry1(fun: fn(x, ..r) -> k) { fun }
fn add2(x, y) { x + y }
fn main() {
curry1(add2)(1)(2)
}Here This makes we wonder if type inference would allow us to replace |
Beta Was this translation helpful? Give feedback.
-
|
Yes, that's a consequence of this approach 😞 You lose principle types and a type annotation changes the meaning of a program. A solution could be, as you say, to add some keyword of sigil to curry a function. |
Beta Was this translation helpful? Give feedback.
-
|
ReScript recently released a major update which changes the language to be uncurried by default rather than curried. They introduced similar syntax, |
Beta Was this translation helpful? Give feedback.
-
|
Looks like they're using it for partial application rather than currying, but pretty close |
Beta Was this translation helpful? Give feedback.
-
The problem
In Elm it's common to have these pipe-friendly APIs for things like decoding, parsing, and validating. A hypothetical decoder API might look something like:
The basic format involves starting with some constructor function that takes
narguments, and then chaining a bunch of operations withnnumber ofand_mapsto slowly piece together something.Just using pipes on their own is insufficient because we're in some other "context", in this case a
Decoder, or aParser, or something else. The magic happens inand_map. The type looks like this......or in gleam syntax...
This works in Elm (and others) specifically because Elm's functions are automatically curried. That is, a function
a -> b -> cis actually a chain of single-argument functionsa -> (b -> c). In Gleam that means instead offn(a, b) -> cwe would havefn(a) -> fn(b) -> c.We can produce a similar API in Gleam today, with the help of the curry utilities found in
gleam/function...These APIs are very nice to consume, and have some advantages over alternative ones that might make use of
.then, but we hit some resistance in Gleam because the explicit currying step. Currently there are utilities to curry functions up to six arguments:curry2,curry3, ...curry6.This explicit currying is clunky and confusing. For those new to FP the word "curry" probably sooner conjures images of a delicious meal rather than some single-argument functions, and inevitably begs the question "why can't I just write
succeed(fn(name, age) { ... }).The answer to that question is simple. We don't have a way to partially supply one (or some) argument(s) to a function.
The proposal
And with that I'd like to present a way to achieve that. I propose we re-use the existing spread syntax (
..) as a way of partially applying a function. Here is a minimal example...Although not 1:1, this approach to partial application has parallels with existing usage of the spread syntax:
[ x, ..rest ]Foo(..foo, bar: x)The above example shows the syntax for partially applying function calls. The second part of this proposal is an extension of the type system to introduce the idea of "a function with at least this many arguments".
Consider again the type of
and_mapwe saw earlier...This required currying to work nicely in the pipe, because we need that
bto also be a function. A revised version ofand_mapusing the proposed spread syntax becomes...The complete implementation could then be...
Now we can write...
Because the spread always implies there are additional arguments, unlike the Elm version we need a second function to act as the terminator in this style of pipe API. For that, we can re-use the initial type of
and_mapand just rename it......and with that we are left with...
Technical details
This essentially involves treating functions as a separate Kind, and introducing a form of row polymorphism to allow us to express the idea of "at least
narguments" in a type annotation and use function application to eliminate arguments from a type.If we look instead at records, this concept may make a bit more sense. A type like...
...is a record with the field
x : Intandradditional fields. This means all the following record types would unify with the above...We run into some additional constraints that seem practical to impose for our function version of row polymorphism. The "no additional rows is valid" case makes less immediate sense for functions. Given the row polymorphic function type...
...it feels like
f(Int) -> Intshould not unify here. Similarly, order must become significant for obvious reasons.Alternatives
@lpil and I have been thinking about this problem on-and-off for a while now. The current decoder API supplies a bunch of
decode{N}functions, and an older version of a parser package I have provided a bunch ofsucceed{N}functions in a similar fashion. This places a hard limit on the arity of the functions you can provide in these APIs.Another idea is to introduce a language construct for automatic currying, with a
currykeyword. Making this a keyword/operator means we can side-step the type system and have a single way to curry arbitrary arity functions rather thancurry2,curry3, and so on. This has the same problem as today, where users are forced to what currying even is before they can consume some API.My thoughts are a little scattered on this. I have a good idea of what it would look like / how it would work in my head, but I've struggled to put it in writing. Thoughts, comments, and questions all very much welcome: I will do my best to clear things up!
Beta Was this translation helpful? Give feedback.
All reactions