Нет
А
N и питание
Устройство
— это 16-битный компьютер, эквивалентный Тьюрингу, полностью состоящий из часов и вентилей NAND, эмулированных в Интернете. NAND имеет собственный процессор, язык машинного кода, язык ассемблера, ассемблер, язык виртуальных машин, переводчик виртуальных машин, язык программирования, компилятор, IDE и пользовательский интерфейс. NAND основан на платформе Jack-VM-Hack, указанной в курсе Nand to Tetris и связанной с ним книге.
Простая программа, которая вводит некоторые числа и вычисляет их среднее значение, демонстрируя поток управления, арифметические операции, ввод-вывод и динамическое распределение памяти.
Выход программы:
How many numbers? 4
Enter a number: 100
Enter a number: 42
Enter a number: 400
Enter a number: 300
The average is 210Эта программа входила в пакет программного обеспечения Nand to Tetris.
Игра в понг, демонстрирующая объектно-ориентированную модель языка. Используйте клавиши со стрелками, чтобы перемещать весло влево и вправо, чтобы отбить мяч. С каждым отскоком ракетка становится меньше, и игра заканчивается, когда мяч достигает нижней части экрана.
Эта программа входила в пакет программного обеспечения Nand to Tetris.
Игра 2048 года, демонстрирующая рекурсию и сложную логику приложения. Используйте клавиши со стрелками для перемещения чисел по сетке 4х4. Одни и те же числа складываются в сумму, если их сложить друг в друга. Как только будет достигнута плитка 2048, вы выиграете игру, но можете продолжать играть, пока не проиграете. Вы проигрываете игру, когда доска заполнена и вы больше не можете делать ходы.
Программа, которая намеренно вызывает переполнение стека посредством бесконечной рекурсии для выполнения выхода из виртуальной машины. Он использует тот факт, что нет никаких проверок во время выполнения, чтобы предотвратить переполнение стека. Ни одна другая современная платформа вам этого не позволит :-)
После запуска программа будет постоянно выводить на экран указатель стека. Как только отображаемое значение превысит 2048, стек достигнет конца предполагаемого пространства памяти и перейдет в пространство кучи, что приведет к взрывному сбою оператора печати:
Стоит отметить две вещи, представляющие примечательный интерес.
Если вы запустите эту программу в пустой ОЗУ, полной нулей (вы можете очистить ОЗУ через пользовательский интерфейс), вы заметите, что программа сбрасывается на полпути выполнения, несмотря на то, что кнопка «Сброс» не была нажата. Почему это происходит, просто: взломанная среда выполнения выполняет инструкцию, которая устанавливает значение счетчика программы на 0, фактически приказывая программе перейти к первой инструкции и начать все сначала.
Если вы запустите пример программы GeneticAlgorithm, а затем запустите ее сразу же после этого, программа в ярости прочитает старую оперативную память, которая просто никогда не была перезаписана.
Программа, которая использует тот факт, что среда выполнения не предотвращает разрушение стека, для вызова функции, которая в противном случае была бы недоступна. Чтобы понять, как это работает, давайте рассмотрим эту иллюстрацию структуры кадра стека NAND.
взято из книги Nand to Tetris.
Если вы не знакомы со структурой стека, вот основная идея эксплойта. Всякий раз, когда функция возвращается, ей необходимо знать, куда (по какому адресу памяти инструкций машинного кода) ей следует перейти, чтобы продолжить поток выполнения. Таким образом, при первом вызове функции этот адрес памяти вместе с некоторыми другими неважными данными временно сохраняется в стеке в области памяти, называемой кадром стека, в качестве ссылки на то, куда следует вернуться. На рисунке показано точное положение этого адреса возврата относительно вызова функции, положение, которое можно реконструировать.
Программа позволяет пользователю перезаписать один адрес памяти в ОЗУ на любое значение. Сложив два и два, если пользователь перезапишет адрес возврата кадра стека адресом другой функции, он, по сути, получит возможность выполнять произвольный код, включенный в программу.
Действительно, если вы введете 267 в качестве ячейки памяти и 1715 в качестве значения для перезаписи (два числа, полученные методом обратного проектирования путем ручной проверки пространства памяти стека и ассемблера), вы увидите эту идею в действии.
Это не уникальная уязвимость NAND. Он существует и в C! Как здорово!
Хотите верьте, хотите нет, но из множества различных компонентов NAND именно этот занял больше всего времени!
Эта программа представляет собой симуляцию существ, использующую простое машинное обучение. Он следует за серией кодов искусственного интеллекта (части первая и вторая) из Code Bullet. Обязательно загляните на его канал, он делает действительно классные вещи!
Просто объяснил:
У каждой точки есть собственный «мозг» векторов ускорения, и они развиваются, чтобы достичь цели посредством естественного отбора. В каждом поколении точки, которые «умирают» ближе к цели, с большей вероятностью будут выбраны в качестве родителей для следующего поколения. Репродукция по своей сути приводит к мутациям некоторых участков мозга, что полностью имитирует естественную эволюцию.
Тем не менее, есть желать лучшего. Из-за производительности единственным фактором, который точки используют для эволюции, является их близость к цели после смерти, что наделяет алгоритм естественного отбора низкой энтропией. Из-за использования памяти ограничения на количество точек и размеры их мозга меньше, чем удовлетворительные. Наконец, из-за технической сложности перестановка препятствий во время моделирования не гарантирует, что точки будут иметь достаточно большой мозг, чтобы достичь цели. Размеры мозга определяются только в начале программы.
Я использовал множество методов оптимизации, чтобы обойти следующие аппаратные ограничения и сделать это возможным:
Чтобы не ходить вокруг да около, я решил документировать эти методы и дополнительную информацию в кодовой базе этой программы для тех, кто заинтересован.
Прежде чем мы начнем, самая важная деталь, которую следует запомнить при написании программ на Jack, — это отсутствие приоритета оператора; возможно, поэтому ваша программа не работает.
Например, вам следует изменить:
4 * 2 + 3 до (4 * 2) + 3
if (~x & y) до if ((~x) & y)
но вы можете оставить if (y & ~x) таким же, чтобы не было двусмысленности оператора.
Без скобок оценочное значение неоднозначного выражения не определено .
NAND может похвастаться собственным полным набором технологий. Как следствие, NAND можно программировать только на Jack, его слабо типизированном объектно-ориентированном языке программирования. С точки зрения непрофессионала, Джек — это C с синтаксисом Java.
Давайте воспользуемся подходом обучения на основе примеров и сразу углубимся в суть.
/**
* 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 ;
}
}
}взято со слайдов лекции Nand to Tetris.
Если у вас уже есть некоторый опыт программирования, это должно показаться вам очень знакомым; ясно, что Джека сильно вдохновила Java. Main.main , точка входа в программу, демонстрирует базовое использование переменных, а также цикл while для потока управления.
Кроме того, он использует Keyboard.readLine и Keyboard.readInt для чтения ввода пользователя, а также Output.printString и Output.println для вывода вывода на экран — все из которых подробно определены в справочнике Jack OS. По умолчанию Jack OS поставляется вместе с вашей программой во время компиляции, чтобы обеспечить взаимодействие со строками, памятью, оборудованием и т. д.
Каждый язык программирования имеет фиксированный набор примитивных типов данных. Джек поддерживает три: int , char и boolean . При необходимости вы можете расширить этот базовый репертуар своими собственными абстрактными типами данных. Предварительные знания об объектно-ориентированном программировании переносятся непосредственно в этот раздел.
/** 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 3взято со слайдов лекции Nand to Tetris.
Мы определяем класс Point для представления абстрактной точки в пространстве. Он использует переменные field для объявления атрибутов типа данных для каждого экземпляра. Он предоставляет функции общедоступного method которые мы можем использовать для взаимодействия с точкой, предоставляя вызывающему объекту возможность складывать две точки и вычислять расстояние между двумя точками.
Все переменные field имеют частную область действия. Если вы хотите получить или установить эти переменные вне объявления класса, эти переменные должны иметь соответствующие функции- method для обеспечения этой функциональности.
Опущенные в примере кода, чтобы оставаться в рамках темы, классы данных обычно определяют методы dispose для освобождения, когда объекты больше не нужны. См. Управление памятью вручную.
Если необходимо, вот ссылка на синтаксис вызова function и 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
}
}взято со слайдов лекции Nand to Tetris.
Помните, мы говорили, что Джек похож на Java? Это был фасад или, в лучшем случае, вводящий в заблуждение. Хотя Java является строго типизированным и поэтому поддерживает сложные функции типов, такие как приведение типов вниз, полиморфизм и наследование, Джек не поддерживает ни одного из них и имеет только один тип: 16-битное целое число со знаком. Это основная причина, почему у Джека такая слабая типизация. По сути, компилятору все равно, если вы смешиваете и сопоставляете разные типы в присваиваниях и операциях.
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 typeвсе сегменты кода взяты из слайдов лекций Nand to Tetris.
Не поймите неправильно: Джек по-прежнему предоставляет мощную и функциональную объектно-ориентированную модель. Эта информация призвана помочь вам понять, когда и как следует выполнять преобразования типов по мере необходимости.
Допустим, вы такой же сумасшедший любитель кошек, как и я! И вы хотели написать эту программу, чтобы показать, насколько вы обожаете кошек.
class Main {
function void main ( ) {
while ( true ) {
do Output . printString ( "Kittens are so adorable! " ) ;
}
}
}Вы можете быть поражены, заметив, что через несколько секунд программа выйдет из строя с сообщением «ERR6» или переполнением кучи!
Jack — это язык программирования с ручным управлением памятью. Это означает, что вы должны быть бдительны и правильно освобождать память, которая больше не нужна, иначе Jack OS подумает иначе и будет способствовать утечке памяти. Лучший практический совет — использовать метод dispose для каждого класса, который представляет объект, который правильно инкапсулирует это освобождение. Таким образом, когда объекты больше не нужны, вы можете вызвать их методы dispose , чтобы гарантировать, что в конечном итоге у вас не закончится куча памяти.
Если вы программировали на других языках с ручным управлением памятью, например C, это должно выглядеть очень знакомо. Одним из ключевых отличий является то, что ОС Jack OS хранит массивы и строки в куче, а не в стеке, что намекает на то, почему программа аварийно завершает работу с переполнением кучи.
Давайте исправим эту программу для наших собратьев-кошачьих фанатиков.
class Main {
function void main ( ) {
var String s ;
while ( true ) {
let s = "Kittens are so adorable! " ;
do Output . printString ( s ) ;
do s . dispose ( ) ;
}
}
}Альтернативно, вы можете выделить память для строки только один раз.
class Main {
function void main ( ) {
var String s ;
let s = "Kittens are so adorable! " ;
while ( true ) {
do Output . printString ( s ) ;
}
}
}Вы заметите, что эти альтернативные версии не только печатают строку намного быстрее, но на этот раз они фактически печатают вечно! Ура!
Давайте быстро заглянем в String.dispose , чтобы вы могли лучше понять, как писать собственные методы dispose .
method void dispose ( ) {
do stringArray . dispose ( ) ;
do Memory . deAlloc ( this ) ;
} Array.dispose вызывается stringArray
method void dispose ( ) {
do Memory . deAlloc ( this ) ;
} Правильные методы dispose должны сначала соответствующим образом вызвать dispose для своих переменных поля, а затем завершить работу с помощью do Memory.deAlloc(this); чтобы освободить сам экземпляр объекта.
Учитывая примитивность Джека и NAND, наличие в языке ружей неизбежно. Я собрал следующие примеры неопределенного поведения, о которых вам следует знать, в порядке от (на мой взгляд) самого важного к наименее важному.
Я нашел это предостережение настолько важным, что перенес его в начало этого раздела.
Выражения Джека
a > b
a < bобманчиво просты. Они не всегда математически корректны и соответственно эквивалентны выражениям Java.
( ( a - b ) & ( 1 << 15 ) ) == 0 && a != b
( ( a - b ) & ( 1 << 15 ) ) != 0 Что там с нюансом? Реализация виртуальной машины преобразует a > b в a - b > 0 . Вот в чем проблема: a - b может переполниться :(
Что означает 20000 > -20000 ? Виртуальная машина преобразует это в 20000 - (-20000) > 0 , что эквивалентно -25336 > 0 . К сожалению, ответ false .
Однако 20000 > -10000 оценивается как 30000 > 0 или true .
Как вы, возможно, догадались, если абсолютное расстояние между a и b больше 32767, a > b и a < b неверны. В остальном, с тобой все в порядке.
Это не ошибка реализации, а скорее несоответствие Nand самому Тетрису. Подробнее об этом здесь. По соображениям совместимости это поведение не будет исправлено.
-32768 единственный в своем роде. Это единственное число, которое обладает таким свойством, что -(-32768) = -32768, одноэлементное число без положительного аналога * . Это может привести к необоснованности и логическим ошибкам.
/**
* 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 внутренне ожидает, что Math.abs вернет положительное число. С -32768 дело обстоит иначе, поэтому Jack OS работает со сбоями.
Вашей главной заботой должна быть обработка логических ошибок с помощью отрицательного оператора. Как программист, если вы хотите гарантировать, что отрицательное число является положительным, вы обязаны проверить наличие -32768 и предпринять соответствующие действия.
* Это справедливо, поскольку ALU NAND внутренне обрабатывает выражение Джека -x как ~(x - 1) . Давайте присвоим x значение -32768 и оценим его шаг за шагом. Вот соответствующие 16-битные двоичные представления вычислений с дополнением до двух:
x = 1000 0000 0000 0000
x - 1 = 0111 1111 1111 1111
~(x - 1) = 1000 0000 0000 0000 = x
Это то же самое! Что здесь произошло? Поскольку NAND — 16-битная машина, -32768 — единственное число, из которого вычитая единицу, вы получаете перевернутые биты. Другими словами, -32768 удовлетворяет условию x - 1 = ~x , что упрощает выражение до ~(~x) или просто x .
Это говорит само за себя, поэтому вот краткая демонстрация.
/**
* 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." ) ;
}
} С другой стороны, вызов функции со слишком большим количеством аргументов вполне допустим. Вы можете использовать ключевое слово arguments для индексации дополнительных аргументов функции. Обратите внимание, что индикатора количества аргументов нет.
Вы можете использовать Array для приведения переменной к любому другому типу. Вызов методов экземпляра, которые не существуют для переменных, приведенных к типу, является неопределенным поведением; компилятор недостаточно умен, чтобы понять, когда вы это делаете.
/**
* 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 ( ) ) ;
}
} Подробный пример см. в программе Overflow.
Изменение кадров стека или внутренних регистров, которые соответственно находятся по адресам памяти 256 по 2047 и 1 по 15 , может привести к неопределенному поведению. Обычно это невозможно без неправильного использования Memory.poke или отрицательной индексации массива. Подробный пример см. в программе SecretPassword.
NAND предлагает проверку программы для файлов .jack , но не для файлов .vm . Это означает, что компилятор виртуальной машины NAND дает вам свободу вызывать несуществующие функции, ссылаться на неназначенные переменные или выполнять любые другие логически недопустимые операции с памятью. В большинстве случаев такого неопределенного поведения виртуальная машина выйдет из строя, и на экране просто ничего не будет отображаться. Вы несете ответственность за отладку программы самостоятельно.
С момента своего появления в 1970-х годах есть веская причина, по которой 16-битные вычисления в современную эпоху утратили популярность. По сравнению с 32-битными или 64-битными вычислениями, 16-битные вычисления предлагали ограниченную вычислительную мощность и объем памяти, которые просто не отвечали требованиям современного программного обеспечения и приложений.
NAND не является исключением из этой реальности.
взято со слайдов лекции Nand to Tetris.
По сравнению с вашим MacBook емкостью 16 ГБ, NAND имеет скудные 4 КБ оперативной памяти, что составляет 0,00002% ! Несмотря на это, этого было достаточно, чтобы доставить нас на Луну, так что кто сказал, что NAND тоже не сможет.
Jack OS резервирует 14 336 адресов памяти.
