Recursion with actors?

[Forgot to CC list.]

The challenge is the actor can't block waiting for an answer from itself.

I came up with something that works by the actor re-forwarding
messages to itself while it waits for partial computations to finish.

import scala.actors.Actor._
import scala.actors.Future

case class Fib(n: Int)
case class Add(a: Future[Int], b: Future[Int])
case class Add2(a: Int, b: Future[Int])

val fib = actor { loop { react {
case Fib(n) if n <= 2 => reply(1)
case Fib(n) =>
val a = self !! (Fib(n-1), { case x => x.asInstanceOf[Int] })
val b = self !! (Fib(n-2), { case x => x.asInstanceOf[Int] })
self.forward(Add(a, b))
case Add(a, b) if a.isSet && b.isSet =>
reply(a() + b())
case Add(a, b) if a.isSet =>
self.forward(Add2(a(), b))
case Add(a, b) if b.isSet =>
self.forward(Add2(b(), a))
case Add(a, b) =>
self.forward(Add(a, b))
case Add2(a, b) if b.isSet =>
reply(a + b())
case Add2(a, b) =>
self.forward(Add2(a, b))
} } }

scala> fib !? Fib(8)
res0: Any = 21

scala> fib !? Fib(20)
res1: Any = 6765

scala> fib !? Fib(21)
res2: Any = 10946

It's pretty slow.

On Sat, Mar 14, 2009 at 10:49 AM, Danny Coates wrote:
> Hi,
>
> I'm a Scala and actor based concurrency noob so I've been implementing
> some simple algorithms as practice, but one of the simplest problems
> is tripping me up, Fibonacci numbers. The serial, recursive algorithm
> is dead simple:
>
> def fib(n: Int): Int = {
>        if(n <= 2) 1
>        else fib(n - 1) + fib(n - 2)
> }
>
> But I can't for the life of me figure out how to do this with "react"
> based actors. How do you do the "else" case above, with the recursion
> and then adding the results? And in general, how does one deal with
> such recursion with react actors?
>
> I hope I'm missing something obvious. If someone has an answer I think
> it would be good example code for the website.
>
> Thanks,
> Danny
>

Ah, ok. Your use of Future was the key that I was missing. Thank you.

The complexity of your solution leads me to believe that actors may
not be a good solution to this type of problem. Is there a recommended
way to do parallel calculations like this in Scala? In Java I would
probably use something like FJTasks.

Thanks,
Danny

On Sun, Mar 15, 2009 at 4:13 AM, J Robert Ray wrote:
> [Forgot to CC list.]
>
> The challenge is the actor can't block waiting for an answer from itself.
>
> I came up with something that works by the actor re-forwarding
> messages to itself while it waits for partial computations to finish.
>
> import scala.actors.Actor._
> import scala.actors.Future
>
> case class Fib(n: Int)
> case class Add(a: Future[Int], b: Future[Int])
> case class Add2(a: Int, b: Future[Int])
>
> val fib = actor { loop { react {
>  case Fib(n) if n <= 2 => reply(1)
>  case Fib(n) =>
>   val a = self !! (Fib(n-1), { case x => x.asInstanceOf[Int] })
>   val b = self !! (Fib(n-2), { case x => x.asInstanceOf[Int] })
>   self.forward(Add(a, b))
>  case Add(a, b) if a.isSet && b.isSet =>
>   reply(a() + b())
>  case Add(a, b) if a.isSet =>
>   self.forward(Add2(a(), b))
>  case Add(a, b) if b.isSet =>
>   self.forward(Add2(b(), a))
>  case Add(a, b) =>
>   self.forward(Add(a, b))
>  case Add2(a, b) if b.isSet =>
>   reply(a + b())
>  case Add2(a, b) =>
>   self.forward(Add2(a, b))
> } } }
>
> scala> fib !? Fib(8)
> res0: Any = 21
>
> scala> fib !? Fib(20)
> res1: Any = 6765
>
> scala> fib !? Fib(21)
> res2: Any = 10946
>
> It's pretty slow.
>
> On Sat, Mar 14, 2009 at 10:49 AM, Danny Coates wrote:
>> Hi,
>>
>> I'm a Scala and actor based concurrency noob so I've been implementing
>> some simple algorithms as practice, but one of the simplest problems
>> is tripping me up, Fibonacci numbers. The serial, recursive algorithm
>> is dead simple:
>>
>> def fib(n: Int): Int = {
>>        if(n <= 2) 1
>>        else fib(n - 1) + fib(n - 2)
>> }
>>
>> But I can't for the life of me figure out how to do this with "react"
>> based actors. How do you do the "else" case above, with the recursion
>> and then adding the results? And in general, how does one deal with
>> such recursion with react actors?
>>
>> I hope I'm missing something obvious. If someone has an answer I think
>> it would be good example code for the website.
>>
>> Thanks,
>> Danny
>>
>

I believe you can fork-joing using scala.actor.Futures (which creates anonymous actors IIRC)

def doSomethingSmall(x : Input) : Output = //DO your small calculation
def combineInSomeMeaningfulWay(currentAggregateValue : Output, currentItem : Output) : Output = null //TODO - Define

val futureResults = for(i <- data) yield Futures.future(doSomethingSmall(i))  //This is the "fork" part

val finalResult = futureResults.foldLeft(initialValue) {
       (currentValue, futureResult) =>
                  combineInSomeMeaningfulWay(currentValue, futureResult()) //This is the "join" part
}

Anyway, I didn't write a fibonacci sequence version, but I hope it gets the point across.


-josh

On Sun, Mar 15, 2009 at 1:58 PM, Danny Coates <dannycoates@gmail.com> wrote:

Ah, ok. Your use of Future was the key that I was missing. Thank you.

The complexity of your solution leads me to believe that actors may
not be a good solution to this type of problem. Is there a recommended
way to do parallel calculations like this in Scala? In Java I would
probably use something like FJTasks.

Thanks,
Danny

On Sun, Mar 15, 2009 at 4:13 AM, J Robert Ray <jrobertray@gmail.com> wrote:
> [Forgot to CC list.]
>
> The challenge is the actor can't block waiting for an answer from itself.
>
> I came up with something that works by the actor re-forwarding
> messages to itself while it waits for partial computations to finish.
>
> import scala.actors.Actor._
> import scala.actors.Future
>
> case class Fib(n: Int)
> case class Add(a: Future[Int], b: Future[Int])
> case class Add2(a: Int, b: Future[Int])
>
> val fib = actor { loop { react {
>  case Fib(n) if n <= 2 => reply(1)
>  case Fib(n) =>
>   val a = self !! (Fib(n-1), { case x => x.asInstanceOf[Int] })
>   val b = self !! (Fib(n-2), { case x => x.asInstanceOf[Int] })
>   self.forward(Add(a, b))
>  case Add(a, b) if a.isSet && b.isSet =>
>   reply(a() + b())
>  case Add(a, b) if a.isSet =>
>   self.forward(Add2(a(), b))
>  case Add(a, b) if b.isSet =>
>   self.forward(Add2(b(), a))
>  case Add(a, b) =>
>   self.forward(Add(a, b))
>  case Add2(a, b) if b.isSet =>
>   reply(a + b())
>  case Add2(a, b) =>
>   self.forward(Add2(a, b))
> } } }
>
> scala> fib !? Fib(8)
> res0: Any = 21
>
> scala> fib !? Fib(20)
> res1: Any = 6765
>
> scala> fib !? Fib(21)
> res2: Any = 10946
>
> It's pretty slow.
>
> On Sat, Mar 14, 2009 at 10:49 AM, Danny Coates <dannycoates@gmail.com> wrote:
>> Hi,
>>
>> I'm a Scala and actor based concurrency noob so I've been implementing
>> some simple algorithms as practice, but one of the simplest problems
>> is tripping me up, Fibonacci numbers. The serial, recursive algorithm
>> is dead simple:
>>
>> def fib(n: Int): Int = {
>>        if(n <= 2) 1
>>        else fib(n - 1) + fib(n - 2)
>> }
>>
>> But I can't for the life of me figure out how to do this with "react"
>> based actors. How do you do the "else" case above, with the recursion
>> and then adding the results? And in general, how does one deal with
>> such recursion with react actors?
>>
>> I hope I'm missing something obvious. If someone has an answer I think
>> it would be good example code for the website.
>>
>> Thanks,
>> Danny
>>
>

On Sun, Mar 15, 2009 at 10:58 AM, Danny Coates wrote:
> Ah, ok. Your use of Future was the key that I was missing. Thank you.
>
> The complexity of your solution leads me to believe that actors may
> not be a good solution to this type of problem. Is there a recommended
> way to do parallel calculations like this in Scala? In Java I would
> probably use something like FJTasks.

A single actor processes its messages serially, one message at a time.
So my example does not work in parallel.

I use java executors when I need to parallelize something and don't
need a messaging system.

This example doesn't need threads; it needs a better algorithm. ;-)
Like the Stream example modified for the Fibonacci sequence.

http://www.scala-lang.org/docu/files/api/scala/Stream.html