Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

LE LANGAGE LISP I - INTRODUCTION LISP signifie LISt Processing (traitement de l

LE LANGAGE LISP I - INTRODUCTION LISP signifie LISt Processing (traitement de liste). Ce langage a été inventé par J. McCarthy au M.I.T. en 1960. Son créateur le destinait aux problèmes non numériques alors que la préoccupation générale des langages nés à cette époque était le calcul numérique. De ce fait, LISP est resté longtemps dans l'oubli. Son essor est dû en partie à l'Intelligence Artificielle. Aujourd'hui, c'est le langage le plus utilisé dans ce domaine. Depuis sa création, LISP a longtemps échappé à toute standardisation. De fait, il existe à l'heure actuelle plusieurs dialectes de LISP. Nous étudierons "CommonLisp", langage qui fait l'objet d'une normalisation ANSI depuis 1984. Guy L. Steele (Carnegie Mellon University, Lexington, Massachusetts) a publié la norme établie par le comité X3J13 en Octobre 1989. CommonLisp présente l'avantage de disposer d'un compilateur rendant les programmes aussi efficaces en exécution que ceux développés dans des langages plus traditionnels. Ce polycopié a pour objectif d'aider à l'initiation au langage LISP en évitant une lecture complète de la documentation CommonLisp. Dans un deuxième temps, cette lecture est cependant vivement conseillée afin d'acquérir une vue plus précise et plus globale du langage. Une documentation en ligne est disponible sur le site Web de l'ENSI Caen. II - LES OBJETS DE LISP II.1 - L'alphabet - Les lettres a,b, ... ,z, A, B, ... Z (par défaut les minuscules sont transformées en majuscules sauf dans les chaînes de caractères). - Les chiffres 0,1,...,9. - D'autres caractères : ! " # $ & ' ( ) * + , - . / : ; < = > ? @ [ \ ] ^ _ {  } ` ~ Remarque : l'emploi de quelques caractères spéciaux comme ' (le caractère quote), %, # ,... , qui ont une signification particulière en LISP, est délicat. Il faut en général les entourer de guillemets pour les faire figurer dans une chaîne de caractères ou encadrer la chaîne de caractères qui les contient par deux barres verticales s'il s'agit d'un symbole (ex : |exemple.nom|). Les commentaires de fin de ligne sont précédés du caractère ; Les commentaires sur plusieurs lignes commencent par #| et se terminent par |# II.2 - Les objets atomiques Les objets atomiques représentent les informations élémentaires. Exemples : ALICE CH4 12CENTS 167 tic-tac exemple_d_atome |to:to| (pour to:to) "exemple de chaînes de caractères" On distingue trois sortes d'objets atomiques : les nombres, les symboles et les chaînes de caractères. CommonLisp manipule des nombres entiers, des nombres rationnels et des nombres réels. Leur notation correspond à la notation usuelle Pascal en ce qui concerne les entiers et les réels. Les rationnels sont notés x/y (ex: 1/2). Les symboles contiennent au moins un caractère non numérique, ceci en tenant compte de la représentation flottante des nombres (2E3 est un nombre et 2A3 est un symbole). Ils jouent le rôle d'identificateurs et servent à nommer les variables et les fonctions. - - Les chaînes de caractères sont désignées par une suite de caractères encadrée de guillemets. Le caractère " est un séparateur, il n'est donc pas possible de le faire apparaître dans une chaîne de caractères. II.3 - Les listes Une liste est représentée par une parenthèse ouvrante, une parenthèse fermante et entre les deux, des objets atomiques ou d'autres listes, séparés par des blancs. Exemples : (X1 X2 X3) ((X1) (X2 X3) X4) (lisp (est un) langage) La liste vide est désignée par NIL ou () . Cette liste est aussi considérée comme un atome. C'est la seule liste ayant cette propriété. Pour toute liste L=(A1 ... AN), les Ai s'appellent les éléments de L. Tout traitement d'une liste laissant invariant ses éléments, s'appelle un traitement au premier niveau. Exemple : L'inversion au premier niveau de la liste ((A B) (A B C) (B C)) donne : ((B C) (A B C) (A B)) L'inversion de la même liste à tous les niveaux donne : ((C B) (C B A) (B A)) Les listes servent à regrouper (structurer) des informations pour mieux les traiter. La structure de liste sera la principale structure de données LISP examinée dans ce cours. CommonLisp manipule également des vecteurs,des structures et des tables de hachage. II.4 - Les expressions symboliques Une expression symbolique (ou S-expression ou Sexp) est un atome ou une liste. En résumé, les objets LISP sont subdivisés de la manière suivante: SEXP ATOMES NOMBRES SYMBOLES CHAINES DE CARACTERES LISTES II.5 - Les fonctions La notion de fonction est une notion primordiale en LISP. Les fonctions sont les seuls moyens de former des programmes. Un grand nombre de fonctions manipulant des atomes et des listes sont prédéfinies et sont à la disposition de l'utilisateur dès le lancement du système. L'utilisateur a par ailleurs des outils pour regrouper ces fonctions et contrôler l'enchaînement de leur exécution. Le corps d'une fonction est l'ensemble des instructions qui indique à l'interpréteur la marche à suivre pour transformer les arguments d'entrée. II.5.1 - L'appel des fonctions ISMRA ENSICAEN - Polycopié LISP - 2001-2002M. REVENU 2 - - L'appel d'une fonction avec ses arguments est représenté par une liste dont le premier élément est le symbole fonctionnel et les autres éléments les arguments de la fonction. Cela correspond à une notation préfixée. L'emploi des nombres pour nommer des fonctions est interdit. En Pascal ou en C, l'appel d'une fonction F est F(X1,X2,...,XN); en LISP, ce sera (F X1 X2 ... XN). Et en généralisant, 2 + 3 sera représenté par (+ 2 3) et (X - 1)(Y + 2) par (* (- X 1) (+ Y 2)). Une forme est une liste représentant une fonction et la suite de ses arguments. Evaluer une forme consiste à calculer la valeur de la fonction qu'elle représente pour les arguments spécifiés dans la liste (ex: (GCD 14 3) ). II.5.2 - Exemples de fonctions Nous allons étudier quelques fonctions numériques (ayant pour arguments des nombres). Celles- ci sont des fonctions de l'arithmétique générique. Leurs arguments peuvent être soit des entiers, soit des rationnels, soit des réels. Le type du résultat dépend du type des arguments. Il est réel si l'un des arguments est réel. Il est entier si cela est possible. a) L'addition : fonction à n arguments, représentée par le symbole fonctionnel "+". Exemples : (+ 2 3 6 9) ---> 20 (+ 8 -2 6) ---> 12 (+ 8) ---> 8 (+) ---> 0 (+ 2 2.0) ---> 4.0 (+ 2 2/3) ---> 8/3 b) La soustraction : fonction à n arguments, représentée par le symbole fonctionnel "-". Exemples : (- 4 2) ---> 2 (- 10 2 3 4) ---> 1 (= 10-2-3-4) (- 8) ---> -8 c) La multiplication : fonction à n arguments, représentée par le symbole fonctionnel "*". Exemples : (* 2 3 5) ---> 30 (* 5) ---> 5 (*) ---> 1 d) La division : fonction à n arguments, représentée par le symbole fonctionnel "/". Exemples : (/ 12 6) ---> 2 (/ 123.45 6.7) ---> 18.4254 (/ 21 5) ---> 21/5 (/ 2) ---> 1/2 (/ 21 5.0) ---> 4.2 II.5.3 - Le principe d'évaluation des arguments d'une fonction ISMRA ENSICAEN - Polycopié LISP - 2001-2002M. REVENU 3 - - L'expression (2 + 5) * 3 s'écrit en LISP : (* (+ 2 5) 3 ) [1] L'interpréteur LISP, décelant le symbole "*" en tête de liste, tentera de multiplier entre eux les autres éléments de la liste. Cette tentative échouerait si la forme (+ 2 5) présente dans la forme [1] n'était pas évaluée auparavant. L'interpréteur LISP évaluera donc systématiquement tous les arguments de la fonction "*", avant de les multiplier entre eux. De ce fait, il évaluera également le nombre 3 présent en deuxième argument dans la forme [1] pour donner la valeur 3. Nous venons de décrire un mécanisme fondamental en LISP, celui de l' évaluation des atomes et des formes. II.5.4 - Evaluation des atomes et des formes a) A chaque atome on peut associer une valeur qui sera un atome ou une liste. Evaluer un atome consiste à trouver cette valeur. Certains atomes ont une valeur prédéfinie au lancement du système. Il s'agit notamment : - des nombres. Ils ont leur propre valeur. Ex: 3 ---> 3 - T ou t : utilisé pour la valeur logique "vrai". Sa valeur est t. - NIL ou nil : représente la valeur logique "faux". Sa valeur est NIL ou (). - certains symboles tels que pi qui a pour valeur 3.1415926535897932385L0. - des mots-clés. Tout symbole commençant par : est un mot-clé et leur valeur est le symbole lui- même. Ex: :tout ---> :TOUT b) Les arguments de la plupart des fonctions sont évalués avant l'entrée dans le corps de la fonction. On dit que ces fonctions sont normales. c) Les arguments de certaines fonctions ne sont pas évalués avant l'entrée dans le corps de la fonction (mais peuvent être évalués sélectivement dans le corps de la fonction). Il s'agit des fonctions spéciales : Exemple : à l'appel de la fonction IF qui teste uploads/Philosophie/ lisp-01.pdf