digitalmars.D.learn - Memoize function in D
- Tony (13/13) Jul 24 2005 Hi.
- Ben Hinkle (35/50) Jul 24 2005 It depends on how general you want the memoizable (is that a word?)
- Tony (15/70) Jul 24 2005 original
- Manfred Nowak (13/16) Jul 24 2005 [...]
- Ben Hinkle (5/10) Jul 24 2005 In D a "Box" is a type whose run-time "type" can be anything so you migh...
- Stefan (6/17) Jul 24 2005 Hi Ben,
- Ben Hinkle (4/6) Jul 24 2005 http://www.digitalmars.com/d/std_boxer.html
- Stefan (4/10) Jul 24 2005 Thanks for the pointer, much appreciated ;)
- Stefan (6/12) Jul 24 2005 "float opCmp(Box other)"
- Burton Radons (10/26) Jul 28 2005 If the compiler sees "a <= b" and "a" is a struct that has an opCmp or a...
- Stefan (7/21) Jul 29 2005 Ah, so it's float to be able to say "it's unordered" by returning float....
- Manfred Nowak (16/17) Jul 24 2005 [...]
- Ben Hinkle (3/20) Jul 24 2005 Are you on Linux? I just tried on Windows and it seems to work.
- Manfred Nowak (14/15) Jul 24 2005 WinXPPro, dmd 0.128 (fresh install)
- Ben Hinkle (6/20) Jul 25 2005 fresh. very odd. Is box.obj stale perhaps? My obj file has init_typeinfo...
- Manfred Nowak (17/18) Jul 25 2005 [...]
- Ben Hinkle (7/25) Jul 25 2005 Looks like a bug. I suggest posting to D.bugs. It could be related to
- Charles Hixson (7/85) Jul 24 2005 There are many examples where static typing gets in the way.
- Russ Lewis (16/74) Jul 25 2005 This is just a stylistic difference, but I prefer to return delegates
- Ben Hinkle (16/29) Jul 25 2005 Good point. I agree. Here's a slightly shorter version of memoize:
- Russ Lewis (3/35) Jul 25 2005 Remember the caching functions.
- Ben Hinkle (6/41) Jul 25 2005 hehe - I got a little carried away in "simplifying" :-P
- Russ Lewis (5/54) Jul 25 2005 True. I wonder, if you take a delegate to a synchronized member
- Burton Radons (22/84) Jul 28 2005 Sure:
- Burton Radons (2/28) Jul 28 2005 Err, I mean if synchronized is ADDED then it stalls.
- Manfred Nowak (9/11) Jul 27 2005 [...]
- Ben Hinkle (8/19) Jul 27 2005 uhh - this might be too esoteric for my understanding, but by "nailing d...
- Manfred Nowak (16/18) Jul 27 2005 [...]
- Tony (31/49) Jul 28 2005 Hi Manfred,
- Manfred Nowak (27/32) Jul 28 2005 [...]
- Tony (18/48) Jul 28 2005 Hi Manfred,
- Manfred Nowak (35/49) Jul 29 2005 Then the set of memoizable functions in the sense above is nearly
- Burton Radons (81/96) Jul 29 2005 Taking any number of arguments isn't possible not because of a
- Chris Sauls (6/13) Jul 29 2005 I like it, but would prefer something like:
Hi. I was wondering if someone could demonstrate how to write a memoize function in D? A memoize routine should accept a function as an argument, and return a new function. This new function should return the same values as the original function, but should also maintain a cache of results from previous calls and return the value(s) from the cache rather than recalculating them, whenever possible. This can be done quite simply in Lisp, and an example is available in Paul Grahams "On Lisp" (freely available as a pdf) if anyone is interested. If there is an elegant solution to this in D, I will be very impressed. Tony Melbourne, Australia
Jul 24 2005
"Tony" <talktotony email.com> wrote in message news:dbvpm6$27db$1 digitaldaemon.com...Hi. I was wondering if someone could demonstrate how to write a memoize function in D? A memoize routine should accept a function as an argument, and return a new function. This new function should return the same values as the original function, but should also maintain a cache of results from previous calls and return the value(s) from the cache rather than recalculating them, whenever possible. This can be done quite simply in Lisp, and an example is available in Paul Grahams "On Lisp" (freely available as a pdf) if anyone is interested. If there is an elegant solution to this in D, I will be very impressed. Tony Melbourne, AustraliaIt depends on how general you want the memoizable (is that a word?) functions to be. If you don't mind nailing down the signatures then it would be easy. The solutions in D are probably just like the solutions in C++. For example alias int function(int) Fcn; class Memoize { Fcn f; int[int] cache; this(Fcn f){ this.f = f; } int opCall(int x) { int y; int* v = x in cache; if (v) { y = *v; } else { y = f(x); cache[x] = y; } return y; } } Memoize memoize(Fcn f) { return new Memoize(f); } int fib(int n) { return n < 2 ? 1 : fib(n-1)+fib(n-2); } int main() { printf("%d\n",fib(8)); Memoize m = memoize(&fib); printf("%d\n",m(8)); return 0; }
Jul 24 2005
"Ben Hinkle" <ben.hinkle gmail.com> wrote in message news:dc0ftf$31aq$1 digitaldaemon.com..."Tony" <talktotony email.com> wrote in message news:dbvpm6$27db$1 digitaldaemon.com...originalHi. I was wondering if someone could demonstrate how to write a memoize function in D? A memoize routine should accept a function as an argument, and return a new function. This new function should return the same values as thecallsfunction, but should also maintain a cache of results from previousPauland return the value(s) from the cache rather than recalculating them, whenever possible. This can be done quite simply in Lisp, and an example is available inwouldGrahams "On Lisp" (freely available as a pdf) if anyone is interested. If there is an elegant solution to this in D, I will be very impressed. Tony Melbourne, AustraliaIt depends on how general you want the memoizable (is that a word?) functions to be. If you don't mind nailing down the signatures then itbe easy. The solutions in D are probably just like the solutions in C++.Forexample alias int function(int) Fcn; class Memoize { Fcn f; int[int] cache; this(Fcn f){ this.f = f; } int opCall(int x) { int y; int* v = x in cache; if (v) { y = *v; } else { y = f(x); cache[x] = y; } return y; } } Memoize memoize(Fcn f) { return new Memoize(f); } int fib(int n) { return n < 2 ? 1 : fib(n-1)+fib(n-2); } int main() { printf("%d\n",fib(8)); Memoize m = memoize(&fib); printf("%d\n",m(8)); return 0; }Hi Ben, I was really wondering whether a generalised memoize routine could be written which would work with any function signature. This can be done quite readily in Lisp. This may be a good example of a situation where strong static typing actually gets in the way. Tony Melbourne, Australia
Jul 24 2005
"Tony" <talktotony email.com> wrote: [...]I was really wondering whether a generalised memoize routine could be written which would work with any function signature. This can be done quite readily in Lisp.[...] Are you sure? From the cited book: | Though adequate for most uses, this implementation of memoize | has several limitations. It treats calls as identical if they | have equal argument lists; this could be too strict if the | function had keyword parameters. Also, it is intended only for | single-valued functions, and cannot store or return multiple | values. So what do you mean by "work with any function signature" in case of D-Signatures? -manfred
Jul 24 2005
I was really wondering whether a generalised memoize routine could be written which would work with any function signature. This can be done quite readily in Lisp. This may be a good example of a situation where strong static typing actually gets in the way.In D a "Box" is a type whose run-time "type" can be anything so you might want to check that out. Probably the most reasonable approach would be to restrict the allowed functions to those that take a single Box[] input and return a Box. It's then the function's job (instead of the compiler's) to make sure it was called with the right arguments.
Jul 24 2005
In article <dc14ai$fmo$1 digitaldaemon.com>, Ben Hinkle says...Hi Ben, that sounds quite interesting, is Box(ing) documented somewhere? How can I learn more about it? Kind regards, StefanI was really wondering whether a generalised memoize routine could be written which would work with any function signature. This can be done quite readily in Lisp. This may be a good example of a situation where strong static typing actually gets in the way.In D a "Box" is a type whose run-time "type" can be anything so you might want to check that out. Probably the most reasonable approach would be to restrict the allowed functions to those that take a single Box[] input and return a Box. It's then the function's job (instead of the compiler's) to make sure it was called with the right arguments.
Jul 24 2005
that sounds quite interesting, is Box(ing) documented somewhere? How can I learn more about it?http://www.digitalmars.com/d/std_boxer.html The one wrinkle in using Box today is that you have to compile your code with -release in order to avoid linking problems. Or you can recompile phobos with debugging.
Jul 24 2005
In article <dc15p2$gn1$1 digitaldaemon.com>, Ben Hinkle says...Thanks for the pointer, much appreciated ;) Best regards, Stefanthat sounds quite interesting, is Box(ing) documented somewhere? How can I learn more about it?http://www.digitalmars.com/d/std_boxer.html The one wrinkle in using Box today is that you have to compile your code with -release in order to avoid linking problems. Or you can recompile phobos with debugging.
Jul 24 2005
In article <dc15p2$gn1$1 digitaldaemon.com>, Ben Hinkle says..."float opCmp(Box other)" Why float as return type, that's quite unusal, no? Just curious ... Kind regards, Stefanthat sounds quite interesting, is Box(ing) documented somewhere? How can I learn more about it?http://www.digitalmars.com/d/std_boxer.html The one wrinkle in using Box today is that you have to compile your code with -release in order to avoid linking problems. Or you can recompile phobos with debugging.
Jul 24 2005
Stefan wrote:In article <dc15p2$gn1$1 digitaldaemon.com>, Ben Hinkle says...If the compiler sees "a <= b" and "a" is a struct that has an opCmp or a class, it converts that into "a.opCmp (b) <= 0"; it only uses opEquals for == and !=. So if you return negative for below, positive for above, zero for equivalent, and float.nan for unordered (nan is unordered with everything including itself), then all of the comparison operators will work correctly. This behaviour is undocumented, of course. :) And classes are resigned to using int opCmp because that's what's in Object. That should really be fixed."float opCmp(Box other)" Why float as return type, that's quite unusal, no?that sounds quite interesting, is Box(ing) documented somewhere? How can I learn more about it?http://www.digitalmars.com/d/std_boxer.html The one wrinkle in using Box today is that you have to compile your code with -release in order to avoid linking problems. Or you can recompile phobos with debugging.
Jul 28 2005
In article <dcc8t7$hce$1 digitaldaemon.com>, Burton Radons says...Stefan wrote:Ah, so it's float to be able to say "it's unordered" by returning float.nan Thanks, that cleared it up for me (though, I always lived under the impression that opCmp could/should only be implemented for types that have at least _some_ natural ordering :). Best regards, Stefan"float opCmp(Box other)" Why float as return type, that's quite unusal, no?If the compiler sees "a <= b" and "a" is a struct that has an opCmp or a class, it converts that into "a.opCmp (b) <= 0"; it only uses opEquals for == and !=. So if you return negative for below, positive for above, zero for equivalent, and float.nan for unordered (nan is unordered with everything including itself), then all of the comparison operators will work correctly. This behaviour is undocumented, of course. :) And classes are resigned to using int opCmp because that's what's in Object. That should really be fixed.
Jul 29 2005
"Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]In D a "Box" is a type whose run-time "type" can be anything[...] It is suggested to be. But is it really? <code> import std.boxer; int f(){ return 1; } void main(){ Box b= box(&f); if( unboxable!( int function())( b)) printf("true\n"); } </code> The above code is not linkable, although compiled with -release. -manfred
Jul 24 2005
"Manfred Nowak" <svv1999 hotmail.com> wrote in message news:dc17cj$hnm$1 digitaldaemon.com..."Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]Are you on Linux? I just tried on Windows and it seems to work.In D a "Box" is a type whose run-time "type" can be anything[...] It is suggested to be. But is it really? <code> import std.boxer; int f(){ return 1; } void main(){ Box b= box(&f); if( unboxable!( int function())( b)) printf("true\n"); } </code> The above code is not linkable, although compiled with -release. -manfred
Jul 24 2005
"Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]Are you on Linux? I just tried on Windows and it seems to work.WinXPPro, dmd 0.128 (fresh install) <output> E:\home\d\tests>dmd box -release e:\dmd\bin\..\..\dm\bin\link.exe box,,,user32+kernel32/noi; OPTLINK (R) for Win32 Release 7.50B1 Copyright (C) Digital Mars 1989 - 2001 All Rights Reserved box.obj(box) Error 42: Symbol Undefined __init_13TypeInfo_DFZi --- errorlevel 1 </output> And you? Do you have a fresh install or a recompiled phobos? -manfred
Jul 24 2005
"Manfred Nowak" <svv1999 hotmail.com> wrote in message news:dc20oe$151h$1 digitaldaemon.com..."Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]fresh. very odd. Is box.obj stale perhaps? My obj file has init_typeinfo's for FZi and PFZi but no DFZi. Looking at the mangling rules D means "delegate" so somehow the compiler started thinking it needed a delegate instead of a regular function, I guess.Are you on Linux? I just tried on Windows and it seems to work.WinXPPro, dmd 0.128 (fresh install) <output> E:\home\d\tests>dmd box -release e:\dmd\bin\..\..\dm\bin\link.exe box,,,user32+kernel32/noi; OPTLINK (R) for Win32 Release 7.50B1 Copyright (C) Digital Mars 1989 - 2001 All Rights Reserved box.obj(box) Error 42: Symbol Undefined __init_13TypeInfo_DFZi --- errorlevel 1 </output> And you? Do you have a fresh install or a recompiled phobos?
Jul 25 2005
"Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]Is box.obj stale perhaps?[...] Sadly true. Must have been an .obj from a test with a delegate. But what is wrong now with this additional line? <code> int function() g= unbox!(int function())(b); </code> yields: <output> E:\home\d\tests>dmd box -release e:\dmd\bin\..\src\phobos\std\boxer.d(576): can't have array of int() e:\dmd\bin\..\src\phobos\std\boxer.d(577): can't have array of int() e:\dmd\bin\..\src\phobos\std\boxer.d(10): template instance std.boxer.unbox!(int(*)()) error instantiating </output> -manfred
Jul 25 2005
"Manfred Nowak" <svv1999 hotmail.com> wrote in message news:dc2qsi$1qkq$1 digitaldaemon.com..."Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]Looks like a bug. I suggest posting to D.bugs. It could be related to http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D.bugs/4218 or http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D.bugs/4444. Maybe I oversimplified when I said "the one wrinkle with using box..." I should have said "the most common wrinkle with using box..."Is box.obj stale perhaps?[...] Sadly true. Must have been an .obj from a test with a delegate. But what is wrong now with this additional line? <code> int function() g= unbox!(int function())(b); </code> yields: <output> E:\home\d\tests>dmd box -release e:\dmd\bin\..\src\phobos\std\boxer.d(576): can't have array of int() e:\dmd\bin\..\src\phobos\std\boxer.d(577): can't have array of int() e:\dmd\bin\..\src\phobos\std\boxer.d(10): template instance std.boxer.unbox!(int(*)()) error instantiating </output> -manfred
Jul 25 2005
Tony wrote:"Ben Hinkle" <ben.hinkle gmail.com> wrote in message news:dc0ftf$31aq$1 digitaldaemon.com...There are many examples where static typing gets in the way. Times where it inappropriately gets in the way are also frequent. (N.B.: "gets in the way" means "makes the solution more complex", not "makes the solution impossible".) What you need to decide is whether you gain enough in error prevention to make up for the cost."Tony" <talktotony email.com> wrote in message news:dbvpm6$27db$1 digitaldaemon.com...originalHi. I was wondering if someone could demonstrate how to write a memoize function in D? A memoize routine should accept a function as an argument, and return a new function. This new function should return the same values as thecallsfunction, but should also maintain a cache of results from previousPauland return the value(s) from the cache rather than recalculating them, whenever possible. This can be done quite simply in Lisp, and an example is available inwouldGrahams "On Lisp" (freely available as a pdf) if anyone is interested. If there is an elegant solution to this in D, I will be very impressed. Tony Melbourne, AustraliaIt depends on how general you want the memoizable (is that a word?) functions to be. If you don't mind nailing down the signatures then itbe easy. The solutions in D are probably just like the solutions in C++.Forexample alias int function(int) Fcn; class Memoize { Fcn f; int[int] cache; this(Fcn f){ this.f = f; } int opCall(int x) { int y; int* v = x in cache; if (v) { y = *v; } else { y = f(x); cache[x] = y; } return y; } } Memoize memoize(Fcn f) { return new Memoize(f); } int fib(int n) { return n < 2 ? 1 : fib(n-1)+fib(n-2); } int main() { printf("%d\n",fib(8)); Memoize m = memoize(&fib); printf("%d\n",m(8)); return 0; }Hi Ben, I was really wondering whether a generalised memoize routine could be written which would work with any function signature. This can be done quite readily in Lisp. This may be a good example of a situation where strong static typing actually gets in the way. Tony Melbourne, Australia
Jul 24 2005
Ben Hinkle wrote:"Tony" <talktotony email.com> wrote in message news:dbvpm6$27db$1 digitaldaemon.com...This is just a stylistic difference, but I prefer to return delegates rather than class references: int delegate(int) memoize(Fcn f) { Memoize m = new Memoize(f); return &m.opCall; } ... int main() { ... int delegate(int) dg = memoize(&fib); ... } The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.Hi. I was wondering if someone could demonstrate how to write a memoize function in D? A memoize routine should accept a function as an argument, and return a new function. This new function should return the same values as the original function, but should also maintain a cache of results from previous calls and return the value(s) from the cache rather than recalculating them, whenever possible. This can be done quite simply in Lisp, and an example is available in Paul Grahams "On Lisp" (freely available as a pdf) if anyone is interested. If there is an elegant solution to this in D, I will be very impressed. Tony Melbourne, AustraliaIt depends on how general you want the memoizable (is that a word?) functions to be. If you don't mind nailing down the signatures then it would be easy. The solutions in D are probably just like the solutions in C++. For example alias int function(int) Fcn; class Memoize { Fcn f; int[int] cache; this(Fcn f){ this.f = f; } int opCall(int x) { int y; int* v = x in cache; if (v) { y = *v; } else { y = f(x); cache[x] = y; } return y; } } Memoize memoize(Fcn f) { return new Memoize(f); } int fib(int n) { return n < 2 ? 1 : fib(n-1)+fib(n-2); } int main() { printf("%d\n",fib(8)); Memoize m = memoize(&fib); printf("%d\n",m(8)); return 0; }
Jul 25 2005
int delegate(int) memoize(Fcn f) { Memoize m = new Memoize(f); return &m.opCall; } ... int main() { ... int delegate(int) dg = memoize(&fib); ... } The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.Good point. I agree. Here's a slightly shorter version of memoize: int delegate(int) memoize(int function(int) f) { struct Frame { int function(int) f; int call(int x){return f(x);} } Frame* frame = new Frame; frame.f = f; return &frame.call; } int fib(int n){return n+10;} int main() { int delegate(int) dg = memoize(&fib); printf("%d\n",dg(5)); return 0; }
Jul 25 2005
Ben Hinkle wrote:Remember the caching functions. Also note that the caching example given above is not thread-safe.int delegate(int) memoize(Fcn f) { Memoize m = new Memoize(f); return &m.opCall; } ... int main() { ... int delegate(int) dg = memoize(&fib); ... } The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.Good point. I agree. Here's a slightly shorter version of memoize: int delegate(int) memoize(int function(int) f) { struct Frame { int function(int) f; int call(int x){return f(x);} } Frame* frame = new Frame; frame.f = f; return &frame.call; } int fib(int n){return n+10;} int main() { int delegate(int) dg = memoize(&fib); printf("%d\n",dg(5)); return 0; }
Jul 25 2005
"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message news:dc3df6$2a7d$1 digitaldaemon.com...Ben Hinkle wrote:hehe - I got a little carried away in "simplifying" :-PRemember the caching functions.int delegate(int) memoize(Fcn f) { Memoize m = new Memoize(f); return &m.opCall; } ... int main() { ... int delegate(int) dg = memoize(&fib); ... } The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.Good point. I agree. Here's a slightly shorter version of memoize: int delegate(int) memoize(int function(int) f) { struct Frame { int function(int) f; int call(int x){return f(x);} } Frame* frame = new Frame; frame.f = f; return &frame.call; } int fib(int n){return n+10;} int main() { int delegate(int) dg = memoize(&fib); printf("%d\n",dg(5)); return 0; }Also note that the caching example given above is not thread-safe.That would actually be an advantage of using a class since it can synchronize the opCall method (or whatever method name is chosen - it doesn't really matter what the name is if the delegate is used)..
Jul 25 2005
Ben Hinkle wrote:"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message news:dc3df6$2a7d$1 digitaldaemon.com...True. I wonder, if you take a delegate to a synchronized member function, does the member function implementation do the synchronization? Or is it not ever legal? Something I'll have to investigate some day, unless somebody has the answer right offhand...Ben Hinkle wrote:hehe - I got a little carried away in "simplifying" :-PRemember the caching functions.int delegate(int) memoize(Fcn f) { Memoize m = new Memoize(f); return &m.opCall; } ... int main() { ... int delegate(int) dg = memoize(&fib); ... } The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.Good point. I agree. Here's a slightly shorter version of memoize: int delegate(int) memoize(int function(int) f) { struct Frame { int function(int) f; int call(int x){return f(x);} } Frame* frame = new Frame; frame.f = f; return &frame.call; } int fib(int n){return n+10;} int main() { int delegate(int) dg = memoize(&fib); printf("%d\n",dg(5)); return 0; }Also note that the caching example given above is not thread-safe.That would actually be an advantage of using a class since it can synchronize the opCall method (or whatever method name is chosen - it doesn't really matter what the name is if the delegate is used)..
Jul 25 2005
Russ Lewis wrote:Ben Hinkle wrote:Sure: import std.thread; class A { int count = 0; int bar () { printf ("Bar\n"); if (count ++ == 0) (new Thread (&bar)).start (); while (count == 1) Thread.yield (); return 0; } } void main () { (new A).bar (); } This prints "Bar\n" and then stalls as expected; if synchronized is removed then it goes through."Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message news:dc3df6$2a7d$1 digitaldaemon.com...True. I wonder, if you take a delegate to a synchronized member function, does the member function implementation do the synchronization? Or is it not ever legal? Something I'll have to investigate some day, unless somebody has the answer right offhand...Ben Hinkle wrote:hehe - I got a little carried away in "simplifying" :-PRemember the caching functions.int delegate(int) memoize(Fcn f) { Memoize m = new Memoize(f); return &m.opCall; } ... int main() { ... int delegate(int) dg = memoize(&fib); ... } The two functionality are roughly equivalent. The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.Good point. I agree. Here's a slightly shorter version of memoize: int delegate(int) memoize(int function(int) f) { struct Frame { int function(int) f; int call(int x){return f(x);} } Frame* frame = new Frame; frame.f = f; return &frame.call; } int fib(int n){return n+10;} int main() { int delegate(int) dg = memoize(&fib); printf("%d\n",dg(5)); return 0; }Also note that the caching example given above is not thread-safe.That would actually be an advantage of using a class since it can synchronize the opCall method (or whatever method name is chosen - it doesn't really matter what the name is if the delegate is used)..
Jul 28 2005
Burton Radons wrote:Sure: import std.thread; class A { int count = 0; int bar () { printf ("Bar\n"); if (count ++ == 0) (new Thread (&bar)).start (); while (count == 1) Thread.yield (); return 0; } } void main () { (new A).bar (); } This prints "Bar\n" and then stalls as expected; if synchronized is removed then it goes through.Err, I mean if synchronized is ADDED then it stalls.
Jul 28 2005
"Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]If you don't mind nailing down the signatures then it would be easy.[...] Are you sure? Isnt there the restriction in D, that no function can have its own type as a parameter or as a return value? If so then by diagonalization you cannot memoize especially a memoize-function or similar. -manfred
Jul 27 2005
"Manfred Nowak" <svv1999 hotmail.com> wrote in message news:dc8lm3$fle$2 digitaldaemon.com..."Ben Hinkle" <ben.hinkle gmail.com> wrote: [...]uhh - this might be too esoteric for my understanding, but by "nailing down the signature" I meant it is possible to write a memoize function for the set of functions with a particular signature. I wouldn't be surprised if a memoize function couldn't memoize itself - though perhaps with some vicious use of vararg ... and/or void* casting it would be possible. I expect it would be possible to memoize another memoize function, though.If you don't mind nailing down the signatures then it would be easy.[...] Are you sure? Isnt there the restriction in D, that no function can have its own type as a parameter or as a return value? If so then by diagonalization you cannot memoize especially a memoize-function or similar. -manfred
Jul 27 2005
"Ben Hinkle" <bhinkle mathworks.com> wrote: [...]I wouldn't be surprised if a memoize function couldn't memoize itself[...] Then my question is not that much esoteric. Tony wanted a generalized, i.e. unrestricted, memoize function capable of attaching a cache to any function, i.e. including itself. But this might be thoretically as possible as that famous program that solves the halting problem. The reference Tony was talking of, says itself that its example solution is restricted in several ways and Tony did not answer my question what is meant by "work with any function signature" in case of D-signatures. Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden. -manfred
Jul 27 2005
"Manfred Nowak" <svv1999 hotmail.com> wrote in message news:dc962h$snm$1 digitaldaemon.com..."Ben Hinkle" <bhinkle mathworks.com> wrote: [...]Hi Manfred, Sorry for being a wee bit slow in replying. The limitations raised by Paul Graham apply when functions have keyword arguments or return multiple values. Its worth noting that (to the best of my knowledge) the majority of programming languages do not support either of these features. So for the functions typical of many languages, Paul Grahams solution is a general one. In addition, dealing with multiple return values requires only a minor addition to the memoize function. I've just had a go at it and it seems to be working correctly (but no guarantees!): (defun memoize (fn) (multiple-value-bind (vals win) (gethash args cache) (if win (values-list vals) (progn (let ((vals (multiple-value-list (apply fn args)))) (setf (gethash args cache) vals) (values-list vals)))))))) I'm not entirely sure of the issues regarding support for keyword arguments so I can't comment on this. My main concern with the D implementations I've seen so far is that a separate version seems to be required for each function signature supported (resulting in duplicate code). Since it is the strong (static) typing that seems to be creating this situation, it seems reasonable to conclude that in this instance strong typing is counter-productive. Tony Melbourne, AustraliaI wouldn't be surprised if a memoize function couldn't memoize itself[...] Then my question is not that much esoteric. Tony wanted a generalized, i.e. unrestricted, memoize function capable of attaching a cache to any function, i.e. including itself. But this might be thoretically as possible as that famous program that solves the halting problem. The reference Tony was talking of, says itself that its example solution is restricted in several ways and Tony did not answer my question what is meant by "work with any function signature" in case of D-signatures. Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden. -manfred
Jul 28 2005
"Tony" <talktotony email.com> wrote: [...][...]Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden.I've just had a go at it and it seems to be working correctly (but no guarantees!):[...] I do not understand Lisp. Therefore I am not able to capture the semantics of your implementation. But with Ben I believe that such generalized memoize constructs are at least close to impossibility. And if this is true, then only a subset of the possible constructs is memoizable and this subset has to be defined. An informal argument for the impossibility of a generalized memoize construct (gmc): Assume a gmc is possible. gmc must turn any construct c into a similar construct c' that on invocation with some arguments p1, ..., pn looks up its cache and then do the appropriate of returning the value cached or execute the construct c with arguments p1,...,pn and cache the result. Now apply gmc to itself: gmc'= gmc( gmc) Now call gmc': result = gmc'( gmc') gmc' works as defind: it looks up the entry for gmc' in the hashtable. There is no entry. So it calls itself with its argument ... resulting in an infinite recursion. A contradiction. Therefore the assumption is wrong, that a gmc as defined can exist. -manfred
Jul 28 2005
"Manfred Nowak" <svv1999 hotmail.com> wrote in message news:dcajm5$1tcn$1 digitaldaemon.com..."Tony" <talktotony email.com> wrote: [...]Hi Manfred, I think we may have a slight misunderstanding here. I have not been seeking a totally general memoize function in D. In fact, there are many instances where it does not make sense to apply a memoize function. Namely when: 1. The function to be memoized involves less processing than the cache lookup in a memoized version, or 2. When a function is not referentially transparent. What I am saying is that for the subset of functions that can benefit from memoizing, it is desirable to be able to write a single memoize function rather than needing to write multiple versions for each different function signature. So far the consensus seems to be that the strong static typing in D precludes this. Tony Melbourne, Australia[...]Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden.I've just had a go at it and it seems to be working correctly (but no guarantees!):[...] I do not understand Lisp. Therefore I am not able to capture the semantics of your implementation. But with Ben I believe that such generalized memoize constructs are at least close to impossibility. And if this is true, then only a subset of the possible constructs is memoizable and this subset has to be defined. An informal argument for the impossibility of a generalized memoize construct (gmc): Assume a gmc is possible. gmc must turn any construct c into a similar construct c' that on invocation with some arguments p1, ..., pn looks up its cache and then do the appropriate of returning the value cached or execute the construct c with arguments p1,...,pn and cache the result. Now apply gmc to itself: gmc'= gmc( gmc) Now call gmc': result = gmc'( gmc') gmc' works as defind: it looks up the entry for gmc' in the hashtable. There is no entry. So it calls itself with its argument ... resulting in an infinite recursion. A contradiction. Therefore the assumption is wrong, that a gmc as defined can exist. -manfred
Jul 28 2005
"Tony" <talktotony email.com> wrote:I have not been seeking a totally general memoize function in D. In fact, there are many instances where it does not make sense to apply a memoize function. Namely when: 1. The function to be memoized involves less processing than the cache lookup in a memoized version, or 2. When a function is not referentially transparent.Then the set of memoizable functions in the sense above is nearly empty and in addition I suggest that this set is undecidable. Informal argument resulting out of condition 1: Every cache lookup needs at least Omega( 1) space and Omega( log (n)) time, where n is the number of arguments stored in the cache. Because the growth of log(n) is unbound memoizing is not suitable for functions whose execution time can be bound by an unknown but fix constant. On the other hand if the execution time of the function to be memoized cannot be bound by a constant the time complexity of the function to be memoized has to grow at least at the magnitude of Omega( log(n)) where n is the number of previous calls(!), regardless of the values of the parameters of the calls. If wihite-box-memoizing would be possible, then this would exclude for example the fibonacci-function from being memoizable, because if n-1 values are cached the n-th value can be computed in constant time. Further restriction resulting out of condition 2 for D: because the evaluation order for functions with more than one parameter is undefined in D, only functions with only one in- parameter are referentially transparent.What I am saying is that for the subset of functions that can benefit from memoizing, it is desirable to be able to write a single memoize function rather than needing to write multiple versions for each different function signature. So far the consensus seems to be that the strong static typing in D precludes this.If this is a consensus it is wrong. Bens first approach uses an implementation with a class, which can be easily templated and extended to handle function-types as arguments. The fact that this template has to be instantiated for each function that has to be memoized and therefore consumes time and space is neglectable because this requirements can be bound by Big-O( l), where l is the length of the description of the type of the memoizee, i.e. no more time and space than needed to describe the memoizee itself. Even if you prefer absolute values for time and space the reqirements are still neglectable compared to the requirements imposed by caching. -manfred
Jul 29 2005
Tony wrote:Hi. I was wondering if someone could demonstrate how to write a memoize function in D? A memoize routine should accept a function as an argument, and return a new function. This new function should return the same values as the original function, but should also maintain a cache of results from previous calls and return the value(s) from the cache rather than recalculating them, whenever possible. This can be done quite simply in Lisp, and an example is available in Paul Grahams "On Lisp" (freely available as a pdf) if anyone is interested. If there is an elegant solution to this in D, I will be very impressed.Taking any number of arguments isn't possible not because of a constraint of static typing, but because D doesn't have variadic templates; no language I know of does. Here's a way in which it could be extended to include it (this would support keyword arguments, if the language did): // Specify that the template can take any number of argument types // that are stashed in the virtual tuple ArgumentTypes. class Memoize (ReturnType, ArgumentTypes...) { // Expand ArgumentTypes into the type so that it takes all the // specified parameters. alias ReturnType function (ArgumentTypes...) FunctionType; FunctionType call; // In this context it's treated as its tuple, which is a kind of // struct with overloaded opCmp, opEquals, and opHash, so that // it can be used in associative arrays like this. ReturnType [ArgumentTypes] cache; this (FunctionType vcall) { this.call = vcall; } // This function takes the argument list and stashes it in args. synchronized ReturnType opCall (ArgumentTypes args...) { ReturnType *pointer = args in cache; // The final context: when used in a function call, expand // a tuple into the arguments. if (pointer is null) return cache [args] = call (args...); return *pointer; } } Memoize! (int, int) memo = new Memoize! (int, int) (&fib); This is still all statically-typed, but that's not a word with much meaning. A statically-typed language is the same as a dynamically-typed language - it merely has constraints on what values can be assigned to a variable. D limits constraints to a given type and its inheritors, so to make D dynamically-typed, you only need to specify a type which all other types inherit from or can be considered as, such as box or a void pointer or Object in some scenarios. A statically-typed language like Cecil allows constraints based on arbitrary predicates, and doesn't have obstructing constructs like value types (which in D's case are simply reference types which initialise implicitly, duplicate on assignment, and are not considered inheritors of Object). If you try to treat D - but not Cecil - as a dynamically-typed language, you'll get into troubles because you'll have to cast an object before you can send a given message to it. But that is purely a difference in message dispatching; it doesn't have anything to do with static typing. A purely dynamically-typed language would be functionally useless, so dynamically-typed languages actually aren't. For example, this Python code is not dynamically typed: class foo: def bar (self): pass class baz: def bar (self): pass foo ().bar () It is actually functionally identical to this code using an extension: class foo: pass class baz: pass def bar (foo self): pass def bar (baz self): pass bar (foo ()) A purely dynamically-typed language doesn't have fields or methods; it's all functions at the global scope and the only way to tell two with the same name apart is by the number of arguments they have. Cecil actually supports this style of programming, although at some depth the code must turn into pure strong static typing for it to be evaluatable (unless if it's empty). If I sound like I'm talking pure gibberish, sorry. I'm sure these issues are given high-falutin' names in computer science or maybe these same names but with different meanings, but I'm just a hobbyist so I wouldn't know.
Jul 29 2005
Burton Radons wrote:Here's a way in which it could be extended to include it (this would support keyword arguments, if the language did): // Specify that the template can take any number of argument types // that are stashed in the virtual tuple ArgumentTypes. class Memoize (ReturnType, ArgumentTypes...) {I like it, but would prefer something like: With A of type TypeInfo[] like the _arguments local given to variadic functions. The quirk then becomes how to handle out/inout arguments. -- Chris Sauls
Jul 29 2005