-
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)
)
)En fait, le fonctionnement de la composition repose sur l'utilisation conjointe d'une affectation et d'un check. Composer ici consiste à identifier les affectations que l'on placera en avant-dernière place dans le check, l'instruction finale étant le push.
Prenons un nouvel exemple:
(map '* (map '+ '(1 2 3)))Il s'agit d'une composition de deux maps.
Le map interne à l'expression sera évidemment compilé sous la forme suivante:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(setq v (+ i i))
(push r v)
)Remarquons ici que le '+' est transformé en: (+ i i).
L'application du map externe consiste simplement à réécrire l'affectation en une nouvelle opération où l'élément de base ne sera plus i mais (+ i i):
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(setq v (* (+ i i) (+ i i)))
(push r v)
)Enfin, si l'on veut appliquer deux filter l'un dans l'autre:
(defun odd(x) (neq (% x 2) 0))
(filter '(< 10) (filter 'odd '(1 10 2 3 9 12 21 4)))Nous obtiendrons deux check imbriqués l'un dans l'autre, chacun appliquant sa condition à i:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(check (odd i)
(check (< i 10)
(push r i)
)
)
)Remarquons que le test le plus imbriqué est le test externe dans notre composition de filter.
La composition se fait en effet en profondeur dans la structure.
Prenons un dernier exemple:
(map '* (filter '(< 100) (map '+ '(1 10 2 3 9 12 21 4) ) ) )Cet exemple comprend un map interne encapsulé dans un filter lui-même imbriqué dans un map.
Le map interne applique un '+' tandis que le map externe applique un '*'. Nous allons en tenir compte pour effectuer notre composition.
Tout d'abord la structure: (filter... (map... nous est connu:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(setq v (+ i i))
(check (< v 10)
(push r v)
)
)L'intégration du (map '* est évidement plus complexe. Il faut d'abord comprendre que l'opérateur '*' doit s'appliquer au v dans l'affectation. Comme le filter s'applique avant ce map, nous en concluons que la nouvelle valeur à calculer doit s'insérer au sein du check.
La composition nous donne donc:
(setq r ())
(loop i '(1 10 2 3 9 12 21 4)
(setq v (+ i i))
(check (< v 10)
; injection en profondeur du map externe au sein du check
(setq vv (* v v))
; désormais notre nouveau focus est 'vv' que l'on pousse dans 'r'
(push r vv)
)
)Ainsi, la composition se construit par injection en profondeur des contraintes et opérations imposées par ces fonctions...
Il suffit de suivre 'vv' pour encapsuler d'autres appels à map ou à filter. Un nouveau filter par exemple, prendrait 'vv' pour tester sa condition, tandis qu'un nouveau map créerait un 'vvv' qui prendrait 'vv' comme source de son calcul. Et ainsi de suite ad infinitum.
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.