(cid:1) Le paradigme fonctionnel

(cid:1) Le paradigme proc dural

(cid:1) Le paradigme objets

Le paradigme objets

paradigme fonctionnel

(cid:1) Le 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

d monstrations par r currence, des analyses

r cursives de complexit , et acqu rir une rigueur

certaine.

fonctions r cursives sont au cSur de ce

" Les fonctions r cursives

fonctions r cursives

paradigme.

Exemple: Haskell, Standard ML et Ocaml, &

Exemple

imp ratif) est le plus

paradigme proc dural (ou imp ratif

(cid:1) Le paradigme proc dural

imp ratif

paradigme proc dural

ancien.

" Il met laccent 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

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

avec Pascal (1970-1990), actuellement C est le

repr sentant largement majoritaire.

paradigme objets

(cid:1) Le paradigme objets

paradigme objets

" s'appuie sur la notion de classe

objet .

classe et d'objet

objet

classe

" Les objets ont du savoir-faire sous la forme

de m thodes

m thodes qui ne sont autres que des

m thodes

proc dures mais destin es tre transmises un

message.

objet receveur sous la forme d'un 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

extensibilit .

Exemple: Smalltalk (1970), popularis avec Java et

Exemple

C++ dans les ann es 1990.

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

quil est sp cialement adapt la manipulation de

symboles.

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) Linteractivit : LISP est principalement interpr t .

: Atome

de base : Atome

Objet de base

Objet

: Atome

de base

Objet

latome.

Lobjet de base de LISP est latome.

latome.

Un atome est :

(cid:1) un nombre,

Exemple:126, -54

Exemple

Exemple:126, -54

Exemple

(cid:1) un symbole : toute s quence non vide de

caract res,

Exemple:Le-Lisp, var, 1+x/y.

Exemple

Les symboles permettent de d signer les

diff rents objets (donn es et fonctions).

liste

: la liste

Structure de base de LISP : la

Structure de base de LISP

liste

: la

Structure de base de LISP

Une liste est une s quence ordonn e,

ventuellement vide, datomes ou de listes,

d limit e entre parenth ses.

Exemple:(* 3 7)

Exemple

(+ (* 3 7) (- 8 4) 10)

(Langages de lIA)

( )

La liste vide joue un r le tr s important en LISP.

Expression l mentaire

expression

Lexpression l mentaire de LISP est la SSSS----expression

expression

Une S-expression est :

(cid:1) soit un atome,

(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

dune S-expression <s> : VALEUR<s>.

Le r le de linterpr te LISP est d valuer une S-

expression pour d terminer sa valeur.

Fonctionnement de base de l valuateur de S----

Fonctionnement de base de l valuateur de S

expression

La valeur dune S-expression est d termin e

diff remment, selon quil sagit dun atome ou dune

liste :

(cid:1) un atome : nombre ou symbole

la valeur dun nombre est lui-m me,

la valeur dun 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.

(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> nest 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

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.

Dans une S-expression toute parenth se ouvrante doit

tre suivie dun nom de fonction.

Exemple:

Exemple

? (1 2 3 4)

** eval : fonction ind finie : 1

Comment d signer une S-expression (atome ou liste)

quon 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)

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:

? (de *(z) ( z z))

= **

La valeur de cette S-expression est le nom de

la fonction qui vient d' tre d finie.

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:

(de fact(n)

(if (= n 1)

(* n (fact (- n 1)))))

R cursion::::

R cursion

Exemple 2:Suite de Fibonacci Un= Un-1 + Un-

Exemple 2:

(de fib(n)

(cond ((= n 0) 0)

((= n 1) 1)

(t (+ (fib (-n 1)) (fib (- n 2)))))

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.

(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

d finissant avec son it r e.

(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

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

valents: : : :

a. Syst mes bibibibi----valents

a. Syst mes

valents

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)

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.

valents: : : :

a. Syst mes bibibibi----valents

a. Syst mes

valents

a. Syst mes

Remarque: Pour avoir la d finition d'une

fonction on utilise la fonction pr d finie

getdef

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.

valents: : : :

b. Syst mes monomonomonomono----valents

b. Syst mes

valents

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

(on n'a pas besoin de getdef).

Nous avons vu que la valeur d'une liste est

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)

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.

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.

(cid:1) FSUBR: une fonction pr d finie crite en langage

machine n' valuant pas tous ses arguments.

Exemple:setq

Exemple:

On peut obtenir le type d'une fonction gr ce

la primitive typefn.

Exemple:

?(typefn 'fact)

= expr

?(typefn 'car)

= subr1

?(typefn '*)

= nsubr

Constructeur

et s lecteur de listes:

Constructeur et s lecteur de listes:

et s lecteur de listes:

Constructeur

cons: permet d'ajouter un atome ou liste en t te

cons

cons

d'une liste.

Exemple:

?(cons 2 '(3 4))

= (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.

et s lecteur de listes:

Constructeur et s lecteur de listes:

Constructeur

et s lecteur de listes:

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:

?(car '(1 2 3))

?(car (cdr (cons 1 '(2 3))))

= 2

et s lecteur de listes:

Constructeur et s lecteur de listes:

Constructeur

et s lecteur de listes:

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

et s lecteur de listes:

Constructeur et s lecteur de listes:

Constructeur

et s lecteur de listes:

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

et s lecteur de listes:

Constructeur et s lecteur de listes:

Constructeur

et s lecteur de listes:

Constructeur

(cid:2)b

?(cadr2(abcd))

(cid:2)c

?(caddr 2(a b c d))

(cid:2)(c)

?(cdadr 2(a (b c) d))

(cid:2)(c d)

?(cddr 2(a b c d))

?(cddar 2((a b c d) (e) f)) (cid:2)(c d)

?(cadar 2((a b c) d e)) (cid:2)b

et s lecteur de listes:

Constructeur et s lecteur de listes:

Constructeur

et s lecteur de listes:

Constructeur

(append <l1> ... <ln>)

retourne la liste obtenue en concatenant les listes <l1>

... <ln>

Exemple:

?(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:

?(list 1 2 '(3 4))

= (1 2 (3 4))

et s lecteur de listes:

Constructeur et s lecteur de listes:

Constructeur

et s lecteur de listes:

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.

Exemple:

?(lenght '(a (b c) d))

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

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".

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

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.

Pr dicats

(constantp <s>)

retourne "t" si <s> est une constante, et

retourne nil sinon. Une constante est soit un

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.

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

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.

logiques

Fonctions logiques

Fonctions

logiques

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.

(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.

S quenceurs

(progn <s1> ... <sN>)

value s quentiellement ses arguments et

retourne la valeur du dernier.

(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" .

Exemples :

?(IF T 1 2)

?(IF NIL 1 2)

?(IF NIL 1)

=NIL

(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>.

(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

(<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.

Exemple :

?(de test (x y)

(COND

((> x y)

((= x y)

'inf))

'sup)

'egal)

)

= test

?(test 12 5)

= sup

?(test 5 8)

=inf

(print <expr>)

value son argument, dite la valeur obtenue et

retourne sa valeur.

Exemple:

?(setq a 3)

= 3

?(print a)

= 3

print est souvent utilis e avec des cha nes de

caract res (entre guillemets).

?(print 'salut) ; on cr e le symbole salut

salut

= salut

?(setq salut "Bonjour")

= Bonjour

?(print salut)

Bonjour

= Bonjour

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

envoy par le syst me pour l'inviter envoyer

une expression).

Exemple:

? (setq x (read))

? 5; r ponse de l'utilisateur

= 5

Programming Paradigms

Programming Paradigms