Cours programmation Lisp : Opérateurs et fonctions
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 : ||).
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:
NOMBRES
ATOMESSYMBOLES
SEXP 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
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). Cellesci 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
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 luimê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 si la valeur d'une expression est Vrai ou Faux, seul le test est d'abord évalué. Ensuite soit l'expression correspondant au "alors", soit l'expression correspondant au "sinon" est évaluée.
d) LISP reconnaît d'autres types de fonctions, appelées MACRO fonctions qui ont un mode
d'évaluation particulier.
Remarque :
Le nombre d'arguments d'une fonction est parfois quelconque. Nous l'indiquerons à l'aide du mot &rest dans la liste des paramètres, ainsi que le prévoit la syntaxe de la définition des fonctions par la fonction "defun".
III - LES PRINCIPALES FONCTIONS PREDEFINIES
Nous allons voir dans ce chapitre les principales fonctions prédéfinies.
III.1 - Evaluation et affectation
a) (QUOTE ) [spéciale]
Fonction spéciale à un argument, retourne la S-expression non évaluée.
Il existe un macro-caractère prédéfini qui facilite l'utilisation (très fréquente) de cette fonction; il s'agit du caractère apostrophe ' . Quand ce caractère est placé devant une expression quelconque , à la lecture l'interpréteur LISP fabrique la liste (QUOTE ).
Exemples :
?(QUOTE 'A) ?'A ?''A ?(QUOTE (+ 1 2))
='A =A ='A =(+ 1 2)
b) (EVAL )
EVAL retourne la valeur de l'évaluation de la valeur de .
Exemples :
?(EVAL '(+ 1 4)) ?(EVAL '(SETQ A 'B))
=5 =B
?(EVAL (SETQ A 'B))
=ERREUR (si B n'a pas de valeur)
c) (SET )
a pour valeur un symbole. SET associe à ce symbole la valeur de et retourne cette valeur. Il s'agit d'une opération d'affectation.
Exemples :
?(SET 'A '(X Y Z)) ?A
=(X Y Z) =(X Y Z)
d) (SETQ ) [spéciale]
Fonction à 2N arguments qui associe au symbole la valeur de et retourne à la valeur . Les affectations se font séquentiellement.
Exemples :
?(SETQ ZERO 0 UN 1 DEUX 2) | ?ZERO | ?UN | |
=2 | =0 | =1 | |
?(SETQ A 'B A 'C) | ?A | ?B | |
=C | =C | =ERREUR |
Ethymologie: Q figure dans SETQ pour QUOTE (les arguments d'ordre pair ne sont pas quotés).
e) (SETF ) [spéciale]
C'est une généralisation de SETQ où indique le moyen d'accès à la donnée à modifier.
Exemples : (cf §III.2 pour la signification de la fonction CAR)
?(SETF L '(a b c)) =(A B C)
?(SETF (CAR L) 4) ? (CAR L) ?L
= 4 = 4 = (4 B C)
D'autres exemples de l'utilisation du SETF seront vus dans la suite du polycopié.
f) (FUNCTION ) [spéciale]
Cette fonction retourne l'interprétation fonctionnelle de .
Si est un symbole, la définition fonctionnelle associée au symbole est retournée.
Si est une lambda expression, la "fermeture lexicale" sera retournée, ce qui permet d'observer correctement, lors des évaluations successives, les règles de liaison lexicale. Une fermeture lexicale consiste en l'association d'un code et d'un environnement (valeur des variables). L'abréviation de l'appel de cette fonction est #' .
Exemples: (voir aussi les fonctions apply et funcall)
?(defun adder (x) (function (lambda (y) (+ x y))))
=adder
?(setq add3 (adder 3))
=#
?(funcall add3 5) = 8
?(defun deux-fn (x)
(list (function (lambda () x)) (function (lambda (y) (setq x y)))))
=deux-fn
?(setq fns (deux-fn 6))
=(# )
?(funcall (car fns))
= 6
?(funcall (cadr fns) 43)
= 43
?(funcall (car fns))
=43
?(defun decroissant? (x y f) (if (> (funcall f x) (funcall f y)) t nil)) = decroissant?
?(decroissant? 1 2 #'(lambda (x) (* x x)) )
=nil
?(setq reciproque #'(lambda (x) (/ 1 x)) )
=#
?(decroissant? 1 2 reciproque)
=t
III.2 - Fonctions de décomposition de listes
a) (CAR ) ou (FIRST )
est évalué et si a pour valeur une liste, CAR retourne le premier élément de cette liste.
Exemples :
?(CAR '(A B C)) | ?(CAR (A B C)) | ?(CAR '((A B) C) | |
=A | =ERREUR | =(A B) | |
?(CAR (SETQ X '(A B))) | ?(CAR X) | ||
=A | =A | ||
?(CAR '(SETQ X '(A B)) | ?(CAR 'A) | ?(CAR NIL) | |
=SETQ | =ERREUR | =NIL |
Ethymologie: CAR est l'abréviation de Contenent of Adress Register. C'est le mnémonique d'une instruction d'une ancienne machine (IBM 704) sur laquelle a été implanté le premier LISP.
b) (CDR ) ou (REST )
Si a pour valeur une liste, CDR retourne la liste obtenue en enlevant son premier élément.
Exemples :
?(CDR '(A B C)) | ?(CDR '((A) (B))) | ?(CDR '(A)) |
=(B C) | =((B)) | =NIL |
?(CDR (SETQ X '(A B))) | ?(CDR X) | ?(CDR '(SETQ X '(A B))) |
=(B) | =(B) | =(X '(A B)) |
?(CDR 'A) ?(CDR NIL)
=ERREUR =NIL
Ethymologie: CDR est l'abréviation de Contenent of Decrement Register et a la même origine que CAR.
c) (C R )
La fonction composée Cx1R o Cx2R o o CxnR où xi est le caractère A ou le caractère D, peut être notée par Cx1x2 xnR.
Exemples :
?(CADR '(A B C)) ;(c-à-d (CAR (CDR )) ) ?(CADDAR '((A B C) E F))
=B =C
Le nombre de CAR et CDR à composer ne doit pas dépasser 3 ou 4 suivant les versions. d) (LAST )
Si a pour valeur une liste L, LAST retourne la liste ayant pour élément le dernier élément de L. Sinon un message d'erreur est retourné.
Exemples :
?(LAST '(A B C)) ?(LAST '(A B (C D))) ?(LAST 12)
=(C) =((C D)) =ERREUR
?(LAST NIL)
=NIL
e) (NTH )
Retourne le nième élément de , les éléments étant numérotés à partir de zéro.
Exemple :
?(NTH 2 '(A B C D))
=C
f) (POP )
indique le moyen d'accès à une valeur devant être une liste. Cette fonction retourne le CAR de cette liste et affecte comme nouvelle valeur à le CDR de son ancienne valeur. est un argument facultatif qui reçoit la valeur retournée par POP. Cette fonction agit par modification physique de la liste.
Exemple :
?(SETF A '(X Y Z W))
=(X Y Z W)
?(POP A)
=X
?A
=(Y Z W)
?(POP (CDR A))
= Z
?A
=(Y W)
III.3 - Fonctions de construction de listes
a) (CONS )
CONS retourne la liste ayant pour CAR la valeur de et pour CDR la valeur de .
Exemples :
?(CONS 'A '(B C)) ?(CONS '(B C) '(B C))
=(A B C) =((B C) B C )
?(CONS '(A) NIL) =((A))
Remarques :
- Les deux listes NIL et (NIL) ont NIL pour CAR et CDR. (CONS NIL NIL) retourne (NIL). - Si la valeur de est un atome, CONS retourne une paire pointée:
?(CONS 'A 'B)
= (A . B)
?(CDR '(A . B))
= B ;(et non (B))
b) (LIST ) Retourne la liste des valeurs des .
Exemples :
?(LIST 'A 'B 'C) ?(LIST (+ 2 3) (CDR '(A B C)))
=(A B C) =(5 (B C))
?(LIST NIL)
=(NIL)
c) (APPEND )
Exemples :
?(APPEND '(A B) '(B C) '(C A)) ?(APPEND NIL '(A))
=(A B B C C A) | =(A) |
?(APPEND 'A 'B) | ?(APPEND '(A B) 'C '(D E)) |
=ERREUR | =ERREUR |
?(APPEND '(A B) 'C) | ?(APPEND '(A B) () '(C)) |
= (A B . C) | =(A B C) |
d) (PUSH )
indique le moyen d'accès à une valeur devant être une liste. PUSH place en tête de cette liste la valeur de et retourne la nouvelle liste formée. Les fonctions POP et PUSH permettent de construire et manipuler physiquement des piles-listes.
Exemple :
?(SETF A '(X Y Z))
=(X Y Z)
?(PUSH 'W A)
=(W X Y Z) ?A
=(W X Y Z)
?(PUSH 'U (CDDR A))
=(U Y Z)
?A
=(W X U Y Z)
III.4 - Autres fonctions sur les listes
a) (LENGTH )
Si la valeur de est une liste, LENGTH retourne le nombre d'éléments (au premier niveau) de cette liste; sinon LENGTH retourne un message d'erreur.
Exemple :
(LENGTH '((A B) (A B C) (B C))) ---> 3
b) (REVERSE )
REVERSE retourne une copie inversée du premier niveau de la liste valeur de .
Exemple :
?(REVERSE '(A (B C) D))
=(D (B C) A)
c) (SUBST )
SUBST fabrique une nouvelle copie de la valeur de l'expression en substituant à chaque occurrence de la valeur de , la valeur de .
Exemple :
?(SUBST '(A B) 'X '(X (X Y)))
=((A B) ((A B) Y))
d) (REMOVE )
REMOVE retourne une copie de dans laquelle l' a été supprimé.
III.5 - Prédicats et fonctions de test
(NULL )
Si la valeur de est NIL, NULL retourne T, sinon retourne NIL.
(ATOM )
Si la valeur de est un atome, ATOM retourne T, sinon retourne NIL.
(LISTP )
Si la valeur de est une liste, même vide, LISTP retourne T, sinon retourne NIL.
(CONSP )
Si la valeur de est une liste non vide, CONSP retourne T, sinon retourne NIL.
(SYMBOLP )
Si la valeur de est un symbole, SYMBOLP retourne T, sinon retourne NIL.
(FUNCTIONP )
Si la valeur de est une fonction, FUNCTIONP retourne T, sinon retourne NIL.
(NUMBERP )
Si la valeur de est un nombre, NUMBERP retourne T, sinon retourne NIL.
(INTEGERP )
Si la valeur de est un nombre entier, INTEGERP retourne T, sinon retourne NIL.
(RATIONALP )
Si la valeur de est un nombre rationnel, RATIONALP retourne T, sinon retourne NIL.
(CONSTANTP )
Si la valeur de est constante, CONSTANTP retourne T, sinon retourne NIL.
(FLOATP )
Si la valeur de est un nombre réel, FLOATP retourne T, sinon retourne NIL.
(EQUAL )
Teste si la valeur de et la valeur de sont égales. Si oui, EQUAL retourne T, Sinon EQUAL retourne NIL.
(EQ )
Si les valeurs des sont des symboles, EQ retourne T s'ils sont égaux.
Si ce ne sont pas des symboles, EQ va tester l'identité des représentations internes des arguments, c'est-à-dire tester s'ils ont la même adresse physique.
(EQL )
Teste si des nombres ou des symboles sont égaux, même s'ils n'ont pas la même adresse physique.
(NOT )
Si la valeur de est T, cette fonction retourne NIL, sinon retourne T.
(MEMBER &key :test)
&key indique la possibilité d'ajouter des arguments dans la forme d'appel avec le mot-clé :TEST
Teste si la valeur x de est un élément (au premier niveau) de la liste L, valeur de . Si OUI, MEMBER retourne la suite des éléments de L commençant par , et sinon, retourne NIL. Si la valeur de est un atome, MEMBER retourne un message d'erreur. Cette fonction utilise le prédicat EQL par défaut. Si on souhaite utiliser un autre prédicat pour effectuer le test, il faut le noter dans la liste d'arguments après le mot-clé :TEST.
Exemples :
?(MEMBER 'B '(A B C A B)) | ?(MEMBER 'A 'B) |
=(B C A B) | =ERREUR |
?(MEMBER '(A B) '((A) (A B) (B))) | ?(MEMBER 'A '((A))) |
=NIL | =NIL |
?(MEMBER '(A B) '((A) (A B) (B)) :test 'EQUAL) ?(MEMBER 'F '(A . F))
=((A B) (B)) =ERREUR
(= )
Si les valeurs de , , sont des nombres égaux, cette fonction retourne T, sinon elle retourne NIL.
( )
Si les valeurs des sont croissantes de façon monotone, cette fonction retourne T, sinon elle retourne NIL.
(> )
Si les valeurs des sont décroissantes de façon monotone, cette fonction retourne T, sinon elle retourne NIL.
( )
Si les valeurs des sont non décroissantes de façon monotone, cette fonction retourne T, sinon elle retourne NIL.
(>= )
Si les valeurs des sont non croissantes de façon monotone, cette fonction retourne T, sinon elle retourne NIL.
(/= )
Si les valeurs des sont toutes différentes, cette fonction retourne T, sinon retourne NIL.
(ZEROP )
Si la valeur de est un nombre et vaut 0, cette fonction retourne T, sinon NIL.
(PLUSP )
Si la valeur de est un nombre et est positive, cette fonction retourne T, sinon NIL.
(MINUSP )
Si la valeur de est un nombre et est négative, cette fonction retourne T, sinon NIL.
(ODDP )
Si la valeur de est un nombre impair, cette fonction retourne T, sinon NIL.
(EVENP )
Si la valeur de est un nombre pair, cette fonction retourne T, sinon NIL.
III.6 - Fonctions de contrôle
Ce sont des fonctions qui contrôlent l'exécution des instructions en imposant une exécution linéaire ou au contraire en rompant la linéarité ou encore en effectuant une exécution en boucle.
Ces fonctions sont presque toujours des fonctions spéciales. Il existe une grande variété de structures de contrôle en LISP.
III.6.1 - Les fonctions de contrôle conditionnelles
a) (IF ) [spéciale]
Si la valeur de est différente de NIL, IF retourne la valeur de ; sinon, IF évalue . IF permet de construire une structure de contrôle de type "si alors sinon" . Exemples :
?(IF T 1 2) ?(IF NIL 1 2) ?(IF NIL 1)
=1 =2 =NIL
2
Schéma de résolution de l'équation de second degré aX + bX + c = 0 :
(IF (= a 0)
(IF (= b 0)
(IF (= c 0)
(PRINT "une infinité de solutions")
(PRINT "aucune solution")) (PRINT "une seule solution"))
(LET ((DELTA (- (* b b) (* 4 a c)))) (IF (> DELTA 0)
(PRINT "2 solutions réelles") (IF (= DELTA 0)
(PRINT "solution double")
(PRINT "2 solutions imaginaires")))))
b) (WHEN ) [spéciale]
Si est Vrai, WHEN évalue chacune des expressions .
c) (UNLESS ) [spéciale]
Si est Faux, UNLESS évalue chacune des expressions .
d) (COND ) [spéciale]
COND est la fonction conditionnelle la plus complète de LISP.
Chaque
( ) où est une expression quelconque et le corps de la clause. COND sélectionne la première
Exemple :
?(defun test (x y)
(COND
((> x y) 'sup)
((= x y) 'egal)
(t 'inf))
)
= test
?(test 12 5)
= sup
?(test 5 8)
=inf
e) (CASE ) [spéciale]
Chaque
( ( ) | ) Exemple:
(CASE objet
(cercle (* pi r r))
((sphere balle) (* 4 pi r r)))
Le mot-clé OTHERWISE permet d'indiquer que faire dans tous les autres cas.
f) (TYPECASE ) [spéciale]
Chaque
g) (OR ) [spéciale]
Evalue dans l'ordre ,s'arrête au premier dont la valeur est distincte de NIL et retourne cette valeur.
Exemple :
?(OR (CDR '(A)) NIL (+ 2 3) (+ 3 4))
= 5
h) (AND ) [spéciale]
Evalue dans l'ordre et s'arrête au premier dont la valeur est NIL. Si aucun des n'a pour valeur NIL, AND retourne la valeur de , sinon AND retourne NIL.
Exemple :
?(AND (SETF X '(A B)) (CDDR X) (SETF Y 0))
=NIL
?X ?Y
=(A B) =ERREUR
III.6.2 - Les fonctions de contrôle séquentielles
a) (PROGN )
Evalue en séquence , et retourne la valeur de sN>.
Exemple :
Pour créer une structure de contrôle de la forme Si X Alors A1 A2 AN Sinon B1 B2 BM : (IF X (PROGN A1 AN) (PROGN B1 B2 BM))
b) (PROG1 )
Evalue en séquence , et retourne la valeur de s1>.
III.6.3 - Les blocs
Il est possible en CommonLisp de sortir directement d'un bloc d'instructions. L'utilisation des fonctions correspondantes doit cependant rester limitée à des cas particuliers de problèmes tels que la gestion des erreurs.
a) (BLOCK {}*)
Définit un bloc de nom . Les formes définies dans ce bloc sont évaluées en séquence sauf en cas de rencontre d'un appel aux fonctions RETURN ou RETURN-FROM. La valeur retournée est celle de la dernière forme évaluée.
b) (RETURN [])
Sort du bloc courant (par exemple une itération) et retourne la valeur de .
(loop while t do
(case (read)
(1 (print "ok"))
(otherwise (return ()))))
c) (RETURN-FROM [])
Sort du bloc de nom et retourne la valeur de .
III.6.4 - Les fonctions de répétition
En LISP, toutes les structures répétitives définies dans les langages tels que PASCAL ou C sont implantées. On retrouve l'équivalent des fonctions WHILE, UNTIL, REPEAT et des fonctions itératives FOR et DO.
a) DO est une fonction générale d'itération à une ou plusieurs variables de contrôle.
(DO ( { | ( [ [] ) } * )
( {}* )
{}* { }* ) Exemple:
?(DO ((x foo (cdr x))
(y bar (cdr y))
(i 1 (+ i 1))
((
(format nil "x= ~s y= ~s i= ~s " x y i))
b) DOLIST est une fonction d'itération sur les listes.
?(DOLIST (x '(a b c)) (prin1 x))
ABC =NIL
c) DOTIMES est une fonction élémentaire d'itération sur les entiers.
La variable est initialisée à 0 et le test >= est utilisé pour sortir de la boucle.
?(DOTIMES (i 10 i) (prin1 i))
0123456789
=10
d) LOOP et ses clauses de contrôle (que l'on peut combiner) permettent d'écrire tout type de
boucle. La description qui en est faite ici n'est pas complète (se référer à la documentation). (LOOP [named ] {}* {}* )
- Clauses d'itération:
FOR | AS FROM TO | DOWNTO BY
IN | ON | BEING REPEAT
- Clauses de test de fin de boucle
WHILE | UNTIL | ALWAYS | NEVER | THEREIS
- Clauses d'accumulation de valeurs
COLLECT | APPEND | NCONC | SUM | COUNT | MIINIMIZE | MAXIMIZE
- Clause d'initialisation
WITH
- Clauses conditionnelles
IF | WHEN | UNLESS | ELSE | END
- Clauses inconditionnelles
DO | RETURN Exemples :
(LOOP FOR i FROM 1 TO 10 DO (PRINT i)) --> 1 2 10 NIL
(avec un nombre par ligne)
(LOOP AS i BELOW 5 DO (PRINT i)) --> 0 1 2 3 4 NIL
(avec un nombre par ligne)
(LOOP FOR item IN '(1 2 5) DO (PRINT item)) --> 1 2 5 NIL
(avec un nombre par ligne)
(LOOP WHILE (hungry-p) DO (eat))
(LOOP FOR x IN '((a) (b) (c)) APPEND x) --> (A B C)
(LOOP FOR x FROM 1 TO 5 AND y = NIL THEN x COLLECT (LIST x y))
--> ((1 NIL) (2 1) (3 2) (4 3) (5 4)) (x et y sont incrémentés en parallèle) (LOOP FOR j FROM 0 TO 10 WHILE test DO
(SETF a 4)
(LOOP (setf a (+ a 1)) (when (> a 7) (return a)) ) --> 8
III.7 - Fonctions numériques
CommonLisp possède plusieurs types de nombres: les nombres entiers à précision illimitée, les rationnels exacts et les nombres flottants. Par ailleurs, CommonLisp dispose également de fonctions pour traiter les nombres complexes, qui sont notés #C( ) (ex: #C(0 1) ).
Le résultat des fonctions de cette catégorie sont du même type que les arguments, si cela est possible.
(+ &rest )
Retourne la somme des valeurs des arguments (&rest indique ici que le nombre d'arguments de la fonction est quelconque). La fonction retourne 0 s'il n'y a pas d'argument.
(- &rest )
Cette fonction retourne la valeur de à laquelle on soustrait les valeurs des autres arguments.
(* &rest )
Retourne le produit des valeurs des arguments (valeur 1 par défaut).
(/ &rest )
Retourne le quotient de la division de la valeur de par celles des autres arguments. Si les valeurs des nombres sont entières, le quotient devra être entier, sinon le résultat sera un nombre rationnel. Si seul est présent, le résultat est égal à 1/ .
(REM ) ou (MOD )
Retourne le reste de la division de la valeur de par celle de .
Exemples :
(REM 16 7) ---> 2
(REM 21 -8) ---> 5
(1+ )
Retourne N+1, où N est la valeur de .
(INCF [])
Incrémente la valeur de de la valeur de (1 par défaut).
(1- )
Retourne N-1, où N est la valeur de .
(DECF [])
Décrémente la valeur de de la valeur de (1 par défaut)..
(ABS )
Retourne la valeur absolue de la valeur de .
Fonctions de conversion:
(COERCE )
Exemple : (COERCE 4 'float) --> 4.0
(FLOAT )
(RATIONAL )
(NUMERATOR )
(DENOMINATOR )
(FLOOR &optional ) : entier inférieur et distance à l'entier supérieur
(CEILING &optional )
(TRUNCATE &optional )
(ROUND &optional )
Ces fonctions retournent 2 valeurs (séparées par un ; et un retour à la ligne).
Exemples:
?(FLOOR 5.2) ?(CEILING 5.2) ?(TRUNCATE 5.2) ?(ROUND 5.8)
=5 ; =6 ; =5 ; =6 ;
0.8000002 -0.8000002 0.2000002 -0.19999999
Autres fonctions
(MIN &rest ) : calcul du plus petit nombre
(MAX &rest ) : calcul du plus grand nombre
(GCD &rest ) : calcul du plus grand diviseur commun
(LCM &rest ) : calcul du plus petit commun multiple
(SIN ) : fonction sinus
Autres fonctions numériques: expt(ex: 25), exp, log, sqrt, phase, sin, cos, asin, acos, atan, sinh
III.8 - Définition des fonctions
Le programmeur a souvent besoin de regrouper plusieurs instructions dépendantes de N paramètres , , et de les faire exécuter dans divers endroits du programme avec des valeurs différentes pour ces paramètres. Il est alors commode d'attribuer un nom à ce regroupement d'instructions et d'utiliser ce nom pour activer ces instructions. On dira dans ce cas qu'on a défini une fonction avec les paramètres formels . Le nom attribué sera le nom de la fonction, les instructions regroupées constitueront son corps et ses arguments au moment de son appel ses paramètres actuels ou effectifs.
L'une des manières d'arriver à cette fin en LISP est d'utiliser la fonction DEFUN (l'abréviation de DEfinir FUNction).
III.8.1 - Définition des fonctions normales
a) Principe de base
(DEFUN [{}* | {}*) [spéciale]
où :
- est un symbole, qui sera le nom de la fonction.
- est une liste (éventuellement vide) qui sera la liste des paramètres formels de lafonction. Elle est de la forme:
= ( {}*
[&optional { | ( [ []] )}*]
[&rest ]
[&key { | ( { | ( )} [ []] )}*]
)
- sont des formes ou des atomes évaluables qui constitueront le corps de la fonction.
L'appel de la fonction se fera par :
( )
Le nombre P de paramètres effectifs devra être obligatoirement égal au nombre de paramètres formels , s'il n'est pas prévu de paramètres facultatifs .
Pour évaluer cette forme, l'interpréteur procèdera de la manière suivante :
Les seront évalués et les variables définies dans prennent les valeurs correspondantes.
On remarquera que les sont évalués avant d'entrer dans le corps de la fonction. Là réside une différence essentielle entre les fonctions de type EXPR et celles de type MACRO.
Notons enfin que DEFUN est elle-même une fonction spéciale et qu'elle retourne le symbole comme valeur.
Exemples :
?(DEFUN AJOUT (ATOME LISTE)
(IF (MEMBER ATOME LISTE)
LISTE
(CONS ATOME LISTE)))
=AJOUT
?(AJOUT 2 '(1 2 3))
=(1 2 3)
?(AJOUT 4 '(1 2 3))
=(4 1 2 3)
?(AJOUT 2 (1 2 3)) =ERREUR
?(DEFUN TOC (X)
(+ X 1))
=TOC
?(SETF X 4) =4
?(TOC 2) ;X prend 2 pour valeur.
=3
?X ;X a repris son ancienne valeur.
=4
?(SETF X 4)
=4
?(TOC (SETF X 2)) ;La sauvegarde de la valeur X se
=3 ;fait après l'évaluation des arguments
?X ;X garde la valeur affectée au moment de l'appel de TOC.
=2
La syntaxe utilisée ci-dessus nous permet de définir des fonctions ayant un nombre fixe de variables. En changeant légèrement cette syntaxe, nous pouvons définir des fonctions ayant un nombre quelconque (non fixé à l'avance) d'arguments.
b) Fonctions ayant un nombre non fixé d'arguments
* (DEFUN (&rest ) )
Lors de l'évaluation de la forme ( ), tout se passe comme avant sauf que prend comme valeur la liste des valeurs des .
Exemple :
?(DEFUN FIRST (&rest X)
(CAR X))
=FIRST
?(FIRST 'A 'B 'C) ?(FIRST (CDR '(A B C)) ?(FIRST)
=A =(B C) =NIL
* (DEFUN )
Avec de la forme (x1 x2 xL &rest xL+1).
Dans ce cas, l'appel de la fonction pourra se faire avec un nombre d'arguments supérieur ou égal à L. Les L premiers arguments seront liés normalement aux L premiers paramètres et le dernier paramètre prendra pour valeur la liste formée des arguments restants.
Exemple :
?(DEFUN TEST (X Y &rest Z)
(LIST X Y Z))
=TEST
?(TEST (1+ 1) (1+ 2) (1+ 3) (1+ 4))
=(2 3 (4 5))
c) Fonctions ayant des paramètres optionnels
- Utilisation du mot-clé &optional dans la définition de la fonction.
Exemples:
(DEFUN bar (a &optional (b 2)) (+ a (* b 3)))
(bar 4 5 ) ---> 19
(bar 4) ---> 10
(DEFUN foo (&optional (a 2 b) (c 3 d)) (list a b c d) )
Les paramètres b et d permettent de savoir comment ont été obtenues les valeurs de a et c.
(foo) ---> (2 NIL 3 NIL) ; NIL indique que la valeur est celle par défaut
(foo 6 4) ---> (6 T 4 T) ; T indique une valeur donnée par un argument
(DEFUN foo (a b &optional (c 4 d)) (list a b c d))
(foo 1 2) ---> (1 2 4 NIL)
(foo 1) ---> ERREUR "pas assez d'arguments"
(foo 1 2 3) ---> (1 2 3 T)
- Utilisation du mot-clé &key dans la définition de la fonction. Ceci permet de fournir des arguments optionnels dans l'ordre souhaité en précisant le mot-clé qui les désigne.
Exemples:
(DEFUN foo1 (a b &key c d) (list a b c d))
(foo1 1 2) ---> (1 2 NIL NIL)
(foo1 1 2 :d 8 :c 6) ---> (1 2 6 8) (foo1 1 2 :d 8) ---> (1 2 NIL 8)
d) Fonctions retournant plusieurs valeurs
En CommonLisp, il est possible qu'une fonction retourne plusieurs valeurs qu'il sera possible de récupérer à l'aide de la fonction MULTIPLE-VALUE-BIND. La fonction doit contenir l'évaluation d'une forme VALUES regroupant les valeurs à retourner.
(VALUES &rest )
(MULTIPLE-VALUE-BIND ( {var}*) )
où () indique la liste des variables qui recevront les valeurs multiples (ou non) retournées
par l'évaluation de ; permet de préciser sous quelle forme on veut recupérer le ou les résultats de cette évaluation.
Exemple:
(DEFUN polar (x y)
(VALUES (SQRT (+ (* x x) (* y y))) (atan y x)))
?(MULTIPLE-VALUE-BIND (r theta)
(polar 3.0 4.0)
(list r theta)) =(5.0 0.9272952)
III.8.2 - Définition de fonctions anonymes
Dans certains cas, il n'est pas nécessaire de donner un nom à une fonction. Lisp permet de décrire des fonctions anonymes: elles sont nommées Lambda expressions à cause de leur origine liée au Lambda calcul de Church.
(LAMBDA [{}* | ] {}*)
Définit une fonction anonyme dont la liste des paramètres formels est et le corps .
Exemple :
?((LAMBDA (X Y) (* X Y)) 2 3)
= 6
D'autres exemples d'utilisation des fonctions anonymes seront donnés lors de l'étude des fonctions d'application APPLY, FUNCALL et MAPCAR.
III.8.3 - Déclaration de variables globales
Les variables utilisées dans les fonctions sont locales et la liaison entre paramètres formels et paramètres réels à l'"entrée" dans une fonction est lexicale, c'est-à-dire fixée à la définition de la fonction. Cela concerne surtout les variables utilisées dans une fonction et n'apparaissant pas dans la liste des paramètres formels. Il est cependant possible de définir des variables globales qui sont dynamiques.
Attention: la valeur d'une telle variable n'est pas réinitialisée en cas de redéclaration, par exemple lorsque l'on recharge le fichier.
(DEFVAR [ []] ) Exemple:
(DEFVAR *TABLE-X* 0)
Exemple illustrant la différence de comportement entre une variable à liaison lexicale et une variable à liaison dynamique:
? (defvar a 5) ; liaison dynamique
? (setf b 30) ; liaison lexicale
? (defun f1 () (print (list a b))) ; a et b ne sont pas définis en tant que paramètres formels
; affichage d'un message signalant que b n'est pas déclarée
? (defun f2 (a) (f1)) ; (f2 10) renvoie (10 30) car a est liée avec la valeur de ; "a" en tant que variable locale à f2.
? (defun f3 (b) (f1)) ; (f3 10) renvoie (5 30) car b est liée à la valeur de "b" en ; tant que variable de l'environnement de définition de f1.
? (let ((a 15)) (f1)) ; renvoie (15 30)
? (let ((a 15) (b 2)) (f1)) ; renvoie (15 30). b reste une variable locale au let.
III.8.4 - Fonctions avec état local
Il est possible d'associer à une fonction ou à plusieurs fonctions un environnement qui sera mémorisé d'un appel à l'autre de l'une de ces fonctions. Cette fonctionnalité est réalisée à l'aide de la fonction "let". Voir la définition de la fonction "let" dans le §III.11.
Exemples:
? (let (x (y 1))
(defun sql (z) (setq x y) (setq y z) (*x x)))
? (sql 2) = 1
? (sql 3)
= 4
? (sql 1)
= 9
? (sql 1) = 1
? (let ((x 0))
(setq compteur #'(lambda () (setq x (1+ x)))))
? (funcall compteur)
= 1
? (funcall compteur)
= 2
III.9 - Fonctions d'entrée-sortie
III.9.1 - Les fonctions d'entrée de base
Toutes les lectures sont réalisées dans le flux d'entrée qui est associé soit au terminal, soit à un fichier sélectionné par la fonction INCHAN.
a) (READ &optional )
Lit une S-expression (atome ou liste) et la retourne en valeur sans l'évaluer. Si le flux d'entrée est le terminal, valeur par défaut, cette fonction attend une entrée au clavier.
Dans le cas d'une lecture dans un fichier, permet de préciser si l'on souhaite déclencher une erreur en fin de fichier (NIL si non, T si oui) et indique la valeur retournée en cas de détection de fin de fichier (par exemple on peut choisir la valeur de retour 'eof).
Exemple :
?(SETF X (READ)) | |
?(+ 1 2) | ;Réponse de l'utilisateur (le caractère d'invite, ici "?" dépend ; de l'implémentation. |
=(+ 1 2) ?X =(+ 1 2) | ;Valeur retournée. |
b) (READ-CHAR &optional )
Lit un caractère sur le flux d'entrée et retourne un objet "caractère". La fonction de sortie correspondante est WRITE-CHAR.
Exemple :
?(READ-CHAR)
3
=#\3
c) (READ-LINE &optional )
Lit la ligne suivante sur le flux d'entrée et retourne une chaîne des caractères de cette ligne. La fonction de sortie correspondante est WRITE-LINE.
Exemple :
?(READ-LINE)ABC DE ?(READ-LINE)
="ABC DE" AB CD 34 ="AB CD 34"
d) (READ-FROM-STRING &optional &key :start :end
:preserve-whitespace)
Cette fonction retourne deux valeurs : l'objet lu et le numéro du premier caractère qui n'est pas lu. Les mots-clés :start et :end permettent de délimiter la portion de la chaîne que l'on veut traiter.
Cette fonction permet en particulier de créer des symboles à partir d'une chaîne de caractères.
Exemples :
? (set (read-from-string "titi") 3)
= 3
? titi
= 3
? (setq a (read-from-string "x1")
= X1
? (set a 5)
= 5
? x1
= 5
? (setq i 1)
= 1
? (set (read-from-string (format nil "R~a" i)) 7)
= 7
? R1
= 7
III.9.2 - Les fonctions de sortie de base
Il existe une fonction très générale WRITE permettant de nombreuses options; ici seules sont fournis quelques fonctions simples de sortie.
a) (PRINT &optional )
Edite les valeurs de , effectue un saut de ligne et retourne la valeur de .
Exemple :
?(PRINT "il fait beau")
"il fait beau"
"il fait beau"
b) (PRIN1 &optional ) Idem PRINT sans saut de ligne.
c) (PRINC &optional )
Idem PRIN1, mais les chaînes de caractères sont affichées sans guillements.
d) (TERPRI &optional ) Ethymologie : TERminer PRInt.
Effectue un saut de ligne et Vide le tampon de sortie,.
e) (FORMAT &rest )
Cette fonction permet d'envoyer dans le flux de sortie les caractères correspondants aux arguments dans le but de les afficher ou de les stocker dans un fichier. La chîne de contrôle précise le format d'impression.
Si = NIL, une chaîne est créée.
Si = T , les données sont envoyées sur le flux de sortie standard.
Si correspond à un fichier ouvert, les données sont envoyés vers ce flux.
En standard on peut utiliser le format ~a pour afficher toute valeur.
Liste des formats: ~d pour les décimaux; ~e et ~f pour les flottants; ~s pour les s-expressions; ~a pour les ascii; ~c pour les caractères; ~r pour les radix.
Exemples:
(SETF X 5 Y 7)
(FORMAT t "x= ~a ; y= ~a" x y) ---> x= 5 ; y= 7
(FORMAT nil "x= ~a ; y= ~a" x y) ---> "x= 5 ; y= 7" Remarque: ~& et ~% font sauter une ligne.
III.9.3 - Les fonctions sur les flux d'entrée/sortie
CommonLisp gère, en tant que flux d'entrée-sortie, le terminal et un certain nombre de fichiers en entrée ou en sortie.
a) (WITH-OPEN-FILE ( :direction :input|:output|:io) {}*)
Cette fonction permet d'ouvrir un fichier en lecture ou en écriture , et d'évaluer les formes dans ce contexte.
Exemples:
Lecture d'un fichier texte contenant une seule liste: lecture globale par un READ:
(WITH-OPEN-FILE (fic-animaux "" :direction :input)
(setf liste (read fic-animaux)))
Lecture d'un fichier texte contenant des données à lire en plusieurs fois:
(WITH-OPEN-FILE (fic-regles "" :direction :input)
(let ((regle (read fic-regles nil 'eof)))
(loop until (eq regle 'eof ) do
(setf regle (read fic-regles nil 'eof))))
b) (LOAD )
Permet de charger (en évaluant toutes les expressions qui s'y trouvent) le fichier lisp de nom , par exemple (load "") ou (load 'tp1). L'extension standard d'un fichier Lisp est ".lsp".
III.9.4 - Les fonctions d'accès aux commandes système
(SHELL ) envoie au système d'exploitation hôte la ligne de commande .
(CD ) permet de changer de répertoire courant.
(EXECUTE ) exécute des programmes autres que les commandes systèmes.
(EXIT) sort de Commonlisp.
III.9.5 - Les fonctions de compilation
a) (COMPILE &optional )
Cette fonction permet de compiler une fonction définie par DEFUN ou une fonction anonyme.
Exemples:
?(defun foo )
?(compile 'foo) ; maintenant "foo" s'exécute plus vite
? (setf f (compile nil '(lambda (a b c) (- (* b b) (* 4 a c)))))
#
? f
#
? (funcall f 2 4 5)
-24
b) (COMPILE-FILE &key :output-file :verbose :print)
Cette fonction permet de compiler un fichier de fonctions Lisp et de mettre le résultat dans le fichier dont le nom est précisé après le mot clé :output-file.
III.10 - Fonctions d'ordre supérieur
Ce sont des fonctions qui prennent en entrée une ou plusieurs fonctions.
a) (APPLY )
a pour valeur un symbole fonctionnel ou une lambda-expression, a pour valeur une liste dont les éléments serviront d'arguments réels à la valeur de . APPLY applique la valeur de aux éléments de et retourne le résultat de cette application.
Exemples :
?(APPLY 'CONS '(a (b c)))
=(A B C)
?(APPLY 'LIST '(U (V W) X))
=(U (V W) X)
?(APPLY #'(LAMBDA (X) (+ X X)) '(3)) ; #' est équivalent à (function )
=6
La fonction APPLY ne s'applique pas sur les formes spéciales:
?(APPLY 'SETQ '(X a Y b Z c))
=ERREUR
La fonction APPLY permet la construction des fonctions récursives dont le paramètre formel est une S-expression quelconque. Le lecteur est invité à examiner de près la liaison des paramètres dans les exemples suivants :
?(DEFUN DER (&rest X) ; dernier élément de X
(IF (NULL (CDR X))
(CAR X)
(DER (CDR X))))
=DER
?(DER 1 2 3)
=(2 3) ; pourquoi ?
?(DER 'a 'b 'c 'd)
=(b c d)
Par contre :
?(DEFUN DER (&rest X) (IF (NULL (CDR X))
(CAR X)
(APPLY 'DER (CDR X))))
=DER
?(DER 1 2 3) =3
?(DER 'a 'b 'c 'd)
=d
De même :
?(DEFUN DER (X &rest Y)
(IF (NULL Y)
X
(APPLY 'DER Y))) ; ici la fonction donne le résultat escompté
b) (FUNCALL ) Cette fonction est équivalente à :
(APPLY (LIST )) et peut être définie par :
(DEFUN FUNCALL (&rest L) (APPLY (CAR L) (CDR L)))
Exemples:
?(FUNCALL 'CAR '(a b c))
=A
?(FUNCALL 'LIST 'u 'y 'w)
=(U Y W)
?(FUNCALL #'(LAMBDA (X Y) (SUBST '+ X Y)) 'a '((b a) a)) =((B +) +)
?(SETQ F 'LIST) =LIST
?(FUNCALL F 'a 'b 'c 'd)
=(A B C D)
La fonction FUNCALL peut être utilisée pour définir les fonctions d'ordre supérieur. Soit par exemple, à définir une fonction PREMIER, prenant en argument un prédicat PRED et une liste LISTE=(X1 XN) et retournant la première valeur PRED(Xi) qui est différente de NIL.
?(DEFUN PREMIER (PRED LISTE)
(COND
((NULL LISTE) NIL)
((FUNCALL PRED (CAR LISTE)) (CAR LISTE))
(T (PREMIER PRED (CDR LISTE)))))
=PREMIER
?(PREMIER 'NUMBERP '(c (a b) 12 3 d))
=12
?(PREMIER #'(LAMBDA(X) (> X 0)) '(-1 -5 0 2 6 -8))
=2
c) (MAPCAR )
a pour valeur un symbole fonctionnel ou une lambda-expression à N arguments (autant que de
MAPCAR retourne la liste des valeurs des applications successives.
Exemples :
?(MAPCAR 'CAR '((a b)(c d e)(d e))) =(a c d)
?(MAPCAR 'CONS '(1 2 3) '(2 3))
=((1 . 2) (2 . 3))
?(MAPCAR 'LIST '(a (b c) d) '((b b) c (a d)) '(1 4 5 6)) =((A (B B) 1) ((B C) C 4) (D (A D) 5))
?(MAPCAR 'MAPCAR '(CAR CADR CADDR)
'(((a b c)) ((b c d)) ((d e f))))
=((A)(C)(F))
On observera les mêmes limitations que dans le cas de APPLY dans l'application d'une fonction spéciale
?(MAPCAR 'SETQ '(X Y Z) '('a 'b 'c))
=ERREUR
Par contre :
?(MAPCAR 'SET '(X Y Z) '(a b c))
=(A B C)
?X ?Y ?Z
=A =B =C
L'utilisation de MAPCAR et APPLY permet d'écrire des fonctions dans un style fonctionnel concis:
?(DEFUN PRODUIT-SCALAIRE (VEC1 VEC2)
(APPLY '+ (MAPCAR '* VEC1 VEC2))
?(DEFUN DIAGONALE (MAT) ;MAT=((a11 a1n) (an1 ann)) (IF MAT
(CONS (CAAR MAT) ;Ajouter a11 (le premier ;élément de MAT)
(DIAGONALE ;à la diagonale de la matrice (MAPCAR 'CDR (CDR MAT))
)))) ;carrée obtenue en enlevant la
;première ligne et la première
;colonne de MAT
d) (MAPC )
Procède de la même manière que MAPCAR sauf qu'elle retourne toujours NIL (alors que la version actuelle sur IBM retourne ).
Exemple :
?(MAPC 'PRIN1 '(1 2 3))
123=NIL
e) (MAPCAN )
MAPCAN est identique fonctionnellement à MAPC. Cependant, chaque application doit retourner une liste en valeur et MAPCAN retourne la liste des valeurs des applications qui sont rassemblées au moyen d'un NCONC. Si une valeur n'est pas une liste, elle est ignorée.
Exemples :
?(MAPCAN #'(LAMBDA (X Y) (LIST (1+ X) (1- Y)))
'(1 2 3) '(1 2 3))
=(2 0 3 1 4 2)
?(MAPCAN #'(LAMBDA (X) (IF (> X 5) (LIST X) X)) '(3 4 5 6 7 5)) =(6 7)
III.11 - Fonctions manipulant l'environnement
Ces fonctions vont permettre de changer l'environnement de façon temporaire. Le terme environnement est pris ici comme l'ensemble des liaisons variable-valeur.
a) (LET ) [spéciale]
est une liste de liaisons de la forme (( ) (
La fonction LET va lier dynamiquement et en parallèle toutes les variables aux valeurs puis lancer l'évaluation des formes . Elle permet d'effectuer des calculs dans un environnement local. sont des variables locales.
b) (LET* ) [spéciale]
Cette fonction est identique à la fonction LET, mais les variables sont liées séquentiellement aux valeurs . Ceci permet de faire apparaitre les variables déjà liées dans les valeurs .
Exemple:
(DEFUN F (a b)
(LET* ((x (+ a b)) (y (* x 2))) ) )
c) (LABELS ( { (
[[{}* | ]] {}*) }* ) [spéciale]
Permet de créer des fonctions temporaires nommée.
Les fonctions définies par DEFUN sont dites statiques. Cela signifie qu'une fois définies, ces fonctions font partie de l'interprète jusqu'à la réinitialisation de celui-ci ou leur destruction provoquée explicitement par l'utilisateur. Nous savons par contre, que les fonctions définies par LET et LAMBDA ont une durée de vie moins longue: leur existence prend fin après l'évaluation de la forme définie par LET ou LAMBDA. Nous disons que ces fonctions sont définies de manière dynamique. Il s'agit maintenant de pousser l'étude de ce genre de fonctions plus loin, et de nous donner les moyens de définir des fonctions locales tout à fait générales, pouvant être appelées récursivement.
LABELS fonctionne comme LET. La seule différence est que l'on peut définir plusieurs fonctions locales qui pourront s'appeler récursivement.
Exemples :
?(DEFUN integer-power (n k) ; calcul de n puissance k (LABELS ((expt0 (x k a)
(COND ((ZEROP k) a)
((EVENP k) (expt1 (* x x) (FLOOR k 2) a))
(T (expt0 (* x x) (FLOOR k 2) (* x a))))) (expt1 (x k a)
(COND ((EVENP k) (expt1 (* x x) (FLOOR k 2) a))
(T (expt0 (* x x) (FLOOR k 2) (* x a)))))) (expt0 n k 1)))
La fonction INTER définie ci-dessous retourne les éléments communs à deux listes L1 et L2.
(DEFUN INTER (L1 L2) (COND
((NULL L2) NIL) ((NULL L1) NIL)
((MEMBER (CAR L1) L2)
(CONS (CAR L1) (INTER (CDR L1) L2))) (T (INTER (CDR L1) L2))))
Il faut éviter de faire le test (NULL L2) dans le corps de la fonction récursive. En effet, d'un appel à l'autre, INTER laisse L2 invariant mais réduit la taille de L1 et amorce l'étape de retour une fois L1 épuisé. Voici une autre version de INTER prenant mieux en compte ces particularités:
(DEFUN INTER (L1 L2) (IF L2
(LABELS ((INTAUX (L) (COND
((NULL L) NIL)
((MEMBER (CAR L) L2)
(CONS (CAR L) (INTAUX (CDR L))))
(T (INTAUX (CDR L)))))
(INTAUX L1)) ))
?(inter '(a b c) '(e f b a)) =(A B)
IV - LA STRUCTURE INTERNE DE LISP
Les objets LISP sont trop complexes pour pouvoir être rangés dans un seul mot mémoire. Ils sont en général représentés par un pointeur. La création des doublets de liste et des autres objets Lisp se fait le plus souvent dynamiquement. Un dispositif général appelé GARBAGE-COLLECTOR récupère automatiquement les doublets et objets inutilisés .
IV.1 - Pointeurs et doublets
On appelle doublet (ou cons) un ensemble de deux pointeurs. Nous le représenterons par un diagramme en "boîtes et flèches":
Une liste peut être considérée comme un ensemble ordonné de deux éléments, le premier s'appelant le CAR et le second le CDR de la liste. On représente donc une liste par un doublet dont la première partie pointe vers le CAR et la seconde vers le CDR de la liste.
Exemples :
a) Représentation en mémoire de la liste (LISP LANGAGE FONCTIONNEL).
b) Représentation de la liste (A (B A) B) par un diagramme en boîtes et flèches.
Notons enfin, qu'on représente quelquefois les listes par des "paires pointées". La paire pointée (A . B) représente une liste dont le CAR est A et le CDR est B.
Exemple :
En notation pointée, la liste (A (B A) B) serait représentée par:
(A . ((B . (A . NIL)) . (B . NIL)))
On peut représenter (et manipuler) de cette manière une liste dont le CDR est un atome et qui n'est pas représentable par la notation habituelle.
IV.2 - Symboles atomiques
Nous savons déjà que les symboles sont utilisés comme identificateurs pour désigner des variables et des fonctions. D'ailleurs, le même symbole peut désigner à la fois une variable et une fonction; suivant la manière dont il est appelé, il remplira tel ou tel rôle. Un symbole est créé implicitement dès sa lecture dans le flux d'entrée ou explicitement par certaines fonctions telles que
MAKE-SYMBOL, GENSYM, etc.
Un symbole atomique est donc un sujet composé. En fait, c'est un pointeur sur une zone mémoire divisée en plusieurs parties. Nous aurons accès à des parties différentes suivant la manière dont nous utilisons le symbole. Nous dirons que chaque partie correspond à une propriété du symbole.
Voici quelques unes de ces propriétés que nous avons manipulées jusqu'ici :
Symbol-Value
Contient la valeur associée au symbole, considéré comme une variable. Les fonctions SET et SETQ sont utilisées pour affecter une valeur au symbole, et ainsi modifier le contenu de la SymbolValue du symbole. On peut également utiliser la fonction SYMBOL-VALUE.
Exemple: (SYMBOL-VALUE 'INTER) retourne la valeur de INTER , ou un message d'erreur si INTER n'a pas de valeur.
Symbol-Function
Contient la valeur associée au symbole considéré comme une fonction. Cette valeur peut être une adresse machine ou une S-expression si la fonction n'est pas encore compilée. L'accès à cette propriété se fait par la fonction SYMBOL-FUNCTION.
Exemple: (SYMBOL-FUNCTION 'INTER) --> le texte correspondant à la fonction
Symbol-Name (print-name)
Contient l'adresse de la chaîne de caractères représentant le nom du symbole. La fonction SYMBOL-NAME retourne cette chaîne.
Exemple: (SYMBOL-NAME 'INTER) --> "INTER"
Symbol-Plist (properties-list)
Voir les fonctions agissant sur cette propriété dans le chapitre VI.
Symbol-Package
On distingue deux types de symboles : les symboles internes et les symboles non internes. Un symbole interne est indexé par son nom dans un catalogue appelé "package", alors qu'un symbole non interne n'appartient à aucun catalogue particulier et est imprimé comme #: suivi du print-name. Par défaut, le nom du package courant est dans la variable Common-Lisp-User.
Notation des packages: SYSTEM::DEFINITION est le symbole DEFINITION du package SYSTEM.
Exemple :
(SETQ FOO 250)
(DEFUN FOO (X) (IF (ATOM X) X (CAR X))) En mémoire, on aura la configuration suivante :
Pointeur symbole --> Symbol-Value --> 250 Symbol-Function --> # "FOO"
Symbol-Plist --> (SYSTEM::DEFINITON (DEFUN FOO))
Symbol-Package --> #
Certains symboles sont déjà connus à l'appel du système:
- les constantes symboliques (qui contiennent leur propre valeur en valeur) : T, NIL,
- les fonctions prédéfinies,
- les variables système; ex: *standard-input* qui contient le nom du flux d'entrée standard desdonnées.
A chaque symbole peut être associée une documentation sous forme d'une chaîne de caractères. Cette documentation, qui est fournie au moment de la définition d'un symbole est rendue disponible en ligne par la fonction DOCUMENTATION.
(DOCUMENTATION )
sert à préciser la nature de l'objet dont on veut la documentation.
- variable correspond aux constructions "defvar", "defparameter" et "defconstant"
- function correspond à "defun" et "defmacro"
- structure correspond à "defstruct"
- type correspond à "deftype" et "defclass"
- setf correspond à "defsetf"
IV.3 - La boucle du top-level
Normalement, on interagit avec Lisp au moyen d'une boucle top-level "read-eval-print". Cette boucle est ainsi nommée car elle se situe au plus haut niveau de contrôle et elle consiste en une boucle sans fin qui lit une expression, l'évalue et affiche le résultat. On ne modifie l'état du système Lisp qu'en invoquant des actions provoquant des effets de bord.
Chaque implémentation de CommonLisp peut présenter des différences entre les interfaces utilisateur: caractère d'invite, présentation du résultat et des résultats multiples, éditeur de ligne, etc.
V - LES FONCTIONS DE MODIFICATION PHYSIQUE
Toutes les fonctions décrites dans cette section doivent être utilisées avec précaution pour éviter de placer le système dans un état de confusion, car elles permettent de modifier physiquement les structures LISP. En particulier il faut prendre garde à la modification physique des listes partagées, c'est-à-dire des listes auxquelles on peut accéder par plusieurs "pointeurs".
Toutefois la possibilité d'une véritable "chirurgie" sur les représentations internes des listes confèrent à LISP la puissance des langages machines.
a) (RPLACA ) (Etymologie : REPLAce CAr)
Remplace physiquement le CAR de la valeur de son premier argument (qui doit donc être une liste) par la valeur de son second argument et retourne la liste ainsi modifiée.
Exemple :
?(SETQ L '(A (B C) D))
=(A (B C) D)
?(RPLACA L (CADR L))
=((B C) (B C) D)
?L
=((B C) (B C) D)
Attention à la modification des listes partagées Exemples (suite):
?(RPLACA (CADR L) 'U)
=(U C)
?L
=((U C) (U C) D)
?(SETQ L '(A B C) LL L)
=(A B C)
?(RPLACA L 'D)
=(D B C)
?L
=(D B C)
?LL
=(D B C)
b) (RPLACD ) (Etymologie : REPLAce CDr)
Remplace physiquement le CDR de la valeur de son premier argument (qui doit donc être obligatoirement une liste) par la valeur de son second argument et retourne la liste ainsi modifiée.
Exemple :
?(SETQ L '(A B C) LL '(X Y Z))
=(X Y Z)
?(RPLACD L LL)
=(A X Y Z)
?L
=(A X Y Z)
Les mêmes précautions que celles prises pour RPLACA doivent être observées dans la modification par RPLACD des listes partagées.
c) (SETF ) [spéciale]
Cette fonction que nous avons vue au §III.1 permet également de faire ces modifications physiques.
Exemples:
?(SETF L '(A B C) LL '(X Y Z))
=(X Y Z)
?(SETF (CAR L) '4 (CDR LL) '(5 6))
=(5 6)
?L
(4 B C)
?LL
(X 5 6)
d) (NCONC &rest
NCONC retourne la liste ainsi modifiée.
Exemple :
?(SETF L1 '(A (B)) L2 '((C D)) L3 '(E F))
=(E F)
?(NCONC L1 L2 L3)
=(A (B) (C D) E F)
?L1
=(A (B) (C D) E F)
?L2
=((C D) E F)
?L3
=(E F)
Si L a pour valeur une liste , (NCONC L L) retourne une liste circulaire en faisant pointer le dernier CDR de vers .
Exemple :
?(SETF L '(A B C)
=(A B C)
?(NCONC L L)
=(A B C A B C A B C ;Faire CTRL/C pour interrompre l'édition, puis ABORT
e) (DELETE )
Supprime toutes les occurences de dans la liste . La valeur de est modifiée physiquement. Attention au cas où la liste devient vide.
f) Exemple d'utilisation des fonctions de modification physique
La fonction INVERSE ci-dessous prend en argument une liste et retourne une copie inversée (au premier niveau) de cette liste.
(DEFUN INVERSE (L)
(COND
((NULL (CDR L)) L)
(T (APPEND (INVERSE (CDR L)) (LIST (CAR L))))))
Calculons le nombre M de doublets consommés par cette fonction lors de l'inversion d'une liste L de n éléments. APPEND consomme autant de doublets que renferme son premier argument au premier niveau (donc autant que (INVERSE (CDR L)) i.e. n-1) et LIST autant de doublets qu'il a d'arguments (donc 1). n doublets seront donc utilisés à la dernière étape et qui s'ajouteront à ceux des étapes antérieures; d'où :
M1 = 1 , Mn = n + Mn-1.
Ce qui donne Mn = n + (n-1) + (n-2) + + 1 = n(n+1) / 2.
Une grande partie de ces doublets est consommée inutilement. La version ci-dessous de la fonction inverse est plus économique :
(DEFUN REVERSE (LISTE RES)
(COND
((NULL LISTE) RES)
(T (REVERSE (CDR LISTE) (CONS (CAR LISTE) RES)))))
Ici RES est une variable tampon qui doit prendre comme valeur NIL lors de l'appel de la fonction.
?(REVERSE '((A B) C D) ())
=(D C (A B))
La fonction REVERSE inverse une liste de n éléments en n étapes et à chaque étape elle utilise un seul doublet (par application de CONS). Le nombre total de doublets utilisés est donc n.
Il n'est pas difficile de se convaincre que si on désire garder la liste de départ intacte, la fonction REVERSE utilise le minimum possible de doublets.
La version ci-dessous de la fonction INVERSE n'utilise aucun doublet! Mais la liste de départ est perdue : ses doublets sont recyclés dans la construction de sa copie inversée.
(DEFUN NREVERSE (LISTE RES)
(COND
((NULL LISTE) RES)
(T (NREVERSE (CDR LISTE) (RPLACD LISTE RES)))))
f) Comment éviter les problèmes liés au partage des listes
Lorsque une liste est partagée et que l'on souhaite faire des modifications physiques sur cette liste pour des raisons d'efficacité, il faut la dupliquer au préalable et travailler sur cette copie.
Cependant, tous les problèmes ne sont pas résolus. En particulier les fonctions ci-dessous ne peuvent traiter les listes circulaires.
(COPY-LIST )
Retourne une copie de la liste au premier niveau.
(COPY-ALIST )
Retourne une copie de la aliste .
(COPY-TREE )
Retourne une copie de à tous les niveaux. Cette fonction copie n'importe quel type d'objet LISP.
VI - LES LISTES D'ASSOCIATIONS ET LES LISTES DE PROPRIETES
VI.1 - Introduction
Dans un tableau on accède à un élément par son rang. Dans une liste, les fonctions d'accès sont réalisées par une composition de CAR et de CDR. Dans une structure composée, on repère les composants par les noms des champs, ces noms étant figés lors de la déclaration de la structure.
Il est quelquefois intéressant de disposer d'une structure de données où l'accès à une composante se fait par un nom (ou clef) calculé ou lu. Par exemple, si l'on veut compter le nombre d'occurences des mots d'un texte, il sera commode de mémoriser ces nombres dans une structure où l'on peut avoir accès directement au mot dont on veut stocker le nombre d'occurences.
Une telle structure s'appelle table ou structure associative. Chaque élément de la structure est repéré par une clef (ou indicateur) à laquelle est associée une valeur.
Pour rendre aisée l'utilisation de cette structure de données, les fonctions suivantes devront être définies:
a) Une fonction CREE qui initialise une structure associative à partir d'une liste d'indicateurs et
d'une liste de valeurs.
b) Une fonction ACCES1 qui, pour un indicateur IND, retourne la valeur associée.
c) Une fonction ACCES2 qui, pour une valeur VAL, retourne le couple (IND VAL).
d) Une fonction AJOUT qui ajoute dans la structure un couple (IND VAL) d'indicateur-valeur.
e) Une fonction MISE-A-JOUR qui, dans la structure, change la valeur d'un indicateur IND par
une nouvelle valeur NVAL.
f) Une fonction DESTRUCTION qui enlève un indicateur IND et sa valeur de la structure.
En CommonLisp, il existe 3 façons de réaliser la structure de données dont on vient de définir les fonctionnalités : les A-listes (ou listes d'association), les P-listes (ou listes de propriétés) et les tables hachées. Leurs représentations internes sont totalement différentes et les fonctions disponibles sur ces structures présentent des particularités et des restrictions par rapport aux définitions ci-dessus.
VI.2 - Les A-Listes (ou listes d'association)
En Lisp, les A-listes sont des listes qui possèdent la structure suivante:
( (clef1 . val1) (clef2 . val2) (clefN . valN) )
Tous les éléments de cette liste particulière doivent être des listes; le CAR de ces listes est la clef, et le CDR est la valeur. Le point placé entre la clef et la valeur n'apparait que si la valeur n'est pas une liste. La clef peut être soit un atome (symbole ou nombre), soit une S-expression quelconque; cependant les fonctions d'accès ne sont pas les mêmes dans les deux cas (prédicat EQ dans le cas d'une clef atome et prédicat EQUAL dans l'autre cas).
Les A-listes peuvent être utilisées comme les listes ordinaires, en particulier on peut les affecter à un symbole par les fonctions SET et SETQ. Dans ce cas, la A-liste sera la "Symbol-Value" du symbole.
Les principales fonctions qui permettent la manipulation des A-Listes sont les suivantes:
a) (ACONS )
Rajoute en tête un élément à la A-liste . L'élément est composé de la clef et de la valeur . Et retourne la nouvelle A-liste.
? (ACONS 'a 10 '((b . 11) (c 2 3)))
= ((a . 10) (b . 11) (c 2 3))
?(SETQ l (ACONS 'a 10 '((b . 11) (c 2 3)))
= ((a . 10) (b . 11) (c 2 3))
?l
= ((a . 10) (b . 11) (c 2 3))
b) (ASSOC &key :test :test-not :key)
Retourne le premier élément de la A-liste dont la clef est en utilisant par défaut le prédicat EQ, ou le prédicat précisé avec le mot-clé :test; s'il n'existe pas un tel élément la fonction ramène NIL.
?(ASSOC 'a '((b . 1) (a . 10)))
=(a . 10)
?(ASSOC '(a b) '((b . 1) ((a b) . 5) (a . z)))
=NIL
?(ASSOC '(a b) '((b . 1) ((a b) . 5) (a . z)) :test 'EQUAL)
= ((A B) . 5)
c) (RASSOC &key :test :test-not :key)
Retourne le premier élément de la A-liste dont la valeur est égale à .
?(RASSOC 'c '((a . b) (a . c) (b . c)))
=(A . C)
?(RASSOC '(b c) '((a . (b c))))
=NIL
?(RASSOC '(b c) '((a . (b c))) :test 'EQUAL)
=(A B C)
d) (SUBLIS )
Retourne une copie de l'expression dans laquelle toutes les occurences des clefs de la Aliste ont été remplacées par leurs valeurs associées correspondantes. La copie retournée partage le maximum de cellules avec l'expression initiale.
?(SUBLIS '((a . z) (b 2 3)) '(a (b a c) d b . b)))
=(z ((2 3) z c) d (2 3) 2 3 )
VI.3 - Les P-Listes
La structure citée ci-dessus peut également être réalisée en LISP par une P-Liste (ou liste de propriétés). Une P-Liste est une liste de la forme ( où est un indicateur de la P-Liste et la valeur dans la P-Liste de . Les sont des atomes (symboles ou nombres) et les des S-expressions. La recherche d'un indicateur dans une P-Liste utilise le prédicat EQ.
La P-Liste elle-même est "stockée" dans le champ "Symbol-Plist" d'un symbole donné. L'accès à une P-liste fera intervenir systématiquement le nom de ce symbole. Le champ "Symbol-Plist" contient à la création du symbole l'adresse de la liste vide. Une fois la P-Liste créée, il contiendra l'adresse de la liste correspondante.
Les fonctions qui permettent la manipulation des P-Listes sont les suivantes :
a) (SYMBOL-PLIST )
a pour valeur un symbole S. SYMBOL-PLIST retourne la valeur de la P-LIST de S Cette fonction est aussi utilisée pour désigner une "place" pour SETF.
?(SETF (SYMBOL-PLIST 'CAPITALES) '(FRANCE PARIS ITALIE ROME))
=(FRANCE PARIS ITALIE ROME)
?(SYMBOL-PLIST 'CAPITALES)
=(FRANCE PARIS ITALIE ROME)
?(GETF (SYMBOL-PLIST 'CAPITALES) 'FRANCE)
=PARIS
b) (GET )
Retourne la valeur dans la P-Liste de de l'indicateur . Si ce dernier n'est pas un indicateur de , GET retourne NIL.
doit avoir pour valeur un symbole.
?(GET 'CAPITALES 'FRANCE)
=PARIS
?(GET 'CAPITALES 'SUISSE)
=NIL
?(SETF (GET 'CAPITALES 'ESPAGNE) 'MADRID)
=MADRID
?(SYMBOL-PLIST 'CAPITALES)
=(ESPAGNE MADRID FRANCE PARIS ITALIE ROME)
c) (GETF )
Cette fonction est identique à GET, mais elle est plus générale car elle permet d'utiliser une pour indiquer sur quelle P-liste on veut faire la recherche.
?(GETF (SYMBOL-PLIST 'CAPITALES) 'FRANCE)
=PARIS
d) (GET-PROPERTIES )
Cette fonction est identique à GETF, mais la recherche dans la P-liste utilise la liste d'indicateurs au lieu du seul indicateur. Cette fonction retourne trois valeurs: le premier indicateur trouvé dans la P-liste, la valeur, la liste de propriétés à partir de l'indicateur.
e) (REMPROP )
Enlève de la P-Liste de l'indicateur et sa valeur (dans la P-Liste) et retourne la sousliste de l'ancienne liste des indicateurs-valeurs de la P-Liste de commençant par . ?(REMPROP 'CAPITALES 'FRANCE)
=(FRANCE LYON ITALIE ROME)
?(GET 'CAPITALES 'FRANCE)
=NIL
f) (REMF )
Idem REMPROP, mais en fournissant une pour accéder à la P-Liste.
Remarques
1) SETF, REMPROP, REMF agissent par effet de bord. On peut utiliser aussi PUSH.
2) Un indicateur ne peut avoir qu'une valeur dans une P-Liste.
3) Un symbole qui reçoit une P-Liste la garde jusqu'à sa modification explicite par l'utilisateur.Aucun mécanisme de liaison par valeur à l'entrée d'une fonction n'agit sur le champ SYMBOL-PLIST d'un symbole.
Exemple :
?(DEFUN ASS (X)
(SETF (SYMBOL-PLIST X) '(UN 1)))
=ASS
?(SYMBOL-PLIST 'ALPHA)
=NIL
?(ASS 'ALPHA)
=(UN 1)
?(SYMBOL-PLIST 'ALPHA)
=(UN 1)
g) Un exemple d'utilisation des P-listes : les mémo-fonctions
Une mémo-fonction est une fonction qui mémorise les valeurs qu'elle calcule et consulte sa mémoire avant de se lancer dans le calcul effectif d'une valeur.
Exemple : la suite de FIBONNACI.
La suite FIBO(n) est définie par:
FIBO(n) = FIBO(n-1) + FIBO(n-2).
On peut l'écrire en LISP par la fonction suivante :
(DEFUN FIBO (N) (COND
((= N 0) 0) ((= N 1) 1)
(T (+ (FIBO (1- N)) (FIBO (- N 2))))))
Rien que dans le calcul de (FIBO 5), cette fonction calcule trois fois (FIBO 2) et deux fois (FIBO 3). Alors que si les valeurs calculées étaient mémorisées, ces répétitions inutiles n'auraient pas lieu. Voici une fonction MEM-FIB qui mémorise ses résultats calculés.
(DEFUN MEM-FIB (N) (COND
((= N 0) 0) ;Retourner 0 pour 0.
((= N 1) 1) ;et 1 pour 1.
((GET 'MEM-FIB N)) ;si la valeur recherchée ;se trouve en mémoire, ;la retourner.
(T (SETF
(GET 'MEM-FIB N) ;sinon, la calculer et
(+ (MEM-FIB (1- N));la mémoriser.
(MEM-FIB (- N 2)))))) ))
VII - LES FONCTIONS DE TYPE MACRO
Un autre type de fonction reconnu par Common Lisp est le type MACRO. L'originalité des MACRO-fonctions réside principalement dans la manière dont la dernière forme présente dans le corps de ces fonctions est évaluée. Cette forme subit deux évaluations : une fois dans l'environnement local de la fonction (i.e. quand les paramètres formels et les variables locales sont encore liés à leurs valeurs) et une deuxième fois hors de l'environnement local, après l'étape de la déliaison. C'est cette deuxième valeur qui est retournée comme le résultat de l'évaluation de la MACRO-fonction. Les MACRO ne sont pas réellement des fonctions et ne peuvent pas être arguments de fonctions telles que APPLY, FUNCALL et MAP.
VII.1 - La définition des macro-fonctions
La définition des fonctions de type MACRO se fait par la fonction DEFMACRO. La syntaxe de la définition est :
(DEFMACRO ) [spéciale]
où est un symbole, est une S-expression formée de variables et , ,
sont des formes ou atomes évaluables.
La fonction DEFMACRO est "spéciale" et retourne en valeur. Après l'évaluation de la forme ci-dessus, acquiert une valeur fonctionnelle de type MACRO. L'appel se fait par la forme ( ). Les étapes ci-dessous se déroulent alors dans l'ordre.
1) et la liste ( ) sont mis en liaison
2) Macro-expansion : , , sont évalués et la valeur de mémorisée.
3) Macro-évaluation : la valeur est à nouveau évaluée et retournée.
On constate que la valeur retournée n'est pas la valeur de la dernière forme ou atome présent dans le corps de la fonction, mais la valeur d'une seconde évaluation de cette forme opérée dans l'environnement de la fonction appelante.
VII.2 - Quelques exemples
Le mécanisme de la double évaluation de la dernière forme présente dans le corps d'une MACRO-fonction change radicalement l'esprit dans lequel ces fonctions doivent être abordées. On ne cherchera pas à retourner immédiatement une valeur, mais à construire une forme qui, évaluée, retourne cette valeur. Il faudra donc avoir présente à l'esprit l'expansion de la MACRO.
Exemples :
a)
?(DEFMACRO MCAR (&rest L) ; appel par (MCAR ) ; On prépare
(CONS 'CAR L)) ; l'expansion (CAR ) =MCAR
?(MCAR '(a b c)) ; L
?(SYMBOL-FUNCTION 'MCAR)
=(SYSTEM::MACRO . #)
b) On sait que la forme (LET ((VAR1 VAL1) (VARn VALn)) s1 sp) est équivalente à ((LAMBDA (VAR1 VARn) s1 sp) VAL1 VALn). On pourra donc essayer d'écrire une MACROfonction qui transforme dans son étape d'expansion la première forme en seconde.
?(DEFMACRO MLET (LV &rest CORPS)
;LV ((VAR1 VAL1) (VARn VALn))
;CORPS (s1 sp) (CONS (CONS 'LAMBDA
(CONS (MAPCAR 'CAR LV) CORPS))
(MAPCAR 'CADR LV)) )
=MLET
?(MLET ((A 2) (B 4)) (PRINT (+ A B)) (PRINT (- A B))) 6
-2
=-2
c) L'une des raisons d'être des MACRO-fonctions est l'écriture des fonctions de contrôleconditionnnelles. Ecrivons à titre d'exemple la fonction OR en MACRO. L'appel se faisant par (OR s1 sn), l'expansion devra être:
(COND (s1)
(t (OR s2 sn)))
?(DEFMACRO MAC-OR (&rest CORPS) (IF CORPS
(LIST 'COND
(LIST (CAR CORPS))
(LIST 'T (CONS 'MAC-OR (CDR CORPS))))))
=MAC-OR
d) Dans le même ordre d'idée, voici la fonction WHILE. L'appel se fait par (WHILE s s1 sn).L'expansion sera:
(IF s (PROGN s1 sn (WHILE s s1 sn)))
?(DEFMACRO MWHILE (&rest CORPS) (LIST 'IF
(CAR CORPS)
(APPEND (CONS 'PROGN (CDR CORPS))
(LIST (CONS 'MWHILE CORPS)))) )
=MWHILE
?(SETQ A 3) =3
?(MWHILE (> A 0) (PRINT A) (SETQ A (1- A))) 3 2 1
=NIL
VII.3 - Le phénomène de capture et les macro-fonctions
Les macro-fonctions servent à construire dynamiquement (c'est-à-dire à l'aide d'un programme, à partir de données) des corps de fonctions, puis à les évaluer. Malencontreusement, il se produit parfois des erreurs dûes aux homonymies entre noms des arguments de la fonction et noms des objets que l'on veut manipuler. Nous allons voir que le mécanisme de double évaluation résoud en partie le masquage des arguments. Etudions ce phénomène sur un exemple.
La fonction UNLESS est l'une des diverses formes de la structure si-alors-sinon. (UNLESS s1 s2 sn) retourne nil si la valeur de s1 est différente de nil, sinon elle évalue dans l'ordre s2 sn et retourne la valeur de sn. On peut remarquer que UNLESS est équivalent à:
(IF (NOT s1) (PROGN s2 )) et l'écrire à l'aide d'une MACRO par:
?(DEFMACRO M-UNLESS (TEST &rest CORPS)
(LIST 'IF (LIST 'NOT TEST) (CONS 'PROGN CORPS))) =M-UNLESS
?(SETQ TEST NIL)
=NIL
?(M-UNLESS TEST 1 2 3)
=3
L'évaluation de la forme (IF (NOT TEST) (PROGN 1 2 3)) (l'expansion de la macro-fonction) ne se fait pas dans l'environnement de la fonction, mais en dehors de cet environnement, quand la variable TEST a retrouvé sa valeur initiale (i.e. NIL).
Cependant, certaines formes de masquages ou d'homonymies peuvent apparaître. Notamment quand la MACR0-expansion construit des formes où interviennent des variables locales. Voici quelques exemples que le lecteur est invité à analyser.
?(DEFMACRO EXCHANGE (VAR1 VAR2) ;échange la valeur de 2
(LET ((R ())) ;variables
(LIST 'SETQ 'R VAR1 ;appel par (EXCHANGE X1 X2)
VAR1 VAR2 ;et expansion par
;(SETQ R X1 X1 X2 X2 R)
VAR2 'R)))
=EXCHANGE
?(SETQ R 1 S 2) =2
?(EXCHANGE R S)
=2 ;expansion par (SETQ R R R S S R)
?R ?S
=2 =2
Autre exemple où une variable locale masque une variable globale:
?(DEFMACRO MOYENNE (&rest LNBR)
;calcule la moyenne de n nombres
;appel par (MOYENNE n1 nk) ;expansion par :
; (LET ((N (LENGHT '(n1 nk)))
; (/ (+ n1 nk) N)) (LIST 'LET
(LIST (LIST 'N (LIST 'LENGHT (LIST 'QUOTE LNBR)))) (LIST '/
(CONS '+ LNBR)
'N))) =MOYENNE
?(SETQ N 10) =10
?(MOYENNE N 3 5)
=11/3 ; (3+3+5) / 3
En fait, on constate que l'expansion de (MOYENNE N 3 5) donne:
(LET ((N (LENGHT '(N 3 5)))) (DIVIDE (+ N 3 5) N))
On aurait pu éviter l'emploi d'une variable locale intervenant dans l'expansion et écrire par exemple :
?(DEFMACRO MOYENNE (&rest LNBR)
(LET ((N (LENGHT LNBR))) (LIST '/
(CONS '+ LNBR)
N)))
=MOYENNE
?(MOYENNE N 3 5)
=6 ; (10+3+5)/3
De même, pour la fonction EXCHANGE :
?(DEFMACRO EXCHANGE (VAR1 VAR2)
(LIST 'SETQ VAR1 VAR2 VAR2 (LIST 'QUOTE (EVAL VAR1)))) =EXCHANGE
?(SETQ S 'A) =A
?(SETQ R 'B) =B
L'expansion de la forme d'appel (EXCHANGE S R) donne alors: (SETQ S R R 'A)
VII.4 - Les fonctions d'aide à la construction de listes complexes
Afin d'éviter les successions de CONS, LIST et APPEND dans la construction de listes et en particulier dans l'écriture des MACRO-fonctions, LISP met à notre disposition des MACROcaractères qui rendent cette construction plus aisée et plus lisible. Un MACRO-caractère est un caractère qui a une valeur fonctionnelle. A la lecture de ce caractère, la valeur retournée par la fonction associée à ce MACRO-caractère remplace le MACRO-caractère lu. Nous connaissons déjà le MACRO-caractère QUOTE. Nous allons voir les MACRO-caractères '`' (BACKQUOTE), ',' (virgule) et '@' (arrobas). Ces MACRO-caractères n'ont pas d'arguments. La transformation provoquée par leur valeur fonctionnelle s'opère sur la première S-expression qui les succède dans le flux d'entrée.
a) Utilisation du caractère "backquote":
`(x1 xp) est lu comme '(x1 xp)
b) Utilisation du caractère "virgule" associé au caractère "backquote":
Si xi1, , xip ont une valeur, à la lecture de `(x1 ,xi1 ,xip xn) les xij sont remplacés par leur valeur.
Exemples :
?(SETQ X '(a b c) Y '(1 2 3))
=(1 2 3)
?`(X ,X ,Y Y)
=(X (a b c) (1 2 3) Y)
?`((CAR ,X) ,(CDR X) (Y ,(CDR Y)))
=((CAR (a b c)) (b c) (Y (2 3)))
c) Utilisation du caractère "arrobas" associé aux caractères "backquote" et "virgule": Si X a pour
valeur une liste, dans `(.. ,@X ) ,@X est remplacé par la suite des éléments de X.
Exemples :
?(SETQ X '(a b c) Y '(1 2 3)) =(1 2 3)
?`(,X ,@Y)
=((a b c) 1 2 3)
?`(,@(CDR X) (,(CAR X) ,@Y) fin) =(b c (a 1 2 3) fin)
?`((LAMBDA ,X (APPLY 'LIST (QUOTE ,X))) ,@Y)
=((LAMBDA (a b c) (APPLY 'LIST '(a b c))) 1 2 3)
Voici quelques exemples de fonctions de type MACRO écrites à l'aide des MACRO-caractères étudiés ci dessus :
?(DEFMACRO MLET (LV &rest CORPS)
`((LAMBDA ,(MAPCAR 'CAR LV) ,@CORPS) ,@(MAPCAR 'CADR LV)))
?(DEFMACRO EXCH (VAR1 VAR2)
`(SETQ ,VAR1 ,VAR2 ,VAR2 (QUOTE ,(EVAL VAR1))))
?(DEFMACRO MAC_OR (&rest CORPS) (IF CORPS
`(COND (,(CAR CORPS))
(T (MAC_OR ,@(CDR CORPS))))))
?(DEFMACRO MSETQ (&rest CORPS)
;appel par (MSETQ X1 VAL1 Xn VALn)
;CORPS prend la valeur (X1 VAL1 Xn VALn) ;expansion par :
; (PROGN (SETQ (QUOTE X1) VAL1)
; (MSETQ X2 VAL2 Xn VALn)) (COND
((NULL CORPS) NIL) ;MSETQ retourne toujours NIL ((NULL (CDR CORPS)) 'ERREUR)
;un nombre impair d'éléments dans CORPS
(T `(PROGN (SETQ (QUOTE ,(CAR CORPS)) ,(CADR CORPS))
(MSETQ ,@(CDDR CORPS))))))
VII.5 - La mise au point des macro-fonctions
a) (MACROEXPAND-1 )
a pour valeur une forme dont le CAR est une fonction de type MACRO. MACROEXPAND-1 retourne l'expansion de cette forme. (Cette fonction ne retourne pas cette valeur sur l'IBM).
Exemples :
?(MACROEXPAND-1 '(MAC_OR (CDDR L) (CADR L) (CAR L))) =(COND ((CDDR L)) (T (MAC_OR (CADR L) (CAR L))))
?(MACROEXPAND-1 '(LET ((X '(a b c))) (PRINT (CAR X)))) =(LAMBDA (X) (PRINT (CAR X))) '(a b c))
b) (MACROEXPAND )
Permet d'expanser dans la forme qui est la valeur de tous les appels de MACRO à tous les niveaux. (Même remarque que pour MACROEXPAND-1)
VIII - LES SYMBOLES, LES CHAÎNES DE CARACTERES, LES VECTEURS, LES
SéQUENCES, LES TABLES DE HACHAGE, LES STRUCTURES
Outre les fonctions de manipulation des nombres et des listes, Common Lisp propose des fonctions de gestion des symboles, de manipulation des chaînes de caractères et des vecteurs, et de création de structures. Ne sont présentées dans ce paragraphe que les principales fonctions appartenant à ces catégories.
Notons que CommonLisp propose aussi des fonctions s'appliquant à des séquences (une séquence est une liste ou un vecteur), des tables de hachage, des "readtables" et des "streams". Pour une information sur ces fonctions, voir le livre de G.L STEELE, cité dans la bibliographie.
VIII.1 - Les fonctions de gestion des symboles
(MAKE-SYMBOL )
?(make-symbol "y")
=#:|y|
?=(make-symbol (concatenate 'string "a" "b"))) =#:|ab|
(GENSYM &optional )
retourne à chaque appel un nouveau symbole créé par concaténation de "g" ou d'un paramètre
optionnel et de la valeur de la variable système *gensym-counter*
? (gensym)
= g101
(GENTEMP &optional ) retourne un nouveau symbole dans le package .
? (gentemp (format nil "~s" (setq b 'a)))
= a0
? (gentemp)
= T1
Le compteur associé à gentemp s'incrémente de 1 à chaque appel.
Pour créer des symboles, voir aussi la fonction READ-FROM-STRING.
VIII.2 - Les fonctions de manipulation des chaînes de caractères
Une chaîne de caratères est une collection de caractères accessibles par leur index (numéro). L'index du premier caractère d'une chaîne est égal à 0. La représentation externe d'une chaîne est: "xxxxxxxxxxxxx"
Les fonctions de base sont : LENGTH, CHAR, AREF, ELT.
La fonction de conversion des chaînes est: STRING.
Les fonctions de comparaison des chaînes sont: STRING=, STRING &key :start1 :end1 :start2 :end2)
Les fonctions de création des chaînes sont: CONCATENATE, MAKE-STRING, SUBSTRING.
D'autres fonctions sont disponibles pour accéder aux caractères d'une chaîne, pour modifier physiquement une chaîne ou pour rechercher des sous-chaînes.
Exemples:
?(CHAR "Floor and" 0)
=#\F
?(LENGTH "foo")
=3
?(MAKE-STRING 3 :initial-element '#\s)
="sss"
?(CONCATENATE 'STRING "a" "bc")
="abc"
?(STRING 'A)
="A"
VIII.3 - Les fonctions de manipulation des vecteurs et des tableaux
Un vecteur est une collection d'objets Lisp accessibles par leur index ou numéro. Ces objets Lisp sont des S-expressions pouvant avoir des types différents. Les index des vecteurs débutent à la valeur 0.
La représentation externe d'un vecteur est:
#( ) et d'un tableau à 2 dimensions est:
#2A(( ) ( )) La dimension d'un tableau peut être quelconque.
(MAKE-ARRAY &key :element-type :initial-element)
fabrique un nouveau tableau de éléments. Chacun de ces éléments est initialisé à la valeur
fournie après le mot-clé :initial-element.
? (MAKE-ARRAY 5)
= #(NIL NIL NIL NIL NIL)
? (MAKE-ARRAY 5 :type-element 'fix :initial-element 0) = #(0 0 0 0 0)
?(MAKE-ARRAY '(2 2))
=#2A((NIL NIL) (NIL NIL))
(VECTOR )
fabrique un vecteur de taille N, initialisé avec les valeurs des S-expressions .
?(VECTOR 1 2 3 4)
=#(1 2 3 4)
Les principales fonctions manipulant les vecteurs sont: AREF, VECTOR-PUSH, VECTORPOP, ADJUST-ARRAY.
?(SETQ A (VECTOR 1 2 3 4))
=#(1 2 3 4)
?(AREF A 1) ; accès en lecture
=2
?(SETF (AREF A 1) 5) ; accès en écriture
=5
?A
=#(1 5 3 4)
VIII.4 - Les séquences
Le type "Séquence" recouvre les types "liste" et "vecteur". Les fonctions décrites ci-dessous sont fondées sur la propriété commune à ces deux types: ce sont des ensembles ordonnés d'éléments. Outre les fonctions déjà vues, telles que ELT, LENGTH, CONCATENATE, voici quelques fonctions utiles:
(FIND :test :key )
(SUBSEQ &optional )
(MAP &rest )
(SOME &rest )
? (some #'(lambda (x) (eql 'a x)) '(d v a c))
T
? (some #'(lambda (x) (if (eql 'a x) x)) '(d v a c))
A
? (some #'(lambda (x) (if (eql 'a (car x)) x)) '((d) (v b) (a e f) (c)))
(A E F)
(EVERY &rest )
? (every #'(lambda (x y) (equal x y)) '(a b) '(a b))
T
? (every #'(lambda (x y) (equal x y)) '(a b) '(a c))
NIL
(NOTANY &rest )
(NOTEVERY &rest )
(REMOVE &key :from-end :test :test-not :start :end :count :key) Retourne une copie de la séquence modifiée.
(DELETE &key :from-end :test :test-not :start :end :count :key) Modification physique de la séquence.
(SORT &key :key)
Modification physique de la séquence selon le prédicat de comparaison de 2 éléments
et le moyen d'accès à la donnée s'il s'agit d'une liste ou d'une structure quelconque.
? (sort '(("cc" 1) ("aa" 2) ("bb" 3)) #'string-lessp :key #'car) (("aa" 2) ("bb" 3) ("cc" 1))
(MERGE &key :key) Retourne une copie de la fusion des séquences déja triées.
VIII.5 - Les tables de hachage
CommonLisp propose des fonctions spécialisées dans la création, la modification et l'accès aux tables de hachage;
(MAKE-HASH-TABLE &key :test :size :rehash-size :rehash-threshold) crée une table de hachage, dont on peut préciser le test d'accès aux éléments, la taille, etc.
(GETHASH