Re: Wrapping my head around 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

sorry forget about the email,
gonna look at the code again

On Mon, Feb 23, 2009 at 3:50 PM, Luc Duponcheel <luc.duponcheel@gmail.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

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.duponcheel@gmail.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.duponcheel@gmail.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