(cid:1) Le paradigme fonctionnel (cid:1) Le paradigme procédural (cid:1) Le paradigme à objets Le paradigme à objets
3
paradigme fonctionnel (cid:1) Le paradigme fonctionnel paradigme fonctionnel paradigme fonctionnel • Le terme de programmation fonctionnelle désigne une famille de langages de programmation ayant un certain nombre de traits en commun, dont un rôle central donné aux fonctions, d'où le nom. • On peut y raisonner comme en maths, faire des • On peut y raisonner comme en maths, faire des démonstrations par récurrence, des analyses récursives de complexité, et acquérir une rigueur certaine.
fonctions récursives sont au cœur de ce • Les fonctions récursives fonctions récursives fonctions récursives
paradigme.
Exemple: Haskell, Standard ML et Ocaml, … Exemple Exemple Exemple
4
impératif) est le plus paradigme procédural (ou impératif (cid:1) Le paradigme procédural impératif impératif paradigme procédural paradigme procédural
ancien.
• Il met l’accent sur l'appel de procédure pour
effectuer un calcul séquentiel.
• L'itération est le mécanisme central pour effectuer un calcul répétitif, la récursivité y est rarement un calcul répétitif, la récursivité y est rarement optimisée. optimisée.
• La programmation impérative considère qu'un
texte de programme est une suite d'instructions pilotant un ordinateur.
Exemple : Apparu avec Fortran (1967), poursuivi Exemple Exemple Exemple avec Pascal (1970-1990), actuellement C est le représentant largement majoritaire.
5
paradigme à objets (cid:1) Le paradigme à objets paradigme à objets paradigme à objets • s'appuie sur la notion de classe objet . classe et d'objet objet objet classe classe • Les objets ont du savoir-faire sous la forme de méthodes méthodes qui ne sont autres que des méthodes méthodes procédures mais destinées à être transmises à un message. objet receveur sous la forme d'un message objet receveur sous la forme d'un message message. message message message message • Le calcul est donc décentralisé dans les objets, Le calcul est donc décentralisé dans les objets, dont les méthodes peuvent être fonctionnelles ou impérative. réutilisation du logiciel et son • Notion de réutilisation réutilisation réutilisation
extensibilité.
Exemple: Smalltalk (1970), popularisé avec Java et Exemple Exemple Exemple
C++ dans les années 1990.
6
Introduction Introduction Introduction Introduction Conçu en 1958 par J. McCarthy, LISP est un des plus
vieux langages de programmation.
Il fut pendant longtemps confié à la recherche en
intelligence artificielle.
LISP se distingue des langages traditionnels par le fait qu’il est spécialement adapté à la manipulation de qu’il est spécialement adapté à la manipulation de symboles. Avantages Avantages :::: Avantages Avantages (cid:1) La simplicité de la syntaxe : elle repose sur la seule
structure de liste.
(cid:1) La puissance du langage en particulier l’équivalence
complète entre données et programmes.
(cid:1) L’interactivité : LISP est principalement interprété.
8
: Atome de base : Atome Objet de base Objet : Atome : Atome de base de base Objet Objet
l’atome. L’objet de base de LISP est l’atome. l’atome. l’atome.
Un atome est : (cid:1) un nombre, Exemple:126, -54 Exemple Exemple Exemple:126, -54 Exemple Exemple Exemple Exemple (cid:1) un symbole : toute séquence non vide de
caractères,
Exemple:Le-Lisp, var, 1+x/y. Exemple Exemple Exemple Les symboles permettent de désigner les différents objets (données et fonctions).
9
liste : la liste Structure de base de LISP : la Structure de base de LISP liste liste : la : la Structure de base de LISP Structure de base de LISP
Une liste est une séquence ordonnée,
éventuellement vide, d’atomes ou de listes, délimitée entre parenthèses. délimitée entre parenthèses.
Exemple:(* 3 7) Exemple Exemple Exemple
(+ (* 3 7) (- 8 4) 10) (Langages de l’IA) ( )
La liste vide joue un rôle très important en LISP.
10
Expression élémentaire Expression élémentaire Expression élémentaire Expression élémentaire
expression L’expression élémentaire de LISP est la SSSS----expression expression expression
Une S-expression est : (cid:1) soit un atome, (cid:1) soit une liste. (cid:1) soit une liste. Toute S-expression a une valeur en LISP. Il est
important de bien différencier une S- expression de sa valeur. On note la valeur d’une S-expression <s> : VALEUR<s>.
Le rôle de l’interprète LISP est d’évaluer une S-
expression pour déterminer sa valeur.
11
Fonctionnement de base de l’évaluateur de S---- Fonctionnement de base de l’évaluateur de S Fonctionnement de base de l’évaluateur de S Fonctionnement de base de l’évaluateur de S
expression expression expression expression
La valeur d’une S-expression est déterminée
différemment, selon qu’il s’agit d’un atome ou d’une liste :
(cid:1) un atome : nombre ou symbole (cid:1) un atome : nombre ou symbole la valeur d’un nombre est lui-même, la valeur d’un symbole : (cid:1) soit prédéfinie dans LISP et non modifiable : le
symbole est alors une des deux constantes de LISP « t » ou « nil », t a pour valeur lui-même , nil a pour valeur ( ).
(cid:1) soit définie et modifiée dynamiquement, variable.
12
(cid:1) une liste (<s0>… <sn>) est évaluée comme suit : - LISP considère que <s0> est un symbole qui désigne un nom de fonction ; <s0> n’est pas évalué. <s0> ne doit être ni une liste ni un symbole qui ne correspond pas à un de fonction connu par LISP.
- LISP évalue la sous-expression <s1> et - LISP évalue la sous-expression <s > et
Publicité
détermine VALEUR<s1>, … <sn> et détermine VALEUR<sn>
- LISP applique la fonction associée à <s0> aux
arguments VALEUR<s1>…VALEUR<sn> ; la sous- expression aura pour valeur le résultat de cette application.
13
Dans une S-expression toute parenthèse ouvrante doit
être suivie d’un nom de fonction.
Exemple: Exemple Exemple Exemple ? (1 2 3 4) ** eval : fonction indéfinie : 1
Comment désigner une S-expression (atome ou liste)
qu’on ne veut pas évaluer ? (cid:2) grâce à la fonction « quote » ?(quote (1 2 3 4)) = (1 2 3 4) Abbréviation : ‘(1 2 3 4)
14
Définition de fonctions Définition de fonctions Définition de fonctions Définition de fonctions Un programme en Lisp est une fonction ou un
ensemble de fonctions. L'utilisateur définit les fonctions grâce à la primitive "de".
Exemple: Exemple: Exemple: Exemple: ? (de **(z) (* z z)) = ** La valeur de cette S-expression est le nom de
la fonction qui vient d'être définie.
15
Récursion:::: Récursion Récursion Récursion Syntaxiquement, une fonction LISP est
récursive si le nom de cette fonction figure dans sa propre défintion.
Exemple 1:Factorielle Exemple 1: Exemple 1: Exemple 1: (de fact(n) (if (= n 1) 1 (* n (fact (- n 1)))))
16
Récursion:::: Récursion Récursion Récursion Exemple 2:Suite de Fibonacci Un= Un-1 + Un- Exemple 2: Exemple 2: Exemple 2:
é
(de fib(n)
(cond ((= n 0) 0) (cond ((= n 0) 0) ((= n 1) 1) (t (+ (fib (-n 1)) (fib (- n 2)))))
17
Le rôle de l'interprète LISP est d'évaluer une S-
expression pour déterminer sa valeur.
Il procède selon l'itération suivante:
Lire une S-expression
Evaluer la S-expression
Imprimer la valeur trouvée
Une session LISP consiste à faire évaluer successivement différentes expressions qui obéissent à une syntaxe très simple.
18
(cid:1) LISP ne fait pas une distinction lexicale entre les symboles de fonctions et les symboles de variables.
(cid:1) Sinon, ceci va nous empêcher de construire par exemple une fonction récursive en la par exemple une fonction récursive en la définissant avec son itérée.
19
(cid:1) LISP ne fait pas une distinction lexicale entre les symboles de fonctions et les symboles de variables.
(cid:1) Sinon, ceci va nous empêcher de construire par exemple une fonction récursive en la par exemple une fonction récursive en la définissant avec son itérée.
(cid:1) Il existe deux classes de systèmes LISP
suivant la façon dont ce problème est résolu:
a. Systèmes bi-valents b. Systèmes mono-valents
20
valents: : : : a. Systèmes bibibibi----valents a. Systèmes valents valents a. Systèmes a. Systèmes Chaque symbole peut recevoir deux valeurs, une valeur comme variable dite C-val et une valeur comme fonction dite F-val.
Exemple: (setq a 3) (setq a 3) Nous mettons 3 dans la c-val de a
Les symboles +,-,*,... ont une F-val dans
l'environnement initial.
Le symbole fib a une F-val à partir de la définition
de la fonction fib.
21
valents: : : : a. Systèmes bibibibi----valents a. Systèmes valents valents a. Systèmes a. Systèmes Remarque: Pour avoir la définition d'une
fonction on utilise la fonction prédéfinie getdef
Exemple: ?(getdef 'fib) Exemple: ?(getdef 'fib)
Dans les systèmes bi-valents rien n'empêche
de donner une valeur à la fois à la C-val et la F-val d'un symbole.
Nous trouvons comme exemple de système
bivalents le-Lisp et Mac-Lisp.
22
valents: : : : b. Systèmes monomonomonomono----valents b. Systèmes valents valents b. Systèmes b. Systèmes Dans ces systèmes un symbole ne peut recevoir qu'une seule valeur dite C-val.
L'évaluation de la fonction donne sa définition L'évaluation de la fonction donne sa définition
(on n'a pas besoin de getdef).
23
Nous avons vu que la valeur d'une liste est
Publicité
obtenue en opérant le premier élément, qui correspond au nom de la fonction, sur les valeurs des autres éléments.
Mais prenons cet exemple: ?(setq a 5) Mais prenons cet exemple: ?(setq a 5) La règle générale n'a pas été appliquée : a n'a pas été évaluée puisqu'il s'agit de lui donner une valeur.
24
On distingue d'abord les primitives prédéfinies et les
fonctions définies par l'utilisateur:
(cid:1) SUBR: on appelle SUBR une fonction prédéfinie
écrite en langage machine évaluant ses arguments.
(cid:1) EXPR ou LAMBDA: une fonction écrite en LISP
évaluant ses argument. évaluant ses argument.
(cid:1) FSUBR: une fonction prédéfinie écrite en langage
machine n'évaluant pas tous ses arguments.
Exemple:setq Exemple: Exemple: Exemple:
25
On peut obtenir le type d'une fonction grâce à
la primitive typefn.
Exemple: Exemple: Exemple: Exemple: ?(typefn 'fact) ?(typefn 'fact) = expr ?(typefn 'car) = subr1 ?(typefn '*) = nsubr
26
Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur cons: permet d'ajouter un atome ou liste en tête - cons cons cons d'une liste.
Exemple: Exemple: Exemple: Exemple: ?(cons 2 '(3 4)) = (2 3 4) ?(cons '(1 2) '(3 4)) ?(cons '(1 2) '(3 4)) = ((1 2) 3 4)
- carcarcarcar: sélectionne et retourne le premier élément d'une
liste.
(car <l>) retourne la tête de la liste VALEUR<l>,
retourne erreur si VALEUR<l> n'est pas une liste.
27
et sélecteur de listes: Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur - cdr: retourne une liste sans son premier élément (cdr <l>) retourne le reste de la liste VALEUR<l>, retourne erreur si VALEUR<l> n'est pas une liste.
Exemple: Exemple: Exemple: Exemple: ?(car '(1 2 3)) =1 ?(car (cdr (cons 1 '(2 3)))) = 2
28
et sélecteur de listes: Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur (cid:1) CADR Permet d'extraire le second élément dela liste
fournie en argument.
Exemple: (cadr ‘(a b c)) = (car (cdr ‘(a b c)))
= (car ‘(b c)) = b
29
et sélecteur de listes: Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur (cid:1) CADDR Permet d'extraire le troisième élément dela
liste fournie en argument.
Exemple: (car (cdr (cdr ‘(a b c)))) = (car (cdr ‘(b
c))) = (car ‘(c)) = c
30
et sélecteur de listes: Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur (cid:2)b ?(cadr′(abcd)) (cid:2)c ?(caddr ′(a b c d)) (cid:2)(c) ?(cdadr ′(a (b c) d)) (cid:2)(c d) (cid:2)(c d) ?(cddr ′(a b c d)) ?(cddr ′(a b c d)) ?(cddar ′((a b c d) (e) f)) (cid:2)(c d) ?(cadar ′((a b c) d e)) (cid:2)b
31
et sélecteur de listes: Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur - (append <l1> ... <ln>) retourne la liste obtenue en concatenant les listes <l1>
... <ln> Exemple: Exemple: Exemple: Exemple: ?(append '(ceci est ) '(un support de cours) '(en Lisp)) ?(append '(ceci est ) '(un support de cours) '(en Lisp)) = (ceci est un support de cours en Lisp)
- (list <s1> ...<sn>) retourne la liste dont les éléments <s1> ...<sn>.
Exemple: Exemple: Exemple: Exemple: ?(list 1 2 '(3 4)) = (1 2 (3 4))
32
et sélecteur de listes: Constructeur et sélecteur de listes: Constructeur et sélecteur de listes: et sélecteur de listes: Constructeur Constructeur - (length <s>) retourne le nombre d'éléments de plus haut niveau de <s>, si <s> est une liste, sinon 0 (si <s> est un atome. 0 (si <s> est un atome.
Exemple: ?(lenght '(a (b c) d)) =3
33
Prédicats Prédicats Prédicats Prédicats Les fonctions prédicats sont toujours
évaluantes
et retrournent nil si le prédicat est faux. Si le prédicat est vrai, la réponse peut Si le prédicat est vrai, la réponse peut
dépendre des systèmes puisque "vrai" admet comme représentation toute S- expression différente de nil. De nombreux système utilise l'atome "t".
34
Prédicats Prédicats Prédicats Prédicats - (atom <s>) retourne "t" si VALEUR<s> est un atome numérique ou symbolique, et retourne () si c'est une liste non vide.
- (null <s>) retourne "t" si VALEUR<s> est égal à () et () dans le cas retourne "t" si VALEUR<s> est égal à () et () dans le cas
contraire.
- (eq <s1> <s2>) permet de tester l'identité de deux atomes: Si
VALEUR<s1> et VALEUR<s2> sont identiques retourne "t", sinon retourne ().
- (symbolp <s>) retourne "t" si <s> est un symbole, et retourne nil
sinon.
35
Prédicats Prédicats Prédicats Prédicats - (constantp <s>) retourne "t" si <s> est une constante, et
Publicité
retourne nil sinon. Une constante est soit un nombre, une chaîne de caractères ou nil. nombre, une chaîne de caractères ou nil.
- (consp <s>) retourne "t" si <s> est une liste non vide, et
retourne nil sinon.
- (listp <s>) retourne "t" si <s> est une liste, et retourne nil
sinon.
36
Fonctions logiques Fonctions logiques Fonctions logiques Fonctions logiques Ce sont les fonctions pour lesquelles la valeur
logique du résultat ne dépend que de la valeur logique des arguments. Par exemple "OR" retourne une expression de valeur "OR" retourne une expression de valeur logique vraie si l'un au moins des arguments est de valeur logique vraie sinon retourne nil.
De plus pour éviter des évaluations inutiles,
l'évaluation s'arrête dés le premier argument dont la valeur est vraie. Pour cette raison OR est une F-SUBR.
37
logiques Fonctions logiques Fonctions logiques logiques Fonctions Fonctions - (or <s1> ..<sN>) retourne la valeur du premier argument dont la
valeur est différent de nil, et nil sinon.
L'évaluation est arrêté dés l'obtention de nil. L'évaluation est arrêté dés l'obtention de nil. - (and <s1> ..<sN>) retourne la valeur du dernier argument si les évaluations de tous les arguments sont de valeur vraie, et nil s'il n'existe pas.
38
Séquenceurs Séquenceurs Séquenceurs Séquenceurs (progn <s1> ... <sN>) évalue séquentiellement ses arguments et
retourne la valeur du dernier.
39
(IF <s1> <s2> <s3>)
Si la valeur de <s1> est différente de NIL, IF retourne la
valeur de <s2>; sinon, IF évalue <s3>.
IF permet de construire une structure de contrôle de type
"si alors sinon" . "si alors sinon" .
Exemples : ?(IF T 1 2) =1 ?(IF NIL 1 2) =2 ?(IF NIL 1) =NIL
40
(WHEN <test> <s1> ... <sN>)
Si <test> est Vrai, WHEN évalue chacune des
expressions <sI>.
(UNLESS <test> <s1> ... <sN>)
Si <test> est Faux, UNLESS évalue chacune des
expressions <sI>.
41
(COND <l1> <l2> ... <lN>)
COND est la fonction conditionnelle la plus complète de LISP.
Chaque <li> est une liste appelée clause, ayant la structure
suivante:
(<ss> <s1> <s2> ... <sN>) où <ss> est une expression
quelconque et <s1> ... <sN> le corps de la clause. COND sélectionne la première <li> dont la valeur de <ss> est différente de NIL. Si le nombre des <si> de la clause est nul, COND retourne la valeur de <ss>, sinon les <s1> ... <sN> de la clause sont évalués et la valeur de <sN> est retournée. Si aucune clause n'est sélectionnée, COND retourne NIL.
42
Exemple :
?(de test (x y) (COND
((> x y) ((= x y) ((= x y) 'inf)) (t
'sup) 'egal) 'egal)
) = test ?(test 12 5) = sup ?(test 5 8) =inf
43
- (print <expr>) évalue son argument, édite la valeur obtenue et
retourne sa valeur.
Exemple: Exemple: ?(setq a 3) = 3 ?(print a) a = 3
44
print est souvent utilisée avec des chaînes de print print print
caractères (entre guillemets).
?(print 'salut) ; on crée le symbole salut salut = salut = salut ?(setq salut "Bonjour") = Bonjour ?(print salut) Bonjour = Bonjour
45
L'utilisation de print ne se justifie que lorsque
le résultat de l'évaluation n'est pas édité.
- (readreadreadread) c'est une fonction 0-aire qui retourne sans
l‘évaluer la réponse de l'utilisateur (un ? est l‘évaluer la réponse de l'utilisateur (un ? est envoyé par le système pour l'inviter à envoyer envoyé par le système pour l'inviter à envoyer une expression).
Exemple: ? (setq x (read)) ? 5; réponse de l'utilisateur = 5
46