Главная » Софт » Пишем свой язык программирования, часть 1: пишем языковую ВМ

Пишем свой язык программирования, часть 1: пишем языковую ВМ

Введение

Доброго времени суток всем хабрачитателям!

Итак, пожалуй стоит сказать, что целью моей работы, на основе которой будет написан ряд статеек было пройти весь путь создания полнофункционального ЯП самому с 0 и затем поделиться своими знаниями, наработками и опытом с интересующимися этим людьми.

Я буду описывать создание языка, который описал ранее тут.

Следовательно — тема интересна многим. Он заинтересовал многих и вызвал бурную дискуссию в комментариях.

Думаю, что сразу стоит выложить информацию о проекте:

Сайт (будет заполнен документацией чуть позже).
Репозиторий

В релиз я не спешу выкладывать последние версии языка и среды выполнения, т.к. Чтобы самому потрогать проект и увидеть все в действии, лучше скачать репозиторий и запускать все из папки bin. мне порой бывает просто лень это делать.

Проект я писал на FPC, т.к. Кодить я умею на C/C++ и на Object Pascal. Вторым определяющим фактором стало то, что FPC поддерживает огромное количество целевых платформ и пересобрать проект под нужную платформу можно с минимумом переделок. на мой взгляд этот язык гораздо проще и лучше подходит для написание подобного. Этот язык весьма красив и нагляден, а кода я буду приводить не так уж и много. Если вы по непонятным мне причинам не любите Object Pascal, то не спешите закрывать пост и бежать кидаться камнями в комментарии. Только то, что нужно.

Итак, начну пожалуй я своё повествование.

Ставим цели

Прежде всего, любому проекту нужны поставленные цели и ТЗ, которые придется в будущем реализовывать. Нужно заранее определиться, какого типа язык будет создаваться, чтобы написать первичную ВМ для него.

Ключевые моменты, которые определяли дальнейшую разработку моей ВМ следующие:

  • Динамическая типизация и приведение типов. Её поддержку я решил организовать на этапе разработки вм.
  • Поддержка многопоточности. Включил этот пункт в этот список заранее, чтобы должным образом спроектировать архитектуру ВМ и организовать поддержку многопоточности на уровне ядра ВМ, а не в дальнейшем с помощью костылей.
  • Экспорт внешних методов. Без этого язык будет бесполезен. Разве что его встраивать в какой-нибудь проект.
  • Компилируемость языка (в цельный абстрактный исполняемый файл). Частично компилируемый или интерпретируемый? От этого многое зависит.
  • Общая архитектура ВМ. Стековая или регистровая будет наша ВМ? Я попробовал реализовать и то и то. Выбрал для поддержки стековую ВМ.
  • Как вы видите работу с переменными, массивами, структурами? Лично я в тот момент хотел реализовать язык, в котором автоматически почти все завязывается на неявных указателях, ведь такой подход сильно экономил бы память и упрощал жизнь разработчику. Если мы допустим передаем в методы что-нибудь большое, то автоматом передастся лишь указатель на это большое.

Итак, мной были выбраны вышеописанные приоритеты и я приступил к реализации языковой виртуальной машины. Странно это конечно, обычно сначала пишутся какие-либо парсеры/трансляторы, а затем уже и ВМ. Чтож, я начал разрабатывать проект именно в этом порядке и буду описывать его дальше в том порядке, в каком я его разрабатывал.

Сразу скажу, что ВМ я назвал максимально красноречиво — SVM (Stack-based Virtual Machine).

Начнем, пожалуй, с реализации класса переменной

Изначально я просто использовал variant тип, потому что так проще и быстрее. Это был костыль, но он подпирал проект и позволил мне быстренько реализовать первую версию ВМ и языка. Позже я засел за код и написал реализацию своего «variant». По-сути нужно написать класс, который хранит указатель на значение в памяти, в моей реализации это null/cardinal/int64/double/string/array. Можно было бы использовать case типизацию, но я посчитал, что будет лучше реализовать так, как я реализовал.

Перед тем, как начать писать код класса, я решил сразу закинуть директиву в заголовок модуля для более гибкой поддержки строк будущим языком.

для тех, кто может быть не в курсе, в чем разница между 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 у очередного класса. его нужно вызывать в ручном режиме и работать с ним соответственно. Т.е. Для освобождения памяти из под других объектов можно использовать отдельный опкод. В его очередь добавляются указатели на объявляемые временные объекты (эта роль ложится на по большей мере на транслятор и немного на разработчика).

у сборщика мусора на момент вызова есть уже готовый список указателей, по которому нужно пробежаться и освободить память. Т.е.

Итак, теперь разберемся с компиляцией в абстрактный исполняемый файл

Идея изначально заключалась в том, что приложения, написанные на моём языке смогут выполняться без исходников, как это происходит с многими похожими языками. Т.е. его можно будет использовать в коммерческих целях.

У меня получилось следующее: Для этого нужно определить формат исполняемых файлов.

  1. Заголовок, например «SVMEXE_CNS».
  2. Секция, содержащая список библиотек, из которых будут импортироваться методы.
  3. Секция импорта нужных методов, библиотеки из которых импортируются методы указываются по их номеру в секции выше.
  4. Секция констант.
  5. Секция кода.

Не думаю, что стоит выкладывать подробные шаги реализации парсеров для этих секций, ведь вы можете все сами посмотреть в моём репозитории.

Выполнение кода

После разбора вышеперечисленных секций и инициализации ВМ у нас остается одна секция с кодом. В моей ВМ выполняется не выровненный байткод, т.е. инструкции могут быть произвольной длины.

Набор опкодов — инструкций для виртуальной машины с небольшими комментариями я показываю заранее ниже:

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.

Если вам понравилась эта статья, то не ленитесь закинуть плюс в карму и поднять её в топе, я старался и буду стараться для вас.

Если вам что-то непонятно — то добро пожаловать в комментарии или на форум.

Возможно ваши вопросы и ответы на них будут интересны не только вам.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Из песочницы] Haiku β1 — сделаем /b/ OS великой снова

Совсем недавно (почти 4 месяца назад) вышла новая Haiku (далее — просто BeOS, ибо проект гораздо удачнее ReactOS — настолько, что разница между Haiku и BeOS уже пренебрежимо мала). Да и недавно прочитанный киберпанк-роман Александра Чубарьяна давал понять, что BeOS ...

Минкомсвязи одобрило законопроект об изоляции рунета

Министерство цифрового развития, связи и массовых коммуникаций РФ поддержало законопроект №608767-7 об автономной работе рунета, внесённый в Госдуму 14 декабря 2018 года. Об этом сегодня сообщил замглавы Минкомсвязи Олег Иванов в ходе расширенного заседания комитета Госдумы по информационной политике, информационным технологиям ...