There's an amazing amount of depth to SK logic, in terms of how we can use it, where it crops up, etc. but the basics of what it is should be graspable by any programmer. Each "combinator" is just a very simple function. We can write them in Javascript (or rewrite in any other language with first-class functions):
const I = x => x;
const K = x => (y => x);
const S = x => (y => (z => x(z)(y(z))));
const Y = x => (x(Y(x)));
When the game writes two such functions side-by-side `xy` (e.g. `SK`) that's calling the `x` function with `y` as an argument (e.g. `S(K)` in JS). The brackets in the game are for disambiguating, e.g. `SKI` is the same as `(SK)I` which is `S(K)(I)` in JS, whereas `S(KI)` is `S(K(I))` in JS.Some things to note:
- `I` and `Y` are redundant; we can get the same behaviour using combinations of just `S` and `K`
- `S` and `K` form a turing-complete programming language. In other words, not only can we implement SK logic inside Javascript, we can also implement a Javascript interpreter as a (massive) combination of `S` and `K`.
- Since SK logic is turing-complete, we can't solve the halting problem for it (i.e. we can't always tell if a combination of `S` and `K` will eventually stop reducing or go on forever).
- Most languages, like Javascript, evaluate the argument of a function call before running the function (they are "strict" or "eager"). That might cause some of these combinations to go into an infinite loop unnecessarily: e.g. `Kxy` should reduce to `x`, regardless of what `y` is; but the Javascript equivalent above would be `K(x)(y)`, which will evaluate `x` and `y` first. If `y` happens to go into an infinite loop, trying to evaluate `K(x)(y)` in Javascript will also cause an infinite loop, even though it should ignore `y` and just return `x`.
- The `Y` combinator will always cause such infinite loops; e.g. `Y(KI)` should reduce to `KI(Y(KI))`, and the `Y(KI)` (recursive call) should get discarded to leave `I`. Yet in Javascript the arguments (`I` and `Y(K(I))`) will always be evaluated first, which causes an infinite loop/stack overflow: `Y(K(I))` will become `K(I)(Y(K(I)))`, which will evaluate `I` and `Y(K(I))`, which will become `K(I)(Y(K(I)))`, which will evaluate `I` and `Y(K(I))`, and so on.
- There are alternatives to `Y` which will work in strict/eager languages; the most popular is called `Z`; `Z` can also be implemented using just `S` and `K`.
- Languages which don't evaluate their arguments first are called "non-strict". The LazyK language has non-strict evaluation, so it's a more "correct" implementation of SK logic than the simplistic JS functions above.
- LazyK is a "toy" language. Haskell is the most famous/popular example of a "real" language which is non-strict (although it's not very famous/popular!)