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à.