6.20 Le jeu de la vie de Conway en LispE - naver/lispe GitHub Wiki
Une seule ligne de code
Le jeu de la vie de Conway se joue dans une grille infinie et se résume aux trois règles suivantes:
- Une cellule morte possédant exactement trois cellules voisines vivantes naît.
- Une cellule vivante possédant deux ou trois cellules voisines vivantes le reste.
- Dans toutes les autres configurations, elle meurt.
Or, il y a quelques années, un programme APL a fait beaucoup parlé de lui. En effet, le jeu avait été implanté en... une ligne de code:
⍝ Le jeu de la vie de Conway en une ligne d'APL
life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
Une ligne à l'allure ésotérique ou cabalistique qui laissa nombre d'observateurs perplexe. APL fait partie d'une famille de langage que l'on appelle langage de tableau ou array languages en anglais. Ces langages, tels que UIUA ou BQN, ont été conçu avec l'idée de remplacer les mots clefs habituels des langages, le plus souvent en anglais, par un jeu de symboles mathématiques dont la combinaison permet de manipuler des scalaires, des vecteurs ou des matrices de taille variable. Les utilisateurs de ces langages, qui affirment qu'ils sont aussi lisibles, si ce n'est plus, que les langages traditionnels s'amusent souvent à découvrir la façon la plus concise et la plus efficace de combiner ces symboles pour implanter des algorithmes complexes. Le jeu de la vie est, d'une certaine façon, leur dernière victime.
Nous allons montrer comment grace à LispE, on peut mettre en lumière les ressorts cachés de cette ligne diabolique.
LispE
Pourquoi choisir LispE?
Pour une raison toute bête, LispE est un dialecte de Lisp qui s'appuie sur des tableaux et non des listes chainées. De ce fait, nombre d'opérateurs d'APL peuvent être implantés en LispE.
Malheureusement, en tant que digne représentant de la famille Lisp, les parenthèses sont présentes... en grand nombre:
(sqrt (sum (maplist (λ(x) (* x 2)) '(1 2 3 4 5 6))))
Ce qu'APL réduit à quelques symboles:
√+/2ר1 2 3 4 5 6.
Il est clair qu'aucun dialecte de Lisp n'arrivera jamais à atteindre une telle concision. En revanche, nous pouvons peut-être nous inspirer d'autres langages existants pour au moins réduire le nombre de parenthèses.
L'opérateur de composition
LispE dispose d'un opérateur qui permet de combiner plusieurs appels de fonctions en une seule expression intégrée.
Par exemple, une expression LispE typique qui applique deux fonctions, filter et map, à une liste générée par iota 10 s'écrit généralement sous la forme suivante:
(filter '(< 10) (map '(* 2) (iota 10)))
Cependant, avec l'opérateur de composition . , on peut simplifier cette expression en composant ces fonctions:
(filter '(< 10) . map '(* 2) (iota 10))
De plus, il n'y a pas de limite au nombre de fonctions que vous pouvez composer en utilisant cet opérateur. Par exemple, vous pouvez calculer la racine carrée de la somme d'une séquence de nombres avec :
(sqrt . sum . iota 10) ; 7.4162
Soyons honnête, ce que cet opérateur autorise, c'est de faire sauter les parenthèses du dernier élément de la liste. Mais, il a le bon goût d'exister et de permettre de réduire de façon significative les parenthèses. Il faut simplement être conscient que dans certains cas, cela peut conduire à une erreur.
;Le compilateur recompose hélas cette expression sous la forme: (cons (car '(a b c) 'd))
(cons . car '(a b c) 'd)
Le jeu de la vie en une ligne
Reprenons le fameux programme APL:
life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}
Tout d'abord, il faut comprendre qu'un programme APL s'interprète de la droite vers la gauche. Le ⍵ ici est l'équivalent d'un argument de fonction. En APL, on fait la différence entre les opérateurs monadiques et dyadiques:
- un opérateur monadique prend un seul argument à sa droite.
- un opérateur dyadique prend deux arguments, un à gauche et un à droite.
Si l'on prend la partie la plus à droite de l'expression: ¯1 0 1 ⌽¨ ⊂⍵, on voit qu'elle est composée de trois opérateurs: ⌽¨ ⊂. Le premier prend une matrice, qui correspond à la grille du jeu de Conway, et la transforme en une liste de sous-ensemble, il est monadique. L'opérateur ¨, applique alors l'opérateur ⌽ à chacun des éléments de cette liste. ⌽ effectue donc trois rotations -1 0 1 sur les colonnes de la matrice initiale ⍵, ce qui génère trois nouvelles matrices.
Si l'on traduit ce code en LispE, on obtient:
; On va initialiser ⍵ avec une matrice de 1 et de 0
; Notons que LispE permet l'utilisation de caractères unicodes pour ses noms de variables
(setq ⍵ (rho 5 5 . integers 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 ))
La matrice ⍵ initiale à la forme suivante:
(0 0 0 0 0)
(0 0 0 1 0)
(0 1 1 1 0)
(0 0 0 0 0)
(0 0 0 0 0)
On applique alors trois rotations différentes sur ⍵:
(maplist (λ(x) (rotate ⍵ x)) '(-1 0 1))
;Notons que rotate peut aussi s'écrire: ⌽
(maplist (λ(x) (⌽ ⍵ x)) '(-1 0 1))
Après application de maplist, on obtient une liste de trois matrices:
;rotation -1
(0 0 0 0 0)
(0 0 1 0 0)
(1 1 1 0 0)
(0 0 0 0 0)
(0 0 0 0 0)
;rotation 0
(0 0 0 0 0)
(0 0 0 1 0)
(0 1 1 1 0)
(0 0 0 0 0)
(0 0 0 0 0)
;rotation 1
(0 0 0 0 0)
(0 0 0 0 1)
(0 0 1 1 1)
(0 0 0 0 0)
(0 0 0 0 0)
Pour bien comprendre l'idée sous-jacente, il faut se rappeler que ce qui est important ici, c'est de connaitre le nombre de voisins d'une cellule donnée. Les rotations permettent donc à chaque itération de ramener à la position dans la grille de chaque cellule, l'ensemble de ses voisins.
Par conséquent, on fait d'abord deux rotations des colonnes, une vers la gauche l'autre vers la droite. La rotation 0 permet simplement de garder la grille initiale.
On va ensuite appliquer à chacune de ces 3 matrices une rotation des lignes. Ce qui va donner un total de 9 matrices.
Dans le programme APL, cela revient à utiliser le produit externe: °. et à appliquer la rotation des lignes grâce à l'opérateur ⊖:
¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵
Autrement dit, on applique 3 rotations des lignes à chacune des matrices obtenues par la rotation des colonnes, soit 9 matrices comme résultat.
En LispE, cela donne:
(outer (λ(x ⍺) . rotate ⍺ x true) '(1 0 -1) . maplist (λ(x) . rotate ⍵ x) '(1 0 -1))
; Notons que la fonction outer peut aussi s'écrire: °
; Pour garder la correspondance avec APL, nous allons définir la macro suivante:
(defmacro ⊖(l n) (rotate l n true))
; On peut alors réécrire la ligne au-dessus:
(° (λ(x ⍺) . ⊖ ⍺ x) '(1 0 -1) . maplist (λ(x) . ⌽ ⍵ x) '(1 0 -1))
Evidemment, on est loin de la concision du langage APL, mais malgré tout, on retrouve les mêmes opérateurs. rotate ⍺ x true effectue une rotation des lignes des matrices issues de maplist.
Il suffit dès lors de sommer les colonnes puis les lignes:
+/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵
Le premier opérateur: +⌿applique une réduction sur les colonnes et le second une réduction sur les lignes, en sommant les valeurs entre elles.
LispE propose les mêmes opérateurs:
(-// '+ . -// '+ . ° (λ(x ⍺) . ⊖ ⍺ x) '(1 0 -1) . maplist (λ(x) . ⌽ ⍵ x) '(1 0 -1))
On obtient alors:
(0 0 1 1 1)
(1 2 4 3 2)
(1 2 4 3 2)
(1 2 3 2 1)
(0 0 0 0 0)
La règle est alors la suivante:
- Si la valeur de la cellule vaut 3, elle est vivante au cycle suivant
- Si la valeur de la cellule vaut 4, alors si une cellule était vivante au cycle présent, elle survit au cycle suivant
3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵
L'opérateur = teste les valeurs à sa gauche sur la matrice à sa droite et génère deux matrices Booléennes, en plaçant un 1 aux positions correspondants à un 3 ou un 4.
1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵
Pour répondre à la contrainte pour les cellules de valeur 4, on fait une intersection avec la matrice d'origine, puis on effectue une union avec la matrice des 3.
Voici donc, notre propre implantation du jeu de la vie en LispE:
; Finalement on peut enfin implanter notre jeu de la vie en une seule ligne de LispE:
((λ(⍺) (| (& (== ⍺ 4) ⍵) (== ⍺ 3))) . -// '+ . -// '+ . ° (λ(x ⍺) . ⊖ ⍺ x) '(1 0 -1) . maplist (λ(x) . ⌽ ⍵ x) '(1 0 -1))
; ou avec les parenthèses:
(
(λ(⍺)
(|
(& (== ⍺ 4) ⍵)
(== ⍺ 3)
)
)
(-// '+ (-// '+
(° (λ(x ⍺) (⊖ ⍺ x))
'(1 0 -1)
(maplist (λ(x) (⌽ ⍵ x)) '(1 0 -1))
)
))
)
L'opérateur == effectue un balayage complet de la matrice pour détecter la présence des 3 ou des 4.
Remarquons que l'on crée une lambda qui s'applique à l'expression précédente, de façon à partager la variable ⍺ pour effectuer la recherche des 3 et des 4.
Le calcul pour les 4 impose une intersection avec les valeurs de la matrice initiale: (& (== ⍺ 4) ⍵), il suffit ensuite de faire l'union.
On obtient alors:
; Etape suivante
(0 0 0 0 0)
(0 0 0 1 0)
(0 0 1 1 0)
(0 0 1 0 0)
(0 0 0 0 0)
Conclusion
Le jeu de la vie de Conway, implanté en une seule ligne de code en APL, a suscité beaucoup d'intérêt. Le code utilise des opérations mathématiques pour manipuler des matrices et mettre en œuvre les règles du jeu. APL est un langage de tableau, où les opérations se font sur des vecteurs et des matrices, ce qui permet une concision et une efficacité étonnantes.
Grâce à l'opérateur de composition de LispE, nous avons pu révéler les mécanismes cachés derrière cette ligne de code APL complexe. En utilisant des opérations comme la rotation des lignes et des colonnes, la réduction des colonnes et des lignes et l'application de règles spécifiques, nous avons pu comprendre étape par étape le fonctionnement de cette implémentation du jeu de la vie.
LispE est un langage de programmation basé sur Lisp qui utilise des tableaux plutôt que des listes chaînées. Même s'il n'atteint pas la concision d'APL, LispE offre suffisamment de fonctionnalités pour traduire et comprendre des codes APL complexes.
En conclusion, l'implémentation en une seule ligne de code en APL du jeu de la vie de Conway est un exemple frappant de la puissance des langages de tableau. Bien que sa concision soit difficile à égaler dans d'autres langages, la traduction et l'analyse pas à pas dans un langage comme LispE permettent de démystifier cette ligne de code complexe et de comprendre les opérations mathématiques sous-jacentes.