Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

La Implementación de Rational.pas

Reporte Técnico ECCI-94-03

Proyecto 326-89-019

Adolfo Di Mare

Resumen   

      La unidad rational.pas es un módulo Pascal muy simple que sirve para manejar números racionales. Esta implementación se ha hecho tomando como base la implementación del ADT Elem, la que sirvió de plantilla para crear las operaciones de aritmética de números racionales.

      El ADT elemental TRational tiene todas las operaciones que los ADTs contenedores necesitan para manipular al ADT elemental, por lo que puede ser almacenado en cualquier contenedor.

      El valor didáctico de este ADT estriba en que al estudiarlo, el estudiante puede ver porqué es muy sencillo usar la unidad elem.pas como plantilla para crear nuevos ADTs. Básicamente, el trabajo realizado consistió en es usar el editor de textos para remplazar el nombre TElem por TRational, y luego agregar las operaciones particulares sobre números racionales.

      Como estos ADTs sirven de plantilla para crear los ADTs elementales que estarán almacenados en un contendor, su estudio tiene un alto valor didáctico.

1. Abstracción de TRational   

      Un número racional es el cociente de dos números enteros. Todos los números racionales representados con TRational siempre tienen el divisor mayor que cero.

      El ADT TRational es un ADT elemental, pero no es un contenedor, pues los contenedores son aquellos ADTs cuya razón de existencia es almacenar a otros ADTs (los más importantes contenedores son la Lista y el Arbol). Los ADTs elementales existen para independizar la implementación del contenedor del elemento contenido. Todo ADT elemental tiene un conjunto de operaciones básicas , que son las que usa el contenedores puedan manipularlos, y otro conjunto de operaciones que lo caracterizan. En el caso de TRational, en esta segunda clase de operaciones se encuentra las operaciones aritméticas sobre números racionales.

2. Operaciones   

      Las operaciones del ADT TRational son las operaciones aritméticas. Además, Rational.pas incluye todas las operaciones que un contenedor necesita para manipular a su ADT elemental. Estas son sus operaciones:

Init(r)

Constructor; inicializa el número racional.

Clear(r)

Limpia al número racional.

Done(r)

Destructor; destruye al número racional.

Copy(x,y)

Copia el valor del número racional "y" en "x".

Move(x,y)

Le traslada a "x" el valor del número "y".

Equal(x,y)

Compara el valor de "x" con el de "y".

Load(r,F)

Carga el valor de "r" desde el archivo "F".

Store(r,F)

Almacena el valor de "r" en el archivo "F".

OK(r)

Verifica la invariante del ADT.

Fix(r)

Repara número racionales.

Fill(x, n,d)

x := (n/d);

Numerator(x)

x := (n/d); ==> Numerator(x) = n;

Denominator(x)

x := (n/d); ==> Denominator(x) = d;

Is_ZERO(x)

Es x = 0?

Minus(x, xm)

x = (n/d); ==> xm := -(n/d);

Inverse(x, inv)

x = (n/d); ==> inv := -(d/n);

Add(x,y, r)

r := x+y;

Sub(x,y, r)

r := x-y;

Multiply(x,y, r)

r := x*y;

Divide(x,y, r)

r := x/y:

To_STRING(r)

r := (n/d); ==> To_STRING(r) = '(n/d)'

      Las primeras operaciones [Init()...Fix()] son las que los contenedores usan para manipular al ADT que contienen. Por si solas no caracterizan al ADT TRacional. Las que se lo caracterizan son las otras, que sirven para cambiar el valor de un número racional.

      Como Pascal no permite la Sobrecarga de Operadores, lo que si es permitido en Ada y C++, entonces las operaciones aritméticas se han definido como procedimientos que reciben en sus primeros argumentos los valores sobre los que operan, y retornan el resultado en el último argumento.

      La operación Rational.Fill(r, n,d) es muy importante, pues es la que permite cambiarle el valor al número racional. Las operaciones que complementan a Fill() son las funciones Numerator() y Denominator(), que retornan el numerador y denominador del número racional.

3. Modelo   

      El modelo del ADT es un diagrama de la estructura de datos usado para implementarlo. El modelo de TRational es muy simple:

      Los campos "num" y "den" son de tipo LONGINT, para permitira el almacenamiento de números racionales relativamente grandes.

4. Comportamientos   

      Al definir este ADT no se le definieron comportamientos, pues en general, estos se usan para los ADT contenedores.

5. Detalles de implementación   

      Para facilitar la programación, los números racionales almacenados siempre tiene su denominador estrictamente mayor que cero.

      La implementación se ha hecho buscando la claridad en lugar de la eficiencia. Por eso, los algoritmos que implementan las operaciones artiméticas son muy simples. Existen casos en los que esta implementación tan simple comporta una pérdida de precisión, o un rebase aritmético (overflow). La implementación puede mejorarse mucho en este sentido.

      Para lograr el ocultamiento de datos se usa el siguiente truco:

{[])======================================([]}
{[]}  TYPE                                {[]}
{[]}    Rep = RECORD                      {[]}
{[]}      num : LONGINT; { numerador    } {[]}
{[]}      den : LONGINT; { denominador  } {[]}
{[]}    END;                              {[]}
{[])======================================([]}
{[]}    TRational =                       {[]}
{[]}      ARRAY[1..SizeOf(Rep)] OF BYTE;  {[]}
{[])======================================([]}

      El tipo TRational realmente es un arreglo de BYTES, pero que tiene exactamente el tamaño de una variable de tipo "Rep". Por eso, para accesar los campos del ADT, en la implementación se usa una transferencia de tipos:

     VAR
       r : TRational

     { ... }

       r.num := 3;             { ¡¡¡ ERROR !!! }
       Write(Rep(r).num:10);   { ok }

      El compilador Pascal sólo permite transferencia de tipos cuando los tipos tiene exactamente el mismo tamaño. Esto es muy importante, porque evita que el programador bisoño haga muchas transferencia de tipos que son inválidas.

      Esta manera de definir los tipos obliga al programador del ADT TRational a usar la palabra "Rep" cada vez que accesa los campos privados del ADT, con lo que se logra simular el ocultamiento de datos. Otra forma de lograr el mismo efecto es definir los tipos de la siguiente manera:

{[])======================================([]}
{[])  IMPLEMENTATION                      ([]}
{[])======================================([]}
{[]}  TYPE                                {[]}
{[]}    RepRational = RECORD              {[]}
{[]}      num : LONGINT; { numerador    } {[]}
{[]}      den : LONGINT; { denominador  } {[]}
{[]}    END;                              {[]}
{[])======================================([]}
{[]}    TRational = RECORD                {[]}
{[]}      Rep : RepRational;              {[]}
{[]}    END;                              {[]}
{[])======================================([]}

      La gran ventaja de este truco sobre el anterior es que hace innecesario usar transferencias de tipos, las que nunca dejan de ser peligrosas. Para accesar el "Rep" del ADT, el programador escribe "r.Rep.num". Además, el nombre de la variable que se está accesando [r] aparece de primero, mientras en que la otra forma aparece después [Rep(r)].

      La razón por la que en la implementación de Rational.pas no se usa el segundo truco, que es a todas luces mejor, es para mostrarle al estudiante que hay otras maneras de hacer las cosas, y para que aprecie las ventajas de la segunda forma sobre la primera.

      Después de todos, ¿que es la tecnología sino la concatenación de pequeños trucos que nos llevan a lograr grandes resultados con poco esfuerzo?

6. Versión C++ de plantillas   

      Debido a las cualidades adicionales de C++, que es un un lenguaje mucho más expresivo que Pascal, la implementación C++ de los números racionales está inspirada en la versión Pascal, pero permite usar los operadores directamente en expresiones. Al usar plantillas se logra además una conveniencia adicional para el programador cliente, quien no tiene que preocuparse de cargar con 2 archivos para la clase, pues en el archivo "rational.h" está toda la implementación completa. Eso sí, para usarla es necesario que el sistema C++ de compilación sea capaz de eliminar las redundancias que surgen cuando el mismo archivo de encabezado (".h") es incluido en varios archivos de código diferentes (".cpp") .

      En algunas ocasiones es útil escoger el tamaño de los números enteros usado para almacenar un número racional. Si se escogen enteros cortos, de 2 bytes, el rango numérico puede ser tan pequeño que algunas multiplicaciones o divisiones rebasen la capacidad de almacenamiento y, en consecuencia, los resultados obtenidos serían incorrectos. Esto sucede porque al multiplicar 2 número de "N" dígitos, el valor resultante puede tener el doble de dígitos. Por ejemplo en una variable de 16 bits es posible almacenar valores en el rango [-32768..32767], por lo que al sumar los números racionales "[127/256]+[255/511]" se obtendría un resultado incorrecto, porque la multiplicación de los denominadores requiere almancenar el valor "256x511==130816", que rebasa los límites del rango numérico de los enteros de 16 bits.

      En otras ocasiones puede ser conveniente usar números de rango arbitrario, implementados posiblemente usando lista de dígitos, que pueden crecer tanto como sea necesario (hasta alcanzar el límte de la memoria disponible, por supuesto). Para estas aplicaciones, la clase C++ rational<INT> es ideal, pues al estar implementado con plantillas puede usarse directamente sin modificación alguna. Debido a que muchas operaciones son "inline", el costo en eficiencia es mínimo en la mayor parte de los casos.

7. Reconocimientos   

      Esta investigación se realizó dentro del proyecto de investigación 326-93-256 "DBgen: generación automática de programas a partir de su base de datos", inscrito ante la Vicerrectoría de Investigación de la Universidad de Costa Rica. La Escuela de Ciencias de la Computación e Informática también ha aportado fondos para este trabajo.

8. Código fuente   

Todos los fuentes rational.zip [.zip]

http://www.di-mare.com/adolfo/p/src/rational.zip

Tipo abstracto de datos TRational [.pas]

http://www.di-mare.com/adolfo/p/src/rational.pas

Documentación Doxygen de la clase rational<INT> [.html]

http://www.di-mare.com/adolfo/p/rational/template/index.html

Fuente documentado por Doxygen de [rational.h]

http://www.di-mare.com/adolfo/p/rational/rational_8h_source.html

La implementación C++ de plantillas se encuentra en [rational.zip], dentro del subdirectorio template.

Bibliografía   

Indice   

[-]	Resumen
[1]	Abstracción de TRational
[2]	Operaciones
[3]	Modelo
[4]	Comportamientos
[5]	Detalles de implementación
[6]	Versión C++ de plantillas
[7]	Reconocimientos
[8]	Código fuente
	Bibliografía
	Indice
	Acerca del autor
	Acerca de este documento
	Principio Indice Final

Acerca del autor   

Adolfo Di Mare <adolfo@di-mare.com>

Acerca de este documento   

Referencia:	Di Mare, Adolfo: La Implementación de Rational.pas, Reporte Técnico ECCI-94-03 Proyecto 326-89-019, Escuela de Ciencias de la Computación e Informática (ECCI), Universidad de Costa Rica (UCR), 1994.       http://www.di-mare.com/adolfo/p/rational.htm       http://www.di-mare.com/adolfo/p/src/rational.zip
Autor:	Adolfo Di Mare <adolfo@di-mare.com>
Contacto:	Apdo 4249-1000, San José Costa Rica Tel: (506) 207-4020       Fax: (506) 438-0139
Revisión:	ECCI-UCR, Diciembre 2007
Visitantes: