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.

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.

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.

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.