Tutorial LISP

E acea vreme a anului când am chef de a face tutoriale. Cum colegii mei înjură cel mai mult PLF, voi face un tutorial cu care să îi ajut la această materie: tutorial de LISP.

Cum nu am chef să rezolv mai multe probleme simpluțe de pe siteul profei, voi face una singură, dar mai complexă: voi implementa Conway's Game of Life, fără UI desigur, că de-aia nu îs masochist.

Ce este Conway's Game of Life? Citiți pe Wikipedia.

Începem prin a ne defini trei funcții ajutătoare:

(defun multime(l)     (cond         ((null l) nil)         ((not (in (cdr l) (car l))) (cons (car l) (multime (cdr l))))         (t (multime (cdr l)))     ) )

(defun keep_true(l)     (cond         ((null l) nil)         ((not (null (car l))) (cons (car l) (keep_true(cdr l))))         (t (keep_true(cdr l)))     ) )

(defun in(l el)
(cond
((null l) nil)
((equal (car l) el) t)
(t (in (cdr l) el))
)
)

(defun add_coords(change cell)
(list (+ (car change) (car cell)) (+ (cadr change) (cadr cell)))
)

Prima transformă o listă dată într-o mulțime (în ordine inversă, dar pe noi nu ne prea in­tere­sează asta). A doua păstrează doar elementele cu valoare diferită de „nil” din listă, a treia este o simplă verificare a aparte­nenței unui element la o listă. Nu putem folosi funcția built-in member pentru că aceasta lucrează cu eql pentru comparare și aceasta nu returnează true pentru perechile noastre de coordonate. Ultima funcție este „de­plasarea„ unui punct într-o direcție, adică adăugăm la coordonata x un dx și la coordonata y un dy (și la coordonata Skyfall ne uităm afiș că ce nume tâmpit o avut filmul).

Prima funcție este de a obține starea următoare a unei celule, știind starea ei curentă și numărul de vecini. Asta nu e mare brânză și nici măcar nu folosim chestii specifice pro­gramării funcționale, pur și simplu 3 if-uri.

(defun next_state(current_state nr_neighbors)     (if (null current_state)         (if (= nr_neighbors 3) t nil)         (if (or (< nr_neighbors 2) (> nr_neighbors 3)) nil  t)     ) )

Next up: verificăm dacă două celule sunt vecine. Facem aceasta verificând că diferența dintre co­or­do­natele lor pe x și pe y sunt mai mici sau egale cu 1 și că cele două celule nu sunt identice. Again, no functional pro­gram­ming.

(defun are_neighbors(cell1 cell2)     (and (and (<= (abs  (- (car cell1) (car cell2))) 1)               (<= (abs  (- (cadr cell1) (cadr cell2))) 1)           ) (not (equal cell1 cell2))     ) )

Urmează să obținem numărul de vecini vii la momentul curent pe care îi are o celulă. În primul rând cu mapcar verificăm dacă celula dată este vecină cu o celulă din lista de celule vii și returnăm 1, altfel returnăm 0. În final, însumăm lista obținută.

(defun nr_alive(l cell)     (apply '+ (mapcar (lambda (c) (if (are_neighbors cell c) 1 0)) l)) )

Știm numărul de celule vii? E timpul să știm celule moarte. Aici vom parcurge toate celulele din jurul celulei date și verificăm dacă nu este în lista de celule vii. Celulele din jur le obținem adunând la celula curentă pe rând o serie de direcții (1 0), (0 1) etc. Cu mapcar \:D/ Cum mapcar returnează o valoare pentru toate celule, inclusiv pentru cele vii din vecini, pentru acestea returnăm nil și apoi filtrăm și păstrăm doar valorile non-nil (cu funcția keep_true definită mai sus)

(defun dead_neighbors(l cell)     (keep_true (mapcar (lambda (c) (if (not (in l (add_coords c cell))) (add_coords c cell) )) '((1 1) (1 0) (1 -1) (0 1) (0 -1) (-1 1) (-1 0) (-1 -1)))) )

Penultima funcție ne returnează funcțiile care vor rămâne vii la următoare iterație. Again cu mapcare iterăm peste ele și folosim funcția next_state și în final filtrăm rezul­tatele cu keep_true.

(defun surviving_cells(cells)     (keep_true (mapcar (lambda (cell) (if (next_state t (nr_alive cells cell)) cell)) cells))
)

Ultime funcție reprezintă iterația de joc în sine. Înviem celule moarte pentru iterația următoare și le concatenăm cu lista de celule care rămân vii tura următoare. Celulele moarte care învie le aflăm fix ca în funcția precedentă, doar că în funcția next_state dăm nil ca primul parametru.

(defun tick(cells)     (append         (keep_true             (mapcar (lambda (c)                         (if (next_state nil (nr_alive cells c)) c))                     (multime                         (mapcan                             (lambda (cell)                                 (dead_neighbors cells cell))                             cells))))         (surviving_cells cells)     ) )

And voila. That's Conway's Game of Life for you. Mai lipsește doar un UI drăguț și un game loop and you can be mesmerized by the evolving patterns. Dar să faceți și voi ceva. Spor la LISP-uit.