SKI transformar, cómo programar en un lenguaje funcional

Question

Estoy frente al siguiente código Prolog. La expresión [X] >> Y representa para la expresión lambda lambda X.Y. El código elimina la lambda y da una expresión combinatoria sobre S, K y 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)).

Este es un ejemplo de cómo funciona:

 ?- 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'))

Supongamos que quisiera el mismo código conversión en Haskell, ML, o similares. ¿Cómo puedo hacer esto? ¿Puedo utilizar las expresiones lambda disponibles en el lenguaje de programación funcional directa? O tengo que regresión a algunas instalaciones de programación meta?

Saludos

P.S .: El código anterior no es la conversión de esquí que alcanza muy corto expresiones de esquí. Código mejor es posible que los cheques de ocurrencia de la variable ligada en el cuerpo expresión lambda.

Answer 1

Su código de prólogo puede ser traducido casi literalmente en una coincidencia de patrones de LD o Haskell. Por supuesto que había necesidad de definir su propio ADT para las expresiones lambda. Y en su mayor conjunto óptimo de combinadores y la conversión de ese conjunto se lo recomiendo para referirse a http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497

Answer 2

Puede utilizar directamente expresiones Lamdba. En Haskell:

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

(nota que no sabía de SKI hasta sabe, este fragmento es una conversión directa de las definiciones de Wikipedia en Haskell, ya que funciona, pero no comprobar si es conceptualmente derecha)