168
Campus Booster ID : 513 www.supinfo.com Copyright © SUPINFO. All rights reserved Programmation Fonctionnelle - Le Lisp -

02-Programmation Fonctionnelle - Le Lisp

  • Upload
    litig53

  • View
    3.379

  • Download
    2

Embed Size (px)

Citation preview

Page 1: 02-Programmation Fonctionnelle - Le Lisp

Campus Booster ID : 513

www.supinfo.com

Copyright © SUPINFO. All rights reserved

Programmation Fonctionnelle- Le Lisp -

Page 2: 02-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

Contact:[email protected]

SUPINFONE: 1 317

Marianne BELIS

Programmation Fonctionnelle - Le Lisp -

Page 3: 02-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)

Publication: « La simulation des flux de transports de marchandises en agglomération » (2002).

Contact:[email protected] SUPINFONE: 1 50087

Arnaud CUEILLE

Programmation Fonctionnelle - Le Lisp -

Page 4: 02-Programmation Fonctionnelle - Le Lisp

Objectifs de ce module

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.

En suivant ce module vous allez:

Programmation Fonctionnelle - Le Lisp -

Page 5: 02-Programmation Fonctionnelle - Le Lisp

Plan du module

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

Les structures de contrôle.

Fonctions complexes.

Opérations symboliques.

Voici les parties que nous allons aborder:

Programmation Fonctionnelle - Le Lisp -

Page 6: 02-Programmation Fonctionnelle - Le Lisp

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

Programmation Fonctionnelle - Le Lisp -

Page 7: 02-Programmation Fonctionnelle - Le Lisp

Plan de la partie

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

Voici les chapitres que nous allons aborder:

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

Page 8: 02-Programmation Fonctionnelle - Le 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***

Origine du langage Lisp.

John Mc CARTHY

PrésentationGénéralités, éléments de base

Page 9: 02-Programmation Fonctionnelle - Le Lisp

FORTRAN PL/I

1957 1960 1964 1966

Historique des principaux langages, dont le Lisp.

BASICCOBOL

LISP

1958

ALGOL

1970 1972

LOGO

B PASCAL

PROLOG

PrésentationGénéralités, éléments de base

Page 10: 02-Programmation Fonctionnelle - Le Lisp

LISP 1.5 CommonLISP

1960 1967 1975 1977

Historique des dialectes Lisp .

VLISPSCHEME

INTERLISP

1966

MACLISP

1984

LE_LISP

AutoLISP

1985 1986

EULISP

PrésentationGénéralités, éléments de base

Page 11: 02-Programmation Fonctionnelle - Le 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é***

Spécificités du langage fonctionnel Lisp

PrésentationGénéralités, éléments de base

Page 12: 02-Programmation Fonctionnelle - Le Lisp

Lecture d’une expression

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

READ-EVAL-PRINT

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

Evaluation de l’expression

PrésentationGénéralités, éléments de base

Impression du résultat

Page 13: 02-Programmation Fonctionnelle - Le Lisp

Les atomes

Les listes

Les paires pointées

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

Les expressions symboliquesGénéralités, éléments de base

Page 14: 02-Programmation Fonctionnelle - Le Lisp

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

Les expressions symboliquesGénéralités, éléments de base

Page 15: 02-Programmation Fonctionnelle - Le Lisp

Les noms :

Un caractère

ex: a

Suite de caractères sans séparateur

ex: supinfo

Les nombres :

Nombres positifs

Nombres négatifs

La forme que peuvent prendre les atomes.

Les expressions symboliquesGénéralités, éléments de base

Page 16: 02-Programmation Fonctionnelle - Le Lisp

a

B

ATOME

Pierre

Atome-Long

unseulatomelong

128

-345

*86

49CE+

Exemples d'atomes

Les expressions symboliquesGénéralités, éléments de base

Page 17: 02-Programmation Fonctionnelle - Le Lisp

ATTENTION !

il existe un

atome

particulier

appelé NIL !

à suivre

Les expressions symboliquesGénéralités, éléments de base

Page 18: 02-Programmation Fonctionnelle - Le Lisp

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

Les expressions symboliquesGénéralités, éléments de base

Page 19: 02-Programmation Fonctionnelle - Le 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)

La liste des séparateurs en LISP

Les expressions symboliquesGénéralités, éléments de base

Page 20: 02-Programmation Fonctionnelle - Le Lisp

ATTENTION !

Il existe un

séparateur

particulier :

le point <.> !

à suivre …

Les expressions symboliquesGénéralités, éléments de base

Page 21: 02-Programmation Fonctionnelle - Le Lisp

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

Les expressions symboliquesGénéralités, éléments de base

Page 22: 02-Programmation Fonctionnelle - Le Lisp

(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

Exemples de listes

Les expressions symboliquesGénéralités, éléments de base

Page 23: 02-Programmation Fonctionnelle - Le Lisp

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)

Les expressions symboliquesGénéralités, éléments de base

Page 24: 02-Programmation Fonctionnelle - Le Lisp

Longueur d'une liste

Profondeur d'une liste

Appel d'une fonction Lisp

Autres notions élémentaires

Les expressions symboliquesGénéralités, éléments de base

Page 25: 02-Programmation Fonctionnelle - Le Lisp

(A B C)

1er élément

2ème élément

3ème élément

Le premier élément est précédé d'une parenthèse.

Le second élément est encadré de séparateurs, ici un espace.

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

Notion de longueur d'une liste : ici, longueur = 3

Les expressions symboliquesGénéralités, éléments de base

Page 26: 02-Programmation Fonctionnelle - Le Lisp

(une (liste (profonde)))

1er niveau

2ème niveau

3ème niveau

Le premier élément (l’atome “une”) est au premier niveau: profondeur 0.

Le second élément (l’atome “liste”) est au second niveau: profondeur 1.

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

Notion de profondeur d'une liste : ici, profondeur = 2

Les expressions symboliquesGénéralités, éléments de base

Page 27: 02-Programmation Fonctionnelle - Le Lisp

( … … … )

Les

parenthèses

sont aussi

utilisées pour

marquer le

début et la fin

de l'appel d'une

fonction.

Les expressions symboliquesGénéralités, éléments de base

Page 28: 02-Programmation Fonctionnelle - Le Lisp

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

Nom de la fonction appelée

Argument n°1

Argument n°2

Argument n°n

Appel d'une fonction

Les expressions symboliquesGénéralités, éléments de base

Page 29: 02-Programmation Fonctionnelle - Le Lisp

(fonction … … )

Le nom de la

fonction est

placé toujours

après la

parenthèse

ouvrante et

précède les

arguments.

Les expressions symboliquesGénéralités, éléments de base

Page 30: 02-Programmation Fonctionnelle - Le Lisp

L'addition :

(+ … …)

La soustraction :

(- … …)

La multiplication :

(* … …)

La division :

(/ … …)

Présentation des opérations arithmétiques élémentaires

Fonctions arithmétiques élémentairesGénéralités, éléments de base

Page 31: 02-Programmation Fonctionnelle - Le Lisp

Exemples

FONCTIONS RESULTAT

?(+ 2 3) = 5

?(- 13 7 2)

?(* 5 11)

?(/ 15 3)

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

= 4

= 55

= 5

= 26

Fonctions arithmétiques élémentairesGénéralités, éléments de base

Page 32: 02-Programmation Fonctionnelle - Le Lisp

QUOTE

CAR

CDR

CONS

APPEND

Les fonctions primitivesGénéralités, éléments de base

Page 33: 02-Programmation Fonctionnelle - Le Lisp

QUOTE Empêche l’évaluation de l'expression symbolique fournie en argument.Retourne l’expression non évaluée.

Exemple:? (quote (2 + 3))= (2 + 3)

Les fonctions primitivesGénéralités, éléments de base

Page 34: 02-Programmation Fonctionnelle - Le Lisp

(quote <argument>)

Nom de la fonction

Argument

Appel de la fonction QUOTE

Les fonctions primitivesGénéralités, éléments de base

Page 35: 02-Programmation Fonctionnelle - Le Lisp

? ‘(+ 2 3 4)

Exemple

FONCTION quote RESULTAT

?(quote (+ 2 3)) = (+ 2 3)

?(a b c)

?′(- 5 3)

?′(* 2 3 2)

?′(/ 21 7)

?(/ 21 7)

= (+ 2 3 4)

= (- 5 3)

= (* 2 3 2)

= (/ 21 7)

= 3

Les fonctions primitivesGénéralités, éléments de base

**eval: fonction indéfinie: a

Page 36: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctions primitivesGénéralités, éléments de base

Page 37: 02-Programmation Fonctionnelle - Le Lisp

(car <argument>)

Nom de la fonction

Argument

Appel de la fonction CAR

L'argument doit être une liste

Les fonctions primitivesGénéralités, éléments de base

Page 38: 02-Programmation Fonctionnelle - Le Lisp

Exemple

FONCTION car RESULTAT

?(car (a b c))** eval : fonction indefinie : a

?(car '(a b c))

?(car (+ 2 3 4))

?(car '(- 5 3))

?(car '(2 3 1))

?(car '(() 21))

? car '(12 9 3)

= a

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

= -

= 2

= () ou NIL

** eval : variable indéfinie : car

Les fonctions primitivesGénéralités, éléments de base

Page 39: 02-Programmation Fonctionnelle - Le Lisp

CDRRetourne une liste privée de son premier élément.

Les fonctions primitivesGénéralités, éléments de base

Page 40: 02-Programmation Fonctionnelle - Le Lisp

(cdr <argument>)

Nom de la fonction

Argument

Appel de la fonction CDR

L'argument doit être une liste.

Les fonctions primitivesGénéralités, éléments de base

Page 41: 02-Programmation Fonctionnelle - Le Lisp

Exemple

FONCTION cdr RESULTAT

?(cdr '(+ 2 3)) = (2 3)

?(cdr '(14 ()))

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

?(cdr (- 5 3))

?(cdr '(3 atomes seuls))

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

?(cdr '(12))

= (())

= (4)

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

= (atomes seuls)

= ((3 4))

= ()

Les fonctions primitivesGénéralités, éléments de base

Page 42: 02-Programmation Fonctionnelle - Le Lisp

(CAR (CDR <liste>)) (CADR <liste>)

(CAR (CDR (CDR <liste> ))) (CADDR <liste>)

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

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

Les fonctions primitivesGénéralités, éléments de base

Page 43: 02-Programmation Fonctionnelle - Le Lisp

(cadr <argument>) ↔ (car (cdr <argument>))

Nom de la fonction imbriquée

Appel de la fonction CADR

L'argument doit être une liste.

Les fonctions primitivesGénéralités, éléments de base

Page 44: 02-Programmation Fonctionnelle - Le Lisp

Trucs et

astuces…

Afin de lire

correctement

une imbrication

de fonctions,

commencez par

celle inscrite en

profondeur !

Les fonctions primitivesGénéralités, éléments de base

Page 45: 02-Programmation Fonctionnelle - Le Lisp

CADRPermet 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

Les fonctions primitivesGénéralités, éléments de base

Page 46: 02-Programmation Fonctionnelle - Le Lisp

CADDRPermet 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

Les fonctions primitivesGénéralités, éléments de base

Page 47: 02-Programmation Fonctionnelle - Le Lisp

Exemples

FONCTIONS RESULTAT

?(cadr ′(a b c d)) = b

?(caddr ′(a b c d))

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

?(cddr ′(a b c d))

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

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

= c

= (c)

= (c d)

= (c d)

= b

Les fonctions primitivesGénéralités, éléments de base

Page 48: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctions primitivesGénéralités, éléments de base

Page 49: 02-Programmation Fonctionnelle - Le Lisp

(cons <arg 1> <arg 2>)

Nom de la fonction

Arguments

Appel de la fonction CONS

Le nombre d'arguments est fixe et égal à deux.

Les fonctions primitivesGénéralités, éléments de base

Page 50: 02-Programmation Fonctionnelle - Le Lisp

Exemple

FONCTION cons RESULTAT

?(cons ‘a '(b c)) = (a b c)

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

?(cons '(a b c))

?(cons ‘a ‘b)

?(cons ‘a ())

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

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

= ((a b) c d)

**cons : mauvais nombre d'arguments : 2

= (a.b)

= (a)

**eval : fonction indefinie : 12

= (a.380)

Les fonctions primitivesGénéralités, éléments de base

Page 51: 02-Programmation Fonctionnelle - Le Lisp

APPENDPermet de concaténer les listes transmises en argument.

Les fonctions primitivesGénéralités, éléments de base

Page 52: 02-Programmation Fonctionnelle - Le Lisp

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

Nom de la fonction

Arguments

Appel de la fonction APPEND

Les fonctions primitivesGénéralités, éléments de base

Page 53: 02-Programmation Fonctionnelle - Le Lisp

Exemple

FONCTION append RESULTAT

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

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

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

?(append '(a b) ())

?(append '(a) '380)

?(append ‘a '(380))

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

= (a b c)

= (a b c)

= (a b)

= (a . 380)

= (380)

= (a 380)

Les fonctions primitivesGénéralités, éléments de base

Page 54: 02-Programmation Fonctionnelle - Le Lisp

ATOM

CONSP

NULL

EQUAL

NUMBERP

< ou > ou <= ou >=

Les prédicats Généralités, éléments de base

Quelques prédicats usuels:

Page 55: 02-Programmation Fonctionnelle - Le Lisp

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

Les prédicats Généralités, éléments de base

Page 56: 02-Programmation Fonctionnelle - Le Lisp

(atom <argument>)

Nom de la fonction

Argument

Appel de la fonction ATOM

Les prédicats Généralités, éléments de base

Page 57: 02-Programmation Fonctionnelle - Le Lisp

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

Les prédicats Généralités, éléments de base

Page 58: 02-Programmation Fonctionnelle - Le Lisp

(consp <argument>)

Nom de la fonction

Argument

Appel de la fonction CONSP

Les prédicats Généralités, éléments de base

Page 59: 02-Programmation Fonctionnelle - Le Lisp

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

Les prédicats Généralités, éléments de base

Page 60: 02-Programmation Fonctionnelle - Le Lisp

(null <argument>)

Nom de la fonction

Argument

Appel de la fonction NULL

Les prédicats Généralités, éléments de base

Page 61: 02-Programmation Fonctionnelle - Le Lisp

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

Les prédicats Généralités, éléments de base

Page 62: 02-Programmation Fonctionnelle - Le Lisp

(equal <arg1> <arg2>)

Nom de la fonction

Argument

Appel de la fonction EQUAL

Les prédicats Généralités, éléments de base

Page 63: 02-Programmation Fonctionnelle - Le Lisp

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

Les prédicats Généralités, éléments de base

Page 64: 02-Programmation Fonctionnelle - Le Lisp

(numberp <argument>)

Nom de la fonction

Argument

Appel de la fonction NUMBERP

Les prédicats

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

Page 65: 02-Programmation Fonctionnelle - Le Lisp

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

Les prédicats Généralités, éléments de base

Page 66: 02-Programmation Fonctionnelle - Le Lisp

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

Nom de la fonction

Arguments

Appel des fonctions <, >, <=, >=

Les prédicats Généralités, éléments de base

Page 67: 02-Programmation Fonctionnelle - Le Lisp

= t

?(numberp ‘a)

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

Exemples

FONCTION RESULTAT

?(atom ‘pierre) = t

?(consp '(une liste))

?(null ())

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

?(numberp 216)

= (une liste)

= t

= 216

Les prédicats Généralités, éléments de base

= ()

= ()

Page 68: 02-Programmation Fonctionnelle - Le Lisp

SETQ

LET

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Page 69: 02-Programmation Fonctionnelle - Le Lisp

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

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Page 70: 02-Programmation Fonctionnelle - Le Lisp

(setq <symbole1> <valeur1>... <symbole n> <valeur n>)

Nom de la fonction

Arguments

Appel de la fonction SETQ

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Page 71: 02-Programmation Fonctionnelle - Le Lisp

Exemples (ATTENTION, exercices chaînés)

FONCTION setq RESULTAT

?(setq a 3) = 3

?(+ a 6)

?(setq b (+ 3 4))

?(setq c (+ a b))

?(setq x 2 y 3)

?(* x y)

= 9

= 7

= 10

= 3

= 6

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Page 72: 02-Programmation Fonctionnelle - Le Lisp

LETRetourne la valeur d’une fonction dont les variables ont des valeurs locales à LET.

Exemple : ( let ( (a 2) (b 3) ) (+ a b) ) = 5

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Page 73: 02-Programmation Fonctionnelle - Le Lisp

(let (<symb1 val1>… <symb n val n>) fonction)

Liste des paires variable-valeur

Forme générale de la fonction LET

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Nom de la fonction interne à LET

Page 74: 02-Programmation Fonctionnelle - Le Lisp

Exemple (ATTENTION, exercices chaînés)

FONCTION let RESULTAT

? a = 13

? b

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

? a

? b

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

= 27

= 40

= 13

= 27

= 50

Fonctions d'affectation et d'évaluationGénéralités, éléments de base

Page 75: 02-Programmation Fonctionnelle - Le Lisp

Profondeur 0.

Profondeur 1.

Profondeur 2.

Racine.

Sommet.

Feuille.

1

2

3

4

5

6

MODELISATION des ARBRES : Rappel

Arête.7

Représentation graphique des listesGénéralités, éléments de base

4

5

1

2

36

7

Page 76: 02-Programmation Fonctionnelle - Le Lisp

Profondeur 0 :

()

Profondeur 1 :

A

B

MODELISATION d'une liste à 1 niveau : (A B)

Représentation graphique des listesGénéralités, éléments de base

BA

Page 77: 02-Programmation Fonctionnelle - Le Lisp

Profondeur 0 :

()

Profondeur 1 :

()

B

Profondeur 2 :

1

2

3

MODELISATION d'une liste à 2 niveaux : ( ( 1 2 3 ) B )

Représentation graphique des listesGénéralités, éléments de base

B( )

1 2 3

Page 78: 02-Programmation Fonctionnelle - Le Lisp

Profondeur 1 :

()

()

()

Profondeur 2 :

A

B

C

D

E

F

MODELISATION d'une liste à 2 niveaux : ((A B) (C D) (E F))

Représentation graphique des listesGénéralités, éléments de base

BA FEDC

Page 79: 02-Programmation Fonctionnelle - Le Lisp

Profondeur 1 : G

Profondeur 3 :

A

B

C

H

Profondeur 4 : F

Profondeur 6 :

D

E

MODELISATION d'une liste complexe :

((( A )( B )( C )) G ((((( D E )) F ) H )))

Représentation graphique des listesGénéralités, éléments de base

G

CA B H

F

ED

0

1

2

3

4

5

6

Page 80: 02-Programmation Fonctionnelle - Le Lisp

Trucs et

astuces…

Afin de ne pas

faire d'erreur

sur les

imbrications de

parenthèses,

numérotez-les !

Représentation graphique des listesGénéralités, éléments de base

Page 81: 02-Programmation Fonctionnelle - Le Lisp

- 1 - :

Lecture de la liste de gauche à droite

Avant la première parenthèse, indicer par le chiffre zéro : 0(

- 2 - :

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

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

Méthode de modélisation d'une liste complexe :

((( A )( B )( C )) G ((((( D E )) F ) H )))

Représentation graphique des listesGénéralités, éléments de base

G

CA B H

F

ED

0

1

2

3

4

5

6

Page 82: 02-Programmation Fonctionnelle - Le Lisp

Contrôle :

On doit retrouver le zéro en fin de ligne, sinon :

erreur de parenthésage

(ou) erreur d'indice

L'indice indique le 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

Méthode pour modéliser une liste complexe : (réponse)

0(1(2(3 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

Représentation graphique des listesGénéralités, éléments de base

G

CA B H

F

ED

0

1

2

3

4

5

6

Page 83: 02-Programmation Fonctionnelle - Le Lisp

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

Fonction CAR appliquée à la liste initiale.

Fonction CDR appliquée à la liste initiale.

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

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

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

1

2

3

4

5

6

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

7

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

Représentation graphique des listes

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

(A (B C) D E)

( (B C) D E)A

(car ‘(A(BC)DE)) (cdr ‘(A(BC)DE))

4

7

8

3

1

2

5

6

Page 84: 02-Programmation Fonctionnelle - Le Lisp

Représentation graphique des listesGénéralités, éléments de base

Arbre complet de la liste (A (B C) D E)

(A (B C) D E)

((B C) D E)

(C)

(D E)

(E)

C

DB

(B C)

A

NILENIL

Page 85: 02-Programmation Fonctionnelle - Le Lisp

READ

PRINT

PRINCH

TERPRI

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 86: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 87: 02-Programmation Fonctionnelle - Le Lisp

(read)

Nom de la fonction

Aucun argument

Appel de la fonction READ

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 88: 02-Programmation Fonctionnelle - Le Lisp

PRINTEdite 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).

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 89: 02-Programmation Fonctionnelle - Le Lisp

(print <arg1> <arg n>)

Nom de la fonction

Arguments

Appel de la fonction PRINT

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 90: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 91: 02-Programmation Fonctionnelle - Le Lisp

(princh <caractere> <nombre>)

Nom de la fonction

Caractère

Appel de la fonction PRINCH

Les fonctions d'entrée/sortieGénéralités, éléments de base

Nombre de répétitions

Page 92: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 93: 02-Programmation Fonctionnelle - Le Lisp

(terpri <nombre>)

Nom de la fonction

Argument

Appel de la fonction TERPRI

Les fonctions d'entrée/sortieGénéralités, éléments de base

Page 94: 02-Programmation Fonctionnelle - Le Lisp

Exemple (ATTENTION, exercices chaînés)

FONCTIONS RESULTAT

?(setq a (read)) ?

?le_lisp

? a

?(print "lisp")

?(print)

?(princh '-' 12)

= le_lisp

= le_lisp

lisp

= () après un saut de ligne

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

Les fonctions d'entrée/sortieGénéralités, éléments de base

?(terpri 2) = t après 2 sauts de ligne

Page 95: 02-Programmation Fonctionnelle - Le Lisp

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

L’environnement de programmationGénéralités, éléments de base

Page 96: 02-Programmation Fonctionnelle - Le Lisp

Pause-réflexion sur cette 1ère partie

Avez-vous des questions ?

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

Page 97: 02-Programmation Fonctionnelle - Le Lisp

Les structures de contrôle

Programmation Fonctionnelle - Le Lisp -

Page 98: 02-Programmation Fonctionnelle - Le Lisp

Plan de la partie

Les opérations de sélection

La récursivité

Fonctions récursives sur les ensembles

L’itération

Voici les chapitres que nous allons aborder:

Les structures de contrôle

Page 99: 02-Programmation Fonctionnelle - Le Lisp

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

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

Les opérations de sélectionLes structures de contrôle

Page 100: 02-Programmation Fonctionnelle - Le Lisp

(if (condition) (alors_action1) (sinon_action2)…. …(sinon_action n))

Nom de la fonction

Conditionà évaluer

Appel de la fonction IF

Les opérations de sélectionLes structures de contrôle

Action pour condition vraie

Actions pour condition fausse

Page 101: 02-Programmation Fonctionnelle - Le Lisp

(cond vrai

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

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

. . vrai

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

Structure de la fonction COND

Les opérations de sélectionLes structures de contrôle

Page 102: 02-Programmation Fonctionnelle - Le Lisp

Exemple (ATTENTION, exercices chaînés)

FONCTIONS RESULTAT

?(if (numberp 1)

'(un nombre)

'(pas un nombre))

= (un nombre)

?(if (numberp 'A)

'(un nombre)

'(pas un nombre))

?(cond

((numberp 1) '(un nombre))

(T '(pas un nombre)))

?(cond

((numberp 'A) '(un nombre))

(T '(pas un nombre)))

= (pas un nombre)

= (un nombre)

= (pas un nombre)

Les opérations de sélectionLes structures de contrôle

Page 103: 02-Programmation Fonctionnelle - Le Lisp

Concept fondamental :

en mathématique :

relation de récurrence

en informatique :

procédures récursives

La récursivité

La récursivitéLes structures de contrôle

Page 104: 02-Programmation Fonctionnelle - Le Lisp

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

Le principe de la récursivité en algorithmique

La récursivitéLes structures de contrôle

Page 105: 02-Programmation Fonctionnelle - Le Lisp

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:

Correspondance entre les modèles, Exemple : la factorielle

La récursivitéLes structures de contrôle

(defun fact (n)(cond

((= n 0) 1)(t (* n (fact (- n 1)) ) )

)

Page 106: 02-Programmation Fonctionnelle - Le Lisp

1 * fact( 0 )

3 * fact( 2 )

= 1

2 * fact( 1 )

1 * 1 = 1

2 * 1 = 2

3 * 2 = 6

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

EMPILER

DEPILER

Retour de la Pile

La récursivitéLes structures de contrôle

Page 107: 02-Programmation Fonctionnelle - Le Lisp

MEMBER : teste si un élément est présent dans une liste

Autre exemple de fonction récursive :

La récursivitéLes structures de contrôle

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

Page 108: 02-Programmation Fonctionnelle - Le Lisp

ENSEMBLE : teste si une liste est un ensemble (pas de doublons)

Autres exemples de fonctions récursives :

Fonctions récursives sur les ensemblesLes structures de contrôle

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

Page 109: 02-Programmation Fonctionnelle - Le Lisp

INCLUS : teste si tous les éléments d'une liste se trouvent dans une autre

Autres exemples de fonctions récursives :

Fonctions récursives sur les ensemblesLes structures de contrôle

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

Page 110: 02-Programmation Fonctionnelle - Le Lisp

COMPARE : teste l'égalité de deux ensembles

Autres exemples de fonctions récursives :

Fonctions récursives sur les ensemblesLes structures de contrôle

?(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) = ()

Page 111: 02-Programmation Fonctionnelle - Le Lisp

UNIQUE : transforme une liste en un ensemble (sans doublons)

Autres exemples de fonctions récursives :

Fonctions récursives sur les ensemblesLes structures de contrôle

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

Page 112: 02-Programmation Fonctionnelle - Le Lisp

UNION : créé un ensemble constitué des éléments de 2 listes

Autres exemples de fonctions récursives :

Fonctions récursives sur les ensemblesLes structures de contrôle

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

Page 113: 02-Programmation Fonctionnelle - Le Lisp

INTER : créé un ensemble constitué des éléments communs

Autres exemples de fonctions récursives :

Fonctions récursives sur les ensemblesLes structures de contrôle

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

Page 114: 02-Programmation Fonctionnelle - Le Lisp

Fonctions itératives:

PROG..GO..RETURN

WHILE

Syntaxe de PROG:

(prog <liste> <S-expression1>…..<S-expression n>)

Syntaxe de GO: (go <atom>)

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

L’itérationLes structures de contrôle

Page 115: 02-Programmation Fonctionnelle - Le Lisp

Exemple 1: la puissance p d’un nombre n

L’itérationLes structures de contrôle

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

?(puissance 3 2) = 9

Page 116: 02-Programmation Fonctionnelle - Le Lisp

Exemple 2: dernier élément d’une liste

L’itérationLes structures de contrôle

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

FONCTION dernier RESULTAT

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

Page 117: 02-Programmation Fonctionnelle - Le Lisp

Exemple 3: inversion d’une liste

L’itérationLes structures de contrôle

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

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

Page 118: 02-Programmation Fonctionnelle - Le Lisp

Exemple 4: la variante itérative de la factorielle

L’itérationLes structures de contrôle

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

?(factorielle '(3)) = 6

Page 119: 02-Programmation Fonctionnelle - Le Lisp

Syntaxe de WHILE

(WHILE (condition) (S-expression1) (S-expression2) ………………….

(S-expression n))

WHILE évalue les S-expressions TANT QUE la condition retourne VRAI

L’itérationLes structures de contrôle

Page 120: 02-Programmation Fonctionnelle - Le Lisp

Exemple: affichage du décompte d’un nombre n

L’itérationLes structures de contrôle

?(defun decompte (n)(while (> n 0)

(print n)(decr n)

))

FONCTION decompte RESULTAT

?(decompte 4) 4

3

2

1

= ()

Page 121: 02-Programmation Fonctionnelle - Le Lisp

Pause-réflexion sur cette 2ème partie

Avez-vous des questions ?

Les structures de contrôle

Page 122: 02-Programmation Fonctionnelle - Le Lisp

Fonctions complexes

Programmation Fonctionnelle - Le Lisp -

Page 123: 02-Programmation Fonctionnelle - Le Lisp

Plan de la partie

Les fonctionnelles

Les fonctions anonymes

Les macro fonctions

Voici les chapitres que nous allons aborder:

Fonctions complexes

Page 124: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctionnellesFonctions complexes

Page 125: 02-Programmation Fonctionnelle - Le Lisp

(APPLY < f > < liste >)

retourne la valeur de l'application de la fonction < f > sur la liste < liste >

Les fonctionnellesFonctions complexes

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

Page 126: 02-Programmation Fonctionnelle - Le Lisp

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.

Les fonctionnellesFonctions complexes

FONCTION mapcar RESULTAT

?(mapcar '1+ '(1 2 3 4 5)) = (2 3 4 5 6)

(defun mapcar (fonction liste)(if (null liste)

()(cons (apply fonction (list (car liste)))

(mapcar fonction (cdr liste)))

))

Page 127: 02-Programmation Fonctionnelle - Le Lisp

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

Les fonctions anonymesFonctions complexes

FONCTION lambda RESULTAT

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

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

?(apply a '(2 3))

= (lambda (x y)

(* x y))

= 6

?(mapcar (lambda (x) (* x x x)

'(2 3 4 5))= (8 27 64 125)

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

(LAMBDA <paramètres> <corps de la fonction> <valeurs locales>)

Page 128: 02-Programmation Fonctionnelle - Le Lisp

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.

Les macro fonctionsFonctions complexes

FONCTION RESULTAT

?(if (< a 0) (1- a) (1+ a)) = (cond

((< a 0) (1- a))

(t (1+ a))

)

(dmd if(test vrai faux)(list 'cond

(list test vrai)(list 't faux)

))

Page 129: 02-Programmation Fonctionnelle - Le Lisp

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

Les macro fonctionsFonctions complexes

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)

Page 130: 02-Programmation Fonctionnelle - Le Lisp

Les macro fonctions EMPILE et DEPILE

Les macro fonctionsFonctions complexes

FONCTION RESULTAT

?(setq a `(toto riri))

?(empile a 'fifi)

?(empile a 'truc)

?a

=(toto riri)

=(fifi toto riri)

=(truc fifi toto riri)

=(truc fifi toto riri)

?(depile a)

?a

= truc

= (fifi toto riri)

(dmd empile (liste var)`(setq ,liste (cons ,var ,liste))

)(dmd depile (liste)

`(let ((res (car ,liste)))(setq ,liste (cdr ,liste))

))

Page 131: 02-Programmation Fonctionnelle - Le Lisp

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

Les macro caractères

Les macro fonctionsFonctions complexes

FONCTION dmc RESULTAT

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

? '($ $)

= $

= (1euro 1euro)

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

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

= $

= (1 2 3 5 6)

Page 132: 02-Programmation Fonctionnelle - Le Lisp

Pause-réflexion sur cette 3ème partie

Avez-vous des questions ?

Fonctions complexes, opérations symboliques

Page 133: 02-Programmation Fonctionnelle - Le Lisp

Opérations symboliques

Programmation fonctionnelle - Le Lisp -

Page 134: 02-Programmation Fonctionnelle - Le Lisp

Plan de la partie

Dérivation des expressions algébriques

Exploration des arborescences

Explorer un espace d’états

Raisonnement symbolique

Voici les chapitres que nous allons aborder:

Opérations symboliques

Page 135: 02-Programmation Fonctionnelle - Le Lisp

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.

Dérivation des expressions algébriquesOpérations symboliques

Page 136: 02-Programmation Fonctionnelle - Le Lisp

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

Dérivation des expressions algébriquesOpérations symboliques

Page 137: 02-Programmation Fonctionnelle - Le Lisp

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 RESULTAT

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

Dérivation des expressions algébriquesOpérations symboliques

Page 138: 02-Programmation Fonctionnelle - Le Lisp

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

Dérivation des expressions algébriquesOpérations symboliques

Page 139: 02-Programmation Fonctionnelle - Le Lisp

SIMPLIFIER : applique récursivement le processus de simplification jusqu'à l'obtention d'une expression irréductible.

Fonction : SIMPLIFIER

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

Dérivation des expressions algébriquesOpérations symboliques

Page 140: 02-Programmation Fonctionnelle - Le Lisp

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

Exploration des arborescencesOpérations symboliques

Page 141: 02-Programmation Fonctionnelle - Le Lisp

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

Exploration en profondeur Liste d'exploration

En inordre:fils gauche, noeud, autres fils

4 * 3 + 5 * 2

En préordre:un noeud puis les autres fils

+ * 4 3 * 5 2

Exploration des arborescencesOpérations symboliques

+

* *

4 3 5 2

En postordre:les fils d’abord, les noeuds ensuite

4 3 * 5 2 * +

Exploration en largeur Liste d'exploration

Largeur :on examine les noeuds du même niveau

+ * * 4 3 5 2

Page 142: 02-Programmation Fonctionnelle - Le Lisp

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

Exploration des arborescencesOpérations symboliques

+

* *

4 3 5 2(setq arbre

'(+(*

(4)(3)

)(*

(5)(2)

))

)

Page 143: 02-Programmation Fonctionnelle - Le Lisp

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

Exploration des arborescencesOpérations symboliques

+

* *

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 Liste d'exploration

? (preordre ‘prin arbre) + * 4 3 * 5 2

Page 144: 02-Programmation Fonctionnelle - Le Lisp

Exploration en INORDRE de l’arbre ci-dessous:

Exploration des arborescencesOpérations symboliques

+

* *

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 Liste d'exploration

? (inordre ‘prin arbre) 4 * 3 + 5 * 2

Page 145: 02-Programmation Fonctionnelle - Le Lisp

Exploration en POSTORDRE de l’arbre ci-dessous

Exploration des arborescencesOpérations symboliques

+

* *

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 Liste d'exploration

? (postordre ‘prin arbre): 4 3 * 5 2 * +

Page 146: 02-Programmation Fonctionnelle - Le Lisp

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

Exploration des arborescencesOpérations symboliques

+

* *

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 Liste d'exploration

? (largeur ‘prin arbre) + * * 4 3 5 2

Page 147: 02-Programmation Fonctionnelle - Le Lisp

Exemple d’arborescence: une classification hiérarchique

Exploration des arborescencesOpérations symboliques

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

Page 148: 02-Programmation Fonctionnelle - Le Lisp

chose

inanimé

roche

artificielle

maisonvoiturenuage

naturelle

etre_vivant

ordinateur

Exploration des arborescencesOpérations symboliques

fleur

animale

reptile

pin

insectearbre

plante

mammifère

chienchene singe etre_humain

Page 149: 02-Programmation Fonctionnelle - Le Lisp

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.

Explorer un espace d’étatsOpérations symboliques

Page 150: 02-Programmation Fonctionnelle - Le Lisp

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

Explorer un espace d’étatsOpérations symboliques

- - -

- $ $

- - fin

J:0 1 2I:0

1

2

Page 151: 02-Programmation Fonctionnelle - Le Lisp

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)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

- - -

- $ $

- - fin

0 1 2

0

1

2

*

Explorer un espace d’étatsOpérations symboliques

Page 152: 02-Programmation Fonctionnelle - Le Lisp

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)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* - -

- $ $

- - fin

0 1 2

0

1

2

*

Explorer un espace d’étatsOpérations symboliques

Page 153: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * -

- $ $

- - fin

0 1 2

0

1

2

*

Explorer un espace d’étatsOpérations symboliques

Page 154: 02-Programmation Fonctionnelle - Le Lisp

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)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

Explorer un espace d’étatsOpérations symboliques

Page 155: 02-Programmation Fonctionnelle - Le Lisp

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)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

Explorer un espace d’étatsOpérations symboliques

Page 156: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * *- $ $

- - fin

0 1 2

0

1

2

*

Explorer un espace d’étatsOpérations symboliques

Page 157: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * ** $ $

- - fin

0 1 2

0

1

2 *

Explorer un espace d’étatsOpérations symboliques

Page 158: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * ** $ $

* - fin

0 1 2

0

1

2 *

Explorer un espace d’étatsOpérations symboliques

Page 159: 02-Programmation Fonctionnelle - Le Lisp

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)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

Explorer un espace d’étatsOpérations symboliques

Page 160: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * ** $ $

* * fin

0 1 2

0

1

2 o

Explorer un espace d’étatsOpérations symboliques

Page 161: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * ** $ $

* o fin

0 1 2

0

1

2 o

Explorer un espace d’étatsOpérations symboliques

Page 162: 02-Programmation Fonctionnelle - Le Lisp

Exemple, Le Labyrinthe : 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 (member (tref labyrinthe I (1+ J)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * ** $ $

o o fin

0 1 2

0

1

2

o

Explorer un espace d’étatsOpérations symboliques

Page 163: 02-Programmation Fonctionnelle - Le Lisp

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)) '(- fin))) (cherche-sortie I (1+ J))) (if (and pas-trouve (member (tref labyrinthe (1+ I) J) '(- fin))) (cherche-sortie (1+ I) J)) (if (and pas-trouve (member (tref labyrinthe I (1- J)) '(- fin))) (cherche-sortie I (1- J))) (if (and pas-trouve (member (tref labyrinthe (1- I) J) '(- fin))) (cherche-sortie (1- I) J)) (ifn pas-trouve (tset labyrinthe I J 'o)) ) )

* * *o $ $

o o fin

0 1 2

0

1

2

o

Explorer un espace d’étatsOpérations symboliques

Page 164: 02-Programmation Fonctionnelle - Le Lisp

Pause-réflexion sur cette 4ème partie

Avez-vous des questions ?

Opérations symboliques

Page 165: 02-Programmation Fonctionnelle - Le Lisp

Pas de distinction entre la structure

de données et celle du programme

Pas de distinction entre la structure

de données et celle du programme

Typage dynamique

des données

Typage dynamique

des données

Le Lisp :un langage

trés puissant basé sur les

fonctions

Le Lisp :un langage

trés puissant basé sur les

fonctions

Applications:raisonnementsymbolique, résolution de

jeux, …

Applications:raisonnementsymbolique, résolution de

jeux, …

Résumé du module

Langage interprété à

syntaxe simple

Langage interprété à

syntaxe simple

Programmation Fonctionnelle - Le Lisp -

Page 166: 02-Programmation Fonctionnelle - Le Lisp

Pour aller plus loin…

Publications

Eléments d'intelligence artificielle de Farreny et Ghallab

(Ed. Hermes, 1987)

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

Si vous voulez approfondir vos connaissances:

Programmation Fonctionnelle - Le Lisp -

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

512 problèmes corrigés en Pascal, C++, Lisp, Prolog

Louis Gacôgne

(Ed.Ellipses, 1996))

Page 167: 02-Programmation Fonctionnelle - Le Lisp

Félicitations

Vous avez suivi avec succès le module de cours n°3

Programmation Fonctionnelle - Le Lisp -

Page 168: 02-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.

Programmation Fonctionnelle - Le Lisp -