[dunham]

In the base definition are no numbers involved. Just S K and I, with these rewrite rules:

    S x y z = x z (x z)
    K x y = x
    I x = x

So, you can think of the whole thing as a list of S K I and parenthesized sequences of S, K, and I.

If you see S up front, you take the next three things (call then x y and z) and put them back on in this order x y (x z). x, y, and z are either a letter or a parenthesized sequence of letters and parentheses.

Note that S is the only combinator that makes the list longer.

If you want to think of them as functions they need to be _curried_. So they take one argument at a time and return a new function that takes the next argument. In javascript, if "(x, y) => x + y" were your function, the curried version would be: "x => y => x + y".

Expressed in javascript, our combinators are like: (but lazily evaluated)

    let S = x => y => z => x(z)(y(z))
    let K = x => y => x
    let I = x => x

Note for example that (K x) would be a new function that takes one more value, throws it away and returns x. K is sometimes called the constant function.

True / False are represented by building an expression that returns either the first thing that comes after it, or the second thing. So True/False are in essence their own if statements:

    T t e = t
    F t e = e

(I'll call the variables t and e for "then" and "else".)

So T = K, and SK will do what F is doing above, we apply it to t e and expand using the rules above to see:

    S K t e = K e (t e) = e

You can think of this as just applying the rewrite rules above, but it sounds like you want to also think of it in terms of functions. In which case, in the javascript notation you're looking at:

    S(K)(t)(e)

S is applied to K to get a new function that takes two more arguments, above we wrote:

    S = x => y => z => x(z)(y(z))

so

    S(K) is y => z => K(z)(K(y(z))

Applying this to 't', we get

    S(K)(t) is z => K(z)(K(t(z))

And then applying this to e:

    S(K)(t)(e) is K(e)(K(t(e)))

Now K(e) is (anything) => e, so the K(t(e)) is just thrown away.

This is where trying to express it in javascript gets a little wiggy. The t(e) here might not make sense. The K(e) function throws away the K(t(e)) but in javascript all of the arguments are evaluated before handing them to the function, so it would evaluate t(e) and then K(t(e)) before handing it K(e), where it is then ignored.

In the SKI calculus, recursion relies on this laziness (or you'd loop forever going down a path that would be thrown away).

Numbers can be expressed as functions using _Church encoding_.

  Zero f x = x
  Succ num f x = f (num f x)

Here, Zero is 0, Succ Zero is 1, Succ (Succ Zero) is 2, etc. If you expand this out, it looks like:

  Zero f x = x
  One f x = f(x)
  Two f x = f(f(x))
  ...

So a number ends up being something that takes a function and a value and calls the function on the value that number of times. There are ways to do addition, subtraction, multiplication, etc.

If you want to go deep down this rabbit hole, there was an IOCCC entry that was a simplified version of Haskell that compiled down to the SKI calculus - and it could compile itself. The process of developing it is written up here:

   https://crypto.stanford.edu/~blynn/compiler/

It's pretty dense stuff, but fascinating.

[mikewarot]

Elsewhere in the thread, was a YouTube link showing demos of church numbers, all in javascript. It was interesting, and there was a function to take church numbers and convert them back to normal whole numbers. I get the big picture, but am hung up on a detail or two.

>S K t e = K e (t e) = e

S K t e = K e (t e) // that makes sense

What is (t e)? I got to the same point in the python example down thread.

[dunham]

Yeah, I tried to mention that near the end, but it can be hard to explain.

It is "t" applied to "e" - so it would be t(e) in javascript notation. This could be nonsensical, but because of lazy evaluation it never gets expanded/evaluated. (K doesn't use its second argument.)

The SKI stuff is defined as applying those replacement rules from the outside in, so:

    K e (t e) ... ->  e ...

you take that whole expression from the front (K and the next two expressions) and replace it with the expression that was in the first argument's location. But (t e) here is dropped without ever being expanded / evaluated.

Most languages fully evaluate arguments before passing them to functions, but a few rare languages like Haskell don't evaluate the arguments until they're needed. So for

    K e (t e)

it will assign the whole tree (t e) wherever y occurs in the function definition, and just keep passing it along until something needs its value (if you use apply it to something like a function, use it in a case statement, or pass it to a primitive function like plus).

The miranda language (whose source was recently published) is also lazy, and works by compiling your code down to SKI combinators and then evaluating them. So this actually has been used in practice.