Native delimited continuations in (byte-code) OCaml

All you guys waiting to implement zippers etc. in Ocaml can go right ahead: There's now a library implementation of delimited continuations.

In fact, there are two implementations. A native implementation in C that copies the relevant part of the interpreter's stack, and a pure Ocaml version that requires monadic style of writing code.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

A month behind...

This was posted on caml-list on February 28th.

See that "(new topic)" link on the left?

That's for posting comments about things like this when you find out about them! ;)

Our goal is quality not

Our goal is quality not timeliness :-)

Dynamic binding

Indeed this story is month behind the caml-list message, which
Jacques Carette has very kindly helped me to post. The code was
written back last year, btw. The timing nevertheless is fortuitous.
Now that OCaml has delimited continuations, we can implement
lightweight threads and dynamic binding (aka, the environment). The
latter lets us parameterize a function invoked deep in the code
without changing all the callers of that function. Dynamic binding is
pervasive (e.g.: current working directory, i/o redirection), and is
quite useful in moderation, as it adds expressivity to the language
(see Luc Moreau, A Syntactic theory of dynamic binding).

Delimited continuations help us combine both threads and dynamic
environment in the ``natural way''. If someone has a real-world
example of using dynamic environment, and experienced or anticipates
its problematic interaction with threads, I'd indeed appreciate
hearing about it.

SLIME

If someone has a real-world example of using dynamic environment, and experienced or anticipates its problematic interaction with threads, I'd indeed appreciate hearing about it.

We have had some interesting problems in SLIME. This is an Emacs mode in which most commands are implemented with RPCs to a Common Lisp system and many of those commands send the user's code fragments for evaluation (e.g. eval-region). Most RPCs are executed by SLIME in a new thread and for the eval-region example the user's code can spawn more threads of its own too. The problem is to preserve everybody's invariants on the dynamic environment while everybody else is spawning threads.

The most interesting issue for us has been what part of the dynamic environment a new thread will inherit from its parent. We have to pass on information needed by SLIME (e.g. "Which Emacs are we talking to") and leave out information that we know is invalid (e.g. "There are three recursive Emacs debugger loops on my stack"). The user's application has similar concerns that we need to somehow respect without knowing explicitly what they are.

I can say that it isn't enough to not pass on any dynamic bindings at all because tricks like:

(let ((foo *foo*))
  (spawn (lambda ()
           (let ((*foo* foo))
             ...))))

are all very well for our own variable *foo* but no help for other peoples' variables. Likewise to pass on all the dynamic environment is no good because tricks like:

(spawn (lambda ()
         (let ((*foo* nil)) ; don't inherit value
           ...)))

have the same problem.

A workable solution in the Lisp context seems to be having a shared mechanism for each user to flag which state should be inherited by the new thread and for the rest to excluded. Allegro Common Lisp have a nice way to handle this if I recall correctly.

P.S. It's interesting to write code that should be portable to systems that don't inherit any dynamic bindings aswell as to those that inherit them all!

P.P.S. I don't know what a delimited continuation is so I apologise if I have missed the topic completely :-)

Private and shared dynamic bindings

Thank you, Luke and Dave. Your comments about the importance of being
able to inherit some of the dynamic environment (and declare
the rest private to a `thread') are appreciated.

The partial inheritance of the dynamic environment at thread
creation is the natural outcome of the joint work with Chung-chieh
Shan and Amr Sabry on delimited dynamic binding. Here's an example,
which uses delimited continuations (shift) to create and
cooperatively run two `threads':

(define parmp (my-make-parameter #f)) ; will be private in threads
(define parms (my-make-parameter #f)) ; this parameter will be `shared'

; A sample function to print the current dynamic environment.
(define (tf1 title)
  (printf "~a: private ~a, shared ~a~n" title (parmp) (parms)))

(define (test4)
  (my-parameterize ((parmp 1))
    (my-parameterize ((parms 500))
      (let*
	((thread1
	   (push-prompt p0
	     (my-parameterize ((parmp (parmp))) ; this line makes parmp private
	       (tf1 "thread1: starting")
	       (my-parameterize ((parmp 10))
		   (shiftV p0 f f)		; suspend
		   (tf1 "thread1: continuing...")
		   (parmp 11) (parms 600)       ; mutate both parameters
		   (shiftV p0 f f)		; suspend
		   (tf1 "thread1: finishing, after dlet...")))))
	  (thread2
	    (my-parameterize ((parmp 2))
	      (push-prompt p0
		; the following line designates parmp private in thread2
	        (my-parameterize ((parmp (parmp))) 
		  (tf1 "thread2: starting")
		  (shiftV p0 f f)		; suspend
		  (tf1 "thread2: continuing...")
		  (my-parameterize ((parmp 22))
		    (shiftV p0 f f)		; suspend
		    (tf1 "thread2: finishing, after dlet...")))))))
	(my-parameterize ((parmp 100))
	  (my-parameterize ((parms 501))
	    (tf1 "main thread")
	    (let*
	      ((thread1 (thread1 #f))
	       (_ (tf1 "main thread"))
	       (thread2 (thread2 #f))
		)
	      (my-parameterize ((parmp 110))
		(my-parameterize ((parms 510))
		  (thread1 #f)
		  (thread2 #f))))))))))

This example produces the following result:

thread1: starting: private 1, shared 500
thread2: starting: private 2, shared 500
main thread: private 100, shared 501
thread1: continuing...: private 10, shared 501
main thread: private 100, shared 600
thread2: continuing...: private 2, shared 600
thread1: finishing, after dlet...: private 11, shared 510
thread2: finishing, after dlet...: private 22, shared 510

Incidentally, dynamic variable (aka, parameters) are mutable. Mutation
of a `shared' parameter is visible to everyone; mutation to the
private one is visible only in the corresponding thread. That behavior
is inherent in the implementation; we don't need to do anything
special for it. To designate a parameter `private', we merely need to
add a dummy binding for it: (my-parameterize ((parmp (parmp)))
...)
. No special syntax is needed.

In the above code, (shiftV p0 f f) can be read as mere
(shift f f), and push-prompt p0 as
reset. The code implements the parameter object interface
(see SRFI-39 and also Chez Scheme). The implementation is certainly
different from that of SRFI-39 (in fact, SRFI-39 explicitly disclaims
all the thread-related issues).

Dynamic binding (and threads) in OCaml

This thread started with OCaml; so it ought to finish likewise. The
following link describes the dynamic binding library in Ocaml


http://caml.inria.fr/pub/ml-archives/caml-list/2006/04/74eefb9afe6aba40ff249e2aa2e1727d.en.html

The validation code pointed to in the library contains the thread
example of the previous message, now in OCaml.

mzscheme parameters

Dynamic binding is used in PLT Scheme quite effectively, but there are indeed some subtleties. PLT Scheme has several kinds of implicit parameters: thread cells, preserved thread cells, and parameters. Jacob Matthews has blogged about the difference between thread cells and parameters. The question is whether or not throwing to a continuation captured in a different thread should restore the previous value of a dynamic binding. There are use cases for both behaviors.

Another useful feature of mzscheme's implicit parameters is their control space behavior in tail position. Thanks to continuation marks, the syntactic form for dynamically binding a parameter's value (parameterize) preserves tail position for the body of the syntactic form. This may seem counterintuitive, since resetting the binding seems to be a necessary "after" operation to be performed when the body finishes evaluating. But parameter values are associated with continuation frames via continuation marks, and consequently when the body is in tail position, its continuation frame is automatically removed, effectively resetting the dynamic binding without requiring any extra information about the reset to be pushed on the continuation.

also

Let me clarify my last sentence above. There are two aspects of continuation marks that allow parameterize to retain tail position. First, as I said above, the dynamic binding is associated with the continuation frame as a mark so it gets automatically uninstalled with the continuation frame. Second, when one parameterize occurs in tail position of another for the same parameter, it overwrites the previous value, because that previous value is no longer reachable.

Also, How to add threads to a sequential language without getting tangled up seems pertinent to this topic, though I haven't read it. It's in my printer now...