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




 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
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