154 lines
5 KiB
Markdown
154 lines
5 KiB
Markdown
|
Programmation fonctionnelle — Théophile Bastian
|
||
|
===============================================
|
||
|
|
||
|
Ce projet implémente les deux fonctionnalités de cœur demandées dans le sujet,
|
||
|
à savoir
|
||
|
|
||
|
* compiler avec succès le langage de base (transformation CPS +
|
||
|
défonctionalisation) ;
|
||
|
* ajouter une primitive ifzero.
|
||
|
|
||
|
Quelques fonctionnalités supplémentaires ont été implémentées, et sont
|
||
|
détaillées plus bas.
|
||
|
|
||
|
Le dépôt Git du projet se situe ici :
|
||
|
|
||
|
>> https://git.tobast.fr/tobast/mpri-funcprog-project/ <<
|
||
|
|
||
|
**ATTENTION !** `src/tests/` est un git-submodule, il est donc nécessaire de
|
||
|
cloner avec le flag `--recursive`, ou de lancer ensuite un
|
||
|
|
||
|
git submodule update --init
|
||
|
|
||
|
afin de pouvoir récupérer le dépôt entier !
|
||
|
|
||
|
|
||
|
Flags disponibles pour `joujou`
|
||
|
-------------------------------
|
||
|
|
||
|
En plus de `--debug`, quelques flags ont été ajoutés :
|
||
|
|
||
|
* `--light-debug` : affiche uniquement les langages intermédiaires
|
||
|
pretty-printés pour la lisibilité et non l'exhaustivité. Voir plus bas.
|
||
|
* `--no-var-var-bind` : désactive la passe de suppression des liaisons
|
||
|
variable-variable. Voir plus bas.
|
||
|
* `--no-const-propagation` : désactive la passe de propagation naïve des
|
||
|
constantes. Voir plus bas.
|
||
|
|
||
|
|
||
|
Fichiers de tests
|
||
|
-----------------
|
||
|
|
||
|
Tous les tests fournis, ainsi que ceux ajoutés, donnent le bon résultat
|
||
|
(incluant `loop`, sur lequel `gcc` fonctionne). La plupart des tests sont de
|
||
|
moi, mais certains sont de Glen Mével, partagés via le dépôt
|
||
|
https://github.com/tobast/mpri18-funcprog-tests
|
||
|
|
||
|
* `if_fib.lambda` (par Glen) : fibonacci avec ifzero
|
||
|
* `if_func.lambda` : tester ifzero en se basant sur `church.lambda`
|
||
|
* `if_func_branch.lambda` : tester la branche prise par ifzero
|
||
|
* `if_nested.lambda` (par Glen) : constructions ifzero imbriquées
|
||
|
* `multi_args.lambda` : fonction à deux arguments
|
||
|
* `multi_args_rec.lambda` : fonction récursive à plusieurs arguments
|
||
|
* `over_application.lambda` : fonction sur-appliquée (`id id x`)
|
||
|
* `partial_eval.lambda` : évaluation partielle de fonction
|
||
|
* `rec_factorial.lambda` : récursion simple (factorielle)
|
||
|
* `rec_fibo.lambda` : récursion plus compliquée (fibonacci)
|
||
|
* `redef.lambda` : redéfinition d'une variable avec le même nom
|
||
|
* `ren.lambda` (par Glen) : transitivité de l'effacement des var-var
|
||
|
* `simple_call.lambda` : appel de fonction simple
|
||
|
* `simple_if.lambda` : construction ifzero simple
|
||
|
|
||
|
|
||
|
Transformation CPS
|
||
|
------------------
|
||
|
|
||
|
La transformation CPS suit essentiellement les lignes directrices du projet.
|
||
|
Une attention particulière a été portée à essayer de générer le **moins de
|
||
|
continuations inutiles possible**.
|
||
|
|
||
|
Par exemple, naïvement, le code `id y` serait traduit en quelque chose comme
|
||
|
|
||
|
cps_transf y (λx ·
|
||
|
cps_transf id (λf ·
|
||
|
f x k))
|
||
|
|
||
|
ce qui donnerait
|
||
|
|
||
|
let xCont x =
|
||
|
let fCont f =
|
||
|
Call f x k
|
||
|
in
|
||
|
Call fCont id
|
||
|
in
|
||
|
Call xCont y
|
||
|
|
||
|
Le code généré par ce projet serait plutôt de la forme
|
||
|
|
||
|
let f = id in
|
||
|
let x = y in
|
||
|
Call f x cont
|
||
|
|
||
|
ce qui est optimisé avant le passage au C en un simple
|
||
|
|
||
|
Call id y cont
|
||
|
|
||
|
|
||
|
Défonctionalisation
|
||
|
-------------------
|
||
|
|
||
|
Rien de particulier à signaler sur cette partie, suit les lignes directrices du
|
||
|
projet.
|
||
|
|
||
|
|
||
|
Élimination des associations variable = variable
|
||
|
------------------------------------------------
|
||
|
|
||
|
Comme suggéré, une passe de compilation après `Defun`, implémentée dans le
|
||
|
module `VarVarBind`, se charge de supprimer toutes les instructions du type
|
||
|
|
||
|
let x = y in (* … *)
|
||
|
|
||
|
en remplaçant simplement `y` par `x` dans la suite, lorsque x et y sont des
|
||
|
variables. Il suffit pour cela d'un parcours du code, utilisant un
|
||
|
environnement mappant certaines variables sur certaines autres. On prend soin
|
||
|
de respecter la transitivité, c'est-à-dire de traduire correctement
|
||
|
|
||
|
let y = x in
|
||
|
let z = y in (* … *)
|
||
|
|
||
|
|
||
|
Propagation naïve des constantes
|
||
|
--------------------------------
|
||
|
|
||
|
Pour nettoyer un peu plus le code produit, le module `ConstantPropag` effectue
|
||
|
après le passage de `VarVarBind` une sorte de propagation naïve des constantes,
|
||
|
c'est-à-dire qu'on propage les constantes et simplifie les expressions autant
|
||
|
que possible, sans toutefois jamais propager au-delà d'un appel de fonction.
|
||
|
|
||
|
La propagation au-delà d'un appel de fonction (non implémentée, donc), plus
|
||
|
compliquée à implémenter, aurait toutefois pu supprimer des continuations
|
||
|
inutiles du type de celles mentionnées pour CPS plus haut.
|
||
|
|
||
|
|
||
|
Pretty-printing
|
||
|
---------------
|
||
|
|
||
|
Pour m'aider à y voir clair tout au long du projet, j'ai implémenté des pretty
|
||
|
printers n'affichant rien de superflu pour `Tail` et `Top`. Par exemple, sur
|
||
|
le test `simple_call.lambda`, la sortie pour `Tail` est
|
||
|
|
||
|
let bl_exit1_ = λ((v_7_)) ·
|
||
|
Exit in
|
||
|
let id = λ((x) (bl_6_)) ·
|
||
|
Call bl_6_ (x) in
|
||
|
let bl_3_ = λ((v_2_)) ·
|
||
|
Print v_2_;
|
||
|
Call bl_exit1_ (v_2_) in
|
||
|
let v_4_ = 42 in
|
||
|
let v_5_ = id in
|
||
|
Call v_5_ (v_4_) (bl_3_)
|
||
|
|
||
|
On peut obtenir la sortie des pretty-printers avec `--debug`, ou avec
|
||
|
`--light-debug` pour n'avoir que ces sorties là.
|