Replicated WorkersThis 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 workersThis week's exercise is to write a primenumber 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 spacesMake an implementation in JR using whatever structures seem most suitable (e.g. channels, shared data structures). Linda in JavaIntroduction: A TupleSpace SimulationKramer and Magee provide a version of tuplespaces implemented below. Look at the packages and an example SupervisorWorker 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 webpage not work, here is a local copy of the SupervisorWorker. Primes using the tuplespace simulationFirst, implement the same prime finding algorithm as in JR but this time using the Kramer and Magee tuplespace 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 tuplespace. You might even optimiseaway the tuplespace altogether... Erlang: Simple ExercisesHere 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 guideFollow the quickstart guide from erlang.org. This explains how to use the erlang system. Sequential Programming ExercisesBasic RecursionThese 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.
Tail recursionThe factorial function from the quickstart 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(N1). It is not tail recursive because the recursive call fac(N1) is not the whole result – it has to be multiplied by N. Here is a tail recursive version. It uses a twoargument 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(N1,N*A). This is tail recursive, since the result of the recursive call fac(N1,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
Concurrent Programming ExercisesStarting Processes and Communication
Dynamic Process Creation: Prime SieveImplement the prime number seive using the usual pipeline algorithm.
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 ErlangTo 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, 20Aug2013 16:01:20 CEST
