Programmation Fonctionnelle et Symbolique
Evaluation des expressions symboliques

3.a La boucle «top-level»
3.b. Notion d'Environnement
3.c. La Fonction «Quote»
3.d. Manipulation élémentaire des Listes
3.e. Les Prédicats
3.f. Structures de Contrôle fondamentales
3.g. Typologie des fonctions
3.h. Définition et Appel de Fonction (rappel)

Résumé

Certaines S-expr codent des programmes; elles sont donc destinées à être évaluées par un évaluateur. Dans cette partie nous allons étudier en détail le fonctionnement de cet évaluateur; et passer en revue quelques fonctions prédéfinies indispensables à la programmation en Lisp. <

3.a La boucle «top-level»

Le langage Lisp est généralement implanté sous forme d'un programme interactif (interprèteur) qui répète indéfiniment (ou presque) une bouclettop-level, c'est-à dire un mécanisme qui :

lit une commande (sous forme de S-expr),
l'exécute (évalue cette S-expr), Dans tout ce qui suit, les questions posées par l'utilisateur seront précédées par ?- , les réponses de l'interprèteur étant indiquées par ->, les messages d'erreur par :: . Quelques exemples très simples : ?- 5 ; on demande d'évaluer le nombre 5 -> 5 ; évidemment le résultat est 5 ! ?- ( + 5 4 ) ; appliquons la fonction + aux arguments numériques 5 et 4 -> 9 ; Victoire ! ?- ( - ( * 8 4 ) ( + 15 16 ) ) ; de plus en plus fort -> 1 ; sauf erreur

Analysons soigneusement le travail de l'interprèteur sur ce dernier exemple:

1) La S-expr ( - ( * 8 4 ) ( + 15 16 ) ) est lue par le «lecteur» (la première phase de la boucle top-level).
2) Elle est transmise à l'évaluateur.
2.1) L'évaluateur reconnait qu'il s'agit d'une expression de la forme «(t-tExpr1tExpr2t)». Il décide donc d'évaluer les deux sous-expressions ( * 8 4 ) et ( + 15 16 ) et de soustraire ensuite les résultats.
2.2) l'expression (* 8 4) est transmise à l'évaluateur.
2.2.1) l'évaluateur reconnait qu'il s'agit de faire le produit des résultats des 2 expressions «8» et «4».
2.2.2) l'expression «8» est transmise à l'évaluateur, qui s'aperçoit qu'on lui demande de calculer la valeur de l'atome numérique 8. Le résultat est évidemment 8 !
2.2.3) Même chose pour 4, qui donne 4.
2.2.4) Le produit des résultats est effectué, qui donne 32.
2.3) l'expression (+ 15 16) est transmise à l'évaluateur, qui, après diverses péripéties semblables aux précédentes, renvoie la valeur 31.
2.4) Les résultats sont soustraits: l'évaluateur renvoie alors la valeur 32 - 31 = 1 .
3) le résultat est imprimé.

Suggestion : On peut illustrer ceci par une imbrication de boîtes d'évaluation, chaque boite étant de la forme : +-- expression --+ | | | | | | | EVAL | | | | | | | +--- résultat ---+ Avec un certain nombre de règles : L'évaluation d'un nombre renvoie ce nombre lui-même : +---- nombre ----+ | | | | | | | EVAL | | | | | | | +---- nombre ----+ L'évaluation d'une somme (ou différence, ou produit, etc..) provoque l'évaluation de ses arguments, et le calcul de la somme (...) des résultats partiels : +----- ( + e e ) ------o | 1 2 | | | | +- e --+ +- e -+ | | | 1 | | 2 | | | | | | | | | | | | | | | +- r -+ +- r -+ | | 1 2 | | \ / | | \ / | | \ / | | additionneur | | | | | | | | V | +---------- R -----------+ L'entrée dans une boite correspond à un appel au module évaluateur.

Exercice: tracer la boite pour l'évaluation de l'expression dont le calcul a été détaillé plus haut :

( - ( * 8 4 ) ( + 15 16 ) )

3.b Notion d' Environnement

En Lisp les atomes (non-numériques) peuvent jouer le rôle de variables, c'est-à-dire que l'on peut :

leur associer une valeur,
récupérer cette valeur.

L'association d'une valeur à une variable se fait notamment lors d'un appel de fonction. Considérons par exemple la fonction : (de FOO (X Y Z) ( + X (* Y Z ) ) ) Lorsque l'on écrit ceci les trois atomes X, Y et Z n'ont pas de valeur particulière, puisque ce sont des variables muettes (des paramêtres). En revanche, lorsqu'on appelle la fonction FOO, p.ex (FOO (+ 3 1) 2 1)) on leur fournit des valeurs : X vaut 4, Y vaut 2 et Z vaut 1. On doit ensuite évaluer le corps de la fonction dans cet environnement.

La valeur d'une variable dans un environnement donné s'obtient simplement par évaluation de l'atome (symbole) qui représente cette variable :

+-- x :symbole --+ | | | | | | | | | | | | | | | V | | | +-- valeur(x) ---+ Exemple : Calcul de (FOO 2 3 4) : +------ (FOO 2 3 4) -----------------------o | | | X=2 Y=3 Z=4 | | | | | | +----- ( + X (* Y Z) ) -----------+ | | | | | | | | | | | | | | | +- Y -+ +--- ( * Y Z) -----+ | | | | | | | | | | | | | | | +- Y -+ +- Z -+ | | | | | | | | | | | | | | | | | +- 2 -+ | | | | | | | | | | | | | | | | | | | | | | +- 3 -+ +- 4 -+ | | | | | | \ / | | | | | | | \ / | | | | | | * | | | | | | | | | | | | | | | | | | | | | V | | | | | | | | | | | | +------- 12 -------+ | | | | | | | | \ / | | | | / | | | | \ / | | | | \ / | | | | + | | | | | | | | | | | | | V | | | | | | | +------------- 14 ----------------+ | | | | | +----------------- 14 ---------------------+ Attention : un environnement peut en cacher un autre ! Considérons par exemple la fonction (de BLOUP ( X Y ) (+ (FOO 2 X Y) (FOO 11 12 X))) et l'appel (BLOUP 5 6).

le corps de BLOOP est évalué dans l'environnement [X=5, Y=6]
le corps de FOO est évalué une première fois dans [X=2, Y=5, Z=6]; et une seconde fois dans [X=11, Y=12, Z=5]

3.c La Fonction «Quote»

Nous avons proclamé dans l'introduction que Lisp permettait de manipuler des expressions symboliques sous formes de S-expr. Or nous n'avons présenté pour l'instant que des expressions renvoyant des résultats numériques.

Un exemple concret : nous voulons chercher le premier élement de la liste (+ X Y). Premier essai :

?- (CAR (+ X Y)) :: erreur : X : variable non définie. Evidemment, puisque l'interprèteur Lisp tente d'évaluer la S-expr (+tXtY)qui contient deux atomes dont la valeur n'est pas définie. Eussent-ils été définis (par exemple évaluation de la même expression dans un environnement où x=2 et y=1), que le résultat 5 ne nous aurait pas convenu (puisque nous voulons récupérer l'atome «+»).

Il faut donc indiquer à l'évaluateur qu'il ne doit pas évaluer la forme -synonyme de S-expr- (+ x y) , qui doit être protégée de l'évaluation par la fonction prédéfinie quote (to quote = citer). Deuxième essai:

?- (quote ( + x y ) ) -> ( + x y ) ?- (car (quote (+ x y))) -> + ; ‡à marche ! En résumé : l'évaluation d'une S-expr de la forme (quote Expr) renvoie le premier argument Expr sans l'évaluer. La boite correspondante : +- (quote expr) -+ | | | | | | | | | | | | | | | V | | | +----- expr -----+ L'usage de telles expressions est très fréquent, aussi il existe une facilité de notation sans laquelle la vérification du nombre de parenthèses d'une expression serait un vrai cauchemar : (quote Expr) est noté 'Expr Dans notre exemple, on écrira donc de préférence : (car '(+ x y)))

3.d Manipulation élémentaire des Listes

Les 3 opérations fondamentales sur les doublets sont :

la construction d'un doublet à partir de deux S-expr,
l'ccès aux composantes gauches et droites d'un doublet.

Les fonctions correspondantes s'appellent cons (à deux paramêtres), car et cdr (à un paramêtre). Comme les fonctions arithmétiques, elles évaluent leurs paramêtres.

Exemples/Exercices:

?- (cons 'laurel 'hardy)) -> (laurel . hardy) ?- (cons 'laurel (cons 'hardy nil)) -> (laurel hardy) ?- '(laurel hardy) -> (laurel hardy) ?- (car '(laurel hardy)) -> laurel ?- (cdr '(laurel hardy)) -> hardy Exercices:

Ecrire une fonction L2 qui prend deux paramêtres et renvoie une liste formée de ces deux paramêtres. Par exemple : ?- (L2 'dupont 'durand) -> (dupont durand)
Ecrire une fonction qui prend comme paramêtre une liste de deux objets et retourne cette liste mais dans l'ordre inverse (le premier de l'une est le second de l'autre et vice-versa).

Il existe un certain nombre de «fonctions d'accès» qui sont des compositions de car et cdr : cadr, cdar, caar, cddr, caddr, cdddr, etc... Leur signification est évidente, (caddr X) par exemple représente : (car (cdr (cdr X))) Exercice : Quelles fonctions représentent l'accès au premier, second, troisième élément d'une liste ? Au premier élement du second élément d'une liste de listes ? (Réponses : car, cadr, caddr , caadr).

3.e Les Prédicats

On appelle prédicats les fonctions qui fournissent un résultat «booléen», vrai ou faux. Il est clair que nous en aurons besoin dès que nous aborderons la programmation en Lisp. La convention adoptée pour la représentation des booléens est la suivante :

l'atome nil représente la valeur «faux» (rappel : il représente aussi la liste vide , d'où la notation () ).
tout autre objet représente «vrai», en particulier l'atome T (true). (notet: en général les atomes nil et T sont des «constantes» : l'évaluation de T renvoie T).

Bien entendu, il y a des prédicats arithmétiques ; par exemple les comparaisons = < > <= >= etc...: ?- ( = 1 2 ) -> () ?- ( < 1 2 ) -> T Attention à l'ordre des paramêtres ! (< 2 X) signifie « 2 est il inférieur à X ?» (et non le contraire)

Les S-expr. sont un mélange de nombres, d'atomes et de doublets. On dispose de prédicats pour déterminer le «type» des objets :

(number Expr) indique si l'évaluation de Expr fournit un résultat numérique;
(atom Expr) réussit pour les atomes non-numériques,
(stringp Expr) indique si l'argument est une chaîne,
(consp Expr) renvoie T pour les doublets.

On dispose également de deux prédicats de comparaison de S-Expr : eq et equal. La différence entre les deux prédicats repose sur des considérations techniques d'implémentation des doublets :

equal indique si ses paramêtres sont semblables ;
eq indique s'ils sont identiques

ce n'est pas tout à fait la même chose : ?- (eq (cons 1 (cons 2 3)) (cons 1 (cons 2 3))) -> T ?- (equal(cons 1 (cons 2 3)) (cons 1 (cons 2 3))) -> () Pourquoi ? dans les deux cas on fabrique deux expressions -à des emplacements distincts en mémoire- qui ont cependant la même structure. eq teste l'identité, equal la similarité.

Remarque : Les nombres et les atomes n'existent qu'en un seul exemplaire en mémoire : la comparaison par eq ou equal fournit dans ce cas forcément le même résultat.

On dispose également des opérateurs booléens and, or et not, avec la signification habituelle. On notera cependant que les opérateurs and et or sont évalués en 'court-circuit'; par exemple dans l'expression :

(or (= X 0) (= (/ 1 X) Y) ) il ne peut y avoir de division par zéro.

3.f Structures de Contrôle Fondamentales

Dans tout langage de programmation on appelle «structure de contrôle» tout mécanisme permettant de combiner plusieurs actions en une action plus complexe. Question : Citez les structures de contrôle de vos langages favoris.

Réponse : Ne pas oublier que l'enchaînement de deux instructions est aussi une structure de contrôle ! Ici, nous programmons avec des fonctions; c'est-à-dire que nous composons entre elles des expressions, en leur appliquant des fonctions - pour l'instant prédéfinies, mais çà ne durera pas. Par conséquent, la première structure de contrôle de Lisp est l'application d'une fonction a des arguments; structure sous-jacente dans tout ce que nous avons vu.

L'alternative

La fonction cond réalise une alternative multiple; présentée sous la forme :

(cond Clause1 Clause2 ... Clausen) Où chaque clause est une liste dont le premier élément représente une condition, et la suite la liste des choses à évaluer si la condition s'avère satisfaite.

Exemple :

(cond ((number X) «C'est un entier») ((stringp X) «C'est une chaîne») ((null X) «C'est nil») ((atom X) «C'est atomique») (T «Un doublet»)) Remarques :

L'évaluation des conditions se fait dans l'ordre des clauses, et s'arrête à la première condition vraie.
Si aucune condition n'est satisfaite, l'évaluation d'une forme (cond ...) renvoie nil.
On utilise fréquemment l'atome T (true) comme «attrape-tout» pour la dernière clause (clause sinon).

Exemple : Ecrire une fonction qui calcule le maximum parmi trois nombres : (de M3 (N P Q) (cond ( (and (>= N P) (>= N Q)) N) ( (and (>= P N) (>= P Q)) P) ( T Q) )) Exercice:

Ecrire une fonction F qui renvoie la différence entre le plus grand et le plus petit nombre parmi trois :

?- (F 5 13 6) -> 8 (6 cas) Remarques :

Il faut insister sur l'importance de la présentation d'une expression Lisp, et donc d'une certaine normalisation (ne pas tout écrire sur une seule ligne, de préférence...). Ca facilite notablement la relecture, et la chasse aux parenthèses manquantes.
Il est possible d'emboîter à volonté les «cond», mais c'est souvent tout à fait inutile; par exemple un bout de programme du style : (cond ( c1 e1) ( T (cond (c2 e2) ( T e3))) qui fait le pendant à l'expression: si c1 alors e1 sinon si c2 alors e2 sinon e3 peut s'écrire beaucoup plus simplement : (cond (c1 e1) (c2 e2) (T e3) )
d'autre part, l'évaluation des connecteurs and et or étant faite en «court-circuit» on peut substituer : (and A B) à (cond ( A B) ( T ())) (or A B) à (cond (A T) (B T)) (not A) à (cond (A ()) (T T)) sans parler d'autres horreurs faisant intervenir des imbrications de cond, de not, etc... que je n'ai pas les moyens de vous empêcher d'inventer.
Alternative simple :
Le «si..alors..sinon» est une forme bien connue d'alternative; qui existe bien sùr en Lisp. On ne l'utilise que lorsqu'il n'y a vraiment que deux cas possibles ; dès qu'il y en a 3 on préfèrera l'emploi de cond.
(if Cond Expr₁ Expr₂ ) équivaut à : (cond (Cond Expr₁ ) ( T Expr₂ ) ) Exercice : Exprimer AND OR et NOT à l'aide de IF.
Bloc avec variables locales La fonction let permet de définir un 'bloc' possédant des variables locales propres ; la forme :
(let ((var₁ exp₁ ) ...(var_k exp_k )) Expression) est évaluée de la manière suivante :
- Les expressions exp₁ ... exp_k sont évaluées séquentiellement;
- Un environnement «local» est créé, dans lequel les variables var₁ ..var_k prennent les valeurs calculées précédemment (éventuellement les anciennes valeurs de ces variables sont «cachées» dans une pile)
- Le corps Expression est évalué dans le nouvel environnement ; le résultat obtenu sera la valeur du bloc;
- les variables var₁ ...var_k retrouvent leurs valeurs d'origine (récupérées sur la pile de sauvegarde).
Exemples : ?- (de F (Liste) (let ((X (car Liste) (Y (cdr Liste)) ) (cons Y (cons X nil)))) ?- (F '(1 2)) -> (2 1) Exercice :
Soit L une liste contenant 3 nombres qui représentent les coefficients d'une équation du second degré. Définir un bloc qui renvoie la valeur du discriminant.
Réponse :
(let ( (A (car L)) (B (cadr L)) (C (caddr L)) ) (- ( * B B ) ( * 4 (* A C)))) L'intérêt de cette structure de contrôle est double : premièrement la notation s'en trouve abrégée - et donc, en principe, éclaircie - et d'autre part, on évite la réévaluation d'expressions ainsi factorisées. Par exemple dans (let ((B (CALCUL X))) ((* B B)) ) l'expression (CALCUL L) ne sera évaluée qu'une seule fois ; contrairement à ce qui se passe pour : (* (CALCUL L) (CALCUL L)).
3.g Typologie des Fonctions
Un des casse-têtes du débutant est de se rappeler le nombre exact d'arguments d'une fonction, et aussi de savoir si elle évalue ou non ses arguments. En la matière, la terminologie usuelle est la suivante :
Toute fonction prédéfinie est appelée SUBR (du FORTRAN ancien SUBROUTINE) si elle évalue tous ses arguments, FSUBR si a priori ses arguments ne sont pas tous évalués.
Parmi les SUBR, on distingue encore plusieurs catégories : les SUBR à nombre fixé d'arguments, baptisées selon les cas SUBR0 SUBR1 SUBR2 SUBR3 etc.. et les SUBRN ayant un nombre variable de paramêtres.
Exemple: CONS est une SUBR2, + est une SUBRN
Même chose pour les FSUBR, répertoriées en FSUBR1, FSUBR2... Exercice : Classifiez les fonctions que vous connaissez.
3.h Définition et Appel de Fonction (Rappel)
La définition de fonctions «utilisateur» se fait par l'appel d'une fonction prédéfinie appelée de (ou defun, defunct, def ... sur autres systèmes). La forme générale est: (de Nom (var₁ .. var_k ) Expression) Les atomes (var₁ .. var_k ) représentent les paramètres formels de la fonction Nom . L'expression est le corps.
Accessoirement, la définition d'une fonction renvoie le nom de cette fonction (puisqu'il faut bien renvoyer quelque chose !). Exemples :
?- (de CARRE (X) ( * X X )) -> CARRE ?- (de DELTA (A B C) (- (CARRE B) (* 4 A C))) -> DELTA ( Les fonctions prédéfinies + et * admettent en fait un nombre quelconque d'arguments : ce sont des SUBRN ) L'appel d'une fonction définie par l'utilisateur est tout à fait similaire à l'invocation d'une fonction prédéfinie. Par exemple: ?- (CARRE 4) -> 16 ?- (CARRE (+ 2 3)) -> 25 ?- (CARRE (CARRE 3)) -> 81 En résumé, l'appel d'une fonction construite par : (de Nom (var₁ .. var_k ) Expression) est fait par l'évaluation d'une liste dont le premier élément est le nom de la fonction et les autres les paramètres effectifs : ( Nom exp₁ .. exp_k )
La règle du jeu est facile à comprendre: l'appel de la fonction Nom provoque l'évaluation des S-Expr exp₁ ... exp_k , (qui sont les paramètres effectifs) dans l'environnement courant. Un environnement local est alors construit, dans lequel les résultats des exp_i sont liés aux var_i qui leur correspondent. Le corps de la fonction est évalué dans l'environnement local; le résultat est transmis comme résultat de la fonction ; et les anciennes valeurs des atomes var₁ ... var_k sont restituées.

+------ ( nom exp ... exp ) -------------+ | 1 n | | | | + exp + + exp + | | | 1| | n| | | | | | | | | | | | | | | +- r -+ +- r -+ | | 1 n | | | | | | +----- corps de la fonction -----o | | | | | | | var =r | | | | 1 1 | | | | | | | | . | | | | . | | | | | | | | var =r | | | | n n | | | | | | | | | | | | | | | | | | | +---------- résultat -------------+ | | | | | V | +-------------- résultat ------------------+
M. BILLAUD Département Informatique IUT-A Bordeaux (1989)

Programmation Fonctionnelle et Symbolique Evaluation des expressions symboliques