Re-entrant parameterize modification isolation when using shift/reset

[Greg Rosenblatt]

I'm using dynamic binding while also using delimited control operators such as shift and reset.  When shift captures the context of a `parameterize`, I'd like to be able to resume that continuation in the same context multiple times without observing modifications caused by other resumptions.

I was surprised that subsequent re-entries can observe modifications from the earlier ones, since my mental model of dynamic parameters was that their values were retrieved from a fresh dynamic calling context, whose frames are copied each time the delimited continuation is invoked.  But it looks like dynamic parameters actually rely on a shared mutable cell, in this case a thread cell.

Knowing this, I have a strange workaround using a wrapping thread to force a distinct thread cell to be created for each resumption, providing isolation.  Is there a better way to do this?

I'm also interested in the reasons behind the current design.  Is there a downside to storing parameter bindings directly on the stack, rather than in a thread cell pointed to by the stack?

Here is an example, including a demonstration of the workaround:

```

#lang racket/base
(require racket/control)

(define P (make-parameter #f))
(define (show) (displayln (P)))
(define (inc) (P (+ 1 (P))))

(define (re-enter k)
  (define result (void))
  (define t (thread
              (lambda ()
                (set! result (k (void))))))
  (thread-wait t)
  result)


(define K (reset (parameterize ((P 0))
                   (show)
                   (inc)
                   (shift k k)
                   (show)
                   (inc)
                   (P))))

;; The behavior that surprised me:

(displayln "without threads:")
(K) ; 2
(K) ; 3
(K) ; 4

;; The behavior I would like:

(displayln "with threads:")
(re-enter K) ; 5
(re-enter K) ; 5

(re-enter K) ; 5

```

Program output:

0
without threads:
1
2
2
3
3
4
with threads:
4
5
4
5
4
5

[jackh...@gmail.com]

I don't fully follow the example you gave because I'm not super familiar with shift/reset, but would using continuation marks directly instead of parameters work for your use case? Continuation marks work like what you described, where data is stored directly on the stack rather than in a thread cell pointed to by the stack.

[Greg Rosenblatt]

Thanks for the response, Jack.

I'm looking at: https://docs.racket-lang.org/reference/contmarks.html

I don't see a way to update the value of an existing key without installing a new mark.  Is it possible to do that?  Parameters allow you to update the value associated with the innermost use of `parameterize` without re-parameterizing.  These updates are what I'd like to isolate between resumes.

The idea in the example is that `(shift k k)` "throws" the continuation at that point up to the enclosing `reset`.  So `K` ends up bound to a procedure of one (unused) argument that continues where the `(shift k k)` left off, inside the body of the `parameterize`.  You can use continuations like these to implement a form of cooperative thread or coroutine, which can even be resumed from the same point multiple times.  However in cases where you're also using `parameterize`, unlike spawning a real Racket thread, it looks like we don't get the benefit of local parameter updates being isolated across multiple resumes, so each one sees any further updates made by other resumes, like they are sharing mutable state.  I was hoping to see each resume begin in the same dynamically-scoped state, oblivious to dynamically-scoped updates made by other resumes.

Aside from the thread-wrapping hack, I'm not sure I see a good way to recover isolation behavior from non-isolation-by-default (though the reverse doesn't seem to be a problem: if we started with isolation-by-default, we could recover non-isolation by installing a mutable box as the parameter).  An alternative is to abandon parameters completely and replace them with algebraic state effects (also using delimited continuations), but it seems like a shame to have to do that when parameters are already so close to the right thing.

[Matthew Flatt]

At Sun, 25 Jul 2021 10:35:00 -0700 (PDT), Greg Rosenblatt wrote:
> I was surprised that subsequent re-entries can observe modifications from
> the earlier ones, since my mental model of dynamic parameters was that
> their values were retrieved from a fresh dynamic calling context, whose
> frames are copied each time the delimited continuation is invoked.

> [...]

> I'm also interested in the reasons behind the current design. Is there a
> downside to storing parameter bindings directly on the stack, rather than
> in a thread cell pointed to by the stack?

I think I see what you mean here, but I also think that idea would run
into trouble. A (delimited) continuation is invoked every time you
return a value to a continuation, whether or not that continuation was
captured by `call/cc`. Internally, in fact, the current continuation
frequently gets reified and invoked through returns. I think it would
create a bad interaction among features if a distinction were made
between explicit (applying a captured continuation) and implicit
(returning a value) continuation invocations.

> I'd like to be able to resume that continuation in the same context
> multiple times without observing modifications caused by other

> resumptions. [...] But it looks like dynamic parameters actually rely

> on a shared mutable cell, in this case a thread cell.

Yes, parameters are based on a mapping

parameter * thread * paramterizization -> box

When you set or look up a parameter value, the thread part comes from
`current-thread`, and the parameterization part comes from a
continuation mark. So, that's why capture and restore within a thread
sees the same box, but capture and restore of a continuation in a
different thread gets a different box.

I think you want to introduce a notion of "resume" that replaces the
thread part of the mapping, plus a replacement notion of
parameterization. That is, each time you resume, the applied
continuation should extend one that maps an internal mark to the
current resume. A replacement for `parameterize` would also install a
mark (with a different key) to identify a "parameterization", while
also mapping the parameter * parameterization * resume to a fresh box.
When you look up a parameter value or mutate a parameter, the current
mark for the resume and the current mark for the parameterization would
let you find the right box.

It may be best to have a "parameterization" specific to each
"parameter" (i.e., a separate mark for each parameter), instead of
aggregating them in the way `parameterize` does. In the case of threads
and parameters, aggregation makes it easier to create a new thread that
inherits the parameterization of the creating thread. But if you don't
need that, aggregation also works less well with delimited continuation
capture, because `parameterize` captures all parameter values and not
just the ones that are set in the `parameterize` form.

[Greg Rosenblatt]

Thanks, I think that makes sense.

Is the `parameter * thread * parameterization -> box` part implemented as something like a global weak-hash, or is it built directly into the stack representation?

Continuing the other conversation for a moment with a code reference to explain to my future self, or anyone else curious, what I meant by "algebraic state effects". Here's a simple implementation with a couple examples:

```

#lang racket/base

(require racket/control)

(struct state-parameter (tag)
        #:property prop:procedure
        (case-lambda
          ((self)   (shift-at (state-parameter-tag self) k (lambda (x) ((k x)      x))))
          ((self v) (shift-at (state-parameter-tag self) k (lambda (_) ((k (void)) v))))))

;; Analogous to make-parameter, but without a default value
(define (make-state-parameter)
  (state-parameter (make-continuation-prompt-tag)))

(define-syntax state-parameterize*
  (syntax-rules ()
    ((_ ()         body ...)
     (let () body ...))
    ((_ ((e.p e))  body ...)
     (let ((p e.p) (x e))
       ((reset-at (state-parameter-tag p)
                  (let ((result (begin body ...)))
                    (lambda (_) result)))
        x)))
    ((_ (b bs ...) body ...)
     (state-parameterize* (b) (state-parameterize* (bs ...) body ...)))))

(define-syntax state-parameterize-etc
  (syntax-rules ()
    ((_ final       ()               body ...)
     (state-parameterize* final body ...))
    ((_ (final ...) ((e.p e) bs ...) body ...)
     (let ((p e.p) (x e))
       (state-parameterize-etc (final ... (p x)) (bs ...) body ...)))))

;; Analogous to parameterize
(define-syntax-rule (state-parameterize etc ...) (state-parameterize-etc () etc ...))


;; The same kind of single state example
(define P (make-state-parameter))

(define (show) (displayln (P)))
(define (inc) (P (+ 1 (P))))

(define K
  (reset
    (state-parameterize ((P 0))

      (show)
      (inc)
      (shift k k)
      (show)
      (inc)
      (P))))

(displayln "with algebraic state:")
(K) ; 2
(K) ; 2
(K) ; 2


;; An example with multiple states
(define R (make-state-parameter))
(define Q (make-state-parameter))
(define (show2) (displayln `(R: ,(R) Q: ,(Q))))
(define (inc2) (R (+ 1 (R))) (Q (- (Q) 1)))

(define J
  (reset
    (state-parameterize ((R 0) (Q 0))
      (show2)
      (inc2)
      (shift k k)
      (show2)
      (inc2)
      (list (R) (Q)))))

(displayln "with multiple algebraic states:")
(J) ; 2 -2
(J) ; 2 -2
(J) ; 2 -2

```

[Matthew Flatt]

At Fri, 30 Jul 2021 12:56:37 -0700 (PDT), Greg Rosenblatt wrote:
> Is the `parameter * thread * parameterization -> box` part implemented as
> something like a global weak-hash, or is it built directly into the stack
> representation?

A parameter holds a key and a thread cell, where the thread cell is
used if the parameter hasn't been `parameterized`. The key is used to
look for a thread cell in a parameterization that's found as a
continuation marks. A thread cell is basically a mutable emphemeron
hash that maps threads to values, plus a default value to use if
there's no mapping for a thread.

So, you probably want something similar, except probably using the key
to look up a continuation mark instead of the parameterization
indirection, and then using "resume cells" instead of "thread cells".