Re: weak HTs

[Bruno H. <br...@cl...>]

Sam wrote:
> >    :VALUE ??
>
> mail assignment to warships.
> when a warship is sunk, we want to remove the mail->warship map.

OK. But when the key is dead, we want to remove the (key, value)
pair as well, right? (A warship cannot be sent mail if its name has been
forgotten.) So we end up with :EITHER for this usecase.

> >    :BOTH ??
>
> same as :EITHER, but instead of "is the spouse of" we are recording
> "is the spouse/widow of".

How can this work? Once the spouse/husband is dead, the other one cannot
refer to it any more.

This :BOTH is semantic and implementatory nonsense:
1. what should gethash return when the value is dead but the key is not?
2. maphash will call its argument with value = unbound.
3. what is the entry good for when the key is dead?

> > And how to implement a canonicalization tables, for which the key
> > occurs in the value? :KEY doesn't fit, and :BOTH doesn't fit either.
>
> why ?  I think :BOTH could be used here...

Think more...

I've found the following issues/questions in the code:
      1. spvw_garcol loop is not correct
      2. count is not decremented by the GC
      3. hashtabl.d hash a %2 instead of /2
      4. weakkvt is an array, why? replace, subseq etc. make no sense
         because the weakkvt is only used as an auxiliary objects by the
         hash tables.
         Did you do it so that the maximum length is = 2^24 not 2^16?
      5. when is the value marked when the type is :key?
         You need to be able to do these things correctly:
         (let ((m1 (make-hash-table :weak :key))
               (m2 (make-hash-table :weak :key))
               (m3 (make-hash-table :weak :key))
               (m4 (make-hash-table :weak :key))
               (x1 (list 1)))
           (let ((x2 (list 2)) (x3 (list 3)) (x4 (list 4)) (x5 (list 5)))
             (setf (gethash x1 m1) x2)
             (setf (gethash x2 m2) x3)
             (setf (gethash x3 m3) x4)
             (setf (gethash x4 m4) x5))
           (gc)
           (gethash (gethash (gethash (gethash x1 m1) m2) m3) m4))
         must return x5. Of course this must work independently of the
         order of m1, m2, m3, m4 in the all_weakkvts list.

Missing comments:
      6. maphash looks only at the key, is this sufficient for all types?
         yes, because spvw_garcol kills the entire entry.
      7. In spvw_garcol, there is no need to call gc_mark for :EITHER.
         Put a comment there!

In summary, I've found so many problems that I think before fixing that,
it's good to implement more primitive operations. (Just like you cannot
get PROG right if you haven't implemented LET, BLOCK and TAGBODY before.)

I propose the following types of objects:

   weak-pointer              is ok as it is
   weak-and                  a box holding two values x and y,
                             as long as both x and y are alive.
   no weak-or                because that would be the same semantic
                             nonsense as :BOTH above.
   weak-mapping              a box holding two values x and y,
                             as long as x is alive. Implements a mapping
                             x -> y. This is the semantic equivalent to a
                             weak hash table of type :KEY with just 1 entry.
   weak-and-mapping          a box holding three values x, y and z,
                             as long as x and y are alive. Implements a
                             mapping (x, y) -> z.
   weak-or-mapping           a box holding three values x, y and z,
                             as long as x or y are alive. Implements a
                             mapping (x, y) -> z.

THEN, when you've implemented these elementary bricks, it should be much
clearer how to fix the weak hash tables.

Btw, I do need efficient weak hash sets and weak hash tables for CLOS
(weak hash sets for the subclasses list, and weak hash tables for the
object -> #<eql-specializer object> mapping).

Bruno