[<<][compsci][>>][..]
Sun Sep 6 10:55:07 CEST 2009

Monads vs. delimited control

So, practically: I have a need to turn a function that uses explicit
mutation of a dynamic variable into a pure function.  How to do this
without adding explicit state threading?

Simplified: you want the dynamic parameter to be included inbetween
the prompt and the shift / control operator that reifies the dynamic
context into a function.  I.e. something like this:

#lang scheme/base
(require scheme/control)
(provide make-counter state)
(define state (make-parameter #f))
(define (make-counter)
  (reset
   (parameterize ((state 0)) ;; param sandwiched between `reset' and `shift'
     (let loop ()
       (printf "state = ~s\n" (state))
       (shift k k)
       (state (add1 (state))) ;; mutate
       (loop)))))

The problem is that it doesn't give you referential transparency: the
mutation is still visible when a certain continuation gets invoked
multiple times, as the parameter's storage location is a shared value.

Every continuation should somehow include its own value of the
parameter.  This can be assured by saving the parameter's value
whenver a continuation is created, and resetting it whenever it is
resumed:

#lang scheme/base
(require scheme/control)
(provide make-counter state invoke)
(define state (make-parameter #f))
(define (make-counter)
  (reset
   (parameterize ((state 0))
     (let loop ()
       (printf "state = ~s\n" (state))
       (state (let ((s (state))) (shift k (cons k s))))
       (state (add1 (state))) ;; mutate
       (loop)))))
(define (invoke ctx)  ((car ctx) (cdr ctx)))

Here the continuation is extended with a context value `s' which is
passed to the continuation by `invoke' and used to reset the `state'
parameter upon context entry.


It looks like this is related to the ``continuations + storage cell''
approach in [1], though a bit too dense for me atm.

Some related work.  In [2] investigates the interaction between DC and
`dynamic wind', while [3] focusses on DC and dynamic binding.  I must
admit I fail to understand the subtleties, as it all seems ``obvious''
to me from the pov. of continuation marks.  I'll come back to this
after using it in practice.

To summarize: partial continuations capture control, while parameters
are useful for ``locally global'' threaded state in case it's not
_practical_ to implement that lexically.  You locally give up
referential transparency to increase modularity and simplicity of
function interfaces.


[1] http://eprints.kfupm.edu.sa/62283/1/62283.pdf md5://e60a51d38011e8dca44540f590643001
[2] http://people.cs.uchicago.edu/~robby/pubs/papers/icfp2007-fyff.pdf
[3] http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding



[Reply][About]
[<<][compsci][>>][..]