<div class="gmail_quote">On Tue, Jan 4, 2011 at 4:30 AM, Guilherme Vieira <span dir="ltr"><<a href="mailto:n2.nitrogen@gmail.com">n2.nitrogen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="h5"><div class="gmail_quote">On Tue, Jan 4, 2011 at 3:27 AM, Andrei Alexandrescu <span dir="ltr"><<a href="mailto:SeeWebsiteForEmail@erdani.org" target="_blank">SeeWebsiteForEmail@erdani.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>On 1/3/11 11:01 PM, Guilherme Vieira wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>
On Tue, Jan 4, 2011 at 2:50 AM, Nick Sabalausky <a@a.a> wrote:<br>
<br></div><div>
"Andrei Alexandrescu" <<a href="mailto:SeeWebsiteForEmail@erdani.org" target="_blank">SeeWebsiteForEmail@erdani.org</a><br></div>
<mailto:<a href="mailto:SeeWebsiteForEmail@erdani.org" target="_blank">SeeWebsiteForEmail@erdani.org</a>>> wrote in message<div><div></div><div><br>
news:ifu70u$2dvs$1@digitalmars.com...<br>
>I just added a higher-order function memoize to std.functional which I<br>
>think is pretty cool. See the docs here:<br>
><br>
><br>
<a href="http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize" target="_blank">http://d-programming-language.org/cutting-edge/phobos/std_functional.html#memoize</a><br>
><br>
> I'm also thinking of adding that cutting-edge directory as a<br>
place for<br>
> storing documentation for commits that are in flux but not officially<br>
> released yet.<br>
><br>
><br>
> Andrei<br>
<br>
Neat! 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 "Meh.. Whatever". I'm really exponentially developing a<br>
liking to the D community, even though I didn'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 ("n2liquid") Vieira<br>
</div></blockquote>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br><font color="#888888">
<br>
<br>
Andrei<br>
</font></blockquote></div><div><br></div></div></div>Is there really need for ParameterTypeTuple? I figured this works:<div><br><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div>
<blockquote class="gmail_quote" style="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="'courier new', monospace">template memoize(alias fun, uint maxSize = uint.max)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace">{</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> auto memoize(Args...)(Args args)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> {</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> static typeof(fn(args))[Tuple!(typeof(args))] memo;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> auto t = tuple(args);</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> auto p = t in memo;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> if (p) return *p;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> static if (maxSize != uint.max)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> {</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> if (memo.length >= maxSize) memo = null;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> }</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> auto r = fun(args);</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for parameters ", t);</font></blockquote></div><div>
<blockquote class="gmail_quote" style="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="'courier new', monospace"> memo[t] = r;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> return r;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace"> }</font></blockquote></div><div><blockquote class="gmail_quote" style="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="'courier new', monospace">}</font></blockquote></div></blockquote><div><div><br><font color="#888888">-- <br></font><div class="im">Atenciosamente / Sincerely,<br>Guilherme ("n2liquid") Vieira<br>
</div></div></div></div>
</blockquote></div><br>Dirty fix for the ubyte[4] problem:<div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace">struct wrapper(T)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace">{</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> this(T value) { this.value = value; }</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> T value;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace">}</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"><br></font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace">template memoize(alias fun, uint maxSize = uint.max)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace">{</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> auto memoize(Args...)(Args args)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> {</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> static wrapper!(typeof(fn(args)))[Tuple!(typeof(args))] memo;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> auto t = tuple(args);</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> auto p = t in memo;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> if (p) return p.value;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> static if (maxSize != uint.max)</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> {</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> if (memo.length >= maxSize) memo = null;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> }</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> auto r = fun(args);</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> //writeln("Inserting result ", typeof(r).stringof, "(", r, ") for parameters ", t);</font></blockquote></div><div>
<blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> memo[t] = wrapper!(typeof(fn(args)))(r);</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> return r;</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace"> }</font></blockquote></div><div><blockquote class="gmail_quote" style="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="Apple-style-span" face="'courier new', monospace">}</font></blockquote></div></blockquote><div><div><div><br></div><div>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?</div>
<div><br>-- <br>Atenciosamente / Sincerely,<br>Guilherme ("n2liquid") Vieira<br>
</div></div></div>