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.

#### Table of Contents

- Functional Programming
- List length
- List repetition
- Basic tree traversal
- Tree levels
- Find Files
- Towers of Hanoi
- Idioms
- For-each
- Priority
- Barrier Synchronization
- Timeout
- Fork-join
- Parallel Or
- Retry
- Routing
- First-N from channel
- Unique from channel
- Multi-value timeout
- Quorum
- First-N publications
- Applications
- Auction
- Counter
- Two-way load balancer
- N-way load balancer
- Monitor actor
- Parallel Sieve of Eratosthenes

### Functional Programming#

#### List length#

Write a function which, given a list, returns the number of elements in the list.#### 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]`.

#### 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()))))

#### 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()))))

#### 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("/")

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

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

#### 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")

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

#### 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 -}

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

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

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

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

#### 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.*

#### 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.#### 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.#### 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.*

#### Parallel Sieve of Eratosthenes#

Eratosthenes's Sieve is an algorithm for finding prime numbers. In an imperative setting, it works as follows:- start with a list of natural numbers from 2 to n (some number)
- remove and output the first number of the list (call it p)
- remove all multiples of p from the list
- 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:

- step 3 can be done in parallel for all multiples of p
- 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))

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