6.20 Le jeu de la vie de Conway en LispE

Parenthèses

English Version

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 laisse 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 ses 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 l'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.

(cons . car 'a 'b) ; pour le compilateur (car 'a 'b) est une expression complète

Le programme APL expliqué

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 l'a transforme en une liste de sous-ensemble, il est monadique. L'opérateur ¨, applique alors l'opérateur ⌽ à chacun des éléments de ce sous-ensemble. ⌽ effectue alors 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 initialise ⍵ avec une matrice de 1 et de 0
(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))

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 voisin 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 disposer de la grille initiale.

On va ensuite appliquer à chacune des 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))

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:

(// '+ . -// '+ . outer (λ(x ⍺) . rotate ⍺ x true) '(1 0 -1)  . maplist (λ(x) . rotate ⍵ 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

1 ⍵ ∨.∧ 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 une nouvelle matrice où lorsque la valeur est présente, on met un 1 et un 0 sinon.

On obtient alors deux matrices, chacune avec des 1 là où l'on trouve un trois ou un quatre.

Pour répondre à la contrainte pour les cellules de valeur ', on fait une intersection avec la matrice d'origine, puis on effectue une union avec la matrice des 3.

En LispE, cela donne:

((λ(δ) (| (& (== δ 4) ⍵) . == δ 3)) . // '+ . // '+ . outer (λ(x ⍺) . ⌽ ⍺ x true) '(1 0 -1) . ↑(λ(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

En conclusion, l'opérateur de composition . en LispE offre une manière concise et lisible de combiner plusieurs appels de fonctions en une seule expression intégrée. Il permet de simplifier la syntaxe et de rendre le code plus élégant. De plus, cet opérateur permet également la composition de fonctions de haut niveau, ce qui peut améliorer la performance et la lisibilité du code. Bien qu'il puisse sembler éloigné de la tradition Lisp avec ses parenthèses, il apporte des avantages significatifs en termes de concision et de lisibilité.