It's Actors All The Way Down

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

This article is dedicated to the memory of John McCarthy (1927–2011) We are constantly on a quest for the elegant combination of simplicity and expressiveness in computer languages—what Alan Kay calls the “Maxwell’s Equations of Software“. An important early milestone was John McCarthy’s LISP [1] (The evolution of these ideas and the thinking behind them […]

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

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

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

The Actor Model of Computation, as defined by Carl Hewitt [1] and elaborated by Gul Agha [2], defines three primitive operations. These operations are “Send”, “Create” and “Become”. The “Send” operation transmits an asynchronous message to a known receiver. The “Create” operation constructs a new actor with a specified initial behavior. The “Become” operation defines […]