openlang

Converting functions into continuations for deep handlers

In the documentation's deep-handler example, there's this paragraph:

A computation f can itself perform effects. When f performs Yield, its task is paused and placed in the ready-task queue, then the scheduler runs the next queued task. When the effect is Fork f, it pauses the current task and immediately runs the new task f by tail-calling spawn f. Note that picking the new task to run first is an arbitrary decision. Another possible choice would put f's task into the ready queue and immediately continue k instead.

Perhaps I'm overlooking something simple, but consider this scheduler example:

type _ Effect.t += Fork : (unit -> unit) -> unit t
                 | Yield : unit t

(* Round-robin scheduling with concurrency *)
let run (entry : unit -> unit) : unit =
  let pending : (int * (int, unit) continuation) option ref =
    ref None (* exchanger awaiting a partner *)
  in
  let ready = Queue.create () in (* ready-task queue *)
  let schedule cont arg =
    let resume () = continue cont arg in
    Queue.push
      resume ready
  in
  let next () =
    if Queue.is_empty ready then () (* finished *)
    else begin
      let resume = Queue.pop ready in
      resume ()
    end
  in
  let rec start (work : unit -> unit) : unit =
    match work () with
    | () -> next ()
    | exception err ->
        print_endline (Printexc.to_string err);
        next ()
    | effect Yield, cont -> schedule cont (); next ()
    (* How can work be queued at this point? *)
    | effect (Fork work), cont -> schedule cont (); start work
    | effect (Xchg value), cont ->
        begin match !pending with
        | Some (other, saved) -> pending := None; schedule saved value; continue cont other
        | None -> pending := Some (value, cont); next ()
        end
  in
  start entry

What would put work onto ready?

The conversation continues 3

Follow the reasoning
  1. Permalink

    It seems you can skip the schedule helper and manipulate ready itself instead.

    Rather than writing

        | effect (Fork work), cont -> schedule cont (); start work

    swap the order with the following:

        | effect (Fork work), cont -> Queue.push (fun () -> start work) ready; continue cont ()
  2. Permalink

    Although this version apparently needs the start function to wrap it, because when work is called from within the handler it isn't surrounded by that handler itself. Do you have any thoughts on whether that is necessary, since otherwise the result feels rather asymmetric compared with the example's scheduler? I was merely wondering whether there's a reason Effect.Deep lacks a primitive comparable to Effect.Shallow's fiber.

Other sides of the same question

  1. Please review my go pipeline implementation (still learning the language)

    Hello Everybody, I am learning go and its concurrency features, and “pipeline” is one of the usual patterns. Here's my versio…

    Replies 3Latest activity go