28 août 2009

18 messages - Retourner à l'article

Et si on commençait par les fonctions !

Échos de la recherche
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.
Piste rouge
Le 28 août 2009, par Pierre Lescanne - 18 commentaires

  • 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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 2018 à 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

  • Et si on commençait par les fonctions !

    le 28 mars 2019 à 04:16, par Andrés Navas

    Merci pour cet article. J’ai une question très simple : c’était vraiment von Newman le premier à avoir pensé les nombres naturels de la manière décrite ? Quelle est donc la différence avec la vision dans l’arithmétique de Peano ?

    Répondre à ce message

    • Et si on commençait par les fonctions ! Les entiers naturels vus par von Neumann

      le 15 janvier 2021 à 10:42, par Pierre Lescanne

      Merci de de votre intérêt et de vos questions. Tout d’abord ,excusez-moi de répondre si tard. Cet article était sorti de mon champ de vision.

      En effet, c’est von Neumann qui a introduit cette approche ensembliste des entiers naturels.

      John von Neumann, « An Axiomatization of Set Theory », dans Jean van Heijenoort, From Frege to Gödel : A Source Book in Mathematical Logic, 1879-1931, Cambridge, Massachusetts, Harvard University Press, 1967 (texte de 1925 traduit en anglais et réimprimé).

      son original en allemand : Eine Axiomatisierung der Mengenlehre. In : Journal für die reine und angewandte Mathematik, Band 154, 1925, S. 219–240.

      Ce qui différencie l’approche de Peano de celle de von Neumann est que l’approche de Peano est axiomatique (il pose les principe des entiers naturels). Von Neumann de son côté propose un modèle des entiers naturels à l’intérieur des ensembles, en montrant que l’on peut représenter les entiers naturels par des ensembles spécifiques. D’une part, il déduit la théorie des entiers naturels à partir de celle des ensembles, d’autre part, il montre que si la théorie des ensembles est cohérente, celle des entiers naturels l’est aussi.

      Church fait la même chose avec le lambda-calcul comme théorie sous-jacente à la place de la théorie des ensembles et il s’en sert pour jeter les bases de la théorie de la calculabilité.

      Bien cordialement,

      Pierre Lescanne

      Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.

Actualités des maths