It's Actors All The Way Down

2021-06-08 EDIT: Added serializer implementation using only the actor message-event queue. One of the earliest concepts explored on this blog was the Serializer, which is a mechanism for providing exclusive access to a group of actors [1]. More recently, Carl Hewitt has referred to an extended version of this mechanism (with holes) as “Swiss Cheese”. […]

Computability Theory is the foundation for computer software development. Our programming languages embody the techniques and models described by various theories of computation [1]. The Turing Machine is the canonical example of the Imperative Model [2]. Lambda Calculus is the canonical example of the Functional Model [3]. Kleene’s Church-Turing Thesis asserts the equivalence of these […]

Software development is a defect injection process. With every line of code we write, we have a chance of introducing unintended behavior into the system. This chance increases with conceptual complexity. The more difficult a system is to understand, the greater our chance of introducing defects. In his 1980 Turing Award lecture, Tony Hoare said […]

Flow control is a critical feature in a network of asynchronous communicating processes. Our fanciful exploration of a yak-shaving barber’s shop provided us with patterns we can apply to more general problems. The bounded-buffer mechanism is a generalization of our barber’s waiting room. It mediates between producers and consumers, matching the rate of production with […]

The Actor Model explicitly avoids placing constraints on message delivery order beyond causality [1]. Messages may not be delivered before the message which caused them to be sent. In other words, time can’t flow backward. Beyond that, messages arrive in a non-deterministic order. This can sometimes have surprising consequences. Two messages sent in sequence from […]

This article could probably be called “Left Recursion Considered Harmful“. PEG parsers are unambiguous and relatively easy to reason about. A little reasoning about left-recursive PEGs shows that they don’t make sense. The motivation to use left recursion seems to be driven by the desire to build left-associative parse-trees for arithmetic operators. However, parse-tree generation […]

We build on the parsers from part 2 of this series to enhance and extend their capability. In particular, we extend the concept of modular grammars to construct chains of parsers which define a multi-stage transformation pipeline. The parsers forming these chain are enhanced to match and transform tree-structures, rather than being limited to simple […]

It’s usually not enough to simply recognize patterns in an input stream. Soon we will want to take action based on what we recognize. In order to facilitate this, we will begin creating semantic values from the input tokens and trigger semantic actions when certain patterns are recognized. In part 1 of this series we […]

Parsing Expression Grammars (PEGs) define a powerful class of matchers for recognizing strings of a formal language [1]. They’re well suited to parsing the syntax of computer languages. PEG-based tools like OMeta [2] have been successfully applied to a wide variety of transformation problems [3] [4]. The fundamental elements of PEGs can be described compactly […]

This is part two of an article exploring what we mean when we say “message-passing”. Part one described how synchronous rendezvous can be expressed with actors. Part two describes an actor implementation of object-oriented method invocation. For Object-Oriented developers from the Smalltalk tradition, message-passing involves a dynamic method lookup, invocation of that method with the […]

A significant challenge in developing concurrent systems is the problem of composability. We create a solution that works properly in isolation, but when composed with other solutions leads to interference. The actor model ensures that individual actors may be composed without changing their behavior. Interference is prevented by definition, keeping the system consistent. In order […]