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