Proposal: n-ary partial application

[dhil]

This proposal is about providing lightweight syntax for partial application of n-ary function application for n > 1.

What: Partial application

Links supports partial application of curried functions, e.g.

sig pow : (Int) -> (Int) ~> Int
fun pow(r)(n) {
  if (n == 0) 1
  else r * pow(r)(n-1)
}

links> var pow2 = pow(2);
pow2 = fun : (Int) ~> Int

The application pow(2) returns a new function, which we bind to pow2, this function returns powers of 2, e.g.

links> pow(2);
4 : Int
links> pow(3);
8 : Int

We can also use pow to make a squaring function

links> var square = curry(flip(uncurry(pow)))(2);
fun : (Int) ~> Int
links> square(2);
4 : Int
links> square(4);
16 : Int

Arguably in Links the natural definition of pow makes use of a binary function, i.e.

sig pow' : (Int, Int) ~> Int
fun pow'(r, n) {
  if (n == 0) 1
  else r * pow(r, n - 1)
}

However, Links has no syntactic support for partial applying a binary (or in general n-ary) function. The programmer must write an explicit function abstraction, e.g.

links> var square' = fun(r) { pow'(r, 2) };
square' : fun : (Int) ~> Int

Motivation

Partial application is useful in higher-order programming. As a simple motivating example suppose we are given a list of integers and asked to 1) interpret as exponents to compute powers of two, 2) square the integers. Partial application in Links provides an elegant solution to the first problem:

links> map(pow(2), [1, 2, 3, 4]);
[2, 4, 8, 16] : [Int]

To solve the second task using pow we need to either flip the curried parameters of pow or explicitly abstract over it, i.e.

links> map(curry(flip(uncurry(pow)))(2), [1, 2, 3, 4]);
[1, 4, 9, 16] : [Int]
links> map(fun(r) { pow(r)(2) }, [1, 2, 3, 4]);
[1, 4, 9, 16] : [Int]

(In the absence of a sufficient clever optimising compiler, the latter is more efficient.)

As remarked in the previous section, the natural definition of pow in Links would be in terms of a binary function. In general for any n-ary functions such that n > 1 the programmer needs to explicitly abstract over the application.

I propose to add support for "anonymous arguments", providing syntax for partial application of n-ary functions, e.g.

links> map(pow'(2,_), [1,2,3,4])
[2, 4, 8, 16]
links> map(pow'(_,2), [1,2,3,4])
[1, 4, 9, 16] : [Int]

Here _ is an anonymous argument. So pow'(2,_) is intended to be equivalent to pow(2), whilst pow'(_,2) is intended to be equivalent to fun(r) { pow(r)(2) }.

Concrete syntax

The token _ should be allowed to be appear in argument position.

Semantics

The argument _ should be interpreted as a "hole", that needs to be abstracted over. Thus, writing f(x,_,z) should be semantically equivalent to introducing an explicit function abstraction for the second argument, i.e. fun(y) { f(x,y,z) }. In other words, f has been partially applied in its first and third argument positions.

The argument _ should be allowed to appear multiple times in an application in any argument position. For simplicity we could allow it to be used as an argument for any n-ary for n > 0 rather than n > 1. Even though the case when n = 1 is degenerate.

Implementation work

This proposal can be realised as a front-end desugaring pass.

The following translation illustrates the essence of the intended implementation:

  [| f(_,...,_) |]
= fun(x1)...(xN) { f(x1,...,xN) }

This translation is obviously inadequate, since it does not account for non-anonymous arguments. The general translation will have to inspect each sugared argument to check whether it is anonymous, and at the same time build up the desugared argument list, something along the lines of following:

  [| f(p1,...,pN) |]
= TRANSFORM(f;p1,...,pN;[])

where
  TRANSFORM(f; x :: ps; ps') = TRANSFORM(f; ps; ps' ++ [x])
  TRANSFORM(f; _ :: ps; ps') = fun(x) { TRANSFORM(f; ps; ps' ++ [x]) }, x fresh
  TRANSFORM(f;      []; ps') = f(ps')

We can make the transformation more general by not restricting the term in function position to be a variable.

Other remarks

I think this project could make a good initial internship or student project.

[jamescheney]

You've designed this such that pow(_,_) would desugar to something of type (Int) -> (Int) -> Int, which is nice because the desugaring is more compositional but a bit counterintuitive. In Scala for example pow(_,_) would have type (Int,Int) => Int. Is there a reason to prefer one strategy over the other (other than that the curried version will certainly confuse Scala programmers :)?

[SquidDev]

Just wondering the expected behaviour of non-hole arguments with side effects?

For instance, I believe pow({ println("foo"); 2 }, _) would desugar to fun(x) { pow({ println("foo"); 2}, x) }, and so print a message every time the resulting function is called.

It's not entirely clear to me what the expected behaviour is here, and both seem like they could be confusing for different people. I'm afraid I haven't used Scala, so don't know what they do there. Scheme allows both behaviours with cut and cute macros, though I realise that's less suitable here.

[dhil]

Admittedly, I hadn't thought much about the implications of the case when all arguments are anonymous. E.g. consider a ternary function f : A * B * C -> D

Scala approach: f(_,_,_) : A * B * C -> D, this is an identity. My approach: f(_,_,_) : A -> (B -> (C -> D)), this is the result of currying f, which is different to partial application.

My interests are partial application, rather, than currying. I suppose in a purely functional setting these two approaches are isomorphic, but not necessarily so in an effectful setting. I suppose this is a reason to prefer the Scala-approach.

@SquidDev

Just wondering the expected behaviour of non-hole arguments with side effects?

For instance, I believe pow({ println("foo"); 2 }, _) would desugar to fun(x) { pow({ println("foo"); 2}, x) }, and so print a message every time the resulting function is called.

This is a great question. My primary motivation was pure higher-order programming, thus I did not give the question of side effects much thought. I suppose in the "spirit of partial application" I'd expect the effect to played once at closure creation time; for example by hoisting out non-value arguments along the lines of

 [| pow({ println("foo"); 2 }, _) |]
= var v = {println("foo"); 2 }; fun(x) { pow(v, x) }

However, in Scala the side effect is delayed until all arguments have been supplied.

---

As a side remark, I can note that I plan to put together another proposal to redefine the semantics of inline block expressions { ... } to mean nullary function abstraction, i.e. a thunk or suspend computation. This is convenient syntactic sugar for effectful programming. A while ago I did a quick survey of the Links programs that I have access to, and only a few make use of the inline block expressions (I turn out to be the primary user).

[dhil]

Having slept on it, I am now converging towards adopting the Scala-approach. I think shrinking the domain is the better approach in an effectful setting. I think my suggested approach conflates partial application and currying, which was not my original intent. I suppose the big question is whether side-effects should be performed when a partial application occur, or after all arguments have been supplied. With curried functions side-effects naturally happen during partial application.

[jamescheney]

We already check that things are (generalized) values in other places, for type inference, so perhaps we could check that if underscores appear in a function call then all of the arguments are either underscores or generalized values, i.e. no side effects. Scala doesn't need to worry about this because it does local type inference rather than let-bound, and requires type parameters to be given explicitly in function definitions, so there is no value restriction issue.

I suppose the counterargument is that if you want the side-effecting operations to be performed first, then this stops you from using the partial application syntax at all. But this (a) doesn't stop you doing the usual pure functional programming things and (b) I think it may be a feature to require writing an explicit lambda-abstraction making the fact you want the side effects to happen once per call rather than a bug.

[dhil]

A little experiment with side effects and partial application in Scala 2.11.12

scala> def abcd(a : Unit, b : Unit, c : Unit, d : Unit) : Unit = { () }
abcd: (a: Unit, b: Unit, c: Unit, d: Unit)Unit

scala> val acd = abcd(_ : Unit, print("b"), _ : Unit, _ : Unit);
acd: (Unit, Unit, Unit) => Unit = <function3>

scala> val ac = acd(_ : Unit, _ : Unit, print("d"));
ac: (Unit, Unit) => Unit = <function2>

scala> val c = ac(print("a"), _ : Unit);
c: Unit => Unit = <function1>

scala> c(print("c"));
cadb