Dr. Wided LEJOUAD CHAARI Dr. Inès ALAYA LOUHICHI Dr Ahlem BEN HASSINE

OBJECTIFS DU COURS

 Aborder la programmation fonctionnelle

 Maîtriser les principales primitives du langage Lisp

 Comprendre le fonctionnement des programmes Lisp

 Ecrire des fonctions simples, maîtriser le concept de récursivité

 Utiliser Le_Lisp dans des applications d’IA

INTRODUCTION

Les principaux paradigmes de programmation :

► Le paradigme fonctionnel ► Le paradigme procédural ► Le paradigme à objets

LE PARADIGME FONCTIONNEL

► La programmation fonctionnelle désigne une famille de langages de programmation ayant un certain nombre de traits en commun, dont un rôle central donné aux fonctions, d'où le nom.

► On peut y raisonner comme en mathématiques, faire des démonstrations par récurrence, des analyses récursives de complexité, et acquérir une rigueur certaine.

► Les fonctions récursives sont au cœur de ce paradigme. Exemples : Haskell, Standard ML et Ocaml

LE PARADIGME PROCEDURAL

► Le paradigme procédural (ou impératif) est le plus ancien.

► Il met l’accent sur l'appel de procédures pour effectuer un calcul séquentiel.

► L'itération est le mécanisme central pour effectuer un calcul répétitif, la récursivité y est rarement optimisée.

► La programmation impérative considère qu'un texte de programme est une suite d'instructions pilotant un ordinateur.

Exemples : Apparu avec Fortran (1967), poursuivi avec Pascal (1970-1990), actuellement C est le représentant largement majoritaire.

LE PARADIGME A OBJETS

► Le paradigme à objets s'appuie sur la notion de classes et d'objets.

► Les objets ont du savoir-faire sous la forme de méthodes qui ne sont autres que des procédures mais destinées à être transmises à un objet receveur sous la forme d'un message.

► Le calcul est donc décentralisé dans les objets, dont les méthodes peuvent être fonctionnelles ou impératives.

► Notion de réutilisation du logiciel et son extensibilité. Exemples : Smalltalk (1970), popularisé avec Java et C++ dans les années 1990.

LISP

LIST PROGRAMMING

Introduction Conçu en 1958 par J. McCarthy, LISP est un des plus vieux langages de programmation. Il fut pendant longtemps confié à la recherche en intelligence artificielle. LISP se distingue des langages traditionnels par le fait qu’il est spécialement adapté à la manipulation des symboles.

Avantages :  La simplicité de la syntaxe : elle repose sur la seule

structure de liste.

 La puissance du langage en particulier l’équivalence

complète entre données et programmes.

 L’interactivité : LISP est principalement interprété.

 Son concepteur

◦ John Mc CARTHY

 Création ◦ En 1960

 Spécificités

◦ Langage fonctionnel ◦ Traitement symbolique ◦ Code formé de listes parenthésées

 1960 → Lisp 1.5  1966 → MACLISP  1967-1975 → INTERLISP – SCHEME  1977 → VLISP  1984 → LE_LISP – Common LISP  1985-1986 →EULISP – AutoLISP

 Syntaxe simple mais parenthèses multiples  Utilisation intensive de la récursivité  Typage dynamique des données  Pas de distinction entre données et

programmes

 Langage interprété

Objet de base : Atome

L’objet de base de LISP est l’atome.

Un atome est : ► un nombre Exemple : 126, -54 ► un symbole : toute séquence non vide de caractères, Exemple : Le-Lisp, var, 1+x/y. Les symboles permettent de désigner les différents objets

(données et fonctions).

Structure de base de LISP : Liste

Une liste est une séquence ordonnée, éventuellement vide,

d’atomes ou de listes, délimitée par des parenthèses.

Exemple : (* 3 7)

(+ (* 3 7) (- 8 4) 10) (Langages de l’IA) ( )

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

Expression élémentaire

L’expression élémentaire de LISP est la S-expression

Il existe 3 catégories d’expressions symboliques :  Les atomes,  Les listes,  Les paires pointées.

 a  B  ATOME  Pierre  Atome-Long  unseulatomelong  128  -345  *86

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 de1 atome et d’une

liste

 (Une liste) liste constituée de 2 atomes  () liste vide correspond à NIL

Une paire pointée est spécifiée par l’utilisation du séparateur <.> situé entre 2 objets.

 Exemple : (A.B)

Fonctionnement de base de l’évaluateur de S-expression

Toute S-expression a une valeur en LISP. Il est important de bien différencier une S-expression de sa valeur. On note la valeur d’une S-expression <s> : VALEUR<s>.

Le rôle de l’interprète LISP est d’évaluer une S-expression

pour déterminer sa valeur.

Fonctionnement de base de l’évaluateur de S-expression

La valeur d’une S-expression est déterminée différemment,

selon qu’il s’agit d’un atome ou d’une liste :

► un atome : nombre ou symbole

► la valeur d’un nombre est lui-même, ► la valeur d’un symbole :

Fonctionnement de base de l’évaluateur de S-expression

► la valeur d’un symbole :  soit prédéfinie dans LISP et non modifiable : le

symbole est alors une des deux constantes de LISP « t » ou « nil », t a pour valeur lui-même , nil a pour

valeur ( ).

 soit définie et modifiée dynamiquement, variable.

Une liste (<s0>… <sn>) est évaluée comme suit : - LISP considère que <s0> est un symbole qui désigne un nom de fonction ; <s0> n’est pas évalué. <s0> ne doit être ni une liste ni un symbole qui ne correspond pas à une fonction connue par LISP.

- LISP évalue les sous-expressions <s1> … <sn> et

détermine resp. VALEUR<s1>, … <sn>

- LISP applique la fonction associée à <s0> aux

arguments VALEUR<s1>…VALEUR<sn> ; la sous- expression aura pour valeur le résultat de cette application.

Dans une S-expression toute parenthèse ouvrante doit être suivie

d’un nom de fonction.

Exemple : ? (1 2 3 4) ** eval : fonction indéfinie : 1

Comment désigner une S-expression (atome ou liste) qu’on ne veut

pas évaluer ?

 grâce à la fonction « quote » ? (quote (1 2 3 4)) = (1 2 3 4) Abréviation : ‘(1 2 3 4)

Définition de fonctions Un programme en Lisp est une fonction ou un ensemble de fonctions. L'utilisateur définit les fonctions grâce à la primitive de ou defun.

Exemple: ? (de **(z) (* z z) = ** La valeur de cette S-expression est le nom de la

fonction qui vient d'être définie.

Récursion:

Syntaxiquement, une fonction LISP est récursive si le nom de cette fonction figure dans sa propre définition.

Exemple 1: Factorielle (de fact(n) (if (= n 1) 1 (* n (fact (- n 1)))))

Récursion : Exemple 2: Suite de Fibonacci Un= Un-1 + Un-2

(de fib (n) (cond ((= n 0) 0) ((= n 1) 1) (t (+ (fib (-n 1)) (fib (- n 2)))))

Le rôle de l'interprète LISP est d'évaluer une S-expression pour déterminer sa valeur. Il procède selon l'itération suivante:

Lire une S-expression

Evaluer la S-expression

Imprimer la valeur trouvée

Une session LISP consiste à faire évaluer successivement différentes expressions qui obéissent à une syntaxe très simple.

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

Lecture d’une expression

Evaluation de l’expression

Impression du résultat

 LISP ne fait pas une distinction lexicale entre les

symboles de fonctions et les symboles de variables.

 Sinon, ceci va nous empêcher de construire par

exemple une fonction récursive en la définissant avec son itérée.

 Il existe deux classes de systèmes LISP suivant la façon

dont ce problème est résolu :

a. Systèmes bi-valents b. Systèmes mono-valents

a. Systèmes bi-valents :

Chaque symbole peut recevoir deux valeurs, une valeur comme variable dite C-val et une valeur comme fonction dite F-val.

Exemple : (setq a 3) Nous mettons 3 dans la C-val de a

Les symboles +,-,*,... ont une F-val dans l'environnement initial. Le symbole fib a une F-val à partir de la définition de la fonction fib.

► Pour avoir la définition d'une fonction on utilise la fonction prédéfinie getdef

Exemple : ? (getdef 'fib)

Dans les systèmes bi-valents rien n'empêche de donner une valeur à la fois à la C-val et la F-val d'un symbole.

Exemples de systèmes bivalents le-Lisp et Mac-Lisp.

b. Systèmes mono-valents : Dans ces systèmes, un symbole ne peut recevoir qu'une seule valeur dite C-val.

L'évaluation de la fonction donne sa définition (pas besoin de getdef).

► Nous avons vu que la valeur d'une liste est obtenue en opérant le premier élément, qui correspond au nom de la fonction, sur les valeurs des autres éléments.

► Mais prenons cet exemple : ? (setq a 5)

La règle générale n'a pas été appliquée : a n'a pas été

évaluée puisqu'il s'agit de lui donner une valeur.

► On distingue d'abord les primitives prédéfinies et les fonctions définies par l'utilisateur :

SUBR: on appelle SUBR une fonction prédéfinie écrite en

langage machine évaluant ses arguments.

EXPR ou LAMBDA: une fonction écrite en LISP évaluant ses

argument.

FSUBR: une fonction prédéfinie écrite en langage machine

n'évaluant pas tous ses arguments (setq).

► On peut obtenir le type d'une fonction grâce à la

primitive typefn.

Exemples : ?(typefn 'fact) = expr ?(typefn 'car) = subr1 ?(typefn '*) = nsubr

- L’addition (+ … …)

- La soustraction

(- … …)

- La multiplication

(* … …) - La division (/ … …)

- QUOTE

- CAR

- CDR

- CONS

- APPEND

- Empêche l’évaluation de l’expression arithmétique

fournie en argument.

Retourne l’expression non évaluée.

(quote <argument>)

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

- Extrait le premier élément d’une liste. Celui-ci peut

être un atome ou une liste.

(car <argument>)

L’argument doit être une liste.

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

(cdr <argument>)

L’argument doit être une liste.

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

- (car (cdr <liste>)) -> (cadr <liste>) - (car (cdr (cdr <liste>))) -> (caddr <liste>) - (car (cdr (car (cdr <liste>)))) -> (cadadr <liste>)

Afin de lire correctement une imbrication de fonctions, commencez par celle inscrite en profondeur

Permet d’extraire le troisième élément de la liste fournie en argument.

(caddr ‘(a b c)) = (car (cdr (cdr ‘(a b c))))

= (car (cdr ‘(b c))) = (car ‘(c)) = c

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

(cons <arg1> <arg2>)

Le nombre d’arguments est fixe = 2

Permet de concaténer les listes transmises en arguments

(append <arg1> <arg2> … <argn>)

Constructeur et sélecteur de listes:

- Cons : permet d'ajouter un atome ou une liste en tête

d'une liste.

? (cons 2 '(3 4)) = (2 3 4) ? (cons '(1 2) '(3 4)) = ((1 2) 3 4)

Constructeur et sélecteur de listes : ►(car <l>) retourne la tête de la liste VALEUR<l>, retourne erreur si VALEUR<l> n'est pas une liste. ►(cdr <l>) retourne le reste de la liste VALEUR<l>, retourne erreur si VALEUR<l> n'est pas une liste.

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

Constructeur et sélecteur de listes: - (append <l1> ... <ln>) retourne la liste obtenue en concaténant les listes <l1> ... <ln>

? (append '(ceci est ) '(un support de cours) '(en Lisp)) = (ceci est un support de cours en Lisp)

- (list <s1> ...<sn>) retourne la liste dont les éléments <s1> ...<sn>.

? (list 1 2 '(3 4)) = (1 2 (3 4))

- (length <s>) retourne le nombre d'éléments de plus haut niveau de <s>,

si <s> est une liste, sinon 0 (si <s> est un atome).

Exemple: ? (length '(a (b c) d)) = 3

► Les fonctions prédicats sont toujours évaluantes, elles retournent nil si le prédicat est faux.

► Si le prédicat est vrai, la réponse peut dépendre des systèmes puisque "vrai" admet comme représentation toute S-expression différente de nil.

► De nombreux systèmes utilisent l'atome "t".

- (atom <s>) retourne "t" si VALEUR<s> est un atome numérique ou symbolique, et retourne () si c'est une liste non vide.

- (null <s>) retourne "t" si VALEUR<s> est égal à () et () dans le cas contraire.

- (eq <s1> <s2>) permet de tester l'identité de deux atomes. Si VALEUR<s1> et VALEUR<s2> sont identiques retourne "t", sinon retourne ().

- (equal <s1> <s2>) permet de tester si VALEUR<s1> est semblable à VALEUR<s2>, elle retourne « t », sinon (). Elle admet comme arguments des listes et des atomes.

- (symbolp <s>) retourne "t" si <s> est un symbole, et retourne nil sinon.

- (constantp <s>) retourne "t" si <s> est une constante, et retourne nil sinon. Une constante est soit un nombre, une chaîne de caractères ou nil.

- (consp <s>) retourne "t" si <s> est une liste non vide, et retourne nil sinon.

- (listp <s>) retourne "t" si <s> est une liste, et retourne nil sinon.

- (numberp <s>) Teste si l’argument est un nombre. Retourne le nombre si le test est vérifié, () sinon.

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

* eqn  =

► Ce sont les fonctions pour lesquelles la valeur logique du

résultat ne dépend que de la valeur logique des arguments.

► OR retourne une expression de valeur logique vraie si l'un au moins des arguments est de valeur logique vraie sinon retourne nil.

► L’évaluation s'arrête dès le premier argument dont la valeur est vraie. Pour cette raison OR est une F-SUBR.

- (or <s1> …<sN>) retourne la valeur du premier argument dont la valeur est différent de nil, et nil sinon. L'évaluation s’arrête dès l'obtention d’une valeur vraie.

- (and <s1> …<sN>) retourne la valeur du dernier argument si les évaluations de tous les arguments sont vraies, et nil sinon. L’évaluation s’arrête dès l’obtention d’une valeur nil.

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

évalue séquentiellement ses arguments et retourne la valeur du dernier.

● Utile pour la structure conditionnelle IF.

-- la longueur au plus haut niveau ● (longueur1 l) ● (longueur2 l) -- la longueur au plus bas niveau ● (palindrome l) ● (appartient e l) ● (inverse l) ● (intersection l1 l2) ● (dernier l) ● (lsd l)

-- la liste sans son dernier élément

● (nieme n l) -- l’équivalent de nth en Lisp ● (elem-rang-pair l) ● (elem-rang-impair l) ● (coupler l1 l2) ● (extremites l) ● (abs-list l) ● (snoc l e) -- ajout d’un élément en queue d’une liste ● (subst new old l) ● (aplatir l)

Opérateur LET  En LISP, on tend à privilégier une programmation fonctionnelle et à manipuler des fonctions au sens mathématique du terme.

Applications d’un ensemble dans un autre pour lesquels

la notion d’affectation n’intervient pas.

Ceci n’est pas incompatible avec la nécessité de sauvegarder

des résultats intermédiaires.

Opérateur LET  La primitive LET offre le moyen de le faire.

 La fonction let est très utilisée pour procéder à l'évaluation

d'expressions dans un environnement provisoire.

 Elle permet de créer des variables locales.

(let ((<var1> <s1>) ...(<varn> <sn>)) <expr1> ... <exprn>)

► Cette fonction permet de : - évaluer successivement <s1>...<sn> - lier <var1> ... <varn> aux évaluations obtenues - évaluer successivement <expr1> ... <exprn> - délier <var1> ... <varn> - retourner l'évaluation de <exprn>

Exemple : ? (setq x 2 y 4) = 4 ? (let ((x (- x y)) (y (+ x y))) (* x y)) = -12

► Les liaisons se font en parallèle; ► La deuxième liaison, à savoir, y à (+ x y) se fait avec

la valeur de x antérieure à l'appel de let.

► D’autres primitives de modification de la valeur d’un symbole permettent le parcours et la construction progressive de listes.

► Elles facilitent la programmation de fonctions itératives.

(nextl <v>) : retourne (car <v>) et affecte au symbole <v> la

valeur de (cdr <v>)

(newl <v> <e>) : affecte à <v> la valeur de (cons <e> <v>) et

retourne cette valeur

(while <test> <e1>… <en>) : itère sur l’évaluation séquentielle de

<e1>… <en> tant que VALEUR<test> est différente de ().

Exemple : REVERSE itératif

(de reverse (l) (let ((resultat))

(while l (newl resultat (nextl l)))

resultat))

 La plupart des systèmes LISP possèdent dans le descriptif d'un symbole un champ appelé P-LIST permettant à l'utilisateur d'attacher aux symboles des propriétés.

 Le mode d'utilisation de ce champ varie d'un système à un

autre. Le_Lisp attache à la P-LIST d'un symbole une liste plate de longueur paire appelée P-liste dont le format est le suivant : (<prop1><val1> ... <propN><valN>)

Les indicateurs <prop1> ... <propN> indiquent une propriété et sont suivis de la valeur de cette propriété.

► La gestion de cette liste est assurée par les fonctions SUBR suivantes : - (plist <symb>) retourne la P-liste de symbole <symb> - (plist <symb> <l>) affecte <l> à la P-liste du symbole <symb> - (putprop <symb> <val> <prop>) affecte à <prop> la valeur

<val> dans la P-liste de symbole <symb>

- (getprop <symb> <prop>) retourne la valeur de <prop> dans la

P-liste <symb>

- (remprop <symb> <prop>) supprime, si elle existe, <prop> dans

la P-liste <symb>

La fonction EVAL évalue la valeur de son argument. Exemple : ? (setq a '(* 2 4)) = (* 2 4) ? (setq x 'a) = a ? x = a ? (eval x) =(* 2 4) ? (eval (eval x)) = 8

La fonction EVAL est appliquée implicitement par l'évaluateur. En l'appelant explicitement, on force une deuxième évaluation.

- (print <expr>) évalue son argument, édite la valeur obtenue et retourne sa valeur.

Exemple: ? (setq a 3) = 3 ? (print a) a = 3

► print est souvent utilisée avec des chaînes de caractères (entre ˵ ˶).

► L'utilisation de print ne se justifie que lorsque le résultat de l'évaluation n'est pas édité.

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

? (setq salut "Bonjour") = Bonjour

? (print salut) = Bonjour

- (read) c'est une fonction 0-aire qui retourne sans l’évaluer la réponse de l'utilisateur (un ? est envoyé par le système pour l'inviter à envoyer une expression).

Exemple : ? (setq x (read)) ? 5 ; réponse de l'utilisateur = 5

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

(princh <caractere> <nombre>)

Exemple : ? (princh ‘-’ 12) = ------------

- terpri L’appel sans arguments vide le tampon et commence une nouvelle ligne (retourne nil).

(terpri <nombre>)

Dans le cas de la présence d’un argument, celui-ci correspond au nombre de sauts de lignes à appliquer.

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

● Editeur pepe ● Fonction d’appel de pepe : - Ê (Ctrl E) - (pepe <nom_fichier>) - (pepe (pretty <nom_fichier>)) ● Charger un fichier : - (load <nom_fichier>) -^L<nom_fichier> ● Effacer l’écran : - (tycls) ● Quitter l’interpréteur : - (end)

► La fonction Trace modifie la définition d'une fonction : la fonction édite une ligne à chaque fois qu'elle est appelée en indiquant les valeurs des variables.

On revient à la définition initiale par la fonction Untrace. (trace <f>) (untrace <f>)

► La fonction Trace est très utile pour suivre les appels

d'une fonction récursive.

► La fonction Step permet une évaluation pas à pas.

(step <expr>)

► Cette fonction donne avec plus de détails au niveau des opérations élémentaires, une évaluation pas à pas.

Avez-vous des QUESTIONS ?

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

Structure de la fonction IF

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

; condition à évaluer ; action pour condition vrai ; actions pour condition fausse

(IF <s1> <s2> <s3>)

Si la valeur de <s1> est différente de NIL, IF retourne la valeur de <s2>; sinon, IF évalue <s3>. IF construit une structure de contrôle de type "si alors sinon" .

Exemples : ? (IF T 1 2) =1 ? (IF NIL 1 2) =2 ? (IF NIL 1) = NIL

(WHEN <test> <s1> ... <sN>)

Si <test> est Vrai, WHEN évalue chacune des expressions <sI>.

(UNLESS <test> <s1> ... <sN>)

Si <test> est Faux, UNLESS évalue chacune des expressions <sI>.

Structure de la fonction COND

(cond

((test1) ((test2)

(action1)) (action2))

… (t

(actions par défaut)))

Exemple :

? (de test (x y) (COND ((> x y) 'sup) ((= x y) 'egal) (t 'inf)) ) = test ? (test 12 5) = sup ?(test 5 8) = inf

Concept fondamental :

► En mathématiques : Une relation de récurrence

► En informatique :

Procédures récursives

► 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

► 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 ALORS SINON

n = 0 réponse = 1 réponse = n * fact (n – 1)

♦ Programme LISP : (defun fact (n)

(cond ((= n 0) 1)

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

3 * fact (2)

-------------- 3 * 2 = 6

Déroulement de la fonction pour Factorielle (3) ? (fact 3) = 6 E M P I L E R

2 * fact (1) -------------- 2 * 1 = 2

= 1 RETOUR DE LA PILE

-------------- 1 * 1 = 1

D E P I L E R

1 * fact (0)

● (ensemble l) teste si une liste est un ensemble (pas de doublons) ● (inclus l1 l2) teste si tous les éléments d’une liste se trouvent dans une autre ● (compare l1 l2) teste l’égalité de deux ensembles ● (unique l) transforme une liste en un ensemble (sans doublons) ● (union l1 l2) crée un ensemble constitué des éléments de deux listes ● (inter l1 l2) crée un ensemble constitué des éléments communs

Fonctions Itératives :

► PROG…GO...RETURN

(prog <liste> <S-expr1> … <S-expr n>) (go <atom>) (return <S-expr>)

Exemple 1:

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

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

Exemple 3: 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) ) )

Fonctions Itératives : ► WHILE

(WHILE (condition) (S-expr 1) (S-expr 2)

… (S-expr n) )

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

Exemple 1: afficher le décompte d’un nombre

(defun decompte (n) (while (> n 0) (print n) (decr n)

)

; décrémente n

Exemple 2: inverse version itérative (vu dans let)

(de reverse (l) (let ((resultat))

(while l (newl resultat (nextl l))) resultat))

Avez-vous des QUESTIONS ?

► Les Fonctions Anonymes

► Les Fonctionnelles de Récursion

► Les Filtres

► Les Macro Fonctions

► (lambda <liste-arguments> <corps> )

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

► Une lambda-expression est appelée description anonyme d’une fonction.

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

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

► Elle permet de définir une fonction sans nom qui n'est pas utilisable hors de la S-expression dans laquelle elle est définie.

100

Exemples : ? ((lambda (x y) (* x y)) 2 3) = 6 ? (setq a '(lambda (x y) (* x y))) = (lambda (x y)(* x y)) ? (apply a '(2 3)) = 6 ? ((lambda (x) (+ x x)) 3) = 6

101

► Fonction d’ordre supérieur qui prend les fonctions comme arguments et les applique sur des ensembles de données.

102

 Ces fonctionnelles ont pour but d'appliquer une même

fonction successivement à différents morceaux d'une ou plusieurs listes.

 APPLY  MAPCAR

103

 (APPLY <f> <liste>) retourne la valeur de l'application de la fonction < f > sur la

liste <liste>

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

= 9

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

= (a b c d)

? (apply '/ '(6 2))

? (apply 'modulo '(6 2))

= 3

= 0

104

 La fonctionnelle de récursion la plus utilisée est mapcar.

 Cette fonctionnelle applique la fonction (supposée

unaire) aux éléments successifs d'une liste (car, cadr, caddr,...) et retourne la liste des résultats de ces applications.

 On peut utiliser aussi mapcar avec plusieurs listes.

105

Donc il existe deux utilisations de mapcar. Usage1 : (mapcar <s> <l>) évalue <s> et applique le résultat aux éléments de la liste <l> et retourne la liste des résultats. Exemples : ? (mapcar '1+ '(1 2 3)) = (2 3 4) ? (mapcar 'car '((a b) (c) ((d e) f))) =(a c (d e))

106

Usage 2 : (mapcar <s> <l1> ... <ln>) évalue <s> et applique le résultat aux car des listes <l1> ... <ln>

puis à

leurs éléments suivants (cadr, caddr,...) et retourne la liste des

résultats.

Exemples : ? (mapcar '+ '(1 2 3) '(4 5 6)) = (5 7 9) ? (mapcar (lambda (x y) (+ (* x 2) (* y 3))) '(1 2 3) '(4 5 6)) = (14 19 24)

107

(let ((x a)) <expr>)

((lambda (x) <expr>) a)

Exemples : (let ((x 2)) (+ x x)) ((lambda (x) (+ x x)) 2)

108

Soient les deux fonctions suivantes :

1. Retourner les plus petits qu’un élément dans une liste

(de petits (a l) (cond

((null l) ()) ((< (car l) a) (cons (car l) (petits a (cdr l)))) (t (petits a (cdr l))))

109

2. Retourner les plus grands qu’un élément dans une liste

(de grands (a l) (cond

((null l) ()) ((>= (car l) a) (cons (car l) (grands a (cdr l)))) (t (grands a (cdr l))))

110

Filtres  Les deux fonctions petits et grands sont, à l’exception

des deux tests, rigoureusement identiques.

 Elles effectuent le même travail : passer en revue les éléments d’une liste en les soumettant à un test et ne retenir que ceux qui passent le test.

 Alors peut-on programmer ceci en une fonction

générale qui prendrait comme argument la fonction de test à utiliser et la liste à filtrer par ce test ?

111

Filtres (de filtre (test l) (cond

((null l) ()) ((funcall test (car l)) (cons (car l) (filtre test (cdr l)))

(t (filtre test (cdr l)))))

112

Filtres  funcall (funcall <fn> <s1> …<sn>) où <fn> désigne une fonction

qui sera appliquée aux arguments <s1> …<sn>.

Exemple : ? (filtre (lambda (x) (>= x 9)) ‘(15 7 12 3)) = (15 12)

113

Filtres Nos deux fonctions petits et grands peuvent s’exprimer alors comme suit : (de petits (a l) (filtre (lambda (x) (< x a)) l)) (de grands (a l) (filtre (lambda (x) (>= x a)) l))

L’intérêt du filtre est de créer une classe de fonctions très générales pour sélectionner des éléments dans une liste.

114

 Les objets LISP sont trop complexes pour pouvoir être

rangés dans un seul mot mémoire.

 Ils sont en général représentés par un pointeur.  La création des doublets de listes et des autres objets

Lisp se fait le plus souvent dynamiquement.

 Un dispositif général appelé GARBAGE-COLLECTOR

récupère automatiquement les doublets et objets inutilisés .

115

 Pointeurs et doublets On appelle doublet (ou cons) un ensemble de deux pointeurs. Nous le représentons par un diagramme en "boîtes et flèches":

Une liste peut être considérée comme un ensemble ordonné de deux éléments, le premier s'appelle le CAR et le second le CDR de la liste. On représente donc une liste par un doublet dont la première partie pointe vers le CAR et la seconde vers le CDR de la liste.

116

 Pointeurs et doublets Exemples : a. Représentation en mémoire de la liste (LISP LANGAGE FONCTIONNEL).

117

 Pointeurs et doublets

b. Représentation de la liste (A (B A) B) par un diagramme en boîtes et flèches.

118

119

120

121

122

123

● (ajoutN e n l) Ecrire une fonction ajoutN qui ajoute un élément à la nième position d’une liste. ● (rech e p l) Ecrire une fonction rech qui cherche si un élément e se trouve à la position p d’une liste l. ● (pair l) retourne la liste des éléments pairs d’une liste (Utiliser les Filtres) ● (impair l) retourne la liste des éléments impairs d’une liste (Utiliser les Filtres) ● (list-abs-mapcar l) Ecrire une fonction qui retourne la liste des valeurs absolues des éléments d’une liste (Utiliser mapcar) ● Ecrire une fonction qui retourne f(1). Appliquer cette fonction à f(x) = 3x² + 2

124

● Ecrire une variante de la fonction mapcar : mapcar-fill (f l1 l2) où f est une fonction, l1 et l2 des listes et qui retournent la même chose que mapcar si les deux listes sont de même longueur et une liste dont les premiers éléments sont les mêmes que ce qui est renvoyé par mapcar et le reste des éléments sont les éléments supplémentaires de la liste la plus longue.

Exemples : ? (mapcar-fill ’+ ’(1 5 8) ’(3 4 2)) = (4 9 10) ? (mapcar-fill ’+ ’(1 5 8) ’(3 4 2 6 7 4 2)) = (4 9 10 6 7 4 2)

125

● Ecrire une fonction mappend (fun l) qui applique la fonction fun à chaque élément de la liste l (et dont le résultat doit être une autre liste) puis renvoie la concaténation des résultats ainsi obtenus.

Exemple : ? (mappend (lambda (x) (list x (1+ x))) ’(5 3 9 2 5)) =(5 6 3 4 9 10 2 3 5 6)

? (mapcar (lambda (x) (list x (1+ x))) ’(5 3 9 2 5)) = ((5 6) (3 4) (9 10) (2 3) (5 6))

126

● Ecrire une fonction combien qui retourne le nombre d’éléments de la liste vérifiant un prédicat.

Exemples : (combien 'evenp '(1 5 7 6 2)) = 2 (combien 'numberp '(2 3 4 a b 5 t + 8)) = 5 (combien (lambda (x) (= (modulo x 2) 0)) '(1 5 7 6 2)) = 2 ● Ecrire une fonction TRI qui affiche un menu permettant à l’utilisateur de choisir un algorithme de tri à appliquer. La liste à trier est saisie au clavier.

127

● (de next-line (l) (mapcar ’+ (cons 0 l) (append l (list 0))))

1. Tester la fonction next-line en l’appliquant n fois à la liste (1). 2. En utilisant la fonction next-line, écrire une fonction triangle (n) qui construit une liste contenant les listes correspondant aux lignes du triangle de Pascal d’ordre n. Exemples :

(triangle 0) ((1)) (triangle 1) ((1) (1 1)) (triangle 2) ((1) (1 1) (1 2 1)) (triangle 3) ((1) (1 1) (1 2 1) (1 3 3 1)) (triangle 4) ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

128

► Une macro est évaluée en deux étapes :

♦ La première correspond à une phrase d’expansion (ou de traduction) en une forme évaluable en LISP.

♦ Dans la deuxième étape, cette forme est évaluée.

129

► Exemple :

(dmd si (test vrai faux)

(list ′cond

(list test vrai) (list ′t faux) )

)

130

► Exemple :

FONCTION

RESULTAT

? (si (< a 0) (1- a) (1+ a))

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

? (de incdec (a) (si (< a 0) (1- a) (1+ a)) = incdec

? (incdec 5) = 6

131

► 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) ? (setq a `(toto riri)) ? `( a b ,a a) ? `(a b ,@a a)

= (a b c d) = (toto riri) = (a b (toto riri) a) = (a b toto riri a)

132

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

133

► Les macro fonctions EMPILE et DEPILE

FONCTION

RESULTAT

? (setq a `(toto riri)) ? (empile a 'fifi) ? (empile a 'truc) ? a

? (depile a) ? a

=(toto riri) =(fifi toto riri) =(truc fifi toto riri) =(truc fifi toto riri)

= (fifi toto riri) = (fifi toto riri)

134

► Les macro caractères

♦ Caractères spéciaux auxquels sont associées des fonctions ♦ Fonctionnement en 2 temps comme les macro fonctions :

- Génération de code LISP - Exécution

135

FONCTION dmc ? (dmc |$| () '1euro) ? '($ $) ? (dmc |$| () (eval (read))) ? '(1 2 3 $ (+ 2 3) 6)

RESULTAT

= $ = (1euro 1euro) = $ = (1 2 3 5 6)

136

Pause-Réflexion sur la 3ème Partie

Avez-vous des QUESTIONS ?

137

OPÉRATIONS SYMBOLIQUES

► Dérivation des Expressions Algébriques

► Exploration des Arborescences

► Explorer un Espace d’Etats

► Raisonnement Symbolique

138

DÉRIVATION DES EXPRESSIONS ALGÉBRIQUES

► Illustration dans le cas d’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 - 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.

139

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

140

DÉRIVATION DES EXPRESSIONS ALGÉBRIQUES

► Fonction DERIV

FONCTION deriv

RESULTAT

(deriv '(+ x 3) 'x)

= (+ 1 0)

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

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

141

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

142

DÉRIVATION DES EXPRESSIONS ALGÉBRIQUES

► Fonction SIMPLIF

FONCTION simplif

RESULTAT

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

143

DÉRIVATION DES EXPRESSIONS ALGÉBRIQUES

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

144

DÉRIVATION DES EXPRESSIONS ALGÉBRIQUES

► Fonction SIMPLIFIER

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

(defun simplifier (exp)

(let ((dexp (simplif exp)))

(if (equ

Programming Paradigms and Lisp Language

Programming Paradigms and Lisp Language