On Separating Values and Effects

Tags: , , , , , , , , , , , , , , , ,

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

Continue reading » No comments

Mutable Objects in Kernel

Tags: , , , , ,

One important difference between Kernel and traditional LISP/Scheme is Kernel’s pervasive use of encapsulated types [1]. There is a clear distinction in Kernel between decomposable structures and opaque objects. Encapsulated types are a significant contributor toward smooth extensibility. They allow the definition of objects, and operations on those object, that are indistinguishable from primitives. We […]

Continue reading » 8 Comments

Semantic Extensibility with Vau

Tags: , , , , , , , , , , ,

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

Continue reading » 5 Comments

Fexpr the Ultimate Lambda

Tags: , , , , , , , , , , , , , ,

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

Continue reading » 7 Comments

Finger Tree: A Functional Value Object

Tags: , , , , , , ,

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

Continue reading » 8 Comments

Evaluating Expressions, part 3 – Pairs and Parallelism

Tags: , , , , , , , , ,

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

Continue reading » 5 Comments

Evaluating Expressions, part 2 – Conditional Special Form

Tags: , , , , , ,

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

Continue reading » 3 Comments

Evaluating Expressions, part 1 – Core Lambda Calculus

Tags: , , , , ,

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

Continue reading » 5 Comments

Actors in Clojure — Why Not?

Tags: , , , , , , , , , , ,

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

Continue reading » 14 Comments