[plt-scheme] hash-has-key?

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.

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.

If, on the other hand, the compiler had no information about the type
of variables and return values, it could only either force the
programmer to perform unwrapping manually, which may be inconvenient,
or it could do automatic unwrapping everywhere, which would indeed
defy the use of introducing the values of type Option[T] in the first
place.

I hope I could make the concept somewhat more clear.

cu,
Thomas


-- 
When C++ is your hammer, every problem looks like your thumb.