Programmation Fonctionnelle et Symbolique - Expressions Symboliques

Résumé

Les expressions symboliques sont formées à partir d'atomes et de doublets. Elles permettent de représenter des listes, qui peuvent elles-mêmes coder des arbres, qui peuvent représenter beaucoup de choses !. Dans tout ce qui suit nous nous conformerons à la tradition Lispienne en utilisant l'abréviation S-expr pour désigner les Expressions Symboliques.

2.1. Les Atomes

Les S-expressions les plus simples sont les Atomes : ce sont des entités indivisibles (a priori) repérées par leur nom (une chaîne de caractères). On distingue deux catégories : Les nombres (ou atomes numériques)et les symboles (appelés aussi - allez savoir pourquoi- atomes non numériques) :

Exemples : abcd toto + * 1789 -123456 sont six atomes, dont deux numériques. (Exercice réservé aux mal-comprenants : trouvez lesquels ?)

Il existe un atome non-numérique qui joue un rôle particulier et que l'on note nil ou bien () ; nous en reparlerons très bientôt.

2.2. Les doublets

Un doublet est la donnée de deux S-Expr.

Voici par exemple une représentation graphique du doublet construit à partir des atomes A et B: 

  .
 / \
A   B
La notation linéaire consacrée pour ce genre d'objet est : ( A . B )

Attention : ce doublet est très différent de son collègue ( B . A ) !

On utilise aussi le vocable paire pointée pour désigner les doublets. Remarquez bien que les parties gauches et droites d'un doublet peuvent être également des doublets, qui eux-mêmes, etc...

Exercice : donnez une représentation graphique de l'objet décrit par la S-expr suivante : ( ( A . ( B . C ) ) . D )

Solution 

      .
     / \
    .   D
   / \
  A   .
     / \
    B   C
Exercice : Donnez la S-expr qui décrit l'objet : 
      . 
     / \
    A   .
       / \
      B   .
         / \
        C   NIL
Solution : ( A . ( B . ( C . nil ) ) )

Pour des raisons historiques, les composantes gauche et droite d'un doublet sont appelées respectivement car et cdr de ce doublet. L'opération qui consiste à faire un doublet à partir de deux S-expr est appelée cons.

Exercice : donnez le car du cdr du cdr de l'expression précédente. (réponse : C).

L'ensemble des S-expressions est donc l'ensemble des objets (finis) qui sont:

Ceci est une définition récursive bien fondée (c'est-à-dire pas complètement absurde) puisqu'elle définit

Curiosités:

2.3. Notation des Listes

Nous venons de voir une notation pour les S-expr. qui représentent en fait des arbres binaires dans toute leur généralité. Nous allons voir comment représenter des listes (séquences) d'objets par des S-expr ; et quelques facilités de notation bien agréables. Mais auparavant nous rappellerons la notion de liste.

2.3.a Définition des Listes

Pour construire des listes d'objets il faut tout d'abord avoir un ensemble d'objets de base (par exemple OBJETS=Nombres si on veut construire des listes de nombres) ; dès lors l'ensemble L des listes d'objets est défini par :

l est une liste si et seulement si

Nous avons donc un objet () qui représente la liste vide, et une opération (appelée cons, comme pour les s-expr) qui permet de fabriquer une liste l en mettant un objet o devant une liste plus petite l'.
cons[ 5 , ( 8 5 6 2 ) ] = ( 5 8 5 6 2 ) ]
ce qui, soit dit en passant, sous-entend l'existence de deux fonctions réciproques de cons : premier et reste, applicables aux listes non vides :
premier [ cons[o,l] ] = o
reste [ cons[o,l] ] = l

On a donc : LISTES = { () } u OBJETS x LISTES

2.3.b Représentation des Listes par des S-expr

Il est facile de représenter une liste (séquence) d'objets (par exemple la liste formée des 4 atomes DO MI SOL et DO par un arbre binaire «en peigne» : 
     .
    / \
  DO   \
      / \
    MI   \
        / \
     SOL   \
          / \
        DO   nil
La notation vue plus haut nous conduirait à représenter la chose sous la forme :
(DO . (MI . (SOL . (DO . nil))))
C'est lourd et peu commode. On adopte donc une convention plus agréable en notant simplement la chose :
( DO MI SOL DO )
Remarques:
  1. Par convention l'atome nil désigne la liste vide notée également ()
  2. L'objet suivant: 
                        .
                   / \
                  A   \
                     / \
                    B   \
                       / \
                      C   D
    est noté (A B C . D), il faut prendre garde de ne pas le confondre avec la liste à 4 éléments (A B C D) .
  3. on peut avoir des listes d'expressions quelconques, qui peuvent être éventuellement représenter des listes ...
    ( (DO MI SOL SI-BEMOL) (RE FA LA DO) (SOL SI RE FA) )

Une liste L est donc représentée par un doublet (dans le cas où elle n'est pas vide bien sùr):

Exercices :
  1. Combien y a t'il d'éléments dans : ( (A B) (C D) () )
  2. Donnez les représentation graphiques et les notations linéaires des objets suivants :

    2.4. Représentation d'arbres par des listes

    Nous avons vu précédemment que les S-expr pouvaient servir à dénoter les arbres binaires. La représentation d'arbres quelconques est aisée : considérons par exemple les arbres : + * GLOUP /|\ /|\ / | \ / \ A B 2 2 B + / \ / \ C D A propos, qu'est ce donc qu'un arbre ? C'est : Un arbre est représenté par une liste dont le premier élément est la racine de l'arbre; et les suivants les sous-arbres immédiats :
    ( + A B 2 )

    Exercice: dessiner l'arbre correspondant à :

    (f (g a b) c d)

    Le codage d'un arbre par une liste est en fait une fonction (appelons la «c» que l'on peut présenter de la manière suivante :

    c : Arbres -> S-expr c[ symbole ] = symbole c[ racine ] = ( racine c[a1 ] c[a2 ] ... c[an ] ) a1 a2 .. an La présentation de cette fonction sous forme récursive est en fait très naturelle : elle ne fait que suivre le schéma de définition des arbres :

    Un des objectifs principaux de ce cours est de vous habituer à :

    Mais nous aurons le temps d'y revenir...

    2.5 Représentation des Programmes

    2.5.1 Syntaxe Abstraite

    On peut associer à tout fragment de programme (PASCAL, p.e) son arbre de syntaxe abstraite. Par exemple l'arbre de syntaxe abstraite associé à l'instruction : while A>(B-2)*C do A:=A+1 (qui ne fait rien de spécialement intéressant, le problème n'est pas là) : boucle_ttq / \ > affectation / \ / \ A * A + / \ / \ - C A 1 / \ B 2 Pourquoi «abstraite» ? Parce que cet arbre fait abstraction des problèmes liés aux conventions de représentation écrite (syntaxe) des objets du langage Pascal (les problèmes de point-virgules, de priorités d'opérateurs, etc...); pour s'attacher à la structure profonde du programme.

    Bref, ceci pour dire qu'un programme peut être représenté par un arbre que l'on code par une expression symbolique !

    2.5.2 Syntaxe Abstraite des Fonctions

    En Lisp nous programmerons en écrivant des fonctions; voici par exemple la fonction DOUBLE. Que fait cette fonction ? Elle prend un nombre (disons x) et renvoie le double de sa valeur; c'est-à-dire 2*x .
    Double : x ---> 2*x
    Pour définir une fonction il nous faut un certain nombre d'informations :
    son nom, DOUBLE
    les noms de ses paramêtres, X (ici un seul)
    le corps de la fonction; 2*X
    On peut décrire ceci sous forme d'un arbre : definition / | \ / \ nom liste de corps paramêtres En Lisp, la définition de cette fonction s'écrit : (de DOUBLE (X) (* X 2 ) ) La définition d'une fonction est décrite par une liste à 4 éléments, dans l'ordre : Exercice : Analysez la définition suivante (en devinant ce que vous ne savez pas encore): 
     (de COMIQUE (LAUREL HARDY)
     (if ( <= LAUREL HARDY)  
         LAUREL  
         HARDY 
     ))
    Réponse :
    séance TP à prévoir dès que possible:
    Utilisation Pratique de Lisp
    Exercice :

    Ecrire une fonction MAX qui donne le maximum de deux nombres.

    Exercice :

    Ecrire une fonction MAX3 qui donne le plus grand parmi 3 nombres.

    Exercice :

    Ecrire une fonction DELTA qui calcule le discriminant associé à une

    équation du second degré (encore !!) dont les coefficients sont donnés en paramêtres.

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