# Julia Language Combinators The SKI Combinator System

## Example

The SKI combinator system is sufficient to represent any lambda calculus terms. (In practice, of course, lambda abstractions blow up to exponential size when they are translated into SKI.) Due to the simplicity of the system, implementing the S, K, and I combinators is extraordinarily simple:

## A Direct Translation from Lambda Calculus

``````const S = f -> g -> z -> f(z)(g(z))
const K = x -> y -> x
const I = x -> x
``````

We can confirm, using the unit testing system, that each combinator has the expected behaviour.

The I combinator is easiest to verify; it should return the given value unchanged:

``````using Base.Test
@test I(1) === 1
@test I(I) === I
@test I(S) === S
``````

The K combinator is also fairly straightforward: it should discard its second argument.

``````@test K(1)(2) === 1
@test K(S)(I) === S
``````

The S combinator is the most complex; its behaviour can be summarized as applying the first two arguments to the third argument, the applying the first result to the second. We can most easily test the S combinator by testing some of its curried forms. `S(K)`, for instance, should simply return its second argument and discard its first, as we see happens:

``````@test S(K)(S)(K) === K
@test S(K)(S)(I) === I
``````

`S(I)(I)` should apply its argument to itself:

``````@test S(I)(I)(I) === I
@test S(I)(I)(K) === K(K)
@test S(I)(I)(S(I)) === S(I)(S(I))
``````

`S(K(S(I)))(K)` applies its second argument to its first:

``````@test S(K(S(I)))(K)(I)(I) === I
@test S(K(S(I)))(K)(K)(S(K)) === S(K)(K)
``````

The I combinator described above has a name in standard `Base` Julia: `identity`. Thus, we could have rewritten the above definitions with the following alternative definition of `I`:

``````const I = identity
``````

## Showing SKI Combinators

One weakness with the approach above is that our functions do not show as nicely as we might like. Could we replace

``````julia> S
(::#3) (generic function with 1 method)

julia> K
(::#9) (generic function with 1 method)

julia> I
(::#13) (generic function with 1 method)
``````

with some more informative displays? The answer is yes! Let's restart the REPL, and this time define how each function is to be shown:

``````const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
@eval Base.show(io::IO, ::typeof(\$f)) = print(io, \$(string(f)))
@eval Base.show(io::IO, ::MIME"text/plain", ::typeof(\$f)) = show(io, \$f)
end
``````

It's important to avoid showing anything until we have finished defining functions. Otherwise, we risk invalidating the method cache, and our new methods will not seem to immediately take effect. This is why we have put semicolons in the above definitions. The semicolons suppress the REPL's output.

This makes the functions display nicely:

``````julia> S
S

julia> K
K

julia> I
I
``````

However, we still run into problems when we try to display a closure:

``````julia> S(K)
(::#2) (generic function with 1 method)
``````

It would be nicer to display that as `S(K)`. To do that, we must exploit that the closures have their own individual types. We can access these types and add methods to them through reflection, using `typeof` and the `primary` field of the `name` field of the type. Restart the REPL again; we will make further changes:

``````const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
@eval Base.show(io::IO, ::typeof(\$f)) = print(io, \$(string(f)))
@eval Base.show(io::IO, ::MIME"text/plain", ::typeof(\$f)) = show(io, \$f)
end
Base.show(io::IO, s::typeof(S(I)).name.primary) = print(io, "S(", s.f, ')')
Base.show(io::IO, s::typeof(S(I)(I)).name.primary) =
print(io, "S(", s.f, ')', '(', s.g, ')')
Base.show(io::IO, k::typeof(K(I)).name.primary) = print(io, "K(", k.x, ')')
Base.show(io::IO, ::MIME"text/plain", f::Union{
typeof(S(I)).name.primary,
typeof(S(I)(I)).name.primary,
typeof(K(I)).name.primary
}) = show(io, f)
``````

And now, at last, things display as we would like them to:

``````julia> S(K)
S(K)

julia> S(K)(I)
S(K)(I)

julia> K
K

julia> K(I)
K(I)

julia> K(I)(K)
I
`````` PDF - Download Julia Language for free