Tag Archives: sequence

“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 , , , , , , , , , | 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

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

Finger Tree: A Functional Value Object

A Finger Tree is a data-structure that supports amortized O(1) additional and removal of elements from either end [1]. It also can support a large number of common sequence operations, including concatenation, very efficiently. Our implementation is based on the Hinze-Paterson structure [2], simplified for use as a Deque. It is possible to implement a […]

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

Evaluating Expressions, part 6 – Actor Primitives

In part 6 of our series implementing programming language constructs with actors, we explore meta-circular definition of imperative actor primitives. We have now moved beyond expressions which yield values, and focus on statements which cause effects. The constructs explored here are the heart of any actor-based system. In order to support actor primitive statements, our […]

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