Hash table cursor with delimited continuations

Hash table cursor with delimited continuations

[Taylan Ulrich Bayırlı/Kammer]

Out of interest, I tried implementing a hash table cursor using
hash-for-each and delimited continuations:

    (use-modules
     (srfi srfi-9)
     (ice-9 hash-table))

    (define-record-type <ht-cursor>
      (make-cursor %cont key value)
      cursor?
      (%cont %cursor-cont)
      (key   cursor-key)
      (value cursor-value))

    (define ht-iter-prompt (make-prompt-tag "ht-iter"))

    (define (ht-cursor ht)
      (call-with-prompt
       ht-iter-prompt
       (lambda ()
         (hash-for-each
          (lambda (k v)
            (abort-to-prompt ht-iter-prompt k v))
          ht))
       (lambda (cont k v)
         (make-cursor cont k v))))

    (define (ht-cursor-next cursor)
      (call-with-prompt
       ht-iter-prompt
       (%cursor-cont cursor)
       (lambda (cont k v)
         (make-cursor cont k v))))

(The cursor would be valid so long as the table isn't mutated.)

But I hit the following problem:

scheme@(guile-user)> (define ht (alist->hash-table '((a . 0) (b . 1))))
scheme@(guile-user)> (define cursor (ht-cursor ht))
scheme@(guile-user)> (cursor-key cursor)
$2 = a
scheme@(guile-user)> (set! cursor (ht-cursor-next cursor))
ERROR: In procedure #<partial-continuation 1a24e00>:
ERROR: Throw to key `vm-error' with args `(vm-run "Unrewindable partial
continuation" (#<vm-continuation 1c7b270>))'.

Entering a new prompt.  Type `,bt' for a backtrace or `,q' to continue.
scheme@(guile-user) [1]>


I couldn't find any direct documentation about this, only some mentions
of "rewindable" flags in the C API in (info "(guile) Dynamic Wind").

Is it a bug, or an undocumented limitation?..  I don't know what I
should generally expect when using delimited continuations with Guile
APIs implemented in C such as hash-for-each.

Thanks in advance,
Taylan

Re: Hash table cursor with delimited continuations

[Mark H Weaver]

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

> Out of interest, I tried implementing a hash table cursor using
> hash-for-each and delimited continuations:
>
>     (use-modules
>      (srfi srfi-9)
>      (ice-9 hash-table))
>
>     (define-record-type <ht-cursor>
>       (make-cursor %cont key value)
>       cursor?
>       (%cont %cursor-cont)
>       (key   cursor-key)
>       (value cursor-value))
>
>     (define ht-iter-prompt (make-prompt-tag "ht-iter"))
>
>     (define (ht-cursor ht)
>       (call-with-prompt
>        ht-iter-prompt
>        (lambda ()
>          (hash-for-each
>           (lambda (k v)
>             (abort-to-prompt ht-iter-prompt k v))
>           ht))
>        (lambda (cont k v)
>          (make-cursor cont k v))))
>
>     (define (ht-cursor-next cursor)
>       (call-with-prompt
>        ht-iter-prompt
>        (%cursor-cont cursor)
>        (lambda (cont k v)
>          (make-cursor cont k v))))
>
> (The cursor would be valid so long as the table isn't mutated.)
>
> But I hit the following problem:
>
> scheme@(guile-user)> (define ht (alist->hash-table '((a . 0) (b . 1))))
> scheme@(guile-user)> (define cursor (ht-cursor ht))
> scheme@(guile-user)> (cursor-key cursor)
> $2 = a
> scheme@(guile-user)> (set! cursor (ht-cursor-next cursor))
> ERROR: In procedure #<partial-continuation 1a24e00>:
> ERROR: Throw to key `vm-error' with args `(vm-run "Unrewindable partial
> continuation" (#<vm-continuation 1c7b270>))'.

The problem is that the partial continuation created by
'abort-to-prompt' includes a stack frame for 'hash-for-each', which is
implemented in C.  Guile does not support invoking partial continuations
that include C stack frames.  This is Andy's area, not mine, but I guess
the problem is that we don't have enough information to relocate a C
stack frame.

For now, the solution to problems like this is to avoid implementing
higher-order procedures in C, so that in practice C stack frames are
rarely found in the middle of the stack.

      Mark

Re: Hash table cursor with delimited continuations

[Taylan Ulrich Bayırlı/Kammer]

Mark H Weaver <mhw@netris.org> writes:

> The problem is that the partial continuation created by
> 'abort-to-prompt' includes a stack frame for 'hash-for-each', which is
> implemented in C.  Guile does not support invoking partial continuations
> that include C stack frames.  This is Andy's area, not mine, but I guess
> the problem is that we don't have enough information to relocate a C
> stack frame.
>
> For now, the solution to problems like this is to avoid implementing
> higher-order procedures in C, so that in practice C stack frames are
> rarely found in the middle of the stack.

I see, thanks for the explanation.

Taylan

Re: Hash table cursor with delimited continuations

[Amirouche Boubekki]

Le 2015-10-01 15:56, taylanbayirli@gmail.com 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