[plt-scheme] hash-has-key?

On Sun, Mar 29, 2009 at 3:33 AM, Thomas Chust <chust at web.de> wrote:
> 2009-03-28 Sam TH <samth at ccs.neu.edu>:
>> On Sat, Mar 28, 2009 at 3:43 PM, Thomas Chust <chust at web.de> wrote:
>>>
>>> In the same vein you could generate unwrapping code that throws an
>>> exception if a "not found" value is encountered and strips the wrapper
>>> otherwise for code like
>>>
>>>  (let: ([v : ValueType (hash-ref ht some-key)])
>>>    ...)
>>>
>>> but not for something like
>>>
>>>  (let: ([v : Any (hash-ref ht some-key)])
>>>    ...)
>>
>> This does not help at all.  Imagine that the 'not-found-value' is
>> called QQQ.  Then we have two choices:
>>
>> - QQQ is a value in our language.  Then it can be stored in the hash,
>> and we can't tell if we need to throw an exception.  This is the
>> current situation.
>> [...]
>
> Hello Sam,
>
> in the design I described, QQQ is a value in the language and it can
> be stored in the hash. Still it is perfectly clear whether an
> exception should be thrown or not.
>
> Since this is apparently not intuitive, let me elaborate the design
> somewhat more formally and precisely again:
>
> - Let Any be an abstract type that is common to all values of the language.
>
> - Let Hash[K, V] be the type of hash tables with keys of type K and
> values of type V.
>
> - Let Option[T] be an abstract parameterized type with exactly two subtypes:
>  * None is the type of the special value (none) and a subtype of
> Option[T] for any T.
>  * Some[T] is a subtype of Option[T] and the type of any wrapped value
>    (some t) where t is of type T.
>
> In the design I described, the function hash-ref I defined has the
> signature Hash[K, V] -> K -> Option[V] for any K and V. It takes a
> hash table and a key and returns either the value v associated to the
> key wrapped as (some v) or it returns (none) if and only if the hash
> table contains no value associated to the given key.
>
> To emphasize this again, the call (hash-ref ht k) will never return
> the special value (none) in this setup unless ht does not contain any
> value associated with the key k. Even if ht is of the fully generic
> type Hash[Any, Any] and it contains a key k that is associated with
> the value (none), the call (hash-ref ht k) will not return (none), but
> rather (some (none)).
>
> Thus, whether a value is associated to a key in a hash table or not is
> clearly reflected in the return value of hash-ref. However, if a value
> is found, it is not returned as is but rather wrapped into another
> value of type Some[T], where T is the type of the original value.

So, far, this can easily be implemented in Scheme, without types.

(define (new-hash-ref h k)
   (let/ec k (list (hash-ref h k (lambda _ (k #f))))))

> Since these wrapper objects by themselves are not particularly useful
> you have to unwrap them at some point. And when it comes to the
> unwrapping of these values, a statically typed language has a certain
> advantage over a dynamically typed one:
>
> If a compiler knew that a variable had some type T and that it was
> assigned a value of type Option[T], it could automatically insert code
> that unwrapped any value of type Some[T] into a T and threw an
> exception for the unique value of type None. If the value of type
> Option[T] was assigned to a variable of type Option[T] or of type Any,
> though, the compiler would insert no such unwrapping code. This
> approach would probably result in behavior that seemed right most of
> the time.

What if the hash table had type Hash[String, Any]?

What if our language contains type inference?  What is the inferred
type of (hash-ref h k)?

You should look at Richard Cobbe's dissertation [1], which contains a
fuller discussion of these issues in the context of Java.

[1] http://www.ccs.neu.edu/scheme/pubs/#dissertation-cobbe
-- 
sam th
samth at ccs.neu.edu