Трансформирование лыж, как программировать на функциональном языке

Question

Я сталкиваюсь с следующим кодом пролога. Выражение [x] >> y означает выражение Lambda Lambda xy, код устраняет лямбду и дает комбинаторную экспрессию над S, K и I:

convert([X]>>Y,'I') :- X==Y, !.
convert([X]>>Y,apply('K',Y)) :- var(Y), !.
convert([X]>>([Y]>>Z),R) :-
     convert([Y]>>Z,H), convert([X]>>H,R).
convert([X]>>apply(Y,Z),apply(apply('S',S),T)) :-
     convert([X]>>Y,S), convert([X]>>Z,T).
convert([_]>>Y,apply('K',Y)).

Вот пример, как это работает:

 ?- convert([X]>>([Y]>>apply(Y,X)),R).
 R = apply(apply('S', apply(apply('S', apply('K', 'S')), 
  apply('K', 'I'))), apply(apply('S', apply('K', 'K')), 'I'))

Предположим, я хотел бы кодировать то же самое обращение В Haskell, ML или тому подобное. Как я могу это сделать? Могу ли я использовать выражения Lambda, доступные на языке функционального программирования напрямую? Или мне нужно регрессировать на некоторые метапрограммные объекты?

С уважением

PS: приведенный выше код не является конверсией лыж, которая приводит к очень коротким лыжным выражениям. Возможно, лучший код, что проверяет на наличие связанной переменной в теле выражения Lambda.

Answer 1

Ваш пролог может быть переведен практически дословно в соответствие шаблона ML или Haskell. Конечно, вам нужно определить свой собственный ADT для выражений Lambda. И для наиболее оптимального набора комбинаторов и преобразования для этого набора, я бы порекомендовал обратиться к http://www.amazon.com/functional-programing-international-computer-science/dp/0201192497

Answer 2

Вы можете напрямую использовать выражения Lamdba. В Хаскелле:

i x = x
k x = \y -> x
s x y z = x z $ y z

r = s (s (k s) (k i)) (s (k k) i)

-- r 3 (+5) -> 8

(Обратите внимание, что я не знал, чтобы знать, чтобы знать, этот фрагмент представляет собой прямое преобразование определений в Википедии в Хаскелл; он работает, но проверяйте, правильно ли он концептуально)