Geekly articles weekly

Escrevemos nossa linguagem de programação, parte 1: escrevemos uma linguagem VM

1. Introdução


Bom dia a todos habrachitateli!

Então, talvez valha a pena dizer que o objetivo do meu trabalho, com base no qual várias estátuas serão escritas, era criar um YP totalmente funcional a partir de 0 e depois compartilhar meu conhecimento, melhores práticas e experiência com aqueles que estão interessados.

Vou descrever a criação da linguagem que descrevi anteriormente aqui .

Ele interessou muitos e provocou uma discussão acalorada nos comentários. Portanto - o tópico é interessante para muitos.

Acho que vale a pena postar imediatamente informações sobre o projeto:

Site (será preenchido com a documentação um pouco mais tarde).
Repositório

Para tocar no projeto você mesmo e ver tudo em ação, é melhor baixar o repositório e executar tudo da pasta bin. No lançamento, não tenho pressa em carregar as versões mais recentes do idioma e do tempo de execução, porque às vezes é muito preguiçoso para eu fazer isso.

Eu posso codificar em C / C ++ e Object Pascal. Eu escrevi o projeto no FPC desde na minha opinião, essa linguagem é muito mais simples e mais adequada para escrever assim. O segundo fator determinante foi que o FPC suporta um grande número de plataformas de destino e é possível reconstruir um projeto para a plataforma desejada com um mínimo de alterações. Se, por algum motivo, eu não gostar do Object Pascal, não se apresse em fechar a publicação e correr para atirar pedras no comentário. Essa linguagem é muito bonita e intuitiva, mas não fornecerei tanto código. Apenas o que você precisa.

Então, talvez eu comece minha história.

Estabelecemos metas


Antes de tudo, qualquer projeto precisa de seus objetivos e do TK, que deverá ser implementado no futuro. É necessário decidir com antecedência que tipo de idioma será criado para gravar a VM principal para ele.

Os principais pontos que determinaram o desenvolvimento adicional da minha VM são os seguintes:

  • Digitação dinâmica e conversão de tipos. Decidi organizar o apoio dela no estágio de desenvolvimento da VM.
  • Suporte multithreading. Eu incluí este item nesta lista antecipadamente, a fim de projetar adequadamente a arquitetura da VM e organizar o suporte para multithreading no nível principal da VM e, posteriormente, com muletas.
  • Exportação de métodos externos. Sem isso, a linguagem será inútil. A menos que seja incorporado a qualquer projeto.
  • Compilação do idioma (em um único arquivo executável abstrato). Parcialmente compilado ou interpretado? Muito depende disso.
  • Arquitetura geral da VM. A pilha ou o registro será nossa VM? Eu tentei implementar isso e aquilo. Eu escolhi uma VM empilhada para suporte.
  • Como você vê o trabalho com variáveis, matrizes, estruturas? Pessoalmente, naquele momento, eu queria implementar uma linguagem na qual quase tudo estivesse vinculado a indicadores implícitos, porque essa abordagem economizaria bastante memória e simplificaria a vida do desenvolvedor. Se permitirmos que algo grande seja passado para os métodos, apenas um ponteiro para esse grande será automaticamente transferido.

Então, eu escolhi as prioridades acima e comecei a implementar a máquina virtual de idiomas. Isso é estranho, é claro, geralmente todos os analisadores / tradutores são escritos primeiro e depois as VMs. Bem, comecei a desenvolver o projeto nesta ordem e descreverei-o ainda mais na ordem em que o desenvolvi.

Devo dizer imediatamente que chamei de VM o mais eloquente possível - SVM (Máquina Virtual Baseada em Pilha).

Vamos começar com a implementação da classe variável


Inicialmente, simplesmente usei um tipo de variante, porque é mais simples e rápido. Era uma muleta, mas sustentou o projeto e me permitiu implementar rapidamente a primeira versão da VM e do idioma. Mais tarde, sentei-me no código e escrevi uma implementação da minha "variante". Em essência, você precisa escrever uma classe que armazene um ponteiro para um valor na memória, na minha implementação é null/cardinal/int64/double/string/array . Pode-se usar a digitação de casos, mas achei que seria melhor implementar a maneira como implementei.

Antes de começar a escrever o código da classe, decidi colocar imediatamente a diretiva {$ H +} no cabeçalho do módulo para oferecer suporte mais flexível a seqüências de caracteres no idioma futuro.
P.S. para aqueles que podem não estar cientes da diferença entre os modos H e H + FPC.

Ao montar o código no modo H, as strings serão apresentadas como uma matriz de caracteres. Quando H + - como um ponteiro para um pedaço de memória. No primeiro caso, as linhas serão inicialmente fixadas em comprimento e limitadas por padrão a 256 caracteres. No segundo caso, as linhas serão dinamicamente expansíveis e muito mais caracteres poderão ser inseridos nelas. Eles funcionarão um pouco mais devagar, mas com mais funcionalidade. Com o H +, você também pode declarar cadeias de caracteres como uma matriz de caracteres, por exemplo, desta maneira:

 var s:string[256];
Portanto, para iniciantes, declararemos Enum um tipo, que usaremos como um determinado sinalizador para determinar o tipo de dados por ponteiro:

 type TSVMType = (svmtNull, svmtWord, svmtInt, svmtReal, svmtStr, svmtArr);

A seguir, descrevemos a estrutura básica do nosso tipo de variável e alguns métodos:

  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;

A classe não herda de nada, portanto, chamadas herdadas no construtor e destruidor podem ser omitidas. Vou prestar atenção à diretiva em linha. É melhor adicionar {$ inline on} ao cabeçalho do arquivo, com certeza. Seu uso ativo em VMs aumentou significativamente a produtividade (Mb em algum lugar de 15 a 20%!). Ela diz ao compilador que o corpo do método é melhor incorporado no local de sua invocação. O código de saída será um pouco maior no final, mas funcionará mais rápido. Nesse caso, é recomendável usar o inline.

Ok, nesta fase, lavamos a base de nossa classe. Agora precisamos descrever um número de setters e getters (setter & getter) em nossa classe.

A tarefa é escrever alguns métodos que permitirão empinar e depois recuperar os valores de nossa classe.

Primeiro, vamos descobrir a atribuição de um valor para a nossa classe. Primeiro, você pode escrever um setter generalizado e, em seguida, para tipos de dados individuais:

 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;

Agora você pode escrever código para alguns getters:

 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;

Ok, ótimo, agora que você passou algum tempo olhando para o IDE e digitando com entusiasmo o código de setters e getters, somos confrontados com a tarefa de implementar o suporte para nosso tipo de operações matemáticas e lógicas. Como exemplo, darei a implementação da operação de adição:

 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;

Tudo é simples. Outras operações podem ser descritas de maneira semelhante e agora nossa classe está pronta.
Para matrizes, é claro, você ainda precisa de alguns métodos, um exemplo de obter um elemento pelo índice:

 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;

Ótimo. Agora podemos seguir em frente.

Percebemos uma pilha


Depois de um tempo, cheguei a esses pensamentos. A pilha deve ser estática (para velocidade) e dinâmica (para flexibilidade) ao mesmo tempo.

Portanto, a pilha é implementada em blocos. I.e. como deve funcionar - inicialmente a matriz da pilha tem um determinado tamanho (decidi definir o tamanho do bloco para 256 elementos, para que ficasse bonito e não pequeno). Consequentemente, um contador é incluído na matriz, indicando a parte superior atual da pilha. A realocação de memória é uma operação extra longa, que pode ser executada com menos frequência. Se mais valores forem empurrados para a pilha, seu tamanho sempre poderá ser expandido para o tamanho de outro bloco.

Trago toda a implementação da pilha:

 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;

Nos métodos externos, a VM passa um ponteiro para a pilha para que eles possam pegar os argumentos necessários a partir daí. Um ponteiro para o fluxo da VM foi adicionado posteriormente, para que as chamadas de retorno de chamada de métodos externos pudessem ser implementadas e, em geral, para transferir mais energia sobre os métodos da VM.

Então, como você se familiarizou com a organização da pilha. A pilha de retorno de chamada é organizada da mesma maneira, para simplicidade e conveniência das operações de chamada e retorno e a pilha do coletor de lixo. A única coisa são os outros tamanhos dos blocos.

Fale sobre lixo


Geralmente é muito, muito. E você precisa fazer algo com isso.

Antes de tudo, quero falar sobre como os coletores de lixo são organizados em outras linguagens, por exemplo, em Lua, Ruby, Java, Perl, PHP, etc. Eles trabalham com o princípio de contar ponteiros para objetos na memória.

I.e. então alocamos memória para alguma coisa, é lógico - o ponteiro foi imediatamente colocado em uma variável / array / em outro lugar. O coletor de lixo em tempo de execução imediatamente adiciona esse ponteiro a si mesmo com uma lista de possíveis objetos de lixo. Em segundo plano, o coletor de lixo monitora constantemente todas as variáveis, matrizes etc. Se não houver ponteiro para algo da lista de lixo possível, isso significa que o lixo e a memória dele devem ser removidos.

Eu decidi vender minha bicicleta. Estou mais acostumado a trabalhar com a memória no princípio de Taras Bulba. Eu te dei à luz - quero matar você, quando eu ligar para o próximo Livre na próxima aula. Portanto, o coletor de lixo da minha VM é semi-automático. I.e. ele precisa ser chamado no modo manual e trabalhar com ele de acordo. Por sua vez, são adicionados indicadores para objetos temporários declarados (esse papel cabe principalmente ao tradutor e um pouco ao desenvolvedor). Para liberar memória de outros objetos, você pode usar um código de operação separado.

I.e. o coletor de lixo no momento da chamada possui uma lista pronta de ponteiros que você precisa examinar e liberar memória.

Então, agora vamos lidar com a compilação em um arquivo executável abstrato


Originalmente, a idéia era que aplicativos escritos em meu idioma pudessem ser executados sem fonte, como é o caso de muitos idiomas semelhantes. I.e. pode ser usado para fins comerciais.

Para fazer isso, determine o formato dos arquivos executáveis. Eu tenho o seguinte:

  1. Cabeçalho, por exemplo "SVMEXE_CNS".
  2. Uma seção que contém uma lista de bibliotecas das quais os métodos serão importados.
  3. A seção de importação dos métodos necessários, as bibliotecas das quais os métodos são importados são indicadas por seu número na seção acima.
  4. Seção de constantes.
  5. Seção de Código

Acho que não vale a pena definir as etapas detalhadas para implementar analisadores para essas seções, porque você pode ver tudo por si mesmo no meu repositório.

Execução de código


Após analisar as seções acima e inicializar a VM, temos uma seção com o código. Na minha VM, um bytecode não alinhado é executado, ou seja, as instruções podem ter comprimento arbitrário.

Um conjunto de códigos de operação - instruções para uma máquina virtual com pequenos comentários, mostrados com antecedência abaixo:

 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 );

Portanto, você se familiariza fluentemente com as operações que a VM escrita por mim pode realizar. Agora eu quero falar sobre como tudo funciona.

Uma VM é implementada como um objeto, para que você possa implementar facilmente o suporte a multithreading.

Possui um ponteiro para uma matriz com opcodes, IP (Instruction Pointer) - deslocamento da instrução executada e ponteiros para outras estruturas da VM.

A execução de código é um grande caso de mudança.

Basta fornecer uma descrição da VM:

 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;

Um pouco sobre o tratamento de exceções


Para fazer isso, a VM possui uma pilha de manipuladores de exceção e um grande bloco try / catch no qual a execução do código é quebrada. Na pilha, é possível colocar uma estrutura que possui um deslocamento do ponto de entrada no bloco de tratamento de captura e finalmente / final de exceção. Também forneci o ops trs, que é colocado antes da captura e lança o código para finalmente / final, se for bem-sucedido, excluindo simultaneamente o bloco com informações sobre manipuladores de exceção da parte superior da pilha correspondente. Apenas? Simples. É conveniente? Convenientemente.

Vamos falar sobre métodos e bibliotecas externas


Eu já os mencionei antes. Importações, bibliotecas ... Sem elas, o idioma não terá a flexibilidade e a funcionalidade desejadas.

Primeiramente, na implementação da VM, declaramos o tipo do método externo e o protocolo para chamá-lo.

 type TExternalFunction = procedure(PStack: pointer); cdecl; PExternalFunction = ^TExternalFunction;

Ao importar uma VM, o analisador de seção de importação preenche uma matriz de ponteiros para métodos externos. Portanto, cada método tem um endereço estático, calculado no estágio de montagem do aplicativo na VM e pelo qual o método desejado pode ser chamado.

A chamada ocorre posteriormente desta maneira durante a execução do código:

 TExternalFunction(self.extern_methods^.GetFunc(TSVMMem(self.stack.popv).GetW))(@self.stack);

Vamos escrever uma biblioteca simples para nossa VM


E deixe-a primeiro implementar o método 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.

Sumário


Provavelmente, terminarei meu primeiro artigo de um ciclo concebido.

Hoje descrevi a criação do idioma runtime com alguns detalhes. Acredito que este artigo será muito útil para pessoas que decidem tentar escrever sua própria linguagem ou entender como funcionam linguagens de programação semelhantes.

O código completo da VM está disponível no repositório, na ramificação / runtime / svm.

Se você gostou deste artigo, não tenha preguiça de dar uma vantagem no carma e elevá-lo no topo, tentei e tentarei por você.

Se algo não estiver claro para você, bem-vindo aos comentários ou ao fórum .

Talvez suas perguntas e respostas sejam interessantes não apenas para você.

Source: https://habr.com/ru/post/pt435202/

More articles:


All Articles