Interprétation

L’objectif de ce TP est de mettre en œuvre un interprète pour un petit langage fonctionnel.

Déclaration des types des expressions

Le type de données pour les expressions de notre petit langage est directement inspiré du type de données utilisé par GHC (vous pouvez aller voir la structure de données Expr du module CoreSyn de l’API de GHC).

Nous poserons les déclarations de types suivantes :

type Nom = String

data Expression = Lam Nom Expression
                | App Expression Expression
                | Var Nom
                | Lit Litteral
                deriving (Show,Eq)

data Litteral = Entier Integer
              | Bool   Bool
              deriving (Show,Eq)

Une Expression peut être :

Prenons quelques exemples de représentation pour clarifier ces types. Voici une liste d’expressions (écrites en utilisant la syntaxe de Haskell) et leur représentation (de type Expression) :

Expression Représentation
a Var "a"
\x -> x Lam "x" (Var "x")
True Lit (Bool True)
not True App (Var "not") (Lit (Bool True))
add Var "add"
add 12 App (Var "add") (Lit (Entier 12))
add 12 34 App (App (Var "add") (Lit (Entier 12))) (Lit (Entier 34))

Comme il est rapidement fastidieux d’écrire des expressions en utilisant cette représentation, nous allons commencer notre travail par un petit analyseur syntaxique.

Analyse syntaxique d’expressions

Pour écrire un analyseur syntaxique pour les petites expressions, nous utiliserons les constructions vues en cours, avec de légères modifications.

Module Parser

Vous utiliserez le module Parser donné dans le dépôt git du cours, en plaçant le fichier Parser.hs (et non le fichier ParserCours.hs) dans le même répertoire que votre fichier Interprete.hs et en ajoutant

import Parser

au début de votre fichier. Quand vous chargerez votre fichier par :load Interprete.hs dans GHCi, il ira aussi charger le module Parser.

À la différence du code écrit pendant le cours, le type Parser de Parser.hs est une instance des classes de type Functor, Applicative, Alternative et Monad. Vous retrouverez la documentation de ces différentes classes de type dans les modules Data.Functor, Control.Applicative et Control.Monad. Bien entendu, les classes de type étant très génériques, leur documentation est abstraite. La documentation du module Parser dans le mini-haddock décrit donc ce que signifient toutes les fonctions dans le cas précis des parseurs.

Au passage, notez que le fait que Parser soit une instance des classes de type Monad permet d’utiliser la notation do illustrée en cours pour la monade IO.

Quelques exemples illustreront mieux les différences. L’analyseur syntaxique qui retrouve une chaîne de caractères précise peut ainsi s’écrire :

chaine :: String -> Parser String
chaine ""     = pure ""
chaine (c:cs) = car c      >>= \_ ->
                chaine cs  >>= \_ ->
                pure (c:cs)

mais il peut aussi être écrit, de façon un peu plus concise en utilisant le combinateur (>>) (défini automatiquement pour toutes les instances de Monad) qui met en séquence deux parseurs quand le résultat du premier n’est pas intéressant :

chaine :: String -> Parser String
chaine ""     = pure ""
chaine (c:cs) = car c      >>
                chaine cs  >>
                pure (c:cs)

ou alors en utilisant do :

chaine :: String -> Parser String
chaine ""     = pure ""
chaine (c:cs) = do car c
                   chaine cs
                   pure (c:cs)

De même, some (qui est défini automatiquement pour les instances d’Alternative) peut se recoder ainsi :

some :: Parser a -> Parser [a]
some p = p      >>= \r ->
         many p >>= \rs ->
         pure (r:rs)

soit, avec do :

some :: Parser a -> Parser [a]
some p = do r  <- p
            rs <- many p
            pure (r:rs)

Dans la suite vous pourrez donc utiliser la syntaxe que vous préférez. Cependant, prenez garde à l’indentation de votre code quand vous utilisez do : dans la fonction some ci-dessus, il est primordial que r, rs et pure soient alignés. Utilisez donc des espaces pour indenter votre code pour éviter les mauvaises surprises avec les tabulations.

Autre point : le module Parser fourni a un entête :

module Parser ( Parser
              , Resultat
              , runParser
              , resultat
              , unCaractereQuelconque
              , carQuand
              , car
              , chaine
              -- réexporte les fonctions utiles de Control.Applicative
              , (<|>), empty, many, some )
where

qui précise explicitement ce qui est exporté par le module. Notez que cette liste ne mentionne pas MkParser : le type des parseurs est abstrait à l’extérieur du module, la seule façon de construire des parseurs sera donc d’utiliser les briques de base et les combinateurs (pure, (>>=), etc. sont déjà exportés par le Prelude, ils n’ont pas été réexportés explicitement).

Analyse proprement dite

Nous voulons autoriser des espaces à plusieurs endroits des expressions.

  1. Définissez un analyseur syntaxique espacesP :: Parser () qui consomme tous les espaces au début de la chaîne à analyser, et retourne toujours () pour ignorer ces espaces.

    Par exemple :

Commençons par analyser les expressions les plus simples possibles : les variables. Pour simplifier, nous considérerons que les noms de variables sont juste des suites de lettres minuscules (sans accent).

  1. Définissez un analyseur syntaxique nomP :: Parser Nom qui analyse le premier nom apparaissant dans la chaîne.

    Pour traiter correctement les espaces dans la suite, ce parseur consommera aussi tous les espaces qui suivent le nom (il utilisera pour cela espacesP). Mais il échouera si la chaîne commence par des espaces (quand on combinera deux analyseurs, le premier se chargera de consommer les espaces du milieu).

    Par exemple :

  2. Définissez un analyseur syntaxique varP :: Parser Expression.

    Par exemple :

  3. Définissez une fonction applique :: [Expression] -> Expression telle que :
    • applique [] n’est pas définie,
    • applique [e] vale e,
    • applique [e1, e2] vale App e1 e2,
    • applique [e1, e2, e3] vale App (App e1 e2) e3,
    • etc.

    (Dans la famille des fonctions fold de Data.List vous trouverez une fonction qui fait tout le travail. La définition récursive n’est pas très longue non plus.)

  4. Définissez deux analyseurs syntaxiques exprP :: Parser Expression et exprsP :: Parser Expression tels que :
    • pour l’instant exprP soit équivalent à varP,
    • exprsP parse une suite de une ou plusieurs expressions (chacune parsées par exprP) et les combine en une expression par la fonction applique1.

    Par exemple :

  5. Définissez un analyseur syntaxique lambdaP :: Parser Expression qui reconnaisse une expression utilisant la syntaxe suivante inspirée d’Haskell : \ x -> ee sera parsé par exprsP.

    Par exemple :

    Notez en particulier que, pour qu’une chaîne écrite en Haskell contienne le caractère \, il faut écrire \\ dans le code, car \ sert d’échappement (pensez notamment à '\n', le caractère de fin de ligne) :

    Vous pourrez bien entendu étendre la syntaxe pour utiliser aussi une autre notation si vous voulez, par exemple pour parser aussi "λx → x" (« λ » est la lettre grecque « lambda » ; la notation \ pour définir les fonctions anonymes en Haskell a été choisie pour sa ressemblance avec λ).

  6. Étendez la définition de exprP pour que

  7. Définissez un analyseur syntaxique exprParentheseeP :: Parser Expression tel que :

    Étendez exprP pour que les expressions parenthésées soient acceptées comme des expressions. Ainsi, vous aurez :

  8. Définissez un analyseur syntaxique nombreP :: Parser Expression :

  9. Définissez un analyseur syntaxique booleenP :: Parser Expression :

    Ajoutez les nombres et les booléens à exprP.

  10. Peaufinez le tout en définissant un analyseur syntaxique expressionP :: Parser Expression correspondant à exprsP éventuellement précédé d’espaces.

Dans la suite, nous allons interpréter des expressions. Commençons donc par une simple fonction pour combiner tout le travail précédent.

  1. Définissez une fonction au nom court, disons ras (résultat de l’analyse syntaxique), pour faire toute l’analyse :

    Cette fonction échouera (par exemple par un error "Erreur d’analyse syntaxique") si l’analyse syntaxique échoue ou si elle n’a pas analysé la chaîne complète.

Interprétation

Remarque : Il est possible de traiter cette section sans avoir d’analyse syntaxique fonctionnelle, mais il faudra du coup saisir les Expressions directement, ce qui est rapidement fastidieux…

Pour éviter les ambiguïtés entre \ et \\ suivant que l’on parle d’une expression ou de sa représentation dans une chaîne de caractères dans le code Haskell, nous utiliserons dans la suite λ.

Interpréter une expression de notre mini-langage fonctionnel signifie appliquer chaque fonction à son argument tant qu’il y en a. Les différentes fonctions d’interprétation que nous allons mettre au point convertiront ainsi une expression en une valeur.

Expression Valeur
12 12
True True
(λx -> x) 12 12
(λx -> x) Une valeur correspondant à cette fonction
a Échec, si a n’est pas défini

Interprète simple

Nous avons tout d’abord besoin de définir ce que nous appellerons une valeur. Nous allons profiter du fait qu’Haskell est lui-même un langage fonctionnel pour donner un type simple aux valeurs fonctionnelles de notre langage : nous utiliserons directement des fonctions Haskell !

Nous aurons donc deux sortes de valeurs : des littéraux et des fonctions.

data ValeurA = VLitteralA Litteral
             | VFonctionA (ValeurA -> ValeurA)

(nous utilisons le suffixe A parce que nous allons mettre au point des variantes dans la suite).

Notez au passage que, en choisissant ce type pour les valeurs, nous avons choisi de donner une interprétation stricte à notre langage, c’est-à-dire en évaluation par valeur : l’argument que prend une fonction est une ValeurA (et non pas une expression non encore évaluée). Ce choix simplifie l’interprète.

Malheureusement, nous ne pouvons pas demander à Haskell de générer automatiquement du code pour afficher ces ValeurA.

  1. Essayez tout de même d’ajouter :

    Comprenez-vous le problème ?

Nous allons donc donner une instance de la classe Show à la main. Comme l’indique la documentation de la classe Show définie dans le Prelude (consultez cette documentation !), il suffit de définir show2 pour avoir une définition complète. Pour le type ValeurA, cette fonction aura donc le type ValeurA -> String.

instance Show ValeurA where
    show (VFonctionA _) = "λ"
                       -- ^ ou "VFonctionA _", ou "<fun>" ou toute
                       --   autre représentation des fonctions de
                       --   votre choix
    show (VLitteralA
  1. Complétez la définition de l’instance Show pour ValeurA.

    Vérifiez que vous pouvez afficher des ValeurA dans GHCi sans vous faire insulter :

Bien entendu, les réponses doivent correspondre au format que vous aurez choisi. Nous avons choisi de représenter dans les exemples de cet énoncé les littéraux simplement comme leur contenu pour avoir l’affichage le plus compact possible, le type levant toute ambiguïté.

Interpréter les littéraux, c’est-à-dire convertir les expressions Lit en valeurs, ne va donc poser aucun problème.

Interpréter les fonctions est plus difficile. Nous voulons associer à l’expression (λx -> x), c’est-à-dire Lam "x" (Var "x"), une VFonctionA f telle que f (VLitteralA (Bool True)) vaudra VLitteralA (Bool True). Pour arriver à cette fin, f doit déclencher l’interprète sur l’expression Var "x" en se « souvenant » que son paramètre x est associé à la valeur reçue en argument. Pour cela, nous utiliserons un environnement.

type Environnement a = [(Nom, a)]

Un environnement de type Environnement ValeurA est donc une liste d’associations de valeurs à des noms.

Interpréter une variable reviendra juste à aller chercher sa valeur dans l’environnement. (Vous irez piocher les fonctions standard dont vous aurez besoin, par exemple lookup ; pensez à regarder les modules Data.List, Data.Maybe, etc. et pas seulement les fonctions du Prelude).

Enfin, pour interpréter l’application App e e', il suffit d’interpréter e et e'. e doit naturellement s’interpréter comme une VFonctionA f : il suffit alors d’appliquer la fonction f à l’interprétation de e'.

  1. Définissez interpreteA :: Environnement ValeurA -> Expression -> ValeurA.

    Vérifiez que vous obtenez le résultat attendu sur un certain nombre d’expressions, notamment :

    Attention : (λx -> x x)(λx -> x x) est une fonction qui boucle. Comprenez-vous pourquoi ? Vous devrez donc interrompre son interprétation par Ctrl+C.

    Dans le cas où on essaie d’interpréter une variable qui n’apparaît pas dans l’environnement, l’interprète pourra échouer de la façon qui vous arrange.

Quelques primitives, pour un langage moins primitif

Outre le fait d’être très utile pour interpréter les fonctions, l’environnement peut contenir des primitives, des valeurs qui ne sont pas forcément exprimables dans le langage. En particulier, dans notre mini-langage, nous n’avons pas de façon de manipuler les littéraux. Mais ces manipulations peuvent s’exprimer en Haskell, bien entendu.

  1. Définissez une fonction negA :: ValeurA telle que :

    Cette fonction pourra bien entendu échouer comme ça vous arrange dans le cas où elle n’est pas appliquée à un entier, par exemple :

  2. Définissez une fonction addA :: ValeurA telle que :

On voit bien que l’on pourrait définir les quatre opérations arithmétiques de même, avec un code quasiment identique.

  1. Définissez une fonction releveBinOpEntierA :: (Integer -> Integer -> Integer) -> ValeurA qui prend en argument un opérateur binaire sur les entiers et en fait une ValeurA.

    En définissant alors

    vous aurez :

  2. Définissez ifthenelseA :: ValeurA telle que :

Boucle d’interaction

Une boucle d’interaction répète les étapes suivantes jusqu’à la fin de son entrée standard :

Vous pourrez utiliser les fonctions de System.IO, notamment isEOF, et toutes les autres fonctions standard qui vous sembleront utiles.

  1. Définissez main :: IO () pour implémenter une boucle d’interaction.

    Vous pourrez l’utiliser de la façon suivante :

Interprète avec erreurs

L’interprète simple précédent est sans pitié dans les cas d’erreurs, par exemple pour les expressions 1 2 (où 1 n’est pas une fonction et ne peut donc pas être appliquée à 2), ou quand il tombe sur une variable qui n’est pas définie, ou quand il trouve une addition appliquée à d’autres arguments que des entiers, etc.

Plutôt que des exceptions qui cassent l’interprétation, nous allons permettre à notre interprète de retourner une erreur.

Une solution serait de définir :

interpreteB :: Environnement ValeurB -> Expression -> Maybe ValeurB

Au lieu de se contenter d’un Maybe, nous allons utiliser le type Either un peu plus riche : comme vous pouvez le voir dans la documentation de Data.Either, ce type est défini ainsi :

data Either a b = Left a
                | Right b

Ce type est souvent utilisé comme un Maybe enrichi, de sorte à avoir une explication de l’erreur en cas d’échec. Right est alors utilisé pour le cas de réussite (right signifie à la fois droit et correct), Left le cas d’erreur.

Nous utiliserons donc les types suivants :

data ValeurB = VLitteralB Litteral
             | VFonctionB (ValeurB -> ErrValB)

type MsgErreur = String
type ErrValB   = Either MsgErreur ValeurB
  1. Définissez une instance de la classe Show pour votre type ValeurB.

Les causes possibles d’erreurs sont donc :

  1. Définissez interpreteB :: Environnement ValeurB -> Expression -> ErrValB.

    Par exemple :

Désormais les primitives peuvent aussi générer des erreurs.

  1. Définissez addB :: ValeurB qui retourne une erreur si un de ses deux arguments n’est pas un entier. Elle propagera aussi les erreurs éventuelles de ses arguments.

  2. Définissez quotB :: ValeurB qui, en plus de détecter toutes les erreurs que détecte addB, détecte aussi la division par zéro.

Interprète traçant

Repartons du code de l’interprète simple, pour lui ajouter la possibilité de tracer l’avancée du calcul. Pour cela, nous allons produire, comme résultat, non seulement la valeur proprement dite, mais également une chaîne de caractères.

data ValeurC = VLitteralC Litteral
             | VFonctionC (ValeurC -> OutValC)

type Trace   = String
type OutValC = (Trace, ValeurC)
  1. Définissez l’instance de Show pour ValeurC.

L’interprète aura désormais le type Environnement ValeurC -> Expression -> OutValC. Pour indiquer l’avancée du calcul, nous allons simplement ajouter un '.' à la trace à chaque fois que nous interprétons une application, de sorte que la trace d’une application sera la concaténation de :

  1. Définissez interpreteC :: Environnement ValeurC -> Expression -> OutValC tel que :

Notez que cet interprète interagit de façon subtile avec l’évaluation paresseuse. Si nous avions défini :

type OutValC = (ValeurC, Trace)

l’évaluation dans GHCi de (λx → x x)(λx → x x) n’aurait affiché qu’une parenthèse ouvrante avant de boucler.

Plus généralement, pour afficher la trace, GHCi cherche à obtenir chacun de ses caractères, ce qui veut dire que la façon dont vous la construisez change l’ordre d’évaluation…

Pour finir sur cet interprète, nous allons définir une primitive pingC qui correspondra simplement à la fonction identité mais affichant un 'p' dans la trace.

  1. Définissez pingC :: ValeurC.

Interprète monadique

Ces variations sur l’interprète amène à un triste constat : chaque variante a demandé de récrire une grande partie du code, même pour les cas qui ne sont pas concernés. Par exemple, bien qu’ils ne produisent pas de trace, le cas des littéraux est différent entre interpreteA et interpreteC parce qu’à chaque fois l’interprète est fortement lié au type de la valeur à retourner. Nous nous proposons ici de généraliser l’interprète pour qu’il soit plus adaptable.

Quel type donner à la fonction d’interprétation généralisée ? En partant des exemples précédents, nous pouvons constater qu’ils sont toujours de la forme suivante :

interpreteM :: Environnement ValeurM -> Expression -> ? ValeurM

avec comme type du résultat un type qui est construit sur le type des valeurs : c’était directement une valeur pour l’interprète le plus simple, un type un peu plus riche dans les deux autres cas. Nous voudrions donc quelque chose comme :

data ValeurM = VLitteralM Litteral
             | VFonctionM (ValeurM -> m ValeurM)

interpreteM :: Environnement ValeurM -> Expression -> m ValeurM

Haskell refuse cette définition de ValeurM : m n’est pas lié. Nous devons donc utiliser cette définition :

data ValeurM m = VLitteralM Litteral
               | VFonctionM (ValeurM m -> m (ValeurM m))
  1. Définissez l’instance de Show pour ValeurM m (puisque ValeurM attend un argument pour être un type, il faut lui en donner un pour définir une instance de Show)3.

Variante simple

Pour adapter l’interprète simple à cette définition, il faut définir un type SimpleM pour instancier le m de la définition.

Nous prendrons le type le plus simple pour notre objectif :

data SimpleM v = S v
               deriving Show
  1. Transformez votre interpreteA en un

    en ajoutant et enlevant le constructeur S aux endroits opportuns.

Tous les endroits où vous avez dû ajouter et enlever des S sont des points du code qui vont devoir changer quand vous allez remplacer SimpleM par un autre type pour les variantes de l’interprète. Les classes de types permettent justement de faire de la surcharge de fonctions qui sont instanciées selon les types.

{>> corriger à partir d’ici, après AMP <<}

Ces différents types vont être des monades. Les deux fonctions essentielles d’une monade sont :

Définissons la monade associée à SimpleM :

instance Monad SimpleM where
    return      = S
    (S v) >>= f = f v

Attention : en salle TP, vous utilisez GHC 7.6. Si vous écrivez votre code avec une version plus récente de GHC, consultez cette note4.

  1. Définissez interpreteM :: Monad m => Environnement (ValeurM m) -> Expression -> m (ValeurM m).

    interpreteM ressemblera beaucoup à interpreteSimpleM, où les ajouts de S sont des appels à return, et où les enlèvements de S correspondent à des enchaînements utilisant >>= ou la notation do (>>= et/ou do ne devraient être utiles que pour l’application).

Nous pouvons alors définir un interprète en instanciant la monade :

type InterpreteM m = Environnement (ValeurM m) -> Expression -> m (ValeurM m)

interpreteS :: InterpreteM SimpleM
interpreteS = interpreteM
  1. Testez votre interprète interpreteS pour vérifier qu’il se comporte comme interpreteSimpleM.

Variante traçante

Mettons maintenant à l’épreuve la malléabilité de cet interprète.

Définissons tout d’abord une variante traçante.

data TraceM v = T (Trace, v)
              deriving Show
  1. Définissez l’instance de Monad pour TraceM :
    • return ne génère qu’une trace vide,
    • T (t, v) >>= f doit déclencher f avec la valeur v (qui sera de type ValeurM dans nos applications) et créer une nouvelle valeur de type TraceM v en concaténant la trace t et celle produite par f.

En définissant :

interpreteMT :: InterpreteM TraceM
interpreteMT = interpreteM

pingM :: ValeurM TraceM
pingM = VFonctionM (\v -> T ("p", v))

nous avons directement :

ghci> interpreteMT [("ping", pingM)] (ras "ping 12")
T ("p",12)
ghci> interpreteMT [("ping", pingM)] (ras "ping 12")
T ("p",12)
ghci> interpreteMT [("ping", pingM)] (ras "ping ping")
T ("p",λ)
ghci> interpreteMT [("ping", pingM)] (ras "ping ping 12")
T ("pp",12)
ghci> interpreteMT [("ping", pingM)] (ras "(λx -> x ) ping 12")
T ("p",12)
ghci> interpreteMT [("ping", pingM)] (ras "(λx -> x x) ping 12")
T ("pp",12)

sans avoir modifié une seule ligne de l’interprète !

Bien entendu, si nous voulons tracer les applications, comme nous l’avions fait dans interpreteC, il faut modifier son code. Cependant, il suffira cette fois d’un petit ajout dans le seul cas qui change, l’application.

  1. Définissez interpreteMT' :: InterpreteM TraceM pour retrouver exactement les mêmes traces que interpreteC.

    Notez au passage que pingM n’a pas à être modifié !

Variante avec erreurs

Enfin, définissons une variante avec erreurs.

data ErreurM v = Succes v
               | Erreur String
               deriving Show

Les monades contiennent une fonction dont la définition est optionnelle mais bien utile dans notre cas : fail :: String -> m a. Par défaut elle lève une exception mais ici nous allons la redéfinir :

instance Monad ErreurM where
    fail e = Erreur e
  1. Complétez la définition de l’instance de Monad ErreurM.

  2. Définissez interpreteE :: InterpreteM ErreurM.

    En utilisant fail au lieu d’utiliser explicitement Erreur, vous pouvez même définir un interprète de type interpreteE :: Monad m => InterpreteM m, qui sera tout aussi valable dans les monades SimpleM et TraceM précédentes (mais où les erreurs lèveront des exceptions, bien entendu) !

    Vérifiez que vous obtenez les mêmes comportements qu’avec interpreteB.

Cerise sur le gâteau

Il est un peu fastidieux d’injecter les fonctions de Haskell telles que (+) en primitives du langage. D’autant que le travail s’avère être le même pour toutes les fonctions.

Pour éviter de se répéter à l’infini, nous pouvons utiliser les classes de types pour définir une fonction surchargée injecte qui transforme une valeur (une fonction, par exemple) Haskell en une ValeurM.

Nous allons pour cela utiliser des extensions du langage Haskell, que vous activerez par ces pragmas en début de votre fichier source :

{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}

Définissons la classe des valeurs Haskell injectables dans notre langage :

class Monad m => Injectable m t where
    injecte :: t -> ValeurM m

Pour chaque valeur de type t que nous voulons convertir en ValeurM, nous allons donc définir une instance de cette classe de types. Par exemple, pour les booléens, nous aurons :

instance Monad m => Injectable m Bool where
    injecte = VLitteralM . Bool
  1. Définissez l’instance de Injectable pour les Integer.

Nous voulons pouvoir injecter automatiquement une fonction comme negate :: Integer -> Integer. Il nous faut pour cela une instance pour un type fonctionnel. Ainsi, si nous avons à injecter une fonction de type Integer -> t, nous pouvons utiliser une VFonctionM qui va attendre un entier. Pour produire son résultat (qui doit correspondre au type t), elle utilisera bien entendu l’injection du résultat.

  1. Définissez les instances de Injectable pour les fonctions prenant en premier argument un Integer ou un Bool :

  2. En définissant un environnement

    etc., définissez un interprète monadique avec toutes les primitives qui vous intéressent et faites-en une version interactive.

Pousse-café : un interprète parallèle

Pour torturer un peu votre interprète en lui donnant du fil à retordre, nous allons écrire des expressions un peu longues à évaluer.

  1. Analysez fibonacci.interp pour comprendre comment cette expression est l’implémentation naïve de Fibonacci. Vous devriez y retrouver :

    • le combinateur de point fixe de Curry
    • beaucoup de fonctions \lazy -> ... qui seront finalement appliquées à 0 : comme l’interprète est strict, il est important d’explicitement bloquer l’évaluation de certaines sous-expressions en en faisant des fonctions et en contrôlant à quel moment elles seront évaluées en les appliquant à une valeur quelconque.

    Que se passerait-il sans les \lazy -> ... ?

  2. Ajoutez à votre interprète des primitives if (similaire à ifthenelseA) et infst (correspondant à (<) en Haskell).

    En compilant votre interprète avec l’option -O2 (meilleur niveau d’optimisation), mesurez avec time la durée d’exécution du calcul de Fibonacci et trouvez un nombre qui demande une dizaine de secondes à évaluer sur votre machine.

  3. En ajoutant par et pseq dans votre interprète, rendez votre interprète parallèle et évaluez le gain de temps en fonction du nombre du processeurs que vous lui consacrez. Vous lancerez donc :

    si vous voulez exécuter votre interprète en utilisant deux cœurs.


Références ayant inspiré cet énoncé :


  1. Notez que cette recombinaison correspond au fait que les fonctions sont curryfiées : on applique une fonction à deux arguments à son premier argument, ce qui nous donne une fonction ; puis on applique cette fonction résultat au second argument.

  2. ou showsPrec, mais cette fonction est bien plus compliquée !

  3. Haskell utilise des sortes, un système de types pour les types. Vous pouvez ainsi demander :

    * est la sorte d’un type. Vous pouvez ainsi explorer comment il sorte les classes de types telle que Show

  4. À partir de GHC 7.10, la classe Monad est une classe fille de Applicative, qui est elle-même fille de Functor. Du coup, toute instance de Monad devra être aussi instance des deux autres classes. Il suffit pour cela d’ajouter, pour chacune de vos instances de Monad, par exemple SimpleM :

    ap et liftM sont des fonctions du module Control.Monad.