There're serveral concurrent models nowadays, CSP, Actors, π-calculus ...etc. It is believed that these concurrent models could bring high performance and scalable concurrent network service. Actor-model(I may call it Actors in the rest of the article) is a hot one that many folks would like to talk about it. But rather than using it, have you imagined to implement one for better learning it? Well, if your answer is yes then this is the article for you. I'll show you a feature-limited tiny actor-model implementation in Scheme, although you may call it a poor man's threading system, hope that's enough for you to understand the principle.

BTW. folks may kindly mention LFE(stands for Lisp Flavored Erlang) which is a Lisp syntax frontend implemented on Erlang compiler. In this article, I'm trying to show a tiny Actors framework written with pure Scheme. So they're very different in concept.

I would pick GNU Guile, because we need its delimited-continuations for coroutine. But it won't stop you to pick your fav Scheme implementation for Actors if you get the principle in this article.

Actors? Now that you have Scheme...

Why I've picked Actors rather than others, say, CSP? Because Actors has something to do with Scheme historically. And this is a Scheme blog, don't you know? Alright, not true, I write many things, but this blog is built with Scheme. ;-)

After Carl Hewitt introduced Actor-model in 1973, Gerald Sussman and Guy Steele's attempt to understand Actors resulted in the creation of the Scheme. Then they published a paper to show the conclusion: "we discovered that the 'actors' and the lambda expressions were identical in implementation."

It is believed that a proper Actors implementation requires at least two key features provided by languages[1]: first-class-continuation and proper-tail-call. First-class-continuation is used to construct light-weight process in userland, and the proper-tail-call is actually more efficient, in addition to being clearer. Maybe it's the reason why Scheme stick to them in the original. I'll try to explain why they're important for Actors, later. Well, folks may say that there'd be message passing and pattern matching as well, but these features could be contructed relative easily upon any mainstream languages. It's unnecessay to be provided by language itself.

The benefit of Actors is well-known: lock-free by means of message passing, async (if you play them properly with non-block), high concurrency...

Of course, there're caveats in Actors too. The actor model has no direct notion of inheritance or hierarchy, which means it is time consuming and confusing to program actors with trends of common behaviour. Besides, a *real* Actors framework demands scalability, which means it should support exchanging states and continuations between distributed nodes. It is a hard problem for efficient implementing. Moreover, it is not easy to do static-analysis debuggning and optimizing...etc for such a model.[2] These prolems seem to have been preventing Actors to be a mainstream computing model for a long time. For me, I would like to use it only in a high concurrent and scalable server design. It's great for server developping, but maybe not so generic for common usage just like what Object-Oriented Model does.

What is Actors exactly?

According to Carl Hewitt, unlike previous models of computation, Actors was inspired by physics, including general relativity and quantum mechanics. In theory, Actors can be described by several of axioms/laws/formulas. This article is not going to explain Actors in formal mathmatics, since it's painful to understand for non-mathmaticians.

The Actors, from programming perspective, at least consist of these priciples:

  1. Light-weight processes (actors) are the units for scheduling, it is unnessary to be the OS-level process; 
  2. Actors must communicate only by means of message(immutable) passing;
  3. Each actor has its own mailbox, and can be accessed only by its owner. This means the states are local;
  4. A proper pattern matching machanism for parsing the messages;
  5. Actors may block themselves, but no actor should block the thread on which it is running;
  6. Actors may spawn new actors;
  7. Sharing states and processes by distributed nodes.

Then we may write a prove-of-concept one by following them. Some features maybe considered to be very hard, but they're somehow implemented in certain modern languages, say, Erlang.

First, we have to consider how to implement light-weight processes, say, actors. The best way is not calling fork, nor pthread, but continuations.

Delimited Continuations

Continuations are dragons! Keep distance from it and pray some hero to slaught it for you is safer!

Alright, you might leave now.

Oh you don't buy it, right?

Continuations is good for implementing lightweight threads/coroutines. Unlike fork/pthread, such threads won't trap into OS kernel, hence this so-called green-thread would reduce much overhead, and lockfree (actually, just less locks). In brief, it's faster. Unfortunately, I'm not going to discuss what is continuations and how they're implemented in GNU Guile in this article. But it is necessary to explain the difference between full-continuations(call/cc) and delimited-continuations in a simple way. To show why the later would be better for light-weight coroutines. Maybe I could write another article to discuss them, deeper.

Similarly, I will discuss continuations from programing perspective.

When we talk about continuations, people may mention call/cc, as folks may know it is full-continuations. Full stack will be copied when capturing it, nevertheless, the worse situation is in Guile, there'll be two stacks are copied, continuations-stack and VM-stack. Please don't worry if you don't understand what I said. It's too heavy to use call/cc, that's what I want to say. Please see the figure below:

This figure maybe too simple, but you get the idea about how full-continuations are captured in principle.

And how about delimited continuations?

Again, it's too simple to show the true implementation in Guile, but you got how delimited-continuations are captured. Here's a better article if you want to learn more.

I hope it could help to understand why delimited-continuations is excellent for implementing light-weight processes. The point is that you just need to copy few stack frames (rather than full stack) in userland, which is light enough for scheduling.

I'm not going to discuss how to handle delimited-continuations in detail here, because it could be a very large topic. One may play delimited-continuations in many fancy ways. Here I just give an simplest example to show the principle of a coroutine.

(use-modules (ice-9 control)) ; import delimited-continuations module

(define workqueue '())

;; silly function to show the principle
(define (fun x)
  (display "start\n")
  (abort) ; yield here, the rest computation (continuation) is stopped then scheduled
  (display x)(newline)
  (display "end\n"))

;; very simple scheduler, just add a yield thread to a queue
(define (scheduler k)
  (set! workqueue (cons k workqueue)))

;; % is a breviate of call-with-prompt
(define (spawn-thread proc)
  (% (proc) scheduler))

(spawn-thread (lambda () (fun 123)))
;; ==> start

workqueue
;; ==> (#<partial-continuation 28baba0>) ; or something similar

((car workqueue)) ; run this thread
;; ==> 123
       end

You may notice that the key points are two, % for drawing the bottom line for capturing and abort for yielding. Besides, we have scheduler to deal with the captured continuation, it's the second argument of % as you might see.

Well, now I believe it's enough to enter Actors.

Actors in Scheme

There're various ways to implement Actors, here I'm trying to mimic an Erlang style one. Here's a ping-pong game code. If you ever played Erlang, you'll be familiar with the ping-pong code in Erlang manual:

-module(tut15).

-export([start/0, ping/2, pong/0]).

ping(0, Pong_PID) ->
    Pong_PID ! finished,
    io:format("ping finished~n", []);

ping(N, Pong_PID) ->
    Pong_PID ! {ping, self()},
    receive
        pong ->
            io:format("Ping received pong~n", [])
    end,
    ping(N - 1, Pong_PID).

pong() ->
    receive
        finished ->
            io:format("Pong finished~n", []);
        {ping, Ping_PID} ->
            io:format("Pong received ping~n", []),
            Ping_PID ! pong,
            pong()
    end.

start() ->
    Pong_PID = spawn(tut15, pong, []),
    spawn(tut15, ping, [3, Pong_PID]).

But if you transfer Erlang code to S-expr:

(define (ping . args)
  (match args
    ((0 pong-pid)
     (! pong-pid 'finished)
     (format #t "ping finished~%"))
    ((n pong-pid)
     (! pong-pid (list 'ping (self)))
     (receive
      ('pong #t
       (format #t "ping received pong~%")))
     (ping (1- n) pong-pid))))

(define (pong)
  (receive
   ('finished #t
    (format #t "pong finished~%"))
   (('ping ping-pid)
    (format #t "pong received ping~%")
    (! ping-pid 'pong)
    (pong))))

(define (start)
  (let ((pong-pid (spawn pong '())))
    (spawn ping (list 3 pong-pid))
    (active-scheduler)))

Well, looks similar huh? Anyway, I just intended to write so, maybe helpful for you to learn Actors in Guile compared to Erlang code.

Before we try the code above to work, we have to implment the Actors framework first. We need to implement message passing, mailbox check, process spawn, and scheduler. Let me show the code directly:

;;==============Tiny framework of Actor-model=========================
(use-modules (ice-9 control) ; for delimited-continuations
             (ice-9 match)   ; for pattern matching
             (ice-9 q))      ; for queue data structure

(define *mailbox* (make-hash-table))
(define *task-queue* (make-q))
(define (gen-pid) (gensym "actor-"))

;; send message to the pid (uniq to a process)
(define-syntax-rule (! pid msg)
  (let ((mq (hashq-ref *mailbox* pid)))
    (if mq
        (enq! mq msg)
        (error '! "send msg: invalid pid" pid))))

(define-syntax-rule (has-task?)
  (not (q-empty? *task-queue*)))

;; get pid of the current process
(define-syntax-rule (self)
  (if (has-task?)
      (car (q-front *task-queue*))
      (error 'self "No task!")))

;; check mail box for current process, schedule to sleep when it's empty
(define-syntax-rule (receive body ...)
  (let lp()
    (match (hashq-ref *mailbox* (self))
      ((or #f (? q-empty?)) (abort 'sleep) (lp))
      ;; Very important!!! We must schedule the process after each receive scheduled,
      ;; or we failed to capture the correct continuation here. Don't blame me if you
      ;; see ghost when remove it, follow me to keep you safe!!!
      (mq ((lambda (_) (match _ body ...)) (deq! mq)) (abort 'sleep)))))

(define-syntax-rule (%schedule)
  (when (has-task?) ((cdr (q-front *task-queue*)))))

(define-syntax-rule (active-scheduler)
  (% (%schedule) scheduler))

;; a simple scheduler to dispatch the process with status
;; `sleep' to suspend the current process and run the next process from queue
;; `quit' to exit the current process
(define (scheduler k s)
  (case s
    ((sleep)
     (enq! *task-queue* (cons (car (deq! *task-queue*)) k)))
    ((quit)
     (hashq-remove! *mailbox* (car (deq! *task-queue*)))))
  (active-scheduler))

;; spawn a new process to run proc with args as arguments
(define (spawn proc args)
  (let ((pid (gen-pid)))
    (hashq-set! *mailbox* pid (make-q))
    (enq! *task-queue* (cons pid (lambda () (apply proc args) (abort 'quit))))
    pid))

Pretty easy, right? The principle is explicitly:

  1. spawn a process as running a function
  2. send messages between processes, depends on how you write these functions
  3. use receive to check mailbox for the current process and handle them
  4. schedule the current process when mailbox is empty
  5. quit the process properly when the function is over (no loop again)

And maybe you've noticed that the two key features mentioned above: first-class-continuations and proper-tail-call plays great role in the Actors. Actually, we're using first-class-delimited-continuations for implementing light-weight processes. The proper-tail-call, well, you see it everywhere in the code, right? it makes the code clearer and elegant. Or you may imagine how to rewrite them in while loops.

Here is a complete version you may try.

Don't be upset if you can't understand delimited-continuations properly, it looks easy but not easy at all. I may write another article for it. But this time, please focus on Actors' principle only.

Caveats

I'm sorry but I didn't implement serializable-continuations which is used to Sharing states and processes by distributed nodes. It's another big topic to make it properly. I may discuss it in the future.

Refs:

[1] Scheme@33, William.D.Clinger.

[2] Why has the actor model not succeeded? Paul.Mackay http://www.doc.ic.ac.uk/~nd/surprise_97/journal/vol2/pjm2/