Show HN : un ordinateur programmable construit avec des portes NAND

NAND : un ordinateur 16 bits complet, Turing-équivalent, implémenté sur le web

• NAND est un ordinateur 16 bits Turing-équivalent émulé sur le web avec uniquement des portes NAND et une horloge
• NAND possède son propre CPU, langage machine, assembleur, langage d’assemblage, langage de VM, traducteur VM, langage de programmation, compilateur, IDE et UI
• NAND est basé sur la plateforme Jack-VM-Hack décrite dans le cours Nand to Tetris et les livres associés

Exemples de programmes

Average

• Un programme simple qui reçoit des nombres en entrée et calcule leur moyenne
• Montre le contrôle de flux, les opérations arithmétiques, les E/S et l’allocation dynamique de mémoire

Pong

• Un jeu de Pong qui montre le modèle orienté objet du langage
• Déplacez la raquette à gauche et à droite avec les touches fléchées pour renvoyer la balle
• À chaque renvoi, la raquette rétrécit, et la partie se termine lorsque la balle tombe en bas de l’écran

2048

• Le jeu 2048 pour montrer la récursivité et une logique applicative complexe
• Déplacez les nombres sur une grille 4x4 avec les touches fléchées
• Les nombres identiques fusionnent lorsqu’ils se rencontrent
• Atteindre la tuile 2048 permet de gagner, mais on peut continuer à aller plus loin
• La partie se termine lorsque le plateau est plein et qu’aucun mouvement n’est possible

Overflow

• Un programme qui provoque volontairement un stack overflow par récursion infinie afin de s’échapper de la machine virtuelle
• Exploite l’absence de vérifications d’exécution pour empêcher le stack overflow
• Affiche en continu la valeur du pointeur de pile pendant l’exécution
• Lorsque la pile atteint la fin de l’espace mémoire prévu et déborde sur le tas, les instructions d’impression se mettent à dysfonctionner de manière explosive

SecretPassword

• Un programme qui appelle une fonction normalement inaccessible en exploitant l’absence de protection contre le stack smashing au runtime
• Il faut comprendre l’organisation des stack frames de NAND
• Permet à l’utilisateur d’écraser n’importe quelle adresse mémoire avec une valeur arbitraire
• En remplaçant l’adresse de retour d’une fonction par l’adresse d’une autre, on peut exécuter du code arbitraire
• En entrant un emplacement mémoire précis et la valeur à y écrire, obtenus en inspectant manuellement les adresses de pile et l’assembleur, on peut voir cette idée fonctionner

GeneticAlgorithm

• La partie qui a demandé le plus de temps de développement parmi les nombreux composants de NAND
• Une simulation biologique utilisant un apprentissage automatique simple
• Le « cerveau » de chaque point est constitué de vecteurs d’accélération qui évoluent vers l’objectif par sélection naturelle
• À chaque génération, les points « morts » les plus proches de l’objectif ont plus de chances d’être choisis comme parents de la génération suivante
• La reproduction fait muter les cerveaux et simule efficacement l’évolution naturelle
• En raison de contraintes de performance, de nombreuses techniques d’optimisation sont utilisées pour contourner les limites matérielles et rendre cela possible

Programmer en Jack

• Le point le plus important en programmant en Jack est qu’il n’existe pas de priorité des opérateurs. Cela peut être la raison pour laquelle votre programme ne fonctionne pas correctement.
• Il faut expliciter la priorité avec des parenthèses, comme dans 4 * 2 + 3 → (4 * 2) + 3, if (~x & y) → if ((~x) & y)

Introduction à Jack

• NAND affiche l’intégralité de sa propre stack technique
• Jack est un langage orienté objet à typage faible. En simplifiant : du C avec une syntaxe Java
• Apprenons-le à travers un exemple

Types de données personnalisés

• Jack prend en charge trois types de base : int, char, boolean
• Il est possible de les étendre selon les besoins avec des types de données abstraits
• Les connaissances en programmation orientée objet s’appliquent directement
• Dans l’exemple, la classe Point définit un point abstrait dans l’espace
• Les variables field déclarent les propriétés propres à chaque instance du type de données
• Des fonctions publiques method permettant de manipuler les points sont fournies afin que l’appelant puisse additionner des points ou calculer la distance entre deux points
• Toutes les variables field ont une portée privée. Pour y accéder, il faut passer par des fonctions method
• Par convention, les classes de données définissent une méthode dispose
• Voir la syntaxe d’appel de function et method

Conversions de type faibles

• Jack a été fortement inspiré par Java, mais ce n’est qu’une façade simplifiée
• Java est un langage fortement typé qui prend en charge des fonctionnalités complexes comme le downcasting, le polymorphisme et l’héritage
• En revanche, Jack ne prend en réalité en charge qu’un seul type : l’entier signé sur 16 bits
• C’est la principale raison de son typage faible
• Le compilateur Jack ne se soucie donc pas du mélange de différents types dans les affectations et les opérations
• Jack fournit malgré tout un modèle orienté objet puissant et fonctionnel
• Cela aide à comprendre quand et comment effectuer des conversions de type

Gestion manuelle de la mémoire

• Jack est un langage à gestion manuelle de la mémoire
• Il faut veiller à libérer correctement la mémoire dont on n’a plus besoin
• Sinon, l’OS de Jack considérera qu’il y a une fuite mémoire
• La bonne pratique consiste à écrire une méthode dispose pour chaque classe afin d’encapsuler correctement la désallocation
• Appeler cette méthode quand l’objet n’est plus nécessaire permet d’éviter l’épuisement de la mémoire du tas
• Si vous avez déjà utilisé d’autres langages à gestion manuelle de la mémoire comme C, cela vous sera familier
• La différence est que l’OS de Jack stocke les tableaux et les chaînes sur le tas plutôt que sur la pile
• String.dispose peut servir de modèle pour écrire une méthode dispose

Comportement indéfini

Priorité des opérateurs

• C’est tellement important que cela a été déplacé plus haut

Opérateurs plus petit / plus grand

• Les comparaisons a > b, a < b en Jack semblent simples, mais elles ne sont pas toujours correctes mathématiquement
• La machine virtuelle les transforme en a - b > 0. Or a - b peut déborder
• Comment 20000 > -20000 sera-t-il évalué ? 20000 - (-20000) > 0, soit -25336 > 0, donc false
• En revanche, 20000 > -10000 devient 30000 > 0, donc true
• Si la différence absolue entre a et b dépasse 32767, alors a > b et a < b deviennent faux. Sinon, tout va bien
• Ce n’est pas un bug, mais une incompatibilité avec Nand to Tetris. Ce comportement ne sera pas corrigé pour préserver la compatibilité

-32768

• -32768 est le seul nombre ayant la propriété particulière -(-32768) = -32768. C’est un singleton sans équivalent positif
• Cela peut provoquer des erreurs de logique pourtant apparemment valides
• Car -x est traité en interne comme ~(x-1)
• Si x vaut -32768, alors x-1 = ~x. ~(~x) redevient x
• Que s’est-il passé ? Comme NAND est une machine 16 bits, soustraire 1 à -32768 donne comme résultat l’inversion des bits
• Le point important est de traiter les erreurs de logique liées à l’opérateur unaire négatif
• Vérifier le cas -32768 et le gérer correctement relève de la responsabilité du programmeur

Appel de fonction avec trop peu d’arguments

• Un comportement indéfini évident qui ne nécessite pas d’explication

Conversion de type inappropriée

• Une variable peut être castée en n’importe quel type via Array
• Appeler une méthode d’instance inexistante provoque un comportement indéfini
• Le compilateur n’est pas assez intelligent pour le détecter

Stack overflow

• Voir le programme Overflow

Modification des stack frames ou des registres internes

• Modifier les stack frames ou les registres internes aux adresses 256~2047 et 1~15 peut provoquer un comportement indéfini
• En général, c’est impossible sauf en utilisant mal Memory.poke ou des indices de tableau négatifs
• Voir le programme SecretPassword

Spécifications matérielles

• Il y a une raison pour laquelle le calcul 16 bits a été abandonné après les années 1970

• Sa capacité de traitement et sa mémoire sont limitées par rapport au 32 bits ou au 64 bits, et ne répondent pas aux exigences des logiciels modernes

• NAND ne fait pas exception

• Comparé à un MacBook avec 16 GiB, NAND ne dispose que de 4 KiB de RAM, soit seulement 0,00002 %

• Malgré cela, c’est suffisant pour nous emmener sur la Lune

• L’OS de Jack réserve 14 336 adresses mémoire sur 4 KiB pour le tas. C’est extraordinairement peu

• Il est donc très important que les applications Jack libèrent efficacement la mémoire

• Si votre projet est trop ambitieux, vous pourriez manquer de mémoire sur le tas et devoir réécrire entièrement vos types de données et votre logique

• Sur les 4 KiB, 8 192 adresses mémoire sont réservées à l’écran

• Chaque bit de chaque adresse est mappé linéairement aux pixels de l’écran 512x256, avec une numérotation des bits LSb commençant à 0

• L’adresse mémoire 24 576 est réservée au clavier

• Elle reflète la valeur du code ASCII de la touche enfoncée

• Il ne faut cependant pas y accéder directement pour gérer les entrées utilisateur. Il faut utiliser la classe Keyboard de l’OS de Jack et les fonctions associées

• Le clavier de NAND reconnaît l’ASCII et les touches spéciales

• 240 adresses mémoire sont réservées aux variables de classe statiques, et 1 792 à la pile globale

• Tant que vous ne faites pas de récursion profonde, cette limite ne devrait pas poser de problème

[GN⁺]

Avis Hacker News

• Le projet Nand to Tetris permet de comprendre en profondeur les niveaux d’abstraction d’un ordinateur
• Le kit d’ordinateur 6502 de Ben Eater a lui aussi une valeur pédagogique similaire
• Ce projet est documenté de manière suffisamment structurée pour servir de base à plusieurs cours universitaires
• Au début des années 1990, l’examen de qualification en matériel informatique de l’UC Berkeley proposait un sujet similaire : concevoir, uniquement avec des portes NAND, un processeur RISC microcodé et pipeline
  • À l’époque, il n’était pas demandé de le construire réellement ; il suffisait de rédiger le plan détaillé sur papier
• Ce projet semble similaire à MarquisdeGeek/gates
• En suivant le cursus Nand2Tetris, j’avais envie de construire virtuellement quelque chose de similaire, et le voir réellement implémenté est impressionnant
  • Cela a probablement permis d’améliorer considérablement la compréhension du fonctionnement d’un ordinateur
• Certains font remarquer qu’un signal d’horloge a aussi été utilisé en plus des portes NAND
• Je n’ai pas terminé le parcours Nand2Tetris, mais en tant qu’admirateur, j’aimerais examiner ce projet de près
• Je me demande combien de portes NAND ont été utilisées au total
• Merci pour cette approche fidèle aux principes fondamentaux