Não
UM
N e alimentado
Dispositivo
é um computador equivalente a Turing de 16 bits feito inteiramente a partir de um relógio e portas NAND emuladas na web. NAND possui sua própria CPU, linguagem de código de máquina, linguagem assembly, assembler, linguagem de máquina virtual, tradutor de máquina virtual, linguagem de programação, compilador, IDE e interface de usuário. NAND é baseado na plataforma Jack-VM-Hack especificada no curso Nand to Tetris e seu livro associado.
Um programa simples que insere alguns números e calcula sua média, mostrando fluxo de controle, operações aritméticas, E/S e alocação dinâmica de memória.
Saída do 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 foi fornecido pelo pacote de software Nand to Tetris.
O jogo Pong, mostrando o modelo orientado a objetos da linguagem. Use as setas do teclado para mover a raquete para a esquerda e para a direita para quicar a bola. A cada salto, a raquete fica menor e o jogo termina quando a bola atinge a parte inferior da tela.
Este programa foi fornecido pelo pacote de software Nand to Tetris.
O jogo de 2048, exibindo recursão e lógica de aplicação complexa. Use as setas do teclado para mover os números pela grade 4x4. Os mesmos números se combinam em sua soma quando movidos uns para os outros. Assim que o bloco 2048 for alcançado, você ganha o jogo, mas pode continuar jogando até perder. Você perde o jogo quando o tabuleiro está cheio e você não pode fazer mais movimentos.
Um programa que causa deliberadamente um estouro de pilha por meio de recursão infinita para executar um escape de máquina virtual. Ele aproveita o fato de que não há verificações de tempo de execução para evitar um estouro de pilha. Nenhuma outra plataforma moderna permitirá que você faça isso :-)
Ao ser executado, o programa imprimirá constantemente o ponteiro da pilha na tela. Quando esse valor exibido exceder 2.048, a pilha terá atingido o fim do espaço de memória pretendido e se espalhará pelo espaço de memória heap, fazendo com que a instrução print funcione mal de forma explosiva:
Duas coisas de notável interesse merecem ser destacadas.
Se você executar este programa em uma RAM vazia cheia de zeros (você pode limpar a RAM através da interface do usuário), notará que o programa se reinicia no meio de sua execução, apesar de não pressionar o botão "Reset". O motivo pelo qual isso acontece é simples: o tempo de execução jailbroken executa uma instrução que define o valor do contador do programa como 0, efetivamente informando ao programa para pular para a primeira instrução e recomeçar.
Se você executar o programa de exemplo GeneticAlgorithm e, em seguida, executá-lo imediatamente depois, o programa em sua fúria lerá a memória RAM antiga que simplesmente nunca foi substituída.
Um programa que explora o fato de que o tempo de execução não impede o esmagamento da pilha para chamar uma função que de outra forma seria inacessível. Para entender como isso funciona, vamos examinar esta ilustração do layout do stack frame da NAND.
retirado do livro Nand to Tetris.
Se você não está familiarizado com layouts de pilha, aqui está a ideia principal por trás do exploit. Sempre que uma função retorna, ela precisa saber para onde (qual endereço de memória de instruções de código de máquina) ela deve ir para prosseguir com o fluxo de execução. Portanto, quando a função é chamada pela primeira vez, esse endereço de memória, junto com alguns outros dados sem importância, é armazenado temporariamente na pilha em uma região de memória chamada quadro de pilha, como referência para onde retornar. A ilustração descreve a posição exata desse endereço de retorno em relação à chamada de função, uma posição que pode sofrer engenharia reversa.
O programa permite ao usuário substituir um único endereço de memória na RAM por qualquer valor. Somando dois mais dois, se o usuário substituir o endereço de retorno de um quadro de pilha pelo endereço de outra função, ele essencialmente ganhará a capacidade de executar código arbitrário incluído no programa.
Na verdade, se você inserir 267 como o local da memória e 1715 como o valor a ser sobrescrito, dois números submetidos à engenharia reversa pela inspeção manual do espaço de memória da pilha e do montador, você verá essa ideia em ação.
Esta não é uma vulnerabilidade exclusiva da NAND. Também existe em C! Que legal!
Acredite ou não, dentre os muitos componentes diferentes do NAND, este sozinho foi o que levou mais tempo para ser desenvolvido!
Este programa é uma simulação de criatura que utiliza aprendizado de máquina simples. Segue a série codificada de inteligência artificial (partes um e dois) do Code Bullet. Não deixe de conferir o canal dele, ele faz coisas muito legais!
Explicado de forma simples:
Cada ponto tem seu próprio “cérebro” de vetores de aceleração e eles evoluem para atingir uma meta por meio da seleção natural. A cada geração, os pontos que “morrem” mais perto da meta têm maior probabilidade de serem selecionados como pais da próxima geração. A reprodução faz com que parte do cérebro sofra mutações, simulando de forma totalmente eficaz a evolução natural.
No entanto, há muito a desejar. Devido ao desempenho, o único fator que os pontos usam para evoluir é a proximidade do objetivo após a morte, dotando o algoritmo de seleção natural de baixa entropia. Devido ao uso da memória, existem limites menores do que satisfatórios no número de pontos e no tamanho de seus cérebros. Por último, devido à complexidade técnica, a substituição de obstáculos durante a simulação não garante que os pontos tenham cérebros grandes o suficiente para atingir a meta. O tamanho do cérebro só é determinado no início do programa.
Utilizei uma infinidade de técnicas de otimização para contornar as seguintes restrições de hardware e tornar isso possível:
Para evitar rodeios, limitei-me a documentar essas técnicas e insights adicionais na base de código deste programa para os interessados.
Antes de começarmos, o detalhe mais importante a lembrar sobre a escrita de programas em Jack é que não há prioridade de operador; provavelmente é por isso que seu programa não está funcionando.
Por exemplo, você deve alterar:
4 * 2 + 3 a (4 * 2) + 3
if (~x & y) para if ((~x) & y)
mas você pode manter if (y & ~x) igual, pois não há ambiguidade do operador.
Sem parênteses, o valor de avaliação de uma expressão ambígua é indefinido .
A NAND possui sua própria pilha de tecnologia completa. Como consequência, o NAND só pode ser programado em Jack, sua linguagem de programação orientada a objetos de tipo fraco. Em termos leigos, Jack é C com a sintaxe de Java.
Vamos adotar a abordagem de aprendizagem baseada em exemplos e mergulhar de cabeça.
/**
* 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 ;
}
}
}retirado dos slides da palestra Nand to Tetris.
Se você já tem alguma experiência com programação, isso deve lhe parecer muito familiar; está claro que Jack foi fortemente inspirado em Java. Main.main , o ponto de entrada do programa, demonstra o uso básico de variáveis, bem como o loop while para fluxo de controle.
Além disso, ele usa Keyboard.readLine e Keyboard.readInt para ler a entrada do usuário, e Output.printString e Output.println para imprimir a saída na tela - todos definidos em detalhes na Referência do Jack OS. Por padrão, o Jack OS é fornecido com o seu programa durante a compilação para permitir a interface com strings, memória, hardware e muito mais.
Cada linguagem de programação possui um conjunto fixo de tipos de dados primitivos. Jack suporta três: int , char e boolean . Você pode estender esse repertório básico com seus próprios tipos de dados abstratos, conforme necessário. O conhecimento prévio sobre programação orientada a objetos é transferido diretamente para esta seção.
/** 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 3retirado dos slides da palestra Nand to Tetris.
Definimos uma classe Point para representar um ponto abstrato no espaço. Ele usa variáveis field para declarar atributos por instância do tipo de dados. Ele expõe funções method públicos que podemos usar para fazer interface com o ponto, dando ao chamador a funcionalidade de somar dois pontos e calcular a distância entre dois pontos.
Todas as variáveis field têm escopo privado. Se você deseja obter ou definir essas variáveis fora da declaração da classe, essas variáveis devem ter funções method correspondentes para fornecer esta funcionalidade.
Omitido do exemplo de código para permanecer no tópico, é comum que as classes de dados definam métodos dispose para desalocação quando os objetos não forem mais necessários. Consulte Gerenciamento manual de memória.
Se necessário, aqui está uma referência para sintaxe de chamada function e 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
}
}retirado dos slides da palestra Nand to Tetris.
Lembra como dissemos que Jack era semelhante a Java? Isso foi uma fachada ou, na melhor das hipóteses, enganosa. Embora Java seja fortemente tipado e, como tal, suporte recursos de tipos complexos, como downcasting, polimorfismo e herança, Jack não oferece suporte a nada disso e possui apenas um tipo subjacente: o inteiro assinado de 16 bits. Esta é a principal razão pela qual Jack tem uma digitação tão fraca. Na verdade, o compilador não se importará se você misturar e combinar diferentes tipos de atribuições e operações.
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 os segmentos de código retirados dos slides da palestra Nand to Tetris.
Não leve a mal – Jack ainda fornece um modelo orientado a objetos poderoso e funcional. Este insight pretende ajudá-lo a entender quando e como realizar conversões de tipo conforme necessário.
Digamos que você seja um amante louco de gatos, assim como eu! E você queria escrever este programa para mostrar o quanto você adora gatos.
class Main {
function void main ( ) {
while ( true ) {
do Output . printString ( "Kittens are so adorable! " ) ;
}
}
}Você pode se surpreender ao notar que, após alguns segundos, o programa irá travar com “ERR6” ou um heap overflow!
Jack é uma linguagem de programação gerenciada manualmente pela memória. Isso significa que você deve estar atento para desalocar adequadamente a memória que não é mais necessária, caso contrário o Jack OS pensará o contrário e facilitará um vazamento de memória. O conselho de melhores práticas é apresentar um método dispose para cada classe que represente um objeto que encapsule adequadamente essa desalocação. Assim, quando os objetos não forem mais necessários, você poderá chamar seus métodos dispose para garantir que não ficará sem memória heap.
Se você programou em outras linguagens gerenciadas manualmente pela memória, como C, isso deve parecer muito familiar. Uma diferença importante é que o Jack OS armazena arrays e strings no heap em vez de na pilha, sugerindo por que o programa trava com um heap overflow.
Vamos consertar esse programa para nossos companheiros fanáticos por 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, você poderia alocar memória para a string apenas uma vez.
class Main {
function void main ( ) {
var String s ;
let s = "Kittens are so adorable! " ;
while ( true ) {
do Output . printString ( s ) ;
}
}
}Você notará que essas versões alternativas não apenas imprimem a string muito mais rápido, mas desta vez elas imprimirão para sempre! Viva!
Vamos dar uma olhada rápida em String.dispose para que você possa entender melhor como escrever seus próprios métodos dispose .
method void dispose ( ) {
do stringArray . dispose ( ) ;
do Memory . deAlloc ( this ) ;
} Array.dispose chamado por stringArray
method void dispose ( ) {
do Memory . deAlloc ( this ) ;
} Os métodos dispose adequados devem primeiro chamar dispose apropriadamente em suas variáveis de campo e depois terminar com do Memory.deAlloc(this); para desalocar a própria instância do objeto.
Com o quão primitivos Jack e NAND são, as armas de fogo dentro da linguagem são inevitáveis. Compilei os seguintes exemplos de comportamento indefinido dos quais você deve estar ciente, ordenados (na minha opinião) do mais importante para o menos importante.
Achei essa advertência tão importante que a movi para o início desta seção.
As expressões de Jack
a > b
a < bsão enganosamente simples. Eles nem sempre são matematicamente corretos e são respectivamente equivalentes às expressões Java
( ( a - b ) & ( 1 << 15 ) ) == 0 && a != b
( ( a - b ) & ( 1 << 15 ) ) != 0 O que há com a nuance? A implementação da máquina virtual converte a > b em a - b > 0 . Aqui está o problema: a - b pode transbordar :(
Qual é a avaliação 20000 > -20000 ? A máquina virtual transpila isso para 20000 - (-20000) > 0 que é avaliado como -25336 > 0 . Infelizmente, a resposta é false .
No entanto, 20000 > -10000 é avaliado como 30000 > 0 ou true .
Como você deve ter imaginado, se a distância absoluta entre a e b for maior que 32.767, a > b e a < b estão errados. Caso contrário, você está bem.
Este não é um bug de implementação, mas sim uma inconsistência do Nand com o próprio Tetris. Mais sobre isso aqui. Por motivos de compatibilidade, esse comportamento não será corrigido.
-32768 é único. É o único número que possui a propriedade tal que -(-32768) = -32768, um singleton sem contraparte positiva * . Isso pode levar a erros de lógica e doentios.
/**
* 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 retorne um número positivo. Este não é o caso de -32768, então o Jack OS não funciona bem.
Sua principal preocupação deve ser lidar com erros lógicos com o operador negativo. Como programador, se você deseja garantir que o negativo de um número negativo seja positivo, é sua responsabilidade verificar o caso de -32768 e tomar as medidas adequadas.
* Isso é verdade porque a ALU da NAND processa internamente a expressão Jack -x como ~(x - 1) . Vamos definir x como -32768 e avaliá-lo passo a passo. Aqui estão as representações binárias correspondentes em complemento de dois de 16 bits da computação:
x = 1000 0000 0000 0000
x - 1 = 0111 1111 1111 1111
~(x - 1) = 1000 0000 0000 0000 = x
É a mesma coisa! O que aconteceu aqui? Como a NAND é uma máquina de 16 bits, -32768 é o único número tal que, se você subtrair um, obterá seus bits invertidos. Em outras palavras, -32768 satisfaz x - 1 = ~x , simplificando a expressão para ~(~x) ou apenas x .
Este é autoexplicativo, então aqui está uma breve demonstração.
/**
* 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 outro lado, chamar uma função com muitos argumentos é perfeitamente válido. Você pode usar a palavra-chave arguments para indexar argumentos extras de função. Observe que não há indicador para a contagem de argumentos.
Você pode utilizar Array para converter uma variável em qualquer outro tipo. Chamar métodos de instância que não existem em variáveis de tipo convertido é um comportamento indefinido; o compilador não é inteligente o suficiente para perceber quando você está fazendo isso.
/**
* 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 ( ) ) ;
}
} Veja o programa Overflow para um exemplo detalhado.
A modificação dos quadros de pilha ou dos registros internos que residem respectivamente nos endereços de memória 256 a 2047 e 1 a 15 pode levar a um comportamento indefinido. Isso normalmente não é possível sem o uso indevido Memory.poke ou indexação de matriz negativa. Consulte o programa SecretPassword para obter um exemplo detalhado.
A NAND oferece validação de programa para arquivos .jack , mas não para arquivos .vm . Isso significa que o compilador de máquina virtual da NAND oferece liberdade para chamar funções inexistentes, fazer referência a variáveis não atribuídas ou executar qualquer outra operação de memória logicamente inválida. Na maioria dos casos de comportamento indefinido, a máquina virtual escapará e a tela simplesmente não exibirá nada. Será sua responsabilidade depurar o programa sozinho.
Desde o seu surgimento na década de 1970, há uma boa razão pela qual a computação de 16 bits caiu em desgraça na era moderna. Em comparação com a computação de 32 ou 64 bits, a computação de 16 bits oferecia poder de processamento e capacidade de memória limitados que simplesmente não atendiam às demandas de software e aplicativos contemporâneos.
NAND não é exceção a esta realidade.
retirado dos slides da palestra Nand to Tetris.
Comparado ao seu MacBook de 16 GiB, o NAND possui escassos 4 KiB de RAM, uma proporção de 0,00002% ! Apesar disso, foi o suficiente para nos levar à lua, então quem pode dizer que a NAND também não pode.
O Jack OS reserva 14.336 endereços de memória
