5 ms·
I've given an 101 minutes trying really hard to grok this... everything I've found skips the very basic definition of what S and K are for some astoundingly dum
by mikewarot 6y ago
I've given an 101 minutes trying really hard to grok this... everything I've found skips the very basic definition of what S and K are for some astoundingly dumb reason.
Stephen Wolfram obviously knows what he's talking about... but lacks Feynman's ability to put it into layman's terms.
My suspicion is that there is an implied list, and if you go off the end of the list, you get a hidden zero... if not, you get a one.
The SKI combinator Wikipedia page has a section about Boolean logic that comes close to making sense to me.
Please let me know if I'm getting this right.... restating the page, putting it into familiar notation
Booleans are a list of [1,0]
T(x,y) = x
F(x,y) = y
Applying this over Booleans
T(1,0) --> 1
F(1,0) --> 0
They then go to explain that
T(x,y) = K combinator
Then they go on to explain
False(x,y) = SK, which I think is K(S(Boolean)
It's at this point, I'm lost.
Is SK --> S(K(xy)) or K(S(xy))
I can't resolve that to get any further.
- rraghur 6y agoTry this video of you haven't already https://youtu.be/pAnLQ9jwN-E https://youtu.be/pAnLQ9jwN-E
- mikewarot 6y agoI did... thanks for the link. I also went back and started watching the first part.
- dvt 6y agoThis is what S and K (and I) are: S := λx.λy.λz.x z (y z) K := λx.λy.x I := λx.x There's nothing really more to it. What's weird/amazing is that just with these three (technically, just S and K, as I can be derived from them), you can compute anything.
- mikewarot 6y agoI still don't understand the way this breaks down... How many parameters do S,K,or I take? If x=11, y=12, z=13 what are S,K? I assume I = 11
- dvt 6y agoThis is more of a λ-Calculus question (unrelated to combinators, really). But S takes 3, K takes 2, and I takes 1. This isn't strictly correct because S/K/I isn't a function, but rather a chain of lambdas with no free variables (and we get the number of "parameters the function takes" by counting the lambda symbols). See §1 in [1]. In your specific case, S 11 12 = 12 K 11 12 13 = 11 13 (12 13) I 11 = 11 Keep in mind that the literals "11," "12," and "13" in λ-Calculus aren't numbers. [1] https://personal.utdallas.edu/~gupta/courses/apl/lambda.pdf https://personal.utdallas.edu/~gupta/courses/apl/lambda.pdf
- mikewarot 6y agoIf I understand this right... S takes 2 values, and returns 1 K takes 3 values, and returns the 1st, 3rd, and (2nd applied to 3rd) I returns the value it is given (like a no-op)
- dvt 6y ago> K takes 3 values, and returns the 1st, 3rd, and (2nd applied to 3rd) Everything applies: so, e.g., when we see something like ABC, we actually omit the parentheses; if we include them, we have (((A)B)C). This can be confusing because applications associate to the left, but lambdas associate to the right[1]. So 11 13 (12 13) is actually (((11)13)((12)13)). In roundabout English, 11 applies to 13 which then applies to the result of 12 applies to 13. [1] https://www.cs.cmu.edu/~anupamg/251-notes/lambda_calculus.pdf https://www.cs.cmu.edu/~anupamg/251-notes/lambda_calculus.pd...
- mikewarot 6y agoThe impedance mismatch is too hard, given the nature of this medium... thanks for trying to help. Maybe next time?
- carapace 6y agoLook here mate yer over thinking it innit? In Python: S = lambda x: lambda y: lambda z: x(z)(y(z)) K = lambda x: lambda y: x I = lambda x: x That there is runnable code and with it you can implement numbers, math, logic, etc. That's all the SKI combinators are: those functions. You apply them to themselves in various patterns and they model numbers and arithmetic and programming languages. In [1]: S = lambda x: lambda y: lambda z: x(z)(y(z)) In [2]: K = lambda x: lambda y: x In [3]: I = lambda x: x In [4]: K(I) Out[4]: <function __main__.<lambda>.<locals>.<lambda>(y)> In [5]: _(S) is I Out[5]: True In [6]: K(I)(S) is I Out[6]: True Hope that helps.
- dunham 6y agoIn 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.