pony-lecture/ipr0gram-2.md at master · sylvanc/pony-lecture

Actor-Model Programming #2

Let's recap!

The actor-model unifies data structures, functions and concurrency in a single concept.

The actor-model was invented by Carl Hewitt in 1973.

Gul Agha's 1985 dissertation developed a foundational model which is the basis of all actor-model programming languages.

Actors make parallel programs easy.

They combine data, functions, and units of execution.
They express _composable concurrency_.
In Pony, they are _safe_ and _consistent_.

Massively Parallel Ping Pong

Let's modify the PingPong example.

actor PingPong
  let _out: OutStream
  let _partner: PingPong
  let _print: Bool
  var _pings: U64 = 0
  var _pongs: U64 = 0

  new create(pings: U64, print: Bool, out: OutStream) =>
    _out = out
    _partner = PingPong.partner(this, print, out)
    _print = print

    for i in Range(0, pings) do
      _partner.ping()
    end

  new partner(that: PingPong, print: Bool, out: OutStream) =>
    _out = out
    _partner = that
    _print = print

  be ping() =>
    _pings = _pings + 1
    _partner.pong()
    if _print then _out.write(ANSI.green() + "Ping... " + ANSI.reset()) end

  be pong() =>
    _pongs = _pongs + 1
    if _print then _out.write(ANSI.red() + "Pong! " + ANSI.reset()) end

Instead of one pair of PingPong actors, this creates any number of pairs. They each send some number of pings to their partner.

Let's try 10 actors, each sending 10 pings and receiving 10 pongs...

That's about 200 messages.

Let's try 1000 actors, each sending 1000 pings and receiving 1000 pongs...

That's about 2 million messages.

Massively parallel programs in Pony are:

Easy to write.
Easy to scale.
Easy to reason about.

Live Coding in Pony

Let's extend the adventure game.

Concepts:

Traits.
Actors.
Constructors (named, sound, non-null).

Example #1

actor Person
  let _name: String
  let _things: SetIs[Thing iso]

  new create(name': String) =>
    """
    All fields must be initialised by the time a constructor is done.
    Until all fields are initialised, we can't do anything that might
    try to read a field.
    """
    _name = name'
    // name()
    _things = SetIs[Thing iso].create()

  new two_names(first: String, last: String) =>
    _name = first + " " + last
    _things = SetIs[Thing iso].create()

  fun name(): String =>
    _name

Conveniences:

Inline field initialisation.
Implicit constructors.

Example #1a

actor Person
  """
  When we initialise a field here, it's initialised the same way in every
  constructor.

  Specifying a type without a constructor as an expression implicitly uses the
  default constructor, which is create().
  """
  let _things: SetIs[Thing iso] = SetIs[Thing iso]
  let _name: String

  new create(name': String) =>
    _name = name'

  new two_names(first: String, last: String) =>
    _name = first + " " + last

What types can we send in messages?

Any _sendable_ type.
These are `iso`, `val` and `tag`.
`iso` is sendable because it is isolated. We know only one actor can read from or write to the object.
`val` is sendable because it is immutable. We know _no_ actor can write to the object, so it's safe for _any_ actor to read from it.
`tag` is sendable because it allows neither reading from nor writing to the object.

Concepts:

Behaviours have sendable parameters.
Destructive read.

Example #2

use "collections"

actor Person
  let _name: String
  let _things: SetIs[Thing iso] = SetIs[Thing iso]

  new create(name': String) =>
    _name = name'

  be take(thing: Thing iso) =>
  // be take(thing: Thing ref) =>
    """
    Behaviour parameters must be sendable.
    We use `consume` to perform a destructive read.
    """
    _things.set(consume thing)
    // _things.set(thing)

What's the type of consume thing?

`Thing iso^` The `^` means it's an _ephemeral_ type.

An ephemeral type indicates that the previous path to the object no longer exists.

A path is a sequence of field reads, starting from any actor, any local variable in any stack frame, or any message in any queue. For a `Thing iso`, we know there is only one `iso` path to the object, because it's isolated. So for a `Thing iso^` we know there are _no_ `iso` paths to the object! In fact, we know there are no _readable_ paths to the object.

What can we do with an iso^ that's different from an iso?

We can assign it to an `iso` variable, going from zero `iso` references to one `iso` reference.
We can send it to another actor, because we know we have not retained an `iso` reference.

Concepts:

Implementing a trait.
Function receiver capabilities.
Receiver capability subtyping.

Example #3

trait Thing
  fun tag name(): String

class CinemaTicket is Thing
  """
  A CinemaTicket implements the Thing trait.
  """
  let film: String

  new create(film': String) =>
    film = film'

  fun tag name(): String =>
  // fun ref name(): String =>
    """
    Since a CinemaTicket is a Thing, it must provide a name() function.
    """
    "cinema ticket"
    // film

Concepts:

Main actor.
Capability recovery.

Example #4

actor Main
  new create(env: Env) =>
    """
    Here's a program that creates one Person.
    Then we hand her a cinema ticket.
    We use `recover` to create an _isolated_ ticket.
    """
    let alice = Person("Alice")
    let ticket: CinemaTicket iso = recover CinemaTicket("Minions") end
    // let ticket = recover CinemaTicket("Minions") end
    alice.take(consume ticket)
    // alice.take(ticket)
    // alice.take(CinemaTicket("Minions"))

Concepts:

Actor constructors are asynchronous.
Causality.

Example #5

actor Main
  new create(env: Env) =>
    """
    Now we have a pub, and we want to put Alice in the pub.
    Because of causality, the first message Alice will ever send is to tell
    the pub she has arrived.
    And that message is a cause of every message Alice ever sends.
    """
    let pub = Place("Pub")
    let alice = Person("Alice", pub)

    // Are actors constructed in order?
    // let bob = Person("Bob", pub)
    // let charlotte = Person("Charlotte", pub)
    // let dave = Person("Dave", pub)
    // let elspeth = Person("Elspeth", pub)

Conveniences:

Union types.
Default arguments.
Single vs. multiple assignment variables.

Example #5a

actor Person
  let _name: String
  let _things: SetIs[Thing iso] = SetIs[Thing iso]
  var _place: Place

  new create(name: String, place: Place) =>
    _name = name
    _place = place
    _place.arrive(this, place)
    // _place.arrive(this, None)
    // _place.arrive(this)

Concepts:

Aliasing iso as tag.
Using identity to refer to mutable objects another actor holds.

Example #6

actor Main
  new create(env: Env) =>
    """
    We start by putting Alice and Bob in the pub.
    We give Alice a cinema ticket.
    Then we tell Alice to give her cinema ticket to Bob.
    """
    let pub = Place("Pub")
    let alice = Person("Alice", pub)
    let bob = Person("Bob", pub)

    let ticket: CinemaTicket iso = recover CinemaTicket("Minions") end
    let ticket_id: CinemaTicket tag = ticket
    // let ticket = recover CinemaTicket("Minions") end
    // let ticket_id = ticket

    alice.take(consume ticket)
    // alice.take(ticket)
    alice.give(bob, ticket_id)
    // alice.give(bob, ticket)

Concepts:

Ephemeral results.
Partial functions.
Exception handling.

Example #6a

actor Person
  let _name: String
  let _things: SetIs[Thing iso] = SetIs[Thing iso]
  var _place: Place

  be give(whom: Person, thing: Thing tag) =>
    """
    If we have the `thing` we're being asked to give away, extract it from our
    set of things and tell the recipient to take it.
    """
    try
      let thing' = _extract(thing)
      whom.take(consume thing')
    end

  fun ref _extract(thing: Thing tag): Thing iso^ ? =>
  // fun ref _extract(thing: Thing tag): Thing iso^ =>
    """
    Extract the `thing` from our set, returning an ephemeral type.
    What if it isn't there? What value can we return?
    """
    _things.extract(thing)

What happens if Alices has a Bicycle iso and she wants to know if the brakes are set?

digraph {
  rankdir=LR;
  node [fontsize="24"];
  edge [fontsize="18"];
  bicycle [shape=box]
  brakes [shape=box]
  set [shape=box]
  alice -> bicycle [label=iso]
  bicycle -> brakes [label=ref]
  brakes -> set: Bool [label=val]
}

This is an example of _viewpoint adaptation_. Alice has an `iso` bicycle because it's hers, the bicycle has `ref` brakes (where `ref` is a reference type: a plain-old mutable object) because the rider needs to be able to engage and disengage the brakes, and whether or not the brakes are engaged is a boolean.

Viewpoint adaptation goes from right to left.

digraph {
  rankdir=LR;
  node [fontsize="24"];
  edge [fontsize="18"];
  bicycle [shape=box]
  brakes [shape=box]
  set [shape=box]
  alice -> bicycle [label=iso]
  bicycle -> brakes [label=ref]
  brakes -> set: Bool [label=val]
}

`brakes` sees `set` as `val`.
`bicycle` sees `brakes` as `ref`.
`ref -> val = val`, so `bicycle` sees `set` as `val`.
`alice` sees `bicycle` as `iso`.
`iso -> val = val`, so `alice` sees `set` as `val`.
In other words: `iso -> (ref -> val) = val`.
Great! Alice can see whether or not the brakes are set.

What if Bob wants to see if know if Alice's brakes are set?

digraph {
  rankdir=LR;
  node [fontsize="24"];
  edge [fontsize="18"];
  bicycle [shape=box]
  brakes [shape=box]
  set [shape=box]
  alice -> bicycle [label=iso]
  bob -> bicycle [label=tag]
  bicycle -> brakes [label=ref]
  brakes -> set: Bool [label=val]
}

`brakes` sees `set` as `val`.
`bicycle` sees `brakes` as `ref`.
`ref -> val = val`, so `bicycle` sees `set` as `val`.
`bob` sees `bicycle` as `tag`.
`tag -> val = ⊥`, so `bob` can't see `set`.
In other words: `tag -> (ref -> val) = ⊥`.
Bob will have to ask Alice if her brakes are set.

Concepts:

Using val for sharing.

Example #7

trait Thing

trait EThing

actor Person
  let _name: String
  let _things: SetIs[Thing iso] = SetIs[Thing iso]
  let _ethings: SetIs[EThing val] = SetIs[EThing val]
  var _place: Place

  be download(ething: EThing val) =>
    """
    EThings can be shared. No need to consume.
    """
    _ethings.set(ething)

  be take(thing: Thing iso) =>
    _things.set(consume thing)

What if Alice and Bob want to read the same ebook?

digraph {
  rankdir=LR;
  node [fontsize="24"];
  edge [fontsize="18"];
  ebook [shape=box]
  text [shape=box]
  alice -> ebook [label=val]
  bob -> ebook [label=val]
  ebook -> text [label=ref]
}

`ebook` sees `text` as `ref`.
`alice` sees `ebook` as `val`.
`val -> ref = val`, so `alice` sees `text` as `val`.
`bob` sees `ebook` as `val`.
`val -> ref = val`, so `bob` sees `text` as `val`.
Alice and Bob can read the same ebook!

An ephemeral (or unaliased) type is annotated with ^.

The dual of an ephemeral type is a borrowed (or _aliased_) type, which is annotated with `!`. In non-generic code, `!` isn't needed, since we already know that `iso! == tag`.

In generic code, we often don't know the reference capability of a type.

In `Array[A]`, our type parameter `A` could have _any_ reference capability. `!` allows the programmer to specify an alias of an unknown reference capability, for example: `A!`

What about viewpoint adaptation through an unknown reference capability?

`val->ref = val`, but what's `A->B`?
It's: `A->B`
Arrow types allow the programmer to express viewpoint adaptation in the presence of unknown reference capabilities.

What if the unknown reference capability is the receiver?

`this->A`

Advanced concepts:

Type aliases.
Generic types.
Generic functions.
Operator overloading.
Viewpoint adapted types.
Aliased types.
Apply sugar.

Advanced Example

type Set[A: (Hashable #read & Equatable[A] #read)] is HashSet[A, HashEq[A]]

class HashSet[A, H: HashFunction[A!] val] is Comparable[HashSet[A, H] box]
  """
  This is implemented as a map of an alias of a type to itself.
  """
  let _map: HashMap[A!, A, H]

  fun op_and[K: HashFunction[this->A!] val = H](that: this->HashSet[A, H]):
    HashSet[this->A!, K]^
  =>
    """
    Create a set with the elements that are in both this and that.
    """
    let r = HashSet[this->A!, K](size().min(that.size()))

    for value in values() do
      try
        that(value)
        r.set(value)
      end
    end
    r

Some fun things we've covered:

Traits, actors, classes.
Sounds constructors, non-null type system.
Inline initialisation, constructor sugar.
Sendable types.
Destructive read, ephemeral types.
Non-reflexive aliasing.
Receiver capabilities.
Capability recovery.
Asynchronicity and causality.
Uniom types.
Default arguments.
Single and multiple assignment variables.
Partial functions, exception handling.
Viewpoint adaptation.

Some advanced things we've covered:

Type aliases.
Generic types.
Generic functions.
Operator overloading.
Viewpoint adapted types.
Aliased types.
Apply sugar.

Some fun things we haven't covered:

Update sugar.
Structural subtyping.
Pattern matching.
The foreign function interface.
Intersection types.
Tuples.
Lambdas.
Partial application.

Actor-Model Variations

What are the Pony guarantees?

Data-race free.
Causal messaging.
No global state.
Type-safe, memory-safe, exception-safe.
Actors don't crash.
Actors are garbage collected.
Ahead-of-time compilation to native code.

When are Pony actors garbage collected?

When their message queue is empty.
And when the message queue will remain empty forever.
Pony uses a novel protocol to achieve this without stop-the-world garbage collection.
Currently, other actor languages require the programmer to manually manage actor lifetime.

Why don't Pony actors crash?

Messages to Pony actors are type-safe. A Pony actor will never receive a message it doesn't understand.
Pony code is exception-safe. There are no uncaught exceptions.
Pony code is memory-safe. There are no null pointers or out-of-bounds reads/writes.

Can Pony programs crash?

Sadly, yes. How?

By exhausting all available memory.
By calling code written in another language that has weaker guarantees.

Didn't you say JavaScript was an actor-model language?

Yes! A JavaScript program is an actor.
Seriously! A JavaScript program reacts to events (behaviours) in sequence.
Typically, there is only one actor.
But with web workers, you can have more.

JavaScript

var pings = 0
var pongs = 0

onmessage = function(e) {
  if(e.type == "ping") { // Our ping behaviour.
    pings += 1 // Changing state.
    e.sender.postMessage({type: "pong", sender: this})
  } else if(e.type == "pong") { // Our pong behaviour.
    pongs += 1 // Changing state.
  }
}

What are the JavaScript guarantees?

Messages are ordered between pairs of actors (pair-ordered), but not generally.
Messages aren't type-safe: an actor can be sent a message it doesn't understand.
Objects in messages are copied, so there are no data races.
The identity of objects in messages is lost.
Actors are not garbage collected, and can terminate, so actor references can be invalid.

What about Node.js?

Node.js has a web workers API.
It's an actor-model language too!

Actors on the JVM: Akka

Akka is a powerful, mature actor-model toolkit for Scala and Java.
Like Pony and JavaScript, actors are presented as asynchronous objects.

Akka

class PingPong() extends Actor {
  var pings = 0 // State.
  var pongs = 0

  def receive = {
    case PingMessage(that) => // This is our ping behaviour.
      pings += 1 // Changing state.
      that ! PongMessage(this) // Sending a message.
    case PongMessage(that) => // This is our pong behaviour.
      pongs += 1 // Changing state.
    case StopMessage => // Akka actors must be manually terminated.
      context.stop(self)
  }
}

What are the Akka guarantees?

Messages are usually pair-ordered.
Some actors have mailboxes that support out-of-order messaging.
Messages aren't type-safe: an actor can be sent a message it doesn't understand.
Objects in messages are __not__ data-race free.
Actors are not garbage collected, and can crash, so actor references can be invalid.

Actors as functions: Erlang

Erlang has been extensively used in production systems for more than 20 years.
Actors are presented as asynchronous _functions_ rather than asynchronous _objects_.

Erlang

pingpong(Pings, Pongs) ->
  receive % We are looking for a message.
    {ping, That} ->
      % This is our ping behaviour.
      That ! pong, % Sending a message.
      pingpong(Pings + 1, Pongs); % Changing state.
    pong ->
      % This is our pong behaviour.
      pingpong(Pings, Pongs + 1); % Changing state.
    exit ->
      % Erlang actors must be manually terminated.
      ok
  end.

What are the Erlang guarantees?

Messages will be _enqueued_ in pair-order.
Messages can be _reacted to_ in any order.
All data is immutable, so no race conditions.
But all data in messages is copied anyway.
Actors are not garbage collected, and can crash, so actor references can be invalid.

Erlang allows an actor to pattern match on its queue.

This is why messages can be _reacted to_ in any order.

Out-of-order message processing

func() ->
  receive
    goodbye ->
      io:format("received goodbye~n", []),
      receive
        hello ->
          io:format("received hello~n", [])
      end
  end.

go() ->
  That = spawn(?MODULE, func, []),
  That ! hello,
  That ! goodbye,
  ok.

We send hello and then goodbye. The actor reacts to goodbye first, then hello.

Akka and JavaScript pattern match on a single message to determine how to react.

Erlang pattern matches on the _queue_, allowing it to select _which_ message to react to.

Summary of Guarantees

Feature	Pony	JavaScript	Akka	Erlang
Data-race free?	Yes	Copies	No	Copies
Message enqueuing?	Causal	Pair-ordered	Pair-ordered	Pair-ordered
Message handling?	Causal	Pair-ordered	Usually pair-ordered	Any
Actors GC'd?	Yes	No	No	No

Come get involved!

Join our community of students, hobbyists, industry developers, tooling developers, library writers, compiler hackers, and type system theorists.

Why not you?

http://ponylang.org

People at Imperial you can contact directly:

s.drossopoulou@imperial.ac.uk

sylvan@causality.io

FilesExpand file tree

ipr0gram-2.md

Latest commit

History

ipr0gram-2.md

File metadata and controls

Actor-Model Programming #2

Massively Parallel Ping Pong

Live Coding in Pony

Actor-Model Variations

Come get involved!