xxxxxx@gmail.com (Taylan Ulrich "Bayırlı/Kammer") writes:

> xxxxxx@gmail.com (Taylan Ulrich "Bayırlı/Kammer") writes:
>
>> A full cursor API for hash tables I have yet to see in any Scheme
>> implementation I looked at.  It's unclear to me how the cursor would
>> deal with rehashes.
>
> Correction: Racket has one, and the cursor is guaranteed to work so long
> as no entries are added to or removed from the hash table.
>
> I'll ponder and ask around on possible problems with that and add it if
> I don't find out about any problems.

If I'm not mistaken, implementing a cursor as an integer is simple with
hash tables using open addressing.

For those using chaining, one could use a record type bundling a bucket
vector index with a cell; 'cursor-next' could look like:

    (let ((index (cursor-index cursor))
          (cell (cursor-cell cursor)))
      (if (null? (cdr cell))
          (make-cursor (+ 1 index) (vector-ref buckets (+ 1 index)))
          (make-cursor index (cdr cell))))

(except that I don't handle the termination case, and don't jump over
empty buckets, but you get the idea)

That requires a low-level implementation when the bucket vector isn't
actually a Scheme vector, and I would rather not burden implementations
with that.  There might also be problems I fail to see right now with
this strategy I came up with on a whim.  We're also allocating a new
cursor for every step.

An alternative might be to use continuations:

  (define (hashtable-cursor ht)
    (call-with-prompt ht-walk
      (lambda ()
        (hashtable-walk ht
          (lambda (k v)
            (abort-to-prompt ht-walk k v))))
      (lambda (cont k v)
        (make-cursor cont k v))))

  (define (hashtable-cursor-next cursor)
    (call-with-prompt ht-walk
      (cursor-cont cursor)
      (lambda (cont k v)
        (make-cursor cont k v))))

I just tried that in Guile, but apparently the partial continuation I
create ends up being an "unrewindable" one.  I don't know why; it could
be because rewinding across C stack frames is not supported or so.

I also tried to make a call/cc based version, and failed, although it
seems possible because it doesn't have the "unrewindable continuation"
problem (I came far enough to notice that).  Possibly it mandates a
different API than hashtable-cursor/hashtable-cursor-next.  The
implementation would probably be pretty inefficient too.

So I'd say we want to keep cursors out of SRFI-126.  Or I can try to add
them as an optional feature if you think that would help.

Taylan