Show HN: Una computadora programable hecha con compuertas NAND

 (github.com/ArhanChaudhary)
2 puntos por GN⁺ 2024-04-27 | 1 comentarios | Compartir por WhatsApp
  • NAND es una computadora de 16 bits equivalente a Turing emulada en la web, basada en la premisa educativa de estar compuesta solo por un clock y compuertas NAND, e incluye desde la CPU hasta el IDE y la UI
  • Su stack propio se basa en la plataforma Jack-VM-Hack e incluye CPU, lenguaje de máquina, ensamblador, assembler, lenguaje VM, VM translator, lenguaje Jack y compiler
  • Los programas de ejemplo incluyen Average, Pong y 2048, además de una demo de VM escape que usa stack overflow y stack smashing, y GeneticAlgorithm, que usa machine learning simple
  • Jack es un lenguaje orientado a objetos de tipado débil, similar a la sintaxis de Java, pero internamente depende de un único signed 16-bit integer y tiene muchas restricciones, como ausencia de precedencia de operadores, gestión manual de memoria y comportamiento indefinido
  • El proyecto no implica que todos los cálculos se ejecuten realmente en compuertas NAND físicas; es una implementación educativa y teórica que usa un compiler en TypeScript, un VM translator, un simulador de lógica de compuertas NAND basado en Rust y WebAssembly

El stack completo de computadora que ofrece NAND

  • NAND se presenta como una computadora web de 16 bits cuyo nombre significa Not A Nand-powered Device
  • Emula una computadora equivalente a Turing hecha con clock y compuertas NAND, e incluye por sí misma los siguientes componentes
    • CPU
    • lenguaje de código máquina
    • lenguaje ensamblador
    • assembler
    • lenguaje de máquina virtual
    • traductor de máquina virtual
    • lenguaje de programación
    • compilador
    • IDE
    • interfaz de usuario
  • Está basada en el curso Nand to Tetris y en la plataforma Jack-VM-Hack del libro relacionado
  • Se ofrece un video demo de NAND

Programas de ejemplo y demos

  • Average

    • Programa simple que recibe números y calcula el promedio
    • Muestra control flow, operaciones aritméticas, I/O y asignación dinámica de memoria
    • Es un programa incluido en la Nand to Tetris software suite

  • Pong

    • Juego Pong que muestra un modelo orientado a objetos
    • El paddle se mueve a la izquierda y derecha con las flechas para rebotar la pelota
    • Cada vez que la pelota rebota, el paddle se achica; si la pelota toca la parte inferior de la pantalla, termina el juego
    • Es un programa incluido en la Nand to Tetris software suite

  • 2048

    • Juego 2048 que muestra recursion y application logic compleja
    • En una grid 4x4, los números se mueven con las flechas y los números iguales se combinan
    • Se gana al llegar al tile 2048, pero se puede seguir jugando hasta perder

  • Overflow

    • Provoca intencionalmente un stack overflow mediante recursión infinita para realizar un virtual machine escape
    • Aprovecha que en runtime no hay una verificación para prevenir stack overflow
    • Cuando el valor del stack pointer supera 2048, el stack sale de su espacio de memoria previsto y se desborda hacia el heap memory space
    • Si se ejecuta con la RAM vacía, el programa puede reiniciarse a mitad de camino por una instruction que establece el program counter en 0
    • Si se ejecuta justo después de GeneticAlgorithm, puede leer memoria RAM anterior que no fue sobrescrita

  • SecretPassword

    • Aprovecha que el runtime no bloquea el stack smashing para llamar a una función que originalmente no era accesible
    • El usuario puede sobrescribir una memory address de la RAM con el valor que quiera
    • Si se sobrescribe la return address del stack frame con la dirección de otra función, es posible ejecutar código arbitrario dentro del programa
    • Los valores de ejemplo son memory location 267 y overwrite value 1743
    • El mismo tipo de vulnerabilidad también existe en el buffer overflow de C

  • GeneticAlgorithm

    • Es una simulación de creatures que usa machine learning simple
    • Cada dot tiene su propio “brain” compuesto por acceleration vectors y evoluciona mediante selección natural para llegar al goal
    • Un dot que muere más cerca del goal tiene mayor probabilidad de ser elegido como parent de la siguiente generación
    • Durante el proceso de reproduction, parte del brain muta para simular evolución natural
    • Se ofrece un video demo de Genetic Algorithm

Restricciones de hardware que enfrentó GeneticAlgorithm

  • GeneticAlgorithm fue el programa individual que más tiempo llevó desarrollar entre los varios componentes de NAND
  • Por rendimiento, el único factor que usan los dots para evolucionar es qué tan cerca están del goal al morir, por lo que la entropy del algoritmo de selección natural es baja
  • Por uso de memoria, hay límites poco satisfactorios en la cantidad de dots y el tamaño del brain
  • Por complejidad técnica, aunque se reubiquen obstacles durante la simulation, no se garantiza que el brain del dot sea lo suficientemente grande como para llegar al goal
    • El brain size solo se determina al inicio del programa
  • La implementación evita las restricciones de NAND mediante varias optimizaciones
    • El ROM instruction memory space es limitado, por lo que si hay demasiado código no compila
    • El GeneticAlgorithm final usa el 99.2% del instruction memory space
    • El RAM memory space es limitado, por lo que es necesario optimizar el heap memory usage
    • La razón por la que la pantalla se llena de static entre generaciones es que el screen memory space se usa como temporary swap memory para la siguiente generación
    • NAND no tiene floating point type, y el rango de integer representable va de -32768 a 32767
    • La precisión del cálculo de fitness se reduce y también hay que considerar integer overflow
  • Las optimizaciones relacionadas y más insight están documentados en el codebase de GeneticAlgorithm

Cómo escribir programas NAND en Jack

  • Se destaca que la causa más importante de que un programa no funcione en Jack es la ausencia de precedencia de operadores
    • 4 * 2 + 3 debe escribirse como (4 * 2) + 3
    • if (~x & y) debe escribirse como if ((~x) & y)
    • El valor de evaluación de una expresión ambigua sin paréntesis es indefinido
  • Jack es un lenguaje de programación orientado a objetos de tipado débil de NAND
    • Según la descripción, se parece más a “C con sintaxis de Java”
    • Como NAND tiene su propio stack tecnológico completo, solo puede programarse en Jack
  • El Jack OS básico se empaqueta junto con el programa al compilar
    • Proporciona strings, memoria e interfaces con el hardware
    • Incluye funciones como Keyboard.readLine, Keyboard.readInt, Output.printString y Output.println
  • Jack admite tres tipos primitivos: int, char y boolean
    • Se pueden definir tipos de datos abstractos mediante clases
    • Las variables field declaran atributos por instancia
    • Las variables field tienen alcance privado, y para acceder desde afuera se requiere un método
  • function y method se invocan de maneras distintas
    • Un método del objeto actual puede llamarse dentro de la misma clase como do g();
    • Una llamada a función debe ir precedida por el nombre de la clase
    • Un método de objeto se invoca a través del objeto, como do b.q();

Tipado débil y gestión de memoria en Jack

  • A diferencia de Java, Jack no admite tipado fuerte, down casting, polimorfismo ni herencia
  • Internamente, el único tipo real es un entero con signo de 16 bits
    • Al compilador no le preocupa que se mezclen tipos en asignaciones y operaciones
    • Si se pone 65 en un char, puede tratarse como equivalente a 'A'
    • Si se pone 5000 en una variable Array y se ejecuta a[100] = 77, eso se convierte en RAM[5100] = 77
    • Las entradas de un array pueden contener distintos tipos de datos
    • Si el layout de memoria coincide, un Array puede usarse como si fuera una instancia de otra clase
  • Jack es un lenguaje con gestión manual de memoria
    • Si no se libera la memoria que ya no se necesita, se produce una fuga de memoria
    • Un heap overflow aparece como ERR6
    • Jack OS almacena arrays y strings en el heap, no en el stack
  • Como buena práctica, una clase que representa un objeto debe tener un método dispose
    • Primero se llama a dispose en las variables de campo
    • Al final, se libera la propia instancia del objeto con do Memory.deAlloc(this);
  • Un loop que crea e imprime repetidamente string literals puede provocar un heap overflow
    • Se puede liberar el string en cada iteración, o bien
    • Se puede asignar el string una sola vez y reutilizarlo para seguir imprimiendo

Comportamiento indefinido y precauciones

  • Operadores de comparación

    • a > b y a < b no siempre son matemáticamente correctos
    • La implementación de la VM convierte a > b en a - b > 0
    • Como a - b puede desbordarse, 20000 > -20000 resulta false
    • Si la distancia absoluta entre a y b es mayor que 32767, > y < pueden equivocarse
    • Este comportamiento no se corrige por compatibilidad con Nand to Tetris

  • -32768

    • -32768 es el único valor para el que -(-32768) = -32768
    • Como no tiene contraparte positiva, puede generar falta de solidez y errores lógicos
    • Output.printInt espera internamente que Math.abs devuelva un número positivo, pero en -32768 no ocurre así, lo que hace que Jack OS funcione mal

  • Llamadas a funciones con muy pocos argumentos

    • Llamar sin argumentos a una función que tiene parámetros también puede producir comportamiento indefinido
    • En cambio, una llamada a función con demasiados argumentos es válida, y los argumentos extra pueden indexarse con la palabra clave arguments
    • No hay indicador de cantidad de argumentos

  • Type casting inadecuado

    • Con Array se puede castear una variable a otro tipo
    • Llamar a un método de instancia inexistente en la variable casteada es comportamiento indefinido
    • El compilador no es lo suficientemente smart como para detectarlo

  • Modificación de stack frames y registros internos

    • Modificar un stack frame en las direcciones de memoria 256 a 2047, o un registro interno de 1 a 15, puede provocar comportamiento indefinido
    • En general, se indica que es difícil hacerlo sin un mal uso de Memory.poke o sin indexación negativa de arrays

  • Carga de archivos VM de usuario

    • NAND ofrece validación de programas para archivos .jack, pero no para archivos .vm
    • En un archivo .vm se pueden hacer llamadas a funciones inexistentes, referencias a variables no asignadas y operaciones de memoria lógicamente inválidas
    • En la mayoría de los casos se produce un escape de la máquina virtual y puede que no se muestre nada en pantalla

Especificaciones de hardware y distribución de memoria

  • La RAM de NAND está compuesta por 32,768 words, y cada word contiene un número binario de 16 bits
  • El hardware reserva 8,192 direcciones de memoria para la pantalla
    • Cada bit de cada dirección se mapea linealmente al píxel correspondiente de la pantalla de 512x256
    • La numeración de bits usa el esquema LSb 0
  • El teclado está mapeado a la dirección de memoria 24576
    • La tecla presionada actualmente se refleja en esa ubicación
    • En lugar de procesar directamente la entrada del usuario desde esa dirección, se recomienda usar la clase Keyboard de Jack OS
  • El teclado reconoce caracteres ASCII y teclas especiales
    • nueva línea = 128
    • backspace = 129
    • flechas izquierda/arriba/derecha/abajo = 130~133
    • home/end/page up/page down/insert/delete/ESC = 134~140
    • F1~F12 = 141~152
  • El hardware reserva 240 direcciones de memoria para variables de clase estáticas y 1,792 direcciones de memoria para el stack global
    • Se indica que, mientras no se use recursión profunda, esta limitación por lo general no es un problema

Implementar un OS propio más allá de Jack OS

  • Básicamente, al compilar, Jack OS se empaqueta junto con el programa y proporciona strings, memoria e interfaces de hardware
  • Se puede proporcionar una implementación de OS propia con una interfaz de hardware dedicada
    • El IDE trata los archivos de Jack OS igual que los archivos de programa normales
    • Los archivos del OS también se pueden eliminar o sobrescribir
  • Aunque se use un OS propio, hay funciones core que deben implementarse obligatoriamente para compilar
    • Sys.init: no es Main.main, sino el verdadero entry point hardcodeado en la implementación de la VM
    • Memory.alloc: es el asignador de memoria heap que se usa internamente cuando un constructor de clase crea un objeto
    • String.newWithStr: constructor interno para string literals
    • Math.multiply: se invoca internamente en lugar de la expresión Jack x * y
    • Math.divide: se invoca internamente en lugar de la expresión Jack x / y
  • Sys.init del Jack OS incluido inicializa la memoria, math, screen y output; luego llama a Main.main() y después a Sys.halt()

Funcionamiento interno de NAND

  • La computadora NAND sigue una arquitectura Harvard
    • La ROM, que es la memoria de instrucciones, está separada de la RAM, que es la memoria de datos
    • La CPU hace que ambas funcionen juntas
  • La CPU es una accumulator machine
    • En el control flow depende mucho de registros integrados
    • Aquí el acumulador es el registro D
  • El instruction set de la CPU tiene solo dos opcodes
    • El instruction set es relativamente simple, pero ofrece funciones ricas
    • La ALU se especifica mediante expresiones que se pueden calcular en una instrucción
  • El compilador y la máquina virtual no son conceptos exclusivos de NAND, así que se tratan brevemente
    • Algunas características extrañas de la sintaxis son resultado de facilitar la implementación del compilador
    • El compilador es un recursive descent parser sobre una gramática LL(1)
    • El compilador genera código VM, y la VM se usa como una stack machine simple
    • Cada instrucción VM se mapea a assembly y machine code
  • El código de implementación se puede consultar en core y en la implementación del compilador

Puntos clave del lenguaje Jack y de la referencia del OS

  • Un programa Jack se compone de una colección de clases
    • Cada clase se define en un archivo separado
    • Se necesita una o más clases, y una de ellas debe ser Main
    • Según Jack OS, el entry point es la función main de la clase Main
  • Una clase puede incluir declaraciones field, static, constructor, method y function
    • El orden de las declaraciones field y static es arbitrario
    • El orden de las declaraciones de subrutinas también es arbitrario
    • El tipo es uno de void, int, boolean, char o el nombre de una clase
  • Características de sintaxis
    • Los espacios en blanco y comentarios se ignoran
    • & y | son operadores bitwise y no hacen short-circuit
    • true, false y null son -1, 0 y 0, respectivamente
    • Las constantes string no pueden incluir directamente un newline ni comillas, y tampoco permiten escapes
    • Las comillas y el newline son proporcionados por String.doubleQuote() y String.newLine() del OS
    • Los identifiers son case-sensitive
  • Clases principales de Jack OS
    • Array: creación y dispose de arrays
    • Keyboard: pulsación de tecla, carácter, línea e input de enteros
    • Math: abs, multiply, divide, sqrt, max, min
    • Memory: peek, poke, alloc, deAlloc
    • Output: salida en pantalla de texto y movimiento del cursor
    • Screen: dibujo de pixel, línea, rectángulo y círculo
    • String: creación de strings, dispose, acceso a caracteres, append y conversión de enteros
    • Sys: halt, error, wait
  • Un estado inválido muestra un código de error con el formato "ERR[N]" y finaliza la ejecución del programa
    • ERR3: división por cero
    • ERR6: heap overflow
    • ERR15, ERR16: índice de string fuera de rango
    • ERR17: el string está lleno
    • ERR20: ubicación ilegal del cursor

No es un proyecto hecho solo con compuertas NAND reales

  • La FAQ reconoce que la descripción y el título “everything made from NAND gates” son engañosos, aunque de buena fe
  • El compilador y el traductor de la máquina virtual están escritos en TypeScript
  • El kernel emulado y el hardware emulado no representan exactamente cómo funciona una computadora real
  • El simulador real de lógica con compuertas NAND está escrito en Rust y ocupa solo una pequeña parte de todo el codebase
    • El código Rust se compila a WebAssembly para ejecutarse en el navegador
    • Se indica que, por este motivo, prácticamente se elimina la premisa de que toda la computación se ejecuta en compuertas NAND
  • NAND cumple el rol de proyecto educativo y teórico
    • En teoría, la misma lógica de CPU podría funcionar también en una manifestación real del hardware emulado
    • Se presenta como ejemplo de proyecto de hardware FPGA basado en nand2tetris: https://gitlab.com/x653/nand2tetris-fpga/

Alcance de la implementación y límites del IDE

  • NAND sigue la especificación del curso Nand to Tetris y del libro relacionado
  • El implementador desarrolló por su cuenta la CPU, el assembler, el traductor de máquina virtual y la especificación del compilador, y al portar la plataforma a la web agregó su propio IDE y UI
  • La razón por la que Jack debe especificar tipos es que el compilador necesita determinar a qué clase pertenece un método de instancia
    • s.appendChar(33) de una s declarada con tipo String se transforma durante la compilación en String.appendChar(s, 33)
  • El IDE sacrifica la experiencia de usuario para simplificar la implementación
    • Usa contenteditable y lógica de posicionamiento del cursor para el syntax highlighting
    • Como resultado, es lento, notoriamente buggy y los keybinds comunes no funcionan
  • Para compilar y ejecutar el código, basta con presionar “Start”
    • Por lo general, el OS tarda un poco menos de 1 segundo en inicializar la memoria y configurar los servicios

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-04-27
Opiniones en Hacker News

  • Es un gran proyecto paralelo y el README también está muy bueno. Después de trastear un poco con la 6502 Computer de Ben Eater (https://eater.net/), estaba pensando en seguir Nand to Tetris.

    • ¿Será posible construir una computadora física de NAND-to-Tetris? ¿O es simplemente un ejercicio para hacerse en un entorno puramente virtual?

  • Solo con este material se podrían armar varios cursos universitarios. Es material muy bien hecho.

    • ¿No es simplemente Nand2Tetris? Hice ese curso y, a primera vista, parece lo mismo, incluso con el lenguaje Jack incluido.

  • Está realmente bien hecho. Básicamente recorrió en persona capas de abstracción que la mayoría de los programadores no verá en toda su carrera.

  • Excelente trabajo. NAND to Tetris me ayudó a conseguir mi primer empleo después de graduarme de la universidad.

    • Me da curiosidad saber cómo te ayudó.

  • A principios de los años 90, en el examen de certificación de hardware de computadoras de UC Berkeley, un diseño parecido era el problema central.
    En concreto, se trataba de diseñar desde cero, usando solo compuertas NAND, un procesador RISC con pipeline basado en microcódigo; no hacía falta construirlo físicamente, pero había que entregar un diseño detallado en papel.

  • Un trabajo realmente impresionante. Cuando hice el curso Nand2Tetris, también quise hacer una implementación virtual parecida.
    Me impresiona que realmente lo haya logrado, y ahora seguramente entiende muy bien cómo funciona una computadora.

    • Yo también esta mañana estaba pensando en algo parecido: modelar componentes básicos en SVG.
      Pero me sorprende que alguien ya haya hecho un trabajo un orden de magnitud más increíble de lo que yo imaginaba.

  • Excelente trabajo. Hace poco también empecé Nand2Tetris, y me gustaría terminar en los próximos meses la Parte 1, que es la parte de hardware del curso.
    Dejé anotado mi progreso en este blog: https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • Mentira. Usaste compuertas NAND y un reloj.

    • Ese reloj también se puede hacer con un oscilador en anillo; un oscilador en anillo se construye con un número impar de compuertas NAND conectadas como compuertas NOT.

  • Excelente trabajo. Lo dejé en marcadores para revisarlo en profundidad después.
    Me gusta NAND-to-Tetris, pero nunca lo terminé, así que tengo ganas de explorar este proyecto.

  • Tengo curiosidad: ¿cuántas compuertas NAND hay en total?

    • Revisé el código con detalle, y en cada ciclo de reloj las compuertas NAND se usan 3,234 veces :)