From oleg-at-okmij.org Mon Apr 10 18:25:29 2006
To: caml-list@inria.fr
Subject: ANN: Dynamic binding library
From: oleg-at-pobox.com
Message-ID: <20060411012529.5B1F5AC2A@Adric.metnet.navy.mil>
Date: Mon, 10 Apr 2006 18:25:29 -0700 (PDT)
Status: OR


Dynamic binding adds expressiveness; as Luc Moreau emphasized, it is,
when used in moderation, quite useful: for parameterizing a function
deep in the code without changing the interface of all callers; for
propagating the environment information like the current working
directory, printing-depth, etc.  Dynamic binding is inescapable in
mobile code or continuation-based web servers. Dynamic binding, in
some restricted form, is already present in OCaml: exception handlers
are dynamically bound by the 'handle' form. This message announces the
availability of general dynamic binding. This is joint work with
Chung-chieh Shan and Amr Sabry.

Dynamic binding is implemented as a regular library (dependent on the
delimited continuations library announced earlier on this list).  No
changes to the OCaml system and no code transformations are required;
(parts of the) code that do not use dynamic variables incur no
overhead and run at the same speed as before. Here's the interface:

type 'a dynvar
val dnew : unit -> 'a dynvar

   Given a dynvar, a value and a thunk, evaluate the thunk in the dynamic
   environment extended with the binding of the given value to the
   given dynvar
val dlet : 'a dynvar -> 'a -> (unit -> 'w) -> 'w

   Dereferencing: obtain the value associated with the dynvar
   by the closest dynamically-enclosing dlet
val dref : 'a dynvar -> 'a

   Mutation: obtain the current value of the dynvar and change that
   value to the given one. This `mutation' has the effect only
   within the dynamic scope of the latest dlet
val dset : 'a dynvar -> 'a -> 'a

   Given a dynvar and a function, apply the function to the current
   value of the dynvar, and return the result. The application
   is evaluated in the dynamic environment _outside_ of the
   closest dynamically-enclosing dlet.
val dupp : 'a dynvar -> ('a -> 'w) -> 'w


Our dynamic variables are mutable (cf. fluid-variables in many Scheme
systems); mutations however are visible only within the scope of the
dlet statement where they occurred. Here's the simple example

let test12 =
  let p = dnew () in
  dlet p 1 (fun () ->
    let v1 = dref p in
    let v2 = dlet p 2 (fun () ->
      let v3 = dset p 12 in
      let v4 = dref p in
      (v3,v4)) in
    let v5 = dref p in
    (v1,v2,v5))

which yields (1, (2, 12), 1). The function 'dupp' is an extension of
the conventional dynamic binding. It lets us obtain not only the
current binding to the dynamic variable, but any of the previous
bindings as well. In general, we can fold over the execution stack as
if it were a list (please see the 'nub' example in the test code
below).

Because dynamic binding is implemented in terms of delimited
continuations, the two features harmoniously interact. We can use
dynamic variables in shift-based, cooperative threads. At thread
creation time, the user can `designate' some existing dynamic
variables to be private to the thread; the rest are inherited from the
parent. New dynamic variables and new bindings automatically become
thread-private, so the above designation is accomplished with just
dlet.  Mutation and rebinding of private dynamic variables have effect
only in the corresponding thread. Mutations to shared variables are
visible to everyone. Likewise, a re-parameterization of a dynamic
variable in the parent thread is visible in all child threads sharing
that variable. Such partial inheritance of dynamic environment among
threads is an often desired feature; luckily, it is inherent in our
design and thus available `for free'. The end of the test code
vdynvar.ml demonstrates the partial inheritance among the parent and
two cooperatively run threads.

The implementation is surprisingly, short. In particular,

let dref p      = shift p (fun f -> fun v -> f v v)
let dset p newv = shift p (fun f -> fun v -> f v newv)
let dupp p g    = shift p (fun f -> fun y -> f (g y) y)

with dlet taking not much longer.