5 ms·

This 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

by dvt 6y ago

This 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 ago
If 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 ago
    The impedance mismatch is too hard, given the nature of this medium... thanks for trying to help. Maybe next time?
    - carapace 6y ago
      Look 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.
      - mikewarot 6y ago
        Yes, having code that I can play with did help... but I can't figure out S, no matter what I give it, I always get some sort of error. TypeError: 'int' object is not callable
        dvt 6y ago
        Hint: if you pass it x, y, z where they are functions, it won't complain :) Python is (weakly) typed, so in your case, it tries to call 1(something) and that won't work. In (untyped) Lambda Calculus, everything is a function.
        mikewarot 6y ago
        I got S(I)(I)(I)(4) to return 4, everything else is errors.
        carapace 6y ago
        > TypeError: 'int' object is not callable Heh, yeah I did that too when I was wrapping my head around 'em. The thing to remember is that in SKI combinator logic nothing else exists. You can't pass 'int' objects to SKI because they don't exist in that universe. (Obviously you can in the sense that Python will let you do it, but it's logically meaningless.) (I had to break out pencil and paper and walk through some evaluations of SKI expressions by hand.) Let's have versions of I that also print their names and arg as a side effect: def E(x): print('E', x) return x def F(x): print('F', x) return x def G(x): print('G', x) return x Consider: S(E)(F) Start with the definition of S: S = lambda x: lambda y: lambda z: x(z)(y(z)) Substitute: S = lambda E: lambda y: lambda z: E(z)(y(z)) So now S returns this new function (call it S') that has the E function embedded in the closure: S' = lambda y: lambda z: E(z)(y(z)) That gets called on F: S'(F) Substitute: S' = lambda F: lambda z: E(z)(F(z)) And this creates S'' with both E and F embedded: S'' = lambda z: E(z)(F(z)) So the result is a function that takes some function z, calls F on it, calls G on it, and then calls the result of the first on the result of the second. S''(G) E(G)(F(G)) E(G) -> G ; prints "E <function G at 0x000001E0A4A741F0>" G(F(G)) F(G) -> G ; prints "F <function G at 0x000001E0A4A741F0>" G(G) prints "G <function G at 0x000001E0A4A741F0>" G <--- G returns itself. In action: In [16]: S(E)(F) Out[16]: <function __main__.<lambda>.<locals>.<lambda>.<locals>.<lambda>(z)> In [17]: S(E)(F)(G) E <function G at 0x000001E0A4A741F0> F <function G at 0x000001E0A4A741F0> G <function G at 0x000001E0A4A741F0> Out[17]: <function __main__.G(x)> Since G is also a version of I we can get away with passing it anything (not just functions): In [18]: S(E)(F)(G)("Hi!") E <function G at 0x000001E0A4A741F0> F <function G at 0x000001E0A4A741F0> G <function G at 0x000001E0A4A741F0> G Hi! Out[18]: 'Hi!' That's why you can pass anything to SIII (aka S(I)(I)(I) in Python) and it returns it, because SIII = I. In [19]: S(I)(I)(I) is I Out[19]: True HTH
    - dvt 6y ago
      I think you're definitely getting it, but you're also trying to see how these combinators are useful or at least usable. That's a bit of a tricky question because as @carapace mentions, you'd need to start combining them in interesting ways to get anything useful out of SKI.

by dvt 6y ago

mikewarot 6y ago

If 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 ago
  The impedance mismatch is too hard, given the nature of this medium... thanks for trying to help. Maybe next time?
  - carapace 6y ago
    Look 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.
    - mikewarot 6y ago
      Yes, having code that I can play with did help... but I can't figure out S, no matter what I give it, I always get some sort of error. TypeError: 'int' object is not callable
      - dvt 6y ago
        Hint: if you pass it x, y, z where they are functions, it won't complain :) Python is (weakly) typed, so in your case, it tries to call 1(something) and that won't work. In (untyped) Lambda Calculus, everything is a function.
        mikewarot 6y ago
        I got S(I)(I)(I)(4) to return 4, everything else is errors.
        carapace 6y ago
        > TypeError: 'int' object is not callable Heh, yeah I did that too when I was wrapping my head around 'em. The thing to remember is that in SKI combinator logic nothing else exists. You can't pass 'int' objects to SKI because they don't exist in that universe. (Obviously you can in the sense that Python will let you do it, but it's logically meaningless.) (I had to break out pencil and paper and walk through some evaluations of SKI expressions by hand.) Let's have versions of I that also print their names and arg as a side effect: def E(x): print('E', x) return x def F(x): print('F', x) return x def G(x): print('G', x) return x Consider: S(E)(F) Start with the definition of S: S = lambda x: lambda y: lambda z: x(z)(y(z)) Substitute: S = lambda E: lambda y: lambda z: E(z)(y(z)) So now S returns this new function (call it S') that has the E function embedded in the closure: S' = lambda y: lambda z: E(z)(y(z)) That gets called on F: S'(F) Substitute: S' = lambda F: lambda z: E(z)(F(z)) And this creates S'' with both E and F embedded: S'' = lambda z: E(z)(F(z)) So the result is a function that takes some function z, calls F on it, calls G on it, and then calls the result of the first on the result of the second. S''(G) E(G)(F(G)) E(G) -> G ; prints "E <function G at 0x000001E0A4A741F0>" G(F(G)) F(G) -> G ; prints "F <function G at 0x000001E0A4A741F0>" G(G) prints "G <function G at 0x000001E0A4A741F0>" G <--- G returns itself. In action: In [16]: S(E)(F) Out[16]: <function __main__.<lambda>.<locals>.<lambda>.<locals>.<lambda>(z)> In [17]: S(E)(F)(G) E <function G at 0x000001E0A4A741F0> F <function G at 0x000001E0A4A741F0> G <function G at 0x000001E0A4A741F0> Out[17]: <function __main__.G(x)> Since G is also a version of I we can get away with passing it anything (not just functions): In [18]: S(E)(F)(G)("Hi!") E <function G at 0x000001E0A4A741F0> F <function G at 0x000001E0A4A741F0> G <function G at 0x000001E0A4A741F0> G Hi! Out[18]: 'Hi!' That's why you can pass anything to SIII (aka S(I)(I)(I) in Python) and it returns it, because SIII = I. In [19]: S(I)(I)(I) is I Out[19]: True HTH
  - dvt 6y ago
    I think you're definitely getting it, but you're also trying to see how these combinators are useful or at least usable. That's a bit of a tricky question because as @carapace mentions, you'd need to start combining them in interesting ways to get anything useful out of SKI.