Tag Archives: data-flow

“Same Fringe” Revisited

The fringe of a binary tree is simply the sequence of leaves reading from left to right [1]. Comparing the fringe of two binary trees to see if they are the same has been described as the simplest problem that requires multiprocessing or coroutines to easily solve [2]. The challenge is to stop the comparison […]

Posted in Uncategorized | Also tagged , , , , , , , , , | Leave a 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

Futures and Capabilities

In the Actor Model, concurrency is the default. Sequencing must by arranged explicitly. An important case of sequencing occurs when there is a data dependency between different parts of a system. One part produces a value that another part needs to perform its function. One mechanism for sequencing data-dependent operations is to create a Future. […]

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

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

Evaluating Expressions, part 7 – Transactions and Exceptions

In part 7 of our series implementing programming language constructs with actors, we implement parallel execution of block statements. Parallel execution motivates the use of single-assignment data-flow variables. We also introduce transactions and exception handling. The only extension required to our grammar from part 6 is the inclusion of a THROW statement: stmt ::= ‘LET’ […]

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

Evaluating Expressions, part 5 – Recursion

Some language environments provide an interactive interface called a Read-Eval-Print-Loop (abbreviated REPL). One key characteristic of a REPL is the ability to incrementally define, extend and re-define your environment. This is particularly challenging in a pure-functional context, such as the evaluator we have developed so far. Modularity and incremental development seems to imply the need […]

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

Actors in Clojure — Why Not?

In his article about state management in Clojure, Rich Hickey discusses his reasons for choosing not to use the Erlang-style actor model. While Erlang has made some implementation choices that can lead to problems, the problems are not intrinsic to the Actor Model. As the actor implementation with the longest history of success, Erlang naturally represents […]

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

Solving “Same Fringe” with Stream Generators

A classic problem in concurrent programming is known as the “same fringe” problem [1]. What is the same fringe problem? As described by Richard Gabriel [2]: The samefringe problem is this: two binary trees have the same fringe if they have exactly the same leaves reading from left to right. There are many different approaches […]

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