spyked bricks in the wall

să scriem împreună un simulator de automate celulare (iii)

Am pus până acum bazele unui simulator de automate celulare și apoi am ajuns la o implementare funcțională conform unor specificații. Pe scurt, am obținut o mașinărie capabilă de a primi la intrare un șir de celule „goale” sau „umplute” (fiecare), prelucrându-l inductiv și obținând la fiecare pas de inducție un alt șir de celule cu aceleași proprietăți. Zisa mașinărie nu prelucrează celulele arbitrar, ci pe baza unui set de reguli care iau în calcul valoarea celulei și a vecinilor direcți, stabiliți după ordinea din șir. Putem privi șirul de șiruri rezultat fie ca pe o secvență de evenimente, fie ca pe un „covor” care are pe prima linie primul șir de celule, pe a doua șirul următor și așa mai departe.

Uneltele folosite până acum ne-au permis să vizualizăm datele doar în cel de-al doilea mod. Exemplele relevă astfel șabloane fractale precum cel al triunghiului Sierpinski, imagini regulate sau care se autoreglează „în jos”, sau dimpotrivă, reprezentări profund neregulate [i] care aduc a „randomness”. Acest al doilea mod de vizualizare oferă deci o privire sintetică asupra evoluției unui automat celular elementar oarecare.

Putem însă la fel de bine să folosim Haskell și unele din bibliotecile grafice avute la dispoziție pentru a vizualiza rezultatele în primul mod. Având la dispoziție o listă de stări, deci o listă de liste de celule, putem afișa o stare sub forma unui cadru într-o animație, extinzând astfel evoluția pe axa timpului. Propun astfel ca o celulă să fie afișată sub forma unui „petic” de 20 x 20 pixeli dintr-o imagine, după cum urmează: o celulă având valoarea E va fi reprezentată printr-un pătrat alb, în timp ce o celulă F va avea asociat un pătrat umplut cu negru. „Peticele” care formează o stare vor fi concatenate de la stânga la dreapta într-o imagine/cadru cu înălțimea 20 și lățimea 20 x lungimea șirului.

Aceste considerente fiind stabilite, să definim latura pătratului ca fiind variabila rs și să importăm câteva module Haskell ce se vor dovedi a fi utile:

import Text.Printf
import Graphics.Rendering.Cairo
import Cell1D
 
rs :: Double
rs = 20

Modulul Cell1D cuprinde implementarea simulatorului din articolele anterioare. Text.Printf face parte din biblioteca standard Haskell și ne va ajuta un pic mai încolo. În fine, modulul Graphics.Rendering.Cairo, peste al cărui API vă recomand să vă uitați înainte de a continua, se va ocupa cu desenul propriu-zis și cu aruncarea acestuia într-un fișier. Imaginea noastră e o hartă bidimensională de pixeli grupați în pătrate rs x rs, pixelul 0 x 0 al imaginii aflându-se în colțul din stânga-sus. Primul pătrat va începe astfel la 0 x 0, al doilea la rs x 0, al treilea la (2 * rs) x 0 și așa mai departe. Pentru a desena o celulă sub forma unui pătrat va trebui să ținem deci cont de indexul acesteia în cadrul șirului și de starea ei (E sau F).

Fiind astfel înarmați cu toată informația necesară desenării unei celule, vom implementa funcția drawCell, care apelează rectangle și fill pentru a scrie într-un buffer oarecare dat de monada Render din bibliotecă:

drawCell :: Int -> Cell -> Render ()
drawCell n c = do
    let n' = fromIntegral n
        (r,g,b) = if c == F then (0,0,0) else (1,1,1)
 
    setSourceRGB r g b
    rectangle (n' * rs) 0 rs rs
    fill

Observăm apelul funcției setSourceRGB, care are ca efect lateral setarea culorii la (0,0,0) sau (1,1,1) în funcție de valoarea celulei. Putem eventual să procedăm într-un mod similar pentru a colora în alb toată suprafața inițială a imaginii:

drawBackground :: Int -> Render ()
drawBackground num = do
    setSourceRGB 1 1 1
    rectangle 0 0 (cnum * rs) rs
    fill
    where
    cnum = fromIntegral num

Ați observat probabil o funcție un pic dubioasă, fromIntegral. Rolul ei e acela de a face cast de la un tip așa-zis „întreg” (în cazul acesta) către Double, care e folosit de Cairo pentru desenat. Pentru cast-ul invers vom folosi floor, care rotunjește în jos din tipuri reale în tipuri întregi.

Având la dispoziție o listă de celule, o putem desena astfel: generăm întâi o listă de indecși [0..length cs - 1] din lista de celule cs, după care „lipim” cele două liste folosind zip și dăm rezultatul ca argument către drawCell. Problemele sunt două la număr: unu, trebuie să mapăm cumva funcția pe lista nou-rezultată de perechi index-celulă și doi, trebuie să aducem drawCell într-o formă în care să poată primi ca unic argument o pereche index-celulă în loc de două argumente.

Ambele probleme pot fi rezolvate în Haskell în mod idiomatic. Cea dintâi prin aplicarea unui „map”, însă nu orice fel de map: dat fiind că suntem în cadrul monadei Render și vrem să întoarcem un rezultat de tip () (adică un fel de void al Haskell-ului), vom folosi mapM_, deci un apel posibil ar putea fi:

mapM_ drawCell cns

Apelul nu va trece însă de sinteza de tip, din cauza celei de-a doua probleme. Funcțiile Haskell sunt implicit în formă Curry, ceea ce înseamnă că aplicarea unui argument unei funcții cu n argumente duce la generarea unei alte funcții care primește n - 1 argumente și așa mai departe. drawCell primește două argumente, unul de tip Int și încă unul de tip Cell, ori noi vrem să putem primi un singur argument de tipul (Int, Cell). Din fericire funcția uncurry știe deja să facă asta, deci codul va arăta astfel:

drawLat :: [Cell] -> Render ()
drawLat cs = do
    drawBackground $ length cs
    let cns = zip [0..length cs - 1] cs
 
    mapM_ (uncurry drawCell) cns

Felul în care sunt trimise argumentele poate părea o idee greu de digerat. Nu-i bai, reveniți la tutorial, luați o foaie și un pix și studiați exemplul mai pe îndelete. Eventual puteți implementa o variantă proprie de uncurry pentru a vă lămuri că în spate nu se petrec chestii voodoo [ii].

Generarea propriu-zisă a unei imagini e un pic mai dubioasă. Biblioteca Cairo ne impune în primul rând sa desenăm pe un obiect de tip Surface, care-i o abstractizare a imaginii propriu-zisă. Vom face asta cu ajutorul funcției withImageSurface. Vom folosi renderWith pentru a desena pe „suprafață” și apoi o vom transforma într-un format de fișier convenabil, png să zicem.

cellsToFile :: FilePath -> [Cell] -> IO ()
cellsToFile path cells = withImageSurface FormatRGB24 pnw pnh df
    where
    pnw = length cells * floor rs
    pnh = floor rs
    df srf = do
        renderWith srf $ drawLat cells
        surfaceWriteToPNG srf path

Observăm că withImageSurface are nevoie de argumente întregi, deci am folosit floor pentru a face cast la rs în Int.

Momentan să presupunem că nu dorim să generăm animația finală, ci doar o secvență de fișiere png de forma „prefix000.png”, „prefix001.png” și așa mai departe. Vom formata numerele sub forma „prefixabc.png” folosind printf, care e foarte similar cu printf-ul din C. Funcția printf va fi mapată pe un șir de numere [0..n - 1] generat în mod similar cu cel de mai sus.

genPaths :: String -> Int -> [FilePath]
genPaths prefix n = map (printf "%s%.03d.png" prefix) [0..n-1]

În fine, acum putem abstractiza la nivelul șirurilor de stări. Folosim același idiom ca mai devreme pentru a apela cellsToFile, în cadrul funcției latsToFiles:

latsToFiles :: String -> [[Cell]] -> IO ()
latsToFiles prefix lats = mapM_ (uncurry cellsToFile) $ zip paths lats
    where
    paths = genPaths prefix $ length lats

Să definim și o funcție main, care ia exampleLat3 din articolul anterior și întoarce evoluția după cinci sute de iterații a regulii 184:

main = do
    lat0 <- exampleLat3
    let result = take 500 $ runCell1D rule184 lat0
    latsToFiles "myDraw" result

Compilând și rulând exemplul, vom obține cinci sute de fișiere: „myDraw000.png„, „myDraw001.png” și așa mai departe până la „myDraw499.png”. Putem transforma în linie de comandă fișierele într-un singur gif animat folosind utilitarul convert din cadrul bibliotecii ImageMagick:

$ convert myDraw*.png "myDraw.gif"

„myDraw.gif” ar trebui deci să arate cam în felul următor:

În concluzie, cam așa ar arăta o implementare minimală a unui simulator de automate celulare elementare, extins cu posibilitatea de a scoate la ieșire un fișier animat. Am atașat și de această dată fișierul sursă asociat articolului, cu aceleași recomandări ca data trecută. În plus, vă propun o serie de exerciții care să vă ajute să vă faceți simulatorul mai „fancy”:

• Reimplementați animația în întregime în Haskell folosind binding-uri Haskell pentru imagemagick, trecând astfel peste necesitatea de a folosi convert. Rulați din nou toate exemplele făcute până acum și trageți niște concluzii pe baza lor.
• Extindeți funcția main astfel încât să poată parsa argumente primite în linia de comandă. Argumentele trimise programului pot fi luate cu ajutorul getArgs. Adăugați opțiuni referitoare la lungimea șirului de celule, starea inițială, numărul de pași de execuție, „numărul” automatului și așa mai departe. Eventual starea inițială ar putea fi citită dintr-un fișier text cu „x”-uri și „.”-uri, prin implementarea unei instanțe Read etc.
• Faceți posibilă afișarea în format imagine a evoluției automatului la fel ca în articolul anterior („covor” de celule). Un exercițiu interesant l-ar putea constitui renunțarea la diverse biblioteci grafice și înlocuirea cu o bibliotecă proprie care scoate fișiere de tip SVG sau alt format vectorial ușor de parsat.
• Adăugați posibilitatea generării de automate bidimensionale, în genul Game of Life. O alternativă ar fi automatele cu latici hexagonale sau automate celulare 3D. Oricare din acestea poate fi un proiect în sine; deja aici se deschid drumuri către simulări ceva mai sofisticate ale traficului în diverse domenii sau către construcții în genul elementelor din circuitele logice. Dacă vă pasionează de exemplu fizica sau chimia, sunt sigur că există studii referitoare la dinamica unor soluții sau a unor sisteme fizice (discrete sau continue) simulate folosind automate celulare. Eu n-am dubii că puteți simula cam orice cu ajutorul lor.

1. Studiul regularității automatelor celulare elementare plecând de la stări inițiale aleatoare a dus la împărțirea acestora în patru clase distincte. E demn de menționat și faptul că regularitatea de un anumit fel și interacțiunea între celule fac ca anumite automate celulare să fie echivalente computațional cu o mașină Turing. [↩]
2. Problema se poate complica și mai tare. Idiomurile de tip curry-uncurry sunt doar cazuri particulare de Arrows, care iau intrările și ieșirile funcțiilor și le compun în moduri care se repetă de la un tip de calcul la altul. În caz că vă întrebați, denumirea de „Arrow” se trage de la cea de săgeată din teoria categoriilor. [↩]