search

eclipse-archived / golo-lang

Golo - a lightweight dynamic language for the JVM.
http://golo-lang.org/
Eclipse Public License 2.0
476 stars 91 forks source link

Autocurry and partialization #344

Open yloiseau opened 8 years ago

yloiseau commented 8 years ago

On curry and partialization

reflections on the idea suggested in https://github.com/eclipse/golo-lang/issues/326#issuecomment-169293658

What we have

Manual partialization

function add = |a, b, c| -> a + b + c

add("a", "b", "c") == "abc"
add(c="a", a="b", b="c") == "bca"

let addA = ^add: bindTo("a")
addA("b", "c") == "abc"

let addB = ^add: bindAt(1, "b")
addB("a", "c") == "abc"

let addC = ^add: bindAt("c", "c")
addC("a", "b") == "abc"

let addBC = ^add: insertArguments(1, "b", "c")
addBC("a") == "abc"

let l = list["a", "b", "c", "d"]: map(|x| -> ^add: bindTo(x))
l: get(2)("d", "e") == "cde"

let f = ^add: insertArguments(0, 2, 20)
          : andThen(^add: insertArguments(0, "The answer", " is "))
f(20) == "The answer is 42"

or fluent variant:

augment gololang.FunctionReference {
  function fallback = |this, name, args| -> this: bindAt(name, args: get(0))
}

function add = |a, b, c| -> a + b + c

let addA = ^add: a("a")
let addB = ^add: b("b")
let addC = ^add: c("c")
let addBC = ^add: b("b"): c("c")
function add = |a| -> |b| -> |c| -> a + b + c

add("a")("b")("c") == "abc"

let addA = add("a")
let addB = |a| -> |c| -> add(a)("b")(c)
let addC = |a| -> |b| -> add(a)(b)("c")
let addBC = |a| -> add(a)("b")("c")

let l = list["a", "b", "c", "d"]: map(^add)
l: get(2)("d")("e") 

let f = add(2)(20): andThen(add("The answer")(" is "))

With this (simplified) decorator:

function curry = |func| -> match {
  when func:type():parameterCount() < 2 then func
  otherwise ^_curried_: bindTo(func): asVarargsCollector(objectArrayType!())
}

local function _curried_ = |func, args| -> match {
  when args: size() == func:type():parameterCount() then func: invoke(args)
  otherwise curry(func: insertArguments(0, args))
}

we have:

@curry
function add = |a, b, c| -> a + b + c

add("a", "b", "c") == "abc"

let addA = add("a")
let addAB = add("a", "b")
let addB = curry(|a, c| -> add(a, "b", c))

let list["a", "b", "c", "d"]: map(^add)
l: get(2)("d", "e")

let f = add(2, 20): andThen(add("The answer", " is "))

When (if) macro will work, it should be possible to define a macro transforming

function add = |a, b, c| -> a + b + c

into

function add = |a, b, c| -> a + b + c
function add = |a, b| -> |c| -> a + b + c
function add = |a| -> |b, c| -> a + b + c

and thus:

add("a", "b", "c") == "abc"
add(c="a", a="b", b="c") == "bca"

let addA = add("a")
let addAB = add("a", "b")
let addB = |a, c| -> add(a, "b", c))
# or
let addB = ^add\2: bindAt(1, "b")
let addC = ^add\3: bindAt("c", c")

let list["a", "b", "c", "d"]: map(^add)
l: get(2)("d", "e")

let f = add(2, 20): andThen(add("The answer", " is "))

These solutions don't exclude the previous ones.

Autocurry at resolution time

When looking up the function at runtime, if only a function with more parameter than the call site is found, a partialized version can be returned instead of failing.

function add = |a, b, c| -> a + b + c

add("a", "b", "c") == "abc"
add(c="a", a="b", b="c") == "bca"

let addA = add("a")
let addAB = add("a", "b")
# or
let addAB = ^add: insertArguments(0, "a", "b")

let addB = |a, c| -> add(a, "b", c))
# or
let addB = ^add: bindAt(1, "b")
# or, if made named arguments aware
let addB = add(b="b")

let list["a", "b", "c", "d"]: map(^add)
l: get(2)("d", "e")

let f = add(2, 20): andThen(add("The answer", " is "))

For the implicit aspect, we can imagine a way to activate the feature modulewise, for instance a special comment or a dummy import that configure the runtime. For instance

#-*- with: autocurry -*-#

adding a meta flag in the module, inspected by the runtime.

Partialization with special placeholders

Adding a special call syntax, with a placeholder symbol, that returns a partialized version of the function. This can be done at runtime, or as a syntactic sugar expanded to normal partialization at compiletime.

function add = |a, b, c| -> a + b + c

add("a", "b", "c") == "abc"
add(c="a", a="b", b="c") == "bca"

let addA = add("a", ?, ?)
let addAB = add("a", "b", ?)
# or
let addAB = ^add: insertArguments(0, "a", "b")

let addB = add(?, "b", ?))
# or
let addB = ^add: bindAt(1, "b")

let addBC = add(?, "b", "c")

let list["a", "b", "c", "d"]: map(|x| -> add(x, ?, ?))
l: get(2)("d", "e")

let f = add(2, 20, ?): andThen(add("The answer", " is ", ?))

pros and cons: same as manual partialization, since it can be seen just as syntactic sugar. Plus:

We can already do a lot of things. The proposed changes (autocurry or special call syntax) would only allow a less verbose use, more specifically in composition and HOF.

I'm not fixed yet. The special syntax is clear and more explicit, but the autocurry is easier to use when applying in HOF.

yloiseau commented 8 years ago

ping @jponge @franckverrot @danielpetisme

franckverrot commented 8 years ago

Great detailed explanations here! :heart_eyes:

I'm not so fond of the special placeholders (being ? or _) if I'd need to change (add or remove a special placeholder) all over the place when my initial method signature changes. Autocurrying at resolution time looks great. :+1:

yloiseau commented 8 years ago

@franckverrot even with autocurry, if your signature changes, say you add a final parameter, you'll need to change the calls anyway, or you'll end up with partialized functions everywhere :smile:

jponge commented 8 years ago

For me the biggest issue of auto-currying is that it hides errors, since function calls either evaluate if the right number of parameters are present, or else it returns a partially-applied function if less arguments are given. That's a blocker for me :wink:

I'm very fond of the placeholder option. It is explicit and in line with what other languages do.

franckverrot commented 8 years ago

@yloiseau partial functions everywhere is just fine. I :heart: Haskell for that.

yloiseau commented 8 years ago

@franckverrot I agree. I'm also more inclined to the autocurry solution.

But I was answering your remark that you need to add placeholders if signature changes. The fact is that even with autocurry you have to change the code if the signature change, but at the final call side, not the partializing one. For instance given:

# String × String × String → String
function foo = |a, b, c| -> "<" + a + b + c + ">"

say you partialize foo, whatever the way:

# fix a and b
# String → String
let f = ^foo: bindTo("a"): bindTo("b")

# fix a
# String × String → String
let g = ^foo: bindTo("h") 
# fix a and b
# String → String
let f = foo("a", "b", ?)

# fix a
# String × String → String
let g = foo("h", ?, ?) 
# fix a and b
# String → String
let f = foo("a", "b")

# fix a
# String × String → String
let g = foo("h")

NOTE: with placeholders, it's easier to partialize on other parameters. Compare

let h = foo(?, "b", ?)

and

let h = |a, c| -> foo("b")

(and since it's a binding and not a new function, we guaranty parameter names stay the same) :smile:

Anyway, we can now do things such as:

println(list["x", "y"]: map(f): reduce("z", g)  
# <h<hz<abx>><aby>>

Imagine that now, you change foo signature, say you add a parameter for the suffix:

# String × String × String × String → String
function foo = |a, b, c, suff| -> "<" + a + b + c + suff

The placeholder form no longer works, since foo("a", "b", ?) would raise an exception that we don't have a 3 param function named "foo".

Without changing the code, the curry version would indeed partialize fine, but:

# fix a and b
# String × String → String
let f = foo("a", "b")

# fix a
# String × String × String → String
let g = foo("h")

The map works thanks to curry, and we thus have a list of String → String functions:

list["x", "y"]: map(f)
# list[f1, f2] = list[|v| -> "<abx" + v, |v| -> "<aby" + v]

Reducing it with : reduce("z", g), we have g(g("z", f1), f2), that is

g(g("z", |v| -> "<abx" + v), |v| -> "<aby" + v)

This would fail at compile time in Caml, thanks to the strong type system, since we would have g : String → String → String → String and we would have needed g : String → (String → String → String) → String. Same in Haskell, as functions does not implement Show.

Actually, g and the mapped list can be seen as 

let g =  |b, c| -> |suff| -> "<h" + b + c + suff
let l = list[|v| -> "<abx" + v, |v| -> "<aby" + v]

so l: reduce("z", g) would work in Golo (with autocurry)! 

l: reduce("z", g)
g(g("z", |v| -> "<abx" + v), |v| -> "<aby" + v)
g((|b, c| -> |suff| -> "<h" + b + c + suff)("z", |v| -> "<abx" + v), |v| -> "<aby" + v)
g(|suff| -> "<hz" + (|v| -> "<abx" + v): toString(), |v| -> "<aby" + v)
|suff| -> "<hz" + (|suff| -> "<hz" + (|v| -> "<abx" + v): toString()): toString() + (|v| -> "<aby" + v): toString())

The functions in the lists are converted into Strings, and joined, and we get a function taking the suffix, the added parameter that was not partialized. Indeed (actuall working code):

let g =  |b, c| -> |suff| -> "<h" + b + c + suff
let l = list[|v| -> "<abx" + v, |v| -> "<aby" + v]

println(l: reduce("z", g): invoke("k"))

gives

<hFunctionReference{handle=MethodHandle(Object)Object, parameterNames=[suff]}FunctionReference{handle=MethodHandle(Object)Object, parameterNames=[v]}k

This is what @jponge had in mind. No fail, just the wrong behavior.

If we want the same behavior as before, We have to change the partialization. The placeholder form is now:

# fix a, b and suffix
# String → String
let f = foo("a", "b", ?, ">")

# fix a and suffix
# String × String → String
let g = foo("h", ?, ?, ">")

and the curry one:

# fix a, b and suffix, can't be done directly with autocurry
# String → String
let f = |x| -> foo("a", "b", x, ">")

# fix a and suffix, can't be done directly with autocurry
# String × String → String
let g = |b, c| -> foo("h", b, c, ">")

If we added a parameter for prefix, this would have been more readable for the autocurry, leading to:

let f = foo("<", "a", "b", ?)
let g = foo("<", "h", ?, ?)

vs.

let f = foo("<", "a", "b")
let g = foo("<", "h")

An other solution is to change the way the functions are called to partialize the new parameter when called, e.g.

list["x", "y"]: map(f: bindAt("suff", ">")): reduce("z", g: bindAt("suff", ">")))

So, to conclude on your previous remark, with both methods you need to change your code if the function signature change, either by adding a placeholder or changing the calls, or by adding a partializing argument.

Actually, the more I think about it, the more I like the placeholder approach, even if I find the autocurry more natural and elegant. The only drawback of placeholders is that the previous mapping case can't be done:

let foo = |a, b| -> a + b

list["x", "y"]: map(foo)

fails with placeholders, but gives a list of unary functions with curry. To do it without curry, we have to use a lambda:

let foo = |a, b| -> a + b

list["x", "y"]: map(|a| -> foo(a, ?))
# or
list["x", "y"]: map(|a| -> foo: bindTo(a))

However, this case can be covered by the decorator:

list["x", "y"]: map(curry(foo))

I'm really not fixed…

yloiseau commented 8 years ago

Moreover, the placeholder approach could be compile time syntactic sugar…

Note that the solutions are not mutually exclusives :smile:

yloiseau commented 8 years ago

Hum... no it could not be compile time syntactic sugar :disappointed: We must do the same lookup as for functions, and thus foo("a", ?) can't be replaced by ^foo: bindTo("a") since the '^' does not lookup in imported modules (we must fully qualify... see #249 ), while call does. If #249 is fixed (probably by the upcoming function resolution refactoring of #326 ), then the placeholders could be replaced by binding at runtime (not sure).

yloiseau commented 8 years ago

Regarding methods, it would be nice if, given an object with a :foo(x, y) method

let f = o: foo(?, "a")

would be equivalent to 

let f = |x| -> o: foo(x, "a")

and even

let f = ?: foo("z", "a")
let g = ?:foo(?, "w")

equivalent to

let f = |o| -> o: foo("z", "a")
let g = |o, x| -> o: foo(x, "w")

In this case, we have a syntax problem since "?:" will collide with the elvis operator... :cry:

yloiseau commented 8 years ago

As a POC, I just hacked a macro that implements the placeholder approach, but with a $ since it must be a valid Golo identifier (it could have been _)

Actually, it's more an implementation of the similar Scala _ feature to create lambdas.

Let's name it f for now, just to show some example:

f(($1 + $4) * ($2 + $3))

is expanded into

|$1, $2, $3, $4| -> ($1 + $4) * ($2 + $3)

All variable beginning with $ are used as lambda parameter, in the name order (hence $1, $2...) not in appearance order. I choose this notation for the obvious link to shell parameters, but anything identifiable (i.e. with a specific prefix or suffix) and sortable can be used. Here I fixed a $-prefix (defined in the macro), and number, but I might use $a, $b... as long as lexicographical order is parameter order.

The tag $ has a special meaning only in the scope of the macro (no change to the language).

nice!

We can repeat parameters, and use captured values as well:

let z = 2
let bar = f(($1 * z) + $1)

is expanded into

let z = 2
let bar = |$1| -> ($1 * z) + $1

cool!

We can obviously map then:

list[1, 2, 3, 4]: map(f($ + 1))

(note that with only 1 parameter, $ can be used alone, since no sorting is involved)

And now for the partializing aspect:

let baz = f(  addAll($2, "b", "c", $1)  )
let hello = f(  $1: say("Hello", $2)  )

will expand to:

let baz = |$1, $2| -> addAll($2, "b", "c", $1)
let hello = |$1, $2| -> $1: say("Hello", $2)

Note that it works on objects too, and we can swap parameters! :tada:

It would be interesting to polish it and integrate it into the future macro std lib.

If so, I need some opinions on:

Any thoughts @jponge @franckverrot ? /cc @Artpej @danielpetisme

jponge commented 8 years ago

Doing it as a macro has some advantages, since macros are here for that and it saves the compiler from dealing with another case.

Somehow I still find it easier to read something macro-less for partial functions, like:

let adder = |x, y, z| -> x + y + z
let plus1and2 = adder(_, 1, 2)

Now if you go with macros and getting back to your questions:

  1. $ is ok if we can do $1, $2, $abc, $_name, etc. Still, note that $ is a valid prefix in current Golo.
  2. On the macro name:
    • how about partial?
    • 1 letter is perhaps too short
    • unicode is a no-go :smiling_imp:
yloiseau commented 8 years ago

In the current macro POC, the placeholder argument can be anything that starts with $, as long as they sort in the intended order. For instance f($a + $c - $b) is expanded as |$a, $b, $c| -> $a + $c - $b.

The macro approach does not introduce a new keyword or special symbol. I used $ exactly because it's a valid prefix (and for the shell analogy), and it still is.

The unicode name was for kidding (although I like lst: map(λ($ + 1))) :smile: