28 août 2009

17 messages - Retourner à l'article

Voir tous les messages - Retourner à l'article

  • 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
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.