display | more...

In addition to the original S, K, and I combinators first introduced by Moses Schönfinkel as a basis for the lambda calculus, David A. Turner added several more combinators to the list to address inefficiencies involved when translating expressions in the lambda calculus to combinators (a process called abstraction elimination). These were first used in the implementation of Turner's Miranda functional programming language. Some implementations of Haskell also are apparently based on the Turner set combinators.

The Turner set includes all of the original Schönfinkel combinators, which (for completeness) are defined by the contraction rules:

  • I x -> x
  • K x y -> x
  • S f g x -> (f x) (g x)

Turner motivated his addition of combinators by noting that the S combinator sometimes needlessly has to pass copies of its third argument to both the right and the left, when most of the time all that is needed is to pass the third argument to either the right or the left. So the B and C combinators were created:

  • B f g x -> f (g x)
  • C f g x -> (f x) g

Four more four-argument combinators were added to cover other common cases that often arise in abstraction elimination:

  • S' c f g x -> ((c (f x)) (g x)
  • B* c f g x -> (c (f (g x)))
  • C' c f g x -> (c (f x)) g
  • U f p x y -> (f x) y

By testing all abstraction elimination steps against these patterns in the order they are listed here, the process can be made more efficient:

  • S (K p) (K q) -> K (p q)
  • S (K p) I -> p
  • S (K p) (B q r) -> B* p q r
  • S (K p) q -> B p q
  • S (B p q) (K r) -> C' p q r
  • S p (K q) -> C p q
  • S (B p q) r -> S' p q r

The results of abstraction elimination using the Turner set combinators can drastically reduce the number of combinators needed. For instance, the Church numeral for three, λf x.f (f (f x)), has a representation in the SKI combinator set as:

S (S (K S) K) (S (S (K S) K) I)

which is 11 combinators. Using the Turner set, this becomes:

S (S B* I) I

Only five combinators. This means that combinator graph reduction will be much more efficient.

Log in or register to write something here or to contact authors.