6.9 Injecter du Haskell dans Lisp

De Haskell à 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.

Evaluation différée

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]

Composition

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..]
166650

Comme 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.

map/filter

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.

(map fonc liste)

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

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.

Composer

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

take, drop, fold et scan

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.

Programmation sans états

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.

C'est quoi le problème?

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:

• Difficulté à débogguer, 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 ces architectures n'est hélas plus à démontrer...

Structures de données

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. Une première rencontre avec ces objets se traduit souvent par des questions du style: "mais comment on change les valeurs de ces bousins ?"

Evidemment, il n'y a pas de réponse...

Car les structures de données dans un langage 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.