www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Memoize function in D

reply "Tony" <talktotony email.com> writes:
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
next sibling parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"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, Australia

It 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
next sibling parent reply "Tony" <talktotony email.com> writes:
"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...
 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


 function, but should also maintain a cache of results from previous


 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


 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

It 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

 be easy. The solutions in D are probably just like the solutions in C++.

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

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
next sibling parent Manfred Nowak <svv1999 hotmail.com> writes:
"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
prev sibling next sibling parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
 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
next sibling parent reply Stefan <Stefan_member pathlink.com> writes:
In article <dc14ai$fmo$1 digitaldaemon.com>, Ben Hinkle says...
 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.

Hi Ben, that sounds quite interesting, is Box(ing) documented somewhere? How can I learn more about it? Kind regards, Stefan
Jul 24 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
 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
next sibling parent Stefan <Stefan_member pathlink.com> writes:
In article <dc15p2$gn1$1 digitaldaemon.com>, Ben Hinkle says...
 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.

Thanks for the pointer, much appreciated ;) Best regards, Stefan
Jul 24 2005
prev sibling parent reply Stefan <Stefan_member pathlink.com> writes:
In article <dc15p2$gn1$1 digitaldaemon.com>, Ben Hinkle says...
 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.

"float opCmp(Box other)" Why float as return type, that's quite unusal, no? Just curious ... Kind regards, Stefan
Jul 24 2005
parent reply Burton Radons <burton-radons smocky.com> writes:
Stefan wrote:
 In article <dc15p2$gn1$1 digitaldaemon.com>, Ben Hinkle says...
 
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.

"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 28 2005
parent Stefan <Stefan_member pathlink.com> writes:
In article <dcc8t7$hce$1 digitaldaemon.com>, Burton Radons says...
Stefan wrote:
 
 "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.

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
Jul 29 2005
prev sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
"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
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Manfred Nowak" <svv1999 hotmail.com> wrote in message 
news:dc17cj$hnm$1 digitaldaemon.com...
 "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

Are you on Linux? I just tried on Windows and it seems to work.
Jul 24 2005
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
"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
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Manfred Nowak" <svv1999 hotmail.com> wrote in message 
news:dc20oe$151h$1 digitaldaemon.com...
 "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?

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.
Jul 25 2005
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
"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
parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Manfred Nowak" <svv1999 hotmail.com> wrote in message 
news:dc2qsi$1qkq$1 digitaldaemon.com...
 "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

Looks like a bug. I suggest posting to D.bugs. It could be related to digitalmars.D.bugs/4218 or 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..."
Jul 25 2005
prev sibling parent Charles Hixson <charleshixsn earthlink.net> writes:
Tony wrote:
 "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...
 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


 function, but should also maintain a cache of results from previous


 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


 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

functions to be. If you don't mind nailing down the signatures then it

 be easy. The solutions in D are probably just like the solutions in C++.

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

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

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.
Jul 24 2005
prev sibling next sibling parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Ben Hinkle wrote:
 "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, Australia

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

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.
Jul 25 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
 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
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Ben Hinkle wrote:
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; }

Remember the caching functions. Also note that the caching example given above is not thread-safe.
Jul 25 2005
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message 
news:dc3df6$2a7d$1 digitaldaemon.com...
 Ben Hinkle wrote:
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; }

Remember the caching functions.

hehe - I got a little carried away in "simplifying" :-P
 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
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Ben Hinkle wrote:
 "Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message 
 news:dc3df6$2a7d$1 digitaldaemon.com...
 
Ben Hinkle wrote:

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

Remember the caching functions.

hehe - I got a little carried away in "simplifying" :-P
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)..

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...
Jul 25 2005
parent reply Burton Radons <burton-radons smocky.com> writes:
Russ Lewis wrote:

 Ben Hinkle wrote:
 
 "Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message 
 news:dc3df6$2a7d$1 digitaldaemon.com...

 Ben Hinkle wrote:

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

Remember the caching functions.

hehe - I got a little carried away in "simplifying" :-P
 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)..

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

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.
Jul 28 2005
parent Burton Radons <burton-radons smocky.com> writes:
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
prev sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
"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
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Manfred Nowak" <svv1999 hotmail.com> wrote in message 
news:dc8lm3$fle$2 digitaldaemon.com...
 "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

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.
Jul 27 2005
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
"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
parent reply "Tony" <talktotony email.com> writes:
"Manfred Nowak" <svv1999 hotmail.com> wrote in message
news:dc962h$snm$1 digitaldaemon.com...
 "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

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) (let ((cache (make-hash-table :test #'equal))) #'(lambda (&rest args) (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, Australia
Jul 28 2005
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
"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
parent reply "Tony" <talktotony email.com> writes:
"Manfred Nowak" <svv1999 hotmail.com> wrote in message
news:dcajm5$1tcn$1 digitaldaemon.com...
 "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

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
Jul 28 2005
parent Manfred Nowak <svv1999 hotmail.com> writes:
"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
prev sibling parent reply Burton Radons <burton-radons smocky.com> writes:
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 # Call the first version of bar based on the # type of its first argument. 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
parent Chris Sauls <ibisbasenji gmail.com> writes:
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: # class Memoize (R function(A...)) { /*blah*/ } 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