Show HN: um computador programável feito com portas NAND

NAND: um computador completo de 16 bits Turing-equivalente implementado na web

• NAND é um computador de 16 bits Turing-equivalente emulado na web usando apenas portas NAND e clock
• NAND tem sua própria CPU, linguagem de máquina, assembly, montador, linguagem de VM, tradutor de VM, linguagem de programação, compilador, IDE e UI
• NAND é baseado na plataforma Jack-VM-Hack especificada no curso Nand to Tetris e no livro relacionado

Exemplos de programas

Average

• Um programa simples que recebe números como entrada e calcula a média
• Mostra fluxo de controle, operações aritméticas, I/O e alocação dinâmica de memória

Pong

• O jogo Pong mostra o modelo orientado a objetos da linguagem
• Use as teclas de seta para mover a raquete para a esquerda e para a direita e rebater a bola
• A cada rebatida, a raquete fica menor, e o jogo termina quando a bola cai na parte de baixo da tela

2048

• O jogo 2048 mostra recursão e lógica de aplicação complexa
• Use as teclas de seta para mover os números em uma grade 4x4
• Números iguais se fundem quando se encontram
• Você vence ao alcançar o bloco 2048, mas pode continuar acumulando mais
• O jogo termina quando o tabuleiro está cheio e não há mais movimentos possíveis

Overflow

• Um programa que provoca intencionalmente um stack overflow com recursão infinita para escapar da máquina virtual
• Explora o fato de não haver verificações em tempo de execução para evitar stack overflow
• Durante a execução, imprime continuamente o valor do ponteiro da pilha
• Quando a pilha chega ao fim do espaço de memória previsto e invade a memória do heap, as instruções de impressão passam a falhar de forma explosiva

SecretPassword

• Um programa que chama uma função inacessível explorando o fato de o runtime não impedir stack smashing
• É preciso entender o layout dos stack frames do NAND
• Permite ao usuário sobrescrever qualquer endereço de memória com qualquer valor
• Se o endereço de retorno de uma função for sobrescrito com o endereço de outra função, é possível executar código arbitrário
• Se você inserir um local específico de memória e o valor de sobrescrita, obtidos por inspeção manual dos endereços da pilha e do assembly, verá essa ideia funcionar

GeneticAlgorithm

• Entre os muitos componentes do NAND, esta foi a parte que mais tempo levou para desenvolver
• Uma simulação biológica usando aprendizado de máquina simples
• O "cérebro" de cada ponto é um conjunto de vetores de aceleração, que evolui por seleção natural até o alvo
• Em cada geração, pontos que "morreram" mais perto do alvo têm maior probabilidade de serem escolhidos como pais da geração seguinte
• A reprodução sofre mutações no cérebro, simulando de forma efetiva a evolução natural
• Devido a limitações de desempenho, várias técnicas de otimização foram usadas para contornar as restrições do hardware e tornar isso possível

Programando em Jack

• O ponto mais importante ao programar em Jack é que não existe precedência de operadores. Isso pode ser a razão de o programa não funcionar corretamente.
• É preciso explicitar a precedência com parênteses, como em 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

Introdução ao Jack

• NAND exibe toda a sua própria stack tecnológica
• Jack é uma linguagem orientada a objetos com tipagem fraca. Em termos simples, é C com sintaxe de Java
• Vamos aprender com um exemplo

Tipos de dados personalizados

• Jack suporta três tipos básicos: int, char, boolean
• Conforme necessário, isso pode ser expandido com tipos abstratos de dados
• Conhecimentos de programação orientada a objetos se aplicam diretamente
• No exemplo, a classe Point define um ponto abstrato no espaço
• Variáveis field declaram propriedades por instância do tipo de dado
• Ela fornece funções públicas method para manipular pontos, permitindo ao chamador somar pontos ou calcular a distância entre dois pontos
• Todas as variáveis field têm escopo privado. Para acessar essas variáveis, é preciso expô-las por meio de funções method
• É uma convenção que classes de dados definam um método dispose
• Consulte a sintaxe de chamadas function e method

Conversão fraca de tipos

• Foi dito que Jack é fortemente inspirado em Java, mas isso é apenas uma fachada
• Java é uma linguagem com tipagem forte e oferece recursos complexos de tipo como downcasting, polimorfismo e herança
• Já Jack, na prática, só suporta um único inteiro com sinal de 16 bits
• Essa é a principal razão de Jack ter tipagem fraca
• Por isso, o compilador de Jack não se importa se diferentes tipos forem misturados em atribuições e operações
• Jack ainda oferece um modelo orientado a objetos poderoso e funcional
• Isso vai ajudar a entender quando e como fazer conversão de tipos

Gerenciamento manual de memória

• Jack é uma linguagem de gerenciamento manual de memória
• É preciso tomar cuidado para liberar corretamente a memória que não é mais necessária
• Caso contrário, o Jack OS vai considerar que há vazamento de memória
• A prática recomendada é escrever um método dispose para cada classe, encapsulando corretamente a desalocação
• Chamar esse método quando o objeto não for mais necessário ajuda a evitar falta de memória no heap
• Se você já usou outras linguagens com gerenciamento manual de memória, como C, isso será familiar
• A diferença é que o Jack OS armazena arrays e strings no heap, não na pilha
• Veja String.dispose para entender como escrever métodos dispose

Comportamento indefinido

Precedência de operadores

• Isso é tão importante que foi movido para cima

Operadores de maior e menor

• As comparações a > b, a < b em Jack parecem simples, mas nem sempre estão corretas matematicamente
• A máquina virtual as transforma em a - b > 0. O problema é que a - b pode causar overflow
• Como 20000 > -20000 será avaliado? 20000 - (-20000) > 0, ou seja, -25336 > 0, o que resulta em false
• Mas 20000 > -10000 vira 30000 > 0, ou seja, true
• Se a diferença entre os valores absolutos de a e b for maior que 32767, a > b e a < b podem dar resultado errado. Caso contrário, tudo bem
• Isso não é um bug, mas uma incompatibilidade com Nand to Tetris. Esse comportamento não será corrigido para manter a compatibilidade

-32768

• -32768 é o único número com a propriedade peculiar de que -(-32768) = -32768. É um singleton sem par positivo
• Isso pode causar erros lógicos aparentemente inválidos
• Porque -x é tratado internamente como ~(x-1)
• Se x receber -32768, então x-1 = ~x. Assim, ~(~x) volta a ser x
• O que aconteceu? Como NAND é uma máquina de 16 bits, subtrair 1 de -32768 produz um resultado em que os bits ficam invertidos
• O importante é lidar com erros lógicos no tratamento do operador de negação
• Verificar o caso de -32768 e tratá-lo adequadamente é responsabilidade do programador

Chamada de função com argumentos insuficientes

• Um comportamento indefinido óbvio que dispensa explicação

Conversão de tipo inadequada

• É possível converter uma variável para Array e depois para qualquer tipo
• Chamar um método de instância que não existe causa comportamento indefinido
• O compilador não é inteligente o bastante para detectar isso

Stack overflow

• Consulte o programa Overflow

Modificar stack frames ou registradores internos

• Modificar stack frames ou registradores internos nos endereços 256~2047 e 1~15 pode causar comportamento indefinido
• Em geral isso não é possível, a menos que Memory.poke ou índices negativos de array sejam usados de forma incorreta
• Consulte o programa SecretPassword

Especificações de hardware

• Existe um motivo para a computação de 16 bits ter caído em desuso depois da década de 1970

• Em comparação com 32 bits ou 64 bits, ela tem capacidade de processamento e memória limitadas e não atende às exigências do software moderno

• NAND não é exceção

• Comparado a um MacBook com 16GiB, o NAND tem apenas 4KiB de RAM. Isso é só 0,00002%

• Mesmo assim, ainda é o bastante para nos levar à Lua

• O Jack OS reserva 14.336 endereços de memória do total de 4KiB para o heap. É um número anormalmente pequeno

• Por isso, é muito importante que aplicações em Jack liberem memória de forma eficiente

• Se o plano for ambicioso demais, você pode acabar sem memória no heap e ter de reescrever completamente os tipos de dados e a lógica

• Do total de 4KiB, 8.192 endereços de memória são reservados para a tela

• Cada bit de cada endereço é mapeado linearmente para pixels da tela 512x256. Usa numeração de bits LSb 0

• O endereço de memória 24.576 é reservado para o teclado

• Ele reflete o valor do código ASCII da tecla pressionada

• Mas não se deve acessá-lo diretamente para tratar entrada do usuário. É preciso usar a classe Keyboard e as funções relacionadas fornecidas pelo Jack OS

• O teclado do NAND reconhece ASCII e teclas especiais

• 240 endereços de memória são reservados para variáveis estáticas de classe, e 1.792 para a pilha global

• A menos que haja recursão profunda, esse limite não deve ser um problema

[GN⁺]

Comentários do Hacker News

• É possível entender profundamente os níveis de abstração de um computador por meio do projeto Nand to Tetris
• O kit de computador 6502 do Ben Eater também tem um valor educacional semelhante
• Este projeto tem materiais tão bem organizados que poderiam servir para várias disciplinas universitárias
• No exame de qualificação em hardware de computadores da UC Berkeley, no início dos anos 1990, houve uma questão semelhante que pedia projetar um processador RISC microcodificado e com pipeline usando apenas portas NAND
  • Na época, não era exigido construir de fato; bastava colocar o projeto detalhado no papel
• Este projeto parece semelhante a MarquisdeGeek/gates
• Ao fazer o curso Nand2Tetris, eu queria construir virtualmente algo parecido, e é impressionante ver isso implementado de verdade
  • Isso provavelmente deve ter melhorado bastante a compreensão sobre como os computadores funcionam
• Há quem aponte que, além das portas NAND, também foi usado um clock
• Não cheguei a concluir o Nand2Tetris, mas, como fã, quero examinar este projeto a fundo
• Fico curioso para saber quantas portas NAND foram usadas no total
• Agradecimentos por essa abordagem fiel aos princípios fundamentais