Now is the time we come full-circle in our exploration of Kernel/Scheme/LISP and show how Actors can be implemented on this foundation. This should dispel the notion that Actors are just functions/procedures. Sure, when an Actor receives a message you could say that the message is “applied” to the Actor’s current behavior. In that sense, [...]
Posted in Uncategorized | Also tagged asynchronous, concurrency, evaluation, event, event-loop, Kernel, lambda-calculus, message-passing, Scheme, synchronization, vau-calculus |
John Shutt has reformulated the foundations of LISP/Scheme [1]. Observing that Lambda is a primitive applicative constructor, he proposes Vau as a primitve operative constructor instead. This changes our focus from implicit evaluation to explicit evaluation. Applicatives evaluate their operands before evaluating the combination. Operatives act directly on their (unevaluated) operands, possibly evaluating them selectively. [...]
Posted in Uncategorized | Also tagged evaluation, extensibility, functional, Kernel, lambda-calculus, language, LISP, pair, queue, Scheme, vau-calculus |
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 [...]
Posted in Uncategorized | Also tagged evaluation, extensibility, functional, Kernel, lambda-calculus, language, LISP, object-oriented, pair, pattern-matching, recursion, Scheme, value, vau-calculus |
Mutable shared state is the root of all evil in concurrent systems. The history of concurrent computation is a basically the story of approaches to managing mutable shared state. The thread model, which has long held the dominant position, leads to intractable complexity [1]. The actor model captures state in the behavior of an actor. [...]
One significant difference between message-passing in Erlang and the pure Actor Model is the Erlang concept of mailboxes. Actors don’t have mailboxes, at least not in the sense that they can be queried. Messages simply arrive at some non-deterministic time after they are asynchronously sent, invoking the current behavior of the actor. However, in Erlang, [...]
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 [...]
In a loosely-coupled system connected with asynchronous messages, a flood of client requests can exceed the capacity of a service. When this happens, we would prefer that the service respond with an indication of the overloaded condition, rather than making us wait for service we may never receive. The Twitter “fail whale” is an example. [...]
The Observer pattern causes temporal coupling in systems with synchronous message passing. This can lead to failure in Object-Oriented systems. Asynchronous messaging avoids the pitfalls. Actor-based implementations more accurately realize the original intent of the pattern. The intent of the Observer pattern is to “define a one-to-many dependency between objects so that when one object [...]
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 [...]
Happy New Year and welcome to 2011. With the coming of the new year, I’m happy to announce the availability of a simulator/debugger environment for Humus, currently hosted at http://dalnefre.com/humus/sim/humus.html Please note that this is a simulator of the Humus language written in JavaScript, so it runs very slowly. It is intended to allow experimentation [...]
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’ [...]
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 evaluation, imperative, language, pair, primitive, protocol, sequence, serializer, state-machine, synchronization, value |
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 data-flow, equation, evaluation, imperative, language, pattern-matching, protocol, recursion, synchronization, unification, value |
In part 4 of our series implementing programming language constructs with actors, we extend our pattern matching behaviors to support pattern equations. These are true equations that express relationships between patterns. They form the basis for introducing LET and IF expressions. The grammar for our extended language is shown below. Changes from part 3 are [...]
In part 3 of our series implementing programming language constructs with actors, we explore parallel evaluation of sub-expressions and introduce pairs. Pairs allow the construction of tuples, generalizing structured multi-part patterns and values. In order to support pair expressions and patterns, we’ve refactored the grammar from part 2 to separate out literal constants expressions and [...]
We continue exploring actor implementation of programming language constructs by adding a special form for conditional expressions. This will not increase the expressive power of the language. In part 1 we implemented a Turing-complete pure untyped lambda calculus. Now we add direct efficient support for conditional expressions and introduce basic pattern matching. Changes from the [...]
One of the best ways to understand programming language constructs is to implement them. We will begin by implementing a simple, yet Turing-complete, functional expression language. In subsequent articles, we will extend this language with additional features. For now we will focus on just the “untyped” lambda calculus, augmented with constants. The grammar for our expression [...]