Orc User Guide v1.0.0

The simplest expression one can write is a constant. It evaluates trivially to that constant value.

Cor has three types of constants, and thus for the moment three types of values:

Cor has a standard set of arithmetic, logical, and comparison operators. As in most other programming languages, they are written in the usual infix style. They have Java-like operator precedence, which can be overridden by adding parentheses.

Here is the full set of operators that Cor supports:

There is also a unary negation operator, written -, for example -(2 ** 5).

The = operator can compare values of any type. Values of different type are always unequal; for example, 10 = true evaluates to false.

Numbers with no decimal part, such as 3, are treated as integers. Arithmetic operators with two integer arguments will perform an integer operation and return an integer result; for example, 5 / 2 performs integer division and evaluates to 2. However, if either argument to an operator has a decimal part (even if it is trivial, as in 3.0), the other argument will be promoted, and a decimal operation will be peformed. For example, 5 / 2.0 and 5.0 / 2 both perform decimal division and evaluate to 2.5.

A conditional expression in Cor is of the form if E then F else G. Its meaning is similar to that in other languages: the value of the expression is the value of F if and only if E evaluates to true, or the value of G if and only if E evaluates to false. Note that G is not evaluated at all if E evaluates to true, and similarly F is not evaluated at all if E evaluates to false. Thus, for example, evaluation of if true then 2+3 else 1/0 does not evaluate 1/0; it only evaluates 2+3.

Unlike other languages, expressions in Cor may be silent. If E is silent, then the entire expression is silent. And if E evaluates to true but F is silent (or if E evaluates to false and G is silent) then the expression is silent.

Note that conditionals have lower precedence than any of the operators. For example, if false then 1 else 2 + 3 is equivalent to if false then 1 else (2 + 3), not (if false then 1 else 2) + 3.

The behavior of conditionals is summarized by the following table (v denotes a value).

A variable can be bound to a value. A declaration binds one or more variables to values. The simplest form of declaration is val, which evaluates an expression and binds its result to a variable. Declarations follow the rules of lexical scoping.

val x = 1 + 2
val y = x + x

If the expression on the right side of a val is silent, then the variable is not bound, but evaluation of other declarations and expressions continues. If an evaluated expression depends on that variable, that expression is silent.

val x = 1/0
val y = 4+5
if false then x else y

Cor supports two basic data structures, tuples and lists.

We have seen how to construct data structures. But how do we examine them, and use them? We use patterns.

A pattern is a powerful way to bind variables. When writing val declarations, instead of just binding one variable, we can replace the variable name with a more complex pattern that follows the structure of the value, and matches its components. A pattern's structure is called its shape; a pattern may take the shape of any structured value. A pattern can hierarchically match a value, going deep into its structure. It can also bind an entire structure to a variable.

Patterns are linear; that is, a pattern may mention a variable name at most once. For example, (x,y,x) is not a valid pattern.

Note that a pattern may fail to match a value, if it does not have the same shape as that value. In a val declaration, this has the same effect as evaluating a silent expression. No variable in the pattern is bound, and if any one of those variables is later evaluated, it is silent.

It is often useful to ignore parts of the value that are not relevant. We can use the wildcard pattern, written _, to do this; it matches any shape and binds no variables.

Like most other programming languages, Cor 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

After defining the function, we can call it. A call looks just like the left side of the declaration except that the variable names (the formal parameters) have been replaced by expressions (the actual parameters).

To evaluate a call, we treat it as a sequence of val declarations associating the formal parameters with the actual parameters, followed by the body of the function.

{- Evaluation of add(1+2,3+4) -}
val x = 1+2
val y = 3+4
x+y

Notice that the evaluation strategy of functions allows a call to proceed even if some of the actual parameters are silent, so long as the values of those actual parameters are not used in the evaluation of the body.

def cond(b,x,y) = if b then x else y
cond(true, 3, 5/0)

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 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 a(x) = x-3
def b(y) = y*4
val funs = (a,b)

def onetwosum(f) = f(1) + f(2)
def triple(x) = x * 3

def onetwosum(f) = f(1) + f(2)

onetwosum( lambda(x) = x * 3 )
{- 
  identical to:
  def triple(x) = x * 3
  onetwosum(triple)
-}

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

{- Fibonacci numbers -}
def fib(0) = 1
def fib(1) = 1
def fib(n) = if (n < 0) then 0 else fib(n-1) + fib(n-2)

{- Alternate definition of the Fibonacci function -}

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

def fib(n) = 
  if (n < 0) then 0 
  else (
    val (x,_) = H(n) 
    x
  )
     
    

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

def stutter([]) = []
def stutter(h:t) = h:h:mutter(t)
def mutter([]) = []
def mutter(h:t) = h:stutter(t)

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

Cor has two kinds of comments.

A line which begins with two dashes (--), preceded only by whitespace, is a single line comment. The region from the two dashes to the next encountered newline, inclusive, is ignored.

-- This is a single line comment.
	 -- This is also a single line comment.

Multi-line comments are enclosed by matching braces of the form {- -}. Multi-line comments may be nested. They may appear anywhere, even in the middle of an expression.

{- 
   This is a
   multiline comment.
-}
   
{- Multiline comments {- can be nested -} -}

{- They may appear anywhere, -} 
1 + {- even in the middle of an expression. -} 2 + 3

An Orc expression may be a site call. Sites are called using the same syntax as a function call, but with a slightly different meaning. Sites are introduced and bound to variables by a special declaration.

{- Get the top search result for "computation orchestration" -}
Google("computation orchestration")

{-
  Create a search site from a search engine URL,
  bind the variable Search to that site,
  then use that site to search for a term.
-}
val Search = SearchEngine("http://www.google.com/")
Search("first class value")

{- 
  Use the 'println' site to print a string, followed by
  a newline, to an output console.
  The return value of this site call is a signal.
-}
println("Hello, World!")

{-  Define the Buffer site  -}
site Buffer = orc.lib.state.Buffer

Orc has four combinators: parallel, sequential, pruning, and otherwise. A combinator forms an expression from two component expressions. Each combinator captures a different aspect of concurrency. Syntactically, the combinators are written infix, and have lower precedence than operators, but higher precedence than conditionals or declarations.

-- Publish 1 and 2 in parallel  
1 | 1+1

{- 
  Access two search sites, Google and Yahoo, in parallel.

  Publish any results they return.
  
  Since each call may publish a value, the expression
  may publish up to two values.
-}  
Google("cupcake") | Yahoo("cupcake")

-- Publish 1, 2, and 3 in parallel  
1+0 | 1+1 | 1+2

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

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

-- Publish 0, 1, 2 and 3 in parallel  
(0 | 2) >n> (n | n+1)

-- Prepend the site name to each published search result
-- The cat site concatenates any number of arguments into one string  
  Google("cupcake") >s> cat("Google: ", s)
| Yahoo("cupcake") >s> cat("Yahoo: ", s)

-- Publish 3, 6, and 9 in arbitrary order.
(3,6,9)  >(x,y,z)>  ( x | y | z )

-- Filter out values of the form (_,false)
( (4,true) | (5,false) | (6,true) )  >(x,true)> x
-- Publishes 4 and 6 

{- 
  Print two strings to the console,
  but don't publish the return values of the calls.
-}
( println("goodbye") | println("world") ) >> stop

{- 
  Publish the cross product of {1,2} and {3,4}:
  (1,3), (1,4), (2,3), and (2,4).
-}
(1 | 2) >x> (3 | 4) >y> (x,y)

-- Publish either 5 or 6, but not both
x+2 <x< (3 | 4)

-- Query Google and Yahoo for a search result
-- Print out the result that arrives first; ignore the other result
println(result) <result< ( Google("cupcake") | Yahoo("cupcake") )

{- 
  This example actually prints both "true" and "false" to the
  console, regardless of which call responds first.
-}
stop <x< println("true") | println("false")

-- Publish either 9 or 25, but not 16.
x*x <(x,true)< ( (3,true) | (4,false) | (5,true) )

Some Cor expressions have new behaviors in the context of Orc, due to the introduction of concurrency and of sites.

-- Publish either 5 or 6
2 + (3 | 4)

-- Publish exactly one of 0, 1, 2 or 3
(0 | 2) + (0 | 1)

-- Publish all integers in the interval 1..n, in arbitrary order. 
def range(n) = if (n > 0) then (n | range(n-1)) else stop 

-- Publish 1, 2, and 3 in arbitrary order.
range(3)

Orc is designed to communicate with the external world, and one of the most important characteristics of the external world is the passage of time. Orc implicitly interacts with the passage of time by calling external services which take time to respond. However, Orc can also explicitly wait for some amount of time, using the special site Rtimer.

The site Rtimer is a relative timer. It takes as an argument a number of milliseconds to wait. It waits for exactly that amount of time, and then responds with a signal.

-- Print "red", wait for 3 seconds (3000 ms), and then print "green" 
println("red") >> Rtimer(3000) >> println("green") >> stop

The following example defines a metronome, which publishes a signal once every t milliseconds, indefinitely.

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

We can also use Rtimer together with the pruning combinator to enforce a timeout.

{-
  Publish the result of a Google search.
  If it takes more than 5 seconds, time out.
-}
result 
  <result< ( Google("impatience") 
           | Rtimer(5000) >> "Search timed out.")

We have seen Orc's predefined data structures: tuples and lists. 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 )

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.

When the combined expressions 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 combined expressions are small, write a cascade of sequential combinators all on the same line.

F >x> G >y> H

Remember that sequential is right associative; in this example, x is bound in both G and H, and y is bound in H.

When the combined expressions are large 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-running 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 combined expressions are small, write them on the same line:

F <x< G

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)

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

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).

Declarations should always end with a newline.

def add(x,y) = x + y
val z = 7
add(z,z)

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

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 Buffer. 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.closenb(), which returns a signal immediately.

In the section on Cor, 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)

While lists are a very useful data structure, they are not indexed; it is not possible to get the nth element of a list in constant time. However, this capability is often needed in practice, so the Orc standard library provides a function IArray to create immutable arrays. Once initialized, an immutable array cannot be rewritten; it can only be read.

IArray takes two arguments: an array size, and a function to initialize the array. The function takes the index being initialized as an argument (indices start at 0), and publishes the value to be stored at that array position. Here are a few examples:

{- Create an array of 10 elements; element i is the ith power of 2 -}
IArray(10, lambda(i) = 2 ** i)

{- Create an array of 5 elements; each element is a newly created buffer -}
IArray(5, lambda(_) = Buffer())

The array is used like a function; the call A(i) returns the ith element of the array A. A call with an out-of-bounds index halts.

{- Create an array of 3 buffers -}
val A = IArray(10, lambda(_) = Buffer())

{- Send true on the 0th channel
   and listen for a value on the 0th channel. -}
A(0).put(true) | A(0).get()

Since arrays are accessed by index, there is a library function specifically designed to make programming with indices easier. The function upto(n) publishes all of the numbers from 0 to n-1 simultaneously; thus, it is very easy to access all of the elements of an array simultaneously. Suppose we have an array A of n email addresses and would like to send the message m to each one.

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

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.

The Ref site creates rewritable reference cells.

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

These are very similar to ML's ref cells. r.write(v) stores the value v in the reference r, overwriting any previous value, and publishes a signal. r.read() publishes the current value stored in r.

However, unlike in ML, a reference cell can be left initially empty by calling Ref with no arguments. A read operation on an empty cell blocks until the cell is written.

{- Create a cell, and wait 1 second before initializing it. -}
{- The read operation blocks until the write occurs. -}
val r = Ref()
r.read() | Rtimer(1000) >> r.write(1) >> stop

The Orc library also offers write-once reference cells, using the Cell site. A write-once cell has no initial value. Read operations block until the cell has been written. A write operation succeeds only if the cell is empty; subsequent write operations simply halt.

{- 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()
  Rtimer(1000) >> r.write(2) >> println("Wrote 2") >> stop
| Rtimer(1000) >> r.write(3) >> println("Wrote 3") >> stop
| r.read()

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.

{- 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()
  Rtimer(1000) >> r := 2 >> println("Wrote 2") >> stop
| Rtimer(1000) >> r := 3 >> println("Wrote 3") >> stop
| r?

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)>
  ( if(x=3) >> signal
  | if(y=3) >> signal ) 

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

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])

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

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

[5] >x>
  x >[]> 0
| x >[_]> 1
| x >_> 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 buffers for available data. The list of buffers is ordered by priority. The first buffer in the list has the highest priority, so it is polled first. If it has no data, then the next buffer is polled, and so on.

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

def priorityPoll([]) = stop
def priorityPoll(b:bs) = b.getnb() ; 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:

let(
    val a = F
    val b = G

      (a || b)
    | if(a) >> true 
    | if(b) >> true 
)

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 if(a) >> true and if(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 let(...) 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 Rtimer site. The following program runs F for at most one second, publishing its result if available and the value 0 otherwise.

let( F | Rtimer(1000) >> 0 )

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

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

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

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( y | Rtimer(1000) >> x )

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 | Rtimer(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"
| Rtimer(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 = Buffer()
repeat(c.get) << 
    F >x> c.put(x) >> stop 
  | Rtimer(1000) >> c.closenb()

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

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

val c = Buffer()
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.closenb()

val r = Ref()
(F <x< r.read()) | (G >x> r.write(x))

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

We can write a function interruptible that implements the interrupt idiom to execute any function in an interruptible way. interruptible(g) calls the function g, which is assumed to take no arguments, and silences its publications. It immediately publishes another function, which we can call at any time to terminate the execution of g. For simplicity, we assume that g itself publishes no values.

Here is a naive implementation that doesn't quite work:

def interruptible(f) =
  val done = Semaphore(0)
  done.release
    << f() >> stop 
     | done.acquire() >> c.closenb()

{- wrong! -}
val stopper = interruptible(g)
...

The function interruptible is correct, but the way it is used causes a strange error. The function g executes, but is always immediately terminated! This happens because the val declaration which binds stopper also kills all of the remaining computation in interruptible(g), including the execution of g itself.

The solution is to bind the variable differently:

def interruptible(f) =
  val done = Semaphore(0)
  done.release
    << f() >> stop 
     | done.acquire() >> c.closenb()

interruptible(g) >stopper>
...

This idiom, wherein a function publishes some value that can be used to monitor or control its execution, arises occasionally in Orc programming. When using this idiom, always remember to avoid terminating that execution accidentally. Since Orc is a structured concurrent language, every process is contained with some other process; kill the containing process, and the contained processes die too.

def lifter() =
  val c = Buffer()
  def loop() = c.get() >f> ( f() >> stop | loop() )
  c.put | loop()

def delayedPrint() = Rtimer(1500) >> println("Delayed 1.5 seconds")

lifter() >lift>
(
println("Running...") 
  << Rtimer(1000) | delayedPrint() | lift(delayedPrint)
)

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 = Buffer()
  
  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.

def shuffle(a,b) = if (random(2) = 1) then (a,b) else (b,a)

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

def phil(n,a,b) =
  def thinking() = 
    println(n + " thinking") >> 
    if (random(10) < 9)
      then Rtimer(random(1000))
      else stop
  def hungry() = take((a,b))
  def eating() = 
    println(n + " eating") >> 
    Rtimer(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)

val fork = Semaphore(1)
philosophers(5,fork,fork)

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.acquirenb() 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. 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.

{-
Start a philosopher actor; never publishes.
Messages sent between philosophers include:
- ("fork", p): philosopher p relinquishes the fork
- ("request", p): philosopher p requests the fork
- ("rumble", p): sent by a philosopher to itself when it should
  become hungry

name: identify this process in status messages
mbox: our mailbox; the "address" of this philosopher is mbox.put
missing: set of neighboring philosophers holding our forks
-}
def philosopher(name, mbox, missing) =
  {- deferred requests for forks -}
  val deferred = Buffer()
  {- forks we hold which are clean -}
  val clean = Set()

  def sendFork(p) =
    {- remember that we no longer hold the fork -}
    missing.add(p) >>
    p(("fork", mbox.put))
 
  def requestFork(p) =
    p(("request", mbox.put))
  
  {- Start a timer which will tell us when we're hungry. -}
  def digesting() =
      println(name + " thinking") >>
      thinking()
    | Rtimer(random(1000)) >>
      mbox.put(("rumble", mbox.put)) >>
      stop

  {- Wait to become hungry -}
  def thinking() =
    def on(("rumble", _)) =
      println(name + " hungry") >>
      map(requestFork, missing) >>
      hungry()
    def on(("request", p)) =
      sendFork(p) >> thinking()
    on(mbox.get())

  {- Eat once we receive all forks -}
  def hungry() =
    def on(("fork", p)) =
      missing.remove(p) >>
      clean.add(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(mbox.get())

  {- Dirty forks, process deferred requests, then digest -}
  def eating() =
    clean.clear() >>
    Rtimer(random(1000)) >>
    map(sendFork, deferred.getAll()) >>
    digesting()

  {- All philosophers start out 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) =
  {- A set with 1 item -}
  def Set1(item) = Set() >s> s.add(item) >> s
  {- A set with 2 items -}
  def Set2(i1, i2) = Set() >s> s.add(i1) >> s.add(i2) >> s

  {- create an NxN matrix of mailboxes -}
  val cs = uncurry(IArray(n, lambda (_) = IArray(n, ignore(Buffer))))

  {- create the first row of philosophers -}
  philosopher((0,0), cs(0,0), Set())
  | for(1, n) >j>
    philosopher((0,j), cs(0,j), Set1(cs(0,j-1).put))

  {- create remaining rows -}
  | for(1, n) >i> (
      philosopher((i,0), cs(i,0), Set1(cs(i-1,0).put))
      | for(1, n) >j>
        philosopher((i,j), cs(i,j), Set2(cs(i-1,j).put, cs(i,j-1).put))
    )

{- Simulate a 3x3 grid of philosophers for 10 seconds -}
let(
  philosophers(3)
  | Rtimer(10000)
) >> "HALTED"

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 Buffer 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.

-- Queue of lock requests
val m = Buffer()
-- 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) = Rtimer(start) >>
  acquire(false) >> println("START READ") >>
  Rtimer(1000) >> println("END READ") >>
  release() >> stop
def writer(start) = Rtimer(start) >>
  acquire(true) >> println("START WRITE") >>
  Rtimer(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
  | Rtimer(60) >> acquire(true)
)

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 ^[4] 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.

def quicksort(a) =

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

  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')>
    ( if (s' + 1 < t') >> swap(s', t') >> part(p, s'+1, t'-1)
    | if (s' + 1 = t') >> swap(s', t') >> s'
    | if (s' + 1 > t') >> t'
    )

  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)

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.

include "net.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 website.

x.member, where x evaluates to a Java class or object, is evaluated as follows:

Note that no distinction is made between static and non-static members; it is an error to reference a non-static member through a class, but this does not change how members are resolved. Note also that if a field shares a name with one or more methods, there is no way to access the field directly.

The following (rather useless) example illustrates how the dot operator can be used to access both static and non-static methods and fields:

{- bind Integer to a Java class -}
class Integer = java.lang.Integer

{- call a static method -}
val i = Integer.decode("5")
{- read a field -}
val m = Integer.MIN_VALUE.read()
{- write a field -}
Integer.MIN_VALUE.write(5) >>
{- call a non-static method -}
i.toString()

When x evaluates to a Java object (but not a Java class), the syntax x(...) is equivalent to x.apply(...).

When x evaluates to a Java class, the syntax x(...) calls the class's constructor. In case of overloaded constructors, the appropriate constructor is chosen based on the number and types of arguments as described in Method Resolution.

If C is bound to a Java class, it can be used as a pattern. A pattern C(x) matches any Java object of that class or any of its subclasses. The variable x is simply bound to the object again; thus the matcher is just a partial identity function.

When a method handle is called, the actual Java method called is chosen based on the runtime types of the arguments, as follows:

The reason for the unusual implicit narrowing of BigDecimal and BigInteger is that Orc numeric literals have these types, and it would be awkward to have to perform an explicit conversion every time such a value is passed to a Java method expecting a primitive.

Currently we do not implement specificity rules for choosing the best matching method; the first matching method (according to some unspecified order) is chosen. Note also that we do not support varargs methods explicitly, but instead varargs may be passed as an array of the appropriate type.

Orc values are implemented by Java objects, so in general any Orc value may be passed to a site implemented in Java. Standard Orc values have the following Java types:

Java objects may be used directly as values anywhere in an Orc program. Primitive Java values cannot be used directly in an Orc program, but are automatically boxed (and unboxed) as necessary.

When both arguments of an arithmetic or comparison operator are Java numeric types, the arguments are implicitly coerced to the widest of the two argument types. "Widest" is defined by the following relation, where ">" means "is wider than": BigDecimal > Double > Float > BigInteger > Long > Integer > Short > Byte

Orc sites imported with the site declaration are implemented as Java classes which extend orc.runtime.sites.Site. Here we will summarize the most important features of this and related classes; for a detailed description, refer to the Javadoc.

Sites must implement a single method: callSite(Args args, Token token). The Orc engine calls this method whenever the site is called by the Orc program.

The args argument (of type Args) is used to get the arguments which were passed to the site call by the Orc program. It has the following important methods:

The token argument (of type Token) is a sort of callback which is used by the site to return a value or signal that it has halted. It has the following important methods:

The callSite method must return control to its caller within a short, deterministic amount of time. To implement a site which blocks or waits for some condition, callSite must save the token and return without calling any of the above methods. Then when it is time for the site call to return, call the appropriate method on the token.

We will implement a simplified version of Orc's Buffer site, called ExampleBuffer. The goal will be to be able to run this Orc program:

-- Import the site definition
site ExampleBuffer = ExampleBuffer
-- Create a new buffer site
val b = ExampleBuffer()
-- wait for a value in the buffer
b.get()
-- put a value in the buffer
| b.put(3) >> stop
-- Publishes: 3

The first step is to create ExampleBuffer.java. The ExampleBuffer site is actually a discovery site: all it does when called is create and return a reference to a new site (the buffer instance).

public class ExampleBuffer extends EvalSite {
  public Object evaluate(Args args) {
    return new ExampleBufferInstance();
  }
}

Next we must implement ExampleBufferInstance, which defines the behavior of an individual buffer. We can put this class either in its own file or in ExampleBuffer.java, since that is the only class which refers to it directly. How does an instance behave? If we write b.get(), that means that b responds to the message get with a site which we call to get a value from the buffer. So we'll extend DotSite, telling it to respond to the message "get" with a GetMethod site, and likewise for "put". We'll use a linked list to store the actual contents of the buffer.

class ExampleBufferInstance extends DotSite {
  private LinkedList<Object> contents = new LinkedList<Object>();
  public ExampleBufferInstance() {
    addMember("get", new GetMethod());
    addMember("put", new PutMethod());
  }
}

The GetMethod site is implemented as an inner class so it has easy access to the contents of the buffer. In the implementation we first check if there is an item in the buffer. If so, we return it. Otherwise, we must store the token in a queue to be notified when the next item is put in the buffer. We synchronize on the outer object to protect against concurrent modification.

private LinkedList<Token> waiters = new LinkedList<Token>();
private class GetMethod extends Site {
  public void callSite(Args args, Token token) {
    synchronized (ExampleBufferInstance.this) {
      if (!contents.isEmpty()) {
        token.resume(contents.removeFirst());
      } else {
        waiters.add(token);
      } 
    }
  }
}

PutMethod is even simpler since it doesn't need to block. If there is a token waiting for an item, we give it the item. Otherwise we put the item in the buffer. We synchronize on the outer object to protect against concurrent modification. When done we return a dummy "signal" value.

private class PutMethod extends EvalSite {
  public Object evaluate(Args args) {
    Object item = args.getArg(0);
    synchronized (ExampleBufferInstance.this) { 
      if (!waiters.isEmpty()) {
        waiters.removeFirst().resume(item);
      } else {
        contents.add(item);
      } 
    }
    return signal();
  }
}

Putting it all together, here is the entire implementation:

import java.util.LinkedList;

import orc.runtime.sites.EvalSite;
import orc.runtime.sites.DotSite;
import orc.runtime.sites.Site;
import orc.runtime.Token;

public class ExampleBuffer extends EvalSite {
  public Object evaluate(Args args) {
    return new ExampleBufferInstance();
  }
}

class ExampleBufferInstance extends DotSite {
  private LinkedList<Object> contents = new LinkedList<Object>();
  private LinkedList<Token> waiters = new LinkedList<Token>();
    
  private class GetMethod extends Site {
    public void callSite(Args args, Token token) {
      synchronized (ExampleBufferInstance.this) {
        if (!contents.isEmpty()) {
          token.resume(contents.removeFirst());
        } else {
          waiters.add(token);
        } 
      }
    }
  }

  private class PutMethod extends EvalSite {
    public Object evaluate(Args args) {
      Object item = args.getArg(0);
      synchronized (ExampleBufferInstance.this) { 
        if (!waiters.isEmpty()) {
          waiters.removeFirst().resume(item);
        } else {
          contents.add(item);
        } 
      }
      return signal();
    }
  }

  public ExampleBufferInstance() {
    addMember("get", new GetMethod());
    addMember("put", new PutMethod());
  }
}

While we believe Orc is an excellent language for web service scripting, currently the library support for such tasks is at a proof-of-concept level. The web service libraries are not bundled with the core Orc distribution, do not have stable APIs, and are not officially documented. However this section should provide you with enough information to get started.

All Orc sites related to web services are bundled in a separate "OrcSites" library. As with the core Orc distribution, you can either download this library as a prepackaged JAR or check out the source code from the "OrcSites" module in version control. We generally recommend the latter approach, since the source code provides several examples which can be used as a basis for creating your own web service sites.

Within the OrcSites source code you will find:

Several of the examples require you to create .properties files and place them in your classpath. The simplest way to do this is to make sure the examples/ directory is in your classpath, and place the necessary .properties files there.

Web services use a variety of protocols, so there are a variety of ways to contact them. All of them boil down to creating a Java proxy site for the service and calling that. Previous sections explain how to implement such Java sites which can be called in Orc. Because web services tend to use blocking I/O, Java wrappers make frequent use of ThreadedSite and Kilim to ensure that web service calls don't block the Orc engine.

OrcSites includes a generic site orc.lib.net.Webservice which allows you to connect to any SOAP RPC (specifically rpc/encoded) service, without writing Java wrappers. Instead Apache Axis is used to generate Java wrappers on-demand.

http://www.xmethods.net is a good place to find examples of SOAP RPC services:

Example:

site orc.lib.net.Webservice
{-
Find documentation of this service at:
http://www.xmethods.net/ve2/WSDLRPCView.po?
key=uuid:BF3EFCDD-FCD4-8867-3AAC-068985E7CB89
-}
val service = Webservice(
  "http://www.ebob42.com/cgi-bin/"
  + "Romulan.exe/wsdl/IRoman")
service.intToRoman(451)

Many services use ad-hoc REST/XML protocols. Unfortunately, there is no REST equivalent to WSDL, so there's no way to automatically generate an API for REST services. We're not trying to solve this problem with Orc, but when the web services community reaches some kind of consensus, Orc will support it.

For now you must write a Java wrapper for each service which handles marshalling and unmarshalling the data. There's no reason such marshalling code couldn't be written in Orc, calling low-level HTTP and XML libraries directly, but there would be no advantage to doing so, so we let each language play to its strengths. OrcSites includes utility classes to assist with submitting requests and parsing responses.

OrcSites includes the following examples of this type of service:

Each of the Orc constants has the expected type:

Orc allows subtyping: some types are included in other types. For example, Integer is a subtype of Number, because all Integers are also Numbers.

Each of the primitive operators typechecks in the obvious way; for example && requires two Boolean operands and returns a Boolean result. Some of the arithmetic operators also support ad-hoc polymorphism; for example, a + expression with two Integer operands has type Integer, but with one or more Number operands it instead has type Number.

There are two other important types: Top and Bot.

Top is the universal type; it is the type of any value, and all other types are subtypes of it.

Bot is the empty type; no value has type Bot. It is a subtype of all other types. Expressions with type Bot are expressions that the typechecker can verify will never publish any values. In particular, stop will never publish, so it has type Bot.

Bot has an interesting status in Orc. In other typed languages, if an expression has type Bot, this usually indicates a guaranteed error, infinite loop, or other failure to return a value. Since sequential programming rarely involves subexpressions that are guaranteed never to return, Bot is usually just a curiosity or a formal artifact of the type system, and indeed many static type systems do not have a Bot type at all. In Orc, however, Bot is very useful, since it is frequently the case that Orc expressions are written to carry out ongoing concurrent activities but never publish any values, and the type system can use the type Bot to indicate that no publications will ever be seen from such expressions.

The type of a tuple is a tuple of the types of each of its elements.

In the conditional expression if E then F else G, the expression E must have type Boolean, and the type of the whole expression is the join of the types of F and G, as described for the parallel combinator.

Though the typechecker can infer the types of many expressions without additional information from the programmer, there are some cases where the algorithm does need assistance. In particular, whenever a function is defined (using the def keyword), the programmer must also include a signature for that function, supplying its argument types and return type.