Today I found out where the one-letter names of some functions in combinatory logic come from. I’d seen these before (for example, in To Mock a Mockingbird) but I had no idea what inspired the names.

These functions — I, K, S, T, and Z — are known as the Schönfinkel combinators, and their names are somewhat mnemonic in German. (Only somewhat. Don’t get your hopes up.)

Definition | Name | Name origin |

λx. x | I | Identitätsfunktion (identity function) |

λx,y. x | K | Konstanzfunktion (constant function) |

λx,y,z. xz(yz) | S | Verschmelzungsfunktion (amalgamation function) |

λx,y,z. xzy | T | Vertauschungsfunktion (exchange function) |

λx,y,z. x(yz) | Z | Zusammensetzungsfunktion (composition function) |

Source: Practical Foundations of Mathematics, footnote on page 89. Available online here.

If you’re not familiar with the notation in the function definitions, see this introduction to lambda calculus.

* * *

For a daily dose of computer science and related topics, follow @CompSciFact on Twitter.

But why Y?

Rather than “Z” and “T”, I was taught “B” and “C” (respectively). Any idea where they came from?

And then, of course, there’s Y.

Hey John,

sorry but you have a few spelling errors in there:

Konstanzfunktion should be Konstante Funktion (Konstanz is a town in Germany :) ).

Vershmelzungfunktion is missing a c and an s, as in Verschmelzungsfunktion.

Vertauscungsfunktion is missing an h, as in Vertauschungsfunktion.

Zusammensetzungfunktion is missing an s, as in Zusammensetzungsfunktion.

Though in German, I think you use Identitätskombinator, Konstantenkombinator, etc.

Pseudonym: The same footnote says “the last two were called C and B respectively by Haskell Curry, who introduced several others.”

Thomas: Paul Taylor writes “Konstanzfunktion” but the rest of the spelling errors are transcription errors on my part. I’ve updated the post to squeeze in the letters I left out.

Peter: Nice pun. :)

I haven’t found where the name Y comes from. The answer may be in “Combinatory Logic, Volume 1” by Haskell Curry and Robert Feys, 1958. They define Y on page 178. I don’t have the book, so I’m going by Google Books and it doesn’t give much context. All I can see is

“We call Y the paradoxical combinator. (We may have other combinators”

Y not Y?

Interesting. I shared an office with Mike Joy (now Warwick) whose PhD was on combinators. At the time he wrote it, there was an almost complete alphabet of combinators from A to Z.

I hadn’t worked out the pun: Y = Why

If you’ve come across them S’, B’ and C’ are arguably more useful than S, B and C (they are switches).