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

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.

* * *

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

  6. Y because the letter Y has one stem which splits in two, just like what the function does. That’s probably the reason, or at least that’s how I look at it.

Leave a Reply

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