News for hackers. Stuff that matters.
Re:Hidden treasure in the D standard library by thinkpad20 on Thursday August 28, 2014 @03:41PM (#8239260)
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!`?
Re:Hidden treasure in the D standard library by andralex on Thursday August 28, 2014 @04:27PM (#8239513)
1. 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

Re:Hidden treasure in the D standard library by delluminatus on Thursday August 28, 2014 @05:37PM (#8239852)
> 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.

Re:Hidden treasure in the D standard library by andralex on Thursday August 28, 2014 @05:39PM (#8239861)
Affirmative. Use "aHash is anotherHash" to compare references.
Re:Hidden treasure in the D standard library by jnetterf on Thursday August 28, 2014 @04:12PM (#8239432)
The standard library (Phobos) is open source. You can find the implementation of memoize at https://github.com/D-Programming-Language/phobos/blob/6cd2e4...

memoize is a template (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) in D are really quite powerful.

Re:Hidden treasure in the D standard library by tel on Thursday August 28, 2014 @04:17PM (#8239465)
How do you know what types are hashable?
Re:Hidden treasure in the D standard library by andralex on Thursday August 28, 2014 @04:43PM (#8239594)
Must support comparison for equality and the hash function. Default built-ins provided appropriately.
Re:Hidden treasure in the D standard library by repsilat on Friday August 29, 2014 @04:19AM (#8241596)
In theory you could use a tree for unhashable things with a total order, and you could use a list for just about anything else (though you might want to emit a warning...).

I assume D has enough magic to pattern match on the traits of the types in the argument list?

Re:Hidden treasure in the D standard library by dllthomas on Friday August 29, 2014 @12:37PM (#8243253)
Presuming you have equality.
Re:Hidden treasure in the D standard library by tel on Thursday August 28, 2014 @04:54PM (#8239645)
Oh, that's tragic.
Re:Hidden treasure in the D standard library by andralex on Thursday August 28, 2014 @05:41PM (#8239869)
s/tr/m/
Re:Hidden treasure in the D standard library by tel on Thursday August 28, 2014 @05:54PM (#8239935)
Very 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.
Re:Hidden treasure in the D standard library by andralex on Thursday August 28, 2014 @06:12PM (#8240018)
Those won't compile.
Re:Hidden treasure in the D standard library by tel on Thursday August 28, 2014 @07:52PM (#8240413)
Oh, dlthomas caught what went wrong! I misunderstood, apologies. If they dont compile then that's great.
Re:Hidden treasure in the D standard library by sanderjd on Thursday August 28, 2014 @07:20PM (#8240273)
Why is it tragic?
Re:Hidden treasure in the D standard library by dllthomas on Thursday August 28, 2014 @07:28PM (#8240305)
My 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.

Re:Hidden treasure in the D standard library by v0i0-0 on Thursday August 28, 2014 @04:19PM (#8239479)
Have 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...