Walter Bright wrote:
> D's tuple support has reached the point where function currying is straightforward. I held off from doing a standard library with these because Tom S's bind library is much more comprehensive, and I hope he'll update it with these.
> 
> ------ Curry first argument -----------------
> 
> R delegate(U) Curry(Dummy=void, R, A, U...)(R function(A, U) dg, A arg)
> {
>     struct Foo
>     {
>     typeof(dg) dg_m;
>     typeof(arg) arg_m;
> 
>     R bar(U r)
>     {
>         return dg_m(arg_m, r);
>     }
>     }
> 
>     Foo* f = new Foo;
>     f.dg_m = dg;
>     f.arg_m = arg;
>     return &f.bar;
> }
> 
> R delegate(U) Curry(R, A, U...)(R delegate(A, U) dg, A arg)
> {
>     struct Foo
>     {
>     typeof(dg) dg_m;
>     typeof(arg) arg_m;
> 
>     R bar(U r)
>     {
>         return dg_m(arg_m, r);
>     }
>     }
> 
>     Foo* f = new Foo;
>     f.dg_m = dg;
>     f.arg_m = arg;
>     return &f.bar;
> }
> 
> void main()
> {
>     static int plus(int x, int y, int z)
>     {
>     return x + y + z;
>     }
> 
>     auto plus_two = Curry(&plus, 2);
>     printf("%d\n", plus_two(6, 8));
>     auto plus_three = Curry(plus_two, 3);
>     printf("%d\n", plus_three(7));
> 
>     int minus(int x, int y, int z)
>     {
>     return x + y + z;
>     }
> 
>     auto minus_two = Curry(&minus, 2);
>     printf("%d\n", minus_two(6, 8));
>     auto minus_three = Curry(minus_two, 3);
>     printf("%d\n", minus_three(7));
> }
> -------- Curry all the arguments -------------------------
> 
> R delegate() CurryAll(Dummy=void, R, U...)(R function(U) dg, U args)
> {
>     struct Foo
>     {
>     typeof(dg) dg_m;
>     U args_m;
> 
>     R bar()
>     {
>         return dg_m(args_m);
>     }
>     }
> 
>     Foo* f = new Foo;
>     f.dg_m = dg;
>     foreach (i, arg; args)
>     f.args_m[i] = arg;
>     return &f.bar;
> }
> 
> R delegate() CurryAll(R, U...)(R delegate(U) dg, U args)
> {
>     struct Foo
>     {
>     typeof(dg) dg_m;
>     U args_m;
> 
>     R bar()
>     {
>         return dg_m(args_m);
>     }
>     }
> 
>     Foo* f = new Foo;
>     f.dg_m = dg;
>     foreach (i, arg; args)
>     f.args_m[i] = arg;
>     return &f.bar;
> }
> 
> 
> void main()
> {
>     static int plus(int x, int y, int z)
>     {
>     return x + y + z;
>     }
> 
>     auto plus_two = CurryAll(&plus, 2, 3, 4);
>     printf("%d\n", plus_two());
>     assert(plus_two() == 9);
> 
>     int minus(int x, int y, int z)
>     {
>     return x + y + z;
>     }
> 
>     auto minus_two = CurryAll(&minus, 7, 8, 9);
>     printf("%d\n", minus_two());
>     assert(minus_two() == 24);
> }
> -----------------------

Nice walter.

Its too bad though that inner function delegates don't live past the stack frame or this wouldn't really be necessary..hehe.

-DavidM

Bill Baxter wrote:
> Hasan Aljudy wrote:
> 
>>
>>
>> Brad Roberts wrote:
>>
>>> The net is a truly wonderful resource:
>>>
>>> http://en.wikipedia.org/wiki/Curried_function
>>
>>
> Although apparently confusion over what's "currying" and what's "partial function evaluation" abounds.

And I am no exception -- what I should have said was "partial function /application/".  At least in this case, there's no actual evaluating going on.

Anyway I'm mostly aware of this distinction between currying and partial application because of a big debate on the python mailing list when someone proposed a standard "currying" library, that was basically a Python version of Walter's "curry" functions.  The currying proposal eventually got it's name changed to "partial function application proposal" because, as was pointed out, it wasn't currying.

http://www.python.org/dev/peps/pep-0309/

It is now in python 2.5 as the function called "partial()" in the module functools.


--bb

David Medlock wrote:

> Walter Bright wrote:
> 
>> D's tuple support has reached the point where function currying is straightforward. I held off from doing a standard library with these because Tom S's bind library is much more comprehensive, and I hope he'll update it with these.
>>
>> ------ Curry first argument -----------------
>>
>> R delegate(U) Curry(Dummy=void, R, A, U...)(R function(A, U) dg, A arg)
>> {
>>     struct Foo
>>     {
>>     typeof(dg) dg_m;
>>     typeof(arg) arg_m;
>>
>>     R bar(U r)
>>     {
>>         return dg_m(arg_m, r);
>>     }
>>     }
>>
>>     Foo* f = new Foo;
>>     f.dg_m = dg;
>>     f.arg_m = arg;
>>     return &f.bar;
>> }
>>
>> R delegate(U) Curry(R, A, U...)(R delegate(A, U) dg, A arg)
>> {
>>     struct Foo
>>     {
>>     typeof(dg) dg_m;
>>     typeof(arg) arg_m;
>>
>>     R bar(U r)
>>     {
>>         return dg_m(arg_m, r);
>>     }
>>     }
>>
>>     Foo* f = new Foo;
>>     f.dg_m = dg;
>>     f.arg_m = arg;
>>     return &f.bar;
>> }
>>
>> void main()
>> {
>>     static int plus(int x, int y, int z)
>>     {
>>     return x + y + z;
>>     }
>>
>>     auto plus_two = Curry(&plus, 2);
>>     printf("%d\n", plus_two(6, 8));
>>     auto plus_three = Curry(plus_two, 3);
>>     printf("%d\n", plus_three(7));
>>
>>     int minus(int x, int y, int z)
>>     {
>>     return x + y + z;
>>     }
>>
>>     auto minus_two = Curry(&minus, 2);
>>     printf("%d\n", minus_two(6, 8));
>>     auto minus_three = Curry(minus_two, 3);
>>     printf("%d\n", minus_three(7));
>> }
>> -------- Curry all the arguments -------------------------
>>
>> R delegate() CurryAll(Dummy=void, R, U...)(R function(U) dg, U args)
>> {
>>     struct Foo
>>     {
>>     typeof(dg) dg_m;
>>     U args_m;
>>
>>     R bar()
>>     {
>>         return dg_m(args_m);
>>     }
>>     }
>>
>>     Foo* f = new Foo;
>>     f.dg_m = dg;
>>     foreach (i, arg; args)
>>     f.args_m[i] = arg;
>>     return &f.bar;
>> }
>>
>> R delegate() CurryAll(R, U...)(R delegate(U) dg, U args)
>> {
>>     struct Foo
>>     {
>>     typeof(dg) dg_m;
>>     U args_m;
>>
>>     R bar()
>>     {
>>         return dg_m(args_m);
>>     }
>>     }
>>
>>     Foo* f = new Foo;
>>     f.dg_m = dg;
>>     foreach (i, arg; args)
>>     f.args_m[i] = arg;
>>     return &f.bar;
>> }
>>
>>
>> void main()
>> {
>>     static int plus(int x, int y, int z)
>>     {
>>     return x + y + z;
>>     }
>>
>>     auto plus_two = CurryAll(&plus, 2, 3, 4);
>>     printf("%d\n", plus_two());
>>     assert(plus_two() == 9);
>>
>>     int minus(int x, int y, int z)
>>     {
>>     return x + y + z;
>>     }
>>
>>     auto minus_two = CurryAll(&minus, 7, 8, 9);
>>     printf("%d\n", minus_two());
>>     assert(minus_two() == 24);
>> }
>> -----------------------
> 
> 
> Nice walter.
> 
> Its too bad though that inner function delegates don't live past the stack frame or this wouldn't really be necessary..hehe.
> 
> -DavidM

Oh yes I will add another plug for a great book which explains currying in the context of functions as well as programs:

http://www.dina.dk/~sestoft/pebook/

-DavidM

I've done implemented "true" function currying (according to Bill Baxter), which converts, say, the function

  static int plus(int a, int b, int c)

to

  ((int delegate(int)) delegate (int)) delegate(int)
     (I added extra brackets to perhaps make it more readable)

which means you call it like this:

  curried_plus(1)(2)(3) instead of
  plus(1,2,3)

and you can do partial function application on it very easily:

  auto plus2 = curried_plus(2);

Side note: about half the code I've attached is to determine the type of the return value. This could be completely avoided if we had type inference on return values, so

CurriedTypeImpl!(RetType, NewParams).Type bar(MyParam myParam)

  could become

auto bar(MyParam myParam)

and the CurriedType2 and CurriedTypeImpl templates could disappear. In fact, it was with these templates that I spent the most time before they worked.

Also, typeid's of function/delegate types are printed wrongly (see the comments in the main function). I don't know whether that is because of writefln or DMD or what, but it doesn't show the fucntion parameters.


Here's the code:

import std.traits;
import std.stdio;
import std.string;


// For finding the return type
template CurriedTypeImpl(RetType, Params...)
{
    static assert(Params.length > 0);
    static if (Params.length == 1)
    {
        alias RetType delegate(Params[0]) Type;
    }
    else
    {
        alias CurriedTypeImpl!(RetType, Params[1..length]).Type delegate(Params[0]) Type;
    }
}

// Also for finding the return type
template CurriedType2(DG, KnownParams...)
{
    alias ParameterTypeTuple!(DG)[KnownParams.length .. length] Params;
    alias ReturnType!(DG) RetType;
    alias CurriedTypeImpl!(RetType, Params).Type Type;
}

// Here's where the currying is actually done
CurriedType2!(DG, KnownParams).Type RealCurry(DG, KnownParams...)(DG dg, KnownParams p)
{
    alias ParameterTypeTuple!(dg)[KnownParams.length .. length] Params;
        static assert(Params.length > 0);

    alias ReturnType!(dg) RetType;
    alias Params[1..length] NewParams;
    alias Params[0] MyParam;

    struct Foo
    {
        KnownParams p_m;
        DG dg_m;
        static if (Params.length == 1)
        {
            RetType bar(MyParam myParam)
            {
                return dg_m(p_m, myParam);
            }
        }
        else
        {
            CurriedTypeImpl!(RetType, NewParams).Type bar(MyParam myParam)
            {
                return RealCurry(dg_m, p_m, myParam);
            }
        }
    }

    Foo* f = new Foo;
    f.dg_m = dg;
    foreach (i, arg; p)
        f.p_m[i] = arg;
    return &f.bar;
}

void main()
{
    static int plus(int x, int y, int z)
    {
    return x + y + z;
    }

    auto curried_plus = RealCurry(&plus);
    auto plus_two = curried_plus(2);
    auto plus_two_plus_three = plus_two(3);

    writefln(plus_two_plus_three(4)); // 9
    writefln(plus_two(5)(6));         // 13
    writefln(typeid(typeof(curried_plus)));   // Should print 'int delegate(int) delegate(int) delegate(int)' but actually prints 'int delegate() delegate() delegate()'
    writefln(typeid(typeof(plus_two_plus_three))); // Should print 'int delegate(int)' but actually prints 'int delegate()'
    writefln(typeid(typeof(plus))); // Should print 'int(int,int,int)' but actually prints 'int()'
}

Cheers,

Reiner

David Medlock wrote:
> David Medlock wrote:
>
>>
>> Nice walter.
>>
>> Its too bad though that inner function delegates don't live past the stack frame or this wouldn't really be necessary..hehe.
>>
>> -DavidM
> 
> Oh yes I will add another plug for a great book which explains currying in the context of functions as well as programs:
> 
> http://www.dina.dk/~sestoft/pebook/
> 
>

Oh yeh... that's the reason I had "partial evaluation" on the brain when I should have been saying "partial application".  I looked over that link the last time you posted it, too.

From what I gather from that web page and a quick google for "partial evaluation", it is a much more advanced beast than partial function application.  In partial evaluation you'd take something like triple_integral(fx,fy,fz) that integrates over three variables, and your partial evaluation usage would be:

      single_integral = partial_eval(triple_integral, gx, gy);
      answer = single_integral(gz);

Looks just like partial application, except in partial evaluation, the first two variables would actually be precomputed (integrated out) to create a new function that really did not require gx and gy to perform its computation.

Is that the way you understand it, too, David?

If so then there ain't no simple 1-page template that's going to be able to do that for the general case.  :-)  But it would be mighty cool if there were.

--bb

Reiner Pope wrote:
> I've done implemented "true" function currying (according to Bill Baxter), which converts, say, the function
> 
>   static int plus(int a, int b, int c)
> 

Cool! I don't know if it'll actually be of any use to anyone, but it's a very nice demo of the power and succinctness of D templates.

I tinkered with it a little myself, but moved on to something else after a few false starts.  It was generating that recursive return type that was tripping me up.

Nice work!

--bb

Bill Baxter wrote:
> David Medlock wrote:
> 
>> David Medlock wrote:
>>
>>>
>>> Nice walter.
>>>
>>> Its too bad though that inner function delegates don't live past the stack frame or this wouldn't really be necessary..hehe.
>>>
>>> -DavidM
>>
>>
>> Oh yes I will add another plug for a great book which explains currying in the context of functions as well as programs:
>>
>> http://www.dina.dk/~sestoft/pebook/
>>
>>
> 
> Oh yeh... that's the reason I had "partial evaluation" on the brain when I should have been saying "partial application".  I looked over that link the last time you posted it, too.
> 
>  From what I gather from that web page and a quick google for "partial evaluation", it is a much more advanced beast than partial function application.  In partial evaluation you'd take something like triple_integral(fx,fy,fz) that integrates over three variables, and your partial evaluation usage would be:
> 
>       single_integral = partial_eval(triple_integral, gx, gy);
>       answer = single_integral(gz);
> 
> Looks just like partial application, except in partial evaluation, the first two variables would actually be precomputed (integrated out) to create a new function that really did not require gx and gy to perform its computation.
> 
> Is that the way you understand it, too, David?
> 
> If so then there ain't no simple 1-page template that's going to be able to do that for the general case.  :-)  But it would be mighty cool if there were.
> 
> --bb

I guess it depends on whether you wish to do it at runtime or compile time.

The point of the book( speaking here of Chapter 4, I haven't fully digested all of it) is that you can take a function which simply computes a value and slowly degenerate it into a function which accepts N inputs then computes the result. Where N is the number of variables in the function.

Taking this to the extreme(accepting both values and commands) would be an interpreter( or script evaluator ).
This is partial evaluation at runtime.

Or you could run the compiler on the function each time a new value or type is presented.  This is compile time partial application and is the one represented by D templates.

It reinforces my belief that data is the only piece of most programs which will not change much. The inputs define the program.  Looking over some of the most reusable programs out there(compilers, web browsers, spreadsheets) they are completely defined by their inputs.

-DavidM

PS. If I am understanding this incorrectly, please speak up and I will eat my humble pie.

Bill Baxter wrote:
>  From what I gather from that web page and a quick google for "partial evaluation", it is a much more advanced beast than partial function application.  In partial evaluation you'd take something like triple_integral(fx,fy,fz) that integrates over three variables, and your partial evaluation usage would be:
> 
>       single_integral = partial_eval(triple_integral, gx, gy);
>       answer = single_integral(gz);
> 
> Looks just like partial application, except in partial evaluation, the first two variables would actually be precomputed (integrated out) to create a new function that really did not require gx and gy to perform its computation.
> 
> Is that the way you understand it, too, David?

I understand partial evaluation (PE) to be a specific form of optimization which is just inlining + const-folding in the simple cases. While it would be able to optimize your example, its strengths lie also in places where it isn't so explicit. For instance, you could write:

writefln("a=[%d]",a);

and running the partial evaluator would reduce that to:

pustr("a=[");
putint(a);
putstr("]");

That sort of optimization is pretty easy for a
compiler to do (note that PE really is a compiler technique, not a library technique), because you just have to inline, convert to static single assignment, const-fold and you're mostly done, except for tricky situations with reference semantics.

The really interesting things, though, come when you want to set up partial evaluation with non-const values (ie set up code to optimize away things which will be constant, but only known at runtime). 'Tempo' for C does this.

A lot of stuff in D templates is really just a way to force the compiler to inline things (like, say, templated regexps). If the optimizer were sufficiently powerful (perhaps we could even look into something like guaranteed optimization) then the need for these *should* disappear, since you could trust the compiler to partially evaluate them.

PE could open a lot of opportunities, but the problem is that you only really notice it in speed and early catching of errors; there are no cool language features that you have to show for it.

Cheers,

Reiner