Le L-système et la Tortue

L-système

Les L-systèmes sont un formalisme introduit en 1968 par le biologiste Aristid Lindenmayer pour décrire la croissance des plantes. Ce formalisme décrit une grammaire permettant de dériver un mot à partir d’un mot de départ ou axiome et des règles de réécriture ou dérivation. Les L-systèmes que nous définissons ci-dessous sont les L-systèmes libres (ou hors contexte) et déterministes.

Définition

Un L-système est la donnée :

  1. d’un alphabet fini A = {a1, a2, …, an} de symboles ;
  2. de règles de dérivation

    r : A A*
    a u
    A* désigne l’ensemble des mots sur l’alphabet A ;
  3. d’un axiome u0 ∈ A*.

Exemple

Voici le L-système permettant d’obtenir (en partie) le flocon de Koch.

  1. l’alphabet A = {F, +, − } ;
  2. l’axiome u0 = F ;
  3. les règles de dérivation :

    F F − F +  + F − F
    + +

Dérivation d’un mot

Étant donné un L-système, il est possible de construire une suite (un)n ∈  de mots à partir de l’axiome et des règles de dérivation :

  1. Le mot initial est l’axiome u0.
  2. On calcule le mot un + 1 à partir du mot un en remplaçant chacune des lettres x de un par son image r(x) donnée par les règles de dérivation.

Exemple

Avec l’exemple du L-système présenté ci-dessus, voici les premiers mots obtenus :

n un
0 F
1 F − F +  + F − F
2 F − F +  + F − F − F − F +  + F − F +  + F − F +  + F − F − F − F +  + F − F

le mot u2 est de longueur 36 et le mot suivant, u3, est de longueur 148.

Implémentation

Nous allons implémenter les L-systèmes. Pour cela commençons en indiquant au typeur de quoi nous allons parler. Nous utiliserons simplement des Char comme symboles (et donc des listes de Char, c’est-à-dire des chaînes de caractères, pour les mots). Pour les règles, nous utiliserons directement une fonction associant à un symbole un mot. Enfin, un L-système complet sera la liste (infinie) des mots.

type Symbole  = Char
type Mot      = [Symbole]
type Axiome   = Mot
type Regles   = Symbole -> Mot
type LSysteme = [Mot]
  1. Définissez la fonction motSuivant :: Regles -> Mot -> Mot qui prend en argument les règles d’un L-système et un mot un et calcule le mot un + 1.

    Cette fonction peut être écrite en utilisant :
    • la récursivité,
    • une fonction bien choisie du Prelude,
    • ou une liste en compréhension.

    Vous proposerez les 3 versions (motSuivant, motSuivant', et motSuivant''). Une seule version est vraiment indispensable pour poursuivre le TP, ne bloquez pas trop longtemps sur les deux autres pendant la séance de TP encadré si vous ne voyez pas.

    Indices :
    • pour la deuxième version, l’outil Hoogle (par exemple son instance en ligne) est d’une précieuse aide ;
    • pour la troisième, si vous ne voyez pas, vous pourrez relire le premier chapitre du LYAH.
  2. Pour vérifier vos fonctions, vous définirez la règle pour le L-système du flocon de von Koch et vous vérifierez que vous obtenez des mots de la bonne longueur pour les premiers mots du L-système.

  3. Définissez une fonction lsysteme :: Axiome -> Regles -> LSysteme qui calcule le L-système défini par l’axiome et les règles données.

Tortue

Les mots d’un L-système peuvent être interprétés en dessins en associant à chaque symbole un ordre pour la tortue.

La tortue graphique est un automate de dessin dont l’état est caractérisé par sa position courante et le cap vers lequel elle est prête à se diriger. Nous définirons donc le synonyme de type suivant :

type EtatTortue = (Point, Float)

Point est le type défini par Gloss pour un point et le second élément de la paire est le cap, c’est-à-dire un angle par rapport à l’axe des abscisses exprimé en radians.

La tortue pourra initialement comprendre trois ordres :

Nous définirons le synonyme de type suivant :

type Config = (EtatTortue -- État initial de la tortue
              ,Float      -- Longueur initiale d’un pas
              ,Float      -- Facteur d’échelle
              ,Float      -- Angle pour les rotations de la tortue
              ,[Symbole]) -- Liste des symboles compris par la tortue

pour décrire une configuration de la tortue.

  1. Définissez les fonctions suivantes :
    • etatInitial :: Config -> EtatTortue,
    • longueurPas :: Config -> Float,
    • facteurEchelle :: Config -> Float,
    • angle :: Config -> Float,
    • symbolesTortue :: Config -> [Symbole].

    Ces fonctions se contentent d’extraire l’information du quintuplet.

  2. Définissez la fonction avance :: Config -> EtatTortue -> EtatTortue calculant l’état de la tortue après avoir avancé d’un pas.

  3. Définissez les fonctions tourneAGauche :: Config -> EtatTortue -> EtatTortue et tourneADroite :: Config -> EtatTortue -> EtatTortue.

  4. Définissez la fonction filtreSymbolesTortue :: Config -> Mot -> Mot qui supprime tous les symboles qui ne sont pas des ordres pour la tortue dans le mot passé en argument.

Nous allons réutiliser la bibliothèque de fonctions Gloss. Gloss fournit la fonction line :: Path -> Picture pour créer un dessin composé d’une ligne passant par tous les points du chemin (rappelons que Path est défini par : type Path = [Point]).

Les dessins que la tortue peut faire avec les ordres décrits précédemment sont simplement des lignes composées de tous les traits correspondant aux pas. Le résultat d’une suite d’ordres sera donc une liste de tous les Points par lesquels la tortue est passée.

Nous définirons donc :

type EtatDessin = (EtatTortue, Path)

pour la paire contenant, à un instant donné, l’état de la tortue et le chemin qu’elle a parcouru jusqu’à maintenant.

  1. Définissez une fonction interpreteSymbole :: Config -> EtatDessin -> Symbole -> EtatDessin qui calcule le nouvel état atteint par l’exécution de l’ordre correspondant au symbole donné en partant de l’état donné.

  2. Dans la fonction interpreteSymbole, avez-vous ajouté en tête ou en queue le nouveau point dans le chemin ? Cela a-t-il une conséquence d’un point de vue complexité (quand la taille du chemin est importante) ?

  3. Définissez une fonction interpreteMot :: Config -> Mot -> Picture.

    Indice : Pour la construire pas à pas, vous pourrez définir une fonction intermédiaire de type EtatDessin -> Mot -> EtatDessin puis exploiter le résultat final de cette fonction pour faire une Picture. Il y a plusieurs façons d’écrire cette fonction intermédiaire (comme presque toujours, bien sûr). Il y a notamment une version assez naturelle utilisant un fold, mais il est difficile de l’écrire ainsi du premier coup : je vous conseille de la définir récursivement puis de voir si vous y reconnaissez le schéma d’un fold (r ou l ?).

Pour rendre le dessin correspondant à un mot, vous pourrez utiliser le code suivant :

import Graphics.Gloss

dessin = interpreteMot (((-150,0),0),100,1,pi/3,"F+-") "F+F--F+F"

main = display (InWindow "L-système" (1000, 1000) (0, 0)) white dessin

qui devrait alors vous afficher :

Flocon de von Koch, au tout début
Flocon de von Koch, au tout début

Comme lors du TP précédent, le code peut être exécuté en compilant le fichier .hs en un exécutable. Il existe une autre solution, plus rapide (la compilation est relativement longue) : utiliser runghc. Malheureusement, il existe une petite incompatibilité entre runghc et GLUT au M5, qu’il est possible de contourner grâce à la variable d’environnement LD_PRELOAD. Vous pourrez ainsi exécuter dans votre shell :

$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libglut.so runghc exemple.hs

pour déclencher le programme exemple.hs quand il utilise Gloss.

Afin de pouvoir visualiser la construction progressive de l’image au fur et à mesure des itérations du L-système, nous allons utiliser la fonction animate de Gloss qui prend comme dernier argument, au lieu d’une image de type Picture, une fonction de type Float -> Picture. Cette fonction crée l’image correspondant à l’instant qu’elle reçoit en argument. Comme pour la courbe du dragon, vous transformerez cet instant en un indice dans la liste du L-système, en prenant le enieme élément de la liste avec

enieme = round instant `mod` 8

Attention : comme l’indique cet extrait, vous utiliserez un modulo pour éviter d’afficher une courbe trop avancée dans votre L-système. En effet Gloss est rapidement très gourmand en ressources (notamment mémoire) pour des figures trop compliquées.

  1. Définissez une fonction lsystemeAnime :: LSysteme -> Config -> Float -> Picture, prenant en argument un L-système, une configuration et un instant et calcule l’image correspondant.

    Le facteur d’échelle donné par la configuration indique comment la longueur d’un pas de la tortue est modifiée d’une itération à la suivante : par exemple, si la longueur de pas initiale est de 800 et le facteur d’échelle de 1/2, lsystem !! 0 sera dessiné avec un pas de longueur 800, mais lsystem !! 1 sera dessiné avec un pas de longueur 400.

Exemples

Vous pourrez ainsi visualiser les courbes suivantes, notamment la courbe du dragon construite par L-système. N’oubliez pas que Gloss vous permet de vous déplacer, de zoomer et dézoomer, etc.

vonKoch1 :: LSysteme
vonKoch1 = lsysteme "F" regles
    where regles 'F' = "F-F++F-F"
          regles  s  = [s]

vonKoch2 :: LSysteme
vonKoch2 = lsysteme "F++F++F++" regles
    where regles 'F' = "F-F++F-F"
          regles  s  = [s]

hilbert :: LSysteme
hilbert = lsysteme "X" regles
    where regles 'X' = "+YF-XFX-FY+"
          regles 'Y' = "-XF+YFY+FX-"
          regles  s  = [s]

dragon :: LSysteme
dragon = lsysteme "FX" regles
    where regles 'X' = "X+YF+"
          regles 'Y' = "-FX-Y"
          regles  s  = [s]

vonKoch1Anime :: Float -> Picture
vonKoch1Anime = lsystemeAnime vonKoch1 (((-400, 0), 0), 800, 1/3, pi/3, "F+-")

vonKoch2Anime :: Float -> Picture
vonKoch2Anime = lsystemeAnime vonKoch2 (((-400, -250), 0), 800, 1/3, pi/3, "F+-")

hilbertAnime :: Float -> Picture
hilbertAnime = lsystemeAnime hilbert (((-400, -400), 0), 800, 1/2, pi/2, "F+-")

dragonAnime :: Float -> Picture
dragonAnime = lsystemeAnime dragon (((0, 0), 0), 50, 1, pi/2, "F+-")

Tortue volante

Nous allons enrichir les capacités de la tortue pour pouvoir dessiner des plantes (ce qui était le but des L-systèmes), par exemple :

Une brindille
Une brindille

Pour cela, il faut que notre tortue puisse « voler » : nous allons enregistrer certaines positions dans le tracé et lui permettre de revenir à une position enregistrée. Plus précisément, les mots que nous allons interpréter pourront contenir deux nouveaux ordres, [ et ], signifiant :

Concrètement, le nouvel EtatDessin contiendra une pile (codée par une liste) d’EtatTortue, avec l’état courant tout en haut de la pile.

Puisque la tortue va désormais pouvoir « voler » vers une position précédente, c’est-à-dire commencer un tracé ailleurs, l’EtatDessin ne contiendra pas seulement un Path, mais une liste de Path. De sorte que vous changerez la définition ainsi :

type EtatDessin = ([EtatTortue], [Path])
  1. Faites le changement de EtatDessin. Constatez que le compilateur vous insulte copieusement.

Haskell est fortement typé statiquement : vous pouvez profiter du compilateur pour savoir tous les endroits de votre code que vous devez réusiner ! (Au passage, pour que les insultes de GHC soient bien localisées, il est très important d’avoir explicitement donné les signatures de toutes vos fonctions.)

  1. Réusinez votre code pour l’adapter au nouvel EtatDessin. Vous vérifierez que votre code fonctionne avec les exemples précédents.

Exemples botanistes

brindille :: LSysteme
brindille = lsysteme "F" regles
    where regles 'F' = "F[-F]F[+F]F"
          regles  s  = [s]

broussaille :: LSysteme
broussaille = lsysteme "F" regles
    where regles 'F' = "FF-[-F+F+F]+[+F-F-F]"
          regles  s  = [s]

brindilleAnime :: Float -> Picture
brindilleAnime = lsystemeAnime brindille (((0, -400), pi/2), 800, 1/3, 25*pi/180, "F+-[]")

broussailleAnime :: Float -> Picture
broussailleAnime = lsystemeAnime broussaille (((0, -400), pi/2), 500, 2/5, 25*pi/180, "F+-[]")

LYAH

  1. Lisez Récursivité du LYAH (ou la VO anglaise) et expérimentez les exemples.