Pas
UN
N et alimenté
Appareil
est un ordinateur 16 bits équivalent à Turing, entièrement constitué d'une horloge et de portes NAND émulées sur le Web. NAND dispose de son propre processeur, langage de code machine, langage d'assemblage, assembleur, langage de machine virtuelle, traducteur de machine virtuelle, langage de programmation, compilateur, IDE et interface utilisateur. NAND est basé sur la plateforme Jack-VM-Hack spécifiée dans le cours Nand to Tetris et son livre associé.
Un programme simple qui saisit des nombres et calcule leur moyenne, montrant le flux de contrôle, les opérations arithmétiques, les E/S et l'allocation dynamique de mémoire.
Résultat du programme :
How many numbers? 4
Enter a number: 100
Enter a number: 42
Enter a number: 400
Enter a number: 300
The average is 210Ce programme a été fourni par la suite logicielle Nand to Tetris.
Le jeu de Pong, mettant en valeur le modèle orienté objet du langage. Utilisez les touches fléchées pour déplacer la pagaie vers la gauche et la droite pour faire rebondir une balle. À chaque rebond, la raquette devient plus petite et le jeu se termine lorsque la balle touche le bas de l'écran.
Ce programme a été fourni par la suite logicielle Nand to Tetris.
Le jeu de 2048, mettant en valeur la récursion et la logique d'application complexe. Utilisez les touches fléchées pour déplacer les nombres sur la grille 4x4. Les mêmes nombres se combinent pour former leur somme lorsqu'ils sont déplacés les uns dans les autres. Une fois la tuile 2048 atteinte, vous gagnez la partie, mais vous pouvez continuer à jouer jusqu'à ce que vous perdiez. Vous perdez la partie lorsque le plateau est plein et vous ne pouvez plus faire de mouvements.
Un programme qui provoque délibérément un débordement de pile via une récursivité infinie pour effectuer un échappement de machine virtuelle. Il exploite le fait qu'il n'y a pas de contrôles d'exécution pour éviter un débordement de pile. Aucune autre plateforme moderne ne vous permettra de faire cela :-)
Lors de l'exécution, le programme imprimera constamment le pointeur de pile sur l'écran. Une fois que cette valeur affichée dépasse 2048, la pile aura atteint la fin de son espace mémoire prévu et se répandra sur l'espace mémoire du tas, provoquant un dysfonctionnement de l'instruction print de manière explosive :
Deux choses d’un grand intérêt méritent d’être soulignées.
Si vous exécutez ce programme sur une RAM vide pleine de zéros (vous pouvez effacer la RAM via l'interface utilisateur), vous remarquerez que le programme se réinitialise à mi-chemin de son exécution même si vous n'appuyez pas sur le bouton "Réinitialiser". La raison pour laquelle cela se produit est simple : le runtime jailbreaké exécute une instruction qui définit la valeur du compteur du programme à 0, indiquant ainsi au programme de passer à la première instruction et de recommencer.
Si vous exécutez l'exemple de programme GeneticAlgorithm puis l'exécutez immédiatement après, le programme dans son déchaînement lit l'ancienne mémoire RAM qui n'a tout simplement jamais été écrasée.
Un programme qui exploite le fait que le runtime n'empêche pas le stack smashing pour appeler une fonction qui serait autrement inaccessible. Afin de comprendre comment cela fonctionne, examinons cette illustration de la disposition du cadre de pile de NAND.
tiré du livre Nand à Tetris.
Si vous n'êtes pas familier avec les dispositions de pile, voici l'idée principale derrière l'exploit. Chaque fois qu'une fonction revient, elle doit savoir où (quelle adresse mémoire d'instruction de code machine) elle doit aller pour poursuivre le flux d'exécution. Ainsi, lorsque la fonction est appelée pour la première fois, cette adresse mémoire, ainsi que d'autres données sans importance, sont temporairement stockées sur la pile dans une région mémoire appelée cadre de pile comme référence pour savoir où retourner. L'illustration décrit la position exacte de cette adresse de retour par rapport à l'appel de fonction, une position qui peut faire l'objet d'une ingénierie inverse.
Le programme permet à l'utilisateur d'écraser une seule adresse mémoire dans la RAM par n'importe quelle valeur. En mettant deux et deux ensemble, si l'utilisateur devait écraser l'adresse de retour d'un cadre de pile par l'adresse d'une autre fonction, il aurait essentiellement la possibilité d'exécuter du code arbitraire inclus dans le programme.
En effet, si vous entrez 267 comme emplacement mémoire et 1715 comme valeur à écraser, deux nombres rétro-conçus en inspectant manuellement l'espace mémoire de la pile et l'assembleur, vous verrez cette idée en action.
Il ne s'agit pas d'une vulnérabilité propre à NAND. Cela existe aussi en C ! Comme c'est cool !
Croyez-le ou non, parmi les très nombreux composants différents de la NAND, celui-ci à lui seul a pris le plus de temps à développer !
Ce programme est une simulation de créature qui utilise un simple apprentissage automatique. Il fait suite à la série codée sur l’intelligence artificielle (parties un et deux) de Code Bullet. N'oubliez pas de jeter un œil à sa chaîne, il fait des trucs vraiment cool !
Expliqué simplement :
Chaque point possède son propre « cerveau » de vecteurs d'accélération, et ils évoluent pour atteindre un objectif grâce à la sélection naturelle. À chaque génération, les points qui « meurent » plus près de l'objectif sont plus susceptibles d'être sélectionnés comme parents de la génération suivante. La reproduction provoque intrinsèquement la mutation d’une partie du cerveau, simulant ainsi de manière tout à fait efficace l’évolution naturelle.
Néanmoins, il y a beaucoup à désirer. En raison de leurs performances, le seul facteur utilisé par les points pour évoluer est leur proximité de l'objectif à leur mort, conférant à l'algorithme de sélection naturelle une faible entropie. En raison de l’utilisation de la mémoire, il existe des limites plus que satisfaisantes quant au nombre de points et à la taille de leur cerveau. Enfin, en raison de la complexité technique, le remplacement des obstacles lors de la simulation ne garantit pas que les points auront un cerveau suffisamment gros pour atteindre l'objectif. La taille du cerveau n'est déterminée qu'au début du programme.
J'ai utilisé une myriade de techniques d'optimisation pour contourner les restrictions matérielles suivantes et rendre cela possible :
Pour éviter de tourner autour du pot, je me suis contenté de documenter ces techniques et des informations supplémentaires dans la base de code de ce programme pour les personnes intéressées.
Avant de commencer, le détail le plus important à retenir concernant l’écriture de programmes dans Jack est qu’il n’y a pas de priorité pour l’opérateur ; c'est probablement pourquoi votre programme ne fonctionne pas.
Par exemple, vous devez modifier :
4 * 2 + 3 à (4 * 2) + 3
if (~x & y) à if ((~x) & y)
mais vous pouvez conserver if (y & ~x) le même car il n'y a pas d'ambiguïté d'opérateur.
Sans parenthèses, la valeur d'évaluation d'une expression ambiguë est indéfinie .
NAND possède sa propre pile technologique complète. En conséquence, NAND ne peut être programmé qu’en Jack, son langage de programmation orienté objet faiblement typé. En termes simples, Jack est C avec la syntaxe de Java.
Adoptons l'approche de l'apprentissage basé sur des exemples et plongeons-y directement.
/**
* This program prompts the user to enter a phrase
* and an energy level. Program output:
*
* Whats on your mind? Superman
* Whats your energy level? 3
* Superman!
* Superman!
* Superman!
*/
class Main {
function void main ( ) {
var String s ;
var int energy , i ;
let s = Keyboard . readLine ( "Whats on your mind? " ) ;
let energy = Keyboard . readInt ( "Whats your energy level? " ) ;
let i = 0 ;
let s = s . appendChar ( 33 ) ; // Appends the character '!'
while ( i < energy ) {
do Output . printString ( s ) ;
do Output . println ( ) ;
let i = i + 1 ;
}
}
}tiré des diapositives de la conférence Nand à Tetris.
Si vous avez déjà une certaine expérience en programmation, cela devrait vous sembler très familier ; il est clair que Jack a été fortement inspiré par Java. Main.main , le point d'entrée du programme, démontre l'utilisation de base des variables ainsi que la boucle while pour le flux de contrôle.
De plus, il utilise Keyboard.readLine et Keyboard.readInt pour lire les entrées de l'utilisateur, et Output.printString et Output.println pour imprimer la sortie à l'écran, qui sont tous définis en détail dans la référence Jack OS. Par défaut, le système d'exploitation Jack est fourni avec votre programme lors de la compilation pour permettre l'interface avec les chaînes, la mémoire, le matériel, etc.
Chaque langage de programmation possède un ensemble fixe de types de données primitifs. Jack en prend en charge trois : int , char et boolean . Vous pouvez étendre ce répertoire de base avec vos propres types de données abstraits selon vos besoins. Les connaissances préalables en programmation orientée objet sont directement transférées dans cette section.
/** Represents a point in 2D plane. */
class Point {
// The coordinates of the current point instance:
field int x , y ;
// The number of point objects constructed so far:
static int pointCount ;
/** Constructs a point and initializes
it with the given coordinates */
constructor Point new ( int ax , int ay ) {
let x = ax ;
let y = ay ;
let pointCount = pointCount + 1 ;
return this ;
}
/** Returns the x coordinate of the current point instance */
method int getx ( ) { return x ; }
/** Returns the y coordinate of the current point instance */
method int gety ( ) { return y ; }
/** Returns the number of Points constructed so far */
function int getPointCount ( ) {
return pointCount ;
}
/** Returns a point which is this
point plus the other point */
method Point plus ( Point other ) {
return Point . new ( x + other . getx ( ) ,
y + other . gety ( ) ) ;
}
/** Returns the Euclidean distance between the
current point instance and the other point */
method int distance ( Point other ) {
var int dx , dy ;
let dx = x - other . getx ( ) ;
let dy = y - other . gety ( ) ;
return Math . sqrt ( ( dx * dx ) + ( dy * dy ) ) ;
}
/** Prints the current point instance, as "(x, y)" */
method void print ( ) {
var String tmp ;
let tmp = "(" ;
do Output . printString ( tmp ) ;
do tmp . dispose ( ) ;
do Output . printInt ( x ) ;
let tmp = ", " ;
do Output . printString ( tmp ) ;
do tmp . dispose ( ) ;
do Output . printInt ( y ) ;
let tmp = ")" ;
do Output . printString ( tmp ) ;
do tmp . dispose ( ) ;
}
} var Point p1 , p2 , p3 ;
let p1 = Point . new ( 1 , 2 ) ;
let p2 = Point . new ( 3 , 4 ) ;
let p3 = p1 . plus ( p2 ) ;
do p3 . print ( ) ; // prints (4, 6)
do Output . println ( ) ;
do Output . printInt ( p1 . distance ( p2 ) ) ; // prints 5
do Output . println ( ) ;
do Output . printInt ( getPointCount ( ) ) ; // prints 3tiré des diapositives de la conférence Nand à Tetris.
Nous définissons une classe Point pour représenter un point abstrait dans l'espace. Il utilise des variables field pour déclarer les attributs par instance du type de données. Il expose les fonctions method publique que nous pouvons utiliser pour interagir avec le point, donnant à l'appelant la fonctionnalité permettant d'ajouter deux points ensemble et de calculer la distance entre deux points.
Toutes les variables field ont une portée privée. Si vous souhaitez obtenir ou définir ces variables en dehors de la déclaration de classe, ces variables doivent avoir des fonctions method correspondantes pour fournir cette fonctionnalité.
Omis de l'exemple de code pour rester dans le sujet, il est habituel que les classes de données définissent des méthodes dispose pour la désallocation une fois que les objets ne sont plus nécessaires. Voir Gestion manuelle de la mémoire.
Si nécessaire, voici une référence pour la syntaxe d’appel function et method .
class Foo {
...
method void f ( ) {
var Bar b ; // Declares a local variable of class type Bar
var int i ; // Declares a local variable of primitive type int
do g ( ) ; // Calls method g of the current class on the current object instance
// Note: Cannot be called from within a function (static method)
do Foo . p ( 3 ) ; // Calls function p of the current class;
// Note: A function call must be preceded by the class name
do Bar . h ( ) ; // Calls function h of class Bar
let b = Bar . r ( ) ; // Calls function or constructor r of class Bar
do b . q ( ) ; // Calls method q of class Bar on the b object
}
}tiré des diapositives de la conférence Nand à Tetris.
Rappelez-vous comment nous avons dit que Jack était similaire à Java ? C’était une façade, ou au mieux trompeur. Alors que Java est fortement typé et, en tant que tel, prend en charge des fonctionnalités de type complexes telles que le downcasting, le polymorphisme et l'héritage, Jack ne prend en charge aucun de ces éléments et n'a qu'un seul type sous le capot : l'entier signé de 16 bits. C'est la principale raison pour laquelle Jack est si faiblement typé. En effet, le compilateur ne se souciera pas de savoir si vous mélangez et faites correspondre différents types dans les affectations et les opérations.
var char c ;
var String s ;
let c = 65 ; // 'A'
// Equivalently
let s = "A" ;
let c = s . charAt ( 0 ) ; var Array a ;
let a = 5000 ;
let a [ 100 ] = 77 ; // RAM[5100] = 77 var Array arr ;
var String helloWorld ;
let helloWorld = "Hello World!"
let arr = Array . new ( 4 ) ; // Arrays are not strictly typed
let arr [ 0 ] = 12 ;
let arr [ 1 ] = false ;
let arr [ 2 ] = Point . new ( 5 , 6 ) ;
let arr [ 3 ] = helloWorld ; class Complex {
field int real ;
field int imaginary ;
...
}
. . .
var Complex c ;
var Array a ;
let a = Array . new ( 2 ) ;
let a [ 0 ] = 7 ;
let a [ 1 ] = 8 ;
let c = a ; // c == Complex(7, 8)
// Works because it matches the memory layout
// of the Complex typetous les segments de code extraits des diapositives du cours Nand à Tetris.
Ne le prenez pas mal : Jack fournit toujours un modèle orienté objet puissant et fonctionnel. Ces informations ont pour but de vous aider à comprendre quand et comment effectuer les conversions de type selon vos besoins.
Disons que vous êtes un fou amoureux des chats, tout comme moi ! Et vous vouliez écrire ce programme pour montrer à quel point vous adorez les chats.
class Main {
function void main ( ) {
while ( true ) {
do Output . printString ( "Kittens are so adorable! " ) ;
}
}
}Vous serez peut-être surpris de remarquer qu'après quelques secondes, le programme plantera avec "ERR6", ou un débordement de tas !
Jack est un langage de programmation géré manuellement en mémoire. Cela signifie que vous devez être vigilant pour désallouer correctement la mémoire qui n'est plus nécessaire, sinon le Jack OS pensera autrement et facilitera une fuite de mémoire. Le conseil de bonne pratique consiste à proposer une méthode dispose pour chaque classe qui représente un objet qui encapsule correctement cette désallocation. Ainsi, lorsque les objets ne sont plus nécessaires, vous pouvez appeler leurs méthodes dispose pour vous assurer de ne pas manquer de mémoire.
Si vous avez programmé dans d'autres langages gérés manuellement en mémoire, comme C, cela devrait vous sembler très familier. Une différence clé est que Jack OS stocke les tableaux et les chaînes sur le tas plutôt que sur la pile, ce qui explique pourquoi le programme plante avec un débordement de tas.
Réparons ce programme pour nos amis fanatiques félins.
class Main {
function void main ( ) {
var String s ;
while ( true ) {
let s = "Kittens are so adorable! " ;
do Output . printString ( s ) ;
do s . dispose ( ) ;
}
}
}Alternativement, vous pouvez allouer de la mémoire à la chaîne une seule fois.
class Main {
function void main ( ) {
var String s ;
let s = "Kittens are so adorable! " ;
while ( true ) {
do Output . printString ( s ) ;
}
}
}Vous remarquerez que non seulement ces versions alternatives impriment la chaîne beaucoup plus rapidement, mais que cette fois elles s'imprimeront pour toujours ! Hourra!
Jetons un coup d'œil rapide à String.dispose afin que vous puissiez mieux comprendre comment écrire vos propres méthodes dispose .
method void dispose ( ) {
do stringArray . dispose ( ) ;
do Memory . deAlloc ( this ) ;
} Array.dispose appelé par stringArray
method void dispose ( ) {
do Memory . deAlloc ( this ) ;
} Les méthodes dispose appropriées doivent d'abord appeler de manière appropriée dispose sur leurs variables de champ, puis terminer par do Memory.deAlloc(this); pour libérer l'instance d'objet elle-même.
Compte tenu du caractère primitif de Jack et de NAND, les coups de pied dans le langage sont inévitables. J'ai compilé les exemples suivants de comportements non définis dont vous devez être conscient, classés (à mon avis) du plus important au moins important.
J'ai trouvé cette mise en garde si importante que je l'ai déplacée vers le début de cette section.
Les expressions de Jack
a > b
a < bsont d’une simplicité trompeuse. Elles ne sont pas toujours mathématiquement correctes, et sont respectivement équivalentes aux expressions Java
( ( a - b ) & ( 1 << 15 ) ) == 0 && a != b
( ( a - b ) & ( 1 << 15 ) ) != 0 C'est quoi la nuance ? L'implémentation de la machine virtuelle convertit a > b en a - b > 0 . Voici le problème : a - b peut déborder :(
À quoi correspond 20000 > -20000 ? La machine virtuelle transpile cela en 20000 - (-20000) > 0 qui est évalué à -25336 > 0 . Malheureusement, la réponse est false .
Cependant, 20000 > -10000 est évalué à 30000 > 0 , ou true .
Comme vous l'avez peut-être deviné, si la distance absolue entre a et b est supérieure à 32 767, a > b et a < b sont faux. Sinon, tu vas bien.
Ce n'est pas un bug d'implémentation, mais plutôt une incohérence avec Nand et Tetris lui-même. Plus d'informations ici. Pour des raisons de compatibilité, ce comportement ne sera pas corrigé.
-32768 est unique en son genre. C'est le seul nombre qui détient la propriété telle que -(-32768) = -32768, un singleton sans contrepartie positive * . Cela peut conduire à des erreurs de cohérence et à des erreurs de logique.
/**
* Program output:
* --.)*(
*/
class Main {
function void main ( ) {
// Note that -32768 must instead be written as ~32767
// because the CPU can't load a number that large
do Output . printInt ( ~ 32767 ) ;
}
} Output.printInt s'attend en interne à ce que Math.abs renvoie un nombre positif. Ce n'est pas le cas avec -32768, donc le Jack OS fonctionne mal.
Votre principale préoccupation devrait être de gérer les erreurs logiques avec l’opérateur négatif. En tant que programmeur, si vous souhaitez garantir que le négatif d'un nombre négatif est positif, il est de votre responsabilité de vérifier le cas -32768 et de prendre les mesures appropriées.
* Cela est vrai car l'ALU de NAND traite en interne l'expression Jack -x comme ~(x - 1) . Fixons x à -32768 et évaluons-le étape par étape. Voici les représentations binaires en complément à deux de 16 bits correspondantes du calcul :
x = 1000 0000 0000 0000
x - 1 = 0111 1111 1111 1111
~(x - 1) = 1000 0000 0000 0000 = x
C'est la même chose ! Que s'est-il passé ici ? Parce que NAND est une machine 16 bits, -32768 est le seul nombre tel que si vous en soustrayez un, vous obtenez ses bits inversés. En d'autres termes, -32768 satisfait x - 1 = ~x , simplifiant l'expression en ~(~x) ou simplement x .
Celui-ci est explicite, voici donc une brève démonstration.
/**
* Program output:
* I have 818 cookies.
*/
class Main {
function void main ( ) {
do Main . cookies ( ) ;
}
function void cookies ( int a ) {
do Output . printString ( "I have " ) ;
do Output . printInt ( a ) ;
do Output . printString ( " cookies." ) ;
}
} En revanche, appeler une fonction avec trop d’ arguments est parfaitement valable. Vous pouvez utiliser le mot-clé arguments pour indexer des arguments de fonction supplémentaires. Notez qu'il n'y a pas d'indicateur pour le nombre d'arguments.
Vous pouvez utiliser Array pour convertir une variable dans n'importe quel autre type. L’appel de méthodes d’instance qui n’existent pas sur des variables transtypées est un comportement non défini ; le compilateur n'est pas assez intelligent pour comprendre quand vous faites cela.
/**
* Program output:
* 4
*/
class Main {
constructor Main new ( ) {
return this ;
}
function void main ( ) {
var Array a ;
var Main b ;
var String c ;
let a = Array . new ( 1 ) ;
let b = Main . new ( ) ;
let a [ 0 ] = b ;
let c = a [ 0 ] ;
// Invalidly calling `String.length` on an instance of `Main`.
do Output . printInt ( c . length ( ) ) ;
}
} Voir le programme Overflow pour un exemple détaillé.
La modification des trames de pile ou des registres internes qui résident respectivement aux adresses mémoire 256 à 2047 et 1 à 15 peut conduire à un comportement indéfini. Cela n'est généralement pas possible sans une mauvaise utilisation Memory.poke ou de l'indexation de tableau négative. Consultez le programme SecretPassword pour un exemple détaillé.
NAND propose une validation de programme pour les fichiers .jack mais pas pour les fichiers .vm . Cela signifie que le compilateur de machine virtuelle NAND vous donne carte blanche pour appeler des fonctions inexistantes, référencer des variables non attribuées ou effectuer toute autre opération de mémoire logiquement invalide. Dans la plupart des cas de comportement indéfini, la machine virtuelle s'échappera et l'écran n'affichera tout simplement rien. Il sera de votre responsabilité de déboguer le programme vous-même.
Depuis son essor dans les années 1970, il y a une bonne raison pour laquelle l'informatique 16 bits est tombée en disgrâce à l'ère moderne. Comparé à l'informatique 32 bits ou 64 bits, l'informatique 16 bits offrait une puissance de traitement et une capacité de mémoire limitées qui ne répondaient tout simplement pas aux exigences des logiciels et applications contemporains.
NAND ne fait pas exception à cette réalité.
tiré des diapositives de la conférence Nand à Tetris.
Par rapport à votre MacBook 16 GiB, la NAND profite d'un maigre 4 KiB de RAM, soit un ratio de 0,00002% ! Malgré cela, c'était suffisant pour nous emmener sur la lune, alors qui peut dire que NAND ne le peut pas non plus.
Le Jack OS réserve 14 336 adresses mémoire
