O trabalho em um minuto
Se você só puder ler um parágrafo, leia este. O resto do site detalha cada pedaço.
O GenESyS é um simulador feito pelo professor. Ele já tinha um pedaço inicial para autômatos celulares (grades de células que evoluem por regras simples, como o Jogo da Vida). Esse pedaço era incompleto e com bugs. O Tema 6 pediu para transformá-lo num componente universal: que aceite muitos tipos de grade, vizinhança, borda, conjunto de estados, política de atualização e, principalmente, regras escritas pelo próprio usuário.
O grupo entregou exatamente isso, dividido assim: o Sutter fez a generalização universal (bordas, conjuntos de estados, vizinhanças N dimensionais, políticas de atualização). O Pedro fez o ponto central do tema, a regra definida pelo usuário: o usuário escreve uma função em C, ela é compilada na hora e carregada no simulador rodando, sem recompilar o GenESyS inteiro.
As quatro camadas do componente
Lattice, Cell, State.Neighborhood, Boundary.StateSet, LocalRule.UpdatePolicy.O que é um autômato celular
Um autômato celular é um mundo discreto: uma grade de células, cada uma com um estado, que muda em passos de tempo seguindo uma regra que olha só para os vizinhos. Coisas simples geram padrões surpreendentes. A melhor forma de entender é vendo. Mexa abaixo.
A tupla (L, S, N, f)
Todo autômato celular é definido por quatro coisas (mais a política de tempo):
L = o lattice, a grade de células (aqui, uma linha).
S = os estados possíveis (aqui, 0 ou 1: morta ou viva).
N = a vizinhança (aqui, a célula olha a da esquerda e a da direita).
f = a regra local, que diz o próximo estado a partir do estado atual e dos vizinhos.
No autômato elementar (o da demo), cada célula olha 3 células: ela e os 2 vizinhos. São 8 combinações possíveis. Para cada uma, a regra diz se o resultado é 0 ou 1. Oito respostas de 0 ou 1 formam um número de 8 bits, de 0 a 255. Esse é o número de Wolfram da regra. Clique nos quadradinhos abaixo e veja o número mudar.
A tabela da regra (a definição de f)
Cada coluna é uma das 8 vizinhanças possíveis (esquerda, centro, direita). O quadrado de baixo é a resposta da regra para aquela vizinhança. Clique para alternar 0/1.
Número da regra resultante: 30 (a demo acima usa este mesmo número)
Game of Life: a mesma ideia em duas dimensões
O Jogo da Vida do Conway é um autômato celular 2D. Cada célula olha as 8 ao redor (vizinhança de Moore). A regra B3/S23: uma célula morta com exatamente 3 vizinhas vivas nasce; uma viva com 2 ou 3 vizinhas sobrevive; o resto morre. Dessas três frases emergem estruturas que se movem, oscilam e até "calculam". Aperte play.
Dica: clique nas células do tabuleiro para desenhar você mesmo.
O que olhar aqui
O blinker (3 células em linha) é o teste mais simples: vira vertical, depois horizontal de novo. Período 2. Esse comportamento é checado por um teste do trabalho.
O glider volta à própria forma deslocada de uma casa na diagonal a cada 4 passos. Ele "anda". Outro teste do trabalho confere exatamente isso.
É a mesma estrutura da regra elementar (grade, estados, vizinhança, regra), só que a grade tem 2 dimensões e a vizinhança tem 8 vizinhos em vez de 2. No componente, basta trocar a configuração: setLatticeType com 2 dimensões, setNeighboorhoodType(MOORE), setLocalRuleType(GAME_OF_LIFE).
O que o professor pediu (Tema 6)
O enunciado pede para pegar o suporte a autômatos celulares que já existia no GenESyS e torná-lo universal: geral o suficiente para representar uma família ampla de autômatos, não só alguns casos fixos no código.
Universal quer dizer: o usuário pode escolher
E o enunciado é explícito sobre qual é o ponto mais difícil e mais importante: como representar a regra local definida pelo usuário. Uma regra precisa de mais do que uma conta simples; ela acessa o estado da célula, dos vizinhos, às vezes a posição e o passo de tempo.
As duas linhas que o enunciado sugere
Linha A (parser): escrever a regra numa linguagem interpretada pelo simulador. Elegante, mas limitada para regras complexas.
Linha B (compilação dinâmica): o usuário escreve a regra em C++, ela é compilada na hora numa biblioteca e chamada durante a simulação. Mais geral e mais eficiente. É a que o professor mais elogia para este tema.
A arquitetura em quatro camadas
O componente CellularAutomataComp é a ponte entre o motor do GenESyS e o subsistema de autômatos. Ele é dono de um objeto de cada camada. Trocar o comportamento do autômato é trocar qual objeto está em cada camada.
Lattice é a grade N dimensional, dona das Cell. Cada Cell guarda o estado atual, o próximo e a posição. State é o valor da célula. A grade pode ter 1, 2 ou 3 dimensões.Neighborhood define quem são os vizinhos: Center (1D), Moore (8 em 2D), VonNeumann (4 em 2D). Boundary define o que existe além da borda: Fixed, Closed (periódica), Reflexive, Adiabatic.StateSet diz quais valores são válidos: Enumerable, Integer, Bit, Double. LocalRule é a regra de transição: Elementary (Wolfram), GameOfLife, e a estrela do trabalho, UserDefined.UpdatePolicy diz quando as células mudam: SYNCHRONOUS (todas ao mesmo tempo), SEQUENTIAL (uma a uma em ordem), RANDOM (ordem sorteada) ou BLOCKS (em blocos).Como o motor dá um passo (atualização síncrona em 2 fases)
Esse detalhe é importante e cai em prova: para todas as células verem o mesmo "instante", o passo é feito em duas fases. Primeiro a regra é aplicada a todas as células, escrevendo o próximo estado num campo separado. Só depois todas trocam de uma vez (o atual vira o próximo). Assim nenhuma célula enxerga um vizinho já atualizado no mesmo passo. O livro recomenda exatamente isso (Capítulo 11).
// CellularAutomata_Classic::applyLocalRule() for (cada célula) localRule.applyRule(célula); // fase 1: calcula nextState for (cada célula) célula.updateState(); // fase 2: currentState = nextState
O diagrama de classes completo está na seção UML.
A regra definida pelo usuário: o coração do trabalho
Este é o ponto central do Tema 6 e a parte do Pedro. Em vez de ter só algumas regras fixas no código, o usuário escreve a própria regra, e o GenESyS a compila e roda na hora. Entenda isto bem: é o que o professor mais vai perguntar.
O contrato (tudo que o usuário escreve)
O usuário não precisa conhecer nada de dentro do GenESyS. Ele escreve apenas uma função em C com este formato:
extern "C" long nextState( long self, // estado atual da célula const long* neighbors, // estados dos vizinhos int numNeighbors); // quantos vizinhos // retorna: o próximo estado da célula
Há também uma versão estendida, nextStateEx, que recebe a posição da célula e a dimensão. Assim a regra pode depender de onde a célula está, não só dos vizinhos. Foi acrescentada porque o enunciado pede que a regra possa acessar a posição da célula no lattice.
O caminho da regra (compilação dinâmica)
Quando o modelo é verificado, isto acontece nos bastidores:
- O texto da regra é salvo num arquivo
.cpp. - O
CppCompilercompila comg++ -shared -fPICgerando uma biblioteca.so. dlopencarrega a biblioteca no simulador que já está rodando.dlsymacha a funçãonextStatedentro dela.- A cada passo, para cada célula, essa função é chamada.
Se o código do usuário tiver erro, a verificação falha com mensagem clara, sem travar o simulador. Cada compilação usa um nome único de arquivo para o dlopen nunca pegar uma versão velha em cache.
CppCompiler que já existia no GenESyS (o mesmo mecanismo do componente CppForG). É a abordagem que o enunciado chama de "particularmente forte para este tema".Experimente: escreva uma regra e rode
Abaixo, uma versão de brincadeira do mesmo contrato, rodando no navegador. Escreva o corpo da função (em JavaScript, mas a ideia é idêntica à de C). Use self (0 ou 1), n[0] e n[1] (vizinho esquerdo e direito) e pos (posição). Retorne 0 ou 1.
Pronto. Clique em "Compilar e rodar".
No trabalho real, esse "compilar" é o g++ de verdade gerando uma biblioteca nativa. Aqui é só uma simulação no navegador para você sentir o conceito.
A sequência completa
O diagrama abaixo mostra o ciclo de vida da regra do usuário, da verificação do modelo até a chamada por célula. Veja a explicação na seção UML.
A parte universal: bordas, estados, vizinhanças e tempo
Esta é a parte do Sutter: deixar o componente genérico em todas as outras dimensões. Aqui vão as ideias que você precisa explicar, com uma demo das bordas (a mais visual).
Condições de contorno (o que existe além da borda)
A demo mostra uma regra simples: "copie o vizinho da esquerda", que faz um ponto andar para a direita. Veja a diferença no que acontece quando ele chega na borda.
As quatro bordas
Fixed (fixa): além da borda existe um valor fixo (0). O ponto chega na ponta e some.
Closed (periódica): a grade é um anel. O ponto sai por um lado e volta pelo outro (toroidal).
Reflexive (espelhada): a borda reflete os estados de volta para dentro.
Adiabatic: a borda copia o valor da própria célula da ponta.
Na demo: linha de cima = borda fixa (o ponto some na ponta). Linha de baixo = borda periódica (o ponto dá a volta).
Conjuntos de estados
Quais valores uma célula pode ter, com validação: Enumerable (lista de valores), Integer (só inteiros), Bit (só 0 ou 1), Double (aceita fração). Tentar pôr um valor inválido é rejeitado. Isso importa porque a regra depende fortemente de quais estados existem.
Políticas de atualização
Síncrona: todas mudam juntas (o padrão clássico). Sequencial: uma de cada vez, em ordem. Aleatória: ordem sorteada. Em blocos: de grupo em grupo. A aleatória usa um embaralhamento que dá o mesmo resultado em qualquer computador para a mesma semente, então a simulação continua reproduzível.
std::shuffle por um Fisher-Yates com distribuição definida foi uma decisão de engenharia. O std::shuffle consome o gerador de forma diferente em cada biblioteca padrão, então o resultado mudaria entre Linux e Mac. Com a versão definida, a mesma semente dá a mesma ordem em todo lugar. Resultado comprovável, que é uma exigência da disciplina.Como roda e como foi testado
Tudo roda pelo terminal, sem interface gráfica. O componente é compilado por CMake junto com o GenESyS e validado por uma bateria de testes automatizados.
Compilar e rodar os testes
# configurar e compilar os testes do componente cmake -S . -B build/tests -DGENESYS_BUILD_TESTS=ON \ -DGENESYS_BUILD_GUI_APPLICATION=OFF cmake --build build/tests -j \ --target genesys_test_cellular_automata \ genesys_test_cellular_automata_user_defined \ genesys_test_cellular_automata_component \ genesys_test_cellular_automata_elementary \ genesys_test_cellular_automata_neighborhood # rodar -> 36 de 36 verdes
A regra do usuário precisa de um compilador C++ (g++ ou clang) disponível no sistema, porque ela compila código em tempo de execução.
Como se prova que está certo
Um autômato celular é determinístico: a mesma configuração sempre dá o mesmo resultado. Então a validação não usa média de várias rodadas nem intervalo de confiança (isso é para modelos com aleatoriedade). A prova correta é reprodução exata de resultados teóricos conhecidos.
Por isso os testes comparam, célula por célula, a saída do motor com a regra 30 do livro (página 242), a regra 90 (Sierpinski) e o Game of Life (blinker e glider). Se bater exatamente, está correto.
Os 36 testes, por arquivo
| Arquivo de teste | Casos | O que prova |
|---|---|---|
| test_cellular_automata | 11 | Parte universal: estados Integer/Bit/Double rejeitam valores inválidos, regra 90 nas 4 bordas, Game of Life, contagem de vizinhos em 1D/2D/3D, políticas de atualização determinísticas. |
| test_cellular_automata_elementary | 4 | Regra 30 igual ao livro, regra 90 igual ao Sierpinski, determinismo, grade vazia continua vazia. |
| test_cellular_automata_user_defined | 8 | Regra do usuário reproduz 30/90, regra do usuário igual ao preset embutido, falha graciosa em código inválido, Game of Life via regra do usuário, borda periódica (anel), glider, e a regra com posição (contrato estendido). |
| test_cellular_automata_component | 5 | A verificação compila e carrega a regra do usuário, rejeita configuração sem fonte / com fonte inválida / sem tipo, e a persistência salva e recarrega a configuração inteira. |
| test_cellular_automata_neighborhood | 8 | Conversão posição para índice, contagem de vizinhos de Moore e Von Neumann em várias dimensões e raios, ordem determinística dos vizinhos. |
Total: 36 de 36 verdes. A suíte inteira do simulador (1409 testes) também passa, sem regressão causada pelo componente.
Os diagramas UML, explicados
UML é uma forma padrão de desenhar software. Dois diagramas resumem o componente: o de classes (a estrutura) e o de sequência (o passo a passo da regra do usuário).
Como ler o diagrama de classes
Cada caixa é uma classe (um tipo de objeto). As setas têm significado:
Triângulo vazado aponta para a classe "pai": significa herança (a filha é um tipo de pai). Exemplo: LocalRule_UserDefined é uma LocalRule.
Losango preenchido significa composição: a classe é dona daquele objeto. Exemplo: CellularAutomataComp é dono do Lattice, e o Lattice é dono das Cell.
Seta tracejada significa uso: LocalRule_UserDefined usa o CppCompiler para compilar a regra.
As caixas estão agrupadas pelas quatro camadas da seção Arquitetura. A caixa vermelha é a regra do usuário (Linha B); a verde é o compilador que ela usa.
O diagrama de sequência
Lê-se de cima para baixo. As colunas são os objetos; as setas são as chamadas, na ordem do tempo. A parte de cima (azul) é a verificação do modelo: a regra do usuário é compilada, carregada e o símbolo da função é resolvido. A parte de baixo (verde) é a simulação: a cada passo, para cada célula, a função do usuário é chamada e o próximo estado é gravado.
Roteiro para gravar o vídeo
Uma apresentação de 20 a 25 minutos, dividida em blocos. Para cada bloco: o que falar, o que mostrar na tela e uma frase pronta para abrir. Adapte com suas palavras; o importante é o encadeamento.
Abertura e contexto
Apresente o grupo, a disciplina e o tema. Diga em uma frase o que é o trabalho.
"Nosso DCS é o Tema 6: transformar o suporte a autômatos celulares do GenESyS num componente universal, com foco no ponto central do tema, que é permitir regras definidas pelo usuário."
O que é um autômato celular
Mostre a demo da regra elementar (seção 01) rodando. Explique a tupla (L, S, N, f) e o número de Wolfram com a tabela da regra. Troque para a regra 90 e mostre o Sierpinski aparecendo.
"Cada célula olha só os vizinhos e segue uma regra. Dessa simplicidade surgem padrões complexos. Esse número, 30, codifica a regra inteira."
Game of Life (a mesma ideia em 2D)
Mostre o glider andando e o blinker piscando. Diga que o componente faz isso só trocando a configuração (2 dimensões, vizinhança de Moore, regra Game of Life).
"É a mesma estrutura, agora em duas dimensões. E tudo isso é configurável no nosso componente, sem mexer no código."
O que o professor pediu
Liste as dimensões que ficam configuráveis (tipo, dimensão, vizinhança, borda, estados, regra, política). Destaque que o ponto mais difícil e mais valorizado é a regra definida pelo usuário, e que escolhemos a Linha B (compilação dinâmica).
"O enunciado deixa claro: o ponto central é a regra do usuário. Escolhemos compilar a regra em tempo real, que é a via mais geral."
A arquitetura em 4 camadas
Mostre o diagrama de classes (seção 08). Explique as quatro camadas e como o CellularAutomataComp é dono de um objeto de cada. Explique o passo em 2 fases (calcula todos os próximos estados, depois troca todos juntos).
"Separamos o problema em quatro camadas. Trocar o comportamento do autômato é só trocar qual objeto está em cada camada."
A regra do usuário (o coração)
Esta é a parte mais importante, gaste mais tempo. Mostre o contrato (nextState e nextStateEx). Mostre o diagrama de sequência e narre os passos: salva o código, g++ compila o .so, dlopen carrega, dlsym acha a função, e a cada célula ela é chamada. Use a demo "escreva sua regra" para mostrar uma regra rodando ao vivo.
"O usuário escreve só esta função. O GenESyS compila ela na hora, carrega como biblioteca e chama para cada célula. Se o código tiver erro, falha com mensagem clara, sem travar."
A parte universal
Mostre a demo das bordas. Explique as quatro condições de contorno, os conjuntos de estados e as políticas de atualização. Mencione a decisão do Fisher-Yates para manter o resultado reproduzível entre sistemas.
"Além da regra, generalizamos a estrutura inteira: bordas, tipos de estado, vizinhanças em até três dimensões e como o tempo avança."
Testes e verificação
Mostre a tabela dos 36 testes (seção 07). Explique a ideia-chave: como o sistema é determinístico, a prova de correção é reprodução exata da teoria, não estatística. Cite a regra 30 do livro, o Sierpinski e o glider. Mostre o resultado: 36 de 36 verdes.
"Como o autômato é determinístico, provamos que está certo reproduzindo, célula por célula, os resultados conhecidos da teoria. Trinta e seis testes, todos verdes."
Fechamento
Resuma: estrutura universal mais regra do usuário compilada dinamicamente cobrem o tema inteiro. Diga o que ficou como arquitetura aberta para o futuro (lattices não retangulares, regras não uniformes). Agradeça.
"Em resumo: o componente ficou universal e expressivo. O usuário configura tudo e ainda escreve a própria regra. Obrigado."
Glossário e perguntas prováveis
Termos que você precisa saber dizer
- Autômato celular
- Grade de células que evoluem em passos por uma regra local que olha os vizinhos.
- Lattice
- A grade de células. Pode ter 1, 2 ou 3 dimensões.
- Estado
- O valor de uma célula (por exemplo 0 ou 1, morta ou viva).
- Vizinhança
- Quais células influenciam uma célula. Moore = as 8 ao redor; Von Neumann = as 4 ortogonais.
- Condição de contorno
- O que acontece na borda: fixa, periódica (anel), espelhada, adiabática.
- Regra local
- A função que decide o próximo estado de uma célula a partir dela e dos vizinhos.
- Número de Wolfram
- O número de 0 a 255 que codifica uma regra elementar 1D.
- Política de atualização
- Quando as células mudam: síncrona, sequencial, aleatória ou em blocos.
- Atualização síncrona
- Todas as células mudam ao mesmo tempo, em duas fases, para ninguém ver vizinho já atualizado.
- Compilação dinâmica
- Compilar código em tempo de execução numa biblioteca e carregá-la no programa rodando.
- dlopen / dlsym
- Funções do sistema que carregam uma biblioteca e acham uma função dentro dela.
- Determinístico
- Sempre dá o mesmo resultado para a mesma entrada. Por isso a validação é por reprodução exata.
Perguntas que o professor pode fazer
Por que compilar a regra em vez de interpretar com um parser?
CppCompiler que já existia no GenESyS. O próprio enunciado diz que essa via é particularmente forte para o tema.O que acontece se o código da regra do usuário tiver um erro?
_check) retorna erro com a mensagem do compilador, sem travar o simulador. Existe um teste justamente para isso (falha graciosa).