SKI transformer, comment programmer dans un langage fonctionnel

Question

Je suis face le code Prolog suivant. L'expression [X] >> Y peuplements pour l'expression lambda lambda X.Y. Le code élimine le lambda et donne une expression sur S combinatoires, K et 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)).

Voici un exemple comment cela fonctionne:

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

Supposons que je voudrais la même conversion du code dans Haskell, ML, ou similaires. Comment puis-je faire ceci? Puis-je utiliser les expressions lambda disponibles dans le langage de programmation fonctionnelle directement? Ou dois-je régressent à certaines installations de programmation de méta?

Cordialement

P.S .: Le code ci-dessus n'est pas la conversion ski qui conduit à très court expressions SKI. Code meilleur est possible que les contrôles pour occurence de la variable liée dans le corps de l'expression lambda.

Answer 1

Votre code Prolog peut être traduit presque mot pour mot dans une correspondance de motif de ML ou Haskell. Bien sûr, vous aurez besoin de définir votre propre ADT pour les expressions lambda. Et pour le plus ensemble optimal de combinateurs et conversion pour cet ensemble, je vous recommande de se référer à http://www.amazon.com/Functional-Programming-International-Computer-Science/dp/0201192497

Answer 2

Vous pouvez directement utiliser des expressions lamdba. Dans 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

(notez que je ne savais pas de SKI à savoir, cet extrait est une conversion directe des définitions sur Wikipédia en Haskell, cela fonctionne, mais faire vérifier si elle est conceptuellement à droite)