I’ll return your call later

It was a while ago when I came across the paper a technique for implementing first-class continuations in languages that do not support stack manipulation and inspection. The technique is rather clever, using a source to source transformation to produce a set of functions which can use exception handling and chaining to capture the active stack frames. These frames can then be restarted at a later stage. The technique has been tried out in various implementations of Scheme.
 
The web page mentioned above details an implementation in C#. However, I think that the verbosity of the C# implementation hides some of the essential details and therefore want to walk through an example using F# as the implementation language. I should point out that we need to use the obj (System.Object) type in some places so we don’t gain all of the benefits of the type checking that F# carries out. However, the conciseness of the implementation more than makes up for this.
 
We need an example function to work through. Having been recently reminded of the classic co-routine example of matching the fringes of two trees, we’ll work on an implementation of a function which takes a tree and returns an element from the fringe together with a continuation which will return the next element.
type ‘a Tree =
  | Leaf of ‘a
  | Node of ‘a Tree * ‘a Tree
 
let rec getNext tree =
  match tree with
  | Leaf x -> callcc (fun k -> Some(x, k))
  | Node (l,r) ->
      match getNext l with
      | Some _ as result -> result
      | None -> getNext r
 
The idea is that we’ll define a suitable callcc, which stands for call with current continuation. If we called this function on Node(Leaf(1), Leaf(2)) we’d expect to get back a pair of 1 and a continuation. We could then pass None into this continuation to get the next result which would be a pair of 2 and another continuation.
 
The first step in the source to source conversion is to introduce temporaries
let rec getNext_an tree =
  match tree with
  | Leaf x -> callcc (fun k -> Some(x, k))
  | Node (l,r) ->
    let temp0 = getNext_an l
    match temp0 with
    | Some _ as result -> result
    | None -> getNext_an r
 
and then to convert into tail recursive functions
let rec getNext_0 tree =
  match tree with
  | Leaf x -> callcc (fun k -> Some(x,k))
  | Node (l,r) ->
    let temp0 = getNext_0 l
    getNext_1 (temp0, r)
   
and getNext_1 (temp0, r) =
  match temp0 with
  | Some _ as result -> result
  | None -> getNext_0 r
 
We can now start defining some of the machinary.  The representation of a continuation frame which supports on Invoke function to invoke the continuation. This object contains a list of frames further down the stack, allowing these frames to be shared if the continuation is captured again.
 
[<AbstractClass>]
type ContinuationFrame() =
  let mutable continuation : ContinuationFrame list = []
  member v.Continuation with get() = continuation and set(value) = continuation <- value
  abstract member Invoke : obj -> obj
 
We now define the exception which will be passed up the stack. It will accumulate the frames as we go.
  
type ContinuationData() =
  let mutable new_frames: ContinuationFrame list = []
  let mutable old_frames : ContinuationFrame list = []
  member a.NewFrames with get() = new_frames and set(v) = new_frames <- v
  member b.OldFrames with get() = old_frames and set(w) = old_frames <- w
 
exception SaveContinuation of ContinuationData
 
We can extend the continuation frame type with a Reload method which will be used for rebuilding the stack. Type extension in F# is great for doing this.
 
type ContinuationFrame with
  member v.Reload(frames_above : ContinuationFrame list, restart_value) =
    let continue_value =
      if frames_above = []
      then restart_value
      else List.hd(frames_above).Reload(List.tl frames_above, restart_value)
    try
      v.Invoke(continue_value)
    with
       SaveContinuation data as ex ->
         data.OldFrames <- v.Continuation
         raise ex
        
We can now define a type representing a continuation.
type Continuation(new_frames, old_frames) =
  let mutable frames = []
  let mutable new_frames_mutable = new_frames
  do frames <- old_frames
  do while (new_frames_mutable <> []) do
       let new_frame : ContinuationFrame = List.hd new_frames_mutable
       new_frames_mutable <- List.tl new_frames_mutable
       new_frame.Continuation <- frames
       frames <- new_frame :: frames
  member v.Frames () = frames
  member v.Reload (restart_value) =
    let rev = List.rev frames
    List.hd(rev).Reload(List.tl rev, restart_value)
 
And the structures needed for getting the continuation capture started. We’ll need to run all computation inside the thunk of EstablishInitialContinuation. This function adds an initial exception handler onto the stack which can capture the exception which is accumulating the stack frames, and which can then reset the stack and continue.
type CWCC_frame0 (receiver : Continuation -> obj) =
  inherit ContinuationFrame()
  override v.Invoke return_value =
    let asCont = (return_value :?> Continuation)
    receiver (Continuation(List.rev(List.tl(asCont.Frames())),[]))
 
let BeginUnwind() =
  raise (SaveContinuation(ContinuationData()))
 
let CWCC receiver =
    try
      BeginUnwind()
    with
      SaveContinuation data as ex ->
        data.NewFrames <- (CWCC_frame0(receiver) :> ContinuationFrame) :: data.NewFrames
        raise ex
 
exception WithInitialContinuation of (unit -> obj)
 
let InitialContinuationAux thunk =
  try
    thunk()
  with
      SaveContinuation data as ex ->
        let k = Continuation(data.NewFrames, data.OldFrames)
        raise (WithInitialContinuation(fun () -> k.Reload(k)))
 
let EstablishInitialContinuation th =
  let mutable thunk = th
  let mutable again = true
  let mutable result = 0 :> obj
  while again do
    again <- false
    try
      result <- InitialContinuationAux thunk
    with
      WithInitialContinuation new_thunk ->
        thunk <- new_thunk
        again <- true
  result
 
For our example function, we now need to define some specialized frames, and we need to capture the relevant exceptions in the body of the function.
 
type GetNext_f0<‘a>(r : ‘a Tree, f : (‘a * Continuation) option * ‘a Tree -> (‘a * Continuation) option)  =
  inherit ContinuationFrame()
  override v.Invoke continue_value =
      let value = ((box continue_value) :?> (‘a * Continuation) option)
      f(value, r) :> obj
 
let rec getNext_e0 tree  =
  match tree with
  | Leaf x ->
      CWCC (fun k -> Some(x,k) :>obj)
  | Node (l,r) ->
    let mutable temp0 = None
    try
      temp0 <- getNext_e0 l
    with
      SaveContinuation data as ex ->
        data.NewFrames <- (GetNext_f0(r, getNext_e1) :> ContinuationFrame) :: data.NewFrames
        raise ex
    getNext_e1 (temp0, r)
   
and getNext_e1 (temp0, r) =
  match temp0 with
  | Some _ as result ->
      result
  | None ->
      getNext_e0 r
 
We can now take an example tree.
 
let tree = Node(Leaf(0), Node(Node(Leaf 1, Leaf 2), Leaf 3))
 
And get the first result.
 
let res0 = EstablishInitialContinuation (fun () -> getNext_e0 tree :> obj)
 
We can now get hold of the continuation, and return None from it. This will cause the code to find the next element of the fringe.
let cont0 = (fun (Some (_,x)) -> x) (res0 :?> (int * Continuation) option)
let res1 = EstablishInitialContinuation(fun () -> cont0.Reload(None));;
 
We can then do this several more times.
 
let cont1 = (fun (Some (_,x)) -> x) (res1 :?> (int * Continuation) option)
let res2 = EstablishInitialContinuation(fun () -> cont1.Reload(None));;
let cont2 = (fun (Some (_,x)) -> x) (res2 :?> (int * Continuation) option)
let res3 = EstablishInitialContinuation(fun () -> cont2.Reload(None));;
let cont3 = (fun (Some (_,x)) -> x) (res3 :?> (int * Continuation) option)
 
The web page goes into the details of each of the classes and functions.
 
As a quick aside, it is really neat that F# now comes as part of the beta for Visual Studio 2010, making it feel like a first class .NET language.
 
Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s