From OpenCog
(Redirected from CombinatorTree)
Jump to: navigation, search


One of the tools used in formalizing and implementing OCP Schemata and Predicates is a branch of mathematics called combinatory logic. This section briefly reviews combinatory logic and explains its utilization in OCP schemata and predicates.

Combinatory logic is a fairly obscure branch of mathematics, generally well known only in the functional programming community. However, we strongly believe that it is more than just a mathematical trick; we feel that its basic insight of representing complex structures as functions of functions of functions gets at something important for AI.

For the reader who wishes to go deeper on the mathematical side, the best explanation of the basic principles of combinatory logic that we have found is in the functional programming textbook by Field and Harrison (1988). The more ambitious and mathematically-oriented reader is referred to the original source, Combinatory Logic by Haskell Curry and Robert Feys (1958), which is difficult reading but well worth the effort required (at least where Volume 1 is concerned; we have doubts whether anyone has ever completed Volume 2).

Basic Ideas of Combinatory Logic

Conceptually, combinatory logic is simple. One begins with a few basic entities, called combinators. These combinators can take other combinators as inputs, and produce other combinators as outputs. This basic operation of action or function application is typically denoted by adjacency, e.g.

f g

refers to the combinator that f will output when given g as an input.

Application is assumed to left-associate (currying), so that

f g h = (f g) h

This convention takes a while to get used to, but provides great simplicity of expression once fully internalized. If one wants right association, one must explicitly insert parentheses, as in

f (g h)

which feeds as input to f, the output that g gives on being given input h.

The remarkable thing is that, from this simple framework alone, one can generate anything at all. In other words, this is yet another way of providing universal computational capability.

The standard, almost minimal formulation of combinatory logic uses only two combinators, S and K (to be defined just below). These are enough to give the combinatory framework arbitrary computational power.

We will use underlined characters to denote combinators (e.g. S, K), which allows us to use non-underlined letters like S and K to denote other things without possibility of confusion. This underlining is not standard combinatory logic notation.

Formalization of Combinators

More formally speaking, one may specify a combinator algebra as follows. One starts with a finite set of combinators,

Basic-Combinator = { f1 , … , fn }

Then one introduces the notion of a combinator expression, which can be expressed as a (finite) tree of a special kind.

The nodes of a Combo tree contain either combinators or @ symbols. The @ symbol denotes function application. So for instance, we may have

 /   \
f     g

which means f is applied to g, or in curried notation, f g, or in standard functional notation f(g). Or one may have

    /   \
   @     h
 /  \
f    g

which means

  • curried: (f g) h
  • uncurried: (f(g))(h)

Formally, the space of Combo trees is defined by the fact that

  • leaf nodes have to have basic combinators at them, not @ symbols
  • non-leaf nodes have to have @ symbols at them

One may then define


as the space of combinator expression obtained from one's given set of basic combinators.

The essence of combinator activity lies in the multiplication table associated with a set of basic combinators. Each expression of the form

 /   \
f     g

where f and g are basic combinators, either

  • evaluates to NULL, meaning that f cannot act on g
  • evaluates to some basic combinator

This allows us to define an evaluation map on the space of combinator expressions, where we say that

  • a combinator expression evaluates to NULL if any of its subexpressions evaluate to NULL
  • otherwise, a combinator expression evaluates to what its root node evaluates to, after recursive evaluation of all subexpressions

In principle, the combinator multiplication table could be entirely random and unstructured. However, this case is not all that interesting in practice. Instead, there are usually patterns in evaluations, which can be encapsulated in variable-bearing macro rules or substitution rules.

The basic combinators called S and K are the only ones needed to give combinatory logic arbitrarily great expressive power. In OCP we make use of a much broader set of combinators, beginning with the slightly expanded combinator set S, K, I, B, C defined as follows:

I x = x

K e f  = e

S f g x= (f x) (g x)

B f x y = f (x y)

C f x y = f y x

Another important combinator is the Y-combinator

Y f = Y ( Y f)

but we have avoided this one in OCP because, in practice, it has a high probability of giving rise to nonterminating expressions. We have also introduced a number of higher-level combinators for dealing with things like functions and lists, which will be discussed later on.

It is not hard to figure out how to represent I, B and C in terms of S and K. The representation of Y in these terms is a little trickier, and is given by the definitions

U f x ==> f (x x)

Y = S (K (U I)) U

Note that adjacency always means function application in combinatory logic. To denote function composition one uses the compositor combinator, B.

In practice one usually wants to extend the basic combinator vocabulary even further. For instance, one can introduce the notion of an ordered or unordered list as a primitive, so that one can then have expressions like

f (x, y)

The list operator called "fold" defined by

fold f v [] = v

fold f v (x : xs) = f x (fold f v xs)

can be particularly useful. (This is called foldl in Haskell.)

One can also introduce primitives like numbers, strings, and so forth. In this sense the OCP schema module is much like a functional programming language. The reason one introduces these extra primitives, is that otherwise the expression of some intuitively simple things becomes overly complicated. For instance, in the minimalist approach, using only the basic combinators given above, one represents numbers, numerical operators, and logical operators in terms of a code which expresses each of them as a certain combination of S and K combinators. Elegant, but not so pragmatic.

Diagrammatic representation of Combinators

Some readers may find it useful to see a diagrammatic representation of many of the combinators presented above


     / \            @
    @   x          / \
   / \      =>    /   \
  @   g          @     @
 / \            / \   / \
S   f          f   x g   x


   / \
  @   y    =>   x
 / \
K   x


 / \    =>   x
I   x


     / \            @
    @   x          / \
   / \      =>    f   @
  @   g              / \
 / \                g   x
B   f


     / \           @
    @   y         / \
   / \     =>    @   x
  @   x         / \
 / \           f   y
C   f


    @             @
   / \           / \
  @   x   =>    @   x
 / \           / \
W   f         f   x


  @            @
 / \     =>   / \
D   f        f   f