Bill Clementson's Blog: Y Combinator in Erlang

Y Combinator in Erlang

Monday, June 11, 2007

It's always nice to come across old favorites when you're learning a new programming language. In reading some posts on the Erlang mailing list recently, I came across an implementation of the Y Combinator in Erlang (if you're not familiar with the Y Combinator, you might want to read this intro, or this one, or the pedagogical introduction to Y in The Little Schemer). A little googling showed that this had come up before on the Erlang mailing list; but this was the first time I had come across an Erlang version of Y.

The code for the Y Combinator in Erlang looks very similar to the equivalent in Scheme:

Scheme Y Combinator:

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

Erlang Y Combinator:

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

So, we can define a factorial function, assign it to a variable

Fac = fun (F) ->
	      fun (0) -> 1;
		  (N) -> N * F(N-1)
	      end
      end.

and call it using the Y combinator function:

(emacs@bc)8> (y(Fac))(5).
120

But, we don't even have to assign it to a variable, we can just call it as an anonymous function (even though it calls itself recursively!):

(emacs@bc)10> (y(fun (F) -> fun (0) -> 1; (N) -> N * F(N-1) end end))(5).
120

And, if we "tweak" our Y combinator function to accept another argument that is a function that is to be "applied" against the function call, then we can even implement something like argument tracing on the calls to our anonymous function:

%% Y Combinator that does something to the called function
ya(F1, M) ->
    G = fun (F) -> M(fun (A) -> F1(F(F), A) end) end,
    G(G).

%% Make a factorial function that has argument tracing
fact_args() ->
    Apply =
	fun (F, A) ->
		R=apply(F, [A]),
		io:format("arg:~p, result:~p~n", [A, R]),
		R
	end,
    Fact =
	fun (F) ->
		fun (0) -> 1;
		    (N) -> N * F(N-1)
		end
	end,
    ya(Apply, Fact).

To test it out:

(emacs@bc)11> Fact_Args = fact_args().
#Fun
(emacs@bc)12> Fact_Args(5).
arg:0, result:1
arg:1, result:1
arg:2, result:2
arg:3, result:6
arg:4, result:24
120

Of course, we could have just used our modified Y combinator function to create an anonymous function that applies an anonymous "apply" function to an anonymous recursive "factorial" function to get the same result:

(ya(fun (F, A) ->
	    R=apply(F, [A]),
	    io:format("arg:~p, result:~p~n", [A, R]),
	    R
    end,
    fun (F) ->
	    fun (0) -> 1;
		(N) -> N * F(N-1)
	    end
    end))(5).

:-)

June 2007
Sun	Mon	Tue	Wed	Thu	Fri	Sat
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
May Jul