wiki

Wiki for sbi.re
Log | Files | Refs | Submodules | README

achille.md (7856B)


1---
2title: Achille
3author: lucas
4created: 8/11/2021
5updated: 08/11/2021
6---
7
8**achille** est le nom d'une libraire confectionnée par mes soins, qui permet de
9définir des générateurs incrémentaux de sites statiques en Haskell. Elle est
10utilisée pour ce [wiki](wiki:meta/wiki) et quelques autres de mes sites.  Je pourrais rentrer
11dans les détails mais plus d'information sur le pourquoi et le comment de cette
12librairie est [disponible ici][documentation].
13
14Sur cette page --- et c'est pourquoi elle est temporaire, je veux simplement
15rassembler quelques notes sur le futur d'*achille*, afin de corriger les
16quelques (sévères) limitations.
17
18[documentation]: https://acatalepsie.fr/projects/achille
19
20## Fruits à portée de main
21
22- Utiliser des chemins fortement typés. A voir entre
23  [path](https://github.com/commercialhaskell/path) ou
24  [strong-path](https://github.com/wasp-lang/strong-path#readme).
25- Améliorer le logging, le rendre optionnel.
26- Mesurer le temps écoulé pendant les runs, l'afficher.
27- Unifier l'API. Choisir des conventions (`match`, `matchFile`,
28  `match_`, etc) et s'y tenir.
29- Rajouter des tests unitaires. Normalement l'infrastructure de base est en
30  place.
31- Remplacer `glob` par une alternative plus efficace et complète. Possiblement
32  [glob-posix](https://hackage.haskell.org/package/glob-posix), un wrapper pour
33  la fonction `glob`.
34  - On veut des patterns de recherche plus complets, notamment pouvoir ignorer
35    certains fichiers, ou faire l'union de plusieurs patterns.
36  - On veut pouvoir imposer *un ordre sur les fichiers*, probablement juste
37    lexicographique. Actuellement l'ordre des résultats est aléatoire, ce qui
38    explique pourquoi entre deux générations les pages du wiki changent de
39    place dans l'index.
40- Pas uniquement se baser sur les timestamps pour invalider le cache.
41  Des fois le timestamp change sans pour autant impacter le contenu.
42  Et parfois le fichier change avec un timestamp plus ancien (Probable
43  qu'utiliser `git` provoque ce genre de chose).
44  Se renseigner sur ce qu'utilisent d'autres build system, certainement qu'on
45  peut calculer un checksum pour pas trop cher.
46- [Arrêter d'utiliser `Data.Default`](https://markkarpov.com/post/data-default.html).
47
48## Incrémentalisme
49
50Ce qui suit n'est pas du vrai code Haskell, juste une vague idée de ce qu'on
51pourrait faire.
52
53```haskell
54class Incremental a where
55  Delta :: *
56  -- ...
57
58fold :: (Foldable t, Incremental (t a), Monoid a, Monad m)
59     => Delta (t a)
60     -> Task m a
61
62foldr :: (Foldable t, Incremental (t a), Monad m)
63      => (a -> b -> b)
64      -> b
65      -> Delta (t a)
66      -> Task m b
67```
68
69L'idée étant qu'on doit pouvoir réimplémenter l'interface de `Foldable` (ou
70n'importe quelle autre classe) de telle sorte que ses opérations agissent non
71plus sur `a` mais `Delta a`, et profitent de leur propre cache pour
72incrémentaliser leur calcul. Bon, `Foldable` c'est pas forcément le meilleur
73exemple parce qu'on pourra seulement mémoriser un peigne à droite, mais si un
74élément a changé au milieu il faudra remonter l'arbre de calcul jusqu'en haut.
75
76```haskell
77fmap :: (Functor t, Incremental (t a), Incremental (t b), Monad m)
78     => (a -> b)
79     -> Delta (t a)
80     -> Task m (Delta (t b))
81```
82
83Souvent quand on entend parlé de calcul incremental (et de *différenciation
84automatique*), le type `Delta a` ne permet pas en soit de retomber sur une
85valeur de type `a`. En revanche, on peut ajouter un delta a n'importe quelle
86valeur pour en obtenir une nouvelle.
87
88```haskell
89apply :: a -> Delta a -> a
90```
91
92Dans notre cas, j'ai l'impression qu'on veut juste ajouter de l'information à
93une valeur, en indiquant précisemment *comment* elle a changé.
94
95```
96extract :: Delta a -> a
97```
98
99*TODO*: Investiguer STM et [stm-incremental].
100
101[stm-incremental]: https://hackage.haskell.org/package/stm-incremental
102
103## Pagination
104
105Pour l'instant, il n'y a pas de manière simple de faite de la pagination.
106En particulier, mettons que je récupère une liste d'articles de blog :
107
108```haskell
109renderPost :: FilePath -> Task IO Post
110renderPage :: [Post] -> Task IO ()
111chunksOf   :: Int -> [a] -> [[a]]
112match      :: Pattern -> (FilePath -> m a) -> Task m [a]
113forM_      :: Monad m => [a] -> (a -> m b) -> m ()
114
115main :: IO ()
116main = achille do
117  posts :: [Post] <- match "posts/*.md" renderPost
118
119  -- je peux découper en plusieurs listes de taille 5
120  let pages = chunksOf 5 posts
121
122  -- ensuite je peux générer chacune des pages de pagination
123  forM_ pages renderPage
124```
125
126Avec cette implémentation, les pages de pagination sont générées
127systématiquement, indépendamment de si la liste d'articles a changé ou non.
128On peut forcer la pagination a n'être générée que lorsque la liste d'article
129a changé.
130
131```haskell
132mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
133
134main :: IO ()
135main = achille do
136  posts <- match "posts/*.md" renderPost
137  watch posts do
138    mapM_ renderPage (chunksOf 5 posts)
139```
140
141C'est un début, mais lorsqu'un seul des articles change, la totalité des pages
142de pagination est générée, y compris celles où il ne figure pas.
143Si on imagine que les idées de la partie précédente ont porté leur fruit, ça
144pourrait donner :
145
146```haskell
147match    :: Pattern -> (FilePath -> m a) -> Task m (Delta [a])
148chunksOf :: Int -> Delta [a] -> Task m (Delta [[a]])
149forM_    :: Delta [a] -> (a -> m b) -> Task m ()
150
151main :: IO ()
152main = achille do
153  posts <- match "posts/*.md" renderPost
154  pages <- chunksOf 5 posts
155  forM_ pages renderPage
156```
157
158Si les primitives `chunksOf`, `match` et `forM_` sont implémentées correctement,
159alors on devrait avoir le comportement souhaité. La syntaxe n'a pas l'air plus
160alourdie que ça.
161
162## Catégories et Clotures
163
164Un des problèmes majeurs de la librairie est le suivant : L'amélioration notable
165d'*achille* par rapport à Hakyll est la gestion *explicite* des dépendances entre
166les étapes de génération. Récupérer le résultat d'une étape pour l'utiliser
167ailleurs est une simple histoire de bind monadique `>>=`. Seulement du point de
168vue de la librairie, impossible de savoir où la valeur est utilisée à la droite
169du bind. Si la valeur à gauche change, on doit donc choisir entre forcer l'évaluation
170de tout ce qu'il y a à droite, en profondeur, au risque de faire du travail
171inutile, ou ne pas ré-évaluer, au risque de ne pas mettre à jour suffisamment de
172choses. On opte pour la première approche pour s'assurer d'un résultat correct,
173mais ça oblige l'utilisateur a devoir se soucier lui-même de la mémoisation s'il
174veut s'épargner du calcul redondant. Dans l'idée, on aimerait savoir exactement
175où sont utilisés les résultats intermédiraires, pour ne seulement déclencher que
176les taches qui en dépendent.
177
178Conal Elliott a publié le papier *Compiling to Categories* dans lequel il
179rappelle que n'importe quelle catégorie cartésienne close est un modèle du
180lambda calcul. Autrement dit, étant donné une catégorie `c :: * -> * -> *` (en Haskell)
181et une instance `Category c`, il est possible de convertir automatiquement
182n'importe quelle fonction `a -> b` en une flèche de la catégorie `c a b`.
183
184C'est exactement ce que permet son plugin GHC [concat], avec lequel il
185implémente plusieurs transformations originales.
186
187[concat]: https://github.com/conal/concat
188
189En reprenant les notations de la partie précédente, et si on arrive à prouver
190que `Incr a b = Delta a -> Task m (Delta b)` est une catégorie, alors on devrait
191pouvoir convertir n'importe quelle fonction `a -> b` en son équivalent
192incrémental/mémoïsé `Delta a -> Task m (Delta b)` *for free*.
193
194Le risque, c'est que *concat* est fortement expérimental, et l'utiliser dans
195notre librairie obligerait tous les utilisateurs à dépendre d'un plugin GHC.
196Mais comme je suis le seul utilisateur de cette librairie, c'est jouable