wiki

achille.md (7856B)

---

---
title: Achille
author: lucas
created: 8/11/2021
updated: 08/11/2021
---

**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](wiki:meta/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][documentation].

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.

[documentation]: https://acatalepsie.fr/projects/achille

## Fruits à portée de main

- Utiliser des chemins fortement typés. A voir entre
  [path](https://github.com/commercialhaskell/path) ou
  [strong-path](https://github.com/wasp-lang/strong-path#readme).
- 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](https://hackage.haskell.org/package/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`](https://markkarpov.com/post/data-default.html).

## Incrémentalisme

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

```haskell
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.

```haskell
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.

```haskell
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].

[stm-incremental]: https://hackage.haskell.org/package/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 :

```haskell
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é.

```haskell
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 :

```haskell
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.

[concat]: https://github.com/conal/concat

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