www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Function Currying

reply Walter Bright <newshound digitalmars.com> writes:
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);
}
-----------------------
Nov 14 2006
next sibling parent reply Hasan Aljudy <hasan.aljudy gmail.com> writes:
Is everyone supposed to know what currying means? and what are its uses?

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);
 }
 -----------------------

Nov 14 2006
parent reply Brad Roberts <braddr puremagic.com> writes:
The net is a truly wonderful resource:

http://en.wikipedia.org/wiki/Curried_function

Hasan Aljudy wrote:
 Is everyone supposed to know what currying means? and what are its uses?
 
 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);
 }
 -----------------------


Nov 14 2006
next sibling parent reply Hasan Aljudy <hasan.aljudy gmail.com> writes:
Brad Roberts wrote:
 The net is a truly wonderful resource:
 
 http://en.wikipedia.org/wiki/Curried_function

I've read that a while ago, but it doesn't make much of a sense. Why would anyone need such a thing? My original question was, is it something that everyone is supposed to already know its meaning and uses?
 
 Hasan Aljudy wrote:
 Is everyone supposed to know what currying means? and what are its uses?

 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);
 }
 -----------------------



Nov 14 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Hasan Aljudy wrote:
 
 
 Brad Roberts wrote:
 The net is a truly wonderful resource:

 http://en.wikipedia.org/wiki/Curried_function

I've read that a while ago, but it doesn't make much of a sense. Why would anyone need such a thing? My original question was, is it something that everyone is supposed to already know its meaning and uses?

It's handy when you want to 'save' a command for future use, such as pushing it onto an undo/redo stack. Being able to encapsulate the arguments into just a function call make this particularly useful.
Nov 14 2006
parent reply Hasan Aljudy <hasan.aljudy gmail.com> writes:
Walter Bright wrote:
 Hasan Aljudy wrote:
 Brad Roberts wrote:
 The net is a truly wonderful resource:

 http://en.wikipedia.org/wiki/Curried_function

I've read that a while ago, but it doesn't make much of a sense. Why would anyone need such a thing? My original question was, is it something that everyone is supposed to already know its meaning and uses?

It's handy when you want to 'save' a command for future use, such as pushing it onto an undo/redo stack. Being able to encapsulate the arguments into just a function call make this particularly useful.

Hmm, sounds legitimate but I still don't quiet get it. Can you give a more concrete example? I mean, I can always save a command using a nested function. Why would I choose to call a curry template for something like, say: void func( type arg ) { doSomething(arg); ...... doSomething(arg); .. doSomething(arg); .. doSomething(arg); //I'm tired of this .. //call nested functions to the rescue .. void doit() { doSomething(arg); } doit(); doit(); ... doit(); } I'm more confident using a nested function, at least I know what's going on. With a curried function, I'd be more like "gee I'm not sure what's going on but I hope this works ..".
Nov 14 2006
parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Hasan Aljudy" <hasan.aljudy gmail.com> wrote in message 
news:eje8hg$10on$1 digitaldaemon.com...
 Hmm, sounds legitimate but I still don't quiet get it. Can you give a more 
 concrete example?
 I mean, I can always save a command using a nested function. Why would I 
 choose to call a curry template for something like, say:

 void func( type arg )
 {
     doSomething(arg);
     ......
     doSomething(arg);
     ..
     doSomething(arg);
     ..
     doSomething(arg);

     //I'm tired of this ..
     //call nested functions to the rescue ..
     void doit()
     {
         doSomething(arg);
     }

     doit();
     doit();
     ...
     doit();
 }

 I'm more confident using a nested function, at least I know what's going 
 on. With a curried function, I'd be more like "gee I'm not sure what's 
 going on but I hope this works ..".

Go ahead and try to return doit() from func(), or save it somewhere where it will be accessed after func() returns ;) I mean, you _could_ do it without templates using a struct as the context (much as Walter's posted code does), but you'd be seriously restricting yourself to functions/delegates with certain signatures.
Nov 14 2006
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Hasan Aljudy wrote:
 
 
 Brad Roberts wrote:
 The net is a truly wonderful resource:

 http://en.wikipedia.org/wiki/Curried_function

I've read that a while ago, but it doesn't make much of a sense. Why would anyone need such a thing? My original question was, is it something that everyone is supposed to already know its meaning and uses?

Yes, if you've been through a decent CS undergrad program you should probably at least have a vague idea what it is. It's more common in functional languages (which should also be part of a decent undergrad curriculum). Although apparently confusion over what's "currying" and what's "partial function evaluation" abounds. The difference as I understand it is that 'currying' is supposed to create a new function that takes one parameter and returns a function of one less parameter. So curried_add, a curried version of add(a,b,c), could be called like curried_add(a)(b)(c). So the thing that 'curries' add() should just take 'add' as a paramter: curried_add = curry(add). The key is that when you're currying, nothing is actually evaluated. curried_add still does everything the original function did. Partial evaluation is when you actually reduce the number of arguments by one or more, by 'baking them in'. Like in Walter's examples. So the examples are actually showing partial evaluation, not currying. As for usefulness... one use case is similar to delegates. If you have some function like do_something(Object, argument), with partial evaluation you can create a new function do_something_to_object(argument), where the object doesn't have to be supplied. And since you can repeat the process for any number of arguments you can have something like a delegate that contains N implicit .ptr values rather than just one. Functional language folks are crazy about it. ML doesn't actually even have multi-argument functions. Every function is always fully curried, so every function takes at most 1 argument. If it appears to take 2 arguments like "add a b", it's a disguise. 'add' really takes 1 argument, and returns another function of 1 argument, which then takes the second argument, and finally returns a value. It would be interesting to see if you could actually make a real 'curry' function. One that takes a function, foo(a,b,c,d) of N arguments and returns a cascaded set of functions with 1 argument each that you can call like curried_foo(a)(b)(c)(d). It should be doable with some sort of recursive template. --bb
Nov 14 2006
parent Bill Baxter <wbaxter gmail.com> writes:
Bill Baxter wrote:
 Hasan Aljudy wrote:
 
 Brad Roberts wrote:

 The net is a truly wonderful resource:

 http://en.wikipedia.org/wiki/Curried_function


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
Nov 15 2006
prev sibling parent reply =?iso-8859-1?q?Knud_S=F8rensen?= <12tkvvb02 sneakemail.com> writes:
On Tue, 14 Nov 2006 20:07:41 -0800, Brad Roberts wrote:

 The net is a truly wonderful resource:
 
 http://en.wikipedia.org/wiki/Curried_function
 

someone should add a D example to that wiki page.
Nov 15 2006
parent Georg Wrede <georg.wrede nospam.org> writes:
Knud Sørensen wrote:
 On Tue, 14 Nov 2006 20:07:41 -0800, Brad Roberts wrote:
 
 
The net is a truly wonderful resource:

http://en.wikipedia.org/wiki/Curried_function

someone should add a D example to that wiki page.

Yeah, but it better not just show partial function evaluation!!
Nov 15 2006
prev sibling next sibling parent reply David Medlock <noone nowhere.com> writes:
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
Nov 15 2006
parent reply David Medlock <noone nowhere.com> writes:
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
Nov 15 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
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
Nov 15 2006
next sibling parent David Medlock <noone nowhere.com> writes:
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.
Nov 15 2006
prev sibling parent Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
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
Nov 15 2006
prev sibling parent reply Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
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
Nov 15 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
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
Nov 15 2006