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

5.0 KiB Raw Permalink Blame History