Tag Archives: composition

On Separating Values and Effects

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 […]

Posted in Uncategorized | Also tagged , , , , , , , , , , , , , , | Leave a comment

Debugging Actor Systems

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 […]

Posted in Uncategorized | Also tagged , , , , , , , , , | 1 Comment

Producer/Consumer Rate-Matching

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 […]

Posted in Uncategorized | Also tagged , , , , , , , , , , , , , , | Leave a comment

In-Order Message Delivery

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 […]

Posted in Uncategorized | Also tagged , , , , , | 1 Comment

Parsing Expression Grammars, part 4

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 […]

Posted in Uncategorized | Also tagged , , , , , , | 2 Comments

Parsing Expression Grammars, part 3

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 […]

Posted in Uncategorized | Also tagged , , , , , , | Leave a comment

Parsing Expression Grammars, part 2

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 […]

Posted in Uncategorized | Also tagged , , , , , , , , | 2 Comments

Parsing Expression Grammars, part 1

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 […]

Posted in Uncategorized | Also tagged , , , , | 2 Comments

Message Passing, part 2 – Object-Oriented Method Invocation

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 target […]

Posted in Uncategorized | Also tagged , , , , , , | 2 Comments

Composing Actors

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 […]

Posted in Uncategorized | Also tagged , , , , , | 12 Comments