sbi.re

Achille

Auteurices : flupe
Date d'ajout : 08 Novembre 2021
Modifié le : 10 Novembre 2021
[source]

achille est le nom d’une libraire confectionnée par mes soins, qui permet de définir des générateurs incrémentaux de sites statiques en Haskell. Elle est utilisée pour ce wiki et quelques autres de mes sites. Je pourrais rentrer dans les détails mais plus d’information sur le pourquoi et le comment de cette librairie est disponible ici.

Sur cette page — et c’est pourquoi elle est temporaire, je veux simplement rassembler quelques notes sur le futur d’achille, afin de corriger les quelques (sévères) limitations.

Fruits à portée de main

  • Utiliser des chemins fortement typés. A voir entre path ou strong-path.
  • Améliorer le logging, le rendre optionnel.
  • Mesurer le temps écoulé pendant les runs, l’afficher.
  • Unifier l’API. Choisir des conventions (match, matchFile, match_, etc) et s’y tenir.
  • Rajouter des tests unitaires. Normalement l’infrastructure de base est en place.
  • Remplacer glob par une alternative plus efficace et complète. Possiblement glob-posix, un wrapper pour la fonction glob.
    • On veut des patterns de recherche plus complets, notamment pouvoir ignorer certains fichiers, ou faire l’union de plusieurs patterns.
    • On veut pouvoir imposer un ordre sur les fichiers, probablement juste lexicographique. Actuellement l’ordre des résultats est aléatoire, ce qui explique pourquoi entre deux générations les pages du wiki changent de place dans l’index.
  • Pas uniquement se baser sur les timestamps pour invalider le cache. Des fois le timestamp change sans pour autant impacter le contenu. Et parfois le fichier change avec un timestamp plus ancien (Probable qu’utiliser git provoque ce genre de chose). Se renseigner sur ce qu’utilisent d’autres build system, certainement qu’on peut calculer un checksum pour pas trop cher.
  • Arrêter d’utiliser Data.Default.

Incrémentalisme

Ce qui suit n’est pas du vrai code Haskell, juste une vague idée de ce qu’on pourrait faire.

class Incremental a where
  Delta :: *
  -- ...

fold :: (Foldable t, Incremental (t a), Monoid a, Monad m)
     => Delta (t a)
     -> Task m a

foldr :: (Foldable t, Incremental (t a), Monad m)
      => (a -> b -> b)
      -> b
      -> Delta (t a)
      -> Task m b

L’idée étant qu’on doit pouvoir réimplémenter l’interface de Foldable (ou n’importe quelle autre classe) de telle sorte que ses opérations agissent non plus sur a mais Delta a, et profitent de leur propre cache pour incrémentaliser leur calcul. Bon, Foldable c’est pas forcément le meilleur exemple parce qu’on pourra seulement mémoriser un peigne à droite, mais si un élément a changé au milieu il faudra remonter l’arbre de calcul jusqu’en haut.

fmap :: (Functor t, Incremental (t a), Incremental (t b), Monad m)
     => (a -> b)
     -> Delta (t a)
     -> Task m (Delta (t b))

Souvent quand on entend parlé de calcul incremental (et de différenciation automatique), le type Delta a ne permet pas en soit de retomber sur une valeur de type a. En revanche, on peut ajouter un delta a n’importe quelle valeur pour en obtenir une nouvelle.

apply :: a -> Delta a -> a

Dans notre cas, j’ai l’impression qu’on veut juste ajouter de l’information à une valeur, en indiquant précisemment comment elle a changé.

extract :: Delta a -> a

TODO: Investiguer STM et stm-incremental.

Pagination

Pour l’instant, il n’y a pas de manière simple de faite de la pagination. En particulier, mettons que je récupère une liste d’articles de blog :

renderPost :: FilePath -> Task IO Post
renderPage :: [Post] -> Task IO ()
chunksOf   :: Int -> [a] -> [[a]]
match      :: Pattern -> (FilePath -> m a) -> Task m [a]
forM_      :: Monad m => [a] -> (a -> m b) -> m ()

main :: IO ()
main = achille do
  posts :: [Post] <- match "posts/*.md" renderPost

  -- je peux découper en plusieurs listes de taille 5
  let pages = chunksOf 5 posts

  -- ensuite je peux générer chacune des pages de pagination
  forM_ pages renderPage

Avec cette implémentation, les pages de pagination sont générées systématiquement, indépendamment de si la liste d’articles a changé ou non. On peut forcer la pagination a n’être générée que lorsque la liste d’article a changé.

mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

main :: IO ()
main = achille do
  posts <- match "posts/*.md" renderPost
  watch posts do
    mapM_ renderPage (chunksOf 5 posts)

C’est un début, mais lorsqu’un seul des articles change, la totalité des pages de pagination est générée, y compris celles où il ne figure pas. Si on imagine que les idées de la partie précédente ont porté leur fruit, ça pourrait donner :

match    :: Pattern -> (FilePath -> m a) -> Task m (Delta [a])
chunksOf :: Int -> Delta [a] -> Task m (Delta [[a]])
forM_    :: Delta [a] -> (a -> m b) -> Task m ()

main :: IO ()
main = achille do
  posts <- match "posts/*.md" renderPost
  pages <- chunksOf 5 posts
  forM_ pages renderPage

Si les primitives chunksOf, match et forM_ sont implémentées correctement, alors on devrait avoir le comportement souhaité. La syntaxe n’a pas l’air plus alourdie que ça.

Catégories et Clotures

Un des problèmes majeurs de la librairie est le suivant : L’amélioration notable d’achille par rapport à Hakyll est la gestion explicite des dépendances entre les étapes de génération. Récupérer le résultat d’une étape pour l’utiliser ailleurs est une simple histoire de bind monadique >>=. Seulement du point de vue de la librairie, impossible de savoir où la valeur est utilisée à la droite du bind. Si la valeur à gauche change, on doit donc choisir entre forcer l’évaluation de tout ce qu’il y a à droite, en profondeur, au risque de faire du travail inutile, ou ne pas ré-évaluer, au risque de ne pas mettre à jour suffisamment de choses. On opte pour la première approche pour s’assurer d’un résultat correct, mais ça oblige l’utilisateur a devoir se soucier lui-même de la mémoisation s’il veut s’épargner du calcul redondant. Dans l’idée, on aimerait savoir exactement où sont utilisés les résultats intermédiraires, pour ne seulement déclencher que les taches qui en dépendent.

Conal Elliott a publié le papier Compiling to Categories dans lequel il rappelle que n’importe quelle catégorie cartésienne close est un modèle du lambda calcul. Autrement dit, étant donné une catégorie c :: * -> * -> * (en Haskell) et une instance Category c, il est possible de convertir automatiquement n’importe quelle fonction a -> b en une flèche de la catégorie c a b.

C’est exactement ce que permet son plugin GHC concat, avec lequel il implémente plusieurs transformations originales.

En reprenant les notations de la partie précédente, et si on arrive à prouver que Incr a b = Delta a -> Task m (Delta b) est une catégorie, alors on devrait pouvoir convertir n’importe quelle fonction a -> b en son équivalent incrémental/mémoïsé Delta a -> Task m (Delta b) for free.

Le risque, c’est que concat est fortement expérimental, et l’utiliser dans notre librairie obligerait tous les utilisateurs à dépendre d’un plugin GHC. Mais comme je suis le seul utilisateur de cette librairie, c’est jouable