S combinator in Erlang

Question

I'm starting to learn lambda calculus and I need to implement I, S, K combinators in Erlang. Of course, S, K, I stands for:

S = λxyz.xz(yz) K = λxy.x I = λx.x

I have no problem understanding I=SKK transformation on paper (like presented here: To prove SKK and II are beta equivalent, lambda calculus) but it seems that I don't understand it when it comes to functional languages and high-order functions...

I managed to do I and K (lets say in module test):

i(X) -> X.
k(X) -> fun(Y) -> X end.

Also I know how to run K x (K x) (SKK x = K x (K x))

kxk(X) -> (k(X))(k(X)).

But I can't get it around to write S combinator. I tried:

s(X) -> fun (Y) -> fun(Z) -> X,Z (Y,Z) end end.

But still, I'm not able to transform SKK x into x

I try to run it like this:

skkx(X) ->  s((k((k(X))))).

Any help would be appreciated, as I'm completely lost.

Trincomalee

Indeed, your problem is purely notational. If you understand how beta-reduction works, then surely you understand the idea. The rest is just notation. – Belier

Answer 1

From the Erlang shell:

1> I = fun (X) -> X end.
#Fun<erl_eval.6.80247286>
2> K = fun (X) -> fun (Y) -> X end end.
#Fun<erl_eval.6.80247286>
3> S = fun (X) -> fun (Y) -> fun (Z) -> (X(Z))(Y(Z)) end end end.
#Fun<erl_eval.6.80247286>
4> ((S(K))(K))(42).
42

Or as functions in a module:

i(X) -> X.
k(X) -> fun(Y) -> X end.
s(X) -> fun (Y) -> fun (Z) -> (X(Z))(Y(Z)) end end.

Gathers

ok, I still seems to have some problems :/ In my module I have: i(X) -> X. k(X) -> fun(Y) -> X end. s(X) -> fun (Y) -> fun (Z) -> (X(Z))(Y(Z)) end end. skk(X) ->((s(k))(k))(X). When I run (tppr is module name): tppr:skk(x). I get: ** exception error: bad function k in function tppr:'-s/1-fun-0-'/3 What am I missing? – Trincomalee

In your definition of skk(X) ->((s(k))(k))(X) you have written lowercase k - this is the atom 'k', not the function k/1. If you instead write skk(X) ->((s(fun k/1))(fun k/1))(X), it should work. – Gathers

Thank You, yes, that was the case, quite silly one, I must admit ;) – Trincomalee