1
$\begingroup$

In the SKI combinator calculus, Kxy returns the constant function which always returns x. Since y is always ignored, why not just define K as having a single parameter, namely, x? What is the purpose of having a variable y which is guaranteed to be ignored by K? I'm guessing that there would be some deleterious effect on the system if one were to omit y from the definition of K, but I can't figure out what that would be.

EDIT: For example, one can define K in terms of a simpler combinator, like, say:

$Jx := () \implies x$ (in JS anonymous function style). I.e., $J$ returns a thunk of $x$ just like $K$ does, but without the vestigial second parameter.

Then define $Kxy := Jx$. At that point the $SKI$ calculus is just the $SJ$ calculus since $K$ can be retrieved from $J$ and $I$ is definable in terms of $S$ and $K$.

$\endgroup$

1 Answer 1

1
$\begingroup$

Maybe it would help to think about it comparing to functions:

$K$ can be interpreted as the function with two arguments that returns the first. In Python, it would be

def K(x, y):
    return x

$I$ is the identity function. It can be written as:

def I(x):
    return x

Are those Python functions equivalent? No. To prove that the existence of $K$ is necessary, you can actually prove that $I$ can be expressed with only $S$ and $K$, but not the converse : $I = SKx$. Indeed, $SKxy = Ky(xy) = y = Iy$.

From a mathematical point of view: you need projections to do some computations. I am sure that you agree that working with multiple arguments. However, you sometimes need to only keep some of them. This is the same reason one of the basic operations of general recursive functions is the projection. In SK-calculus, you can use the $S$ rule to do a projection on a different argument.

$\endgroup$
5
  • $\begingroup$ Thanks @Nathaniel. And I'm wondering if I understand $K$ correctly. I thought it was a higher order function and returned a function, so that calls like "$Ky(xy)$" would go through. $\endgroup$
    – Hank Igoe
    Jan 8, 2023 at 19:03
  • 1
    $\begingroup$ There is always two points of view, depending on currying: you can see $K$ either as a function with two arguments, or as a function that takes one argument and returns a function that takes one argument. $\endgroup$
    – Nathaniel
    Jan 8, 2023 at 21:10
  • $\begingroup$ @Nathaniel Do you have a reference that contains a proof that the converse isn't possible? $\endgroup$
    – Sam Ezeh
    Jan 8, 2023 at 22:04
  • $\begingroup$ @SamEzeh Sorry, I have not. My guess is that it can be done by induction on the size of an expression using only $S$ and $I$. $\endgroup$
    – Nathaniel
    Jan 8, 2023 at 22:18
  • 1
    $\begingroup$ The $K$ combinator is higher-order, since it can accept functions as argument and return them. However there is an isomorphism between $(A \times B) \rightarrow C$ and $A \rightarrow (B \rightarrow C)$. This isomorphism is the essence of many constructions in functional programming and logic, and studied abstractly in cartesian closed categories. $\endgroup$ Jan 8, 2023 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.