hash metamethod?

[Joshua Haberman <joshua@...>]

Languages like Ruby, Python, etc. allow you to define hash functions that apply to your objects.  You define a hash function and a comparison function, and this lets user-defined types be keys in hash tables based on their values.

Does anyone have a Lua PowerPatch that implements anything like this?

I know this question comes up from time to time on this list (like [0] and [1]), and I'm familiar with the objections.  Let me address them:

1. writing fast/correct hash functions in Lua is too hard.  To me this is the easiest objection to answer.  Lua internally already has good hash functions for its built-in types.  And every Lua value you might want to create a hash function for is nothing but a combination of Lua's existing types.  So expose to Lua programs Lua's internal hash functions, along with a function that combines multiple hash values in an intelligent way.  Every Lua-defined hash function would boil down to nothing but calls to Lua's internal hashing functions and the combining function.  Presto: good, high-performing hash functions.

2. hashing mutable structures is too risky, because bad things happen if you mutate them.  it's true that programmers can shoot themselves in the foot by doing the wrong thing, and this is a bit subtle.  but Ruby and Python do it, and I've never come across any horror stories of the one time I was up until 2am tracking down a bug where I mutated my hash keys.  Add some stern warnings in the __hash documentation and be done with it.

3. You can do this by having a canonical instance of each object you want to hash, by using a memotable on construction.  This works to a certain extent, but is annoying for many practical reasons.  For example, your objects might not be immutable for their entire lifetimes, you might just want to take a second to find and remove duplicates among objects that at other times will be modified.  Also, it's non-intuitive in general to have code that looks like it's constructing an object but may actually return an existing object that you're sharing with someone else.  The people you're sharing the object with could mess up and mutate the object even though they're not supposed to.  It's just a strange paradigm in general, and personally I'd much rather live with the potential strangeness of having a __hash metamethod than deal with the strangeness of canonical objects (and I say this as someone who's tried both).

There is one problem with my proposed scheme that bothers me a bit.  The question is: what would a table return as its default __hash and __eql methods?  On one hand I'd want it to treat the table by value, calling __hash and __eql on all of its individual members, so that tables with the same contents hash the same.  On the other hand, I wouldn't want to give up the ability to hash by table identity, because it's sometimes very useful.  I don't have a good answer for this yet.

In any case, like I said I'm mainly wondering if anyone has a PowerPatch, I'm not going to argue that it should go into the main Lua (though I wouldn't mind that either :)

Josh

[0] http://lua-users.org/lists/lua-l/2003-02/msg00525.html
[1] http://lua-users.org/lists/lua-l/2005-06/msg00127.html