В связи с карантином я открыл для себя платформу Coursera и в короткий срок прошел там уже несколько довольно объемистых курса. Один из них From Nand To Tetris (далее буду для краткости называть его N2T) осуществил одну из моих мечт — спроектировать компьютер с нуля (или хотя бы почувствовать как это) — об этом я задумывался, когда читал книжку Эндрю Таненбаума «Архитектура компьютера». Кстати, по моему, идеологически курс N2T близок книжке Таненбаума, но курс, в отличие от книжки — проектно-центрированный, т. е. упор в нем делается на то, чтобы вы делали компьютер своими руками. Авторы курса — профессора университета Hebrew University of Jerusalem — Noam Nisan и Shimon Shoken. Компьютер, который они таким образом создали (первая часть курса), они назвали Hack Computer. Вторая часть курса посвящена в основном созданию компилятора для Java-подобного языка программирования высокого уровня для этого компьютера, который авторы назвали Jack Language (а еще там есть язык ассемблера и виртуальная машина). Ну а теперь, выписываю ключевые слова, чтобы через много лет восстановить сей курс в памяти.
1. Булева алгебра
Законы де Моргана (De Morgan’s laws). Таблицы истинности (truth tables).
Вентили:
И (AND), ИЛИ (OR), НЕ (NOT), исключающее ИЛИ (XOR), мультиплексор (MUX), демультиплексор (DMUX).
Многовходовые вентили (multiple-way gate).
Hardware Definition Language (HDL). Пример описания чипа на HDL:
IN a[4], b[4], c, ...
OUT out1, ou2, ...
PARTS:
Chip1(in=a[0], out=x);
Chip2(in1=b[1], in2=c, out=y);
Chip3(in1=x, in2=y, out=out1);
Chip3(in1=a[1], in2=x, out=out2);
...
}
2. Арифметика
Полусумматор (half adder), полный сумматор (full adder).
Формат хранения отрицательных целых чисел. Дополнительный код (two’s complement).
Арифметико-логическое устройство (Arithmetic Logic Unit). Zeroing and negation.
3. Память
Схемы с памятью. Sequential chips, sequential logic.
Зачем в компьютере сигнал синхронизации (clock). Чтобы состояние автомата изменялось только после того, как все сигналы устаканились.
Время распространения сигнала — propagation delay.
Период синхросигнала — clock unit.
Двухступенчатый D-триггер (триггер синхронизируемый фронтом) — edge-triggered flip-flop. Запоминание на фронте, изменение выхода — на спаде.
Регистр (register). Регистр-счетчик (counter).
Микросхемы памяти. Как строить их иерархически:
RAM64 = 8x RAM8 + 8-way MUX
RAM512 = 8x RAM64 + 8-way MUX
RAM4K = 8x RAM512 + 8-way MUX
RAM16K = 4x RAM512 + 4-way MUX
4. Машинный язык
Мнемоническое обозначение машинной команды (Mnemonics).
Базовые операции: арифметические, логические, управление потоком выполнения (flow control).
Модель компьютера Hack: АЛУ, регистр данных D, регистр адреса A, память программ (ROM), память данных (RAM).
A-commands and C-commands.
A-command example:
@25
C-command examples:
M=D+1
0;JMP
Метки в ассемблерном коде:
(SOMELABEL)
D=D+M;JGT
M=D+1
@SOMELABEL
0;JMP
// data-label (predefined label to register R0)
@R0
D=M
// data-label (label to a variable)
@arr
M=D
Формат машинной команды:
comp bits: specifies the operation (to the right of the '=' sign)
dest bits: specifies the destination register(s)
jump bits: specifies a branching command
Общение с устройствами ввода-вывода. Memory-mapped input and output.
Буфер дисплея и регистр контроллера клавиатуры проецируются на адресное пространство процессора.
5. Архитектура компьютера
Фон-Неймановская архитектура (Von Neumann architecture).
Fetch-execute cycle. Program counter (PC).
Hack computer has harward architecture.
- Instruction memory
- ALU
- A-register, D-register, PC
- Data memory
{
IN inM[16],
instruction[16],
reset;
OUT outM[16],
writeM,
addressM[15],
pc[15];
PARTS:
...
...
...
}
6. Ассемблер (компилятор языка ассемблера)
При разработке ассемблера нужно взаимодействовать с файловой системой (откуда мы берем исходный код на языке ассемблера). Если вы пишете на C++, то используйте типы из пространства имен filesystem:
#include <experimental/filesystem>
namespace fs = std::experimental::filesystem;
#else
#include <filesystem>
namespace fs = std::filesystem;
#endif
// fs::is_directory
// fs::directory_iterator
// fs::path
Алгоритм ассемблера
- Удаление пустых строк и комментариев
- Построение таблицы символов. Два вида символов: метки в коде и метки в данных. Среди меток данных есть предопределенные символы (R0…R15, SCREEN, KBD, SP, LCL, ARG, THIS, THAT)
- Resolving symbols — превращение символов в конкретные числа.
- Трансляция исходного кода команда за командой (мнемонику команды превращаем в двоичные числа)
7. Виртуальная машина
Двухступенчатый компилятор (Two-tier compiler):
Stack machine — машина со стековой адресацией памяти (т. е. аргументы команды как и результат ее выполнения запихиваются в стек):
push x
push y
add
pop z
Память виртуальной машины компьютера Hack делится на сегменты:
- local — для локальных переменных (является частью стека функции); адрес сегмента хранится в регистре LCL (RAM[1])
- argument — для аргументов функции (является частью стека функции); адрес сегмента хранится в регистре ARG (RAM[2])
- static — для хранения глобальных переменных; занимает область памяти RAM[16…255]
- constant — псевдосегмент (константы напрямую зашиваются в машинные команды)
- this — сегмент, который содержит объект (экземпляр класса) для которого вызван некий метод; адрес сегмента хранится в регистре THIS (RAM[3])
- that — сегмент, который содержит массив (или, иначе, служит для обращения к элементам массива); адрес сегмента хранится в регистре THAT (RAM[4])
- pointer — сегмент, состоящий из двух 16-битных слов, содержит адреса сегментов this и that (т. е. регистры THIS и THAT)
- temp — сегмент для служебных целей, без которого не обойтись при вызове функции; занимает область памяти RAM[5…12]
Отдельно следует упомянуть о стеке, под который отведена область памяти RAM[256…2047]. Адрес вершины стека находится в регистре SP (RAM[0]).
Формат например команды push, таков:
offset — числовая константа (0, 1, 2, 3 и т. д.), представляющая собой смещение от начала стека.
Приведем примеры обращений (а именно — запихивания в стек) к разным сегментам:
push local 0 // локальная переменная номер ноль
push static 3 // глобальная переменная номер три
push constant 123 // числовая константа сто двадцать три
push this 4 // поле (field) номер четыре объекта для которого вызван метод
push that 5 // элемент номер пять массива, адрес которого равен адресу сегмента that
push pointer 0 // адрес сегмента this
push pointer 1 // адрес сегмента that
8. Виртуальная машина. Поддержка ветвлений, циклов и функций.
Команды виртуальной машины для поддержки ветвлений.
if-goto labelname // conditional jump (depends on the top value in the stack which is true or false)
label labelname // declares a label with name "labelname"
Команды виртуальной машины для поддержки функций.
function foo nLocals // declares a function named "foo" which has nLocals local variables
return // returns from a function
Непосредственно перед командой call в стек командой push запихиваются параметры функции. Команда call устанавливает указатель сегмента ARG на только что запихнутые в стек параметры функции — для этого команде call нужно «знать», сколько этих параметров. Команда call запихивает в стек адрес возврата. Далее команда call сохраняет в стеке значения всех указателей сегментов специфичные для конкретной функции (LCL, ARG, THIS, THAT) — с тем, чтобы в дальнейшем команда return могла все эти указатели восстановить. После этого команда call перепрыгивает на адрес фукции.
Команда function устанавливает указатель сегмента локальных переменных (LCL) на начало стекового фрейма и запихивает в него энное количество нулей — это будут начальные значения локальных переменных. Для этого команде function нужно знать, сколько внутри функции используется локальных переменных.
Непосредственно перед командой return функция должна запихнуть в стек возвращаемое значение при помощи команды push. Даже если функция ничего не должна возвращать (объявлена как void), то она все равно должна вернуть неважно-что — например, ноль. Команда return копирует возвращаемое значение на место 0-ого аргумента функции (на него указывает указатель сегмента ARG). Далее команда return устанавливает указатель вершины стека на следующее слово после того места, куда она скопировала возвращаемое значение (т. е. происходит очистка стека). Далее восстанавливаются прежние значения указателей сегментов (ARG, THIS, THAT) — значения сохранены в стеке непосредственно над тем местом, на которое указывает LCL. Но чтобы восстановить сам LCL нужно задействовать временную переменную temp. Далее команда return извлекает из стека адрес возврата и перепрыгивает на него.
9. Язык Jack
Язык Jack — это язык высокого уровня, для которого в ходе курса студенты пишут компилятор. Язык поддерживает ООП, за исключением наследования. Все поля класса автоматически являются приватными, а все остальные члены класса — публичные. Кроме полей в классе могут быть:
— методы — функции, которые принимают неявный параметр this — указатель на объект;
— функции — функции, которые не принимают неявный параметр this (аналог статических функций в C#).
Язык создавался с такой целью, чтобы для него максимально легко было написать компилятор. Отсюда у него имеются такие особенности как:
— Обязательное наличие оператора return в конце каждой функции или метода.
— Слабая типизация: любой переменной можно присвоить значение любого типа.
— Каждая сущность обозначается своим ключевым словом: var — локальная переменная, constructor — конструктор, field — поле, method — метод и т. д. Для такого свойства грамматики языка есть специальный термин LL(k). Язык Jack обладает грамматикой типа LL(1), что означает, что для определения правила грамматики, которое следует применить, достаточно проанализировать всего один токен.
Пример класса точки на плоскости на языке Jack:
{
field int x;
field int y;
constructor Point new(int ax, int ay)
{
let x = ax;
let y = ay;
return this;
}
method void dispose()
{
do Memory.dealloc(this);
return;
}
method int getX() { return x; }
method int getY() { return y; }
method int setX(int value) { let x = value; }
method int setY(int value) { let y = value; }
method void Print()
{
do Output.printString("(");
do Output.printInt(x);
do Output.printString(",");
do Output.printInt(y);
do Output.printString(")");
return;
}
void Draw() { do Screen.drawPixel(x, y); }
function Point Add(Point a, Point b)
{
var Point p;
let p = Point.new(
a.getX() + b.getX(),
a.getY() + b.getY());
return p;
}
}
Язык опирается на стандартную библиотеку, которую авторы курса также называют операционной системой:
— Строковые литералы транслируются в объекты класса String.
— Синтаксис для работы с массивами предполагает обращение к классу Array.
— Операция умножения (оператор *) транслируется в вызов функции Math.multiply, операция деления — в Math.divide. Обе операции реализованы программно, а не аппаратно, как и вычисление квадратного корня (Math.sqrt).
10. Компилятор языка Jack. Токенизация и синтаксический анализ.
При написании компилятора вам может очень помочь Книга Дракона.
Первый этап компиляции называется Tokenization или Lexycal Analysis. Это разбивание всего текста на минимальные неделимые кирпичики — токены. В коде на C++, который я написал, токены выглядели так (привожу только фрагмент кода):
{
KEYWORD,
SYMBOL,
INTEGER_CONST,
STRING_CONST,
IDENTIFIER
};
class Token
{
private:
TokenTypeEnum tokenType;
...
};
{
CLASS,
METHOD,
FUNCTION,
CONSTRUCTOR,
INT,
BOOLEAN,
CHAR,
VOID,
VAR,
STATIC,
FIELD,
LET,
DO,
IF,
ELSE,
WHILE,
RETURN,
TRUE,
FALSE,
KWD_NULL,
THIS
};
// keyword
class KeywordToken : public Token
{
private:
KeywordTypeEnum keywordType;
...
};
// { } ( ) [ ] . , ; + - * / & | < > = ~
class SymbolToken : public Token { ... }
// integer literal
// 0...32767
class IntegerConstToken : public Token { ... }
// string literal
// ".*"
class StringConstToken : public Token { ... }
Лексический анализ программируется легко — путем посимвольного анализа текста.
Второй этап компиляции называется Parsing (синтаксический анализ или разбор). Берется поток токенов, получившийся на этапе лексического анализа, и из него строится синтаксическое дерево (parse tree). Строится оно на основе грамматических правил языка (грамматика).
Задача сводится к построению грамматики (т. е. правил). Правила грамматики можно записывать при помощи регулярных выражений (или некоего их подобия) или прямо сразу в коде (в моем случае — на C++). Возьмем например самое верхнее правило, описывающее класс:
// ^ ^ ^ ^ ^ ^
// keyword identi- open class members zero or closing
// fier brace (nonterminals) more times brace
TreeElement Class()
{
TreeElement aclass = new TreeElement("class");
aclass->AddChild(Keyword(KeywordTypeEnum::CLASS));
auto class_name = aclass.AddChild(Identifier());
aclass->AddChild(Symbol('{'));
while (true)
{
if (auto close_brace = Symbol('}'))
{
aclass.AddChild(close_brace);
break;
}
if(auto class_var_dec = ClassVarDec())
aclass.AddChild(class_var_dec);
else if(auto subroutine_dec = SubroutineDec())
aclass.AddChild(subroutine_dec);
else
throw std::runtime_error("Class");
}
return aclass;
}
// class_variable --> (field | static) var_type var_name (, var_name)? ;
// ^ ^ ^ ^ ^ ^ ^
// keyword nonterm identifier symbol identi- zero or symbol
// fier more times
TreeElement ClassVarDec() { ... }
// subroutine --> (constructor | function | method) return_type sub_name ( parameter_list ) subroutine_body
// ^ ^ ^ ^ ^ ^ ^
// keyword nonterm identi- symbol nonterm symbol nonterm
// fier
TreeElement SubroutineDec() { ... }
Правила бывают терминальные и нетерминальные. Терминальные — это те, правая часть которых является константой (например правила identifier или keyword). Нетерминальные правила — это те, правая часть которых включают в себя другие правила. Их я в коде выше обозначил словом nonterm.
Построив синтаксическое дерево, можно далее пройти по нему и сгенерировать машинный код (в нашем случае — байт-код для виртуальной машины). А можно сгенерировать машинный код и сразу в процессе построения синтаксического дерева.
10. Компилятор языка Jack. Генерация байт-кода.
Генерация кода суть трансляция всех методов и функций в исходном коде на языке высокого уровня (Jack в нашем случае) в команды виртуальной машины (байт-код). У каждой функции или метода могут быть параметры (аргументы) и локальные переменные, а у методов есть еще и указатель THIS на экземпляр класса, к которому он принадлежит (можно сказать, что THIS — это тоже параметр метода, только неявный). Плюс есть еще экземплярные и статические поля класса.
Все упомянутые переменные обладают разным временем жизни и областью видимости, поэтому для удобства их можно помещать в разные таблицы символов. Я помещал все поля класса в отдельную таблицу, которая существовала в течение всей компиляции класса. А локальные переменные и параметры функций и методов я помещал в другую таблицу, которая заполняется в начале трансляции функции, и очищается по окончании этой трансляции.
Каждому из упомянутых типов переменных соответствует свой тип сегмента памяти виртуальной машины:
— аргументы методов и функций — сегмент argument
— локальные переменные методов и функций — сегмент local
— экземплярные поля класса — сегмент this
— статические поля класса — сегмент static
Трансляция выражений осуществляется в виртуальной машине со стековой адресацией очень легко. Пример:
// a = b * (c + d)
push b
push c
push d
add // c + d
mul // b * (c + d)
pop a // a = b * (c + d)
Как вызываются функции и методы. С функциями всё просто — вызывающий код запихивает в стек явные параметры функции и выполняет команду call. При вызове метода в стек запихивается помимо явных параметров еще и адрес объекта, для которого вызывается метод (this). Вызываемый метод должен этот адрес достать из стека и поместить к указатель сегмента THIS (напомню, что этот указатель доступен через сегмент pointer по индексу 0).
Обращение к элементу массива с заданным индексом осуществляется через указатель THAT (который доступен через сегмент pointer по индексу 1). К этому указателю просто прибавляется индекс элемента массива.
11. Операционная система
Операционная система в проекте N2T представляет собой библиотеку классов, которые предоставляют прикладным программам жизненно необходимые сервисы, такие как:
— обращение к произвольным адресам памяти (класс Memory)
— вывод данных на экран (класс Screen)
— считывание ввода с клавиатуры (класс Keyboard)
— математические функции (класс Math)
Из интересностей можно отметить класс Memory, в котором для обращения к произвольному слову в памяти используется массив размером во всю память. А также класс Math, который умеет умножать числа методом сдвига и вычислять квадратный корень числа (методом поиска решения уравнения x**2 = y).