Re: choose-and-remove! operation taylanbayirli@xxxxxx 12 Sep 2015 12:43 UTC

John Cowan <> writes:

> Taylan Ulrich Bayırlı/Kammer scripsit:
>> It's unfortunate that this conflicts with Gauche, but shouldn't one use
>>     (pop! (hash-table-ref ht k) x)
> One should, except that there is no SRFI for macros like pop!.  Someone
> (hint, hint) should write one on top of SRFI 17.  A good starting place
> would be the CLHS: <>.

    (define-syntax pop!
      (syntax-rules ()
        ((pop! <place>)
         (let ((stack <place>))
           (set! <place> (cdr stack))
           (car stack)))))

This works fine with SRFI-17.  I don't think anything more is necessary?
For instance

    (pop! (hash-table-ref ht k))

expands to

    (let ((stack (hash-table-ref ht k)))
      (set! (hash-table-ref ht k) (cdr stack))
      (car stack))

which in turn, via SRFI-17, expands to

    (let ((stack (hash-table-ref ht k)))
      ((setter hash-table-ref) ht k (cdr stack))
      (car stack))

which when '(setter hash-table-ref)' is hash-table-set! is equivalent to

    (let ((stack (hash-table-ref ht k)))
      (hash-table-set! ht k (cdr stack))
      (car stack)).

This assumes the invariant that '(hash-table-ref ht k)' returns a pair.
Testing against 'null?' will mean a third lookup of the key, which is
tolerable.  (Common subexpression elimination might help, though I'm not
sure about the interaction with weak hash tables.)  In practice, the
lookup should generally not fail either, since you would expect the
entry to be initialized with '() at the very least.  If one really
desires, the following will abstract that out as well:

    (define-syntax hnull?
      (syntax-rules ()
        ((hnull? <ht> <k>)
         (null? (hash-table-intern! <ht> <k> '())))))

    (define-syntax hpop!
      (syntax-rules ()
        ((hpop! <ht> <k>)
         (pop! (hashtable-ref <ht> <k>)))))

so now your code looks like:

    (if (hnull? ht k)
        (exceptional case)
        (use (hpop! ht k)))

and that required 8 lines of helper syntax code of which 6 are
boilerplate, and that's the pessimal case.  I don't see a need to
specify these anywhere.

That's regarding the hash table specific ones.  For the generic push!
and pop!, host this on Snow and be done with it:

    (define-library (aux push/pop)
      (import (scheme base))
      (export push! pop!)
        (define-syntax push!
          (syntax-rules ()
            ((push! <place> <value>)
             (set! <place> (cons <value> <place>)))))
        (define-syntax pop!
          (syntax-rules ()
            ((pop! <place>)
             (let ((stack <place>))
               (set! <place> (cdr stack))
               (car stack)))))))

Composability for the win!  No need to add these to any spec IMO.