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

habr.png

Введение


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

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

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

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


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

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

  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.

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

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

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

© Habrahabr.ru