Y Combinator in Clojure

Even if it is hard to explain why, I particularly like the Y combinator. It isn't very practical in most "standard" languages. However, there is something poetic with it.

A couple of years ago I came from long exposure to SML and Haskell. As a consequence, when I started working with Erlang, I really missed the possibility to define everything as an anonymous inner function. I tended to organize my functions with inner sub-functions that often were recursive. As far as I knew (and still know), in Erlang it is rather hard to do this kind of things. First, the syntax is less clear than the Haskell equivalent and second, the "lambda" functions cannot be recursive. As a consequence, I tried using the Y combinator. And no, it is not a particularly good idea, but I enjoyed it.

Some times later, I tried to work with the Y combinator in Python. As Python completely lacks any form of tail call optimization, this is a very bad practice. However, I really liked the idea of using the Y combinator as a decorator... and that is almost as nice as the "apply decorator trick". Well, of course the apply decorator trick has no drawbacks and can be employed in real settings. The Y combinator in Python cannot (besides, the implementation I gave works only with functions with one argument, but the extension to arbitrary functions is trivial).

Back to clojure... I decided to implement Y in clojure as well. Of course, since clojure does not have TCO either, it is just a toy device. Moreover, there is no need for such a tool (as the syntax for nested recursive functions in clojure is nice). However, as I said... I love the Y combinator.

Well... this is the clojure version:

(defn Y [F]
  (let [G (fn [K]
        (F (fn [& A]
         (apply (K K) A))))]
    (G G)))


(def fact
     (Y (fn [f]
      (fn [n]
        (if (<= n 0)
          1
          (* n (f (- n 1))))))))


End of the story (yeah, basically it is like the scheme version). By the way... I'm starting toying with trampolines to see what can be done.

Clojure, Y Combinator, Programming

The Y combinator in Python

I’ve been asked how would the Y combinator look like in Python (see comments of this post; comments are lost with the migration). In that post the Y combinator is also explained detailedly (and may be an interesting reading).

Python is an imperative language, however, its functions are first class citizens and can be manipulated in a quite functional way. We have closures, anonymous functions and recursion. That’s all we need to build the Y combinator in Python.

Moreover, the Y combinator in Python looks like a decorator. Quite unfortunately, using recursion in Python is usually a poor choice. Python has a rather low limit on recursive calls (and even if you can rise it, it’s not good programming practice).

In Python function calls are quite expensive and there is no tail recursion optimization.
Indeed, even though Python is great in manipulating functions (and is something I use relatively often), recursion should not the preferred method to loop. It’s much better to use iterators/generators in for loops ore as a second (usually inferior) choice, while loops.

However, this is the implementation of the Y combinator in Python (along with the traditional factorial example):

def y(f):
    def g(k):
        return f(lambda a: (k(k))(a))
    return g(g)

@y
def fact(h):
    def fact_aux(n):
        if n == 0:
            return 1
        else:
            return n * h(n-1)
    return fact_aux

print fact(5)

Anonymous Recursive Erlang Functions with and without the Y combinator

In Erlang creating recursive anonymous recursive functions is not trivial. Basically the point is that the anonymous function has no name (gee...), thus you can’t reference a function inside it’s own definition. Which makes sense, by the way. In Haskell, for example, this problem does not exist. You can write:

main =
    let fact 0 = 1
        fact n = n * fact (n-1)
    in show $ mainfact 5

and everything works as expected. If we want to write this in Erlang we can’t just write:

main() ->;
    fact = fun(0) -> 1;
              (N) -> N * fact(N-1)
           end,
    io:format("~p~n", [fact(5)]).

because fact is not bound when we examine the anonymous function body. The solution is dramatically trivial.

First think about this:

X = fun(X) -> X(X) end,
    X(X).

Ok: you got it, it loops forever (Ctrl-C is your friend). Basically you forever call X.

However, it’s not hard to see how we can implement some kind of counter:

-module(recursive).
-compile(export_all).

main() ->
    F = fun(0, F) -> io:fwrite("Stop.\n");
           (N, F) -> io:format("~p~n", [N]),
    F(N-1, F)
end,
F(3, F).

We just did recursion with Erlang anonymous functions. If you, like me, just wanted a solution to this problem, you may stop reading here. Now we will get to the Y combinator solution extending this way of thinking and then will present the Y combinator from a theoretical point of view.

We’ve got a function with 2 parameters, one of which is just a way to carry around the function itself. What happens if we decide to curry the function? What does currying mean? From wikipedia:

In computer science, currying, invented by Moses Schönfinkel and Gottlob Frege, and independently by Haskell Curry, is the technique of transforming a function that takes multiple arguments (or more accurately an n-tuple as argument) in such a way as it can be called as a chain of functions each with a single argument.

Of course, you want to reverse the parameters so that we have:

main2() ->
    F = fun(F, 0) -> io:fwrite("Stop.\n");
           (F, N) -> io:format("~p~n", [N]),
    F(F, N-1)
    end,
    F(F, 3).

Then the idea is that:

f: A x B → C

becomes:

f: A → (B → C)

so that the return value of f(x) is a function h: B → C. Thus f(x, y) becomes (f(x))(y).

Ok, nothing new under the sun. Haskell programmers curry and uncurry functions all the time. You can do that even in Python! Well, kind of.

main3() ->
    F = fun(F) ->
            fun(0) -> io:fwrite("Stop.\n");
               (N) -> io:format("~p~n", [N]), (F(F))(N-1)
            end
        end,
    (F(F))(3).

Don’t you find that using (F(F))(x) all the time sucks? I do. The first thing I would do is to define:

g(F, N) ->
    (F(F))(N).

main4() ->
    F = fun(F) ->
            fun(0) -> io:fwrite("Stop.\n");
               (N) -> io:format("~p~n", [N]), g(F, N-1)
            end
        end,
    g(F, 3).

Well, quite more readable (as soon as you find some fancy name for g). However, this approach has at least one major drawback: we can use g to obtain some number, but functional programming is about function manipulation. Being able to build a recursive function from scratch is out ultimate goal.

The idea is that we should “inject” g behaviour into “F”. That is to say we should put into F something that has g behaviour as well. A key idea could be currying g:

g2(H) ->
    fun(N)->
        (H(H))(N)
    end.

main5() ->
    F = fun(H) ->
            fun(0) -> io:fwrite("Stop.\n");
               (N) -> io:format("~p~n", [N]), (g2(H))(N-1)
            end
        end,
    (g2(F))(3).

We are getting nearer to the solution. In fact g2(F)isalmost the function we are looking for.

Unfortunately it is not the right candidate to be passed to F as well.

Basically we want to write :

fun(H) ->
    fun(0) -> io:fwrite("Stop.\n");
       (N) -> io:format("~p~n", [N]),  H(N-1)
    end
end

and H should “do the right thing”. Moreover, we want to build H from out anonymous function in a fashion similar to what we got with g2(F). The idea of g2 is (using anonymous functions):

main6() ->
    F = fun(H) ->
           fun(0) -> io:fwrite("Stop.\n");
              (N) -> io:format("~p~n", [N]),
                ((fun(K) -> fun(A) -> (K(K))(A) end end)(H))(N-1)
           end
        end,
    ((fun(K) -> fun(A) -> (K(K))(A) end end)(F))(3).

this is done “factoring out” (fun(K) -> fun(A) -> (K(K))(A) end end). We leave H in its place and pass (fun(K) -> fun(A) -> (K(K))(A) end end) from the caller. Code is easier than the explanation.

main7() ->
    F = fun(H) ->
                fun(0) -> io:fwrite("Stop.\n");
                   (N) -> io:format("~p~n", [N]), H(N-1)
                end
        end,
    ((fun(K) -> F(fun(A) -> (K(K))(A) end) end)
        (fun(K) -> F(fun(A) -> (K(K))(A) end) end))(3).

Now things are quite messy and you have almost as many parentheses as if you were coding in Lisp. However, this way we were able to put the recursion logic out of F. And we are almost done.

Let’s give the (fun(K) -> F(fun(A) -> (K(K))(A) end) end) a name (G) and rewrite the messy code:

main8() ->
    F = fun(H) ->
            fun(0) -> io:fwrite("Stop.\n");
               (N) -> io:format("~p~n", [N]), H(N-1)
            end
        end,
    G = (fun(K) -> F(fun(A) -> (K(K))(A) end) end),
    (G(G))(3).

We notice that:

1. iteration logic is not in F
2. G does not substantially depend from how F is done.
3. We can define a function that takes F and using G returns the G(G) function

y(F) ->
    G = (fun(K) -> F(fun(A) -> (K(K))(A) end) end),
    G(G).

main9() ->
    F = fun(H) ->
                fun(0) -> io:fwrite("Stop.\n");
                   (N) -> io:format("~p~n", [N]), H(N-1)
                end
        end,

Recursive_F = y(F),
    Recursive_F(3),
    Recursive_F(7).

Well... the function we called yis the Erlang version of the Y combinator. Basically Y can be used to make recursive any erlang function with one argument. Besides, there are versions which can deal with functions with more formal parameters. However, the construction is quite the same as the one I presented for this version.