Suite de ma petite histoire concernant les tests d'églalité entre deux algorithmes, j'ai reprogrammé mon interprêteur de lambda-calcul (vu que j'ai paumé l'autre dans un disque dur qui a cramé... ).
Le fait de l'avoir reprogrammé a été plutôt une bonne chose, dans la mesure où le code est plus robuste et m'a permis de faire des choses un peu plus intéressantes.
Le parseur est capable de reconnaître n'importe quel lambda terme de cette forme : U = x | lambda x°U | (U)U, autrement dit, le parseur est capable de reconnaître n'importe quel lambda-terme "pur".
Afin de simplifier l'écriture des expressions, j'ai réalisé deux "petites" choses : les définitions de terme et les définitions de fonctions.
Une définition de terme s'écrit de la manière suivante : def name°U, avec name, le nom du terme et U le terme associé à la variable.
Par exemple : def vrai ° lambda f°lambda x°f correspond à la définition du terme vrai. On pourra dire que vrai fait alors partie du vocabulaire du langage, puisqu'il s'agit d'un terme défini.
A chaque fois que le parseur rencontrera le mot vrai, il le remplacera par son équivalent en lambda-calcul : lambda f°lambda x°f.
Une définition de fonction est un peu plus complexe que la définition d'un terme.
Je voulais être capable d'écrire une fonction sous n'importe quelle forme.
Par exemple, on écrit souvent un couple en lambda-calcul sous cette forme : (x,y), qui en réalité correspond à ceci : lambda z°((z)x)y.
On écrit souvent, en informatique, les fonctions de cette façon : name(x,y).
Et enfin, pour les opérations mathématiques, on écrit souvent des choses de cette façon : x+y, x*y, x=y...
Il me fallait donc trouver une solution qui prenne en compte toutes les formes d'écritures possibles.
Une fonction se définit donc comme suit : app signature°U, avec signature une "phrase" ponctuée de points d'interrogations (j'avoue m'être inspiré de la façon dont ADO.NET gère les paramètres passés aux requêtes SQL ).
Il devient donc possible d'écrire des choses de ce genre là :
Ca marche plutôt bien, comme vous pouvez le voir ici : Factorielle(4) - (605 ko) FactoriellePlusRapide(4) - (65 ko).
- app (?,?)°lambda a°lambda b°lambda z°((z)a)b, ceci permet ensuite d'utiliser l'expression (x,y) au lieu de lambda z°((z)x)y.
- app if ? then ? else ?°lambda b°lambda u°lambda v°((b)u)v, ceci permet d'utiliser if bool_expr then expr1 else expr2 au lieu de ((bool_expr)expr1)expr2.
- app ?+?°lambda x°lambda y°((x)succ)y, avec succ l'expression successeur en lambda-calcul, ceci permet d'utiliser l'opérateur d'addition plus simplement : a+b à la place de lambda f°lambda x°((a)f)((b)f)x.
- etc...
Cependant, si le moteur régissant les calculs semble fonctionner de façon très correcte, j'ai un petit ennui concernant le parseur.
En effet, en définissant : ?+?, ?*? et ?=?, on ne peut pas écrire de choses de ce genre là : (1+1)*(1+1)=4. Ce qui est plutôt gênant...
Cela vient du fait qu'avec les définitions d'applications, on peut se retrouver avec des symboles qui ne font pas partie, nativement, du lambda-calcul pur.
Explication :
Le parseur prend en paramètre un string, et fait une série de vérifications dessus.En effet, quand on envoie le string (1+1)*(1+1) au parseur, le parseur détecte (U)V, avec U = 1+1 et V = *(1+1). Ce qui est évidemment faux, puisqu'il devrait détecter : ?*?.
- Il vérifie d'abord si le string est uniquement composé d'une suite ininterrompue de chiffres et de lettres.
- Si c'est le cas, il vérifie si cette suite appartient aux définitions (def name°U) de l'environnement.
- Si c'est le cas, il renvoie le lambda-terme correspondant à la définition
- Sinon, il renvoie le string encapsulé dans un lambda-terme de type variable.
- Sinon, il vérifie si le string est de la forme : lambda x°U.
- Si c'est le cas, il renvoie un lambda-terme de type abstraction.
- Sinon, il vérifie si le string est composé d'une successions de termes parenthésés.
- Et c'est là que ça coince.
Mon parseur est donc pour le moment, relativement incorrect, dans la mesure où la gestion des parentèses est assez "foirée".
Si vous avez des idées, ou si vous êtes intéressés... Ou si vous voulez voir le code source du parseur (ça serait sûrement utile pour avoir plus d'idées :p), ça m'aiderait bien en fait.
Partager