Autómatas celulares unidimensionales en Python

Estaba yo leyendo este verano un libro titulado Think Complexity cuando en un capítulo empezó a hablar de los autómatas celulares unidimensionales. El tema me interesó y por eso esta entrada. Veamos primero a qué nos referimos cuando hablamos de esto.

Cuando hablamos a autómatas celulares, nos referimos a pequeñas entidades independientes pero que interaccionan entre sí. Celulares porque son la unidad elemental del universo donde van a existir y autómatas porque deciden por ellas mismas, basadas en un conjunto de reglas predefinido, cuando el tiempo avanza de forma discreta (es decir, a pasos).

Este concepto abstracto puede visualizarse con facilidad si nos imaginamos una rejilla. Cada celda es una célula capaz de cambiar su estado según su entorno.

Los autómatas celulares fueron objeto de estudio de Stephen Wolfram, matemático conocido por haber diseñado el programa Mathemathica y Wolfram Alpha.

Los autómatas celulares unidimensionales son aquellos que forman parte de un universo unidimensional. Es decir, cada célula tiene una vecina a su izquierda y a su derecha. En los bordes se pueden definir varios comportamientos pero el concepto no varía. Pensemos en ello como una tira de celdas.

El estudio de estos autómatas es interesante, ya que pueden generarse patrones/situaciones muy complejas en base a unas reglas sencillas.

¿Cómo se definen las reglas?

Wolfram usó un sistema para definir las reglas de estos autómatas que hoy conocemos como Wolfram Code. Se basa en definir una tabla con los estados presentes de la célula y sus vecinas así como el valor que deberá adoptar en esa situación la célula. Como Wolfram usó células con solo dos estados, todo está en binario, y la parte baja de la tabla es un número de 8 bits. Este número se suele pasar a decimal y así se identifica.

Estados presentes 111 110 101 100 011 010 001 000
Estado futuro 0 0 1 1 0 0 1 0

Esta tabla representa la Regla 50, porque 00110010 en binario es 50.

¿Cómo se representan?

Una manera muy interesante de representar estos autómatas es poner cada paso en una fila distinta dentro de una imagen.

Una vez que sabemos esto vamos a hacer un programa en Python que nos permita observar la evolución de estos autómatas.

Usaremos el procedimiento original, que es empezar con todos los estados de los autómatas en 0 salvo el del autómata central, que será 1.

La clase Automata

La clase autómata va a contener las reglas, así como un ID y el estado que posee. Además, por cuestiones técnicas conviene guardar el estado anterior que tuvo.

class Automata(object):

    rules = list()

    def __init__(self,idx=0):
        self.idx = idx
        self.state = False
        self.statePrev = False

Como podéis ver, rules no lleva self, es decir, va a ser una variable compartida entre todas las instancias de Automata. Esto es porque las reglas son idénticas a todos los autómatas.

La clase World

Ahora vamos a definir el universo donde residen estos autómatas. Este universo almacena una lista con los autómatas, se encarga de actualizarlos según las normas y de dibujarlos usando PIL. También he insertado el código que codifica las normas según el número en decimal.

class World(object):
    def __init__(self,rule=50):
        self.rule = rule
        self.im = Image.new("L",(WIDTH,HEIGHT))
        self.data = np.zeros(WIDTH*HEIGHT,dtype=np.uint8)
        b = bin(rule)[2:].zfill(8)
        Automata.rules = [True if c == "1" else False for c in b]
        self.list = list()
        self.step = 0
    
    def add(self):
        automata = Automata(len(self.list))
        self.list.append(automata)

    def update(self):
        for automata in self.list:

            automata.statePrev = automata.state
            p = self.list[automata.idx - 1].statePrev if automata.idx > 0 else False
            n = self.list[automata.idx + 1].state if automata.idx < len(self.list)-1 else False
            s = automata.state

            if p and s and n:
                automata.state = automata.rules[0]
            elif p and s and not n:
                automata.state = automata.rules[1]
            elif p and not s and n:
                automata.state = automata.rules[2]
            elif p and not s and not n:
                automata.state = automata.rules[3]
            elif not p and s and n:
                automata.state = automata.rules[4]
            elif not p and s and not n:
                automata.state = automata.rules[5]
            elif not p and not s and n:
                automata.state = automata.rules[6]
            elif not p and not s and not n:
                automata.state = automata.rules[7]
            

    def draw_row(self):
        if self.step == 0:
            middle = len(self.list) // 2
            self.list[middle].state = True
        for i,automata in enumerate(self.list):
            if automata.state:
                self.data[self.step*HEIGHT+i] = 255
        self.step += 1
    def save(self):
        self.im.putdata(self.data)
        self.im.save("RULE-%d.png" % self.rule)

Con esto ya lo tenemos casi todo. Ahora faltaría poner en marcha todo. La idea es simplemente crear una instancia de World, hacer unas cuantas llamadas a add, y después ir haciendo el ciclo update/draw_row. Una vez hayamos acabado, hacemos save y obtendremos un PNG con la imagen.

Código completo

import numpy as np
from PIL import Image

WIDTH = 5001
HEIGHT = 5001

class Automata(object):

    rules = list()

    def __init__(self,idx=0):
        self.idx = idx
        self.state = False
        self.statePrev = False

class World(object):
    def __init__(self,rule=50):
        self.rule = rule
        self.im = Image.new("L",(WIDTH,HEIGHT))
        self.data = np.zeros(WIDTH*HEIGHT,dtype=np.uint8)
        b = bin(rule)[2:].zfill(8)
        Automata.rules = [True if c == "1" else False for c in b]
        print(Automata.rules)
        self.list = list()
        self.step = 0
    
    def add(self):
        automata = Automata(len(self.list))
        self.list.append(automata)

    def update(self):
        for automata in self.list:

            automata.statePrev = automata.state
            p = self.list[automata.idx - 1].statePrev if automata.idx > 0 else False
            n = self.list[automata.idx + 1].state if automata.idx < len(self.list)-1 else False
            s = automata.state

            if p and s and n:
                automata.state = automata.rules[0]
            elif p and s and not n:
                automata.state = automata.rules[1]
            elif p and not s and n:
                automata.state = automata.rules[2]
            elif p and not s and not n:
                automata.state = automata.rules[3]
            elif not p and s and n:
                automata.state = automata.rules[4]
            elif not p and s and not n:
                automata.state = automata.rules[5]
            elif not p and not s and n:
                automata.state = automata.rules[6]
            elif not p and not s and not n:
                automata.state = automata.rules[7]
            

    def draw_row(self):
        if self.step == 0:
            middle = (len(self.list) // 2)
            self.list[middle].state = True
        for i,automata in enumerate(self.list):
            if automata.state:
                self.data[self.step*HEIGHT+i] = 255
        self.step += 1
    def save(self):
        self.im.putdata(self.data)
        self.im.save("RULE-%d.png" % self.rule)
    def __str__(self):
        s = str()
        for l in self.list:
            s += "T" if l.state else "F"
        return s

def world_run(rule):
    world = World(rule)
    for _ in range(WIDTH):
        world.add()

    for _ in range(HEIGHT):
        world.draw_row()
        world.update()
    world.save()

def main():
    rule = input("Rule: ")
    try:
        rule = int(rule)
        if 255 >= rule >= 0:
            world_run(rule)
            print("Check for the generated RULE-%d.png file" % rule)
        else:
            raise ValueError
    except ValueError:
        print("Please, insert a number between 0 and 255")
        main()

if __name__ == "__main__":
    main()

Algunas reglas importantes

Regla 30

Una de las más importantes a nivel matemático. Ha sido objeto de mucho estudio, sin embargo no vamos a entrar en detalles más allá de su aspecto visual.

Vista ampliada

Regla 110

Esta regla es también muy interesante. ¡Se demostró que era Turing completa!

Vista en detalle

Regla 126

Esta regla no es tan importante, pero personalmente me parece muy bonita.

Vista ampliada

Reglas 57 y 99

Son dos reglas isomorfas. Es decir, son en realidad la misma regla pero aplicada a lados distintos. Elijo estas dos porque se aprecia muy bien el isomorfismo.

Regla 57
Regla 99

Regla 169

Vista en detalle

Regla 129

Regla 90

Es el famoso triángulo de Sierpinski.

Regla 150

Regla 105

Esta regla no tiene isomorfo.

En este artículo no he querido entrar en las complejidades matemáticas de todo esto. Es algo que todavía no entiendo así que no sería sincero por mi parte exponerlo.

Bonus: Richard Feynman y Steve Jobs

Quien me conoce sabe de sobra que uno de los personajes de la historia que más ha influido en mi vida es Richard Feynman. Debo reconocer que entré en un estado de éxtasis al descubrir que Feynman y Wolfram no solo trabajaron juntos, sino que lo hicieron alrededor de la regla 30 antes mostrada. También me sorprendió que Steve Jobs y Wolfram resultasen ser amigos de toda la vida. No dejo de sorprenderme de los contactos de ciertos personajes históricos entre sí.

Feynman a la izquierda, Wolfram a la derecha
loading...

Documentación con rustdoc

La documentación es una parte importante y muchas veces olvidada de un proyecto de software. Rust cuenta desde el principio con una herramienta destinada a que escribir documentación sea poco doloroso, se trata de rustdoc.

Comentarios en Markdown

Los comentarios de rustdoc empiezan con 3 barras y pueden llevar Markdown. Se escriben encima de la función, estructura, etc que describamos.

/// Perfil almacena los datos del perfil de un usuario en nuestra webapp
struct Perfil{
    username: String,
    password: String,
    url: Option<String>
}

impl Perfil{
    /// Genera un nuevo Perfil
    /// # Ejemplo
    /// ```
    /// let user = Perfil::new("The42","1234");
    /// ```
    pub fn new(u: &str, p: &str) -> Perfil{
        Perfil {username: String::from(u), password: String::from(p), url: None}
    }
}

Mencionar que el código del comentario es sometido a tests también por cargo test. Para generar la documentación basta con escribir cargo doc y Cargo generará la documentación en formato HTML.

Consultando documentación

El mejor sitio para leer la documentación de Rust es Docs.rs. Docs.rs ejecuta cargo doc a todas las crates de Crates.io y las expone al público sin costo.

 

Tests en Rust

Mientras los programas no puedan verificarse de forma matemática de forma sencilla, la única manera de asegurarse que un programa más o menos funciona es con tests. Rust soporta tests de forma nativa. Gracias a la directiva #[test].

Definiendo una función de test

Una función de test es cualquiera que lleve la directiva #[test]. Normalmente, estos tests se dejan dentro de un módulo con la directiva #[cfg(test)].

fn suma(a: i32,b: i32) -> i32{
    a+b
}

#[cfg(test)]
mod test{

    #[test]
    fn suma(){
        assert_eq!(super::suma(4,5),9);
    }
}

La macro assert_eq! provocará un panic! si sus argumentos no coinciden. También es posible hacer fallar los tests llamando a panic! manualmente. ¿Cómo se ejecutan estos test te preguntarás? Sencillo, con cargo test. Automáticamente Cargo selecciona las funciones de test y las ejecuta todas, generando un informe de tests existosos y tests que han fallado.

Obviamente, existen más opciones dentro de los tests. assert! comprobará que una expresión sea true. #[should_panic] se deberá indicar en aquellas funciones de test en lo que lo correcto sea que ocurra un panic!. Por otro lado, la trait Debug es interesante.

Es posible ejecutar tests de forma manual, con cargo test NOMBRE_TEST.

 

Cargo y módulos en Rust

El software va creciendo poco a poco en un proyecto y es vital que esté bien organizado. Rust incluye un potente sistema de módulos para manejar estas situaciones y Cargo nos ayuda a gestionar las dependencias del proyecto.

Módulos

Los módulos se definen con la palabra reservada mod y por defecto todo es privado. Es necesario indicar pub para hacer esos campos públicos. Con use podemos acortar la manera con la que hacemos referencia a los componentes del módulo. Así pues, use es similar a using namespace de C++.

mod network{
    pub fn version() -> String{
        String::from("Network 1.0.0")
    }
    pub mod server{
        fn private_thing(){

        }
        pub fn public_thing(){

        }
    }
}

fn main() {
    println!("{}",network::version());
    {
        use network::server::public_thing;
        public_thing();
    }
}

Los módulos resultan una opción más interesante si tenemos múltiples archivos. Por norma general, si un módulo se define en el fichero de entrada del compilador, este se busca en dos sitios:

  • Un fichero nombre_del_modulo.rs
  • Un fichero nombre_del_modulo/mod.rs (opción recomendada para módulos de varios archivos)

Por lo que el código anterior puede sustituirse por esto en el fichero principal:

mod network;

fn main() {
    println!("{}",network::version());
    {
        use network::server::public_thing;
        public_thing();
    }
}

Y esto en un fichero network.rs

pub fn version() -> String{
    String::from("Network 1.0.0")
}
pub mod server{
    fn private_thing(){

    }
    pub fn public_thing(){

    }
}

Podemos usar use-as para modificar el nombre con el que se importa una función.

mod network;

fn main() {
    println!("{}",network::version());
    {
        use network::server::public_thing as super_thing;
        super_thing();
    }
}

 

Crates

El código en Rust se organiza en crates, que son colecciones de módulos que se distribuyen. Piensa en ello como si fuesen gemas de Ruby o librerías de C++. Las crates se pueden compartir con la gente. El mayor repositorio de crates de la comunidad Rust es crates.io.

Las crates se pueden generar con rustc o con cargo, aunque es habitual usar la segunda opción. Vamos a ver primero como usaríamos una crate externa. En este caso voy a usar regex. Sé que en esta parte no vas a saber como descargar regex y usarla, pero voy a explicar el código.

extern crate regex;

use regex::Regex;

fn main() {
    let r = Regex::new(r"([A-Za-z0-9])([.]|[_]|[A-Za-z0-9])+@gmail.com").unwrap();
    if r.is_match("pucela_segunda@gmail.com") {
        println!("Correo válido de Gmail");
    }else{
        println!("Correo no válido de Gmail");
    }
}

Básicamente se usa extern crate para importar una crate externa, en este caso regex. Con use lo único que hacemos es acortar la manera de llamar a las funciones. Si no estuviese podríamos poner perfectamente regex::Regex::new en vez de Regex::new y funcionaría.

Cargo

Cargo es una herramienta que cumple dos funciones dentro del ecosistema Rust. Por un lado es un gestor de dependencias y por otro lado gestiona también las compilaciones.

En su parte de gestor de dependencias nos permite especificar que crates necesita el proyecto para compilar, su versión y si la crate lo soporta, con qué características activadas.

En su parte de gestor de compilaciones, realiza la compilación con rustc y añade las flags pertinentes al compilador. También se le pueden especificar cosas más complejas, aunque en Rust no suele ser habitual tener configuraciones de compilación excesivamente complejas.

Todo lo relativo a Cargo se define en el archivo Cargo.toml. Que tiene una estructura similar a esta:

[package]
name = "super_app"
version = "0.1.0"
authors = ["Adrián Arroyo Calle"]

[dependencies]
regex = "0.2.2"

En la sección dependencies puedes añadir línea por línea la crate que te haga falta. Consulta la documentación de cada crate para esto, pues puede haber variaciones.

Comandos básicos de Cargo

Crear un proyecto con Cargo

cargo new –bin mi_proyecto # si queremos que sea ejecutable

cargo new mi_crate # si queremos que sea una crate

Compilar y ejecutar

cargo run

cargo build # solo compilar

cargo build –release # compilar en modo Release

Cargo automáticamente se encarga de obtener las dependencias en la fase de compilación.

Instalar aplicaciones

cargo install APLICACION

Muchas herramientas de pueden distribuir a través de Cargo. Por ejemplo, Racer, un programa que sirve de autocompletado para IDEs como Eclipse o Visual Studio.

Ejecutar tests

cargo test

Generar documentación

cargo doc

Plugins de Cargo

Cargo es extensible gracias a plugins. Algunos interesantes son Clippy, cargo-audit, rustfmt,

Box, Rc y RefCell, punteros inteligentes en Rust

Hasta ahora hemos trabajado con tipos primitivos, con estructuras o con tipos de la librería estándar como String o Vec. Sin embargo, ¿si queremos implementar algo similar a String como lo haríamos? Aquí entran en juego, los punteros inteligentes, punteros con capacidades extra. Los más importantes son Box, Rc y RefCell.

Box, reservar memoria en el heap

Box es parecido a malloc de C. Reservan memoria en la parte alta de la memoria. El uso principal de Box en Rust es el de implementar estructuras de datos cíclicas o recursivas.

fn main() {
    let n = Box::new(42);
    println!("n = {}", n);
}

No es muy útil usarlo así. Solo compensa usarlo en situaciones donde es necesario que la variable ocupe un tamaño fijo, que a priori es indeterminado.

Rc, ¡viva la multipropiedad!

Rc es un puntero inteligente algo más interesante. Permite que un dato sea propiedad de varias variables a la vez. Funciona con un mecanismo de recolector de basura. La clave está en que cuando hagamos clone de un Rc no obtendremos una copia exacta, sino una referencia más al dato original. Esto permite ahorrar memoria. Veamos en un ejemplo, como Regex se comparte entre varias variables. Se trata del mismo Regex, en ningún momento ocurre una duplicidad en memoria.

extern crate regex;

use regex::Regex;
use std::rc::Rc;


fn main() {
    let r = Rc::new(Regex::new(r"([A-Za-z0-9])([.]|[_]|[A-Za-z0-9])+@gmail.com").unwrap());
    if r.is_match("pucela_segunda@gmail.com") {
        println!("Correo válido de Gmail");
    }else{
        println!("Correo no válido de Gmail");
    }

    let puntero = r.clone();
    println!("Reference Count: {}",Rc::strong_count(&puntero));
    puntero.is_match("perro@gmail.com");
    r.is_match("_pepe@gmail.com");
}

La línea Reference Count nos dice cuantas variables tienen ahora mismo acceso a ese dato. Rc funciona a la perfección en un solo hilo, pero si quieres hacer lo mismo entre hilos debes usar Arc. Rc por sí mismo, solo permite lecturas, es cuando lo juntamos con RefCell cuando obtenemos soporte de escritura.

RefCell, saltándonos las normas

En primer lugar, RefCell es muy interesante y poderoso, pero no es recomendable usarlo si se pueden usar otros métodos. Digamos que RefCell permite llevar las normas del compilador de Rust sobre préstamos y dueños al runtime. Esto puede provocar crasheos así que normalmente se usa con Rc que previene estas situaciones.

use std::rc::Rc;
use std::cell::RefCell;

fn main(){
    let n = Rc::new(RefCell::new(42));
    let x = n.clone();
    let y = n.clone();
    *x.borrow_mut() += 10;
    *y.borrow_mut() += 10;
    println!("N: {:?}",n.borrow());
}

El resultado de este código es 62. Por tanto, hemos conseguido que distintas variables pudiesen mutar el dato.

Con esto ya hemos visto los punteros inteligentes más importantes de Rust. Existe alguno más como Cell que sin embargo, no es tan usado.