Show HN : Un ordinateur programmable construit avec des portes NAND

 (github.com/ArhanChaudhary)
2 points par GN⁺ 2024-04-27 | 1 commentaires | Partager sur WhatsApp
  • NAND est un ordinateur 16 bits équivalent à une machine de Turing émulé sur le web, qui inclut du CPU jusqu’à l’IDE et à l’interface utilisateur, à partir du postulat pédagogique qu’il est composé uniquement d’une horloge et de portes NAND
  • Sa pile logicielle repose sur la plateforme Jack-VM-Hack et fournit ensemble le CPU, le langage machine, l’assembleur, l’assembler, le langage VM, le VM translator, le langage Jack et le compilateur
  • Les programmes d’exemple incluent Average, Pong et 2048, mais aussi des démonstrations de VM escape exploitant un stack overflow et un stack smashing, ainsi que GeneticAlgorithm utilisant un machine learning simple
  • Jack est un langage orienté objet faiblement typé, proche de la syntaxe Java, mais il repose en interne sur un unique entier signé 16 bits et présente de fortes contraintes : pas de priorité des opérateurs, gestion manuelle de la mémoire et comportements non définis
  • Le projet ne signifie pas que tous les calculs sont réellement exécutés par des portes NAND physiques ; il s’agit d’une implémentation à visée éducative et théorique utilisant un compilateur TypeScript, un VM translator, un simulateur logique de portes NAND en Rust et WebAssembly

La pile informatique complète fournie par NAND

  • NAND est un ordinateur 16 bits basé sur le web, présenté comme l’acronyme de Not A Nand-powered Device
  • Il émule un ordinateur équivalent à une machine de Turing construit avec une horloge et des portes NAND, et intègre directement les composants suivants
    • CPU
    • langage machine
    • langage assembleur
    • assembleur
    • langage de machine virtuelle
    • traducteur de machine virtuelle
    • langage de programmation
    • compilateur
    • IDE
    • interface utilisateur
  • Il repose sur la plateforme Jack-VM-Hack du cours Nand to Tetris et des ouvrages associés
  • Une vidéo de démonstration de NAND est fournie

Programmes d’exemple et démonstrations

  • Average

    • Un programme simple qui prend des nombres en entrée et calcule leur moyenne
    • Il montre le control flow, les opérations arithmétiques, les E/S et l’allocation dynamique de mémoire
    • Il est fourni dans la suite logicielle Nand to Tetris

  • Pong

    • Un jeu de Pong qui montre le modèle orienté objet
    • Les flèches du clavier permettent de déplacer la raquette à gauche et à droite pour renvoyer la balle
    • La raquette rétrécit à chaque rebond de la balle, et la partie se termine lorsque la balle touche le bas de l’écran
    • Il est fourni dans la suite logicielle Nand to Tetris

  • 2048

    • Un jeu 2048 qui illustre la récursion et une logique applicative complexe
    • Sur une grille 4x4, les nombres se déplacent avec les flèches du clavier et les valeurs identiques fusionnent
    • Atteindre la tuile 2048 permet de gagner, mais il est possible de continuer à jouer jusqu’à la défaite

  • Overflow

    • Il provoque intentionnellement un stack overflow via une récursion infinie afin d’effectuer une évasion de machine virtuelle
    • Il exploite l’absence de vérification à l’exécution contre les stack overflows
    • Lorsque la valeur du stack pointer dépasse 2048, la pile sort de l’espace mémoire prévu et déborde dans l’espace mémoire du tas
    • S’il est exécuté dans une RAM vide, le programme peut se réinitialiser en cours d’exécution à cause d’une instruction qui fixe le program counter à 0
    • Exécuté juste après GeneticAlgorithm, il peut lire une mémoire RAM précédente qui n’a pas été écrasée

  • SecretPassword

    • Il exploite le fait que le runtime n’empêche pas le stack smashing pour appeler une fonction normalement inaccessible
    • L’utilisateur peut écraser une adresse mémoire de la RAM avec la valeur de son choix
    • En remplaçant l’adresse de retour d’une stack frame par l’adresse d’une autre fonction, il devient possible d’exécuter un code arbitraire dans le programme
    • Les valeurs d’exemple sont l’emplacement mémoire 267 et la valeur d’écrasement 1743
    • Le même type de vulnérabilité existe aussi dans les buffer overflows en C

  • GeneticAlgorithm

    • Une simulation de créatures utilisant un machine learning simple
    • Chaque point possède son propre « cerveau », composé d’un vecteur d’accélération, et évolue vers l’objectif via la sélection naturelle
    • Les points morts plus près de l’objectif ont davantage de chances d’être sélectionnés comme parents de la génération suivante
    • Pendant la reproduction, une partie du cerveau subit des mutations pour simuler l’évolution naturelle
    • Une vidéo de démonstration de Genetic Algorithm est fournie

Les contraintes matérielles rencontrées par GeneticAlgorithm

  • GeneticAlgorithm est, parmi les différents composants de NAND, le programme unique qui a demandé le plus de temps de développement
  • Pour des raisons de performance, le seul facteur utilisé par les points dans leur évolution est leur proximité avec l’objectif au moment de leur mort, ce qui réduit l’entropie de l’algorithme de sélection naturelle
  • En raison de l’utilisation mémoire, il existe des limites jugées insatisfaisantes sur le nombre de points et la taille de leur cerveau
  • En raison de la complexité technique, même si les obstacles sont replacés pendant la simulation, rien ne garantit que le cerveau des points soit suffisamment grand pour atteindre l’objectif
    • La taille du cerveau n’est décidée qu’au démarrage du programme
  • L’implémentation contourne les contraintes de NAND grâce à plusieurs optimisations
    • L’espace mémoire d’instructions en ROM est limité, donc le code ne compile pas s’il devient trop volumineux
    • Le GeneticAlgorithm final utilise 99,2 % de l’espace mémoire d’instructions
    • L’espace mémoire RAM est limité, il faut donc optimiser l’usage de la mémoire du tas
    • Si l’écran se remplit d’une image statique entre les générations, c’est parce que l’espace mémoire de l’écran sert de mémoire d’échange temporaire pour la génération suivante
    • NAND ne possède pas de type à virgule flottante, et la plage des entiers représentables va de -32768 à 32767
    • La précision du calcul de fitness diminue et il faut aussi tenir compte des dépassements d’entiers
  • Les optimisations associées et des informations supplémentaires sont documentées dans la codebase de GeneticAlgorithm

Écrire des programmes NAND avec Jack

  • La cause la plus importante des programmes qui ne fonctionnent pas en Jack est l’absence de priorité des opérateurs
    • 4 * 2 + 3 doit être écrit comme (4 * 2) + 3
    • if (~x & y) doit être écrit comme if ((~x) & y)
    • la valeur d’évaluation d’une expression ambiguë sans parenthèses est indéfinie
  • Jack est le langage de programmation orienté objet à typage faible de NAND
    • D’après la description, il se rapproche d’un « C avec une syntaxe Java »
    • Comme NAND dispose de sa propre pile technologique complète, on ne peut programmer qu’en Jack
  • Le Jack OS de base est embarqué avec le programme au moment de la compilation
    • il fournit des chaînes de caractères, la mémoire et une interface avec le matériel
    • il inclut des fonctions comme Keyboard.readLine, Keyboard.readInt, Output.printString et Output.println
  • Jack prend en charge trois types primitifs : int, char et boolean
    • il est possible de définir des types de données abstraits via des classes
    • les variables field déclarent des attributs propres à chaque instance
    • les variables field ont une portée privée, et un accès externe nécessite une méthode
  • function et method s’appellent différemment
    • une méthode de l’objet courant peut être appelée dans la même classe avec do g();
    • un appel de fonction doit être précédé du nom de la classe
    • une méthode d’objet s’appelle via l’objet, comme dans do b.q();

Typage faible et gestion de la mémoire dans Jack

  • Contrairement à Java, Jack ne prend pas en charge le typage fort, le downcasting, le polymorphisme ni l’héritage
  • En interne, il n’existe en réalité qu’un seul type : un entier signé sur 16 bits
    • le compilateur ne se soucie pas du mélange de types dans les affectations et les opérations
    • si l’on met 65 dans un char, il peut être traité comme équivalent à 'A'
    • si l’on met 5000 dans une variable Array puis que l’on exécute a[100] = 77, cela revient à RAM[5100] = 77
    • les entrées d’un tableau peuvent contenir des types de données différents
    • si l’agencement mémoire correspond, un Array peut être utilisé comme une instance d’une autre classe
  • Jack est un langage à gestion manuelle de la mémoire
    • si l’on ne désalloue pas une zone mémoire devenue inutile, une fuite mémoire se produit
    • un dépassement du tas apparaît sous la forme de ERR6
    • le Jack OS stocke les tableaux et les chaînes dans le tas, et non dans la pile
  • Pour les classes représentant des objets, disposer d’une méthode dispose est une bonne pratique
    • il faut d’abord appeler dispose sur les variables field
    • puis désallouer l’instance elle-même à la fin avec do Memory.deAlloc(this);
  • Une boucle qui recrée et affiche en permanence des littéraux de chaîne peut provoquer un dépassement du tas
    • soit en désallouant la chaîne à chaque itération
    • soit en allouant la chaîne une seule fois et en la réutilisant pour pouvoir continuer à l’afficher

Comportements indéfinis et points d’attention

  • Opérateurs de comparaison

    • a > b et a < b ne sont pas toujours mathématiquement exacts
    • l’implémentation VM convertit a > b en a - b > 0
    • a - b peut déborder, donc 20000 > -20000 devient false
    • si la distance absolue entre a et b dépasse 32767, > et < peuvent être faux
    • ce comportement n’est pas corrigé pour des raisons de compatibilité avec Nand to Tetris

  • -32768

    • -32768 est la seule valeur pour laquelle -(-32768) = -32768
    • elle n’a pas de pendant positif, ce qui peut entraîner des incohérences et des erreurs logiques
    • Output.printInt suppose en interne que Math.abs renvoie un nombre positif, mais ce n’est pas le cas pour -32768, ce qui fait dysfonctionner le Jack OS

  • Appels de fonction avec trop peu d’arguments

    • appeler sans argument une function qui attend des paramètres peut provoquer un comportement indéfini
    • à l’inverse, un appel de fonction avec trop d’arguments est valide, et les arguments supplémentaires peuvent être indexés via le mot-clé arguments
    • il n’existe pas d’indicateur du nombre d’arguments

  • Conversion de type inappropriée

    • il est possible de caster une variable vers un autre type en utilisant Array
    • appeler une méthode d’instance inexistante sur une variable castée produit un comportement indéfini
    • le compilateur n’est pas assez intelligent pour le détecter

  • Modification de la pile d’exécution et des registres internes

    • modifier une pile d’exécution située aux adresses mémoire 256~2047 ou des registres internes 1~15 peut provoquer un comportement indéfini
    • il est indiqué que cela reste généralement difficile sans mauvais usage de Memory.poke ou indexation négative de tableau

  • Chargement de fichiers VM utilisateur

    • NAND fournit une validation des programmes pour les fichiers .jack, mais pas pour les fichiers .vm
    • dans un fichier .vm, on peut appeler une fonction inexistante, référencer une variable non affectée ou effectuer des opérations mémoire logiquement invalides
    • dans la plupart des cas, cela entraîne une sortie de la machine virtuelle et rien ne s’affiche à l’écran

Spécifications matérielles et disposition mémoire

  • La RAM de NAND est composée de 32 768 mots, chaque mot contenant un nombre binaire sur 16 bits
  • Le matériel réserve 8 192 adresses mémoire pour l’écran
    • chaque bit de chaque adresse est mappé linéairement au pixel correspondant de l’écran 512x256
    • la numérotation des bits suit la convention LSb 0
  • Le clavier est mappé à l’adresse mémoire 24576
    • la touche actuellement enfoncée est reflétée à cet emplacement
    • il est recommandé d’utiliser la classe Keyboard du Jack OS plutôt que de traiter directement les entrées utilisateur à cette adresse
  • Le clavier reconnaît les caractères ASCII et les touches spéciales
    • nouvelle ligne = 128
    • retour arrière = 129
    • flèche gauche/haut/droite/bas = 130~133
    • home/end/page up/page down/insert/delete/ESC = 134~140
    • F1~F12 = 141~152
  • Le matériel réserve 240 adresses mémoire pour les variables statiques de classe et 1 792 adresses mémoire pour la pile globale
    • il est indiqué que cette limite ne pose généralement pas de problème tant qu’on ne fait pas de récursion profonde

Aller au-delà de Jack OS et implémenter son propre OS

  • Par défaut, Jack OS est intégré au programme lors de la compilation et fournit les chaînes, la mémoire et l’interface matérielle
  • Il est possible de fournir sa propre implémentation d’OS avec une interface matérielle dédiée
    • L’IDE traite les fichiers Jack OS comme des fichiers de programme ordinaires
    • Les fichiers d’OS peuvent aussi être supprimés ou écrasés
  • Même avec un OS personnalisé, certaines fonctions de base doivent impérativement être implémentées pour la compilation
    • Sys.init : le véritable point d’entrée codé en dur dans l’implémentation de la VM, et non Main.main
    • Memory.alloc : l’allocateur de mémoire sur le tas utilisé en interne lorsqu’un constructeur de classe crée un objet
    • String.newWithStr : le constructeur interne pour les littéraux de chaîne
    • Math.multiply : appelé en interne à la place de l’expression Jack x * y
    • Math.divide : appelé en interne à la place de l’expression Jack x / y
  • Dans le Jack OS fourni, Sys.init initialise la mémoire, les mathématiques, l’écran et la sortie, puis appelle Main.main() avant d’appeler Sys.halt()

Fonctionnement interne de NAND

  • L’ordinateur NAND suit une architecture Harvard
    • La ROM, qui contient les instructions, et la RAM, qui contient les données, sont séparées
    • Le CPU coordonne le fonctionnement des deux
  • Le CPU est une machine à accumulateur
    • Le contrôle du flux dépend fortement de registres intégrés
    • Ici, l’accumulateur est le registre D
  • Le jeu d’instructions du CPU ne comporte que deux opcodes
    • Le jeu d’instructions est relativement simple, mais offre des fonctionnalités riches
    • L’ALU est définie par les expressions qu’une instruction peut calculer
  • Le compilateur et la machine virtuelle ne sont pas des concepts propres à NAND, ils sont donc traités brièvement
    • Certaines particularités syntaxiques un peu étranges résultent de choix visant à simplifier l’implémentation du compilateur
    • Le compilateur est un analyseur par descente récursive basé sur une grammaire LL(1)
    • Le compilateur génère du code VM, et la VM est utilisée comme une simple machine à pile
    • Chaque instruction VM est associée à de l’assembleur et à du code machine
  • Le code d’implémentation est disponible dans core et dans l’implémentation du compilateur

L’essentiel du langage Jack et de la référence OS

  • Un programme Jack est composé d’une collection de classes
    • Chaque classe est définie dans un fichier séparé
    • Il faut au moins une classe, dont l’une doit être Main
    • Selon Jack OS, le point d’entrée est la fonction main de la classe Main
  • Une classe peut contenir des déclarations field, static, constructor, method et function
    • L’ordre des déclarations field et static est arbitraire
    • L’ordre des déclarations de sous-routines est également arbitraire
    • Un type peut être void, int, boolean, char ou un nom de classe
  • Caractéristiques de la syntaxe
    • Les espaces et les commentaires sont ignorés
    • & et | sont des opérateurs bit à bit et ne font pas de court-circuit
    • true, false et null valent respectivement -1, 0 et 0
    • Une constante de chaîne ne peut pas contenir directement un saut de ligne ni des guillemets, et les séquences d’échappement ne sont pas prises en charge
    • Les guillemets et les sauts de ligne sont fournis par l’OS via String.doubleQuote() et String.newLine()
    • Les identifiants sont sensibles à la casse
  • Principales classes de Jack OS
    • Array : création et libération de tableaux
    • Keyboard : saisie de touches, caractères, lignes et entiers
    • Math : abs, multiply, divide, sqrt, max, min
    • Memory : peek, poke, alloc, deAlloc
    • Output : affichage sur l’écran texte et déplacement du curseur
    • Screen : dessin de pixels, lignes, rectangles et cercles
    • String : création de chaînes, libération, accès aux caractères, ajout et conversion d’entiers
    • Sys : halt, error, wait
  • Un état invalide affiche un code d’erreur au format "ERR[N]" et met fin à l’exécution du programme
    • ERR3 : division par zéro
    • ERR6 : débordement du tas
    • ERR15, ERR16 : index de chaîne hors limites
    • ERR17 : la chaîne est pleine
    • ERR20 : position de curseur illégale

Ce n’est pas un projet composé uniquement de portes NAND réelles

  • La FAQ reconnaît que la description et le titre « everything made from NAND gates » sont trompeurs, mais de bonne foi
  • Le compilateur et le traducteur de machine virtuelle sont écrits en TypeScript
  • Le noyau émulé et le matériel émulé ne représentent pas fidèlement le fonctionnement d’un véritable ordinateur
  • Le véritable simulateur logique de portes NAND est écrit en Rust et ne représente qu’une petite partie de l’ensemble du code
    • Le code Rust est compilé en WebAssembly pour être exécuté dans le navigateur
    • Il est indiqué que cela retire en pratique l’hypothèse selon laquelle tous les calculs s’exécutent sur des portes NAND
  • NAND joue le rôle d’un projet éducatif et théorique
    • En théorie, la même logique CPU pourrait fonctionner dans une manifestation réelle du matériel émulé
    • Un exemple de projet matériel FPGA basé sur nand2tetris est donné : https://gitlab.com/x653/nand2tetris-fpga/

Portée de l’implémentation et limites de l’IDE

  • NAND suit les spécifications du cours Nand to Tetris et du livre associé
  • L’auteur a implémenté lui-même le CPU, l’assembleur, le traducteur de machine virtuelle et les spécifications du compilateur, puis a porté la plateforme sur le web en y ajoutant son propre IDE et sa propre interface
  • La raison pour laquelle Jack impose de déclarer les types est que le compilateur doit déterminer à quelle classe appartient une méthode d’instance
    • s.appendChar(33) sur s déclaré avec le type String est transformé pendant la compilation en String.appendChar(s, 33)
  • Pour simplifier l’implémentation, l’IDE sacrifie l’expérience utilisateur
    • Il utilise contenteditable et une logique de positionnement du curseur pour la coloration syntaxique
    • En conséquence, il est lent, visiblement bogué et les raccourcis clavier courants ne fonctionnent pas
  • Pour compiler et exécuter le code, il suffit d’appuyer sur « Start »
    • L’OS met généralement un peu moins d’une seconde à initialiser la mémoire et à configurer les services

À lire aussi

1 commentaires

 
GN⁺ 2024-04-27
Avis sur Hacker News

  • Excellent projet parallèle, et le README est vraiment très bon. Après avoir un peu bricolé avec le 6502 Computer de Ben Eater (https://eater.net/), j’envisageais d’essayer de suivre Nand to Tetris

    • Serait-il possible de construire un ordinateur NAND-to-Tetris physique ? Ou est-ce seulement un exercice réalisé dans un environnement purement virtuel ?

  • Avec ces ressources, on pourrait créer plusieurs cours universitaires. C’est très bien fait

    • Ce n’est pas tout simplement Nand2Tetris ? J’ai suivi ce cours et, à première vue, ça semble identique, jusqu’au langage Jack inclus

  • Vraiment très bien réalisé. C’est comme s’il avait parcouru lui-même des couches d’abstraction que la plupart des programmeurs ne verront jamais de toute leur carrière

  • Super travail. NAND to Tetris m’a aidé à décrocher mon premier emploi après l’université

    • Je suis curieux de savoir en quoi ça t’a aidé

  • Au début des années 1990, à l’UC Berkeley, une conception de ce genre était au cœur de l’examen de qualification en matériel informatique
    Plus précisément, il fallait concevoir à partir de zéro, uniquement avec des portes NAND, un processeur RISC pipeline basé sur du microcode ; il n’était pas nécessaire de le construire réellement, mais il fallait remettre une conception détaillée sur papier

  • Travail vraiment impressionnant. Quand je suivais le cours Nand2Tetris, j’avais moi aussi envie de créer une implémentation virtuelle similaire
    C’est impressionnant de l’avoir effectivement menée à bien, et il doit maintenant avoir une excellente compréhension du fonctionnement d’un ordinateur

    • Ce matin encore, j’avais une idée similaire : modéliser les composants de base en SVG
      Mais je suis surpris de voir que quelqu’un a déjà réalisé un travail d’un ordre de grandeur supérieur à ce que j’imaginais

  • Excellent travail. J’ai récemment commencé Nand2Tetris moi aussi, et j’aimerais terminer dans les prochains mois la première partie du cours, consacrée au matériel
    J’ai noté mon avancement ici sur mon blog : https://gurudas.dev/blog/2024/04/13/nand-to-tetris-2024-proj...

  • C’est faux. Tu as utilisé des portes NAND et une horloge

    • Cette horloge aussi peut être faite avec un oscillateur en anneau, et un oscillateur en anneau se construit avec un nombre impair de portes NAND branchées comme des portes NOT

  • Beau travail. Je l’ai mis en favori pour l’examiner en détail plus tard
    J’aime NAND-to-Tetris, mais je ne l’ai jamais terminé, donc j’ai hâte de parcourir ce projet

  • Par curiosité, quel est le nombre total de portes NAND ?

    • J’ai examiné le code de près, et les portes NAND sont utilisées 3 234 fois à chaque cycle d’horloge :)