Chapter 4
Combinators

Overview

Combinators are an alternative to pure functions. They do not use variables and are, therefore, immune to the scoping problems caused by conflicts of names of formal parameters. We present an introduction to combinatory algebras and show how to convert pure functions into combinators.

After an introduction, we discuss combinatory algebras in Section 2. They are the theoretical background of the constructs used later. In Section 3 we show how expressions can be turned into combinators, by a method called combinatory abstraction. Then, in Section 4, we use combinatory abstraction to convert pure functions into terms without variables. The implementation of these ideas requires control of the order of substitutions in rewrite rules. We discuss the techniques needed to achieve this control. A section on applications concludes the chapter. We resume the discussion of fixed points from Chapter 3 and present some of the theory of computation within combinatory algebras.

This chapter shows once more that Mathematica is well suited to implementing formal systems and to experimenting with them. Here, we use expressions that have deeply nested heads. We show how we can specify the order of evaluation using replacement rules with conditions.

Programs

Combinators.m

Numerals.m

Notebooks

Combinators.nb