Digital Mars - digitalmars.D.learn - Memoize function in D

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → 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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → 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