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
next sibling 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 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**:
http://stackoverflow.com/questions/245584/d-templates-coolest-hack/4437847#4437847

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**:
 http://stackoverflow.com/questions/245584/d-templates-coolest-hack/4437847#4437847

 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

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
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 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 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 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 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 %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 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**:
 http://stackoverflow.com/questions/245584/d-templates-coolest-hack/4437847#4437847

 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
prev sibling next sibling 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)

That would create several caches, depending on calls with convertible arguments. Andrei
Jan 04 2011
parent 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)

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
prev sibling 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 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
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 Guilherme Vieira <n2.nitrogen gmail.com> writes:
--00163628430a4b57360498ff6933
Content-Type: text/plain; charset=ISO-8859-1

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 --00163628430a4b57360498ff6933 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Jan 4, 2011 at 3:27 AM, Andrei Alexandre= scu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">= SeeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D= "gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding= -left:1ex;"> <div class=3D"im">On 1/3/11 11:01 PM, Guilherme Vieira wrote:<br> </div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-l= eft:1px #ccc solid;padding-left:1ex"><div class=3D"im"> On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky &lt;a a.a&gt; wrote:<br> <br></div><div class=3D"im"> =A0 =A0&quot;Andrei Alexandrescu&quot; &lt;<a href=3D"mailto:SeeWebsiteFor= Email erdani.org" target=3D"_blank">SeeWebsiteForEmail erdani.org</a><br></= div> =A0 =A0&lt;mailto:<a href=3D"mailto:SeeWebsiteForEmail erdani.org" target= =3D"_blank">SeeWebsiteForEmail erdani.org</a>&gt;&gt; wrote in message<div>= <div></div><div class=3D"h5"><br> =A0 =A0news:ifu70u$2dvs$1 digitalmars.com...<br> =A0 =A0 &gt;I just added a higher-order function memoize to std.functional= which I<br> =A0 =A0 &gt;think is pretty cool. See the docs here:<br> =A0 =A0 &gt;<br> =A0 =A0 &gt;<br> =A0 =A0<a href=3D"http://d-programming-language.org/cutting-edge/phobos/st= d_functional.html#memoize" target=3D"_blank">http://d-programming-language.= org/cutting-edge/phobos/std_functional.html#memoize</a><br> =A0 =A0 &gt;<br> =A0 =A0 &gt; I&#39;m also thinking of adding that cutting-edge directory a= s a<br> =A0 =A0place for<br> =A0 =A0 &gt; storing documentation for commits that are in flux but not of= ficially<br> =A0 =A0 &gt; released yet.<br> =A0 =A0 &gt;<br> =A0 =A0 &gt;<br> =A0 =A0 &gt; Andrei<br> <br> =A0 =A0Neat! This is a great example of why D kicks so much ass :)<br> <br> <br></div></div><div class=3D"im"> Uh, yes. It looks like the kind of thing I would do, show to others and<br> hear they say &quot;Meh.. Whatever&quot;. I&#39;m really exponentially deve= loping a<br> liking to the D community, even though I didn&#39;t event get to code<br> anything serious yet.<br> <br> This simply rocks. Keep it up, Andrei!<br> <br> --<br> Atenciosamente / Sincerely,<br> Guilherme (&quot;n2liquid&quot;) Vieira<br> </div></blockquote> <br> Glad you folks like it. There&#39;s a little story behind this. I first rea= d Dominus&#39; book chapter years ago, around the time I&#39;d decided to w= rite TDPL. Back then I was thinking - it would just be so cool to be able t= o define generic memoization in D. I tried my hand at an implementation. Bu= t D had no tuples, no aliasing for functions, no good variadics, and even i= f you could find a way to pack parameters, associative arrays had plenty of= related issues.<br> <br> I&#39;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.<br> <br> Nevertheless, I found two issues: one, ParameterTypeTuple doesn&#39;t work = for overloaded functions, and associative arrays don&#39;t work for ubyte[4= ] keys... still a ways to go.<br><font color=3D"#888888"> <br> <br> Andrei<br> </font></blockquote></div><div><br></div>Is there really need for Parameter= TypeTuple? I figured this works:<div><br><blockquote class=3D"webkit-indent= -blockquote" style=3D"margin: 0 0 0 40px; border: none; padding: 0px;"><div=

px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-= left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex= ; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= template memoize(alias fun, uint maxSize =3D uint.max)</font></blockquote><= /div><div><blockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margi= n-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1p= x; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding= -left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= {</font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"= margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex;= border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left= -style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0auto memoize(Args...)(Args args)</font></blockquote></div><div><b= lockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px= ; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-le= ft-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; = "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0{</font></blockquote></div><div><blockquote class=3D"gmail_quote"= style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-le= ft: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); b= order-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0static typeof(fn(args))[Tuple!(typeof(args))] memo;</font=
</blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"margin-=

-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style:= solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0auto t =3D tuple(args);</font></blockquote></div><div><bl= ockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px;= margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-lef= t-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "=

=A0=A0 =A0 =A0 =A0auto p =3D t in memo;</font></blockquote></div><div><bloc= kquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; m= argin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-= color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0if (p) return *p;</font></blockquote></div><div><blockquo= te class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; margi= n-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-colo= r: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0static if (maxSize !=3D uint.max)</font></blockquote></di= v><div><blockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-r= ight: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; = border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-le= ft: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0{</font></blockquote></div><div><blockquote class=3D"gmai= l_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; m= argin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204,= 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0 =A0 =A0if (memo.length &gt;=3D maxSize) memo =3D null;</= font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"mar= gin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; bo= rder-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-st= yle: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0}</font></blockquote></div><div><blockquote class=3D"gmai= l_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; m= argin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204,= 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0auto r =3D fun(args);</font></blockquote></div><div><bloc= kquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; m= argin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-= color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0//writeln(&quot;Inserting result &quot;, typeof(r).string= of, &quot;(&quot;, r, &quot;) for parameters &quot;, t);</font></blockquote=
</div><div>

px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-= left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex= ; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0memo[t] =3D r;</font></blockquote></div><div><blockquote = class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-b= ottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: = rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0return r;</font></blockquote></div><div><blockquote class= =3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom= : 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(2= 04, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0}</font></blockquote></div><div><blockquote class=3D"gmail_quote"= style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-le= ft: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); b= order-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= }</font></blockquote></div></blockquote><div><div><br>-- <br>Atenciosamente= / Sincerely,<br>Guilherme (&quot;n2liquid&quot;) Vieira<br> </div></div></div> --00163628430a4b57360498ff6933--
Jan 03 2011
prev sibling next sibling parent Guilherme Vieira <n2.nitrogen gmail.com> writes:
--001485e9a89ef755d80498ffdc0a
Content-Type: text/plain; charset=ISO-8859-1

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 --001485e9a89ef755d80498ffdc0a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Jan 4, 2011 at 4:30 AM, Guilherme Vieira= <span dir=3D"ltr">&lt;<a href=3D"mailto:n2.nitrogen gmail.com">n2.nitrogen= gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style= =3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div><div></div><div class=3D"h5"><div class=3D"gmail_quote">On Tue, Jan 4,= 2011 at 3:27 AM, Andrei Alexandrescu <span dir=3D"ltr">&lt;<a href=3D"mail= to:SeeWebsiteForEmail erdani.org" target=3D"_blank">SeeWebsiteForEmail erda= ni.org</a>&gt;</span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> <div>On 1/3/11 11:01 PM, Guilherme Vieira wrote:<br> </div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-l= eft:1px #ccc solid;padding-left:1ex"><div> On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky &lt;a a.a&gt; wrote:<br> <br></div><div> =A0 =A0&quot;Andrei Alexandrescu&quot; &lt;<a href=3D"mailto:SeeWebsiteFor= Email erdani.org" target=3D"_blank">SeeWebsiteForEmail erdani.org</a><br></= div> =A0 =A0&lt;mailto:<a href=3D"mailto:SeeWebsiteForEmail erdani.org" target= =3D"_blank">SeeWebsiteForEmail erdani.org</a>&gt;&gt; wrote in message<div>= <div></div><div><br> =A0 =A0news:ifu70u$2dvs$1 digitalmars.com...<br> =A0 =A0 &gt;I just added a higher-order function memoize to std.functional= which I<br> =A0 =A0 &gt;think is pretty cool. See the docs here:<br> =A0 =A0 &gt;<br> =A0 =A0 &gt;<br> =A0 =A0<a href=3D"http://d-programming-language.org/cutting-edge/phobos/st= d_functional.html#memoize" target=3D"_blank">http://d-programming-language.= org/cutting-edge/phobos/std_functional.html#memoize</a><br> =A0 =A0 &gt;<br> =A0 =A0 &gt; I&#39;m also thinking of adding that cutting-edge directory a= s a<br> =A0 =A0place for<br> =A0 =A0 &gt; storing documentation for commits that are in flux but not of= ficially<br> =A0 =A0 &gt; released yet.<br> =A0 =A0 &gt;<br> =A0 =A0 &gt;<br> =A0 =A0 &gt; Andrei<br> <br> =A0 =A0Neat! This is a great example of why D kicks so much ass :)<br> <br> <br></div></div><div> Uh, yes. It looks like the kind of thing I would do, show to others and<br> hear they say &quot;Meh.. Whatever&quot;. I&#39;m really exponentially deve= loping a<br> liking to the D community, even though I didn&#39;t event get to code<br> anything serious yet.<br> <br> This simply rocks. Keep it up, Andrei!<br> <br> --<br> Atenciosamente / Sincerely,<br> Guilherme (&quot;n2liquid&quot;) Vieira<br> </div></blockquote> <br> Glad you folks like it. There&#39;s a little story behind this. I first rea= d Dominus&#39; book chapter years ago, around the time I&#39;d decided to w= rite TDPL. Back then I was thinking - it would just be so cool to be able t= o define generic memoization in D. I tried my hand at an implementation. Bu= t D had no tuples, no aliasing for functions, no good variadics, and even i= f you could find a way to pack parameters, associative arrays had plenty of= related issues.<br> <br> I&#39;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.<br> <br> Nevertheless, I found two issues: one, ParameterTypeTuple doesn&#39;t work = for overloaded functions, and associative arrays don&#39;t work for ubyte[4= ] keys... still a ways to go.<br><font color=3D"#888888"> <br> <br> Andrei<br> </font></blockquote></div><div><br></div></div></div>Is there really need f= or ParameterTypeTuple? I figured this works:<div><br><blockquote style=3D"m= argin:0 0 0 40px;border:none;padding:0px"><div> <blockquote class=3D"gmail_quote" style=3D"margin-top:0px;margin-right:0px;= margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color= :rgb(204, 204, 204);border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">template memoize(alias fun,= uint maxSize =3D uint.max)</font></blockquote></div><div><blockquote class= =3D"gmail_quote" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px= ;margin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 20= 4);border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">{</font></blockquote></div>= <div><blockquote class=3D"gmail_quote" style=3D"margin-top:0px;margin-right= :0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-= color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0auto memoize(Args= ...)(Args args)</font></blockquote></div><div><blockquote class=3D"gmail_qu= ote" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left= :0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-le= ft-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0{</font></blockqu= ote></div><div><blockquote class=3D"gmail_quote" style=3D"margin-top:0px;ma= rgin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;bo= rder-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex= "> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0static ty= peof(fn(args))[Tuple!(typeof(args))] memo;</font></blockquote></div><div><b= lockquote class=3D"gmail_quote" style=3D"margin-top:0px;margin-right:0px;ma= rgin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color:r= gb(204, 204, 204);border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0auto t = =3D tuple(args);</font></blockquote></div><div><blockquote class=3D"gmail_q= uote" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;margin-lef= t:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-l= eft-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0auto p = =3D t in memo;</font></blockquote></div><div><blockquote class=3D"gmail_quo= te" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:= 0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-lef= t-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0if (p) re= turn *p;</font></blockquote></div><div><blockquote class=3D"gmail_quote" st= yle=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;= border-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-styl= e:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0static if= (maxSize !=3D uint.max)</font></blockquote></div><div><blockquote class=3D= "gmail_quote" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;ma= rgin-left:0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);= border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0{</font><= /blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"margin-to= p:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-widt= h:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-= left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0 =A0 =A0i= f (memo.length &gt;=3D maxSize) memo =3D null;</font></blockquote></div><di= v><blockquote class=3D"gmail_quote" style=3D"margin-top:0px;margin-right:0p= x;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-col= or:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0}</font><= /blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"margin-to= p:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-widt= h:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;padding-= left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0auto r = =3D fun(args);</font></blockquote></div><div><blockquote class=3D"gmail_quo= te" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:= 0.8ex;border-left-width:1px;border-left-color:rgb(204, 204, 204);border-lef= t-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0//writeln= (&quot;Inserting result &quot;, typeof(r).stringof, &quot;(&quot;, r, &quot= ;) for parameters &quot;, t);</font></blockquote></div><div> <blockquote class=3D"gmail_quote" style=3D"margin-top:0px;margin-right:0px;= margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;border-left-color= :rgb(204, 204, 204);border-left-style:solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0memo[t] = =3D r;</font></blockquote></div><div><blockquote class=3D"gmail_quote" styl= e=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;bo= rder-left-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:= solid;padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0 =A0 =A0return r;= </font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"m= argin-top:0px;margin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-l= eft-width:1px;border-left-color:rgb(204, 204, 204);border-left-style:solid;= padding-left:1ex"> <font face=3D"&#39;courier new&#39;, monospace">=A0=A0 =A0}</font></blockqu= ote></div><div><blockquote class=3D"gmail_quote" style=3D"margin-top:0px;ma= rgin-right:0px;margin-bottom:0px;margin-left:0.8ex;border-left-width:1px;bo= rder-left-color:rgb(204, 204, 204);border-left-style:solid;padding-left:1ex= "> <font face=3D"&#39;courier new&#39;, monospace">}</font></blockquote></div>= </blockquote><div><div><br><font color=3D"#888888">-- <br></font><div class= =3D"im">Atenciosamente / Sincerely,<br>Guilherme (&quot;n2liquid&quot;) Vie= ira<br> </div></div></div></div> </blockquote></div><br>Dirty fix for the ubyte[4] problem:<div><br></div><b= lockquote class=3D"webkit-indent-blockquote" style=3D"margin: 0 0 0 40px; b= order: none; padding: 0px;"><div><blockquote class=3D"gmail_quote" style=3D= "margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex= ; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-lef= t-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= struct wrapper(T)</font></blockquote></div><div><blockquote class=3D"gmail_= quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; mar= gin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 2= 04); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= {</font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"= margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex;= border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left= -style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0this(T value) { this.value =3D value; }</font></blockquote></div>= <div><blockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-rig= ht: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; bo= rder-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left= : 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0T value;</font></blockquote></div><div><blockquote class=3D"gmail= _quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; ma= rgin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, = 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= }</font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"= margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex;= border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left= -style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= <br></font></blockquote></div><div><blockquote class=3D"gmail_quote" style= =3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.= 8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-= left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= template memoize(alias fun, uint maxSize =3D uint.max)</font></blockquote><= /div><div><blockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margi= n-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1p= x; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding= -left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= {</font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"= margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex;= border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left= -style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0auto memoize(Args...)(Args args)</font></blockquote></div><div><b= lockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px= ; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-le= ft-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; = "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0{</font></blockquote></div><div><blockquote class=3D"gmail_quote"= style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-le= ft: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); b= order-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0static wrapper!(typeof(fn(args)))[Tuple!(typeof(args))] m= emo;</font></blockquote></div><div><blockquote class=3D"gmail_quote" style= =3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.= 8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-= left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0auto t =3D tuple(args);</font></blockquote></div><div><bl= ockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px;= margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-lef= t-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "=

=A0=A0 =A0 =A0 =A0auto p =3D t in memo;</font></blockquote></div><div><bloc= kquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; m= argin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-= color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0if (p) return p.value;</font></blockquote></div><div><blo= ckquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; = margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left= -color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0static if (maxSize !=3D uint.max)</font></blockquote></di= v><div><blockquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-r= ight: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; = border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-le= ft: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0{</font></blockquote></div><div><blockquote class=3D"gmai= l_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; m= argin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204,= 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0 =A0 =A0if (memo.length &gt;=3D maxSize) memo =3D null;</= font></blockquote></div><div><blockquote class=3D"gmail_quote" style=3D"mar= gin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; bo= rder-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-st= yle: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0}</font></blockquote></div><div><blockquote class=3D"gmai= l_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; m= argin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204,= 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0auto r =3D fun(args);</font></blockquote></div><div><bloc= kquote class=3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; m= argin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-= color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0//writeln(&quot;Inserting result &quot;, typeof(r).string= of, &quot;(&quot;, r, &quot;) for parameters &quot;, t);</font></blockquote=
</div><div>

px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-= left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex= ; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0memo[t] =3D wrapper!(typeof(fn(args)))(r);</font></blockq= uote></div><div><blockquote class=3D"gmail_quote" style=3D"margin-top: 0px;= margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-wid= th: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; p= adding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0 =A0 =A0return r;</font></blockquote></div><div><blockquote class= =3D"gmail_quote" style=3D"margin-top: 0px; margin-right: 0px; margin-bottom= : 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(2= 04, 204, 204); border-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= =A0=A0 =A0}</font></blockquote></div><div><blockquote class=3D"gmail_quote"= style=3D"margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-le= ft: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); b= order-left-style: solid; padding-left: 1ex; "> <font class=3D"Apple-style-span" face=3D"&#39;courier new&#39;, monospace">= }</font></blockquote></div></blockquote><div><div><div><br></div><div>But I= think I get why ParameterTypeTuple is important. My version of the templat= e give ugly error messages when I call a memoized function with the wrong p= arameter types. ParameterTypeTuple would make them go away, right?</div> <div><br>-- <br>Atenciosamente / Sincerely,<br>Guilherme (&quot;n2liquid&qu= ot;) Vieira<br> </div></div></div> --001485e9a89ef755d80498ffdc0a--
Jan 03 2011
prev sibling next sibling parent 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]=

 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
prev sibling next sibling parent "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)

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
prev sibling next sibling 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 "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**:
 http://stackoverflow.com/questions/245584/d-templates-coolest-hack/4437847#4437847

 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 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 "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
prev sibling next sibling parent "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
prev sibling parent "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
prev sibling next sibling parent Guilherme Vieira <n2.nitrogen gmail.com> writes:
--001636416495aae3d00498fe28d1
Content-Type: text/plain; charset=ISO-8859-1

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:

 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 --001636416495aae3d00498fe28d1 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky = <span dir=3D"ltr">&lt;a a.a&gt;</span> wrote:<br><blockquote class=3D"gmail= _quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:= 1ex;"> &quot;Andrei Alexandrescu&quot; &lt;<a href=3D"mailto:SeeWebsiteForEmail er= dani.org">SeeWebsiteForEmail erdani.org</a>&gt; wrote in message<br> news:ifu70u$2dvs$1 digitalmars.com...<br> <div><div></div><div class=3D"h5">&gt;I just added a higher-order function = memoize to std.functional which I<br> &gt;think is pretty cool. See the docs here:<br> &gt;<br> &gt; <a href=3D"http://d-programming-language.org/cutting-edge/phobos/std_f= unctional.html#memoize" target=3D"_blank">http://d-programming-language.org= /cutting-edge/phobos/std_functional.html#memoize</a><br> &gt;<br> &gt; I&#39;m also thinking of adding that cutting-edge directory as a place= for<br> &gt; storing documentation for commits that are in flux but not officially<= br> &gt; released yet.<br> &gt;<br> &gt;<br> &gt; Andrei<br> <br> </div></div>Neat! This is a great example of why D kicks so much ass :)<br> </blockquote></div><div><br></div>Uh, yes. It looks like the kind of thing = I would do, show to others and hear they say &quot;Meh.. Whatever&quot;. I&= #39;m really exponentially developing a liking to the D community, even tho= ugh I didn&#39;t event get to code anything serious yet.<div> <br></div><div>This simply rocks.=A0Keep it up, Andrei!<br><div><br>-- <br>= Atenciosamente / Sincerely,<br>Guilherme (&quot;n2liquid&quot;) Vieira<br> </div></div> --001636416495aae3d00498fe28d1--
Jan 03 2011
prev sibling 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 Andrew Wiley <debio264 gmail.com> writes:
--20cf3054a203bdc6a30498ff0cec
Content-Type: text/plain; charset=ISO-8859-1

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? --20cf3054a203bdc6a30498ff0cec Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Jan 3, 2011 at 10:15 PM, Andrei = Alexandrescu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erd= ani.org">SeeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote= class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc soli= d;padding-left:1ex;"> I just added a higher-order function memoize to std.functional which I thin= k is pretty cool. See the docs here:<br> <br> <a href=3D"http://d-programming-language.org/cutting-edge/phobos/std_functi= onal.html#memoize" target=3D"_blank">http://d-programming-language.org/cutt= ing-edge/phobos/std_functional.html#memoize</a><br> <br> I&#39;m also thinking of adding that cutting-edge directory as a place for = storing documentation for commits that are in flux but not officially relea= sed yet.</blockquote><div><br></div><div>Pretty sweet, but if I&#39;m under= standing this correctly, the memoized version of a pure function isn&#39;t = pure, is it? Is there any way to get that to happen?=A0</div> </div><br> --20cf3054a203bdc6a30498ff0cec--
Jan 03 2011
prev sibling next sibling parent Guilherme Vieira <n2.nitrogen gmail.com> writes:
--0016361e815c89aabc0498ff3a16
Content-Type: text/plain; charset=ISO-8859-1

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?

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 --0016361e815c89aabc0498ff3a16 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Jan 4, 2011 at 4:05 AM, Andrew Wiley <sp= an dir=3D"ltr">&lt;<a href=3D"mailto:debio264 gmail.com">debio264 gmail.com= </a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin= :0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <br><br><div class=3D"gmail_quote"><div><div></div><div class=3D"h5">On Mon= , Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu <span dir=3D"ltr">&lt;<a hre= f=3D"mailto:SeeWebsiteForEmail erdani.org" target=3D"_blank">SeeWebsiteForE= mail erdani.org</a>&gt;</span> wrote:<br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> I just added a higher-order function memoize to std.functional which I thin= k is pretty cool. See the docs here:<br> <br> <a href=3D"http://d-programming-language.org/cutting-edge/phobos/std_functi= onal.html#memoize" target=3D"_blank">http://d-programming-language.org/cutt= ing-edge/phobos/std_functional.html#memoize</a><br> <br> I&#39;m also thinking of adding that cutting-edge directory as a place for = storing documentation for commits that are in flux but not officially relea= sed yet.</blockquote><div><br></div></div></div><div>Pretty sweet, but if I= &#39;m understanding this correctly, the memoized version of a pure functio= n isn&#39;t pure, is it? Is there any way to get that to happen?=A0</div> </div><br> </blockquote></div><div><br></div><div>memoize uses a static variable. Are = static variables considered &quot;global&quot; as far as pure functions are= concerned? If not, then I see no reason for it not to be pure, or am I mis= sing something?</div> <div><br></div>Additionally, I don&#39;t understand this:<div><br><blockquo= te class=3D"webkit-indent-blockquote" style=3D"margin: 0 0 0 40px; border: = none; padding: 0px;"><blockquote class=3D"gmail_quote" style=3D"margin-top:= 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-lef= t-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: sol= id; padding-left: 1ex; "> &quot;Technically the memoized function should be pure because=A0<span clas= s=3D"d_inlinecode"><a name=3D"memoize"></a>memoize</span>=A0assumes it will= always return the same result for a given tuple of arguments. However,=A0<= span class=3D"d_inlinecode"><a name=3D"memoize"></a>memoize</span>=A0does n= ot enforce that because sometimes it is useful to=A0<a name=3D"memoize"></a=
memoize=A0an impure function, too.&quot;</blockquote>

ial, Verdana, sans-serif; line-height: 25px; "><br></span></div><div>Wouldn= &#39;t memoizing an impure function be a.. bug? It would return the same ca= ched value when in fact it should have returned something else based on ext= ernal factors. When can that be desirable?<br clear=3D"all"> <br>-- <br>Atenciosamente / Sincerely,<br>Guilherme (&quot;n2liquid&quot;) = Vieira<br> </div></div> --0016361e815c89aabc0498ff3a16--
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:
--001636284880d0c5a70498ffcff9
Content-Type: text/plain; charset=ISO-8859-1

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:



 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"

 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


 memoize an impure function, too."

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

 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 --001636284880d0c5a70498ffcff9 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Jan 4, 2011 at 4:48 AM, Jonathan M Davis= <span dir=3D"ltr">&lt;<a href=3D"mailto:jmdavisProg gmx.com">jmdavisProg g= mx.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"= margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div class=3D"im">On Monday 03 January 2011 22:17:52 Guilherme Vieira wrote= :<br> &gt; On Tue, Jan 4, 2011 at 4:05 AM, Andrew Wiley &lt;<a href=3D"mailto:deb= io264 gmail.com">debio264 gmail.com</a>&gt; wrote:<br> &gt; &gt; On Mon, Jan 3, 2011 at 10:15 PM, Andrei Alexandrescu &lt;<br> &gt; &gt;<br> &gt; &gt; <a href=3D"mailto:SeeWebsiteForEmail erdani.org">SeeWebsiteForEma= il erdani.org</a>&gt; wrote:<br> &gt; &gt;&gt; I just added a higher-order function memoize to std.functiona= l which I<br> &gt; &gt;&gt; think is pretty cool. See the docs here:<br> &gt; &gt;&gt;<br> &gt; &gt;&gt;<br> &gt; &gt;&gt; <a href=3D"http://d-programming-language.org/cutting-edge/pho= bos/std_functional.htm" target=3D"_blank">http://d-programming-language.org= /cutting-edge/phobos/std_functional.htm</a><br> &gt; &gt;&gt; l#memoize<br> &gt; &gt;&gt;<br> &gt; &gt;&gt; I&#39;m also thinking of adding that cutting-edge directory a= s a place for<br> &gt; &gt;&gt; storing documentation for commits that are in flux but not of= ficially<br> &gt; &gt;&gt; released yet.<br> &gt; &gt;<br> &gt; &gt; Pretty sweet, but if I&#39;m understanding this correctly, the me= moized<br> &gt; &gt; version of a pure function isn&#39;t pure, is it? Is there any wa= y to get<br> &gt; &gt; that to happen?<br> &gt;<br> &gt; memoize uses a static variable. Are static variables considered &quot;= global&quot; as<br> &gt; far as pure functions are concerned? If not, then I see no reason for = it<br> &gt; not to be pure, or am I missing something?<br> <br> </div>pure functions cannot access mutable globals or static variables. If = they could,<br> they could end up returning a different result with the same parameters bec= ause<br> the global or static variable changed.<br> <div class=3D"im"><br> &gt; Additionally, I don&#39;t understand this:<br> &gt;<br> &gt; &quot;Technically the memoized function should be pure because memoize= assumes<br> &gt; it<br> &gt;<br> &gt; &gt; will always return the same result for a given tuple of arguments= .<br> &gt; &gt; However, memoize does not enforce that because sometimes it is us= eful to<br> &gt; &gt; memoize an impure function, too.&quot;<br> &gt;<br> &gt; Wouldn&#39;t memoizing an impure function be a.. bug? It would return = the same<br> &gt; cached value when in fact it should have returned something else based= on<br> &gt; external factors. When can that be desirable?<br> <br> </div>It&#39;s quite easy to have a function which you cannot actually make= pure but which<br> you know to be logically pure. For instance, if a function called a C funct= ion,<br> it can&#39;t be pure unless you play some games with function pointers and = casting<br> and the like. So, really, any function which calls a C function can&#39;t b= e pure.<br> However, it&#39;s pretty easy to have a C function which is logically pure.= So, your<br> D function is then logically pure, but it&#39;s not actually pure, so pure = functions<br> can&#39;t call it. But it would work just fine with memoize. Sure, it&#39;s= definitely<br> less safe to use impure functions with memoize, and it could cause bugs, bu= t<br> that doesn&#39;t mean that it shouldn&#39;t necessarily be disallowed. It j= ust means<br> that if the programmer wants to use memoize, they&#39;re going to have to b= e aware<br> that it could cause bugs if the function in question should actually be<br> returning a different value on future callls.<br> <font color=3D"#888888"><br> - Jonathan M Davis<br> </font></blockquote></div><br>Ah, I was under the impression that trusted = was used to force purity. Shame.. Sorry I mixed things up.<div><br></div><d= iv>In any case, aren&#39;t those rules a bit too rigid? No matter how you l= ook at memoize, it should generate pure functions (since it exhibits pure n= ature, are logically pure or whatever you call it). Would it be tough on th= e compiler for it to actually find if a function is pure or not by a more d= etailed analysis of its behavior?<br clear=3D"all"> <br>-- <br>Atenciosamente / Sincerely,<br>Guilherme (&quot;n2liquid&quot;) = Vieira<br> </div> --001636284880d0c5a70498ffcff9--
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:
--001636284618e46af30499007367
Content-Type: text/plain; charset=ISO-8859-1

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

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

 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 --001636284618e46af30499007367 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Tue, Jan 4, 2011 at 5:28 AM, Jonathan M Davis= <span dir=3D"ltr">&lt;<a href=3D"mailto:jmdavisProg gmx.com">jmdavisProg g= mx.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"= margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div class=3D"im">On Monday 03 January 2011 22:59:37 Guilherme Vieira wrote= :<br> &gt; Ah, I was under the impression that trusted was used to force purity.= <br> &gt; Shame.. Sorry I mixed things up.<br> &gt;<br> &gt; In any case, aren&#39;t those rules a bit too rigid? No matter how you= look at<br> &gt; memoize, it should generate pure functions (since it exhibits pure nat= ure,<br> &gt; are logically pure or whatever you call it). Would it be tough on the<= br> &gt; compiler for it to actually find if a function is pure or not by a mor= e<br> &gt; detailed analysis of its behavior?<br> <br> </div> safe, trusted, and system have nothing to do with purity. If a fun= ction is<br> marked as pure, then it&#39;s pure. If it&#39;s not, then it&#39;s not. End= of story. Now,<br> the concept of &quot;weakly&quot; pure functions was recently added, but al= l pure<br> functions are still marked with pure. Strongly pure functions are pure func= tions<br> where all of the parameters are immutable or implicitly convertible to immu= table<br> (so, immutable variables and value types). Weakly pure functions are pure<b= r> functions whose parameters are not all immutable or implicitly convertible = to<br> immutable. Unlike strongly pure functions, they can alter their arguments.<= br> However, just like strongly pure functions, they cannot access globals or<b= r> statics. Strongly pure functions can be optimized such that only one call t= o<br> them is made in an expression because their return value will always be the= <br> same, and they cannot alter their parameters. Weakly pure functions cannot = be<br> optimized in that manner, but because they don&#39;t alter the global state= , they<br> can be safely called from strongly pure functions without violating the str= ongly<br> pure function&#39;s purity.<br> <br> Pure is not logically pure for essentially the same reasons that const is n= ot<br> logically const. Making it logical instead of guaranteed eliminates the<br> guarantees, and the compiler can no longer rely on those guarantees, making= them<br> _far_ less valuable.<br> <br> It is true that a memoized function must be logically pure, or you&#39;re g= oing to<br> get errors. However, if you were to force such functions to be pure, it wou= ld be<br> highly limiting. And since memoize _can&#39;t_ be pure, it would make recur= sion with<br> memoize impossible. True, allowing for memoized functions to be impure make= s it<br> so that the programmer must be more careful, but it&#39;s still quite usefu= l - in<br> fact more useful - that way. And since you _can&#39;t_ have memoize be pure= anyway,<br> it&#39;s not like you&#39;re losing any guarantees from the compiler like i= f you tried<br> to make pure logically pure or const logically const.<br> <font color=3D"#888888"><br> - Jonathan M Davis<br> </font></blockquote></div><br>Don&#39;t take me too seriously since I&#39;m= learning those things on-the-fly here (I&#39;m greedy). The const FAQ (<a = href=3D"http://www.digitalmars.com/d/2.0/const-faq.html#logical-const">http= ://www.digitalmars.com/d/2.0/const-faq.html#logical-const</a>) says D doesn= &#39;t support logical const because it would break transitivity, and they = deemed transitivity to be more important (Walter even thinks it&#39;s bad, = doesn&#39;t he?), so I understand why const in D is not logical const.<div> <br></div><div>But in the case of memoize, aren&#39;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.</div><div><br></div><div>Or by analysis of beh= avior. Obviously, that wouldn&#39;t work for external C functions, but at l= east memoize would be okay. Also, I&#39;m to guess it would be extremely ha= rd to write a compiler that does this, but I&#39;d just like to confirm.</d= iv> <div><br></div><div> Walter: would it be hard/impossible for the compiler t= o look at memoize and tell it exhibits pure behavior and is, thus, pure?<br= clear=3D"all"><br>-- <br>Atenciosamente / Sincerely,<br>Guilherme (&quot;n= 2liquid&quot;) Vieira<br> </div> --001636284618e46af30499007367--
Jan 03 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 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 next sibling parent "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
prev sibling next 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
prev sibling 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 next 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 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
prev sibling 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=

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

 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