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.