According to the Wikipedia page on SKI-combinator calculus, I is the identity function, K is the constant function, and S is "substitution". I understand the first two, but I don't see what S has to do with substitution and wikipedia offers no explanation or clarification.
2026-03-25 11:11:46.1774437106
On
In what sense is the S-combinator "substitution"?
2.3k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
I think the name $S$ arises because of the role that the $S$ combinator plays in the conversion from lambda-terms. Suppose you have a lambda-term $\lambda a.(P Q)$ and you want to find an equivalent $SKI$-combinator. (The $S$ combinator is not involved except when the term has this form.) This term takes its argument $T$ and substitutes it into $P$ and $Q$ in place of the free variable $a$, then applies the result $P[a:=T]$ to the result $Q[a:=T]$.
When we convert to combinatory logic, there are no parameter variables. So in place of the $\lambda$-abstraction, we need a combinator which performs an analogous substitution operation on its arguments. This combinator, which we call $S$, will take $P$ and $Q$ and an argument $T$ and perform the combinatorial analogue of substitution before applying $P$ to $Q$. That is, we want $$S P Q T = (P T) (Q T).$$
The other two $SKI$-combinators, $K$ and $I$, do not perform this substitution. $I$ is used in the trivial case when one is converting the term $\lambda a.a$, and $K$ is used in the case where there is no substitution, when the bound variable $a$ does not appear in the body of the abstraction and so no substitution of the argument for the bound variable is necessary.
(I have been trying to find a citation for this explanation, which I think I did not make up myself, but not had any success so far. If I do find one I will add it.)
[Added 2021: It appears that the letter “S” was originally chosen not for its association with substitution, but because it was the first letter of schmelzen, “to fuse”, and that Schönfinkel understood the $S$ combinator not as a substitution operator but as a fusion operator. See my remarks in the other answer.]
Read the comments below this answer. It turns out that my reference was wrong.
These are the original combinators as Schönfinkel originally named them:
So... no. I can't think of any reasonable sense in which S means "substitution". I think an edit of Wikipedia is in order.
Source: Paul Taylor, Practical Foundations of Mathematics.
(This is too long for a comment, but it is directly pertinent, so I am adding it here. —MJD 2017)
I have been reading Schönfinkel 1924 again, and he does not seem to think of $S$ as anything like a substitution operator. One might think of it as a substitution operator if one were mainly interested in converting combinator expressions to functions, but Schönfinkel is mainly concerned with going in the other direction, and for him $S$ is a fusion operator, as his name for it suggests. (Verschmelz is to fuse or melt together, akin to English “smelt” and “melt”.) For Schönfinkel, the purpose of $S$ is that if you have an expression with a repeated subexpression, you can first apply $T$ and $Z$ to move the duplicated subexpression into the right position, so that the result has the form $(f x)(g x)$, and then you can “fuse” the two $x$es into one by using the $S$ operator: $(f x)(g x) → Sfgx$.
Schönfinkel does not seem to explain why he decided to name it $S$ instead of $V$. Note also that he used $C$ for what we now call $K$.
(Added this in 2021. — MJD)
I feel a little silly that I didn't think of this before: “Why he decided to name it $S$ instead of $V$” seems clear now. The name of the function is “Verschmelzungsfunktion”, but the “Ver-” is merely a prefix attached to the main signifier, “schmelz-”. Two of Schönefinkel's five functions begin with “Ver-“, so abbreviating either as “V” would have been confusing. Instead, it appears that Shönfinkel chose to abbreviate them with “S” for “schmelzen” (melt, fuse) and “T” for “tauschen” (swap, exchange) respectively.