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.