[e-lang] Orc in E with a first working test case

[Mark S. Miller]

On Wednesday I heard a wonderful talk by Pref. Jay Misra on his new Orc
language.
     http://www.cs.utexas.edu/users/wcook/papers/OrcJSSM05/OrcJSSM.pdf
     http://www.cs.utexas.edu/users/wcook/projects/orc/
     http://www.stanford.edu/class/ee380/Abstracts/061025-slides.pdf
I invited him to give the talk again at HP Labs, which he did. Many of the 
local capabilities crowd attended, and we had a lively discussion.

Orc has many of the same goals as some of our systems (Joule, E, Joe-E + 
Waterken, etc...). Its emphasis is on the distributed concurrency control side 
of things. I was simply amazed at its combination of expressiveness and 
simplicity. Although Orc resembles other process algebra systems, as far as I 
could tell, it does not make unreasonable assumptions about what's 
implementable. It also looks to me like a much easier system to teach, learn, 
and use.

Below is a draft implementation of Orc as I currently understand it in E,
followed by a first working test case based on Dr. Misra's first example.

------------------------------------------------------------------------------
# Copyright 2006 Hewlett-Packard, Inc. under the terms of the MIT X license
# found at http://www.opensource.org/licenses/mit-license.html ...............

pragma.syntax("experimental")

def promiseAllResolved := <elang:interp.promiseAllResolved>

def [never,_] := Ref.promise()

def orc {

     ########################### orc syntactic primitives ####################

     /**
      * orc`@site(@args*)` => e`orc.call($site, [$args*])
      * <p>
      * We assume that a nullary call to a site is written as
      * orc`@site()`, so that we may interpret orc`@site` as
      * an expression whose value is the channel to that site,
      * rather than a call on that channel.
      */
     to call(site, args) {
         def callAgent(term, chan) {
             if (!Ref.isResolved(term)) {
                 when (promiseAllResolved(args)) -> {
                     def result := E.send(site, "run", args)
                     when (result) -> {
                         chan <- publish(result)
                     }
                 }
             }
         }
         return callAgent
     }

     /** orc`@left | @right` => e`orc.par($left, $right)` */
     to par(leftAgent, rightAgent) {
         def parAgent(term, chan) {
             if (!Ref.isResolved(term)) {
                 leftAgent <- run(term, chan)
                 rightAgent <- run(term, chan)
             }
         }
         return parAgent
     }

     /**
      * orc`@left >@x> @right` => e`orc.pipe($left, fn $x{$right})`
      * orc`@left >> @right` => e`orc.pipe($left, fn _{$right})`
      */
     to pipe(leftAgent, rightAgentFn) {
         def pipeAgent(term, chan) {
             def rightChan {
                 to publish(val) {
                     if (!Ref.isResolved(term)) {
                         rightAgentFn <- run(val) <- run(term, chan)
                     }
                 }
             }
             leftAgent <- run(term, rightChan)
         }
         return pipeAgent
     }

     /**
      * orc`@left where @x:elem-of @right` =>
      *   e`orc.where(fn $x{$left}, $right)`
      */
     to where(leftAgentFn, rightAgent) {
         def whereAgent(term, chan) {
             def [x,xR] := Ref.promise()
             leftAgentFn <- run(x) <- run(term, chan)
             def [rightTerm,rightTermR] := Ref.promise()
             def leftChan {
                 to publish(val) {
                     if (!Ref.isResolved(term)) {
                         xR.resolveRace(val)
                         rightTermR.resolveRace(null)
                     }
                 }
             }
             when (term) -> { rightTermR.resolveRace(null) }
             rightAgent <- run(rightTerm, leftChan)
         }
         return whereAgent
     }

     ################## primitive Orc command line interpreter ##############

     /**
      * To run an orc expression as a command, do
      * <pre>    orc.go(currentVat, agentExpr)</pre>
      * where agentExpr is the translation of the orc syntactic primitives
      * into E agent creation calls listed above.
      * This returns a promise for the results published by this agent by the
      * time the local vat quiesces.
      */
     to go(currentVat, agent) {
         var results := []
         def goChan {
             to publish(val) {
                 results with= val
             }
         }
         # XXX A more realistic command line interpreter would provide the
         # caller a way to resolve the term argument, in order to stop the
         # command.
         agent(never, goChan)
         def getResults() {
             if (currentVat.isQuiescent()) {
                 return results
             } else {
                 return getResults <- run()
             }
         }
         return getResults <- run()
     }

     ####################### built in sites ########################

     /** orc`0` (bold, not number) => e`orc.zero` */
     to zero() { return never }

     /** orc`if` => e`orc.test` */
     to test(cond) { return if (cond) { null } else { never } }

     /** orc`Signal` => e`orc.signal` */
     to signal() { return orc.test(true) }

     /**
      * orc`Rtimer` => e`orc.makeRtimer(timer)`
      * <p>
      * Note that the E expansion references "timer", which is bound in the
      * privilegedScope but not in the safeScope. The binding for timer must be
      * provided by other means, as is necessary, since it represents a source
      * of authority.
      */
     to makeRtimer(timer) {
         def rtimer(t) {
             return timer.whenPast(timer.now() + t,
                                   fn{orc.signal()})
         }
         return rtimer
     }

     /**
      * orc`let` => e`orc`
      * <p>
      * In order to simulate the ML-like tuple, which Orc demands, this method
      * will pick up the 1-arity case, yielding just the value, while the
      * match clause will pick up the remaining cases, returning a list of
      * values.
      */
     to run(val) { return val }

     match [`run`, args] { args }
}


# rune(["~/e/src/esrc/scripts/updoc.e", "~/e/src/esrc/com/hp/orc/orc.emaker"])
? def orc := <import:com.hp.orc.orc>
? pragma.syntax("experimental")

? def CNN() { return "US News" }
# value: <CNN>

? def BBC() { return "UK News" }
# value: <BBC>

? def newsAgent := orc.par(orc.call(CNN, []), orc.call(BBC, []))
# value: <parAgent>

? def printNewsAgent := orc.pipe(newsAgent, fn m { orc.call(println, [m]) })
# value: <pipeAgent>

? def results := orc.go(currentVat, printNewsAgent)
? interp.waitAtTop(results)
? results
# stdout: US News
#         UK News
#

# value: [null, null]