Prg fonctionnelle et

logique 

2ème Année Filière Informatique
Khaled Ben Lamine
2018-2019
 Plan
• Donner une vue globale sur les langages et les
paradigmes de programmation avec une focalisation sur
deux paradigmes qui sont la programmation fonctionnelle
et la programmation logique

1. Historique des langages de programmation

2. Paradigmes de programmation

3. La programmation fonctionnelle

4. La programmation Logique
Historique:

Les pionniers de la programmation

• Charles Babbage (1791-1871):


Invente la « machine analytique ». Sa compagne, Ada
Augusta Lovelace, est considérée comme la première
programmeur.

• Konrad Zuse (1942):


Développe Plankalkül. Cette notation (implémentée
seulement en 1975 à titre historique) fut un précurseur
des langages de programmation.
Historique: 

Langages de très bas niveau

• Ces langages machines et assembleurs sont dépendant

du hardware. Initialement binaires, puis éventuellement
symboliques.

• Il y a un unique langage machine, et habituellement un

seul langage assembleur pour chaque type de
processeur.

• La compatibilité ascendante est souvent très difficile: Aller

des 386 vers 486 , ou du 486 aux Pentium, ….

Historique: 

Fortran: 1954-1990

• Le premier langage de haut niveau à avoir été implémenté et ayant introduit

les variables, tel que nous les connaissons, les boucles, procédures,
étiquettes…

• Développé pour le calcul scientifique.

• La première version avait plusieurs caractéristiques uniques, souvent

disgracieuses, mais conservées pour maintenir une compatibilité
descendante.

• Encore utilisé pour des applications d’ingénierie nécessitant beaucoup de

manipulations de tableaux et bénéficiant d’une bibliothèque importante de
programmes

• La dernière version, Fortran 90, converge vers les autres langages de

programmation.
Historique: 

Algol 60

• Le premier langage à introduire les blocs et la récursivité,

et à être défini formellement. N’est plus utilisé mais est un
ancêtre de plusieurs langages contemporains.

• Souvent considéré comme le langage le plus innovateur

de l’histoire des langages de programmation.
Historique: 

Cobol

• Orienté vers le traitement de données (applications de gestion)

• Organisation très stricte

• Structures de contrôles faibles

• Structures de données élaborées, les enregistrements (records)

sont introduits.

• Populaire dans le monde des affaires et des services

gouvernementaux, moins dans les universités.

• A vécu un regain d’intérêt lors de la « crise » du bug du passage à

l’an 2000.
Historique: 

PL/I

• Une combinaison des meilleurs éléments (tel qu’on

pensait à l’époque) de Fortran, Algol 60 et Cobol.

• Conçu pour être complètement général, pour être

utilisé pour toute application de l’époque.

• Encouragé par IBM

• Peu utilisé aujourd’hui.

• Introduit la manipulation d’événements (event handling).

Historique: 

Basic

• Le premier langage utilisé en informatique personnelle

(personal computing).

• Le premier langage appris par plusieurs programmeurs:

Conçu pour être facile à apprendre.

• Très simple, puissance limitée, mais peut être utilisé dans

plusieurs domaines d’applications.

• Les versions de Basic utilisées aujourd’hui sont plus

complexes.
Historique: 

Simula 67

• Une extension d’Algol 60 conçu pour la simulation de

processus concurrents.

• Introduit les concepts de programmation orientée objet:

classes et encapsulation.

• Prédécesseur de Smalltalk et C++.

• N’est plus très utilisé.

Historique: 

Algol 68

• Sa conception est d’une élégance toujours inégalée.

• Très difficile à implémenter.

• Une description formelle habile, mais difficile à

comprendre.

• Jamais vraiment utilisé.

Historique: 

Pascal

• Une version simplifiée d’Algol 68.

• Populaire pour l’enseignement de la programmation

structurée.

• Un « bon » « premier langage » à apprendre, favorise de

bonnes habitudes de programmation.

• Ses extensions (comme Delphi) sont des systèmes de

programmation complets, aussi puissant que des
environnements Java, par exemple.
Historique: 

Modula-2

• Un successeur de Pascal, plus conceptuellement

uniforme.

• Mécanismes de programmation concurrente (plusieurs

processus en parallèle).

• Peu utilisé, bien que ce soit un bon langage.

• Ses successeurs, Modula-3 et Oberon, sont encore plus

attrayants, pratiques — et peu utilisés, (supplantés par
C++.)
Historique: 

Ada

• Le résultat d’un processus de conception très élaboré, à

plusieurs étapes, et une tentative plus réussie que PL/I
d’obtenir un langage général.

• Complètement standardisé: ne possède aucun dialecte

( tout comme Java).

• 2 standards: Ada 83 (original), et Ada 95.

• Permet la concurrence de façon élégante et

systématique.
Historique: 

C

• Utilisé pour implémenter Unix.

• Utile pour la programmation système et le développement

pour les ordinateurs personnels.

• Populaire dans le passé, toujours utilisé, mais supplanté

par C++.

• De bas niveau / haut niveau.

Historique: 

LISP

• Un des premiers langages de programmation.

• Basé sur l’évaluation de fonctions. Utile pour le calcul

symbolique.

• Initialement l’unique langage de l’intelligence artificielle

(Prolog est plus jeune de 12 ans).

• Plusieurs dialectes: Scheme, Common Lisp.

• Des successeurs très élégants (Miranda, ML, Haskell)

mais peu utilisés.
Historique: 

Prolog

• Un langage de très haut niveau.

• Déclaratif, basé sur un sous-ensemble de la logique, les preuves

sont interprétées comme les calculs.

• Puissant:

• Gère le Non-déterminisme (backtracking intégré).

• Appariement flexible et élaboré.

• Mémoire Associative: accès par le contenu

• Un outil puissant, entre des mains habiles.

Historique: 

Smalltalk

• Programmation orientée objet très pure (plus que Java,

beaucoup plus que C++).

• Intégré à un environnement de programmation et une

interface usagée.

• Un outil puissant, entre des mains habiles.

Historique: 

C++

• L’extension orientée objet du langage impératif C.

• De conception hybride, avec les concepts orientés objet

ajoutés à un langage qui n’était pas conçu pour cela.

• Syntaxe compliquée, sémantique difficile.

• Très en vogue et en demande. Java ne l’a pas encore

supplanté, classé comme le langage le plus demandé en
2016,
Historique: 

Java

• Une version modifiée de C++ beaucoup plus élégante.

• Pleinement orienté objet (Quoi que pas aussi consistant

que Smalltalk)

• Conçu pour la programmation pour Internet, mais

d’utilisation générale.

• En vogue.
Historique: 

Langage Script

• Traitement de fichiers texte

• Perl

• Python

• Programmation du web

• JavaScript

• PHP
Historique: 

Spécialisation d’un Langage

• Langages à usage général:

• la plupart des langages que vous connaissez,

• Langages spécialisés: par exemple

• Matlab; Octave (mathématiques),

• Cobol (production de rapports),

• SQL (bases de données),

• Perl (adapté au traitement et à la manipulation de fichiers texte,

langage interprété intermédiaire entre C et des langages script
comme Shell ou Sed) ,
Historique: 

Liens Historiques entre les Langages
Historique: 

Liens Historiques entre les Langages
Historique: 

Liens Historiques entre les Langages
Historique: 

Classement des Langages de Programmation:
Historique: 

Classement des Langages de Programmation:

• Se limiter aux dix premiers est un choix très difficile dans la mesure où
la suite du classement est également intéressante.

• On retrouve par exemple de la 11e à la 20e place :

• Arduino (#11),

• Ruby (#12),

• Assembleur (#13),

• Scala (#14),

• Matlab (#15),

• HTML (#16),

• Shell (#17),

• Perl (#18),

• Visual Basic (#19)

• Cuda (#20). 
 SOMMAIRE

1. Introduction

2. Aperçu Historique

3. Paradigmes de Programmation

4. Programmation fonctionnelle

5. Programmation logique
 Paradigmes de programmation

Définition
• Un Paradigme est un modèle de pensée qui oriente la
recherche et la réflexion scientifique (Larousse)

• Un paradigme de programmation est une façon de penser

qui oriente l’analyse, la conception et le codage d’un
programme,

• Chaque paradigme permet d’autres techniques de

programmation: Les paradigmes sont complémentaires

Paradigmes de programmation
classification
• Le nombre de paradigmes est
de l’ordre de 29 paradigmes
réellement utilisés, mais le
nombre de LP est beaucoup
plus important,

• Chaque paradigme est défini

par un ensemble de concepts
de programmation,
Paradigmes de programmation

classification
• 2 grandes approche dans la programmation

• Une approche "impérative" (opérationnelle) totalement déterministe,

où l'on décrit à la machine, exactement ce qu'elle doit faire (un
programme = suite d'instruction à exécuter par la machine)

• Une approche déclarative, totalement non déterministe : on décrit à

la machine ce que l'on veut qu'elle calcule (c'est à elle de trouver
l'algo) des langages s'en approche Prolog, CAML, Lisp

• Les langages impératifs au départ étaient voué au calcul numérique

opposé au calcul symbolique.

Paradigmes de programmation
classification
• Programmation impérative:

• ce type de programmation présente 3 propriétés:

• traitement séquentiel des instructions,

• usage de variables représentant des espaces mémoires ou des états,

• usage d’affectations pour changer les valeurs des variables, ou les états

• Exemples: Pascal, C, C++, Java ….,

• Programmation déclarative:

• ce type de programmation permet au programmeur de déclarer diverses entités

sans se soucier de la façon dont celles-ci seront utilisées. Le programme pourra
ensuite utiliser ces déclarations pour résoudre le problème, exemples: Prolog, Lisp
Paradigmes de programmation

Classification
Paradigmes de programmation

Classification
 Paradigmes de programmation

Programmation Impérative

• Programmation procédurale:

• Le programme est divisé en blocs pouvant contenir des variables

locales, ainsi que d’autres blocs: (Fortran, Pascal, C,),

• la programmation est basée sur des instructions/commandes “fais

quelque chose”,

• Programmation orientée objet:

• Des objets se rapportant au problème sont définis, avec leurs attributs

et leur façon de réagir à différents événements,

• Le problème est résolu grâce à des structures de contrôles basées sur

l’envoi de messages entre ces objets: (Java, Smalltalk, C++, C#, Eiffel)
 Paradigmes de programmation

Programmation Impérative

• Programmation concurrente:

• Langage permettant la mise en œuvre de plusieurs activités concurrentes

pouvant s’exécuter simultanément, communiquer et se synchroniser entre
elles. Les données peuvent être partagées ou pas: cas de Ada 95, ou Java

• Programmation évènementielle:

• la logique du programme est commandée par l’apparition d’évènements

auxquels il faut répondre,

• elle est souvent basée sur l’approche objet,

• un événement est souvent le résultat d’une intervention de l’utilisateur: clic,

déplacement de souris, …: cas de Java
 Paradigmes de programmation

Programmation déclarative

• Programmation fonctionnelle:

• Un programme consiste en la déclaration de fonctions,

• La structure de contrôle se résume en l’application et

l’évaluation de fonctions,

• Un appel à une fonction est fait. Celle-ci retournera un élément

qui ne dépend que de la valeur des paramètres de la fonction.
Les paramètres peuvent, eux même, être des appels à des
fonctions: Lisp, Haskell, Scala, Erlang, Java+Guava, F#

• Les paramètres de fonctions peuvent être des appels de

fonctions,
 Paradigmes de programmation

Programmation déclarative

• Programmation logique:

• Un programme consiste en la déclaration d’une série d’axiomes et de règles de

déduction, avec la présentation d’un théorème à prouver. Le programme répond
si le théorème peut être prouvé ou non à partir des déclarations: (Prolog),

• Tout est défini en terme de prédicats logiques,

• La structure de contrôle est implicite: unification et chainage arrière,

• Programmation à base de contraintes:

• utilise le principe de la programmation logique,

• orientée but: résolution de contraintes, généralement sous forme

 Paradigmes de programmation

Langages Multi Paradigmes

• De plus en plus de langages sont multi-paradigmes: C++,

Python, Oz, Ruby, Ocalm, F#….

• Extensions orienté objet: non seulement C++, mais les

dialectes de Lisp (CLOS) et Prolog (XPCE/Prolog, Prolog++).

• Programmation logique combinée à la programmation

fonctionnelle (encore expérimental).

• Langages concurrents (comme Ada): au lieu d’avoir un

processus sur un processeur, permet plusieurs processus
en parallèle.
 SOMMAIRE

1. Introduction

2. Aperçu Historique

3. Paradigmes de Programmation

4. Programmation fonctionnelle

5. Programmation logique
 Programmation
fonctionnelle
• Objectif général

• Découverte de la programmation fonctionnelle

• Les formes qu'elle prend syntaxiquement (expressions, fonctions et

listes récursives)

• Compétences générales attendues

• Spécifier un calcul de façon fonctionnelle plutôt qu'impérative :

programmer au moyen d'expressions plutôt que d'instructions

• Spécifier des calculs récursivement plutôt qu'itérativement

• Spécifier un calcul générique : abstraire un calcul au moyen de

paramètres fonctionnels et de retours fonctionnels
 Concepts fonctionnels
• Ecriture fonctionnelle : programmation par applications
de fonctions plutôt que par l'exécution de séquences
d’instructions

• Transparence référentielle : chaque expression peut

être remplacée par son résultat sans changer le
comportement du programme - sans effets de bord

• Programmation fonctionnelle pure : sans effets de

bords, avec transparence référentielle.
 Concepts fonctionnels
• Flot de contrôle non linéaire: si aucune dépendance ne
les lie, deux fonctions peuvent être appelées dans
n’importe quel ordre,

• Evaluation retardée: selon le besoin

• Garbage collector: ramasse miette au niveau de la

mémoire

• Inférence de type: Déterminer automatiquement le type

d'une expression ou d'une fonction
 Historique
• 1958 : John Mac Carthy (MIT)

• 1986 : common lisp ANSI (portabilité, consistance, expressivité, efficacité, stabilité).

• Les enfants de lisp :

• Logo (1968), langage visuel pédagogique

• Smalltalk (1969, Palo Alto Research Center de Xerox) premier langage orienté objets

• ML (1973, R. Milner, University of Edinburgh), preuves formelles, typage statique, puis

CaML (1987 INRIA), projet coq, et Haskell purement fonctionnel, paresseux.

• Scheme (1975, Steele et Sussman MIT) mieux défini sémantiquement, portée lexicale,
fermeture, et continuations de première classe.

• emacs-lisp (Stallman 1975, Gosling 1982), langage d'extension de GNU Emacs.

• CLOS (1989, Common Lisp Object System), common lisp orienté objets.
 Programmation fonctionnelle
concepts de base

• Exemple:

• Soit la fonction factorielle:

‘‘ n! est le produit des entiers entre 1 et n’’

ou

n! = 1 * … * n ou n! = ∏ i , ∀ i ∈ [1, …,n]

ou

0! = 1 et n ! = n * (n – 1) !, si n>0

Programmation fonctionnelle
concepts de base
 Programmation fonctionnelle
concepts de base

• Le paradigme fonctionnel
n'utilise pas de machine à
• Le paradigme impératif états pour décrire un
s’appuie sur le modèle de programme, mais un
machine à états (ou de Turing) emboîtement de fonctions qui
avec une mémoire centrale et se présentent comme des
des instructions qui modifient « boîtes noires » que l'on peut
son état grâce à des imbriquer les unes dans les
affectations successives: autres: pas de variable, pas
affectation, variables d’affectation

 Programmation fonctionnelle
concepts de base

• La sortie S ne dépend que des entrées E1, E2, ……, En

• Pour le même n-uplet en entrée E1, E2, …, En, la sortie est toujours
la même
 Programmation fonctionnelle
concepts de base

• L’exécution d’un programme fonctionnel comprend l’évaluation d’une

expression symbolique dite s-expression.

• Souvent, il y a un environnement interactif qui permet l’évaluation d’une

expression entrée par l’utilisateur (comme c’est le cas avec une machine à
calculer).

• On appelle session le cycle continu de:

• entrer une expression,

• et de la laisser évaluer.

• Les expressions contiennent généralement des références aux fonctions

prédéfinies dans une bibliothèque ou définies par le programmeur dans un
script.
 Paradigme fonctionnel
concepts de base

• L’évaluation d’une expression consiste en la simplification de l’expression à

sa plus simple forme équivalente.

• Une expression qui ne peut plus être simplifiée est dite sous sa forme
canonique.

• Le processus de simplification repose sur l’usage des définitions comme

règles de réécritures : si l’expression à simplifier est une instance de la
partie gauche d’une définition (= pattern matching), elle se simplifie à la
partie droite de la règle sous la substitution appropriée.

• On appelle réduction une séquence d’expressions e1, . . . , en dont chaque

expression ei (i >= 2) est une simplification de ei−1 obtenue en appliquant
une seule définition.

• Une réduction e1, . . . , en est dite totale quand en est en forme canonique.
 Paradigme fonctionnel
concepts de base

• En général, on peut construire plusieurs réductions pour une seule

expression..
square (3 + 4)
square (3 + 4) =
= (3 + 4) * (3 + 4)
square 7 =
= 7 * (3 + 4)
7*7 =
= 7*7
49 =
49
• Une caractéristique-clef de la programmation fonctionnelle est:

• Si on peut construire différentes réductions totales pour une seule expression,

elles résultent toutes à une même forme canonique: le résultat est toujours le
même.

• Il est possible qu’une réduction ne se termine pas.

Programmation Fonctionnelle

Concepts de base – Principe1: tout est fonction

• Fonction: au sens mathématique

• f : x —> x

• f : x—> 3 . x ou f(x) = 3 . x

• Lambda-calcul:

• λx.x

• (λx. 3 * x) 9 —> 3 * 9

Programmation Fonctionnelle

Concepts de base – Principe1: tout est fonction

• Contrairement aux mathématiques, les L.P font la différence entre la définition de la

fonction et l’application de la fonction:

• Définition de la fonction: déclaration de la fonction et la description de ce qu’elle

doit faire, en utilisant des paramètres formels,

• Application de la fonction: appel de la fonction déclarée utilisant les paramètres

actuels ou « arguments »,

• Mathématiques vs L.P. Impératifs:

• En L.P. impératifs, les variables réfèrent à une adresse mémoire et une valeur ,

• En mathématiques, les variables représentent toujours la valeur actuelle, d’où une

expression comme x:= x + 1 n’a pas de sens,

L’approche fonction dans la programmation doit donc éliminer la notion de variable

et par voie de conséquence l’opération d’affectation
Programmation Fonctionnelle

Concepts de base – Principe1: tout est fonction

• Un programme comme description d’un traitement spécifique doit permettre de rendre

compte de:

• Le « comment » du traitement: ce qui doit être fait!!

• Le pourquoi du traitement: quel résultat attendu !!

• De ce fait, Un programme n’est autre qu’une fonction mathématique:

• Vision fonction
• Vision programme / procédure

• f: X —> Y, à chaque x de X, associe un y

de Y • X est l’ensemble des entrées
du programme / paramètres
• X est l’ensemble domaine de f,
• Y est l’ensemble des résultats
• Y est l’ensemble image de f, du programme / valeurs
retournées
• y = f(x) ; x est dite variable indépendante,
y est dite variable dépendante
Programmation Fonctionnelle

Concepts de base – Principe2: récursivité

• L’itération est proscrite:

for
While
…

• L’itération remplacée par une fonction qui s’appelle elle-même

• La récursion terminale: L’appel récursif est la dernière instruction

 Programmation Fonctionnelle

Concepts de base – Principe2: récursivité

La récursivité
Programmation Fonctionnelle

Concepts de base – Principe 3: ordre supérieur

• Tout comme en mathématiques, l’approche fonctionnelle

dans la programmation doit aussi permettre l’utilisation
des fonctions de différentes façons:

• Les fonctions sont des objets généraux du langage dont

l’utilisation ne comporte aucune restriction,

• Les fonctions peuvent être à leurs tours des valeurs,

• Les fonctions peuvent être traitées par d’autres fonctions

et être des paramètres d’autres fonctions (notion de
composition de fonctions en mathématiques)
Programmation Fonctionnelle

Concepts de base – Principe 3: ordre supérieur

• Fonction d’ordre supérieur: fonction en paramètre

• Dérivée: deriv ( f , x) = d f (x) / dx

• Application d’une fonction sur chaque élément d’une

collection:

• Ex: mapcar ( ‘(lambda(x) (* x x)) ‘(4 6 8)) dont l’évaluation

aboutit à (16 36 64)

• Composition de fonctions: f o g (x) = f(g(x))

• Avantages: généricité / réutilisabilité , extension du langage

Programmation Fonctionnelle

Concepts de base – Principe 4: déterminisme

• Indépendance / Déterminisme:

• f(x) = x + time () NON

• f(x,t)= x + t OUI

• Fonction = opération déclarative:

• Indépendante,

• Sans état interne,

• Déterministe

Une fonction retourne toujours la même valeur pourvu qu’on lui fournisse
les mêmes paramètres
 Programmation Fonctionnelle

Concepts de base – Principe 4: déterminisme

Programmation en C:
Programmation en Lisp:
int n = 2;
(defun inc(n k)
int inc(int k)
« incrémentation sans
{ /* incrémentation par
effet de bord »
effet de bord */
(+ n k))
n = n + k;
return n;
(+ (inc 2 1)(inc 2 1))
}

f(inc(1) + inc(1)); Le 1er appel de la fonction inc

renvoie la même valeur que le
Le 1er appel de la fonction inc ne second appel
renvoie pas la même valeur que
le second appel
Programmation Fonctionnelle

Concepts de base – Principe 4: déterminisme

• Propriété de l’immuabilité: réduit les effets de bord & améliore l’approche concurrente:
une variable (fonctionnelle) est équivalente à:

• variable (mathématique)

• constante (impératif)

• final (Java)

• Flot de contrôle non linéaire: si aucune dépendance ne les lie, deux fonctions peuvent
être appelées dans n’importe quel ordre,

• Evaluation retardée: selon le besoin

• Garbage collector: ramasse miette au niveau de la mémoire

• Inférence de type: Déterminer automatiquement le type d'une expression ou d'une

fonction
Programmation Fonctionnelle

Concepts de base – Principe 4: déterminisme

• Les langages de programmation fonctionnelle « pures » (Miranda, Haskell) et les

programmes fonctionnels doivent avoir les qualités suivantes:

1. Tous les programmes et les procédures sont des fonctions et distinguent

clairement les valeurs en entrée « paramètres » et les valeurs à la sortie « résultats
»,

2. Il n’y a pas de variables, ni d’affectations; les variables sont remplacées par les
paramètres,

3. Il n’y a pas de boucles; les boucles sont remplacées par les appels récursifs,

4. La valeur résultat d’une fonction dépend seulement de la valeur de ses

paramètres et non de l’ordre des évaluations ou du chemin qui a mené à l’appel
de la fonction,

5. Les fonctions peuvent être vues comme des valeurs qui peuvent être traitées par
d’autres fonctions et jouer le rôle de paramètres de fonctions,
Programmation Fonctionnelle

Concepts de base – Principe 4: déterminisme

—  Par exemple:

(* (+ 2 3) (* 4 (+ 4 6)))
1er 2nd
paramètre paramètre
Fonction * de la de la
fonction * fonction *

(+ 2 3)
1er 2nd
paramètre paramètre
de la de la
fonction + fonction +
Fonction +
Programmation Fonctionnelle

Concepts de base – Principe 5: listes
• Liste vide : [ ] dans Haskell, ( ) dans Lisp

• Ajouter un élément en tête de liste:

• Haskell Lisp

• 1 : [] == [1] (cons 1 ()) == (1)

• 1 : [2 , 3] == [1, 2, 3] (cons 1 ‘(2 3)) == (1 2 3)

• [Link][] == [1,2,3] (cons 1 (cons 2 (cons 3 ()))) == (1 2 3)

• Récupérer la tête d’une liste:

• head [1,2] == 1 (car ‘(1 2)) == 1

• Récupérer la queue:

• tail [1,2] == [2] (cdr ‘(1 2)) == (2)

Programmation Fonctionnelle

Avantages
• Les langages dits purement fonctionnels n'autorisent pas la
programmation impérative. De fait, ils sont dénués d'effets de bord et
protégés contre les problèmes que pose l’exécution concurrente:
parallélisation facile des programmes fonctionnels

• Les langages fonctionnels ont comme autre propriété la transparence

référentielle. Il s’agit du principe selon lequel le résultat du programme
ne change pas si on remplace une expression par une expression
de valeur égale. 

• La programmation fonctionnelle se prête mieux à l’application de façon

automatique des preuves de fonctionnement.

• Les programmes fonctionnels sont beaucoup plus robustes et plus

facilement maintenables,
Programmation
fonctionnelle
Fondements théoriques
 Le λ-calcul
• Théorie des fonctions d'Alonzo Church (1930), comme
modèle universel de calcul, directeur de thèse d'Alan
Turing (machines de Turing, théorie de la calculabilité).

• peut encoder n’importe quel calcul (équivalent à machine

de Turing)

• est à la base des langages fonctionnels (Lisp, ML,

Haskell, Scheme)

• récemment est présent dans la plupart des langages de

programmation (Java, Phyton, javascript, c#,…)
 Le λ-calcul
• Syntaxe

• Variables : x, y, … sont des λ-termes

• Applications (d’une fonction) : si u et v sont des λ-termes

uv est aussi un λ-terme. On peut alors voir u comme une
fonction et v comme un argument, uv étant alors l'image
de v par la fonction u.

• Abstractions lambda (fonction) : si x est une variable et u

un λ-terme alors λx.u est un λ-terme. Intuitivement, λx.u
est la fonction qui à la variable ou paramètre x associe ou
retourne une expression u. (unary anonymous fonction)
 Le λ-calcul

• syntaxe

expression ::= variable identifiant

| expression expression application d’une fct

| λ variable . expression abstraction d’une fct

| ( expression) groupement
 Le λ-calcul

• Variables

• x

• une occurrence de variable est dite muette ou liée si

elle apparaît dans le corps d'un λ-terme dont elle est
paramètre, sinon elle est dite libre.
 Le λ-calcul
• Variables

• Ainsi, les variables libres d'une expression sont définies par :

• si x ∈ alors libres(x) = {x},

• libres(λx u) = libres(u) - {x},

• libres(uv) = libres(u) ∪ libres(v)

• Une variable ayant une occurrence non libre dans une expression est dite liée
dans cette expression.

• Une variable qui n’a pas d’occurrence dans une expression, elle n’est ni libre, ni
liée.

• Une expression est dite close si elle n'a pas de variable libre.
 Le λ-calcul
• Variables liées et libres:

• Exemples:

• (a) libres (λx x) = libres(x) - {x} = {x} - {x} = {}, x est lié dans
(λx x)

• (b) libres(λx y) = libres(y) - {x} = {y} - {x} = {y}, y est libre

dans (λx y), x est lié

• (c) libres(λx (λy (x + y)) = libres((λy (x + y)) - {x} = libres (( x

+ y))- {y} - {x} = {x,y} - {y} - {x} = {} , x et y sont liés (λx (λy (x
+ y))
 Le λ-calcul
• Applications

• fu

• appliquer la fonction f à son argument u

• f u v appliquer f à ses deux arguments -> appliquer f à u

donne une fonction qu’on applique à v.

• ((f u) v)

• Les applications sont faites de gauche à droite en l'absence

de parenthèses
 Le λ-calcul
Abstractions

paramètre/variable

signifiant de
Fonction
λa.b expression retournée

abstraction lambda

Fonction anonyme unaire

 Le λ-calcul
• Exemples :

• Constante : λx.y

• Identité : λx.x

• Fonction renvoyant une fonction : λx.(λy.a)

• Application : xyz ou ((xy)z)

• Fonctions à plusieurs arguments : λxy.a (λx.λy.a)

Remarques: les applications sont faites de gauche à droite en

l'absence de parenthèses.
 Le λ-calcul
substitution
• Cette opération permet de remplacer les occurrences d'une variable par
un terme pour réaliser le calcul des λ-termes. On note t[x := u] la
substitution dans un lambda terme t de toutes les occurrences d'une
variable x par un terme u.

• Définition

• Variable: si t est une variable alors t[x := u] = u si x = t et t sinon

• Application: si t = vw alors t[x := u] = v[x := u]w[x := u] si v et w sont

des termes.

• Abstraction: si t = λy.v alors t[x := u] = λy.(v[x := u]) si x ≠ y et y n’est

pas une variable libre de u. Si y est une variable libre de u, on
renomme y avant de substituer. Si x = y le résultat est t.
 Le λ-calcul
substitution

• Exemple: Dans ces exemples, les symboles x; y; z; a sont des variables.

• Dans une application : xyz[y := a] = xaz; x y [y:=λz.x ]= x (λz.x)

• Dans une abstraction (cas normal) : λ[Link][y := a] = λ[Link]

• Capture de variable libre : λx.x y[y := ax] = λ[Link](et non λ[Link]), renommage de
la variable liée

• λx.x y [y:=λz. x] = λ t. t (λz. x)

• λx.z(λ[Link]) [z:=λ[Link]] = λx.(λ[Link])(λt.(λ[Link])t)


• Substitution inopérante (sur variable liée): λ[Link][x := z] = λ[Link] = λ[Link]

!77
 Le λ-calcul
β-réduction
• On appelle redex un terme de la forme (λx.u)v.

• On définit alors la β-réduction

(λx.u)v —> u[x := v]

• La réduction du terme (λx.u)v est la valeur de la fonction λx.u appliquée à la

variable v.

• u est l'image de x par la fonction (λx.u),

• L'image de v est obtenue en substituant dans u, x par v.

• Exemples

• (λ[Link])a donne xy[x := a] = ay

• (λx.y)a donne y[x := a] = y

 Le λ-calcul
β-réduction

• Exemple

((λa.a) λb.λc.b)(x)λe.f

= (λb.λc.b) (x) λe.f

= (λc.x) λe.f

= x

β- Normal form
 Le λ-calcul
la normalisation
• Un lambda-terme t est dit en forme normale si aucune β-réduction ne peut lui être
appliquée, c'est-a-dire si t ne contient aucun redex.

• Différentes stratégies de réduction sont définies dans le λ-calcul : stratégie applicative

(par valeur, dans les langages lisp et scheme), stratégie paresseuse (par nom, dans
Haskell).

• l'ordre d'évaluation des arguments d'une fonction n’a pas d'influence sur le résultat.

• Exemple

• Les symboles x; y; z; a sont des variables. Soit le terme (λx.y)((λ[Link])a)

• Strategie applicative : (λx.y) ((λ[Link]) a) —> (λx.y) aa —> y

• Strategie paresseuse : (λx.y) ((λ[Link]) a) —> y

 Le λ-calcul
la normalisation
• Le processus de β-réduction est un processus qui est
non-déterministe == plusieurs possibilités peuvent s’offrir
sur la façon de choisir les termes sur lesquelles on
souhaite opérer la β-réduction

• La question est de savoir si le choix qu’on peut faire influe

sur la terminaison de la réduction ou sur la forme
normale.

• On démontre que la forme normale ne dépend pas du

choix, par contre la terminaison dépend du choix fait sur
les possibilités de réduction.
 Le λ-calcul
combinator

• une lambda fonction qui n’a pas de variable libre

• λb.b combinator

• λb.a not combinator

• λab.a combinator

• λ[Link] not combinator

 Le λ-calcul
combinator

• exemples

• λa.a identité

• λf.ff auto application

• λab.a premier

• λab.b second
 Le λ-calcul

λ TM
 Le λ-calcul

Tout peut être une Fonction

 Le λ-calcul
combinator

• Pour compléter cette modélisation pour un langage de

programmation minimal, on définie les fonctions
incrémentation, décrémentation, addition, soustraction,
les opérateurs booléens et les valeurs booléennes,

• On définie de même la récursivité,

 Le λ-calcul
Booléens
T : true λab.a VRAI

F: false λab.b FAUX

not λ[Link] Négation

and λ[Link] conjonction

or λ[Link] Disjonction

if λ[Link] if

and true false= λ[Link] true false = true false true = λpq.p false true = false.

if true p q = λ[Link] true p q = true p q = λab.a p q = p

 Le λ-calcul
Récursivité

• Y combinator

Y= λt. (λx.t(x x)) (λx.t(x x))

• Yf = λt. (λx.t(x x)) (λx.t(x x)) f = (λx.f(x x)) (λx.f(x x)) = f

((λx.f(x x)) (λx.f(x x))) = f(Y f)

• Tf = f(Yf) = f(f(Yf)) = f(f(f(Yf))) = ….

 Le λ-calcul
Récursivité

• T = λf.λ[Link](= n 1) 1 (* n f (- n 1))

• (YT) 2 = T (YT) 2 = if (= 2 1) 1 (* 2 (YT (- 2 1))) = (* 2 (YT

1)) = (2 * 1) = 2

• (YT)1 = T (YT) 1 = if (= 1 1) 1 (0 1 (Y T(- 1 1))) = 1

Programmation Fonctionnelle

notion d’expression symbolique et types

• En Lisp,

• objects de base : sortes de mots appelés atomes,

• un objet auto-évaluant,

• ou un symbole

• Une expression (en anglais form) Common Lisp peut être :

• un atome

• ou une expression composée (avec des parenthèses).

Programmation Fonctionnelle

notion d’expression symbolique et types

• Les programmes et les données sont exprimés à l’aide de la même

syntaxe « s-expressions » « expressions symboliques »:

• L’application de fonctions et les instructions conditionnelles sont écrites

comme des listes, entre parenthèses, avec le nom de l’instruction
comme préfixe, ex:

(+ 2 3) (cons a (b c )) ….

• Le programme et les données sont distinguées selon le contexte.

• Cette uniformité des données et du programme permettent une grande

flexibilité et une haute expressivité:

• Les programmes peuvent être manipulés comme des données.

Programmation Fonctionnelle

notion d’expression symbolique et types
• Les structures de données simples:

• Symboles:

• Ce sont des “mots” qui ne sont pas des nombres. Ils ne peuvent
contenir les caractères spéciaux suivants : ( ) [ ] { } ; , " ’ ‘ # /

• un symbole est généralement utilisé comme variable, son type est

implicite dépendant de sa valeur. Sa valeur est l’objet qui lui est lié (s’il
existe), par exemple: (setq pi 3.14159)

• Atomes:

• Chaines de caractères, exemple: enit ;

• nombres, entiers ou flottants, exemples: 2 , 2.3, ..

• Les atomes sont des s-expressions dont leurs valeurs sont identiques à
eux mêmes (auto-évaluant)
Programmation Fonctionnelle

notion d’expression symbolique et types
• Les Structures de Données Composées: les listes

• Le format général d’une liste:

(E1 E2 ...... En) où Ei est une S-expression.

• Dépendamment du contexte, une liste peut être traitée littéralement:

• comme une donnée:

‘((révolution Tunisie) (anniversaire "14 janvier 2017"))

• comme une application de fonction avec les paramètres passés par

valeur:

(append x y)
( + 3 5)
Programmation Fonctionnelle

notion d’expression symbolique et types
• Les Structures de Données Composées: les listes

• Une liste est une suite d’objets séparés par des blancs
et entourée d’une paire de parenthèses (le nombre
d’objets est la longueur de la liste).

• Une liste (E1 E2 ...... En) est produite par cons:

(cons E1 (cons E2 ... (cons En ()) ... ))

E1 E2 En
Programmation Fonctionnelle

notion d’expression symbolique et types
• Les listes et l’accès à leurs éléments:

• Les listes sont définies récursivement:

Une liste vide: (), (c’est aussi un atome)

Une liste non-vide: (cons ‘a L) où L est un symbole dont la valeur

est une liste.

• La tête et la queue d’une liste:

(car (cons ‘a L)) retourne a

(cdr (cons ‘a x)) retourne x

(car ()) et (cdr ()): paramètre invalide

Programmation Fonctionnelle

notion d’expression symbolique et types
• Les listes et l’accès à leurs éléments:

• Une convention de notation pour accéder aux autres éléments de la liste:

(caar x) (car (car x))

(cdadr x) (cdr (car (cdr x))))
• Par exemple, l’évaluation suivante se fait en 4 étapes:

(caadar '((p ((q r) s) u) (v)))

(caadr '(p ((q r) s) u))
(caar '(((q r) s) u))
(car '((q r) s))
(q r)
• Le deuxième élément d’une liste x — s’il existe:

(cadr x)

• Le troisième, quatrième, ... : 


(caddr x), (cadddr x), ...
 Programmation Fonctionnelle

notion d’expression symbolique et types

Construction : cons, list, list*, append, copy-list, copy-tree, revappend,

butlast, ldiff, subst, subst-if, subst-if-not,adjoin, union, intersection, set-
difference, set-exclusive-or, subsetp

Acc`es : car, cdr, member, nth, nthcdr, last, butlast, cadadr, cdaaar, . . .
first, second, . . ., tenth

Autres : length, subseq, copy-seq, count, reverse, concatenate, position,

find, merge, map, some, every, notany, notevery,search, remove, remove-
duplicates, elt, substitute, mismatch
Programmation Fonctionnelle

Règles d’évaluation
• Lisp est utilisé de façon interactive :

• Aucun programme principal,

• L’interpréteur est une boucle Read-Eval-Print. Il lit une s-expression e, l’évalue

et imprime sa valeur v (e) (ou un message spécifique).Il peut aussi lire une
“définition” et l’enregistrer.

• Un programme Lisp est une collection de fonctions qui peuvent être invoquées
directement ou indirectement par l’interpréteur.

• L’évaluation est une fonction récursive. L’évaluation d’une s-expression peut

requérir l’évaluation de sous-expressions.

• Toute s-expression est évaluée: Il faut dire explicitement à Lisp de ne pas

évaluer quelque chose (avec la fonction quote ou ‘ )

• Les symboles et les atomes sont des cas d’évaluation de base. Les autres s-
expressions constituent des cas inductifs.
Programmation Fonctionnelle

Règles d’évaluation

• Une expression tapée à la boucle d’interaction est

d’abord

• lue et analysée syntaxiquement.

• Le résultat de cette analyse est une représentation interne

de l’expression (S-expression).

• La fonction responsable de cette analyse s’appelle read.

• Cette fonction est disponible à l’utilisateur.

Programmation Fonctionnelle

Règles d’évaluation

• La S-expression est ensuite évaluée, c’est à dire que sa

valeur est calculée.

• Cette évaluation peut donner des effets de bord.

• Le résultat de l’évaluation est un ou plusieurs objets Lisp.

• La fonction responsable de l’évaluation de S-expressions

s’appelle eval.

• Cette fonction est disponible à l’utilisateur.

Programmation Fonctionnelle

Règles d’évaluation
• Les objets résultant de l’évaluation sont ensuite affichés
(ou imprimés) en représentation externe.

• La fonction responsable de l’affichage s’appelle print.

• Cette fonction est disponible à l’utilisateur.

 Programmation Fonctionnelle

Règles d’évaluation
• Les cas d’évaluation de base :

• Les atomes, comme les nombres et les chaînes de caractères,

s’évaluent à eux mêmes, ex: 2, ‘‘a’’ », 0, nil, (), T

• Les symboles sont évalués en fonction de l’environnement

courant et remplacés par leurs valeurs (état dynamique de
l’environnement),

• La liste vide () est évaluée à elle-même car elle a le double

statut de liste vide et d’atome, aussi noté nil. Elle représente
aussi la valeur booléenne false.

• L’évaluation d’un booléen donne ce booléen. La valeur

booléenne true est représentée par T (ou #t dans certains
dialectes et #f ou nil la valeur booléenne false).
 Programmation Fonctionnelle

Règles d’évaluation

• Expressions composées

• Une expression composée est une liste de sous-

expressions entourées de parenthèses : (op e1 e2 ... en)

• Le plus souvent, la première sous-expression est un

symbole

• qui est le nom d’une fonction, d’une macro ou d’un

opérateur spécial.

• Les autres sous-expressions sont les arguments de la

fonction, de la macro ou de l’opérateur spécial.
 Programmation Fonctionnelle

Règles d’évaluation
• Les cas d’évaluation de base (fonction) :

• L’expression à évaluer est une liste (e0 ... en).

• La parenthèse ouverte est la marque du cas inductif.

• Cas des combinaisons:

• 1. Les ei sont évalués (soient vi les valeurs) ; v0 doit

être une fonction dont le domaine contient (v1, . . . ,
vn).

• 2. La fonction v0 est appliquée à (v1, . . . , vn).

• 3. Le résultat est affiché.

 Programmation Fonctionnelle

Règles d’évaluation

• Cas des formes spéciales:

• La syntaxe est celle d’une combinaison, mais chaque

forme spéciale a sa propre règle d’évaluation.

• Les formes spéciales sont identifiées par un mot-clef,

qui est le premier élément de l’expression à évaluer;
 Programmation Fonctionnelle

Règles d’évaluation
CL-USER> (+ 3 4)

CL-USER> (length "hello")

CL-USER> (+ (* 3 4 2) (- 5 4) (/ 5 3))

80/3

CL-USER> (if (> 5 4) "oui" "non")

"oui"

CL-USER> (length ‘(1 2 3 4))

CL-USER> (floor 10.3)

10

0.3000002

Ici, if est un opérateur spécial, alors que +, *, -, /, >,

length sont des fonctions.

 Programmation Fonctionnelle

Règles d’évaluation
• Exemple d’évaluation d’une s-expression de type combinaison :

(+ (* 3 -2) (- 5 3))

Fonction addition v((* 3 -2)) = -6 v((- 5 3)) = 2

-4
 Programmation Fonctionnelle

Règles d’évaluation
• Exemple d’évaluation d’une s-expression de type combinaison :

(cons (cons 3 ()) (cons 5 (cons 4 ())))

Fonction cons v((cons 3 ())) = (3) v((cons 5 (cons 4 ())) =

(cons v(5) v((cons 4 ())))=

((3) 5 4)

 Programmation Fonctionnelle

Règles d’évaluation
• Autres formes spéciales:

• La fonction Quote ou ‘:

• La fonction quote bloque le processus systématique d’évaluation:

(quote pi) ou de façon équivalente: 'pi

• La fonction setq:

(setq pi 3.141592) ou (setq x (+ 3 4))

• Exemples:

(* 2.0 pi) retourne 6.283184

(* 2.0 'pi) paramètre invalide

('* 2.0 'pi) fonction invalide

(write 'pi) affiche le symbole pi

(write pi) affiche 3.141592

 Programmation Fonctionnelle

Règles d’évaluation
• Exemple d’évaluation d’une s-expression de type macro :

(and e1 ... en)

• Les ei sont évalués dans l’ordre et la première valeur

fausse est retournée ; les valeurs suivantes ne sont pas
calculées.

• S’il n’y a pas de valeurs fausses, la dernière valeur

calculée est retournée.

• S’il n’y a pas de valeurs du tout, T ou #t est retournée.

CL-USER> (and (= 2 2) (< 2 1) (/ 2 0) (+ 2 3))

NIL
 Programmation Fonctionnelle

Règles d’évaluation

• La définition d’une macro est essentiellement une

fonction qui génère du code Lisp.

• Une fonction produit des résultats mais une macro

produit des expressions-qui lorsque évaluée produit des
résultats.

• exemple :

> (defmacro nil! (var) (list ’setq var nil))

NIL!

 Programmation Fonctionnelle

Règles d’évaluation

• (nil! x) a le même effet que (setq x nil)

• l’expression (nil! var) est transformée en (setq var nil)

avant d’être évaluée.

• Deux étapes:

1. construire l’expression spécifiée par la définition de la

macro (macroexpansion)

2. évaluer l’expression à la place de l’appel de la macro

 Programmation Fonctionnelle

Règles d’évaluation
• Autres formes spéciales:

• La forme lambda :

• La fonction qui à son unique argument associe le carré de sa valeur s’écrit λx .

mult x x

• en Lisp, elle s’écrit: (lambda (x) (* x x))

• La liste (x) est la liste des paramètres.

• La liste (* x x) est le corps de la forme lambda.

==> (lambda (x) (* x x))

:-) # lambda function

==> ((lambda (pi) (* pi pi)) 12)

:-) 144

==> ((lambda (car) (* car car)) 12)

:-) 144

==> x

:-) Error - unbound variable x

 Programmation Fonctionnelle

Règles d’évaluation

• Exemples

( (lambda (x) (* 2 x))

( (lambda (x)

(- 9 ( (lambda (x) (+ 3 x)) x) ) ) x))

((lambda (w) (* 2 w))

((lambda (v)

(- 9 ((lambda (u) (+ 3 u)) v))) x))

Programmation Fonctionnelle

Porté, Réduction et Combinaison
==> (setq x 5)

:-) 5

• Les expressions qui suivent ont toutes pour valeur 2.

((lambda (x) (* 2 x)) ((lambda (x) (- 9 ((lambda (x) (+ 3 x)) x))) x))

(lambda (w) (* 2 w)) (lambda (v) (- 9 ((lambda (u) (+ 3 u)) v))) x))

(* 2 ((lambda (v) (- 9 ((lambda (u) (+ 3 u)) v))) x)) ((lambda (w) (* 2 w)) (- 9 ((lambda (u) (+ 3
u)) x)))

((lambda (w) (* 2 w)) ((lambda (v) (- 9 (+ 3 v))) x))

(* 2 (- 9 ((lambda (u) (+ 3 u)) x)))

(* 2 ((lambda (v) (- 9 (+ 3 v))) x))

((lambda (w) (* 2 w)) (- 9 (+ 3 x)))

(* 2 (- 9 (+ 3 x)))
Programmation Fonctionnelle

Occurrences libres et liées

• On retrouve les mêmes notions vues dans les fondements

théoriques avec le λ-calcul:

• Pour évaluer l’expression ((lambda (x) (+ x y)) 5) il est nécessaire

que y ait une valeur ; par contre, la valeur éventuelle de x est sans
importance.

• On peut d’ailleurs remplacer les deux occurrences de x par z, par

exemple.

• Même dans un environnement où y n’est pas lié, l’expression

(lambda (x) (+ x y)) a une “valeur potentielle”, mais cette valeur
(fonctionnelle) ne pourra être appliquée à un argument que dans
un environnement où y est lié.
Programmation Fonctionnelle

Occurrences libres et liées

• Soit une forme lambda du type (lambda (... x ...) E)

• Toute occurrence de x dans le corps E est dite liée.

• Par extension, une occurrence de x est liée dans une expression si cette
expression comporte une sous-expression (forme lambda) dans laquelle
l’occurrence en question est liée.

• Une occurrence non liée (en dehors d’une liste de paramètres) est libre.

• Dans l’expression

((lambda (x) (- 9 ((lambda (x) (+ 3 x)) x))) x)

les deux premières occurrences de x sont des paramètres, les troisième et

quatrième occurrences de x sont liées, la cinquième occurrence de x est libre.
Programmation Fonctionnelle

Arguments et valeurs des fonctionnelles

• Les fonctions, sont généralement des valeurs des formes lambda,

• On peut définir une fonctionnelle admettant d’autres

fonctionnelles comme arguments, et renvoyant une fonctionnelle
comme résultat.

• Pour pouvoir réutiliser une fonctionnelle, on lie la forme lambda

qui lui est associée à un symbole en utilisant « define » (ou
«defun» selon le langage utilisé)

• Ceci évoque les mathématiques mais contraste avec les langages

de programmation usuels, qui ne permettent généralement pas,
par exemple, de renvoyer une procédure comme résultat de
l’application d’une autre procédure à ses arguments.
Programmation Fonctionnelle

Arguments et valeurs des fonctionnelles

• La fonction de déclaration de fonction:

• La fonction defun (ou define) permet de déclarer des fonctions à introduire

dans l’environnement , de sorte qu’elles peuvent être appelées en
deuxième étape:

(defun puissance3 (x)

(* x x x))

function puissance3

—> (define puissance3(lambda (x) (* x x x)))

function puissance3

—> (puissance3 2)

8
Programmation Fonctionnelle

Récursivité et terminaison

• La récursivité est un des principes de base de la programmation

fonctionnelle,

• Le risque qui se pose avec la récursivité est l’engagement dans une

évaluation infinie, d’où se pose la question de la terminaison d’une forme
récursive,

• Exemples:

• (defun fact (n) (* n (fact (- n 1)))) qui ne termine jamais

• appel de fact avec argument négatif , ne termine jamais

• Une définition récursive d’une fonction doit comporter toujours une

condition d’arrêt de la récursivité,
Programmation Fonctionnelle

Récursivité et terminaison

• Exemple de la fonction fibonacci:

(define fib (n)

(if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))

• Terminaison de (fib n) (n ∈ N) : pas de problème (démonstration par

récurrence).

• L’efficacité du calcul est inacceptable :

(fib 9)

(+ (fib 8) (fib 7))

(+ (+ (fib 7) (fib 6)) (fib 7))

...
Programmation Fonctionnelle

Récursivité et terminaison

• Version de Fibonacci plus efficace:

(defun fib_a (n a b)

(if (= n 0) a (fib_a (- n 1) b (+ a b))))

• Si n, a et b ont pour valeurs respectives n, fi et fi+1, alors

(fib_a n a b) a pour valeur fn+i. En particulier,

(fib_a n 0 1) a pour valeur fn.

Programmation Fonctionnelle

Récursivité et terminaison

• Principe de la récursivité structurelle

• Le système “accepte” toute définition récursive syntaxiquement

correcte, même si la procédure associée donne lieu à des calculs infinis.

• L’utilisateur doit savoir si, dans un domaine donné, le calcul se

terminera toujours.

• Pour les domaines usuels, des schémas existent qui garantissent la

terminaison.

• Cas particulier : les schémas structurels, basés sur la manière dont les
objets du domaine de calcul sont construits.

• Le processus d’évaluation réduit le calcul de f(v) au calcul de f(v1), . . . ,

f(vn) où les vi sont des composants (immédiats) de v.
Programmation Fonctionnelle

Récursivité et terminaison

• Cette technique est sûre tant que l’on se limite aux domaines dont les
objets ont un nombre fini de composants (immédiats ou non),
clairement identifiés.

• Domaines usuels de base : Nombres naturels, Listes, Expressions

symboliques.

• Conceptuellement, les naturels sont construits à partir de 0 et de la

fonction successeur:

• 0 n’a pas de composant (objet de base)

• 16 est le seul composant immédiat de 17=succ(16)

• Correspondance naturelle entre les listes et les arbres. Chaque nœud

de l’arbre a un nombre fini quelconque de fils.
Programmation Fonctionnelle

Fonctionnelles typiques

• La fonction let :

• La fonction let permet à des valeurs d’avoir des noms temporaires à

l’intérieur d’une s-expression:

> (let ((a 2) (b 3)) (+ a b))

5
• L’évaluation de cette s-expression se fait come suit:

• La première s-expression est une liste d’affectation, et les symboles

utilisés auront dans le reste des s-expressions de la liste les valeurs
associées,

• Le résultat de l’évaluation de la dernière s-expression est retourné

comme valeur retournée de la fonction let,
Programmation Fonctionnelle

Fonctionnelles typiques

• La fonction if :

• La fonction if permet une évaluation similaire à la construction if-then-else, ainsi que

la fonction cond:

(if <expr1> <expr2> <expr3>)

(cond (<expr1> <expr11>) (<expr2> <expr21>) …..(<exprn> <exprn1>))

(if (= a 0) if a = 0 then

0 return 0

(/ 1 a)) else return 1/a

(cond ((= a 0) 0) if a = 0 then retrurn 0

((= a 1) 1) elsif a = 1 then return 1

(T (/ 1 a))) else return 1/a

Programmation Fonctionnelle

Fonctionnelles typiques

DEFPARAMETER toujours affecte une

valeur:

[1]> (defparameter a 1)
SETF est une macro qui utilise SETQ, mais a
A
plus de possibilités. dans un sens il est un
opérateur d’affectation plus général E.g.
[2]> (defparameter a 2)
avec SETF:

> (defparameter c (list 1 2 3))

[3]> a
> (setf (car c) 42)

2
42

> c

DEFVAR affecte la valeur 1 seule fois:

(42 2 3)

[4]> (defvar b 1)

• mais avec SETQ:

[5]> (defvar b 2)
• [> (setq (car c) 42)

B
*** - SETQ: (CAR C) is not a symbol

[6]> b

Programmation Fonctionnelle

Principales Problématiques

• L’évaluation retardée:

• Dans l’expression (if a b c) l’évaluation de b et c est retardée jusqu’à ce que a soit

évaluée et en fonction du résultat b ou c sera évaluée. Ceci explique pourquoi
cette fonction ne peut être écrite comme fonction par l’utilisateur,

• La prise en compte de ce type de processus diffère d’un L.F. à un autre et peut

rendre plus complexe la sémantique du langage,

• La gestion dynamique de la mémoire:

• Un système de gestion de la mémoire par pile, n’est pas adapté, car la référence
à des environnements locaux de fonctions peut persister même après avoir quitté
la fonction.

• Une solution consiste en l’interdiction de la désallocation de la mémoire, avec la

mise en place d’un système de « garbage collector »
Programmation logique
• Programmation logique

a- Introduction

b- fondements théoriques : rappel sur le calcul des prédicats

c – concepts de base

d- Unification

e- Principe de Résolution

f- Principe de recherche de solutions : approche non déterministe et

déterministe

g- Hypothèse du monde clos

Programmation logique
• Définition d’un langage de programmation logique:

• Un L.P. logique est un système de notation permettant d’écrire des déclarations

logiques et des algorithmes spécifiés pour implémenter les règles d’inférences.

• Ensemble des déclarations logiques = axiomes = programme logique,

• Ensemble des déclarations dérivables = théorèmes = entrées ou requêtes

ou buts

• Dans un système de programmation logique « pure » rien n’ai dit sur la façon
dont certaines déclarations doivent être dérivées. Le chemin pour y arriver ou
les étapes pour y parvenir, qu’un système automatique de déduction choisit,
relève de la partie contrôle d’un système de programmation logique.

• Paradigme de la programmation logique établi par Kowalski:

Algorithme = logique + contrôle

Programmation Logique

Naissance

• La logique comme science du raisonnement et de la preuve a existé

depuis le temps des philosophes Grecs,

• La logique symbolique comme théorie mathématique de la preuve a

démarré avec les travaux de G. BOOLE et A. De Morgan au milieu des
années 1800,

• Les déclarations logiques, ou des formes restreintes de ces

déclarations, sont vues comme un L.P. et exécutées par un ordinateur
à travers un système d’interprétation: travail réalisé par Robinson,
Colmerauer et Kowalski, a donné naissance au L.P. Prolog, dans les
années 1970s,

• Ces travaux ont conduit à la naissance d’autres L.P. logiques,

notamment des langages à base d’équation,
Programmation Logique

Naissance
Programmation Logique

Fondements Théoriques
• Rappel de logique Mathématique / Formelle:

• Le Calcul des Prédicats du 1er ordre présente la difficulté de:

• offrir une multitude de façons différentes pour exprimer les mêmes déclarations,

• Proposer plusieurs règles d’inférence,

• Par conséquent, la plupart des L.P. Logiques ont fait le choix de se restreindre à un sous-ensemble du Calcul des
Prédicats du 1er ordre:

• Utiliser seulement des Clauses de Horn

• Utiliser une seule règle d’inférence: Le Principe de Résolution

• Une Clause de Horn est une expression de la forme:

• a1⋀ a2 ⋀ a3 . . . ⋀ an → b les ai et b sont des prédicats

• Ceci signifie: b est vraie si tous les ai sont vrais, s’écrit aussi: b ← a1 ⋀ a2 ⋀ a3 . . . ⋀ an

• La clause sans queue: b ← veut dire que b est toujours vrai (formellement c’est un axiome, ou une
affirmation)

• La clause sans tête: ← a1 ⋀ a2 ⋀ a3 . . . ⋀ an représente une séquence de questions à vérifier,

Programmation Logique

Fondements Théoriques
• Rappel de logique Mathématique / Formelle:

• La transformation d’une formule du Calcul des Prédicats du 1er

ordre en une Clause de Horn, nécessite plusieurs étapes
(élimination des connecteurs autres que ⋀ et, → la
Skolémisation, élimination des quantificateurs, …) (voir cours
Logique Formelle ou Logique Mathématique);

• Exemple de passage vers une description sous forme de Clause de

Horn:

• Le pgcd de 2 entiers positifs u et v se définie par:

• Le pgcd de u et 0 est u.

• Le pgcd de u et v, si v n’est pas 0, est le même que le pgcd de v

et le reste de la division de u par v
Programmation Logique

Fondements Théoriques
• Rappel de logique Mathématique / Formelle:

• Traduction en Prédicats du 1er ordre:

• ∀u, pgcd(u, 0, u).

• ∀u, ∀v, ∀w, ¬ zero(v) ⋀ pgcd(v, mod(u, v), w) → pgcd(u,

v, w)

• Formulation sous forme de Clause de Horn:

• → pgcd(u, 0, u)

• ¬ zero(v) ⋀ pgcd(v, mod(u, v), w) → pgcd(u, v, w)

• Autre Exemple:

• ∀ x, y, z, x est le grandparent de z si x est parent y qui est parent de

z

• parent(x, y) ⋀ parent(y,z) → grandparent(x,z)

Programmation Logique

Fondements Théoriques
• Rappel de logique Mathématique / formelle:

• L’énoncé formel du principe de Résolution: (voir cours de logique formelle ou logique mathématique) :

• La mise en œuvre du Principe de Résolution sur des Clauses de Horn se présente comme suit:

Soient 2 clauses de Horn:

a ← a1 , a2 , a3 . . . , an.

b ← b1 , b2 , b3 . . . , bm.

Si bi peut être mis en correspondance (unifié ) avec a, il est possible d’inférer une nouvelle clause de Horn
de la forme

b ← b1 , b2 , b3 . . bi-1 , a1 , a2 , a3 . . . , an , bi+1 . . ., bm

Ce processus est poursuivi jusqu’à ce qu’éventuellement une clause de Horn vide soit produite. Si tel est le
cas, alors nous avons une preuve de la déclaration originelle.
Programmation Logique

Concepts de Base
• Écrire un programme en Prolog consiste essentiellement à définir un ensemble d'entités et des relations
entre ces entités.

• Pour se référer à une entité, on utilise des termes. Un terme est une constante, une variable ou un
terme composé :

• Terme Constante :

• Désigne une entité du monde.

• Tout identificateur qui commence par une lettre minuscule est une constante.

• Si on veut utiliser une constante qui commence par une lettre majuscule, il faudra la délimiter par
des apostrophes, Exemples : ali, 3, ‘ENIT'.

• Terme Variable :

• sert à désigner une entité inconnue mais qui existe.

• Aussitôt que cette entité devient connue (on dira alors que la variable est instanciée), elle sera
toujours associée à celle-ci (au sein de la même formule).

• Tout identificateur qui commence par une lettre majuscule. Une variable peut aussi commencer par
le symbole ‘_ ‘ (il s'agira alors d'une variable anonyme).
Programmation Logique

Concepts de Base

• Pour se référer à une relation, on utilise des prédicats.

• Un prédicat est une expression qui retourne une valeur de vérité quand
elle est appliquée à certains arguments (les arguments d'un prédicat sont
des termes)

• Un prédicat avec un seul argument représente une propriété, ex: grand-

de-taille (ali)

• Si un prédicat a plus d'un argument, il exprime une relation entre des

entités du monde, ex: on peut écrire une expression mere(fatma, ali) pour
indiquer que fatma est la mère de ali, ou que ali est la mère de fatma.
C’est au programmeur de se donner une convention et de la respecter
dans tout le programme,

• L'argument d'un prédicat peut être n'importe quel terme. Il peut être un
terme composé, ou simple comme une constante ou une variable.
Programmation Logique

Concepts de Base

• Un prédicat appliqué à des arguments représente une relation entre des entités du monde qui
peut être vraie ou fausse .

• Comment fait-on pour déterminer cette valeur de vérité?

• Une façon simple de le faire est de le déclarer, ou de l’affirmer, en l’exprimant comme un fait
de Prolog:

• Pour affirmer que fatma est la mère de ali, on le déclare ainsi:

mere (fatma, ali).

• Si on a plusieurs déclarations/affirmations, on les définie comme un ensemble de faits:

homme(ali).

homme(mohamed).

femme(fatma).

mere(fatma, ali).

pere(mohamed, ali).

Programmation Logique

Concepts de Base

• Requêtes:

• Pour utiliser ces faits (ce programme), il faut poser des questions à Prolog, à travers la
formulation d’une requête.

• Une requête est une expression prédicative entrée après l'invite ?- . Prolog y répondra par YES si
elle est vraie, et NO dans le cas contraire.

• Pour vérifier si fatma est une femme:

?- femme(fatma).

Yes

• On peut aussi exprimer une requête en utilisant un argument de type variable:

?- femme(X).

X= fatma

Yes

• Comment fait Prolog pour répondre à ce type de questions? Substitution et Instance

Programmation Logique

Concepts de Base

• Substitution:

• Une substitution θ est un ensemble fini (éventuellement vide) de paires de la forme Xi =

ti, où Xi est une variable et ti est un terme, qui respecte les contraintes suivantes :

- Pour tout Xi = ti ∈ θ et Xj = tj ∈ θ, où i ≠ j, on ne peut pas avoir Xi = Xj .

- Soit Xi = ti ∈ θ . Pour tout Xj = tj ∈ θ , Xi ne peut pas apparaître dans tj .

• Exemples / Contre exemples:

• Les ensembles {X = ali, Y = 2} et {X = fatma, Y = f(Z)} sont des substitutions

• L'ensemble {X = ali, Z = f(X)} n'est pas une substitution légale, parce que la variable
X ne peut pas apparaître dans un autre terme.

• L'ensemble {X = ali, Y = 2, X = fatma} n'est pas une substitution parce que X

apparaît deux fois à gauche du signe =.

• L’ensemble {X = p(Z), Y = Z} est une substitution valide.

Programmation Logique

Concepts de Base

• Substitution (suite):

• Une substitution s’applique généralement à un terme composé ou une

expression prédicative A;

• L’effet de θ sur A, noté θ A est comme suit:

• pour toute variable X présente dans A, on remplace toutes les

occurrences de celle-ci par le terme t qui lui est associé dans θ

• Exemple:

• la substitution θ = {X = ali, Y = 2}, appliquée à l'expression p(X,f(Z),Y),

produit une nouvelle expression p(ali,f(Z),2)

• θ = {X = ali, Y= 2} appliquée à A = p(X,X,fatma), donne: p(ali,ali,fatma)

Programmation Logique

Concepts de Base

• Instance:

• Une expression A est une instance d'une autre expression

B s'il existe une substitution θ telle que A = θ B.

• Par exemple:

• A = p(ali,Y) est une instance de B = p(X,Y), car A = θ B,

avec θ = {X=ali}

• p(ali,fatma) est une instance de p(X,Y) avec θ = {X=ali,

Y= fatma}
Programmation Logique

Concepts de Base
• Requêtes (suite):

• Reprenons notre programme (un ensemble de faits):

homme(ali).

homme(mohamed).

femme(fatma).

mere(fatma, ali).

pere(mohamed, ali).

• Une réponse à une requête en utilisant un ou plusieurs arguments de type variable, est une substitution
de toutes les variables apparaissant dans la requête:

?- homme(X).

X= ali 1ère substitution

X= mohamed 2ème substitution

Yes

• Ou encore:

?- pere(X,Y), femme(Y).

No Pas de substitution
Programmation Logique

Concepts de Base
• Clauses:

• Si un programme Prolog se limitait à un ensemble de faits, Prolog

n’aurait aucune utilité,

• On doit pouvoir déterminer une relation entre deux entités de façon

indirecte, par exemple pour exprimer le fait que:

une personne est propriétaire d’un objet si elle l’a acheté

• Pour ce faire, on utilise une clause pour le dire et définir un prédicat en

fonction d’autres prédicats:

proprietaire (X,Y):- acheter(X,Y).

ceci se comprend comme suit:

pour savoir si X est le propriétaire de Y, il faut vérifier si X a acheté Y

Programmation Logique

Concepts de Base
• Clauses (suite):

• Notre programme peut être complété comme suit:

proprietaire(X,Y):- acheter(X,Y).

proprietaire(X,Y):- recevoir(X,Y).

acheter(fatma,manteau).

recevoir(ali,auto).

• Requête:

?- proprietaire(X,Y).

X = fatma; Y = manteau

X = ali ; Y = auto

Yes
Programmation Logique

Unification

• Approche intuitive:

• Intuitivement, l'unification consiste en une tentative pour déterminer s'il

existe une manière d'instancier deux expressions afin de les rendre égales.

• Plus formellement, l'unification de deux termes A et B est une substitution

telle que

θ A = B. On dénote θ l'unificateur de A et B.

• Par exemple, la substitution {Y = ali, X = voiture-de(ali)} est un unificateur

des énoncés :

nettoie(ali,X) et nettoie(Y,voiture-de(Y))

• En Prolog, l’opérateur ‘=‘ signifie l’unification

Programmation Logique

Unification

• Unificateur le Plus Général d’un ensemble d’expressions

E, est un unificateur g de E (s’il existe) tel que pour tout
unificateur S de E il existe un autre unificateur S’ tel que

E S = E g S’.

• Exemple : E1 = Y E2 = f(X)

• Unificateur le plus général : {f(X)/Y}

Programmation Logique

Unification

• Approche intuitive:

• Quand Prolog tente d’unifier un but (une requête ) avec un fait ou la tête d’une
clause, il peut être amener à renommer les variables:

nettoie (ali, X)

?- nettoie(X, voiture-de(ali))

• la variable X du fait n’a rien à voir avec la variable X de la requête et donc Prolog
procède implicitement à une re-nomination des variables comme suit:

nettoie (ali, X)

?- nettoie(X1, voiture-de(ali))

• L’unification devient alors possible avec:

{X = voiture-de(ali), X1=ali}
Programmation Logique

Unification

• Approche intuitive:

• Prolog tente systématiquement de trouver l’unificateur le plus général, c’est-à-

dire celui qui n’instancie une variable que si c’est vraiment nécessaire pour
obtenir un unificateur:

nettoie(ali,X) = nettoie(Y,Z)

{ Y = ali, X = Z }

ou

{ Y = ali, X = Z, W = mohamed }

ou

{ Y = ali, X = voiture-de(ali), Z = voiture-de(ali) }

ou

...

Programmation Logique

Unification

• Algorithme d’Unification : algorithme intuitif

• Intuitivement, deux expressions prédicatives A et B s'unifient si elles sont formées à partir d'un même
prédicat, avec le même nombre d'arguments.

• Chaque argument du prédicat de A doit s'unifier avec l'argument à la même position dans B.

• Chaque argument est lui-même un terme, qui peut être une variable, une constante ou un terme
composé.

• Deux termes s'unifient si une des trois conditions suivantes est respectée :

1- Les deux termes sont des constantes identiques.

2- Un des termes est une variable non instanciée. Dans ce cas la variable sera

instanciée par l'autre terme (si ce terme ne contient pas la variable en question).

3- Les deux termes respectent les conditions suivantes :

- Ils ont le même foncteur et le même nombre d'arguments.

- Les arguments s’unifient.

Programmation Logique

Unification

function unify(E1, E2)

begin
case
both E1 and E2 are constants or the empty list:
if (E1 = E2)
then return {}
else return FAIL;
E1 is a variable:
if (E1 occurs in E2)
then return FAIL
else return {E2 / E1};
E2 is a variable:
if (E2 occurs in E1)
then return FAIL
else return {E1 / E2};
either E1 or E2 is the empty list: return FAIL
Programmation Logique

Unification

otherwise:
begin
HE1 := first element of E1;
HE2 := first element of E2;
SUBS1 := unify(HE1, HE2);
if (SUBS1 = FAIL) then return FAIL;
TE1 := apply (SUBS1, rest of E1);
TE2 := apply (SUBS1, rest of E2);
SUBS2 := unify(TE1, TE2);
if (SUBS2 = FAIL)
then return FAIL;
else return composition (SUBS1, SUBS2);
end
end
end.
 Programmation Logique

Unification

Exemple :
Programmation Logique

Unification
Programmation Logique

Unification
• Algorithme d’Unification :

• Voici l'algorithme qui retourne un unificateur (le plus général) , s'il existe, et retourne ECHEC sinon :

Exemple:
• Pour savoir qui est une femme, il suffit de
homme(ali).
faire la requête suivante :

homme(mohamed).
?- femme(X).

homme(salah).
X = fatma.

femme(fatma).
X = zohra.

femme(zohra).
X = mouna.

femme(mouna).
• Pour retourner la réponse, l'interprète Prolog
tente d'unifier le but femme(X) avec chacun
pere(salah,ali).

des faits que le programme contient, dans

pere(mohamed,ali).
l'ordre de leur apparition.

pere(mouna,salah).
• L'unification avec le fait homme(ali) échoue,
puisque les deux prédicats sont différents. Il
mere(mouna,zohra).

en sera de même pour les deux faits qui

mere(mohamed,zohra).
suivent.

mere(salah, zohra).
• C'est seulement lorsque l'interprète rencontre
le fait femme(fatma) que l'unification réussit.

mere(zohra,fatma).

Programmation Logique

Unification

• Variables anonymes:

• Une variable anonyme est une variable dont la valeur instanciée après unification nous importe peu.
Une variable anonyme est n'importe quel identificateur commençant par le symbole’_’.

• Par exemple, si on désire seulement savoir si ali a un fils, on peut faire la requête suivante :

?- pere(_,ali).

Yes

• Deux occurrences d'une variable anonyme dans un prédicat sont distinctes.

• Par exemple, si nous désirons seulement savoir s'il existe une mère, nous soumettrons la requête
suivante :

?- mere(_,_).

Yes

• Cette requête n'est pas équivalente à celle-ci :

?- mere(X,X).

No
 Programmation Logique

Unification
• Algorithme d’Unification :

• On peut utiliser directement l'opérateur "=" pour unifier deux termes (ou deux expressions prédicatives) :

?- p(X,X) = p(1,W).

?- X = 1.

X = 1

X = 1

W = 1

?- ali = mohamed.

?- p(Y,fun(Y)) = p(toto,Z).

No

Y = toto

Z = fun(toto)

?- suc(X) = suc(suc(suc(0))).

X = suc(suc(0))

?- p(X,X,2) = p(1,W,W).

No

?- p(X,X) = p(1,2).

No

Pour s'assurer que deux termes ne sont pas

unifiables, on utilise l'opérateur \= :

?- p(X,X) = p(1,1).

X = 1
?- p(X,X,2) \= p(1,W,W).

Yes
Programmation Logique

Unification

• Les Structures de Listes: Les structures de listes se présentent comme:

• [1 , 2 , 3] une liste contenant 3 éléments qui sont des constantes,

• [X|T] une liste dont la tête est représentée par la variable X et la queue par la variable
T

• L’unification de [X|T] avec [1 , 2 , 3] conduit à:

? [X|T] = [1 , 2 , 3]

X = 1 , T = [2,3]

?- [1,2|X] = [1,2]

X = []

?- [1,2|X] = [1,2,7,3,4]

X = [7,3,4]
Programmation Logique

Principe de Résolution

• Exécution d’un programme: Algorithme de Résolution

• Les règles d’un programme Prolog ont la forme suivante :

• H :- B1,B2, : : :,Bn

• H et B1,B2, : : :,Bn constituent la tête et le corps de la règle, respectivement.

• La signification d'une règle est la suivante :

• pour résoudre un but H, il faut résoudre la conjonction de buts

• B1,B2, : : :,Bn.

• Un fait peut être considéré comme une clause sans corps.

• Pour satisfaire une requête, l'interpréteur Prolog utilise l'algorithme de résolution,

qui utilise une pile, appelée résolvante, pour contenir tous les buts qui restent à
résoudre
Programmation Logique

Principe de Résolution

• Exécution d’un programme: Algorithme de Résolution

0) Se positionner à la première clause du programme

1) Résolvante = requête

2) Tant que la résolvante n'est pas vide :

2.1) Obj ← Premier objectif de la résolvante

2.2) Retirer le premier objectif de la résolvante

2.3) Chercher la première clause C = H :- B1;B2; : : :Bn telle que H s'unifie avec Obj

Si on réussit
2.4) Ajouter au début de la résolvante tous les buts B1,B2,: : :Bn

2.5) Si il existe d'autres têtes de clauses unifiables avec Obj

Mémoriser la position de la clause C comme dernier point de choix

2.6) Retourner à 2.1

Sinon
2.7) Si il existe des points de choix :
Retourner au dernier point de choix (Backtrack)

Revenir à l'étape 2.3

Sinon :

Retourner ECHEC

3) Retourner l'instantiation des variables de la requête

Programmation Logique

Principe de Résolution

Exemple:

homme(ali).

homme(mohamed).
parents(X,M,P):- mere(X,M), pere(X,P).

homme(salah).
frere(X,Y):- homme(Y), parents(X,M,P),

femme(fatma).
parents(Y,M,P).

femme(zohra).

femme(mouna).

Déroulons l’algorithme pour la requête

pere(salah,ali).
suivante:

pere(mohamed,ali).

pere(mouna,salah).

?- frere(salah, mohmed).

mere(mouna,zohra).

Yes
mere(mohamed,zohra).

mere(salah, zohra).

mere(zohra,fatma).

 Programmation Logique

Principe de Résolution
• Algorithme d’Unification :

• La recherche de solutions par Prolog est une recherche non déterministe = recherche de
toutes les solutions possibles,

• l’algorithme de recherche de Prolog repose sur une stratégie « profondeur d’abord» et de «

gauche à droite » dans la considération des buts à atteindre (à effacer) en parcourant les
clauses dans l’ordre de leur apparition dans le programme,
ancetre(X,mohamed)

Exemple:

1 5

ancetre(X,Y) :- parent(X,Z), ancetre(Z,Y).

ancetre(X,X).

parent(X,Z1), ancetre(Z1, mohamed)

parent(ali, mohamed)
2 {X=ali, Z1=mohamed} {X=mohamed}

?- ancetre(X, mohamed)
ancetre(mohamed, mohamed) succès

X=ali ->;
{X=ali}

3 4

X=mohamed ->;

parent(mohamed, Z2), ancetre(Z2, mohamed)

{X=ali, X2=mohamed, Y2=mohamed} {X=ali}

échec succès

Programmation Logique

Principe de Résolution

• Recherche de quelques solutions :

• pour limiter la recherche à quelques solutions, Prolog

fournit un opérateur de coupure de l’arbre de
recherche, l’opérateur « cut » représenté par « ! » ou « /
»

• L’ activation de l’opérateur « cut » quand il est

rencontré comme question courante, provoque le gel
des choix faits, depuis ceux de la situation courante
jusqu’aux points de choix relatifs à la question qui a fait
apparaitre le « cut » parmi la liste des questions,
 Programmation Logique

Principe de recherche de solutions
• Recherche de quelques solutions : l’utilisation du « cut »

• Exemple:

ancetre(X,mohamed)

Exemple:
1 5

ancetre(X,Y) :- parent(X,Z), !, ancetre(Z,Y).

parent(X,Z1), !, ancetre(Z1, mohamed)

ancetre(X,X).

2 {X=ali, Z1=mohamed} {X=mohamed}

parent(ali, mohamed)

!, ancetre(mohamed, mohamed) succès

?- ancetre(X, mohamed)

{X=ali}

X=ali ->;

3 4

parent(mohamed, Z2), ancetre(Z2, mohamed)

{X=ali, X2=mohamed, Y2=mohamed} {X=ali}

échec succès

Programmation Logique

Principales problématiques

• La négation par l’échec:

• Les L.P. logiques (dont Prolog) pratiquent la négation par

l'échec, c’est-à-dire que pour démontrer not(F) Prolog va
tenter de démontrer F. Si la démonstration de F échoue,
Prolog considère que not(F) est démontrée.

• Pour Prolog, not(F) signifie que la formule F n’est pas

démontrable, et non que c’est une formule fausse. C ’est ce
que l’on appelle l'hypothèse du monde clos.

• La négation par l'échec ne doit être utilisée que sur des

prédicats dont les arguments sont déterminés et à des fins de
vérification,
Programmation Logique

Principales problématiques

• La négation par l’échec: (suite)

• Dangers :

• Considérez le programme suivant :

p(a).

• Et interrogez Prolog avec :

?- X = b, not p(X).

YES {X = b}

• Prolog répond positivement car p(b) n’est pas démontrable.

• Par contre, interrogez le avec :

?- not p(X), X=b.

NO

• Prolog répond négativement car p(X) étant démontrable avec {X = a}, not p(X) est
considéré comme faux.
Programmation Logique

Principales problématiques

• Utilisation d’information de contrôle dans la

programmation logique:

• L’opérateur « cut » est un mécanisme explicite de contrôle

qui est introduit dans le programme !!!

• Le fait que la stratégie utilisée par Prolog soit la stratégie «

profondeur d’abord » et le choix de parcours linéaire des
buts de «gauche à droite», consiste en une information
implicite de contrôle qui fait que certains programmes
peuvent échouer,

• Exemple, reconsidérer le fonctionnement du programme vu

précédemment avec la clause suivante:

ancetre(X,Y) :- ancetre(Z,Y), parent(X,Z).