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

Polimorfismo uniforme más eficiente

Propuesta de Investigación

N° 326-98-391

Adolfo Di Mare

I Elementos básicos

I.1 Título del proyecto de investigación

I.2 Título del programa al cual pertenece el proyecto

I.3 El programa está inscrito en la Vicerrectoría de Investigación

I.4 Unidad base a la que pertenece el investigador principal

I.5 Unidad de adscripción del proyecto

I.6 Descriptores

Programación de computadores    C++, C, Pascal, Eficiencia

Programación orientada a los objetos Implementación de programas

I.7 Tipo de investigación

I.8 Protección de la propiedad intelectual

      Pese a lo anterior, y si del proyecto resulta un descubrimiento que puede servir de base para entrar al mercado con un producto, con suficiente antelación el investigador principal lo hará del conocimiento de las autoridades universitarias, para con ellos negociar un acuerdo adecuado.

I.9 Información acerca de los investigadores

      Este proyecto ha sido planeado para que su ejecución comience en el II Semestre de 1998, y para que termine a fines del año 1999, con una carga de 1/3 TC para el investigador principal. El presupuesto docente será aportado por la ECCI por la duración total del proyecto, que es de tres semestres.

      El profesor Di Mare será responsable de ejecutar todo el trabajo en el proyecto, que consiste en obtener material bibliográfico adecuado, experimentar implementando programas de computación y reportar los resultados en artículos de investigación.

      No hará falta que la Vicerrectoría de Investigación apoye presupuestariamente el proyecto, pues se usarán los recursos disponibles en la ECCI para su desarrollo.

I.10 Información relacionada con la propuesta

[DiM­78]	Di Mare, Adolfo: Diseño y Programación Estructurada, en Fundamentos de Algoritmos y Lenguajes, pp [28­42], Departamento de Ciencias de la Computación, Escuela de Matemática, Universidad de Costa Rica, 1978.
[DiM­87a]	Di Mare, Adolfo: DB3mnugn: Generación de Prototipos de Sistemas y Tutores Electrónicos mediante Menúes, Reporte Técnico PIBDC-01-87, proyecto 326-86-053, Escuela de Ciencias de la Computación e Informática, UCR 1987.
[DiM­88a]	Di Mare, Adolfo: MAKE: cómo compilar rápido en Clipper, Reporte Técnico PIBDC-04-88, Proyecto 326­86­053, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1988.       http://www.di-mare.com/adolfo/p/makedbf.htm
[DiM­88b]	Di Mare, Adolfo: Convenciones de Programación para Pascal, Reporte Técnico ECCI­01­88, Proyecto 326­86­053, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1988.       http://www.di-mare.com/adolfo/p/convpas.htm
[DiM­90c]	Di Mare, Adolfo: Programación de Computadores: Ayer, Hoy, Mañana, Revista Rumbo, 1990.       http://www.di-mare.com/adolfo/p/rumboprg.htm
[DiM­91a]	Di Mare, Adolfo: Abstracción de datos en Pascal, Reporte Técnico PIBDC-01-91, proyecto 326-89-019, Escuela de Ciencias de la Computación e Informática, UCR 1991.
[DiM­91b]	Di Mare, Adolfo & Oviedo, Eduardo: Turtle: La Tortuga LOGO para Turbo Pascal, Ponencia presentada en el V Congreso Internacional de Logo, celebrado en noviembre de 1991 en San José, Costa Rica, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica;1991.       http://www.di-mare.com/adolfo/p/turtle.htm
[DiM­91c]	Di Mare, Adolfo: Tipos Abstractos de Datos y Programación por Objetos, Reporte Técnico PIBDC-03-91, proyecto 326-89-019, Escuela de Ciencias de la Computación e Informática, UCR 1991.       http://www.di-mare.com/adolfo/p/oop-adt.htm
[DiM­92]	Di Mare, Adolfo: Yet Another C++ Money Class, The C Users Journal, Vol.10 No.4, pp [58­64], Abril 1992.       http://www.di-mare.com/adolfo/p/money.htm
[DiM­93]	Di Mare, Adolfo: La programación por objetos en los sistemas de información, Revista Acta Académica, Universidad Autónoma de Centro América, Número 13, pp [35­41], Noviembre 1993.       http://www.uaca.ac.cr/acta/1993nov/oopsig.htm
[DiM­94a]	Di Mare, Adolfo: Prueba interactiva de ADTs, Reporte Técnico ECCI­94­01, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94b]	Di Mare, Adolfo: La Implementación de Elem.pas, Reporte Técnico ECCI­94­02, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94c]	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, Universidad de Costa Rica, 1994.
[DiM­94d]	Di Mare, Adolfo: La Implementación de Poly.pas, Reporte Técnico ECCI­94­04, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94e]	Di Mare, Adolfo: La Implementación de ListAHO.pas, Reporte Técnico ECCI­94­05, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94f]	Di Mare, Adolfo: La Implementación de List.pas, Reporte Técnico ECCI­94­06, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94g]	Di Mare, Adolfo: La Implementación de Tree.pas, Reporte Técnico ECCI­94­07, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94h]	Di Mare, Adolfo: La Implementación de Heap.pas, Reporte Técnico ECCI­94­08, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94i]	Di Mare, Adolfo: Uso de la unidad Test.pas, Reporte Técnico ECCI­94­09, Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.
[DiM­94j]	Di Mare, Adolfo: Manejo de excepciones en Turbo Pascal, Reporte Técnico ECCI­94­10 (Revisión 3), Proyecto 326­89­019, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, 1994.       http://www.di-mare.com/adolfo/adt/except.htm
[DiM­94k]	Di Mare, Adolfo: Licenciado programador, Revista Acta Académica, Universidad Autónoma de Centro América, Número 14, Páginas [56­57], Marzo 1994.       http://www.di-mare.com/adolfo/p/licprog.htm
[DiM­94l]	Di Mare, Adolfo: "genridx.h" Una interfaz uniforme para el uso de archivos indizados en C, Revista Acta Académica, Universidad Autónoma de Centro América, Número 15, pp [35­58], Noviembre 1994.       http://www.uaca.ac.cr/acta/1994nov/genridx.htm
[DiM­96b]	Di Mare, Adolfo: Tres formas diferentes de explicar la recursividad; Revista Ingeniería, Facultad de Ingeniería, Universidad de Costa Rica, Volumen 6, Número 2, pp [31­44], 1996.       http://www.di-mare.com/adolfo/p/recurse1.htm
[DiM­96c]	Di Mare, Adolfo: Uso de convenciones de programación para descifrar programas, Revista Ingeniería, Facultad de Ingeniería, Universidad de Costa Rica, Volumen 6, Número 2, pp [45­54], 1996.       http://www.di-mare.com/adolfo/p/reverse.htm
[DiM­97d]	Di Mare, Adolfo: Propuesta para mejorar el curso Principios de Informática, Reporte Técnico ECCI­97­01, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, Julio 1997.       http://www.di-mare.com/adolfo/p/princinf.htm

I.11 Información acerca de los estudiantes que participan en el proyecto

II Plan de investigación

II.1 Antecedentes

II.1.a Planteamiento del problema

      Parece entonces que la ciencia y la academia tienen objetivos contrapuestos, al menos bajo la óptica del uso de los resultados de investigación que cada uno hace. Es usual que los investigadores afirmen que solo un 5% de toda la investigación tiene aplicación en el "mundo real". O sea, prácticamente afirman que la labor de los investigadores es tener muchas ideas, y concretarlas en publicaciones o prototipos, para que luego la industria escoja unos pocos y los transforme en productos que la sociedad pueda asimilar.

      Sin embargo, a veces ocurre que una invención académica tiene una belleza especial, que seduce a alguna persona. Eso es lo que ha ocurrido con el polimorfismo uniforme, cuya mejor definición aparece en [MDC­91]. Esta técnica de programación es una tecnología que puede reducir sustancialmente el tamaño de los programas. ¿Por qué es esto importante?

      En verdad el tamaño de los computadores actuales es tan grande, en los niveles de los giga-bytes, que resulta paradójico esforzarse en reducir el tamaño de un programa de varios megabytes, a unos cuantos kilobytes (recuerde el lector que Basic, el lenguaje que hizo famoso a Bill Gates, en su versión original ¡ocupa solo 2K!). El progreso requiere de la eficiencia, como lo muestra la siguientes anécdota del automóvil.

      Pese a que ya en los años cincuentas se había desarrollado la tecnología mecánica para que los autos alcanzaran velocidades superiores a los cien kilómetros por hora, en los ochentas, y todavía en los noventas, se continúa trabajando en lograr mayor eficiencia, para disminuir el consumo de combustible, la polución, el tamaño y comodidad de los vehículos modernos, etc.

      Por eso cabe estudiar ahora como aumentar la reutilización de componentes de programación [Kru­92] para mejorar el desempeño de los sistemas computacionales, y disminuir su costo de mantenimiento [Boe­81], usando para ello la elegante tecnología del polimorfismo uniforme.

      ¿Qué promete el polimorfismo uniforme? Reutilizar componentes de programación. ¿Por qué ha sido desechado por la industria? Pues sencillamente porque en la industria primero se usó la genericidad de Ada [Mey­86], y luego el polimorfismo paramétrico de C++ [Str­89] los que, aunque funcionan, hacen muy difícil compartir la implementación de cada algoritmo polimórfico. Pese a que Ada ha sido desechado como el principal lenguaje del departamento de defensa de los Estados Unidos, ya la industria ha aceptado a C++ como su estándar [Bec­98], lo que efectivamente desecha el uso del polimorfismo uniforme a favor del paramétrico.

      A primera vista parece que todos estos problemas ya están resueltos, pues C++ cuenta con plantillas que permiten especializar algoritmos para cualquier tipo de datos. Sin embargo, esta solución siempre implica que haya duplicación del código objeto final, pues cada instanciación de una plantilla resulta en una sección de código ejecutable diferente, especializada para el tipo de datos instanciado. Si en lugar de usar plantillas se usa herencia para implementar los algoritmos polimórficos, entonces se cae en el problema de que se pierde la verificación fuerte de tipos, pues para reuitilizar algoritmos lo que se hace es homologarlos a un solo tipo base, que es el polimórfico.

      En este proyecto se busca estudiar algoritmos polimórficos para implentarlos de forma que se pueda compartir el código objeto final (lo que no ocurre si se usan plantillas en C++), pero sin renunciar a la verificación fuerte de tipos (que es el precio de usar herencia y polimorfismo en la implementación). Se busca encontrar formas de expresar algoritmos polimórficos que mejoren el rendimiento de una implementación en que se usa siempre semántica de referencia, aunque no se llegue a la eficiencia que implica la parametrización.

      ¿Es posible disfrutar de las ventajas del polimorfismo uniforme sin caer en los problemas del polimorfismo paramétrico? ¿Es siempre necesario perder la verificación fuerte de tipos si se usan algoritmos polimórficos? Vale la pena estas preguntas. Pero más vale llegar a la respuesta.

II.1.b Relevancia académica

      Además, los resultados de este proyecto insidirán positivamente en la docencia porque las técnicas desarrolladas se podrán aprovechar rápidamente en los cursos de programación de computadoras, organización de lenguajes, sistemas operativos, etc.

      También esta línea de investigación, si es apoyada por los académicos de la ECCI, puede llegar a convertirse en un sólido Programa de Investigación.

      Pero lo más importante es que es un problema bonito, que merece una solución.

II.1.c Estado actual del conocimiento

• Biblioteca de componentes de Booch [Boo­87]: es una de las primeras bibliotecas, y es muy apreciada en la comunidad Ada. Como Ada tiene paquetes genéricos, en esta biblioteca se usan plantillas para producir contenedores. Sin embargo, esta biblioteca obliga a entregar los fuentes de los algoritmos, y además duplica el código para cada instanciación.
        Los componentes de Booch son el paradigma que se ha seguido para la construcción de contenedores desde hace diez años, tanto por su cobertura como por su antigüedad. Es posible que haya que alejarse un poco de él para encontrar soluciones, pues muchas veces la costumbre obstaculiza el progreso.
• Borland International Data Structures [BI­92]: No se puede dejar de mencionar a BIDS, el trabajo de Borland, productor no solo de la revolución Turbo Pascal en los años 80, sino también por su excelente compilador C++.
        Borland es el más famoso e importante productor de compiladores para la plataforma Intel x86 y, sin duda alguna, sus bibliotecas de contenedores son importantes. Siguen en mucho el paradigma de Booch y vienen en varias versiones pues fueron desarrolladas mientras C++ crecía como lenguaje. Por eso, al principio, la instanciación de un contenedor era responsabilidad del programador, para lo que debía invocar a una serie de macros. Cuando la especificación del lenguaje C++ fue más estable y completa, Borland reimplementó su biblioteca original usando plantillas, y siempre dentro del paradigma de Booch.
        Esta biblioteca incluye dos tipos de contenedores. Los primeros son una jerarquía derivada del modelo Smalltalk, y tiene la desventaja de que lo que se alamacena en un contenedor siempre es una referencia al objeto. Además, esta biblioteca no ofrece la protección de la verificación fuerte de tipos, pues todos los objetos almacenados en un contenedor se homologan por ser siempre descendientes de la clase abstracta Object.
        La otra biblioteca que incluye BIDS es muy similar a STL [Aus­97]. De hecho, Borland participó activamente en el desarrollo de la biblioteca de plantillas estándar de C++ [STL­95], y ya sugiere usar STL para todos los programas.
• The Eiffel Library: [Mey­90]: Bertrand Meyer ha definido a Eiffel, un exquisito lenguaje que se siente mucho como Pascal pero que tiene mucho más poder expresivo.
        El gran atractivo de Eiffel es haber llegado a ser todo lo que C++ pudo haber sido, si no hubiera sido sobre-diseñado por un comité. Eiffel también tiene soporte del sistema de compilación para programación de grandes proyectos, como lo muestra su capacidad para definr que un componente ya es obsoleto. Sus bibliotecas incluyen contenedores, y por supuesto hay una versión de los componentes de Booch para Eiffel. Quizá un programador formado en la eficiencia de C y C++ se rehúse a programar en Eiffel porque forzosamente en sus programas estará presente el recolector de basura, con la ineficiencia que comporta: este es su gran defecto.
        Eiffel es un lenguaje precioso. Java, el descendiente directo de C++ [Anu­96] no tiene la consistencia, la elegancia ni el poder de Eiffel [Dvo­97].
• GNU [Lg++95]: Libg++ es una biblioteca basada en la jerarquía de clases del lenguaje Smalltalk [GR­83]. Ha sido muy utilizada porque tiene el apoyo del proyecto GNU, que busca entregarle a la humanidad programas reutilizables de alta calidad, a precio nulo. Libg++ es producto del esfuerzo de Keith Gorlen [Gor­87].
• Library of Efficient Data Types [LED­96]: LEDA es una biblioteca similar a Libg++, aunque incluye algoritmos para manipulación de grafos que no se encuentran en otras bibliotecas.
• Public Ada Library: PAL es un conglomerado de esfuerzos que forman una biblioteca de distribución y uso gratuito, que se encuentra en el repositorio público WUARCHIVE de la Universidad de Washington en San Luis. Es mantenida por su administrador Richard Conn, y contiene otras bibliotecas Ada, como por ejemplo la biblioteca AJPO del Ada Joint Program Office o la biblioteca SEI del Software Engineering Institute.
• A Systematic Catalogue of Reusable Abstract Data Types [US­94]: Esta biblioteca para Ada llama la atención porque trata ser muy completa y, para lograrlo, sus autores no vacilaron en implementar cada contenedor de varias formas diferentes. Es muestra de que para alcanzar alta eficiencia se requiere de un gran esfuerzo. Esta biblioteca forma parte de PAL.
• Standard Template Library [STL­95]: En estos momentos STL es la biblioteca más famosa, pues recientemente fue declarada estándar para el lenguaje C++. Recoge la experiencia en construcción de contenedores que hasta el momento se ha acumulado, y ofrece todos los algoritmos que uno encuentra en un buen libro de estructura de datos. En estos momentos, STL es el paradigma de la parametrización.

      Muchas de estas bibliotecas se pueden conseguir en Internet, sin costo alguno. Es interesante que a veces los desarrolladores hasta han tenido la opción de modificar el lenguaje para adaptarlo a la biblioteca [Ste­95].

      El común denominador de todos estos esfuerzos es que no implementan el polimorfismo uniforme, sino más bien parametrización por medio de plantillas, u obligan al programador cliente de la bibioteca a prescindir de la verificación fuerte de tipos, pues los contenedores almacenan referencias (punteros) a los objetos. O sea que, si se escoge usar una biblioteca eficiente (plantillas), hay que renunciar al polimorfismo uniforme, mas si se escoge la generalidad de un contenedor heterogéneo, entonces hay que renunciar a la verificación fuerte de tipos. Por eso en esta investigación se busca lograr la combinación de ambas cualidades: la eficiencia de las plantillas con la generalidad del polimorfismo uniforme.

      Como ya hay mucho terreno avanzado en la implementación de contenedores, en esta investigación se hará especial énfasis en la implementación de algoritmos polimórficos, sin por ello descuidar la de contenedores.

II.2 Perspectiva teórica

      Al usar parametrización el programador puede escribir algoritmos que no dependan del tipo de los datos manipulados, lo que evita duplicar código fuente. En el contexto de los Tipos abstractos de datos contenedores (ADT: Abstract data type), la parametrización es el mecanismo que permite que el contenedor sea independiente de los objetos que contiene, pues con un solo módulo es posible obtener contenedores para elementos de tipos diferentes. Con base en el mismo código fuente parametrizable es posible obtener un árbol de enteros, de personas, o de listas de valores booleanos. La parametrización sirve para definir un nuevo ADT contenedor en términos del ADT contenido; este último tipo de datos es el parámetro de la definición. Si Pascal fuera capaz de parametrizar contenedores directamente, sería posible escribir declaraciones como la siguiente, que define las listas de números enteros y de árboles de reales "TLint" y "TLreal":

   VAR
     TLint   : TList< INTEGER >;
     TLTreal : TList< TTree< REAL > >;

TYPE
  <TSort> = ARRAY[Low<>..High<>] OF <TElem>;

PROCEDURE Sort_<TSort>(    { ADH }
  {?} VAR A :  <TSort>     { Arreglo a ordenar }
);
{ RESULTADO
  Ordena el vector "A" con el método de la búrbuja. }
VAR
  j,k     : INTEGER;
  temp    : <TElem>;
  interch : BOOLEAN;
BEGIN { Sort_<TSort> }
  k := 1;
  REPEAT
    interch := FALSE;
    FOR j := Low<A> TO High<A> - k DO BEGIN

      IF (A[j+1] <= A[j]) THEN BEGIN
        interch := TRUE;

        temp   := A[j+1]; { los intercambia: }
        A[j+1] := A[j];
        A[j]   := temp;   { A[j] <==> A[j+1] }

      END;
    END;
    INC(k);
  UNTIL NOT interch;
END;  { Sort_<TSort> }

      El ejemplo clásico de parametrización de procedimientos es la rutina Sort(), que ordena un vector independientemente del tipo de datos que contenga. En la Figura 1 está una versión simplificada de Sort(), expresada como una plantilla escrita en pseudo-Pascal. Esta implementación parametrizable del procedimiento Sort() puede ordenar cualquier arreglo, independientemente de las cualidades del vector (tipo de elemento contenido, dimensión, cantidad de elementos, algoritmo para comparar los elementos). Los parámetros que deben ser definidos por el programador para usar la función Sort() se encuentran encerrados entre paréntesis angulares: <TSort>, <TElem>, Low<A> y High<A>. Estos dos últimos sirven para definir el rango del vector. Además, el operador "<=" también es un parámetro de esta plantilla, pues es el que se usar para comparar a cualesquiera dos elementos del vector.

      Se llama Instanciación al proceso de especializar una plantilla de código parametrizable a un tipo. Para instanciar basta copiar el código de la plantilla y sustituirle las hileras por los nombres adecuados de las constantes y los tipos de datos. En el caso de los tipos, la instanciación ocurre cuando se declara la variable, y se obtiene así una instancia. El término "parametrización" nace de instanciar de esta forma los tipos, que son parámetros en las plantillas de código.

      Pese a que no hay duplicación de código fuente cuando se usa parametrización, el resultado de compilar un algoritmo parametrizable produce código objeto diferente para tipos de datos diferentes, pues lo usual es que el compilador genere una copia completa de toda la implementación del contenedor para cada uno de los tipos parametrizados (de aquí viene el nombre "plantilla" que se usa para denotar a la facilidad de parametrización de C++).

      Es fácil compartir el código objeto si lo que cada instancia del contenedor contiene es una referencia, -puntero-, al elemento almacenado, pues lo usual es que todos los punteros tengan el mismo tamaño, independientemente del tamaño del objeto a que apuntan. Este es el enfoque que se ha usado para CLU [LG­86] o para Napier88 [MDC­91], y para los lenguajes que permiten polimorfismo uniforme, en que se usa la "Semántica de referencia". En esos lenguajes, en casi todos los casos, los objetos son punteros al lugar en la memoria en que su valor está almacenado. Cuando el contenedor almacena los objetos, y no referencias a ellos, compartir el código de las operaciones es más difícil porque los objetos diferentes tienen tamaños diferentes y requieren ser manipulados usando operaciones diferentes.

      Si se usa semántica de referencia para implementar la parametrización, no hace falta duplicar el código objeto de cada algoritmo, pero a cambio el acceso a cada dato es más lento, pues hay que derreferenciar un puntero para llegar a su valor. Además, cada dato ocupa más espacio de memoria, pues al usado para almacenar su valor hay que agregarle el que ocupa el puntero que le referencia. Por eso en este trabajo se hacen esfuerzos por implementar la parametrización sin recurrir a la semántica de referencia.

      De acuerdo a [MDC­91] el "Polimorfismo" en un lenguaje de programación "es la habilidad de escribir programas que son independientes de la forma de los objetos que manipulan". Es un concepto mucho más amplio que la unión de la parametrización con la herencia, pues el polimorfismo hace al lenguaje mucho más expresivo. Por eso en [CW­85] se le llama "Polimorfismo de inclusión" a la herencia y en [MDC­91] se afirma que la parametrización que ofrecen tanto Ada como C++ apenas es un truco para implementar el polimorfismo, que ellos llaman "Polimorfismo textual" (pg 344). En estos dos lenguajes, la parametrización es una forma restringida del "Polimorfismo paramétrico" de [CW­85] (pg 475).

void qsort(
     void *base,
     size_t nelem,
     size_t width,
     int (*fcmp) (const void *, const void *),
     int (*fswp) (const void *, const void *)
);

      En la práctica, el concepto de polimorfismo tiene dos significados. El primero ya se ha explicado, y se deriva de la práctica de usar punteros a funciones, como en el caso del procedimiento qsort() de la Figura 2. En este caso un programa o un módulo es polimórfico cuando usa punteros a funciones para ocultar el proceso que las rutinas realizan sobre los datos; puede verse la parametrización como un camino para llegar al polimorfismo, pues la parametrización se puede implementar usando polimorfismo.

      El segundo significado de polimorfismo se usa en el contexto de la programación orientada a los objetos (OOP: Object Oriented Programming), cuando se dice que un método es polimórfico si puede ser invocado indirectamente por medio de un puntero que está almacenado dentro de cada instancia del objeto; este es el polimorfismo de inclusión de [CW­85]. Usando la terminología de C++, los objetos polimórficos son los que tienen "Métodos virtuales", también llamados "Funciones virtuales". Cuando se invoca un método virtual se dice que se ha usado "ligamiento tardío" (late binding), "ligamiento dinámico" (dynamic binding) o "ligamiento en tiempo de ejecución" (run-time binding).

      Una muestra de que el polimorfismo es un concepto mucho más amplio que la parametrización es el del lenguaje ML [Mil­84], o el de Miranda [Tur­86], que cuentan con "Polimorfismo uniforme", que garantiza que todos los tipos siempre compartan la misma implementación de cualquier algoritmo polimórfico. Esto no ocurre se usan los paquetes genéricos de Ada, o las plantillas de C++, pues en estos lenguajes al instanciar un procedimiento polimórfico el compilador genera una copia del código para cada tipo (de aquí el nombre despectivo de polimorfismo de editor de textos para la genericidad [MDC­91], pg 369).

      Los lenguajes C, C++ y Pascal no incorporan las formas más poderosas de polimorfismo porque el costo que se paga por esa gran flexibilidad, en tiempo de ejecución, es demasiado alto, pues las formas más abstractas de polimorfismo se implementan usando punteros, lo que aumenta tanto el tamaño de las variables como el tiempo de ejecución de los programas. Esta pérdida de eficiencia es inaceptable para muchos programadores C++, pese a que para bastantes programadores no tiene sentido siquiera entender qué es el polimorfismo uniforme. De todas formas, siempre habrá casos en que contar con la expresividad adicional que brinda esta técnica de programación justifique el costo de aprender a usarla.

      En el contexto de los lenguaje Pascal y C (o C++), diseñados para producir programas de alta eficiencia, cuando se habla de polimorfismo es porque internamente (a nivel de implementación) se usan referencias a objetos en lugar de los objetos en sí. Una forma simple de entender el polimorfismo es pensar que "polimorfismo" significa "uso de punteros". O sea que, cuando se usa polimorfismo, no se manipula al objeto, sino que se usa una referencia al objeto, que es un puntero. Con frecuencia se confunde la parametrización con el polimorfismo, pues la idea de usar punteros a funciones como vehículo para implementar la parametrización no es nueva. Por ejemplo, ya en 1986 se hablaba de cómo hacerlo [CI­86], aunque la técnica usada es bastante restrictiva [Gol­86].

      En un plano más abstracto, el polimorfismo es un concepto muy similar a la parametrización. Como se sobreentiende que al usar polimorfismo internamente el compilador recurre a punteros y referencias [MDC­91], que es lo contrario de lo que generalmente ocurre al usar parametrización [Str­89], los objetos polimórficos pueden tener comportamientos mucho más variados que los que solo están parametrizados. Por ejemplo, una lista polimórfica puede contener varios elementos, cada uno de un tipo diferente, mientras que la lista parametrizada solo puede contener elementos de un mismo tipo (en particular, una lista polimórfica podría contener a su vez otra lista, o varios elementos de tipos diferentes).

VAR      { Listas heterogéneas polimórficas: }
  Lm1 : TList = ((a,b,c), [1.2.3.4], "hilera", ("algo",1,3));
  Lm2 : TList =  (a,b,c);

VAR      { Listas parametrizadas: }
  Lp1 : TList<INTEGER> = (1,2,3,4,5,6);
  Lp2 : TList<CHAR>    = ('c','h','a','r');

      En la Figura 3 se compara la expresividad que se logra con el polimorfismo, pues la lista "Lm1" tiene elementos que son de tipos muy variados (listas, arreglos, números, hileras), mientras que las listas parametrizadas "Lp1" y "Lp2" son homogéneas, pues todos sus elementos son del mismo tipo. Para manipular la lista "Lm1" el programador necesita que el lenguaje le provea de mecanismos para averiguar en tiempo de ejecución el tipo de cada objeto, para que pueda aplicarle las operaciones que le son válidas. Desde la perspectiva de los contenedores heterogéneos, el polimorfismo es una facilidad de abstracción más general que la parametrización.

II.3 Objetivos

II.3.a Objetivos generales

• Mejorar la eficiencia de los algoritmos más importantes que requieren polimorfismo uniforme, dentro de las restricciones semánticas de los lenguajes convencionales Pascal, C y C++, sin sacrificar la verificación fuerte de tipos, y superando el rendimiento que se obtiene al usar el ligamiento dinámico de la programación orientada a los objetos.

II.3.b Objetivos específicos

• Seleccionar e implementar al menos tres algoritmos representativos que permitan medir la eficiencia de la técnica de polimorfismo desarrollada en el proyecto.
• Implementar una pequeña biblioteca de contenedores polimórficos, que incluya por lo menos a la lista y el grafo, dentro de las restricciones de los lenguajes más importantes en este momento: Pascal, C y C++.
• Medir el rendimiento de los algoritmos implementados para compararlo con el de la biblioteca STL de C++, que es el estándar industrial actual.

      En este proyecto se tratará de reclutar estudiantes, preferiblemente de la Maestría en Computación e Informática de la ECCI, para que colaboren en esta investigación. También busca apoyar ayudar a la formación del Centro de Investigación en Computación de la ECCI, promoviendo la investigación en una de las áreas más importante de la computación: la programación de computadores.

II.4 Procedimiento y metodología

      En lo posible, se tratará de producir resultados para el lenguaje Pascal, que no tiene plantillas, aunque seguramente el éxito se alcanzará usando el lenguaje C++, que tiene construcciones sintácticas más avanzadas. Siempre es saludable tratar de lograr resultados usando un mínimo de recursos, pues de esa manera se llega a la eficiencia, por lo que como estrategia de investigación siempre se tratará de lograr resultados primero en Pascal, y luego en C y C++. Será durante el proceso de investigación cuando se pueda determinar si la expresividad de Pascal no es suficiente para alcanzar los objetivos propuestos. La gran ventaja de lograr resultados en Pascal que es que podrán ser usados para los cursos básicos en la ECCI.

      La primera labor a realizar es probar varias formas de implementar el polimorfismo uniforme, usando como base la tecnología que ya se ha desarrollado, principalmente examinando la biblioteca BIDS de Borland, y la biblioteca estándar STL para C++. Sin embargo, también es importante echarle un vistazo a la biblioteca LEDA, pues incluye algoritmos para grafos.

      Luego hay que entrar a una etapa es de consolidación, en la que se busca implementar varios de los algoritmos escogidos en la primera etapa. Posiblemente en esta etapa sea necesario hacer y rehacer varias veces el trabajo pues, infortunadamente, cuando se construyen artefactos de programación es usual iterar varias veces hasta encontrar una implementación adecuada. En esta etapa también hay que escoger los algoritmos a implementar; esta escogencia se hará con base en la información recolectada a lo largo del proyecto, por lo que en esta propuesta no se puede predecir cuáles algoritmos conviene estudiar.

      Cabe destacar que el trabajo de implementar algoritmos no se reducirá a implementar contenedores, sino otros algoritmos en general. Por ejemplo, no será suficiente para cumplir con los objetivos del proyecto implementar el contenedor polimórfico lista, sino que también hay que estudiar algoritmos como el qsort() de la Figura 2.

      Al final del proyecto se hará una evaluación retrospectiva, en que se buscará determinar si el trabajo realizado es suficiente, o si por el contrario han quedado por fuera algoritmos importantes. En esta etapa se usará como punto de evaluación la experiencia documentada en el uso de la biblioteca STL de C++, la que todavía no es muy conocida por los programadores.

      La eficiencia en computación se determina midiendo la cantidad de recursos que utiliza un algoritmo. Lo usual es medir dos variables: el espacio (cantidad de memoria utilizada) y el tiempo (esfuerzo requerido para realizar una tarea). Como los algoritmos sobre los que se trabajará ya existen, pues no es el fin de esta investigación desarrollar nuevos algoritmos sino implementar los ya conocidos de mejor manera, la forma de medir la eficiencia consiste en comparar los algoritmos programados de forma tradicional, con los producidos en el proyecto. Al cotejar tiempos de ejecución y uso de espacio será posible determinar cuán eficientes son los algoritmos producidos en el proyecto.

      Pero también la eficiencia puede medirse de otra manera, que es menos objetiva, porque no se puede hacer mecánicamente. Esta otra forma de eficiencia consiste en evaluar la "belleza" o "elegancia" con que se ha implementado un algoritmo. En esto el investigador principal de este proyecto ya ha trabajado en el pasado, en que produjo el artículos "Convenciones de Programación para Pascal" [DiM­88b]. Muchas personas opinan que no hace falta hacer este tipo de estudio, pues si "ya funciona no hay que arreglarlo" (if it ain't broken; don't fix it!). Pero siempre es bueno analizar, aunque no con gran detalle, este aspecto de la implementación de un algoritmo. Por eso, en este proyecto se usará un poquito de esfuerzo para determinar si los algoritmos producidos son más elegantes, más simples, o menos engorrosos, aunque el esfuerzo más importante se dedicará a medir eficiencia cuantitavivamente. Estas comparaciones se harán con la versión de cada algoritmo implementado usando parametrización.

      La tecnología STL será un punto de guía durante todo el proyecto, y las experiencias reportadas por otros investigadores y por la industria moldearán el desarrollo de esta investigación. En la última etapa, a la luz del trabajo realizado, será posible determinar si este proyecto se transforma en un Programa de Investigación que pase a formar parte del Centro de Investigación en Computación de la ECCI, o si más bien conviene invertir esfuerzos en otros trabajos.

II.5 Duración del proyecto

II.6 Cronograma

      El proyecto terminará en con el siglo, al finalizar el año 1999; ya para ese momento habrá suficiente trabajo avanzado como para determinar si vale la pena ampliarlo, o transformarlo en un programa de investigación.

      En amena conversación el Director de la ECCI, profesor Marcelo Jenkins, PhD. y el investigador principal del proyecto, profesor Adolfo Di Mare, acordaron que lo que más conviene es que este proyecto se ejecute en tres semestres, para acoplarlo con los planes generales de investigación de toda la ECCI. Originalmente se había planeado insertar este proyecto en el PIBD: Programa de investigación en bases de datos (326-97-902), que dirige el profesor José Ronald Argüello, pero a fin de cuentas se determinó que conviene más a la Escuela que este proyecto se desarrolle en un corto plazo.

      Los resultados de este proyecto serán, principalmente, publicaciones, preferiblemente en el idioma inglés. Se espera producir una publicación por semestre, aunque es muy posible que al finalizar el proyecto haya más de tres.

      Como productos quedarán las bibliotecas de programas producidas, junto con su documentación escrita en formato HTML. Una versión inicial de las bibliotecas será entregada al finalizar el segundo semestre de ejecución del proyecto, a mediados del año 1999.

III Beneficios derivados de la ejecución del proyecto

III.1 Beneficios materiales

III.2 Beneficios institucionales

III.3 Beneficios académicos

• Se fortalecerá el PIBD, que es una iniciativa que desde hace muchos años impulsan los profesores Argüello y Di Mare.
• En estos momentos, la investigación de los profesores de la ECCI se realiza principalmente como apoyo a otras unidades académicas, por lo que la ejecución de este proyecto refuerza la investigación en computación, que es un quehacer fundamental de la Escuela.
• Este proyecto tiene posibilidades de crecer luego hasta ser un programa de investigación, pues siempre es necesario encontrar mejorar la eficiencia de los programas, lo que a mediano plazo sirve para consolidar la investigación en la ECCI.
• Este proyecto sirve para apoyar la creación del Centro de Investigación en Computación, que necesita la Universidad para conseguir recursos externos dirigidos al desarrollo tecnológico de la computación.

IV Presupuesto y recursos

      Además, el investigador principal cuenta con un computador Pentium bastante completo, que usará para escribir programas o artículos. Ya cuenta también con los compiladores necesarios para trabajar, y mediante Internet se pueden obtener otros recursos que puedan requerirse para realizar el trabajo.

Agradecimientos

Bibliografía referenciada

Indice [I] Elementos básicos [1] Título del proyecto de investigación [2] Título del programa al cual pertenece el proyecto [3] El programa está inscrito en la Vicerrectoría de Investigación [4] Unidad base a la que pertenece el investigador principal [5] Unidad de adscripción del proyecto [6] Descriptores [7] Tipo de investigación [8] Protección de la propiedad intelectual [9] Información acerca de los investigadores [10] Información relacionada con la propuesta [11] Información acerca de los estudiantes que participan en el proyecto [II] Plan de investigación [1] Antecedentes [a] Planteamiento del problema [b] Relevancia académica [c] Estado actual del conocimiento [2] Perspectiva teórica [3] Objetivos [a] Objetivos generales [b] Objetivos específicos [4] Procedimiento y metodología [5] Duración del proyecto [6] Cronograma [III] Beneficios derivados de la ejecución del proyecto [1] Beneficios materiales [2] Beneficios institucionales [3] Beneficios académicos [IV] Presupuesto y recursos Agradecimientos Bibliografía referenciada 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: Polimorfismo uniforme más eficiente - Propuesta de Investigación, Proyecto N° 326-98-391, Escuela de Ciencias de la Computación e Informática, UCR 1998.       http://www.di-mare.com/adolfo/inv/polimefc.htm
Internet:	http://www.di-mare.com/adolfo/inv/polimefc.htm
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, Junio 1998
Visitantes:

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1998
Derechos de autor reservados © 1998