Implement n-ary handlers

[dhil]

The task is to implement shallow n-ary handlers (also called multi handlers), as found in Frank, and deep n-ary handlers with my generalised semantics, that let multi handlers simulate parameterised handlers efficiently. As a result, I can remove the special implementation of parameterised handlers.

[dhil]

In order to implement n-ary handlers, I first need to come up with a syntax for operation patterns. My current idea is to support something along the lines of

handle(do Foo, { var z = do Bar; do Bar + z }) {
  case (x,y) -> x + y # value (or return) case
  case (<Foo>, <Bar>) => resume -> resume(36, 2) # operation case
  case (x, <Bar>) => resume -> resume(x, 4)  # value and operation case
  case (<Foo>, y) => resume -> resume(0, y) # operation and value case
}

which would evaluate to 42.

The pipe example could be implemented as follows

# The deep pipe handler
fun deepPipe(prod, cons) {
  handle(cons(), prod()) {
    case (x, _) -> x
    case (x, <Send(_)>) -> x # technically a shallow clause.
    case (<Await>, <Send(x)>) => resume -> resume(x, ())
    case (<Await>, _) -> error("the producer has finished.") # technically a shallow clause.
  }
}

# The shallow pipe handler.
fun shallowPipe(prod, cons) {
   handle(cons(), prod()) {
      case (x, _) -> x
      case (x, <Send(_)>) -> x
      case (<Await -> r>, <Send(x) -> c>) -> shallowPipe(fun() {r(x)}, fun() {c(())})
      case (<Await>, _) -> error("the producer has finished")
   }
}

Some fiddling with the lexer seems inevitable to support < and > in operation patterns.

[dhil]

@SquidDev this is the pipes examples with multiple inputs, that I mentioned. It makes use of ability to capture the resumption shallowly and deeply.

# Pipes with multiple inputs.
sig yield : (a) {Yield: (a) -> ()|_}-> ()
fun yield(x) {do Yield(x)}

sig await : () {Await:a |_}-> a
fun await() {do Await}

sig multiPipe : ([Comp({Yield:(a) -> (), Await{ap} |e}, _)]
                , Comp({Await:a, Yield{yp} |e}, b)) {Await{ap}, Yield{yp} |e}~> b
fun multiPipe(sources, sink) {
  switch (sources) {
    case [] -> error("sources exhausted.")
    case source :: sources ->
      handle(sink(), source()) {
        case (x, _) -> x
        case (x, <Yield(_)>) -> x
        case (<Await>, <Yield(x)>) # deep capture
             with resume ->  resume(x, ())
        case (<Await -> r>, _) -> # shallow capture
             multiPipe(sources, fun() { r(await()) })
      }
  }
}

sig sum3 : () {Await:Int |_}-> Int
fun sum3() { await() + await() + await() }

sig yield1 : () {Yield:(Int) -> () |_}-> ()
fun yield1() { yield(1) }

multiPipe([yield1, yield1, yield1], sum3) # returns 3.

[dhil]

Here is an implementation of the above program using unary shallow handlers.

# Pipes with multiple inputs.
sig yield : (a) {Yield: (a) => ()|_}-> ()
fun yield(x) {do Yield(x)}

sig await : () {Await:() => a |_}-> a
fun await() {do Await()}

mutual {
  sig pipe : (() {Await: () => a, Yield{y} |e}~> b, [() {Await{x}, Yield:(a) => () |e}~> ()]) {Await{x}, Yield{y} |e}~> b
  fun pipe(c, ps) {
    shallowhandle(c()) {
       case <Await() => resume> -> copipe(ps, fun(x) { resume(x) })
    }
  }

  sig copipe : ([() {Await{x}, Yield:(a) => () |e}~> ()], (a) {Await: () => a, Yield{y} |e}~> b) {Await{x}, Yield{y} |e}~> b
  fun copipe(ps, c) {
    switch (ps) {
      case [] -> error("sources exhausted.")
      case p :: ps ->
        shallowhandle(p()) {
          case _ -> copipe(ps, c)
          case <Yield(x) => resume> -> pipe(fun () { c(x) }, fun() { resume(()) } :: ps)
        }
    }
  }
}

sig sum3 : () {Await:() => Int |_}-> Int
fun sum3() { await() + await() + await() }

sig yield1 : () {Yield:(Int) => () |_}-> ()
fun yield1() { yield(1) }

pipe(sum3, [yield1, yield1, yield1]) # returns 3.

It uses the state-passing technique to pass around the list of producers (ps). There is no fancy manipulation of the continuations, meaning this program can be efficiently implemented using sheep handlers. It is difficult to implement with deep handlers.