[rust-dev] Addressing "the hashtable problem" with type classes

Lindsey Kuper lindsey at rockstargirl.org
Fri Jun 29 12:54:46 PDT 2012


On Thu, Dec 1, 2011 at 8:25 PM, Niko Matsakis <niko at alum.mit.edu> wrote:
> There is a danger with typeclasses only on functions because they
> permit a lack of coherence.  This danger is particularly acute with
> collections, where the definition of a particular interface---such as
> hashable or ord---may be used in structuring the data structure. This
> renders the data structure corrupt when used with a different
> implementation.
>
> To see the problem, consider a hashtable defined something like this:
>
>    mod ht {
>        iface hash {
>            fn hash() -> uint;
>            fn eq(other: self) -> bool;
>        }
>
>        type t<K,V> = { buckets: [bucket<K,V>] }
>
>        fn create<K:hash,V>() -> @t<K,V> {
>            ...
>        }
>
>        fn put<K:hash,V>(ht: @t<K,V>, k: K, v: V) {
>            ...
>        }
>
>        fn get<K:hash,V>(ht: @t<K,V>, k: K) -> V {
>            ... // fails if not present
>        }
>    }
>
> This looks reasonable.  Now we create two modules, `Module1` and
> `Module2`, which both share a reference to the same hashtable, but
> which have different implementations of the `hash` interface in scope:
>
>    mod Module1 {
>        impl hash for uint {
>            fn hash() -> uint { ret self; }
>            fn eq(other: int) -> bool { ret self == other; }
>        }
>        ...
>        fn foo() -> str {
>            let h = ht::create();
>            ht::put(ht, 3u, "hi"); // 3u.hash() == 3u here
>            ret Module2::bar(h);
>        }
>    }
>
>    mod Module2 {
>        impl hash for uint {
>            fn hash() -> uint { ret self / 2; }
>            fn eq(other: int) -> bool { ret self == other; }
>        }
>        ...
>        fn bar(h: @ht::t<uint, str>) -> str {
>            ret ht_get(ht, 3u); // fails because 3u.hash() == 1u here
>        }
>    }

So, I want to get an actual-running-code example of the instance
coherence problem as it stands in Rust, and Niko's example here seems
like a good place to start.  Is "impl hash for uint" a typo for "impl
of hash for uint"?  (If not, then I'm confused, because "impl hash for
uint" just sounds like an interface-less implementation of some
methods for uint, incidentally named "hash".  That missing "of"
changes the semantics of the example.)

Lindsey


More information about the Rust-dev mailing list