Combinator Module Users' Manual

Purpose

This document provides information on using the predicates exported from the combinator module. Furthermore, as the predicates, themselves, are derivative (they depend entirely on the syntax and semantics of the combinators and the language used to express them), this document provides an overview of the implementation language and the use of combinators.

Background

Combinatory logic (CL) is one language of mathematics.¹ Like the lambda calculus, one expresses a function by combining a set of terms; unlike the lambda calculus, CL has no variables; the terms are combinators, not lambda terms, and the method of combining combinators is composition, not application, as it is for the lambda calculus. Given, or, despite, the similarities and differences of CL to the lambda calculus, the results of both languages is the same: one can build any arbitrary computable expression using a small set of "primitive" terms.

Concessions

Pure combinatory logic has normal order evaluation ("lazy"), and the result of composing combinators is a combinatory term. We allow some intrusions of the "real world" into this implementation of CL in order to simplify translating information between the rest of Prolog and the CL domain.

• The first such concession is the introduction of several new, pragmatic, combinators, such as Natural numbers and arithmetic operators. These additions are, of course, redundant: like the lambda calculus, it is possible to represent Number as a composition of combinators, but then translating between Prolog and the combinators module becomes a tedious task. I chose to enhance the syntax with these new combinators.
• The second concession is the introduction of the (non-existant) "Query" combinator: '?'. This combinator, when appended to the end of a CL expression converts the common CL representation of true (the 'k' combinator) to the Prolog goal true/0, and converts the common CL representation of false (the term '`ki' or '`sk' (they are universally equivalent)) to the Prolog goal fail/0. I find the very stark declaration of intent this combinator imparts to an expression to be a valuable documentation tool, and it also, by automatically mapping a CL term to a Prolog truth equivalent, fits very nicely into the nondeterministic programming style.
• Whereever possible, combinators are evaluated lazily, but some things are not so easily implemented. The sage birds, particularly the 'y' combinator² should be avoided as they cause the system to fall into infinite regression.

Syntax

We use the composition syntax as implemented by Unlambda:³ the grammar is unambiguous and is generally more succinct than other unambiguous grammars.⁴ The grammar is as follows:

<program>	::=	(<composed-term> | <combinator>) <query-token>?
A combinatory logic program is a single combinatory expression. The program may be optionally decorated by the query token, which indicates that the program evaluates to a boolean expression that should be converted to the equivalent Prolog goal.
<expression>	::=	<combinator-or-number> | <composed-term>
The expression is either a single combinator or a term composed of two or more combinators. The syntax of which is the following:
<composed-term>	::=	<compose-token> <expression> <expression>
So, a composed-term is simply the composition of two expressions. The sub-expressions are evaluated, when necessary, before the entire term is evaluated.
<combinator-or-number>	::=	<natural-number> | <operator> | <combinator>
The combinators are a subset of traditional combinators defined in [Smu1985]; the operators are the concessions made to "traditional" algebra for working with the natural numbers allowed in this language.
<combinator>	::=	b | c | i | j | k | l | m | n | o | p | r | s | t | u | v | w
<operator>	::=	< | > | = | + | * | - | / | :
The operators have their usual arithmetic meanings (the = combinator is the identity comparitor, not the assignment operator); the one special case is the : combinator which is taken to mean list-concatenation: 1:List prepends the element 1 to a List of elements.6
<natural-number>	::=	<digit> | (<digit> <natural-number>)
<digit>	::=	0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
As we see above, combinators are selected letters of the alphabet, the meanings of which we will define below. The final bits of the syntax are the tokens:
<compose-token>	::=	`
<query-token>	::=	?

Combinator Meanings

The combinators declared above each have an equivalent representation in the lambda calculus -- this gives them their respective definitions. The below table shows the combinators with their given names and their lambda-equivalents.

Combinator	Given Name7	Lambda Equivalent
b	Bluebird	Bxyz	=	x(yz)
c	Cardinal	Cxyz	=	xzy
i	Identity Bird	Ix	=	x
j	Jay	Jxyzw	=	xy(xwz)
k	Kestrel	Kxy	=	x
l	Lark	Lxy	=	x(yy)
m	Mockingbird	Mx	=	xx
n	Nightingale8	Nx	=	xKSK
o	Owl	Oxy	=	y(xy)
p	Penguin9	Pxyzwv	=	x(ywv)(zwv)
r	Robin	Rxyz	=	yzx
s	Starling	Sxyz	=	xz(yz)
t	Thrush	Txy	=	yx
u	Turing bird	Uxy	=	y(xxy)
v	Vireo	Vxyz	=	zxy
w	Warbler	Wxy	=	xyy

Examples

Subtract 2

The term "``c-2" subtracts 2 from a given number, so the goal

map("``c-2", [31, 41, 59, 26, 5], Ans)

Gives the list

Ans = [29, 39, 57, 24, 3]

If we were not to use combinators and the mapping predicate, the equivalent Prolog code to do the same transformation would be:

subtract2([Elt|Rest]) -->
  { NewElt is Elt - 2 },
  [NewElt],
  subtract2(Rest).
subtract2([]) --> [].

Increment

The term "`+1" increments a given number:

X := 1..10, map("`+1", X, Y)

=> Y = [2,3,4,5,6,7,8,9,10,11]

The equivalent combinator-free Prolog code:

inc([Elt|Rest]) -->
  { NewElt is Elt + 1 },
  [NewElt],
  inc(Rest).
inc([]) --> [].

Minimum Element

The term "```pt<v" is a predicate that returns true if the first given number is less than the second (the Vireo is how CL creates pairs). When applied over a list of numbers, it gives the minimum element of the list:

foldl([31,41,59,26,5], "```pt<v", 31, X)

=> X = 5

Prolog non-combinator equivalent:

min_list([Num|Nums], Accum, Ans) :-
  (Num < Accum -> NewAccum = Num; NewAccum = Accum),
  min_list(Nums, NewAccum, Ans).
min_list([]) --> [].

Sum of Squares

The term "``b+`w*" squares the given number and adds it to an accumulated result, essentially transforming an input list into the sum of the elements squared.

foldl([3, 4], "``b+`w*", 0, X)

=> X = 25

Prolog non-combinator equivalent:

sum_of_squares([Num|Nums], Accum, Ans) :-
  Square is Num * Num,
  NewAccum is Square + Accum,
  sum_of_squares(Nums, NewAccum, Ans).
sum_of_squares([]) --> [].

Summary

The above examples show that with map/3 and foldl/4¹⁰ one may capture the programming logic in the combinator, and the recursion scheme falls out of the predicate selected: it is possible to write programs using combinators. Moreover these programs may be specified at any time: compiled into a module or even specified dynamically at runtime. Modules using combinators rely on a few simple predicates to accomplish this feat; below we review these predicates.

:- module(combinators)

Dependences

:- use_module(library(lambda), [apply/3, test/2]).

:- use_module(library(syntax), ['<-'/2]).

Exported Predicates

The combinators module exports the following predicates:

• compose/3
• phi_equivalent/2

Exported Operators

This module does not export any operators.

compose/3

phi_equivalent/2

Endnotes

Works Consulted