Pages

Tuesday, October 23, 2012

About the used language

Since November 2011, the last time I posted something here, the FreeAlgView software was neglected due to lack of time. Previously, the development was achieved in Spanish (except source code), and now I will do it in English. A pair of annotations:
  • The project has to be (I want it to be) now international, and the "de facto" international language is English.
  • I carry out this project as final degree project and furthermore in the Hochschule für angewandte Wissenchaften Würzburg-Schweinfurt (Würzburg, Germany), in an Erasmus capacity. I can't thus achieve this project in spanish.
And finally:
  • I choose the sentence case style to write titles in English. This style is robuster (it is easier to know which words are capitalized and which not), and it is the style followed by many British publishers (Nature, The Economist or The Times). Furthermore, the Spanish style for titles is also the sentence case style (and I like it more). I want to utter this warning because many people are confused with this fact, and they want to advice me about "my mistakes" [1].
Viele Grüße :),
Peregring-lk

[1] Of course, I will have sure mistakes writting English, due to I'm not a native English speaker, but the "sentence case title style" isn't one of them :)

Leer más...

Welcome to the FreeAlgView project

Welcome to the official blog about the FreeAlgView project. This isn't really the first welcome, but it just the first welcome in this FreeAlgView revival (the first FreeAlgView development was neglected due to lack of time). This project is actually my final degree project and it is enrolled in the VII Concurso Universitario De Software Libre [1].

Description of FreeAlgView

FreeAlgView means a "Free Algorithm Viewer", and its complete description is:

A libre and learning-oriented algorithm animation application

Functionally spoken, FreeAlgView is a "animator of algorithms". The purpose of FreeAlgView is to make easier to understand algorithms and thus to improve the learning process. It will be contain whichever feature that makes easier to understand an algorithm: execution step-by-step, to hide superfluous variables, and so on. FreeAlgView is open to anybody who wants to learn algorithms, but I will initially focus my attention on the university community (students and professors in computer science/engineering) .

Those algorithms have to be written in a interpreted programming language designed "de facto" for FreeAlgView. FreeAlgView reads an algorithm (written in this language) and its animation configuration (feature dont designed yet) and it just animates the algorithm evolution. In absence of user configuration, a default animation is chosen.

This programming language is intended for human reading, but not just a pseudocode language, because of pseudocode languages are closer to natural languages but not designed to be processed by computers (and thus, more difficult to design parsers for it).

FreeAlgView project and FreeAlgView application

Unlike the old develop (July-November 2011), the project will be now formally executed by project management issues (a personal challenge). Specifically, it will be achieved following the PMBOK Guide recommendations. The project has a duration of five months (148 days), starting at 21th October 2012 (two days ago) and finishing at 20th March 2013, whose outcome will be the FreeAlgView application. The event launching officially the project is the FreeAlgView project charter, that anybody can get just below the blog title. This document specifies definitions, purposes, a preliminary timeline, requirements, and so on, providing a complete project definition. The other links related to this project can be found at the top of the blog, in the section (widget) FreeAlgView links (also in the project charter itself, together with a description, in section 8). This blog will be the official communication tool of the project during this time.

In the project management context, it is necessary to make a clear distinction between project and software:

  • Project "A project is a temporary endeavour undertaken to create a unique product, service or result". That implies a project has a defined period of time: a defined beginning and a defined end; and of course a defined outcome.
  • Software In the other hand, software is a entity which life cycle ends when nobody use it. It doesn't have thus a defined end and strictly spoken it is nor temporary (at most temporal, as opposed to eternal, but not just temporary).
Therefore, saying "project" to refer to "software" or anything else not according to this definition, for example, "the Firefox project", is incorrect in this context. The "Firefox project" is really a continuous effort over an application (the web browser Firefox) without a defined end, and if you want to refer to "what firefox (community) is doing" or "what firefox want to do", really you want to refer to the "Firefox purpose", to the "Firefox effort" or to the "Firefox mission". In other cases, with "Firefox project" people want to say "Firefox development" or just "Firefox (software)".

However I make here a proper use of this terms and when I say "project" I say this temporary five-months effort undertaken to create FreeAlgView (application); and when I say just "FreeAlgView" I want to refer only to the application itself.

Alles klar? :)

Viele Grüße,
Peregring-lk

[1] A free software university Spanish contest.

Leer más...

Monday, November 21, 2011

Problemas técnicos con CMake y Bison++

En bison++ y flex++ no acaba la cosa. Con cmake también he tenido mis problemas, aunque esta vez relativos al nuevo bison++. Bison++ es en realidad una extensión de bison, y cuando se instala el primero, se sobreescribe el segundo. Como prueba, si se ejecuta la órden bison --version te devuelve el mismo resultado que bison++ --version, que no es ni más ni menos que la versión de bison++.

La diferencia es que si se usa bison++ para traducir un .y, se genera una macro, llamada YY_USE_CLASS que permite al preprocesador de C generar todo el código correspondiente a una clase, al contrario que si se usa bison, que no la genera y se selecciona el código correspondiente a funciones y variables globales, como de costumbre.

El juego de conflictos proviene del hecho de querer aprovechar el módulo de CMake, FindBISON.cmake, para no tener que hacer una búsqueda manual de paquetes. Así que me propuse trabajar con bison añadiendo manualmente la macro YY_USE_CLASS de igual forma que en el caso del post anterior:

%header{
// Defines para stype, véase post anterior.
#ifndef yy_CodeBisonParser_stype
#define yy_CodeBisonParser_stype YY_CodeBisonParser_stype
#endif

#ifndef YY_USE_CLASS_
#define YY_USE_CLASS_
#endif
%}

De esta forma todo funcionaba a la perfección. Pero había un problema que estaba metiendo las castañas en el fuego, y era que, al ejecutar "$cmake ." por segunda vez, o "$make", me daba un aviso indicando que en el fichero CMakeCache.txt había un error de una entrada inválida, que era precisamente la de la versión de bison++.

El origen del problema proviende del siguiente hecho, lo que requiere una pequeña explicación:

Cuando en tu CMakeFiles.txt incluyes una órden del tipo FIND_PACKAGE(<NOMBRE_PACKETE>), bison busca en su directorio de módulos (/usr/share/cmake-2.8/Modules en mi caso) el fichero Find<NOMBRE_PACKETE>.cmake y ejecuta el código que incluye, que busca el packete deseado, genera una serie de macros para que el usuario pueda usar a continuación (como BISON_TARGET) y actualiza las entradas de CMakeCache con los resultados de la búsqueda del paquete, y si ésta fue o no satisfactoria. Luego, cualquier nueva llamada a cmake o a make antes consulta CMakeCache para ver si todo es correcto antes de continuar.

Una de las tareas que realiza el módulo FindBISON.cmake es reconocer la versión actual del packete mediante una expresión regular. Resulta que la expresión regular contenida en FindBISON.cmake para detectar la versión está diseñada para detectar la versión de bison, y como bison++ sobreescribe al fichero de bison, la expresión regular no coincide con la devuelta por "$bison --version". Por tanto, introduce la salida completa de ésta instrucción y la copia en CMakeCache.txt.

Resulta, además, que CMakeCache.txt no soporta todavía valores multilinea en sus entradas, y la versión de bison --version (cuando se ha instalado bison++), arroja una salida multilinea, y de ahí el error producido.

Para solucionarlo, no he tenido más remedio que copiar el módulo FindBISON.cmake a una copia local, renombrarlo por FindBISONPP.cmake y hacer algunos cambios:

// FindBISONPP.cmake

// Comentarios iniciales.

// Sustituir en esta línea bison por bison++
FIND_PROGRAM(BISON_EXECUTABLE bison++ DOC "path to the bison++ executable")

IF(BISON_EXECUTABLE)
   // Dos intrucciones SET, una EXECUTE_PROCESS, otro SET, y un bloque IF-ELSE.
   // En la parte else, se ha sustituido la expresión regular de esta forma:
   STRING(REGEX REPLACE "^bison\\+\\+ Version ([^,]+).*" "\\1"
          BISON_VERSION "${BISON_version_output})

   // En la macro BISON_TARGET, casi al final, hay una sección ADD_CUSTOM_COMMAND.
   // Ahí, en el atributo COMMENT:
   COMMENT "[BISON++][${Name}] Building parser with bison++ ${BISON_VERSION}"
ENDIF(BISON_EXECUTABLE)

// Esto se cambia ya que ahora hemos cambiado de directorio y no 
// encontraría el directorio. Se modifica la línea a continuación.
INCLUDE(FindPackageHandleStandardArgs)
FIND_PACKAGE_HANDLE_STANDARD_ARGS(BISON++ REQUIRED_VARS BISON_EXECUTABLE
       VERSION_VAR BISON_VERSION) 

Y así se arregla definitivamente el problema. Con el bison original también existe este problema. La órden "$bison --version" tiene una salida de unas cuantas líneas de versión + créditos. Si tienes la versión inglesa del paquete no hay ningún problema, ya que la expresión regular de FindBISON.cmake está configurada para detectar correctamente la versión. Pero con la versión española del paquete, en la salida se ha sustituido Bison por bison, y ya la expresión regular no encaja, repitiéndose el problema anterior. La solución consiste en realizar un cambio en su expresión regular. La versión original contiene:

"^bison \\(GNU Bison\\) ([^\n]+)\n.*" "\\1" 
Y hay que cambiarla, en tu copia local, por:
"^bison \\(GNU [Bb]ison\\) ([^\n]+)\n.*" "\\1"
Y nuevamente, se soluciona el problema. Por último, cuando en CMake se añade una órden FIND_PACKAGE, CMake busca módulos primero en su directorio de módulos (prsente en la variable CMAKE_MODULE_PATH), y si ahí no lo encuentra, busca en su directorio de isntalación, pero nunca en el directorio local. Para obligarle a buscar en el directorio local hay que hacer lo siguiente en CMake:
SET(CMAKE_MODULE_PATH ${CMAKE_MODULE_PATH} ${CMAKE_SOURCE_DIR})

# Pongo como ejemplo mi módulo para bison++
FIND_PACKAGE(BISONPP REQUIRED)
Y definitivamente se arregla el problema. También puede pasar que el módulo de flex no reconozca bien la versión y capture la salida entera (aunque no da error porque la salida de flex --version no ocupa más de una línea).

El problema puede provenir del hecho que, sin que hayas instalado flex manualmente, la tengas instalada en tu sistema. Posiblemente algún paquete la ha instalado como dependencia, pero también puede haber instalado, en vez de flex, el paquete flex-old, cuya funcionalidad es casi idéntica pero la salida de la versión es distinta, de modo que la expresión regular del módulo FindFLEX.cmake no coincide con ella. Con instalar el paquete flex es suficiente, ya que se desistala automáticamente flex-old (al menos en ubuntu) y no hay conflictos por dependencias.

Leer más...

Problemas técnicos con Flex++ y Bison++

Un cambio importante entre la fase de traducción del hito actual (v0.0.5) y la implementada en la primera entrada, es la completa migración a C++ de los mismos. El «scanner» de flex ahora ha pasado a ser de flex++ y el «parser» de bison ahora es bison++. Para ambas migraciones, hay un par de retos a superar.

Flex++: redefinición

En el caso de flex++, todo ha sido relativamente cómodo. Existe una opción, que puede indicarse tanto por la línea de comandos de flex como en la sección de declaraciones de su '.l' (ahora pasado a ser '.ll'), que es la opción c++ (%option c++), y ya flex se encarga de hacer la traducción necesaria para tener una clase con funciones miembro y atributos en vez de una serie de funciones y variables globales.

Pero el compilador me da un error de redefinición que no lograba solventar. El problema radica en que, por defecto, el nombre de la clase obtenida es yyFlexLexer, y no puede ser cambiada, al menos no mediante órdenes de flex. Esto es así porque estas clases están definidas (no implementadas) en <FlexLexer.h>, de la librería de flex. Una posible solución sería hacer una copia local y modificarla, pero no es una solución elegante. La otra vía es mediante un cambio de prefijo, con la opción %option prefix="Code" (en mi caso). El fichero .cpp generado (CodeFlexLexer.cpp en mi caso) contiene todas las definiciones con este cambio de prefijo (CodeFlexLexer en vez de yyFlexLexer), pero en <flexlexer.h> dichas redefiniciones no están.

Evidentemente, todos los módulos que necesiten incluir la clase, deberán incluir la cabecera <flexlexer.h> (que no contendrá el cambio de prefijo), así que, si se incluye una variable, por ejemplo "CodeFlexLexer _lexer", el compilador dará un aviso de tipo no declarado. En la documentación, te indican que bastaría incluir el siguiente código en los módulos que lo necesiten:

// Módulo donde usar la clase:
#undef yyFlexLexer
#define yyFlexLexer codeFlexLexer
#include <FlexLexer.h>

De esta forma, el módulo ya conoce el tipo "codeFlexLexer" y todo va de perlas. Pero hay un problema técnico adicional que complica un poco las cosas. La inclusión de #undef yyFlexLexer es por si existen varios lexers diferentes, y así evitar conflictos de nombres (cosa que me hará falta en un futuro).

Analizemos la siguiente situación. Tenemos el módulo CodeParser.hpp (donde tengo mi parser), y el módulo CodeFlexer.hpp, que incluye a <FlexLexer.h>

:
// CodeParser.hpp

#include "CodeFlexer.hpp"

// Definición de la clase CodeParser, con la variable «FlexLexer _lexer»
class CodeParser : public CodeBisonParser
{ ... }
// CodeFlexer.hpp

#undef yyFlexLexer
#define yyFlexLexer CodeFlexLexer
#include <FlexLexer.h>

// Definición de la clase CodeLexer, que hereda de CodeFlexLexer redefinida
class CodeLexer : public CodeFlexLexer
{ ... }
Y por último, el fichero generado por flex, CodeFlexLexer.cpp, que necesita tipos definidos en CodeParser, cuya sección de interés es la siguiente:
// CodeFlexLexer.cpp

// ... definiciones macro de flex

// La sección #undef no viene, porque esta es la versión generada de flex,
// y no le hace falta.
#define yyFlexLexer CodeFlexLexer
#include <FlexLexer.h>

#include "CodeParser.hpp"

// ... implementación de las funciones miembro.

El problema viene de la mano de la compilación de este último eslabón. Si detenemos su compilación después de la fase de preprocesado con la opción -E de gcc, obtendremos algo tal que así:

// CodeFlexLexer.cpp tras fase de preprocesado

// definiciones macro de flex

#define yyFlexLexer CodeFlexLexer
#include <FlexLexer.h>

// Inclusión de CodeLexer a través de CodeParser
#undef yyFlexLexer
#define yyFlexLexer CodeFlexLexer
#include >FlexLexer.h<

class CodeParser : public CodeBisonParser
{ ... };

// Continuación de CodeLexer

class CodeLexer : public CodeFlexLexer
{ ... }

// Continuación de CodeFlexLexer.cpp

// Implementación de las funciones miembro.

Aquí, el problema es que FlexLexer.h no tiene un buen control de las macros sobre su propia inclusión, y <FlexLexer.h> ¡se incluye dos veces!, lo que provoca que "CodeFlexLexer", ¡se defina dos veces!, dando un error de compilación por redefinición:

/usr/include/FlexLexer.h:112:7: error: redefinición de ‘class CodeFlexLexer’
/usr/include/FlexLexer.h:112:7: error: definición previa de ‘class CodeFlexLexer’

Siendo la línea 112 precisamente donde comienza la definición de la clase en dicho fichero de cabecera.

Llegar a descubrir este error me ha llevado varias horas de trabajo, hasta que por fin dí con la tecla, y ahora os brindo la solución:

En el fichero '.l' de flex he añadido las siguientes macros como santo y seña del analizador léxico que voy a generar, que debe añadir antes de la inclusión de cualquier fichero necesitado, que a su vez incluya directa o indirectamente a <FlexLexer.h>

// CodeFlexLexer.ll

%{
// ...

#ifndef _CODE_FLEX_LEXER_
#define _CODE_FLEX_LEXER_
#endif

#include "CodeParser.hpp"
%}

Y en CodeParser:

// CodeParser.hpp

#ifndef _CODE_FLEX_LEXER
#define yyFlexLexer CodeFlexLexer
#include <FlexLexer.h>
#endif

class CodeLexer : public CodeFlexLexer
{ ... }

De esta forma, <FlexLexer.h> solo se incluirá una vez ¡por cada analizador léxico distinto! (por ejemplo, _CODE_FLEX_LEXER y _COMMAND_FLEX_LEXER_).

Comunicación flex-bison

El segundo problema, aunque aquí no hay ni trampa ni cartón, puesto que ésto viene explicado en la documentación de flex por un lado y de bison por otro, es como conseguir comunicar flex y bison.

Hay dos problemas; el primero es que flex no permite definir los parámetros que contendrá la función yylex(), aunque creo que sí puede cambiarse su nombre (se pueden especificar analizadores léxicos reentrantes, pero eso es otro amplio tema en el que no he entrado), y el segundo es que bison++ no incluye ningún lexer como variable, solo una función virtual yylex() (que esta vez sí puede redefinirse tanto en nombre como en parámetros de entrada).

Esta función hay que implementarla manualmente, mediante la opción de bison %define FLEX_BODY <cuerpo>. También se pueden especificar sus miembros con %define MEMBERS <miembros>, donde <cuerpo> y <miembros> es código C++ puro. El nombre de la función puede cambiarse con %define LEX <nuevo_nombre>.

Hay dos opciones. La primera es indicar el analizador léxico como miembro del parser e implementar el cuerpo de FLEX_BODY con una llamada a la función que devuelve el token necesitado. Por ejemplo:

%define LEX lexer 
%define MEMEBERS private: CodeLexer _lexer
%define FLEX_BODY { return _lexer.yylex(); }

La segunda opción, y es la elegida por mí, es especificar la función como virtual pura y no añadir miembros:

%define LEX lexer
%define FLEX_BODY =0

De esta forma, y como la función lexer es virtual, puede implementarse en una clase heredada por él: que en mi caso es CodeParser herendaod de CodeBisonParser. De esta forma, el código queda más elegante y tratable.

Y ahora viene el último problema y eslabón de la comunicación: los parámetros de entrada para la función yylex() del analizador léxico. Como hemos dicho, flex no permite modificar los parámetros de entrada de la función yylex(). Pero flex necesita su famoso "yylval" para poder incluir en él los valores semánticos de cada token devuelto.

La solución consiste, una vez más, en hacer uso de la herencia, en este caso, CodeLexer heredando de CodeFlexLexer. Heredando la clase, se puede especificar la variable yylval como variable privada para que la función tenga acceso a él, y con la opción %option yyclass = "CodeLexer", indicar que flex debe generar la función CodeLexer::yylex() en vez de CodeFlexLexer:yylex(), para que la función sea miembro de la clase heredada y no de su clase base, y así tener acceso a las variables privadas que necesita.

Bison++: definición de tipos

También hay problemas con bison++, y también relacionados con las macros que maneja. Todas las opciones %define generan una macro asociada al valor indicado a continuación:

%name CodeBisonParser
%define lex lexer // Genera YY_CodeBisonParser_lex lexer
%define lex_body = 0 // Genera YY_CodeBisonParser_lex_body = 0

No lo he probado, pero creo que de esta forma podemos generar las macros que queramos. El problema es que bison tiene, repartido en todo su esqueleto de código después de esta sección de declaraciones, sentencias del tipo:

#ifndef YY_CodeBisonParser_NOMBRE
#define YY_CodeBisonParser_NOMBRE VALOR_POR_DEFECTO
#endif

Y <NOMBRE> siempre son mayúsculas, de modo que, si los define se indican en minúsculas, no se cambian sus valores. Por ejemplo:

#define YY_CodeBisonParser_lexer lexer

#ifndef YY_CodeBisonParser_LEXER
#define YY_CodeBisonParser_LEXER yylex
#endif

Como podrá suponerse el lector, el valor final de YY_CodeBisonParser_LEXER es yylex en vez de lexer, que será finalmente el valor usado. Así que hay que tener precaución con este detalle, y siempre hacer estas definiciones en mayúsculas.

Pero hay una excepción, y es la variable STYPE. Este es el nombre dado al tipo de la unión que usa bison para especificar todos los posibles tipos para los valores semánticos de los tokens. Esta variable debe indicar en minúsculas, pero además, hay otro problema.

La macro de bison++ para STYPE tiene la siguiente forma: yy_CodeBisonParser_stype. Como habréis podido observar, el prefijo esta vez es yy en vez de YY. Si se intenta redefinir (en mi caso con CodeValueToken), ocurre lo siguiente:

#define YY_CodeBisonParser_stype CodeValueToken

typedef union { ... } yy_CodeBisonParser_stype;

#define YY_CodeBisonParser_stype yy_CodeBisonParser_stype

Es decir, el valor final de YY_CodeBisonParser_stype es yy_CodeBisonParser_stype, que no está definido como macro, sino directamente como nombre del tipo. Parece que está hecho para no ser modificable, pues el tipo yy_CodeBisonParser_stype se usa directamente sin un #ifndef previo, y finalmente YY_CodeBisonParser_stype se sobreescribe. Por lo tanto, si intentas redefinirlo con la directiva %define no servirá para nada.

La solución consiste en hacer lo siguiente en el fichero .y (en mi caso .yy):

%header{
#ifndef yy_CodeBisonParser_stype
#define yy_CodeBisonParser_stype YY_CodeBisonParser_stype
#endif
%}

// Esto se debe incluir antes de la declaración de la unión y después de las definiciones.
De esta forma, el código generado queda como sigue y el renombrado se consigue con efectividad:
#define YY_CodeBisonParser_stype CodeValueToken;

// Nuestro nuevo código
#ifndef yy_CodeBisonParser_stype
#define yy_CodeBisonParser_stype YY_CodeBisonParser_stype
#endif

typedef union { ... } yy_CodeBisonParser_stype

#define YY_CodeBisonParser yy_CodeBisonParser_stype
Esta inserción funciona gracias a que bison++ inserta los bloques por órden: primero una serie de preámbulos generados automáticamente, luego todas las definiciones de usuario e inserciones de código en el mismo órden en que fueron declaras, y luego el resto del código generado automáticamente. La cuestión del órden es importante en bison/bison++, ya que, como hemos dicho, las definiciones se hacen en el mismo órden; por ello es importante añadir, antes que nada, la órden %define name, ya que a partir de ella se generan los nombres de todas las macros. Luego el resto de directivas %define y %union en cualquier órden deseado, pero siempre y cuando el bloque %header que hemos puesto se añada entre %define stype y %union { ... }. Y un último comentario adicional: bison++ «repite» toda la generación de código relativa a definiciones tanto en el código cabecera como en el .cpp, ya que en el .cpp no se generará una instrucción #define "cabecera.hpp". La órden %header, sin embargo, permite al usuario insertar código personalizable en ambos ficheros, cosa necesaria ya que la definición de stype también se inserta en ambos.

Leer más...

FreeAlgView v0.0.5

Tras una semana de intensa lucha contra las adversidades, ya he conseguido tener una primera visualización de algoritmos. Este logro se ha marcado con un tag llamado v0.0.5, que corresponde a la primera versión usable (y primitivo) del software. Se muestra en el video a continuación:

Los algoritmos que reconoce el software son aquellos que no contengan recursividad ni estructuras de datos. Solamente números enteros y reales.

Las variables, como ya hemos dicho en la anterior entrada, no necesitan ser declarados, pero tampoco hay mecanismo de detección de tipos válidos. Por ejemplo, en el caso del algoritmo de la raíz cuadrada de un número negativo, itera infinitamente sin dar ningún tipo de aviso ni manera de evitar la entrada de números negativos. Es un aspecto a mejorar como objetivo cercano a resolver.

Tampoco se puede, todavía, configurar la visualización. Así, por ejemplo, si el algoritmo usa demasiadas variables, éstas pueden salirse de la pantalla por ambos extremos, ya que todas las variables se muestran en una línea horizontal continúa centrada en la ventana de la aplicación. Así que, aunque el software computaría cualquier algoritmo (con las condiciones expuestas anteriormente) no se visualizarían correctamente en este tipo de casos.

Y poco más puedo decir del estado actual del proyecto. Solo que seguiré trabajando para ir, poco a poco, mejorar la calidad general y usabilidad del mismo.

Leer más...

Saturday, November 12, 2011

Primer intérprete prototipo

Tras mucha espera buscando un primer intérprete funcional, conseguí realizar el primero, con éxito satisfactorio, probado con el algoritmo mesopotámico del cálculo de la raíz cuadrada. Con este objetivo de primer intérprete prototipo me volví a apuntar un año más al concurso universitario del software libre, en ésta su sexta edición.

El lenguaje de programación de la aplicación se llama FAV, que son precisamente las iniciales de nuestra aplicación, FreeAlgView. Es de sintáxis inspirada en C, aunque dinámicamente tipado. Las variables no hace falta declararlas, se crean en su primera ocurrencia en una sentencia de asignación (como en Octave).

Y para muestra un botón, el código del algoritmo mesopotámico del cálculo de la raíz cuadrada, que ha sido el usado para probar el intérprete:
aprox ⟸ sqrtMeso(n, aprox)
{
    do
    {
        prevAprox ⟸ aprox;
        aprox ⟸ (n / aprox + aprox) / 2;
    } while (|aprox - prevAprox| > 0.001);
}
El intérprete ahora mismo soporta el tipo entero y real, los operadores de suma, resta, división (real únicamente) y operaciones comparativas <,>,<=,>=. Como único operador unario, por ahora, tenemos el operador de valor absoluto y la sentencia do while. No hay sentencias return (aunque quizás se añada una sentencia de abandono de función).

Tampoco hay, todavía, un mecanismo de control de tipos para los parámetros de entrada, que seguramente se diseñarán para especificarse de forma externa al algoritmo, junto a su fichero de configuración gráfica. De esta forma no se ensucia el algoritmo y queda los más claro posible.

No existen tampoco variables globales, todo serán funciones. Es por un motivo sencillo: FreeAlgView no computa ni crea programas, solamente algoritmos. Y para tal fin, no hacen falta variables globales, ni función main.

No se han enriquecido más las sentencias permitidas del lenguaje porque, ante nada, se quería conseguir un intérprete funcional minimalista para conocer la dinámica interna del intérprete. Una vez programada y conocida la estructura interna del interprete, añadir nuevas sentencias es una tarea mecánica y más sencilla, cosa que buscaba, y encontré.

El uso del interprete es, por ahora, sencillo, en consola solamente hay que ejecutarlo pasándole como parámetros el nombre del script y sus parámetros. Nuestro script recibe dos parámetros, el primero es el número al que se quiere hallar su raíz cuadrada, y el segundo parámetro es cualquier aproximación a él (en nuestro caso hemos pasado como aproximación de la raíz de 25 la cifra 128). La ejecución es como sigue:

user@laptop:~/FreeAlgView$ ./FreeAlgView sqrtMeso.fav 25 128
Out parameters
5

Y efectivamente, la raíz de 25 es 5. El siguiente paso es tener un primer prototipo de visualizador gráfico, y luego, un primero prototipo de personalización. A medida que se consigan estos objetivos, se irán colocando aquí.

Leer más...

Sunday, July 17, 2011

Presentación

Acabo de comenzar un nuevo proyecto, que quizás se convierta en proyecto fin de carrera si todo marcha bien. En caso contrario, mi proyecto fin de carrera será FreePhyloTree.

El proyecto que ando desarrollando, todavía en fase de planificación, se llama FreeAlgView. Se trata de un visualizador general de algoritmos. Es decir, una aplicación con una miniconsola a modo de interprete que permite visualizar la ejecución de cualquier script escrito en un lenguaje de programación que aún he de diseñar. Dicho script contendrá, evidentemente, el algoritmo a ejecutar/visualizar.

Estamos, sobre todo, ante una aplicación docente, cuyo objetivo es hacer más fácil y comprensible a cualquier alumno y/o interesado la comprensión de cualquier algoritmo que se esté estudiando. Si estás intentando comprender el funcionamiento de, por ejemplo, el algoritmo de Floyd o el simplex bidimensional, solo has de traducir el algoritmo, desde el lenguaje en el que te lo encontraste al lenguaje de FreeAlgView, para ver su ejecución paso a paso, pararlo, ir hacia detrás y hacia delante, y observar detenidamente el valor de las variables, bajo un entorno gráfico que intenta hacer la visualización lo más fácil y elegante posible.

El proyecto estará desarrollado integramente en C++ y Qt. En principio, las animaciones serán bidimensionales, así que no será posible visualizar algoritmos que requieran, para su visualización, un entorno 3D. Aunque este es un detalle que podría cambiar con el tiempo.

El blog del proyecto será el blog que estás leyendo y el repositorio estará alojado en gitorius, y a la derecha teneis un enlace a él.

Anteriormente, este sofware se llamaba AlgViewer, pero tras advertir que existe otro programa de igual nombre y parecido propósito, aunque relacionado con la medicina, decidí renombrar el proyecto, primero a Visualg, que también estaba ocupado (es un programa portugués de parecido propósito al mío, pero no gráfico), y finalmente elegí FreeAlgView, y así se unificaba formato de título con el de mi anterior proyecto, FreePhyloTree.

Leer más...