martes, 3 de noviembre de 2015

Un pequeño mnemotécnico.

Cuando trabajamos con los números enteros, existe una relación muy útil entre las comparaciones estrictas y las no estrictas. Es esta [$$a\le b \iff a<b+1$$] Igualmente su simétrica, [$$a\ge b \iff a+1>b$$]Con aritmética modular, la que se suele usar en computación debido a la precisión finita, es algo más imperfecto ya que no funciona en los casos extremos [$$a\le MAX; a< MIN$$] Donde [$MIN$] es el menor entero representado y [$MAX$] el mayor entero representado. Al usar aritmética modular [$$MAX+1=MIN$$]Por esa razón aunque [$a\le MAX$] es siempre cierto, al usar la relación "equivalente" obtenemos [$a< MAX+1 = MIN$] que es siempre falso.

Advirtiendo este caso, la única pega es acordarse si el [$+1$] se añade con el [$<$] o con el [$\le$] y si a un lado o al otro. Aquí entra en juego la regla mnemotécnica. El [$+1$] aparece en el lado mayor de la relación no estricta. Podemos imaginarnos como la rayita del igual se convierte en el [$1$] y podemos recordar el lado mayor ya que [$+1$] lo hace mayor.

Esta relación es muy útil para simplificar código ya que permite homogeneizar todas las condiciones de enteros (si no llegan a [$MIX$] o [$MAX$], claro). Otra relación también conocida es la de la negación [$$¬(a<b)\iff a\ge b$$] y su complementaria y simétricas.

sábado, 11 de julio de 2015

miniSL parte 27 - Funciones nativas sobre enteros (II)

En la última entrada mencionamos que la división debía realizarse de otra forma ya que no debemos permitir una división por cero. La misma restricción aparece en la operación resto.

Realmente tenemos que cambiar poco en comparación con la macro NATIVE_INTEGER_BINARY. Un if antes de la división que lance una excepción si intentamos dividir por cero y otro if que impida dividir sin argumentos. Esto es así porque la división no tiene un elemento neutro.
#define NATIVE_INTEGER_BINARY_DIVISION(name, op) \
CELL& Native_##name(Script& script, CELL& args, CELL& envir) \
{ CELL* a=&script.Evaluate(args, envir); \
 int r=0; \
 if(a->type!=CONS_CTOR) throw L"Division arity must not be zero"; \
 r=a->head->GetInteger(); \
 for(a=a->tail; a->type==CONS_CTOR; a=a->tail) \
 { int d=a->head->GetInteger(); \
  if(d==0) throw L"Division by zero"; \
  r=r op d; \
 } \
 return script.CreateInteger(r); \
}
Esto que hemos hecho hasta ahora es una macro. Con esta macro, generamos las funciones para la división y para el resto.
NATIVE_INTEGER_BINARY_DIVISION(Div, /)
NATIVE_INTEGER_BINARY_DIVISION(Mod, %)
En el siguiente post, veremos los operadores relacionales. Estos operadores son distintos a los aritméticos ya que siempre devuelven un booleano. Por eso requieren un tratamiento especial.

jueves, 30 de abril de 2015

miniSL parte 26 - Funciones Nativas sobre Enteros (I)

En esta entrada del lenguaje MiniSL vamos a empezar a definir las funciones predefinidas. Empezaremos por las operaciones básicas para enteros.

Todas las funciones predefinidas se almacenan en celdas NATIVE_VAL. Estas celdas almacenan un puntero a la función que vamos a definir. Al evaluarlas se ejecuta el siguiente código en la función Evaluate()

case NATIVE_VAL: return aux->native(*this, *c.operands, envir);

El primer argumento de una función nativa es el propio objeto Script. Usamos este objeto para crear nuevas celdas en el montículo o evaluar subexpresiones. El segundo argumento es la celda con la lista de operandos. Es importante aquí distinguir entre un operando y un argumento. Un operando es una expresión que todavía no se ha evaluado, mientras que un argumento es el valor obtenido de evaluar esa expresión en el entorno dinámico. Finalmente, ese entorno dinámico es el que se pasa en el tercer argumento.

Supongamos que queremos sumar dos números. Lo que tendríamos que hacer para hacer eso es evaluar los operandos para obtener los argumentos (recordemos que la evaluación de una lista es la lista de los resultados de la evaluación, ver en la parte 14 el caso  CONS_CTOR), sumarlos y crear una nueva celda con el resultado. Lo más tedioso es comprobar que los argumentos existen y navegar por la lista para obtenerlos. Sería algo como esta función:

CELL& Native_Add2(Script& script, CELL& args, CELL& envir)
{ 
 CELL* a=&script.Evaluate(args, envir);
 if(a->type==CONS_CTOR) 
 {
  int l=a->head->GetInteger();
  a=a->tail;
  if(a->type==CONS_CTOR)
   return script.CreateInteger(l + a->head->GetInteger()); 
 } 
 throw L"Argument missing";
}

Realmente, podemos definir las operaciones básicas para cero, uno o múltiples argumentos. Bastaría usar un bucle. Tomamos como resultado de sumar ningún argumento el elemento neutro de la suma que es el cero.

CELL& Native_AddN(Script& script, CELL& args, CELL& envir) 
{
 CELL* a=&script.Evaluate(args, envir); 
 int r=0;
 if(a->type==CONS_CTOR) 
 {
  r=a->head->GetInteger(); 
  for(a=a->tail; a->type==CONS_CTOR; a=a->tail)
   r=r + a->head->GetInteger();
 }
 return script.CreateInteger(r);
}

Y fácilmente podemos hacer una macro que cambie el + por lo que sea y el 0 por lo que sea. El único truco es usar el operador de concatenación de tokens ## para generar cada vez un nombre distinto.

#define NATIVE_INTEGER_BINARY(name, emptyval, op) \
CELL& Native_##name(Script& script, CELL& args, CELL& envir) \
{ CELL* a=&script.Evaluate(args, envir); \
 int r=emptyval; \
 if(a->type==CONS_CTOR) \
 { r=a->head->GetInteger(); \
  for(a=a->tail; a->type==CONS_CTOR; a=a->tail) \
   r=r op a->head->GetInteger(); \
 } \
 return script.CreateInteger(r); \
}

Y usamos esta macro para definir la suma, resta, multiplicación, and bit a bit, or bit a bit y xor bit a bit.

NATIVE_INTEGER_BINARY(Add, 0, +)
NATIVE_INTEGER_BINARY(Sub, 0, -)
NATIVE_INTEGER_BINARY(Mul, 1, *)
NATIVE_INTEGER_BINARY(BAnd, -1, &)
NATIVE_INTEGER_BINARY(BOr, 0, |)
NATIVE_INTEGER_BINARY(BXor, 0, ^)

No hemos definido ni la división ni el módulo ya que requieren la comprobación de que el denominador se distinto a cero. Lo dejamos para la siguiente entrada de esta serie.

lunes, 30 de marzo de 2015

miniSL parte 25 - Lectura de listas


Bienvenidos de nuevo a la serie de artículos sobre la implementación de MiniSL, un pequeño lenguaje de programación. Esta vez vamos a analizar la función que lee la sintaxis de las listas. Una lista no es más que una serie de expresiones separadas por un separador y que finaliza con un finalizador. Generalmente el separador será una coma o un punto y coma, mientras que el finalizador será un paréntesis que se cierra.

CELL& Script::ReadList(ISTREAM& i, ISTREAM::int_type separator, ISTREAM::int_type finalizer)
{

Para crear la lista necesitamos construirla de derecha a izquierda con las celdas de tipo CONS_CTOR que no son más que pares. Así, la lista (1,2,3,4) se almacena como (1, (2, (3, (4, EMPTY_LIT)))). Como leemos la lista de izquierda a derecha, hemos de guardarlas en una pila. Usaremos la variable seq para ese fin.

 std::vector<CELL*> seq;

Continuamos leyendo mientras no nos encontremos con el finalizador o el fin del fichero. Es importante ver aquí que podemos encontrarnos con una lista vacía y no entrar en el bucle. Eso deja la pila vacía.

 TOKEN t;
 while((t=PeekToken(i)).type!=T_RAW || (t.raw!=finalizer && t.raw!=ISTREAM::traits_type::eof()) )
 {

Siempre leemos una expresión y la guardamos en nuestra pila.

  seq.push_back(&ReadExpression(i));

Tras la expresión comprobamos que o bien viene un separador o un finalizador. Cualquier otra cosa es un error. Nos saltamos el separador y continuamos el bucle.

  t=PeekToken(i);
  if( t.type==T_RAW && t.raw==separator )
   ReadToken(i);
  else if( t.type!=T_RAW || t.raw!=finalizer )
   throw L"Expecting a separator or a finalizer after expression";
 }

Una vez leída la lista, lanzamos un error si nos detuvimos porque encontramos un EOF.

 if(t.type==T_RAW && t.raw==ISTREAM::traits_type::eof())
  throw L"Expecting finalizer but found EOF";

Consumimos el finalizador que nos ha detenido.

 ReadToken(i); //Skip finalizer

Ahora vamos a ir sacando las celdas de la pila para construir la lista mediante pares. La lista vacía es EMPTY_LIT.

 CELL* s=&CreateCell(EMPTY_LIT);

Mientras la pila tenga algo, lo vamos sacando y lo vamos incorporando a la lista. No hay otra forma de hacerlo que de derecha a izquierda, por eso usábamos la pila.

 while(!seq.empty())
 {
  s=&CreateCell(CONS_CTOR, seq.back(), s);
  seq.pop_back();
 }

Y ya está la lista. Incluso en el caso de que no hubiera ningún dato en la lista, la variable s apuntaría a EMPTY_LIT, la lista vacía, de forma correcta.

 return *s;
}

De esta manera hemos construido una lista usando celdas CONS_CTOR y EMPTY_LIT.
Con esta función hemos acabado el análisis sintáctico. A partir de ahora sólo nos queda introducir las funciones de nuestro lenguaje MiniSL para que podamos computar algo. Empezaremos en la siguiente entrega.

sábado, 13 de diciembre de 2014

miniSL parte 24 - Expresiones infijas

Seguimos estudiando el analizador sintáctico de miniSL. Hemos empezado con las expresiones de mayor precedencia. Primarias en la parte 22. Postfijas en la 23. Prefijas también en la 23. Ahora vamos a ver las infijas.

Si bien hasta ahora cada tipo de expresión tenía una única precedencia, con las infijas esto no es así. Una expresión infija puede tener una precedencia distinta a la de otra expresión infija. La precedencia de cada expresión infija viene dada por los operadores que la componen. De hecho, hemos visto ya el algoritmo para analizar las expresiones infijas en este blog. Es el algoritmo de playa de agujas.

En miniSL la función que implementa este algoritmo es ReadInfixExpression(). En esta versión del algoritmo usamos la recursividad. No es la versión más eficiente, pero sí es la más sencilla de entender. La idea es mantener siempre la precedencia de la expresión que estamos analizando. Si el siguiente operador es de menor precedencia, no lo analizamos y dejamos que sea la función que nos ha llamado la que se encargue. Obviamente, la primera llamada deberá ser con la precedencia más baja posible.

CELL& Script::ReadInfixExpression(ISTREAM& i, int precedence)
{

En la variable a vamos a mantener la expresión analizada hasta ahora que tendrá la precedencia dada en precedence o una mayor. Empezamos con una expresión prefija que es justo la de mayor precedencia tras las infijas, por lo que aseguramos esta condición.

CELL* a=&ReadPrefixExpression(i);

Ahora vemos que el siguiente token de la entrada sea un operador. Es decir, un T_SYMBOL. Si no es un operador, el análisis de la expresión no puede continuar y finalizamos. En este bucle continuaremos mientras vayamos encontrando operadores. También debemos tener en cuenta que si lo que nos encontramos no es un operador, no debemos consumir ese token ya que otra función podría necesitarlo para continuar el análisis léxico. Por eso usamos peek().

TOKEN t;
while((t=PeekToken(i)).type==T_SYMBOL)
{

En este punto sabemos que estamos tratando con un operador. Obtengamos qué operador es, qué precedencia tiene y qué asociatividad.

STRING const& s=*t.data->string_val;
int prec=SymbolPrecedenceAndAssoc(s);
bool right_assoc=(prec&1)!=0;

Ahora viene la decisión comentada anteriormente y núcleo del algoritmo. Si la precedencia del operador es menor que la de la expresión actual (precedencia que tenemos almacenada en el parámetro precedence), retornamos lo que hayamos analizado hasta ahora y la función que nos ha llamado deberá hacerse cargo de ese operador con una precedencia tan baja. En el caso de que el operador sea exactamente de la misma precedencia que la expresión que estoy analizando, deberemos decidir si lo aglutinamos en esta expresión (por lo que continuamos el algoritmo aquí) o en la expresión superior (por lo que retornamos a la función llamante). Esto depende de la asociatividad del operador como veremos algo más abajo.

if(right_assoc ? prec<precedence : prec<=precedence)
return *a;

Una vez que hemos decidido que debemos procesar este operador, lo consumimos de la entrada.

ReadToken(i);

A continuación leemos el resto de la expresión con precedencia mayor (o igual en el caso de asociatividad por la derecha) que el operador recién leído. Cuando se encuentre con una precedencia menor, volverá a esta función y seguiremos comparando con la precedencia de precedence.

CELL& b=ReadInfixExpression(i, prec);

Llegados a este punto, tenemos dos expresiones y un operador. Construimos las celdas correspondientes. La celda a se aglutina por la izquierda y la celda b por la derecha. El resultado se vuelve a almacenar en a. Esto significa que siempre asociamos por la izquierda en este bucle. Por esto mismo retornábamos en caso de precedencias iguales si queríamos asociar por la derecha.

CELL& operands=CreateCell(CONS_CTOR, a, &CreateCell(CONS_CTOR, &b, &CreateCell(EMPTY_LIT)));
a=&CreateCell(COMBINE_CODE, t.data, &operands );
}

Este retorno es la salida cuando encontramos un token que no es un operador y salíamos del bucle.

return *a;
}

Con esta función completada sólo nos falta implementar la función que lee listas. Esta función ReadList() ha aparecido ya varias veces usada en las expresiones primarias y postfijas. La describiremos en la siguiente parte de esta serie.

domingo, 15 de junio de 2014

miniSL Parte 23 - Expresiones postfijas y prefijas

Esta es otra parte de la serie dedicada al mini-lenguaje MiniSL. Tal como veníamos haciendo en las partes anteriores, vamos a seguir ascendiendo por las reglas de analizador descendente recursivo. La regla que usa las expresiones primarias es la de las expresiones postfijas. Esta regla está implementada por la función ReadPostfixExpression().

CELL& Script::ReadPostfixExpression(ISTREAM& i)
{

Siguiendo nuestra sintaxis, una expresión postfija es una expresión primaria.

 CELL* p=&ReadPrimaryExpression(i);

Seguida de ninguna, una o varias llamadas de función. Estas llamadas deben empezar forzosamente por el carácter “(”. No podemos consumirlo porque si no es una llamada a función, podría ser otra cosa importante como un operador infijo. Así que sólo ojeamos el siguiente token con PeekToken(). Este procedimiento de mirar por adelantado es muy usual en el reconocimiento sintáctico y se denomina lookahead (mira hacia delante). Se detalló el funcionamiento de PeekToken() en la parte 17 de esta serie.

 TOKEN t=PeekToken(i);
 while(t.type==T_RAW && t.raw=='(')
 {

Una vez que estamos seguros de que lo que tenemos es una llamada a función, la consumimos. Primero el paréntesis de apertura. Luego leemos la lista de argumentos en una celda especial de combinación (como se explicó en la parte sexta de esta serie). Finalmente, consumimos el paréntesis de cierre.

  t=ReadToken(i);
  p=&CreateCell(COMBINE_CODE, p, &ReadList(i, ',', ')'));
  t=PeekToken(i);
 }

 return *p;
}

Lo que generamos es un árbol en el cual cada nodo es una celda de combinación (COMBINE_CODE) que representa una llamada a función y en sus argumentos añadimos una lista. Veremos las listas en la sección 25, pero ya sabemos que las listas se construyen con celdas del tipo CONS_CTOR y EMPTY_LIT.


Para la función ReadPrefixExpression(), lo que haremos será lo siguiente.

CELL& Script::ReadPrefixExpression(ISTREAM& i)
{
 if(PeekToken(i).type==T_SYMBOL)
 {

Si encontramos un símbolo, lo consumimos y llamamos recursivamente a esta función para el argumento de la función prefija.
  TOKEN t=ReadToken(i);
  CELL& expr=ReadPrefixExpression(i);

El resultado lo guardamos como un único argumento (una única celda CONS_CTOR) en una llamada (celda COMBINE_CODE).

  return CreateCell(COMBINE_CODE, t.data, &CreateCell(CONS_CTOR, &expr, &CreateCell(EMPTY_LIT)));
 }

Si no empezábamos por un símbolo es que hemos llegado a la expresión postfija.

 return ReadPostfixExpression(i);
}

Estas funciones son simples y lo único que hacen es seguir la gramática. De hecho, estas funciones son la parte más representativa de lo que es un reconocedor sintáctico descendiente recursivo. En la siguiente parte veremos algo un poco distinto y usaremos el algoritmo de playa de agujas para leer expresiones infijas.

domingo, 2 de febrero de 2014

miniSL parte 22 - Expresiones primarias

En esta entrada de la serie dedicada al mini-lenguaje de programación MiniSL vamos a ver las expresiones primarias. Las expresiones primarias son las expresiones que no están formadas por otras expresiones o no hay ambigüedad en su análisis porque están parentizadas. En el caso de MiniSL eso incluye los siguientes casos:
  • Una expresión entre paréntesis.
  • Una lista entre corchetes. 
  • Un nombre.
  • Un literal (cadena o entero).
La función que lee una expresión primaria es ReadPrimaryExpression(). Lo primero que hace esta función es leer el siguiente token y, según sea su tipo, procede de una forma u otra.

CELL& Script::ReadPrimaryExpression(ISTREAM& i)
{
 TOKEN t=ReadToken(i);
 switch(t.type)
 {

Los tokens T_RAW consistían en un único carácter. Este carácter podrá ser o bien un paréntesis de apertura “(” o un corchete de apertura “[”. En el primer caso estamos en una expresión entre paréntesis y en el segundo caso una lista. Como vemos, no hay ambigüedad posible.

 case T_RAW:
  switch(t.raw)
  {

En el caso de expresión entre paréntesis, leemos la expresión. Comprobamos que el paréntesis se cierra usando ConsumeRawToken() que ya vimos en las funciones de ayuda. Finalmente, retornamos la celda leída en la expresión interna como la correspondiente a la parentización.

  case '(':
   {
    CELL& x=ReadExpression(i);
    ConsumeRawToken(i, ')', L"Expecting closing round bracket");
    return x;
   }

En el caso de una lista, usamos la función ReadList() indicando que la lista se separa por comas y termina en corchete “]”. Veremos la función ReadList() en la parte 25 de esta serie.

  case '[': return ReadList(i, ',', ']');
  default: throw L"Unexpected token";
  }

Tanto en el caso de nombres como de literales es muy fácil devolver la celda ya que el token la generaba y guardaba.

 case T_NAME: return *t.data;
 case T_LITERAL: return *t.data;
 default:  throw L"Expecting a primary expression";
 }
}

Como observamos, lo hecho no es más que una regla de un reconocedor descendente recursivo. En la siguiente parte de esta serie nos dedicaremos a las expresiones postfijas y prefijas.