4 ms·
I'm curious how D implements memoizing an arbitrary function. To memoize something, you need to be able to check if it's being called with the same arguments. B
by thinkpad20 12y ago
I'm curious how D implements memoizing an arbitrary function. To memoize something, you need to be able to check if it's being called with the same arguments. But to do that, you need a definition of "same" (i.e., an equivalence relation). For example, if the argument is a dictionary, is it considered the same argument only if the pointer is the same, or if the keys and values are the same, assuming a recursive definition of "same"? Also, you need a way to store computed values, using the arguments as keys, which for efficiency would require either an ordering (for a tree) or hashing (for a hash table) on the arguments. Multiple arguments would further complicate things. How does this get automated? And for some things, memoization wouldn't make sense (for example, with function arguments in higher-order functions). Sensible defaults would take care of most of these things, but it makes me wonder how they chose to address these things. And is the memo recreated each time the (outer) function is called, or is it stored for the duration of the program? Also, how does the type system play with this? What's the type of `memoize!`?
- jnetterf 12y agoThe standard library (Phobos) is open source. You can find the implementation of memoize at https://github.com/D-Programming-Language/phobos/blob/6cd2e43eab2b0e4c5c6cc7bbfd30cbd5e132735d/std/functional.d#L680 https://github.com/D-Programming-Language/phobos/blob/6cd2e4... memoize is a template (http://dlang.org/template.html http://dlang.org/template.html). In this case, a template is used to create a "version" of "memoize" with the right parameters and return value (i.e., `fn` and `memoize!fn` are the same type). Each of these "versions" has a hash table from argument tuples to results. I believe the hash is computed by calling a toHash function for each item in the tuple. Tuples and type tuples (http://dlang.org/tuple.html http://dlang.org/tuple.html) in D are really quite powerful.
- tel 12y agoHow do you know what types are hashable?
- andralex 12y agoMust support comparison for equality and the hash function. Default built-ins provided appropriately.
- tel 12y agoOh, that's tragic.
- andralex 12y agos/tr/m/
- tel 12y agoVery magical—but I'm not convinced all types have meaningful equality or hashes. It's convenient to have, but thorny whenever you, say, have anonymous functions lying around.
- sanderjd 12y agoWhy is it tragic?
- dllthomas 12y agoMy read of this is that tel (mis)interpreted andralex as saying that all types must support equality and hashing, not that types must support equality and hashing to be hashable. It would be tragic because there can be types with no meaningful way to produce a hash or test for equality. If that's not the case, then I don't understand either.
- v0i0-0 12y agoHave a look at the sourcecode [1]. It is just implemented with an associative array (implemented as hash table) from argument tuples to the return type. This means that keys have to be atomic or provide their to_hash and equality check themselves. Check out the D template system, it is quite impressive what you can express with it. 1: https://github.com/D-Programming-Language/phobos/blob/master/std/functional.d#L756 https://github.com/D-Programming-Language/phobos/blob/master...
- andralex 12y ago1. Sheer comparison for equality is used. (It is user definable.) For e.g. built-in hashes, contents must compare equal. 2. The store is a hashtable. 3. Multiple arguments are grouped in a tuple - no major complication. 4. Where memoization doesn't make sense you'll get a compile-time error because e.g. comparison for equality is't defined. At least most of the time :o). 5. The memory is thread-local. 6. memoize takes the name of the memoized argument and creates a distinct type for each memoized function. TL;DR: business as usual
- delluminatus 12y ago> 1. Sheer comparison for equality is used. (It is user definable.) For e.g. built-in hashes, contents must compare equal. Wow, so if you compare aHash == anotherHash, it doesn't just compare the references, it actually examines both hashes for content equivalence? That's fairly unconventional, but probably convenient sometimes.
- andralex 12y agoAffirmative. Use "aHash is anotherHash" to compare references.