Show HN: Computador programável feito com portas NAND

 (github.com/ArhanChaudhary)
2 pontos por GN⁺ 2024-04-27 | 1 comentários | Compartilhar no WhatsApp
  • NAND é um computador de 16 bits Turing-completo emulado na web, incluindo desde a CPU até IDE e UI com a proposta educacional de ser composto apenas por clock e portas NAND
  • Sua stack própria é baseada na plataforma Jack-VM-Hack, oferecendo CPU, linguagem de máquina, assembly, assembler, linguagem de VM, tradutor de VM, linguagem Jack e compilador
  • Os programas de exemplo incluem Average, Pong e 2048, além de demos de VM escape usando stack overflow e stack smashing, e até o GeneticAlgorithm com machine learning simples
  • Jack é uma linguagem orientada a objetos de tipagem fraca, parecida com Java na sintaxe, mas internamente depende de um único signed 16-bit integer e tem grandes limitações, como ausência de precedência de operadores, gerenciamento manual de memória e comportamento indefinido
  • O projeto não significa que todos os cálculos sejam realmente executados em portas NAND físicas; trata-se de uma implementação educacional e teórica com compiler em TypeScript, tradutor de VM, simulador de lógica de portas NAND em Rust e WebAssembly

A stack completa de computador oferecida pelo NAND

  • NAND é apresentado como sigla de Not A Nand-powered Device, um computador web de 16 bits
  • Ele emula um computador Turing-completo feito de clock e portas NAND, incluindo internamente os seguintes componentes
    • CPU
    • linguagem de máquina
    • linguagem assembly
    • assembler
    • linguagem de máquina virtual
    • tradutor de máquina virtual
    • linguagem de programação
    • compilador
    • IDE
    • interface de usuário
  • A base é a plataforma Jack-VM-Hack do curso Nand to Tetris e de livros relacionados
  • Há um vídeo de demonstração do NAND

Programas de exemplo e demos

  • Average

    • Um programa simples que recebe números e calcula a média
    • Mostra control flow, operações aritméticas, I/O e alocação dinâmica de memória
    • É um programa fornecido pela suíte de software do Nand to Tetris

  • Pong

    • Um jogo de Pong que demonstra o modelo orientado a objetos
    • As setas movem a paddle para a esquerda e para a direita para rebater a bola
    • A paddle encolhe a cada rebatida, e o jogo termina quando a bola toca a parte de baixo da tela
    • É um programa fornecido pela suíte de software do Nand to Tetris

  • 2048

    • Um jogo 2048 que demonstra recursion e lógica de aplicação complexa
    • Em uma grid 4x4, as setas movem os números, e números iguais se combinam
    • Ao alcançar o tile 2048, o jogador vence, mas pode continuar jogando até perder

  • Overflow

    • Executa intencionalmente um virtual machine escape ao provocar stack overflow por recursão infinita
    • Explora o fato de o runtime não ter verificação de prevenção de stack overflow
    • Quando o valor do stack pointer ultrapassa 2048, a stack sai da área de memória pretendida e invade o espaço de memória heap
    • Se for executado com a RAM vazia, o programa pode ser resetado no meio por causa de uma instruction que define o program counter como 0
    • Se for executado logo após o GeneticAlgorithm, é possível ler dados antigos da RAM memory que não foram sobrescritos

  • SecretPassword

    • Explora o fato de o runtime não impedir stack smashing para chamar uma função originalmente inacessível
    • O usuário pode sobrescrever uma memory address da RAM com o valor desejado
    • Ao sobrescrever o return address de um stack frame com o endereço de outra função, torna-se possível executar código arbitrário dentro do programa
    • Os valores de exemplo são memory location 267 e overwrite value 1743
    • O mesmo tipo de vulnerabilidade também existe em buffer overflow em C

  • GeneticAlgorithm

    • É uma simulação de criaturas usando machine learning simples
    • Cada dot tem seu próprio “brain”, composto por vetores de aceleração, e evolui para alcançar o goal por meio de seleção natural
    • Dots que morrem mais perto do goal têm maior chance de ser escolhidos como parents da próxima geração
    • Durante a reprodução, partes do brain sofrem mutation para simular evolução natural
    • Há um vídeo de demonstração do Genetic Algorithm

Limitações de hardware enfrentadas pelo GeneticAlgorithm

  • O GeneticAlgorithm foi o programa individual que mais tempo levou para ser desenvolvido entre os vários componentes do NAND
  • Por questões de desempenho, o único fator usado pelos dots na evolução é o quão perto do goal eles morrem, o que reduz a entropy do algoritmo de seleção natural
  • Por uso de memória, há limitações insatisfatórias no número de dots e no tamanho do brain
  • Por complexidade técnica, mesmo que os obstáculos sejam reposicionados durante a simulação, não há garantia de que o brain dos dots seja grande o suficiente para alcançar o goal
    • O brain size é definido apenas no momento em que o programa começa
  • A implementação contorna as restrições do NAND com várias otimizações
    • O espaço de memória de instruções da ROM é limitado, então se houver código demais ele não compila
    • O GeneticAlgorithm final usa 99,2% do espaço de memória de instruções
    • O espaço de RAM memory é limitado, então é preciso otimizar o uso de heap memory
    • A razão de a tela ficar preenchida de forma static entre gerações é que o espaço de memória da tela é usado como memória temporária de swap para a próxima geração
    • O NAND não tem tipo floating point, e o intervalo de integer representável vai de -32768 a 32767
    • A precisão do cálculo de fitness diminui, e integer overflow também precisa ser considerado
  • Otimizações relacionadas e insights adicionais estão documentados na codebase do GeneticAlgorithm

Escrevendo programas NAND com Jack

  • É enfatizado que a principal causa de programas não funcionarem em Jack é a ausência de precedência de operadores
    • 4 * 2 + 3 deve ser escrito como (4 * 2) + 3
    • if (~x & y) deve ser escrito como if ((~x) & y)
    • O valor de avaliação de uma expression ambígua sem parênteses é undefined
  • Jack é a linguagem de programação orientada a objetos fracamente tipada do NAND
    • Pela descrição, ela é mais próxima de “C com sintaxe de Java”
    • Como o NAND tem sua própria complete tech stack, só é possível programar com Jack
  • O Jack OS básico é bundled com o programa no momento da compilação
    • Ele fornece strings, memory e interface com o hardware
    • Inclui funções como Keyboard.readLine, Keyboard.readInt, Output.printString e Output.println
  • Jack oferece suporte a três tipos primitivos: int, char e boolean
    • É possível definir abstract data types por meio de classes
    • Variáveis field declaram atributos de cada instância
    • Variáveis field têm escopo privado, e o acesso externo exige methods
  • function e method têm formas de chamada diferentes
    • O method do objeto atual pode ser chamado dentro da mesma classe como do g();
    • Uma function call precisa ter o nome da classe como prefixo
    • O method de um objeto é chamado por meio do objeto, como em do b.q();

Tipagem fraca e gerenciamento de memória em Jack

  • Diferentemente de Java, Jack não oferece suporte a strong typing, down casting, polymorphism nem inheritance
  • Internamente, existe de fato apenas um tipo: signed 16-bit integer
    • O compiler não se importa se tipos forem misturados em assignments e operations
    • Se você colocar 65 em um char, ele pode ser tratado como equivalente a 'A'
    • Se você colocar 5000 em uma variável Array e executar a[100] = 77, isso vira RAM[5100] = 77
    • Entradas de array podem conter data types diferentes entre si
    • Se o memory layout bater, Array pode ser usado como se fosse uma instância de outra classe
  • Jack é uma linguagem de gerenciamento manual de memória
    • Se memory que não é mais necessária não for desalocada, ocorre memory leak
    • Heap overflow aparece como ERR6
    • O Jack OS armazena arrays e strings no heap, não na stack
  • Como boa prática, classes que representam objetos devem ter um method dispose
    • Primeiro, chama-se o dispose das variáveis field
    • No final, a própria instância do objeto é desalocada com do Memory.deAlloc(this);
  • Um loop que cria repetidamente string literals para exibir pode causar heap overflow
    • É possível desalocar a string a cada iteração
    • Ou alocar a string apenas uma vez e reutilizá-la para continuar imprimindo

Comportamento indefinido e cuidados

  • Operadores de comparação

    • a > b e a < b nem sempre são matematicamente corretos
    • A implementação da VM converte a > b em a - b > 0
    • Como a - b pode sofrer overflow, 20000 > -20000 vira false
    • Se a distância absoluta entre a e b for maior que 32767, > e < podem falhar
    • Esse comportamento não é corrigido por compatibilidade com Nand to Tetris

  • -32768

    • -32768 é o único valor para o qual -(-32768) = -32768
    • Como ele não tem equivalente positivo, pode causar unsoundness e logic errors
    • Output.printInt espera internamente que Math.abs retorne um número positivo, mas isso não acontece com -32768, então o Jack OS funciona de forma incorreta

  • Chamada de função com argumentos insuficientes

    • Chamar uma function que tem parameters sem argumentos também pode gerar undefined behavior
    • Por outro lado, uma function call com argumentos demais é válida, e os argumentos extras podem ser indexados com a keyword arguments
    • Não há indicador de quantidade de argumentos

  • Type casting inadequado

    • É possível fazer cast de variáveis para outro tipo usando Array
    • Chamar um instance method inexistente em uma variável convertida é undefined behavior
    • O compiler não é smart o bastante para perceber isso

  • Modificação de stack frame e registradores internos

    • Modificar o stack frame nos endereços de memória 256~2047 ou os internal registers 1~15 pode causar undefined behavior
    • Em geral, isso é difícil de fazer sem uso incorreto de Memory.poke ou negative array indexing

  • Carregamento de arquivos VM do usuário

    • O NAND fornece validação de programa para arquivos .jack, mas não para arquivos .vm
    • Em arquivos .vm, é possível chamar funções inexistentes, referenciar variáveis não atribuídas e realizar operações de memória logicamente inválidas
    • Na maioria dos casos, ocorre virtual machine escape e nada pode ser exibido na tela

Especificações de hardware e layout de memória

  • A RAM do NAND é composta por 32.768 words, e cada word armazena um número binário de 16 bits
  • O hardware reserva 8.192 endereços de memória para a screen
    • Cada bit de cada endereço é mapeado linearmente para o pixel correspondente da screen 512x256
    • A numeração de bits segue o esquema LSb 0
  • O keyboard é mapeado para o endereço de memória 24576
    • A tecla atualmente pressionada é refletida nessa posição
    • Em vez de tratar a entrada do usuário diretamente nesse endereço, recomenda-se usar a classe Keyboard do Jack OS
  • O keyboard reconhece caracteres ASCII e teclas especiais
    • nova linha = 128
    • backspace = 129
    • seta para esquerda/cima/direita/baixo = 130~133
    • home/end/page up/page down/insert/delete/ESC = 134~140
    • F1~F12 = 141~152
  • O hardware reserva 240 endereços de memória para static class variables e 1.792 endereços de memória para a global stack
    • É dito que esse limite geralmente não causa problemas, a menos que se faça recursão profunda

Indo além do Jack OS e implementando um OS próprio

  • Basicamente, o Jack OS é incluído junto com o programa na compilação e fornece string, memória e interface de hardware
  • É possível fornecer uma implementação própria de OS com uma interface de hardware dedicada
    • A IDE trata o arquivo do Jack OS da mesma forma que um arquivo de programa comum
    • O arquivo do OS também pode ser apagado ou sobrescrito
  • Mesmo usando um OS próprio, existem funções centrais que obrigatoriamente precisam ser implementadas para a compilação
    • Sys.init: é o ponto de entrada real codificado diretamente na implementação da VM, e não Main.main
    • Memory.alloc: é o alocador de memória heap usado internamente quando um construtor de classe cria um objeto
    • String.newWithStr: é o construtor interno para literais de string
    • Math.multiply: é chamado internamente no lugar da expressão Jack x * y
    • Math.divide: é chamado internamente no lugar da expressão Jack x / y
  • O Sys.init do Jack OS fornecido inicializa memória, matemática, tela e saída, depois chama Main.main() e então Sys.halt()

Funcionamento interno do NAND

  • O computador NAND segue a arquitetura Harvard
    • A ROM, que é a memória de instruções, e a RAM, que é a memória de dados, ficam separadas
    • A CPU faz as duas funcionarem em conjunto
  • A CPU é uma accumulator machine
    • Ela depende fortemente de registradores embutidos no fluxo de controle
    • Aqui, o acumulador é o registrador D
  • O conjunto de instruções da CPU tem apenas dois opcodes
    • O conjunto de instruções é relativamente simples, mas oferece bastante funcionalidade
    • A ALU é definida pelas expressões que podem ser calculadas em uma instrução
  • O compilador e a máquina virtual não são conceitos exclusivos do NAND, então são tratados brevemente
    • Alguns recursos sintáticos estranhos são resultado de facilitar a implementação do compilador
    • O compilador é um parser recursive descent sobre uma gramática LL(1)
    • O compilador gera código VM, e a VM é usada como uma stack machine simples
    • Cada instrução da VM é mapeada para assembly e código de máquina
  • O código de implementação pode ser visto em core e compiler implementation

Pontos centrais da linguagem Jack e da referência do OS

  • Um programa Jack é composto por uma coleção de classes
    • Cada classe é definida em um arquivo separado
    • É necessário haver uma ou mais classes, e uma delas deve ser Main
    • No Jack OS, o ponto de entrada é a função main da classe Main
  • Uma classe pode incluir declarações de field, static, constructor, method e function
    • A ordem das declarações de field e static é arbitrária
    • A ordem das declarações de sub-rotinas também é arbitrária
    • O tipo pode ser void, int, boolean, char ou nome de classe
  • Características da sintaxe
    • Espaços em branco e comentários são ignorados
    • & e | são operadores bit a bit e não fazem short-circuit
    • true, false e null são respectivamente -1, 0 e 0
    • Constantes de string não podem incluir diretamente quebra de linha nem aspas, e escapes também não são permitidos
    • Aspas e quebra de linha são fornecidas pelo OS por meio de String.doubleQuote() e String.newLine()
    • Identificadores diferenciam maiúsculas de minúsculas
  • Principais classes do Jack OS
    • Array: criação e descarte de arrays
    • Keyboard: pressionamento de teclas, caractere, linha e entrada de inteiro
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: saída na tela de texto e movimentação do cursor
    • Screen: desenho de pixel, linha, retângulo e círculo
    • String: criação de string, descarte, acesso a caractere, append e conversão de inteiro
    • Sys: halt, error, wait
  • Um estado inválido exibe um código de erro no formato "ERR[N]" e encerra a execução do programa
    • ERR3: divisão por zero
    • ERR6: overflow de heap
    • ERR15, ERR16: índice de string fora dos limites
    • ERR17: a string está cheia
    • ERR20: posição ilegal do cursor

Não é um projeto feito apenas com portas NAND reais

  • O FAQ reconhece que a descrição e o título “everything made from NAND gates” são enganosos, mas feitos de boa-fé
  • O compilador e o tradutor da máquina virtual foram escritos em TypeScript
  • O kernel emulado e o hardware emulado não representam exatamente a forma como um computador real funciona
  • O simulador de lógica de portas NAND real foi escrito em Rust e ocupa apenas uma pequena parte de toda a base de código
    • O código em Rust é compilado para WebAssembly para rodar no navegador
    • Por isso, afirma-se que a premissa de que toda computação roda em portas NAND é, na prática, removida
  • O NAND cumpre o papel de projeto educacional e teórico
    • Em teoria, a mesma lógica de CPU poderia funcionar também em uma manifestação real do hardware emulado
    • Como exemplo de projeto de hardware FPGA baseado em nand2tetris, é citado https://gitlab.com/x653/nand2tetris-fpga/

Escopo da implementação e limitações da IDE

  • O NAND segue a especificação do curso Nand to Tetris e do livro relacionado
  • O implementador criou diretamente as especificações da CPU, assembler, tradutor de máquina virtual e compilador, e ao portar a plataforma para a web adicionou sua própria IDE e UI
  • O motivo de Jack exigir declaração de tipos é que o compilador precisa determinar a qual classe um método de instância pertence
    • s.appendChar(33) em s declarado como tipo String é convertido durante a compilação em String.appendChar(s, 33)
  • A IDE sacrifica a experiência do usuário para simplificar a implementação
    • Para syntax highlighting, ela usa contenteditable e lógica de posicionamento do cursor
    • Como resultado, é lenta, visivelmente bugada, e atalhos comuns de teclado não funcionam
  • Para compilar e executar o código, basta clicar em “Start”
    • O OS normalmente leva um pouco menos de 1 segundo para inicializar a memória e configurar os serviços

Leituras relacionadas

1 comentários

 
GN⁺ 2024-04-27
Comentários do Hacker News

  • Excelente projeto paralelo, e o README também é muito bom. Depois de mexer um pouco no 6502 Computer do Ben Eater (https://eater.net/), eu estava pensando em seguir o Nand to Tetris

    • Será que também seria possível construir um computador físico NAND-to-Tetris? Ou é apenas um exercício feito em um ambiente puramente virtual?

  • Só com esse material daria para montar algumas disciplinas universitárias. É um material bem feito

    • Isso não é simplesmente Nand2Tetris? Fiz esse curso e, à primeira vista, parece igual, incluindo até a linguagem Jack

  • Muito bem feito. É como se a pessoa tivesse percorrido pessoalmente camadas de abstração que a maioria dos programadores não verá durante toda a carreira

  • Trabalho incrível. NAND to Tetris me ajudou a conseguir meu primeiro emprego depois da faculdade

    • Fiquei curioso para saber como ajudou

  • No início dos anos 1990, no exame de qualificação em hardware de computadores da UC Berkeley, um projeto parecido era a questão central
    Especificamente, era preciso projetar do zero, usando apenas portas NAND, um processador RISC pipeline baseado em microcódigo; não era necessário construí-lo de fato, mas era preciso entregar um projeto detalhado no papel

  • Trabalho realmente impressionante. Quando fiz o curso Nand2Tetris, eu também quis criar uma implementação virtual parecida
    É impressionante que alguém tenha realmente conseguido, e agora essa pessoa deve entender muito bem como um computador funciona

    • Eu também estava pensando esta manhã em algo parecido, modelando componentes básicos em SVG
      Mas é surpreendente ver que alguém já fez um trabalho uma ordem de grandeza mais impressionante do que eu imaginava

  • Excelente trabalho. Recentemente também comecei o Nand2Tetris e quero terminar nos próximos meses a parte 1, que é a parte de hardware do curso
    Registrei meu progresso neste blog: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • Mentira. Você usou portas NAND e um clock

    • Esse clock também pode ser feito com um oscilador em anel, e um oscilador em anel pode ser composto por um número ímpar de portas NAND ligadas como portas NOT

  • Trabalho incrível. Marquei nos favoritos para olhar com mais calma depois
    Gosto de NAND-to-Tetris, mas nunca fui até o fim, então estou ansioso para explorar este projeto

  • Fiquei curioso: qual é o número total de portas NAND?

    • Dei uma olhada mais detalhada no código e, a cada ciclo de clock, as portas NAND são usadas 3.234 vezes :)