Re: Hash table cursor with delimited continuations

[Amirouche Boubekki]

Le 2015-10-01 15:56, address@hidden a écrit :
> Out of interest, I tried implementing a hash table cursor using
> hash-for-each and delimited continuations:

As Mark noted on IRC this is related to 
http://mumble.net/~campbell/scheme/foof-loop.txt

I've hit a similar problem in wiredtiger. wiredtiger is built out 
hashmaps called tables which can be queried using cursors with the 
following procedures:

(cursor-set-key cursor key)
(cursor-search cursor)

Then you can navigate using:

(cursor-next cursor)
(cursor-prev cursor)

One important thing do while scanning a table is to (cursor-reset 
cursor) before re-using the cursor for another scan.

The thing is that my procedure is a composition of stream procedure 
starting with a stream built out of a hashmap cursor. I don't know in 
advance when the cursor must be reset. Let's say (stream-wiredtiger 
"prefix") is a stream over all key/value pairs where key starts with 
"prefix". If I do:

((compose (stream-take 10) stream-wiredtiger) "prefix")

I take only the first 10 elements of the stream and the stream must be 
closed but there is no stream-close procedure.

Instead of using call/cc somehow, I make a list out of 
(stream-wiredtiger "prefix"), reset the cursor and return a stream with 
(list->stream LIST).

Here is the implementation of the list that is used to build 
stream-wiredtiger:

(define (lookup prefix cursor)
  (with-cursor cursor
    (cursor-key-set cursor prefix)
    (if (cursor-search-near cursor)
        (let loop ((atoms (list)))
          ;; make sure it did not go beyond the keys
          ;; we are interested in
          (if (prefix? prefix (cursor-key-ref cursor))
              (let ((atoms (cons (cursor-value-ref cursor) atoms)))
                ;; is there any other key in the hashmap?
                (if (cursor-next cursor)
                    (loop atoms)
                    atoms))))
        (list))))

The advantage is that I don't need to use call/cc. The problem is that 
the stream must fit into memory. Also another approach would be to only 
reset the cursor if we fully consume the stream. This will have a small 
performance impact on scanning but will save memory.

This went a little off-topic. I'll just add that outside the fact that 
srfi-41 procedures don't support currying it's basically gremlin 
traversal 
http://tinkerpop.incubator.apache.org/docs/3.0.0-incubating/#traversal


--
Amirouche ~ amz3 ~ http://www.hypermove.net