02-Programmation Fonctionnelle - Le Lisp

Campus Booster ID : 513

www.supinfo.com

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:marianne.belis@supinfo.com

SUPINFONE: 1 317

Marianne BELIS

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:Arnaud.CUEILLE@supinfo.com SUPINFONE: 1 50087

Arnaud CUEILLE

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:

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:

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

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:

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

FORTRAN PL/I

1957 1960 1964 1966

Historique des principaux langages, dont le Lisp.

BASICCOBOL

1970 1972

B PASCAL

PROLOG

LISP 1.5 CommonLISP

1960 1967 1975 1977

Historique des dialectes Lisp .

VLISPSCHEME

INTERLISP

MACLISP

LE_LISP

AutoLISP

1985 1986

EULISP

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

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

Impression du résultat

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

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

Les noms :

Un caractère

Suite de caractères sans séparateur

ex: supinfo

Les nombres :

Nombres positifs

Nombres négatifs

La forme que peuvent prendre les atomes.

Pierre

Atome-Long

unseulatomelong

Exemples d'atomes

ATTENTION !

il existe un

particulier

appelé NIL !

à suivre

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

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

ATTENTION !

Il existe un

séparateur

particulier :

le point <.> !

à suivre …

LISTE S-EXPRESSION Suite ordonnée d’atomes ou 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

Exemples de listes

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)

Longueur d'une liste

Profondeur d'une liste

Appel d'une fonction Lisp

Autres notions élémentaires

(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

(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

( … … … )

parenthèses

sont aussi

utilisées pour

marquer le

début et la fin

de l'appel d'une

fonction.

(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

(fonction … … )

Le nom de la

fonction est

placé toujours

après la

parenthèse

ouvrante et

précède les

arguments.

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

Exemples

FONCTIONS RESULTAT

?(+ 2 3) = 5

?(- 13 7 2)

?(* 5 11)

?(/ 15 3)

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

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

APPEND

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

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

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

(quote <argument>)

Nom de la fonction

Argument

Appel de la fonction QUOTE

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

**eval: fonction indéfinie: a

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

(car <argument>)

Nom de la fonction

Argument

Appel de la fonction CAR

L'argument doit être une liste

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)

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

= () ou NIL

** eval : variable indéfinie : car

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

(cdr <argument>)

Nom de la fonction

Argument

Appel de la fonction CDR

L'argument doit être une liste.

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

= (())

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

= (atomes seuls)

= ((3 4))

(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

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

Nom de la fonction imbriquée

Appel de la fonction CADR

L'argument doit être une liste.

Trucs et

astuces…

Afin de lire

correctement

une imbrication

de fonctions,

commencez par

celle inscrite en

profondeur !

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

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

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

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

(cons <arg 1> <arg 2>)

Nom de la fonction

Arguments

Appel de la fonction CONS

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

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)

**eval : fonction indefinie : 12

= (a.380)

APPENDPermet de concaténer les listes transmises en argument.

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

Nom de la fonction

Arguments

Appel de la fonction APPEND

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)

= (a . 380)

= (380)

= (a 380)

NUMBERP

< ou > ou <= ou >=

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

Quelques prédicats usuels:

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

(atom <argument>)

Nom de la fonction

Argument

Appel de la fonction ATOM

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

(consp <argument>)

Nom de la fonction

Argument

Appel de la fonction CONSP

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

(null <argument>)

Nom de la fonction

Argument

Appel de la fonction NULL

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.

(equal <arg1> <arg2>)

Nom de la fonction

Argument

Appel de la fonction EQUAL

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

(numberp <argument>)

Nom de la fonction

Argument

Appel de la fonction NUMBERP

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.

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

Nom de la fonction

Arguments

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

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

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

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

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

Nom de la fonction

Arguments

Appel de la fonction SETQ

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)

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

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

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

Liste des paires variable-valeur

Forme générale de la fonction LET

Nom de la fonction interne à LET

Exemple (ATTENTION, exercices chaînés)

FONCTION let RESULTAT

? a = 13

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

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

Profondeur 0.

Profondeur 1.

Profondeur 2.

Racine.

Sommet.

Feuille.

MODELISATION des ARBRES : Rappel

Arête.7

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

Profondeur 0 :

Profondeur 1 :

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

Profondeur 0 :

Profondeur 1 :

Profondeur 2 :

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

Profondeur 1 :

Profondeur 2 :

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

BA FEDC

Profondeur 1 : G

Profondeur 3 :

Profondeur 4 : F

Profondeur 6 :

MODELISATION d'une liste complexe :

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

CA B H

Trucs et

astuces…

Afin de ne pas

faire d'erreur

sur les

imbrications de

parenthèses,

numérotez-les !

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

CA B H

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

CA B H

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.

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

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

Représentation graphique des listes

(A (B C) D E)

( (B C) D E)A

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

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

(A (B C) D E)

((B C) D E)

NILENIL

PRINCH

TERPRI

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

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.

(read)

Nom de la fonction

Aucun argument

Appel de la fonction READ

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

(print <arg1> <arg n>)

Nom de la fonction

Arguments

Appel de la fonction PRINT

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

(princh <caractere> <nombre>)

Nom de la fonction

Caractère

Appel de la fonction PRINCH

Nombre de répétitions

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.

(terpri <nombre>)

Nom de la fonction

Argument

Appel de la fonction TERPRI

FONCTIONS RESULTAT

?(setq a (read)) ?

?le_lisp

?(print "lisp")

?(print)

?(princh '-' 12)

= le_lisp

= () après un saut de ligne

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

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

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

Pause-réflexion sur cette 1ère partie

Avez-vous des questions ?

Les structures de contrôle

Plan de la partie

Les opérations de sélection

La récursivité

Fonctions récursives sur les ensembles

L’itération

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

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

Nom de la fonction

Conditionà évaluer

Appel de la fonction IF

Action pour condition vraie

Actions pour condition fausse

(cond vrai

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

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

. . vrai

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

Structure de la fonction COND

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)

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

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

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

(defun fact (n)(cond

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

1 * fact( 0 )

3 * fact( 2 )

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

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

Autre exemple de fonction récursive :

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

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

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

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

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)

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)

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)

Fonctions itératives:

PROG..GO..RETURN

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

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 RESULTAT

?(puissance 3 2) = 9

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 RESULTAT

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

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 RESULTAT

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

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 RESULTAT

?(factorielle '(3)) = 6

Syntaxe de WHILE

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

(S-expression n))

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

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

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

(print n)(decr n)

FONCTION decompte RESULTAT

?(decompte 4) 4

Pause-réflexion sur cette 2ème partie

Fonctions complexes

Plan de la partie

Les fonctionnelles

Les fonctions anonymes

Les macro fonctions

Fonctions complexes

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

Les fonctionnellesFonctions complexes

(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

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.

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

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

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

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)

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)

Les macro fonctions EMPILE et DEPILE

FONCTION RESULTAT

?(setq a `(toto riri))

?(empile a 'fifi)

?(empile a 'truc)

=(toto riri)

=(fifi toto riri)

=(truc fifi toto riri)

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

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

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

Opérations symboliques

Programmation fonctionnelle - Le Lisp -

Plan de la partie

Dérivation des expressions algébriques

Exploration des arborescences

Explorer un espace d’états

Raisonnement symbolique

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

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

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)

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

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

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

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

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

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

4 3 5 2(setq arbre

(4)(3)

(5)(2)

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

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

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

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

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

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

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

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

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

inanimé

artificielle

maisonvoiturenuage

naturelle

etre_vivant

ordinateur

animale

reptile

insectearbre

plante

mammifère

chienchene singe etre_humain

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

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

- - fin

J:0 1 2I:0

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

* * *- $ $

- - fin

* * ** $ $

- - fin

* * ** $ $

* - fin

* * ** $ $

* * fin

* * ** $ $

* o fin

* * ** $ $

o o fin

* * *o $ $

o o fin

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

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:

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

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

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.

02-Programmation Fonctionnelle - Le Lisp

Documents

Programmation fonctionnelle - Ex-Machina · 2020-04-11 · Programmation Fonctionnelle 5 Bien entendu il était ici possible de résoudre la récurrence en faisant des maths, pour

Programmation fonctionnelle Le langage LISP D. Le langage LISP. Objets. Structure d'un programme. Primitives de manipulation des listes. Primitives booléennes

Programmation fonctionnelle en langage Scheme - labri.fr · Historique Les langages des ann ees 1950 I FORTRAN (1954) : calcul scienti que, donn ees et calcul num erique. I Lisp (1958)

Programmation fonctionnelle 1/10

LISP - Alexandre Dulaunoy · LISP est un langage interactif avec un environnement de programmation intégré. Ceci implique non seule-ment que tous les programmes et toutes les données

Comprendre la programmation fonctionnelle, Blend Web Mix le 02/11/2016

OpenMusic / Common Lisprepmus.ircam.fr/_media/bresson/enseignement/stage... · Le langage Common Lisp comprend une composante importante dédiée à la programmation orientée objet,

Introduction à la programmation fonctionnelle Cours 2kn/teaching/ipf/cours/pdfs/ipf_cours... · 2021. 2. 17. · Introduction à la programmation fonctionnelle Cours 2 kn@lri.fr

Programmation fonctionnelle avancee´conchon/PFA/manpfa1.pdf · Programmation fonctionnelle avancee´ ... I types de base (int, bool, string, unit) I construction let I appel de fonction

Scala : programmation fonctionnelle

La programmation fonctionnelle en javascript / PF

Scheme lave plus blanc - Le site de Henri Garretah.garreta.free.fr/polys/PolyScheme.pdf2 Programmation fonctionnelle, 1. Introduction 1.1. Lisp et Scheme Le langage Lisp dérive des

Programmation Fonctionnelle Introductionluigi.santocanale/... · Programmation Fonctionnelle Introduction Luigi Santocanale LIF, Aix-Marseille Université Marseille, FRANCE 29 août

Le langage Lisp

Programmation Fonctionnelle en Haskell · 2010-06-20 · 1 Programmation Fonctionnelle en Haskell Licence « Sciences et Technologies » Parcours « Informatique » – 2ème année

Ce qui compte c'est les valeurs ! Introduction à la programmation fonctionnelle

PROGRAMMATION FONCTIONNELLE - MONTEFIORE

Langages de l’informatique Introduction Les langages ......Programmation imp´erative Programmation fonctionnelle Programmation en logique p. 3 - Licence des droits d’usage en

Programmation fonctionnelle - Boisvert · Programmation fonctionnelle Programmation fonctionnelle et création d'un langage orienté objet Sébastien Boisvert Http://boisvert.info

Letout Lisp