Пишем свой язык программирования, часть 1: пишем языковую ВМ
Введение
Доброго времени суток всем хабрачитателям!
Итак, пожалуй стоит сказать, что целью моей работы, на основе которой будет написан ряд статеек было пройти весь путь создания полнофункционального ЯП самому с 0 и затем поделиться своими знаниями, наработками и опытом с интересующимися этим людьми.
Я буду описывать создание языка, который описал ранее тут.
Он заинтересовал многих и вызвал бурную дискуссию в комментариях. Следовательно — тема интересна многим.
Думаю, что сразу стоит выложить информацию о проекте:
Сайт (будет заполнен документацией чуть позже).
Репозиторий
Чтобы самому потрогать проект и увидеть все в действии, лучше скачать репозиторий и запускать все из папки bin. В релиз я не спешу выкладывать последние версии языка и среды выполнения, т.к. мне порой бывает просто лень это делать.
Кодить я умею на C/C++ и на Object Pascal. Проект я писал на FPC, т.к. на мой взгляд этот язык гораздо проще и лучше подходит для написание подобного. Вторым определяющим фактором стало то, что FPC поддерживает огромное количество целевых платформ и пересобрать проект под нужную платформу можно с минимумом переделок. Если вы по непонятным мне причинам не любите Object Pascal, то не спешите закрывать пост и бежать кидаться камнями в комментарии. Этот язык весьма красив и нагляден, а кода я буду приводить не так уж и много. Только то, что нужно.
Итак, начну пожалуй я своё повествование.
Ставим цели
Прежде всего, любому проекту нужны поставленные цели и ТЗ, которые придется в будущем реализовывать. Нужно заранее определиться, какого типа язык будет создаваться, чтобы написать первичную ВМ для него.
Ключевые моменты, которые определяли дальнейшую разработку моей ВМ следующие:
- Динамическая типизация и приведение типов. Её поддержку я решил организовать на этапе разработки вм.
- Поддержка многопоточности. Включил этот пункт в этот список заранее, чтобы должным образом спроектировать архитектуру ВМ и организовать поддержку многопоточности на уровне ядра ВМ, а не в дальнейшем с помощью костылей.
- Экспорт внешних методов. Без этого язык будет бесполезен. Разве что его встраивать в какой-нибудь проект.
- Компилируемость языка (в цельный абстрактный исполняемый файл). Частично компилируемый или интерпретируемый? От этого многое зависит.
- Общая архитектура ВМ. Стековая или регистровая будет наша ВМ? Я попробовал реализовать и то и то. Выбрал для поддержки стековую ВМ.
- Как вы видите работу с переменными, массивами, структурами? Лично я в тот момент хотел реализовать язык, в котором автоматически почти все завязывается на неявных указателях, ведь такой подход сильно экономил бы память и упрощал жизнь разработчику. Если мы допустим передаем в методы что-нибудь большое, то автоматом передастся лишь указатель на это большое.
Итак, мной были выбраны вышеописанные приоритеты и я приступил к реализации языковой виртуальной машины. Странно это конечно, обычно сначала пишутся какие-либо парсеры/трансляторы, а затем уже и ВМ. Чтож, я начал разрабатывать проект именно в этом порядке и буду описывать его дальше в том порядке, в каком я его разрабатывал.
Сразу скажу, что ВМ я назвал максимально красноречиво — SVM (Stack-based Virtual Machine).
Начнем, пожалуй, с реализации класса переменной
Изначально я просто использовал variant тип, потому что так проще и быстрее. Это был костыль, но он подпирал проект и позволил мне быстренько реализовать первую версию ВМ и языка. Позже я засел за код и написал реализацию своего «variant». По-сути нужно написать класс, который хранит указатель на значение в памяти, в моей реализации это null/cardinal/int64/double/string/array. Можно было бы использовать case типизацию, но я посчитал, что будет лучше реализовать так, как я реализовал.
Перед тем, как начать писать код класса, я решил сразу закинуть директиву {$H+} в заголовок модуля для более гибкой поддержки строк будущим языком.
П.с. для тех, кто может быть не в курсе, в чем разница между H- и H+ режимом FPC.
При сборке кода в режиме H- строки будут представлены в виде массива символов. При H+ — в виде указателя на кусок памяти. В первом случае строки будут изначально фиксированной длины и ограничены по дефолту 256 символами. Во втором случае — строки будут динамически расширяемыми и в них можно будет запихнуть гораздо больше символов. Будут работать немного медленнее, зато более функционально. При H+ можно также объявлять строки как массив символов, например таким вот образом:
var s:string[256];
Итак, для начала объявим Enum тип, который будем использовать как некий флажок, для определения типа данных по указателю:
type
TSVMType = (svmtNull, svmtWord, svmtInt, svmtReal, svmtStr, svmtArr);
Далее опишем основную структуру нашего типа переменной и некоторые методы:
TSVMMem = class
m_val: pointer;
m_type: TSVMType;
constructor Create;
destructor Destroy;
procedure Clear;
end;
...
constructor TSVMMem.Create;
begin
m_val := nil;
m_type := svmtNull;
end;
destructor TSVMMem.Destroy;
begin
Clear;
end;
procedure TSVMMem.Clear; inline;
begin
case m_type of
svmtNull: { nop };
svmtWord: Dispose(PCardinal(m_val));
svmtInt: Dispose(PInt64(m_val));
svmtReal: Dispose(PDouble(m_val));
svmtStr: Dispose(PString(m_val));
svmtArr: begin
SetLength(PMemArray(m_val)^, 0);
Dispose(PMemArray(m_val));
end;
else
Error(reVarInvalidOp);
end;
end;
Класс ни от чего не наследуется, поэтому inherited вызовы в конструкторе и деструкторе можно не делать. Уделю внимание директиве inline. В заголовок файла лучше добавить {$inline on}, чтоб наверняка. Её активное использование в ВМ довольно ощутимо повысило производительность (мб где-то аж на 15–20%!). Она говорит компилятору, что тело метода лучше встроить на место его вызова. Выходной код будет немного больше в итоге, но работать будет быстрее. В данном случае, использование inline целесообразно.
Ок, запилили мы на этом этапе основу нашего класса. Теперь нужно описать ряд сеттеров и геттеров (setter & getter) у нашего класса.
Задача в чем — написать пару методов, которые позволят запихнуть и в дальнейшем получить обратно значения из нашего класса.
Для начала разберемся с присвоением значения для нашего класса. Первым можно написать обобщенный сеттер, ну, а дальше, для отдельных типов данных:
procedure TSVMMem.SetV(const value; t:TSVMType); inline;
begin
if (m_val <> nil) and (m_type = t) then
begin
case t of
svmtWord: PCardinal(m_val)^ := Cardinal(value);
svmtInt: PInt64(m_val)^ := Int64(value);
svmtReal: PDouble(m_val)^ := Double(value);
svmtStr: PString(m_val)^ := String(value);
end;
end
else
begin
if m_val <> nil then
FreeMem(m_val);
m_type := t;
case t of
svmtWord: begin
New(PCardinal(m_val));
PCardinal(m_val)^ := Cardinal(value);
end;
svmtInt: begin
New(PInt64(m_val));
PInt64(m_val)^ := Int64(value);
end;
svmtReal: begin
New(PDouble(m_val));
PDouble(m_val)^ := Double(value);
end;
svmtStr: begin
New(PString(m_val));
PString(m_val)^ := String(value);
end;
else
Error(reVarTypeCast);
end;
end;
end;
...
procedure TSVMMem.SetW(value:cardinal); inline;
begin
if (m_val <> nil) and (m_type = svmtWord) then
PCardinal(m_val)^ := value
else
begin
if m_val <> nil then
FreeMem(m_val);
m_type := svmtWord;
New(PCardinal(m_val));
PCardinal(m_val)^ := value;
end;
end;
Теперь можно и для пары геттеров написать код:
function TSVMMem.GetW:cardinal; inline;
begin
Result := 0;
case m_type of
svmtWord: Result := PCardinal(m_val)^;
svmtInt: Result := PInt64(m_val)^;
svmtReal: Result := Trunc(PDouble(m_val)^);
svmtStr: Result := StrToQWord(PString(m_val)^);
else
Error(reVarTypeCast);
end;
end;
Ок, замечательно, теперь, после того, как вы просидели некоторое время пялясь в IDE и с энтузиазмом печатая код сеттеров и геттеров, мы стоим перед задачей реализации поддержки нашим типом математических и логических операций. В качестве примера я приведу реализацию операции сложения:
procedure TSVMMem.OpAdd(m:TSVMMem); inline;
begin
case m_type of
svmtWord: case m.m_type of
svmtWord: SetW(GetW + m.GetW);
svmtInt: SetI(GetW + m.GetI);
svmtReal: SetD(GetW + m.GetD);
svmtStr: SetD(GetW + StrToFloat(m.GetS));
else
Error(reVarInvalidOp);
end;
svmtInt: case m.m_type of
svmtWord: SetI(GetI + m.GetW);
svmtInt: SetI(GetI + m.GetI);
svmtReal: SetD(GetI + m.GetD);
svmtStr: SetD(GetI + StrToFloat(m.GetS));
else
Error(reVarInvalidOp);
end;
svmtReal: case m.m_type of
svmtWord: SetD(GetD + m.GetW);
svmtInt: SetD(GetD + m.GetI);
svmtReal: SetD(GetD + m.GetD);
svmtStr: SetD(GetD + StrToFloat(m.GetS));
else
Error(reVarInvalidOp);
end;
svmtStr: case m.m_type of
svmtWord: SetS(GetS + IntToStr(m.GetW));
svmtInt: SetS(GetS + IntToStr(m.GetI));
svmtReal: SetS(GetS + FloatToStr(m.GetD));
svmtStr: SetS(GetS + m.GetS);
else
Error(reVarInvalidOp);
end;
else
Error(reVarInvalidOp);
end;
end;
Все просто. Аналогичным образом можно описать и дальнейшие операции и вот наш класс готов.
Для массивов ещё конечно нужны пара методов, пример получения элемента по индексу:
function TSVMMem.ArrGet(index: cardinal; grabber:PGrabber): pointer; inline;
begin
Result := nil;
case m_type of
svmtArr: Result := PMemArray(m_val)^[index];
svmtStr: begin
Result := TSVMMem.CreateFW(Ord(PString(m_val)^[index]));
grabber^.AddTask(Result);
end;
else
Error(reInvalidOp);
end;
end;
Супер. Теперь мы можем двигаться дальше.
Реализуем стек
Спустя время я пришел к таким мыслям. Стек должен быть и статичным (для быстродействия) и динамичным (для гибкости) одновременно.
Поэтому стек реализован блочно. Т.е. как это должно работать — изначально массив стека имеет определенный размер (я решил поставить размер блока в 256 элементов, чтобы было красиво и не мало). Соответственно, в комплекте с массивом идет счетчик, указывающий на текущую вершину стека. Перевыделение памяти — это лишняя долгая операция, которую можно выполнять реже. Если в стек будет ложиться больше значений, то его размер можно будет всегда расширить на размер ещё одного блока.
Привожу реализацию стека целиком:
type
TStack = object
public
items: array of pointer;
size, i_pos: cardinal;
parent_vm: pointer;
procedure init(vm: pointer);
procedure push(p: pointer);
function peek: pointer;
procedure pop;
function popv: pointer;
procedure swp;
procedure drop;
end;
PStack = ^TStack;
procedure TStack.init(vm: pointer);
begin
SetLength(items, StackBlockSize);
i_pos := 0;
size := StackBlockSize;
parent_vm := vm;
end;
procedure TStack.push(p: pointer); inline;
begin
items[i_pos] := p;
inc(i_pos);
if i_pos >= size then
begin
size := size + StackBlockSize;
SetLength(items, size)
end;
end;
function TStack.peek: pointer; inline;
begin
Result := items[i_pos - 1];
end;
procedure TStack.pop; inline;
begin
dec(i_pos);
if size - i_pos > StackBlockSize then
begin
size := size - StackBlockSize;
SetLength(items, size);
end;
end;
function TStack.popv: pointer; inline;
begin
dec(i_pos);
Result := items[i_pos];
if size - i_pos > StackBlockSize then
begin
size := size - StackBlockSize;
SetLength(items, size);
end;
end;
procedure TStack.swp; inline;
var
p: pointer;
begin
p := items[i_pos - 2];
items[i_pos - 2] := items[i_pos - 1];
items[i_pos - 1] := p;
end;
procedure TStack.drop; inline;
begin
SetLength(items, StackBlockSize);
size := StackBlockSize;
i_pos := 0;
end;
Во внешние методы ВМ будет передавать указатель на стек, чтобы они могли взять оттуда нужные аргументы. Указатель на поток ВМ добавил позже, чтобы можно было реализовывать callback вызовы из внешних методов да и в общем, для передачи большей власти над ВМ методам.
Итак, как с тем, как устроен стек вы ознакомились. Таким же образом устроен callback стек, для простоты и удобства call & return операций и стек сборщика мусора. Единственное — другие размеры блоков.
Поговорим о мусоре
Его, как правило много, очень много. И с ним нужно что-то делать.
Первым делом хочу рассказать о том, как устроены сборщики мусора в других языках, например в Lua, Ruby, Java, Perl, PHP и т.д. Они работают по принципу подсчета указателей на объекты в памяти.
Т.е. вот выделили мы память под что-то, логично — указатель сразу поместили в переменную/массив/куда-то ещё. Сборщик мусора среды выполнения сразу же добавляет этот указатель себе с список возможных мусорных объектов. В фоне, сборщик мусора постоянно мониторит все переменные, массивы и т.д. Если там не оказывается указателя на что-то из списка возможного мусора — значит это мусор и память из под него нужно убрать.
Я решил реализовать свой велосипед. Мне более привычна работа с памятью по принципу Тараса Бульбы. Я тебя породил — я тебя и убью, подразумеваю я, когда вызываю очередной Free у очередного класса. Поэтому сборщик мусора у моей ВМ полуавтоматический. Т.е. его нужно вызывать в ручном режиме и работать с ним соответственно. В его очередь добавляются указатели на объявляемые временные объекты (эта роль ложится на по большей мере на транслятор и немного на разработчика). Для освобождения памяти из под других объектов можно использовать отдельный опкод.
Т.е. у сборщика мусора на момент вызова есть уже готовый список указателей, по которому нужно пробежаться и освободить память.
Итак, теперь разберемся с компиляцией в абстрактный исполняемый файл
Идея изначально заключалась в том, что приложения, написанные на моём языке смогут выполняться без исходников, как это происходит с многими похожими языками. Т.е. его можно будет использовать в коммерческих целях.
Для этого нужно определить формат исполняемых файлов. У меня получилось следующее:
- Заголовок, например «SVMEXE_CNS».
- Секция, содержащая список библиотек, из которых будут импортироваться методы.
- Секция импорта нужных методов, библиотеки из которых импортируются методы указываются по их номеру в секции выше.
- Секция констант.
- Секция кода.
Не думаю, что стоит выкладывать подробные шаги реализации парсеров для этих секций, ведь вы можете все сами посмотреть в моём репозитории.
Выполнение кода
После разбора вышеперечисленных секций и инициализации ВМ у нас остается одна секция с кодом. В моей ВМ выполняется не выровненный байткод, т.е. инструкции могут быть произвольной длины.
Набор опкодов — инструкций для виртуальной машины с небольшими комментариями я показываю заранее ниже:
type
TComand = (
{** for stack **}
bcPH, // [top] = [var]
bcPK, // [var] = [top]
bcPP, // pop
bcSDP, // stkdrop
bcSWP, // [top] <-> [top-1]
{** jump's **}
bcJP, // jump [top]
bcJZ, // [top] == 0 ? jp [top-1]
bcJN, // [top] <> 0 ? jp [top-1]
bcJC, // jp [top] & push callback point as ip+1
bcJR, // jp to last callback point & rem last callback point
{** for untyped's **}
bcEQ, // [top] == [top-1] ? [top] = 1 : [top] = 0
bcBG, // [top] > [top-1] ? [top] = 1 : [top] = 0
bcBE, // [top] >= [top-1] ? [top] = 1 : [top] = 0
bcNOT, // [top] = ![top]
bcAND, // [top] = [top] and [top-1]
bcOR, // [top] = [top] or [top-1]
bcXOR, // [top] = [top] xor [top-1]
bcSHR, // [top] = [top] shr [top-1]
bcSHL, // [top] = [top] shl [top-1]
bcNEG, // [top] = -[top]
bcINC, // [top]++
bcDEC, // [top]--
bcADD, // [top] = [top] + [top-1]
bcSUB, // [top] = [top] - [top-1]
bcMUL, // [top] = [top] * [top-1]
bcDIV, // [top] = [top] / [top-1]
bcMOD, // [top] = [top] % [top-1]
bcIDIV, // [top] = [top] \ [top-1]
bcMV, // [top]^ = [top-1]^
bcMVBP, // [top]^^ = [top-1]^
bcGVBP, // [top]^ = [top-1]^^
bcMVP, // [top]^ = [top-1]
{** memory operation's **}
bcMS, // memory map size = [top]
bcNW, // [top] = @new
bcMC, // copy [top]
bcMD, // double [top]
bcRM, // rem @[top]
bcNA, // [top] = @new array[ [top] ] of pointer
bcTF, // [top] = typeof( [top] )
bcSF, // [top] = sizeof( [top] )
{** array's **}
bcAL, // length( [top] as array )
bcSL, // setlength( [top] as array, {stack} )
bcPA, // push ([top] as array)[top-1]
bcSA, // peek [top-2] -> ([top] as array)[top-1]
{** memory grabber **}
bcGPM, // add pointer to TMem to grabber task-list
bcGC, // run grabber
{** constant's **}
bcPHC, // push copy of const
bcPHCP, // push pointer to original const
{** external call's **}
bcPHEXMP, // push pointer to external method
bcINV, // call external method
bcINVBP, // call external method by pointer [top]
{** for thread's **}
bcPHN, // push null
bcCTHR, // [top] = thread(method = [top], arg = [top+1]):id
bcSTHR, // suspendthread(id = [top])
bcRTHR, // resumethread(id = [top])
bcTTHR, // terminatethread(id = [top])
{** for try..catch..finally block's **}
bcTR, // try @block_catch = [top], @block_end = [top+1]
bcTRS, // success exit from try/catch block
bcTRR, // raise exception, message = [top]
{** for string's **}
bcSTRD, // strdel
bcCHORD,
bcORDCH,
{** [!] directly memory operations **}
bcALLC, //alloc memory
bcRALLC, //realloc memory
bcDISP, //dispose memory
bcGTB, //get byte
bcSTB, //set byte
bcCBP, //mem copy
bcRWBP, //read word
bcWWBP, //write word
bcRIBP, //read int
bcWIBP, //write int
bcRFBP, //read float
bcWFBP, //write float
bcRSBP, //read string
bcWSBP, //write string
bcTHREXT,//stop code execution
bcDBP //debug method call
);
Итак, вы бегло ознакомились с тем, какие операции может выполнять написанная мной ВМ. Теперь хочется сказать о том, как это все работает.
ВМ реализована как object, благодаря чему можно без проблем реализовать поддержку многопоточности.
Имеет указатель на массив с опкодами, IP (Instruction Pointer) — смещение выполняемой инструкции и указатели на прочие структуры ВМ.
Выполнение кода идет большим switch-case.
Просто приведу описание ВМ:
type
TSVM = object
public
ip, end_ip: TInstructionPointer;
mainclasspath: string;
mem: PMemory;
stack: TStack;
cbstack: TCallBackStack;
bytes: PByteArr;
grabber: TGrabber;
consts: PConstSection;
extern_methods: PImportSection;
try_blocks: TTRBlocks;
procedure Run;
procedure RunThread;
procedure LoadByteCodeFromFile(fn: string);
procedure LoadByteCodeFromArray(b: TByteArr);
end;
Немного об обработке исключений
Для этого в ВМ есть стек обработчиков исключений и большой try/catch блок, в который завернуто выполнение кода. С стек можно положить структуру, которая имеет смещение точек входа на catch и finally/end блока обработки исключений. Также я предусмотрел опкод trs, который ставится перед catch и перебрасывает код на finally/end, если он выполнился успешно, попутно удаляя блок с информацией об обработчиках исключений с вершины соответствующего стека. Просто? Просто. Удобно? Удобно.
Поговорим о внешних методах и библиотеках
Я уже упоминал о них ранее. Импорты, библиотеки… Без них язык не будет обладать желаемой гибкостью и функционалом.
Первым делом в реализации ВМ объявим тип внешнего метода и протокол его вызова.
type
TExternalFunction = procedure(PStack: pointer); cdecl;
PExternalFunction = ^TExternalFunction;
Парсер секции импорта заполняет при ицициализации ВМ массив указателей на внешние методы. Следовательно каждый метод имеет статичный адрес, который вычисляется на этапе сборке приложения под ВМ и по которому может быть вызван нужный метод.
Вызов в дальнейшем происходит таким вот образом в процессе выполнения кода:
TExternalFunction(self.extern_methods^.GetFunc(TSVMMem(self.stack.popv).GetW))(@self.stack);
Напишем простую библиотеку для нашей ВМ
И пусть она будет реализовывать для начала метод Sleep:
library bf;
{$mode objfpc}{$H+}
uses SysUtils, svm_api in '..\svm_api.pas';
procedure DSleep(Stack:PStack); cdecl;
begin
sleep(TSVMMem(Stack^.popv).GetW);
end;
exports DSleep name 'SLEEP';
end.
Итоги
На этом я пожалуй закончу свою первую статью из задуманного цикла.
Сегодня я довольно подробно описал создание среды выполнения языка. Считаю, что данная статья будет очень полезна людям, которые решат попробовать написать свой ЯП или же разобраться с тем, как работают подобные языки программирования.
Полный код ВМ доступен в репозитории, в ветке /runtime/svm.
Если вам понравилась эта статья, то не ленитесь закинуть плюс в карму и поднять её в топе, я старался и буду стараться для вас.
Если вам что-то непонятно — то добро пожаловать в комментарии или на форум.
Возможно ваши вопросы и ответы на них будут интересны не только вам.
