Geekly articles weekly

Escribimos nuestro lenguaje de programación, parte 1: escribimos un lenguaje VM

Introduccion


Buen día a todos los habrachitateli!

Entonces, quizás valga la pena decir que el objetivo de mi trabajo, sobre la base de la cual se escribirán varias estatuas, fue crear un YP completamente funcional desde 0 y luego compartir mi conocimiento, mejores prácticas y experiencia con aquellos que estén interesados.

Describiré la creación del lenguaje que describí anteriormente aquí .

Interesó a muchos y provocó una acalorada discusión en los comentarios. Por lo tanto, el tema es interesante para muchos.

Creo que vale la pena publicar inmediatamente información sobre el proyecto:

Sitio (se completará con la documentación un poco más tarde).
Repositorio

Para tocar el proyecto usted mismo y ver todo en acción, es mejor descargar el repositorio y ejecutar todo desde la carpeta bin. En el lanzamiento, no tengo prisa por subir las últimas versiones del idioma y el tiempo de ejecución, porque a veces es demasiado flojo para mí hacerlo.

Puedo codificar en C / C ++ y Object Pascal. Escribí el proyecto en FPC desde En mi opinión, este lenguaje es mucho más simple y más adecuado para escribir así. El segundo factor determinante fue que FPC admite una gran cantidad de plataformas de destino, y puede reconstruir el proyecto para la plataforma deseada con un mínimo de modificaciones. Si por alguna razón no me gusta Object Pascal, entonces no te apresures a cerrar la publicación y correr para arrojar piedras al comentario. Este lenguaje es muy hermoso e intuitivo, pero no proporcionaré tanto código. Justo lo que necesitas.

Entonces, tal vez comenzaré mi historia.

Fijamos metas


En primer lugar, cualquier proyecto necesita sus objetivos y conocimientos tradicionales, que deberán implementarse en el futuro. Es necesario decidir de antemano qué tipo de lenguaje se creará para escribir la máquina virtual principal.

Los puntos clave que determinaron el desarrollo posterior de mi VM son los siguientes:

  • Escritura dinámica y conversión de tipos. Decidí organizar su apoyo en la etapa de desarrollo de la VM.
  • Soporte multihilo. Incluí este elemento en esta lista de antemano para diseñar correctamente la arquitectura de la VM y organizar el soporte para subprocesos múltiples en el nivel central de la VM, y no más tarde con muletas.
  • Exportación de métodos externos. Sin esto, el lenguaje será inútil. A menos que lo inserte en cualquier proyecto.
  • Compilación del lenguaje (en un único archivo ejecutable abstracto). Parcialmente compilado o interpretado? Mucho depende de esto.
  • Arquitectura general de VM. ¿La pila o el registro será nuestra VM? Traté de implementar esto y aquello. Elegí una VM apilada para soporte.
  • ¿Cómo ves trabajar con variables, matrices, estructuras? Personalmente, en ese momento quería implementar un lenguaje en el que casi todo esté vinculado a punteros implícitos, porque tal enfoque ahorraría enormemente memoria y simplificaría la vida del desarrollador. Si permitimos que algo grande pase a los métodos, entonces solo se transferirá automáticamente un puntero a ese grande.

Entonces, elegí las prioridades anteriores y comencé a implementar la máquina virtual de lenguaje. Esto es extraño, por supuesto, generalmente los analizadores / traductores se escriben primero y luego las máquinas virtuales. Bueno, comencé a desarrollar el proyecto en este orden y lo describiré más en el orden en que lo desarrollé.

Debo decir de inmediato que llamé a VM lo más elocuente posible: SVM (máquina virtual basada en pila).

Comencemos con la implementación de la clase variable


Inicialmente, simplemente usé un tipo de variante, porque es más simple y más rápido. Era una muleta, pero apoyó el proyecto y me permitió implementar rápidamente la primera versión de VM y lenguaje. Más tarde me senté en el código y escribí una implementación de mi "variante". En esencia, debe escribir una clase que almacene un puntero a un valor en la memoria, en mi implementación es null/cardinal/int64/double/string/array . Se podría usar la tipificación de casos, pero pensé que sería mejor implementar la forma en que lo hice.

Antes de comenzar a escribir el código de clase, decidí poner inmediatamente la directiva {$ H +} en el encabezado del módulo para un soporte más flexible para cadenas en el idioma futuro.
P.S. para aquellos que pueden no ser conscientes de la diferencia entre los modos H- y H + FPC.

Al ensamblar código en modo H, las cadenas se presentarán como una matriz de caracteres. Cuando H + - como un puntero a un pedazo de memoria. En el primer caso, las líneas serán inicialmente fijadas en longitud y limitadas por defecto a 256 caracteres. En el segundo caso, las líneas se expandirán dinámicamente y se pueden meter muchos más caracteres en ellas. Trabajarán un poco más lento, pero más funcionalmente. Con H +, también puede declarar cadenas como una matriz de caracteres, por ejemplo de esta manera:

 var s:string[256];
Entonces, para empezar, declararemos a Enum un tipo, que usaremos como un determinado indicador para determinar el tipo de datos por puntero:

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

A continuación, describimos la estructura básica de nuestro tipo de variable y algunos 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;

La clase no hereda de nada, por lo que se pueden omitir las llamadas heredadas en el constructor y el destructor. Prestaré atención a la directiva en línea. Es mejor agregar {$ inline on} al encabezado del archivo, seguro. Su uso activo en máquinas virtuales aumentó significativamente la productividad (¡Mb en algún lugar hasta en un 15-20%!). Ella le dice al compilador que el cuerpo del método está mejor incrustado en el lugar de su invocación. El código de salida será un poco más grande al final, pero funcionará más rápido. En este caso, se recomienda usar en línea.

Ok, en esta etapa hemos lavado los cimientos de nuestra clase. Ahora necesitamos describir un número de setters y getters (setter & getter) en nuestra clase.

La tarea es escribir un par de métodos que le permitirán estudiar y luego recuperar los valores de nuestra clase.

Primero, descubramos la asignación de un valor para nuestra clase. Primero puede escribir un setter generalizado, y luego, para tipos de datos individuales:

 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;

Ahora puedes escribir código para un par de captadores:

 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;

Bien, genial, ahora que ha pasado un tiempo mirando el IDE y escribiendo con entusiasmo el código para los iniciadores y captadores, nos enfrentamos a la tarea de implementar el soporte para nuestro tipo de operaciones matemáticas y lógicas. Como ejemplo, daré la implementación de la operación de adición:

 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;

Todo es simple Se pueden describir otras operaciones de manera similar, y ahora nuestra clase está lista.
Para las matrices, por supuesto, aún necesita un par de métodos, un ejemplo de cómo obtener un elemento por í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;

Genial Ahora podemos seguir adelante.

Nos damos cuenta de una pila


Después de un tiempo, llegué a tales pensamientos. La pila debe ser tanto estática (para la velocidad) como dinámica (para la flexibilidad) al mismo tiempo.

Por lo tanto, la pila se implementa en bloques. Es decir cómo debería funcionar: inicialmente, la matriz de la pila tiene un cierto tamaño (decidí establecer el tamaño del bloque en 256 elementos para que fuera hermoso y no pequeño). En consecuencia, se incluye un contador con la matriz, que indica la parte superior actual de la pila. La reasignación de memoria es una operación extra larga, que se puede realizar con menos frecuencia. Si se introducen más valores en la pila, su tamaño siempre se puede expandir al tamaño de otro bloque.

Traigo toda la implementación de la pila:

 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;

En métodos externos, la VM pasará un puntero a la pila para que puedan tomar los argumentos necesarios desde allí. Posteriormente se agregó un puntero a la secuencia de VM, de modo que las llamadas de devolución de llamada de métodos externos podrían implementarse y, en general, transferir más potencia sobre los métodos de VM.

Entonces, cómo te familiarizaste con cómo se organiza la pila. La pila de devolución de llamada está organizada de la misma manera, por simplicidad y conveniencia de las operaciones de devolución y llamada y la pila del recolector de basura. Lo único son los otros tamaños de los bloques.

Habla de basura


Suele ser mucho, mucho. Y necesitas hacer algo con eso.

En primer lugar, quiero hablar sobre cómo se organizan los recolectores de basura en otros idiomas, por ejemplo, en Lua, Ruby, Java, Perl, PHP, etc. Trabajan según el principio de contar punteros a objetos en la memoria.

Es decir así que asignamos memoria para algo, es lógico: el puntero se colocó inmediatamente en una variable / matriz / en otro lugar. El recolector de basura en tiempo de ejecución agrega inmediatamente este puntero a sí mismo con una lista de posibles objetos basura. En segundo plano, el recolector de basura monitorea constantemente todas las variables, matrices, etc. Si no hay un puntero a algo de la lista de basura posible, significa que la basura y la memoria de debajo deben eliminarse.

Decidí vender mi bicicleta. Estoy más acostumbrado a trabajar con memoria según el principio de Taras Bulba. Te di a luz, te mataré, quiero decir, cuando llame al próximo Libre en la próxima clase. Por lo tanto, el recolector de basura de mi VM es semiautomático. Es decir debe llamarse en modo manual y trabajar con él en consecuencia. A su vez, se agregan punteros a objetos temporales declarados (este rol recae principalmente en el traductor y un poco en el desarrollador). Para liberar memoria de debajo de otros objetos, puede usar un código de operación separado.

Es decir el recolector de basura en el momento de la llamada tiene una lista de punteros listos para usar que debe revisar y liberar memoria.

Entonces, ahora trataremos con la compilación en un archivo ejecutable abstracto


Originalmente, la idea era que las aplicaciones escritas en mi idioma podrían ejecutarse sin fuente, como es el caso con muchos lenguajes similares. Es decir Se puede utilizar con fines comerciales.

Para hacer esto, determine el formato de los archivos ejecutables. Tengo lo siguiente:

  1. Encabezado, por ejemplo "SVMEXE_CNS".
  2. Una sección que contiene una lista de bibliotecas desde las cuales se importarán los métodos.
  3. La sección de importación de los métodos requeridos, las bibliotecas desde las cuales se importan los métodos se indican por su número en la sección anterior.
  4. Sección de constantes.
  5. Sección de código

No creo que valga la pena exponer los pasos detallados para implementar analizadores para estas secciones, porque usted mismo puede ver todo en mi repositorio.

Ejecución de código


Después de analizar las secciones anteriores e inicializar la VM, tenemos una sección con el código. En mi VM, se ejecuta un bytecode no alineado, es decir las instrucciones pueden ser de longitud arbitraria.

Un conjunto de códigos de operación: instrucciones para una máquina virtual con pequeños comentarios que muestro con anticipación a continuación:

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

Entonces, usted se familiarizó con fluidez con las operaciones que la VM escrita por mí puede llevar a cabo. Ahora quiero hablar sobre cómo funciona todo.

Una VM se implementa como un objeto, por lo que puede implementar fácilmente el soporte de subprocesos múltiples.

Tiene un puntero a una matriz con códigos de operación, IP (puntero de instrucción): desplazamiento de la instrucción ejecutada y punteros a otras estructuras de VM.

La ejecución del código es un gran caso de cambio.

Solo dé una descripción de la 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;

Un poco sobre el manejo de excepciones


Para hacer esto, la VM tiene una pila de controladores de excepciones y un gran bloque try / catch en el que se envuelve la ejecución del código. Desde la pila, puede colocar una estructura que tenga un desplazamiento de punto de entrada en el bloque de manejo de excepciones de captura y finalmente / final. También proporcioné el código de operación trs, que se coloca antes de capturar y arroja el código para finalmente / finalizar si tiene éxito, eliminando simultáneamente el bloque con información sobre los controladores de excepciones desde la parte superior de la pila correspondiente. Es simple? Simple ¿Es conveniente? Convenientemente

Hablemos de métodos externos y bibliotecas.


Ya los mencioné antes. Importaciones, bibliotecas ... Sin ellas, el lenguaje no tendrá la flexibilidad y funcionalidad deseadas.

En primer lugar, en la implementación de la VM, declaramos el tipo de método externo y el protocolo para llamarlo.

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

Al importar una VM, el analizador de la sección de importación llena una matriz de punteros a métodos externos. Por lo tanto, cada método tiene una dirección estática, que se calcula en la etapa de ensamblaje de la aplicación en la VM y por la cual se puede llamar al método deseado.

La llamada más tarde ocurre de esta manera durante la ejecución del código:

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

Escribamos una biblioteca simple para nuestra VM


Y deje que primero implemente el 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.

Resumen


Sobre esto, probablemente terminaré mi primer artículo de un ciclo concebido.

Hoy describí la creación del lenguaje en tiempo de ejecución con cierto detalle. Creo que este artículo será muy útil para las personas que deciden intentar escribir su propio lenguaje o comprender cómo funcionan los lenguajes de programación similares.

El código VM completo está disponible en el repositorio, en la rama / runtime / svm.

Si te gustó este artículo, entonces no seas perezoso para agregar un plus en karma y elevarlo en la parte superior, lo intenté y lo intentaré por ti.

Si algo no está claro para usted, bienvenido a los comentarios o al foro .

Quizás sus preguntas y respuestas sean interesantes no solo para usted.

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

More articles:


All Articles