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