Programmation fonctionnelle
On peut charger et évaluer le contenu d'un fichier avec (load <str>). .... Partie TD.
1)A partir de la liste (+ 1 2 3), écrire un appel retournant : a) + (car '(+ 1 2 3)) ....
Un arbre binaire est une structure définie sur un ensemble fini de noeuds (ou ...
part of the document
de caractères.
( ) pour les fonctions
; le reste de la ligne est en commentaire
pour la fonction quote
Liste
Cette définition dune liste est récursive : (pain vin (A B)) (Espace est un séparateur)
III/Caractèristiques.
Standardisation récente (début 90 : Common Lisp)
On dispose en standard de liste comme structure de données ET dopérations de bases sur les listes.
Les fonctions ( listes
Les données ( listes
En Lisp, il nexiste pas de programme principal ; le langage peut être compilé ou interprété.
Prog source .
Execution
immédiate du code
Création dun programme
( executable.
Détection derreurs de syntaxe
En Lisp, la valeur logique Faux est représentée par une liste vide ( )
Tout ce qui est différent de Faux est Vrai, mais il existe un symbole particulier qui vaut toujours Vrai : t.
Nil et ( ) représente le même élément, en interne, il sagit de la même adresse mémoire.
Interpreteur.
Appeler un fonction, cest écrire une liste dont le premier élément est un nom de fonction et où les éléments suivants sont des arguments (+ 1 2)
On a automatiquement évaluation du ou des arguments.
La valeur dun nombre est lui même.
Le Lisp est un langage préfixé, on commence donc par le nom de la fonction.
IV/Présentation des fonctions.
Notation : symbole
liste
atome
symbole
nombre
chaine de caractère
-Fonction évaluation
-Accès aux éléments dune liste ( Structure
-Construire des listes ( de liste
-Créer une nouvelle fonction
-Fonction de contrôle ( if .
Toute fonction retourne un résultat
1)Fonction dévaluation.
Pour utiliser une liste en tant que structure de données et non en tant quappel de fonction, on utilise la fonction quote.(quote )
La fonction quote a un seul argument quelle retourne non évalué.
Ex : quote(+ 1 2) ( + 1 2
La fonction quote se note également
2)Fonction daccès aux éléments dune liste.
(car ) : fonction avec un seul argument de type liste
Il y a automatiquement évaluation de largument ; car retourne la copie du premier élément de la liste.
Ex : (car (+ 1 2)) ( Erreur car évaluation (+ 1 2) ( 3 : nombre ( Erreur
(car (quote(+ 1 2)) ( +
(car (+ 1 2) ( +
(cdr ) retourne une copie de la liste privée du premier élément.
Il y a dabord évaluation de largument : ce dernier doit être une liste après évaluation.
Convention : (car ())
(cdr ())
Remarque : 1)Lévaluation dun nombre est un nombre
2) Lévaluation dune liste est une liste
3) Lévaluation de t vaut t
3)Fonction de construction de liste.
! Il y dabord évaluation des arguments.
(cons ) : si évaluation est une liste cons ajoute en tête le résultat de lévaluation de .
(cons a (bc)) ( (abc)
Si après évaluation est un atome cons retourne la paire pointée (s1 .s2)
Ex : (cons a b) ( a b ( (a.b)
(append
.) concatène les listes à
Ex : (append (ab) ( )
..(car( )) (cdr (ab))) ( abb
(list .....) : retourne la liste de lévaluation de ses n arguments.
Ex : (lsit (+ 1 2) 3 4 (a)) ( 3 3 4 (a) ( (3 3 4 (a))
Exo : a) (cons (a) (bc)) ( (cons ((a) (bc))) ( ((a)bc)
b) (append (a) (bc)) ( (append (a) (bc)) ( (abc)
c) (list (a) (bc)) ( (list (a) (bc)) ( ((a)(bc)).
4)Les prédicats .
Les prédicats retournent t ou nil
5)Fonction de définition de fonction.
(defun
)
: nom de la nouvelle fonction
: liste des arguments de la fonction
: constituent le corps de la fonction ; à lappel de la fonction, on évalue en séquence ,.., . La fonction va retourner lévaluation de .
Ex : (defun carre(n) (* n n))
( (carre(2)) ( 4
(defun ajout (a b) (+ a b))
( (ajout carre(2) (+ 1 3)) ( 8
(defun essai() (ajout 1 2)) ( (essai) ( 3
6)Fonction de contrôle.
(cond ( )
( )) : nombre quelconque de listes.Le premier élément de la série de listes vaut t ou nil après évaluation.
Lorganisation de chaque liste est la suivante :
Le premier élément de la liste est évalué (le résultat est évalué de manière booléenne).
Cond sélectionne la première des listes dont lévaluation du premier élément est différente de nil. Cond évalue alors les différentes expressions de cette liste et retourne lévaluation de la dernière.
Ex : (defun essai(s))
(cond ((null s) 1)
Si test1 est Vrai alors renvoie1 Sinon
((atom s) 2)
Si test2 est Vrai alors renvoie 2 Sinon
(t 3)))
Si test3 est Vrai alors renvoie 3
7)Fonction daffichage.
(printf ) : affiche lévaluation de lexpression et retourne cette évaluation.
(print (+ 1 2)) ( 3
Pour afficher plusieurs expression avec du texte :
(print (list « mes1 » (+ 1 2)))
Pour un affichage plus élaboré :
(format [
]
Largument détermine le flux de sortie
Un fichier
Fabriquer une chaîne de caractères : nil
Affichage : t
Le deuxième argument est str caractère qui peut contenir des directives :
~% : saut de ligne
~A : remplacé par une variable.
(format nil « mes ~A » (+ 1 2)) ( « mes 3 »
(format t « mes ~A » (+ 1 2))
( mes 3 affichage
( nil ( valeur de retour
8)Fonctions auxiliaires.
Lunique fonction qui ne retourne pas de résultat est la fonction : (exit()) qui quitte linterpréteur .Cest un exemple de fonction sans argument.
On peut charger et évaluer le contenu dun fichier avec (load ).
Largument est le nom du fichier.
Le fichier a pour extension .lsp.
La valauer de retour est t, si ça se passe bien et nil sinon.
Erreur nom de fichier
Erreur ( ) dans le fichier
Truc.lsp
$clisp
(carre 2) ( erreur
(load « truc »)
(carre 2)
4
Approfondissement.
I/Représentation des nombres.
En Common Lisp on trouve quatre types de nombres :
entiers
rationnels
réels
complexes
Pour les entiers, le langage nimpose pas de limite, il y aura allocation automatique en mémoire pour un grand entier.
Il y a deux représentations internes :
[-215
215-1] : pour la représentation sur deux octets
Le passeg dune représentation à lautre est transparent pour lutilisateur. Un rationnel est la division de deux entiers numératuer/diviseur.
II/Les fonctions arithmétiques.
(+ [
]) ( +
+
[...] : arguments optionnels
(+ ) ( 0
(- [....]) retourne - ( +
+)
retourne - sil ny a quun argument
(* [
.]) retourne *
.*
( * ) (1
(/ [
]) retourne /...
retourne 1/ sil ny a quun seul argument.
III/Outils de mise au point.
(trace [
])
(trace) sans argument retourne la lsitedes fonctions qui sont actuellement tracées.
(trace carré cube) ( déclenche le traçage des fonctions correspondantes.
(carre 3)
trace(carre 3)
1.trace carre ( 9
9
(untrace [
])
(untrace) supprime le traçage de toute fonction.
(untrace cube) : arrête le traçage de la fonction cube.
Il existe des variables globales.
Par convention, elles commencent et terminent par /*
Flux de sortie : * trace-output *
Pour sauver la trace dans un fichieer, il faut redéfinir le flux et lui associer un fichier.
(open [option])
Par défaut, le flux dentrée est en lecture.
Pour ouvrir un fichier en sortie :
(open « toto » : direction : output)
Il faut associer le résultat de la fonction open avec flux de trace.
Setq * trace-output * (open «
» : direction : output))
On na pas sauvé le flux de sortie dorigine, pour arrêter la trace, on force la sortie de linterpréteur.
Pour une trace plus facile à utiliser :
Ex : (defun debut-trace (fich)
(setq * sauve-sortie * * trace-output *)
(setq * trace output * (open fich : direction : output))
(defun fin-trace()
(close * trace output *)
(setq * trace output * sauve sortie))
(Pour commencer la trace dans le fichier (debut trace « nom »)
(Pour arrêter, (fin-trace)
Partie TD.
1)A partir de la liste (+ 1 2 3), écrire un appel retournant :
a) + (car (+ 1 2 3))
b) 1 (car (cdr (+ 1 2 3)))
c) 2 (car (cdr ( cdr (+ 1 2 3))))
d) (3 ) (cdr (cdr (cdr (+ 1 2 3))))
2)A partir de a, et de (b c d), écrire un appel retournant :
(a b c d) (cons a (bcd))
(b c d a) (append (b c d) (list a))
3)Remplir le tableau et vérifier avec linterpréteur :
( )aa(b c)1(+ 1 2)AtomTTNilNilTTListpTNilTTNilNilNullTNilNilNilNilNilNumberpNilNilNilNilTTSymbolp
TTNilNilNilT
4)Ecrire la fonction (dernier ) qui retourne le dernier élément de la liste l
Ex : (dernier (abc)) ( c
(defun dernier(l)
(cond ((null(cdr l)) (car l))
(t (dernier (cdr l)))))
Condition darrêt : fonction null => on renvoie le seul et premier élément (car l)
T : condition fausse => appel récursif (dernier (liste premier élément))
( : on ferme la condition à la fin.
5)Ecrire la fonction (lg ()) qui retourne le nombre déléments si largument est une liste et 0 sinon
Ex : (lg (a b c)) ( 3
(lg ((a b) c)) ( 2
(defun lg( l )
(cond ((null (l) 0)
(t (+ 1 (lg(cdr l))))))
6)Ecrire la fonction (lgAll() qui renvoie 0 si largument est un atome et le nombre total déléments sinon.
Ex : (lgAll ( (a b) c)) ( 3
(defun lgAll (s)
(cond (( atom s) 0)
((listp (car s)) (+ (lgAll (cdr s)) (lgAll (car s)) ))
(t ( + 1 (lgAll (cdr s)) ))))
7)Ecrire la fonction aplatir
Ex : (aplatir ((a (b c))( ) ((( d ))) e )) ( (a b c d e)
Attention correction non mise !!
IV /Correction et trace.
Dernier (e) = e e : élément quelconque (liste ou atome)
Dernier (e1 e2
.en) = dernier(e1 e2
.en)
(Defun dernier (l )
(cond (( null (cdr l )) ( liste à un seul élément (car l)
(t ( dernier (cdr l ) ))))
nbElt( ) = 0
nbElt(e1 e2
.en) = 1 + nbElt(e1 e2
.en)
(defun lg (s)
( cond (( atom s) 0)
(t (+ 1 (lg (cdr s) )))))
Récursivité : code + environnement , association variables ( valeurs.
Insérer trace de lg (cf cours pap /TP)
V/Présentation des fonctions booléenes.
(not ) : retourne T si lévaluation de est ( ) ( Faux
retourne Nil si lévaluation de est ( de ( ) ( Vrai
>(not 0) (Faux 0 ( ( ) ( not renvoie nil
>(not ( ) ) (Vrai ( ) ( Nil ( not renvoie T
Les fonctions Null et Not ont exactement le même comportement, cependant, pour des raisons de lisibilité, on utilise Null pour tester si une liste est vide et Not pour inverser une valeur logique.
(and [
]) : si and na pas dargument, la fonction retourne True
and évalue les arguments
et stoppe lévaluation dès que lévaluation dun élément vaut Nil, dans ce cas la fonction retourne Nil, sinon elle retourne lévaluation du dernier argument.
(and 1 2 4) ( T
(and 1 ( ) 4) ( nil
(or [
]) : si or na pas dargument, la fonction retourne Nil, sinon, or évalue les arguments en séquence (de s1 à sn) et stoppe l'évaluation dès qu'un argument ou une valeur est ( de Nil.
Les fonctions and et or peuvent être utilisées comme des fonctions de contrôle .
Exemple : on veux savoir si le premier élément d'une liste est un nombre
(defun test1 (s)
cond( (listp s) (numberp (car l))
(t ( ) )))
(defun test1 (s)
(and (listp s) (numberp (car s))))
(defun test1 (s)
(and (numberp(car s)) (listp s)))
'(a b)'(1 c)( )7test1nilTnilniltest2nilTnilniltest3nilTnilerror
Remarque : La fonction and n'est pas commutative .Test1 et test2 ont le même comportement algorithmique ( on peut utiliser and comme fonction de contrôle.
Les Arbres.
I/Arbres binaires.
1)Définition récursive.
Un arbre binaire est une structure définie sur un ensemble fini de noeuds (ou sommets) qui :
- soit ne contiennnet aucun noeud
- soit est formé de trois noeuds disjoints
- un noeud racine
- un arbre binaire (sous arbre gauche)
-un arbre binaire (sous arbre droit)
2)Parcours.
Le parcours d'un arbre consiste à examiner systèmatiquement et dans un certain ordre tous les noeuds de l'arbre pour y effectuer un même traitement.
On va détailler plus loin le parcours en profondeur
Ici, un arbre est pris au sens d'une arborescence, c'est à dire d'un arbre ayant une racine unique.
Algorithme de parcours en profondeur :
parcours (arbre)
si arbre est vide
alors fin
sinon traitement1
parcours du sous arbre gauche de l'arbre
traitement2
parcours du sous arbre droit de l'arbre
traitement3
Au cours d'un parcours, il y aura soit traitment 1, soit traitement2, soit traitement3.
Traitement1 : ordre préfixe
Traitement2 : ordre infixe
Traitement3 : ordre postfixe
R
+
G D
a b
Parcours préfixe : + a b (RGB)
Parcours infixe : a + b (GRD)
Parcours postfixe : a b + (GDR)
Exemple :
n1
n2 n3
n4 n5 n6 n7
n8 n9 n10
n11
Parcours préfixe : n1/n2/n4/n8/n11/n9/n5/n3/n6/n10/n7
Parcours infixe : n8/n11/n4/n9/n2/n5/n1/n10/n6/n3/n7
Parcours suffixe :
En ajoutant à cet arbre les sous arbres vides, le parcours en profondeur consiste à partir à gauche le plus loin possible et à suivre les contours de l'arbre.
PAGE
PAGE 14
Atome
Liste
Caractères non spéciaux
(
)
Atome
Liste
1)Interpréteur
2)Compilateur
Saisie
Evaluation
Affichage résultat
(Gère les erreurs de syntaxe)
S_expression
Atomes = atom
Nil ( null
Listes = listp
Nombre =
numberp
Str
Symbole = symbolp
1945
1960
;truc.lsp
(defun carre(n) (* n n))
(defun cube(n) (* n n n))
