Combinatory logic

Portals and other large-scale resources

• Wikipedia's
• PlanetMath's

Implementing CL

• Talks about it at haskell-cafe $\subset$ haskell-cafe
• Lot of interpreters at John's Lambda Calculus and Combinatory Logic Playground
• CL++, a lazy-evaluating combinatory logic interpreter with some computer algebra service: e.g. it can reply the question $\mathbf {+} \;\mathbf {2} \;\mathbf {3} ;$ with $\mathbf {5}$ instead of a huge amount of parantheses and $\mathbf {K}$, $\mathbf {S}$ combinators. Unfortunately I have not written it directly in English, so all documantations, source code and libraries are in Hungarian. I want to rewrite it using more advanced Haskell programming concepts (e.g. monads or attribute grammars) and directly in English.

Programming in CL

I think many thoughts from John Hughes' Why Functional Programming Matters can be applied to programming in Combinatory Logic. And almost all concepts used in the Haskell world (catamorphisms etc.) helps us a lot here too. Combinatory logic is a powerful and concise programming language. I wonder how functional logic programming could be done by using the concepts of Illative combinatory logic, too.

Datatypes

Continuation passing for polynomial datatypes

Direct product

Let us begin with a notion of the ordered pair and denote it by $\Diamond _{2}$. We know this construct well when defining operations for booleans

• $\mathbf {true} \equiv \mathbf {K}$
• $\mathbf {false} \equiv \mathbf {K_{*}}$
• $\mathbf {not} \equiv \mathbf {\Diamond _{2}} \;\mathbf {false} \;\mathbf {true}$

and Church numbers. I think, in generally, when defining datatypes in a continuation-passing way (e.g. Maybe or direct sum), then operations on so-defined datatypes often turn to be well-definable by some $\mathbf {\Diamond _{n}}$.

We define it with

• $\mathbf {\Diamond _{2}} \equiv \lambda \;x\;y\;f\;.\;f\;x\;y$

in $lambda$-calculus and

• $\mathbf {\Diamond _{2}} \equiv \;\mathbf {C_{(1)}} \;\mathbf {C_{*}}$

in combinatory logic.

A nice generalization scheme:

• as the $\langle \dots \rangle$ construct can be generalized to any natural number $n$ (the concept of $n$-tuple, see Barendregt's $\lambda$ Calculus)
• and in this generalized scheme $\mathbf {I}$ corresponds to the 0 case, $\mathbf {C_{*}}$ to the 1 case, and the ordered pair construct $\Diamond _{2}$ to the 2 case, as though defining
  • $\mathbf {\Diamond _{0}} \equiv \mathbf {I}$
  • $\mathbf {\Diamond _{1}} \equiv \mathbf {C_{*}}$

so we can write definition

• $\mathbf {\Diamond _{2}} \equiv \mathbf {C_{(1)}} \;\mathbf {C_{*}}$

or the same

• $\mathbf {\Diamond _{2}} \equiv \mathbf {C} \cdot \mathbf {C_{*}}$

in a more interesting way:

• $\mathbf {\Diamond _{2}} \equiv \mathbf {C} \cdot \mathbf {\Diamond _{1}}$

Is this generalizable? I do not know. I know an analogy in the case of $\mathbf {left}$, $\mathbf {right}$, $\mathbf {just}$, $\mathbf {nothing}$.

Direct sum

The notion of ordered pair mentioned above really enables us to deal with direct products. What about it dual concept? How to make direct sums in Combinatory Logic? And after we have implemented it, how can we see that it is really a dual concept of direct product?

A nice argument described in David Madore's Unlambda page gives us a continuation-passig style like solution. We expect reductions like

• $\mathbf {left} \;x\to \lambda \;f\;g\;.\;f\;x$
• $\mathbf {right} \;x\to \lambda \;f\;g\;.\;g\;x$

so we define

• $\mathbf {left} \equiv \lambda \;x\;f\;g\;.\;f\;x$
• $\mathbf {right} \equiv \lambda \;x\;f\;g\;.\;g\;x$

now we translate it from $\lambda$-calculus into combinatory logic:

• $\mathbf {left} \equiv \mathbf {K_{(2)}} \;\mathbf {C_{*}}$
• $\mathbf {right} \equiv \mathbf {K_{(1)}} \;\mathbf {C_{*}}$

Of course, we can recognize Haskell's Either (Left, Right).

Maybe

Let us remember Haskell's maybe:

maybe :: a' -> (a -> a') -> Maybe a -> a'
maybe n j Nothing = n
maybe n j (Just x) = j x

thinking of

• n as nothing-continuation
• j as just-continuation

In a continuation passing style approach, if we want to implement something like the Maybe constuct in $\lambda$-calculus, then we may expect the following reductions:

• $\mathbf {nothing} \equiv \lambda \;n\;j\;.\;n$
• $\mathbf {just} \;x\;\to \;\lambda \;n\;j\;.\;j\;x$

we know both of them well, one is just $\mathbf {K}$, and we remember the other too from the direct sum:

• $\mathbf {nothing} \equiv \mathbf {K}$
• $\mathbf {just} \equiv \mathbf {right}$

thus their definition is

• $\mathbf {nothing} \equiv \mathbf {K}$
• $\mathbf {just} \equiv \mathbf {K_{(1)}} \;\mathbf {C_{*}}$

where both $\mathbf {just}$ and $\mathbf {right}$ have a common definition.

Catamorphisms for recursive datatypes

List

Let us define the concept of list by its catamorphism (see Haskell's foldr): a list (each concrete list) is a function taking two arguments

• a two-parameter function argument (cons-continuation)
• a zero-parameter function argument (nil-continuation)

and returns a value coming from a term consisting of applying cons-continuations and nil-continuations in the same shape as the correspondig list. E. g. in case of having defined

• $\mathbf {oneTwoThree} \equiv \mathbf {cons} \;\mathbf {1} \;\left(\mathbf {cons} \;\mathbf {2} \;\left(\mathbf {cons} \;\mathbf {3} \;\mathbf {nil} \right)\right)$

the expression

• $\mathbf {oneTwoThrree} \;\mathbf {+} \;\mathbf {0}$

reduces to

• \mathbf+\;\mathbf1 (\mathbf+\;\mathbf2 (\mathbf+\;\mathbf3\;\mathbf0))

But how to define $\mathbf {cons}$ and $\mathbf {nil}$? In $\lambda$-calculus, we should like to see the following reductions:

• $\mathbf {nil} \;c\;n\;\to \;\;n$
• $\mathbf {cons} \;h\;t\;\to \;\lambda \;c\;n\;.\;c\;h\;\left(t\;c\;n\right)$

Let us think of the variables as $h$ denoting head, $t$ denoting tail, $c$ denoting cons-continuation, and $n$ denoting nil-continuation.

Thus, we could achieve this goal with the following definitions:

• $\mathbf {nil} \equiv \lambda \;c\;n\;.\;n$
• $\mathbf {cons} \equiv \lambda \;h\;t\;c\;n\;.\;c\;h\;\left(t\;c\;n\right)$

Using the formulating combinators described in Haskell B. Curry's Combinatory Logic I, we can translate these definitions into combinatory logic without any pain:

• $\mathbf {nil} \equiv \mathbf {K} _{*}$
• $\mathbf {cons} \equiv \mathbf {B} \left(\mathbf {\Phi } \;\mathbf {B} \right)\mathbf {C_{*}}$

Of course we could use the two parameters in the opposite order, but I am not sure yet that it would provide a more easy way.

A little practice: let us define concat. In Haskell, we can do that by

concat = foldr (++) []

which corresponds in cominatory logic to reducing

• $\mathbf {concat} \;l\equiv l\;\mathbf {append} \;\mathbf {nil}$

Let us use the ordered pair (direct product) construct:

• $\mathbf {concat} \equiv \mathbf {\Diamond _{2}} \;\mathbf {append} \;\mathbf {nil}$

and if I use that nasty $\mathbf {centred} </mathbf>$ (see later)

• $\mathbf {concat} \equiv \mathbf {centred} \;\mathbf {append}$

Monads in Combinatory Logic?

Concrete monads

Maybe as a monad

return

Implementing the return monadic method for the Maybe monad is rather straightforward, both in Haskell and CL:

instance Monad Maybe
        return = Just
        ...

• $\mathbf {maybe\!\!-\!\!return} \equiv \mathbf {just}$

map

Haskell:

instance Functor Maybe where
        map f = maybe Nothing (Just . f)

$\lambda$-calculus: Expected reductions:

• $\mathbf {maybe\!\!-\!\!map} \;f\;p\;\to \;p\;\mathbf {nothing} \;\left(\mathbf {just_{(1)}} \;f\right)$

Definition:

• $\mathbf {maybe\!\!-\!\!map} \equiv \lambda \;f\;p\;.\;p\;\mathbf {nothing} \;\left(\mathbf {just_{(1)}} \;f\right)$

Combinatory logic: we expect the same reduction here too

• $\mathbf {maybe\!\!-\!\!map} \;f\;p\;\to \;p\;\mathbf {nothing} \;\left(\mathbf {just_{(1)}} \;f\right)$

let us get rid of one parameter:

• $\mathbf {maybe\!\!-\!\!map} \;f\;\to \;\mathbf {\Diamond _{2}} \;\mathbf {nothing} \;\left(\mathbf {just_{(1)}} \;f\right)$

now we have the definition:

• $\mathbf {maybe\!\!-\!\!map} \equiv \mathbf {\Diamond _{2}} \;\mathbf {nothing} \;\cdot \;\mathbf {just_{(1)}}$

bind

Haskell:

instance Monad Maybe (>>=) where
        (>>=) f p = maybe Nothing f

$\lambda$-calculus: we expect

• $\mathbf {maybe\!\!-\!\!=\!\!<\!\!<} \;f\;p\;\to \;p\;\mathbf {nothing} \;f$

achieved by defintion

• $\mathbf {maybe\!\!-\!\!=\!\!<\!\!<} \equiv \lambda \;f\;p\;.\;p\;\mathbf {nothing} \;f$

In combinatory logic the above expected reduction

• $\mathbf {maybe\!\!-\!\!=\!\!<\!\!<} \;f\;p\;\to \;p\;\mathbf {nothing} \;f$

getting rid of the outest parameter

• $\mathbf {maybe\!\!-\!\!=\!\!<\!\!<} \;f\;\to \;\mathbf {\Diamond _{2}} \;\mathbf {nothing} \;f$

yielding definition

• $\mathbf {maybe\!\!-\!\!=\!\!<\!\!<} \equiv \mathbf {\Diamond _{2}} \;\mathbf {nothing}$

and of course

• $\mathbf {maybe\!\!-\!\!\!>\!\!>\!\!=} \equiv \mathbf {C} \;\mathbf {maybe\!\!-\!\!=\!\!<\!\!<}$

But the other way (starting with a better chosen parameter order) is much better:

• $\mathbf {maybe\!\!-\!\!\!>\!\!>\!\!=} \;p\;f\;\to \;p\;\mathbf {nothing} \;f$
• $\mathbf {maybe\!\!-\!\!\!>\!\!>\!\!=} \;p\;\to \;p\;\mathbf {nothing}$

yielding the much simplier and more efficient definition:

• $\mathbf {maybe\!\!-\!\!\!>\!\!>\!\!=} \equiv \mathbf {C_{*}} \;\mathbf {nothing}$

We know already that $\mathbf {C_{*}}$ can be seen as as a member of the scheme of tuples: $\mathbf {\Diamond _{n}}$ for $n=1$ case. As the tupe construction is a usual guest at things like this (we shall meet it at list and other maybe-operations like $\mathbf {maybe\!\!-\!\!join}$), so us express the above definition with $\mathbf {C_{*}}$ denoted as $\Diamond _{1}$:

• $\mathbf {maybe\!\!-\!\!\!>\!\!>\!\!=} \equiv \mathbf {\Diamond _{1}} \;\mathbf {nothing}$

hoping that this will enable us some interesting generalization in the future.

But why we have not made a more brave genralization, and express monadic bind from monadic join and map? Later in the list monad, we shall see that it may be better to avoid this for sake of deforestation. Here a maybe similar problem will appear: the problem of superfluous $\mathbf {I}$.

join

• $\mathbf {maybe\!\!-\!\!join} \equiv \mathbf {\Diamond _{2}} \;\mathbf {nothing} \;\mathbf {I}$

We should think of changing the architecture if we suspect that we could avoid $\mathbf {I}$ and solve the problem with a more simple construct.

The list as a monad

Let us think of our list-operations as implementing monadic methods of the list monad. We can express this by definitions too, e.g.

we could name

• $\mathbf {list\!\!-\!\!join} \equiv \mathbf {concat}$

Now let us see mapping a list, concatenating a list, binding a list. Mapping and binding have a common property: yielding nil for nil. I shall say these operations are centred: their definition would contain a $\mathbf {C} \;\mathbf {\Diamond _{2}} \;\mathbf {nil}$ subexpression. Thus I shall give a name to this subexpression:

• $\mathbf {centred} \equiv \mathbf {C} \;\mathbf {\Diamond _{2}} \;\mathbf {nil}$

Now let us define map and bind for lists:

• $\mathbf {list\!\!-\!\!map} \equiv \mathbf {centred} _{(1)}\;\mathbf {cons} _{(1)}$
• $\mathbf {list\!\!-\!\!=\!\!<\!\!<} \equiv \mathbf {centred} _{(1)}\;\mathbf {append} _{(1)}$

now we see it was worth of defining a common $\mathbf {centred}$. But to tell the truth, it may be a trap. $\mathbf {centred}$ breaks a symmetry: we should always define the cons and nil part of the foldr construct on the same level, always together. Modularization should be pointed towards this direction, and not to run forward into the T-street of $\mathbf {centred}$.

Another remark: of course we can get the monadic bind for lists

• $\mathbf {list\!\!-\!\!\!>\!\!>\!\!=} \equiv \mathbf {C} \;\mathbf {list\!\!-\!\!=\!\!<\!\!<}$

But we used $\mathbf {append}$ here. How do we define it? It is surprizingly simple. Let us think how we would define it in Haskell by foldr, if it was not defined already as ++ defined in Prelude: In defining

(++) list1 list2

we can do it by foldr:

(++) [] list2 = list2
(++) (a : as) list2 = a : (++) as list2

thus

(++) list1 list2 = foldr (:) list2 list1

let us se how we should reduce its corresponding expression in Combinatory Logic:

• $\mathbf {append} \;l\;m\to l\;\mathbf {cons} \;m$

thus

• $\mathbf {append} \,l\,m=l\,\mathbf {cons} \,m$
• $\mathbf {append} \;l=\!\!_{1}\;l\;\mathbf {cons}$
• $\mathbf {append} \equiv \mathbf {C_{*}} \;\mathbf {cons}$

Thus, we have defined monadic bind for lists. I shall call this the deforested bind for lists. Of course, we could define it another way too: by concat and map, which corresponds to defining monadic bind from monadic map and monadic join. But I think this way forces my CL-interpreter to manage temporary lists, so I gave rather the deforested definition.

Defining the other monadic operation: return for lists is easy:

instance Monad [] where
        return = (: [])

in Haskell -- we know,

(: [])

translates to

return = flip (:) []

so

• $\mathbf {list\!\!-\!\!return} \equiv \mathbf {C} \;\mathbf {cons} \;\mathbf {nil}$

How to AOP with monads in Combinatory Logic?

We have defined monadic list in CL. Of course we can make monadic Maybe, binary tree, Error monad with direct sum constructs...

But separation of concerns by monads is more than having a bunch of special monads. It requires other possibilities too: e.g. being able to use monads generally, which can become any concrete mondads.

Of course my simple CL interpreter does not know anything on type classes, overloading. But there is a rather restricted andstatic possibility provided by the concept of definition itself:

• $\mathbf {work} \equiv \mathbf {A\!\!-\!\!\!>\!\!>\!\!>\!\!=} \;\mathbf {subwork\!\!-\!\!1} \;\mathbf {parametrized\!\!-\!\!subwork\!\!-\!\!2}$

and later we can change the binding mode named A e.g. from a failure-handling Maybe-like one to a more general indeterminism-handling list-like one, then we can do that simply by replacing definition

• $\mathbf {A\!\!\!-\!\!>\!\!>\!\!>\!\!=} \equiv \mathbf {maybe\!\!\!-\!\!>\!\!>\!\!>\!\!=}$

with definition

• $\mathbf {A\!\!\!-\!\!>\!\!>\!\!>\!\!=} \equiv \mathbf {list\!\!\!-\!\!>\!\!>\!\!>\!\!=}$

Illative Combinatory Logic

Systems of Illative Combinatory Logic complete for first-order propositional and predicate calculus by Henk Barendregt, Martin Bunder, Wil Dekkers.

I think combinator $\mathbf {G}$ can be thought of as something analogous to Dependent types: it seems to me that the dependent type construct $\forall x:S\Rightarrow T$ of Epigram corresponds to $\mathbf {G} \;S\;(\lambda x.T)$ in Illative Combinatory Logic. I think e.g. the followings should correspond to each other:

• $\mathbf {realNullvector} :\;\;\;\forall n:\mathbf {Nat} \Rightarrow \mathbf {RealVector} \;n$
• $\mathbf {G} \;\,\mathbf {Nat} \;\,\mathbf {RealVector} \;\,\mathbf {realNullvector}$

My dream is making something in Illative Combinatory Logic. Maybe it could be theroretical base for a functional logic language?