Aqui está uma pergunta teórica - uma que não oferece uma resposta fácil em nenhum caso, nem mesmo a trivial.

No Jogo da Vida de Conway, existem construções como o metapixel que permitem ao Jogo da Vida simular qualquer outro sistema de regras do Jogo da Vida. Além disso, sabe-se que o Jogo da Vida é Turing completo.

Sua tarefa é construir um autômato celular usando as regras do jogo da vida de Conway que permitirão o jogo de Tetris.

Seu programa receberá entradas alterando manualmente o estado do autômato em uma geração específica para representar uma interrupção (por exemplo, movendo uma peça para a esquerda ou direita, largando-a, girando-a ou gerando aleatoriamente uma nova peça para colocar na grade), contando um número específico de gerações como tempo de espera e exibindo o resultado em algum lugar do autômato. O resultado exibido deve se parecer com uma grade real do Tetris.

Seu programa será pontuado das seguintes maneiras, em ordem (com critérios mais baixos atuando como desempate para critérios mais altos):

• Tamanho da caixa delimitadora - vence a caixa retangular com a menor área que contém completamente a solução fornecida.

• Alterações menores na entrada - o menor número de células (no pior dos casos em seu autômato) que precisa ser ajustado manualmente para uma interrupção vence.

• Execução mais rápida - vence o menor número de gerações para avançar um tique na simulação.

• Contagem inicial de células vivas - menor número de vitórias.

• Primeiro a postar - post anterior vence.

Isso começou como uma missão, mas terminou como uma odisseia.

Busca pelo processador Tetris, 2.940.928 x 10.295.296

O arquivo padrão, em toda a sua glória, pode ser encontrado aqui , visível no navegador aqui .

Este projeto é o culminar dos esforços de muitos usuários ao longo dos últimos 1 e 1/2 anos. Embora a composição da equipe tenha variado ao longo do tempo, os participantes, por escrito, são os seguintes:

• PhiNotPi
• El'endia Starman
• K Zhang
• Azul (Peixe Muddy)
• Vacas charlatão (Kritixi Lithos)
• Mego
• Quartata

Também gostaríamos de agradecer a 7H3_H4CK3R, Conor O'Brien e a muitos outros usuários que se esforçaram para solucionar esse desafio.

Devido ao escopo sem precedentes dessa colaboração, essa resposta é dividida em partes em várias respostas escritas pelos membros dessa equipe. Cada membro escreverá sobre subtópicos específicos, correspondendo aproximadamente às áreas do projeto nas quais eles estiveram mais envolvidos.

Distribua quaisquer upvotes ou recompensas por todos os membros da equipe.

Índice

1. visão global
2. Metapixels e VarLife
3. Hardware
4. QFTASM e Cogol
5. Assembléia, tradução e o futuro
6. Novo idioma e compilador

Considere também verificar nossa organização do GitHub, onde colocamos todo o código que escrevemos como parte de nossa solução. As perguntas podem ser direcionadas para nossa sala de bate-papo de desenvolvimento .

Parte 1: Visão geral

A ideia subjacente deste projeto é abstração . Em vez de desenvolver um jogo Tetris diretamente no Life, lentamente aumentamos a abstração em uma série de etapas. Em cada camada, nos distanciamos das dificuldades da Vida e nos aproximamos da construção de um computador que é tão fácil de programar quanto qualquer outro.

Primeiro, usamos os metapixels da OTCA como base do nosso computador. Esses metapixels são capazes de emular qualquer regra "realista". O Wireworld e o computador Wireworld serviram como importantes fontes de inspiração para este projeto, por isso buscamos criar uma construção semelhante com metapixels. Embora não seja possível emular o Wireworld com metapixels OTCA, é possível atribuir diferentes regras a metapixels diferentes e criar arranjos de metapixels que funcionem de maneira semelhante aos fios.

O próximo passo foi construir uma variedade de portas lógicas fundamentais para servir de base ao computador. Já nesta fase, estamos lidando com conceitos semelhantes ao design de processadores do mundo real. Aqui está um exemplo de uma porta OR, cada célula nesta imagem é na verdade um metapixel OTCA inteiro. Você pode ver "elétrons" (cada um representando um único bit de dados) entrar e sair do portão. Você também pode ver todos os diferentes tipos de metapixels que usamos em nosso computador: B / S como plano de fundo preto, B1 / S em azul, B2 / S em verde e B12 / S1 em vermelho.

A partir daqui, desenvolvemos uma arquitetura para o nosso processador. Dedicamos um esforço significativo ao projetar uma arquitetura que fosse ao mesmo tempo não esotérica e tão facilmente implementável quanto possível. Enquanto o computador Wireworld usava uma arquitetura rudimentar acionada por transporte, este projeto usa uma arquitetura RISC muito mais flexível, completa com vários opcodes e modos de endereçamento. Criamos uma linguagem assembly, conhecida como QFTASM (Quest for Tetris Assembly), que orientou a construção do nosso processador.

Nosso computador também é assíncrono, o que significa que não há relógio global controlando o computador. Em vez disso, os dados são acompanhados por um sinal de relógio à medida que flui pelo computador, o que significa que precisamos apenas focar nos horários locais, mas não globais, do computador.

Aqui está uma ilustração da nossa arquitetura de processador:

A partir daqui, é apenas uma questão de implementar o Tetris no computador. Para ajudar a conseguir isso, trabalhamos em vários métodos de compilação de linguagem de nível superior no QFTASM. Temos uma linguagem básica chamada Cogol, uma segunda linguagem mais avançada em desenvolvimento e, finalmente, temos um back-end do GCC em construção. O atual programa Tetris foi escrito / compilado pela Cogol.

Depois que o código final do Tetris QFTASM foi gerado, as etapas finais foram reunidas a partir desse código na ROM correspondente e, em seguida, dos metapixels para o Game of Life subjacente, concluindo nossa construção.

Executando Tetris

Para aqueles que desejam reproduzir o Tetris sem mexer no computador, você pode executar o código fonte do Tetris no intérprete QFTASM . Defina os endereços de exibição de RAM como 3-32 para visualizar o jogo inteiro. Aqui está um link permanente para sua conveniência: Tetris in QFTASM .

Funcionalidades do jogo:

• Todos os 7 tetrominos
• Movimento, rotação, quedas suaves
• Linha limpa e pontuação
• Peça de visualização
• As entradas do jogador injetam aleatoriedade

Exibição

Nosso computador representa a placa Tetris como uma grade em sua memória. Os endereços 10 a 31 exibem o quadro, os endereços 5 a 8 exibem a peça de visualização e o endereço 3 contém a pontuação.

Entrada

A entrada no jogo é realizada editando manualmente o conteúdo do endereço RAM 1. Usando o intérprete QFTASM, isso significa executar gravações diretas no endereço 1. Procure "Gravação direta na RAM" na página do intérprete. Cada movimento requer apenas a edição de um único bit de RAM e esse registro de entrada é limpo automaticamente após a leitura do evento de entrada.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

Sistema de pontuação

Você recebe um bônus por limpar várias linhas em um único turno.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Parte 2: OTCA Metapixel e VarLife

OTCA Metapixel

( Fonte )

O OTCA Metapixel é uma construção do Jogo da Vida de Conway que pode ser usada para simular qualquer autômato celular semelhante ao da Vida. Como o LifeWiki (link acima) diz,

O metapixel da OTCA é uma célula unitária de 35328 de período 2048 × 2048 que foi construída por Brice Due ... Tem muitas vantagens ... incluindo a capacidade de emular qualquer autômato celular do tipo Life e o fato de que, quando diminuído o zoom, o ON e células OFF são fáceis de distinguir ...

O que os autômatos celulares semelhantes à vida significam aqui é essencialmente que as células nascem e sobrevivem de acordo com quantas de suas oito células vizinhas estão vivas. A sintaxe para essas regras é a seguinte: um B seguido pelo número de vizinhos vivos que causarão um nascimento, uma barra e um S seguido pelo número de vizinhos vivos que manterão a célula viva. Um pouco prolixo, então acho que um exemplo vai ajudar. O Jogo da Vida canônico pode ser representado pela regra B3 / S23, que diz que qualquer célula morta com três vizinhos vivos ficará viva e qualquer célula viva com dois ou três vizinhos vivos permanecerá viva. Caso contrário, a célula morre.

Apesar de ser uma célula de 2048 x 2048, o metapixel da OTCA realmente tem uma caixa delimitadora de 2058 x 2058, a razão é que ela se sobrepõe a cinco células em todas as direções com seus vizinhos diagonais . As células sobrepostas servem para interceptar planadores - que são emitidos para sinalizar os vizinhos de metacélulas em que está - para que eles não interfiram com outros metapixels ou voem indefinidamente. As regras de nascimento e sobrevivência são codificadas em uma seção especial de células no lado esquerdo do metapixel, pela presença ou ausência de comedores em posições específicas ao longo de duas colunas (uma para o nascimento e outra para a sobrevivência). Quanto à detecção do estado das células vizinhas, veja como isso acontece:

Um fluxo 9-LWSS passa no sentido horário pela célula, perdendo um LWSS para cada célula adjacente que ativou uma reação de honeybit. O número de LWSSes ausentes é contado detectando a posição do LWSS frontal, colidindo com outro LWSS na direção oposta. Essa colisão libera planadores, o que desencadeia uma ou duas reações de honeybit se os comedores que indicam que a condição de nascimento / sobrevivência estão ausentes.

Um diagrama mais detalhado de cada aspecto do metapixel da OTCA pode ser encontrado em seu site original: Como funciona? .

VarLife

Eu construí um simulador on-line de regras do tipo vida, onde você pode fazer com que qualquer célula se comporte de acordo com qualquer regra do tipo vida e chamei de "variações da vida". Este nome foi abreviado para "VarLife" para ser mais conciso. Aqui está uma captura de tela (link para ele aqui: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):

Recursos notáveis:

• Alterne células entre vivo / morto e pinte o quadro com regras diferentes.
• A capacidade de iniciar e interromper a simulação e executar uma etapa de cada vez. Também é possível executar um determinado número de etapas o mais rápido possível ou mais lentamente, na taxa definida nas caixas ticks por segundo e milissegundos por tick.
• Limpe todas as células vivas ou redefina totalmente a placa para um estado em branco.
• Pode alterar o tamanho da célula e da placa e também para permitir o empacotamento toroidal horizontal e / ou verticalmente.
• Links permanentes (que codificam todas as informações no URL) e URLs curtos (porque às vezes há informações demais, mas são legais de qualquer maneira).
• Conjuntos de regras, com especificação B / S, cores e aleatoriedade opcional.
• E por último, mas definitivamente não menos importante, renderizar gifs!

O recurso de renderização em gif é o meu favorito, porque demorou muito trabalho para implementar, por isso foi realmente gratificante quando eu finalmente o decifrei às 7 da manhã, e porque torna muito fácil compartilhar as construções do VarLife com outras pessoas. .

Circuitos Básicos VarLife

Em suma, o computador VarLife precisa apenas de quatro tipos de células! Oito estados em todos, contando os estados morto / vivo. Eles são:

• B / S (preto / branco), que serve como um buffer entre todos os componentes, pois as células B / S nunca podem estar vivas.
• B1 / S (azul / ciano), que é o principal tipo de célula usado para propagar sinais.
• B2 / S (verde / amarelo), usado principalmente para controle de sinal, garantindo que não seja retropropagado.
• B12 / S1 (vermelho / laranja), usado em algumas situações especializadas, como atravessar sinais e armazenar um pouco de dados.

Use este URL curto para abrir o VarLife com estas regras já codificadas: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Fios

Existem alguns projetos de cabos diferentes com características variadas.

Esse é o fio mais fácil e básico do VarLife, uma faixa azul delimitada por faixas verdes.

URL curto: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Este fio é unidirecional. Ou seja, ele mata qualquer sinal que tente viajar na direção oposta. É também uma célula mais estreita que o fio básico.

URL curto: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Os fios diagonais também existem, mas não são muito utilizados.

URL curto: http://play.starmaninnovations.com/varlife/kJotsdSXIj

Portões

Na verdade, existem várias maneiras de construir cada porta individual, então mostrarei apenas um exemplo de cada tipo. Este primeiro gif demonstra as portas AND, XOR e OR, respectivamente. A idéia básica aqui é que uma célula verde age como um AND, uma célula azul age como um XOR e uma célula vermelha age como um OR, e todas as outras células ao seu redor estão lá apenas para controlar o fluxo adequadamente.

URL curto: http://play.starmaninnovations.com/varlife/EGTlKktmeI

O portão AND-NOT, abreviado para "ANT gate", acabou sendo um componente vital. É um portão que passa um sinal de A se e somente se não houver sinal de B. Portanto, "A AND NOT B".

URL curto: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Embora não seja exatamente um portão , uma telha de passagem de arame ainda é muito importante e útil.

URL curto: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

Aliás, não existe um portão NÃO aqui. Isso ocorre porque, sem um sinal de entrada, uma saída constante deve ser produzida, o que não funciona bem com a variedade de tempos exigidos pelo hardware atual do computador. Nós nos demos muito bem sem ele de qualquer maneira.

Além disso, muitos componentes foram projetados intencionalmente para caber em uma caixa delimitadora de 11 por 11 (um ladrilho ), onde são necessários 11 sinais de carrapatos entrando no ladrilho para sair do ladrilho. Isso torna os componentes mais modulares e mais fáceis de encaixar, conforme necessário, sem ter que se preocupar em ajustar os fios para espaçamento ou tempo.

Para ver mais portões que foram descobertos / construídos no processo de exploração de componentes de circuitos, confira esta postagem no blog de PhiNotPi: Blocos de Construção: Portões Lógicos .

Atrasar componentes

No processo de projetar o hardware do computador, a KZhang criou vários componentes de atraso, mostrados abaixo.

Atraso de 4 marcações: URL curto: http://play.starmaninnovations.com/varlife/gebOMIXxdh

Atraso de 5 marcações: URL curto: http://play.starmaninnovations.com/varlife/JItNjJvnUB

Atraso de 8 marcações (três pontos de entrada diferentes): URL curto: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

Atraso de 11 marcações: URL curto: http://play.starmaninnovations.com/varlife/kfoADussXA

Atraso de 12 marcações: URL curto: http://play.starmaninnovations.com/varlife/bkamAfUfud

Atraso de 14 marcações: URL curto: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Atraso de 15 marcações (verificado por comparação com isso ): URL curto: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Bem, é isso para componentes básicos de circuitos no VarLife! Veja a publicação de hardware do KZhang para saber os principais circuitos do computador!

Parte 3: Hardware

Com nosso conhecimento das portas lógicas e da estrutura geral do processador, podemos começar a projetar todos os componentes do computador.

Desmultiplexador

Um desmultiplexador, ou demux, é um componente crucial para a ROM, RAM e ALU. Ele direciona um sinal de entrada para um dos muitos sinais de saída com base em alguns dados do seletor. É composto por 3 partes principais: um conversor serial para paralelo, um verificador de sinal e um divisor de sinal de relógio.

Começamos convertendo os dados do seletor serial para "paralelo". Isso é feito dividindo e atrasando estrategicamente os dados para que o bit mais à esquerda intercepte o sinal do relógio no quadrado 11x11 mais à esquerda, o próximo bit de dados intercepte o sinal do relógio no próximo quadrado 11x11 e assim por diante. Embora todos os bits de dados sejam emitidos em todos os quadrados 11x11, todos os bits de dados se cruzam com o sinal do relógio apenas uma vez.

Em seguida, verificaremos se os dados paralelos correspondem a um endereço predefinido. Fazemos isso usando portas AND e ANT no relógio e dados paralelos. No entanto, precisamos garantir que os dados paralelos também sejam emitidos para que possam ser comparados novamente. Estes são os portões que eu inventei:

Finalmente, apenas dividimos o sinal do relógio, empilhamos vários verificadores de sinal (um para cada endereço / saída) e temos um multiplexador!

ROM

A ROM deve receber um endereço como entrada e enviar as instruções nesse endereço como saída. Começamos usando um multiplexador para direcionar o sinal do relógio para uma das instruções. Em seguida, precisamos gerar um sinal usando algumas passagens de fios e portas OR. Os cruzamentos de fio permitem que o sinal do relógio percorra todos os 58 bits da instrução e também permitem que um sinal gerado (atualmente em paralelo) se mova para baixo através da ROM a ser emitida.

Em seguida, apenas precisamos converter o sinal paralelo em dados seriais e a ROM está completa.

Atualmente, a ROM é gerada executando um script no Golly que converterá o código de montagem da sua área de transferência na ROM.

SRL, SL, SRA

Esses três portões lógicos são usados ​​para mudanças de bits e são mais complicados do que o típico AND, OR, XOR etc. nos dados. O segundo argumento dado a esses portões determina quantos bits mudar.

Para o SL e o SRL, precisamos

1. Verifique se os 12 bits mais significativos não estão ativados (caso contrário, a saída é simplesmente 0) e
2. Atrasar os dados a quantidade correta com base nos 4 bits menos significativos.

Isso é possível com um monte de portas AND / ANT e um multiplexador.

O SRA é um pouco diferente, porque precisamos copiar o bit de sinal durante o turno. Fazemos isso ANDing o sinal do relógio com o bit de sinal e, em seguida, copiamos essa saída várias vezes com separadores de fios e portas OR.

Trava Set-Reset (SR)

Muitas partes da funcionalidade do processador dependem da capacidade de armazenar dados. Usando 2 células B12 / S1 vermelhas, podemos fazer exatamente isso. As duas células podem se manter ligadas e também podem ficar juntas. Usando alguns circuitos extras, redefinidos e lidos, podemos fazer uma simples trava SR.

Sincronizador

Ao converter dados seriais em dados paralelos e definir várias travas SR, podemos armazenar uma palavra inteira de dados. Então, para recuperar os dados novamente, podemos apenas ler e redefinir todas as travas e atrasar os dados de acordo. Isso nos permite armazenar uma (ou mais) palavra de dados enquanto aguarda outra, permitindo que duas palavras de dados que chegam em momentos diferentes sejam sincronizadas.

Read Counter

Este dispositivo monitora quantas vezes mais ele precisa endereçar a partir da RAM. Faz isso usando um dispositivo semelhante à trava SR: um T flip-flop. Toda vez que o flip-flop T recebe uma entrada, ele muda de estado: se estava ligado, desliga e vice-versa. Quando o flip-flop T é ativado e desativado, ele envia um pulso de saída, que pode ser alimentado em outro flip-flop T para formar um contador de 2 bits.

Para fazer o contador de leitura, precisamos configurar o contador no modo de endereçamento apropriado com duas portas ANT e usar o sinal de saída do contador para decidir para onde direcionar o sinal do relógio: para a ALU ou para a RAM.

Fila de leitura

A fila de leitura precisa acompanhar qual contador de leitura enviou uma entrada para a RAM, para que possa enviar a saída da RAM para o local correto. Para fazer isso, usamos algumas travas SR: uma para cada entrada. Quando um sinal é enviado para a RAM a partir de um contador de leitura, o sinal do relógio é dividido e define a trava SR do contador. A saída da RAM é AND com a trava SR e o sinal de relógio da RAM redefine a trava SR.

ALU

A ALU funciona de maneira semelhante à fila de leitura, na medida em que usa uma trava SR para rastrear para onde enviar um sinal. Primeiro, a trava SR do circuito lógico correspondente ao código de operação da instrução é configurada usando um multiplexador. A seguir, os valores do primeiro e do segundo argumento são ANDed com a trava SR e depois são passados ​​para os circuitos lógicos. O sinal do relógio redefine a trava à medida que passa, para que a ALU possa ser usada novamente. (A maioria dos circuitos é concentrada, e uma tonelada de gerenciamento de atraso é inserida, então parece uma bagunça)

RAM

A RAM foi a parte mais complicada deste projeto. Exigia um controle muito específico sobre cada trava SR que armazenava dados. Para leitura, o endereço é enviado para um multiplexador e enviado para as unidades de RAM. As unidades de RAM emitem os dados armazenados em paralelo, que são convertidos em serial e emitidos. Para escrever, o endereço é enviado para um multiplexador diferente, os dados a serem gravados são convertidos de serial para paralelo, e as unidades de RAM propagam o sinal pela RAM.

Cada unidade de RAM de 22x22 metapixels possui esta estrutura básica:

Reunindo toda a RAM, temos algo parecido com isto:

Juntando tudo

Usando todos esses componentes e a arquitetura geral do computador descrita na Visão geral , podemos construir um computador em funcionamento!

Downloads: - Computador Tetris finalizado - Script de criação de ROM, computador vazio e computador de localização principal

Parte 4: QFTASM e Cogol

Visão geral da arquitetura

Em resumo, nosso computador possui uma arquitetura RISC Harvard assíncrona de 16 bits. Ao construir um processador manualmente, uma arquitetura RISC ( computador com conjunto de instruções reduzido ) é praticamente um requisito. No nosso caso, isso significa que o número de códigos de operação é pequeno e, muito mais importante, que todas as instruções são processadas de maneira muito semelhante.

Para referência, o computador Wireworld usou uma arquitetura acionada por transporte , na qual a única instrução era MOVe os cálculos eram executados escrevendo / lendo registros especiais. Embora esse paradigma leve a uma arquitetura muito fácil de implementar, o resultado também é inutilizável: todas as operações aritméticas / lógicas / condicionais requerem três instruções. Ficou claro para nós que queríamos criar uma arquitetura muito menos esotérica.

Para manter nosso processador simples e aumentar a usabilidade, tomamos várias decisões importantes de design:

• Sem registros. Cada endereço na RAM é tratado da mesma forma e pode ser usado como qualquer argumento para qualquer operação. De certa forma, isso significa que toda a RAM pode ser tratada como registradora. Isso significa que não há instruções especiais de carregamento / armazenamento.
• Na mesma linha, mapeamento de memória. Tudo o que poderia ser gravado ou lido em compartilha um esquema de endereçamento unificado. Isso significa que o contador de programa (PC) é o endereço 0, e a única diferença entre instruções regulares e instruções de controle de fluxo é que as instruções de controle de fluxo usam o endereço 0.
• Os dados são de série na transmissão, paralelos no armazenamento. Devido à natureza baseada em "elétrons" do nosso computador, a adição e subtração são significativamente mais fáceis de implementar quando os dados são transmitidos na forma serial little-endian (bit menos significativo primeiro). Além disso, os dados seriais eliminam a necessidade de barramentos de dados complicados, que são realmente amplos e complicados de tempo adequadamente (para que os dados permaneçam juntos, todas as "faixas" do barramento devem experimentar o mesmo atraso de viagem).
• Arquitetura de Harvard, significando uma divisão entre memória de programa (ROM) e memória de dados (RAM). Embora isso reduza a flexibilidade do processador, isso ajuda na otimização do tamanho: a duração do programa é muito maior que a quantidade de RAM necessária, para que possamos dividir o programa em ROM e depois nos concentrar na compactação. , o que é muito mais fácil quando é somente leitura.
• Largura de dados de 16 bits. Essa é a menor potência de duas que é mais larga que uma placa Tetris padrão (10 blocos). Isso nos fornece um intervalo de dados de -32768 a +32767 e um comprimento máximo de programa de 65536 instruções. (2 ^ 8 = 256 instruções é suficiente para a maioria das coisas simples que podemos querer que um processador de brinquedo faça, mas não o Tetris.)
• Design assíncrono. Em vez de ter um relógio central (ou, equivalentemente, vários relógios) ditando o tempo do computador, todos os dados são acompanhados por um "sinal de relógio" que viaja em paralelo com os dados enquanto circula pelo computador. Certos caminhos podem ser mais curtos que outros e, embora isso represente dificuldades para um design com relógio central, um design assíncrono pode lidar facilmente com operações de tempo variável.
• Todas as instruções são do mesmo tamanho. Consideramos que uma arquitetura na qual cada instrução possui 1 código de operação com 3 operandos (destino do valor-valor) foi a opção mais flexível. Isso inclui operações de dados binários e movimentos condicionais.
• Sistema de modo de endereçamento simples. Ter uma variedade de modos de endereçamento é muito útil para dar suporte a itens como matrizes ou recursão. Conseguimos implementar vários modos importantes de endereçamento com um sistema relativamente simples.

Uma ilustração da nossa arquitetura está contida no post de visão geral.

Funcionalidade e operações da ULA

A partir daqui, era uma questão de determinar qual funcionalidade nosso processador deveria ter. Foi dada atenção especial à facilidade de implementação, bem como à versatilidade de cada comando.

Movimentos Condicionais

Movimentos condicionais são muito importantes e servem como fluxo de controle em pequena e grande escala. "Pequena escala" refere-se à sua capacidade de controlar a execução de uma movimentação de dados específica, enquanto "grande escala" refere-se ao seu uso como uma operação de salto condicional para transferir o fluxo de controle para qualquer trecho de código arbitrário. Não há operações de salto dedicadas porque, devido ao mapeamento de memória, uma movimentação condicional pode copiar dados para a RAM comum e copiar um endereço de destino para o PC. Também optamos por renunciar a movimentos incondicionais e saltos incondicionais por um motivo semelhante: ambos podem ser implementados como um movimento condicional com uma condição codificada como TRUE.

Optamos por ter dois tipos diferentes de movimentos condicionais: "mova se não for zero" ( MNZ) e "mova se for menor que zero" ( MLZ). Funcionalmente, MNZequivale a verificar se algum bit nos dados é 1, enquanto MLZequivale a verificar se o bit de sinal é 1. Eles são úteis para igualdades e comparações, respectivamente. A razão pela qual escolhemos esses dois em detrimento de outros, como "mover se zero" ( MEZ) ou "mover se maior que zero" ( MGZ), é que MEZexigiria a criação de um sinal VERDADEIRO a partir de um sinal vazio, enquanto MGZé uma verificação mais complexa, exigindo o bit de sinal seja 0 enquanto pelo menos um outro bit seja 1.

Aritmética

As próximas instruções mais importantes, em termos de orientação do design do processador, são as operações aritméticas básicas. Como mencionei anteriormente, estamos usando dados seriais little-endian, com a escolha do endianness determinada pela facilidade das operações de adição / subtração. Ao fazer com que o bit menos significativo chegue primeiro, as unidades aritméticas podem acompanhar facilmente o bit de transporte.

Optamos por usar a representação do complemento de 2 para números negativos, pois isso torna a adição e a subtração mais consistentes. Vale a pena notar que o computador Wireworld usou o complemento de 1.

Adição e subtração são a extensão do suporte aritmético nativo do nosso computador (além das mudanças de bits que serão discutidas mais adiante). Outras operações, como multiplicação, são complexas demais para serem tratadas por nossa arquitetura e devem ser implementadas em software.

Operações bit a bit

Nosso processador tem AND, ORe XORinstruções que não o que você esperaria. Em vez de ter uma NOTinstrução, optamos por ter uma instrução "e-não" ( ANT). A dificuldade com a NOTinstrução é novamente que ela deve criar sinal a partir da falta de sinal, o que é difícil com os autômatos celulares. A ANTinstrução retornará 1 apenas se o primeiro bit de argumento for 1 e o segundo bit de argumento for 0. Portanto, NOT xé equivalente a ANT -1 x(assim como XOR -1 x). Além disso, ANTé versátil e tem sua principal vantagem em mascarar: no caso do programa Tetris, o usamos para apagar tetrominoes.

Mudança de bits

As operações de troca de bits são as operações mais complexas manipuladas pela ALU. Eles recebem duas entradas de dados: um valor para mudar e uma quantidade para alterá-lo. Apesar de sua complexidade (devido à quantidade variável de mudança), essas operações são cruciais para muitas tarefas importantes, incluindo as muitas operações "gráficas" envolvidas no Tetris. Mudanças de bits também serviriam de base para algoritmos eficientes de multiplicação / divisão.

Nosso processador possui operações de deslocamento de três bits, "shift left" ( SL), "shift right logic" ( SRL) e "shift right aritmetic" ( SRA). Os dois primeiros turnos de bits ( SLe SRL) preenchem os novos bits com todos os zeros (o que significa que um número negativo deslocado para a direita não será mais negativo). Se o segundo argumento da mudança estiver fora do intervalo de 0 a 15, o resultado será todos os zeros, como seria de esperar. Para o último deslocamento de bits SRA, o deslocamento de bits preserva o sinal da entrada e, portanto, atua como uma verdadeira divisão por dois.

Pipelining de instruções

Agora é a hora de falar sobre alguns dos detalhes da arquitetura. Cada ciclo da CPU consiste nas cinco etapas a seguir:

1. Busque a instrução atual na ROM

O valor atual do PC é usado para buscar a instrução correspondente na ROM. Cada instrução possui um opcode e três operandos. Cada operando consiste em uma palavra de dados e um modo de endereçamento. Essas partes são divididas uma da outra à medida que são lidas na ROM.

O código de operação é de 4 bits para suportar 16 códigos de operação únicos, dos quais 11 são atribuídos:

0000  MNZ    Move if Not Zero
0001  MLZ    Move if Less than Zero
0010  ADD    ADDition
0011  SUB    SUBtraction
0100  AND    bitwise AND
0101  OR     bitwise OR
0110  XOR    bitwise eXclusive OR
0111  ANT    bitwise And-NoT
1000  SL     Shift Left
1001  SRL    Shift Right Logical
1010  SRA    Shift Right Arithmetic
1011  unassigned
1100  unassigned
1101  unassigned
1110  unassigned
1111  unassigned

2. Escreva o resultado (se necessário) da instrução anterior na RAM

Dependendo da condição da instrução anterior (como o valor do primeiro argumento para uma movimentação condicional), uma gravação é executada. O endereço da gravação é determinado pelo terceiro operando da instrução anterior.

É importante observar que a gravação ocorre após a busca das instruções. Isso leva à criação de um slot de atraso de ramificação no qual a instrução imediatamente após uma instrução de ramificação (qualquer operação que grava no PC) é executada em vez da primeira instrução no destino da ramificação.

Em certos casos (como saltos incondicionais), o slot de atraso da ramificação pode ser otimizado. Em outros casos, não pode, e a instrução após uma ramificação deve ser deixada vazia. Além disso, esse tipo de slot de atraso significa que as ramificações devem usar um destino de ramificação 1 endereço menor que a instrução de destino real, para contabilizar o incremento do PC que ocorre.

Em resumo, como a saída da instrução anterior é gravada na RAM após a busca da próxima instrução, os saltos condicionais precisam ter uma instrução em branco após eles, ou o PC não será atualizado corretamente para o salto.

3. Leia os dados para os argumentos da instrução atual da RAM

Como mencionado anteriormente, cada um dos três operandos consiste em uma palavra de dados e um modo de endereçamento. A palavra de dados é 16 bits, a mesma largura que a RAM. O modo de endereçamento é de 2 bits.

Os modos de endereçamento podem ser uma fonte de complexidade significativa para um processador como esse, pois muitos modos de endereçamento no mundo real envolvem cálculos em várias etapas (como adicionar compensações). Ao mesmo tempo, modos de endereçamento versáteis desempenham um papel importante na usabilidade do processador.

Procuramos unificar os conceitos de uso de números codificados como operandos e de endereços de dados como operandos. Isso levou à criação de modos de endereçamento baseados em contador: o modo de endereçamento de um operando é simplesmente um número que representa quantas vezes os dados devem ser enviados em torno de um loop de leitura de RAM. Isso abrange endereçamento imediato, direto, indireto e indireto duplo.

00  Immediate:  A hard-coded value. (no RAM reads)
01  Direct:  Read data from this RAM address. (one RAM read)
10  Indirect:  Read data from the address given at this address. (two RAM reads)
11  Double-indirect: Read data from the address given at the address given by this address. (three RAM reads)

Após essa desreferenciação ser realizada, os três operandos da instrução têm funções diferentes. O primeiro operando é geralmente o primeiro argumento para um operador binário, mas também serve como condição quando a instrução atual é uma movimentação condicional. O segundo operando serve como o segundo argumento para um operador binário. O terceiro operando serve como o endereço de destino para o resultado da instrução.

Como as duas primeiras instruções servem como dados, enquanto a terceira serve como endereço, os modos de endereçamento têm interpretações ligeiramente diferentes, dependendo da posição em que são usadas. Por exemplo, o modo direto é usado para ler dados de um endereço RAM fixo (desde é necessária uma leitura de RAM), mas o modo imediato é usado para gravar dados em um endereço de RAM fixo (já que não são necessárias leituras de RAM).

4. Calcule o resultado

O opcode e os dois primeiros operandos são enviados à ALU para executar uma operação binária. Para as operações aritmética, bit a bit e shift, isso significa executar a operação relevante. Para os movimentos condicionais, isso significa simplesmente retornar o segundo operando.

O opcode e o primeiro operando são usados ​​para calcular a condição, que determina se deve ou não gravar o resultado na memória. No caso de movimentos condicionais, isso significa determinar se algum bit no operando é 1 (para MNZ) ou determinar se o bit de sinal é 1 (para MLZ). Se o opcode não for uma movimentação condicional, a gravação será sempre realizada (a condição é sempre verdadeira).

5. Incremente o contador do programa

Finalmente, o contador do programa é lido, incrementado e gravado.

Devido à posição do incremento do PC entre a leitura da instrução e a gravação da instrução, isso significa que uma instrução que incrementa o PC em 1 é não operacional. Uma instrução que copia o PC para si mesma faz com que a próxima instrução seja executada duas vezes seguidas. Porém, lembre-se de que várias instruções consecutivas do PC podem causar efeitos complexos, incluindo loop infinito, se você não prestar atenção ao pipeline de instruções.

Quest for Tetris Assembly

Criamos uma nova linguagem assembly chamada QFTASM para o nosso processador. Essa linguagem de montagem corresponde 1 a 1 com o código da máquina na ROM do computador.

Qualquer programa QFTASM é escrito como uma série de instruções, uma por linha. Cada linha é formatada assim:

[line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

Opcode List

Como discutido anteriormente, existem onze códigos de operação suportados pelo computador, cada um dos quais com três operandos:

MNZ [test] [value] [dest]  – Move if Not Zero; sets [dest] to [value] if [test] is not zero.
MLZ [test] [value] [dest]  – Move if Less than Zero; sets [dest] to [value] if [test] is less than zero.
ADD [val1] [val2] [dest]   – ADDition; store [val1] + [val2] in [dest].
SUB [val1] [val2] [dest]   – SUBtraction; store [val1] - [val2] in [dest].
AND [val1] [val2] [dest]   – bitwise AND; store [val1] & [val2] in [dest].
OR [val1] [val2] [dest]    – bitwise OR; store [val1] | [val2] in [dest].
XOR [val1] [val2] [dest]   – bitwise XOR; store [val1] ^ [val2] in [dest].
ANT [val1] [val2] [dest]   – bitwise And-NoT; store [val1] & (![val2]) in [dest].
SL [val1] [val2] [dest]    – Shift Left; store [val1] << [val2] in [dest].
SRL [val1] [val2] [dest]   – Shift Right Logical; store [val1] >>> [val2] in [dest]. Doesn't preserve sign.
SRA [val1] [val2] [dest]   – Shift Right Arithmetic; store [val1] >> [val2] in [dest], while preserving sign.

Modos de endereçamento

Cada um dos operandos contém um valor de dados e uma movimentação de endereçamento. O valor dos dados é descrito por um número decimal no intervalo de -32768 a 32767. O modo de endereçamento é descrito por um prefixo de uma letra ao valor dos dados.

mode    name               prefix
0       immediate          (none)
1       direct             A
2       indirect           B
3       double-indirect    C 

Código de exemplo

Sequência de Fibonacci em cinco linhas:

0. MLZ -1 1 1;    initial value
1. MLZ -1 A2 3;   start loop, shift data
2. MLZ -1 A1 2;   shift data
3. MLZ -1 0 0;    end loop
4. ADD A2 A3 1;   branch delay slot, compute next term

Esse código calcula a sequência de Fibonacci, com o endereço de RAM 1 contendo o termo atual. Ele transborda rapidamente após 28657.

Código cinza:

0. MLZ -1 5 1;      initial value for RAM address to write to
1. SUB A1 5 2;      start loop, determine what binary number to covert to Gray code
2. SRL A2 1 3;      shift right by 1
3. XOR A2 A3 A1;    XOR and store Gray code in destination address
4. SUB B1 42 4;     take the Gray code and subtract 42 (101010)
5. MNZ A4 0 0;      if the result is not zero (Gray code != 101010) repeat loop
6. ADD A1 1 1;      branch delay slot, increment destination address

Este programa calcula o código Gray e armazena o código em endereços sucessivos começando no endereço 5. Este programa utiliza vários recursos importantes, como endereçamento indireto e um salto condicional. Ele para quando o código Gray resultante é o 101010que ocorre na entrada 51 no endereço 56.

Intérprete Online

El'endia Starman criou um intérprete online muito útil aqui . Você é capaz de percorrer o código, definir pontos de interrupção, executar gravações manuais na RAM e visualizar a RAM como uma exibição.

Cogol

Uma vez definidas a arquitetura e a linguagem assembly, o próximo passo no lado "software" do projeto foi a criação de uma linguagem de nível superior, algo adequado para o Tetris. Assim, eu criei a Cogol . O nome é um trocadilho com "COBOL" e um acrônimo para "C of Game of Life", embora seja interessante notar que Cogol é para C o que nosso computador é para um computador real.

O Cogol existe em um nível logo acima da linguagem assembly. Geralmente, a maioria das linhas de um programa Cogol corresponde a uma única linha de montagem, mas existem alguns recursos importantes da linguagem:

• Os recursos básicos incluem variáveis ​​nomeadas com atribuições e operadores que possuem sintaxe mais legível. Por exemplo, ADD A1 A2 3torna-se z = x + y;, com o compilador, mapeando variáveis ​​para endereços.
• Looping construções, tais como if(){}, while(){}e do{}while();de modo que o compilador alças ramificação.
• Matrizes unidimensionais (com aritmética de ponteiro), que são usadas para a placa Tetris.
• Sub-rotinas e uma pilha de chamadas. Eles são úteis para impedir a duplicação de grandes blocos de código e para oferecer suporte à recursão.

O compilador (que escrevi do zero) é muito básico / ingênuo, mas tentei otimizar manualmente várias construções de linguagem para obter um curto comprimento de programa compilado.

Aqui estão algumas breves visões gerais de como os vários recursos de idioma funcionam:

Tokenização

O código-fonte é tokenizado linearmente (passagem única), usando regras simples sobre quais caracteres podem ficar adjacentes a um token. Quando é encontrado um personagem que não pode ser adjacente ao último caractere do token atual, o token atual é considerado completo e o novo personagem inicia um novo token. Alguns caracteres (como {ou ,) não podem ser adjacentes a outros caracteres e, portanto, são seus próprios tokens. Outros (como >ou =) só são permitidos a ficar adjacente a outros caracteres dentro da sua classe, e podem, assim, formar fichas como >>>, ==ou >=, mas não gosta =2. Os caracteres de espaço em branco forçam um limite entre os tokens, mas não são incluídos no resultado. O personagem mais difícil de tokenizar é- porque pode representar subtração e negação unária e, portanto, requer um revestimento especial.

Análise

A análise também é feita de uma única maneira. O compilador possui métodos para lidar com cada uma das diferentes construções de idioma, e os tokens são retirados da lista de tokens global à medida que são consumidos pelos vários métodos do compilador. Se o compilador vir um token que não espera, ele gera um erro de sintaxe.

Alocação Global de Memória

O compilador atribui a cada variável global (palavra ou matriz) seu próprio endereço de RAM designado. É necessário declarar todas as variáveis ​​usando a palavra-chave mypara que o compilador saiba alocar espaço para ela. Muito mais legal do que as variáveis ​​globais nomeadas é o gerenciamento da memória do endereço de rascunho. Muitas instruções (principalmente condicionais e muitos acessos à matriz) requerem endereços temporários temporários para armazenar cálculos intermediários. Durante o processo de compilação, o compilador aloca e desaloca endereços temporários, conforme necessário. Se o compilador precisar de mais endereços temporários, ele dedicará mais RAM como endereços temporários. Eu acredito que é típico para um programa exigir apenas alguns endereços temporários, embora cada endereço temporário seja usado muitas vezes.

IF-ELSE Afirmações

A sintaxe para if-elseinstruções é o formulário C padrão:

other code
if (cond) {
  first body
} else {
  second body
}
other code

Quando convertido para QFTASM, o código é organizado da seguinte maneira:

other code
condition test
conditional jump
first body
unconditional jump
second body (conditional jump target)
other code (unconditional jump target)

Se o primeiro corpo for executado, o segundo corpo será pulado. Se o primeiro corpo for pulado, o segundo corpo será executado.

Na montagem, um teste de condição geralmente é apenas uma subtração, e o sinal do resultado determina se é necessário dar um salto ou executar o corpo. Uma MLZinstrução é usada para lidar com desigualdades como >ou <=. Uma MNZinstrução é usada para manipular ==, uma vez que salta sobre o corpo quando a diferença não é zero (e, portanto, quando os argumentos não são iguais). Condicionais de múltiplas expressões não são suportadas no momento.

Se a elseinstrução for omitida, o salto incondicional também será omitido e o código QFTASM se parecerá com o seguinte:

other code
condition test
conditional jump
body
other code (conditional jump target)

WHILE Afirmações

A sintaxe para whileinstruções também é o formulário C padrão:

other code
while (cond) {
  body
}
other code

Quando convertido para QFTASM, o código é organizado da seguinte maneira:

other code
unconditional jump
body (conditional jump target)
condition test (unconditional jump target)
conditional jump
other code

O teste da condição e o salto condicional estão no final do bloco, o que significa que são reexecutados após cada execução do bloco. Quando a condição retorna false, o corpo não é repetido e o loop termina. Durante o início da execução do loop, o fluxo de controle salta sobre o corpo do loop para o código de condição, para que o corpo nunca seja executado se a condição for falsa na primeira vez.

Uma MLZinstrução é usada para lidar com desigualdades como >ou <=. Diferentemente das ifinstruções, uma MNZinstrução é usada para manipular !=, uma vez que salta para o corpo quando a diferença não é zero (e, portanto, quando os argumentos não são iguais).

DO-WHILE Afirmações

A única diferença entre whilee do-whileé que o do-whilecorpo do loop a não é pulado inicialmente, por isso é sempre executado pelo menos uma vez. Geralmente uso do-whileinstruções para salvar algumas linhas de código de montagem quando sei que o loop nunca precisará ser ignorado completamente.

Matrizes

Matrizes unidimensionais são implementadas como blocos contíguos de memória. Todas as matrizes são de tamanho fixo com base em suas declarações. As matrizes são declaradas da seguinte forma:

my alpha[3];               # empty array
my beta[11] = {3,2,7,8};   # first four elements are pre-loaded with those values

Para a matriz, este é um possível mapeamento de RAM, mostrando como os endereços 15-18 são reservados para a matriz:

15: alpha
16: alpha[0]
17: alpha[1]
18: alpha[2]

O endereço rotulado alphaé preenchido com um ponteiro para o local de alpha[0], portanto, no caso em que o endereço 15 contém o valor 16. A alphavariável pode ser usada dentro do código Cogol, possivelmente como ponteiro de pilha, se você desejar usar esse array como pilha. .

O acesso aos elementos de uma matriz é feito com a array[index]notação padrão . Se o valor de indexfor uma constante, essa referência será automaticamente preenchida com o endereço absoluto desse elemento. Caso contrário, ele executa alguma aritmética do ponteiro (apenas adição) para encontrar o endereço absoluto desejado. Também é possível aninhar a indexação, como alpha[beta[1]].

Sub-rotinas e chamadas

Sub-rotinas são blocos de código que podem ser chamados de vários contextos, impedindo a duplicação de código e permitindo a criação de programas recursivos. Aqui está um programa com uma sub-rotina recursiva para gerar números de Fibonacci (basicamente o algoritmo mais lento):

# recursively calculate the 10th Fibonacci number
call display = fib(10).sum;
sub fib(cur,sum) {
  if (cur <= 2) {
    sum = 1;
    return;
  }
  cur--;
  call sum = fib(cur).sum;
  cur--;
  call sum += fib(cur).sum;
}

Uma sub-rotina é declarada com a palavra-chave sube uma sub-rotina pode ser colocada em qualquer lugar dentro do programa. Cada sub-rotina pode ter várias variáveis ​​locais, que são declaradas como parte de sua lista de argumentos. Esses argumentos também podem receber valores padrão.

Para lidar com chamadas recursivas, as variáveis ​​locais de uma sub-rotina são armazenadas na pilha. A última variável estática na RAM é o ponteiro da pilha de chamadas e toda a memória depois serve como a pilha de chamadas. Quando uma sub-rotina é chamada, ele cria um novo quadro na pilha de chamadas, que inclui todas as variáveis ​​locais e o endereço de retorno (ROM). Cada sub-rotina no programa recebe um único endereço de RAM estático para servir como ponteiro. Esse ponteiro fornece o local da chamada "atual" da sub-rotina na pilha de chamadas. A referência a uma variável local é feita usando o valor desse ponteiro estático mais um deslocamento para fornecer o endereço dessa variável local específica. Também está contido na pilha de chamadas o valor anterior do ponteiro estático. Aqui'

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

fib map:
0: return
1: previous_call
2: cur
3: sum

Uma coisa interessante sobre as sub-rotinas é que elas não retornam nenhum valor específico. Em vez disso, todas as variáveis ​​locais da sub-rotina podem ser lidas após a execução da sub-rotina, portanto, uma variedade de dados pode ser extraída de uma chamada de sub-rotina. Isso é feito armazenando o ponteiro para a chamada específica da sub-rotina, que pode ser usada para recuperar qualquer uma das variáveis ​​locais do quadro de pilha (recentemente desalocado).

Existem várias maneiras de chamar uma sub-rotina, todas usando a callpalavra-chave:

call fib(10);   # subroutine is executed, no return vaue is stored

call pointer = fib(10);   # execute subroutine and return a pointer
display = pointer.sum;    # access a local variable and assign it to a global variable

call display = fib(10).sum;   # immediately store a return value

call display += fib(10).sum;   # other types of assignment operators can also be used with a return value

Qualquer número de valores pode ser fornecido como argumento para uma chamada de sub-rotina. Qualquer argumento não fornecido será preenchido com seu valor padrão, se houver. Um argumento que não é fornecido e não possui valor padrão não é limpo (para salvar instruções / tempo), portanto, pode assumir qualquer valor no início da sub-rotina.

Os ponteiros são uma maneira de acessar várias variáveis ​​locais da sub-rotina, embora seja importante observar que o ponteiro é apenas temporário: os dados para os quais o ponteiro aponta serão destruídos quando outra chamada de sub-rotina for feita.

Etiquetas de depuração

Qualquer {...}bloco de código em um programa Cogol pode ser precedido por um rótulo descritivo de várias palavras. Esse rótulo é anexado como um comentário no código de montagem compilado e pode ser muito útil para depuração, pois facilita a localização de partes específicas do código.

Otimização do slot de atraso de ramificação

Para melhorar a velocidade do código compilado, o compilador Cogol realiza uma otimização realmente básica do slot de atraso como uma passagem final sobre o código QFTASM. Para qualquer salto incondicional com um slot de atraso de ramificação vazio, o slot de atraso pode ser preenchido pela primeira instrução no destino do salto e o destino do salto é incrementado em um para apontar para a próxima instrução. Isso geralmente salva um ciclo cada vez que um salto incondicional é realizado.

Escrevendo o código Tetris em Cogol

O programa final do Tetris foi escrito em Cogol, e o código fonte está disponível aqui . O código QFTASM compilado está disponível aqui . Por conveniência, é fornecido um link permanente aqui: Tetris no QFTASM . Como o objetivo era jogar golfe no código de montagem (não no código Cogol), o código Cogol resultante é pesado. Muitas partes do programa normalmente seriam localizadas em sub-rotinas, mas essas sub-rotinas eram realmente curtas o suficiente para duplicar as instruções salvas do código nascallafirmações. O código final possui apenas uma sub-rotina, além do código principal. Além disso, muitas matrizes foram removidas e substituídas por uma lista equivalentemente longa de variáveis ​​individuais ou por muitos números codificados no programa. O código QFTASM final compilado tem menos de 300 instruções, embora seja apenas um pouco mais longo que a própria fonte Cogol.

Parte 5: Assembléia, Tradução e o Futuro

Com o nosso programa de montagem do compilador, é hora de montar uma ROM para o computador Varlife e traduzir tudo em um grande padrão GoL!

Montagem

A montagem do programa de montagem em uma ROM é feita da mesma maneira que na programação tradicional: cada instrução é traduzida em um equivalente binário e, em seguida, é concatenada em um grande blob binário que chamamos de executável. Para nós, a única diferença é que o blob binário precisa ser convertido em circuitos Varlife e conectado ao computador.

K Zhang escreveu o CreateROM.py , um script Python para Golly que faz o assembly e a tradução. É bem simples: pega um programa de montagem da área de transferência, monta-o em um binário e converte esse binário em circuito. Aqui está um exemplo com um testador de primalidade simples incluído no script:

#0. MLZ -1 3 3;
#1. MLZ -1 7 6; preloadCallStack
#2. MLZ -1 2 1; beginDoWhile0_infinite_loop
#3. MLZ -1 1 4; beginDoWhile1_trials
#4. ADD A4 2 4;
#5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
#6. SUB A5 A4 5;
#7. SUB 0 A5 2;
#8. MLZ A2 5 0;
#9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
#10. MLZ A5 3 0;
#11. MNZ 0 0 0; endDoWhile1_trials
#12. SUB A4 A3 2;
#13. MNZ A2 15 0; beginIf3_prime_found
#14. MNZ 0 0 0;
#15. MLZ -1 A3 1; endIf3_prime_found
#16. ADD A3 2 3;
#17. MLZ -1 3 0;
#18. MLZ -1 1 4; endDoWhile0_infinite_loop

Isso produz o seguinte binário:

0000000000000001000000000000000000010011111111111111110001
0000000000000000000000000000000000110011111111111111110001
0000000000000000110000000000000000100100000000000000110010
0000000000000000010100000000000000110011111111111111110001
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011110100000000000000100000
0000000000000000100100000000000000110100000000000001000011
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000110100000000000001010001
0000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000001010100000000000000100001
0000000000000000100100000000000001010000000000000000000011
0000000000000001010100000000000001000100000000000001010011
0000000000000001010100000000000000110011111111111111110001
0000000000000001000000000000000000100100000000000001000010
0000000000000001000000000000000000010011111111111111110001
0000000000000000010000000000000000100011111111111111110001
0000000000000001100000000000000001110011111111111111110001
0000000000000000110000000000000000110011111111111111110001

Quando traduzido para os circuitos Varlife, fica assim:

A ROM é então conectada ao computador, que forma um programa totalmente funcional no Varlife. Mas ainda não terminamos ...

Tradução para Game of Life

Durante todo esse tempo, estivemos trabalhando em várias camadas de abstração acima da base do Game of Life. Mas agora, é hora de abrir a cortina da abstração e traduzir nosso trabalho em um padrão de Jogo da Vida. Como mencionado anteriormente, estamos usando o OTCA Metapixel como base para o Varlife. Portanto, o passo final é converter cada célula no Varlife em um metapixel em Game of Life.

Felizmente, Golly vem com um script ( metafier.py ) que pode converter padrões em diferentes conjuntos de regras em padrões de Jogo da Vida através do OTCA Metapixel. Infelizmente, ele foi projetado apenas para converter padrões com um único conjunto de regras global, para que não funcione no Varlife. Eu escrevi uma versão modificada que aborda esse problema, para que a regra para cada metapixel seja gerada célula por célula para o Varlife.

Portanto, nosso computador (com a ROM do Tetris) possui uma caixa delimitadora de 1.436 x 5.082. Das 7.297.752 células dessa caixa, 6.075.811 são de espaço vazio, deixando uma contagem real da população de 1.221.941. Cada uma dessas células precisa ser traduzida em um metapixel OTCA, que possui uma caixa delimitadora de 2048x2048 e uma população de 64.691 (para um metapixel ON) ou 23.920 (para um metapixel OFF). Isso significa que o produto final terá uma caixa delimitadora de 2.940.928 x 10.407.936 (mais alguns milhares extras para as bordas dos metapixels), com uma população entre 29.228.828.720 e 79.048.585.231. Com 1 bit por célula ativa, são necessários entre 27 e 74 GiB para representar o computador inteiro e a ROM.

Incluí esses cálculos aqui porque deixei de executá-los antes de iniciar o script e muito rapidamente fiquei sem memória no meu computador. Após um killcomando de pânico , fiz uma modificação no script da metafier. A cada 10 linhas de metapixels, o padrão é salvo no disco (como um arquivo RLE compactado em gzip) e a grade é liberada. Isso adiciona tempo de execução extra à tradução e usa mais espaço em disco, mas mantém o uso da memória dentro de limites aceitáveis. Como o Golly usa um formato RLE estendido que inclui a localização do padrão, isso não adiciona mais complexidade ao carregamento do padrão - basta abrir todos os arquivos de padrão na mesma camada.

K Zhang criou esse trabalho e criou um script de metafier mais eficiente que utiliza o formato de arquivo MacroCell, que é muito mais eficiente que o RLE para padrões grandes. Esse script roda consideravelmente mais rápido (alguns segundos, comparado a várias horas do script metafier original), cria uma saída muito menor (121 KB versus 1,7 GB) e pode metafy o computador inteiro e a ROM de uma só vez sem usar uma quantidade enorme de memória. Aproveita o fato de que os arquivos MacroCell codificam árvores que descrevem os padrões. Usando um arquivo de modelo personalizado, os metapixels são pré-carregados na árvore e, após alguns cálculos e modificações para detecção de vizinhos, o padrão Varlife pode ser simplesmente anexado.

O arquivo de padrão de todo o computador e a ROM do Game of Life podem ser encontrados aqui .

O futuro do projeto

Agora que criamos o Tetris, terminamos, certo? Nem mesmo perto. Temos várias outras metas para este projeto em que estamos trabalhando:

• muddyfish e Kritixi Lithos continuam o trabalho na linguagem de nível superior que é compilada no QFTASM.
• El'endia Starman está trabalhando em atualizações para o intérprete QFTASM online.
• O quartata está trabalhando em um back-end do GCC, que permitirá a compilação de códigos C e C ++ independentes (e potencialmente outros idiomas, como Fortran, D ou Objective-C) no QFTASM via GCC. Isso permitirá que programas mais sofisticados sejam criados em uma linguagem mais familiar, embora sem uma biblioteca padrão.
• Um dos maiores obstáculos que precisamos superar antes que possamos progredir é o fato de que nossas ferramentas não podem emitir código independente da posição (por exemplo, saltos relativos). Sem o PIC, não podemos fazer nenhum vínculo e, portanto, perdemos as vantagens de poder vincular a bibliotecas existentes. Estamos trabalhando para tentar encontrar uma maneira de fazer o PIC corretamente.
• Estamos discutindo o próximo programa que queremos escrever para o computador QFT. Agora, Pong parece um bom objetivo.

Parte 6: O compilador mais recente do QFTASM

Embora o Cogol seja suficiente para uma implementação rudimentar do Tetris, é muito simples e muito baixo para a programação de uso geral em um nível facilmente legível. Começamos a trabalhar em um novo idioma em setembro de 2016. O progresso no idioma foi lento devido a bugs difíceis de entender e à vida real.

Criamos uma linguagem de baixo nível com sintaxe semelhante ao Python, incluindo um sistema de tipos simples, sub-rotinas que suportam operadores de recursão e inline. O compilador de texto para QFTASM foi criado com 4 etapas: o tokeniser, a árvore gramatical, um compilador de alto nível e um compilador de baixo nível.

O tokeniser

O desenvolvimento foi iniciado usando o Python usando a biblioteca de tokeniser integrada, o que significa que essa etapa foi bastante simples. Apenas algumas alterações na saída padrão foram necessárias, incluindo a remoção de comentários (mas não #includes).

A árvore gramatical

A árvore gramatical foi criada para ser facilmente extensível sem a necessidade de modificar nenhum código fonte.

A estrutura da árvore é armazenada em um arquivo XML que inclui a estrutura dos nós que podem compor a árvore e como eles são feitos com outros nós e tokens.

A gramática precisava oferecer suporte a nós repetidos e opcionais. Isso foi alcançado através da introdução de metatags para descrever como os tokens deveriam ser lidos.

Os tokens gerados são analisados ​​pelas regras da gramática, de forma que a saída forma uma árvore de elementos gramaticais como subs e generic_variables, que por sua vez contêm outros elementos e tokens da gramática.

Compilação em código de alto nível

Cada recurso do idioma precisa ser compilado em construções de alto nível. Estes incluem assign(a, 12) e call_subroutine(is_prime, call_variable=12, return_variable=temp_var). Recursos como o embutimento de elementos são executados neste segmento. Eles são definidos como operators e são especiais, pois são incorporados sempre que um operador como +ou %é usado. Por causa disso, eles são mais restritos que o código normal - eles não podem usar seu próprio operador nem qualquer operador que dependa do que está sendo definido.

Durante o processo inlining, as variáveis ​​internas são substituídas pelas chamadas. Isso, na verdade, transforma

operator(int a + int b) -> int c
    return __ADD__(a, b)
int i = 3+3

para dentro

int i = __ADD__(3, 3)

Esse comportamento, no entanto, pode ser prejudicial e propenso a erros se a variável de entrada e as variáveis ​​de saída apontarem para o mesmo local na memória. Para usar o comportamento 'mais seguro', a unsafepalavra - chave ajusta o processo de compilação, de modo que variáveis ​​adicionais sejam criadas e copiadas para e da linha, conforme necessário.

Variáveis ​​zero e operações complexas

Operações matemáticas como a += (b + c) * 4não podem ser calculadas sem o uso de células de memória extras. O compilador de alto nível lida com isso, separando as operações em diferentes seções:

scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

Isso introduz o conceito de variáveis ​​de rascunho que são usadas para armazenar informações intermediárias de cálculos. Eles são alocados conforme necessário e desalocados no conjunto geral, uma vez finalizados. Isso diminui o número de locais de memória temporária necessários para o uso. Variáveis ​​de risco são consideradas globais.

Cada sub-rotina possui sua própria VariableStore para manter uma referência a todas as variáveis ​​que a sub-rotina usa, bem como seu tipo. No final da compilação, eles são convertidos em deslocamentos relativos desde o início da loja e recebem os endereços reais na RAM.

Estrutura RAM

Program counter
Subroutine locals
Operator locals (reused throughout)
Scratch variables
Result variable
Stack pointer
Stack
...

Compilação de baixo nível

As únicas coisas que o compilador de baixo nível tem de lidar são sub, call_sub, return, assign, ife while. Esta é uma lista muito reduzida de tarefas que podem ser traduzidas em instruções QFTASM mais facilmente.

sub

Isso localiza o início e o fim de uma sub-rotina nomeada. O compilador de baixo nível adiciona rótulos e, no caso da mainsub - rotina, adiciona uma instrução de saída (pula para o final da ROM).

if e while

Tanto o whilee ifintérpretes de baixo nível são bastante simples: eles recebem ponteiros para as suas condições e salto dependendo deles. whileos loops são ligeiramente diferentes, pois são compilados como

...
condition
jump to check
code
condition
if condtion: jump to code
...

call_sub e return

Diferentemente da maioria das arquiteturas, o computador para o qual estamos compilando não tem suporte de hardware para empurrar e saltar de uma pilha. Isso significa que empurrar e pular da pilha leva duas instruções. No caso de popping, decrementamos o ponteiro da pilha e copiamos o valor para um endereço. No caso de pressionar, copiamos um valor de um endereço para o endereço no ponteiro da pilha atual e, em seguida, incrementamos.

Todos os locais de uma sub-rotina são armazenados em um local fixo na RAM, determinado em tempo de compilação. Para fazer a recursão funcionar, todos os locais de uma função são colocados na pilha no início de uma chamada. Em seguida, os argumentos para a sub-rotina são copiados para sua posição na loja local. O valor do endereço de retorno é colocado na pilha e a sub-rotina é executada.

Quando uma returninstrução é encontrada, a parte superior da pilha é disparada e o contador do programa é definido para esse valor. Os valores para os locais da sub-rotina de chamada são retirados da pilha e na posição anterior.

assign

As atribuições de variáveis ​​são as coisas mais fáceis de compilar: elas pegam uma variável e um valor e compilam na única linha: MLZ -1 VALUE VARIABLE

Atribuindo destinos de salto

Finalmente, o compilador elabora os alvos de salto para os rótulos anexados às instruções. A posição absoluta dos rótulos é determinada e, em seguida, as referências a esses rótulos são substituídas por esses valores. Os rótulos são removidos do código e, finalmente, os números das instruções são adicionados ao código compilado.

Exemplo de compilação passo a passo

Agora que passamos por todas as etapas, vamos passar por um processo de compilação real para um programa real, passo a passo.

#include stdint

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, simples o suficiente. Deveria ser óbvio que, no final do programa, a = 8, b = 12, c = 96. Em primeiro lugar, vamos incluir as partes relevantes de stdint.txt:

operator (int a + int b) -> int
    return __ADD__(a, b)

operator (int a - int b) -> int
    return __SUB__(a, b)

operator (int a < int b) -> bool
    bool rtn = 0
    rtn = __MLZ__(a-b, 1)
    return rtn

unsafe operator (int a * int b) -> int
    int rtn = 0
    for (int i = 0; i < b; i+=1)
        rtn += a
    return rtn

sub main
    int a = 8
    int b = 12
    int c = a * b

Ok, um pouco mais complicado. Vamos para o tokeniser e ver o que sai. Nesse estágio, teremos apenas um fluxo linear de tokens sem nenhuma forma de estrutura

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP )
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT     
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP )
...

Agora, todos os tokens passam pelo analisador de gramática e produz uma árvore com os nomes de cada uma das seções. Isso mostra a estrutura de alto nível conforme lida pelo código.

GrammarTree file
 'stmts': [GrammarTree stmts_0
  '_block_name': 'inline'
  'inline': GrammarTree inline
   '_block_name': 'two_op'
   'type_var': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'a'
    '_global': False

   'operator': GrammarTree operator
    '_block_name': '+'

   'type_var_2': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'b'
    '_global': False
   'rtn_type': 'int'
   'stmts': GrammarTree stmts
    ...

Essa árvore gramatical configura as informações a serem analisadas pelo compilador de alto nível. Inclui informações como tipos de estrutura e atributos de uma variável. A árvore gramatical pega essas informações e atribui as variáveis ​​necessárias para as sub-rotinas. A árvore também insere todas as linhas.

('sub', 'start', 'main')
('assign', int main_a, 8)
('assign', int main_b, 12)
('assign', int op(*:rtn), 0)
('assign', int op(*:i), 0)
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'start', 1, 'for')
('call_sub', '__ADD__', [int op(*:rtn), int main_a], int op(*:rtn))
('call_sub', '__ADD__', [int op(*:i), 1], int op(*:i))
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'end', 1, global bool scratch_2)
('assign', int main_c, int op(*:rtn))
('sub', 'end', 'main')

Em seguida, o compilador de baixo nível precisa converter essa representação de alto nível em código QFTASM. As variáveis ​​são localizadas na RAM da seguinte forma:

int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int <result>
global int <stack>

As instruções simples são compiladas. Finalmente, os números de instruções são adicionados, resultando em código QFTASM executável.

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

A sintaxe

Agora que temos a linguagem básica, precisamos escrever um pequeno programa nela. Estamos usando recuo como o Python, dividindo blocos lógicos e controlando o fluxo. Isso significa que espaço em branco é importante para nossos programas. Todo programa completo possui uma mainsub - rotina que funciona exatamente como a main()função em linguagens do tipo C. A função é executada no início do programa.

Variáveis ​​e tipos

Quando as variáveis ​​são definidas pela primeira vez, elas precisam ter um tipo associado a elas. Os tipos atualmente definidos são inte boolcom a sintaxe para matrizes definidas, mas não o compilador.

Bibliotecas e operadores

stdint.txtEstá disponível uma biblioteca chamada que define os operadores básicos. Se isso não estiver incluído, mesmo operadores simples não serão definidos. Podemos usar esta biblioteca com #include stdint. stdintdefine operadores como +, >>e even *e %, nenhum dos quais são opcodes diretos do QFTASM.

O idioma também permite que os opcodes do QFTASM sejam chamados diretamente __OPCODENAME__.

A adição em stdinté definida como

operator (int a + int b) -> int
    return __ADD__(a, b)

O que define o que o +operador faz quando recebe dois ints.