Orc in 15 Minutes

Introduction (top)

In this tutorial you will learn the basic concepts of Orc through a series of interactive examples. When you see a code example with a run button, click it to run the program. The results of the program will be printed below it. The demos run on our server so you may experience some network delay.

Sites (top)

The fundamental unit of computation in an Orc program is called a site. Sites are similar to functions or procedures in other languages, but they may be remote and therefore unreliable. In this tutorial we will make frequent use of a Prompt site, which communicates with you (the user) by sending you a question and returning your response. For example:

Prompt("What is your favorite food?")

Sites needn't always be remote. For example, the + site which is used to add numbers and concatenate strings is usually implemented locally.

1 + 2

Although Orc uses traditional infix notation for arithmetic and comparison operators, these are still considered sites like any other.

Combinators (top)

Orc has four basic combinators, each to combine two expressions:

  • Parallel, written |
  • Sequential, written >>
  • Pruning, written <<
  • Otherwise, written ;

This tutorial covers the first three combinators.

Parallel Combinator (top)

Two Orc expressions can be evaluated in parallel using |. For example, we can ask the user to choose both an eating utensil and type of dinnerware simultaneously:

  Prompt("Spoon or fork?")
| Prompt("Bowl or saucer?")

Note that both of your answers were returned. In Orc, an expression may return more than one value if it involves more than one concurrent computation. To emphasize this we usually say that an expression publishes (rather than returns) values.

Sequential Combinator (top)

Sites can also be called in sequence. The >> combinator evaluates its right side when its left side publishes a value.

Prompt("What was the last movie you saw?")

  >>

Prompt("Was it good?")

Notice that your first response was not published. >> only publishes the value(s) published by the right side. If you want to use a value published by the left side, you can bind it to a variable, like this:

Prompt("What is your name?")

  >name>

"Hello " + name

If the left side publishes more than one value, the right side is evaluated independently for each value:

(   Prompt("Pick a movie you like:")
  | Prompt("Pick a movie you like:") )

  >movie>

"I heard that " + movie + " is a good movie."

The >> combinator has higher precedence than |, so the parentheses in the previous example are necessary.

Pruning Combinator (top)

The final combinator, <<, combines the concepts of selection, blocking, and termination. It is used to select the first value published by an expression and then terminate that expression. The following program, for example, asks two questions but only publishes the first answer (and does not wait for the second):

fruit

  <fruit<

        Prompt("Apples or oranges?")
      | Prompt("Grapes or mangos?")

Both sides of the pruning combinator begin evaluating immediately, but when the left side needs the value produced by the right side, it blocks until that value is available. The next example will print "red" and "blue" immediately but must wait to print your chosen color until you enter it:

"red" | ("light " + color) | "blue"

  <color<

    Prompt("Choose a color.")

The syntax of << can sometimes be awkward, so Orc supports an alternative (but equivalent) syntax that allows you to write the previous example like this:

val color = Prompt("Choose a color.")
"red" | ("light " + color) | "blue"

A variable introduced by a val declaration is scoped to the expression following the declaration.

If an argument to a site call is a compound expression (not just a variable or constant), then it is treated as syntactic sugar for a pruning composition. For example, these two expressions are equivalent:

  ( 1 +    x      <x< (2 + 3) )
| ( 1 + (2 + 3) )

Fundamental Sites (top)

In addition to the Prompt and + sites we have already seen, Orc provides several other fundamental sites which are necessary for writing useful expressions. The following examples illustrate the most important ones.

Ift(condition) publishes a signal (a special value which carries no information) if and only if condition is true:

  Ift(3 /= 4) >> "three does not equal four"
| Ift(false) >> "impossible!"

Rwait(t) publishes a signal after t milliseconds:

  "immediately"
| Rwait(3000) >> "...three seconds later..."
| Rwait(5000) >> "...five seconds later..."

stop is a special expression which never publishes (similar to the concept of "bottom" or ⊥ in functional languages). It is commonly used with sequential composition to suppress published values, as in this example which waits for a response but does not publish it:

Prompt("I'm not listening...") >> stop

Functions (top)

To facilitate the construction of large programs, Orc allows users to define functions. Function calls look and act like site calls, with two key differences:

  1. A site call must block if some of its arguments are not available, but a function call can begin evaluating immediately.
  2. A site call can publish at most one value, but a function call may publish many values.

Here is a simple recursive function which publishes a number every second:

def metronomeN(i) =
    i
  | Rwait(1000) >> metronomeN(i+1)

metronomeN(0)

Function publications can be interleaved with the parallel combinator. For example, we can interleave publications from two metronomes running at different rates and starting at different initial values:

def metronomeTN(t, i) =
    i
  | Rwait(t) >> metronomeTN(t, i+1)

metronomeTN(1100, 0) | metronomeTN(700, 100)

A common idiom in Orc is to treat an expression as a stream of values which may be filtered. The next example publishes every even number starting at 0:

def metronomeN(i) =
    i
  | Rwait(1000) >> metronomeN(i+1)

metronomeN(0) >n> Ift(n%2 = 0) >> n

Advanced Techniques (top)

Orc shares many features with functional programming languages, including higher-order functions (functions which take functions or sites as arguments) and pattern matching. We will explore these features using a simple but realistic example: an automated booking agent which gets quotes from a list of airlines and returns the best quote received under a certain price and within a certain time limit.

First, we must have a way to get a quote from an airline. For the purposes of this demo, we will assume that there exists a discovery site which, given the name of an airline, returns a site representing that airline. When the airline site is called in turn, it will simulate a request for a quote by prompting you for a quote in dollars.

def Airline(name) =
    -- define a local function
    def MakeQuote() =
        Prompt(name + " quote ($)") >n>
        (name, Read(n))
    -- return it
    MakeQuote
{- EXAMPLE -}
-- Request a delta site and then
-- use it to request a quote
Airline("Delta") >delta> delta()

Next we need a utility function which returns the lesser of two quotes. A quote includes the airline name and a dollar value, so we use pattern matching to extract the dollar value from the quote tuple:

def Airline(name) =
    -- define a function which can be called
    -- like a site
    def MakeQuote() =
        Prompt(name + " quote ($)") >n>
        (name, Read(n))
    -- return the site
    MakeQuote

{- EXAMPLE -}
def minQuote((_,dollar1) as quote1, (_,dollar2) as quote2) =
    Ift(dollar1 <= dollar2) >> quote1
  | Ift(dollar2 <: dollar1) >> quote2

-- Example usage
val delta = Airline("Delta")
val united = Airline("United")
minQuote(delta(), united())

Finally we can put everything together with a function that uses pattern matching and recursion to return the best quote from a list of airline sites:

def Airline(name) =
    -- define a function which can be called
    -- like a site
    def MakeQuote() =
        Prompt(name + " quote ($)") >n>
        (name, Read(n))
    -- return the site
    MakeQuote
def minQuote((n1,q1), (n2,q2)) =
    Ift(q1 <= q2) >> (n1, q1)
  | Ift(q2 <: q1) >> (n2, q2)

{- EXAMPLE -}
-- Return the best quote at or under $200
-- received within 15 seconds
def bestQuote([]) = ("None of the above", 200)
def bestQuote(airline:rest) =
    val best = bestQuote(rest)
    val current = airline() | (Rwait(15000) >> best)
    minQuote(current, best)

bestQuote([Airline("Delta"), Airline("United")])

Conclusion (top)

That concludes this Orc tutorial. Please refer to the Documentation page for further guidance. When you are ready, play with Orc yourself.

Get Started

Get Involved

Contact Us

Supporting Agencies

This research is supported in part by funding from the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed on this website are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Last updated 2013-09-20