à droite, on montre que conc[L,()]=L par récurrence sur L:
-
c est vrai si L est vide (1ere clause)
- soit L=cons[N,R] et supposons conc[R,()]=R on a :
conc[L,()] = cons[N,conc[R,()]] (application clause 2)
= cons[N,R] (hypothèse de récurrence)
= L
Montrez les propriétés suivantes :
- La concaténation est associative
- long conc[L1 ,L2 ] = long L1 + Long L1
- nbsup[X, conc[L1 ,L2 ] ] = nbsup[X,L1 ] + nbsup[X,L2 ]
Exercice : \1ajout d'un élément en fin de liste.
Exercice : Inversion d'une liste
inv : Liste x Liste \8-L \1Liste
inv[ () ] = ()
inv[ cons[N,R] ] = conc[ inv[R] , cons[N,()] ]
Démontrez que inv[conc[L1 ,L2 ]] = conc[inv[l2 ], inv[L1 ]]
Exercice : programmer en LISP fac,long,app et conc
Solutions :
(de fac (N) (cond
((= N 0) 1)
( T (* N (fac (- N 1))) ))
(de long (L)
(cond
((null L) 0)
(T (+ 1 (long (cdr L))))
))
(de app (O L)
(cond
((null L) ())
((eq (car L) O)) T)
( T (app O (cdr L)))
))
(de conc (L1 L2)
(cond ((null l1) l2)
( T (cons (car L1)
(conc (cdr L1) L2)))
)
4.c Utilisation de Fonctions Auxiliaires.
L'emploi de fonctions auxiliaires correspond naturellement à la décomposition
d'actions 'compliquées' en actions simples dans l'algorithmique
traditionnelle. On emploiera donc des fonctions auxiliaires dès lors que le
texte d'une fonction dépasse quelques lignes.
L'intérêt de cette décomposition est renforcé par le fait que Lisp fonctionne
sous forme d'interpréteur : Il est très facile de 'tester' une fonction
indépendamment du reste du programme : les erreurs seront bien plus
facilement localisables si elles se situent dans de petites fonctions.
D'autre part il arrive assez souvent qu'on ne puisse pas exprimer aisément
une fonction de manière directement récursive; mais que cette fonction puisse
être dérivée d'une autre fonction qui, elle, s'exprime facilement ainsi. Un
petit exemple éclairera mon propos: Tout le monde connait la célébre suite de
Fibonnacci :
fib (0) = 0
fib (1) = 1
fib (n+2) = fib (n+1) + fib (n)
et chacun sait (ou vérifiera par lui-même) que la programmation directe de
cette fonction est diablement inefficace (complexité ?)
Aussi s'intéresse-t'on à une autre fonction aux : N -> N x N définie par
récurrence :
aux(0) = (0 , 1)
aux(n) = posons (x,y)=aux(n-1)
alors (x+y,x)
et fib s'obtient alors simplement en appelant cette fonction auxiliaire :
fib'(n) = posons (x,y)=aux(n)
alors y
Exercice :
- calculez les 10 premières valeurs aux[0],aux[1].....
- Montrez que fib'[n] = fib[n] pour tout n positif.
4.d Arbres Binaires
En suivant les mêmes principes, on définit les arbres binaires :
-
l'arbre vide est un arbre binaire
- si t1 et t2 sont des arbres binaires, et s un symbole,
noeud[s,t1,t2] est également un arbre binaire.
Problème (facile) : arbre généalogique
On désire représenter des arbres généalogiques (arbre des ascendants).
Pour représenter de tels arbres en Lisp on choisit le procédé suivant :
- l'arbre vide (individu inconnu) est codé par l'atome NIL = ()
- un arbre binaire non vide (associé à une personne) est codé par une liste à
3 éléments : Le nom de la personne
du noeud, l'arbre associé à sa mère, celui associé à son père.
Exemple :
jules (jules
/ \ (marie (zoe () ())
marie paul (leon () ()))
/ \ / (paul (lise () ())
zoe leon lise ()))
- écrire une fonction qui, pour une personne et un arbre donné, retourne le
nom de la mère de cette personne (si connu, nil sinon).
ex: (mere 'marie '(jules .... )) -> zoe
- même chose pour le père.
- Ecrire une fonction qui indique la liste des noms des ascendants d'une
personne.
4.e Un exemple Pratique: Calcul Formel d'une Dérivée
Pour conclure cette partie nous allons développer un (petit) exemple typique
de ce qu'on appelle «programmation symbolique» (ou «manipulation
d'expressions symboliques».
Il s'agit d'écrire un programme capable d'effectuer la dérivation
(différentiation) d'une expression symbolique par rapport à une variable.
Evidemment, pour un début, nous nous limiterons à des expressions simples,
composées :
- de variables (représentées par les atomes)
- de constantes
- de sommes, produits, différences et quotients d'expressions.
Ces expressions seront codées sous la forme LISP habituelle, par exemple :
1
_________
sera écrit ( / 1 ( + (* a x) b))
ax + b
Bref, nous voulons écrire une fonction qui, à un atome (représentant le nom
d'une variable) et une S-expr (la formule à dériver) fait correspondre une
autre s-expr (la dérivée).
DERIV : Atome x S-Expr --> S-expr
Commençons la programmation de cette fonction DERIV. Les deux cas les plus
simples sont :
- la dérivation d'une expression réduite à une variable (disons x) par
rapport à cette même variable (Dans ce cas la réponse est évidemment 1).
- la dérivation d'une expression réduite à une constante (pas forcément
numérique) ou d'une autre variable (résultat -> 0).
Ne resteront plus ensuite à étudier que les expressions «binaires» de la
forme (opérateur expr-g expr-d). Ce qui suggère la programmation qui suit :
! (de DERIV (var exp)
! (cond
! ((eq var exp) 1)
! ((atom exp) 0)
! ( T (DERIV-BIN var (car exp)
! (cadr exp)
! (caddr exp)))))
Conformément aux bonnes habitudes, nous repoussons la difficulté (la
dérivation d'une expression composée) à plus tard, c'est-à-dire dans une
fonction auxiliaire DERIV-BIN.
Il nous faut maintenant écrire cette fameuse fonction auxiliaire DERIV-BIN:
DERIV-BIN : Variable x Opérateur x Expr1 x Expr2 -> Dérivée
L'entête est facile à écrire
(de DERIV-BIN (var op e1 e2) ... )
Pour le reste, comment s'y prendre ? Supposons que nous avons déjà identifié
l'opérateur «+». Le résultat que nous voulons obtenir est une liste de la
forme: ( + Exp'1 Exp'2 ) o— Exp'1 et Exp'2 sont les dérivées des
expressions Expr1 et Expr2. On pourrait écrire quelque chose du style :
(cons '+ (cons (DERIV var e1)
(cons (DERIV var e2)
nil)))
C'est un peu lourd ! Pour construire une liste contenant 3 objets (ou plus),
il existe heureusement une fonction plus adéquate : l'évaluation de
( list e1 ... e2 )
renvoie la liste des valeurs des valeurs e1 ... e2.
(Conclusion
partielle: il faut lire les manuels !)
Nous écrirons donc de préférence :
( list '+ (DERIV var e1) (DERIV var e2) )
Exercice : Ecrire l'expression qui correspond au calcul de la dérivée d'un
quotient.
Solution: c'est trop fatigant : on décide de repousser la construction des
sommes, produits, etc... dans des fonctions auxiliaires PLUS, MOINS, MULT,
DIVIS.
! (de PLUS (e1 e2) ( list '+ e1 e2))
! (de MULT (e1 e2) ( list '* e1 e2))
! .........
D'autre part, nous avons fréquemment besoin des expressions (DERIV var e1) et
(DERIV var e2) : pourquoi ne pas les stocker dans des variables locales d1,
d2 ?
(LET ( (d1 (DERIV var e1)) (d2 (DERIV var e2)) )
...... (SOMME d1 d2) ...
Le dernier problême à résoudre est «l'aiguillage à quatre pattes» selon la
valeur de l'opérateur. On peut bien sùr s'en tirer par des if imbriqués, mais
on trouve notre bonheur en regardant -une fois de plus-dans le manuel: la
fonction selectq est, en gros, l'équivalent du CASE Pascal :
(selectq expression
( atome1 expressions1 )
( atome2 expressions2 )
.....
( atomen expressionsn ))
L'expression est évaluée, elle doit renvoyer un atome. La liste d'expressions
correspondant à cet atome est alors activée.
Voici DERIV-BIN :
! (de DERIV-BIN
! (var op e1 e2)
! (let ( (d1 (DERIV var e1))
! (d2 (DERIV var e2)) )
! (selectq op ( + (PLUS d1 d2) )
! ( - (MOINS d1 d2) )
! ( * (PLUS (MULT d1 e2)
! (MULT d2 e1) ))
! ( / (DIVIS (MOINS (MULT d1 e2)
! (MULT e1 d2))
! (MULT e2 e2)) ))))
C'est tout !
Voyons les résultats :
?- (DERIV 'x '(+ (* a x) b) ) ; on demande pour x -> ax + b
-> (+ (+ (* a 1) (* 0 x)) 0) ; cad : (a.1 + 0.x) + 0
?- (DERIV 'x '(/ 1 (+ (* a x) b))) ; x -> 1/(ax+b)
-> (/ (- (* 0 (+ (* a x) b))
(* (+ (+ (* a 1)(* 0 x)) 0) 1))
(* (+ (* a x) b) (+ (* a x) b)))
c'est-à-dire :
0.(ax+b) - ((a.1+0.x) + 0).1
----------------------------
(ax+b).(ax+b)
Evidemment, çà serait quand même mieux si notre systême de dérivation
formelle savait faire les simplifications qui s'imposent ; qu'il puisse au
moins réduire les produits par 0, par 1, etc... Il suffit pour cela de
redéfinir les fonctions PLUS, MOINS, MULT et DIVIS :
! (de PLUS (e1 e2)
! (cond
! ((eq e1 0) e2) ; 0 + e2 -> e2
! ((eq e2 0) e1) ; e1 + 0 -> e1
! ((and (numberp e1) (numberp e2)) (+ e1 e2))
! (T (list '+ e1 e2)) ))
On peut faire la même chose pour les autres fonctions :
! (de MOINS (e1 e2)
! (cond
! ((eq e2 0) e1) ; e1 - 0 -> e1
! ((equal e1 e2) 0) ; e - e -> 0
! ((and (numberp e1) (numberp e2)) (- e1 e2))
! (T (list '- e1 e2)) ))
Exercice : réécrire MULT et DIVIS
Solution :
(de MULT (e1 e2)
(cond ((or (eq e1 0) ; 0 * e2 -> 0
((eq e2 0)) 0) ; e1 * 0 -> 0
((and (numberp e1)
(numberp e2)) (* e1 e2)) ( T (list '* e1 e2))))
(de DIVIS (e1 e2)
(cond
( (eq e1 0) 0) ; 0 / e2 -> 0
( (eq e2 1) e1) ; e1 / 1 -> e1
( (equal e1 e2) 1) ; e / e -> 1
( (and (numberp e1)
(numberp e2)) (/ e1 e2))
( T (list '/ e1 e2))))
Les résultats sont encourageants :
?- (DERIV 'x '(+ (* a x) b) ) ; on demande pour x -> ax + b
-> a
?- (DERIV 'x '(/ 1 (+ (* a x) b))) ; x -> 1/(ax+b)
-> (/ (- 0 a)
(* (+ (* a x) b)
(+ (* a x) b)))
c'est-à-dire :
0 - a
------------
(ax+b).(ax+b)
4.f Variables Tampon
Intuitivement, on dit qu'un paramêtre d'une fonction est une variable
tampon quand ce paramêtre grossit au dur et à mesure du déroulement d'un
calcul (alors que le paramêtre sur lequel se fait la récurrence décroit).
Exemple : définition par récurrence de la somme de deux nombres :
plus[O,P] = P
plus[N,P] = plus[N-1,P+1] si N>0
calcul de plus[2,2] : plus[2,2] = plus[1,3] = plus[0,4] = 4 !!
Cette technique permet parfois des améliorations nettes en complexité pour le
calcul de certaines fonctions. Par exemple le calcul de l'inverse d'une
liste, naïvement, peut s'écrire :
inv : Liste -L Liste
inv[ () ] = () (1)
inv[cons[P,R]] = inv[R] conc (P cons ()) (2)
Ce qui conduit à un temps de calcul quadratique
inv[ (a b c d)
= inv[(b c d)] conc (a)
= (inv [(c d)] conc (b) ) conc (a)
= ((inv [(c)] conc (d)) conc (b) ) conc (a)
= (((inv [()] conc (c)) conc (d)) conc (b) ) conc (a)
= ((( () conc (c)) conc (d)) conc (b) ) conc (a)
= (( (c) ) conc (d)) conc (b) ) conc (a) conc 1 étape
= ( (c d) conc (b) ) conc (a) conc 2 étapes
= (c d b ) conc (a) conc 3 étapes
= (c d b a) conc 4 étapes
ceci parce que le coût du calcul de «L1 conc L2» est proportionnel à la
taille de L1.
On peut faire beaucoup mieux : l'idée est de stocker au fur et à
mesure dans une variable tampon les éléments que l'on enlève de la liste que
l'on veut inverser :
r[ (a b c d),() ] = r [ (b c d),( a) ]
= r [ (c d),(b a) ]
= r [ (d),(b c a) ]
= r[ (),(d c b a) ]
= (d c b a)
le résultat attendu est dans le second paramêtre.
D'où la définition de r :
r : Liste x Liste -L Liste
r[ () , L ] = L
r[ N cons R] , L] = r[ R , N cons L]
on a alors : rev[L] = r[L,()]
Théoreme :
rev = inv
Preuve :
- On montre tout d'abord que pour toutes listes L1 L2 on a :
r[L1,L2] = inv[L1] conc L2
Par récurrence sur L1:
- vrai pour L1=() puisque par def de inv : inv[()] = ()
et par def de conc: () conc L2 = L2.
- si L1= P cons R :
r[ P cons R, L2 ] = r[ R , P cons L2 ] def de r
= inv[R] conc (P cons L2) recurrence
et inv[(P cons R)] conc L2
= (inv[R] conc (P cons ())) conc L2 def inv
= (inv[R] conc (P cons (() conc L2))) def conc
= inv[R] conc (P cons L2) def conc
- la liste vide est élément neutre de la concaténation, on a donc :
rev[L] = r[L,()] = inv[L] conc () = inv[L].
Ce qui clôt la démonstration.
Exercice : On veut construire, pour N donné, la liste des entiers de 1 à N
(fonction iota). Par récurrence directe, on a :
iota[0] = ()
iota[N] = iota[N-1] conc (N cons ())
- Montrez que le temps de calcul de cette fonction est quadratique en N.
- Construire une fonction équivalente i de coùt linéaire grâce à l'emploi
d'une fonction auxiliaire f munie d'une variable tampon.
conseil : posez f[N,L] = iota[N] conc L
en justifiant toutes les étapes.
Problème : On représente des nombres binaires par des listes de 0 et de 1.
Exemple : (1 1 0 1) -> le nombre binaire 1101 --> en décimal 13.
On veut écrire une fonction dec, qui à une telle liste associe sa valeur
décimale.
- On remarque tout d'abord que, par exemple :
dec[ (1 0 0 0 1 1 1 0 0) ] = 1*28 + dec[ (0 0 0 1 1 1 0 0) ]
et, plus généralement:
dec[ cons[N,R] ] = N*2long[R] + dec[R]
- montrez que l'on peut donner une définition directe de la fonction f
f : N x Listes -> N
2*long[L]
f[D,L] = D* + dec[L]
(c'est-à-dire n'utilisant pas long ni dec).
- En déduire une définition de f. Estimez le coùt du calcul de dec[L].
- Considérons le programme (impératif) suivant :
programme DEDE
donnée : X : liste
résultat : P : entier
début
P := 0
tant que X non vide faire
debut
P := 2*P + car[X]
X := cdr[X]
fin
fin programme
Montrez le lien entre ce programme et la fonction précédente. On pourra par
exemple calculer en parallèle DEDE[ (1 1 0 1)] et dec[ (1 1 0 1) ].
M. BILLAUD Département Informatique IUT-A Bordeaux (1989)