Fwd: [Design] Orc in E with a first working test case

[Kragen Javier Sitaker]

This sounds like an interesting and potentially important approach to
concurrency.

Message-ID: <[EMAIL PROTECTED]>
Date: Fri, 27 Oct 2006 20:15:54 -0700
From: "Mark S. Miller" <[EMAIL PROTECTED]>
To: Discussion of E and other capability languages <[EMAIL PROTECTED]>

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 ####################

    /**
     * [EMAIL PROTECTED](@args*)` => e`orc.call($site, [$args*])
     * <p>
     * We assume that a nullary call to a site is written as
     * [EMAIL PROTECTED]()`, so that we may interpret [EMAIL PROTECTED] 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
    }

    /** [EMAIL PROTECTED] | @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
    }

    /**
     * [EMAIL PROTECTED] >@x> @right` => e`orc.pipe($left, fn $x{$right})`
     * [EMAIL PROTECTED] >> @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
    }

    /**
     * [EMAIL PROTECTED] 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]