A parte do Pedro: regras locais definidas pelo usuário — a Linha B do Tema 6, em que a regra é escrita em C++ e compilada em tempo de execução dentro do simulador.
O que foi construído: um novo tipo de regra local — USERDEFINED — para o componente de autômatos celulares do GenESyS. Em vez de escolher entre as poucas regras já codificadas no simulador, o usuário escreve uma única função C++, que é compilada para uma biblioteca dinâmica, carregada com dlopen e chamada em cada célula a cada passo. Tudo verificado bit a bit contra a teoria (Rule 30, Rule 90, Game of Life) por uma suíte de 22 testes.
Um autômato celular (AC) é um sistema dinâmico discreto no espaço e no tempo. Formalmente, ele é uma quádrupla (L, S, N, f) mais uma política de atualização. Cada uma dessas peças é configurável no componente do GenESyS.
O motor do GenESyS (CellularAutomata_Classic) usa atualização síncrona. Isso é crucial e fácil de errar: todas as células enxergam o mesmo instante de tempo. O passo acontece em duas fases:
f é aplicada a todas as células, sempre lendo o estado atual. O resultado vai para um campo "próximo estado" (setNextState), sem tocar no estado corrente.updateState): o "próximo" vira o "atual".A vizinhança define a ordem canônica em que os vizinhos chegam à regra. No GenESyS, para 1D centrada raio 1, a ordem é exatamente [left, right] (a própria célula não entra na lista de vizinhos).
■ célula central ■ vizinhos
O que acontece nas bordas da malha, onde faltam vizinhos? Cada estratégia dá um comportamento diferente:
As células fora da borda têm um valor constante (tipicamente 0). É o contorno usado em toda a verificação deste trabalho — simples e reprodutível.
A borda direita "encosta" na esquerda (e topo no fundo em 2D). A malha vira um anel (1D) ou um toro (2D); nada se perde nas pontas.
A borda é espelhada: o vizinho ausente assume o valor da própria célula refletida de volta para dentro.
O vizinho ausente copia o valor da célula da borda — como uma extrapolação de "gradiente zero" na fronteira.
O caso mais simples e mais famoso: 1D, estados {0,1}, vizinhança [left, right]. A regra é totalmente descrita por um único número de 0 a 255 — a numeração de Wolfram.
Cada célula olha para o trio (left, center, right). Há 8 configurações possíveis desse trio (de 111 até 000). A regra diz, para cada uma dessas 8 entradas, qual é o próximo bit. Esses 8 bits de saída, lidos em ordem, formam um número binário de 8 dígitos → daí 2⁸ = 256 regras possíveis.
# A "Rule 90" em binário é 01011010. Lendo as 8 vizinhanças do trio (left,center,right): trio: 111 110 101 100 011 010 001 000 saída: 0 1 0 1 1 0 1 0 → 01011010₂ = 90
Internamente, a classe LocalRule_Elementary calcula o índice number = 4·left + 2·center + 1·right (left é o bit mais significativo) e lê o bit correspondente do número da regra. Esse é exatamente o cálculo de Wolfram.
Gera padrões pseudoaleatórios a partir de uma única célula. Foi usada como gerador de números aleatórios no Mathematica.
// próximo = left ^ (center | right)
A partir de um único 1, desenha o triângulo de Sierpinski — um fractal exato. É um XOR puro entre vizinhos.
// próximo = left ^ right
Provada Turing-completa: é capaz de computar qualquer coisa. O AC mais simples conhecido com esse poder.
// 8 bits = 01101110₂ = 110
O AC bidimensional mais conhecido, de John Conway. Cada célula olha seus 8 vizinhos de Moore e conta quantos estão vivos:
Um quadrado 2×2 — nunca muda. Cada célula viva tem exatamente 3 vizinhos vivos, então todas sobrevivem para sempre.
Uma linha de 3 células oscila entre horizontal e vertical, a cada passo. É o oscilador mais simples.
Um padrão de 5 células que se repete a cada 4 passos, deslocado uma casa na diagonal — anda pela grade.
O Tema 6 oferecia duas linhas para representar a regra local. A Linha A (do Sutter) estende o parser do GenESyS. A Linha B (do Pedro) faz algo mais poderoso: a regra é um trecho de código C++ que o próprio simulador compila enquanto roda e carrega como biblioteca dinâmica.
g++ em tempo de execução, e a função vira código nativo carregado no processo que já está rodando.O usuário só precisa escrever esta função — sem conhecer nenhuma classe interna do GenESyS (nada de Cell, State, etc.):
extern "C" long nextState(long self, const long* neighbors, int numNeighbors);
self — o estado atual da própria célula.neighbors — os estados dos vizinhos, na ordem canônica da vizinhança (1D centrada = [left, right]).numNeighbors — quantos vizinhos vieram (2 em 1D, 8 em Moore 2D…).O extern "C" é essencial: ele desliga o name mangling do C++, para que o símbolo se chame literalmente nextState e possa ser encontrado por dlsym.
nextState (ou só o corpo, via wrapBody)..cpp e chama o g++ para produzir uma biblioteca dinâmica..so recém-criada no próprio processo.nextState dentro da lib.CppForG já existente no GenESyS (em plugins/components/ExternalIntegration/CppForG.cpp), que já fazia compile → load → dlsym com símbolos extern "C". Ou seja, a Linha B não inventa um mecanismo novo — reutiliza uma técnica já validada no próprio simulador.// Rule 90 — Sierpinski (XOR dos vizinhos)
extern "C" long nextState(long self, const long* neighbors, int n) { return neighbors[0] ^ neighbors[1]; // left XOR right }
// Rule 30 — caótico (left XOR (center OR right))
extern "C" long nextState(long self, const long* neighbors, int n) { return neighbors[0] ^ (self | neighbors[1]); }
// Game of Life — conta vizinhos vivos (Moore 2D, B3/S23)
extern "C" long nextState(long self, const long* neighbors, int n) { long living = 0; for (int i = 0; i < n; ++i) living += neighbors[i]; if (self == 1) return (living == 2 || living == 3) ? 1 : 0; return (living == 3) ? 1 : 0; }
LocalRule_UserDefinedHeader-only, herda de LocalRule. Recebe um CppCompiler injetado, tem build(userSource, error) que faz todo o pipeline (escreve fonte → compila → dlopen → dlsym), e applyRule(cell) que junta self+vizinhos num long[], chama a função e grava o próximo estado. O destrutor faz dlclose da lib. Inclui wrapBody() para o usuário escrever só o corpo da regra.
CellularAutomataCompNovo tipo de regra USERDEFINED; método para passar a fonte do usuário; _buildUserDefinedRule() que monta o compilador e dispara o build; _check() reforçado com checagem semântica (rejeita USERDEFINED sem fonte ou com código inválido); e o caminho que conecta a regra ao kernel.
_saveInstance / _loadInstance agora gravam e recarregam o tipo de AC, lattice, vizinhança, contorno, conjunto de estados, tipo de regra e a fonte da regra do usuário. A fonte é carregada antes do tipo de regra, para que um USERDEFINED já tenha seu código disponível ao ser reconstruído.
Adicionado destrutor explícito ~CellularAutomataComp() que libera os sub-objetos (lattice, vizinhança, contorno, regra…) na ordem certa — antes vazavam. Mais a suíte gtest de 22 testes que prova tudo bit a bit.
Brinque com os mesmos algoritmos que rodam no GenESyS. A lógica em JavaScript aqui é idêntica à do C++ — e produz os mesmos diagramas verificados nos testes.
1 no centro · contorno fixed-0 · vizinhança [left, right]. A Rule 90 desenha o triângulo de Sierpinski; a Rule 30, caos.Escreva o corpo de uma regra 1D usando self e neighbors (um array [left, right]). É exatamente o que o usuário escreve em C++ — só que aqui roda na hora, no navegador.
self, neighbors[0], neighbors[1]
g++ -shared -fPIC e carrega com dlopen.O Prof. Cancian separa verificação (o modelo está certo?) de validação (o modelo representa o sistema real?). Para um autômato celular, há uma virtude: o sistema é determinístico.
neighbors[0]^neighbors[1]) produz saída idêntica ao preset embutido LocalRule_Elementary(90) ao longo de 15 passos._check aceita e compila uma regra USERDEFINED válida.Estes são os diagramas exatos afirmados nos testes. O bloco da esquerda é gerado agora pelo mesmo JS das demos; o da direita é o texto literal do arquivo de evidência (a saída do C++). Eles coincidem.
Rule 30 — gerado ao vivo (largura 9, t0..t3)
Rule 30 — ground truth (SPEC / livro p.242)
000010000 000111000 001100100 011011110
Rule 90 — gerado ao vivo (largura 11, t0..t4)
Rule 90 — ground truth (Sierpinski)
00000100000 00001010000 00010001000 00101010100 01000000010
Clique para expandir cada pergunta. Estas são as respostas que o Pedro deve saber para apresentar e responder a banca.
CppForG), em vez de inventar um novo.dlopen() carrega uma biblioteca dinâmica (.so no Linux) no processo que já está rodando, em runtime, e devolve um handle. dlsym(handle, "nextState") procura nessa lib o símbolo de nome nextState e devolve um ponteiro de função, que o simulador chama como qualquer função. Por isso a função precisa de extern "C": sem ele, o C++ "embaralha" o nome do símbolo (name mangling) e o dlsym não o acharia. No fim, dlclose libera a lib.CellularAutomataComp é o ponto de ligação entre o kernel do GenESyS e o subsistema de AC. Ao escolher USERDEFINED, o _check() chama _buildUserDefinedRule(), que cria um CppCompiler, instancia LocalRule_UserDefined e chama build() (compila + carrega + resolve o símbolo). A regra pronta é guardada em _localRule. Quando o kernel dispara um evento (_onDispatchEvent), o componente chama _cellularAutomata->step(), que aplica a regra (e portanto a função do usuário) a todas as células e troca os estados.extern "C" long nextState(long self, const long* neighbors, int numNeighbors). O usuário recebe o estado da própria célula e a lista de estados dos vizinhos (na ordem da vizinhança) e devolve o próximo estado. Não precisa conhecer Cell, State nem nenhuma classe do GenESyS — só aritmética de inteiros. Isso torna a regra trivial de escrever e rápida de compilar.build() retorna false com mensagem de erro, e _check() rejeita a configuração. (2) Bug de heap corrigido: foi adicionado destrutor explícito ao componente para liberar lattice, vizinhança, contorno, regra e a lib dinâmica na ordem certa (antes vazava). (3) Nome único por build: cada compilação gera uma .so com nome único, para o dlopen nunca devolver um mapeamento velho em cache.long escalar, vizinhos como array ordenado) não bloqueia essa expansão.