-
Notifications
You must be signed in to change notification settings - Fork 8
6.9 Injecter du Haskell dans Lisp
Tous les langages fonctionnelles tirent leur origine du Lambda-calcul et de sa première manifestation: Lisp. Certaines instructions emblématiques de Haskell telles que map ont même leur équivalent en Lisp depuis la nuit des temps. Ainsi MacCarthy proposait dès 1960 une instruction: mapList qui appliquait une même fonction à l'ensemble des éléments d'une liste. Mais la réalité est encore plus surprenante lorsque l'on fait l'inventaire des instructions offertes par Haskell. Ainsi, si Lisp est un ancêtre de Haskell, d'un point de vue historique, il est beaucoup plus près d'un grand-oncle qu'un ancêtre direct. Plus exactement, Haskell a été conçu par des mathématiciens autour des théorèmes et démonstrations du lambda-calcul, dont Lisp s'était en son temps inspiré.
Cependant Haskell propose aussi plusieurs mécanismes dont Lisp pourrait bénéficier directement.
L'évaluation différée (lazy evaluation en anglais), est un mécanisme qui permet l'évaluation d'une expression uniquement quand le besoin s'en fait sentir. Pour comprendre l'intérêt de ce mécanisme, imaginons une liste dont la définition est donnée via une expression arithmétique infinie: [1,2,3...]. Il est évidemment impossible d'extraire cette liste d'abord avant de lui appliquer un traitement ensuite. La seule façon de la manipuler est de la contraindre via une condition avec une fonction tel que takeWhile dont le rôle est d'arrêter l'itération dès que sa condition a été vérifiée.
takeWhile (<6) [1..]
[1,2,3,4,5]Mais l'intérêt de Haskell ne s'arrête pas là. En effet, ce langage sait composer les fonctions les unes avec les autres. On utilise souvent le . pour mettre cette composition en exergue (et supprimer aussi quelques parenthèses au passage !!!):
sum . takeWhile (<10000) . filter odd . map (^2) [1..]
166650Comme on le voit sur cet exemple, non seulement on a composé ensemble une suite de fonctions mais surtout, on a appliqué cette composition à une liste infinie que takeWhile borne avec la condition: < 10000.
Evaluation différée et composition sont deux aspects de Haskell dont l'intégration dans LispE nous a semblé importante.
Avant toute chose, nous allons nous intéresser aux deux fonctions les plus simples de notre arsenal: map et filter. Nous allons en particulier étudier la façon dont on peut les interpréter en LispE.
Qu'est-ce que map?
Cette fonction prend deux arguments. Elle applique le premier argument (une fonction ou un opérateur) au second argument, une liste d'éléments.
Prenons un exemple:
(map (lambda (x) (* x 2)) '(1 2 3 4))
;(2 4 6 8)Remarquons que LispE offre aussi une autre façon de rédiger une lambda à l'imitation de Haskell:
(map (\ (x) (* x 2)) '(1 2 3 4))On peut même écrire si l'on veut être encore plus lisible:
(map (λ (x) (* x 2)) '(1 2 3 4))L'interprétation d'un map la plus simple que l'on puisse imaginer est de voir cette fonction comme une boucle sur la liste en argument:
pour i dans liste calculer λ(i)
Or nous disposons d'une fonction en LispE qui fait exactement ça: loop
(loop i liste
( (λ (x) (* x 2)) i)
)Il manque une étape pour transformer cette opération en un vrai map. Il nous faut ranger le résultat dans une liste. Nous allons utiliser à cette fin le push qui range dans LispE une valeur à la fin d'une liste (Notons que dans la majorité des Lisp, cette instruction range la valeur au début de la liste).
(setq r ())
(loop i liste
; on applique notre fonction sur un élément de la liste
(setq v ( [λ (x) (* x 2)] i))
(push r v)
)Voilà, en fin de calcul, r contiendra notre liste finale.
Notons que LispE autorise l'utilisation des crochets: [] à la place des parenthèses pour rendre le code plus lisible.
filter renvoie une liste où seuls les éléments qui satisfont une condition particulière sont conservés.
(filter '(< 10) '(1 3 20 10 21 34 4 5))
;(1 3 4 5)De même que map, filter effectue une boucle sur la liste et vérifie, pour chaque élément, si la condition est vérifiée. Nous pourrions donc réécrire notre expression ci-dessus de la façon suivante:
(setq r ())
(loop i liste
(check (< i 10)
(push r i)
)
)Nous avons choisi de construire ce test avec check et non avec if. La raison en est simple. Lorsque la condition du check est vérifiée, les instructions qui suivent sont toutes exécutées les unes après les autres à la façon d'un block. En choisissant un check nous simplifions le processus d'injection de code. Il suffira d'insérer les instructions en tête ou en queue de la structure pour l'enrichir.
Nous avons donc transformé chacune de ces fonctions en une boucle loop. Imaginons maintenant que nous voulions composer ces deux fonctions.
Observons d'abord deux choses:
- Pour un map, l'application d'une fonction se traduit par la création d'une boucle et d'une variable
v. - Pour un filter, l'application de la condition se traduit par la création d'une boucle et d'un
check sur une condition.
Dans les deux cas, nous avons une boucle loop qui a exactement la même forme et que nous pouvons donc factoriser.
Si l'on prend l'exemple suivant:
(map '+ (filter '(< 10) '(1 10 2 3 9 12 21 4)))Nous allons extraire d'abord la boucle commune:
(loop i '(1 10 2 3 9 12 21 4) ...)Puis nous allons insérer notre condition:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(check (< i 10)
(push r i)
)
)Il nous faut maintenant introduire le map. Son introduction dépend à la fois de la condition mais aussi de la valeur poussée dans r.
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(check (< i 10)
(setq v (+ i i))
(push r v)
)
)Nous voyons sur le code généré que nous avons bien tenu compte de la condition et que nous avons introduit dans r le résultat de l'application de l'opérateur '+' exigé par le map.
Mais que se passe-t-il si nous inversons l'ordre des opérations:
(filter '(< 10) (map '+ '(1 10 2 3 9 12 21 4)))Le code initial pour le map sera le suivant:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(setq v (+ i i))
(push r v)
)Or la condition introduite par filter ne porte plus désormais sur i mais sur le résultat du map...
Ce que nous allons pouvoir re-transcrire de la façon suivante:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(setq v (+ i i))
(check (< v 10)
(push r v)
)
)La plupart des autres fonctions takewhile, take, dropwhile, drop, fold, scan sont de simples variations sur cette composition, introduisant parfois des variables supplémentaires pour contrôler par exemple le nombre d'itération. Ce qui est particulier ici, c'est que l'on compile ces fonctions sous la forme de code Lisp que l'on peut facilement visualiser ou même transformer. Ce choix peut paraître moins efficace qu'une interprétation directe de ces fonctions, mais il autorise à la fois les mécanismes d'évaluation différée et de composition sans qu'aucune modification profonde de l'interpréteur LispE ne soit nécessaire. De plus, cela permet de rendre ces notions plus claires et explicites pour des néophytes que ces concepts arrêtent souvent dans leur compréhension des langages de programmation fonctionnelle.
Si vous voulez voir en détail comment LispE compose ces différentes fonctions ensemble, le plus simple est de créer une fonction defun puis d'afficher son contenu :
(defun voir() (map '* (scanl1 '+ '(10 20 30))))
(prettify voir)
(defun voir ()
(#compose
(0 0)
(setq #accu0 (* (+ #accu0 #i0) (+ #accu0 #i0)) ; case intermédiaire pour la composition des opérations
(push #recipient0 #accu0) ; case intermédiaire pour la composition de l'enregistrement des résultats
(setq #recipient0 ()) ; le code réel commence ici
(setq #first0 true)
(loop #i0 '(10 20 30)
(ncheck #first0
(setq #accu0 (* (+ #accu0 #i0) (+ #accu0 #i0))
(setq #first0 nil)
(setq #accu0 #i0)
)
(push #recipient0 #accu0)
)
)
)L'exemple ci-dessus est une composition réelle telle qu'elle se présente dans LispE. Nous pouvons remarquer que les variables commencent par un # pour éviter toute confusion avec les variables utilisateur. ncheck est une fonction spécifique, qui exécute la première ligne, lorsque la condition échoue, ou la liste d'instructions après la première ligne. D'où :
-
lorsque nous entrons dans le corps de la boucle la première fois, #first0 est vrai, et nous exécutons l'initialisation de #acccu0 avec l'itérateur #i0 et nous mettons #first0 à nil.
-
Dans les boucles suivantes, puisque
#first0est nil, nous exécuterons le calcul réel dans :(setq #accu0 (* (+ #accu0 #i0) (+ #accu0 #i0))).
La programmation sans états est certainement parmi les concepts les plus fondamentaux de la programmation fonctionnelle.
Mais qu'est-ce donc ?
Si l'on devait donner une réponse simple, disons qu'il s'agit d'une approche de la programmation où l'exécution d'un programme ne peut être influencé par une exécution précédente. Autrement dit, le résultat de l'exécution de (f a b) donnera toujours le même résultat pour le même jeu d'arguments (a,b).
Prenons l'exemple suivant:
// Cette fonction dépend d'une variable globale
int etat = 0;
int f(int e) {
etat += e;
return etat;
}
cout << f(10) << " " << f(10) << " " << f(10) << endl;On peut voir dans l'exemple ci-dessus que des appels successifs à f avec le même argument donnera chaque fois des résultats différents. A chaque appel, etat changera de valeur et renverra une valeur différente.
Dans le cas de la programmation fonctionnelle, ce genre de programmation est généralement interdit ou déconseillé. Plus particulièrement, la notion de classe que l'on retrouve en Java et en C++ pose problème dans le sens où l'on peut modifier un champ déclaré dans un objet et par conséquent rendre les méthodes sensibles à des exécutions précédentes.
La plupart des informaticiens ont souvent une certaine difficulté à saisir pourquoi un tel comportement pose problème, puisque la modification des états au sein d'une instance est le plus souvent au coeur de leurs stratégies d'implantation.
En fait, les problèmes sont nombreux:
- Déboggage: la modification d'une seule variable peut avoir un impact sur du code à 1000 lignes de là
- Multi-tâches: si une fonction ou une méthode dépend d'une variable externe, l'accès concurrent à cette variable pose des problèmes métaphysiques que seuls des sémaphores sont à même de résoudre. La complexité de tels architectures n'est hélas plus à démontrer...
La solution est encore une fois donnée par Haskell: les structures de données.
Les structures de données ressemblent superficiellement à des descriptions de classe, ce qui jette souvent les informaticiens habitués à Java ou C++ dans une forme avancée de confusion mentale (oserai-je avoué que ce fut mon cas au début?). Une première rencontre avec ces objets se traduit souvent par des questions du style: "mais comment qu'on change les valeurs de ces bousins ?"
Evidemment, il n'y a pas de réponse...
Car les structures de données dans ces langages de programmation sont immuables (immutable).
- Dans Java on choisit une variable à travers laquelle on va exécuter une méthode.
- Dans Haskell, le choix de la fonction repose sur le polymorphisme. On cherche la fonction dont les paramètres correspondent au type des arguments.
Autrement dit, dans un langage fonctionnel, une instance d'une structure de données n'a d'autre rôle que de guider le choix d'une fonction.
Prenons un exemple simple.
Voici par exemple la description d'une classe pour gérer les cercles et les rectangles dans C++:
class Cercle {
public:
float rayon;
Cercle(r) {
rayon = r;
}
float surface() {
return (M_PI*r*r);
}
};
class Rectangle {
public:
float largeur, longueur;
Rectangle(float l, float L) {
largeur = l;
longueur = L;
}
float surface() {
return largeur*longueur;
}
};
void main() {
Cercle c(20);
Rectangle r(20,30);
cout << c.surface() << endl;
cout << r.surface() << endl;
//Rien n'empêche de modifier c:
c.rayon = 100;
cout << c.surface() << endl;
}
On peut parfaitement modifier les valeurs des instances et obtenir des valeurs différentes pour la surface à chaque fois.
Dans le cadre d'un langage fonctionnel, la logique est inversée. Les fonctions s'appliquent en fonction de leurs arguments.
(data [Cercle _] [Rectangle _ _])
(defpat surface( [Cercle r] ) (* _pi r r))
(defpat surface( [Rectangle w h] ) (* w h))
(println
(surface [Cercle 10])
(surface [Rectangle 10 20])
)