Transcript
Page 1: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

A. Introduction Définition, Caractéristiques, Schéma fonctionnel, Quelques langages fonctionnels B. Lambda-calcul

Variables et fonctions en mathématiques La λλλλ -notation, Fonction à plusieurs arguments Les systèmes λλλλ-applicatifs, Grammaire du λλλλ-calcul Notion de variables libres et liées,

Page 2: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

B. Lambda-calcul Changement de variables

Substitution Contraction Réduction Théorie propre du -calcul Forme normale Ordre de réduction Théorème de Church-Rosser ( première forme ) Théorème de Church-Rosser ( deuxième forme ) Fonctions récursives

Page 3: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Introduction

• Définition :— Le traitement est décrit par application de fonction.— Exemple : f[g(x, h(x), f(x-1, g(h(x-1), 2) ]

• Caractéristiques :— Facilité d'exprimer et de prouver les programmes.— Basé sur un système formel (Lambda-calcul)— Absence d'affectation— Absence de contrôle explicite ( GOTO, EXIT). les langages

fonctionnels ne sont pas impératifs.— calcul basé sur les fonctions.

Page 4: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Introduction

• Schéma de programme fonctionnel: Un seul type de contrôle implicite : Si Cond alors inst1 sinon inst2

Fsi.

• Les instructions peuvent être : conditionnelle, appel de fonction.

• Exemple Fact(n) : Si n = 0 alors 1 sinon mult(n, Fact(n-1)) Fsi

Page 5: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Introduction

• Exemple de langages fonctionnels:

• LISP ( Processor of Listes, Mac Carthy 1960)• ISWIN ( Landin 66)• FP ( Backus 78)• HOPE (80)• MIRANDA(85)

Page 6: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Variables et fonctions en mathématiques : Inconvénient de la notation usuelle

• En mathématiques, la notation usuelle f(x) ne nous permet pas dedistinguer entre la fonction elle-même et la valeur de la fonction pour une valeur déterminée de la variable.

• Ce défaut apparaît clairement dans les théories qui utilisent les fonctions de fonctions.

• Par exemple, dans les théories qui utilisent les opérateurs P et Q, l'application de l'opérateur P à la fonction f(x) est généralement notée P[f(x)]. Que signifie alors P[f(x+1)] ?

Page 7: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� La λλλλ-notation

• Si nous notons par M l'expression qui contient x qui indique la valeur de la fonction quand l'argument a la valeur x nous écrivons λλλλx(M) pour désigner la fonction elle-même. Cette formation est abstraction fonctionnelle.

• Pour désigner la valeur de la fonction pour la valeur 0 par exemple nous écrivons λλλλx(M) (0).

• Ainsi, λλλλx(x2) est la fonction carré.

• Autres abréviations : λλλλxM, µx.M

Page 8: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Fonction à plusieurs arguments

• Pour des fonctions à plusieurs arguments, nous pouvons aussi définir une abstraction fonctionnelle :

λλλλnx1x2....xn.M

• λλλλy(x+y) : désigne l'opération d'addition de l'argument y à x. ( x est alors fixe).

c'est f(y) = x+y

• λλλλx(λλλλy(x+y)) c'est f(x,y) = x +y

• λλλλ2xy.x+y ou λλλλx: λλλλy.x+y

Page 9: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Les systèmes λλλλ-applicatifs

• Un système λλλλ applicatif, défini de manière générales, est un système dans lequel les seules opérations sont l'abstraction fonctionnelle et des applications.

• L'application est représentée par une simple juxtaposition. Ainsifab signifie f appliqué à a, puis le résultat appliqué à b.

Donc fab est (fa)b. fabc c'est ((fa)b)c De cette façon, les valeurs de fonctions à plusieurs variables sont

construites progressivement.

Page 10: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Grammaire du λλλλ-calcul

• Syntaxe V = { x, y, ...} ensemble des variables. C = { a, b, ...} ensemble des constantes.

L --> C / op L --> V L --> ( L L ) associativité à gauche(application) L --> (λλλλV L) associativité à droite(abstraction fonctionnelle)

Page 11: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Grammaire du λλλλ-calcul

• ( L L L ) c'est ( (L L) L )• (λλλλxλλλλyL ) c'est (λλλλx (λλλλyL) )

• Exemple :

• (λλλλxx) est obtenu par abstraction : f(x)• ((λλλλxx)3) est obtenu par application : f(3)

Page 12: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Notion de variables libres et liées

• Une occurrence d'une variable x dans Y est liée ssi x est à l'intérieur d'une partie de Y de la forme λλλλx.Z, sinon elle est libre.

• Variables libres• Soit X, Y dans L et soit x dans V et a dans C.

• Varlib(a) = {}• Varlib(x) = {x}• Varlib(XY)= Varlib(X) U Varlib(Y)• Varlib(λλλλxX)= Varlib(X) - {x}

Page 13: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Notion de variables libres et liées

• Variables liées

• Varlié(a) = {}• Varlié(x) = {}• Varlié(XY)= Varlié(X) U Varlié(Y)• Varlié(λλλλxX)= Varlié(X) U {x}

Page 14: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Notion de variables libres et liées : Exemple

• X = ( (λλλλx(λλλλy.y) λλλλz.x) ) de la forme X = ( M N)

Varlib(X) = Varlib(λλλλy.y) - {x}Uvarlib(x)-{z} Varlib(y)- {y} - {x} U {x} - {z} {y} - {y} - {x} U {x} - {z} {} U {x} {x}

Page 15: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Notion de variables libres et liées : Exemple

X = ( (λλλλx(λλλλy.y) λλλλz.x) ) de la forme X = ( M N)

Varlié(X) = Varlié(λλλλy.y) +{x}UVarlié(x)+ {z} Varlié(y) + {y} + {x} U {} + {z} {} + {y} + {x} U {} + {z} { x, y, z }

Page 16: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Notion de variables libres et liées

• Nous remarquons que x est liée dans M mais libre dans N. Nous pourrions écrire indifféremment

X = ( (λλλλt(λλλλy.y)) λλλλz.x))

car on peut toujours changer le nom de la variable liée.

Page 17: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Changement de variable liée : (Alpha-conversion)

• Un changement de variable liée dans un terme X est le remplacement d'une partie de X de la forme λλλλy.Z, avec y non liée dans Z, par λλλλv.[v/y]Z pour tout v qui n'est ni libre ni liée dans Z.

• (Alpha) : Si y n'est pas libre dans M, alors λλλλx.M = λλλλy[y/x]M.

• Congruence :— X est congruent à Y ssi Y est le résultat d'application d'une série

de changements de variables liées.— La congruence est une relation d'équivalence.

Page 18: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Substitution

• Soit N et M dans L et x une variable libre de M.

• [N/x]M : substituer N à x dans M.• [N/x]a = a• [N/x]x = N• [N/x]y = y si y # x• [N/x](M1M2) = [N/x]M1 [N/x]M2• [N/x](µxM) = (λλλλxM)

Page 19: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Substitution• [N/x]( λλλλyM) = x # y y non libre dans N c'est (λλλλy [N/x] M ) y libre dans N c'est λλλλz [N/x] ([z/y]M)

• Exemple : Prenons M = λλλλy.xy et N = y [t/x] λλλλy.xy = λλλλy.yt (1) [y/x] λλλλy.xy = λλλλy.yy (confusion) =[y/x] λλλλz.xz =λλλλz.zt ce qui est équivalent à(1)

Page 20: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Contraction : Béta-conversion

• Une λλλλ -expression de la forme (λλλλ x.M) N s'appelle un Béta-radical ou Béta-rédex ou rédex.

avec (λλλλ x.M) une abstraction fonctionnelle et (λλλλx.M) N une application

• (Beta) : Si x n'est pas liée dans M alors (λλλλx.M) N = [N/x] M

• si λλλλ x.M est une fonction, son application à n'importe quel N doit être vue comme le résultat de la substitution de x par N dans M

Page 21: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Contraction : Béta-conversion

• Ici aussi, il y a possibilité de confusion de variables. Supposons M = λλλλx.xy et N = y. La substitution de x par N sans tenir compte des variables liées

dans M nous donne λλλλy.yy Mais si nous transformons M en λλλλz.zy ( par (alpha) ) puis nous

substituons x par y nous obtenons finalement λλλλz.zy Il s'agit en d'autres termes d'une substitution aux occurrences

libre de x dans M. Donc, une telle confusion peut apparaître si une variable libre

dans N est liée dans N. Ainsi, l'objet Béta-rédex a pour contractant [N/x]M qui est une

Béta-contraction.

Page 22: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Remarques

• Les règles (Alpha) et (Béta) prises ensemble constituent la Beta-conversion.

• La règle (Alpha) prise seule constitue la Alpha-conversion.

Page 23: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Réduction

• X se réduit à Y (=>) ssi Y est le résultat d'une série(éventuellement vide) de changement de variables liée et de contractions.

=> est réflexive et transitive.

• Exemples : 1. (λλλλ x.xy)F => Fy 2. (λλλλx.y)F => y 3. (λλλλx.(λλλλy.yx)z)v)=> [v/x](( λλλλy.yx)z) == (λλλλy.yv)z => [z/y] (yv] == zv 4. (λλλλx.xxy)( λλλλx.xxy) => (λλλλx.xxy)( λλλλx.xxy)y => (λλλλx.xxy)( λλλλx.xxy)yy => ect...

Page 24: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Théorie propre du λλλλ-calcul

• L'ensemble des énoncés de la forme X >> Y qui sont vrai.• Règles : Alpha, Béta, Axiome( X >> X) et les règles de déductions :

1. X >> Y ==> ZX >> ZY 2. X >> Y ==> XZ >> YZ 3. X >> Y ==> λλλλx.X >> λλλλx.Y 4. X >> Y et Y >> Z ==> X >> Z

Page 25: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Théorie propre du λλλλ-calcul

• Formellement, nous dirons que X >> Y ssi il existe une preuve de cet énoncé utilisant uniquement les axiomes et les règles ci dessus.

• (Eta) : Si x n'est pas libre dans M,alors λλλλx.(Mx) = M

• (Tau) : Si x n'est pas libre ni dans M ni dans N alors• Mx = Nx ==> M = N

Page 26: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Forme normale :

• Un objet sera dit être dans une forme normale, d'une certaine µ-expression s'il ne contient aucun rédex. [ (λλλλx.M) N ]

• Dans l'exemple 3, zv est la forme normale de (λλλλ x.(λλλλy.yx)z)v)

• Le terme de l'exemple 4 n'a pas de forme normale.

Page 27: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Ordre de réduction

• Ordre normal : Plus externe, plus à gauche dans le même niveau. ( par nom)

• par valeur : Plus interne, Plus à gauche dans le même niveau

• Il existe d ’autres ordres

• Deux chemins différents de réduction peuvent-ils aboutir à des formes normales différentes ?

Page 28: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Théorème de Church-rosser première forme

• Si U=>X et U=>Y, il existe Z tel que X=>Z et Y=>Z.

• Corollaire :

Si U a des formes normales X et Y, alors X est congruent à Y ( On peut passer de X à Y par des changements de variables )

Page 29: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Théorème de Church-rosser ( deuxième forme )

• Si E1 ==> E2 et Si E2 forme normale alors il existe une suite de réduction de E1 à E2 selon l ’ORDRE

NORMAL.

• L ’ordre normal garantit de trouver une forme normale si elle existe mais ne garantit pas de la trouver par un nombre minimum de réduction.

Page 30: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Fonctions récursives

soit Fact = (λλλλ n. si (= n 0) 1 (* n (Fact ( - x 1) ) ) ) de la forme Fact = λλλλn. ( ….Fact …) par une Béta-abstraction Fact = (λλλλ fac .(λλλλn. ( …fac …))) Fact Fact = H Fact (1) avec H = (λλλλ fac .(λλλλn. ( …fac …))) (1) implique que Fact est un point fixe de H.

Page 31: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Fonctions récursives

• Il suffit donc de trouver un point fixe de H.

• On démontre que YH = H (YH) , c ’est à dire que YH est un point fixe de H.

• Y est appelé le combinateur du point fixe.

• Solution Fact = YH.

Page 32: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Fonctions récursives : Exemple : Calcul de Fact 1 YH 1 = H (YH) 1 (λλλλ fac. λλλλn. si (= n 0) 1 (* n (fac ( - n 1 )))) YH 1 ( λλλλn. si (= n 0) 1 (* n ( YH ( - n 1 )))) 1 si (= 1 0) 1 (* 1 ( YH ( - 1 1 ))) * 1 ( YH 0 ) * 1 ( H (YH) 0 ) * 1 (λλλλfac. λλλλn. si (= n 0) 1 (* n (fac ( - n 1 )))) (YH) 0 ) * 1 ( λλλλn. si (= n 0) 1 (* n ( YH ( - n 1 )))) 0 * 1 (si (= 0 0) 1 (* 0 ( YH ( - 0 1 ))) * 1 ( 1) 1

Page 33: Programmation fonctionnelle - ESI

Programmation fonctionnelleLambda-calcul

� Fonctions récursives : Combinateur Y

• Y =( λλλλh . (λλλλx. h ( x x)) (λλλλx.h (x x)) )

• Montrons que YH = H (YH)

YH = ( λλλλh . (λλλλx. h ( x x)) (λλλλx.h (x x)) ) H YH = (λλλλx. H ( x x)) (λλλλx.H (x x)) YH = H (λλλλx.H (x x) (λλλλx.H (x x) YH = H ( YH )

Donc YH point fixe de H.


Recommended