← torna

El Joc de la Vida en APL

En l'article sobre llenguatges de programació parlo una mica sobre l'APL, un llenguatge orientat a vectors. M'agradaria explorar una mica més les possibilitats d'aquesta eina, a partir d'un exemple clàssic: el joc de la vida de Conway.

L'APL permet reduir aquest autòmat a una única línia de codi:

      life ← {⊃ ∨/ 1 ⍵ ∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂⍵}

El Joc de la Vida

El joc de la vida de Conway és un autòmat cel·lular. Això significa que és una espècie de joc sense jugadors: a partir d'una configuració inicial, el joc va evolucionant sol, automàticament, segons unes regles senzilles. En el procés, es van creant patrons orgànics.

Va ser dissenyat pel matemàtic britànic John Horton Conway el 1970. El joc consisteix en una graella infinita de cèl·lules. Cada cèl·lula pot ser viva o morta. A cada generació, les cèl·lules neixen, sobreviuen o moren segons quatre regles:

Una cèl·lula viva amb una o cap veïna, mor en solitud.
Una cèl·lula viva amb quatre o més veïnes, mor estressada.
Una cèl·lula viva amb dues o tres veïnes, sobreviu feliç.
Una cèl·lula morta amb tres veïnes, ressuscita.

Això pot semblar un no res, però aquest sistema és Turing complet, és a dir, pot computar qualsevol computació. De fet, podem emular un joc de la vida dins del mateix joc de la vida!

El codi en APL

      life ← {⊃ ∨/ 1 ⍵ ∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂⍵}

Tot el que està {entre claus} és la funció que estem definint. La fletxa (←) l'assigna a la variable life.

Per començar, generem una graella de 5x5 cèl·lules. Fem servir la funció de forma (⍴, la lletra grega ro), que pren un vector a la dreta i li aplica les dimensions que indiquem a l'esquerra.

      x ← 5 5 ⍴ 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0
      x
0 0 0 0 0
0 1 1 1 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0

Un 1 representa una cèl·lula viva, i un 0 una de morta. El patró que fem servir es coneix com a lliscant, perquè a mesura que avancem les generacions, es va movent (lliscant) en diagonal.

A continuació, apliquem la funció de rotació (⌽), amb un 1 com a paràmetre. Això desplaça tota la graella una cèl·lula cap a l'esquerra, passant la columna que sobra de l'esquerra a la dreta.

Provem-ho amb un 2 i un 3:

La gràcia dels llenguatges orientats a vectors és que podem anar més enllà, i donar un vector com a paràmetre per generar les diferents combinacions. Ho fem amb la funció de producte exterior (∘.). (nota: APL fa servir una barra alta (¯) per a indicar un nombre negatiu, per tant, ¯1 és -1). El -1 ho desplaça tot cap a la dreta, l'1 ho desplaça tot cap a l'esquerra, i el 0 no fa res.

      ¯1 0 1 ∘.⌽ ⊂x
┌─────────┬─────────┬─────────┐
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 1 1 1│0 1 1 1 0│1 1 1 0 0│
│0 0 1 0 0│0 1 0 0 0│1 0 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┴─────────┘

I ho fem de nou amb la funció de rotació horitzontal (⊖).

      ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂x
┌─────────┬─────────┬─────────┐
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 1 1 1│0 1 1 1 0│1 1 1 0 0│
│0 0 1 0 0│0 1 0 0 0│1 0 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
├─────────┼─────────┼─────────┤
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 1 1 1│0 1 1 1 0│1 1 1 0 0│
│0 0 1 0 0│0 1 0 0 0│1 0 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
├─────────┼─────────┼─────────┤
│0 0 1 1 1│0 1 1 1 0│1 1 1 0 0│
│0 0 1 0 0│0 1 0 0 0│1 0 0 0 0│
│0 0 0 1 0│0 0 1 0 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┴─────────┘

Ara, sumem les nou matrius que hem generat. Ho fem de manera similar a com ho hem fet al primer exemple. Apliquem la funció de suma (+), tant verticalment (/) com horitzontalment (⌿).

      +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂x
┌─────────┐
│1 2 3 2 1│
│2 3 4 2 1│
│2 4 5 3 1│
│1 2 2 1 0│
│0 1 1 1 0│
└─────────┘

La matriu resultant representa el total de cèl·lules vives veïnes (+ ella mateixa si també és viva). Una cèl·lula serà viva en la següent generació si:

ja és viva, i té dues veïnes vives, o bé,
viva o no, té tres veïnes vives.

Així doncs, en la matriu resultant, les cèl·lules amb un 3 ens indiquen que:

la cèl·lula era viva i tenia dues veïnes vives, o bé,
la cèl·lula era morta però tenia tres veïnes vives.

En qualsevol dels dos casos el resultat és una cèl·lula viva en la següent generació.

Per altra banda, si tenim un 4, ens indica que:

la cèl·lula era viva i tenia tres veïnes vives, o bé,
la cèl·lula era morta però tenia quatre veïnes vives.

Només en el primer cas la cèl·lula serà viva en la següent generació.

Per implementar aquesta lògica, fem servir primer la funció d'igualtat (=) amb 3 i 4 com a paràmetres.

      3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂x
┌─────────┬─────────┐
│0 0 1 0 0│0 0 0 0 0│
│0 1 0 0 0│0 0 1 0 0│
│0 0 0 1 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┘

Fem servir la funció lògica i (and, ∧) per assegurar-nos que sobreviuen les cèl·lules amb un 4 i que ja eren vives. Les cèl·lules amb un 3 viuran sense importar si ja eren vives o no, per això posem un 1. (1 i 0 = 0; 1 i 1 = 1; així només té efecte la nova matriu)

      1 x ∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂x
┌─────────┬─────────┐
│0 0 1 0 0│0 0 0 0 0│
│0 1 0 0 0│0 0 1 0 0│
│0 0 0 1 0│0 1 0 0 0│
│0 0 0 0 0│0 0 0 0 0│
│0 0 0 0 0│0 0 0 0 0│
└─────────┴─────────┘

Combinem les dues matrius aplicant la funció lògica o (or, ∨).

      ∨/ 1 x ∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂x
┌─────────┐
│0 0 1 0 0│
│0 1 1 0 0│
│0 1 0 1 0│
│0 0 0 0 0│
│0 0 0 0 0│
└─────────┘

Finalment, ho col·loquem tot entre claus {així ho definim com a funció} i reemplacem l'x per l'omega (⍵), que representa l'argument de la funció. Cada cop que cridem aquesta funció avancem una generació. També hi afegim la funció show per visualitzar-ho tot millor. Podem veure com el patró lliscant es desplaça una cèl·lula al nord-oest. És viu!

      x    ← 5 5 ⍴ 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 0
      life ← {⊃ ∨/ 1 ⍵ ∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ∘.⌽ ⊂⍵}
      show ← {'.#'[⎕IO + ⍵]}
      x
0 0 0 0 0
0 1 1 1 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
      show x
.....
.###.
.#...
..#..
.....
      show life x
..#..
.##..
.#.#.
.....
.....
      show life life x
.##..
.#.#.
.#...
.....
.....
      show life life life x
.##..
##...
..#..
.....
.....
      show life life life life x
###..
#....
.#...
.....
.....