www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - memoize

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I just added a higher-order function memoize to std.functional which I 
think is pretty cool. See the docs here:

http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize

I'm also thinking of adding that cutting-edge directory as a place for 
storing documentation for commits that are in flux but not officially 
released yet.


Andrei
Jan 03 2011
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:ifu70u$2dvs$1 digitalmars.com...

I just added a higher-order function memoize to std.functional which I 
think is pretty cool. See the docs here:

 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize

 I'm also thinking of adding that cutting-edge directory as a place for 
 storing documentation for commits that are in flux but not officially 
 released yet.


 Andrei


Neat! This is a great example of why D kicks so much ass :)
Jan 03 2011
parent reply Guilherme Vieira <n2.nitrogen gmail.com> writes:
On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a a.a> wrote:


 "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message
 news:ifu70u$2dvs$1 digitalmars.com...

I just added a higher-order function memoize to std.functional which I
think is pretty cool. See the docs here:


 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize

 I'm also thinking of adding that cutting-edge directory as a place for
 storing documentation for commits that are in flux but not officially
 released yet.


 Andrei


 Neat! This is a great example of why D kicks so much ass :)


Uh, yes. It looks like the kind of thing I would do, show to others and hear
they say "Meh.. Whatever". I'm really exponentially developing a liking to
the D community, even though I didn't event get to code anything serious
yet.

This simply rocks. Keep it up, Andrei!

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
Jan 03 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/3/11 11:01 PM, Guilherme Vieira wrote:

 On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a a.a> wrote:

     "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org
     <mailto:SeeWebsiteForEmail erdani.org>> wrote in message
     news:ifu70u$2dvs$1 digitalmars.com...
      >I just added a higher-order function memoize to std.functional which I
      >think is pretty cool. See the docs here:
      >
      >
     http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize
      >
      > I'm also thinking of adding that cutting-edge directory as a
     place for
      > storing documentation for commits that are in flux but not officially
      > released yet.
      >
      >
      > Andrei

     Neat! This is a great example of why D kicks so much ass :)


 Uh, yes. It looks like the kind of thing I would do, show to others and
 hear they say "Meh.. Whatever". I'm really exponentially developing a
 liking to the D community, even though I didn't event get to code
 anything serious yet.

 This simply rocks. Keep it up, Andrei!

 --
 Atenciosamente / Sincerely,
 Guilherme ("n2liquid") Vieira


Glad you folks like it. There's a little story behind this. I first read 
Dominus' book chapter years ago, around the time I'd decided to write 
TDPL. Back then I was thinking - it would just be so cool to be able to 
define generic memoization in D. I tried my hand at an implementation. 
But D had no tuples, no aliasing for functions, no good variadics, and 
even if you could find a way to pack parameters, associative arrays had 
plenty of related issues.

I'd given up on that and forgot most about it, until today. It was nice 
to reckon that getting it done took about a dozen lines and about as 
many minutes. We really have come a very long way.

Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work 
for overloaded functions, and associative arrays don't work for ubyte[4] 
keys... still a ways to go.


Andrei
Jan 03 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 03 January 2011 21:27:22 Andrei Alexandrescu wrote:

 On 1/3/11 11:01 PM, Guilherme Vieira wrote:

 On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a a.a> wrote:
     "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org
     <mailto:SeeWebsiteForEmail erdani.org>> wrote in message
     news:ifu70u$2dvs$1 digitalmars.com...
     
      >I just added a higher-order function memoize to std.functional
      >which I
     
      >think is pretty cool. See the docs here:
     http://d-programming-language.org/cutting-edge/phobos/std_functional.
     html#memoize
     
      > I'm also thinking of adding that cutting-edge directory as a
     
     place for
     
      > storing documentation for commits that are in flux but not
      > officially released yet.
      > 
      > 
      > Andrei
     
     Neat! This is a great example of why D kicks so much ass :)
 
 Uh, yes. It looks like the kind of thing I would do, show to others and
 hear they say "Meh.. Whatever". I'm really exponentially developing a
 liking to the D community, even though I didn't event get to code
 anything serious yet.
 
 This simply rocks. Keep it up, Andrei!
 
 --
 Atenciosamente / Sincerely,
 Guilherme ("n2liquid") Vieira


 
 Glad you folks like it. There's a little story behind this. I first read
 Dominus' book chapter years ago, around the time I'd decided to write
 TDPL. Back then I was thinking - it would just be so cool to be able to
 define generic memoization in D. I tried my hand at an implementation.
 But D had no tuples, no aliasing for functions, no good variadics, and
 even if you could find a way to pack parameters, associative arrays had
 plenty of related issues.
 
 I'd given up on that and forgot most about it, until today. It was nice
 to reckon that getting it done took about a dozen lines and about as
 many minutes. We really have come a very long way.
 
 Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work
 for overloaded functions, and associative arrays don't work for ubyte[4]
 keys... still a ways to go.


Well, it's definitely cool.

- Jonathan M Davis
Jan 03 2011
prev sibling next sibling parent reply Guilherme Vieira <n2.nitrogen gmail.com> writes:
On Tue, Jan 4, 2011 at 3:27 AM, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:


 On 1/3/11 11:01 PM, Guilherme Vieira wrote:


 On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a a.a> wrote:

    "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org
    <mailto:SeeWebsiteForEmail erdani.org>> wrote in message

    news:ifu70u$2dvs$1 digitalmars.com...
     >I just added a higher-order function memoize to std.functional which
 I
     >think is pretty cool. See the docs here:
     >
     >

 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize
     >
     > I'm also thinking of adding that cutting-edge directory as a
    place for
     > storing documentation for commits that are in flux but not
 officially
     > released yet.
     >
     >
     > Andrei

    Neat! This is a great example of why D kicks so much ass :)


 Uh, yes. It looks like the kind of thing I would do, show to others and
 hear they say "Meh.. Whatever". I'm really exponentially developing a
 liking to the D community, even though I didn't event get to code
 anything serious yet.

 This simply rocks. Keep it up, Andrei!

 --
 Atenciosamente / Sincerely,
 Guilherme ("n2liquid") Vieira


 Glad you folks like it. There's a little story behind this. I first read
 Dominus' book chapter years ago, around the time I'd decided to write TDPL.
 Back then I was thinking - it would just be so cool to be able to define
 generic memoization in D. I tried my hand at an implementation. But D had no
 tuples, no aliasing for functions, no good variadics, and even if you could
 find a way to pack parameters, associative arrays had plenty of related
 issues.

 I'd given up on that and forgot most about it, until today. It was nice to
 reckon that getting it done took about a dozen lines and about as many
 minutes. We really have come a very long way.

 Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work for
 overloaded functions, and associative arrays don't work for ubyte[4] keys...
 still a ways to go.


 Andrei


Is there really need for ParameterTypeTuple? I figured this works:

template memoize(alias fun, uint maxSize = uint.max)

{

    auto memoize(Args...)(Args args)

    {

        static typeof(fn(args))[Tuple!(typeof(args))] memo;

        auto t = tuple(args);

        auto p = t in memo;

        if (p) return *p;

        static if (maxSize != uint.max)

        {

            if (memo.length >= maxSize) memo = null;

        }

        auto r = fun(args);

        //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for

 parameters ", t);


        memo[t] = r;

        return r;

    }

}


-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
Jan 03 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 12:30 AM, Guilherme Vieira wrote:

 Is there really need for ParameterTypeTuple? I figured this works:

         template memoize(alias fun, uint maxSize = uint.max)

         {

              auto memoize(Args...)(Args args)


[snip]

That would create several caches, depending on calls with convertible 
arguments.

Andrei
Jan 04 2011
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:


 On 1/4/11 12:30 AM, Guilherme Vieira wrote:

 Is there really need for ParameterTypeTuple? I figured this works:

         template memoize(alias fun, uint maxSize = uint.max)

         {

              auto memoize(Args...)(Args args)


 [snip]

 That would create several caches, depending on calls with convertible  
 arguments.

 Andrei


So the solution should use a struct with overloaded opCall, then.

-- 
Simen
Jan 04 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 7:54 AM, Simen kjaeraas wrote:

 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:


 On 1/4/11 12:30 AM, Guilherme Vieira wrote:

 Is there really need for ParameterTypeTuple? I figured this works:

 template memoize(alias fun, uint maxSize = uint.max)

 {

 auto memoize(Args...)(Args args)


 [snip]

 That would create several caches, depending on calls with convertible
 arguments.

 Andrei


 So the solution should use a struct with overloaded opCall, then.


1. I think it's best to map a function to a function for best impedance 
match.

2. If you memoize an overloaded function, you _do_ want several caches.


Andrei
Jan 04 2011
parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:


 2. If you memoize an overloaded function, you _do_ want several caches.


Yeah. Even I managed to think about that a few seconds after posting. :p


-- 
Simen
Jan 04 2011
prev sibling next sibling parent Guilherme Vieira <n2.nitrogen gmail.com> writes:
On Tue, Jan 4, 2011 at 4:30 AM, Guilherme Vieira <n2.nitrogen gmail.com>wrote:


 On Tue, Jan 4, 2011 at 3:27 AM, Andrei Alexandrescu <
 SeeWebsiteForEmail erdani.org> wrote:


 On 1/3/11 11:01 PM, Guilherme Vieira wrote:


 On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a a.a> wrote:

    "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org
    <mailto:SeeWebsiteForEmail erdani.org>> wrote in message

    news:ifu70u$2dvs$1 digitalmars.com...
     >I just added a higher-order function memoize to std.functional which
 I
     >think is pretty cool. See the docs here:
     >
     >

 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize
     >
     > I'm also thinking of adding that cutting-edge directory as a
    place for
     > storing documentation for commits that are in flux but not
 officially
     > released yet.
     >
     >
     > Andrei

    Neat! This is a great example of why D kicks so much ass :)


 Uh, yes. It looks like the kind of thing I would do, show to others and
 hear they say "Meh.. Whatever". I'm really exponentially developing a
 liking to the D community, even though I didn't event get to code
 anything serious yet.

 This simply rocks. Keep it up, Andrei!

 --
 Atenciosamente / Sincerely,
 Guilherme ("n2liquid") Vieira


 Glad you folks like it. There's a little story behind this. I first read
 Dominus' book chapter years ago, around the time I'd decided to write TDPL.
 Back then I was thinking - it would just be so cool to be able to define
 generic memoization in D. I tried my hand at an implementation. But D had no
 tuples, no aliasing for functions, no good variadics, and even if you could
 find a way to pack parameters, associative arrays had plenty of related
 issues.

 I'd given up on that and forgot most about it, until today. It was nice to
 reckon that getting it done took about a dozen lines and about as many
 minutes. We really have come a very long way.

 Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work for
 overloaded functions, and associative arrays don't work for ubyte[4] keys...
 still a ways to go.


 Andrei


 Is there really need for ParameterTypeTuple? I figured this works:

  template memoize(alias fun, uint maxSize = uint.max)

 {

     auto memoize(Args...)(Args args)

     {

         static typeof(fn(args))[Tuple!(typeof(args))] memo;

         auto t = tuple(args);

         auto p = t in memo;

         if (p) return *p;

         static if (maxSize != uint.max)

         {

             if (memo.length >= maxSize) memo = null;

         }

         auto r = fun(args);

         //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for

 parameters ", t);


          memo[t] = r;

         return r;

     }

 }


 --
 Atenciosamente / Sincerely,
 Guilherme ("n2liquid") Vieira


Dirty fix for the ubyte[4] problem:

struct wrapper(T)

{

    this(T value) { this.value = value; }

    T value;

}



 template memoize(alias fun, uint maxSize = uint.max)


{

    auto memoize(Args...)(Args args)

    {

        static wrapper!(typeof(fn(args)))[Tuple!(typeof(args))] memo;

        auto t = tuple(args);

        auto p = t in memo;

        if (p) return p.value;

        static if (maxSize != uint.max)

        {

            if (memo.length >= maxSize) memo = null;

        }

        auto r = fun(args);

        //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for

 parameters ", t);


        memo[t] = wrapper!(typeof(fn(args)))(r);

        return r;

    }

}


But I think I get why ParameterTypeTuple is important. My version of the
template give ugly error messages when I call a memoized function with the
wrong parameter types. ParameterTypeTuple would make them go away, right?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
Jan 03 2011
prev sibling next sibling parent reply %u <wfunction hotmail.com> writes:
Hi,

I just wanted to say, it's funny how I did the *EXACT* same thing only **a few
days ago**:


Not counting the braces, the actual code is just 4 lines for the compile-time
version, and 5 lines for the run-time version. The page above only has a link to
one of these; both of the versions are here:
http://ideone.com/q8lvf

Pretty short, eh? I doubt that it can get any shorter than that code. :) Feel
free
to use my version inside the library. ("I hereby release the code to the public
domain," to cover the legal stuff.)
Jan 04 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 2:48 AM, %u wrote:

 Hi,

 I just wanted to say, it's funny how I did the *EXACT* same thing only **a few
 days ago**:


 Not counting the braces, the actual code is just 4 lines for the compile-time
 version, and 5 lines for the run-time version. The page above only has a link
to
 one of these; both of the versions are here:
 http://ideone.com/q8lvf

 Pretty short, eh? I doubt that it can get any shorter than that code. :) Feel
free
 to use my version inside the library. ("I hereby release the code to the public
 domain," to cover the legal stuff.)


Wow. I swear I didn't see this! "Great minds think alike" eh? :o)

I think your implementation that defines the function directly is 
better. However, when we plan to make the whole thing work with 
overloading, we'll probably want to go with the template solution.

BTW, right now ParameterTypeTuple catches the lexically first overload 
or something. Instantiating memoize!sqrt latches on sqrt(float). We need 
to generalize ParameterTypeTuple to work with overloaded functions. This 
is where implicit flattening of tuples is going to turn a bit troublesome.


Andrei
Jan 04 2011
parent reply %u <wfunction hotmail.com> writes:
Andrei:

 "Great minds think alike" eh? :o)


Definitely! :]



 BTW, right now ParameterTypeTuple catches the lexically first overload or


something. Instantiating memoize!sqrt latches on sqrt(float). We need to
generalize ParameterTypeTuple to work with overloaded functions. This is where
implicit flattening of tuples is going to turn a bit troublesome.

Huh... I didn't know that. There *should* be a way to make the user get around
it,
such as forcing him to supply the argument list in the template. I'll see if I
can
find a fix for it.

By the way, did you look at my run-time implementation? If you leave a
compile-time version in the library, I highly suggest you leave the run-time
version as well, since it can come handy if the code is external and not known
at
compile-time.
Jan 04 2011
parent reply %u <wfunction hotmail.com> writes:
Hi all,

How does this work, with respect to overloading?

auto memo(alias Fn, TParams...)(TParams args) if (isCallable!(Fn))
{
    static typeof(Func(args))[Tuple!(TParams)] cache;
    auto key = tuple(args);
    return key in cache ? cache[key] : (cache[key] = Func(args));
}

uint fib(uint n)
{ return n > 1 ? memo!(fib)(n - 1) + memo!(fib)(n - 2) : n; }
ulong fib(ulong n)
{ return n > 1 ? memo!(fib)(n - 1) + memo!(fib)(n - 2) : n; }

void main() { memoize(&fib); std.stdio.writefln("%d", fib(50)); }


It seems like it's fixed, right?
Jan 04 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 2:57 PM, %u wrote:

 Hi all,

 How does this work, with respect to overloading?

 auto memo(alias Fn, TParams...)(TParams args) if (isCallable!(Fn))
 {
      static typeof(Func(args))[Tuple!(TParams)] cache;
      auto key = tuple(args);
      return key in cache ? cache[key] : (cache[key] = Func(args));
 }

 uint fib(uint n)
 { return n>  1 ? memo!(fib)(n - 1) + memo!(fib)(n - 2) : n; }
 ulong fib(ulong n)
 { return n>  1 ? memo!(fib)(n - 1) + memo!(fib)(n - 2) : n; }

 void main() { memoize(&fib); std.stdio.writefln("%d", fib(50)); }


 It seems like it's fixed, right?


There's still the risk of keeping multiple hashes. Consider:

ulong fun(ulong n) { ... }
alias memoize!fun mfun;

mfun(5); // creates hash ulong[int]
mfun(5u); // creates hash ulong[uint]
mfun('5'); // creates hash ulong[char]


Andrei
Jan 04 2011
next sibling parent reply %u <wfunction hotmail.com> writes:
 There's still the risk of keeping multiple hashes. Consider:



 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;



 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint]
 mfun('5'); // creates hash ulong[char]



Ohhh I see... so you're basically looking for a compile-time version of overload
resolution, right? Because things seem to be getting complicated very quickly.



(An unrelated side note: I'm new to newsgroups, and I was wondering, what
program
do people mainly use for communication? I'm using the web interface, but do most
people use Thunderbird or something? Thank you!)
Jan 04 2011
next sibling parent Michal Minich <michal.minich gmail.com> writes:
On Tue, 04 Jan 2011 22:49:11 +0000, %u wrote:


 (An unrelated side note: I'm new to newsgroups, and I was wondering,
 what program do people mainly use for communication? I'm using the web
 interface, but do most people use Thunderbird or something? Thank you!)


Also outlook express, omea reader, pan and there many more nntp new 
readers; any is much better than the web interface (which is used mainly 
as a temp solution or to make web links to posts).
Jan 04 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, January 04, 2011 14:49:11 %u wrote:

 There's still the risk of keeping multiple hashes. Consider:
 
 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;
 
 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint]
 mfun('5'); // creates hash ulong[char]


 
 Ohhh I see... so you're basically looking for a compile-time version of
 overload resolution, right? Because things seem to be getting complicated
 very quickly.
 
 
 
 (An unrelated side note: I'm new to newsgroups, and I was wondering, what
 program do people mainly use for communication? I'm using the web
 interface, but do most people use Thunderbird or something? Thank you!)


I signed up for the mailing list and use kmail as my mail client. But if you
use 
the mailing list, then you can use whatever works with your e-mail service, 
which would presumably include whatever mail clients work on your system. I was 
using knode (KDE's newsreader program), but then the state of messages (like 
which you've read and the like) is only on one machine. With the mailing list 
and IMAP, I can have it synced between machines.

- Jonathan M Davis
Jan 04 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 4:49 PM, %u wrote:

 There's still the risk of keeping multiple hashes. Consider:



 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;



 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint]
 mfun('5'); // creates hash ulong[char]



 Ohhh I see... so you're basically looking for a compile-time version of
overload
 resolution, right? Because things seem to be getting complicated very quickly.


It's not that complicated; we'll be able to achieve it somehow. 
Overloads are compile-time entities so they should be easily inspectable.


 (An unrelated side note: I'm new to newsgroups, and I was wondering, what
program
 do people mainly use for communication? I'm using the web interface, but do
most
 people use Thunderbird or something? Thank you!)


I use Thunderbird with NNTP, which is better than the Web interface.


Andrei
Jan 04 2011
parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Tue, 04 Jan 2011 17:06:45 -0600, Andrei Alexandrescu wrote:


 On 1/4/11 4:49 PM, %u wrote:

 There's still the risk of keeping multiple hashes. Consider:



 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;



 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint] mfun('5'); // creates hash
 ulong[char]



 Ohhh I see... so you're basically looking for a compile-time version of
 overload resolution, right? Because things seem to be getting
 complicated very quickly.


 
 It's not that complicated; we'll be able to achieve it somehow.
 Overloads are compile-time entities so they should be easily
 inspectable.


Since this is likely to be useful in other cases as well, maybe it would 
be better to make a general template that selects an overload?  So you'd 
use it like this:

  alias memoize!(selectOverload!(sqrt, double)) msqrt;

A first step towards this would be to make __traits(getOverloads) work 
with module-level functions.  Currently it only works for member 
functions.  Also it would probably be better if it accepted a function 
alias instead of a string containing the function name.

Anyway, I've been able to make the following work for selecting overloads 
of member functions:


import std.traits, std.stdio;

struct S
{
    void foo(int i, double d) { writeln("Overload 1"); }
    void foo(double d, int i) { writeln("Overload 2"); }

    void test()
    {
        alias selectOverload!(S, "foo", int, double) bar;
        bar(1, 3.0);    // Prints "Overload 1"

        alias selectOverload!(S, "foo", double, int) baz;
        baz(4.0, 2);    // Prints "Overload 2"
    }
}

void main()
{
    S s;
    s.test();
}



template selectOverload(T, string fun, Params...)
{
    alias selectOverloadImpl!(Params.length, Params,
        __traits(getOverloads, T, fun)) selectOverload;
}


template selectOverloadImpl(size_t lenP, A...)
{
    static assert (A.length > lenP, "No overload matches");
    static if (equalTuples!(lenP,
        A[0 .. lenP],
        ParameterTypeTuple!(A[lenP])))
    {
        alias A[lenP] selectOverloadImpl;
    }
    else
    {
        alias selectOverloadImpl!(lenP, A[0 .. lenP], A[lenP+1 .. $])
            selectOverloadImpl;
    }
}


template equalTuples(size_t len, T...)
{
    static if (len == 0 && T.length == 0)
        enum equalTuples = true;
    else static if (T.length != len*2)
        enum equalTuples = false;
    else static if (!is (T[0] == T[len]))
        enum equalTuples = false;
    else
        enum equalTuples =
            equalTuples!(len-1, T[1 .. len], T[len+1 .. $]);
}
Jan 05 2011
parent reply Max Samukha <spambox d-coding.com> writes:
On 01/05/2011 11:21 AM, Lars T. Kyllingstad wrote:

 On Tue, 04 Jan 2011 17:06:45 -0600, Andrei Alexandrescu wrote:


 On 1/4/11 4:49 PM, %u wrote:

 There's still the risk of keeping multiple hashes. Consider:



 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;



 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint] mfun('5'); // creates hash
 ulong[char]



 Ohhh I see... so you're basically looking for a compile-time version of
 overload resolution, right? Because things seem to be getting
 complicated very quickly.


 It's not that complicated; we'll be able to achieve it somehow.
 Overloads are compile-time entities so they should be easily
 inspectable.


 Since this is likely to be useful in other cases as well, maybe it would
 be better to make a general template that selects an overload?  So you'd
 use it like this:

    alias memoize!(selectOverload!(sqrt, double)) msqrt;

 A first step towards this would be to make __traits(getOverloads) work
 with module-level functions.  Currently it only works for member
 functions.  Also it would probably be better if it accepted a function
 alias instead of a string containing the function name.


__traits(getOverloads) does work with module level functions if you pass 
a module alias to it. I predict you guys will soon need (and I am happy 
you are approaching this way-point) a means to get from a symbol to its 
parent, that is __traits(parent, symbol).

So there are two ways to solve the problem:

1. Add a version of __traits(getOverloads) that would not require a 
parent as you suggested.
2. Add __traits(parent), so one could do:

void foo();
void foo(int);

alias __traits(getOverloads, __traits(parent, foo), "foo") fooOverloads;

I prefer the second or both, because the parent trait is needed in other 
scenarios.


 Anyway, I've been able to make the following work for selecting overloads
 of member functions:


 import std.traits, std.stdio;

 struct S
 {
      void foo(int i, double d) { writeln("Overload 1"); }
      void foo(double d, int i) { writeln("Overload 2"); }

      void test()
      {
          alias selectOverload!(S, "foo", int, double) bar;
          bar(1, 3.0);    // Prints "Overload 1"

          alias selectOverload!(S, "foo", double, int) baz;
          baz(4.0, 2);    // Prints "Overload 2"
      }
 }

 void main()
 {
      S s;
      s.test();
 }



 template selectOverload(T, string fun, Params...)
 {
      alias selectOverloadImpl!(Params.length, Params,
          __traits(getOverloads, T, fun)) selectOverload;
 }


 template selectOverloadImpl(size_t lenP, A...)
 {
      static assert (A.length>  lenP, "No overload matches");
      static if (equalTuples!(lenP,
          A[0 .. lenP],
          ParameterTypeTuple!(A[lenP])))
      {
          alias A[lenP] selectOverloadImpl;
      }
      else
      {
          alias selectOverloadImpl!(lenP, A[0 .. lenP], A[lenP+1 .. $])
              selectOverloadImpl;
      }
 }


 template equalTuples(size_t len, T...)
 {
      static if (len == 0&&  T.length == 0)
          enum equalTuples = true;
      else static if (T.length != len*2)
          enum equalTuples = false;
      else static if (!is (T[0] == T[len]))
          enum equalTuples = false;
      else
          enum equalTuples =
              equalTuples!(len-1, T[1 .. len], T[len+1 .. $]);
 }
Jan 05 2011
parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Wed, 05 Jan 2011 12:07:50 +0200, Max Samukha wrote:


 On 01/05/2011 11:21 AM, Lars T. Kyllingstad wrote:

 On Tue, 04 Jan 2011 17:06:45 -0600, Andrei Alexandrescu wrote:


 On 1/4/11 4:49 PM, %u wrote:

 There's still the risk of keeping multiple hashes. Consider:



 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;



 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint] mfun('5'); // creates hash
 ulong[char]



 Ohhh I see... so you're basically looking for a compile-time version
 of overload resolution, right? Because things seem to be getting
 complicated very quickly.


 It's not that complicated; we'll be able to achieve it somehow.
 Overloads are compile-time entities so they should be easily
 inspectable.


 Since this is likely to be useful in other cases as well, maybe it
 would be better to make a general template that selects an overload? 
 So you'd use it like this:

    alias memoize!(selectOverload!(sqrt, double)) msqrt;

 A first step towards this would be to make __traits(getOverloads) work
 with module-level functions.  Currently it only works for member
 functions.  Also it would probably be better if it accepted a function
 alias instead of a string containing the function name.


 
 __traits(getOverloads) does work with module level functions if you pass
 a module alias to it.


Cool!  I didn't know that.  Here's an updated version, where 
selectOverload works with both module-level and member functions:


module test;
import std.traits, std.stdio;

void foo(int i, double d) { writeln("Overload 1"); }
void foo(double d, int i) { writeln("Overload 2"); }

void main()
{
    alias selectOverload!(test, "foo", int, double) bar;
    bar(1, 3.0);    // Prints "Overload 1"

    alias selectOverload!(test, "foo", double, int) baz;
    baz(4.0, 2);    // Prints "Overload 2"
}



template selectOverload(alias parent, string fun, Params...)
{
    alias selectOverloadImpl!(Params.length, Params,
        __traits(getOverloads, parent, fun)) selectOverload;
}


template selectOverloadImpl(size_t lenP, A...)
{
    static assert (A.length > lenP, "No overload matches");
    static if (equalTuples!(lenP,
        A[0 .. lenP],
        ParameterTypeTuple!(A[lenP])))
    {
        alias A[lenP] selectOverloadImpl;
    }
    else
    {
        alias selectOverloadImpl!(lenP, A[0 .. lenP], A[lenP+1 .. $])
            selectOverloadImpl;
    }
}


template equalTuples(size_t len, T...)
{
    static if (len == 0 && T.length == 0)
        enum equalTuples = true;
    else static if (T.length != len*2)
        enum equalTuples = false;
    else static if (!is (T[0] == T[len]))
        enum equalTuples = false;
    else
        enum equalTuples =
            equalTuples!(len-1, T[1 .. len], T[len+1 .. $]);
}
Jan 05 2011
parent reply Max Samukha <spambox d-coding.com> writes:
On 01/05/2011 12:24 PM, Lars T. Kyllingstad wrote:

 On Wed, 05 Jan 2011 12:07:50 +0200, Max Samukha wrote:


 On 01/05/2011 11:21 AM, Lars T. Kyllingstad wrote:

 On Tue, 04 Jan 2011 17:06:45 -0600, Andrei Alexandrescu wrote:


 On 1/4/11 4:49 PM, %u wrote:

 There's still the risk of keeping multiple hashes. Consider:



 ulong fun(ulong n) { ... }
 alias memoize!fun mfun;



 mfun(5); // creates hash ulong[int]
 mfun(5u); // creates hash ulong[uint] mfun('5'); // creates hash
 ulong[char]



 Ohhh I see... so you're basically looking for a compile-time version
 of overload resolution, right? Because things seem to be getting
 complicated very quickly.


 It's not that complicated; we'll be able to achieve it somehow.
 Overloads are compile-time entities so they should be easily
 inspectable.


 Since this is likely to be useful in other cases as well, maybe it
 would be better to make a general template that selects an overload?
 So you'd use it like this:

     alias memoize!(selectOverload!(sqrt, double)) msqrt;

 A first step towards this would be to make __traits(getOverloads) work
 with module-level functions.  Currently it only works for member
 functions.  Also it would probably be better if it accepted a function
 alias instead of a string containing the function name.


 __traits(getOverloads) does work with module level functions if you pass
 a module alias to it.


 Cool!  I didn't know that.  Here's an updated version, where
 selectOverload works with both module-level and member functions:


 module test;
 import std.traits, std.stdio;

 void foo(int i, double d) { writeln("Overload 1"); }
 void foo(double d, int i) { writeln("Overload 2"); }

 void main()
 {
      alias selectOverload!(test, "foo", int, double) bar;
      bar(1, 3.0);    // Prints "Overload 1"

      alias selectOverload!(test, "foo", double, int) baz;
      baz(4.0, 2);    // Prints "Overload 2"
 }



 template selectOverload(alias parent, string fun, Params...)
 {
      alias selectOverloadImpl!(Params.length, Params,
          __traits(getOverloads, parent, fun)) selectOverload;
 }


 template selectOverloadImpl(size_t lenP, A...)
 {
      static assert (A.length>  lenP, "No overload matches");
      static if (equalTuples!(lenP,
          A[0 .. lenP],
          ParameterTypeTuple!(A[lenP])))
      {
          alias A[lenP] selectOverloadImpl;
      }
      else
      {
          alias selectOverloadImpl!(lenP, A[0 .. lenP], A[lenP+1 .. $])
              selectOverloadImpl;
      }
 }


 template equalTuples(size_t len, T...)
 {
      static if (len == 0&&  T.length == 0)
          enum equalTuples = true;
      else static if (T.length != len*2)
          enum equalTuples = false;
      else static if (!is (T[0] == T[len]))
          enum equalTuples = false;
      else
          enum equalTuples =
              equalTuples!(len-1, T[1 .. len], T[len+1 .. $]);
 }


Nice! Though I think that overloads should be selected not by type 
equality but by regular overload resolution rules. That is the template 
should take not parameter but argument types.
Jan 05 2011
parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Wed, 05 Jan 2011 13:40:05 +0200, Max Samukha wrote:


 On 01/05/2011 12:24 PM, Lars T. Kyllingstad wrote:

 On Wed, 05 Jan 2011 12:07:50 +0200, Max Samukha wrote:


 On 01/05/2011 11:21 AM, Lars T. Kyllingstad wrote:

 On Tue, 04 Jan 2011 17:06:45 -0600, Andrei Alexandrescu wrote:

 [...]
 Overloads are compile-time entities so they should be easily
 inspectable.


 Since this is likely to be useful in other cases as well, maybe it
 would be better to make a general template that selects an overload?
 So you'd use it like this:

     alias memoize!(selectOverload!(sqrt, double)) msqrt;

 A first step towards this would be to make __traits(getOverloads)
 work with module-level functions.  Currently it only works for member
 functions.  Also it would probably be better if it accepted a
 function alias instead of a string containing the function name.


 __traits(getOverloads) does work with module level functions if you
 pass a module alias to it.


 Cool!  I didn't know that.  Here's an updated version, where
 selectOverload works with both module-level and member functions:

 [...]


 
 Nice! Though I think that overloads should be selected not by type
 equality but by regular overload resolution rules. That is the template
 should take not parameter but argument types.


I agree.  It is actually trivial to modify my example by replacing 
equalTuple!() with implicitlyConvertibleTuple!() which uses an is(T1:T2) 
test instead of is(T1==T2).  But that would make the template select the 
first possible match, instead of the "best match" resolution used by the 
compiler, which is often not what you want.  It would fail miserably for 
the sqrt() example, for instance, by always picking out sqrt(float).

In the end, I think implementing full overload resolution in the library 
will be so hairy it will be better to just add __traits(selectOverload).  
This doesn't look too bad:

  alias memoize!(__traits(selectOverload, sqrt, double)) msqrt;

And if, one day, __traits gets replaced by the meta namespace (bug 3702, 
one of the highest-voted in Bugzilla), it actually looks pretty good:

  alias memoize!(meta.selectOverload(sqrt, double)) msqrt;

;)
-Lars
Jan 05 2011
parent Max Samukha <spambox d-coding.com> writes:
On 01/05/2011 02:12 PM, Lars T. Kyllingstad wrote:

 On Wed, 05 Jan 2011 13:40:05 +0200, Max Samukha wrote:


 On 01/05/2011 12:24 PM, Lars T. Kyllingstad wrote:

 On Wed, 05 Jan 2011 12:07:50 +0200, Max Samukha wrote:


 On 01/05/2011 11:21 AM, Lars T. Kyllingstad wrote:

 On Tue, 04 Jan 2011 17:06:45 -0600, Andrei Alexandrescu wrote:

 [...]
 Overloads are compile-time entities so they should be easily
 inspectable.


 Since this is likely to be useful in other cases as well, maybe it
 would be better to make a general template that selects an overload?
 So you'd use it like this:

      alias memoize!(selectOverload!(sqrt, double)) msqrt;

 A first step towards this would be to make __traits(getOverloads)
 work with module-level functions.  Currently it only works for member
 functions.  Also it would probably be better if it accepted a
 function alias instead of a string containing the function name.


 __traits(getOverloads) does work with module level functions if you
 pass a module alias to it.


 Cool!  I didn't know that.  Here's an updated version, where
 selectOverload works with both module-level and member functions:

 [...]


 Nice! Though I think that overloads should be selected not by type
 equality but by regular overload resolution rules. That is the template
 should take not parameter but argument types.


 I agree.  It is actually trivial to modify my example by replacing
 equalTuple!() with implicitlyConvertibleTuple!() which uses an is(T1:T2)
 test instead of is(T1==T2).  But that would make the template select the
 first possible match, instead of the "best match" resolution used by the
 compiler, which is often not what you want.  It would fail miserably for
 the sqrt() example, for instance, by always picking out sqrt(float).

 In the end, I think implementing full overload resolution in the library
 will be so hairy it will be better to just add __traits(selectOverload).
 This doesn't look too bad:

    alias memoize!(__traits(selectOverload, sqrt, double)) msqrt;

 And if, one day, __traits gets replaced by the meta namespace (bug 3702,
 one of the highest-voted in Bugzilla), it actually looks pretty good:

    alias memoize!(meta.selectOverload(sqrt, double)) msqrt;

 ;)
 -Lars


I agree with every point. Now time for a compiler patch ;)
Jan 05 2011
prev sibling parent %u <wfunction hotmail.com> writes:
It seems to me that this is an unsolvable problem without built-in compiler
support using __traits(getOverloads, Func), since without knowing all the
overloads of a function, you can't possibly write a template to widen the
arguments to the correct parameter types. (The current getOverloads needs a
class
argument, but we need one without.)

Another solution would be another form of an "is" expression that gives you the
compile-time parameter type tuples of a called method, like:

static if (is(Func(args) ParamTypeTuple == function))
{ ... }

Then we can get the type tuples of the overload of the function *after* the
binding, rather than *before*.
Jan 04 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 2:48 AM, %u wrote:

 Hi,

 I just wanted to say, it's funny how I did the *EXACT* same thing only **a few
 days ago**:


 Not counting the braces, the actual code is just 4 lines for the compile-time
 version, and 5 lines for the run-time version. The page above only has a link
to
 one of these; both of the versions are here:
 http://ideone.com/q8lvf

 Pretty short, eh? I doubt that it can get any shorter than that code. :) Feel
free
 to use my version inside the library. ("I hereby release the code to the public
 domain," to cover the legal stuff.)


Just posted a response to that thread, too. Somehow all that thread 
should spill into reddit :o).

One thing one figures by looking at that thread is not what's been done, 
but how much bigger the potential is.


Andrei
Jan 04 2011
parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:


 On 1/4/11 2:48 AM, %u wrote:

 Hi,

 I just wanted to say, it's funny how I did the *EXACT* same thing only  
 **a few
 days ago**:


 Not counting the braces, the actual code is just 4 lines for the  
 compile-time
 version, and 5 lines for the run-time version. The page above only has  
 a link to
 one of these; both of the versions are here:
 http://ideone.com/q8lvf

 Pretty short, eh? I doubt that it can get any shorter than that code.  
 :) Feel free
 to use my version inside the library. ("I hereby release the code to  
 the public
 domain," to cover the legal stuff.)


 Just posted a response to that thread, too. Somehow all that thread  
 should spill into reddit :o).


I took the liberty of spilling it:

http://www.reddit.com/r/programming/comments/ew0c7/coolest_template_metaprogramming_tricks_in_d/


-- 
Simen
Jan 04 2011
prev sibling parent reply spir <denis.spir gmail.com> writes:
On Mon, 03 Jan 2011 23:27:22 -0600
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:


 Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work=20
 for overloaded functions, and associative arrays don't work for ubyte[4]=


=20

 keys... still a ways to go.


Could you or someone else expand on this?

Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Jan 04 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 6:32 AM, spir wrote:

 On Mon, 03 Jan 2011 23:27:22 -0600
 Andrei Alexandrescu<SeeWebsiteForEmail erdani.org>  wrote:


 Nevertheless, I found two issues: one, ParameterTypeTuple doesn't work
 for overloaded functions, and associative arrays don't work for ubyte[4]
 keys... still a ways to go.


 Could you or someone else expand on this?

 Denis
 -- -- -- -- -- -- --
 vit esse estrany ☣

 spir.wikidot.com


An example in Higher Order Perl is memoizing a RGB to CMYK function:

ubyte[4] rgb2cmyk(ubyte[3] rgb)
{
     ubyte[4] result = void;
     result[0] = cast(ubyte)(255 - rgb[0]);
     result[1] = cast(ubyte)(255 - rgb[1]);
     result[2] = cast(ubyte)(255 - rgb[2]);
     result[3] = min(result[0], result[1], result[2]);
     result[0] -= result[3];
     result[1] -= result[3];
     result[2] -= result[3];
     return result;
}

Trying to memoize this yields a range error at runtime.


Andrei
Jan 04 2011
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:


 return result;


Since when is it legal to return a local array?

-manfred
Jan 04 2011
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 12:13 PM, Manfred_Nowak wrote:

 Andrei Alexandrescu wrote:


 return result;


 Since when is it legal to return a local array?

 -manfred


Since a few releases ago fixed-size arrays are value types.

Andrei
Jan 04 2011
parent reply "Manfred_Nowak" <svv1999 hotmail.com> writes:
Andrei Alexandrescu wrote:


 Since a few releases ago


upps. sorry for not reading the docs.

-manfred
Jan 04 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 12:44 PM, Manfred_Nowak wrote:

 Andrei Alexandrescu wrote:


 Since a few releases ago


 upps. sorry for not reading the docs.

 -manfred


BTW I think the rgb2cmyk implementation in Higher Order Perl (which I 
copied) is a bit convoluted. A simplified version is:

ubyte[4] rgb2cmyk(ubyte[3] rgb)
{
     immutable m = max(rgb[0], rgb[1], rgb[2]);
     return [ cast(ubyte)(m - rgb[0]), cast(ubyte)(m - rgb[1]),
             cast(ubyte)(m - rgb[2]), ~m ];
}

Two nice typing touches: max does not necessitate a cast because it's 
implemented to return ubyte for ubytes, and ~m also doesn't need a cast 
thanks to value range propagation.

I don't know how to get rid of the remaining casts.


Andrei
Jan 04 2011
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 04 Jan 2011 14:16:27 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 On 1/4/11 12:44 PM, Manfred_Nowak wrote:

 Andrei Alexandrescu wrote:


 Since a few releases ago


 upps. sorry for not reading the docs.

 -manfred


 BTW I think the rgb2cmyk implementation in Higher Order Perl (which I  
 copied) is a bit convoluted. A simplified version is:

 ubyte[4] rgb2cmyk(ubyte[3] rgb)
 {
      immutable m = max(rgb[0], rgb[1], rgb[2]);
      return [ cast(ubyte)(m - rgb[0]), cast(ubyte)(m - rgb[1]),
              cast(ubyte)(m - rgb[2]), ~m ];
 }

 Two nice typing touches: max does not necessitate a cast because it's  
 implemented to return ubyte for ubytes, and ~m also doesn't need a cast  
 thanks to value range propagation.

 I don't know how to get rid of the remaining casts.


Note that in the current compiler, this produces a heap allocation.

But if that is fixed, the following at least reduces the casts:

ubyte[4] rbg2cmyk(ubyte[3] rgb)
{
     immutable m = max(rgb[0], rgb[1], rgb[2]);
     return cast(ubyte[4])[m-rgb[0], m-rgb[1], m-rgb[2], ~m];
}

-Steve
Jan 04 2011
prev sibling parent reply Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Andrei Alexandrescu napisa=B3:


 BTW I think the rgb2cmyk implementation in Higher Order Perl (which I=20
 copied) is a bit convoluted. A simplified version is:
=20
 ubyte[4] rgb2cmyk(ubyte[3] rgb)
 {
      immutable m =3D max(rgb[0], rgb[1], rgb[2]);
      return [ cast(ubyte)(m - rgb[0]), cast(ubyte)(m - rgb[1]),
              cast(ubyte)(m - rgb[2]), ~m ];
 }
=20
 Two nice typing touches: max does not necessitate a cast because it's=20
 implemented to return ubyte for ubytes, and ~m also doesn't need a cast=20
 thanks to value range propagation.
=20
 I don't know how to get rid of the remaining casts.


I didn't know you have to put them:)

http://www.digitalmars.com/d/2.0/expression.html#ArrayLiteral

"The type of the first element is taken to be the type of all the elements,=
 and all elements are implicitly converted to that type."

But now (2.051) I tested and it seems it goes for the common type. No menti=
on on the change log... Was that changed? If so, why?

--=20
Tomek
Jan 04 2011
parent Tomek =?ISO-8859-2?Q?Sowi=F1ski?= <just ask.me> writes:
Tomek Sowi=F1ski napisa=B3:


 I didn't know you have to put them:)
=20
 http://www.digitalmars.com/d/2.0/expression.html#ArrayLiteral
=20
 "The type of the first element is taken to be the type of all the element=


s, and all elements are implicitly converted

 to that type."
=20
 But now (2.051) I tested and it seems it goes for the common type. No men=


tion on the change log... Was that changed?

 If so, why?


OK, got it:
http://www.digitalmars.com/d/archives/digitalmars/D/array_literal_element_t=
ypes_100812.html

Docs need fixing, though.

--=20
Tomek
Jan 04 2011
prev sibling parent "Nick Sabalausky" <a a.a> writes:
"Manfred_Nowak" <svv1999 hotmail.com> wrote in message 
news:Xns9E63C3202449Bsvv1999hotmailcom 65.204.18.192...

 Andrei Alexandrescu wrote:


 return result;


 Since when is it legal to return a local array?


Since D2, if it's a static array (as result is):

"Static arrays are value types. Unlike in C and D version 1, static arrays 
are passed to functions by value. Static arrays can also be returned by 
functions."
 -  http://www.digitalmars.com/d/2.0/arrays.html#static-arrays
Jan 04 2011
prev sibling next sibling parent Andrew Wiley <debio264 gmail.com> writes:
On Mon, Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:


 I just added a higher-order function memoize to std.functional which I
 think is pretty cool. See the docs here:


 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize

 I'm also thinking of adding that cutting-edge directory as a place for
 storing documentation for commits that are in flux but not officially
 released yet.



Pretty sweet, but if I'm understanding this correctly, the memoized version
of a pure function isn't pure, is it? Is there any way to get that to
happen?
Jan 03 2011
prev sibling next sibling parent Guilherme Vieira <n2.nitrogen gmail.com> writes:
On Tue, Jan 4, 2011 at 4:05 AM, Andrew Wiley <debio264 gmail.com> wrote:


 On Mon, Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu <
 SeeWebsiteForEmail erdani.org> wrote:


 I just added a higher-order function memoize to std.functional which I
 think is pretty cool. See the docs here:


 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize

 I'm also thinking of adding that cutting-edge directory as a place for
 storing documentation for commits that are in flux but not officially
 released yet.



 Pretty sweet, but if I'm understanding this correctly, the memoized version
 of a pure function isn't pure, is it? Is there any way to get that to
 happen?


memoize uses a static variable. Are static variables considered "global" as
far as pure functions are concerned? If not, then I see no reason for it not
to be pure, or am I missing something?

Additionally, I don't understand this:

"Technically the memoized function should be pure because memoize assumes it

 will always return the same result for a given tuple of arguments. However,
 memoize does not enforce that because sometimes it is useful to memoize an
 impure function, too."



Wouldn't memoizing an impure function be a.. bug? It would return the same
cached value when in fact it should have returned something else based on
external factors. When can that be desirable?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
Jan 03 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 03 January 2011 22:17:52 Guilherme Vieira wrote:

 On Tue, Jan 4, 2011 at 4:05 AM, Andrew Wiley <debio264 gmail.com> wrote:

 On Mon, Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu <
 
 SeeWebsiteForEmail erdani.org> wrote:

 I just added a higher-order function memoize to std.functional which I
 think is pretty cool. See the docs here:
 
 
 http://d-programming-language.org/cutting-edge/phobos/std_functional.htm
 l#memoize
 
 I'm also thinking of adding that cutting-edge directory as a place for
 storing documentation for commits that are in flux but not officially
 released yet.


 
 Pretty sweet, but if I'm understanding this correctly, the memoized
 version of a pure function isn't pure, is it? Is there any way to get
 that to happen?


 
 memoize uses a static variable. Are static variables considered "global" as
 far as pure functions are concerned? If not, then I see no reason for it
 not to be pure, or am I missing something?


 
pure functions cannot access mutable globals or static variables. If they
could, 
they could end up returning a different result with the same parameters because 
the global or static variable changed.
 

 Additionally, I don't understand this:
 
 "Technically the memoized function should be pure because memoize assumes
 it
 

 will always return the same result for a given tuple of arguments.
 However, memoize does not enforce that because sometimes it is useful to
 memoize an impure function, too."


 
 Wouldn't memoizing an impure function be a.. bug? It would return the same
 cached value when in fact it should have returned something else based on
 external factors. When can that be desirable?


It's quite easy to have a function which you cannot actually make pure but
which 
you know to be logically pure. For instance, if a function called a C function, 
it can't be pure unless you play some games with function pointers and casting 
and the like. So, really, any function which calls a C function can't be pure. 
However, it's pretty easy to have a C function which is logically pure. So,
your 
D function is then logically pure, but it's not actually pure, so pure
functions 
can't call it. But it would work just fine with memoize. Sure, it's definitely 
less safe to use impure functions with memoize, and it could cause bugs, but 
that doesn't mean that it shouldn't necessarily be disallowed. It just means 
that if the programmer wants to use memoize, they're going to have to be aware 
that it could cause bugs if the function in question should actually be 
returning a different value on future callls.

- Jonathan M Davis
Jan 03 2011
prev sibling next sibling parent Guilherme Vieira <n2.nitrogen gmail.com> writes:
On Tue, Jan 4, 2011 at 4:48 AM, Jonathan M Davis <jmdavisProg gmx.com>wrote:


 On Monday 03 January 2011 22:17:52 Guilherme Vieira wrote:

 On Tue, Jan 4, 2011 at 4:05 AM, Andrew Wiley <debio264 gmail.com> wrote:

 On Mon, Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu <

 SeeWebsiteForEmail erdani.org> wrote:

 I just added a higher-order function memoize to std.functional which I
 think is pretty cool. See the docs here:






 http://d-programming-language.org/cutting-edge/phobos/std_functional.htm

 l#memoize

 I'm also thinking of adding that cutting-edge directory as a place for
 storing documentation for commits that are in flux but not officially
 released yet.


 Pretty sweet, but if I'm understanding this correctly, the memoized
 version of a pure function isn't pure, is it? Is there any way to get
 that to happen?


 memoize uses a static variable. Are static variables considered "global"


 as

 far as pure functions are concerned? If not, then I see no reason for it
 not to be pure, or am I missing something?


 pure functions cannot access mutable globals or static variables. If they
 could,
 they could end up returning a different result with the same parameters
 because
 the global or static variable changed.


 Additionally, I don't understand this:

 "Technically the memoized function should be pure because memoize assumes
 it


 will always return the same result for a given tuple of arguments.
 However, memoize does not enforce that because sometimes it is useful




 to

 memoize an impure function, too."


 Wouldn't memoizing an impure function be a.. bug? It would return the


 same

 cached value when in fact it should have returned something else based on
 external factors. When can that be desirable?


 It's quite easy to have a function which you cannot actually make pure but
 which
 you know to be logically pure. For instance, if a function called a C
 function,
 it can't be pure unless you play some games with function pointers and
 casting
 and the like. So, really, any function which calls a C function can't be
 pure.
 However, it's pretty easy to have a C function which is logically pure. So,
 your
 D function is then logically pure, but it's not actually pure, so pure
 functions
 can't call it. But it would work just fine with memoize. Sure, it's
 definitely
 less safe to use impure functions with memoize, and it could cause bugs,
 but
 that doesn't mean that it shouldn't necessarily be disallowed. It just
 means
 that if the programmer wants to use memoize, they're going to have to be
 aware
 that it could cause bugs if the function in question should actually be
 returning a different value on future callls.

 - Jonathan M Davis


Ah, I was under the impression that  trusted was used to force purity.
Shame.. Sorry I mixed things up.

In any case, aren't those rules a bit too rigid? No matter how you look at
memoize, it should generate pure functions (since it exhibits pure nature,
are logically pure or whatever you call it). Would it be tough on the
compiler for it to actually find if a function is pure or not by a more
detailed analysis of its behavior?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
Jan 03 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday 03 January 2011 22:59:37 Guilherme Vieira wrote:

 Ah, I was under the impression that  trusted was used to force purity.
 Shame.. Sorry I mixed things up.
 
 In any case, aren't those rules a bit too rigid? No matter how you look at
 memoize, it should generate pure functions (since it exhibits pure nature,
 are logically pure or whatever you call it). Would it be tough on the
 compiler for it to actually find if a function is pure or not by a more
 detailed analysis of its behavior?


 safe,  trusted, and  system have nothing to do with purity. If a function is 
marked as pure, then it's pure. If it's not, then it's not. End of story. Now, 
the concept of "weakly" pure functions was recently added, but all pure 
functions are still marked with pure. Strongly pure functions are pure
functions 
where all of the parameters are immutable or implicitly convertible to
immutable 
(so, immutable variables and value types). Weakly pure functions are pure 
functions whose parameters are not all immutable or implicitly convertible to 
immutable. Unlike strongly pure functions, they can alter their arguments. 
However, just like strongly pure functions, they cannot access globals or 
statics. Strongly pure functions can be optimized such that only one call to 
them is made in an expression because their return value will always be the 
same, and they cannot alter their parameters. Weakly pure functions cannot be 
optimized in that manner, but because they don't alter the global state, they 
can be safely called from strongly pure functions without violating the
strongly 
pure function's purity.

Pure is not logically pure for essentially the same reasons that const is not 
logically const. Making it logical instead of guaranteed eliminates the 
guarantees, and the compiler can no longer rely on those guarantees, making
them 
_far_ less valuable.

It is true that a memoized function must be logically pure, or you're going to 
get errors. However, if you were to force such functions to be pure, it would
be 
highly limiting. And since memoize _can't_ be pure, it would make recursion
with 
memoize impossible. True, allowing for memoized functions to be impure makes it 
so that the programmer must be more careful, but it's still quite useful - in 
fact more useful - that way. And since you _can't_ have memoize be pure anyway, 
it's not like you're losing any guarantees from the compiler like if you tried 
to make pure logically pure or const logically const.

- Jonathan M Davis
Jan 03 2011
prev sibling next sibling parent reply Guilherme Vieira <n2.nitrogen gmail.com> writes:
On Tue, Jan 4, 2011 at 5:28 AM, Jonathan M Davis <jmdavisProg gmx.com>wrote:


 On Monday 03 January 2011 22:59:37 Guilherme Vieira wrote:

 Ah, I was under the impression that  trusted was used to force purity.
 Shame.. Sorry I mixed things up.

 In any case, aren't those rules a bit too rigid? No matter how you look


 at

 memoize, it should generate pure functions (since it exhibits pure


 nature,

 are logically pure or whatever you call it). Would it be tough on the
 compiler for it to actually find if a function is pure or not by a more
 detailed analysis of its behavior?


  safe,  trusted, and  system have nothing to do with purity. If a function
 is
 marked as pure, then it's pure. If it's not, then it's not. End of story.
 Now,
 the concept of "weakly" pure functions was recently added, but all pure
 functions are still marked with pure. Strongly pure functions are pure
 functions
 where all of the parameters are immutable or implicitly convertible to
 immutable
 (so, immutable variables and value types). Weakly pure functions are pure
 functions whose parameters are not all immutable or implicitly convertible
 to
 immutable. Unlike strongly pure functions, they can alter their arguments.
 However, just like strongly pure functions, they cannot access globals or
 statics. Strongly pure functions can be optimized such that only one call
 to
 them is made in an expression because their return value will always be the
 same, and they cannot alter their parameters. Weakly pure functions cannot
 be
 optimized in that manner, but because they don't alter the global state,
 they
 can be safely called from strongly pure functions without violating the
 strongly
 pure function's purity.

 Pure is not logically pure for essentially the same reasons that const is
 not
 logically const. Making it logical instead of guaranteed eliminates the
 guarantees, and the compiler can no longer rely on those guarantees, making
 them
 _far_ less valuable.

 It is true that a memoized function must be logically pure, or you're going
 to
 get errors. However, if you were to force such functions to be pure, it
 would be
 highly limiting. And since memoize _can't_ be pure, it would make recursion
 with
 memoize impossible. True, allowing for memoized functions to be impure
 makes it
 so that the programmer must be more careful, but it's still quite useful -
 in
 fact more useful - that way. And since you _can't_ have memoize be pure
 anyway,
 it's not like you're losing any guarantees from the compiler like if you
 tried
 to make pure logically pure or const logically const.

 - Jonathan M Davis


Don't take me too seriously since I'm learning those things on-the-fly here
(I'm greedy). The const FAQ (
http://www.digitalmars.com/d/2.0/const-faq.html#logical-const) says D
doesn't support logical const because it would break transitivity, and they
deemed transitivity to be more important (Walter even thinks it's bad,
doesn't he?), so I understand why const in D is not logical const.

But in the case of memoize, aren't there things that can be done to the
language spec to allow it to be pure? Maybe by adding some language
construct, I dunno.

Or by analysis of behavior. Obviously, that wouldn't work for external C
functions, but at least memoize would be okay. Also, I'm to guess it would
be extremely hard to write a compiler that does this, but I'd just like to
confirm.

 Walter: would it be hard/impossible for the compiler to look at memoize and
tell it exhibits pure behavior and is, thus, pure?

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
Jan 03 2011
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Guilherme Vieira <n2.nitrogen gmail.com> wrote:


  Walter: would it be hard/impossible for the compiler to look at memoize  
 and
 tell it exhibits pure behavior and is, thus, pure?


The simplest solution is this:

template memoize( alias fn ) {
     static if ( isPure!fn ) {
         pure auto memoize( ParameterTypeTuple!fn ) {
             // Blah!
         }
     } else {
         auto memoize( ParameterTypeTuple!fn ) {
             // Blah!
         }

     }
}


-- 
Simen
Jan 04 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 7:59 AM, Simen kjaeraas wrote:

 Guilherme Vieira <n2.nitrogen gmail.com> wrote:


  Walter: would it be hard/impossible for the compiler to look at
 memoize and
 tell it exhibits pure behavior and is, thus, pure?


 The simplest solution is this:

 template memoize( alias fn ) {
 static if ( isPure!fn ) {
 pure auto memoize( ParameterTypeTuple!fn ) {
 // Blah!
 }
 } else {
 auto memoize( ParameterTypeTuple!fn ) {
 // Blah!
 }

 }
 }


I've been mulling over this for a while, maybe it's time to start 
discussing it.

Often you want to say "this entity is pure/const/immutable/safe... if 
this other entity is the same, or generally if this Boolean is true". So 
I was thinking of introducing e.g. a constrained pure:

template memoize( alias fn ) {
     pure(isPure!fn) auto memoize( ParameterTypeTuple!fn ) {
         ...
     }
}

So generally when you write "attribute(expression)" the attribute will 
be in effect if and only if the expression is true.

D has become very powerful at introspecting most of its own abstractions 
in the form of compile-time Booleans. This language extension would 
close the circle by allowing D to introduce attributes and qualifiers 
depending on compile-time Booleans.


Andrei
Jan 04 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 Often you want to say "this entity is pure/const/immutable/safe... if 
 this other entity is the same, or generally if this Boolean is true". So 
 I was thinking of introducing e.g. a constrained pure:
 
 template memoize( alias fn ) {
      pure(isPure!fn) auto memoize( ParameterTypeTuple!fn ) {
          ...
      }
 }


http://d.puremagic.com/issues/show_bug.cgi?id=5125

Bye,
bearophile
Jan 04 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 So generally when you write "attribute(expression)" the attribute will 
 be in effect if and only if the expression is true.


It looks acceptable. Many solutions are better than the current need to
duplicate code :-)

Regarding the purity of memoize, a kind of compiler-blessed built-in
memoization for pure functuions allows pure memoization... (It is a trusted
pure, where the trusted entity is the compiler)

Bye,
bearophile
Jan 04 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-01-04 12:53:43 -0500, bearophile <bearophileHUGS lycos.com> said:


 Regarding the purity of memoize, a kind of compiler-blessed built-in 
 memoization for pure functuions allows pure memoization... (It is a 
 trusted pure, where the trusted entity is the compiler)


One could even argue that memoize makes impure functions pure because 
as long as you don't clear the cache, memoize!func is guarantied to 
return the same value for the same arguments.

-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Jan 04 2011
parent reply "Nick Sabalausky" <a a.a> writes:
"Michel Fortin" <michel.fortin michelf.com> wrote in message 
news:ifvo9g$2d53$1 digitalmars.com...

 On 2011-01-04 12:53:43 -0500, bearophile <bearophileHUGS lycos.com> said:


 Regarding the purity of memoize, a kind of compiler-blessed built-in 
 memoization for pure functuions allows pure memoization... (It is a 
 trusted pure, where the trusted entity is the compiler)


 One could even argue that memoize makes impure functions pure because as 
 long as you don't clear the cache, memoize!func is guarantied to return 
 the same value for the same arguments.


...until maxSize is exceeded and the cache is cleared.
Jan 04 2011
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 12:27 PM, Nick Sabalausky wrote:

 "Michel Fortin"<michel.fortin michelf.com>  wrote in message
 news:ifvo9g$2d53$1 digitalmars.com...

 On 2011-01-04 12:53:43 -0500, bearophile<bearophileHUGS lycos.com>  said:


 Regarding the purity of memoize, a kind of compiler-blessed built-in
 memoization for pure functuions allows pure memoization... (It is a
 trusted pure, where the trusted entity is the compiler)


 One could even argue that memoize makes impure functions pure because as
 long as you don't clear the cache, memoize!func is guarantied to return
 the same value for the same arguments.


 ...until maxSize is exceeded and the cache is cleared.


Even before that. There may be a visible difference between the first 
invocation and all others.

Andrei
Jan 04 2011
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Nick Sabalausky:


 ...until maxSize is exceeded and the cache is cleared. 


Clearing the whole cache when it's full is a brutal behaviour, I don't like it.
See here for something better:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=126059

Bye,
bearophile
Jan 04 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 12:54 PM, bearophile wrote:

 Nick Sabalausky:


 ...until maxSize is exceeded and the cache is cleared.


 Clearing the whole cache when it's full is a brutal behaviour, I don't like
it. See here for something better:
 http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=126059

 Bye,
 bearophile


There is a difference between caching and memoization. I wouldn't want 
to burden the memoization implementation with LRU management.

Andrei
Jan 04 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 There is a difference between caching and memoization.


Yep, memoization is a special case of caching:
http://en.wikipedia.org/wiki/Memoization:
"Although related to caching, memoization refers to a specific case of this
optimization,"



 I wouldn't want to burden the memoization implementation with LRU management.


My second proposal was a LRU, but the first simpler one wasn't. Even removing
one random item when the cache memory is full (like the first inserted, so it's
not a true LRU and you don't need double links) is better than clearing the
clearing the whole memory as now.

Bye,
bearophile
Jan 04 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 1/4/11 1:29 PM, bearophile wrote:

 Andrei:


 There is a difference between caching and memoization.


 Yep, memoization is a special case of caching:
 http://en.wikipedia.org/wiki/Memoization:
 "Although related to caching, memoization refers to a specific case of this
optimization,"



 I wouldn't want to burden the memoization implementation with LRU management.


 My second proposal was a LRU, but the first simpler one wasn't. Even removing
one random item when the cache memory is full (like the first inserted, so it's
not a true LRU and you don't need double links) is better than clearing the
clearing the whole memory as now.

 Bye,
 bearophile


Removing a random element behaves surprisingly well and crossed my mind 
too. If only the built-in hash would allow such a thing...

Andrei
Jan 04 2011
prev sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-01-04 13:27:59 -0500, "Nick Sabalausky" <a a.a> said:


 "Michel Fortin" <michel.fortin michelf.com> wrote in message
 news:ifvo9g$2d53$1 digitalmars.com...

 On 2011-01-04 12:53:43 -0500, bearophile <bearophileHUGS lycos.com> said:
 

 Regarding the purity of memoize, a kind of compiler-blessed built-in
 memoization for pure functuions allows pure memoization... (It is a
 trusted pure, where the trusted entity is the compiler)


 
 One could even argue that memoize makes impure functions pure because as
 long as you don't clear the cache, memoize!func is guarantied to return
 the same value for the same arguments.


 
 ...until maxSize is exceeded and the cache is cleared.


Right, of course. I was speaking about the case where there is no 
maximum size (or maxSize == uint.max). I'm not saying it's a good idea 
in general, just that it has an interesting property.


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Jan 04 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, January 04, 2011 06:15:16 Andrei Alexandrescu wrote:

 On 1/4/11 7:59 AM, Simen kjaeraas wrote:

 Guilherme Vieira <n2.nitrogen gmail.com> wrote:

  Walter: would it be hard/impossible for the compiler to look at
 memoize and
 tell it exhibits pure behavior and is, thus, pure?


 
 The simplest solution is this:
 
 template memoize( alias fn ) {
 static if ( isPure!fn ) {
 pure auto memoize( ParameterTypeTuple!fn ) {
 // Blah!
 }
 } else {
 auto memoize( ParameterTypeTuple!fn ) {
 // Blah!
 }
 
 }
 }


 
 I've been mulling over this for a while, maybe it's time to start
 discussing it.
 
 Often you want to say "this entity is pure/const/immutable/safe... if
 this other entity is the same, or generally if this Boolean is true". So
 I was thinking of introducing e.g. a constrained pure:
 
 template memoize( alias fn ) {
      pure(isPure!fn) auto memoize( ParameterTypeTuple!fn ) {
          ...
      }
 }
 
 So generally when you write "attribute(expression)" the attribute will
 be in effect if and only if the expression is true.
 
 D has become very powerful at introspecting most of its own abstractions
 in the form of compile-time Booleans. This language extension would
 close the circle by allowing D to introduce attributes and qualifiers
 depending on compile-time Booleans.


We really do need something like this, and actually I was thinking of bringing 
it up again. The compiler should be able to determine if a template function is 
pure on its own, since it can look at all of the functions called and determine 
whether they're pure or not (the non-template functions will be obvious and the 
template ones would require the templates to be instantiated anyway, which
would 
tell the compiler whether they were pure or not if the compiler were
determining 
that, so determining whether a particular instantiation of template function
can 
be pure shouldn't be all that hard) and then make the template function pure if 
they are and impure if they're not. Having a condition for purity as you
suggest 
might be better. I don't know. It essentially requires the same thing though. 
It's just that the programmer is then making it explicit.

Regardless, we need _something_ like this or most template functions won't be 
able to be pure. And given how heavy templates are likely to be used in D - 
especially in Phobos - that seems like it would be unacceptable.

Also, nothrow and const have the same problem (and immutable too, I suppose, 
though I'm not sure that that's all that big a deal since it's likely going to 
be rare to mark a function as immutable). So, really, we need to find a way to
do 
this for all such attributes and qualifiers, not just pure. Maybe pure(), 
const(), nothrow(), and immutable() should all be introduced as you're 
suggesting with pure. It might be nice though to have the compiler be able to
do 
it for you rather than having to list every template function manually, since 
presumably, you're going to have to list them all anyway, though perhaps pure() 
and its compatriots would be useful with conditions other than function purity. 
So, maybe something like pure(auto) should be used, and then that would 
effectively lower to pure() with isPure!func for every template function called 
by that template function.

- Jonathan M Davis
Jan 04 2011
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 I just added a higher-order function memoize to std.functional which I 
 think is pretty cool. See the docs here:


I am not sure it's a good idea to put inside the D docs a link to the Google
PDF visualizer.

I suggest to remove the fact() example, because given the other fib() example,
it adds nothing. Or if you want to keep it, you may differentiate it, showing
something different, like putting the alias outside (and renaming the function).



The maxSize parameter is a cutoff for the cache size. If upon a miss the length
of the hash table is found to be maxSize, the table is simply cleared.<


Two alternatives I'd like better:
1) The simpler alternative: when maxSize!=uint.max the associative array values
are linked in a singly linked list. When there's a cache miss and aa.length >
maxSize then the last item of the linked list is removed (there is a pointer to
the last item that gets updated to the penultimate).

2) A bit more complex: when maxSize!=uint.max the associative array values are
linked in a singly linked list. If the requested key is present, its value
moves to the head of the doubly linked list. If it's not present, it's added at
the head of the linked list. If aa.length > maxSize then the last item of the
linked list is removed (a simple LRU implementation). A Python version:
http://code.activestate.com/recipes/498110-memoize-decorator-with-o1-length-limited-lru-cache/

Of course I have written a memoize myself:
http://code.activestate.com/recipes/466320-another-memoize/

Python has function decorators, so there's no need to change the name of
memoized functions nor to change the function contents.

Bye,
bearophile
Jan 04 2011
prev sibling parent reply Eric Poggel <dnewsgroup2 yage3d.net> writes:
On 1/3/2011 11:15 PM, Andrei Alexandrescu wrote:

 I just added a higher-order function memoize to std.functional which I
 think is pretty cool. See the docs here:

 http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize


 I'm also thinking of adding that cutting-edge directory as a place for
 storing documentation for commits that are in flux but not officially
 released yet.


 Andrei


If it's helpful to anyone, Yage has a similar D1 function called Cache:

http://dsource.org/projects/yage/browser/trunk/src/yage/core/cache.d
Jan 04 2011
parent Eric Poggel <dnewsgroup2 yage3d.net> writes:
 If it's helpful to anyone, Yage has a similar D1 function called Cache:

 http://dsource.org/projects/yage/browser/trunk/src/yage/core/cache.d


I almost forgot about licensing.  I release this module under public 
domain or Boost 1.0, whichever is preferred.
Jan 04 2011