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 actor, behavior, composition, effect, evaluation, execution, functional, Humus, imperative, lambda-calculus, open-system, primitive, real-world, theory, time, value |
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 actor, evaluation, extensibility, functional, Kernel, lambda-calculus, 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 actor, evaluation, extensibility, functional, Kernel, lambda-calculus, LISP, object-oriented, pair, pattern-matching, recursion, Scheme, value, vau-calculus |
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 actor, evaluation, imperative, 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 actor, data-flow, equation, evaluation, imperative, 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 […]