Combinatory Logic Miscellanea

Combinatory logic treats all arguments ("variables") as implicit and does a very good job of handling implied arguments one at a time (via 'currying'). There also exist several standard combinatorial expressions to represent propositional logic relations (and, or, implies, not, etc.) Many logic relations are binary: handling more than one implicit argument at a time tends to cause combinatory expressions to grow exponentially in size. In the following paper I introduce a new combinator (the P-combinator) that is designed to curry two arguments across multiple using combinators at linear (not exponential) cost in size.

I've provided a series of puzzles, thematically linked, on combinatory logic. Try your skill at solving these Bird Puzzles.

Implementing the 'v' functor of Unlambda (also known in the literature as a hopelessly egocentric bird) using only s, k, and i poses an interesting challenge. I have written a paper entitled Meditations on the Void that shows various attempts at this task as well as a successful implementation.

Cotillion Group Inc.
7309 Inzer Street
Springfield, VA 22151
703.642.1302
703.642.3230 fax