No
A
N y alimentado
Dispositivo
es una computadora de 16 bits equivalente a Turing hecha completamente de un reloj y puertas NAND emuladas en la web. NAND presenta su propia CPU, lenguaje de código de máquina, lenguaje ensamblador, ensamblador, lenguaje de máquina virtual, traductor de máquina virtual, lenguaje de programación, compilador, IDE e interfaz de usuario. NAND se basa en la plataforma Jack-VM-Hack especificada en el curso Nand to Tetris y su libro asociado.
Un programa simple que ingresa algunos números y calcula su promedio, mostrando el flujo de control, operaciones aritméticas, E/S y asignación de memoria dinámica.
Salida del programa:
How many numbers? 4
Enter a number: 100
Enter a number: 42
Enter a number: 400
Enter a number: 300
The average is 210Este programa fue proporcionado por el paquete de software Nand to Tetris.
El juego de Pong, que muestra el modelo orientado a objetos del lenguaje. Utilice las teclas de flecha para mover la paleta hacia la izquierda y hacia la derecha para hacer rebotar una pelota. Con cada rebote, la paleta se hace más pequeña y el juego termina cuando la pelota golpea la parte inferior de la pantalla.
Este programa fue proporcionado por el paquete de software Nand to Tetris.
El juego de 2048, que muestra recursividad y lógica de aplicación compleja. Utilice las teclas de flecha para mover los números alrededor de la cuadrícula de 4x4. Los mismos números se combinan en su suma cuando se mueven entre sí. Una vez que se alcanza la ficha 2048, ganas el juego, aunque puedes seguir jugando hasta que pierdas. Pierdes el juego cuando el tablero está lleno y no puedes hacer más movimientos.
Un programa que provoca deliberadamente un desbordamiento de pila mediante recursividad infinita para realizar un escape de la máquina virtual. Aprovecha el hecho de que no hay comprobaciones de tiempo de ejecución para evitar un desbordamiento de la pila. Ninguna otra plataforma moderna te permitirá hacer esto :-)
Al ejecutarse, el programa imprimirá constantemente el puntero de la pila en la pantalla. Una vez que este valor mostrado exceda 2048, la pila habrá llegado al final de su espacio de memoria previsto y se derramará en el espacio de memoria del montón, lo que provocará que la declaración de impresión no funcione correctamente de manera explosiva:
Vale la pena señalar dos cosas de notable interés.
Si ejecuta este programa en una RAM vacía llena de ceros (puede borrar la RAM a través de la interfaz de usuario), notará que el programa se reinicia a mitad de su ejecución a pesar de no presionar el botón "Restablecer". Por qué sucede esto es simple: el tiempo de ejecución con jailbreak ejecuta una instrucción que establece el valor del contador del programa en 0, diciéndole efectivamente al programa que salte a la primera instrucción y comience de nuevo.
Si ejecuta el programa de ejemplo GeneticAlgorithm y luego lo ejecuta inmediatamente después, el programa en su alboroto lee la memoria RAM antigua que simplemente nunca se sobrescribió.
Un programa que aprovecha el hecho de que el tiempo de ejecución no impide la destrucción de la pila para llamar a una función que de otro modo sería inaccesible. Para comprender cómo funciona esto, examinemos esta ilustración del diseño del marco de pila de NAND.
tomado del libro Nand to Tetris.
Si no está familiarizado con los diseños de pila, esta es la idea principal detrás del exploit. Siempre que una función regresa, necesita saber dónde (qué dirección de memoria de instrucción de código de máquina) debe ir para continuar con el flujo de ejecución. Entonces, cuando se llama a la función por primera vez, esta dirección de memoria, junto con algunos otros datos sin importancia, se almacena temporalmente en la pila en una región de memoria denominada marco de pila como referencia de dónde regresar. La ilustración describe la posición exacta de esta dirección de retorno en relación con la llamada a la función, una posición que se puede aplicar mediante ingeniería inversa.
El programa permite al usuario sobrescribir una única dirección de memoria en la RAM con cualquier valor. Sumando dos y dos, si el usuario sobrescribiera la dirección de retorno de un marco de pila con la dirección de otra función, esencialmente obtendría la capacidad de ejecutar código arbitrario incluido en el programa.
De hecho, si ingresa 267 como ubicación de memoria y 1715 como valor a sobrescribir, dos números se realizan ingeniería inversa inspeccionando manualmente el espacio de memoria de la pila y el ensamblador, verá esta idea en acción.
Esta no es una vulnerabilidad exclusiva de NAND. ¡También existe en C! ¡Qué genial!
Lo creas o no, de los muchos, muchos componentes diferentes de NAND, ¡este por sí solo fue el que tomó más tiempo en desarrollarse!
Este programa es una simulación de criaturas que utiliza aprendizaje automático simple. Sigue la serie codificada por inteligencia artificial (partes uno y dos) de Code Bullet. Asegúrate de visitar su canal, ¡hace cosas realmente interesantes!
Explicado simplemente:
Cada punto tiene su propio "cerebro" de vectores de aceleración, y estos evolucionan para alcanzar una meta mediante selección natural. En cada generación, los puntos que "mueren" más cerca de la meta tienen más probabilidades de ser seleccionados como padres para la próxima generación. La reproducción causa inherentemente que parte del cerebro mute, simulando de manera totalmente efectiva la evolución natural.
Sin embargo, hay mucho que desear. Debido al rendimiento, el único factor que utilizan los puntos para evolucionar es su cercanía a la meta al morir, lo que dota al algoritmo de selección natural de baja entropía. Debido al uso de la memoria, existen límites menores que satisfactorios en la cantidad de puntos y el tamaño de sus cerebros. Por último, debido a la complejidad técnica, volver a colocar obstáculos durante la simulación no garantiza que los puntos tengan cerebros lo suficientemente grandes como para alcanzar la meta. Los tamaños del cerebro sólo se determinan al comienzo del programa.
He utilizado una gran variedad de técnicas de optimización para sortear las siguientes restricciones de hardware y hacer esto posible:
Para evitar andar con rodeos, me he limitado a documentar estas técnicas y conocimientos adicionales en el código base de este programa para aquellos interesados.
Antes de comenzar, el detalle más importante que debemos recordar al escribir programas en Jack es que no hay prioridad de operador; Probablemente esta sea la razón por la que su programa no funciona.
Por ejemplo, deberías cambiar:
4 * 2 + 3 a (4 * 2) + 3
if (~x & y) a if ((~x) & y)
pero puede mantener if (y & ~x) igual ya que no hay ambigüedad en el operador.
Sin paréntesis, el valor de evaluación de una expresión ambigua no está definido .
NAND cuenta con su propia pila tecnológica completa. Como consecuencia, NAND sólo se puede programar en Jack, su lenguaje de programación orientado a objetos débilmente tipado. En términos sencillos, Jack es C con la sintaxis de Java.
Tomemos el enfoque del aprendizaje basado en ejemplos y profundicemos.
/**
* 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 ;
}
}
}tomado de las diapositivas de la conferencia de Nand a Tetris.
Si ya ha tenido algo de experiencia con la programación, esto le resultará muy familiar; Está claro que Jack se inspiró en gran medida en Java. Main.main , el punto de entrada al programa, demuestra el uso básico de variables así como el bucle while para controlar el flujo.
Además, utiliza Keyboard.readLine y Keyboard.readInt para leer la entrada del usuario, y Output.printString y Output.println para imprimir la salida en la pantalla, todos los cuales se definen en detalle en la referencia de Jack OS. De forma predeterminada, Jack OS se incluye con su programa durante la compilación para permitir la interfaz con cadenas, memoria, hardware y más.
Cada lenguaje de programación tiene un conjunto fijo de tipos de datos primitivos. Jack admite tres: int , char y boolean . Puede ampliar este repertorio básico con sus propios tipos de datos abstractos según sea necesario. Los conocimientos previos sobre programación orientada a objetos se trasladan directamente a esta sección.
/** 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 3tomado de las diapositivas de la conferencia de Nand a Tetris.
Definimos una clase Point para representar un punto abstracto en el espacio. Utiliza variables field para declarar atributos por instancia del tipo de datos. Expone funciones method públicos que podemos usar para interactuar con el punto, brindando a la persona que llama la funcionalidad de sumar dos puntos y calcular la distancia entre dos puntos.
Todas las variables field tienen un alcance privado. Si desea obtener o configurar estas variables desde fuera de la declaración de clase, estas variables deben tener funciones method correspondientes para proporcionar esta funcionalidad.
Omitido en el ejemplo de código para mantener el tema, es habitual que las clases de datos definan métodos dispose para la desasignación una vez que los objetos ya no son necesarios. Consulte Gestión manual de la memoria.
Si es necesario, aquí hay una referencia para la sintaxis de llamada a function y 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
}
}tomado de las diapositivas de la conferencia de Nand a Tetris.
¿Recuerdas que dijimos que Jack era similar a Java? Eso era una fachada o, en el mejor de los casos, engañosa. Si bien Java está fuertemente tipado y, como tal, admite características de tipos complejos como conversión descendente, polimorfismo y herencia, Jack no admite ninguna de estas y solo tiene un tipo bajo el capó: el entero de 16 bits con signo. Ésta es la razón principal por la que Jack tiene un tipo tan débil. De hecho, al compilador no le importará si mezcla y combina diferentes tipos en asignaciones y operaciones.
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 typetodos los segmentos de código tomados de las diapositivas de la conferencia de Nand a Tetris.
No lo tome a mal: Jack todavía proporciona un modelo orientado a objetos potente y funcional. Esta información pretende ayudarle a comprender cuándo y cómo debe realizar conversiones de tipos según sea necesario.
¡Digamos que eres un loco amante de los gatos, como yo! Y querías escribir este programa para mostrar cuánto adoras a los gatos.
class Main {
function void main ( ) {
while ( true ) {
do Output . printString ( "Kittens are so adorable! " ) ;
}
}
}Es posible que se sorprenda al notar que después de unos segundos, el programa fallará con "ERR6" o un desbordamiento del montón.
Jack es un lenguaje de programación administrado manualmente por memoria. Esto significa que debe estar atento para desasignar adecuadamente la memoria que ya no es necesaria; de lo contrario, Jack OS pensará lo contrario y facilitará una pérdida de memoria. El consejo de mejores prácticas es incluir un método dispose para cada clase que represente un objeto que encapsule adecuadamente esta desasignación. Por lo tanto, cuando los objetos ya no sean necesarios, puede llamar a sus métodos dispose para asegurarse de que eventualmente no se quedará sin memoria del montón.
Si ha programado en otros lenguajes administrados manualmente en memoria, como C, esto le resultará muy familiar. Una diferencia clave es que Jack OS almacena matrices y cadenas en el montón en lugar de en la pila, lo que indica por qué el programa falla con un desbordamiento del montón.
Arreglemos este programa para nuestros compañeros fanáticos felinos.
class Main {
function void main ( ) {
var String s ;
while ( true ) {
let s = "Kittens are so adorable! " ;
do Output . printString ( s ) ;
do s . dispose ( ) ;
}
}
}Alternativamente, puede asignar memoria para la cadena sólo una vez.
class Main {
function void main ( ) {
var String s ;
let s = "Kittens are so adorable! " ;
while ( true ) {
do Output . printString ( s ) ;
}
}
}Notarás que estas versiones alternativas no solo imprimen la cadena mucho más rápido, sino que esta vez se imprimirán para siempre. ¡Hurra!
Echemos un vistazo rápidamente a String.dispose para que pueda comprender mejor cómo escribir sus propios métodos dispose .
method void dispose ( ) {
do stringArray . dispose ( ) ;
do Memory . deAlloc ( this ) ;
} Array.dispose llamado por stringArray
method void dispose ( ) {
do Memory . deAlloc ( this ) ;
} Los métodos dispose adecuados primero deben llamar adecuadamente dispose en sus variables de campo y luego terminar con do Memory.deAlloc(this); para desasignar la instancia del objeto en sí.
Con lo primitivos que son Jack y NAND, las pistolas dentro del lenguaje son inevitables. He recopilado los siguientes casos de comportamiento indefinido que debes tener en cuenta, ordenados (en mi opinión) de más importante a menos importante.
Esta advertencia me pareció tan importante que la moví al principio de esta sección.
Las expresiones de Jack.
a > b
a < bson engañosamente simples. No siempre son matemáticamente correctos y son respectivamente equivalentes a las expresiones de Java.
( ( a - b ) & ( 1 << 15 ) ) == 0 && a != b
( ( a - b ) & ( 1 << 15 ) ) != 0 ¿Qué pasa con el matiz? La implementación de la máquina virtual convierte a > b en a - b > 0 . Aquí está el problema: a - b puede desbordarse :(
¿A qué se evalúa 20000 > -20000 ? La máquina virtual transpila esto a 20000 - (-20000) > 0 que se evalúa como -25336 > 0 . Lamentablemente, la respuesta es false .
Sin embargo, 20000 > -10000 se evalúa como 30000 > 0 o true .
Como habrás imaginado, si la distancia absoluta entre a y b es mayor que 32767, a > b y a < b están equivocados. De lo contrario, estás bien.
Esto no es un error de implementación, sino más bien una inconsistencia entre Nand y Tetris. Más sobre esto aquí. Por motivos de compatibilidad, este comportamiento no se solucionará.
-32768 es único en su tipo. Es el único número que tiene la propiedad tal que -(-32768) = -32768, un singleton sin contraparte positiva * . Esto puede conducir a errores lógicos y falta de solidez.
/**
* 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 espera internamente que Math.abs devuelva un número positivo. Este no es el caso con -32768, por lo que Jack OS no funciona correctamente.
Su principal preocupación debería ser manejar los errores lógicos con el operador negativo. Como programador, si desea garantizar que el negativo de un número negativo sea positivo, es su responsabilidad verificar el caso de -32768 y tomar las medidas adecuadas.
* Esto es cierto porque la ALU de NAND procesa internamente la expresión Jack -x como ~(x - 1) . Establezcamos x en -32768 y evalúelo paso a paso. Aquí están las representaciones binarias en complemento a dos de 16 bits correspondientes del cálculo:
x = 1000 0000 0000 0000
x - 1 = 0111 1111 1111 1111
~(x - 1) = 1000 0000 0000 0000 = x
¡Es lo mismo! ¿Qué pasó aquí? Debido a que NAND es una máquina de 16 bits, -32768 es el único número tal que si le restas uno, obtienes sus bits invertidos. En otras palabras, -32768 satisface x - 1 = ~x , simplificando la expresión a ~(~x) o simplemente x .
Éste se explica por sí mismo, así que aquí hay una breve demostración.
/**
* 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." ) ;
}
} Por otro lado, llamar a una función con demasiados argumentos es perfectamente válido. Puede utilizar la palabra clave arguments para indexar argumentos de funciones adicionales. Tenga en cuenta que no hay ningún indicador para el recuento de argumentos.
Puede utilizar Array para convertir una variable en cualquier otro tipo. Llamar a métodos de instancia que no existen en variables de tipo convertido es un comportamiento indefinido; el compilador no es lo suficientemente inteligente como para darse cuenta cuando estás haciendo esto.
/**
* 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 ( ) ) ;
}
} Consulte el programa Overflow para ver un ejemplo detallado.
La modificación de los marcos de pila o los registros internos que residen respectivamente en las direcciones de memoria 256 a 2047 y 1 a 15 puede provocar un comportamiento indefinido. Por lo general, esto no es posible sin un mal uso Memory.poke o una indexación de matriz negativa. Consulte el programa SecretPassword para ver un ejemplo detallado.
NAND ofrece validación de programa para archivos .jack pero no para archivos .vm . Esto significa que el compilador de máquinas virtuales de NAND le da total libertad para llamar a funciones inexistentes, hacer referencia a variables no asignadas o realizar cualquier otra operación de memoria lógicamente no válida. En la mayoría de los casos de comportamiento indefinido, la máquina virtual escapará y la pantalla simplemente no mostrará nada. Será su responsabilidad depurar el programa usted mismo.
Desde su auge en la década de 1970, hay una buena razón por la que la informática de 16 bits ha caído en desgracia en la era moderna. En comparación con la informática de 32 o 64 bits, la informática de 16 bits ofrecía una potencia de procesamiento y una capacidad de memoria limitadas que simplemente no satisfacían las demandas del software y las aplicaciones contemporáneas.
NAND no es una excepción a esta realidad.
tomado de las diapositivas de la conferencia de Nand a Tetris.
En comparación con su MacBook de 16 GiB, NAND disfruta de unos escasos 4 KiB de RAM, ¡una proporción del 0,00002% ! A pesar de esto, fue suficiente para llevarnos a la luna, así que quién puede decir que NAND tampoco puede.
El Jack OS reserva 14.336 direcciones de memoria
