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

Polimorfismo uniforme más eficiente

Propuesta de Renovación 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

Servicios del sistema operativo Contenedores reutilizables Linux

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 fue aprobado con el número 326­98­391, según consta en la nota VI-DGI-3231-98 de la Vicerrectoría de Investigación, con vigencia desde 1 de agosto de 1998 hasta el 31 de diciembre de 1999, con una carga de 1/3 TC para el investigador principal. El presupuesto docente es aportado por la ECCI por la duración total del proyecto, que es de tres semestres.

      El profesor Di Mare es el 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.

      En esta solicitud de renovación se solicita extender el proyecto por tres semestres adicionales, de manera que la renovación comience ajecutarse el primer semestre del año 2000, y termine con el primer semestre del año 2001 (antes de que comiencen las lecciones del segundo semestre del año 2001).

      El presupuesto de trabajo es mínimo porque se se usarán los recursos disponibles en la ECCI para su desarrollo, aunque se solicita un presupuesto para compra de materiales pequeñas, como papel, fotocopias, etc.

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
[DiM­99a]	Di Mare, Adolfo: C Iterators, Reporte Técnico ECCI­99­01, Universidad de Costa Rica, Enero 1999.       http://www.di-mare.com/adolfo/p/c-iter.htm
[DiM­99b]	Di Mare, Adolfo: C Parametrized Lists, Reporte Técnico ECCI­99­02, Universidad de Costa Rica, Abril 1999.       http://www.di-mare.com/adolfo/p/c-list.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.

      Como parte del desarrollo del proyecto de investigación se ha definido una arquitectura de programación que permite reutilizar los módulos de una biblioteca de contenedores, pero con la particularidad de que la reutilización se hace a nivel de lenguaje de máquina, y no a nivel del código fuente de los algoritmos. Para lograrlo, se ha cambiado levemente la forma en que se representan los contenedores, siguiendo un esquema como el que se muestra en la Figura 4. Lo novedoso de este enfoque es que, en lugar de enlazar nodos mediante punteros, lo que se hace es intereconectar con punteros los campos de enlace del contenedor, como se explica en detalle en el artículo "C Parametrized Lists" [DiM­99b].

II.3 Objetivos

II.3.a Objetivos generales

• Contruir una biblioteca con una implementación eficiente de los contenedores "lista", "pila", "cola" y "montículo" (heap), en donde la reutilización se de a nivel de lenguaje de máquina, y no a nivel del código fuente de los algoritmos, de manera que estos contenedores sean un servicio adicional del sistema operativo.

II.3.b Objetivos específicos

• Definir e implementar todas las operaciones esenciales para el contenedor "lista" reutilizable.
• Definir e implementar todas las operaciones esenciales para el contenedor "pila" reutilizable.
• Definir e implementar todas las operaciones esenciales para el contenedor "cola" reutilizable.
• Definir e implementar todas las operaciones esenciales para el contenedor "montículo" (heap) reutilizable.
• Transformar las implementaciones de bibliotecas para que puedan ofrecerse como servicios del sistema operativo Linux.
• Escribir los manuales de uso de las bibliotecas.

      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

      Los sistemas operativos actuales (Win.NT & Linux) están escritos, primordialmente, en el lenguaje C (no C++), por lo que será necesario evaluar cuidadosamente si conviene realizar las implementaciones en el lenguaje C, pese a que tiene mucho menos poder expresivo que C++. De todas maneras, será necesario construir interfaces C++ para el código objeto final. Como estrategia, es mejor implementar primero todos los servicios para el contenedor "lista", para verter toda la experiencia desarrollada esa labor en las implementaciones de los otros contendores ("pila", "cola", "montículo").

      Para tener una aplicación de referencia que sirva para poner los pies sobre la tierra, y no terminar estudiando formas abstractas de polimorfismo que no sirven en la práctica, se estudiará la biblioteca de clases desarrollada por el profesor José Ronald Argüello, en su proyecto de investigación "Extracción inductiva de reglas de asociación en grandes bases de datos (326-97-316)". De esta forma los resultados obtenidos serán insumos directos al programa de investigación en que está incluido el proyecto. Esta labor ser hará cuando el proyecto haya avanzado un poco, para dar tiempo a que hay una colaboración estrecha entre el profesor Argüello y el profesor Di Mare.

      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 es necesario hacer ajustes importantes.

II.5 Duración del proyecto

II.6 Cronograma

      El cronograma se ha confeccionado con una granularidad de un trimestre. Una "X" en la columna indica que se trabajará en la actividad respectiva. Algunas labores se realizarán en forma concurrente, y en la etapa final se revisará todo el trabajo realizado.

      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.

III Beneficios derivados de la ejecución del proyecto

III.1 Beneficios materiales

      Existe la posibilidad de que la Universidad pueda obtener algún beneficio material si la empresa Microsoft, dueña del sistema operativo Win.NT, decide incorporar la tecnología desarrollada en este proyecto en sus programas; es deseable que la empresa Microsoft apoye la investigación en la Universidad de Costa Rica, como reconocimiento a la incorporación en sus productos de las tecnologís desarrolladas en este proyecto. Será necesario esperar a que los productos propuestos en este trabajo existan para definir qué estrategia seguir en este respecto. Por lo pronto, todos los aportes se harán para el sistema operativo Linux, que es de dominio público, lo que evita solicitar permisos o contraer compromisos para usarlo como plataforma de trabajo.

III.2 Beneficios institucionales

III.3 Beneficios académicos

• 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.
• Se fortalecerá el PIBD, "Programa de investigación en bases de datos", dirigido por el profesor José Ronald Argüello, que ha sido establecido desde el año 1997 la Escuela de Ciencias de la Computación e Informática [ECCI].
• Es muy posible que los resultados derivados de esta investigación puedan usarse en los cursos de la carrera de Computación e Informática, especialemente en los cursos CI-1303 Estructuras de Datos y Análisis de Algoritmos, y en CI-1201 Programación II.
• 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.

      Es deseable, y muy importante, contar con un asistente de investigación, quien pueda colaborar durante todo el desarrollo del proyecto. Aunque este apoyo no es un requisito indispensable para alcanzar las metas propuestas, pues al no tener este apoyo lo que ocurrirá es que la amplitud y profundidad del trabajo realizado será menor, vale la pena que el investigador principal del proyecto no se vea obligado a realizar labores de menor nivel intelectual, que lo distraen de profundizar en la investigación.

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 Renovación 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/polirenv.htm
Internet:	http://www.di-mare.com/adolfo/inv/polirenv.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 1999
Visitantes:

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