L'approche Tagless Final, en Haskell
Voir aussi : video youtube - video peertube - code source
L’approche Tagless Final est une façon classique d’organiser du code. Elle permet notamment d’implémenter des DSL ou de compléter le pattern ReaderT.
Grossièrement, l’approche Tagless Final en Haskell consiste à définir le langage de l’application via des classes de types et à définir des interpréteurs de ce langage via des instances. Cette approche a pour avantage d’être facile à comprendre et à faire évoluer.
Cet article développe l’approche Tagless Final à partir d’un exemple classique (définir et interpréter un langage d’expressions arithmétiques) puis présente un exemple d’application Tagless Final + pattern ReaderT.
Initial encoding
On veut implémenter un langage d’expressions arithmétiques (avec entier, réel et addition) puis interpréter des expressions (évaluation, affichage en notation préfixée…) ou faire évoluer le langage (opérateur de comparaison…).
Une première façon de faire est d’utiliser un type algébrique pour définir notre langage d’expressions arithmétiques (on appelle parfois cela un “encodage initial”).
data Expr
= IntConst Int
| RealConst Double
| Add Expr ExprOn peut ensuite écrire des expressions arithmétiques, de type Expr.
expr1 :: Expr
expr1 = Add (IntConst 20) (IntConst 22)
expr2 :: Expr
expr2 = Add (RealConst 20) (RealConst 22)Et réaliser des opérations simples sur des Expr, comme par exemple, les formater en notation préfixée :
view :: Expr -> String
view (IntConst x) = show x
view (RealConst x) = show x
view (Add x y) = "(+ " ++ view x ++ " " ++ view y ++ ")"Cependant, ce type Expr est peu pratique pour l’évaluation, car il nécessite de gérer explicitement les additions “entier-réel” ainsi que le type de retour :
data Result
= IntResult Int
| RealResult Double
deriving Show
eval :: Expr -> Maybe Result
eval (IntConst x) = Just (IntResult x)
eval (RealConst x) = Just (RealResult x)
eval (Add x0 y0) = do
x1 <- eval x0
y1 <- eval y0
case (x1, y1) of
(IntResult x, IntResult y) -> Just $ IntResult (x + y)
(RealResult x, RealResult y) -> Just $ RealResult (x + y)
_ -> NothingExemple d’exécution :
$ ghci expr1.hs
ghci> eval $ Add (IntConst 20) (IntConst 22)
Just (IntResult 42)
ghci> view $ Add (IntConst 20) (IntConst 22)
"(+ 20 22)"
ghci> eval $ Add (IntConst 20) (RealConst 22)
NothingFinal encoding
Pour vérifier des expressions arithmétiques plus efficacement, on définit un type polymorphe Expr a et des fonctions “constructeurs de types”. On parle ici d’encodage final car les constructeurs ne font plus partie du type initial.
newtype Expr a = Expr { unExpr :: a }
intConst :: Int -> Expr Int
intConst x = Expr x
realConst :: Double -> Expr Double
realConst x = Expr x
add :: Num a => Expr a -> Expr a -> Expr a
add (Expr x) (Expr y) = Expr (x+y)On peut ensuite écrire des expressions arithmétiques mais désormais le compilateur interdit les additions “entier-réel” et détermine automatiquement les types de retour.
$ ghci expr2.hs
ghci> unExpr $ add (intConst 20) (intConst 22)
42
ghci> unExpr $ add (realConst 20) (realConst 22)
42.0
ghci> unExpr $ add (intConst 20) (realConst 22)
<interactive>:3:29: error:
• Couldn't match type ‘Double’ with ‘Int’
...Cependant, cet encodage ne représente plus vraiment le langage mais directement son interprétation (évaluation de l’expression arithmétique), ce qui complique l’implémentation d’une autre interprétation (par exemple, le formatage en notation préfixée).
GADT
Une autre solution à l’encodage final précédent consiste à utiliser les types algébriques généralisés (GADT). En effet, les GADT permettent de définir des constructeurs plus précis :
data Expr a where
IntConst :: Int -> Expr Int
RealConst :: Double -> Expr Double
Add :: Num a => Expr a -> Expr a -> Expr aComme pour l’encodage initial, on peut définir des expressions arithmétiques :
expr1 :: Expr Int
expr1 = Add (IntConst 20) (IntConst 22)
expr2 :: Expr Double
expr2 = Add (RealConst 20) (RealConst 22)Ainsi que des interpréteurs (évaluation, formatage) :
eval :: Expr a -> a
eval (IntConst x) = x
eval (RealConst x) = x
eval (Add x y) = eval x + eval y
view :: Expr a -> String
view (IntConst x) = show x
view (RealConst x) = show x
view (Add x y) = "(+ " ++ view x ++ " " ++ view y ++ ")"Mais désormais, les types sont vérifiés plus précisément, notamment pour interdire l’addition “entier-réel” :
$ ghci expr-gadt1.hs
ghci> eval $ Add (IntConst 20) (IntConst 22)
42
ghci> view $ Add (RealConst 20) (RealConst 22)
"(+ 20.0 22.0)"
ghci> eval $ Add (IntConst 20) (RealConst 22)
<interactive>:2:27: error:
• Couldn't match type ‘Double’ with ‘Int’
...Cette approche avec GADT est parfois appelé Tagless Initial car elle ne nomme pas explicitement les résultats (pas de IntResult, RealResult…) et car on encode dès le type initial (Expr).
Cependant, il reste que cette approche n’est pas très évolutive. Par exemple, si on veut ajouter la comparaison less dans notre langage d’expressions arithmétiques, alors il faut modifier le GADT ainsi que ses interpréteurs :
data Expr a where
...
Less :: Ord a => Expr a -> Expr a -> Expr Bool
eval :: Expr a -> a
...
eval (Less x y) = eval x < eval y
view :: Expr a -> String
...
view (Less x y) = "(< " ++ view x ++ " " ++ view y ++ ")"Tagless final encoding
L’approche Tagless Final consiste à implémenter notre langage d’expressions arithmétiques via une classe de types au lieu d’un type algébrique.
class Expr repr where
intConst :: Int -> repr Int
realConst :: Double -> repr Double
add :: Num a => repr a -> repr a -> repr aOn peut ensuite définir des expressions arithmétiques, paramétrée par une représentation de classe Expr :
expr1 :: (Expr repr) => repr Int
expr1 = add (intConst 20) (intConst 22)
expr2 :: (Expr repr) => repr Double
expr2 = add (realConst 20) (realConst 22)Cette représentation permet d’implémenter des interpréteurs. Pour cela, il suffit de définir un type et de lui faire instancier Expr de façon à produire le résultat voulu. Par exemple, pour évaluer une expression arithmétique :
newtype Eval a = Eval { runEval :: a }
instance Expr Eval where
intConst x = Eval x
realConst x = Eval x
add a b = Eval $ runEval a + runEval bOn peut alors définir et évaluer des expressions arithmétiques, vérifiées par le compilateur :
$ ghci expr3.hs
ghci> runEval $ add (intConst 20) (intConst 22)
42
ghci> runEval $ add (realConst 20) (realConst 22)
42.0
ghci> runEval $ add (intConst 20) (realConst 22)
<interactive>:3:31: error:
• Couldn't match type ‘Double’ with ‘Int’
...De même, on peut implémenter un interpréteur pour formater une expression arithmétique en notation préfixée :
newtype Format a = Format { runFormat :: String }
instance Expr Format where
intConst x = Format $ show x
realConst x = Format $ show x
add a b = Format $ "(+ " ++ runFormat a ++ " " ++ runFormat b ++ ")"Enfin, on peut étendre facilement le langage d’expression arithmétique en ajoutant d’autres classes de types. Par exemple, pour la comparaison de nombres :
class Less repr where
less :: Ord a => repr a -> repr a -> repr BoolSi on veut ajouter cette extension à nos interpréteurs précédents, il suffit d’instancier la nouvelle classe pour les types correspondants :
instance Less Eval where
less a b = Eval $ runEval a < runEval b
instance Less Format where
less a b = Format $ "(< " ++ runFormat a ++ " " ++ runFormat b ++ ")"Exemple d’exécution :
$ ghci expr4.hs
ghci> runFormat $ less (intConst 20) (add (intConst 10) (intConst 12))
"(< 20 (+ 10 12))"
ghci> runFormat $ less (intConst 20) (less (intConst 10) (intConst 12))
<interactive>:2:33: error:
• Couldn't match type ‘Bool’ with ‘Int’
...Exemple d’application
Pour finir, voici un exemple d’application utilisant le pattern ReaderT et le style Tagless Final. Il s’agit d’une application basique de gestion d’utilisateurs, stockés dans une variable mutable, et avec un système de log.
Tout d’abord, on définit les extensions, les dépendances et les types de base à manipuler dans l’application.
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Control.Concurrent.MVar
import Control.Monad.Reader
data User = User
{ _name :: String
, _age :: Int
} deriving (Show)Puis on définit le “langage” de l’application via deux classes de types, MonadLog et MonadUsers, selon le style Tagless Final.
class Monad m => MonadLog m where
logMsg :: String -> m ()
class Monad m => MonadUsers m where
getUsers :: m [User]
deleteUser :: String -> m ()On définit l’environnement d’exécution avec un type Env ainsi que le pattern ReaderT avec un type AppM et une fonction d’exécution runAppM. AppM correspond à l’interpréteur du langage de l’application.
data Env = Env
{ _usersVar :: MVar [User]
, _logFunc :: String -> IO ()
}
newtype AppM a =
AppM { unAppM :: ReaderT Env IO a }
deriving (Functor, Applicative, Monad, MonadIO, MonadReader Env)
runAppM :: AppM a -> Env -> IO a
runAppM app env = runReaderT (unAppM app) envIl ne reste qu’à instancier les classes MonadLog et MonadUsers pour AppM.
instance MonadLog AppM where
logMsg msg = do
f <- asks _logFunc
liftIO $ f msg
instance MonadUsers AppM where
getUsers = do
usersVar <- asks _usersVar
liftIO $ readMVar usersVar
deleteUser name = do
usersVar <- asks _usersVar
liftIO $ modifyMVar_ usersVar (return . filter ((/=name) . _name))Et on peut écrire et exécuter l’application proprement dite, via le langage ainsi implémenté. On notera que l’utilisation de monades permet d’écrire l’application très facilement, via la “notation do”.
app1 :: (MonadUsers m, MonadLog m) => m [User]
app1 = do
users0 <- getUsers
logMsg $ "users0: " <> unwords (map _name users0)
deleteUser "John"
users1 <- getUsers
logMsg $ "users1: " <> unwords (map _name users1)
return users1
main :: IO ()
main = do
myVar <- newMVar [User "Pedro" 13, User "John" 42]
let myLog msg = putStrLn $ "-> " <> msg
res <- runAppM app1 (Env myVar myLog)
print resExemple d’exécution :
$ runghc app.hs
-> users0: Pedro John
-> users1: Pedro
[User {_name = "Pedro", _age = 13}]On notera que cette implémentation est relativement simple à étendre. On peut par exemple ajouter d’autres applications, fonctionnalités du langage ou interpréteurs.
Conclusion
L’approche Tagless Final permet d’organiser le code d’une application ou d’un DSL. Elle consiste à définir le langage de base via des classes de types et à implémenter l’interpréteur via des types algébriques et des instances. Elle est simple à mettre en oeuvre et à faire évoluer, tant au niveau du langage qu’au niveau des interpréteurs. En Haskell, c’est une approche classique, alternative à l’approche des Free Monads.
Quelques liens :