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.
martes, 3 de noviembre de 2015
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.
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()
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:
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.
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.
Y usamos esta macro para definir la suma, resta, multiplicación, and bit a bit, or bit a bit y xor bit a bit.
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.
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.
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.
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().
En este punto sabemos que estamos tratando con un operador. Obtengamos qué operador es, qué precedencia tiene y qué asociatividad.
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.
Una vez que hemos decidido que debemos procesar este operador, lo consumimos de la entrada.
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.
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.
Este retorno es la salida cuando encontramos un token que no es un operador y salíamos del bucle.
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.
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().
Siguiendo nuestra sintaxis, una expresión postfija es una expresión primaria.
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.
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.
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.
Si encontramos un símbolo, lo consumimos y llamamos recursivamente a esta función para el argumento de la función prefija.
El resultado lo guardamos como un único argumento (una única celda CONS_CTOR) en una llamada (celda COMBINE_CODE).
Si no empezábamos por un símbolo es que hemos llegado a la expresión postfija.
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.
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:
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.
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.
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.
Tanto en el caso de nombres como de literales es muy fácil devolver la celda ya que el token la generaba y guardaba.
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.
- Una expresión entre paréntesis.
- Una lista entre corchetes.
- Un nombre.
- Un literal (cadena o entero).
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.
miércoles, 18 de diciembre de 2013
La historia de Mel
Una historia clásica de un pasado mejor. Nada mejor para estas fiestas navideñas. Citado de aquí.
Fuente: utastro!nather (Ed Nather), 21 de Mayo de 1983.
La historia de Mel
En un artículo reciente, hablando del lado macho de la programación, se hizo la simple y llana afirmación:
Quizá lo hagan ahora, en esta era decadente de cerveza sin alcohol, calculadoras de bolsillo y programas "user-friendly" pero en los Viejos Buenos Tiempos, cuando el término "software" sonaba a broma y los Verdaderos Ordenadores estaban hechos de tambores y tubos de vacío los Verdaderos Programadores escribían en código máquina. No FORTRAN. No RATFOR. Ni siquiera ensamblador. Código máquina. Crudos, sin adornos, inescrutables números hexadecimales. Directamente
Toda una nueva generación de programadores creció en la ignorancia de este glorioso pasado, por lo que me siento obligado a describir, tan bien como me sea posible debido al salto generacional, cómo un Verdadero Programador escribía código.
Le llamaré Mel, porque ese era su nombre.
Conocí a Mel cuando empecé a trabajar para Royal McBee Computer Corp., una extinta subsidiaria de una compañía de maquinas de escribir. La empresa producía el LGP-30, un pequeño y barato (para los estándares de la época) ordenador con memoria de tambor, y empezaba a producir el RPC-4000, un ordenador con memoria de tambor mejorado, más grande y más rápido. Estos ordenadores costaban demasiado, y tampoco duraron mucho de todas formas (es por esto que no habéis oído hablar de la compañía ni del ordenador)
Había sido contratado para escribir un compilador de FORTRAN para esta nuevo portento y Mel fue mi guía a sus maravillas. Mel no soportaba a los compiladores.
– ¿Si un programa no puede rescribir su propio código — preguntó — qué tiene de bueno?
Mel había escrito, en hexadecimal, el programa de ordenador más conocido que la compañía poseía. Corría sobre el LGP-30 y jugaba al blackjack con los compradores potenciales en las exposiciones de ordenadores. Su efecto era increíble. El stand del LGP-30 estaba siempre lleno en cada exposición, y los vendedores de IBM estaban allí de pie sin poder hacer otra cosa que hablar entre ellos. Si aquello servía para vender ordenadores o no era una pregunta que nadie se planteó nunca.
El trabajo de Mel era reescribir el programa de blackjack para el RPC-4000 (¿Portable? ¿Qué significa eso?). El nuevo ordenador tenia un sistema de direccionamiento de uno más uno, en donde cada instrucción máquina, aparte del código de operación y de la dirección del operando utilizado, tenía una segunda dirección que indicaba donde estaba la próxima instrucción en el tambor giratorio.
¡Una forma moderna de contarlo sería que cada instrucción estaba seguida de un GOTO! Pon eso en la pipa de Pascal y fúmatelo.
Mel amaba al RPC-4000 porque podría optimizar su código: es decir, localizar las instrucciones en el tambor de modo que cuando una hubiera terminado su trabajo, la próxima estuviera pasando por debajo de la cabeza lectora y, por lo tanto, estuviera disponible para su inmediata ejecución. Había un programa que se usaba para hacer eso, un "optimizador de código de ensamblador", pero Mel se oponía a usarlo.
– Nunca sabes donde va a poner las cosas — explicaba — por lo que deberías utilizar constantes separadas.
Tardé un buen tiempo antes de poder entender esa extraña frase. Como Mel conocía el valor numérico de cada código de operación, y había asignado sus propias direcciones en el tambor, cada instrucción que escribía podía también ser considerada como una constante numérica. Podía tomar una instrucción "add" anterior, por ejemplo, y multiplicar algo con ella, si tenía el valor numérico que necesitaba. Su código no era muy sencillo de modificar por otra persona que digamos.
Comparé los programas optimizados a mano de Mel con el mismo código pasado por el programa de optimización de código de ensamblador, y los de Mel siempre se ejecutaban más rápido. Esto era debido a que el sistema de programación "top-down" no había sido inventado aún, y Mel no lo habría utilizado de todas formas. Escribía las partes más internas de los bucles de su programa primero, para que se pudieran situar en las direcciones optimas del tambor. El optimizador de código ensamblador simplemente no era lo suficientemente listo para hacerlo de ese modo.
Mel nunca escribía bucles de espera, a pesar de que la Flexowriter requería un tiempo de espera entre los caracteres de salida para funcionar correctamente. Simplemente situaba las instrucciones en el tambor de forma que cada una ya hubiera pasado por debajo de cabeza cuando se necesitaba; de forma que el tambor debía realizar otra revolución completa para encontrar la instrucción que acababa de pasar. Acuñó un término inolvidable para este proceso. A pesar de que "óptimo" es un término absoluto, como "único", se convirtió en una costumbre hacerlo relativo: "no del todo óptimo" o "menos óptimo" o "o no muy óptimo". Mel llamaba a las localizaciones con mayor tiempo de espera las "más pésimas".
Después de terminar el programa de blackjack y conseguirlo ejecutar ("Incluso el inicializador está optimizado" dijo orgullosamente), recibió una Petición de Modificación desde el departamento de ventas. El programa utilizaba un elegante (y optimizado) generador de números aleatorios para barajar las "cartas" y repartirlas desde el "montón", y algunos de los vendedores creían que esto era demasiado justo, porque a veces los compradores perdían. Querían que Mel modificara el programa para que, cuando se cambiara un interruptor en el panel, pudieran cambiar la suerte y dejar al comprador ganar.
Mel protestó. Creía que la proposición era sencillamente deshonesta, que lo era, y que chocaba con su integridad personal como programador, lo que pasaba de veras, por lo que se negó a hacerlo. El Director de Ventas habló con Mel, igual que lo hizo el Gran Jefe, y, a petición del jefe, unos cuantos Compañeros Programadores. Mel finalmente se rindió y escribió el código, pero hizo la comprobación al revés, y, cuando el interruptor se pulsaba, el programa hacia trampas, ganando todo el rato. Mel estaba encantado con ello, proclamando que su subconsciente era incontrolablemente ético, y se negó estoicamente a arreglarlo
Después de que Mel dejara la compañía en busca de pa$to$ más verdes, el Gran Jefe me preguntó si podía mirar el código y ver si podía encontrar la comprobación y darle la vuelta. Un poco reticente acepté mirar. Seguir el código de Mel era una verdadera odisea.
A veces creo que programar es un arte, y su valor solo puede ser apreciado por otra persona versada en ese arcano arte; existen gemas maravillosas y brillantes ocultas a la vista y admiración humanas, algunas veces para siempre, por la naturaleza misma del proceso. Puedes aprender un montón sobre alguien sólo leyendo su código, incluso en hexadecimal. Mel era, creo, un genio incomprendido.
Quizá mi mayor conmoción fue cuando encontré un inocente bucle que no contenía ninguna condición. Nada. El sentido común me decía que tenía que ser un bucle cerrado, donde el programa se ejecutaría para siempre, sin fin. Sin embargo el control del programa pasaba a través de él hasta el otro extremo sin problemas. Me llevó dos semanas descubrir lo que sucedía.
El RPC-4000 tenía un dispositivo realmente moderno llamado registro índice. Permitía al programador escribir un bucle que utilizara una instrucción indexada en su interior; cada vez que se pasaba por ese punto el valor en el registro índice era añadido a la dirección del operando de aquella instrucción, por lo que se referiría al próximo dato de una serie. Sólo tenía que incrementar el registro índice cada vez. Mel nunca lo utilizó
En su lugar, él ponía la instrucción en un registro de la máquina, añadia uno a su dirección y la almacenaba de nuevo. Entonces ejecutaba la instrucción modificada, directamente desde el registro. El bucle estaba escrito de forma que este tiempo adicional de ejecución se tenía en cuenta, cuando la instrucción en curso terminaba la próxima estaba justo bajo la cabeza de lectura del tambor, lista para ser ejecutada. Pero el bucle no tenía comprobación.
La pista vital llegó cuando me di cuenta que el bit del registro índice, el bit que estaba entre la dirección y el código de operación en la palabra de la instrucción estaba activo… a pesar de que Mel nunca utilizaba el registro índice, dejándolo a cero todo el tiempo. Cuando la luz brilló, casi me cegó.
Mel había situado los datos en los que trabajaba cerca de la parte alta de la memoria, las direcciones más grandes que las instrucciones podían direccionar por lo que, después de que el último dato hubiera sido utilizado, incrementar la dirección de la instrucción haría que se desbordara. El acarreo añadiría uno al código de operación, cambiándolo a la siguiente instrucción en el juego: una instrucción de salto. Además la próxima instrucción de programa estaba en la dirección cero, y el programa seguiría felizmente su recorrido
No me he mantenido en contacto con Mel, por lo que no se si se rindió a los cambios que los tiempos han introducido en las técnicas de programación desde esos días desaparecidos hace mucho tiempo. Me gusta pensar que no lo hizo. De todas maneras me impresionó tanto aquello que dejé de buscar la comprobación, diciéndole al Gran Jefe que no podía encontrarla. No pareció sorprendido.
Cuando dejé la compañía el programa de blackjack seguía haciendo trampas si activabas el interruptor, y creo que es como debe ser. No me siento a gusto hackeado el código de un Verdadero Programador
Fuente: utastro!nather (Ed Nather), 21 de Mayo de 1983.
La historia de Mel
En un artículo reciente, hablando del lado macho de la programación, se hizo la simple y llana afirmación:
Los Verdaderos Programadores escriben en FORTRAN
Quizá lo hagan ahora, en esta era decadente de cerveza sin alcohol, calculadoras de bolsillo y programas "user-friendly" pero en los Viejos Buenos Tiempos, cuando el término "software" sonaba a broma y los Verdaderos Ordenadores estaban hechos de tambores y tubos de vacío los Verdaderos Programadores escribían en código máquina. No FORTRAN. No RATFOR. Ni siquiera ensamblador. Código máquina. Crudos, sin adornos, inescrutables números hexadecimales. Directamente
Toda una nueva generación de programadores creció en la ignorancia de este glorioso pasado, por lo que me siento obligado a describir, tan bien como me sea posible debido al salto generacional, cómo un Verdadero Programador escribía código.
Le llamaré Mel, porque ese era su nombre.
Conocí a Mel cuando empecé a trabajar para Royal McBee Computer Corp., una extinta subsidiaria de una compañía de maquinas de escribir. La empresa producía el LGP-30, un pequeño y barato (para los estándares de la época) ordenador con memoria de tambor, y empezaba a producir el RPC-4000, un ordenador con memoria de tambor mejorado, más grande y más rápido. Estos ordenadores costaban demasiado, y tampoco duraron mucho de todas formas (es por esto que no habéis oído hablar de la compañía ni del ordenador)
Había sido contratado para escribir un compilador de FORTRAN para esta nuevo portento y Mel fue mi guía a sus maravillas. Mel no soportaba a los compiladores.
– ¿Si un programa no puede rescribir su propio código — preguntó — qué tiene de bueno?
Mel había escrito, en hexadecimal, el programa de ordenador más conocido que la compañía poseía. Corría sobre el LGP-30 y jugaba al blackjack con los compradores potenciales en las exposiciones de ordenadores. Su efecto era increíble. El stand del LGP-30 estaba siempre lleno en cada exposición, y los vendedores de IBM estaban allí de pie sin poder hacer otra cosa que hablar entre ellos. Si aquello servía para vender ordenadores o no era una pregunta que nadie se planteó nunca.
El trabajo de Mel era reescribir el programa de blackjack para el RPC-4000 (¿Portable? ¿Qué significa eso?). El nuevo ordenador tenia un sistema de direccionamiento de uno más uno, en donde cada instrucción máquina, aparte del código de operación y de la dirección del operando utilizado, tenía una segunda dirección que indicaba donde estaba la próxima instrucción en el tambor giratorio.
¡Una forma moderna de contarlo sería que cada instrucción estaba seguida de un GOTO! Pon eso en la pipa de Pascal y fúmatelo.
Mel amaba al RPC-4000 porque podría optimizar su código: es decir, localizar las instrucciones en el tambor de modo que cuando una hubiera terminado su trabajo, la próxima estuviera pasando por debajo de la cabeza lectora y, por lo tanto, estuviera disponible para su inmediata ejecución. Había un programa que se usaba para hacer eso, un "optimizador de código de ensamblador", pero Mel se oponía a usarlo.
– Nunca sabes donde va a poner las cosas — explicaba — por lo que deberías utilizar constantes separadas.
Tardé un buen tiempo antes de poder entender esa extraña frase. Como Mel conocía el valor numérico de cada código de operación, y había asignado sus propias direcciones en el tambor, cada instrucción que escribía podía también ser considerada como una constante numérica. Podía tomar una instrucción "add" anterior, por ejemplo, y multiplicar algo con ella, si tenía el valor numérico que necesitaba. Su código no era muy sencillo de modificar por otra persona que digamos.
Comparé los programas optimizados a mano de Mel con el mismo código pasado por el programa de optimización de código de ensamblador, y los de Mel siempre se ejecutaban más rápido. Esto era debido a que el sistema de programación "top-down" no había sido inventado aún, y Mel no lo habría utilizado de todas formas. Escribía las partes más internas de los bucles de su programa primero, para que se pudieran situar en las direcciones optimas del tambor. El optimizador de código ensamblador simplemente no era lo suficientemente listo para hacerlo de ese modo.
Mel nunca escribía bucles de espera, a pesar de que la Flexowriter requería un tiempo de espera entre los caracteres de salida para funcionar correctamente. Simplemente situaba las instrucciones en el tambor de forma que cada una ya hubiera pasado por debajo de cabeza cuando se necesitaba; de forma que el tambor debía realizar otra revolución completa para encontrar la instrucción que acababa de pasar. Acuñó un término inolvidable para este proceso. A pesar de que "óptimo" es un término absoluto, como "único", se convirtió en una costumbre hacerlo relativo: "no del todo óptimo" o "menos óptimo" o "o no muy óptimo". Mel llamaba a las localizaciones con mayor tiempo de espera las "más pésimas".
Después de terminar el programa de blackjack y conseguirlo ejecutar ("Incluso el inicializador está optimizado" dijo orgullosamente), recibió una Petición de Modificación desde el departamento de ventas. El programa utilizaba un elegante (y optimizado) generador de números aleatorios para barajar las "cartas" y repartirlas desde el "montón", y algunos de los vendedores creían que esto era demasiado justo, porque a veces los compradores perdían. Querían que Mel modificara el programa para que, cuando se cambiara un interruptor en el panel, pudieran cambiar la suerte y dejar al comprador ganar.
Mel protestó. Creía que la proposición era sencillamente deshonesta, que lo era, y que chocaba con su integridad personal como programador, lo que pasaba de veras, por lo que se negó a hacerlo. El Director de Ventas habló con Mel, igual que lo hizo el Gran Jefe, y, a petición del jefe, unos cuantos Compañeros Programadores. Mel finalmente se rindió y escribió el código, pero hizo la comprobación al revés, y, cuando el interruptor se pulsaba, el programa hacia trampas, ganando todo el rato. Mel estaba encantado con ello, proclamando que su subconsciente era incontrolablemente ético, y se negó estoicamente a arreglarlo
Después de que Mel dejara la compañía en busca de pa$to$ más verdes, el Gran Jefe me preguntó si podía mirar el código y ver si podía encontrar la comprobación y darle la vuelta. Un poco reticente acepté mirar. Seguir el código de Mel era una verdadera odisea.
A veces creo que programar es un arte, y su valor solo puede ser apreciado por otra persona versada en ese arcano arte; existen gemas maravillosas y brillantes ocultas a la vista y admiración humanas, algunas veces para siempre, por la naturaleza misma del proceso. Puedes aprender un montón sobre alguien sólo leyendo su código, incluso en hexadecimal. Mel era, creo, un genio incomprendido.
Quizá mi mayor conmoción fue cuando encontré un inocente bucle que no contenía ninguna condición. Nada. El sentido común me decía que tenía que ser un bucle cerrado, donde el programa se ejecutaría para siempre, sin fin. Sin embargo el control del programa pasaba a través de él hasta el otro extremo sin problemas. Me llevó dos semanas descubrir lo que sucedía.
El RPC-4000 tenía un dispositivo realmente moderno llamado registro índice. Permitía al programador escribir un bucle que utilizara una instrucción indexada en su interior; cada vez que se pasaba por ese punto el valor en el registro índice era añadido a la dirección del operando de aquella instrucción, por lo que se referiría al próximo dato de una serie. Sólo tenía que incrementar el registro índice cada vez. Mel nunca lo utilizó
En su lugar, él ponía la instrucción en un registro de la máquina, añadia uno a su dirección y la almacenaba de nuevo. Entonces ejecutaba la instrucción modificada, directamente desde el registro. El bucle estaba escrito de forma que este tiempo adicional de ejecución se tenía en cuenta, cuando la instrucción en curso terminaba la próxima estaba justo bajo la cabeza de lectura del tambor, lista para ser ejecutada. Pero el bucle no tenía comprobación.
La pista vital llegó cuando me di cuenta que el bit del registro índice, el bit que estaba entre la dirección y el código de operación en la palabra de la instrucción estaba activo… a pesar de que Mel nunca utilizaba el registro índice, dejándolo a cero todo el tiempo. Cuando la luz brilló, casi me cegó.
Mel había situado los datos en los que trabajaba cerca de la parte alta de la memoria, las direcciones más grandes que las instrucciones podían direccionar por lo que, después de que el último dato hubiera sido utilizado, incrementar la dirección de la instrucción haría que se desbordara. El acarreo añadiría uno al código de operación, cambiándolo a la siguiente instrucción en el juego: una instrucción de salto. Además la próxima instrucción de programa estaba en la dirección cero, y el programa seguiría felizmente su recorrido
No me he mantenido en contacto con Mel, por lo que no se si se rindió a los cambios que los tiempos han introducido en las técnicas de programación desde esos días desaparecidos hace mucho tiempo. Me gusta pensar que no lo hizo. De todas maneras me impresionó tanto aquello que dejé de buscar la comprobación, diciéndole al Gran Jefe que no podía encontrarla. No pareció sorprendido.
Cuando dejé la compañía el programa de blackjack seguía haciendo trampas si activabas el interruptor, y creo que es como debe ser. No me siento a gusto hackeado el código de un Verdadero Programador
 |
| Mel está de pie a la derecha |
lunes, 21 de octubre de 2013
Magia circular
Los números complejos siempre me han parecido maravillosos. Descubro nuevas propiedades una y otra vez. La que traigo hoy es simple y misteriosa.
Supongamos que tengo una circunferencia [$C$] formada por los elementos [$z\in C$]. Entonces si hago la inversa de sus elementos, el conjunto que obtengo [$C'=\{1/z\mid z\in C\}$] es también una circunferencia.
La demostración se me ha resistido un poco, pero una vez descubierta, es hasta sencilla. Sea [$c$] el centro del círculo y [$R\ge 0$] su radio.[$$|z-c|=R$$][$$|z-c|^2=R^2$$] [$$(z-c)(z-c)^*=R^2$$][$$zz^*-cz^*-c^*z+cc^*=R^2$$]Ahora hago [$w=1/z$] por lo que llego a [$$\frac{1}{w} \frac{1}{w^*}-c \frac{1}{w^*} -c^* \frac{1}{w} +cc^*=R^2$$] Si asumo que [$w\ne 0$], es decir, [$z<\infty$], llego a [$$1-c w -c^*w^* +cc^*ww^*=R^2ww^*$$]Reordenando un poco [$$1-c w -c^*w^* +(cc^*- R^2 )ww^*=0$$] Y si asumo que [$cc^*\ne R^2$] (es decir [$|c|\ne R$]) llego hasta [$$ww^*-\frac{c w}{cc^*- R^2}-\frac{c^*w^*}{ (cc^*- R^2)^2 } + \frac{1}{ cc^*- R^2 } =0$$] [$$\left(w-\frac{c^*}{cc^*- R^2}\right) \left(w-\frac{c^*}{cc^*- R^2}\right)^*-\frac{cc^*}{ (cc^*- R^2)^2 } + \frac{1}{ cc^*- R^2 } =0$$] [$$\left(w-\frac{c^*}{cc^*- R^2}\right) \left(w-\frac{c^*}{cc^*- R^2}\right)^* = \frac{R^2}{(cc^*- R^2)^2 }$$] ¡Y ya lo tenemos! [$$\left|w-\frac{c^*}{cc^*- R^2}\right|^2 = \frac{R^2}{ (cc^*- R^2)^2 }$$] [$$\left|w-\frac{c^*}{cc^*- R^2}\right| = \frac{R}{ cc^*- R^2 }$$]
La nueva circunferencia tiene de centro [$ \frac{c^*}{cc^*- R^2}$] y de radio [$ \frac{R}{ cc^*- R^2 } $].
Para los curiosos, las hipótesis de que [$z<\infty$] y que [$|c|\ne R$] aparecen porque estamos restringiéndonos a circunferencias. Si no las tomamos, llegamos a que circunferencias o rectas se transforman en circunferencias o rectas. Las rectas pueden ser vistas comocircunferencias con el centro en el infinito y por tanto se dice que transformamos circunferencias generalizadas en circunferencias generalizadas.
La mejor forma de ver esto es mediante la esfera de Riemann, pero ya lo dejamos para otro día.
Supongamos que tengo una circunferencia [$C$] formada por los elementos [$z\in C$]. Entonces si hago la inversa de sus elementos, el conjunto que obtengo [$C'=\{1/z\mid z\in C\}$] es también una circunferencia.
La demostración se me ha resistido un poco, pero una vez descubierta, es hasta sencilla. Sea [$c$] el centro del círculo y [$R\ge 0$] su radio.[$$|z-c|=R$$][$$|z-c|^2=R^2$$] [$$(z-c)(z-c)^*=R^2$$][$$zz^*-cz^*-c^*z+cc^*=R^2$$]Ahora hago [$w=1/z$] por lo que llego a [$$\frac{1}{w} \frac{1}{w^*}-c \frac{1}{w^*} -c^* \frac{1}{w} +cc^*=R^2$$] Si asumo que [$w\ne 0$], es decir, [$z<\infty$], llego a [$$1-c w -c^*w^* +cc^*ww^*=R^2ww^*$$]Reordenando un poco [$$1-c w -c^*w^* +(cc^*- R^2 )ww^*=0$$] Y si asumo que [$cc^*\ne R^2$] (es decir [$|c|\ne R$]) llego hasta [$$ww^*-\frac{c w}{cc^*- R^2}-\frac{c^*w^*}{ (cc^*- R^2)^2 } + \frac{1}{ cc^*- R^2 } =0$$] [$$\left(w-\frac{c^*}{cc^*- R^2}\right) \left(w-\frac{c^*}{cc^*- R^2}\right)^*-\frac{cc^*}{ (cc^*- R^2)^2 } + \frac{1}{ cc^*- R^2 } =0$$] [$$\left(w-\frac{c^*}{cc^*- R^2}\right) \left(w-\frac{c^*}{cc^*- R^2}\right)^* = \frac{R^2}{(cc^*- R^2)^2 }$$] ¡Y ya lo tenemos! [$$\left|w-\frac{c^*}{cc^*- R^2}\right|^2 = \frac{R^2}{ (cc^*- R^2)^2 }$$] [$$\left|w-\frac{c^*}{cc^*- R^2}\right| = \frac{R}{ cc^*- R^2 }$$]
La nueva circunferencia tiene de centro [$ \frac{c^*}{cc^*- R^2}$] y de radio [$ \frac{R}{ cc^*- R^2 } $].
Para los curiosos, las hipótesis de que [$z<\infty$] y que [$|c|\ne R$] aparecen porque estamos restringiéndonos a circunferencias. Si no las tomamos, llegamos a que circunferencias o rectas se transforman en circunferencias o rectas. Las rectas pueden ser vistas comocircunferencias con el centro en el infinito y por tanto se dice que transformamos circunferencias generalizadas en circunferencias generalizadas.
La mejor forma de ver esto es mediante la esfera de Riemann, pero ya lo dejamos para otro día.
sábado, 24 de agosto de 2013
¿Qué es eso de la programación asíncrona?
Llamadas síncronas
Gran parte del tiempo de las operaciones que realiza un programa en su ejecución se pierde esperando. Esperando que los datos lleguen del disco. Esperando que el usuario pulse una tecla. Esperando que el paquete se mande por red. Esperando, esperando y esperando.La solución clásica a este problema es proporcionarle ese tiempo de espera a otro proceso de manera que se aproveche el uso de CPU. Nuestro proceso se bloquea mientras espera (y si va a esperar mucho incluso se quita de memoria y guarda en disco) y otro toma su lugar. Cuando llega la señal de que la espera ha terminado (y se queda la CPU libre) nuestro proceso se reanuda.
Existen diversas políticas de reparto del tiempo de CPU entre los distintos procesos para que este reparto sea lo más útil posible. Por ejemplo, primando al proceso con el que el usuario está trabajando.
Ahora bien. Desde el punto de vista del programa, ¿qué significa este sistema? Significa que cuando la llamada a una función que realiza una operación termina, la operación se ha completado y que, implícitamente, nuestro programa ha estado esperado a que terminase.
Debido a que la terminación de la operación y la reanudación del programa ocurren a la vez, se dice que estamos realizando llamadas síncronas.
f=leer_fichero() //Hasta que no se lee el fichero no llegamos aquí t=leer_teclado() //Hasta que no se lee el teclado no llegamos aquí buscar(f,t) //Resto del programa
Llamadas asíncronas
La alternativa es no esperar, ser asíncronos. Debido a que no esperamos ocurren dos cosas:- No bloqueamos la ejecución de nuestro programa. Por esta razón a las llamadas asíncronas también se les dice no bloqueantes y a las síncronas, bloqueantes.
- La llamada retorna antes de que se complete la operación y, por tanto, no puede devolver el resultado.
- Pipes: conectar de alguna manera la operación con otra antes de solicitar su realización.
- Polling: preguntar cada cierto tiempo a ver si se ha completado la operación. No suele ser buena idea ya que perdemos tiempo en preguntar.
- Interrupción: esperar a una señal y que nuestro programa o el sistema ejecute, en el momento que se recibe la señal, un código en respuesta a la misma. Es importante ver aquí que este código está desligado del punto en el que se solicitó la operación mediante la llamada asíncrona.
- Eventos/mensajes: es una mejora sobre polling. Cuando termina la operación se envía un mensaje que se encola. El programa no pregunta si una operación en concreto se ha completado. Sólo comprueba si ha llegado algún mensaje. Esto le indica que una operación de las muchas en curso se ha completado. Cada mensaje tiene un indicador de la operación completada y deberá ser respondido correspondientemente, de forma similar a como se hacía con las interrupciones.
- Hebras o fibras: nos rendimos. Usamos llamadas síncronas, pero en vez de que bloqueen mi programa, doy opciones de por dónde se puede continuar la ejecución. En el caso de las hebras es el sistema operativo el que decide cómo planificar la ejecución, en el caso de la fibra es mi propio programa el que lo hace.
- Sincronizar (p.ej. por futuros/promesa): nos rendimos definitivamente. Seguimos ejecutando como si nada mientras no necesitemos el resultado. En el momento que necesitemos el resultado, esperamos hasta tenerlo.
- Retrollamadas: como interrupción, pero indico qué código hay que ejecutar en el momento de realizar la llamada asíncrona. Esto tiene el efecto de bifurcar el flujo de control y analizaremos esto en lo que resta de artículo.
Por otro lado, tanto sincronizar como las hebras/fibras es rendirse y esperar.
Retrollamadas
Lo que realmente está en auge son las retrollamadas (callbacks), sobre todo desde que C# incluyera soporte en el lenguaje para la programación asíncrona. Pero vayamos por partes. ¿Qué es esto de una retrollamada?f=leer_fichero() t=leer_teclado() buscar(f,t) //Resto del programa
Con retrollamadas, en vez de esperar el resultado de las funciones, indico a estas funciones qué tienen que hacer cuando terminen.
leer_fichero_asincrono(usa_fichero) leer_teclado_asincrono(usa_teclado) //Resto del programa
Así, en el caso de leer_fichero_asincrono() lo que hago es decirle que, cuando termine de leer el fichero llame a la función usa_fichero(). Igualmente, con leer_teclado_asincrono(). Estas funciones usa_fichero() y usa_teclado() que se ejecutan cuando se completa la operación son las retrollamadas.
Acabadas las presentaciones, lo importante aquí es que la función leer_fichero_asincrono() no espera y la ejecución continúa. Se ejecuta leer_teclado_asincrono() y tampoco espera, seguimos ejecutando lo que haya que ejecutar despues y, mientras, se lee del fichero y del teclado a la vez.
¿Y dónde está la función buscar() que es donde realmente hacemos algo con lo leído? Bueno, no podemos llamarla hasta que estemos seguros de que tanto el fichero como el teclado se han leído. Esa es la responsabilidad de usa_fichero() y usa_teclado() que deben guardar los datos, comprobar que están ambos y, si es así, llamar la función buscar() con ellos.
var f, t string;
func usa_fichero(rf) { f = rf; if t!="" {buscar(f,t)} }
func usa_teclado(rt) { t = rt; if f!="" {buscar(f,t)} }
//Resto del programaPara eso guardamos los datos recibidos en dos variables visibles por ambas retrollamadas y cuando se comprueba que ambas cadenas se han leído, llama a buscar().
Funciones anónimas
El ejemplo anterior es algo engorroso ya que hay que definir una función por cada retrollamada que se quiera usar. Este hecho ha sido determinante para que no se usaran mucho las retrollamadas. Por fortuna, los lenguajes de programación van evolucionando y se han ido adaptando ideas que venían de lenguajes menos conocidos y académicos. Una de esas ideas son las funciones anónimas y sus clausuras léxicas.Con funciones anónimas el código del ejemplo anterior se reduce lo suficiente como para que sea atractivo su uso.
var f, t string;
leer_fichero_asincrono(rf => { f = rf; if t!="" {buscar(f,t) } )
leer_teclado_asincrono(rt => { t = rt; if f!="" {buscar(f,t) } )
//Resto del programaAunque no hemos solucionado el detalle de que la función buscar() aparece escrita dos veces aunque sólo se llamará una. En este ejemplo es una pequeña tontería, pero en ejemplos mayores el grado de verbosidad aumenta y se dificulta el mantenimiento del programa.
Quiero resaltar aquí que una función asíncrona bifurca el flujo de control ya que van a ocurrir dos cosas a la vez: la operación que haga la función (se hará la retrollamada cuando se complete) y el resto del programa (ya que la función retorna inmediatamente). De manera que si escribo algo como esto:
asincrona( x => parte1(x) ) parte2()
La parte 1 y la parte 2 se ejecutan, a la vez o en momentos distintos, pero no en secuencia. Es más, una vez que la parte 1 se haya completado, ese flujo de control bifurcado muere sin hacer nada más. La parte 2 que es el resto del programa seguirá su ejecución hasta que muera cuando el proceso acabe.
Composición de retrollamadas
En el ejemplo anterior se hacían a la vez tres cosas:- La lectura del fichero
- La lectura del teclado
- La ejecución del resto del programa
var f, t string;
leer_fichero_asincrono(f => { leer_teclado_asincrono(t => buscar(f,t)) })
//Resto del programaEn este caso lo que tenemos es una composición en serie (o secuencia) de las operaciones. Se hacen a la vez dos cosas:
- La lectura del fichero y luego la del teclado
- La ejecución del resto del programa
La solución del café helado
La manera más simple que he visto de resolver estos defectos es la que usa el lenguaje Iced Coffee Script. Básicamente introduce dos nuevas palabras clave await y defer. La palabra clave await marca el resto del código como una función anónima (que llamaré función anónima restante) y la palabra clave defer indica el punto donde introducir esa función anónima como retrollamada.Empezaremos por un ejemplo más simple que sólo lee del teclado e imprime por pantalla. No sigo la sintaxis de Iced Coffee Script, sólo las ideas.
await leer_teclado_asincrono(defer(t)) imprime(t);
La palabra clave await toma el resto del código (que en este caso sólo es imprime(t)) y crea una función anónima con él. Esta función anónima sería algo como t => imprime(t). Luego, sustituye en los defer esa función anónima. El resultado de esta traducción sintáctica (como si fuera una macro) es
leer_teclado_asincrono( t => imprime(t) )
Verdaderamente, hemos hecho el código más largo, pero hemos sacado la retrollamada del argumento de la función asíncrona y por tanto no estamos anidando estructuras sintácticas una dentro de otra. Si tuvieramos que componer secuencialmente varias llamadas es inmediato.
await leer_teclado_asincrono(defer(t)) await leer_fichero_asincrono(defer(f)) await leer_datos_asincrono(defer(d)) imprime(t,f,d)
Mientras que con retrollamadas sería un pequeño lío.
leer_teclado_asincrono(t => {
leer_fichero_asincrono(f => {
leer_datos_asincrono(d => {
imprime(t,f,d)
})
})
})Adicionalmente, el uso de la palabra clave defer permite la composición en paralelo.
await {
leer_teclado_asincrono(defer(t))
leer_fichero_asincrono(defer(f))
leer_datos_asincrono(defer(d))
}
imprime(t,f,d)Recordemos que al llamar a cualquiera de las tres funciones asíncronas, el programa no se detiene. Sólo espera (justo lo que significa await) cuando llega al final de bloque } y una vez se hayan completado las operaciones, se sigue con imprime().
Traducir esto a retrollamadas es bastante más complicado ya que necesitaríamos variables auxiliares y triplicar el código de llamada a imprime() o usar otra función auxiliar.
Continuaciones
El uso de await nos ha ocultado uno de los dos flujos de datos. Es fácil de recuperar si envolvemos todo en una función.funcion lee_e_imprime_asincrono(){
await leer_teclado_asincrono(defer(t))
imprime(t)
}
lee_e_imprime_asincrono()
//Resto del códigoDebo recordar aquí la versión traducida de lee_e_imprime _asincrono () que es
funcion lee_e_imprime_asincrono(){
leer_teclado_asincrono( t => imprime(t) )
}Lo hago para dejar claro que esta función es una función que retorna inmediatamente ya que llama a leer_teclado_asincrono() que hemos dicho que no esperaba a que se completase la lectura, sino que retornaba inmediatamente. Por eso la hemos nombrado con _asincrono al final.
Como retorna inmediatamente, se ejecuta el resto del código a la vez que se lee el teclado y se llama a imprime(). De nuevo, tenemos los dos flujos de control.
Ahora bien, si la función que acabo de crear es asíncrona... ¿por qué no acepta una retrollamada? La respuesta es que ¡debería hacerlo! Si no lo hace, desde el punto de uso sólo tenemos acceso a uno de los dos flujos de control.
lee_e_imprime_asincrono() //Falta acceso al flujo que pasa por imprime() //Resto del código (obviamente tenemos acceso a este flujo desde aquí)
De hecho, esa retrollamada que deberíamos aceptar sería lo que hay que hacer una vez hayamos terminado con la lectura del teclado y sus retrollamadas asociadas (en este caso sólo es llamar a imprime()). Es decir, el acceso que nos falta al otro flujo de control.
funcion lee_e_imprime_asincrono(k funcion){
await leer_teclado_asincrono(defer(t))
imprime(t)
k() //Continua ejecutando k
}Ahora sí podemos componer por el otro flujo de control.
lee_e_imprime_asincrono(()=>imprime("hecho"))
//Resto del códigoEste estilo de llamar a las funciones, donde manipulamos el flujo de control pasando funciones que deben ejecutarse una vez acabada las tareas que realice la función que llamamos, es el estilo de paso de continuaciones.
La alternativa C#
El problema del estilo de paso de continuaciones es que una función tiene una signatura distinta si es síncrona o asíncrona.funcion_sincrona(x,y,z)
funcion_asincrona(x,y,z, continuacion)
Además, nos obliga a que la continuación se conozca por anticipado. No podemos cambiarla. No podemos controlar la operación. Una vez que llamamos a la función asíncrona, perdemos el control.
Una manera de solucionarlo es, en vez de pasar la continuación, reificar la operación asíncrona y devolver un objeto que la represente. Este objeto acepta la continuación y una serie de operaciones que controlan la operación que se está realizando asíncronamente.
En C# ese objeto es de la clase Task. Esta clase permite definir la continuación con los métodos ContinueWith. Además, controla la operación que realiza la función que creó este objeto por ejemplo, esperando síncronamente, retardando, etc.
El ejemplo anterior (con la sintaxis que hemos seguido hasta ahora) usando esta idea sería:
funcion lee_e_imprime_asincrono(){
await leer_teclado_asincrono(defer(t))
imprime(t)
}
lee_e_imprime_asincrono().establece_continuacion(()=>imprime("hecho") )
//Resto del códigoComo todo tiene su lado negativo, esta técnica dificulta la composición en paralelo. Hay que usar métodos explícitos y no se podrían poner varios defer (de hecho, C# ni siquiera usa defer). Es decir, se tiene que gestionar a mano la composición en paralelo de los objetos asíncronos.
Notas finales
Quedan algunos detalles que no voy a discutir. Este artículo se está alargando más de la cuenta. Por ejemplo, ¿cómo se llaman a las retrollamadas? ¿Quién lo hace? ¿Es el sistema operativo? ¿El propio programa?
Es más, ¿tenemos problemas de carreras con las retrollamadas? ¿Tengo que sincronizar el acceso?
Todo esto depende de la plataforma, pero en general se intenta que la retrollamada se realice desde la misma hebra y en ciertos puntos controlados para que no haya este tipo de problemas.
Otro tema que ha quedado en el aire es la definición formal de transformación de las palabras clave await/defer en otra función que usa clausuras. Realmente, sólo se usa una clausura y una máquina de estados. Esto es así porque un bloque await puede aparecer dentro de un bucle. En este caso lo que hay después del await vuelve delante con el bucle. ¿Cuál debe ser entonces la clausura?
También hemos dejado de lado ver qué ocurre con las excepciones o cancelaciones de una llamada asíncrona.
Quizás tratemos estos temas en otro post más adelante.
sábado, 17 de agosto de 2013
miniSL parte 21 - Lectura de números
Como ya adelanté en la entrada anterior, hoy vamos a ver cómo leer números. La función responsable de esto es ReadNumber().
Lo primero es leer un número hasta donde podamos leer. Iremos metiendo lo leído en la cadena s.
Si hemos llegado hasta una “x” o “X”, probablemente sea un número hexadecimal. Comprobaremos que empiece por “0x” o “0X” y pasamos a incorporar los dígitos hexadecimales en la variable s.
Ahora tenemos el número leído y, si no ha habido error, vamos a convertirlo en un valor. Para eso vamos a usar la función wcstoul() que detecta automáticamente si el número empieza por “0x” o es decimal.
La función wcstoul() devuelve en la variable e el puntero al primer carácter que no formaría parte del número. Este puntero deberá dirigirse al final de la cadena y si no es así, ha ocurrido algo raro.
Por otra parte, si todo va bien, usamos CreateInteger() para generar la celda con el entero correspondiente.
En la próxima parte de esta serie del lenguaje MiniSL vamos a ver cómo analizar sintácticamente las expresiones primarias. Estas expresiones son las que no están formadas por otras expresiones por lo que no hay ambigüedad posible en su análisis.
CELL& Script::ReadNumber(ISTREAM& i)
{
Lo primero es leer un número hasta donde podamos leer. Iremos metiendo lo leído en la cadena s.
STRING s; while(unsigned(i.peek())<256 && isdigit(i.peek()) && i.good()) s+=i.get();
Si hemos llegado hasta una “x” o “X”, probablemente sea un número hexadecimal. Comprobaremos que empiece por “0x” o “0X” y pasamos a incorporar los dígitos hexadecimales en la variable s.
if(i.peek()=='x' || i.peek()=='X')
{
if(s.compare(L"0")!=0) throw L"Hexadecimal numbers must begin with 0x";
s+=i.get();
while(unsigned(i.peek())<256 && isxdigit(i.peek()) && i.good())
s+=i.get();
}
Ahora tenemos el número leído y, si no ha habido error, vamos a convertirlo en un valor. Para eso vamos a usar la función wcstoul() que detecta automáticamente si el número empieza por “0x” o es decimal.
if(i.bad()) throw L"Error while reading a number"; wchar_t* e; int value=wcstoul(s.c_str(), &e, 0);
La función wcstoul() devuelve en la variable e el puntero al primer carácter que no formaría parte del número. Este puntero deberá dirigirse al final de la cadena y si no es así, ha ocurrido algo raro.
if(e!=s.c_str()+s.size()) throw L"Invalid number";
Por otra parte, si todo va bien, usamos CreateInteger() para generar la celda con el entero correspondiente.
return CreateInteger(value); }La función CreateInteger() es muy simple. Crea una celda de tipo INT_LIT usando la función CreateCell() y le asigna el valor designado para el entero.
CELL& CreateInteger(int val)
{
CELL& c=CreateCell(INT_LIT);
c.int_val=val;
return c;
}
En la próxima parte de esta serie del lenguaje MiniSL vamos a ver cómo analizar sintácticamente las expresiones primarias. Estas expresiones son las que no están formadas por otras expresiones por lo que no hay ambigüedad posible en su análisis.
jueves, 27 de junio de 2013
miniSL parte 20 - Lectura de nombres y símbolos
En esta entrada vamos a describir cómo se analizan los tokens de nombres y símbolos. Los nombres son muy simples en su composición. Son caracteres alfanuméricos o un subrayado (guión bajo). Sólo llamaremos a ReadName() cuando el primer carácter sea alfabético, por lo que no haremos esta comprobación otra vez.
La lectura de símbolos es algo más delicada. En definitiva, toda secuencia de caracteres simbólicos va a ser un símbolo; excepto cuando hay un igual. De esa manera podremos analizar cosas como “a=-3” de la manera correcta “a = -3”.
Aquí es donde comprobamos el igual. Como queremos heredar de C/C++ el símbolo “==” para la igualdad, hemos de asegurarnos que no se rompa este doble igual.
Internamente, un símbolo es un nombre así que usamos CreateName().
Finalmente, para que funcione el algoritmo de playa de agujas, hemos de establecer la precedencia y asociatividad de cada símbolo. Esto lo hace la siguiente función que asume que los símbolos serán similares a los del C/C++.
Los símbolos que acaban en “=” como “+=” o “%=” son asignaciones (prioridad 11 muy baja) o relacionales (mayor igual o menor igual, prioridad 40).
Como comentamos antes, el caso de los relacionales es algo especial ya que tenemos que distinguir “<<” (desplazamiento) de “<=” (relacional) y de “<<=” (asignación).
Los símbolos que empiezan por “&” también tienen un tratamiento especial ya que debemos distinguir “&&” (lógico) de “&” (operación de bits) y “&=” (asignación).
Los que empiezan por “|” son similares a los que empiezan con “&”, pero con una prioridad algo menor.
Finalmente, los símbolos “!=”, “==”, “~=” y “?=” vamos a tratarlos como relacionales con prioridad 50. El “=” es asignación y tendrá prioridad 11. Finalmente, si no acaba en “=”, será operación con prioridad 54.
Si no conocemos el símbolo, error.
En la próxima entrada veremos la lectura de números. Es algo más compleja porque vamos a leer números enteros en base decimal o hexadecimal, pero veremos algunos trucos para simplificar el código.
Script::TOKEN Script::ReadName(ISTREAM& i)
{
STRING s;
while(unsigned(i.peek())<256 && (isalnum(i.peek()) || i.peek()=='_') && i.good())
s+=i.get();
if(i.bad()) throw L"Error while reading an identifier or a keyword";
return TOKEN(T_NAME, &CreateName(s));
}
La lectura de símbolos es algo más delicada. En definitiva, toda secuencia de caracteres simbólicos va a ser un símbolo; excepto cuando hay un igual. De esa manera podremos analizar cosas como “a=-3” de la manera correcta “a = -3”.
CELL& Script::ReadSymbol(ISTREAM& i)
{
STRING s;
while(CELL::IsSymbol(i.peek()) && i.good())
{
s+=i.get();
Aquí es donde comprobamos el igual. Como queremos heredar de C/C++ el símbolo “==” para la igualdad, hemos de asegurarnos que no se rompa este doble igual.
if(i.peek()!='=' && *(s.end()-1)=='=') break; }
Internamente, un símbolo es un nombre así que usamos CreateName().
return CreateName(s); }
Finalmente, para que funcione el algoritmo de playa de agujas, hemos de establecer la precedencia y asociatividad de cada símbolo. Esto lo hace la siguiente función que asume que los símbolos serán similares a los del C/C++.
int Script::SymbolPrecedenceAndAssoc(STRING const& s)
{
Los símbolos que acaban en “=” como “+=” o “%=” son asignaciones (prioridad 11 muy baja) o relacionales (mayor igual o menor igual, prioridad 40).
bool assign_end= s.at(s.size()-1)=='=';
switch(s.at(0))
{
case '*': case '/': case '%': return assign_end ? 11 : 100;
case '+': case '-': return assign_end ? 11 : 90;
Como comentamos antes, el caso de los relacionales es algo especial ya que tenemos que distinguir “<<” (desplazamiento) de “<=” (relacional) y de “<<=” (asignación).
case '>': case '<': if(s.size()>1 && s.at(0)==s.at(1)) return assign_end ? 11 : 80; else return 40;
Los símbolos que empiezan por “&” también tienen un tratamiento especial ya que debemos distinguir “&&” (lógico) de “&” (operación de bits) y “&=” (asignación).
case '&': if(s.size()>1 && s.at(0)==s.at(1)) return assign_end? 11 : 30 ; else return assign_end? 11 : 70 ;
Los que empiezan por “|” son similares a los que empiezan con “&”, pero con una prioridad algo menor.
case '|': case '^': if(s.size()>1 && s.at(0)==s.at(1)) return assign_end? 11 : 20; else return assign_end? 11 : 60;
Finalmente, los símbolos “!=”, “==”, “~=” y “?=” vamos a tratarlos como relacionales con prioridad 50. El “=” es asignación y tendrá prioridad 11. Finalmente, si no acaba en “=”, será operación con prioridad 54.
case '!': case '=': case '~': case '?': if(assign_end) return s.size()==1 ? 11 : 50; else return 54;
Si no conocemos el símbolo, error.
default: throw L"Unknown symbol"; } }
En la próxima entrada veremos la lectura de números. Es algo más compleja porque vamos a leer números enteros en base decimal o hexadecimal, pero veremos algunos trucos para simplificar el código.
domingo, 19 de mayo de 2013
Álgebras y coálgebras
He encontrado varias veces por Internet la pregunta de qué es un coálgebra y las respuestas han sido más o menos liosas. El motivo es que en computación al hablar de (co)álgebras nos referimos a las F-(co)álgebras. Lo que implica explicar qué es la F y esa F es un funtor. Un funtor es una operación en categorías y hay que introducir parte de la teoría de categorías para explicarlo.
Puede hacerse más simple.
Antes de acabar este apartado sólo resta destacar un caso particular. El del producto cartesiano de cero conjuntos. Llamaremos a este conjunto [$1$] y sólo contiene un elemento que es la tupla vacía [$()$].
Esta definición no debe ser extraña si seguimos la siguiente secuencia. [$$(A\times B \times C) = \{ (a,b,c) \mid a\in A, b\in B, c\in C \}$$][$$(A\times B) = \{ (a,b) \mid a\in A, b\in B \}$$][$$(A) = \{ (a) \mid a\in A \}$$][$$1 = \{ () \}$$]
Teniendo en mente estas funciones, decimos que el tipo lista de enteros [int] no es más que el conjunto de sus valores (que llamaré [$A_{[int]}$]) y las dos funciones que los construyen por inducción. [$$(A_{[int]}, nil : 1\to[int] , cons : (int \times [int]) \to [int] )$$]Muy similar a, por ejemplo, un monoide [$$(M,e:1 \to M ,\otimes:(M\times M)\to M )$$] donde [$M$] son los elementos del monoide, [$e$] el elemento neutro y [$\otimes$] la operación interna. O a la definición de los números naturales[$$(N,cero:1\to N, suc:N \to N)$$] donde [$cero$] es la constante cero y [$suc$] la operación que obtiene el siguiente número natural (el sucesor).
Generalizando de nuevo, vemos que todas estas definiciones tienen siempre la misma estructura.[$$(A, f_1: X_1 \to A,\dots, f_n: X_n \to A)$$]Donde los [$X_i$] son productos cartesianos de conjuntos en los cuales puede estar el propio [$A$] o no.
Bien. Eso es un álgebra. Un conjunto y varias operaciones cuyo codominio es tal conjunto.
¿Qué significado tiene esto?
Pensemos en una lista. La operación cons tomaba una lista y un elemento e introducía ese elemento en la lista.
cons(7,[1,2,3])=[7,1,2,3]
cons(9,[8,1,3])=[9,8,1,3]
cons(4,[])=[4]
El tipo de cons era [$(int\times [int])\to [int]$]. En una coálgebra la operación correspondiente (que llamaremos headtail) deberá tener el tipo [$[int]\to(int\times [int])$] lo que significa que de una lista obtenemos un elemento y otra lista. Una forma de ver esto es pensar que, en la coálgebra, la operación headtail extrae un elemento de la lista. En general, las operaciones de una coálgebra deshacen lo que los constructores hacían en las álgebras. Por esta razón a las operaciones de una coálgebra se las denomina destructores.
headtail([1,2,3])=(1,[2,3])
headtail ([8,1,3])=(8,[1,3])
headtail ([])=????
¿Qué pasó en este último ejemplo? ¿Es realmente headtail una función sobre las listas o sólo sobre las listas no vacías?
Existen dos respuestas aquí.
La primera respuesta es introducir los tipos suma. De esa manera, headtail podría devolver un error sumando el conjunto unidad al tipo de su codominio ([$headtail: [int]\to 1+(int\times [int])$]). Esto es dual a la agrupación de todas las operaciones del álgebra de la lista en una única operación sumando sus dominios ([$nilcons: 1+(int\times [int])\to [int]$]) y por esta vía definimos el funtor polinómico [$F X = 1+(X\times [X])$] y llegamos a las F-(co)álgebras que es de lo que realmente estamos hablando.
Aún introduciendo la posibilidad de que headtail acabe de leer una lista, no significa que lo haga. Usar coinducción permite trabajar con listas infinitas en las cuales siempre podemos ir extrayendo elementos. Esto nos lleva a...
La segunda respuesta es modificar nuestro tipo de datos y decir que no trabajamos con listas, sino con listas infinitas (los llamados streams). Como la lista es infinita, nunca va a estar vacía y siempre podremos usar headtail. Estos tipos de datos infinitos definidos por coálgebras y coinducción se denominan codatos. Son útiles para modelar, por ejemplo, la entrada del usuario que, en principio, nunca acaba.
Puede hacerse más simple.
El producto cartesiano generalizado
Estrictamente hablando el producto cartesiano es una operación entre dos conjuntos.[$$A\times B$$]El resultado es otro conjunto y sus elementos son los pares ordenados de forma que el primer elemento se obtenga del primer conjunto y el segundo elemento del segundo. En notación matemática:[$$A\times B = \{ (a,b) \mid a\in A, b\in B \}$$] Cuando hacemos dos productos cartesianos, surge la duda de si es asociativo o no.[$$A\times (B \times C) \overset{?}{=} (A\times B)\times C$$] En general el producto cartesiano no es asociativo, ya que [$(a,(b,c))\ne((a,b),c)$], pero nada impide usar un producto cartesiano generalizado (que escribiré entre paréntesis) en el cual el producto de tres conjuntos no sean pares, sino triplas. [$$(A\times B \times C) = \{ (a,b,c) \mid a\in A, b\in B, c\in C \}$$] El de cuatro conjuntos serían cuadruplas y el de [$n$] conjuntos lo que llamaremos [$n$]-tuplas. [$$(A_1\times\cdots\times A_n) = \{(a_1,\dots,a_n) \mid a_1\in A_1,\dots,a_n\in A_n \}$$] Usaremos este producto cartesiano generalizado.Antes de acabar este apartado sólo resta destacar un caso particular. El del producto cartesiano de cero conjuntos. Llamaremos a este conjunto [$1$] y sólo contiene un elemento que es la tupla vacía [$()$].
Esta definición no debe ser extraña si seguimos la siguiente secuencia. [$$(A\times B \times C) = \{ (a,b,c) \mid a\in A, b\in B, c\in C \}$$][$$(A\times B) = \{ (a,b) \mid a\in A, b\in B \}$$][$$(A) = \{ (a) \mid a\in A \}$$][$$1 = \{ () \}$$]
Algebras
La idea de usar álgebras proviene de tomar un tipo de datos como sus valores y las operaciones que los construyen por inducción. Por ejemplo, en el caso de una lista, estos constructores serían.- La lista vacía. Lo que se ha venido a llamar la constante nil.
- Añadir un elemento a la lista. Función que se llama cons.
Teniendo en mente estas funciones, decimos que el tipo lista de enteros [int] no es más que el conjunto de sus valores (que llamaré [$A_{[int]}$]) y las dos funciones que los construyen por inducción. [$$(A_{[int]}, nil : 1\to[int] , cons : (int \times [int]) \to [int] )$$]Muy similar a, por ejemplo, un monoide [$$(M,e:1 \to M ,\otimes:(M\times M)\to M )$$] donde [$M$] son los elementos del monoide, [$e$] el elemento neutro y [$\otimes$] la operación interna. O a la definición de los números naturales[$$(N,cero:1\to N, suc:N \to N)$$] donde [$cero$] es la constante cero y [$suc$] la operación que obtiene el siguiente número natural (el sucesor).
Generalizando de nuevo, vemos que todas estas definiciones tienen siempre la misma estructura.[$$(A, f_1: X_1 \to A,\dots, f_n: X_n \to A)$$]Donde los [$X_i$] son productos cartesianos de conjuntos en los cuales puede estar el propio [$A$] o no.
Bien. Eso es un álgebra. Un conjunto y varias operaciones cuyo codominio es tal conjunto.
Coálgebras
En un coálgebra lo que tenemos es [$$(A, f_1: A\to X_1,\dots, f_n: A\to X_n)$$] En este caso las operaciones tienen el conjunto en su dominio.¿Qué significado tiene esto?
Pensemos en una lista. La operación cons tomaba una lista y un elemento e introducía ese elemento en la lista.
cons(7,[1,2,3])=[7,1,2,3]
cons(9,[8,1,3])=[9,8,1,3]
cons(4,[])=[4]
El tipo de cons era [$(int\times [int])\to [int]$]. En una coálgebra la operación correspondiente (que llamaremos headtail) deberá tener el tipo [$[int]\to(int\times [int])$] lo que significa que de una lista obtenemos un elemento y otra lista. Una forma de ver esto es pensar que, en la coálgebra, la operación headtail extrae un elemento de la lista. En general, las operaciones de una coálgebra deshacen lo que los constructores hacían en las álgebras. Por esta razón a las operaciones de una coálgebra se las denomina destructores.
headtail([1,2,3])=(1,[2,3])
headtail ([8,1,3])=(8,[1,3])
headtail ([])=????
¿Qué pasó en este último ejemplo? ¿Es realmente headtail una función sobre las listas o sólo sobre las listas no vacías?
Existen dos respuestas aquí.
La primera respuesta es introducir los tipos suma. De esa manera, headtail podría devolver un error sumando el conjunto unidad al tipo de su codominio ([$headtail: [int]\to 1+(int\times [int])$]). Esto es dual a la agrupación de todas las operaciones del álgebra de la lista en una única operación sumando sus dominios ([$nilcons: 1+(int\times [int])\to [int]$]) y por esta vía definimos el funtor polinómico [$F X = 1+(X\times [X])$] y llegamos a las F-(co)álgebras que es de lo que realmente estamos hablando.
Aún introduciendo la posibilidad de que headtail acabe de leer una lista, no significa que lo haga. Usar coinducción permite trabajar con listas infinitas en las cuales siempre podemos ir extrayendo elementos. Esto nos lleva a...
La segunda respuesta es modificar nuestro tipo de datos y decir que no trabajamos con listas, sino con listas infinitas (los llamados streams). Como la lista es infinita, nunca va a estar vacía y siempre podremos usar headtail. Estos tipos de datos infinitos definidos por coálgebras y coinducción se denominan codatos. Son útiles para modelar, por ejemplo, la entrada del usuario que, en principio, nunca acaba.
martes, 12 de febrero de 2013
miniSL parte 19 - Lectura de cadenas
Continuamos con la implementación de un mini lenguaje de script. En esta entrada vamos a hablar de la función que lee cadenas. Hemos mezclado en una misma función la lectura de cadenas y la creación de nombres.
Esta función es de las más complejas ya que tenemos que tratar con el escape de símbolos, incluyendo símbolos hexadecimales.
Empecemos por el principio y continuemos poco a poco.
La función devolverá una celda. Debido a que, según sea un nombre o no, la celda será STRING_LIT o NAME_CODE y no lo sabríamos por adelantado; hemos de añadir un flag create_name que indique a la función si quiere una cosa u otra.
Lo primero es quitar las dobles comillas con las que empieza la cadena.
Y vamos a ir leyendo mientras no encontremos el cierre de las comillas o haya habido un error. Usaremos la varible s para ir guardando lo que vayamos leyendo.
Aquí empiezan las complicaciones, si encontramos una barra de escape, debemos leer el siguiente carácter y actuar en consecuencia.
Los primeros casos son los códigos de control que se traducen directamente al C/C++. Para los curiosos, los códigos de control se listan en esta página.
En nuestro lenguaje vamos a variar algunas cosas. Por ejemplo, no usamos la comilla simple, pero sí quiero escapar la interrogación.
Si empieza por una equis, entramos en la descripción hexadecimal del carácter escapado. Vamos a ir leyendo dígitos hexadecimales y guardarlos en la variable x.
Usamos la función wcstoul para convertir lo leído en un número hexadecimal. Sólo vamos a permitir hasta el primer plano del UNICODE.
Metemos el carácter en la cadena que estamos construyendo y comprobamos que le sigue un punto y coma. Tampoco es usual tener esto en C, pero quita ambigüedades y añade robustez.
En otro caso, no conocemos la secuencia de escape.
Si no era una secuencia de escape, lo introduce directamente en la cadena. Esto puede ser problemático porque copia directamente cualquier cosa, incluso las que no se ven, del código fuente a la cadena; pero como es un mini lenguaje, vamos a asumirlo.
Finalmente, comprobamos algunas cosas como que terminemos en unas comillas o que no haya habido algún error.
A la hora de retornar la celda, según sea el flag pasado, creamos una cadena o un nombre. Realmente, ahora me doy cuenta que es un error haberlo hecho así y es mejor usar composición de funciones. Para la siguiente versión.
La siguiente parte de esta serie se va a dedicar a leer nombres y símbolos.
Esta función es de las más complejas ya que tenemos que tratar con el escape de símbolos, incluyendo símbolos hexadecimales.
Empecemos por el principio y continuemos poco a poco.
La función devolverá una celda. Debido a que, según sea un nombre o no, la celda será STRING_LIT o NAME_CODE y no lo sabríamos por adelantado; hemos de añadir un flag create_name que indique a la función si quiere una cosa u otra.
CELL& Script::ReadString(ISTREAM& i, bool create_name)
{Lo primero es quitar las dobles comillas con las que empieza la cadena.
i.get();
Y vamos a ir leyendo mientras no encontremos el cierre de las comillas o haya habido un error. Usaremos la varible s para ir guardando lo que vayamos leyendo.
STRING s;
while(i.peek()!='"' && i.good())
{Aquí empiezan las complicaciones, si encontramos una barra de escape, debemos leer el siguiente carácter y actuar en consecuencia.
if(i.peek()=='\\')
{
i.get();
switch(i.get())
{Los primeros casos son los códigos de control que se traducen directamente al C/C++. Para los curiosos, los códigos de control se listan en esta página.
case 'a': s+=L"\a"; break; case 'b': s+=L"\b"; break; case 'f': s+=L"\f"; break; case 'n': s+=L"\n"; break; case 'r': s+=L"\r"; break; case 't': s+=L"\t"; break; case 'v': s+=L"\v"; break; case '\'': s+=L"'"; break; case '"': s+=L"\""; break; case '\\': s+=L"\\"; break;
En nuestro lenguaje vamos a variar algunas cosas. Por ejemplo, no usamos la comilla simple, pero sí quiero escapar la interrogación.
case '?': s+=L"?"; break;
Si empieza por una equis, entramos en la descripción hexadecimal del carácter escapado. Vamos a ir leyendo dígitos hexadecimales y guardarlos en la variable x.
case 'x':
{
STRING x;
while(unsigned(i.peek())<256 && isxdigit(i.peek()) && i.good())
x.push_back(i.get());
if(x.empty()) throw L"Expecting a hexadecimal digit after \\x";Usamos la función wcstoul para convertir lo leído en un número hexadecimal. Sólo vamos a permitir hasta el primer plano del UNICODE.
int n=wcstoul(x.c_str(), NULL, 16); if(n>0xFFFF) throw L"Invalid hexadecimal character";
Metemos el carácter en la cadena que estamos construyendo y comprobamos que le sigue un punto y coma. Tampoco es usual tener esto en C, pero quita ambigüedades y añade robustez.
s.push_back(wchar_t(n)); if(i.get()!=';') throw L"Expecting semicolon after hex escape sequence"; } break;
En otro caso, no conocemos la secuencia de escape.
default: throw L"Unknown escape sequence"; } }
Si no era una secuencia de escape, lo introduce directamente en la cadena. Esto puede ser problemático porque copia directamente cualquier cosa, incluso las que no se ven, del código fuente a la cadena; pero como es un mini lenguaje, vamos a asumirlo.
else s+=i.get(); }
Finalmente, comprobamos algunas cosas como que terminemos en unas comillas o que no haya habido algún error.
if(i.bad()) throw L"Error while reading a string"; if(i.get()!='"') throw L"Unexpected end of file inside a string";
A la hora de retornar la celda, según sea el flag pasado, creamos una cadena o un nombre. Realmente, ahora me doy cuenta que es un error haberlo hecho así y es mejor usar composición de funciones. Para la siguiente versión.
return create_name ? CreateName(s) : CreateString(s); }
La siguiente parte de esta serie se va a dedicar a leer nombres y símbolos.
sábado, 2 de febrero de 2013
Coma serial, agujeros de gusano, gotos desnudos, e implícitos por tipo
Funciones
Llamemos a una función. Una función que está en un lugar distante del código.
La variable a es local. Eso quiere decir que fuera de mi trocito de código no se ve. Por eso necesitamos pasar la variable a a la función doble. ¿Qué pasaría si a fuera global y sí se viese en todo el programa incluida la función doble?
Variables globales
En este caso, no hace falta pasar la variable global a ninguna función, puesto que ya se ve desde allí.
Ahora, una vez guardado el dato 3 en la variable global a, está disponible en cualquier punto del programa. No hace falta pasarlo como argumento a la función doble. El flujo de datos a través de la variable global a se ha ocultado.
La variable global ha hecho que el dato 3 se pase de una punta a la otra del programa sin que haya relación directa entre esos dos trozos de código. Si no vemos la definición de doble, el uso de la variable global a dentro de doble no es tan obvio. No aparece ni en sus parámetros ni en sus argumentos. El efecto es el de un dato que se teleporta de un lugar a otro del programa.
Beam me up, Scotty!
Entra en un lugar del universo y sale por otro completamente distinto. Como los agujeros de gusano, pero mucho peor ya que puede haber más de dos extremos en una variable global.
Que alguien busque un error en un programa lleno de variables globales con datos que se teleportan de un lado a otro sin relación directa es muy, muy difícil.
Conclusión lógica: mejor evitar el uso de variables globales porque separan el flujo de datos del flujo de control.
Se considera al goto dañino
Hay ríos de tinta (y de bits) explicando que la instrucción goto debe ser evitada a toda costa y, además, su uso es síntoma de mal código. Muchas veces se toma demasiado al pie de la letra el título del artículo de Dijkstra que puso este problema sobre la mesa, pero sin terminar de leer el artículo por completo y viendo el porqué de la mala fama del goto.Realmente no siempre el goto es malo. Veamos la razón. El goto es el caso complementario a una variable global. En la variable global era el flujo de datos el que saltaba de una punta a otra del código, con el goto es el flujo de control el que salta.
¿Y si quiero pasar datos desde un goto desnudo hasta su etiqueta? Muy sencillo: debemos usar las variables globales.
Conclusión: los gotos desnudos son malos porque nos fuerzan a usar variables globales. Realmente, la raíz de todo mal está en las variables globales ya que los gotos pueden modificarse para que no sea necesario el uso de estas variables.
Restricción de saltos
¿Cómo podemos restringir el uso de los goto para que sea seguro? La primera lección la da el lenguaje C: un goto sólo puede saltar a una etiqueta que esté en su misma función.void g(void)
{
y:
puts(“ups!”);
}
void f(void)
{
int a;
x:
a=rand();
if(a==0) goto x; //OK: x está en f
else goto y; //ERROR: y está en otra función
printf(“%d\n”,a);
}
De esta forma antes y después del goto están visibles las variables locales de la función. No hace falta usar variables globales ya que la comunicación se realiza mediante variables locales.
Otra lección proviene de la teoría de lenguajes y consiste en añadir al goto un parámetro. Llamaremos a este goto vestido.
goto x(3);
Y en la etiqueta recogemos el argumento.
x(a): print(a);
La etiqueta se comporta en cierta manera como una función que nunca retorna. Esto se acerca al concepto de continuación. También, con las continuaciones, pasamos los datos como si fuera una función y no necesitamos variables globales.
Evitamos la raíz de todo mal: las variables globales y sus agujeros de gusano.
Nota: Una continuación es un valor de forma similar a lo que las clausuras son a las funciones, por lo que el goto vestido no es exactamente una continuación.
Implícitos
Sin embargo, no tener variables globales es tedioso a la hora de escribir un programa porque hay que ir arrastrando el contexto que antes mantenía la variable global.Propongamos este simple ejemplo:
Dato d; //Mi dato d que voy a usar como variable global
void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b)
{
//Esta función hace otras cosas con a y b pero, al final usa h
h(d)
}
void f(AlgunasCosas x, OtrasCosas y)
{
//Esta función hace cosas con x e y, pero al final llama a g
g(a,b)
}
int main()
{
//Prepara x e y
//Preparo mi dato d
f(x,y)
}
La función h usa d. Por ese motivo se dice que d es contexto de h. Como d es global no tenemos problemas en escribirla en cualquier parte del código, incluida h. ¿Qué pasaría si d no pudiera ser global? Tendríamos que ponerla en main(), pasársela a f y propagarla hasta llegar a h. Es decir, tenemos que escribir el contexto en los parámetros de las funciones que lo usan.
Esto es justamente lo que deseamos hacer: que el flujo de datos y de control vayan paralelos.
void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, Dato d)
{
//Esta función hace otras cosas con a y b pero, al final usa h
h(d)
}
void f(AlgunasCosas x, OtrasCosas y, Dato d)
{
//Esta función hace cosas con x e y, pero al final llama a g
g(a,b,d)
}
int main()
{
//Prepara x e y
Dato d; //Mi dato d que voy a usar como variable local
//Preparo mi dato d
f(x,y,d)
}
En las funciones f y g hemos tenido que añadir el dato para transmitirlo hasta la función h. Cada vez que usemos f o g, hemos de añadir d ¡y eso pueden ser muchas, muchas veces! ¿Cómo solucionarlo sin variables globales?
La mejor forma que he visto es mediante argumentos implícitos. Una característica del lenguaje de programación Scala. Consiste en añadir la palabra clave implicit en los parámetros que se comportan como propagadores de contexto.
void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, implicit Dato d)
{
//Esta función hace otras cosas con a y b pero, al final usa h
h(d)
}
void f(AlgunasCosas x, OtrasCosas y, implicit Dato d)
{
//Esta función hace cosas con x e y, pero al final llama a g
g(a,b,d)
}
int main()
{
//Prepara x e y
Dato d; //Mi dato d que voy a usar como variable local
//Preparo mi dato d
f(x,y,d)
}
Hasta ahora nada cambia, pero declarar un parámetro como implícito significa que es opcional y, si no se pone, se busca el llamado valor implícito de ese tipo de datos en el entorno actual. La forma de declarar un valor implícito es también con la palabra clave implicit.
void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, implicit Dato d)
{
//Esta función hace otras cosas con a y b pero, al final usa h
h(d)
}
void f(AlgunasCosas x, OtrasCosas y, implicit Dato d)
{
//Esta función hace cosas con x e y, pero al final llama a g
g(a,b,d)
}
int main()
{
//Prepara x e y
Dato d; //Mi dato d que voy a usar como variable local
//Preparo mi dato d
implicit d; //Usa d como el valor implícito para Dato
f(x,y) //El implícito para el tipo Dato es d.
//Entonces, es como llamar a f(x,y,d)
}
Nota: ¿Por qué Scala asocia un valor implícito al tipo Dato y no, por ejemplo, a cada nombre de manera que si no escribo el argumento implícito busque la variable con nombre “d”? ¿No es muy rebuscado buscar el valor implícito según sea el tipo del parámetro? La respuesta es bastante teórica. Este mecanismo introduce una dependencia de valores desde los tipos y esto es muy útil para otras muchas cosas como los conceptos (también llamados clases de tipos).
Lo interesante es que un parámetro implícito es directamente el valor implícito en el entorno de la función, por lo que tampoco hace falta escribir g(a,b,d).
void h(Dato d); //La función que usa el dato
void g(OtrosDatos a, YMasDatos b, implicit Dato d)
{
//Esta función hace otras cosas con a y b pero, al final usa h
h(d)
}
void f(AlgunasCosas x, OtrasCosas y, implicit Dato d)
{
//Esta función hace cosas con x e y, pero al final llama a g
g(a,b) //d es implícito aquí también
}
int main()
{
//Prepara x e y
Dato d; //Mi dato d que voy a usar como variable local
//Preparo mi dato d
implicit d; //Usa d como un implícito para Dato
f(x,y) //El implícito para el tipo Dato es d.
//Entonces, es como llamar a f(x,y,d)
}
Por supuesto, en este ejemplo sólo nos hemos ahorrado escribir d dos veces, pero en un programa real suele haber muchos más usos de este tipo de parámetros. Así que con estos parámetros implícitos se soslaya el inconveniente de no poder usar variables globales.
La coma serial
Una bagatela para finalizar. El título de esta entrada se llama "Coma serial, agujeros de gusano, gotos desnudos, e implícitos por tipo". Un lector atento habrá visto una escritura inusual de la enumeración. Concretamente usando la coma antes de la conjunción.Este tipo de uso de la coma no es común en el español, pero en inglés sí que lo es. Se denomina la coma de Oxford, la coma de Harvard o la coma serial. Se usa para evitar ambigüedades como estas:
"Dedicado a mis padres, Juan y Ana." Bien. Los padres son Juan y Ana.
"Dedicado a mis padres, Juan, y Ana." Mmmm.... Los padres no son Juan y Ana. ¿Verdad?
En el caso del título podía confundirse "e implícitos por tipo " como si los goto fueran, además de desnudos, implícitos por tipo. No es el caso. Los implícitos por tipo son otra cosa. Para evitar la ambigüedad, usé la coma serial.
Suscribirse a:
Entradas (Atom)
