Máquina Virtual FKScript

Esta entrada forma parte de una serie de artículos dedicados al proyecto FKScript, construcción de un compilador y una máquina virtual para un lenguaje de script con C# y ANTLR, entre los cuales podrás encontrar una descripción detallada de cada módulo, documentación técnica, ejemplos y tutoriales de uso que pueden ser de tu interés. No olvides consultar la página principal de FKScript para más información.

El último módulo necesario en nuestro sistema será la máquina virtual, que será la encargada de interpretar el fichero generado por el ensamblador y ejecutar las instrucciones contenidas en él.

En los próximos apartados veremos la estructura de esta máquina virtual, los procesos de carga de y ejecución del programa y el mecanismo definido para integrar la máquina virtual con otras aplicaciones y permitir la interacción entre ambas.

1. Estructura de la máquina virtual

La estructura de la máquina virtual FKVM se representa en la siguiente figura:

Estructura Máquina Virtual FKVM

Estructura Máquina Virtual FKVM

A continuación se realiza una breve descripción de cada uno de estos elementos.

1.1. Segmento de código

En esta estructura se almacenará todo el código del programa a ejecutar, sin incluir los datos de la cabecera del programa ni los literales iniciales contenidos en el fichero del programa.

1.2. Registro contador de programa

Este registro contendrá en todo momento la posición, dentro del segmeto de código, de la próxima instrucción a ejecutar por la máquina virtual, o en su defecto, el próximo parámetro a leer durante la ejecución de una instrucción determinada.

1.3. Pila

La pila constituye el elemento más importante de la máquina virtual y aque en ella se almacenarán las variables locales del programa y albergará todos los resultados intermedios producidos por el programa en ejecución. Sobre esta estructura la máquina virtual realizará todas las operaciones del programa almacenando en ella todos los valores necesarios para su ejecución. Los valores númericos y booleanos se almacenarán directamente en la pila, y para los valores de tipo cadena se almacenará una referencia a la memoria dinámica.

1.4. Memoria dinámica

En esta estructura de la máquina virtual se almacenarán todos los valores que no sean numéricos o booleanos. En nuestro caso, tan sólo contendrá los valores de tipo cadena de caracteres, ya sean literales utilizados en operaciones del programa o nombres de funciones externas.

1.5. Tabla de funciones API

En esta tabla se registrarán todas las funciones externas disponibles para ser llamadas durante la ejecución de un programa FKScript. Contendrá la relación entre el nombre de éstas y una referencia a la función en sí.

Todas estas estructuras, a excepción de las relacionadas con las funciones API que se comentarán más adelante, estarán representadas en nuestra implementación mediante las siguientes colecciones de C#:

//Pila
private Pila pila = null;

//Memoria dinámica
private List<string> heap = null;

//Segmento de código
private List<float> codigo = null;

//Contador de programa (PC)
private int pc = 0;

2. Carga de un programa

Durante el proceso de carga de un programa en la máquina virtual se deberán realizar las siguientes operaciones:

  1. Apertura y lectura del fichero de entrada.
  2. Lectura y registro de la cabecera del fichero.
  3. Inicialización del segmento de código, pila y memoria dinámica.
  4. Lectura y almacenamiento en la memoria dinámica de los literales iniciales del programa.
  5. Lectura y almacenamiento en el segmento de código de todo el código del programa.

La cabecera del fichero se almacenará en un objeto de tipo Cabecera como el que ya utilizamos durante el ensamblado del programa.

//Apertura del fichero de entrada
BinaryReader fent = new BinaryReader(
new FileStream(path,
FileMode.Open, FileAccess.Read));

//Lectura de la cabecera
cab.magic = fent.ReadInt32();
cab.version = fent.ReadInt32();
cab.revision = fent.ReadInt32();
cab.programName = fent.ReadString();
cab.stackSize = fent.ReadInt32();
cab.heapSize = fent.ReadInt32();
cab.nLocals = fent.ReadInt32();
cab.nConst = fent.ReadInt32();

La inicialización de estructuras es también sencilla y se utilizará parte de la información leida de la cabecera. Así, la pila se inicializará con un tamaño inicial igual al número de variables locales del programa, cab.nLocals, y la memoria dinámica se inicializará al tamaño máximo permitido cab.heapSize.

//Inicialización de estructuras
pc = 0;                                  //Contador de programa
codigo = new List<float>();              //Segmento de código
pila = new Pila(cab.nLocals);            //Pila
heap = new List<string>(cab.heapSize);   //Memoria dinámica

Por último, insertaremos en la memoria dinámica los literales iniciales del programa contenidos en la tabla de literales del fichero de entrada y cargaremos el segmento de código con todo el código del programa.

//Literales iniciales
for (int i = 0; i < cab.nConst; i++)
{
heap.Add(fent.ReadString());
}

//Código del programa
while (fent.PeekChar() != -1)
{
codigo.Add(fent.ReadSingle());
}

fent.Close();

3. Ejecución del programa

El bucle principal de ejecución del programa, una vez inicializadas y cargadas todas las estructuras de la máquina virtual, será muy sencillo. Nos limitaremos a ejecutar todas las instrucciones del programa mientras el contador de programa no haya alcanzado el final del fichero.

Se ha añadido una nueva inicialización previa de la máquina virtual para permitir varias ejecuciones de un mismo programa sin tener que cargarlo de nuevo.

public void ejecutar()
{
//Inicialización de registros y estructuras
inicializarEstado();

//Bucle principal
while (pc < codigo.Count)
{
ejecutarInstruccion();
}
}

4. Ejecución de instrucciones

El proceso de ejecución de una instrucción dependerá obviamente de cada instrucción leída del fichero de entrada. Definiremos un método para cada una de las instrucciones soportadas por FKIL e insertaremos un paso inicial donde se decida qué método ejecutar según la instrucción leida.

private void ejecutarInstruccion()
{
int opcode = (int)codigo[pc++];

switch (opcode)
{
case IPUSH:
case FPUSH:
case SPUSH:
case BPUSH:
ejecutarPUSH();
break;
case POP:
ejecutarPOP();
break;
case IADD:
case FADD:
ejecutarADD();
break;
case ISUB:
case FSUB:
ejecutarSUB();
break;
...
}

Como puede observarse en el código anterior, algunas de las instrucciones de FKIL podrán agruparse en un sólo método de ejecución ya que su efecto sobre la máquina virtual será exactamente el mismo. Así, por ejemplo, todas las operaciones de tipo PUSH se ejecutarán mediante el método único ejecutarPUSH().

A continuación veremos la implementación de los métodos de ejecución de algunas instrucciones de FKIL. En el código fuente proporcionado pordrán consultarse el resto de instrucciones.

4.1. Instrucciones PUSH

Para instrucciones de tipo PUSH leeremos el dato a apilar desde el segmento de código (posición actual del contador de programa) y lo añadiremos a la cima de la pila.

private void ejecutarPUSH()
{
float op1 = codigo[pc++];
pila.Add(op1);
}

4.2. Instrucciones LOAD

Para instrucciones de tipo LOAD leeremos el número de la variable a recuperar desde el segmento de código (posición actual del contador de programa) y lo añadiremos a la cima de la pila. Recordemos que las variables locales también se encuentran almacenadas en la pila.

private void ejecutarLOAD()
{
int op1 = (int)codigo[pc++];
pila.Add(pila[op1]);
}

4.3. Instrucciones STORE

Para instrucciones de tipo STORE leeremos el número de la variable a actualizar desde el segmento de código (posición actual del contador de programa), actualizaremos la variable y desapilaremos el valor almacenado.

private void ejecutarSTORE()
{
int op1 = (int)codigo[pc++];
pila[op1] = pila.pop();
}

4.4. Instrucciones aritméticas

Las instrucciones aritmética sobre valores enteros o reales se realizarán también de forma conjunta mediante un sólo método. Éste leerá y desapilará los dos valores sobre los que actuará la instrucción, ejecutará la operación y volverá a apilar en la cima de la pila el resultado obtenido. Como ejemplo, veamos cómo quedaría la ejecución de una instrucción de tipo ADD:

private void ejecutarADD()
{
float op1, op2;

op1 = pila.pop();
op2 = pila.pop();
pila.Add(op1 + op2);
}

4.5. Instrucciones de comparación

Las comparaciones numéricas o de booleanos serán igual de sencillas que las ya vistas hasta el momento. Se leerán y desapilarán los valores a comparar de la pila, se realizará la comparación y se generará el resultado según el convenio establecido de valores de retorno. En nuestro caso indicamos este convenio en los cometarios al principio del método de ejecución. Así, por ejemplo, la comparación numérica quedaría de la siguiente forma:

private void ejecutarNCMP()
{
//Si OP1 > OP2 --> -1
//Si OP1 = OP2 -->  0
//Si OP1 < OP2 --> +1

float op1, op2, res = 0F;

op1 = pila.pop();
op2 = pila.pop();

if (op1 > op2)
res = -1.0F;
else if (op1 < op2)
res = +1.0F;

pila.Add(res);
}

4.6. Instrucciones de salto condicional

Veamos ahora algún ejemplo de instrucción de salto de tipo IF. Estas instrucciones leerán y desapilarán el valor a comparar desde la pila, realizarán la comparación correspondiente según el tipo concreto de instrucción y actualizarán el contador de programa con el valor correspondiente según se haya cumplido la comparación o no. Así, si la comparación es verdadera se actualizará el contador de programa con el valor almacenado en la cima de la pila (segundo parámetro de la instrucción de salto), y en caso contrario se incrementará el contador en una unidad como ocurría con el resto de instrucciones. Veamos como ejemplo la instrucción IFEQ:

private void ejecutarIFEQ()
{
float op1;

op1 = pila.pop();

if (op1 == 0F)
pc = (int)codigo[pc];
else
pc++;
}

4.7. Instrucción de llamada a función externa

Por último veamos como implementar la ejecución de llamadas a funciones externas. En primer lugar recuperaremos el nombre de la función a partir del parámetro almacenado en la cima de la pila y los literales almacenados en la memoria dinámica de la máquina virtual. Con este valor, accederemos a la tabla de funciones API y en caso de tratarse de una llamada válida llamaremos a la función a través de su delegado.

private void ejecutarCALLAPI()
{
string fun = heap[(int)codigo[pc++]];

if (registroApi.ContainsKey(fun))
registroApi[fun]();
}

5. Integración con otras aplicaciones

Uno de los requisitos que nos pusimos al comienzo de este desarrollo fue que nuestra máquina virtual pudiera integrarse con otras aplicaciones, siempre que éstas expusieran una API con el formato correcto, de forma que pudieran comunicarse entre sí. Dicho de otra forma, queremos que nuestra máquina virtual pueda acoplarse fácilmente como módulo a cualquier otra aplicación y que podamos utilizar parte de la funcionalidad de dicha aplicación desde nuestro lenguaje de script.

Si consultamos la especificación de FKScript, podemos ver que la forma de llamar a funciones de la API de una aplicación externa será declarar dichas funciones al comienzo del programa mediante la palabra clave api e insertar llamadas en el programa (utilizando la sintaxis tradicional de C# o Java) como si de cualquier otra expresión se tratara. Veamos un ejemplo:

api float calcularRadio();
api void dibujarCirculo(int x, int y, float radio);

program void Prueba
{
float r;

r = 10 + calcularRadio();

dibujarCirculo(50, 100, r);
}

En el programa anterior se utilizan dos funciones de la API de una aplicación externa. Ambas funciones están convenientemente declaradas al comienzo del script, indicando su nombre, parámetros y tipo de salida. En el cuerpo del programa se utiliza la primera de ellas, sin parámetros, en el interior de una expresión y la segunda como llamada aislada sin devolver ningún resultado, ambas formas serán válidas en FKScript.

Cuando compilamos este programa a código intermedio, el resultado que obtendremos será el siguiente:

.program Prueba
.locals 1
ipush 10
callapi calcularRadio //Llamada a la función de la API
iadd
istore 0
ipush 50 //Primer parámetro de la llamada = 50
ipush 100 //Segundo parámetro de la llamada = 100
fload 0 //Tercer parámetro de la llamada = Variable ‘r’ (nº variable = 0)
callapi dibujarCirculo //Llamada a la función de la API

Vemos que las llamadas a funciones de la API se transforman en llamadas a la instrucción callapi de FKIL. Además, como se observa, los parámetros que reciba dicha llamada serán apilados previamente a la ejecución de dicha instrucción.

Una vez visto cómo funcionan a alto nivel las llamadas a la API debemos plantearnos varias cuestiones. En primer lugar habrá que implementar algún mecanismo para que la aplicación que hospedará a la máquina virtual comunique a ésta las funciones de su API que estarán disponibles, y en segundo lugar habrá que definir la forma en que deberán estar definidas estas funciones y la forma de comunicación entre ambas aplicaciones.

5.1. Registro de funciones API

Tanto para poder validar las llamadas realizadas a funciones externas (algo que se hará por tanto en tiempo de ejecución y no durante la compilación) como para disponer de las referencias necesarias a dichas funciones la máquina virtual deberá contar con un índice donde se almacene de alguna forma la colección de funciones externas disponibles.

En nuestro caso esto lo conseguiremos utilizando una colección de delegados. Un delegado podría definirse de forma sencilla como una referencia a una función (sé que alguien me caneará por explicarlo de esta manera :) con un prototipo concreto, es decir, un determinado tipo de salida y unos parámetros definidos.

Dado que no sabemos a priori el prototipo de todas las posibles funciones que pueden formar parte de una API determinada, nosotros vamos a optar por obligar a que todas las funciones de la API de una aplicación que quiera hacer uso de FKScript como lenguaje integrado tengan la siguiente forma:

void NombreFuncionAPI()

Es decir, que ninguna función externa podrá recibir directamente parámetros ni devolver ningún resultado. Aunque esto pueda parecer un gran inconveniente no es tal, ya que en la práctica estas restricciones no serán reales sino sólo una cuestión de forma. En el apartado siguiente veremos cómo solventar esto para que nuestras funciones puedan recibir parámetros y devolver resultados.

Una vez decidida la forma que tendrán las funciones externas ya podemos definir nuestro delegado y la colección que hará las funciones de índice:

public delegate void ApiCall();
private Dictionary<string, ApiCall> registroApi = null;

La colección registroApi contendrá una relación entre los nombres de las funciones disponibles (primer parámetro: string) y una referencia a la función propiamente dicha (segundo parámetro: ApiCall) de forma que ésta pueda ser llamada directamente desde la colección.

El mantenimiento de este ínidce deberá realizarlo la aplicación host, es decir, que será la aplicación contenedora la que añada o elimine las funciones que estarán disponibles para su uso desde FKScript. Por lo tanto, tendremos que proporcionar a ésta una forma de realizar estas operaciones. Definiremos para ello dos métodos con los que poder registrar y eliminar funciones del índice de forma sencilla:

public void registrarFuncionApi(string nombre, ApiCall ac)
{
registroApi.Add(nombre, ac);
}

public void deregistrarFuncionApi(string nombre)
{
registroApi.Remove(nombre);
}

5.2. Definición de la API de la aplicación externa

Como dijimos en el apartado anterior, las funciones definidas como API de la aplicación externa deberán tener todas el mismo prototipo: no podrár recibir parámetros ni devolver resultados. Sin embargo ya indicamos que esto no era más que una cuestión de forma y que por tanto nuestras funciones sí que podrían realizar dichas operaciones en la práctica. ¿Cómo conseguiremos esto?

Tanto la recepción de parámetros como la devolución de resultados se realizarán de forma explícita mediante operaciones de la propia función de la API, es decir, será cada función la encargada de leer desde la máquina virtual los parámetros que le sean necesarios y de devolver a la máquina virtual el resultado generado en caso de ser así.

Para ello, implementaremos en nuestra máquina virtual una serie de métodos públicos que puedan ser llamados desde las funciones API para realizar todas las operaciones descritas.

Para la lectura de parámetros la máquina virtual devolverá el dato apilado en la cima de la pila, siempre teniendo en cuenta su tipo:

public int obtenerParametroInt()
{
return (int)pila.pop();
}

public float obtenerParametroFloat()
{
return pila.pop();
}

public bool obtenerParametroBool()
{
return pila.pop() == 0F ? false : true;
}

public string obtenerParametroString()
{
return heap[(int)pila.pop()];
}

Y para la devolución de resultados la máquina virtual se limitará a apilar el dato proporcionado por la función API, teniendo en cuenta su tipo para el correcto almacenamiento y acciones adicionales (como por ejemplo el registro de una cadena en la tabla de literales):

public void devolverRetornoInt(int ret)
{
pila.push((float)ret);
}

public void devolverRetornoFloat(float ret)
{
pila.push(ret);
}

public void devolverRetornoInt(bool ret)
{
pila.push(ret == true ? 1F : 0F);
}

public void devolverRetornoString(string ret)
{
heap.Add(ret);

pila.push((float)heap.Count-1);
}

Como ejemplo, imaginemos que tenemos que implementar una función externa que indique si un determinado número entero es par. Nuestra función recibirá como parámetro un número entero y devolverá como resultado un booleano. La implementación quedaría de la siguiente forma:

public void esPar()   //Prototipo real:  bool esPar(int num)
{
bool res = false;

//Leemos el parámetro desde la máquina virtual
int num = vm.obtenerParametroInt();

if(num % 2 == 0)
res = true;

//Devolvemos el resultado a la máquina virtual
vm.devolverRetornoBool(res);
}

El código fuente completo de la máquina virtual puede descargarse pulsando aquí.

Esta entrada forma parte de una serie de artículos dedicados al proyecto FKScript, construcción de un compilador y una máquina virtual para un lenguaje de script con C# y ANTLR, entre los cuales podrás encontrar una descripción detallada de cada módulo, documentación técnica, ejemplos y tutoriales de uso que pueden ser de tu interés. No olvides consultar la página principal de FKScript para más información.