SKI -Transformation, wie man in einer funktionalen Sprache programmiert

Question

Ich stehe vor dem folgenden Prolog -Code. Der Ausdruck [x] >> y steht für den Lambda -Expression Lambda xy Der Code eliminiert die Lambda und ergibt einen kombinatorischen Ausdruck über S, K und 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)).

Hier ist ein Beispiel, wie es funktioniert:

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

Angenommen, ich möchte das gleiche codieren Wandlung in Haskell, ML oder dergleichen. Wie kann ich das machen? Kann ich die Lambda -Ausdrücke direkt in der funktionalen Programmiersprache verwenden? Oder muss ich mich zu einigen Meta -Programmiereinrichtungen zurückerregen?

Mit freundlichen Grüßen

PS: Der obige Code ist nicht die Skikonvertierung, die zu sehr kurzen Skiausdrücken führt. Besserer Code ist möglich, dass Überprüfungen nach Auftreten der gebundenen Variablen im Lambda -Expressionskörper.

Answer 1

Ihr Prolog -Code kann fast wörtlich in eine Musteranpassung von ML oder Haskell übersetzt werden. Natürlich müssten Sie Ihr eigenes ADT für Lambda -Ausdrücke definieren. Und für den optimalsten Satz von Kombinatoren und Konvertierung für diesen Satz würde ich empfehlen, auf die ich mich beziehen würde http://www.amazon.com/functional-programming-international-computer-science/dp/0201192497

Answer 2

Sie können Lamdba -Ausdrücke direkt verwenden. 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

(Beachten Sie, dass ich nicht wusste, dass Ski zu wissen, dass dieses Snippet eine direkte Umwandlung der Definitionen auf Wikipedia in Haskell ist. Es funktioniert, prüft jedoch, ob es konzeptionell richtig ist)