---------- Forwarded message ---------
Von:
Marc Nieper-Wißkirchen <xxxxxx@gmail.com>Date: Fr., 7. Feb. 2025 um 15:28 Uhr
Subject: Re: Suggestion: ephemeron-case
To: Daphne Preston-Kendal <
xxxxxx@nonceword.org>
Am Mi., 5. Feb. 2025 um 19:16 Uhr schrieb Daphne Preston-Kendal <xxxxxx@nonceword.org>:
>
> On 5 Feb 2025, at 19:03, Marc Nieper-Wißkirchen <xxxxxx@gmail.com> wrote:
>
> >> I don’t see how this is the case. The implementation would somehow need to both inline the helper-proc (in order to do the re-ordering optimization you were worried about when you introduced the reference-barrier procedure) but also discard the reference-barriering nature of the mention of ‘key’. This seems very unlikely.
> >
> > It should be possible to prove the correctness of a program formally.
> > For that, "very unlikely" is not enough.
>
> It’s up to the compiler to do this correctly (or not), of course.
The compiler only has to follow the specification, not the intent of the programmer.
> > That said, all semantics suggested so far have another problem, which
> > I haven't mentioned yet: A reference barrier on the key in the
> > unbroken case is useless. The GC can break an ephemeron if, under the
> > assumption that it is broken, the key will not be kept alive.
> >
> > I am going to post a "real life" example soon (I am currently ill, and
> > my brain is not fully working) so that we have some concrete code to
> > test potential syntax against.
>
> Okay, please do. I’m a bit confused by this. Get well soon!
Thank you. I am still not feeling well, but I managed to produce some example code, which will be incorporated into the next draft.
Here is a simple library for a list-based weak map:
**
#!r6rs
(library (weakmaps)
(export
make-weakmap
weakmap?
weakmap-contains?
weakmap-set!
weakmap-ref
weakmap-delete!)
(import
(rnrs)
(rnrs mutable-pairs)
(srfi :254 ephemerons-and-guardians ephemerons))
;; weakmap-ref and weakmap-contains? keep the KEY argument alive.
;; The KEY argument to all procedures should denote a location or
;; sequence of locations.
;; Note that no explicit tests for broken ephemerons are necessary
;; because "the broken key" #f can never be a regular key.
(define-record-type weakmap
(nongenerative) (sealed #t)
(fields (mutable entries))
(protocol
(lambda (new)
(lambda ()
(new '())))))
(define weakmap-contains?
(lambda (wm key)
(assert (weakmap? wm))
(let f ([entries (weakmap-entries wm)])
(if (pair? entries)
(if (eq? (ephemeron-key (car entries)) key)
(begin
(reference-barrier key)
#t)
(f (cdr entries)))
(begin
(reference-barrier key)
#f)))))
(define weakmap-set!
(lambda (wm key val)
(assert (weakmap? wm))
(let f ([entries (weakmap-entries wm)]
[set-tail! (lambda (tail) (weakmap-entries-set! wm tail))])
(if (null? entries)
(set-tail! (list (make-ephemeron key val)))
(if (eq? (ephemeron-key (car entries)) key)
(set-tail! (cons (make-ephemeron key val) (cdr entries)))
(f (cdr entries) (lambda (tail) (set-cdr! entries tail))))))))
(define weakmap-ref
(lambda (wm key default)
(assert (weakmap? wm))
(let f ([entries (weakmap-entries wm)])
(if (pair? entries)
(if (eq? (ephemeron-key (car entries)) key)
(let ([val (ephemeron-value (car entries))])
(reference-barrier key)
val)
(f (cdr entries)))
(begin
(reference-barrier key)
default)))))
(define weakmap-delete!
(lambda (wm key)
(assert (weakmap? wm))
(let f ([entries (weakmap-entries wm)]
[set-tail! (lambda (tail) (weakmap-entries-set! wm tail))])
(unless (null? entries)
(if (eq? (ephemeron-key (car entries)) key)
(set-tail! (cdr entries))
(f (cdr entries) (lambda (tail) (set-cdr! entries tail)))))))))
**
And here is some code to test it:
**
#!r6rs
(import
(rnrs)
(srfi :254)
(weakmaps))
;;; Weakmaps
(define wm (make-weakmap))
(assert (weakmap? wm))
(define x (string #\x))
(define y (string #\y))
(assert (not (weakmap-contains? wm x)))
(assert (eq? 'dflt (weakmap-ref wm x 'dflt)))
(weakmap-delete! wm y)
(weakmap-set! wm x 1)
(weakmap-set! wm y 2)
(assert (weakmap-contains? wm x))
(assert (weakmap-contains? wm y))
(assert (eqv? 1 (weakmap-ref wm x #f)))
(assert (eqv? 2 (weakmap-ref wm y #f)))
(weakmap-set! wm x 3)
(assert (eqv? 3 (weakmap-ref wm x #f)))
(assert (eqv? 2 (weakmap-ref wm y #f)))
(weakmap-delete! wm x)
(assert (eqv? 2 (weakmap-ref wm y #f)))
(assert (not (weakmap-contains? wm x)))
(assert (eqv? 2
(let ([tmp y])
(set! y #f)
(weakmap-ref wm tmp #f))))
Feel free to ask questions. The reference barrier is needed in the accessor procedures (`weakmap-contains?` and `weakmap-ref`).
Marc