This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Re: Wrapping my head around Actors

3 replies
Jens Alfke
Joined: 2009-01-30,
User offline. Last seen 42 years 45 weeks ago.

On Feb 2, 2009, at 5:11 PM, Erik Engbrecht wrote:
re: Actors as state machineAbsolutely: Refactoring Scala Actors

That's an interesting article, but it's about treating the implementation of the Actor class as a state machine (which is also valid), whereas I'm taking about modeling the execution of Actor-based application code as a state machine.
re: deadlockYup.  Although the situation isn't as severe with event-based (react) actors as it is with threads because (1) actors are much lighter weight and (2) you can cleanly terminate a stuck event-based actor, but you can't easily/safely terminate a stuck thread.

Good points. But I'm most concerned with avoiding deadlock entirely. My hunch is that it will be easier than in traditional threading because the flow of control is represented by actor objects, which means it ties in directly to the data and code being run; whereas in traditional threading the threads tend to be independent of data and code, which makes them this troublesome extra dimension that doesn't fit into structured-programming or OOP methodology.
—Jens
Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
actors
Hello

For didactical reasons,
I've been trying to come up with a simple correct implementation of actors.

Apart from the fact that it could use a more efficient data structure as List,
I would be interested in any comments for improvement.

1) Maybe I'm still making things more complex than needed
2) Maybe it is not correct

and

3) Does it make sense to make use of the X type parameter (the official actors use Any)
4) Does it make sense to introduce variance Actor[-X,+Y] (cfr the variance of PartialFunction)


thx

// synchronized variable of type Y
// that is the result of applying a partial function of type PartialFunction[X,Y]
// to a value of type X

class SyncPartialVar[X,Y](pf: PartialFunction[X,Y]) {
  private[this] var y : Y = _
  def existsFor = pf.isDefinedAt(_)
  def set(x: X) = synchronized {
    y = pf(x)
    notify
  }
  def get = synchronized {
    wait
    y
  }
}

// actor

abstract class Actor[X,Y] extends Runnable {

  private var xs : List[X] = Nil
  private var spys : List[SyncPartialVar[X,Y]] = Nil

  def act() = run()

  def !(x: X) = synchronized {
    val lspys = spys.filter(_.existsFor(x))
    if(!lspys.isEmpty) {
      val lspy = lspys.last
      spys = spys.filter(_ != lspy)
      lspy set x
    } else {
      xs = x :: xs
    }
  }

  def receive(pf: PartialFunction[X,Y]) = synchronized {
    val lxs = xs.filter(pf.isDefinedAt(_))
    if(!lxs.isEmpty) {
      val lx = lxs.last
      xs = xs.filter(_ != lx)
      pf(lx)
    } else {
      val spy = new SyncPartialVar(pf)
      spys = spy :: spys
      spy get
    }
  }
 
}

// test

sealed abstract class PingPong
case class Ping(actor: Actor[PingPong,Unit]) extends PingPong
case class Pong(actor: Actor[PingPong,Unit]) extends PingPong
case class Missed(actor: Actor[PingPong,Unit]) extends PingPong

class PingPongActor(name: String) extends Actor[PingPong,Unit] {
  var isPlaying = true
  def ping(actor: Actor[PingPong,Unit]) {
    println(name + " pings")
    actor ! Ping(this)
  }
  def pong(actor: Actor[PingPong,Unit]) {
    println(name + " pongs")
    actor ! Pong(this)
  }
  def missed(actor: Actor[PingPong,Unit]) = {
    println(name + " misses")
    actor ! Missed(this)
  }
  def run() {
    if(isPlaying) {
      receive {
        case Ping(actor) =>
          if (Math.random < 0.8) { pong(actor) }
          else { isPlaying = false ; missed(actor) }
        case Pong(actor) =>
          if (Math.random < 0.8) { ping(actor) }
          else { isPlaying = false ; missed(actor) }
        case Missed(actor) =>
          { isPlaying = false ; println(name + " wins (game over)") }
      }
    }
  }
}

object Main01 {
  def main(args: Array[String]) {
    val pingActor = new PingPongActor("ping")
    val pongActor = new PingPongActor("pong")
    pingActor ping pongActor
    while(pingActor.isPlaying || pongActor.isPlaying) {
      pongActor.act()
      pingActor.act()
    }
  }
}

--
  __~O
 -\ <,
(*)/ (*)

reality goes far beyond imagination

Luc Duponcheel
Joined: 2008-12-19,
User offline. Last seen 34 weeks 3 days ago.
Re: actors
sorry forget about the email,
gonna look at the code again

On Mon, Feb 23, 2009 at 3:50 PM, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Hello

For didactical reasons,
I've been trying to come up with a simple correct implementation of actors.

Apart from the fact that it could use a more efficient data structure as List,
I would be interested in any comments for improvement.

1) Maybe I'm still making things more complex than needed
2) Maybe it is not correct

and

3) Does it make sense to make use of the X type parameter (the official actors use Any)
4) Does it make sense to introduce variance Actor[-X,+Y] (cfr the variance of PartialFunction)


thx

// synchronized variable of type Y
// that is the result of applying a partial function of type PartialFunction[X,Y]
// to a value of type X

class SyncPartialVar[X,Y](pf: PartialFunction[X,Y]) {
  private[this] var y : Y = _
  def existsFor = pf.isDefinedAt(_)
  def set(x: X) = synchronized {
    y = pf(x)
    notify
  }
  def get = synchronized {
    wait
    y
  }
}

// actor

abstract class Actor[X,Y] extends Runnable {

  private var xs : List[X] = Nil
  private var spys : List[SyncPartialVar[X,Y]] = Nil

  def act() = run()

  def !(x: X) = synchronized {
    val lspys = spys.filter(_.existsFor(x))
    if(!lspys.isEmpty) {
      val lspy = lspys.last
      spys = spys.filter(_ != lspy)
      lspy set x
    } else {
      xs = x :: xs
    }
  }

  def receive(pf: PartialFunction[X,Y]) = synchronized {
    val lxs = xs.filter(pf.isDefinedAt(_))
    if(!lxs.isEmpty) {
      val lx = lxs.last
      xs = xs.filter(_ != lx)
      pf(lx)
    } else {
      val spy = new SyncPartialVar(pf)
      spys = spy :: spys
      spy get
    }
  }
 
}

// test

sealed abstract class PingPong
case class Ping(actor: Actor[PingPong,Unit]) extends PingPong
case class Pong(actor: Actor[PingPong,Unit]) extends PingPong
case class Missed(actor: Actor[PingPong,Unit]) extends PingPong

class PingPongActor(name: String) extends Actor[PingPong,Unit] {
  var isPlaying = true
  def ping(actor: Actor[PingPong,Unit]) {
    println(name + " pings")
    actor ! Ping(this)
  }
  def pong(actor: Actor[PingPong,Unit]) {
    println(name + " pongs")
    actor ! Pong(this)
  }
  def missed(actor: Actor[PingPong,Unit]) = {
    println(name + " misses")
    actor ! Missed(this)
  }
  def run() {
    if(isPlaying) {
      receive {
        case Ping(actor) =>
          if (Math.random < 0.8) { pong(actor) }
          else { isPlaying = false ; missed(actor) }
        case Pong(actor) =>
          if (Math.random < 0.8) { ping(actor) }
          else { isPlaying = false ; missed(actor) }
        case Missed(actor) =>
          { isPlaying = false ; println(name + " wins (game over)") }
      }
    }
  }
}

object Main01 {
  def main(args: Array[String]) {
    val pingActor = new PingPongActor("ping")
    val pongActor = new PingPongActor("pong")
    pingActor ping pongActor
    while(pingActor.isPlaying || pongActor.isPlaying) {
      pongActor.act()
      pingActor.act()
    }
  }
}

--
  __~O
 -\ <,
(*)/ (*)

reality goes far beyond imagination




--
  __~O
 -\ <,
(*)/ (*)

reality goes far beyond imagination

Meredith Gregory
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Re: actors
Luke,

i've been wondering if the transition system defined by Caires in this paper could be a good beginning for pinning down an operational semantics for actors. More specifically, the correspondence runs roughly as
  • Caires' network ~ actor
  • Caires' threads restricted to a given network ~ actor's mbox
  • Caires' stores restricted to a given network ~ actor's local state
There are some differences in the models that need to be nailed down; but, essentially Caires has a given a computational agent in terms of
  • calls to an agent come in on a principal port
  • calls can be processed concurrently
A key difference between actors and Caires' networks is that
  • the local store is potentially concurrently accessed by the threads and only well-typedness guarantees good properties like atomicity or isolation of method-body definitions
i've not thought hard about it, but it might even be possible to devise a typing discipline (= collection of types in the existing type system) that guarantees that well-typed networks behave as actors.

The reason i mention this in the context of your question is that you can more or less read off the scala implementation from page 4 of the paper.

Best wishes,

--greg

On Mon, Feb 23, 2009 at 12:40 PM, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
sorry forget about the email,
gonna look at the code again

On Mon, Feb 23, 2009 at 3:50 PM, Luc Duponcheel <luc [dot] duponcheel [at] gmail [dot] com> wrote:
Hello

For didactical reasons,
I've been trying to come up with a simple correct implementation of actors.

Apart from the fact that it could use a more efficient data structure as List,
I would be interested in any comments for improvement.

1) Maybe I'm still making things more complex than needed
2) Maybe it is not correct

and

3) Does it make sense to make use of the X type parameter (the official actors use Any)
4) Does it make sense to introduce variance Actor[-X,+Y] (cfr the variance of PartialFunction)


thx

// synchronized variable of type Y
// that is the result of applying a partial function of type PartialFunction[X,Y]
// to a value of type X

class SyncPartialVar[X,Y](pf: PartialFunction[X,Y]) {
  private[this] var y : Y = _
  def existsFor = pf.isDefinedAt(_)
  def set(x: X) = synchronized {
    y = pf(x)
    notify
  }
  def get = synchronized {
    wait
    y
  }
}

// actor

abstract class Actor[X,Y] extends Runnable {

  private var xs : List[X] = Nil
  private var spys : List[SyncPartialVar[X,Y]] = Nil

  def act() = run()

  def !(x: X) = synchronized {
    val lspys = spys.filter(_.existsFor(x))
    if(!lspys.isEmpty) {
      val lspy = lspys.last
      spys = spys.filter(_ != lspy)
      lspy set x
    } else {
      xs = x :: xs
    }
  }

  def receive(pf: PartialFunction[X,Y]) = synchronized {
    val lxs = xs.filter(pf.isDefinedAt(_))
    if(!lxs.isEmpty) {
      val lx = lxs.last
      xs = xs.filter(_ != lx)
      pf(lx)
    } else {
      val spy = new SyncPartialVar(pf)
      spys = spy :: spys
      spy get
    }
  }
 
}

// test

sealed abstract class PingPong
case class Ping(actor: Actor[PingPong,Unit]) extends PingPong
case class Pong(actor: Actor[PingPong,Unit]) extends PingPong
case class Missed(actor: Actor[PingPong,Unit]) extends PingPong

class PingPongActor(name: String) extends Actor[PingPong,Unit] {
  var isPlaying = true
  def ping(actor: Actor[PingPong,Unit]) {
    println(name + " pings")
    actor ! Ping(this)
  }
  def pong(actor: Actor[PingPong,Unit]) {
    println(name + " pongs")
    actor ! Pong(this)
  }
  def missed(actor: Actor[PingPong,Unit]) = {
    println(name + " misses")
    actor ! Missed(this)
  }
  def run() {
    if(isPlaying) {
      receive {
        case Ping(actor) =>
          if (Math.random < 0.8) { pong(actor) }
          else { isPlaying = false ; missed(actor) }
        case Pong(actor) =>
          if (Math.random < 0.8) { ping(actor) }
          else { isPlaying = false ; missed(actor) }
        case Missed(actor) =>
          { isPlaying = false ; println(name + " wins (game over)") }
      }
    }
  }
}

object Main01 {
  def main(args: Array[String]) {
    val pingActor = new PingPongActor("ping")
    val pongActor = new PingPongActor("pong")
    pingActor ping pongActor
    while(pingActor.isPlaying || pongActor.isPlaying) {
      pongActor.act()
      pingActor.act()
    }
  }
}

--
  __~O
 -\ <,
(*)/ (*)

reality goes far beyond imagination




--
  __~O
 -\ <,
(*)/ (*)

reality goes far beyond imagination




--
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland