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

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

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

"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

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

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

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

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

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

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