Orc User Guide v2.1.1

Complex expressions recursively contain other expressions. They may be formed in a number of ways: using one of Orc's four combinators, adding a declaration, adding a conditional expression, or using an expression as an operand or site call argument.

{- Publish 1 and 2 in parallel -}  

1 | 1+1

{-
OUTPUT:PERMUTABLE
1
2
-}

{- Publish 1 and 2 in parallel -}
  
(0 | 1) >n> n+1

{-
OUTPUT:PERMUTABLE
1
2
-}

{- Publish 3 and 4 in parallel -}
  
2 >n> (n+1 | n+2)

{-
OUTPUT:PERMUTABLE
3
4
-}

{- Publish 5 -}
  
2 >x> 3 >y> x+y

{-
OUTPUT:
5
-}

{- Print three messages in sequence -}

Println("Yes") >>
Println("We") >>
Println("Can") >>
stop

{-
OUTPUT:PERMUTABLE
Yes
We
Can
-} 

{- Publish either 5 or 6, but not both -}

x+2 <x< (3 | 4)

{-
OUTPUT:
5
-}
{-
OUTPUT:
6
-}

{- This example might actually print both "uh" and "oh" to the
   console, regardless of which call responds first. -}

stop <x< Println("uh") | Println("oh")

{-
OUTPUT:PERMUTABLE
uh
oh
-}
{-
OUTPUT:
uh
-}
{-
OUTPUT:
oh
-}

{- Publish either 5 or 6 -}

2 + (3 | 4)

{-
OUTPUT:
5
-}
{-
OUTPUT:
6
-}

{- Publish exactly one of 0, 1, 2 or 3 -}

(0 | 2) + (0 | 1)

{-
OUTPUT:
0
-}
{-
OUTPUT:
1
-}
{-
OUTPUT:
2
-}
{-
OUTPUT:
3
-}

Orc supports three basic data structures, tuples, lists, and records. This section describes tuples and lists; records are described in a subsequent chapter.

val z = (3,4)
val (x,y) = z

[1,2,3] >first:_> first

( (0,3) | (1,4) | (2,5) | (0,6) ) >(0,x)> x

Like most other programming languages, Orc provides the capability to define functions, which are expressions that have a defined name, and have some number of parameters. Functions are declared using the keyword def, in the following way:

def add(x,y) = x+y

The expression to the right of the = is called the body of the function. x and y are the parameters. By convention, all function names begin with a lowercase letter.

After defining the function, we can call it. A function call looks just like a site call. To execute a call, we treat it like a sequence of val declarations associating the parameters with the arguments, followed by the body of the function. Every value published by the body expression is published by the call. This is unlike a site call, which publishes at most once.

{- add(1+2, 3+4) is equivalent to: -}

val x = 1+2
val y = 3+4
x+y

{-
OUTPUT:
10
-}

Notice that the execution of a function call can proceed even if some of the arguments haven't published a value yet. The parts of the body that depend on them will simply block.

def demo(x,y) = x | y | x+y
demo(3, Rwait(2000) >> 4)

This call publishes 3 immediately, but blocks for 2 seconds before publishing 4 and 7.

A function definition or call may have zero arguments, in which case we write () for the arguments.

def Zero() = 0

def sumto(n) = if n < 1 then 0 else n + sumto(n-1)

def metronome() = signal | Rwait(1000) >> metronome()

def even(n) = 
  if (n :> 0) then odd(n-1)
  else if (n <: 0) then odd(n+1)
  else true
def odd(n) = 
  if (n :> 0) then even(n-1)
  else if (n <: 0) then even(n+1)
  else false

def sum([]) = 0
def sum(h:t) = h + sum(t)

{- Fibonacci numbers -}
def fib(0) = 1
def fib(1) = 1
def fib(n) = fib(n-1) + fib(n-2)

{- Alternate definition of the Fibonacci function -}

{- A helper function: find the pair (Fibonacci(n), Fibonacci(n+1)) -}
def H(0) = (1,1)
def H(n) = H(n-1) >(x,y)> (y, x+y)

def fib(n) = H(n) >(x,_)> x

def take(0,_) = []
def take(n,h:t) = h:take(n-1, t)

{- Fibonacci numbers -}
def fib(0) = 1
def fib(1) = 1
def fib(n) if (n :> 1) = fib(n-1) + fib(n-2)

def even(n) if (n :> 0) = odd(n-1)
def even(n) if (n <: 0) = odd(n+1)
def even(0) = true 
def odd(n) if (n :> 0) = even(n-1)
def odd(n) if (n <: 0) = even(n+1)
def odd(0) = false

In the Orc programming language, functions are first-class values. This means that a function is treated like any other value; it may be published, passed as an argument to a call, incorporated into a data structure, and so on.

Defining a function creates a special value called a closure. The name of the function is a variable and its bound value is the closure. For example, these function declarations create two closures, bound to the variables a and b, from which we subsequently create a tuple called funs:

def a(x) = x-3
def b(y) = y*4
val funs = (a,b)

A closure can be passed as an argument to another function. A function which accepts functions as arguments is called a higher-order function. Here's an example:

def diff(f) = f(1) - f(0)
def triple(x) = x * 3

diff(triple) {-  equivalent to triple(1) - triple(0)  -}

The use of higher-order functions is common in functional programming. Here is the Orc version of the classic 'map' function:

def map(f, []) = []
def map(f, h:t) = f(h):map(f,t)

Sometimes one would like to create a closure directly, without bothering to give it a name. There is a special keyword lambda for this purpose. By writing a function definition without the keyword def and replacing the function name with the keyword lambda, that definition becomes an expression which evaluates to a closure.

def diff(f) = f(1) - f(0)


diff( lambda(x) = x * 3 )
{- 
  this is identical to:
  
  def triple(x) = x * 3
  diff(triple)
-}

In many object-oriented programming languages, one calls a method or accesses a field of an object using the dot operator; for example, obj.m() calls the method m of the object obj.

There is a special kind of site call in Orc which serves a similar purpose. One may write x.msg, for any identifiers x and msg. This treats the value bound to x as a site, and calls it with a special message value msg. If the site understands the message msg (for example, if x is bound to a Java object with a field called msg), the site interprets the message and responds with some appropriate value. If the site does not understand the message sent to it, it does not respond, and no publication occurs. If x cannot be interpreted as a site, no call is made.

Typically this capability is used so that sites may be syntactically treated like objects, with multiple methods and fields. For example, a channel c might understand the messages get and put, to get values from and put values on that channel, respectively. Such calls would be written c.get(), or c.put(6).

A call such as c.put(6) actually occurs in two steps. First c.put sends the message put to the site c; this publishes a site whose only purpose is to put values on the channel. Next, that site is called on the argument 6, sending 6 on the channel. Readers familiar with functional programming will recognize this technique as currying.

In addition to tuples and lists, the Orc language has a third native data structure, called a record.

A record expression is a comma-separated sequence of elements of the form k = E, enclosed by record braces {. and .}, where each k is an identifier called a key, and each E is an expression. Records may have any number of fields, including zero. Each expression is executed and its first published value is taken; the value of the whole record expression is a record containing a pairing of each key with its associated value. Order is irrelevant. If any of the expressions are silent, then the whole record expression is silent.

Elements of records are accessed using the dot (.) syntax described earlier. The expression r.k publishes the value paired with key k in record r. If k is not present in r, the expression is silent.

Suppose r = {. x = 0, y = 1 .}

Like tuples and lists, records can also be matched by a pattern. However, unlike other patterns, a record pattern does not need to name all of the keys in the record being matched; it only needs to match a subset.

Suppose r = {. x = 0, y = 1, z = 2 .}

Orc has a special declaration, def class, which allows a site to be written in Orc itself. This is a convenient mechanism for writing sites whose internal behavior is best expressed by an orchestration, which might be an awkward task in Java, Scala, or other similar languages.

A def class resembles a def in its syntax, but not in its behavior. The site defined by def class is a factory which creates instances of the class. Each def within the body of the def class becomes a method of an instance. The scope expression of these declarations becomes the internal computation of the instance; it begins to run when the instance is created, and cannot be killed by the Orc program, exactly as if it were a computation of an external service.

The following two examples demonstrate some of the behavior of def class. For a more comprehensive explanation of def class and its features, see the Reference Manual.

def class Stack() =
  {- The stack is initially empty -}
  val store = Ref([])

  def push(x) = 
    store? >xs> 
    store := x:xs

  {- Note that popping an empty stack simply halts, with no effect -}
  def pop() = 
    store? >h:t> 
    store := t >> 
    h

  {- A stack instance has no ongoing computation -}
  stop


{- Test the stack -}
val st = Stack()
st.push(3) >> st.push(5) >> st.pop() >> st.pop()

{-
OUTPUT:
3
-}

def class Multicast(source) =
  val listeners = Ref([])

  def addListener(f) = 
    listeners? >fs> 
    listeners := f:fs

  {- The ongoing computation of a multicast -}
  repeat(source) >item> each(listeners?) >sink> sink(item)



{- Test the multicast -}

val c = Channel()
val mcast = Multicast(c.get)
val listenerA = Channel()
val listenerB = Channel()

{- At n seconds, broadcast n. Stop at 9 seconds. -} 
  upto(10) >i> Rwait(1000*i) >> c.put(i) >> stop

{- Listener A joins at 1.5 seconds, hearing 2..9 -}
| Rwait(1500) >> mcast.addListener(listenerA.put) >> stop

{- Listener B joins at 6.5 seconds, hearing 7..9 -}
| Rwait(6500) >> mcast.addListener(listenerB.put) >> stop

{- Publish everything that Listener A hears -}
| repeat(listenerA.get) >a> ("A", a)

{- Publish everything that Listener B hears -}
| repeat(listenerB.get) >b> ("B", b)

{- Shortly after 10 seconds, close down the channels -}
| Rwait(10500) >> 
    listenerA.close() >> 
    listenerB.close() >> 
    c.close() >>
    stop


{-
OUTPUT:PERMUTABLE
("A", 2)
("A", 3)
("A", 4)
("A", 5)
("A", 6)
("A", 7)
("B", 7)
("A", 8)
("B", 8)
("A", 9)
("B", 9)
-}

We have seen Orc's predefined data structures: tuples, lists, and records. Orc also provides the capability for programmers to define their own data structures, using a feature adopted from the ML/Haskell language family called datatypes (also called variants or tagged sums).

Datatypes are defined using the type declaration:

type Tree = Node(_,_,_) | Empty()

This declaration defines two new sites named Node and Empty. Node takes three arguments, and publishes a tagged value wrapping those arguments. Empty takes no arguments and does the same.

Once we have created these tagged values, we use a new pattern called a datatype pattern to match them and unwrap the arguments:

type Tree = Node(_,_,_) | Empty()
{- Build up a small binary tree -}
val l = Node(Empty(), 0, Empty())
val r = Node(Empty(), 2, Empty())
val t = Node(l,1,r)

{- And then match it to extract its contents -}
t >Node(l,j,r)>
l >Node(_,i,_)>
r >Node(_,k,_)>
( i | j | k )

{-
OUTPUT:PERMUTABLE
0
1
2
-}

One pair of datatypes is so commonly used that it is already predefined in the standard library: Some(_) and None(). These are used as return values for calls that need to distinguish between successfully returning a value (Some(v)), and successfully completing but having no meaningful value to return (None()). For example, a lookup function might return Some(result) if it found a result, or return None() if it successfully performed the lookup but found no suitable result.

While the Orc language itself is expressive, and the Standard Library offers a number of useful sites and functions, it is often necessary to extend the capabilities of a program by writing new sites, using existing Java or Scala code, or making use of Orc code written by other programmers. Orc has three declarations, one corresponding to each of these three use cases.

import site Example = "my.example.site.ExampleSite"

import class File = "java.io.File"
import class FileReader = "java.io.FileReader"
import class BufferedReader = "java.io.BufferedReader"
val f = File("example.txt")
val reader = BufferedReader(FileReader(f))
reader.readLine()

{- Retrieve an include file from the Orc website and print the example message declared there -}

include "http://orc.csres.utexas.edu/documentation/example.inc"
Println(example_message)

By default, Orc behaves as an untyped language. However, there is an optional static typechecker built into Orc, and an accompanying set of typed syntax and type annotations to support static typechecking. It can be enabled within the Orc Eclipse plugin, or via a command-line switch. The typechecker assures, up to the limitations of its algorithm, that no type errors will occur when the program is run. This is a useful sanity check on a program, making it easier to catch bugs early, or rule out certain causes for existing bugs. In some cases, it also speeds up program development.

A full description of the Orc typechecker is available in the Reference Manual. The reference manual section for each language feature describes how that feature interacts with the typechecker.

It is beyond the scope of this document to give a full tutorial on static type checking. However, we will briefly introduce the core concepts and describe the typical approach to using the type checker on an existing Orc program with no type information.

val pi = 3.141592653
val radius = 7
val area = pi * radius * radius

Println("Area: " + area)

val pi = 3.141592653
val radius = 7
val area = "pi" * radius * radius  {- type error -}

Println("Area: " + area)

val pi = 3.141592653
val radius = 7
val area = pi * radius * radius  

Println("Area ": area)   {- type error -}

{- Orc -}
def square(x :: Integer) = x * x

/* Scala */
def circleArea(x: int) = x * x

/* Java */
public int circleArea(int x) { return x * x; }

def metronome() :: Signal = signal | Rwait(1000) >> metronome()

def sum(List[Number]) :: Number  {-  a signature for 'sum' -}
def sum([]) = 0
def sum(h:t) = h + sum(t) 

def append[X](List[X], List[X]) :: List[X]  {- Note the use of a type variable, X -}
def append([], l) = l
def append(h:t, l) = h:append(t,l)

val a = [1,2,3]
val b = [4,5]
append(a,b)

val a = [1,2,3]
val b = [4,5]
append[Integer](a,b)

{- Fails to typecheck -}
val c = Channel()
c.put(7)

{- Typechecks -}
val c = Channel[Integer]()
c.put(7)

LinkedList<Integer> l = new LinkedList<Integer>();

When the expressions to be combined are small, write them all on one line.

F | G | H

When the combined expressions are large enough to take up a full line, write one expression per line, with each subsequent expression aligned with the first and preceded by |. Indent the first expression to improve readability.

  long expression 
| long expression
| long expression

A sequence of parallel expressions often form the left hand side of a sequential combinator. Since the sequential combinator has higher precedence, use parentheses to group the combined parallel expressions together.

( expression 
| expression
) >x> 
another expression

When the expressions to be combined are small, write a cascade of sequential combinators all on the same line.

F >x> G >y> H

When the expressions to be combined are individually long enough to take up a full line, write one expression per line; each line ends with the combinator which binds the publications produced by that line.

long expression  >x>  
long expression  >y> 
long expression

For very long expressions, or expressions that span multiple lines, write the combinators on separate lines, indented, between each expression.

very long expression 
  >x>  
very long expression 
  >y> 
very long expression

When the expressions to be combined are small, write them on the same line:

F <x< G

When multiple pruning combinators are used to bind multiple variables (especially when the scoped expression is long), start each line with a combinator, aligned and indented, and continue with the expression.

long expression 
  <x< G
  <y< H

The pruning combinator is not often written in its explicit form in Orc programs. Instead, the val declaration is often more convenient, since it is semantically equivalent and mentions the variable x before its use in scope, rather than after.

val x = G
val y = H
long expression 

Additionally, when the variable is used in only one place, and the expression is small, it is often easier to use a nested expression. For example,

val x = G
val y = H
M(x,y)

is equivalent to

M(G,H)

Sometimes, we use the pruning combinator simply for its capability to terminate expressions and get a single publication; binding a variable is irrelevant. This is a special case of nested expressions. We use the identity site Let to put the expression in the context of a function call.

For example,

x <x< F | G | H

is equivalent to

Let(F | G | H)

The translation uses a pruning combinator, but we don't need to write the combinator, name an irrelevant variable, or worry about precedence (since the expression is enclosed in parentheses as part of the call).

When the body of a declaration spans multiple lines, start the body on a new line after the = symbol, and indent the entire body.

def f(x,y) =
    declaration
    declaration
    body expression

Apply this style recursively; if a def appears within a def, indent its contents even further.

def f(x,y) =
    declaration
    def helper(z) =
    	declaration in helper
    	declaration in helper
    	body of helper
    declaration
    body expression

def f() =       
  def g() = h
  (x,y)

def f() =      
  val t = h
  (x,y)

def f() =       
  val t = u
  -3

Orc has no communication primitives like pi-calculus channels^[1] or Erlang mailboxes^[2]. Instead, it makes use of sites to create channels of communication.

The most frequently used of these sites is Channel. When called, it publishes a new asynchronous FIFO channel. That channel is a site with two methods: get and put. The call c.get() takes the first value from channel c and publishes it, or blocks waiting for a value if none is available. The call c.put(v) puts v as the last item of c and publishes a signal.

A channel may be closed to indicate that it will not be sent any more values. If the channel c is closed, c.put(v) always halts (without modifying the state of the channel), and c.get() halts once c becomes empty. The channel c may be closed by calling either c.close(), which returns a signal once c becomes empty, or c.closeD(), which returns a signal immediately.

In the introduction to the Orc language, we were introduced to lists: how to construct them, and how to match them against patterns. While it is certainly feasible to write a specific function with an appropriate pattern match every time we want to access a list, it is helpful to have a handful of common operations on lists and reuse them.

One of the most common uses for a list is to send each of its elements through a sequential combinator. Since the list itself is a single value, we want to walk through the list and publish each one of its elements in parallel as a value. The library function each does exactly that.

Suppose we want to send the message invite to each email address in the list inviteList:

each(inviteList) >address> Email(address, invite)

Orc also adopts many of the list idioms of functional programming. The Orc library contains definitions for most of the standard list functions, such as map and fold. Many of the list functions internally take advantage of concurrency to make use of any available parallelism; for example, the map function dispatches all of the mapped calls concurrently, and assembles the result list once they all return using a fork-join.

Sometimes a source of data is not explicitly represented by a list or other data structure. Instead, it is made available through a site, which returns the values one at a time, each time it is called. We call such a site a stream. It is analogous to an iterator in a language like Java. Functions can also be used as streams, though typically they will not be pure functions, and should only return one value. A call to a stream may halt, to indicate that the end of the data has been reached, and no more values will become available. It is often useful to detect the end of a stream using the otherwise combinator.

Streams are common enough in Orc programming that there is a library function to take all of the available publications from a stream; it is called repeat, and it is analogous to each for lists.

def repeat(f) = f() >x> (x | repeat(f))

The repeat function calls the site or function f with no arguments, publishes its return value, and recurses to query for more values. repeat should be used with sites or functions that block until a value is available. Notice that if any call to f halts, then repeat(f) consequently halts.

For example, it is very easy to treat a channel c as a stream, reading any values put on the channel as they become available:

repeat(c.get)

Variables in Orc are immutable. There is no assignment operator, and there is no way to change the value of a bound variable. However, it is often useful to have mutable state when writing certain algorithms. The Orc library contains two sites that offer simple mutable storage: Ref and Cell. It also provides the site Array to create mutable arrays.

A word of caution: References, cells, and other mutable objects may be accessed concurrently by many different parts of an Orc program, so race conditions may arise.

val r = Ref(0)
Println(r.read()) >>
r.write(2) >> 
Println(r.read()) >>
stop

{-
OUTPUT:
0
2
-}

{- Create a cell, and wait 1 second before initializing it.
   The read operation blocks until the write occurs. 
-}

val r = Ref()
r.read() | Rwait(1000) >> r.write(1) >> stop

{-
OUTPUT:
1
-}

{- Create a cell, try to write to it twice, and read it.
   The read will block until a write occurs
   and only one write will succeed. 
-}

val r = Cell()
  Rwait(1000) >> r.write(2) >> Println("Wrote 2") >> stop
| Rwait(2000) >> r.write(3) >> Println("Wrote 3") >> stop
| r.read()

{-
OUTPUT:PERMUTABLE
2
Wrote 2
-}

{- Create a cell, try to write to it twice, and read it.
   The read will block until a write occurs
   and only one write will succeed.
-}

val r = Cell()
  Rwait(1000) >> r := 2 >> Println("Wrote 2") >> stop
| Rwait(2000) >> r := 3 >> Println("Wrote 3") >> stop
| r?

{-
OUTPUT:PERMUTABLE
2
Wrote 2
-}

{- Create and initialize an array, then halt on out of bounds read -}
val a = Array(10)
def initialize(i) = 
  if (i <: 10) 
    then a(i) := 2 ** i  >>  initialize(i+1)
    else signal
initialize(0) >> (a(3)? | a(6)? | a(10)?)

{-
OUTPUT:PERMUTABLE
8
64
Error: java.lang.ArrayIndexOutOfBoundsException: 10
-}

{- Create an array of 10 elements; element i is the ith power of 2 -}
fillArray(Array(10), lambda(i) = 2 ** i) >a>
a(4)?

{-
OUTPUT:
16
-}

{- Create an array of 5 elements; each element is a newly created channel -}
fillArray(Array(5), lambda(_) = Channel())

{- Create an array of 2 channels -}
val A = fillArray(Array(2), lambda(_) = Channel())

{- Send true on channel 0,
   listen for a value on channel 0 and forward it to channel 1, 
   and listen for a value on channel 1 and publish it. 
-}

  A(0)?.put(true) >> stop
| A(0)?.get() >x> A(1)?.put(x) >> stop
| A(1)?.get()

{-
OUTPUT:
true
-}

upto(n) >i> A(i)? >address> Email(address, m)

Orc programs occasionally require a data structure that supports constant-time indexing but need not also provide mutable storage. For this purpose, an Array is too powerful. The standard library provides another structure called a Table to fill this role.

The call Table(n,f), where n is a natural number and f a total function over natural numbers, creates and returns an immutable array of size n (indexed from 0), whose ith element is initialized to f(i). A table can also be thought of as a partially memoized version of f restricted to the range [0, n). Table does not return a value until all calls to f have completed, and will halt if any call halts. Given a table T, the call T(i) returns the ith element of T. Notice that unlike array access, the ? is not needed to subsequently dereference the return value, since it is not a mutable reference.

Tables are useful when writing algorithms which used a fixed mapping of indexes to some resources, such as a shared table of communication channels. Such a table could be constructed using the following code:

val size = 10
val channels = Table(size, lambda (_) = Channel())

Notice that the lambda ignores its argument, since each channel is identical. Here is another example, which memoizes the cubes of the first 30 natural numbers:

val cubes = Table(30, lambda(i) = i*i*i)

Orc does not have any explicit looping constructs. Most of the time, where a loop might be used in other languages, Orc programs use one of two strategies:

Matching a value against multiple patterns, as we have seen it so far, is a linear process, and requires a def whose clauses have patterns in their argument lists. Such a match is linear; each pattern is tried in order until one succeeds.

What if we want to match a value against multiple patterns in parallel, executing every clause that succeeds? Fortunately, this is very easy to do in Orc. Suppose we have an expression F which publishes pairs of integers, and we want to publish a signal for each 3 that occurs.

We could write:

F >(x, y)>
  ( Ift(x = 3) >> signal
  | Ift(y = 3) >> signal ) 

But there is a more general alternative:

F >x>
  ( x >(3, _)> signal
  | x >(_, 3)> signal ) 

The interesting case is the pair (3,3), which is counted twice because both patterns match it in parallel.

This parallel matching technique is sometimes used as an alternative to pattern matching using function clauses, but only when the patterns are mutually exclusive.

For example,

def helper([]) = 0
def helper([_]) = 1
def helper(_:_:_) = 2
helper([4, 6])

is equivalent to

[4, 6] >x>
( x >[]> 0
| x >[_]> 1
| x >_:_:_> 2
)

whereas

def helper([]) = 0
def helper([_]) = 1
def helper(_) = 2
helper([5])

{-
OUTPUT:
1
-}

is not equivalent to

[5] >x>
( x >[]> 0
| x >[_]> 1
| x >_> 2
)

{-
OUTPUT:PERMUTABLE
1
2
-}

because the clauses are not mutually exclusive. Function clauses must attempt to match in linear order, whereas this expression matches all of the patterns in parallel. Here, it will match [5] two different ways, publishing both 1 and 2.

One of the most common concurrent idioms is a fork-join: run two processes concurrently, and wait for a result from each one. This is very easy to express in Orc. Whenever we write a val declaration, the process computing that value runs in parallel with the rest of the program. So if we write two val declarations, and then form a tuple of their results, this performs a fork-join.

val x = F
val y = G
   # (x,y)

Fork-joins are a fundamental part of all Orc programs, since they are created by all nested expression translations. In fact, the fork-join we wrote above could be expressed even more simply as just:

(F,G)

def initAll([]) = signal
def initAll(m:ms) = ( m.init() , initAll(ms) ) >> signal

def auction([]) = 0
def auction(b:bs) = max(b.ask(), auction(bs))

Note that all bidders are called simultaneously. Also note that if some bidder fails to return a bid, then the auction will never complete. Later we will see a different solution that addresses the issue of non-termination.

M()  >x>  F | N()  >y>  G

( M() , N() )  >(x,y)>  ( F | G )

Previous sections illustrate how Orc can use the fork-join idiom to process a fixed set of expressions or a list of values. Suppose that instead we wish to process all the publications of an expression F, and once this processing is complete, execute some expression G. For example, F publishes the contents of a text file, one line at a time, and we wish to print each line to the console using the site println, then publish a signal after all lines have been printed.

Sequential composition alone is not sufficient, because we have no way to detect when all of the lines have been processed. A recursive fork-join solution would require that the lines be stored in a traversable data structure like a list, rather than streamed as publications from F. A better solution uses the ; combinator to detect when processing is complete:

F >x> println(x) >> stop ; signal

Since ; only evaluates its right side if the left side does not publish, we suppress the publications on the left side using stop. Here, we assume that we can detect when F halts. If, for example, F is publishing the lines of the file as it receives them over a socket, and the sending party never closes the socket, then F never halts and no signal is published.

The otherwise combinator is also useful for trying alternatives in sequence. Consider an expression of the form F0 ; F1 ; F2 ; .... If F_i does not publish and halts, then F_i+1 is executed. We can think of the F_i's as a series of alternatives that are explored until a publication occurs.

Suppose that we would like to poll a list of channels for available data. The list of channels is ordered by priority. The first channel in the list has the highest priority, so it is polled first. If it has no data, then the next channel is polled, and so on.

Here is a function which polls a prioritized list of channels in this way. It publishes the first item that it finds, removing it from the originating channel. If all channels are empty, the function halts. We use the getnb ("get non-blocking") method of the channel, which retrieves the first available item if there is one, and halts otherwise.

def priorityPoll([]) = stop
def priorityPoll(b:bs) = b.getD() ; priorityPoll(bs)

``Parallel or'' is a classic idiom of parallel programming. The ``parallel or'' operation executes two expressions F and G in parallel, each of which may publish a single boolean, and returns the disjunction of their publications as soon as possible. If one of the expressions publishes true, then the disjunction is true, so it is not necessary to wait for the other expression to publish a value. This holds even if one of the expressions is silent.

The ``parallel or'' of expressions F and G may be expressed in Orc as follows:

val result =
  val a = F
  val b = G
  Ift(a)  >>  true | Ift(b)  >>  true | (a || b)

result

The expression (a || b) waits for both a and b to become available and then publishes their disjunction. However if either a or b is true we can publish true immediately regardless of whether the other variable is available. Therefore we run Ift(a) >> true and Ift(b) >> true in parallel to wait for either variable to become true and immediately publish the result true. Since more than one of these expressions may publish true, the surrounding val is necessary to select and publish only the first result.

Timeout, the ability to execute an expression for at most a specified amount of time, is an essential ingredient of fault-tolerant and distributed programming. Orc accomplishes timeout using pruning and the Rwait site. The following program runs F for at most one second, publishing its result if available and the value 0 otherwise.

Let( F | Rwait(1000) >> 0 )

def auction([]) = 0
def auction(b:bs) = 
  val bid = b.ask() | Rwait(8000) >> 0
  max(bid, auction(bs))

val (r, b) = (F, true) | (Rwait(t), false)
if b then G else H

val s = Some(F) | Rwait(t) >> None()
  s >Some(r)> G
| s >None()>  H

def timeout(x, t) = Let(Some(x) | Rwait(t) >> None())

def repeatWithTimeout(f, t) = 
  timeout(f(), t) 
    >Some(x)> 
  (x | repeatWithTimeout(f, t))

def f'() = timeout(f(), t) >Some(x)> x
repeat(f')

We can use a timer to give a window of priority to one computation over another. In this example, we run expressions F and G concurrently. For one second, F has priority; F's result is published immediately, but G's result is held until the time interval has elapsed. If neither F nor G publishes a result within one second, then the first result from either is published.

val x = F
val y = G
Let( x | Rwait(1000) >> y )

A timer can be used to execute an expression repeatedly at regular intervals, for example to poll a service. Recall the definition of metronome from the previous chapter:

def metronome(t) = signal | Rwait(t) >> metronome()

The following example publishes "tick" once per second and "tock" once per second after an initial half-second delay. The publications alternate: "tick tock tick tock ...". Note that this program is not defined recursively; the recursion is entirely contained within metronome.

  metronome(1000) >> "tick"
| Rwait(500) >> metronome(1000) >> "tock"

The Orc combinators restrict the passing of values among their component expressions. However, some programs will require greater flexibility. For example, F <x< G provides F with the first publication of G, but what if F needs the first n publications of G? In cases like this we use channels or other stateful sites to redirect or store publications. We call this technique routing because it involves routing values from one execution to another.

val c = Channel()
repeat(c.get) << 
    F >x> c.put(x) >> stop 
  | Rwait(1000) >> c.closeD()

val c = Channel()
repeat(c.get) << 
  F >x> 
    (if x >= 0 
        then c.put(x) >> stop
        else c.closeD())

val c = Channel()
val done = Semaphore(0)
repeat(c.get) <<
    F >x> c.put(x) >> stop
  | done.acquire() >> c.closeD()

val c = Channel()
val done = Semaphore(0)
def allow(0) = done.release() >> stop
def allow(n) = c.get() >x> (x | allow(n-1))
allow(5) << 
    F >x> c.put(x) >> stop 
  | done.acquire() >> c.closeD()

val r = Cell()
#
   (F <x< c.read()) | (G >x> c.write(x))

val c = Channel()
repeat(c.get) | (F >x> c.put(x) >> stop ; c.close() >> G)  

We consider various concurrent implementations of the classic "list fold" function from functional programming:

def fold(_, [x])  = x
def fold(f, x:xs) = f(x, fold(xs))

This is a seedless fold (sometimes called fold1) which requires that the list be nonempty and uses its first element as a seed. This implementation is short-circuiting --- it may finish early if the reduction operator f does not use its second argument --- but it is not concurrent; no two calls to f can proceed in parallel. However, if f is associative, we can overcome this restriction and implement fold concurrently. If f is also commutative, we can further increase concurrency.

def afold(_, [x]) = x
def afold(f, xs) =
  def step([]) = []
  def step([x]) = [x]
  def step(x:y:xs) = f(x,y):step(xs)
  afold(f, step(xs))

def cfold(f, xs) =
  val c = Channel()
  
  def xfer([])    = 0
  def xfer(x:xs)  = c.put(x) >> stop | xfer(xs)+1

  def combine(0) = stop
  def combine(1) =  c.get()
  def combine(m) =  c.get() >x> c.get() >y> 
                    ( c.put(f(x,y)) >> stop | combine(m-1))

  xfer(xs) >n> combine(n)

The dining philosophers problem is a well known and intensely studied problem in concurrent programming. Five philosophers sit around a circular table. Each philosopher has two forks that she shares with her neighbors (giving five forks in total). Philosophers think until they become hungry. A hungry philosopher picks up both forks, one at a time, eats, puts down both forks, and then resumes thinking. Without further refinement, this scenario allows deadlock; if all philosophers become hungry and pick up their left-hand forks simultaneously, no philosopher will be able to pick up her right-hand fork to eat. Lehmann and Rabin's solution ^[3], which we implement, requires that each philosopher pick up her forks in a random order. If the second fork is not immediately available, the philosopher must set down both forks and try again. While livelock is still possible if all philosophers take forks in the same order, randomization makes this possibility vanishingly unlikely.

{- Dining Philosophers -}

{- Randomly swap order of fork pick-up -}
def shuffle(a,b) = if (Random(2) = 1) then (a,b) else (b,a)

def take((a,b)) =    
  a.acquire() >> b.acquireD() ;
  a.release() >> take(shuffle(a,b))
    
def drop(a,b) = (a.release(), b.release()) >> signal

{- Define a philosopher -}
def phil(n,a,b) =
  def thinking() = 
    Println(n + " thinking") >> 
    (if (Random(10) <: 9)
      then Rwait(Random(1000))
      else stop)
  def hungry() = take((a,b))
  def eating() = 
    Println(n + " eating") >> 
    Rwait(Random(1000)) >> 
    Println(n + " done eating") >> 
    drop(a,b)
  thinking() >> hungry() >> eating() >> phil(n,a,b)

def philosophers(1,a,b) = phil(1,a,b)
def philosophers(n,a,b) =
  val c = Semaphore(1)
  philosophers(n-1,a,c) | phil(n,c,b)

{- Test the definitions -}
val fork = Semaphore(1)
philosophers(5,fork,fork)

{-
OUTPUT:EXAMPLE
5 thinking
4 thinking
3 thinking
2 thinking
1 thinking
1 eating
4 eating
...
-}

The phil function simulates a single philosopher. It takes as arguments two binary semaphores representing the philosopher's forks, and calls the thinking, hungry, and eating functions in a continuous loop. A thinking philosopher waits for a random amount of time, with a 10% chance of thinking forever. A hungry philosopher uses the take function to acquire two forks. An eating philosopher waits for a random time interval and then uses the drop function to relinquish ownership of her forks.

Calling take(a,b) attempts to acquire a pair of forks (a,b) in two steps: wait for fork a to become available, then immediately attempt to acquire fork b. The call b.acquireD() either acquires b and responds immediately, or halts if b is not available. If b is acquired, signal success; otherwise, release a, and then try again, randomly changing the order in which the forks are acquired using the auxiliary function shuffle.

The function call philosophers(n,a,b) recursively creates a chain of n philosophers, bounded by fork a on the left and b on the right. The goal expression of the program calls philosophers to create a chain of five philosophers bounded on the left and right by the same fork; hence, a ring.

This Orc solution has several nice properties. The overall structure of the program is functional, with each behavior encapsulated in its own function, making the program easy to understand and modify. Mutable state is isolated to the "fork" semaphores and associated take and get functions, simplifying the implementation of the philosophers. The program never manipulates threads explicitly, but instead expresses relationships between activities using Orc's combinators.

Here we implement a different solution to the Dining Philosophers problem, described in "The Drinking Philosophers Problem", by K. M. Chandy and J. Misra ^[4]. Briefly, this algorithm efficiently and fairly solves the dining philosophers problem for philosophers connected in an arbitrary graph (as opposed to a simple ring). The algorithm works by augmenting each fork with a clean/dirty state. Initially, all forks are dirty. A philosopher is only obliged to relinquish a fork to its neighbor if the fork is dirty. On receiving a fork, the philosopher cleans it. On eating, the philosopher dirties all forks. For full details of the algorithm, consult the original paper.

{- The "hygenic solution to the diners problem",
   described in "The Drinking Philosophers Problem", by
   K. M. Chandy and J. Misra.
-}

{- 
Use a Scala set implementation.
Operations on this set are not synchronized.
-}
import class ScalaSet = "scala.collection.mutable.HashSet"

{-
Make a set initialized to contain
the items in the given list.
-}
def Set(items) = ScalaSet() >s> joinMap(s.add, items) >> s


{-
Start a philosopher process; never publishes.

name: identify this process in status messages
mbox: our mailbox
missing: set of neighboring philosophers holding our fork
-}
def philosopher(name, mbox, missing) =
  val send = mbox.put
  val receive = mbox.get
  -- deferred requests for forks
  val deferred = Channel()
  -- forks we hold which are clean
  val clean = Set([])

  def sendFork(p) =
    missing.add(p) >>
    p(("fork", send))
 
  def requestFork(p) =
    clean.add(p) >>
    p(("request", send))
  
  -- While thinking, start a timer which
  -- will tell us when we're hungry
  def digesting() =
      Println(name + " thinking") >>
      thinking()
    | Rwait(Random(30)) >>
      send(("rumble", send)) >>
      stop

  def thinking() =
    def on(("rumble", _)) =
      Println(name + " hungry") >>
      map(requestFork, missing.toList()) >>
      hungry()
    def on(("request", p)) =
      sendFork(p) >>
      thinking()
    on(receive())

  def hungry() =
    def on(("fork", p)) =
      missing.remove(p) >>
      ( 
        if missing.isEmpty() then
          Println(name + " eating") >>
          eating()
        else hungry()
      )
    def on(("request", p)) =
      if clean.contains(p) then
        deferred.put(p) >>
        hungry()
      else
        sendFork(p) >>
        requestFork(p) >>
        hungry()
    on(receive())

  def eating() =
    clean.clear() >>
    Rwait(Random(10)) >>
    map(sendFork, deferred.getAll()) >>
    digesting()

  digesting()

{-
Create an NxN 4-connected grid of philosophers.  Each philosopher holds the
fork for the connections below and to the right (so the top left philosopher
holds both its forks).
-}
def philosophers(n) =
  {- channels -}
  val cs = uncurry(Table(n, lambda (_) = Table(n, ignore(Channel))))

  {- first row -}
  philosopher((0,0), cs(0,0), Set([]))
  | for(1, n) >j>
    philosopher((0,j), cs(0,j), Set([cs(0,j-1).put]))

  {- remaining rows -}
  | for(1, n) >i> (
      philosopher((i,0), cs(i,0), Set([cs(i-1,0).put]))
      | for(1, n) >j>
        philosopher((i,j), cs(i,j), Set([cs(i-1,j).put, cs(i,j-1).put]))
    )

philosophers(2)

{-
OUTPUT:EXAMPLE
(0, 0) thinking
(0, 1) thinking
(1, 0) thinking
(1, 1) thinking
(1, 0) hungry
(0, 0) hungry
(0, 1) hungry
(1, 1) hungry
(1, 1) eating
(1, 1) thinking
...
-}

Our implementation is based on the actor model of concurrency. An actor is a state machine which reacts to messages. On receiving a message, an actor can send asynchronous messages to other actors, change its state, or create new actors. Each actor is single-threaded and processes messages sequentially, which makes some concurrent programs easier to reason about and avoids explicit locking. Erlang is one popular language based on the actor model.

Orc emulates the actor model very naturally. In Orc, an actor is an Orc thread of execution, together with a Channel which serves as a mailbox. To send a message to an actor, you place it in the actor's mailbox, and to receive a message, the actor gets the next item from the mailbox. The internal states of the actor are represented by functions: while an actor's thread of execution is evaluating a function, it is considered to be in the corresponding state. Because Orc implements tail-call optimization, state transitions can be encoded as function calls without running out of stack space.

In this program, a philosopher is implemented by an actor with three primary states: eating, thinking, and hungry. An additional transient state, digesting, is used to start a timer which will trigger the state change from thinking to hungry. Each state is implemented by a function which reads a message from the mailbox, selects the appropriate action using pattern matching, performs the action, and finally transitions to the next state (possibly the same as the current state) by calling the corresponding function.

Forks are never represented explicitly. Instead each philosopher identifies a fork with the "address" (sending end of a mailbox) of the neighbor who shares the fork. Every message sent includes the sender's address. Therefore when a philosopher receives a request for a fork, it knows who requested it and therefore which fork to relinquish. Likewise when a philosopher receives a fork, it knows who sent it and therefore which fork was received.

Here we present an Orc solution to the readers-writers problem. Briefly, the readers-writers problem involves concurrent access to a mutable resource. Multiple readers can access the resource concurrently, but writers must have exclusive access. When readers and writers conflict, different solutions may resolve the conflict in favor of one or the other, or fairly. In the following solution, when a writer tries to acquire the lock, current readers are allowed to finish but new readers are postponed until after the writer finishes. Lock requests are granted in the order received, guaranteeing fairness. Normally, such a service would be provided to Orc programs by a site, but it is educational to see how it can be implemented directly in Orc.

{- A solution to the readers-writers problem -}

{- Queue of lock requests -}
val m = Channel()
{- Count of active readers/writers -}
val c = Counter()

{- Process requests in sequence -}
def process() =
  {- Grant read request -}
  def grant((false,s)) = c.inc() >> s.release()
  {- Grant write request -}
  def grant((true,s)) =
    c.onZero() >> c.inc() >> s.release() >> c.onZero()
  {- Goal expression of process() -}
  m.get() >r> grant(r) >> process()

{- Acquire the lock: argument is "true" if writing -}
def acquire(write) =
  val s = Semaphore(0)
  m.put((write, s)) >> s.acquire()

{- Release the lock -}
def release() = c.dec()

-------------------------------------------------

{- These definitions are for testing only -}
def reader(start) = Rwait(start) >>
  acquire(false) >> Println("START READ") >>
  Rwait(1000) >> Println("END READ") >>
  release() >> stop
def writer(start) = Rwait(start) >>
  acquire(true) >> Println("START WRITE") >>
  Rwait(1000) >> Println("END WRITE") >>
  release() >> stop

Let(
    process()  {- Output:     -}
  | reader(10) {- START READ  -}
  | reader(20) {- START READ  -}
               {- END READ    -}
               {- END READ    -}
  | writer(30) {- START WRITE -}
               {- END WRITE   -}
  | reader(40) {- START READ  -}
  | reader(50) {- START READ  -}
               {- END READ    -}
               {- END READ    -}
  {- halt after the last reader finishes -}
  | Rwait(60) >> acquire(true)
)

{-
OUTPUT:EXAMPLE
END READ
START WRITE
END WRITE
START READ
START READ
END READ
END READ
signal
-}

The lock receives requests over the channel m and processes them sequentially with the function grant. Each request includes a boolean flag which is true for write requests and false for read requests, and a Semaphore which the requester blocks on. The lock grants access by releasing the semaphore, unblocking the requester.

The counter c tracks the number of readers or writers currently holding the lock. Whenever the lock is granted, grant increments c, and when the lock is released, c is decremented. To ensure that a writer has exclusive access, grant waits for the c to become zero before granting the lock to the writer, and then waits for c to become zero again before granting any more requests.

The original quicksort algorithm ^[5] was designed for efficient execution on a uniprocessor. Encoding it as a functional program typically ignores its efficient rearrangement of the elements of an array. Further, no known implementation highlights its concurrent aspects. The following program attempts to overcome these two limitations. The program is mostly functional in its structure, though it manipulates the array elements in place. We encode parts of the algorithm as concurrent activities where sequentiality is unneeded.

The following listing gives the implementation of the quicksort function which sorts the array a in place. The auxiliary function sort sorts the subarray given by indices s through t by calling part to partition the subarray and then recursively sorting the partitions.

{- Perform Quicksort on a list -}

def quicksort(a) =

  def swap(x, y) = a(x)? >z> a(x) := a(y)? >> a(y) := z

  {- Partition the elements based on pivot point 'p' -}
  def part(p, s, t) =
    def lr(i) = if i <: t && a(i)? <= p then lr(i+1) else i
    def rl(i) = if a(i)? :> p then rl(i-1) else i

    #
      (lr(s), rl(t)) >(s', t')>
      ( Ift (s' + 1 <: t') >> swap(s', t') >> part(p, s'+1, t'-1)
      | Ift (s' + 1 = t') >> swap(s', t') >> s'
      | Ift (s' + 1 :> t') >> t'
      )

  {- Sort the elements -}
  def sort(s, t) =
     if s >= t then signal
     else part(a(s)?, s+1, t) >m>
          swap(m, s) >>
          (sort(s, m-1), sort(m+1, t)) >>
          signal

  sort(0, a.length?-1)

val a = Array(3)
a(0) := 1 >>
a(1) := 3 >>
a(2) := 2 >>

quicksort(a) >> arrayToList(a)

{-
OUTPUT:
[1, 2, 3]
-}

The function part partitions the subarray given by indices s through t into two partitions, one containing values less than or equal to p and the other containing values > p. The last index of the lower partition is returned. The value at a(s-1) is assumed to be less than or equal to p --- this is satisfied by choosing p = a(s-1)? initially. To create the partitions, part calls two auxiliary functions lr and rl concurrently. These functions scan from the left and right of the subarray respectively, looking for out-of-place elements. Once two such elements have been found, they are swapped using the auxiliary function swap, and then the unscanned portion of the subarray is partitioned further. Partitioning is complete when the entire subarray has been scanned.

This program uses the syntactic sugar x? for x.read() and x := y for x.write(y). Also note that the expression a(i) returns a reference to the element of array a at index i, counting from 0.

Orc makes very few assumptions about the behaviors of services it uses. Therefore it is straightforward to write programs which interact with human agents and network services. This makes Orc especially suitable for encoding workflows, the coordination of multiple activities involving multiple participants. The following program illustrates a simple workflow for scheduling a business meeting. Given a list of people and a date range, the program asks each person when they are available for a meeting. It then combines all the responses, selects a meeting time which is acceptable to everyone, and notifies everyone of the selected time.

{- This program requires the Orchard environment to run -}
include "forms.inc"
include "mail.inc"

val during = Interval(LocalDate(2009, 9, 10),
                      LocalDate(2009, 10, 17))
val invitees = ["john@example.com", "jane@example.com"]

def invite(invitee) =
  Form() >f>
  f.addPart(DateTimeRangesField("times",
    "When are you available for a meeting?", during, 9, 17)) >>
  f.addPart(Button("submit", "Submit")) >>
  SendForm(f) >receiver>
  SendMail(invitee, "Meeting Request", receiver.getURL()) >>
  receiver.get() >response>
  response.get("times")

def notify([]) =
  each(invitees) >invitee>
  SendMail(invitee, "Meeting Request Failed",
                    "No meeting time found.")
def notify(first:_) =
  each(invitees) >invitee>
  SendMail(invitee, "Meeting Request Succeeded",
                    first.getStart())

map(invite, invitees) >responses>
afold(lambda (a,b) = a.intersect(b), responses) >times>
notify(times)

This program begins with declarations of during (the date range for the proposed meeting) and invitees (the list of people to invite represented by email addresses).

The invite function obtains possible meeting times from a given invitee, as follows. First it uses library sites (Form, DateTimeRangesField, Button, and SendForm) to construct a web form which may be used to submit possible meeting times. Then it emails the URL of this form to the invitee and blocks waiting for a response. When the invitee receives the email, he or she will use a web browser to visit the URL, complete the form, and submit it. The corresponding execution of invite receives the response in the variable response and extracts the chosen meeting times.

The notify function takes a list of possible meeting times, selects the first meeting time in the list, and emails everyone with this time. If the list of possible meeting times is empty, it emails everyone indicating that no meeting time was found.

The goal expression of the program uses the library function map to apply notify to each invitee and collect the responses in a list. It then uses the library function afold to intersect all of the responses. The result is a set of meeting times which are acceptable to everyone. Finally, notify is called to select one of these times and notify everyone of the result.

This program may be extended to add more sophisticated features, such as a quorum (to select a meeting as soon as some subset of invitees responds) or timeouts (to remind invitees if they don't respond in a timely manner). These modifications are local and do not affect the overall structure of the program. For complete details, see examples on our Web site.