Where combinator names come from

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.)

DefinitionNameName origin
λx. xIIdentitätsfunktion (identity function)
λx,y. xKKonstanzfunktion (constant function)
λx,y,z. xz(yz)SVerschmelzungsfunktion (amalgamation function)
λx,y,z. xzyTVertauschungsfunktion (exchange function)
λx,y,z. x(yz)ZZusammensetzungsfunktion (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.

CompSciFact twitter icon

8 thoughts on “Where combinator names come from

  1. 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.

  2. 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.

  3. 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.

  4. 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”

  5. 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).

Leave a Reply

Your email address will not be published. Required fields are marked *