The following exercises will allow you to practice and test your knowledge of the Orc programming languages. Exercises are ordered from easy (requiring only basic knowledge of the language and no concurrency) to hard (requiring a good understanding of Orc and its concurrency model). No exercise should take more than 1 hour, and a most will require only a few minutes. You can use the Try Orc tool to implement and test your solutions.

Each exercise has a hidden solution which may be revealed by clicking "(click for solution)". On the honor system, please attempt the problem before looking at the solution.

Functional Programming#

List length#

Write a function which, given a list, returns the number of elements in the list.

(click for solution)
def length([]) = 0
def length(x:xs) = 1 + length(xs)

length([0,0,0,0])

List repetition#

Write a function which, given a list of natural numbers, returns the list with each element x replaced by x occurrences of the same value. For example, given the list [1,2,1,4], the function returns [1,2,2,1,4,4,4,4].

(click for solution)
def repeats(list) =
  def loop(_, 0, []) = []
  def loop(_, 0, x:xs) = loop(x, x, xs)
  def loop(x, n, xs) = x:loop(x, n-1, xs)
  loop(0, 0, list)

repeats([1,2,1,4])

Basic tree traversal#

You are given a data type for binary trees, which has two constructors: Tree(left, value, right) and Leaf(). These constructors can be used in patterns, i.e. x >Tree(l,v,r)> println(l,v,r). Write a function which, given a tree, publishes the values in the tree.

Use this template to test your program:

type Tree = Tree(_, _, _) | Leaf()

def forTree(x) = {- WRITE YOUR SOLUTION HERE -}

forTree(Tree(
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf())),
  1,
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf()))))

(click for solution)
type Tree = Tree(_, _, _) | Leaf()

def forTree(Leaf()) = stop
def forTree(Tree(left, value, right)) =
  value | forTree(left) | forTree(right)

forTree(Tree(
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf())),
  1,
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf()))))

Tree levels#

You are given a data type for binary trees with the constructors Tree(left, value, right) and Leaf(). Write a function which, given a tree, returns a list of values in the tree ordered by depth. I.e. the first element should be the root value, followed by the root's children, followed by its grandchildren, and so on.

Use this template to test your program:

type Tree = Tree(_, _, _) | Leaf()

def levels(x) = {- WRITE YOUR SOLUTION HERE -}

levels(Tree(
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf())),
  1,
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf()))))

(click for solution)
type Tree = Tree(_, _, _) | Leaf()

def levels(tree) =
  def helper([]) = []
  def helper(Leaf():rest) = helper(rest)
  def helper(Tree(l,v,r):rest) =
    v:helper(append(rest, [l, r]))
  helper([tree])

levels(Tree(
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf())),
  1,
  Tree(
    Tree(Leaf(), 3, Leaf()),
    2,
    Tree(Leaf(), 3, Leaf()))))

Find Files#

You are given the site ls(x) which returns a list of file names found in the directory named by the path x, or an empty list if x is not a directory. Paths are written as strings using POSIX conventions, e.g. "/foo/bar/baz". So for example ls("/usr/") might return ["local/", "bin/", "lib/]. Unlike POSIX, you can assume that directory paths always end in "/".

Write a function find(x) which returns a list of all paths in the directory tree starting at the given path. E.g. find("/") might return ["/", "/usr/", "/usr/bin/", "/usr/bin/ls"].

Use this template to test your program:

def ls("/") = ["usr/", "bin/", "lib/"]
def ls("/usr/") = ["local/", "bin/", "lib/"]
def ls("/usr/bin/") = ["ls", "sh", "find"]
def ls(_) = []

def find(x) = {- WRITE YOUR SOLUTION HERE -}

find("/")

(click for solution)
def ls("/") = ["usr/", "bin/", "lib/"]
def ls("/usr/") = ["local/", "bin/", "lib/"]
def ls("/usr/bin/") = ["ls", "sh", "find"]
def ls(_) = []

-------- main program ------

{-
This implementation uses explicit recursion.
-}

def find(root) =
  {- loop(root path, list of files in root path,
          list of pending paths to examine,
          output accumulator) -}
  def loop(_, [], [], accum) = accum
  def loop(_, [], root:paths, accum) =
    loop(root, ls(root), paths, root:accum)
  def loop(root, file:files, paths, accum) =
    loop(root, files, (root+file):paths, accum)
  loop(null, [], [root], [])

find("/")

(alternative solution)
def ls("/") = ["usr/", "bin/", "lib/"]
def ls("/usr/") = ["local/", "bin/", "lib/"]
def ls("/usr/bin/") = ["ls", "sh", "find"]
def ls(_) = []

-------- main program ------

{-
This implementation makes use of map
and foldr to achieve a much more concise
and readable solution.
-}

def flatten(lists) = foldr(append, [], lists)

def find(root) =
  def resolve(file) = root + file
  root:flatten(map(find, map(resolve, ls(root))))

find("/")

Towers of Hanoi#

Write a function to solve the Towers of Hanoi problem. There are three pegs, numbered 0..2; disks are to be moved from peg 0 to peg 2. Your function should take as its argument the number of disks initially on peg 0, and it should return a list of moves, where a move is a tuple (source peg number, destination peg number), e.g. (0,1). Since the point of this exercise is to practice Orc, not solve puzzles, feel free to use the algorithm given in Wikipedia.

(click for solution)
{--
Algorithm as described in
http://en.wikipedia.org/wiki/Tower_of_Hanoi
--}
def hanoi(n) =
  {- arguments: h(eight), f(rom peg),
     r(emaining peg), t(o peg), m(ove)s -}
  def move(1, f, r, t, ms) = (f,t):ms
  def move(h, f, r, t, ms) =
    move(h-1, f, t, r, ms) >ms>
    move(1, f, r, t, ms)   >ms>
    move(h-1, r, f, t, ms)
  reverse(move(n, 0, 1, 2, []))

hanoi(9)

Idioms#

For-each#

Write a program which prints every element of a given list (in an arbitrary order), without explicitly using recursion. You may use the library function each. (This question is as easy as it sounds.)

(click for solution)
each([1,2,3]) >x> println(x) >> stop

Priority#

You are given two sites "Google" and "Yahoo", which both take a single string (a term to search for) and return a list of search results (for this exercise, the format of each result is not important). Write a function which takes a search string and calls both sites. If Google responds within 5 seconds, return its results, otherwise return whichever results are received first.

Use this template to test your program:

include "search.inc"
def search(term) = {- WRITE YOUR SOLUTION HERE -}

search("tacos")

(click for solution)
include "search.inc"

-------- main program ------

def search(term) = x <x< Google(term) | Rtimer(5000) >> Yahoo(term)

search("tacos")

Barrier Synchronization#

Write a program which calls the sites A1, A2, A3, B1 and B2. Order the calls so that A1() < A2() < A3(), B1() < B2(), and A2() < B2() (where "<" means "precedes in time"). You should be able to write this program correctly without testing it.

(click for solution)
def A1() = Rtimer(random(500)) >> println("A1 called")
def A2() = Rtimer(random(500)) >> println("A2 called")
def A3() = Rtimer(random(500)) >> println("A3 called")
def B1() = Rtimer(random(500)) >> println("B1 called")
def B2() = Rtimer(random(500)) >> println("B2 called")

-------- main program ------

(A1() >> A2(), B1()) >> (A3(), B2())

Timeout#

Write a program which calls the site M. If M responds within 1 seconds, print "OK" and halt, otherwise print "timed out" and halt. Ensure that your program never prints both "OK" and "timed out".

You can use this template to test your program:

def M() = Rtimer(random(500) + 750)

{- WRITE YOUR SOLUTION HERE -}

(click for solution)
def M() = Rtimer(random(500) + 750)

-------- main program ------

  x >true> println("OK")
| x >false> println("timed out")

  <x<   M() >> true
      | Rtimer(1000) >> false

Fork-join#

Write a function which, given a list of sites, calls each site in the list in parallel and publishes a signal when all site calls have returned.

(click for solution)
def forkjoin([]) = signal
def forkjoin(f:rest) = (f(), forkjoin(rest)) >> signal

def example() = Rtimer(random(500)) >> println("called")
forkjoin([example, example, example, example])

Parallel Or#

Write a function which accepts a list of sites which return natural numbers and calls each site in parallel. If any site returns a value less than 100, immediately return that value. Otherwise, return the minimum value returned by any site.

(click for solution)
def f([]) = error("Non-empty list")
def f(g:[]) = g()
def f(g:rest) =
  val x = g()
  val y = f(rest)
  let(
      if(x < 100) >> x
    | if(y < 100) >> y
    | min(x, y)
  )

def example() = Rtimer(random(1000)) >> random(200) + 50
f([example, example, example, example])

Retry#

Write a function which, given a site taking no arguments, calls the site. If the site does not respond within 1 second, ignore its response and call the site again. Repeat this process until the site returns a value in under 1 second, and return that value.

(click for solution)
def retry(M) =
  val (ok,value) =
      M() >x> (true,x)
    | Rtimer(1000) >> (false,signal)
  println("Calling ...") >> 
  if ok then value
  else retry(M)

def example() = Rtimer(500+random(1000)) >> "ok"
retry(example)

Routing#

First-N from channel#

Write a function which, given a number (n) and a channel (c), returns a list of the first n values received from c.

(click for solution)
def firstN(0, c) = []
def firstN(n, c) = c.get() >x> x:firstN(n-1, c)

val c = Buffer()
  firstN(5, c)
| signals(10) >> c.put(random(10)) >> stop

Unique from channel#

Write a function which, given a channel, publishes every value received over the channel, omitting repeated values (so each value published is unique). Hint: use a Set to record the values seen in the channel.

(click for solution)
def unique(c) =
  val seen = Set()
  def loop() =
    c.get() >x>
    if seen.contains(x)
    then loop()
    else x | seen.add(x) >> loop()
  loop()

val c = Buffer()
  unique(c)
| (signals(100) >> c.put(random(10)) >> stop; c.close())

Multi-value timeout#

Write a program which calls a definition f, which may publish multiple values. Publish all of the values published by f() within 1 second, and then terminate the call to f.

(click for solution)
{- Example f -}
def f() = signals(10) >> random(2000) >x> Rtimer(x) >> x

{- Main program -}
val c = Buffer()
repeat(c.get) <<
    f() >x> c.put(x) >> stop
  | Rtimer(1000) >> c.closenb()

Quorum#

Write a function which, given a number (n) and a list of sites, calls every site in the list in parallel and returns a list of the first n responses. The order of items in the returned list is unimportant.

(click for solution)
{- Get the first n items from channel c -}
def firstN(0, c) = []
def firstN(n, c) = c.get() >x> x:firstN(n-1, c)

{- Return a list of the first n responses from sites -}
def quorum(n, sites) =
  val c = Buffer()
  firstN(n, c) | each(sites) >s> c.put(s()) >> stop
  
{- Demo/Test -}
def example() = random(100) >x> Rtimer(x) >> x
quorum(3, [example, example, example, example])

First-N publications#

Write a program which calls a definition f, which may publish multiple values. Publish the first 10 values published by f(), and then terminate the call to f.

(click for solution)
{- Publish first n values received on c, then release s -}
def allow(0, c, s) = c.closenb() >> s.release() >> stop
def allow(n, c, s) = c.get() >x> ( x | allow(n-1, c, s) )

{- Example f -}
def f() = signals(10) >> random(1000) >x> Rtimer(x) >> x

{- Main program -}
val c = Buffer()
val s = Semaphore(0)
allow(5, c, s) <<
  s.acquire() | f() >x> c.put(x) >> stop

Applications#

Auction#

Write a function which conducts an auction given a list of "bidder" sites and a starting bid. An auction consists of a number of bidding rounds performed in sequence. A bidding round consists of calling every bidder site in parallel, passing the current maximum bid. Each bidder site may return a higher value (a bid). The first caller to return a higher bid sets a new maximum bid for the next round. If no callers return a bid within 5 seconds, the auction (and round) ends. Your function should return the value of the winning bid.

(click for solution)
def auction(bidders, max) =
  val (done, bid) =
    Rtimer(5000) >> (true, max)
    | each(bidders) >bidder>
      bidder(max) >bid>
      if(bid > max) >>
      (false, bid)
  println("Current bid: " +  max) >>
  if done then max else auction(bidders, bid)
  
def bidder(max)(n) = if(n < max) >> Rtimer(random(2000)) >> n + 1
auction(map(lambda (_) = bidder(random(10)), range(0,10)), 1)

Counter#

Write a program with three functions: inc, dec, and read. Each of these functions modifies a shared state which is a natural number (n), initially = 0. When inc is called, increment n. When dec is called, decrement n. When read is called, publish the value of n. Each of these functions must act atomically, so that the expression inc() | dec() is guaranteed to leave the counter state unchanged after it completes.

Hint: use a semaphore to control access to the shared state.

(click for solution)
val n = Ref(0)
val lock = Semaphore(1)

def inc() =
  lock.acquire() >>
  n := n? + 1 >>
  lock.release()

def dec() =
  lock.acquire() >>
  n := n? - 1 >>
  lock.release()

def read() =
  lock.acquire() >>
  n? >out>
  lock.release() >>
  out

inc() >> inc() >> read()

Two-way load balancer#

Write a function which takes an input channel (in), an output channel (out), and two sites (P and Q) as arguments. The function must repeatedly read an input value from in, call either P or Q with the value (alternating between the two), and write the result to out. The order values are written to the output channel must correspond to the order values were received on the input channel.

(click for solution)
def balance(in, out, P, Q) =
  val p = Buffer()
  val q = Buffer()
  def write(a, b) = out.put(a()) >> write(b,a)
  def read(a, b) = in.get() >x> ( a(x) >> stop | read(b, a) )
  write(p.get, q.get) | read(compose(p.put, P), compose(q.put, Q))

val in = Buffer()
val out = Buffer()
def compute(x) = x*x
def metronomeTN(t, n) = n | Rtimer(t) >> metronomeTN(t, n+1)
balance(in, out, compute, compute)
| repeat(out.get)
| metronomeTN(500, 1) >n> in.put(n) >> stop

N-way load balancer#

Write a function which takes an input channel (in), an output channel (out), and a list of sites (ps) as arguments. The function must repeatedly read an input value from in, call one of the sites in ps with the value (using each site in the list in turn), and write the result to out. The order values are written to the output channel must correspond to the order values were received on the input channel.

(click for solution)
def balance(in, out, ps) =
  val bs = map(ignore(Buffer), ps)
  def write(b:bs) = out.put(b.get()) >> write(append(bs, [b]))
  def read((p,b):pbs) = in.get() >x> ( b.put(p(x)) >> stop | read(append(pbs, [(p,b)])) )
  write(bs) | read(zip(ps,bs))

val in = Buffer()
val out = Buffer()
def compute(x) = x*x
def metronomeTN(t, n) = n | Rtimer(t) >> metronomeTN(t, n+1)
balance(in, out, [compute, compute, compute, compute])
| repeat(out.get)
| metronomeTN(500, 1) >n> in.put(n) >> stop

Monitor actor#

Write a program with two functions: dec and wait. These functions share a state which is a natural number (n), initially = 5. When dec() is called, decrement n. When wait() is called, wait until n = 0 and then publish a signal. Write the program without using Ref.

Hint: create a single process running in the background which manages the shared state.

(click for solution)
val m = Buffer()
type Message = Dec() | Wait(_)
def actor(n, waiters) =
  def on(Dec()) =
    if n = 1 then join(waiters)
    else actor(n-1, waiters)
  def on(Wait(callback)) =
    if n = 0 then callback()
    else actor(n, callback:waiters)
  on(m.get())

def dec() = m.put(Dec())
def wait() =
  val b = Semaphore(0)
  b.acquire() | m.put(Wait(b.release)) >> stop

  actor(5, []) >> stop
| dec() >> stop
| dec() >> stop
| dec() >> stop
| dec() >> stop
| Rtimer(1000) >> dec() >> stop
| wait() >> "Zero!"

Parallel Sieve of Eratosthenes#

Eratosthenes's Sieve is an algorithm for finding prime numbers. In an imperative setting, it works as follows:
  1. start with a list of natural numbers from 2 to n (some number)
  2. remove and output the first number of the list (call it p)
  3. remove all multiples of p from the list
  4. repeat steps 2 and 3 until the list is empty

Note that step 3 can begin removing multiples starting with p squared (all lower multiples are already removed), and once p > square root of n, the remaining numbers in the list are prime. We can parallelize this algorithm in two easy ways:

  1. step 3 can be done in parallel for all multiples of p
  2. given a list of prime numbers, step 2 can be done in parallel for those prime numbers

Implement a parallel version of this algorithm using these facts.

Note: you can compute the "floored" square root of a number like this:

class Math = java.lang.Math
Math.floor(Math.sqrt(5))

(click for solution)
def sqrt(n) =
  class Math = java.lang.Math
  Math.floor(Math.sqrt(n))

def primes(n) =
  def candidates(n) = rangeBy(3, n+1, 2)
  def sieve(1, _) = []
  def sieve(n, set) =
    def remove(p) = joinMap(set.remove, rangeBy(p*p, n, p))
    sieve(sqrt(n), set) >ps>
    joinMap(remove, ps) >>
    2:filter(set.contains, candidates(n))
  val set = Set()
  joinMap(set.add, candidates(n)) >>
  sieve(n, set)

primes(100)

Here is an alternate solution which uses logical time for synchronization:

(click for alternate solution)
def primes(n) =
  {- publish every dth number from i to n,
     one per logical time unit -}
  def walk(i, d) =
    if i >= n then stop
    else i | Ltimer(1) >> walk(i+d, d)
  val seen = Set() -- visited non-prime numbers
  {- walk down the list of odd numbers; when
     a prime number is encountered, start a new
     process to find multiples of that prime -}
  2 | walk(3, 2) >i> if(~seen(i)?) >> (
    i | walk(i*i, i) >j> seen(j) := true >> stop
  )

primes(1000)

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-1) was last changed on 14-Mar-2009 15:13 by AdrianQuark