Changes between Version 72 and Version 73 of HashTablesCowan


Ignore:
Timestamp:
10/31/13 02:17:19 (4 years ago)
Author:
cowan
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • HashTablesCowan

    v72 v73  
    2323== Rationale == 
    2424 
    25 Hash tables themselves don't really need defending: almost all dynamically typed languages, from awk to !JavaScript to Lua to Perl to Python to Common Lisp, and including many Scheme implementations, have them in some form as a fundamental data structure.  Therefore, what needs to be defended is not the data structure but the procedures.  The present proposal is at an intermediate level.  It supports a great many convenience procedures on top of the basic hash table interfaces provided by [http://srfi.schemers.org/srfi-69/srfi-69.html SRFI 69] and [http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-14.html R6RS].  Nothing in it adds power to what those interfaces provide, but it does add convenience in the form of pre-debugged routines to do various common things, and even some things not so commonly done but useful. 
     25Hash tables themselves don't really need defending: almost all dynamically typed languages, from awk to !JavaScript to Lua to Perl to Python to Common Lisp, and including many Scheme implementations, provide them in some form as a fundamental data structure.  Therefore, what needs to be defended is not the data structure but the procedures.  The present proposal is at an intermediate level.  It supports a great many convenience procedures on top of the basic hash table interfaces provided by [http://srfi.schemers.org/srfi-69/srfi-69.html SRFI 69] and [http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-14.html R6RS].  Nothing in it adds power to what those interfaces provide, but it does add convenience in the form of pre-debugged routines to do various common things, and even some things not so commonly done but useful. 
    2626 
    2727There is no mandated support for thread safety, immutability, or weakness, though there is a semi-portable hook for specifying these features. 
     
    128128* [#Hashtablesassets Hash tables as sets]: `hash-table-union!`, `hash-table-intersection!`, `hash-table-difference!` 
    129129 
    130 * [#Exceptions Exceptions]: `hash-table-not-found?` 
     130* [#Exceptions Exceptions]: `hash-table-key-not-found?` 
    131131 
    132132=== Constructors === 
     
    136136`(make-hash-table `''equality-predicate'' [ ''hash-function'' ] [ ''arg'' ... ]`)` 
    137137 
    138 Returns a newly allocated hash table whose equality predicate and hash function are extracted from ''comparator''.  Alternatively, for backward compatibility the equality predicate and hash function can be passed as separate arguments; this usage is deprecated.  If an equality predicate rather than a comparator is provided, the ability to omit the ''hash'' argument is severely limited.  The implementation must provide hash functions appropriate for use with the predicates `eq?`, `eqv?`, `equal?`, `string=?`, and `string-ci=?`, and may extend this list.  But if any other equality predicate is provided without a hash function, an error should be signaled. 
    139  
    140 It is an error unless the equality predicate accepts two arguments and returns a truth value, and the hash function accepts one argument in the domain of the equality predicate and returns a non-negative exact integer.  It is the programmer's responsibility to ensure that two objects passed to the hash function return the same value if the same objects passed to the equality predicate return true; however, the converse is not required. 
     138Returns a newly allocated hash table whose equality predicate and hash function are extracted from ''comparator''.  Alternatively, for backward compatibility the equality predicate and hash function can be passed as separate arguments; this usage is deprecated.  If an equality predicate rather than a comparator is provided, the ability to omit the ''hash'' argument is severely limited.  The implementation must provide hash functions appropriate for use with the predicates `eq?`, `eqv?`, `equal?`, `string=?`, and `string-ci=?`, and may extend this list.  But if any unknown equality predicate is provided without a hash function, an error should be signaled. 
     139 
     140It is an error unless the equality predicate accepts two arguments and returns a truth value, and the hash function accepts one argument in the domain of the equality predicate and returns a non-negative exact integer.  It is the programmer's responsibility to ensure that if two objects are the same in the sense of equality predicate, then they  return the same value when passed to the hash function.  However, the converse is not required. 
    141141 
    142142If the equality predicate, whether passed as part of a comparator or explicitly, is more fine-grained (in the sense of R7RS-small section 6.1) than `equal?`, the implementation is free to ignore the programmer-specified hash function and use something implementation-dependent.  This allows the use of addresses as hashes, in which case the keys must be rehashed if they are moved by the garbage collector. 
     
    164164Returns `#t` if there is any association to ''key'' in ''hash-table'', and `#f` otherwise.  Must execute in expected amortized constant time.  (SRFI 69 `hash-table-exists?`; R6RS `hashtable-contains?`) 
    165165 
     166Note:  The following three predicates do not obey the trichotomy law and therefore do not constitute a total order on hash tables. 
     167 
    166168`(hash-table=? `''value=? hash-table,,1,, hash-table,,2,,''`)` 
    167169 
     
    190192`(hash-table-ref `''hash-table key'' [ ''failure'' [ ''success'' ] ]`)` 
    191193 
    192 Extracts the value associated to ''key'' in ''hash-table'', invokes the procedure ''success'' on it, and returns its result.  Otherwise, invokes the procedure ''failure'' on no arguments and returns its result.  If ''success'' is not provided and is required, the value itself is returned.  If ''failure'' is not provided but is required, an error that satisfies `hash-table-not-found?` is signaled.  Must execute in expected amortized constant time, not counting the time to call the procedures.  (SRFI 69 `hash-table-ref`) 
     194Extracts the value associated to ''key'' in ''hash-table'', invokes the procedure ''success'' on it, and returns its result; if ''success'' is not provided, then the value itself is returned.  Otherwise, `hash-table-ref` invokes the procedure ''failure'' on no arguments and returns its result; if ''failure'' is not provided, then an error that satisfies `hash-table-key-not-found?` is signaled.  Must execute in expected amortized constant time, not counting the time to call the procedures.  (SRFI 69 `hash-table-ref`) 
    193195 
    194196`(hash-table-ref/default `''hash-table key default''`)` 
     
    213215`(hash-table-set-entries! `''hash-table keys-list values-list''`)` 
    214216 
    215 Repeatedly mutates ''hash-table'', setting each element of ''keys-list'' to the corresponding element of ''values-list'' in the order given.  Excess keys or values are ignored. 
     217Repeatedly mutates ''hash-table'', setting each element of ''keys-list'' to the corresponding element of ''values-list'' in the order in which they are specified.  Excess keys or values are ignored. 
    216218 
    217219`(hash-table-set-alist! `''hash-table alist''`)` 
    218220 
    219 Repeatedly mutates ''hash-table'' using the associations of ''alist'' in the order given. 
     221Repeatedly mutates ''hash-table'' using the associations of ''alist'' in the reverse of the order in which they appear in ''alist''. 
    220222 
    221223`(hash-table-delete! `''hash-table key''`)` 
     
    269271`(hash-table-pop! `''hash-table key''`)` 
    270272 
    271 If an association with ''key'' is found in ''hash-table'', then return the car of the value, and update the value to its own cdr.  If the value is not found or is not a pair, signal an error. 
     273If an association with ''key'' is found in ''hash-table'', then return the car of the value, and update the value to its own cdr.  If the value is not found, an error satisfied by `hash-table-key-not-found` is signaled.  It is an error if the value is not a pair. 
    272274 
    273275`(hash-table-search! `''hash-table key failure success''`)` 
     
    390392=== Exceptions === 
    391393 
    392 `(hash-table-not-found? `''obj''`)` 
     394`(hash-table-key-not-found? `''obj''`)` 
    393395 
    394396Returns `#t` if ''obj'' is an object raised by the `hash-table-ref` procedure or any other procedure that accesses hash tables when the key is not found and there is no failure procedure, and `#f` otherwise. 
     
    402404* S7 does not support arbitrary equality predicates: the implementation chooses a predicate based on the nature of the keys. 
    403405 
    404 * Guile supports arbitrary equality predicates, but in that case the equality predicate and hash function must be passed explicitly to all the primitive procedures.  Consequently, hash tables corresponding to the present proposal would have to be records containing a Guile hash table, an equality predicate, and a hash function, which means that they could not interoperate directly with naked Guile hash tables. 
     406* Guile supports arbitrary equality predicates, but the equality predicate and hash function must be passed explicitly to all the primitive procedures.  Consequently, hash tables corresponding to the present proposal would have to be records containing a Guile hash table, an equality predicate, and a hash function, which means that they could not interoperate directly with naked Guile hash tables. 
    405407 
    406408* SISC, Scheme48/scsh, RScheme, Scheme 9, and Rep do not provide any procedure that copies a hash table, nor any way of inspecting it to determine its equality predicates and hash functions so that it can be re-created.