Newsgroups: comp.lang.misc
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!linus!linus!clouseau!john
From: john@clouseau.mitre.org (John D. Burger)
Subject: Re: Dynamic typing (part 3)
Message-ID: <1991Mar25.170851.2682@linus.mitre.org>
Sender: news@linus.mitre.org (News Service)
Nntp-Posting-Host: clouseau.mitre.org
Organization: The MITRE Corporation, Bedford, MA 01730
Date: Mon, 25 Mar 1991 17:08:51 GMT

db@cs.ed.ac.uk (Dave Berry) wrote:

  I don't see how it's possible to write a polymorphic hash-function
  in any language unless you know all the possible types or
  type-representations that the language will ever have, at the time
  when you write the function.

and ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) replied:

  In the case of something like Lisp, we do know all the possible type
  representations.  There is no particular reason why ML couldn't have
  a built-in polymorphic "hash" function that applies to any
  "equality" type.  Abstract data types are a problem, but if you can
  replace '=' for a data type you can replace 'hash' for it as well.
  (Lisp has a short-cut here which ML lacks; a hash function in Lisp
  has to approximate EQ rather than EQUAL.)

Actually, in Common Lisp, when a programmer creates a hash table she
specifies the equality test she wants to use.  The implementation must
provide EQ, EQL, EQUAL and EQUALP hash tables, which cover the basic
flavors of equality in Common Lisp.

A programmer also has access to an underlying hashing function, if he
wants to implement his own hashed structures.  This function is
SXHASH, which implements EQUAL equality.  That is:

  (EQUAL X Y) implies (= (SXHASH X) (SXHASH Y))

However, none of these built-in predicates implement component-wise
equality for user-defined datatypes, so it's not possible for two
different instances of a particular datatype to (necessarily) be
hashed alike, even if their components are identical.
--
John Burger                                               john@mitre.org

"You ever think about .signature files? I mean, do we really need them?"
  - alt.andy.rooney