|
Chapitre
2
Fonction
processus Curryfication |
Chapitre
3
Théorie
des combinateurs (Présentation non formelle)
H.B. CURRY |
Chapitre
4
Théorie
des combinateurs (Présentation formelle)
L’INDUCTION |
Chapitre
5
Modélisation
Logico-Combinatoire
des réalités informatiques |
Chapitre
6
La machine SK de
D. TURNER |
|
II
FONCTIONS PROCESSUS
CURRYFICATION
2.1
Des notions à comprendre
Fonction processus vs. Fonction graphe
Fonctions en extension
Fonctions en intension
Egalité extensionnelle
-
La notion de fonction
s'est d'abord présentée comme une « activité « très
différente de la fonction ensembliste.
-
C'est la théorie des ensembles qui a introduit
la notion de « fonction graphe « définie par un ensemble:
f = { (x,y), x ∈ D, y ∈
A | y = f(x)}
2.2.1
La fonction graphe
2.2.2
Les fonctions comme activités
-
Lorsque l'on écrit f(x)
= (2 x + 1) / x, on décrit une activité
: prendre l’argument, le multiplier par 2, ajouter 1 puis
diviser par l’argument.
-
L’ancienne notation allemande des places
vides f = (2 [ ] + 1) / [ ] est
plus explicite !
2.2.3
Les fonctions graphes (Définition)
-
La fonction graphe est la fonction de nos cours
de mathématiques. Elle est définie par son « domaine
de départ », son « domaine d’arrivée »
et par son « graphe », ensemble des couples
(x,f(x)) pour x
élément du domaine de départ.
-
Le graphe peut être donné sous la forme d’une
courbe.
2.2.4
Les fonctions processus
a.Définition
-
Une fonction processus est définie par son
« processus de calcul « et non par son « graphe «.
-
Appliquer une fonction processus à un argument
revient à exécuter le processus de calcul qui définit la fonction.
-
On peut obtenir différents types de « résultats «.
b.Résultat
c.Propriétés
-
Une fonction processus n'a pas de domaine
de départ ni de domaine d'arrivée.
-
Elle peut être « définie « ou « indéfinie «
pour un argument donné.
-
La notion de processus n'est pas rigoureusement
définie, cf. la thèse de Church : elle est admise comme une et indivisible
faute d'un contre-exemple !!!
2.3
L'auto-application d'une fonction (Une différence fondamentale)
-
La notion de fonction processus
est plus large que celle de fonction graphe. Ainsi la fonction
« Identité « ou « Do Nothing « telle que I(x)=x
est définie par le processus : le résultat est l'argument.
-
L'AUTO-APPLICATION.
Ainsi définie, elle permet d'écrire I(I)=I.
I peut se prendre lui-même en argument
ce qui est axiomatiquement interdit par la théorie des ensembles.
On ne peut avoir (I,x) ∈ I.
-
Une
fonction est définie en extension si elle est définie par son
graphe.Il est alors possible que la fonction ne
soit pas « effectivement calculable «, c'est-à-dire
qu'il n'existe pas de processus de calcul permettant d'obtenir
son résultat pour un argument donné.
2.3.1
Fonctions en extension (Définition)
2.3.2 Fonctions
en intension
Définition
-
Une fonction en intension
est une fonction processus.
-
Plusieurs fonctions processus peuvent correspondre
à la même fonction en extension tout comme des programmes différents
peuvent « calculer « la même fonction.
Egalité
extensionnelle
-
Soient f
et g deux fonctions en intension,
si l'on a f(x)=g(x) pour tout x
alors f et g
sont dite « extensionnellement égale «. On note cette
égalité f =
ηg.
-
L'égalité extensionnelle est parfois appelée
la η-égalité.
2.4
Curryfication des fonctions
Fonction curryfiée
H.B. Curry
Parenthésage des arguments
L'application
2.4.1
Arité d'une fonction
-
On appelle « arité «
d'une fonction son nombre d'arguments.
-
Une fonction d'arité 1 est dite « monadique «.
-
Une fonction d'arité strictement supérieure
à 1 est dite « polyadique «.
2.4.2
La curryfication
-
Soient
f(x,y) une fonction d'arité 2
-
On considère Fx
définie par Fx(y) = f(x,y)
-
Enfin, on considère F
telle que F(x)=Fx
De
telle manière que l'on a :
f(x,y) = Fx(y) = (F(x))(y)
F est appelée la « curryfiée « de f
-
Nous décidons de ne considérer que les versions
curryfiées des fonctions.
-
Nous sommes alors dans un « monde «
où toutes les fonctions sont monadiques.
-
L'application d'une fonction f
à n arguments x1,...,xn
s'y écrit :
((...((f (x1))(x2))....)(xn-1))(xn)
C'est
un peu lourd mais...
2.4.3
Le parenthésage
(2 + 3) * 5
f(2+3,5)
-
Le parenthésage des arguments joue également
un rôle associatif !
-
A quoi sert le parenthésage des arguments
?
-
Réponse : à RIEN si l'on connaît l'arité
des fonctions. Seul le rôle associatif du parenthésage est nécessaire
!
-
Exemple. Les deux écritures suivantes sont syntaxiquement correctes
et lisibles si l'on sait que F est une fonction d'arité
3, g une fonction d'arité
2 et h une fonction d'arité
1 :
F(g(x,h(y)),h(z),f(F(x,y,z),x))
ou
F (g x (h y)) (h z) (f (F x y z) x)
-
Si l'on se place dans un monde curryfié,
toutes les fonctions sont monadiques et l'on peut supprimer le parenthésage NON-ASSOCIATIF
des arguments :
((...((f (x1))(x2))....)(xn-1))(xn)
ou
((...((f x1)
x2)....) xn-1) xn
-
En revanche f(2 + 3)
ne se déparenthèse pas à cause du rôle associatif des parenthèses.
2.4.4
L'application
app(f,x) = f (x) = f x
-
On pourrait également la noter avec un symbole
infixé, par exemple :
f . x
-
L'opération binaire d'application fut mise
en évidence en 1925 par Von Neumann, le père des ordinateurs
actuels.
-
On dit que Von Neumann a réalisé l'abstraction
de la fonction et de l'argument dans une expression de type
(f x).
-
C'est exactement ce que l'on fait lorsque
l'on écrit f(x) = (x + 1)/2 :
on réalise l'abstraction de x dans (x+1)/2.
L'opération
d'application
x + y + z = (x + y) + z
x . y . z = (x . y) . z
Application
d'une fonction
-
Notation usuelle : f
(x1,x2,...,xn-1,xn)
-
Notation curryfiée : ((...((f
(x1))(x2))...)(xn-1))(xn)
-
Déparenthésage de l'argument
:
((...((f
x1) x2)...) xn-1) xn
((...((f . x1) . x2)...)
. xn-1) . xn
f . x1 . x2
... . xn-1 . xn
f x1 x2 ... xn-1
xn
2.4.5
Convention adoptée
Nous
adoptons les conventions suivantes :
-
Les fonctions sont curryfiées.
-
Déparenthésage de l'argument.
-
Associativité à gauche de l'application.
Donc
:
-
(x + 1) * (2 + 6)
devient * (+ x 1) (+ 2 6)
-
f(g(x,y),z)
devient f (g x y) z
-
+ 1 est la fonction
« successeur «.
|