SCI trasformare, come programmare in un linguaggio funzionale

Question

sto affrontando il seguente codice Prolog. L'espressione [X] >> stand Y per l'espressione lambda lambda X.Y. Il codice elimina lambda e dà un'espressione combinatoria su S, K e 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)).

Ecco un esempio di come funziona:

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

Supponiamo Vorrei codice stesso conversione in Haskell, ML, o simili. Come posso fare questo? Posso usare le espressioni lambda disponibili nel linguaggio di programmazione funzionale direttamente? O devo regresso di alcune strutture meta di programmazione?

Con i migliori saluti

P.S .: Il codice di cui sopra non è la conversione SCI che conduce a brevissimo espressioni di sci. codice migliore è possibile che i controlli di occorrenza di la variabile associata nel corpo espressione lambda.

Answer 1

Il tuo codice di prologo può essere tradotto quasi alla lettera in un pattern matching di ML e Haskell. Naturalmente avrete bisogno di definire il proprio ADT per le espressioni lambda. E per la maggior set ottimale di combinatori e di conversione per il set mi consiglia di fare riferimento a http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497

Answer 2

È possibile utilizzare direttamente le espressioni Lamdba. In 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

(si noti che non sapevo di sci da sapere, questo frammento è una conversione diretta delle definizioni di Wikipedia in Haskell, funziona, ma fare controllare se è concettualmente a destra)