Комбинатор S в Erlang

Я начинаю изучать лямбда-исчисление, и мне нужно реализовать комбинаторы I, S, K в Erlang. Конечно, S, K, I означает:

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

У меня нет проблем с пониманием преобразования I = SKK на бумаге (как показано здесь: Чтобы доказать, что SKK и II являются бета-эквивалентными, лямбда-исчисление), но кажется, что я не понимаю, когда речь идет о функциональных языках и функциях высокого порядка...

Мне удалось сделать I и K (скажем, в модуле test):

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

Также я знаю, как запустить K x (K x) (SKK x = K x (K x))

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

Но я не могу заставить себя написать S-комбинатор. Я старался:

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

Но все же я не могу преобразовать СКК х в х

Я пытаюсь запустить это так:

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

Любая помощь будет оценена по достоинству, так как я полностью потерян.


lambda erlang lambda-calculus s-combinator
person Krodak    schedule 17.10.2011    source источник
comment
Действительно, ваша проблема чисто условная. Если вы понимаете, как работает бета-редукция, то, конечно, вы понимаете эту идею. Остальное просто обозначения.   -  person I GIVE CRAP ANSWERS    schedule 17.10.2011

Ответы (1)


arrow_upward
7
arrow_downward

Из оболочки Erlang:

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

Или как функции в модуле:

i(X) -> X.
k(X) -> fun(Y) -> X end.
s(X) -> fun (Y) -> fun (Z) -> (X(Z))(Y(Z)) end end.
person RichardC    schedule 17.10.2011
comment
хорошо, у меня все еще есть некоторые проблемы :/ В моем модуле у меня есть: i (X) -> X. k (X) -> fun (Y) -> X end. s(X) -> развлечение (Y) -> развлечение (Z) -> (X(Z))(Y(Z)) конец конец. skk(X) ->((s(k))(k))(X). Когда я запускаю (tppr — это имя модуля): tppr:skk(x). я получаю: ** exception error: bad function k in function tppr:'-s/1-fun-0-'/3 Что мне не хватает? - person Krodak; 17.10.2011
comment
В вашем определении skk(X) ->((s(k))(k))(X) вы написали k в нижнем регистре — это атом 'k', а не функция k/1. Если вы вместо этого напишете skk(X) ->((s(fun k/1))(fun k/1))(X), это должно сработать. - person RichardC; 17.10.2011
comment
Спасибо, да, так и было, глупо, надо признать ;) - person Krodak; 17.10.2011