Hi all,
For much of the last year I have been looking at the question of implementing a domain-specific language for nondeterministic (probabilistic and possibilistic) computation in Scala. The best prior work I found of this kind was Oleg Kiselyov's Hansei language embedded in ocaml which he builds atop his delimcc library. His work bottoms out in the scAPI he defines for supporting delimited control operators. He describes his work in detail
here and the implementation details including scAPI
here. The serializability of continuations he has included is also interesting to me for the usual reasons including being able to easily parallelize in distributed fashion the inference I seek to do and move the computations to the data easily, and meanwhile Ian Clarke in his (recently active again)
Swarm project is pursuing this in Scala by hacking around some of the limitations of the Scala standard library continuations.
In order to be able to implement the DSL for nondeterministic computation in Scala I have been looking at existing work on continuations in the JVM with the intention of finding a way to implement scAPI in the JVM and have contacted several users and implementers of similar things and encountered Kilim, JavaFlow, Rife, Mono's continuation extension to the CLR, and many other less immediately relevant things, and I am trying to use that information to come up with a viable strategy. I found that the Scala standard library's delimited continuations are
based on a CPS-transform technique first prototyped in Scheme which
breaks higher-order functions and thus much of collections (which Clarke is now hacking around) and other
common Scala idioms. The technically preferred way forward seems to me to be to ask for the continuation work in the JVM Da Vinci project to move forward by implementing scAPI on threads, modifying the VM as needed similarly to what Mono did. This seems promising because the delimited nature of the stack manipulation in scAPI seems to resolve security and ergonomics concerns with nondelimited continuations that seem to be holding up implementation of this feature for the JVM. The bug for that is
here.
I was advised that this is a long and difficult path to pursue so in the meantime I am trying to figure out if an equivalent, even if less performant, thing can be done using bytecode-munging techniques. To that end I would like to ask here whether the scAPI seems reasonably implementable this way. Quoting Kiselyov's description of it from his caml-shift.pdf: “On one hand, the machine is a standard stack machine: D is a sequence of activation frames, the ‘stack’; the first six transitions look like a function call, pushing a new activation frame onto the stack. The last-but-one transition corresponds to the return from a function call, popping a single frame off the top of the stack and passing the return value to it. The machine also exhibits non-standard stack-manipulation operations: D[D] in the pushSC transition pushes several frames D at once onto the stack; the takeSC transition involves locating a particular frame pushP pD1 and splitting the stack at that frame. The removed prefix D1 is passed as a value to the argument of takeSC; in a real machine, the stack prefix D1 would be copied onto heap, the ordinary place for storing composite values. These non-standard stack operations (called in §4.2 as push_stack_fragment for pushing several frames, get_ek and reset_ek for locating a frame and splitting the stack, and copy_stack_fragment for copying the stack prefix) thus constitute an API, which we call scAPI, for implementing multi-prompt delimited control.”
All advice will be much appreciated.
Anthony