02-programmation Fonctionnelle - Le Lisp

Programmation Fonctionnelle - Le Lisp -

Campus Booster ID : 513

www.supinfo.com Copyright © SUPINFO.

All rights reserved

Programmation Fonctionnelle - Le Lisp -

Votre formateur… Titre: Professeur Référent en IA Distinctions & expérience: Enseignement et recherche en Intelligence Artificielle, Informatique et Electronique. Participation à des congrès internationaux en Intelligence Artificielle Formation: Doctorat en Intelligence Artificielle. Ingénieur en télécommunications. Publications: 60 articles, communications et livres dont 48 sur l’IA Marianne BELIS

Contact: [email protected] SUPINFONE: 1 317

Programmation Fonctionnelle - Le Lisp -

Votre formateur… Titre: Professeur Référent en Algorithmique, Théorie des Graphes et Intelligence Artificielle. Distinction: Mastaire en Recherche Opérationnelle et Intelligence Artificielle. Formation: Ingénieur en Informatique, Conception et Développement, (modélisation, optimisation, simulation, complexité et algorithmique). Qualifié en Gestion des Risques (spécialisé en modélisation et Systèmes d'Information)

Arnaud CUEILLE

Publication: « La simulation des flux de transports de marchandises en agglomération » (2002). Contact: [email protected] SUPINFONE: 1 50087

Programmation Fonctionnelle - Le Lisp -

Objectifs de ce module En suivant ce module vous allez:  Aborder la programmation fonctionnelle.  Maîtriser les principales primitives du langage LISP.  Lire et comprendre le fonctionnement de programmes en LISP.  Ecrire des fonctions simples, maîtriser le concept de récursivité avec des listes.  Utiliser le Lisp dans des applications d’IA comme les système expert, la sortie d’un labyrinthe ou le jeu du taquin.

Programmation Fonctionnelle - Le Lisp -

Plan du module Voici les parties que nous allons aborder:

 Généralités, éléments de base.

 Les structures de contrôle.

 Fonctions complexes.

 Opérations symboliques.

Programmation Fonctionnelle - Le Lisp -

Généralités, éléments de base

Généralités, éléments de base

Plan de la partie Voici les chapitres que nous allons aborder:  Présentation  Les expressions symboliques  Fonctions arithmétiques élémentaires  Les fonctions primitives  Les prédicats  Fonctions d'affectation et d'évaluation  Représentation graphique des listes  Les fonctions d'entrée/sortie  L’environnement de programmation

Généralités, éléments de base

Présentation Origine du langage Lisp.  Son concepteur :  John Mc CARTHY  Création en 1960  Spécificités du Lisp  Langage fonctionnel*  Traitement symbolique**  Le code est formé de listes parenthésées***

John Mc CARTHY

Généralités, éléments de base

Présentation Historique des principaux langages, dont le Lisp. 1957 1958

ALGOL

FORTRAN

1960

1964

1966

LISP

COBOL

1970

1972

PROLOG

LOGO

BASIC

PL/I

B

PASCAL

Généralités, éléments de base

Présentation Historique des dialectes Lisp . 1966 1967

1960

MACLISP

LISP 1.5

1975

INTERLISP

SCHEME

1984 1985 1986

1977

LE_LISP

VLISP

CommonLISP

EULISP

AutoLISP

Généralités, éléments de base

Présentation Spécificités du langage fonctionnel Lisp  Syntaxe simple mais parenthèses multiples

 Utilisation intensive de la récursivité

 Typage dynamique des données*

 Pas de distinction entre données et programme**

 Langage interprété***

Généralités, éléments de base

Présentation

Lecture d’une expression

L’algorithme d’exécution de l’interprète est une boucle

READ-EVAL-PRINT Evaluation de l’expression

Impression du résultat

qui s’exécute à divers niveaux de profondeur en commençant par le plus profond.

Généralités, éléments de base

Les expressions symboliques Il existe trois catégories d'expressions symboliques* :

 Les atomes

 Les listes

 Les paires pointées

Généralités, éléments de base

Les expressions symboliques

ATOME Expression symbolique élémentaire. C’est une S-EXPRESSION insécable*

Généralités, éléments de base

Les expressions symboliques La forme que peuvent prendre les atomes.  Les noms :  Un caractère  ex: a  Suite de caractères sans séparateur  ex: supinfo  Les nombres :  Nombres positifs  Nombres négatifs

Généralités, éléments de base

Les expressions symboliques Exemples d'atomes a B  ATOME  Pierre  Atome-Long  unseulatomelong  128  -345  *86  49CE+

Généralités, éléments de base

Les expressions symboliques

AT

! N O I TENT

n u e t s i il ex e m o t a r e i l u c i part ! L I N appelé … e r v i à su

Généralités, éléments de base

Les expressions symboliques

SÉPARATEUR Caractère qui permet de séparer les expressions.

Généralités, éléments de base

Les expressions symboliques La liste des séparateurs en LISP  Le point :

.

 L’espace  Les parenthèses : ( et )  Les crochets :

[ et ]

 L’apostrophe : quote ou ’  La tabulation  Le point-virgule :

;

 Le retour chariot (return)

Généralités, éléments de base

Les expressions symboliques

! N O I T N E ATT n u e t s Il exi r u e t a sépar e l : r e i l u c i t par ! > . < t poin … e r v i à su

Généralités, éléments de base

Les expressions symboliques

LISTE S-EXPRESSION Suite ordonnée d’atomes ou de listes

Généralités, éléments de base

Les expressions symboliques Exemples de listes  (A B) :

liste constituée de 2 atomes

 (A B C) :

liste constituée de 3 atomes

 (A (B C)) :

liste constituée de 1 atome et d'une liste

 (Une liste) :

liste constituée de 2 atomes

 (Jean aime Marie) :

liste constituée de 3 atomes

 () :

liste vide, correspond à : NIL

Généralités, éléments de base

Les expressions symboliques

Paire pointée Une paire pointée est spécifiée par l'utilisation du séparateur point <.> situé entre deux objets. ex.: (A . B)

Généralités, éléments de base

Les expressions symboliques Autres notions élémentaires

 Longueur d'une liste

 Profondeur d'une liste

 Appel d'une fonction Lisp

Généralités, éléments de base

Les expressions symboliques Notion de longueur d'une liste : ici, longueur = 3 Le premier élément est précédé d'une parenthèse.

1er élément

Le dernier élément est suivi d'une parenthèse.

3ème élément

(A B C) 2ème élément Le second élément est encadré de séparateurs, ici un espace.

Généralités, éléments de base

Les expressions symboliques Notion de profondeur d'une liste : ici, profondeur = 2 Le premier élément (l’atome “une”) est au premier niveau: profondeur 0.

1er niveau

Le dernier élément (l’atome “profonde”) est au troisième niveau: profondeur 2

3ème niveau

(une (liste (profonde))) 2ème niveau Le second élément (l’atome “liste”) est au second niveau: profondeur 1.

Généralités, éléments de base

Les expressions symboliques

) … … (… s e s è h t n e r a p s Les e é s i l i t u i s s u sont a e l r e u q r a m pour e d n i f a l t e t débu e n u ' d l l'appe . n o i t fonc

Généralités, éléments de base

Les expressions symboliques Appel d'une fonction

Nom de la fonction appelée

Argument n°2

(nomdelafonction <arg 1> <arg 2>… <arg n>) Argument n°1

Argument n°n

Généralités, éléments de base

Les expressions symboliques

) … … n o i t c n (fo a l e d m é Le no c a l p t s e n o i fonct a l s è r p a s r u o e t n touj a r v u o e s è h t n e r pa s e l e d è c é r p et . s t n e argum

Généralités, éléments de base

Fonctions arithmétiques élémentaires Présentation des opérations arithmétiques élémentaires  L'addition :  (+ … …)  La soustraction :  (- … …)  La multiplication :  (* … …)  La division :  (/ … …)

Généralités, éléments de base

Fonctions arithmétiques élémentaires Exemples FONCTIONS ?(+

2

?(-

13

3)

?(* 5

7

?(/

= 5 2)

11) 15

RESULTAT

3)

?(+ (* 5 4) (* 2 3))

= 4 = 55 = 5 = 26

Généralités, éléments de base

Les fonctions primitives

 QUOTE

 CAR

 CDR

 CONS

 APPEND

Généralités, éléments de base

Les fonctions primitives

QUOTE Empêche l’évaluation de l'expression symbolique fournie en argument. Retourne l’expression non évaluée. Exemple: ? (quote (2 + 3)) = (2 + 3)

Généralités, éléments de base

Les fonctions primitives Appel de la fonction QUOTE

Nom de la fonction

(quote <argument>) Argument

Généralités, éléments de base

Les fonctions primitives Exemple FONCTION quote

RESULTAT

?(quote (+ 2 3))

= (+ 2 3)

? ‘(+ 2 3 4)

= (+ 2 3 4)

?(a b c)

**eval: fonction indéfinie: a

?′(- 5 3)

= (- 5 3)

?′(* 2 3 2)

= (* 2 3 2)

?′(/ 21 7)

= (/ 21 7)

?(/ 21 7)

= 3

Généralités, éléments de base

Les fonctions primitives

CAR Extrait le premier élément d’une liste. Celui-ci peut être un atome ou une liste.

Généralités, éléments de base

Les fonctions primitives Appel de la fonction CAR

Nom de la fonction

(car <argument>) Argument L'argument doit être une liste

Généralités, éléments de base

Les fonctions primitives Exemple FONCTION car

RESULTAT

?(car (a b c))

** eval : fonction indefinie : a

?(car '(a b c))

= a

?(car (+ 2 3 4))

** car : l'argument n'est pas une liste : 9

?(car '(- 5 3))

= -

?(car '(2 3 1))

= 2

?(car '(() 21))

= () ou NIL

? car '(12 9 3)

** eval : variable indéfinie : car

Généralités, éléments de base

Les fonctions primitives

CDR Retourne une liste privée de son premier élément.

Généralités, éléments de base

Les fonctions primitives Appel de la fonction CDR

Nom de la fonction

(cdr <argument>) Argument L'argument doit être une liste.

Généralités, éléments de base

Les fonctions primitives Exemple FONCTION cdr

RESULTAT

?(cdr '(+ 2 3))

= (2 3)

?(cdr '(14 ()))

= (())

?(cdr '((2 3) 4))

= (4)

?(cdr (- 5 3))

** cdr : l'argument n'est pas une liste : 2

?(cdr '(3 atomes seuls))

= (atomes seuls)

?(cdr '(2 (3 4)))

= ((3 4))

?(cdr '(12))

= ()

Généralités, éléments de base

Les fonctions primitives Les fonctions CAR et CDR peuvent être imbriquées c’est à dire appliquées successivement sur une liste

 (CAR (CDR <liste>))

 (CAR (CDR (CDR <liste> ))) <liste>)

 (CADR <liste>)

 (CADDR

 (CAR (CDR (CAR (CDR <liste>))))  (CADADR <liste>)

Généralités, éléments de base

Les fonctions primitives Appel de la fonction CADR

Nom de la fonction imbriquée

(cadr <argument>) ↔ (car (cdr <argument>)) L'argument doit être une liste.

Généralités, éléments de base

Les fonctions primitives

Truc

… s e c u t s a t e s

e r i l e Afin d e n u t n e m e t c corre e d n o i t a c i r b im , s n o i t c fon r a p z e c n e m m co n e e t i r c s n i celle ! r u e d profon

Généralités, éléments de base

Les fonctions primitives

CADR Permet d'extraire le second élément de la liste fournie en argument. Exemple: (cadr ‘(a b c)) = (car (cdr ‘(a b c))) = (car ‘(b c)) = b

Généralités, éléments de base

Les fonctions primitives

CADDR Permet d'extraire le troisième élément de la liste fournie en argument. Exemple: (car (cdr (cdr ‘(a b c)))) = (car (cdr ‘(b c))) = (car ‘(c)) = c

Généralités, éléments de base

Les fonctions primitives Exemples FONCTIONS

RESULTAT

?(cadr ′(a b c d))

= b

?(caddr ′(a b c d))

= c

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

= (c)

?(cddr ′(a b c d))

= (c d)

?(cddar ′((a b c d) (e) f))

= (c d)

?(cadar ′((a b c) d e))

= b

Généralités, éléments de base

Les fonctions primitives

CONS Ajoute un élément en tête d’une liste

Généralités, éléments de base

Les fonctions primitives Appel de la fonction CONS

Nom de la fonction

(cons <arg 1> <arg 2>) Arguments Le nombre d'arguments est fixe et égal à deux.

Généralités, éléments de base

Les fonctions primitives Exemple FONCTION cons

RESULTAT

?(cons ‘a '(b c))

= (a b c)

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

= ((a b) c d)

?(cons '(a b c))

**cons : mauvais nombre d'arguments : 2

?(cons ‘a ‘b)

= (a.b)

?(cons ‘a ())

= (a)

?(cons '(a b) (12))

**eval : fonction indefinie : 12

?(cons ‘a (+ 20 (* 12 30)))

= (a.380)

Généralités, éléments de base

Les fonctions primitives

APPEND Permet de concaténer les listes transmises en argument.

Généralités, éléments de base

Les fonctions primitives Appel de la fonction APPEND

Nom de la fonction

(append <arg 1> <arg 2> <arg n>) Arguments

Généralités, éléments de base

Les fonctions primitives Exemple FONCTION append

RESULTAT

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

= (a b c d)

?(append '(a) '(b c))

= (a b c)

?(append () '(a b c))

= (a b c)

?(append '(a b) ())

= (a b)

?(append '(a) '380)

= (a . 380)

?(append ‘a '(380))

= (380)

?(append '(a) '(380))

= (a 380)

Généralités, éléments de base

Les prédicats Quelques prédicats usuels:  ATOM  CONSP  NULL  EQUAL  NUMBERP  < ou > ou <= ou >=

Généralités, éléments de base

Les prédicats

ATOM Teste si l'argument est un atome. Retourne t (ou vrai) si ce test est vérifié, ( ) dans le cas contraire.

Généralités, éléments de base

Les prédicats Appel de la fonction ATOM

Nom de la fonction (atom <argument>) Argument

Généralités, éléments de base

Les prédicats

CONSP Teste si l'expression est une liste. Retourne l'expression si le test est vérifié, ( ) dans le cas contraire.

Généralités, éléments de base

Les prédicats Appel de la fonction CONSP

Nom de la fonction (consp <argument>) Argument

Généralités, éléments de base

Les prédicats

NULL Teste si l'expression est égale à ( ). Retourne t (vrai) si le test est vérifié, ( ) dans le cas contraire.

Généralités, éléments de base

Les prédicats Appel de la fonction NULL

Nom de la fonction (null <argument>) Argument

Généralités, éléments de base

Les prédicats

EQUAL Vérifie l’égalité de ses deux arguments. Retourne t (vrai) si le premier argument est égal au second, ( ) (ou NIL) dans le cas contraire.

Généralités, éléments de base

Les prédicats Appel de la fonction EQUAL

Nom de la fonction (equal <arg1> <arg2>) Argument

Généralités, éléments de base

Les prédicats

NUMBERP Teste si l'argument est un nombre. Retourne le nombre si le test est vérifié, ( ) (ou NIL) dans le cas contraire.

Généralités, éléments de base

Les prédicats Appel de la fonction NUMBERP

Nom de la fonction (numberp <argument>) Argument

Généralités, éléments de base

Les prédicats

< ou > ou <= ou >= Compare les arguments transmis, par rapport aux critères d'infériorité ou de supériorité. Retourne le premier argument si le critère est vérifié, ( ) (ou NIL) dans le cas contraire.

Généralités, éléments de base

Les prédicats Appel des fonctions <, >, <=, >=

Nom de la fonction

(< <arg1> <arg2>... <arg n>) Arguments

Généralités, éléments de base

Les prédicats Exemples FONCTION

RESULTAT

?(atom ‘pierre)

= t

?(consp '(une liste))

= (une liste)

?(null ())

= t

?(equal‘(a b)‘(a (b)))

= ()

?(equal '(a (b)) '(a (b)))

= t

?(numberp ‘a)

= ()

?(numberp 216)

= 216

Généralités, éléments de base

Fonctions d'affectation et d'évaluation

 SETQ

 LET

Généralités, éléments de base

Fonctions d'affectation et d'évaluation

SETQ Affecte aux symboles la valeur de l'évaluation des expressions. Les symboles conservent la valeur des expressions après l'appel.

Généralités, éléments de base

Fonctions d'affectation et d'évaluation Appel de la fonction SETQ

Nom de la fonction (setq <symbole1> ... <symbole n> ) Arguments

Généralités, éléments de base

Fonctions d'affectation et d'évaluation Exemples (ATTENTION, exercices chaînés) FONCTION setq

RESULTAT

?(setq a 3)

= 3

?(+ a 6)

= 9

?(setq b (+ 3 4))

= 7

?(setq c (+ a b))

= 10

?(setq x 2 y 3)

= 3

?(* x y)

= 6

Généralités, éléments de base

Fonctions d'affectation et d'évaluation

LET Retourne la valeur d’une fonction dont les variables ont des valeurs locales à LET. Exemple : ( let ( (a 2) (b 3) ) (+ a b) ) = 5

Généralités, éléments de base

Fonctions d'affectation et d'évaluation Forme générale de la fonction LET

Nom de la fonction interne à LET

(let (<symb1 val1>… <symb n val n>) fonction) Liste des paires variable-valeur

Généralités, éléments de base

Fonctions d'affectation et d'évaluation Exemple (ATTENTION, exercices chaînés) FONCTION let

RESULTAT

? a

= 13

? b

= 27

?(let ((a 5) (b 8)) (* a b))

= 40

? a

= 13

? b

= 27

?(let((a (+ 2 3)) (b (+ 4 6))) (* a b))

= 50

Généralités, éléments de base

Représentation graphique des listes MODELISATION des ARBRES : Rappel

1

Profondeur 0.

2

Profondeur 1.

3

Profondeur 2.

4

Racine.

5

Sommet.

6

Feuille.

7

Arête.

4

1 2

5

3

7 6

Généralités, éléments de base

Représentation graphique des listes MODELISATION d'une liste à 1 niveau : (A B)  Profondeur 0 :  ()  Profondeur 1 :  A  B A

B

Généralités, éléments de base

Représentation graphique des listes MODELISATION d'une liste à 2 niveaux : ( ( 1 2 3 ) B )  Profondeur 0 :  ()  Profondeur 1 :  ()

(

 B

)

B

 Profondeur 2 :  1  2  3

1

2

3

Généralités, éléments de base

Représentation graphique des listes MODELISATION d'une liste à 2 niveaux : ((A B) (C D) (E F))  Profondeur 1 :  ()  ()  ()  Profondeur 2 :  A  B  C  D  E  F

A

B

C

D

E

F

Généralités, éléments de base

Représentation graphique des listes MODELISATION d'une liste complexe : ((( A )( B )( C )) G ((((( D E )) F ) H )))  Profondeur 1 : G

0

 Profondeur 3 :  A  B  C

1 2 3

 H  Profondeur 4 : F  Profondeur 6 :  D  E

G

A

B

C

H

4

F

5 6

D

E

Généralités, éléments de base

Représentation graphique des listes

Truc

… s e c u t s a t e s

s a p e n e d n i f r A u s r u e r r e ' d e faire d s n o i t a c i r b m i s e l , s e s è h t n e r a p ! s e l z e t o r é num

Généralités, éléments de base

Représentation graphique des listes Méthode de modélisation d'une liste complexe : ((( A )( B )( C )) G ((((( D E )) F ) H )))  -1-:  Lecture de la liste de gauche à droite  Avant la première parenthèse, indicer par le chiffre zéro : 0(  -2-:

0 1

G

2 3

A

B

C

H

 À chaque parenthèse 4 ouvrante, indicer en incrémentant : 0(1

F

5

 À chaque parenthèse fermante, indicer en 6 décrémentant : 1)0

D

E

Généralités, éléments de base

Représentation graphique des listes Méthode pour modéliser une liste complexe : (réponse) ( ( ( A 3)2(3 B 3)2(3 C 3)2)1 G 1(2(3(4(5(6 D E 6)5)4 F 4)3 H 3)2)1)0

0 1 2 3

 Contrôle :

0

 On doit retrouver le zéro en fin de ligne, 1 sinon :  erreur de parenthésage

2

 (ou) erreur d'indice

3

G

A

B

C

H

 L'indice indique le 4 niveau des atomes grâce au numéro qui l'encadre  ex.: G, au niveau 1  ex.: A, B, C et H, au niveau 3

F

5 6

D

E

Généralités, éléments de base

Représentation graphique des listes 1

Liste initiale : (A (B C) D E)

2

Fonction CAR appliquée à la liste initiale.

3

Fonction CDR appliquée à la liste initiale.

4

La fonction CAR a extrait le premier élément de la liste.

5

La fonction CDR a extrait le reste de la liste en une liste.

6

(B C) est le second élément de la liste initiale.

7 8

D est le troisième élément de la liste initiale. E est le quatrième élément de la liste initiale.

1

(A (B C) D E)

2

3

(car ‘(A(BC)DE))

(cdr ‘(A(BC)DE))

A

( (B C) D E)

4

5 6

8 7

Généralités, éléments de base

Représentation graphique des listes Arbre complet de la liste (A (B C) D E) (A (B C) D E)

A

((B C) D E)

(B C)

(D E)

B

(C)

D

(E)

C

NIL

E

NIL

Généralités, éléments de base

Les fonctions d'entrée/sortie

 READ

 PRINT

 PRINCH

 TERPRI

Généralités, éléments de base

Les fonctions d'entrée/sortie

READ Lit l'expression suivante de type quelconque (atome ou liste) sur le flux d'entrée courant. Retourne la valeur de l'expression entrée.

Généralités, éléments de base

Les fonctions d'entrée/sortie Appel de la fonction READ

Nom de la fonction (read) Aucun argument

Généralités, éléments de base

Les fonctions d'entrée/sortie

PRINT Edite dans le tampon de sortie les différentes expressions transmises à la fonction. L'appel sans argument vide le tampon et commence une nouvelle ligne (retourne NIL).

Généralités, éléments de base

Les fonctions d'entrée/sortie Appel de la fonction PRINT

Nom de la fonction (print <arg1> <arg n>) Arguments

Généralités, éléments de base

Les fonctions d'entrée/sortie

PRINCH Edite un certain nombre de fois le caractère transmis à la fonction.

Généralités, éléments de base

Les fonctions d'entrée/sortie Appel de la fonction PRINCH

Nom de la fonction (princh <nombre>) Caractère

Nombre de répétitions

Généralités, éléments de base

Les fonctions d'entrée/sortie TERPRI Provoque l'impression du tampon de sortie. L'appel sans argument vide le tampon et commence une nouvelle ligne (retourne NIL). Dans le cas de la présence d'un argument, celui-ci correspond au nombre de sauts de ligne à appliquer après impression.

Généralités, éléments de base

Les fonctions d'entrée/sortie Appel de la fonction TERPRI

Nom de la fonction (terpri <nombre>) Argument

Généralités, éléments de base

Les fonctions d'entrée/sortie Exemple (ATTENTION, exercices chaînés) FONCTIONS

RESULTAT

?(setq a (read))

?

?le_lisp

= le_lisp

? a

= le_lisp

?(print "lisp")

lisp

?(print)

= ()

?(princh '-' 12)

------------= -

?(terpri 2)

= t

après un saut de ligne

après 2 sauts de ligne

Généralités, éléments de base

L’environnement de programmation  Editeur vidéo pleine page (nom: PEPE ) Fonction d’appel de PEPE: Ê (Ctrl E) ou: (pepe <nom du fichier> ou (pepe (pretty <nom du fichier>)) La fonction PRETTY imprime les fonctions « joliment ».  (LOAD <nom du fichier>) charge le fichier nommé  Fonction STEP: suivi pas à pas du déroulement du programme  Fonction TRACE: suivi global du déroulement du programme  (TYCLS) pour effacer l'écran  (END) pour quitter l'interpréteur  PEPEHELP.LL (F1) affiche à l’écran les fonctions de l’éditeur

Généralités, éléments de base

Pause-réflexion sur cette 1ère partie Avez-vous des questions ?

Programmation Fonctionnelle - Le Lisp -

Les structures de contrôle

Les structures de contrôle

Plan de la partie Voici les chapitres que nous allons aborder:

 Les opérations de sélection  La récursivité  Fonctions récursives sur les ensembles  L’itération

Les structures de contrôle

Les opérations de sélection

 IF (sélectionne une réponse suite à une condition)

 COND (composée de plusieurs IF emboîtés)

Les structures de contrôle

Les opérations de sélection Appel de la fonction IF

Nom de la fonction

Action pour condition vraie

(if (condition) (alors_action1) (sinon_action2)…. …(sinon_action n)) Condition à évaluer

Actions pour condition fausse

Les structures de contrôle

Les opérations de sélection Structure de la fonction COND

(cond vrai

((test1) --------------------->(action1)) faux

vrai

((test 2) --------------------->(action2)) faux

. . ( T

vrai

-------------------->(actions par défaut)))

Les structures de contrôle

Les opérations de sélection Exemple (ATTENTION, exercices chaînés) FONCTIONS

RESULTAT

?(if (numberp 1) '(un nombre)

= (un nombre)

'(pas un nombre)) ?(if (numberp 'A) '(un nombre)

= (pas un nombre)

'(pas un nombre)) ?(cond ((numberp 1) '(un nombre))

= (un nombre)

(T '(pas un nombre))) ?(cond ((numberp 'A) '(un nombre)) (T '(pas un nombre)))

= (pas un nombre)

Les structures de contrôle

La récursivité La récursivité  Concept fondamental :

 en mathématique :  relation de récurrence

 en informatique :  procédures récursives

Les structures de contrôle

La récursivité Le principe de la récursivité en algorithmique

 Fonction qui s’appelle elle-même

 Appels de plus en plus « simples »

 Solution directe pour le dernier appel

 Respect de la condition d’arrêt

Les structures de contrôle

La récursivité Correspondance entre les modèles, Exemple : la factorielle  Définition récurrente :  n! = n(n - 1)! pour n >= 1 avec 0! = 1  Algorithme récursif:  SI n = 0 ALORS réponse = 1 SINON réponse = n * fact (n - 1)  Programme LISP: (defun fact (n) (cond ((= n 0) 1) (t (* n (fact (- n 1)) ) ) )

Les structures de contrôle

La récursivité Déroulement de la fonction pour : Factorielle(3) ? (fact 3) ---- > = 6

E M P I L E R

3 * fact( 2 )

3*2=6

2 * fact( 1 )

2*1=2

1 * fact( 0 )

1*1=1

=1

Retour de la Pile

D E P I L E R

Les structures de contrôle

La récursivité Autre exemple de fonction récursive :  MEMBER : teste si un élément est présent dans une liste (defun member (x liste) (cond ((null liste) ()) ((equal (car liste) x) liste) (t (member x (cdr liste) ) ) ) )

FONCTION member

RESULTAT

?(member 'a '(b d a f g))

= (a f g)

?(member '3 '(2 5 9))

= ()

Les structures de contrôle

Fonctions récursives sur les ensembles Autres exemples de fonctions récursives :  ENSEMBLE : teste si une liste est un ensemble (pas de doublons) (defun ensemble (liste) (cond ((null liste) t) ((member (car liste) (cdr liste)) ()) (t (ensemble (cdr liste) ) ) ) )

FONCTION ensemble

RESULTAT

?(ensemble '(a b c d e f g))

= t

?(ensemble '(1 2 (1 2 3) 2 (3 4)))

= ()

Les structures de contrôle

Fonctions récursives sur les ensembles Autres exemples de fonctions récursives :  INCLUS : teste si tous les éléments d'une liste se trouvent dans une autre (defun inclus (liste1 liste2) (cond ((null liste1) t) ((member (car liste1) liste2) (inclus (cdr liste1) liste2)) (t ()) ) )

FONCTION inclus

RESULTAT

?(inclus '(a b c) '(a c f b g))

= t

?(inclus '(a b c) '(a c f g))

= ()

?(inclus '(a b c) '(a c f b g a))

= ()

Les structures de contrôle

Fonctions récursives sur les ensembles Autres exemples de fonctions récursives :  COMPARE : teste l'égalité de deux ensembles ?(defun compare (liste1 liste2) (if (inclus liste1 liste2) (inclus liste2 liste1) ) )

FONCTION compare

RESULTAT

?(compare '(1 2 3) '(3 1 2))

= t

?(compare '(1 2 3) '(1 2 4))

= ()

?(compare '(a) 'a)

= ()

Les structures de contrôle

Fonctions récursives sur les ensembles Autres exemples de fonctions récursives :  UNIQUE : transforme une liste en un ensemble (sans doublons) ?(defun unique (liste) (cond ((null liste) ()) ((member (car liste) (cdr liste)) (unique (cdr liste))) (t (cons (car liste) (unique (cdr liste)))) ) )

FONCTION unique

RESULTAT

?(unique '(a b c a b d e))

= (c a b d e)

?(unique '(1 3 4 9))

= (1 3 4 9)

?(unique '(a b c a c))

= (b a c)

Les structures de contrôle

Fonctions récursives sur les ensembles Autres exemples de fonctions récursives :  UNION : créé un ensemble constitué des éléments de 2 listes

?(defun union (liste1 liste2) (unique (append liste1 liste2)) )

FONCTION union

RESULTAT

?(union '(1 3 5) '(1 3 7))

= (5 1 3 7)

?(union '(a b) '(c d e))

= (a b c d e)

?(union '(1 3 5) '(6 3 1))

= (5 6 3 1)

Les structures de contrôle

Fonctions récursives sur les ensembles Autres exemples de fonctions récursives :  INTER : créé un ensemble constitué des éléments communs ?(defun inter (liste1 liste2) (cond ((null liste1) ()) ((member (car liste1) liste2) (cons (car liste1) (inter (cdr liste1) liste2))) (t (inter (cdr liste1) liste2)) ) )

FONCTION inter

RESULTAT

?(inter '(1 2 3) '(4 5 6))

= ()

?(inter '(a b c) '(d e f a))

= (a)

?(inter '(a b c) '(a e i c o))

= (a c)

Les structures de contrôle

L’itération Fonctions itératives:

 PROG..GO..RETURN  WHILE

Syntaxe de PROG: (prog <liste> <S-expression1>…..<S-expression n>)

Syntaxe de GO: (go )

Syntaxe de RETURN: (return <S-expression>)

Les structures de contrôle

L’itération Exemple 1: la puissance p d’un nombre n ?(defun puissance (n p) (prog (resultat) (setq resultat 1) depart (setq resultat (* n resultat)) (setq p (- p 1)) (if (= p 0) (return resultat) (go depart) ) ) )

FONCTION puissance ?(puissance 3 2)

RESULTAT = 9

Les structures de contrôle

L’itération Exemple 2: dernier élément d’une liste

?(defun dernier (liste) (prog () encore (cond ((null (cdr liste)) (return (car liste))) (t (setq liste (cdr liste))) ) (go encore) ) )

FONCTION dernier ?(dernier '(a b c d))

RESULTAT = d

Les structures de contrôle

L’itération Exemple 3: inversion d’une liste

?(defun reverse (liste) (prog (x) (setq x ()) hello (cond ((null liste) (return x)) ((atom liste) (return (cons liste ()))) (t (setq x (cons (car liste) x) liste(cdr liste))) ) (go hello) ) )

FONCTION reverse ?(reverse '(a b c d)

RESULTAT = (d c b a)

Les structures de contrôle

L’itération Exemple 4: la variante itérative de la factorielle

?(defun factorielle (n) (prog (resultat) (setq resultat 1) toujours (cond ((= 0 n) (return resultat)) ) (setq resultat (* resultat n) n (- n 1)) (go toujours) ) )

FONCTION factorielle ?(factorielle '(3))

RESULTAT = 6

Les structures de contrôle

L’itération Syntaxe de WHILE

(WHILE (condition) (S-expression1) (S-expression2) …………………. (S-expression n) ) WHILE évalue les S-expressions TANT QUE la condition retourne VRAI

Les structures de contrôle

L’itération Exemple: affichage du décompte d’un nombre n ?(defun decompte (n) (while (> n 0) (print n) (decr n) ) )

FONCTION decompte ?(decompte 4)

RESULTAT 4 3 2 1 = ()

Les structures de contrôle

Pause-réflexion sur cette 2ème partie Avez-vous des questions ?

Programmation Fonctionnelle - Le Lisp -

Fonctions complexes

Fonctions complexes

Plan de la partie Voici les chapitres que nous allons aborder:

 Les fonctionnelles  Les fonctions anonymes  Les macro fonctions

Fonctions complexes

Les fonctionnelles

FONCTIONNELLE Fonction d'ordre supérieur qui prend les fonctions comme argument et les applique sur des ensembles de données.

Fonctions complexes

Les fonctionnelles  (APPLY < f > < liste >)  retourne la valeur de l'application de la fonction < f > sur la liste < liste > FONCTION apply

RESULTAT

?(apply '+ '(2 3 4))

= 9

?(apply 'append '((a b) (c d)))

= (a b c d)

?(apply '/ '(6 2))

= 3

?(apply 'modulo '(6 2))

= 0

Fonctions complexes

Les fonctionnelles  MAPCAR : fonction qui retourne la liste formée des applications de la fonction transmise en premier argument, à tous les éléments de la liste placée en second argument. (defun mapcar (fonction liste) (if (null liste) () (cons (apply fonction (list (car liste))) (mapcar fonction (cdr liste)) ) ) )

FONCTION mapcar ?(mapcar '1+ '(1 2 3 4 5))

RESULTAT = (2 3 4 5 6)

Fonctions complexes

Les fonctions anonymes (LAMBDA <paramètres> )

 La fonction anonyme LAMBDA retourne l’évaluation d’ une avec des <paramètres> qui prennent des . En dehors de LAMBDA les paramètres sont déliés. FONCTION lambda

RESULTAT

?((lambda (x y) (* x y)) 2 3)

= 6

?((lambda (x y) (cons y x)) 'a 'b)

= (b . a)

?(setq a '(lambda (x y) (* x y)))

= (lambda (x y) (* x y))

?(apply a '(2 3))

= 6

?(mapcar (lambda (x) (* x x x) '(2 3 4 5))

= (8 27 64 125)

Fonctions complexes

Les macro fonctions  Une macro est évaluée en deux étapes. La première correspond à une phase d'expansion (ou de traduction) en une forme évaluable en LISP. Dans la deuxième étape cette forme est évaluée.  Voici un exemple qui transforme la structure IF en une macro. (dmd if(test vrai faux) (list 'cond (list test vrai) (list 't faux) ) )

FONCTION ?(if (< a 0) (1- a) (1+ a))

RESULTAT = (cond ((< a 0) (1- a)) (t (1+ a)) )

Fonctions complexes

Les macro fonctions  Le caractère "backquote" ou ` : construit une liste sans évaluer ses éléments. L'effet du "backquote" est annulé grâce à la "virgule" ou à l'association « virgule-arobas ».

FONCTION

RESULTAT

?`(a b c d)

= (a b c d)

?(setq a `(toto riri))

= (toto riri)

? `( a b ,a a)

= (a b (toto riri) a)

? `(a b ,@a a)

= (a b toto riri a)

Fonctions complexes

Les macro fonctions Les macro fonctions EMPILE et DEPILE (dmd empile (liste var) `(setq ,liste (cons ,var ,liste)) ) (dmd depile (liste) `(let ((res (car ,liste))) (setq ,liste (cdr ,liste)) ) )

FONCTION

RESULTAT

?(setq a `(toto riri))

=(toto riri)

?(empile a 'fifi)

=(fifi toto riri)

?(empile a 'truc)

=(truc fifi toto riri)

?a

=(truc fifi toto riri)

?(depile a)

= truc

?a

= (fifi toto riri)

Fonctions complexes

Les macro fonctions Les macro caractères  Caractères spéciaux auxquels sont associées des fonctions.  Fonctionnent en deux temps comme les macro fonctions: - Génération de code LISP - Exécution

FONCTION dmc

RESULTAT

?(dmc |$| () '1euro)

= $

? '($ $)

= (1euro 1euro)

(dmc |$| () (eval (read)))

= $

'(1 2 3 $ (+ 2 3) 6)

= (1 2 3 5 6)

Fonctions complexes, opérations symboliques

Pause-réflexion sur cette 3ème partie Avez-vous des questions ?

Programmation fonctionnelle - Le Lisp -

Opérations symboliques

Opérations symboliques

Plan de la partie Voici les chapitres que nous allons aborder:  Dérivation des expressions algébriques  Exploration des arborescences  Explorer un espace d’états  Raisonnement symbolique

Opérations symboliques

Dérivation des expressions algébriques  La dérivation d'expressions algébriques sera illustrée dans le cas des expressions ne contenant que des additions et des multiplications*.

 Le programme de dérivation est complété par des programmes de simplification**: - SIMPLIF_PLUS pour l'addition et SIMPLIF_MULT pour la multiplication. -"SIMPLIF" pour simplifier les parenthèses intérieures. - SIMPLIFIER, va en profondeur avec SIMPLIF jusqu'à ce que l'on arrive à une forme irréductible.

Opérations symboliques

Dérivation des expressions algébriques Fonction : DERIV (defun deriv (exp var) (cond ((numberp exp) 0) ((atom exp) (if (equal exp var) 1 0)) ((equal (car exp) '+) (list '+ (deriv (cadr exp) var) (deriv (caddr exp) var))) ((equal (car exp) '*) (list '+ (list '* (cadr exp) (deriv (caddr exp) var)) (list '* (deriv (cadr exp) var) (caddr exp)))) (t 'bof) ) )

FONCTION deriv

RESULTAT

(deriv '(+ x 3) 'x)

= (+ 1 0)

(deriv '(* x(* x x)) 'x)

= (+(* x(+(* x 1)(* 1 x)))(* 1(* x x)))

Opérations symboliques

Dérivation des expressions algébriques Fonction : SIMPLIF (defun simplif (exp) (cond ((null exp) ()) ((atom exp) exp) ((equal (car exp) '+) (simplif_plus (car exp) (cadr exp) (caddr exp))) ((equal (car exp) '*) (simplif_mult (car exp) (cadr exp) (caddr exp))) (t 'ouf) ) )

FONCTION simplif (simplif '(+ (* x 0) (* y 0)))

RESULTAT = (+ 0 0)

Opérations symboliques

Dérivation des expressions algébriques Fonction : SIMPLIF_PLUS et SIMPLIF_MULT (defun simplif_plus (op A1 A2) (cond ((equal A1 0) (simplif A2)) ((equal A2 0) (simplif A1)) (t (list op (simplif A1) (simplif A2))) ) ) (defun simplif_mult (op A1 A2) (cond ((or (equal A1 0) (equal A2 0)) 0) ((equal A1 1) (simplif A2)) ((equal A2 1) (simplif A1)) (t (list op (simplif A1) (simplif A2))) ) )

Opérations symboliques

Dérivation des expressions algébriques Fonction : SIMPLIFIER  SIMPLIFIER : applique récursivement le processus de simplification jusqu'à l'obtention d'une expression irréductible. (defun simplifier (exp) (let ((dexp (simplif exp))) (if (equal exp dexp) exp (simplifier dexp)) ) ) (defun deriver (exp var) (simplifier (deriv exp var)))

FONCTION simplifier et deriver

RESULTAT

(simplifier '(+ (* x 0) (* y 0)))

= 0

(deriver '(* x (* x 2)) 'x)

= (+ (* x 2) (* x 2))

Opérations symboliques

Exploration des arborescences  L'exploration des structures arborescentes est une technique dont la maîtrise est essentielle en programmation symbolique.  Les arbres (ou arborescences : arbres avec relation d'incidence), sont utiles pour représenter un ensemble d'éléments hiérarchisés*.  L'exploration d'un arbre peut se faire en profondeur ou en largeur. Dans le cas d'une exploration en profondeur, il existe trois types de parcours : préordre, inordre et postordre**.

Opérations symboliques

Exploration des arborescences Soit l'expression : (4 * 3) + (5 * 2) et sa représentation graphique sous forme d’arbre.

+

* 4

* 3

Exploration en profondeur En inordre:fils gauche, noeud, autres fils En préordre:un noeud puis les autres fils En postordre:les fils d’abord, les noeuds ensuite

Exploration en largeur Largeur :on examine les noeuds du même niveau

5

2 Liste d'exploration 4 * 3 + 5 * 2 + * 4 3 * 5 2 4 3 * 5 2 * +

Liste d'exploration + * * 4 3 5 2

Opérations symboliques

Exploration des arborescences Représentation en Le_LISP de l’arbre ci-dessous

+ *

*

4

3

(setq arbre '(+ (* (4) (3) ) (* (5) (2) ) ) )

5

2

Opérations symboliques

Exploration des arborescences Exploration en préordre de l’arbre ci-dessous

+

* 4

* 3

5

2

(defun preordre (fonction arbre) (when arbre (apply fonction (list (car arbre))) (preordre fonction (cadr arbre)) (preordre fonction (caddr arbre)) ) )

Exploration en profondeur ? (preordre ‘prin arbre)

Liste d'exploration + * 4 3 * 5 2

Opérations symboliques

Exploration des arborescences Exploration en INORDRE de l’arbre ci-dessous:

+

* 4

* 3

5

2

(defun inordre (fonction arbre) (when arbre (inordre fonction (cadr arbre)) (apply fonction (list (car arbre))) (inordre fonction (caddr arbre)) ) )

Exploration en profondeur ? (inordre ‘prin arbre)

Liste d'exploration 4 * 3 + 5 * 2

Opérations symboliques

Exploration des arborescences Exploration en POSTORDRE de l’arbre ci-dessous

+

* 4

* 3

5

2

(defun postordre (fonction arbre) (when arbre (postordre fonction (cadr arbre)) (postordre fonction (caddr arbre)) (apply fonction (list (car arbre))) ) )

Exploration en profondeur ? (postordre ‘prin arbre):

Liste d'exploration 4 3 * 5 2 * +

Opérations symboliques

Exploration des arborescences LARGEUR sur l'expression : (4 * 3) + (5 * 2)

+

* 4

* 3

5

2

(defun largeur (fonction arbre) (let ((file (list arbre))) (while file (setq file (append file (cdar file))) (apply fonction (list (caar file))) (depile file) ) ) ) (dmd depile (l) `(let ((res (car l))) (setq ,l (cdr ,l)) res ) )

Exploration en largeur ? (largeur ‘prin arbre)

Liste d'exploration + * * 4 3 5 2

Opérations symboliques

Exploration des arborescences Exemple d’arborescence: une classification hiérarchique (setq arbre '(chose (etre_vivant (plante (arbre (pin) (chene) ) (fleur) ) (animal (insecte) (reptile) (mammifere (chien) (singe) (etre_humain) ) ) ) (inanime (naturelle (nuage) (roche) (artificielle (voiture) (maison) (ordinateur)

) ) ) )

Opérations symboliques

Exploration des arborescences chose

etre_vivant

plante

inanimé

animale

naturelle

artificielle

arbre fleur insecte reptile mammifère nuage roche voiture maison ordinateur

pin

chene

chien

singe

etre_humain

Opérations symboliques

Explorer un espace d’états  Un espace d’états est une représentation codée d’un problème réel.  Trouver la solution du problème consiste à trouver le chemin qui relie l'état initial à l'état final (le but).  Le passage d'un état à l'autre se fait par l'application d'opérateurs spécifiques à chaque type de problème.  Dans le cas présent le problème consiste à trouver la sortie d'un labyrinthe représenté sous la forme d'un tableau de symboles.  Le programme doit permettre de marquer le chemin parcouru, de sortir des cul-de-sac et de marquer le chemin correct.

Opérations symboliques

Explorer un espace d’états  Voici le labyrinthe sur lequel nous allons dérouler le programme  Le tableau comporte seulement 9 cases afin de faciliter la compréhension de l’algorithme de recherche de la sortie.Le programme complet sera donné en TP  L'entrée se trouve à la case (0,0)  La sortie est marquée par l’atome "fin".

J:0 I: 0 -

1

2

-

$

1

-

$

2

-

- fin

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 0, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

*- -

-

-

$

-

$

- fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 0, J = 1

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* *- -

$

$

- fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 0, J = 2

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * *-

$

$

- fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

I = 0, J = 1

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve (member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

I = 0, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve (member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 1, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * * *- $ $ -

- fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 2, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * * * $ $ *- - fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 2, J = 1

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * *

* *

$

$

*- fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

I = 2, J = 2

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve (member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 2, J = 1

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * *

* *

$

$

o* fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 2, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * * * $ $ o* o fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 1, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

* * * o* $ $ o o fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Explorer un espace d’états Exemple, Le Labyrinthe :

0 1 2

I = 0, J = 0

(de cherche-sortie (I J) (if (equal (tref labyrinthe I J) 'fin) (setq pas-trouve ()) (tset labyrinthe I J '*) (if (and pas-trouve 0 1 2(member (tref labyrinthe I (1+ J)) '((cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '((cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '((cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '((cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) )

o* * * o $ $ o o fin

fin))) fin))) fin))) fin))) )

Opérations symboliques

Pause-réflexion sur cette 4ème partie Avez-vous des questions ?

Programmation Fonctionnelle - Le Lisp -

Résumé du module Typage dynamique des données

Le Lisp : un langage trés puissant basé sur les fonctions

Langage interprété à syntaxe simple

Applications: raisonnement symbolique, résolution de jeux, …

Pas de distinction entre la structure de données et celle du programme

Programmation Fonctionnelle - Le Lisp -

Pour aller plus loin… Si vous voulez approfondir vos connaissances: Publications Eléments d'intelligence artificielle de Farreny et Ghallab

H. FARRENY: Systèmes Expert, (Ed.Cepadues, 1985)

(Ed. Hermes, 1987)

Intelligence artificielle et informatique théorique (2e ed.) (Broché) de J.-M. Alliot, T. Schiex, P. Brisset

512 problèmes corrigés en Pascal, C++, Lisp, Prolog Louis Gacôgne (Ed.Ellipses, 1996))

Félicitations Vous avez suivi avec succès le module de cours n°3 Programmation Fonctionnelle Le Lisp -

Programmation Fonctionnelle - Le Lisp -

Fin

 Examinez à nouveau les principales primitives de ce langage, son fonctionnement récursif omniprésent et les principales approches de résolution abordées durant ce cours.