Et si on commençait par les fonctions !

Piste rouge Le 28 août 2009  - Ecrit par  Pierre Lescanne Voir les commentaires (16)

Dans cet article on montre qu’au lieu de fonder les mathématiques sur la notion d’ensemble comme le veut la tradition, on peut mettre la notion de fonction au centre de l’édifice.

Du bon usage des flèches

Cet article fait usage de trois types de flèches :

$\quad$

$\quad$

  • la flèche vers la droite précédée de sa barre verticale $\mapsto$ pour décrire les fonctions.
  • la flèche pointée vers la droite $\rightarrow$ pour la réduction des expressions
  • la flèche pointée vers la gauche ← pour la substitution d’une variable par une expression.

Plutôt que des symboles ésotériques, nous avons choisi ces symboles qui sont d’usage courant en mathématiques. Que le lecteur nous pardonne la gymnastique que cela impose pour s’y retrouver.

Du passé faisons table rase

Dans la théorie des ensembles, une fonction $f$ sur un ensemble $A$ est définie par son graphe, c’est-à-dire par l’ensemble des couples $(a, f(a))$ quand $a$ varie sur $A$. La définition du concept de fonction ne vient qu’après celui d’ensemble, une fonction étant définie comme un ensemble particulier. On dit aussi qu’elle est définie en extension, autrement dit qu’on parcourt (qu’on « s’étend » sur) l’ensemble des couples valeurs-résultats. En fait, on ne dit pas comment la valeur $f(a)$ est obtenue à partir de $a$, mais on dit simplement qu’elle est associée à $a$, d’une façon, certes rigoureuse, mais plus ou moins « magique ».

Dans ce qui suit nous allons voir comment on construit les mathématiques à partir de rien ou presque [1]. Traditionnellement depuis Cantor, le point de départ des mathématiques est celui d’ensemble. Nous allons, quant à nous, partir du concept de fonction, mais pas des fonctions du lycée sur les nombres réels, mais des fonctions qui manipulent ce qu’on connait déjà.

Mais au fait qu’est-ce qu’on connait quand on dit que le concept primitif est celui de fonction ? Mais les « fonctions » pardi ! Donc les fonctions que l’on va considérer sont des fonctions sur les fonctions.

JPEG - 494.1 ko

Deux petites fonctions bien gentilles

Commençons par une fonction vraiment simple (peut-être trop simple), la fonction identité sur $a$. Vue de façon ensembliste, son graphe est la « diagonale » de l’ensemble produit $A \times A$, autrement dit l’ensemble des couples $(a,a)$. On aimerait dire que c’est la fonction qui à $a$ associe $a$, en décrivant comment on obtient le résultat (c’est-à-dire $a$) à partir de la donnée (c’est-à-dire $a$), autrement dit on voudrait énoncer que la fonction identité c’est $a \mapsto a$. La fonction identité n’est pas assez compliquée, passons donc à la fonction carré sur $\mathbb {N}$ [2]. Son graphe contient “(3,9), (0,0), (2,4), (4,16), (1,1), (12, 144), ...”, avec l’inconvénient de mettre des points qui laissent planer un doute sur ce qui n’est pas dit. On souhaiterait plutôt affirmer que carré est $n \mapsto n \times n$, en faisant l’hypothèse que l’opérateur de multiplication $\times$ a déjà été défini. On dit alors que $a \mapsto a$ et $n \mapsto n \times n$ sont des définitions en intention, car elles portent en elles ce qu’on veut dire par les mots « fonction identité » et « fonction carré », c’est-à-dire un mécanisme qui dévoile comment on obtient (comment on calcule) le résultat à partir de la valeur qu’on a donnée. La fonction s’identifie à ce qu’on a l’« intention » de lui faire dire, d’où l’adjectif « intentionnelle ». Tout ça est un peu philosophique, mais ça va se clarifier par la suite.

Le mutisme des variables

Nous avons écrit $a \mapsto a$, mais nous aurions tout aussi bien pu écrire $x\, \mapsto\, x$ ou $y\mapsto y$, pour la même fonction. De même nous aurions pu écrire $k \mapsto k \times k$ ou $y \mapsto y \times y$ au lieu de $n \mapsto n \times n$. Cela signifie que le nom de la variable n’est pas vraiment important et qu’on peut donc la « renommer ». On dit aussi que la variable $x$ est liée dans l’expression $x \mapsto x$ ou qu’elle est rendue muette. Le rôle de $x$ est le même dans $x \mapsto x$ que dans ${\forall \ x. (x \in \mathbb{Z}) \Rightarrow x^2 \geq 0}$. Dans l’une et l’autre expression $x$ peut-être changé en $y$ sans changer sa signification. On sait en effet que ${\forall \ x. (x \in \mathbb{Z}) \Rightarrow x^2 \geq 0}$ a le même sens que ${\forall \ y. (y \in \mathbb{Z}) \Rightarrow y^2 \geq 0}$, c’est la même chose avec $x \mapsto x$ qui a le même sens que $y \mapsto y$.

Appliquer une fonction à une valeur

Une fonction est faite pour s’appliquer à des valeurs. Rappelons que les valeurs sont elles-mêmes des fonctions. Si on a une fonction $f$ et une valeur $a$ on va noter $f~a$ le résultat de l’application de $f$ à $a$ [3]. Ainsi l’application de l’identité à $b$ s’écrit $(a \mapsto a)~b$ et l’application de l’identité à carré s’écrit $(a \mapsto a)~ (n \mapsto n \times n)$. On a donc deux constructions de base, l’opérateur $\mapsto$ (que nous appellerons abstraction) et l’application [4].

JPEG - 343.4 ko

Encore quelques fonctions

Avec notre opérateur $\mapsto$, on peut définir des fonctions disons assez naïves ou assez « fondamentales » :

  • la fonction qui fabrique des fonctions constantes, c’est une fonction à laquelle on donne une valeur, disons $c$, et qui retourne la fonction identique à $c$, à savoir
    $c \mapsto (x \mapsto c)$. Donnons lui son nom traditionnel et appelons la K. Notons que le premier $\mapsto$ des deux prend $c$ et produit une fonction.
  • la fonction qui permute ses arguments, c’est la fonction qui prend une fonction $f$ et retourne la fonction qui rend $f~y~x$ quand on lui donne $x$ puis $y$, autrement dit la fonction :
    $f \mapsto (x \mapsto (y \mapsto (f\ y\ x))$. Donnons lui son nom traditionnel et appelons la C. Quand on applique C$~f$ à $x$ et $y$ on obtient $f~y~x$.
  • la fonction deux, c’est la fonction qui prend une fonction et rend la fonction obtenue en l’appliquant deux fois à son argument, autrement dit c’est $f \mapsto (x \mapsto f\ (f\ x))$. Si on applique deux à carré on obtient la fonction bicarré, qui rend la puissance quatre de sa valeur, autrement dit (deux carré) a le même effet [5] qu’une fonction que l’on noterait $n \mapsto n \times n \times n \times n$.

On vient de voir qu’on a considéré des fonctions qui retournent des fonctions comme le fait la fonction K ou des fonctions qui prennent comme valeur des fonctions comme le fait la fonction C. Rien d’étonnant à cela, puisqu’à partir de maintenant, tout est fonction ou, comment disent certains, les fonctions sont les citoyens de première classe [6]. Notons au passage, un fait remarquable, à savoir que la fonction identité est aussi bien l’identité sur $A$, sur $B$, sur ℕ, sur les fonctions de $A$ vers $B$, etc. Comme elle est définie sur le « comment » plutôt que sur le « quoi » elle peut servir à plusieurs endroits, on dit qu’elle est « polymorphe » et c’est très bien ainsi.

Un nouveau calcul

Nous avons bien défini des fonctions, mais nous ne savons pas quoi en faire.

Calculer ou réduire des expressions

On applique une fonction à une valeur, ainsi si on applique la fonction identité à la valeur $\textbf{v}$, cela donne $(a \mapsto a) ~\textbf{v}$, oui mézalor ça n’est pas exactement ce qu’on veut ! On veut que $(a \mapsto a)~ \textbf{v}$ « donne » $\textbf{v}$. Pour cela, il nous faut un mécanisme de réduction des expressions qui se fonde lui même sur une notion de substitution. Nous n’insisterons pas sur ce mécanisme de substitution, nous dirons simplement qu’il doit être subtil, car il faut faire très attention aux variables liées, en évitant de lier une variable qui ne l’était pas ou de renommer une variable liée. Nous supposerons que les lecteurs sont assez intelligents pour éviter de tomber dans ces pièges [7]

Notons $\mathbf{t}[x←u]$ la substitution de la variable $x$ par l’expression $ \mathbf{u}$ dans l’expression $\mathbf{t}$. La réduction de $(x \mapsto \mathbf{t})~ \mathbf{t}'$ produit $\mathbf{t}[x←\mathbf{t}']$. Ainsi la réduction de $(a \mapsto a)~ \mathbf{v}$ est bien $\mathbf{v}$ puisque clairement $a[a←\mathbf{v}]$ est $\mathbf{v}$. La réduction se note par une flèche $\rightarrow$, ainsi on écrit : \[(x \mapsto \mathbf{t})~ \mathbf{t}' \quad\rightarrow \quad \mathbf{t}[x←\mathbf{t}'].\]

Des expressions qui ne se réduisent jamais

La plus simple de ces expressions qui ne se réduisent jamais est l’expression $Ω = (x \mapsto x~x)~(x \mapsto x~x)$. La variable $x$ apparait liée à deux endroits différents, renommons donc le deuxième $x$ ! Cela donne $(x \mapsto x~x)~(y \mapsto y~y)$. Réduisons cette expression :

\[(x \mapsto x~x)~(y \mapsto y ~y) \quad \rightarrow\quad (x~x)[x ← (y \mapsto y ~y)] \ \equiv\ (y \mapsto y~y)~(y \mapsto y~y).\]

Surprise c’est la même à un renommage près ! Mais il faut dire que cette fonction $x$ qui s’applique à elle-même a de quoi surprendre.

Une expression plus « utile » est $\mathbf{Y} = f \mapsto (x \mapsto f~(x~x))~(x \mapsto f~(x~x))$. Si on applique $\mathbf{Y}$ à $\mathbf{g}$, on constate que $\mathbf{Y~g}$ se réduit vers $\mathbf{g~(Y~g)}$. Autrement dit si l’on considère que deux expressions qui se réduisent l’une à l’autre sont « égales », on voit que $\mathbf{Y~g}$ est une expression qui est « égale » à $\mathbf{g}~(\mathbf{Y}~\mathbf{g})$, les mathématiciens disent que $\mathbf{Y~g}$ est un point fixe de $\mathbf{g}$.

Donner un sens aux expressions

Quand on a une expression un peu compliquée, on peut lui donner un sens en la réduisant jusqu’à ce qu’on ne puisse plus le faire. Mais deux questions surgissent :

  • Y a-t-il au plus une forme irréductible ? La réponse est oui. En effet, quand on a le choix entre deux réductions possibles, si on choisit l’une plutôt que l’autre, cela n’a pas de conséquences, car on pourra toujours « se rattraper » plus tard et retomber vers le réduit de l’autre.
  • La réduction s’arrête-elle toujours ? La réponse est non [8], comme on vient de le voir.

À partir de là, il y a deux solutions pour donner du sens.

  • On ne considère que des expressions pour lesquelles la réduction termine, on peut le faire en restreignant les expressions acceptables, c’est-à-dire en limitant l’usage de l’application et de l’abstraction. On élimine en particulier, les fonctions qui s’appliquent à elle-même [9]

Un calcul sans paires

Jusqu’à maintenant nous n’avons pas parlé de paires, parce nous n’avons pas eu besoin et nous n’en aurons pas besoin. En fait, au lieu d’écrire $f(x,y)$, on écrit $f~x~y$ et le processus qui consiste à appliquer la fonction $g$ d’abord à $x$ puis à appliquer le résultat $g~x$ à $y$, autrement dit $g~x~y$, jouera le rôle de $g(x,y)$.

Application, abstraction et variables

Le formalisme que vous venons de définir est particulièrement épuré. Il a deux constructions : l’abstraction et l’application. Il y a en plus les variables pour démarrer la construction des expressions et la réduction pour calculer sur les expressions et leur donner un sens. C’est ce formalisme simple qui peut servir de base aux mathématiques.

Définir les entiers naturels

Von Neumann a le premier proposé de définir les entiers naturels dans la théorie des ensembles en procédant comme suit.

  • ø est 0, autrement dit, vide représente l’entier zéro.
  • {ø} est 1, autrement dit l’ensemble qui ne contient que l’ensemble vide représente l’entier 1.
  • {{ø}, ø}, autrement dit {1, ø} est 2, autrement dit 2 est l’ensemble qui contient les deux ensembles 0 et 1, c’est-à-dire l’ensemble vide et le singleton qui ne contient que vide.
  • Plus généralement, pour représenter l’entier n+1 comme un ensemble on ajoute le singleton $\{$n$\}$ fait de l’ensemble n seul à l’ensemble qui représente n. Cet ensemble a exactement n+1 éléments.

Pour représenter les entiers dans les fonctions, on part d’une idée similaire, on essaye de trouver une fonction que l’on peut associer naturellement aux entiers. Nous avons déjà vu la représentation de l’entier $2$, c’est la fonction deux qui associe à la fonction $f$ la répétition deux fois de la fonction $f$. La fonction $\mathbf{n}$ est donc la fonction

\[f \mapsto (x \mapsto f (... {\scriptstyle n}{\scriptsize fois} ... (f~x))\]

c’est-à-dire la répétition $n$ fois de la fonction $f$. Le nombre $5$ est donc représenté par la fonction $\mathbf{cinq} = f \mapsto (x \mapsto f~(f~(f~(f~(f~x)))))$. Le nombre $0$ est représenté par la fonction $f \mapsto (x \mapsto x)$, autrement dit la fonction constante qui prend toujours la valeur identité. Le nombre $1$ est donc représenté par la fonction $f \mapsto (x \mapsto f~x)$.

A partir de là, on peut décrire toute l’arithmétique dans la théorie des fonctions et de là toutes les mathématiques. Ainsi l’addition de deux entiers naturels est définie par la fonction :

\[ \mathbf{add} = (p \mapsto (q \mapsto (f \mapsto (x \mapsto (p~f)~((q~f)~x ))))).\]

Un peu d’histoire

L’origine de tout cela est un livre dû à Russell [10] et Whitehead dont une légende dit que personne ne l’a jamais lu tant il est rébarbatif, qui s’appelle les Principia Mathematica et qui avait pour but de fonder rigoureusement les mathématiques dans la tourmente de la crise des fondements. Cette recherche a été revitalisée par Alonzo Church, pour donner le formalisme décrit ici avec des notations différentes cependant.

A quoi tout cela sert ?

Ce formalisme a plusieurs applications contemporaines.

  • Fonder les mathématiques.
  • Offrir un cadre rigoureux et efficace pour raisonner, conduisant à la mécanisation du raisonnement sur ordinateur et aux assistants de preuve modernes comme Coq [11].
  • Fournir un fondement mathématique aux langages de programmation et par là initier un nouveau style de programmation [12].

En savoir plus

  • Ceux qui veulent appréhender les ressorts philosophiques de cette théorie liront le livre de Gilles Dowek, Les métamorphoses du calcul : une étonnante histoire de mathématiques, Le Pommier, Essais, (2007). Grand prix de philosophie de l’Académie Française.
  • Ceux qui veulent comprendre la mathématique de tout cela liront le livre de Jean-Louis Krivine, Lambda-Calcul, types et modèles, Masson 1991.
  • Ceux qui veulent surtout jouer avec les fonctions liront l’ouvrage ludique de Raymond Smullyan [13], To Mock a Mockingbird, ISBN 0192801422.
Post-scriptum :

Ce qu’on vient d’expliquer s’appelle le λ-calcul, mais nous n’avons pas parlé de λ, une notation pour $\mapsto$.

Article édité par Étienne Ghys

Notes

[1Bizarrement, cela suppose qu’on connait des mathématiques. En effet, ce que nous allons présenter sert de base aux mathématiques, mais c’est aussi une part d’un domaine des mathématiques, que l’on appelle la logique mathématique.

[2On admet qu’on connait cet objet ℕ, on verra plus tard qu’il est fait de fonctions particulières.

[3On note cela habituellement $f(a)$, mais il y a déjà assez de parenthèses comme ça !

[4dont l’opérateur est une espace « ».

[5Dans le formalisme que nous décrivons ici on ne peut pas démontrer que deux fonctions qui ont le même effet sont égales.

[6contrairement à la théorie des ensembles où ce sont les ensembles qui sont les citoyens de première classe.

[7De façon assez amusante les premières mises en œuvre de langages de programmation fondés sur ce formalisme sont, elles, tombées dans le piège. Le lecteur pourra s’entrainer avec la substitution :
\[ ((x \mapsto x)~(y \mapsto x)) [x ← y]\]
autrement dit on substitue $y$ à $x$ dans $ (x \mapsto x)~(y \mapsto x)$.

[8Cela rappelle la matière traitée dans l’article Est-ce que ça s’arrête ?

[9On entre alors dans le domaine de la théorie des types.

[10Suprenant pour une mathématicien, Russell a reçu le prix Nobel de littérature en 1950 ! Mais à dire vrai il n’a consacré qu’une petite partie de sa vie aux mathématiques.

[11La démonstration du théorème des quatre couleurs de Gonthier et Werner est une grande grande grande fonction. Voir également cet article.

[12☺ Ce style de programmation s’appelle sans originalité la programmation fonctionnelle.

[13Raymond Smullyan est un élève de Church.

Partager cet article

Pour citer cet article :

Pierre Lescanne — «Et si on commençait par les fonctions !» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • Et si on commençait par les fonctions !

    le 28 août 2009 à 18:35, par Marc Mezzarobba

    Je crois qu’il y a un petit problème dans la note 11 : le lien « Werner » renvoie sur une page à propos de Wendelin Werner, alors qu’ici c’est de Benjamin qu’il s’agit.

    Répondre à ce message
    • Et si on commençait par les fonctions !

      le 4 septembre 2009 à 15:16, par Pierre Lescanne

      Il s’agit en effet de Benjamin Werner le frère de Wendelin. Je vais corriger ce lien erroné. Merci de m’avoir signalé l’erreur.

      Pierre Lescanne

      Répondre à ce message
  • Et si on commençait par les fonctions !

    le 1er octobre 2009 à 05:42, par Marc JAMBON

    Cet article est plutôt décevant par rapport à son titre. « Et si l’on commençait par les fonctions ». J’attendais plutôt une introduction à la primitive récursivité qui a l’avantage d’être bien plus simple. Elle s’appuie sur 0 et la fonction successeur qui à x fait correspondre x + 1, ce que tout le monde peut comprendre dès l’école maternelle, on a ainsi une auto génération de N. Rien à voir avec le paragraphe « Définir les entiers naturels » : qu’est-ce que la partie réduite à l’ensemble vide sinon une élucubration de mathématiciens qui est de toute façon basée sur la théorie des ensembles, je croyais qu’on voulait « faire table rase du passé » !

    Répondre à ce message
    • Et si on commençait par les fonctions !

      le 6 octobre 2009 à 18:28, par Pierre Lescanne

      Souvent le but du titre d’un article de vulgarisation est de surprendre le lecteur et de lui présenter quelque chose qu’il n’attendait pas et qui l’interpelle. Je suis donc heureux de vous avoir piégé, car c’était l’un des objectifs de ce titre.

      Ceci dit, l’affirmation que la primitive récursivité est plus simple que le lambda calcul est une question de point de vue sur laquelle Stephen Kleene, le créateur de la récursivité que nous connaissons, a écrit un article fort intéressant :

      Origins of Recursive Function Theory in Annals of the History of Computing, Vol. 3 No. 1, janvier 1981.

      D’autre part, je vous laisse l’affirmation que von Neumann était un « élucubrateur », que je ne partage pas.

      Répondre à ce message
  • Et si on commençait par les fonctions !

    le 6 octobre 2009 à 15:05, par Marc JAMBON

    Point fixe
    Il s’agit du paragraphe.
    Un nouveau calcul.
    Des expressions qui ne se réduisent jamais.

    Les lignes 1 à 4 OK.

    Quant aux lignes 5 à 7 qui proposent un point fixe, là rien à faire, je ne parviens pas à trouver la formule demandée. J’aimerais bien avoir les réductions intermédiaires qui permettent d’y parvenir.

    Répondre à ce message
  • Et si on commençait par les fonctions !

    le 6 octobre 2009 à 18:15, par Pierre Lescanne

    Je vous prie de m’excuser, j’ai fait une erreur stupide et classique, en fait Y g et g (Y g) se réduisent vers le même terme à savoir g(x ↦ g (x x))(x ↦ g (x x)), ce qui fait qu’on peut les considérer comme égaux.

    Alan Turing a proposé un autre Y un peu plus compliqué qui a la propriété que Y g se réduit vers g (Y g).

    Répondre à ce message
  • le web et les combinateurs de point-fixe.

    le 6 novembre à 00:05, par Bailly

    quand on interroge un moteur de recherche « lambda-calcul Y-combinator » les réponses sont pauvres ; en particulier les chapitres sur l’implémentation d’un Y-C dans des langages courants (python, JS, java) bifurquent souvent vers des sortes de « fix » auto-invocants tels que
    fix=(lambda f : (lambda x : ((f)( fix(f)))(x) )).
    Pouvez-vous m’indiquer une meilleure piste ?

    Répondre à ce message
    • le web et les combinateurs de point-fixe.

      le 6 novembre à 16:08, par Pierre Lescanne

      Tout d’abord vous trouverez une présentation du combinateur de point-fixe en français dans le livre de Jean-Louis Krivine « Lambda-calcul, types et modèles ». Une traduction en anglais existe en ligne. En particulier, il y a un lien sur la page de Jean-Louis Krivine.

      je crois comprendre que vous voulez aussi une implantation. Les langages que vous citez sont typés. Or le combinateur de point-fixe ne peut pas être typé, donc si on veut le coder, il faut ruser.

      Ce que je peux suggérer, c’est d’implanter le lambda-calcul. Une petite variante peut être implantée simplement. Puis dans cette implantation, vous pouvez coder le combinateur Y.

      Ai-je répondu à votre attente ?

      Répondre à ce message
      • le web et les (faux) combinateurs de point-fixe.

        le 8 novembre à 18:51, par Bailly

        Oui et non, merci Pierre,
        oui, j’ai deja le livre de Krivine.
        non, j’ai mal posé ma question.
        ce que je cherche ; j’écris des petits algorithmes Python de datasc. et une lubie m’a pris un

        jour : "j’en ai assez de la corvée des boucles for ou while, je n’ai qu’à coder avec un

        combinateur de point fixe comme Church". y’aka...
        Il s’agissait juste d’écrire une function python qui prendrait un F et trouverait son point-

        fixe grâce au comninateur de Turing, donc je suis allé à la pêche sur le web.
        Dans un premier temps je retombais toujours sur des sites USA qui affirmaient :
        "voici une transposition python du Y-combinateur qu’on nommera fix :
        fix= lambda f : (lambda x : f( fix(f))(x) )
        et puis Fact =lambda f : (lambda n : 1 if n <2 else n*f(n-1) ), exemple n=5...."
        Il y a erreur du vocabulaire "combinator" car fix est auto-invocant, et ensuite on déborde la

        pile des appels dès qu’on calcule factorielle de 2000. => fix est éliminé.
        Depuis quelques mois les réponses sont plus astucieuses, par exemple sur

        rosettacode.org/wiki/Y_combinator#Python :
        "Y = lambda f : (lambda x : x(x))(lambda y : f(lambda *args : y(y)(*args)))
        fac = lambda f : lambda n : (1 if n<2 else n*f(n-1))"
        Là on ne voit pas d’auto-invocation explicite dans ce Y_rosettacode, mais quoi qu’il en soit

        il ne échoue au test de factorielle de 2000 ; bien sûr en débugant on s’aperçoit qu’il invoque

        récursivement Y, fac, Y, fac...etc, donc la pile d’appels coince très vite. => Y_rosetta est

        éliminé.

        Ce qui me conduit à préciser les contraintes positives ou négatives de ma question.

        • il faut travailler en langage grand public tel que python ou javascript.
        • acceptation des langages typés, je n’ai pas le choix avec les usuels.
        • refus d’utiliser une bibliothèque qui installerait un surlangage lambda-calcul au-dessus de

        python ou simplement le transformerait au point d’introduire la lazy evaluation.

        • élimination immédiate des artefacts qui plantent la pile pour factorielle de 2000.
        • fabrication des fonctions-point-fixe grâce à quelque chose, un je-ne-sais-quoi qui ne serait

        pas un vrai Y-combinateur mais qui lui ressemblerait le plus possible comme dans le duck-

        typing ( je lui fournis un argument qui décrit la récursion souhaitée, il retourne une

        fonctin-point -fixe de cette récursion, ensuite j’utiliserai cette fonction avec divers

        arguments particuliers).

        Et donc je disais que pour l’instant je n’ai pas trouvé cela sur le web, mais que certains

        spécialistes ont sans doute deja creusé ce domaine, c’est la raison pour laquelle je lançai

        cet appel sur images.maths.cnrs. Mais il se pourrait que mes contraintes sont trop nombreuses

        et que ma lubie est absurde. Encore merci pour votre attention.

        Répondre à ce message
        • le web et les (faux) combinateurs de point-fixe.

          le 16 novembre à 17:50, par Pierre Lescanne

          Je reviens à vous. Vous dites « j’en ai assez de la corvée des boucles for ou while ». Or vous programmez en Python, pourquoi n’utilisez vous pas la récursivité qu’offre ce langage ? Cela est la bonne pratique et vous éviterait de passer par les combinateurs de point-fixe, qui sont inutiles si votre objectif est seulement la récursivité.

          Répondre à ce message
          • le web et les (faux) combinateurs de point-fixe.

            le 18 novembre à 18:36

            merci, PL ; il se pourrait que les 4 contraintes de mon « cahier des charges » soient trop sévères.
            les récursions de Python sont limitées ; -la vraie récursion avec appels imbriqués plante dès que la pile des appels est dépassée et c’est bien normal dans un ordinateur matériel. -les autres récursion, telles que functools.reduce sont parfaites pour les cas où on connaît à l’avance la liste des points à traiter, donc l’équivalent d’une boucle for ; mais pour l’équivalent d’une while, par exemple calculer Pi avec une précision de 10**-20 avec la suite de Leibniz, exemple très lent, on ne connaît pas à l’avance à quel « n » correspond cet « epsilon » de 10**-20 et on ne peut pas fournir à une function de récursion ce « n » ni la suite des nombres entiers de 0 à n, seul le while possède un test d’arrêt des rebouclages. .... enfin, d’après mes explorations de python. L’idée de Church est séduisante car on fournit à un Y-C une fonction qui exprime bien la récurrence souhaitée et le Y-C fait le travail tout seul. Je suis arrivé à la conclusion qu’un vrai Y-C n’est pas praticable, et j’examine une autre piste de simulation : 1) écrire un simulateur de Y-C (même comportement vu de l’extérieur) et surtout abondonner l’exigence de lui fournir un seul argument, mais deux ou trois arguments qui expriment la récurrence souhaitée. En attendant évidemment je survis avec des boucles while !

            Répondre à ce message
            • le web et les (faux) combinateurs de point-fixe.

              le 19 novembre à 12:24, par Pierre Lescanne

              Vous écrivez « on ne connaît pas à l’avance à quel « n » correspond cet « epsilon » de 10**-20 et on ne peut pas fournir à une function de récursion ce « n » ni la suite des nombres entiers de 0 à n, seul le while possède un test d’arrêt des rebouclages. ». J’aurais envie de penser que vous ne maîtrisez pas les arcanes de la récursivité. Voici en Python une fonction qui calcule la racine carrée avec la précision que vous souhaitez (ici 100 000 chiffres, donnée par la constante epsilon). Non seulement la pile ne déborde, mais la réponse est immédiate.

              epsilon = 10 ** (-100000)
              semence = 2

              def racineCarreRecursion(x,n,y) :
                 if (y**2 - x) < epsilon :
                     return y
                 else:
                     return racineCarreRecursion(x,n+1,(x/y + y)/2.0)

              def racineCarre(x) :
                 return racineCarreRecursion(x,0,semence)
              Répondre à ce message
              • le web et les (faux) combinateurs de point-fixe.

                le 19 novembre à 14:29, par Pierre Lescanne

                Juste une petite remarque complémentaire. Le « n » que j’ai mis visait à répondre à votre « n », mais bien sûr il ne joue aucun rôle et que l’on doit programmer ainsi :

                def racineCarreRecursion(x,y) :
                   if (y**2 - x) < epsilon :
                       return y
                   else:
                       return racineCarreRecursion(x,(x/y + y)/2.0)

                def racineCarre(x) :
                   return racineCarreRecursion(x,semence)
                Répondre à ce message
                • Elimination des fonctions auto-invocantes..

                  le 19 novembre à 17:00

                  Il y a un hic . Vous proposez, avec une fonction
                  « racineCarreRecursion » auto-invocante :
                  epsilon = 10 ** (-100000)
                  semence = 2
                  def racineCarreRecursion(x,y) :
                  if (y**2 - x) < epsilon :
                  return y
                  else :
                  return racineCarreRecursion(x,(x/y + y)/2.0)
                  def racineCarre(x) :
                  return racineCarreRecursion(x,semence)

                  Quand on l’expérimente par exemple pour racine de 1000 et
                  avec ce très petit epsilon : :
                  raci = racineCarre(1000)
                  print("raci=",raci)

                  la réponse est immédiate et sans débordement de pile
                  >>>
                  raci= 2, ce qui est faux.

                  Explication, il y avait une erreur d’étourderie dans le
                  test d’arrêt du bouclage. Mutatis mutandis le programme corrigé est
                  epsilon = 10 ** (-100000)
                  semence = 2
                  def racineCarreRecursion(x,y) :
                  if abs(y**2 - x) < epsilon :
                  return y
                  else :
                  return racineCarreRecursion(x,(x/y + y)/2.0)
                  def racineCarre(x) :
                  return racineCarreRecursion(x,semence)

                  raci = racineCarre(1000)
                  print(« raci= »,raci)

                  résultat :
                  RuntimeError : maximum recursion depth exceeded in comparison

                  C’est naturel avec une fonction auto-invocante ; d’ailleurs même avec un
                  epsilon moins sévère on déborde vite: :
                  epsilon = 10 ** (-333)
                  A l’opposé pour
                  epsilon = 10 ** (-300) qui donnera
                  raci= 31.622776601683793

                  la réponse est bonne et très rapide car cet algorithme de
                  racine converge très vite, en une dizaine de tours pour cet epsilon.

                  Je maintiens bien que la récursion avec une fonction auto-invocante est
                  à rejeter si on ne sait pas à l’avance combien de tours notre algorithme
                  exigera, cette arcane de récursivité était facile à expérimenter et tous les contributeurs de sites comme stackoverflow ou rosettacode ou medium présentent ce défaut.

                  Mais ce n’était pas ma question d’origine : trouver sur le web une
                  implémentation « correcte » d’un combinateur de point fixe en python. Il
                  faut se rendre à l’évidence, on n’en trouve pas à cette date.
                  Par conséquent j’allège mes exigences de « correction » ; écrire un simulateur de
                  Y-C (même comportement vu de l’extérieur) et surtout abondonner l’exigence de
                  lui fournir un seul argument, mais accepter deux ou trois arguments qui
                  expriment la récurrence souhaitée, ces arguments étant de préférence des
                  « functions » lambdas. Dès que ce sera au point je publierai.

                  Répondre à ce message
                  • Élimination des fonctions « auto-invocantes »

                    le 21 novembre à 17:30, par Pierre Lescanne

                    Je pense que la page de discussion de cet article n’est pas le lieu pour un tel échange que je vous propose, si vous le souhaitez, continuer sur un autre médium (par exemple le courriel). Je voudrais pour les autres lecteurs rappeler les points suivants.

                    1. Mon programme ne comporte pas d’étourderie.

                    2. Il ne faut pas mélanger les concepts. Le fait que abs(y**2 - x) < epsilon soit une mauvaise condition d’arrêt d’une approximation relève de l’arithmétique des ordinateurs et n’a rien à voir avec la récursivité et l’itération, comme cela est montré par le comportement des deux programmes itératifs suivants. Je précise que je n’ai pas l’intention d’aborder le problème de l’arrêt des itérations et des meilleurs moyens d’approximer une quantité réelle. Il y a des ouvrages spécialisés sur le sujet et mon domaine d’expertise est le lambda-calcul et la récursivité.

                    def rac2While(x) :
                       y = semence
                       while (y**2 - x) >= epsilon:
                           y = (x/y + y)/2.0
                       return y

                    et

                    def rac2WhileAbs(x) :
                       y = semence
                       while abs(y**2 - x) >= epsilon:
                           y = (x/y + y)/2.0
                       return y

                    Le calcul de rac2While(2) converge et la calcul de rac2WhileAbs(2) diverge.

                    3. Je ne connais pas le concept de « fonction auto-invocante ». Peut-être voulez-vous parler de fonction récursive ? J’affirme clairement et sans ambage, qu’avec les fonctions récursives on peut programmer un algorithme pour lequel on ne connaît pas à l’avance le nombre d’appels récursifs imbriqués qui seront nécessaires. C’est ce qui distingue les fonctions récursives (générales) des fonctions récursives primitives. Python implante les fonctions récursives (générales). Ce sont ces fonctions récursives que j’utilise régulièrement quand je programme dans des langages de programmation où la seule structure de contrôle est la récursivité.

                    4. Quant à l’implantation d’un combinateur de point fixe en python, je pense y avoir suffisamment répondu. Vous y arriverez très probablement (car python est Turing-complet). Vous pourrez même le faire sans aucune boucle « while », en utilisant uniquement la récursivité ! Mais je doute que cela soit élégant et naturel. Je ne suis donc pas étonné que vous n’ayez pas trouvé de références pertinentes sur le web.

                    Bien cordialement, et à bientôt sur un autre médium, si vous le souhaitez.

                    Pierre Lescanne

                    Répondre à ce message
  • Et si on commençait par les fonctions !

    le 11 novembre à 15:05, par Pierre Lescanne

    Vous abordez des questions techniques qui dépassent mes compétences. Cependant, il n’y a pas de doutes que des chercheurs ont déjà réfléchi à ces problèmes (il me semble avoir déjà entendu des conférences sur le sujet). Il faudrait donc poser la question sur des forums spécialisés, pour entrer en contact avec ces chercheurs : stackoverflow peut être l’un d’eux.

    P. S. Je ne souscris pas entièrement à la phrase « il faut travailler en langage grand public tel que python ou javascript. ».

    Répondre à ce message

Laisser un commentaire

Qui êtes-vous ?
Votre message

Pour créer des paragraphes, laissez simplement des lignes vides.

Ajouter un document

Suivre IDM