Replicated Workers

This exercise is mainly about programming in the replicated worker style, with or without tuple spaces. There are three main exercises, one using a tuplespace implementation in Java, one using JR but without any tuple spaces at all. Then follow a few simple excercises to get you started with Erlang. And finally, the replicated worker exercise in Erlang.

Finding the first n primes using replicated workers

This week's exercise is to write a prime-number generator using replicated workers.

The idea of the algorithm is as follows: the job pool (e.g. a tuple space) contains candidate prime numbers. The master process initialises the job pool with the first two primes e.g.:

out("Prime", pair(1,2));
out("Prime", pair(2,3));

and the first candidate prime

out("Candidate", 5);

Workers remove the next candidate and test whether it is a prime. To do this, the workers must determine whether the candidate is divisible by any of the numbers in the range [2 .. floor(sqrt candidate)]. Actually it is sufficient to check all the prime numbers in the above range - but that solution is a bit harder!

Once a worker has determined whether a candidate is a prime, it outputs the result, e.g.,

out("Result", pair(5,True));

The master process collects results and prints out primes.

Implement using JR without explicit tuple spaces

Make an implementation in JR using whatever structures seem most suitable (e.g. channels, shared data structures).

Linda in Java

Introduction: A Tuple-Space Simulation

Kramer and Magee provide a version of tuplespaces implemented below. Look at the packages and an example Supervisor-Worker program providing you with an implementation of tuple spaces in Java and an example of their use. (Download, compile and run them).

Should the original web-page not work, here is a local copy of the Supervisor-Worker.

Primes using the tuple-space simulation

First, implement the same prime finding algorithm as in JR but this time using the Kramer and Magee tuple-space simulation

Once you have got the algorithm working, you might like to consider optimising your algorithm by keeping a global array of the primes, together with a count of the number found so far, to minimise the number of read operations from the tuple-space. You might even optimise-away the tuple-space altogether...

Erlang: Simple Exercises

Here are some simple exercises to get you started with Erlang. If you have not programmed in a functional language, pay particular attention to the exercises about lists.

The quick start guide

Follow the quick-start guide from erlang.org. This explains how to use the erlang system.

Sequential Programming Exercises

Basic Recursion

These exercises are about simple recursion over natural numbers.

Suppose that the weekly income of "Dave's Fish and Chip Shop" is given by some function sales which takes a week number as an argument and returns the income for that week. Let us use the following function to approximate this (the definition is not important):

sales(N) ->  (N + 31) rem 7  +  (N + 1) rem 5.
  1. Define a function which given a week number n returns the number of weeks in the range 0,...,n for which the sales were 0.
  2. Define a function which given a week number n and a number s returns the number of weeks in the range 0,...,n for which the sales where higher than s.
  3. Define the function allZeroPeriod(N) such that allZeroPeriod n tests whether the sales for every week in the range 0 to n is zero.
  4. [Harder] Define a function which given a week number n finds the week in the range 0,...,n which had the maximum sales. Don't forget that you can define helper functions.

Tail recursion

The factorial function from the quick-start guide has a simple recursive form. But it is not the most efficient structure. To write recursive functions efficiently in Erlang they must be tail recursive. A function is tail recursive (roughly speaking) if for any recursive call the answer returned by the recursive call is the whole answer.

The following version of factorial is not tail recursive:

-module(test).
-export([fac/1]).

fac(0) -> 1;
fac(N) -> N * fac(N-1).

It is not tail recursive because the recursive call fac(N-1) is not the whole result – it has to be multiplied by N.

Here is a tail recursive version. It uses a two-argument version of factorial. The second argument of fact/2 accumulates the result:

-module(test).
-export([fac/1]).
fac(N) -> fac(N,1).

fac(0,A) -> A;
fac(N,A) -> fac(N-1,N*A).

This is tail recursive, since the result of the recursive call fac(N-1,N*A) is the whole result.

This works by accumulating the result in the second parameter. Tail recursive functions are important since they can be compiled to run very efficiently. This is particularly important when writing functions which will be used as processes in Erlang.

Problem:Rewrite one of your non tail recursive solutions above to be tail recursive.

Recursion Over Lists

  1. Write a function increasing which takes any list of pairs of numbers, and returns the list of only those pairs from the list for which the first element is smaller than the second element.
  2. Write a function changePairs which takes any list of pairs of numbers, and returns the list in which all of the second elements have been replaced by the largest second element.

    changePairs [{1,2},{7,5},{6,3}] gives [{1,5},{7,5},{6,5}]

Concurrent Programming Exercises

Starting Processes and Communication

  1. Write a program which creates a process and sends a message to that process. The created process should print out the message.
  2. Modify the above program so that you can send any number of messages to the process, each of which will be printed out.
  3. Further modify the program so that it swaps adjacent messages, to if you rend it the sequence 1, 2, 3, 4 it will print out 2, 1, 4, 3.

Dynamic Process Creation: Prime Sieve

Implement the prime number seive using the usual pipeline algorithm.

  • The main process creates the first filter process and sends it a sequence of natural numbers starting with 2.
  • A printer process writes the prime numbers that it receives to the output.
  • Each process in the filter pipeline has the following behaviour: it sends the first number that it receives to the printer process, and keeps a copy of that number P. It creates the next process in the pipeline, and then forwards every number it receives which is not divisible by the first number P (use the "rem" operator).

It is a good idea to decide in advance how far you want to search, and to terminate the filters when you are finished.

Implementation using Tuplespaces in Erlang

To attempt the replicated workers using Erlang, download a copy of the tuplespace module ts.beam. This is a compiled version of assignment 3. It provides operations in, out and new. Use the following skeleton code:

-module(primes).
-export([primes/1, ... ]). % all spawn functions go here
-import(ts,[in/2,out/2,new/0]). 
-import(math,[sqrt/1]).

% A read operation implemented using in and out.
read(TS,Pat) -> 
   R = in(TS,Pat), % get matching tuple,    
   out(TS,R),      % put it back, and 
   R.              % return its value.

% Math utilities
limit(N) -> trunc(sqrt(N)).

primes(N) -> % compute the first N primes, starting with 2.
   TS = new(),               % Create the tuplespace 
   No_of_Workers = 5,        % let's not kill the machine!
   initialise(TS),           % initialise the tuplespace   
   start_workers(No_of_Workers,N,TS), % start up the worker pool
   getResults(N,TS).         % print results  

initialise(TS) -> out(TS,{prime, 1, 2}), % the "first" prime is 2
                  out(TS,{nextCandidate, 3}).

start_workers(... ) -> ... .

getResults( ... ) -> ... 
...
Last modified: Tuesday, 20-Aug-2013 16:01:20 CEST
COMPUTER SCIENCE AND ENGINEERING - Chalmers University of Technology and Göteborg University
SE-412 96 Göteborg, Sweden - Tel: +46 (0)31- 772 1000