S Combinator

S.js

/*
S : \x y z -> x z (y z)
*/
// S :: (z -> (a -> b)) -> (z -> a) -> z -> b
function S(x, y, z) {
  return x(z)(y(z));
}

// example:
// add :: a -> a -> a
function add(x) {
  return function(y) {
    return x + y;
  }
}

// mult :: a -> a
function mult3(x) {
  return x * 3;
}

/*
S: x(z)(y(z));
   x(10)(y(10))     // sub 10 for z
   x(10)(mult3(10)) // sub mult3 for y
   add(10)(30);     // eval mult3(10) -> 30; sub add for x
   40               // eval add(10)(30) -> 40
*/
S(add, mult3, 10); // => 40

/*
but what does it mean? why the S combinator? Who cares? How is it useful?
Appears useful mostly for combinatory logic, not so much for real code. At least not directly.
*/

but what does it mean?

It means you fuse two functions into one (this is not the same as applying two functions, see program logic above). This is not really visible from the javascript code S(add, mult3, 10); where you can not have partial function application. One would have to write x => S(add, mult3, x); to make that visible.

why the S combinator?

Without the S combinator one would have to write add(10)(mult3(10)) this shows 10 being present in two positions. The S-combinator reduces this to a single position. Maybe it's useful to think of it as a computing primitive because it can substitute a value to two positions in the program logic.

Without the S combinator one could only do application (apply an argument to it's function). Programs with only application f(g(h(i(10)))) (let f,g,h and i be all pure functions without side effects) can never represent everything that is possible to compute with a computer. The S combinator together with the constant (the K combinator; 10 in the example) can represents all programs. There is a prize out now if somebody can prove only the S combinator by itself can also represent all programs (and thus a constant as well)

How is it useful?

It can be useful for cases where you don't just have a simple scalar (the number 10) but you have a structure (any other memory type that a scalar, for example a struct, class, array etc) which has "under the hood" logic for getting and setting the value. Consider [2].map(x => x * 2) here the implementation of Array already has the logic build in to get to the 2, apply the function and make sure you get a new array out.

But since the S combinator is not defined on Array, we don't have something like [2, 3].s(add, mult3). [2, 3].s(add, mult3) is supposed to represent in pseudo code [2, 3] + ([2, 3] * 3) = [2, 3] + [4, 6] = [6, 9]

Who cares?

It depends ... let's try to rewrite the array code without the S combinator. There are many ways to solve this, i just pick one to compare it to the S combinator way of solving it.

[2, 3].map(x => add(x)(mult3(x))

Now that might look a lot easier depending on what you are used to. Though s in the example above gets rid off all the "bookkeeping" of putting x in all the right places, which can be pretty nice if you have not just two functions to apply but a whole chain of functions. Basically it's just a different way of writing code from the programmers perspective and it comes down to preference. Though something can be said to use the same kind of primitives mathematicians use to describe the raw essence of combinatory logic, they too were looking at how to "refactor" their problems to make abstractions that are easier and more powerful (= applies to many pieces of code/math).

Appears useful mostly for combinatory logic, not so much for real code. At least not directly.

It depends on the language, some language have this as a primitive build in function into the standard library just as Array.map is build into the javascript runtime. Here is one example from haskell. You can read about it more here, scroll down to where it says "The <*> function is really interesting." To explain the example given in the documentation

Using ApplicativeDo: 'fs <*> as' can be understood as the do expression

do f <- fs
   a <- as
   pure (f a)

Here fs is add and as is mult3. The 10 is nowhere to be found because this represents x => S(add, mult3, x); which also didn't have the 10 literal there. The x is implicit. And the pure basically says you are done with the computation now and want to put the value back (into the array or so), instead of returning the computation itself for you to chain more stuff to it later (without pure).

Related video: https://youtu.be/UogkQ67d0nY?t=784

I love it that javascript is inspired by scheme, otherwise I would never, ever, ever understand this. Thank god JS exists.