Scala Actor Prime Sieve

Question

I'm a newish java coder who was recently told to check out scala for its concurrent implementation. I figured a simple (albeit not the best for illustrating concurrency) example might be to have actors solve the Sieve of Eratosthenes. I've cobbled something together thusfar, but I'm not really sure if the direction I'm going is even close to correct. Here's my current code:

import scala.actors.Actor
import scala.actors.Actor._
import Array._

class PrimeActor(val id: Int) extends Actor {

     //Runs one Prime of the Sieve of Eratosthenes
     def sieve(p: Int, list: Array[Int]) {
       var i = 1
       var place = 0
       while(list contains (i * p)) {
       place = list.indexOf(i * p)
       if (list(place) != 0) 
          list.update(place, 0)
       i += 1
       }
     }

   //Checks to see if there is a higher prime in the list
   //If so, creates a new actor to handle it and sends
   //it the list and the prime
   def findandCreateNextPrime(p: Int, list: Array[Int]){
      var i = 1
      var place = list.indexOf(p)
      while(list(place + i) == 0 && (p + i) <= list.last) {
         i += 1
      }
      val newP = list(place+i)

      if (list contains (p + i)) {
         if ((p + i) equals list.last) {
            print(list.last)
         } else {
            print(", ")
            val pA = new PrimeActor(newP)
            pA.start()
            pA ! (list(newP), list)
         } 
     } else {
     println("DONE")
    } 
  }

   //Actor behavior
   def act() {
      loop {
         react{
            case (recievedP: Int, recievedList: Array[Int]) =>
               print(recievedP)
               sieve(recievedP, recievedList)
               findandCreateNextPrime(recievedP, recievedList)
               exit()
         }
      }
   }
}

Any help or directional input would be greatly appreciated. Thanks!

Answer 1

In Scala you can write your code in a functional style. I suggest you to use it. Firstly forget about the Array, it is a mutable collection and mutable collections in scala are evil. Better use immutable collections as List. The same is to say about var. Try to use val where possible.
The simplest way to implement the sieve of Eratosthenes in Scala, I can guess, is the following:

import scala.annotations.tailrec

def sieve(until: Int): Seq[Int] = {
  @tailrec
  def loop(i: Int, primes: Seq[Int]): Seq[Int] = {
    // we reached the desired end
    if (i > until) primes
    else {
      // we already found a factor of this i
      if (primes exists(i % _ == 0)) loop(i + 2, primes)
      // we found a new prime
      else loop(i + 2, primes :+ i)
    }
  }
  // there is no prime smaller than 2
  if (until < 2) Seq.empty[Int]
  // starting with 3 has the advantage, we only need to check i + 2
  else loop(3, Seq.empty[Int] :+ 2)
}

If you just started using Scala this might be a litle confusing, but I will explain.
We want a sequence of all primes until a specific number. We define a recursive function, which will check every second number if it is a prime or not. Because it is tailrecursive, the complier will optimate it to a for-comprehension, so we don't need to bother about StackOverflows. If our counter passes the maximum (until), we return the primes, we detected. This is our recursion-anchor. Otherwise we check wether we found a prime, which is a factor of our curent i. If there is one, we just skip to the next candidate, else we add i to our primes and go on the the next candidate.
Note: The annotation is not necesarry, but if it exists, the compiler while warn you, if the function is not tailrecursive.

Using my suggested code leads us to the problem, you can't use concurency anymore. A good introduction for concurency in scala, is a chapter from Programming Scala. They solved the sleeping barber problem via concurency. Here is a link to their solution.