SKI

I've been playing around with combinators quite a bit over the past week for reasons that will become clear in due course. One of these combinator systems is SKI and it is Turing complete.

SKI is made up of three combinators. although it turns out you really only need two of them.

The I combinator is called the identity combinator. It just takes any arguments and returns the same thing. In Haskell it looks like this* [*These are my implementations of the combinators in Haskell. I think they're right. I guess part of the puzzle here is to see for yourself if they are in fact right.]:

let i xs = xs

The next combinator is a little more complex. It takes a function and a value; evaluates the function on the argument and then returns the function. Note that it throws the result of the computation away!

let k f xs = (\(a,b) -> b) (f xs, f)
let k f xs = f

Because Haskell uses lazy evaluation these two forms should be the same. The first though should make a little bit more explicit what is going on.

The final combinator is S. It does some odd function and meta-function calling (or is that function and function meta-calling?) thing. It takes three arguments. It calls the second with the last to yield a value. It then calls the first argument with the last to yield a function which it then calls on the value from the first part of the computation.

let s z y xs = ( z xs ) ( y xs )

Here's my attempt at what I think these might look like in Python:

def I(xs):
    return xs
def K(f, xs):
    f(xs)
    return f
def S(z, y, xs):
    v = y(xs)
    f = z(xs)
    return f(v)

Maybe that's a little clearer. Now here's the thing that has been occupying me.

Here is what I mean:

def I(*xs):
    return xs
def K(f, *xs):
    f(*xs)
    return f
def S(z, y, *xs):
    v = y(*xs)
    f = z(*xs)
    return f(v) # What about v?

Clearly it doesn't make it more powerful as the original was already Turing complete, but it might make it more expressive, i.e. it might make it simpler to write more complex programs in. What I'm afraid of is that it might break the Turing completeness. That would be unfortunate.

Anther question is what to do with v in the last line. Should it get a star or not?