[nem-en] function partial application

[Michal Moskal]

On 10/5/05, Philippe Quesnel <philippe.quesnel at gmail.com> wrote:
>  here's the 'simple' example:
>  (assuming a func 'inc' that does +1 on a value)
>
>  ----------------
>  -- apply func 'f' twice on x
>  twice f x = f (f x)
>
>  twice twice inc 0 == 4
>  twice twice twice inc 0 == 16
>  twice twice twice twice inc 0 == 65536
>  ---------------
>
>  while trying to figure out exactly how this works,
>  I realized it's a bit more complicated than might be expected at 1st.
>  (I think it works because of partial function application, (ie function
> application is left associative ! ?) )

Yes, it is.

>  .. anyways .. how would this be done in Nemerle ?
>  is it possible to have a solution 'as powerfull' as the above one ?
>
>  (without a thownsand parentheses & cie)

I guess the simplest possible solution would be something along the lines of:

def twice['a] (f : 'a -> 'a) {
  fun (x) { f (f (x)) }
}

def inc = 1 + _;

System.Console.WriteLine (twice (twice) (inc) (0));
System.Console.WriteLine (twice (twice) (twice) (inc) (0));
System.Console.WriteLine (twice (twice) (twice) (twice) (inc) (0));

There are a few points worth a note here. First is the type annotation on
twice. It is required because the Nemerle compiler does not yet generalize
inferred types of local functions and it is not clear it is possible
at all. The type system in Nemerle includes class based object oriented
types.  It is known not to work well with parametric polymorphism. I also
believe that except for porting these nice FP examples, polymorphic local
functions are not very useful. OTOH I dare to say our type inference
algorithm performs well in more common situations, like member access.

Inside the twice definition we see another monster. In most functional
languages the construction:

  some_fun x y = expr

is translated to:

  some_fun = \x. \y. expr

(where \ stands for lambda, or fun in Nemerle).

Nemerle does not support this kind of stuff, because it generates functions
in uncurried form (that is functions returning functions, that can be
later applied to the next argument). This is not very efficient in Nemerle
(though if you are willing to use Haskell, this shouldn't matter ;-).
Moreover the application looks ugly:

  some_fun (1) (2)

because function calls in Nemerle always require parentheses. This is
also why calls to twice require parentheses. Please note that function
application in Nemerle is still left-associative.

Recently we introduced a special notion for supporting the more common
uses of partial application (specializing functions to be precise). You
can see it in inc definition, that translates to:

  def inc = fun (x) { 1 + x }

this slightly is more general than partial application in ML/Haskell,
because it allows to specify any set of missing arguments, not just
first one(s).

This is all consequence of the fact that we have chosen to create a
practically usable language, not a pretty one. We tried to support
these parts of FP that are mostly useful in real world scenarios,
leaving the rest of the language easy to understand for people with
OO background.

Hope this answers your questions!

--
   Michal Moskal,
   http://nemerle.org/~malekith/