Show HN: Una computadora programable hecha con compuertas NAND

NAND: una computadora completa de 16 bits Turing-equivalente implementada en la web

• NAND es una computadora de 16 bits Turing-equivalente emulada en la web usando solo compuertas NAND y un reloj
• NAND tiene su propia CPU, lenguaje de máquina, ensamblador, lenguaje ensamblador, lenguaje de VM, traductor de VM, lenguaje de programación, compilador, IDE e interfaz de usuario
• NAND está basado en la plataforma Jack-VM-Hack descrita en el curso Nand to Tetris y en el libro relacionado

Ejemplos de programas

Average

• Un programa simple que recibe números de entrada y calcula el promedio
• Muestra flujo de control, operaciones aritméticas, I/O y asignación dinámica de memoria

Pong

• El juego Pong muestra el modelo orientado a objetos del lenguaje
• Mueve la paleta a izquierda y derecha con las flechas para rebotar la pelota
• Cada vez que la pelota rebota, la paleta se hace más pequeña, y el juego termina cuando la pelota cae debajo de la pantalla

2048

• El juego 2048 muestra recursión y lógica de aplicación compleja
• Mueve los números en una cuadrícula de 4x4 con las flechas
• Los números iguales se combinan cuando se juntan
• Llegar a la ficha 2048 significa ganar, pero puedes seguir acumulando más
• El juego termina cuando el tablero se llena y ya no se puede mover

Overflow

• Un programa que provoca intencionalmente un stack overflow con recursión infinita para escapar de la máquina virtual
• Aprovecha que no hay verificaciones en tiempo de ejecución para prevenir stack overflow
• Al ejecutarse, sigue imprimiendo el valor del stack pointer
• Cuando el stack llega al final del espacio de memoria previsto y se mete en la memoria del heap, la instrucción de impresión empieza a fallar de forma explosiva

SecretPassword

• Un programa que aprovecha que el runtime no previene stack smashing para llamar a una función inaccesible
• Requiere entender el layout de stack frames de NAND
• Permite que el usuario sobrescriba cualquier dirección de memoria con cualquier valor
• Si sobrescribes la dirección de retorno de una función con la dirección de otra función, puedes ejecutar código arbitrario
• Si ingresas una ubicación de memoria específica y el valor a sobrescribir, obtenidos inspeccionando manualmente direcciones del stack y el ensamblador, puedes ver esta idea en acción

GeneticAlgorithm

• Uno de los muchos componentes de NAND, y el que más tiempo tomó desarrollar
• Una simulación biológica que usa aprendizaje automático simple
• El "cerebro" de cada punto son vectores de aceleración, que evolucionan mediante selección natural hasta llegar al objetivo
• En cada generación, los puntos que "mueren" más cerca del objetivo tienen más probabilidad de ser elegidos como padres de la siguiente generación
• La reproducción muta los cerebros y simula de forma efectiva la evolución natural
• Debido a limitaciones de rendimiento, usa muchas técnicas de optimización para sortear las restricciones del hardware y hacerlo posible

Programar en Jack

• Lo más importante al programar en Jack es que no existe precedencia de operadores. Esa puede ser la razón por la que tu programa no funciona correctamente.
• Debes indicar la precedencia con paréntesis, como en 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

Introducción a Jack

• NAND presume toda su propia pila tecnológica
• Jack es un lenguaje orientado a objetos de tipado débil. En pocas palabras, C con sintaxis de Java
• Aprendámoslo con un ejemplo

Tipos de datos personalizados

• Jack soporta tres tipos básicos: int, char, boolean
• Según lo necesites, puedes extenderlos con tipos de datos abstractos
• El conocimiento de programación orientada a objetos se aplica directamente
• En el ejemplo, la clase Point define un punto abstracto en el espacio
• Las variables field declaran propiedades por instancia del tipo de dato
• Se proporcionan funciones públicas method para manipular puntos, de modo que el llamador pueda sumar puntos o calcular la distancia entre dos puntos
• Todas las variables field tienen alcance privado. Para acceder a ellas, deben exponerse mediante funciones method
• Por convención, las clases de datos definen un método dispose
• Consulta la sintaxis de llamadas a function y method

Conversión de tipos débil

• Se dijo que Jack está muy inspirado en Java, pero eso es solo una fachada
• Java es un lenguaje de tipado fuerte y soporta características de tipos complejas como downcasting, polimorfismo y herencia
• En cambio, Jack en realidad solo soporta un único signed 16-bit integer
• Esa es la razón principal por la que Jack tiene tipado débil
• Por eso, al compilador de Jack no le importa si mezclas tipos distintos en asignaciones y operaciones
• Jack sigue ofreciendo un modelo orientado a objetos potente y funcional
• Esto te ayudará a entender cuándo y cómo debes hacer conversiones de tipo

Gestión manual de memoria

• Jack es un lenguaje con gestión manual de memoria
• Debes tener cuidado de liberar correctamente la memoria que ya no necesitas
• Si no lo haces, Jack OS asumirá que hay una fuga de memoria
• La mejor práctica es escribir un método dispose para cada clase que encapsule correctamente la liberación
• Si llamas este método cuando el objeto ya no se necesita, puedes evitar quedarte sin memoria de heap
• Si ya has usado otros lenguajes con gestión manual de memoria, como C, esto te resultará familiar
• La diferencia es que Jack OS almacena arreglos y cadenas en el heap, no en el stack
• Puedes ver String.dispose para entender cómo escribir un método dispose

Comportamiento indefinido

Precedencia de operadores

• Es tan importante que se movió hacia arriba

Operadores menor y mayor que

• Las comparaciones de Jack a > b, a < b parecen simples, pero no siempre son matemáticamente correctas
• La máquina virtual las convierte en a - b > 0. Pero a - b puede desbordarse
• ¿Cómo se evalúa 20000 > -20000? Se convierte en 20000 - (-20000) > 0, es decir -25336 > 0, y da false
• Pero 20000 > -10000 se convierte en 30000 > 0, es decir true
• Si la diferencia entre los valores absolutos de a y b es mayor que 32767, entonces a > b y a < b fallan. Si no, funcionan bien
• Esto no es un bug, sino una incompatibilidad con Nand to Tetris. No se corregirá por compatibilidad

-32768

• -32768 es el único número con la peculiar propiedad de que -(-32768) = -32768. Es un singleton sin contraparte positiva
• Esto puede causar errores lógicos inesperados
• Porque -x se procesa internamente como ~(x-1)
• Si asignas -32768 a x, se cumple x-1 = ~x. Entonces ~(~x) termina siendo igual a x
• ¿Qué pasó? Como NAND es una máquina de 16 bits, al restarle 1 a -32768 el resultado es invertir sus bits
• Lo importante es manejar correctamente estos errores lógicos en el operador de negación
• Es responsabilidad del programador revisar el caso -32768 y manejarlo de forma adecuada

Llamadas a funciones con argumentos insuficientes

• Un comportamiento indefinido evidente que no necesita explicación

Conversión de tipos inapropiada

• Puedes convertir una variable a Array sin importar su tipo
• Llamar a un método de instancia que no existe produce comportamiento indefinido
• El compilador no es lo bastante inteligente como para detectarlo

Stack overflow

• Consulta el programa Overflow

Modificar stack frames o registros internos

• Modificar stack frames o registros internos en las direcciones 256~2047 y 1~15 puede producir comportamiento indefinido
• Normalmente esto no es posible a menos que abuses de Memory.poke o de índices negativos de arreglos
• Consulta el programa SecretPassword

Especificaciones de hardware

• Hay una razón por la que el cómputo de 16 bits quedó obsoleto después de los años 70

• En comparación con 32 bits o 64 bits, su capacidad de procesamiento y memoria es limitada, y no satisface las exigencias del software moderno

• NAND no es la excepción

• Comparado con una MacBook de 16GiB, NAND solo tiene 4KiB de RAM. Eso es apenas el 0.00002%

• Aun así, alcanza para llevarnos a la luna

• Jack OS reserva 14,336 direcciones de memoria del total de 4KiB para el heap. Es una cantidad absurdamente pequeña

• Por eso es muy importante que las aplicaciones Jack liberen memoria de forma eficiente

• Si tu plan es demasiado ambicioso, podrías quedarte sin memoria de heap y tener que reescribir por completo tus tipos de datos y tu lógica

• Del total de 4KiB, 8,192 direcciones de memoria están reservadas para la pantalla

• Cada bit de cada dirección se mapea linealmente a los píxeles de una pantalla de 512x256. Usa numeración de bits LSb 0

• La dirección de memoria 24,576 está reservada para el teclado

• Refleja el valor de código ASCII de la tecla presionada

• Pero no debes acceder a esto directamente para manejar entrada del usuario. Debes usar la clase Keyboard de Jack OS y sus funciones relacionadas

• El teclado de NAND reconoce ASCII y teclas especiales

• Se reservan 240 direcciones de memoria para variables estáticas de clase y 1,792 para el stack global

• A menos que hagas recursión profunda, este límite no debería ser un problema

[GN⁺]

Opiniones de Hacker News

• El proyecto Nand to Tetris permite comprender en profundidad los niveles de abstracción de una computadora
• El kit de computadora 6502 de Ben Eater también tiene un valor educativo similar
• Este proyecto está tan bien organizado que podría convertirse en varias clases universitarias
• A inicios de los años 90, en el examen de certificación de hardware de computadoras de UC Berkeley, se planteó un problema similar: diseñar un procesador RISC microcodificado y segmentado usando solo compuertas NAND
  • En ese momento no se exigía construirlo realmente; bastaba con escribir el diseño detallado en papel
• Este proyecto parece similar a MarquisdeGeek/gates
• Mientras tomaba el curso de Nand2Tetris, quería construir virtualmente algo parecido, y resulta impresionante ver que alguien lo implementó de verdad
  • Seguramente eso mejoró muchísimo su comprensión de cómo funciona una computadora
• Hay quien señala que, además de las compuertas NAND, también se usó un reloj
• No terminé Nand2Tetris, pero como fan me gustaría revisar este proyecto a fondo
• Da curiosidad saber cuántas compuertas NAND se usaron en total
• Se agradece este enfoque fiel a los principios fundamentales