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

• Le processus peut se terminer en fournissant un résultat.

• Le processus peut ne pas se terminer tout comme un programme qui boucle.

• Le processus peut se terminer en fournissant un message d’erreur.

  Dans les deux derniers cas, on dit que le résultat est « indéfini ».

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

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

• 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.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é.

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 F_x définie par F_x(y) = f(x,y)

• Enfin, on considère F telle que F(x)=f_x

De telle manière que l’on a :

f(x,y) = f_x(y) = (F(x))(y)

• L’opération qui permet de passer d’une fonction ordinaire à sa version curryfiée est appelée la « curryfication » de la fonction en hommage au logicien H.B. Curry qui l’a rendue célèbre.

• La curryfication se généralise à des fonctions d’arité quelconque. Exemple :

g(x,y,z) = ((G(x))(y))(z)

• 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 x₁,…,x_n s’y écrit :

C’est un peu lourd mais…

2.4.3 Le parenthésage

 
• Parenthésage associatif :

• Parenthésage des arguments d’une fonction :

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 (x₁))(x₂))….)(x_n-1))(x_n)

ou

((…((f  x₁) x₂)….) x_n-1) x_n

• En revanche f(2 + 3) ne se déparenthèse pas à cause du rôle associatif des parenthèses.

2.4.4 L’application