Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

PLAN DU CHAPITRE

Il est important d’indiquer que l’intelligence artificielle est vue ici comme une représentation de modèles avec des critères et hypothèses bien établis. La mise en œuvre avec un langage tel que lisp permet de proposer et produire des programmes vérifiant des hypothèses et donc des propriétés. Le programme lui-même sera une preuve du bon traitement et de la conformité du résultat.

Les programmes d’intelligence artificielle qui simulent certains aspects de l’intelligence humaine requièrent des langages symboliques, c’est à dire performants dans le raisonnement sur des symboles plutôt que dans le traitement de l’information numérique. Le langage LISP est né de ce besoin. Les progrès récents dans le matériel et le logiciel font de Lisp un langage (et des outils) commercialement viable. Lisp est maintenant utilisé dans GNU Emacs, un des meilleurs éditeurs de texte Unix, Autocad (logiciel de conception assistée par ordinateur multi domaines comme l'architecture, la mécanique et l'industrie), la norme de programmation industrielle CAO (ConceptionAssistée par Ordinateur de bureau) et Interleaf (distribution et création de publications techniques – Nouvellement QuickSilver). Lisp permet l’analyse de données comme XlipStat. Climb permet en Lisp de faire de l’analyse d’images. Lisp donne la liberté de définir vos propres opérateurs, vous pouvez modeler le langage dont vous avez besoin pour réaliser la demande. Quel que soit le type de programme que vous êtes en train d’écrire Lisp permettra d’inventer la bibliothèque évoluée nécessaire pour arriver à une solution.

Lisp : (LISt Processing (traitement de listes)), est un langage de programmation utilisant les listes comme structures de données. Il fait partie de la famille des langages impératifs et fonctionnels. Ecrit sur la base d’allocations dynamiques, Lisp possède donc un garbage collector et comporte une gestion automatique de la mémoire. Enfin Lisp utilise le code source comme une structure de donnée.

Le langage lisp est conçu sur la théorie des fonctions d'Alonzo Church (1940), le Lambda-calcul (λ-Calcul). Il est basé sur deux concepts :

  1. l'abstraction fonctionnelle.

  2. la réduction d'expressions (application).

En recherche, les langages à base de Lisp, sont considérés comme les assembleurs de l'intelligence artificielle.

Son approche fonctionnelle revient uniquement à développer des bibliothèques de fonctions (donc nous avons une grande possibilité de réutilisation des fonctions existantes). La syntaxe des traitements est identique à celle des données. De part cette conception, les sous-programmes d’un programme sont délimités par des parenthèses et les programmes peuvent créer eux-mêmes directement d’autres programmes.

Dans ce chapitre nous allons aborder :

  1. une présentation du langage et de son environnement.

  2. un outil pour l’exploiter.

  3. sa bibliothèque.

  4. ses structures de contrôle.

PRESENTATION

Lisp permet de faire des démonstrations automatiques, des jeux,… Les traitements des listes pour faire les exécutions sont faits avec des expressions et de la récursivité. Il est possible d’utiliser Lisp avec des expressions itératives (version non native pour ce type de développement impliquant un besoin de créer des macros d’itérations). CLOS (Common Lisp Object System) est une version objet du langage Lisp.

En 1956-58, John McCarthy (1927 - 2011), chercheur au MIT (Massachusetts Institute of Technology) et considéré comme un des fondateurs de l’intelligence artificielle, développe le premier interpréteur Lisp.

En 1969, premier standard pour le langage Lisp. (Franz lisp : le premier lisp sur les machines Unix).

En 1975, Richard Stallman, développe l’éditeur emacs.

Fin 70, création du langage fonctionnel de programmation Scheme à base de Lisp.

En 1982, James Gosling (créateur de Java) développe emacs en langage C pour Unix.

En 1984, développement des interpréteurs Le_Lisp et Common Lisp. Le_Lisp – la version française du LISP - a été développé à l’INRIA (Institut national de recherche en informatique et en automatique) par Jérôme Chailloux et son équipe. Elle est performante et simple et permet un passage rapide vers les autres versions. RPL (ROM-based Procedural Language ou Reverse Polish Lisp) devient le langage de programmation pour les machines à calculer Hewlett-Packard.

En 1985, libre distribution des codes sources, interpréteur EULISP. 20 mars 1985 première version (15.34) de GNU Emacs et développement d’Emacs-lisp (e-lisp) : langage d'extension de gnu-emacs. Gosling permit initialement la libre distribution du code source de Gosling Emacs.

En 1986, développement de l’interpréteur AutoLISP.

En 1986 première norme en Common lisp standard. Les objectifs principaux de standardisation aboutissent à :

  1. une portabilité.

  2. une consistance des versions.

  3. une expressivité simple selon des formes de programmation.

En 1987, création Comité ISO (International Standard Organization) de normalisation de Lisp. Principaux rivaux COMMON LISP et EU-LISP.

Entre 1989 et 1996, travaux de H. Blanchon, C. Boitet du projet LIDIA (Large Internationalisation des Documents par Interaction avec leurs Auteurs) permet de faire de la production de documents techniques multilingues.

En 1992, travaux de John Koza (MIT) sur la "Programmation Génétique". Application du paradigme génétique aux programmes eux-mêmes, naturellement munis d'une structure d'arbre Lisp.

En 1993, CLIM propose la version 2.0 pour créer des interfaces utilisateurs. En 1994, Lisp est normalisé par ANSI (American National Standards Institute).

En 1997, ISLISP devient un standard pour Lisp.

En 1998, la NASA (National Aeronautics and Space Administration) développe avec Lisp et l’intègre dans RAX pour son projet Deep Space.

En 2013, ROS (Robot Operating System) intègre Lisp pour ses développements.

Aujourd’hui : Lisp permet l'écriture d'applications rapide et efficace et s’utilise en langages d'extension d'applications. Lisp a donné suite à de nombreuses versions comme Common Lisp, a influencé des langages comme Scheme ou Smalltalk ainsi que des versions objet comme par exemple FLAVORS.

L'interprète Guile (dialecte Scheme) est utilisé dans le projet GNU et à l'œuvre dans les logiciels gimp (Gnu Image Manipulation Program) et snd (édition de sons).

Lisp se compose de fonctions à évaluer et non pas de procédures à exécuter comme les langages procéduraux. Tous les langages informatiques utilisent la récursivité qui est un outil puissant pour les fonctions répétitives. LISP en fait un de ses principaux outils

Lisp excelle dans le traitement symbolique (non numérique) des données ce qui le rend particulièrement efficace pour la simulation du raisonnement. Il n’existe pas de déclaration de types comme dans les langages procéduraux. Le type des variables se détermine en cours d’exécution du programme. C’est une des caractéristiques de l’IA où le raisonnement et l’information sont souvent confondus (la connaissance est à la fois déclarative et procédurale). Donc programmation interactive et exécution rapide. Il existe aussi des versions compilées.

Toutes les structures de données se ramènent à la construction de listes constituées aussi bien d’atomes que de listes.

L'OUTIL LISPWORKS

Les exercices se font avec l’outil http://www.lispworks.com/. Cet outil a été choisi pour son caractère multi-systèmes d’exploitation. Ce cours n’est pas un cours d’outil, par conséquent, toutes les fonctionnalités ne seront pas développées.

L’outil lispworks est un interpréteur du langage lisp. Il permet de contrôler le résultat d’une fonction et donnera des indications sur les warning et erreurs provoquées. En chargement, il acceptera des fichiers d’extension .lsp et les commentaires seront précédés par le ;.

Figure 1.1. Aperçu de l’outil LispWorks

Aperçu de l’outil LispWorks

L’outil dispose d’une fenêtre de commandes nommée Listener ou le prompt > sera obligatoire pour interpréter les commandes.

Figure 1.2. Aperçu de l’interpréteur LispWorks en fonctionnement

Aperçu de l’interpréteur LispWorks en fonctionnement

Pour interpréter chacune des commandes, après son écriture dans l’interpréteur, il suffit de taper entrer.

L’outil dispose également d’un éditeur et d’un container de résultats qui permettront de faire un travail de programmation avec modifications des écrits en cas d’erreur et interprétation pour obtenir un résultat. Il suffit de cliquer bouton droit sur la feuille d’édition et sur l’output (point bleu serti de demi-cercles). Pour les utiliser il faudra utiliser les clics droits, pour compiler et évaluer les fonctions.

Figure 1.3. Aperçu de l’éditeur LispWorks en phase COMPILE avec le container des résultats

Aperçu de l’éditeur LispWorks en phase COMPILE avec le container des résultats

Figure 1.4. Aperçu de l’éditeur LispWorks après la phase COMPILE avec le container des résultats

Aperçu de l’éditeur LispWorks après la phase COMPILE avec le container des résultats

Figure 1.5. Aperçu de l’éditeur LispWorks en phase EVALUATE avec le container des résultats

Aperçu de l’éditeur LispWorks en phase EVALUATE avec le container des résultats

Figure 1.6. Aperçu de l’éditeur LispWorks après la phase EVALUATE avec le container des résultats

Aperçu de l’éditeur LispWorks après la phase EVALUATE avec le container des résultats

GENERALITE DE LISP

Dans l'industrie, avec la standardisation du Common Lisp, des projets ou certaines applications industrielles sont développées sur des environnements Lisp.

Un programme lisp est constitué d’expressions (il ne s’agit pas d’instructions). Les expressions sont lues en séquence et elles peuvent être aussi imbriquées. Nous utilisons les sous expressions pour définir la profondeur d’une expression.

L’algorithme général d’exécution en Lisp est une boucle sans fin au cours de laquelle les expressions lues au clavier, sont évaluées, leur résultat étant systématiquement imprimé.

Figure 1.7. Cycle du loop

Cycle du loop

L’algorithme d’exécution de l’interprète est une boucle qui s’exécute à divers niveaux de profondeur en commençant par le plus profond. Ce cycle READ-EVAL-PRINT est assimilé au premier loop en informatique. Il faut noter que la partie EVAL peut accepter n’importe quelle expression. Il aura pour rôle de produire une décomposition successive en respectant des cas élémentaires et des propriétés. L’utilisation de la récursivité sera le fondement même pour tester toutes les demandes et permettent des parcours et recherche maitrisés.

Expressions : Il s’agit de la représentation des structures de traitements et de données en Lisp. Les expressions symboliques s’appellent des S-expressions pour Lisp.

Les programmes et les données en Lisp sont une S-expression (liste) engendrée par la grammaire EBNF (Extended Backus-Naur Form) :

    
 <S-expression> ::= <atome> | <liste> 
 <liste> ::= {(S-expression)}
 <atome> ::=  nombre | opérateur | {caractère} | {séparateur}
   

La mécanique globale d’interprétation est assimilable à la lecture d’un dictionnaire. Les symboles ou les fonctions sont définis à l’aide de liaisons. Il faut donc utiliser des mots clefs du langage comme par exemple defparameter ou defun pour définir un symbole ou une fonction.

Les symboles (les variables, les atomes) ne sont pas initialement typés, mais ils sont dotés d’un typage dynamique. Chacune des variables de Lisp peut support un type. Pour connaitre le type, il est possible de le faire en utilisant une commande d’interprétation. La commande est constituée du nom du type supposé de la variable (symbole) suivi de p. Donc, pour cela il faut connaitre les différents types possible du langage dont voici quelques exemples : pour un entier integerp, pour un réel floap, pour un symbole symbolp …

Figure 1.8. Exemples de typage des variables

Exemples de typage des variables

Dans les exemples ci-dessus, les commandes et interprétations sont enchainées. Il est à noter que le typage des variables existe et qu’il peut se modifier au cours des demandes du programmeur.

Apple utilise en interne un langage de développement appartenant à la famille Lisp : Dylan. ROS (Robot Operating System) intègre Lisp pour ses développements. Et de nombreuses applications intègrent le Lisp, par exemple :

  1. des éditeurs de texte (Emacs).

  2. les bases de données orientées objets.

  3. la CAO intelligente (AutoCad).

  4. applications temps-réel.

  5. les programmes des cycles de robots (Ros).

  6. application portable (PlanisWare - Axopen).

  7. web (Hunchentoot, Yahoo! Store).

  8. .....

LA BIBLIOTHEQUE DU LANGAGE LISP

Le langage Lisp utilise la notation "préfixée" qui place la fonction (arithmétique, logique, ….) avant les arguments, par exemple: (+ 2 5).

Rappelons que souvent dans les langages courants (comme le C) utilisent la notation "infixée" qui place l’opérateur entre les arguments: (2 + 5).

La notation "post fixée" est de placer l’opérateur à la fin: (2 5 +).

Atome, séparateur, liste, paire pointée et les nombres

Atome : Il s’agit d’une expression symbolique élémentaire de Lisp. L’atome représente une S-expression insécable (indivisible, inséparable, ne peut pas être coupés). Les atomes sont des caractères ou des suites de caractères « alphanumériques » c’est à dire comprenant des lettres aussi bien que des chiffres ou autres symboles.

Pour les atomes, le langage Lisp ne fait pas de différence entre majuscules et minuscules. Il peut aussi intégrer des symboles comme -, *, &, #, … . Lorsqu’un atome est proposé à une évaluation, Lisp retourne sa valeur. Pour déterminer le vide d’atome dans une liste, il est possible d’utiliser NIL un mot du langage lisp. NIL peut aussi bien être utilisé comme un simple atome, mais il peut signifier aussi la liste vide (et dans ce cas NIL est assimilable à () ) ou bien représenter par traitement la valeur de vérité FAUX. Il est à noter que T (True) représentera pas traitement la valeur de vérité VRAI. NIL et T sont donc deux symboles de Lisp qui sont pourvus de valeur constante et qui ne sont pas simplement des symboles.

Séparateur : Il s’agit d’un caractère qui permet de séparer les expressions. Les caractères séparateurs ne peuvent pas former des atomes.

La liste des séparateurs en Lisp est :

  • le point : .

  • l’espace

  • les parenthèses : ( et )

  • les crochets : [ et ]

  • l’apostrophe : quote ou '

  • la tabulation

  • le point-virgule : ;

  • le retour chariot (return)

Notons qu’il est possible d’avoir des doubles usages des symboles, ainsi les parenthèses délimiteront les S-expression, le point permettra de faire des pairs pointées, le quote sera un opérateur de non interprétation, … .

Liste : il s’agit d’une S-expression qui détermine une suite ordonnée d’atomes et/ou des listes. Une suite ordonnée est une séquence qui sera parcourra de gauche à droite ou de droite à gauche. L’ordre des listes sont des conditions utiles et prépondérantes dans la construction de programmes fonctionnels. Les programmes Lisp sont des listes ou le premier élément est (le nom de) la fonction, et les éléments suivants sont les paramètres d'appel de la fonction.

Exemples de listes :

  • (A B) : liste constituée de 2 atomes A et B.

  • (A B C) : liste constituée de 3 atomes A, B et C.

  • (A (B C)) : liste constituée de 1 atome A et d'une liste (B C).

  • (Une liste) : liste constituée de 2 atomes Une et liste.

  • (Marc joue Bien) : liste constituée de 3 atomes Marc, joue et Bien.

  • () : liste vide, correspond à : NIL.

Notons que le langage Lisp accepte directement une liste vide, elle représente donc la valeur initiale d’une liste.

Longueur d’une liste : Une liste est une donnée composée d’objets dénombrables. Il est possible de faire ou non la distinction entre les objets eux-mêmes. Par conséquent chaque objet compte pour 1. La somme des objets d’une liste constituée sa longueur. Pour une fonction la longueur des paramètres se décomptera en nombre d’arité. Une fonction avec 2 arguments sera nommée fonction avec 2 arités.

Figure 1.9. longueur d'une liste

longueur d'une liste

Profondeur d’une liste : Elle est calculée en fonction des S-expressions contenus dans la liste. Les parenthèses pourront aider à calculer la profondeur d’une liste. Ainsi la première parenthèse dénote la profondeur 0 la suivent la profondeur 1 et ainsi de suite selon les imbrications des parenthèses.

Figure 1.10. Profondeur d'une liste

Profondeur d'une liste

Prenons l’exemple avec numérotation des parenthèses : 0(1(2(3 A 3)2(3 B 3)2(3 C 3)2)1 G 1(2(3(4(5(6 D E 6)5)4 F 4)3 H 3)2)1)0. Il est possible de représenter cette liste sous la forme d’un arbre et de dénoter les profondeurs.

Figure 1.11. Arbre des profondeurs d’une liste

Arbre des profondeurs d’une liste

Paire pointée : Une paire pointée est spécifiée par l'utilisation du séparateur point <.> situé entre 2 objets. Il faut séparer par un blanc, le point, des atomes qui l’entourent.

La paire pointée sera utile pour la construction d’atome, lors de la concaténation de plusieurs atomes. Selon certaines fonctions il est possible que l’interprétation aboutisse à la concaténation souhaitée d’atome d’où la possibilité de faire mais en notant une différence avec un atome originel donné.

Nombre : Les nombres acceptés sont les fractions, les réels, les entiers positifs ou négatifs, … .

Figure 1.12. Arbre des dépendances des nombres

Arbre des dépendances des nombres

La taille des fixnum sont sur un mot mémoire (donc au moins 16 bits). Les Bignum sont sans limite de taille mémoire. La programmation Lisp permet une conversion automatique entre les types.

Les fonctions

Présentation

Fonction : Une fonction est une liste qui se parcourra de gauche à droite. Elle contient en première position le nom de la fonction suivit des arités (arguments, paramètres). Donc nous avons (fonction … …), avec le nom de la fonction est placé toujours après la parenthèse ouvrante et précède les arguments (arités).

Le langage Lisp utilise la notation « préfixée » qui place le nom de fonction (un opérateur, une fonction existante, une fonction crée) avant ses arguments. Il sera toujours possible de créer une fonction, même si elle existe déjà. Dans le cas d’une surcharge, la dernière fonction créée sera toujours celle utilisée lors de son prochain appel.

Il est possible d’indiquer que la nomination même de fonction n’est pas représentative de l’écriture d’une programmation fonctionnelle car en réalité l’interpréteur ne fera pas de distinction entre données et traitements de données et que tout sera représenté sous le format d’une simple séquence à lire dans l’ordre de gauche à droite. C’est pour cela que nous aurons des fonctions, des prédicats,… qui seront uniquement basés sur le concept de séquence.

L'appel d'une fonction

Le nombre d'arguments (arités) dépend de la fonction. L’ensemble fonction + arité représente la fonction à évaluer avec ses arguments. Certaines fonctions acceptent un nombre variable d'arguments. Sauf quelques exceptions Lisp procède toujours de la même façon pour évaluer une séquence. Lisp évalue les éléments de la séquence de gauche à droite, le premier élément est la fonction initiale, puis Lisp applique cette fonction au reste de la séquence élément par élément.

Figure 1.13. Présentation générique d’une fonction Lisp

Présentation générique d’une fonction Lisp

Un appel de fonction est équivalent à une évaluation (interprétation) de la fonction par simple lecture de séquence. Et donc les appels retournent une valeur soit interprétée au sens des opérateurs soit écrite au sens du copier-coller (réécriture simple de la donnée initiale).

Le fonctions arithmétiques

Voici une liste de fonctions arithmétiques préétablies dans Lisp pour permettre le calcul et la manipulation de valeurs :

  • l’addition : (+ <arg1> <arg2> [… <argN>])

  • la soustraction : (- <arg1> <arg2> [… <argN>])

  • la multiplication : (* <arg1> <arg2> [… <argN>])

  • la division : (/ <arg1> <arg2>)

  • l'exponentielle : (expt <base> <pot>)

  • le logarithme : (log <n> <base>)

  • la racine carrée : (sqrt <n>)

  • le maximum : (max <arg1> <arg2> [… <argN>])

  • le minimum : (min <arg1> <arg2> [… <argN>])

  • le sinus : (sin <arg>)

  • le cosinus : (cos <arg>)

  • la tangente : (tan <arg>)

  • la valeur absolue : (abs <arg>)

  • partie entière : (round <arg>)

  • l’incrémentation : (1+ <arg>)

  • la décrémentation : (1- <arg>)

L’interprétation des fonctions arithmétiques renvoie des valeurs. La division n’accepte pas plus de deux arités (arguments). Dans le cas d’un seul argument, la division retourne l’inverse de cet argument.

Les fonctions prédéfinies

Initialement la valeur d’un atome, symbole, n’est pas définie, donc ils ne sont pas liés à une interprétation directe par une valeur. Il est nécessaire de distinguer les valeurs des atomes pour ne pas générer des erreurs du type : atome non défini. Il faut donc agir sur l’interprétation avec une fonction de neutralisation.

QUOTE ou ' : Il s’agit de fonctions Lisp qui empêchent l’évaluation (l’interprétation) de l'expression symbolique fournie en argument et permet de distinguer les atomes spéciaux des constantes et caractères dans les S-expressions.

Figure 1.14. Construction d’une fonction quote ou '

Construction d’une fonction quote ou '

Toutes les données de type caractères, symboles, atome, liste non vide … (soit toutes les S-expressions de ce type) qui ne doivent pas être évaluées sont précédées d’une fonction Quote. C’est donc la fonction Quote qui permet de distinguer les données du programme car les deux sont des listes. Usuellement la fonction Quote est remplacée par le symbole '. Attention, le symbole ' est bien une fonction et par conséquent le symbole ne peut-être un autre symbole approchant (symbole qui n’a pas le même codage). Méfiez-vous donc du copier-coller qui pourrait modifier le symbole.

Figure 1.15. Exemple d’interprétation de la fonction '

Exemple d’interprétation de la fonction '

D’après l’exemple ci-dessus, nous constatons que la fonction ' transmet bien l’interprétation de la liste (d d e) et non l’évaluation de liste alors que sans la fonction ', l’interpréteur indique que d n’est pas une fonction connue pas l’interpréteur. En effet comme (d d e) est une séquence, le premier d est en lieu et place d’une fonction.

NOT : Il s’agit d’une fonction Lisp qui interprète l’arité T en NIL et NIL en T. Nous pouvons dire que la fonction NOT inverse la valeur des arités prédéfinies NIL et T. Le résultat de la fonction NOT pour toutes les autres S-expressions sera NIL.

Figure 1.16. Construction d’une fonction NOT

Construction d’une fonction NOT

Figure 1.17. Exemple d’interprétation de la fonction NOT

Exemple d’interprétation de la fonction NOT

La fonction NOT n’admet qu’une arité. Toutes les S-expressions sont acceptées comme argument de la fonction NOT.

CAR : Il s’agit d’une fonction Lisp qui extrait le premier élément d’une liste. Notons que le premier élément peut être aussi bien un atome, une liste ou une liste de listes donc n’importe quel S-expression. Il est possible de retrouver cette fonction sous le nom de FIRST.

Figure 1.18. Construction de la fonction CAR

Construction de la fonction CAR

La liste donnée en argument de la fonction CAR doit être précédée d’une fonction ' afin de ne pas être évaluée. Le résultat de la fonction sera bien le premier élément de la liste. Il est à noter que le premier élément d’une liste vide est NIL.

Figure 1.19. Exemples d’interprétation de la fonction CAR d’extraction d’élément de listes

Exemples d’interprétation de la fonction CAR d’extraction d’élément de listes

Dans nos exemples, nous interprétons la fonction CAR sans parenthèses englobantes. Il est tout à fait possible de le faire, mais attention lorsque nous utiliserons cette fonction CAR dans une interprétation plus complexe (construite avec un enchainement de plusieurs interprétations), il sera nécessaire de les placer. N’oublions pas aussi que dans ces exemples, nous sommes en présence d’une interprétation directe et que la structure de données en mémoire n’est pas modifiée. L’affichage du résultat donné est un effet de bord de l’outil qui retourne la valeur de l’interprétation uniquement parce que celle–ci a fonctionné. Dans une programmation fonctionnelle, ces affichages ne sont pas sources de demandes. C’est ainsi que lors d’une séquence d’interprétation, seule la dernière interprétation valide sera affichée par l’outil. Pour garder le résultat des demandes, nous devrons intégrer la séquence d’interprétation en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation (n’oublions pas dans ce cas l’utilisation obligatoire des parenthèses).

Pour bien comprendre les exemples de la fonction CAR, il faut regarder la profondeur de l’arité donnée. En effet, le choix du premier élément est délimité par les différentes parenthèses contenues dans l’argument. Le premier élément d’une liste contenant un atome et l’atome lui-même. Le premier élément d’une liste de liste est liste. Ainsi de suite, et pour un meilleur apprentissage, il devient nécessaire d’utiliser son interpréteur avec de nombreux exemples de votre choix pour construire tous les cas possible et pour bien comprendre la fonction CAR.

CDR : Il s’agit d’une fonction Lisp qui retourne une liste privée de son premier élément. Le premier élément de la liste peut-être n’importe quelle S-expression. Il est possible de retrouver cette fonction sous le nom de REST.

Figure 1.20. Construction d’une fonction CDR

Construction d’une fonction CDR

La liste donnée en argument de la fonction CDR doit être précédée d’une fonction ' afin de ne pas être évaluée. Le résultat de la fonction sera bien la liste privé de son premier élément, sinon une erreur. Il est à noter que la liste vide privée de son premier est NIL et que la liste privée de son dernier élément d’une liste contenant une liste vide est NIL aussi.

Figure 1.21. Exemples d’interprétation de la fonction CDR d’extraction de listes

Exemples d’interprétation de la fonction CDR d’extraction de listes

Dans nos exemples, nous interprétons la fonction CDR sans parenthèses englobantes. Il est tout à fait possible de le faire, mais attention lorsque nous utiliserons cette fonction CDR dans une interprétation plus complexe (construite avec un enchainement de plusieurs interprétations), il sera nécessaire de les placer. N’oublions pas aussi que dans ces exemples, nous sommes en présence d’une interprétation directe et que la structure de données en mémoire n’est pas modifiée. L’affichage du résultat donné est un effet de bord de l’outil qui retourne la valeur de l’interprétation uniquement parce que celle–ci a fonctionné. Dans une programmation fonctionnelle, ces affichages ne sont pas sources de demandes. C’est ainsi que lors d’une séquence d’interprétation, seule la dernière interprétation valide sera affichée par l’outil. Pour garder le résultat des demandes, nous devrons intégrer la séquence d’interprétation en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation (n’oublions pas dans ce cas l’utilisation obligatoire des parenthèses).

Pour bien comprendre les exemples de la fonction CDR, il faut regarder la profondeur de l’arité donnée. En effet, le choix d’une liste privée de son premier élément impose que la S-expression donnée soit bien délimitée par les différentes parenthèses. Pour un meilleur apprentissage, il devient nécessaire d’utiliser son interpréteur pour construire et comprendre tous les cas possibles la fonction CDR.

LAST : Il s’agit d’une fonction Lisp qui retourne une liste constituée du dernier élément d’une liste. Le dernier élément de la liste peut-être n’importe quelle S-expression.

Figure 1.22. Construction d’une fonction LAST

Construction d’une fonction LAST

Pour obtenir un résultat, les arguments de la liste doivent être des S-expressions non interprétées, donc il est nécessaire d’utiliser le '. Le résultat est une liste en respectant toutes les S-expressions données.

Figure 1.23. Exemples d’interprétation de la fonction LAST d’extraction de listes

Exemples d’interprétation de la fonction LAST d’extraction de listes

Dans nos exemples, nous interprétons la fonction LAST sans parenthèses englobantes (tout comme CAR et CDR). Il est tout à fait possible de le faire, mais attention lorsque nous utiliserons cette fonction LAST dans une interprétation plus complexe (construite avec un enchainement de plusieurs interprétations), il sera nécessaire de les placer. N’oublions pas aussi que dans ces exemples, nous sommes en présence d’une interprétation directe et que la structure de données en mémoire n’est pas modifiée. L’affichage du résultat donné est un effet de bord de l’outil qui retourne la valeur de l’interprétation uniquement parce que celle–ci a fonctionné. Dans une programmation fonctionnelle, ces affichages ne sont pas sources de demandes. C’est ainsi que lors d’une séquence d’interprétation, seule la dernière interprétation valide sera affichée par l’outil. Pour garder le résultat des demandes, nous devrons intégrer la séquence d’interprétation en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation (n’oublions pas dans ce cas l’utilisation obligatoire des parenthèses).

Pour bien comprendre les exemples de la fonction LAST, il faut regarder la profondeur de l’arité donnée. En effet, le choix du dernier élément est délimité par les différentes parenthèses contenues dans l’argument. Le dernier élément d’une liste contenant un atome et l’atome lui-même. Le dernier élément d’une liste de liste est liste. Ainsi de suite, et pour un meilleur apprentissage, il devient nécessaire d’utiliser son interpréteur avec de nombreux exemples de votre choix pour construire tous les cas possible et pour bien comprendre la fonction LAST. Le résultat des interprétations proposées sont bien des listes. La fonction LAST ne retourne pas d’atome.

BUTLAST : Il s’agit d’une fonction Lisp qui retourne une liste privée de son dernier élément. Le dernier élément de la liste peut-être n’importe quelle S-expression.

Figure 1.24. Construction d’une fonction BUTLAST

Construction d’une fonction BUTLAST

Pour obtenir un résultat, les arguments de la liste doivent être des S-expressions non interprétées, donc il est nécessaire d’utiliser le '. Le résultat est une liste en respectant toutes les S-expressions données.

Figure 1.25. Exemples d’interprétation de la fonction BUTLAST d’extraction de listes

Exemples d’interprétation de la fonction BUTLAST d’extraction de listes

Dans nos exemples, nous interprétons la fonction BUTLAST sans parenthèses englobantes. Il est tout à fait possible de le faire, mais attention lorsque nous utiliserons cette fonction BUTLAST dans une interprétation plus complexe (construite avec un enchainement de plusieurs interprétations), il sera nécessaire de les placer. N’oublions pas aussi que dans ces exemples, nous sommes en présence d’une interprétation directe et que la structure de données en mémoire n’est pas modifiée. L’affichage du résultat donné est un effet de bord de l’outil qui retourne la valeur de l’interprétation uniquement parce que celle–ci a fonctionné. Dans une programmation fonctionnelle, ces affichages ne sont pas sources de demandes. C’est ainsi que lors d’une séquence d’interprétation, seule la dernière interprétation valide sera affichée par l’outil. Pour garder le résultat des demandes, nous devrons intégrer la séquence d’interprétation en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation (n’oublions pas dans ce cas l’utilisation obligatoire des parenthèses).

Pour bien comprendre les exemples de la fonction BUTLAST, il faut regarder la profondeur de l’arité donnée. En effet, le choix du dernier élément à supprimer est délimité par les différentes parenthèses contenues dans l’argument. Le dernier élément d’une liste contenant un atome et l’atome lui-même. Le dernier élément d’une liste de liste est liste. Ainsi de suite, et pour un meilleur apprentissage, il devient nécessaire d’utiliser son interpréteur avec de nombreux exemples de votre choix pour construire tous les cas possible et pour bien comprendre la fonction BUTLAST. Le résultat des interprétations proposées sont bien des listes privées de son dernier élément. La fonction BUTLAST ne retourne pas d’atome.

LIST : Il s’agit d’une fonction Lisp qui permet de former une liste à partir de S-expressions vide ou non. L’interprétation construit une liste des éléments donnés, en d’autres termes elle lie tous les éléments donnés en une seule liste.

Figure 1.26. Construction de la fonction LIST

Construction de la fonction LIST

Pour obtenir un résultat, les arguments de la liste doivent être des S-expressions non interprétées, donc il est nécessaire d’utiliser le '. Le résultat est une liste en respectant toutes les S-expressions données.

Figure 1.27. Exemples d’une interprétation d’une fonction LIST de construction de liste

Exemples d’une interprétation d’une fonction LIST de construction de liste

Dans nos exemples, il est possible d’utiliser la fonction LIST sans parenthèses englobantes. N’oublions pas que nous sommes en présence d’une interprétation et que la structure de données en mémoire n’est pas modifiée. Cette interprétation pourra être intégrée en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation, et dans ce cas l’utilisation des parenthèses sera obligatoire.

Notons dans nos exemples que la construction par la fonction LIST respecte les parenthèses des arguments donnés. Mais il est utile de rappeler que () correspond à NIL d’où la construction avec lors des interprétations de LIST. Pour bien comprendre les exemples de la fonction LSIT, il faut regarder les S-expression données. Pour un meilleur apprentissage, il devient nécessaire d’utiliser son interpréteur pour construire et comprendre tous les cas possibles la fonction LIST.

CONS : Est une fonction qui ajoute un élément en tête d’une liste. Pour son utilisation il est donc obligatoire d’avoir un élément et une liste.

Figure 1.28. Construction de la fonction CONS

Construction de la fonction CONS

Lorsque le deuxième argument est un atome, l’interprétation produit une paire pointée. C’est aussi le cas après évaluation des opérations arithmétiques plus profondes et sans quote. Si la fonction CONS n’arrive pas à interpréter que son deuxième argument est bien une liste pour exemple S-Expression quotée, alors l’interpréteur Lisp cherche à évaluer le premier terme en tant que fonction et cela échoue. Dans nos exemples, il est possible d’utiliser la fonction CONS sans parenthèses englobantes. N’oublions pas que nous sommes en présence d’une interprétation et que la structure de données en mémoire n’est pas modifiée. Cette interprétation pourra être intégrée en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation, et dans ce cas l’utilisation des parenthèses sera obligatoire.

Figure 1.29. Exemples d’une interprétation d’une fonction CONS de construction de listes

Exemples d’une interprétation d’une fonction CONS de construction de listes

Nous constatons que dans les exemples ci-dessus tous les résultats sont des listes constituées d’éléments qui conservent la profondeur des S-expression données.

APPEND : Est une fonction qui permet de concaténer les listes transmises en argument.

Figure 1.30. Construction de la fonction APPEND

Construction de la fonction APPEND

Lorsque le premier argument est un atome, l’interprétation produit une erreur. Lorsque le deuxième argument est un atome, et qu’il n’existe que deux atomes, dont le premier est une liste, alors l’interprétation produit une liste avec une paire pointée, sinon il y a une erreur. Si la fonction APPEND n’arrive pas à interpréter que son deuxième argument est bien une liste pour exemple S-Expression quotée, alors l’interpréteur Lisp cherche à évaluer le premier terme en tant que fonction et cela échoue. Dans nos exemples, il est possible d’utiliser la fonction APPEND sans parenthèses englobantes. N’oublions pas que nous sommes en présence d’une interprétation et que la structure de données en mémoire n’est pas modifiée. Cette interprétation pourra être intégrée en lieux et place d’une arité pour devenir un argument d’utilisation pour une autre fonction d’interprétation, et dans ce cas l’utilisation des parenthèses sera obligatoire.

Figure 1.31. Exemples d’une interprétation d’une fonction APPEND de construction de listes

Exemples d’une interprétation d’une fonction APPEND de construction de listes

Nous constatons que dans les exemples précédents certaines profondeurs de liste n’existent plus lors de l’interprétation. Il est donc nécessaire de bien produire tous les exemples de construction pour avoir tous les résultats possibles. Le modèle d’erreur propose les limites de la fonction.

Les fonctions d'affectation et dévaluation

Prenons comme exemple le liste (A (B C) D E) et regardons l’application des fonctions CAR et CDR dessus. Le résultat produit un arbre des profondeurs et d’accès. Dans cet arbre le fils gauche d’un nœud est le résultat de la fonction CAR sur la liste contenue dans le nœud et le fils droit d’un nœud est le résultat de la fonction CDR sur la liste contenue dans le nœud. Nous avons donc une production totale en CAR et CDR sur toutes les listes proposées à l’évaluation.

Figure 1.32. Arbre de progression dans une liste avec les fonctions CAR et CDR

Arbre de progression dans une liste avec les fonctions CAR et CDR

  1. liste initiale : (A (B C) D E).

  2. fonction CAR appliquée à la liste initiale.

  3. fonction CDR appliquée à la liste initiale.

  4. la fonction CAR a extrait le premier élément de la liste : A.

  5. la fonction CDR a extrait le reste de la liste en une liste : ((B C) D E).

  6. (B C) est le second élément de la liste initiale.

  7. D est le troisième élément de la liste initiale.

  8. E est le quatrième élément de la liste initiale.

Pour avoir l’atome D de la liste initiale (A (B C) D E), nous prenons la lecture de l’arbre en le parcourant de la feuille à la racine et donc pour obtenir D, nous avons emprunté une branche de CAR puis pour avoir (D E), nous avons emprunté une branche de CDR et pour avoir ((B C) D E), nous avons emprunté une branche de CDR, d’où la fonction finale pour avoir l’atome D : CAR ( CDR ( CDR '(A (B C) D E))). Au passage, comme la fonction car est une fonction du langage Lisp, il est possible de ne pas placer les parenthèses englobantes, sinon nous avons de façon générique : ( CAR ( CDR ( CDR '(A (B C) D E)))). Dans l’outil Lisp, la fonction trace permet de visualiser les arbres faits avec les interprétations. Pour produire l’arbre, il faut d’abord nommer la trace sur la fonction par interprétation, puis interpréter la fonction comme usuelle. Il est possible de faire une interprétation d’une trace sur plusieurs fonctions.

Figure 1.33. Exemple de la fonction trace sur des fonctions CAR, CDR sur une liste

Exemple de la fonction trace sur des fonctions CAR, CDR sur une liste

D’après le résultat de CAR ( CDR ( CDR '( A (B C) D E))), nous constatons la progression de l’interprétation d’abord la CDR pour avoir ((B C) D E) puis le CDR pour avoir (D E) et enfin le CAR donnant l’atome D.

Figure 1.34. Exemple de la fonction trace sur une fonction /

Exemple de la fonction trace sur une fonction /

Dans l’outil Lisp, la fonction untrace permet de supprimer une trace d’une fonction.

Le langage lisp permet également de véhiculer et de conserver des valeurs avec des variables (symboles alphanumériques). La portée de la valeur c’est-à-dire la localité globale ou locale dépend de la fonction d’affection utilisée.

SETQ : Il s’agit d’une fonction qui affecte aux symboles la valeur de l'évaluation des S-expressions. Il s’agit d’une initialisation de valeurs en global. Et donc, les symboles conservent en mémoire la valeur des S-expressions après l'appel.

Figure 1.35. Construction de la fonction d’affectation SETQ

Construction de la fonction d’affectation SETQ

Le nombre d'arguments, pour la fonction d’initialisation SETQ, n'est pas fixé, en revanche, les arguments doivent se trouver en nombre pair, car ils s’évaluent et s’interprètent en couple. La valeur est affectée au symbole, et chaque symbole conserve cette valeur au-delà de la fonction SETQ (valeur globale). Pour la fonction SETQ, il est possible de l’utiliser sans les parenthèses englobantes.

Figure 1.36. Exemples de la fonction d’affectation globale SETQ

Exemples de la fonction d’affectation globale SETQ

Nous remarquons dans l’exemple précédent que les symboles a b f gardent leur valeur en dehors de SETQ et ces valeurs peuvent être utilisées par la suite. Nous constatons que dans le cas de plusieurs affectations, l’interprétation de la fonction SETQ retourne la dernière affectation. Traduisant que les autres affectations ont été correctement interprétées. Dans le cas contraire, il y aurait eu une interruption d’affection au niveau de l’erreur. Les types des symboles se font au niveau de l’affectation, nous sommes en présence d’un type fort. La réutilisation d’un symbole par initialisation peut se faire à n’importe quel moment sans se soucier du typage.

SETF : Comme la fonction d’affectation SETQ, la fonction SETF affecte et conserve aux symboles la valeur de l'évaluation des expressions, mais permet de la réservation des emplacements en mémoire.

Figure 1.37. Construction de la fonction d'affectation globale SETF

Construction de la fonction d'affectation globale SETF

Figure 1.38. Construction de la fonction d'affectation globale SETF avec une fonction en argument

Construction de la fonction d'affectation globale SETF avec une fonction en argument

Pour la fonction SETF, il est possible de l’utiliser sans les parenthèses englobantes. Les parenthèses délimitent les liens d’interprétation pour évaluer et attribuer correctement les valeurs aux bons symboles.

Figure 1.39. Exemples de la fonction d’affectation globale SETF

Exemples de la fonction d’affectation globale SETF

Nous remarquons dans l’exemple précédent que les symboles a b c f l gardent leur valeur en dehors de SETF et ces valeurs peuvent être utilisées par la suite. Nous remarquons bien dans les exemples la gestion de place des éléments d’une liste par la fonction SETF. En effet à partir d’une liste contenant 5 atomes est en utilisant la fonction CDR qui va remplacer 4 atomes par 5 atomes, la liste de 6 atomes se construit contrairement avec la fonction d’évaluation SETQ ou il y a une erreur d’interprétation.

DEFPARAMETER : Comme la fonction SETQ, la fonction DEFPARAMETER affecte et conserve aux symboles la valeur de l'évaluation d’une expression. Par contre le nombre d’argument est fixé à un couple symbole valeur. Cette déclaration d’initialisation sera utile pour récupérer auprès des utilisateurs des valeurs tout en créant la variable.

Figure 1.40. Construction de la fonction d'affectation globale DEFPARAMETER

Construction de la fonction d'affectation globale DEFPARAMETER

Bien que la fonction DEFPARAMTER soit une fonction du langage Lisp, il n’est pas possible de l’utiliser sans les parenthèses englobantes. Les parenthèses délimitent les liens d’interprétation pour évaluer et attribuer correctement les valeurs aux bons symboles.

Figure 1.41. Exemples de la fonction d’affectation globale DEFPARAMETER

Exemples de la fonction d’affectation globale DEFPARAMETER

Nous remarquons dans l’exemple précédent que les symboles a b gardent leur valeur en dehors de DEFPARAMETER et ces valeurs peuvent être utilisées par la suite. Il n’est pas possible d’enchainer des initialisations symboles valeurs.

LET : La fonction LET interprète une fonction avec ses arguments dont les variables ont des valeurs locales à la fonction LET. Il est donc nécessaire de bien placer les parenthèses pour bien respecter la différence entre fonction, variables et valeurs.

Figure 1.42. Construction de la fonction d'affectation locale LET

Construction de la fonction d'affectation locale LET

Les expressions d'initialisation sont évaluées dans l'ordre syntaxique, mais pour la fonction LET, les variables locales sont créées après toutes les initialisations. Pour la fonction LET, il est possible de l’utiliser sans les parenthèses englobantes. Il est peut-être plus visuel d’utiliser les parenthèses, car il s’agit d’un moyen pour se délimiter les liens d’interprétation afin d’évaluer et attribuer correctement les valeurs aux bons symboles.

Figure 1.43. Exemples de la fonction d’affectation locale LET

Exemples de la fonction d’affectation locale LET

Nous remarquons dans la deuxième partie de l’exemple précédent que les symboles a et b ont des valeurs globales avec la fonction SETQ. Dans l’interprétation, de la fonction LET les valeurs initiales de a et b (50 et 100) sont remplacées par les valeurs locales (9 (qui résultat de l’interprétation (+ 4 5)) et 10). Et nous constatons ensuite qu’en dehors de la fonction LET les variables a et b reprennent leurs valeurs initiales.

LET* : Pour l’interprétation de la fonction LET*, Les liaisons des variables sont créées séquentiellement après chaque initialisation.

Figure 1.44. Construction de la fonction d'affectation locale LET*

Construction de la fonction d'affectation locale LET*

Pour la fonction LET*, il est possible de l’utiliser sans les parenthèses englobantes. Il est peut-être plus visuel d’utiliser les parenthèses, car il s’agit d’un moyen pour se délimiter les liens d’interprétation afin d’évaluer et attribuer correctement les valeurs aux bons symboles.

Figure 1.45. Exemples de la fonction d’affectation locale LET*

Exemples de la fonction d’affectation locale LET*

L’exemple du LET* indique bien la priorité du déclenchement des interprétations. Dès la lecture de de x 3 la valeur est attribué à x. Contrairement à let ou il est nécessaire de faire intervenir une gestion d’interprétation plus globale pour obtenir la valeur de x. Les fonctions LET et LET* seront aussi utilisées pour définir des fonctions sans pour autant leur donner un nom et donc sans réutilisation. Effet, le fait de faire des interprétations de façon locale avec LET et LET* dénote une construction de fonction avec arguments, mais en absence de nom de fonction, elles ne pourront pas être réutilisées plus tard et le résultat des opérations faites avec les valeurs données seront que ponctuels. Le modèle d’erreur propose les limites de la fonction et donc montre que les variables doivent être accessibles pour être utilisées.

La construction et l’utilisation des fonctions

DEFUN : La fonction Defun permet de créer une fonction avec nom, liste des arités d’entrée (argument) et le programme sous forme de S-expression.

Figure 1.46. Construction d’une fonction

Construction d’une fonction

La fonction Defun supprime l’évaluation des arguments et des listes. Une déclaration de fonction est valide par l’interpréteur si elle retourne le nom de la fonction qui vient d’être définie. Le nom, les arguments et le programme de la fonction sont déclarés de façon globale. Si cette fonction est valide par interprétation, elle pourra immédiatement être utilisée par appel du nom suivit de ses arguments à n’importe quel moment dans les programmes. Et c’est dans le cas d’un appel que les évaluations se feront.

Figure 1.47. Appel d'une fonction Lisp avec arguments

Appel d'une fonction Lisp avec arguments

Figure 1.48. Constructions et appels de fonctions construites

Constructions et appels de fonctions construites

A l’appel, il est à noter que les arguments des fonctions sont sans parenthèses englobantes si celles-ci ne sont pas nécessaires. Une parenthèse dénote le début d’une interprétation et par conséquent une parenthèse ouvrante est toujours suivie d’une fonction (opération). Si le système ne doit pas interpréter la fonction (opération) après la parenthèse ouvrante, alors il y aura une fonction de non interprétation avant la parenthèse. Une fonction peut s’appeler avec ses arguments sans parenthèse englobantes. Mais si les parenthèses étaient nécessaires pour l’interprétation et qu’elles sont oubliées, alors il y a une erreur.

Les fonctions d’entrées/sorties

READ : Il s’agit de la fonction qui permet de récupérer de la valeur venant de l’extérieur du système fonctionnel en cours. Cette fonction lit l'expression de type quelconque (toutes S-expression) sur le flux d'entrée courant.

Figure 1.49. Construction de la fonction de lecture READ

Construction de la fonction de lecture READ

La fonction read s’utilise uniquement avec les parenthèses englobantes. L’interprétation de la fonction read se met en suspend d’une action externe, comme la saisi d’une liste ou d’un atome de la part d’un utilisateur ou d’un système par fonction intermédiaire.

Figure 1.50. Exemples de la fonction d’entrée READ

Exemples de la fonction d’entrée READ

Pour correctement récupérer les valeurs transmises avec un symbole (une variable) il est nécessaire d’utiliser comme fonction de déclaration un defparameter.

PRINT : Il s’agit d’une fonction qui imprime le premier argument sur le flux standard de sortie de l’interpréteur. La fonction imprime les caractères d’échappement et les guillemets. La sortie est précédée par un retour à la ligne.

Figure 1.51. Construction de la fonction d'affichage PRINT

Construction de la fonction d'affichage PRINT

Figure 1.52. Exemples de la fonction de sortie PRINT

Exemples de la fonction de sortie PRINT

Il existe une fonction PRIN1 qui se comporte comme la fonction PRINT mais sans le premier saut de ligne.

TERPRI (PRInt RETurn) : Il s’agit d’une fonction qui provoque l'impression du tampon de sortie. L'appel est sans argument et vide le tampon pour commencer une nouvelle ligne (retourne NIL). La fonction retourne la valeur de l'expression entrée.

Figure 1.53. Construction de la fonction d’affichage TERPRI

Construction de la fonction d’affichage TERPRI

Figure 1.54. Exemples de la fonction de sortie TERPRI

Exemples de la fonction de sortie TERPRI

FORMAT : Il s’agit d’une fonction qui permet de faire de l’affichage en utilisant des symboles et la valeur des symboles. Il sera nécessaire de faire appel aux inclusions par exemple ~A pour faire de l’insertion de valeur lors des affichages.

Figure 1.55. Construction de la fonction d’affichage FORMAT

Construction de la fonction d’affichage FORMAT

Figure 1.56. Exemples de la fonction de sortie FORMAT

Exemples de la fonction de sortie FORMAT

Le format d’écriture t (ou nil) indique que le texte imprimé sera avec guillemets (ou sans guillemets). Ensuite les formats ~A (texte), ~D (décimal), ~5D (avec espaces puis décimal), ~X (Hexadécimaux), ~5 (), … sont les formats pour interpréter les valeurs en fonction des types

Les prédicats

Les prédicats sont des fonctions Lisp qui testent le type ou la valeur des arguments, des arités, des symboles, des variables. L’interprétation de ces prédicats donne un résultat binaire. Ils sont donc évalués à TRUE (VRAI) ou à autre que TRUE, soient NIL ou () et sont utilisés généralement pour la construction de conditions et d’opérations de sélection (structure implantées : IF et COND). Ils seront très utiles pour stopper les récursivités en dénotant des cas de base et permettrons l’envoi de valeur éventuelle (selon les conditions).

ATOM : Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est un atome ou non. L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien un atome. L’interprétation retourne NIL dans le cas contraire.

Figure 1.57. Construction du prédicat de test ATOM

Construction du prédicat de test ATOM

Le prédicat ATOM peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.58. Exemples du prédicat de test ATOM

Exemples du prédicat de test ATOM

Les tests précédents proposés avec le prédicat atom sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

SYMBOLP : Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est un symbole ou non. L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien un symbole. L’interprétation retourne NIL dans le cas contraire.

Figure 1.59. Construction du prédicat de test SYMBOLP

Construction du prédicat de test SYMBOLP

Le prédicat SYMBOLP peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.60. Exemples du prédicat de test SYMBOLP

Exemples du prédicat de test SYMBOLP

Les tests précédents proposés avec le prédicat symbolp sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

CONSP : Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est une liste ou non. L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien une liste. L’interprétation retourne NIL dans le cas contraire.

Figure 1.61. Construction du prédicat de test CONSP

Construction du prédicat de test CONSP

Le prédicat CONSP peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.62. Exemples du prédicat de test CONSP

Exemples du prédicat de test CONSP

Les tests précédents proposés avec le prédicat consp sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

NULL : Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est une liste vide ou NIL ou (). L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien une liste vide ou NIL ou (). L’interprétation retourne NIL dans le cas contraire même avec un atome.

Figure 1.63. Construction des prédicats de test NULL

Construction des prédicats de test NULL

Le prédicat NULL peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.64. Exemples du prédicat de test NULL

Exemples du prédicat de test NULL

Les tests précédents proposés avec le prédicat null sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

ENDP : Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est une liste vide ou NIL ou (). L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien une liste vide ou NIL ou (). L’interprétation retourne NIL dans le cas contraire ou erreur dans le cas d’un atome.

Figure 1.65. Construction des prédicats de test ENDP

Construction des prédicats de test ENDP

Le prédicat ENDP peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.66. Exemples du prédicat de test ENDP

Exemples du prédicat de test ENDP

Les tests précédents proposés avec le prédicat endp sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

LISTP : Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est une liste ou NIL ou (). L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien une liste vide ou NIL ou (). L’interprétation retourne NIL dans le cas contraire.

Figure 1.67. Construction des prédicats de test LISTP

Construction des prédicats de test LISTP

Le prédicat LISTP peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.68. Exemples du prédicat de test LISTP

Exemples du prédicat de test LISTP

Les tests précédents proposés avec le prédicat listp sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

NUMBERP: Il s’agit d’un prédicat avec une arité qui teste si l'argument donné est un nombre. L’interprétation retourne donc T (True, vrai) si ce test est vérifié et que l’argument est bien un nombre. L’interprétation retourne NIL dans le cas contraire.

Figure 1.69. Construction du prédicat de test NUMBERP

Construction du prédicat de test NUMBERP

Le prédicat NUMBERP peut s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.70. Exemples du prédicat de test NUMBERP

Exemples du prédicat de test NUMBERP

Les tests précédents proposés avec le prédicat numberp sont des exemples pour constater quel argument provoquera une erreur ou un résultat, et comment, il faut utiliser ce prédicat en fonction des arités obligatoires. Le but est de pouvoir contrôler ou sécuriser un programme lors des différents parcours et recherches qui seront mis en place pour produire une action. Il est nécessaire de pratiquer et de produire sa connaissance en fonction des prédicats pour éviter des erreurs de compréhension de résultat lors de programmes plus conséquents. Les messages d’erreurs sont à lire pour comprendre comment il faut corriger vos programmes.

ZEROP : Il s’agit d’un prédicat avec 1 arité qui vérifie si l’argument donné est un 0. L’interprétation retourne donc T (True vrai) si la valeur donnée est un entier 0. L’interprétation retourne NIL dans le cas contraire.

Figure 1.71. Construction du prédicat de test ZEROP

Construction du prédicat de test ZEROP

Le prédicat ZEROP peut s'utiliser avec des parenthèses englobantes pour délimiter les liens d’interprétation et d’évaluation. Mais il est possible de ne pas utiliser les parenthèses comme pour les exemples suivants.

Figure 1.72. Exemples du prédicat de test ZEROP

Exemples du prédicat de test ZEROP

Dans l’exemple précédent, seul le zéro entier permet d’avoir T comme interprétation. Il est toujours possible de noter qu’une interprétation stoppe correctement ou non si tous les S-expressions sont indentifiables. D’où l’erreur avec l’atome a, car il est dépourvu de valeur. Il serait possible d’attribuer une valeur à a comme 0 pour obtenir une interprétation T ou une autre différente de 0 pour obtenir un résultat NIL.

< ou > ou <= ou >= ou = : Il s’agit de prédicats avec plusieurs arités de type numérique. Ils vérifient des propriétés d’ordre des arguments numériques donnés. L’interprétation retourne donc T (True vrai) si les arguments sont en adéquation avec la propriété demandée, à savoir tous égaux ou supérieurs ou inférieurs. Même si il y a plusieurs arguments, les propriétés sont faites avec des données 2 à 2, en suivant une interprétation logique de conjonction. L’interprétation retourne NIL dans le cas contraire.

Le nombre d'arguments peut-être supérieur à deux. Dans ce cas, tous les éléments sont vérifiés deux à deux et d’un qu’une interprétation retourne NIL, le résultat est NIL. Pour obtenir un résultat T, il faut que toutes les interprétations deux à deux retournent T.

Figure 1.73. Construction des prédicats de test numérique <, >= et =

Construction des prédicats de test numérique <, >= et =

Les prédicats < ou > ou <= ou >= ou = peuvent s’utiliser sans les parenthèses englobantes. Cependant, les parenthèses délimitent les liens d’interprétation pour évaluer et tester correctement l’argument donné.

Figure 1.74. Exemples des prédicats de test d’ordre sur les nombres

Exemples des prédicats de test d’ordre sur les nombres

Avec les exemples précédents, bien que les prédicats admet 2 artiés, il est possible d’en utiliser qu’une. Dans ce cas il y aura une interprétation à T ou NIL si la S-expression est correctement interprétable et une erreur sinon.

EQUAL : Il s’agit d’un prédicat avec 2 arités qui vérifie l’égalité de ses 2 arguments donnés. L’interprétation retourne donc T (True vrai) si le premier argument est égal au second. L’interprétation retourne NIL dans le cas contraire. EQUAL est universel et teste toutes les S-expressions

EQ : Il s’agit d’un prédicat avec 2 arités qui vérifie l’égalité de ses 2 arguments atomes ou nombres donnés. L’interprétation retourne donc T (True vrai) si le premier argument est égal au second. L’interprétation retourne NIL dans le cas contraire. EQ ne sait pas comparer des listes entre elles. Pour des listes EQ retournera toujours NIL.

Figure 1.75. Construction des prédicats de test EQUAL et EQ

Construction des prédicats de test EQUAL et EQ

De façon plus universelle et contrairement au prédicat =, le prédicat equal compare aussi bien les nombres, que les listes, que les atomes, ce qui n’est pas le cas pour l’opérateur = qui ne comparent que des nombres et eq qui ne sait pas comparer les listes.

Figure 1.76. Exemples des prédicats de test EQUAL et EQ

Exemples des prédicats de test EQUAL et EQ

LES INSTRUCTIONS DE CONTROLE

Les structures de contrôle sont des fonctions plus évoluées qui contrôlent le déroulement du programme selon des conditions imposées. Nous distinguons les structures de « sélection » (IF, COND) et les structures de « répétition » (la récursivité et l’itération). Le principe même de la programmation fonctionnelle est basé sur la récursivité, axe de ce cours, mais, nous évoquerons aussi les structures d’itération.

Les opérations de sélection

IF : La fonction IF du langage Lisp correspond à l’instruction IF des langages procéduraux (Basic, Pascal, C). Elle permet au programme de suivre des chemins différents selon qu’une condition est satisfaite ou pas.

Figure 1.77. Construction d’une opération IF

Construction d’une opération IF

Figure 1.78. Exemples d’opérations de sélection avec la fonction IF

Exemples d’opérations de sélection avec la fonction IF

Dans le cas où la condition est évaluée à VRAI, l'action 1 est réalisée. Dans le cas où la condition est évaluée à FAUX, les actions suivantes sont réalisées. Il est à noter que VRAI permet l’évaluation d’une seule expression, tandis que le FAUX permet l’évaluation de plusieurs expressions et retourne la valeur de la dernière. Pour accepter plusieurs expressions, il sera possible d’utiliser une fonction de conjonction AND.

COND : La fonction COND correspond à l’instruction SWITCH du C. Elle est composée de plusieurs IF emboîtés.

Figure 1.79. Construction d’une opération COND

Construction d’une opération COND

Chaque test correspond à l’évaluation d'une condition. Lorsque la condition est vérifiée, l'action associée est réalisée et fait sortir du COND. Si le test est interprété à FAUX, nous passons au test suivant. Dans le cas où aucune condition n'a été vérifiée, T (True) provoque les actions par défaut. Nous remarquons que dans la fonction COND chaque groupe paire-action se trouve entre des parenthèses.

Figure 1.80. Exemples d’opérations de sélection avec la fonction COND

Exemples d’opérations de sélection avec la fonction COND

Il est important de garantir que les propriétés exprimées par les tests doivent être complémentaire et disjoint. Cela veut bien dire que chaque propriété est une partie de l’ensemble à évaluer et que l’ensemble de tous les tests couvre tous les possibles. D’où l’importance de la valeur T en dernier test qui représente la propriété complémentaire de tous les autres propriétés évaluées à faux avant. Il est possible maintenant de prendre ses principes de sélection pour les appliquer à la résolution de problèmes. Ils sont pratiques pour construire des résolutions par récursivité. Prenons l’exemple de la construction d’une factorielle. Nous avons : n ! = n * ( n - 1) ! et considérons que 0 ! = 1 = 1 ! L’algorithme s’écrit alors :

      
fontion factorielle nommée fact avec un arité (un entier) --> un entier 

fact (n):
   if n > 1 ou n > 0 :
      return 1
   else :
      return n * fact(n-1)
     

Figure 1.81. Programme récursif d’une Factorielle avec une structure IF

Programme récursif d’une Factorielle avec une structure IF

Il est aussi possible d’utiliser un COND pour nous permettre de bien mettre en valeur dans notre programmation avec les 3 propriétés nécessaires.

Figure 1.82. Programme récursif d’une Factorielle avec une structure COND

Programme récursif d’une Factorielle avec une structure COND

Dans une programmation récursive, la pile des appels des fonctions est construite en LIFO (Last In First Out). Lorsque nous finissons d’empiler les appels de la fonction factorielle, nous nous retrouvons au sommet de la pile avec la valeur 1. Cette valeur de 1 est normalement trouvée si n du départ est supérieur ou égal à 1 ou directement si n est égal 0 (qui est la valeur de l’interprétation de (fact 0)). Dans les deux cas, ceci constitue la condition d’arrêt. Ces propriétés sont les cas élémentaires de base pour arrêter la récursivité. Cette valeur de 1 est donc la première valeur sortie lors du dépilement de la pile et remonte pour satisfaire l’appel précédent de la fonction fact. A la fin du dépilement, la valeur finale de la factorielle est retournée. Par exemple pour (fact 3), le calcul fait est en réalité 1 * 2 * 3 pour obtenir 6.

Les opérations d’itération

PROG … GO … RETURN

PROG : Il s’agit d’un opérateur pouvant accepter un nombre d’argument nul. Il a pour but de permettre des itérations en langage Lisp. Bien qu’il soit préférable d’utiliser la récursivité en langage Lisp, il est possible de faire des itérations.

Figure 1.83. Construction d’une opération PROG

Construction d’une opération PROG

La <liste> du PROG comprend les variables locales à PROG. Les <S-expressions> sont évaluées séquentiellement par PROG. L’exécution est interrompue par GO et RETURN. Go renvoie à une expression contenue dans PROG. RETURN interrompt le déroulement du PROG. Son paramètre devient le résultat du PROG.

Figure 1.84. Programme itératif d’une Factorielle avec une structure PROG … GO … RETURN

Programme itératif d’une Factorielle avec une structure PROG … GO … RETURN

Dans l’exemple, resultat est la variable contenant la valeur à transmettre pour l’afficher. Pour faire cette impression, il est nécessaire d’utiliser une fonction de PROG qui est return. N’oublions pas que la valeur d’une itération pour qu’elle soit transmise doit se construire au fur et à mesure et pour cela, il faut utiliser la fonction setq. Le nom boucle est inventé, il ne sert que d’ancre d’appel de la fonction GO. La succession des appels Go boucle constitue la répétition des actions à faire.

LOOP

LOOP : Il s’agit d’un opérateur pouvant reproduire des itérations. Un loop s’utilisera avec les opérations for, repeat et do.

Voici quelques formes de construction avec l’opérateur Loop :

Les fonctions do de loop :

      
(loop do (print 1) (print 2)) 
     

Les fonctions for de loop :

      
(loop for i from 1 to 3 do (print i)) 

(loop for i from 1 below 10 do (print i)) 

(loop for i from 10 above 1 do (print i)) 

(loop for i upfrom 1 to 10 do (print i)) 

(loop for i downfrom 10 to 1 do (print i)) 

(loop for i from 1 upto 10 do (print i))
 
(loop for i from 7 to 10 by 1 
          initially (print i) 
          finally (print (+ i i)) )
     

Les fonctions repeat de loop :

      
(loop repeat 4 do (print "repeat")) 
     

Les fonctions complémentaires

Il est possible d’avoir des fonctions d'ordre supérieur qui prend les fonctions comme argument et les applique sur des ensembles de données.

APPLY : dont la construction est (apply < f > < liste >) est une fonction qui retourne la valeur de l'application de la fonction transmise en premier argument < f > sur la liste placée en second argument < liste >

MAPCAR : dont la construction est (mapcar < f > < liste >) est une fonction qui retourne la liste formée des applications de la fonction transmise en premier argument <f>, à tous les éléments de la liste placée en second argument <liste>.

Différemment de de la fonction APPLY, la fonction MAPCAR applique la fonction successivement aux éléments de la liste.

LAMBDA : dont la construction est ((LAMBDA <variables> <f>) <valeurs locales des variables>) est une fonction qui retourne l’évaluation la fonction <f> avec des <variables> qui prennent des <valeurs locales>. La fonction <f> n’est pas un argument, mais bien le corps d’une fonction construit par la fonction lambda qui produit un résultat avec les valeurs locales en fonction des variables. En dehors de LAMBDA les variables ne sont pas liées et donc non disponibles.

      
dotimes est une macro pour l'itération sur les entiers :
(dotimes (a 3) 
(print a)) 


dolist est une macro pour l'itération sur les éléments d'une liste : 
(dolist (a '(x y z)) 
(print a))
     

     
random tirage parmi des entiers : 
(random 100)
    

    
rem modulo de valeur :
(rem 6 2)
    

Les macros

Une macro est évaluée en 2 étapes. La première correspond à une phase d'expansion (ou de traduction) en une forme évaluable en langage Lisp. Dans la deuxième étape cette forme est évaluée. Les macro-fonctions sont définies avec le mot-clé defmacro.

Figure 1.85. Exemple d’une fonction MACRO

Exemple d’une fonction MACRO

A partir de l’exemple nous avons les 2 étapes :

  • Traduction: les expressions (< a 0), (1- a) et (1+ a) sont passées en arguments de la macro IF sans être évaluées (1- et 1+ sont des opérateurs pour soustraire, respectivement ajouter une unité).

  • Evaluation : le corps de la macro a été expansé pour donner l’expression correspondante du COND qui sera évaluée.

Le caractère backquote ou ` construit une liste sans évaluer ses éléments. L'effet du backquote est annulé grâce à la virgule ou à l'association virgule-arobas. La différence entre le quote et le backquote est que ce dernier peut être annulé à l’intérieur d’une liste de plusieurs manières.

Figure 1.86. Exemple de fonctions MACRO Empile et Depile

Exemple de fonctions MACRO Empile et Depile

Dans les faits, la fonction EMPILE équivaut à une fonction CONS et la fonction DEPILE à une fonction CAR mais à la différence de ceux-ci les macros modifient durablement leurs variables. Ces modifications durables sont dues à l’utilisation d’un SETQ dans leurs définitions.

DANS LA SUITE DU COURS

Nous sommes maintenant en mesure de faire de la programmation fonctionnelle avec le langage Lisp. Toutes les fonctions créées constituent notre bibliothèque. Toutes les fonctions peuvent et doivent être réutilisées pour construire et définir nos futurs programmes. Jusqu’à présent, nous avons accepté toutes les données d’entrées sans savoir comment elles étaient produites. Nos fonctions sont utilisées en tenant compte des domaines, contraintes et des valeurs données. Il s’agit maintenant de construire ces données (et le programmes). Nous allons définir dans le prochain chapitre la notion d’espaces des états tout en garantissant que nous avons toujours des séquences de données. Cette notion sera étendue au programme lui-même. Puis nous envisagerons des réalisations de problèmes guidées par les valeurs des états à obtenir.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels