Programmation Fonctionnelle et Symbolique - Les fonctionnelles

5.1 Motivation
5.2 Les fonctions comme paramètres
5.3 Exercices
5.4 Conclusion

5.1 Motivation

Jusqu'ici nous n'avons vu que des fonctions dont les paramêtres -et les résultats- sont des objets de types relativement simples (entiers, listes, arbres, etc...), que l'on peut facilement définir par récurrence. Nous avons également vu que les fonctions ainsi définies suivent, dans la plupart des cas, des schémas de définition très voisins les uns des autres (comparer par exemple entre elles les fonctions vues en cours).

Dans une telle situation, il est donc assez naturel -pour un informaticien, par nature avare de ses efforts- de chercher a «récupérer» le schéma commun à plusieurs fonctions, pour pouvoir - en le paramêtrant - l'utiliser de plusieurs manières légèrement distinctes.

Voici par exemple une fonction lisp :

(de CARRE (X) (* X X)) Supposons que maintenant, pour une raison obscure, nous voulions écrire une fonction qui prend comme argument une liste de nombres et fabrique en retour la liste des carrés de ces nombres.

Voici la chose :

(de LISTE-CARRE (L) (cond ((null L) nil) ( T (cons (CARRE (car L)) (LISTE-CARRE (cdr L))) )) exemple d'utilisation : ?- (LISTE-CARRE '(1 2 3 4)) -> (1 4 9 16) Et si maintenant, si on veut calculer la liste des cubes des nombres d'une liste ? Il suffit de définir une fonction CUBE, et de remplacer partout CARRE par CUBE, et LISTE-CARRE par LISTE-CUBE.

Pourquoi ? Parce que LISTE-CARRE et LISTE-CUBE sont deux fonctions qui sont de la même famille: elles calculent la liste des images des éléments d'une liste par une certaine fonction, ici CARRE ou CUBE.

5.2 Les fonctions comme paramètres

L'idée va être de définir une fois pour toutes la manière de calculer la liste des images des éléments d'une liste par une certaine fonction (ce qu'on appelle le mapping de la fonction) en donnant une définition où la fonction intervient comme paramètre formel : (de MAP (F L) (cond ((null L) nil) ( T (cons (funcall F (car L)) (MAP F (cdr L))) )) La fonction FUNCALL permet d'appliquer une fonction reçue en paramètre à un certain nombre d'arguments (c'est une SubrN). Certains dialectes de Lisp permettent d'écrire directement (F (car L))..

On peut alors utiliser MAP sous la forme :

?- (MAP 'CARRE '(1 2 3 4)) Remarques :

Traditionnellement, une fonction dont au moins un paramêtre est une fonction est appelée fonctionnelle ou fonction d'ordre supérieur.
La notation lambda nous permet de désigner des fonctions sans leur donner de nom (fonctions anonymes). Par exemple : (LAMBDA (X) (+ X X 1)) désigne la fonction qui à tout X associe 2X+1. On peut donc écrire des choses comme: ?- (MAP (lambda (X) (+ X 2)) '(1 3 4 5 7)) -> (3 5 6 7 9)
La valeur d'une lambda-expression est cette lambda elle-même.

5.3 Exercices

1A) Ecrire une fonction qui sélectionne dans une liste de nombres tous ceux qui sont négatifs.
1B) Ecrire une fonctionnelle SELECT qui sélectionne les éléments d'une liste satisfaisant une certaine condition (prédicat).
1C) Exprimer 1A à partir de 1B.
2A) Ecrire une fonction qui compte le nombre d'apparitions d'un atome donné dans une liste.
2B) Ecrire une fonctionnelle qui compte le nombre d'éléments d'une liste possédant certaine une propriété.
2C) comme 1C
3A) Ecrire : somme des éléments d'une liste
3B) Ecrire : produit des éléments d'une liste
3C) Quelle fonctionnelle convient ?
Réponse: application d'une opération associative avec élément neutre aux éléments d'une liste.
(de TRUC (OP NEUTRE L) (cond ((null L) NEUTRE)) (t (funcall OP (car L) (TRUC OP NEUTRE (cdr L)))))))

5.4 Conclusion

Les fonctions d'ordre supérieur permettent au prix d'un petit effort d'abstraction, de réduire considérablement le niveau de détail des programmes; et donc de diminuer considérablement les coûts de développement/maintenance des logiciels écrits grâce aux langages fonctionnels.

M. BILLAUD Département Informatique IUT-A Bordeaux (1989)