                    Prueba interactiva de ADTs

                               por

                          Adolfo Di Mare

                    Reporte Tcnico ECCI-94-01
                       Proyecto 326-93-256
                           Revisin 1.0


Resumen:
=======

Se discute  los programas  UseList.pas y  UseTree.pas, que  sirven 
para probar interactivamente los Tipos Abstractos de Datos  (ADTs) 
TList y TTree.   Estas implementaciones se  han realizado para  el 
ambiente Turbo Pascal v5.0, aunque para trabajar con ellas es  ms 
cmodo usar la versin v6.0 o una posterior.


Abstract:
========

The programs UseList.pas  and  UseTree.pas  are  discussed.  These 
programs are  usefull to  test interactively  the TList  and TTRee 
Abstract Data Types (ADTs).  These implementations have been  made 
for the Turbo Pascal v5.0  environment, but it is less  cumbersome 
to use version v6.0 or later to work with them.


Esta investigacin se realiz dentro del proyecto de investigacin 
326-93-256 "DBgen: Generacin de Sistemas  a partir de su Base  de 
Datos" inscrito ante  la  Vicerrectora  de  Investigacin  de  la 
Universidad  de  Costa  Rica.   La  Escuela  de  Ciencias  de   la 
Computacin e Informtica tambin ha aportado fondos para realizar 
este trabajo.


                    Prueba interactiva de ADTs
                    ==========================


     El   aprendizaje   de  la   tecnologa  de   Programacin  de 
Computadores se logra siguiendo prcticas artesanales: el aprendiz 
debe ver al maestro realizar una obra tras otra, hasta que llega a 
dominar  la tcnica y puede dedicarse  a trabajar solo. Por eso el 
estudiante  de  computacin necesita  estudiar muchos  ejemplos de 
programas para dominar la Programacin.

     Como la  programacin es  una tecnologa  todava muy  joven, 
todava   no   se   conocen   frmulas   que   permitan   abaratar 
significativamente  la  construccin de  programs.  Aunque  se han 
dado muchos avances, la  verdad  es  que  todava  el  proceso  de 
programacin es bastante  difcil, y requiere  de un gran  cuidado 
por parte del programador. Por eso es que a partir de la dcada de 
los aos setenta el costo ms grande en el desarrollo de  sistemas 
de computacin es el diseo e implementacin de programas.

     Sin embargo, se han dado grandes avances en programacin.  El 
primero fue la introduccin del lenguaje Ensamblador, que liber a 
los programadores de la  incomodidad de programar usando  nmeros, 
que es lo nico que entienden las computadoras digitales. Luego se 
desarrollaron  los   compiladores,  los   que  permiten   expresar 
algoritmos usando una notacin simblica.

     Tanto  los ensambladores como  los compiladores aumentaron en 
un orden de magnitud la eficacia de los programadores: se necesit 
la dcima  parte del  esfuerzo para  construir el  mismo programa.  
Sin embargo, como los costos del equipo de cmputo decrecieron  en 
varios  rdenes  de  magnitud,  los  sistemas  computacionales  se 
hicieron  mucho ms complejos  de lo que es  manejable por un solo 
programador.

     Ante esta realidad, se hizo necesario introducir los  equipos 
de programacin, formados por varios programdores quienes cooperan 
para producir un  sistema  computacional.  Pero  al  tener  varias 
mentes trabajando juntas se hizo necesario encontrar mtodos  para 
coordinarlos.   Por   eso  nace   la  Programacin   Modular,  que 
bsicamente aplica  el principio  de Divide  y Vencers  (Divide & 
Conquer) a la construccin  de programas.  Entonces los  programas 
dejaron   de   ser  algoritmos   monolticos  y   pasaron  a   ser 
conglomerados de  mdulos  cuidadosamente  interrelacionados  para 
cumplir un objetivo.

     A  principios  de la  dcada de  los aos  ochenta surgi  un 
refinamiento  de  la  Programacin  Modular  que  ahora   llamamos 
Programacin por Objetos (Objecto Oriented Programming: OOP),  que 
es un  refinamiento de  la programacin  modular. Al  principio un 
mdulo era concebido como un algoritmo autocontenido, pero con  el 
correr del tiempo se fue haciendo necesario encapsular no slo los 
algoritmos,  sino  tambin   las   estructuras   de   datos.    Se 
distinguieron as dos tipos de mdulos: los procedimentales que ya 
eran conocidos, y  los Tipos Abstractos  de Datos que  sirven para 
describir  no los algoritmos del  programa, sino los datos.  Desde 
un punto  de  vista  pragmtico  tiene  mucho  sentido  crear  las 
abstracciones para procedimientos y  para datos, pues un  programa 
es un algoritmo que manipula datos.

     Desgraciadamente,  tanto la  la Abstraccin de  Datos como la 
Programacin por Objetos no deparan ms de un orden de magnitud en 
la eficacia del programador para construir programas. Se han hecho 
otros intentos,  pero cada  vez ocurre  ms que  el potencial  del 
equipo de cmputo es mucho ms grande que la capacidad que tenemos 
para  programarlo.   Pese  a  esta deficiencia,  lo cierto  es que 
cualquier   programador   necesita   dominar   las   tcnicas   de 
modularizacin conocidas para desempear decorosamente su trabajo, 
pues si las desconoce entonces es muy poco productivo.

     Hay muchas  maneras  de  aprender  a  partir  en  mdulos  un 
programa  complejo.  La que ms  gusta ensear a las Universidades 
es   mostrarle  al  estudiante  ADTs   para  que  luego  l  pueda 
modularizar sus propios programas.  Los ADTs ms importantes  son, 
sin lugar a dudas, el Arreglo, la Lista y el Arbol.

     Como el ADT Arreglo es muy importante, todos los lenguajes de 
alto   nivel   cuentan   con   construcciones   sintcticas   para 
manipularlo.  Sin embargo,  la  lista  y  el  rbol  tienen  menos 
aplicacin,  por  lo  que  generalemnte  se  estudian  en   cursos 
avanzados, principalemente en Estructuras de Datos.

     En este escrito se discute la implementacin de los programas 
UseList.pas  y  UseTree.pas,  que  se han  programado para  que el 
estudiane  puede  experimentar con  varias implementaciones  de la 
lista y el rbol.  La principal ventaja de estos programas es  que 
el estudiante puede utilizar  el depurador simblico del  ambiente 
de  programacin Turbo Pascal  para ver, paso a  paso, cmo es que 
estn implementaados estos ADTs, lo que acelera aprendizaje de los 
conceptos bsicos de modularizacin de programas.

     Es difcil que pueda llegarse a ensear programacin sin usar 
el mtodo  artesanal que  ahora usamos.   El Programador,  como el 
Arquitecto, debe aprender  a  acomodar  muchos  objetos  complejos 
respetando  muchas restricciones.  A pesar de  que la Arquitectura 
existe desde hace  miles  de  aos,  todava  los  estudiantes  de 
Arquitectura aprenden a disear practicando  mucho a la par de  su 
maestro. Seguramente el da  que los computadores puedan  realizar 
suplantar a los  Arquitectos ser el  da que tambin  suplanten a 
los programadores. Pero ese da todava no est cerca.


Implementacin
==============

     Los  programas  UseList.pas  y  UseTree.pas  usan  la  unidad 
Test.pas  para prueba de  ADTs, la que se  describe en un artculo 
aparte. La principal ventaja de Test.pas es que permite definir la 
accin  que  se  efectuar  sobre  el  ADT  junto  al  cdigo  que 
implementa  la  accin.  Por  ejemplo, en  UseList.pas aparece  el 
siguiente procedimiento:

     PROCEDURE List_Count;
     { RESULTADO
       Despliega la cantidad de elementos
       que contiene la lista. }
     BEGIN { List_Count }
       IF Test.Display THEN BEGIN
         Test.Say('Cantidad de elementos de la lista');
         EXIT;
       END;

       Write(
         'La lista contiene ',
         List.Count(GLOBAL.L):1,
         ' elementos');

       Test.KeyDelay(3);
     END;  { List_Count }

     El   procedimiento   List_Count   tiene   dos   partes   bien 
diferenciadas. La primera es la hilera que aparece como  argumento 
de la  funcin Test.Say(),  en que  se describe  la accin  que el 
procedimiento ejecuta.  En la segunda parte del procedimiento est 
el cdigo que implementa la accin.

     Las funciones Test.Display, Test.Say() y Test.KeyDelay()  son 
parte de los servicios que la unidad Test.pas provee. Esta  unidad 
se encarta de construir un men con todas las hileras que aparecen 
como argumento de Test.Say() en el programa, y tambin se  encarga 
de invocar a  la  accin  correspondiente  cuando  el  programador 
selecciona una opcin del men.

     Todas las opciones del  men que despliega tanto  UseList.pas 
como UseTree.pas actan sobre una variable global que tiene varios 
campos.  En el caso de List_Count  esa variable se llama GLOBAL, y 
tiene un campo llamdo "L" que es la lista sobre la que se trabaja. 
Cada  accin  que toma  el programa  bajo el  comando del  usuario 
resulta en un cambio en la variable GLOBAL.

     La implementacin de  UseList.pas  y  de  UseTree.pas  es  un 
conjunto de procedimientos  como List_Count, cada  uno de los  que 
ejercita  una  o varias  de las  operaciones de  los ADTs  TList y 
TTree. Tambin intervienen otros mdulos, como los iteradores, los 
que complementan a los ADTs TTree y TList.


TList, TTree y TElem
====================

     Una clasificacin simple de los Tipos Abstractos de Datos los 
divide en  dos tipos  bsicos: los  simples o  elementales, y  los 
contenedores. Un ADT  es un contenedor  si contiene a  otros ADTs. 
Los contenedores ms importantes son tres:

     1.- El ADT Arreglo [ARRAY]
     2.- El ADT Lista   [List.pas]
     3.- El ADT Arbol   [Tree.pas]

     Los ADTs contenedores son  ms complejos que los  elementales 
porque  deben  tener  todas  las  operaciones  que  cualquier  ADT 
elemental tiene, y adems necesitan las operaciones para manipular 
al ADT elemental que contienen. Por eso es ms til estudiar a los 
ADTs  contenedores que  a los elementales.   Para este fin  se han 
construido  dos  programas: UseList.pas  permite manipular  al ADT 
TList, y UseTree.pas trabajo con el ADT TTree.

     La implementacin de cada ADT consta de dos unidades  Pascal, 
lo  que  incrementa la  modularidad. La  primera contiene  todo el 
cdigo  que implementa al contenedor  (TList y TTree).  La segunda 
tiene  todas  las operaciones  del ADT  elemental contenido  en el 
contendor  (TElem).  El  ADT elemental puede  ser, a su  vez, otro 
contenedor.  De hecho, los programas UseList.pas y UseTree.pas han 
sido construidos de  forma puedan trabajar  con Listas de  Listas, 
Arboles de Listas, Listas de Arboles de Listas, etc.  Para esto es 
muy importante que cada ADT  contenedor tenga definida, a su  vez, 
las operaciones que  usa  el  contenedor  para  manipular  al  ADT 
elemental que contiene.

     Los programas  UseList.pas y  UseTree.pas han  sido diseados 
para  mostrar  la modularidad  que se  obtiene al  separar en  dos 
undidades la implementacin de un ADT contenedor. Para esto se han 
escrito  cuatro versiones  del ADT elemental  que pueden manipular 
UseList.pas y UseTree.pas:

     - ElemC.pas       Letra
     - ElemI.pas       Nmero
     - ElemZ.pas       Nmero con memoria dinmica asociada
     - Rational.pas    Nmero racional
Cada uno de estos ADTs tiene todas las operaciones elementales que 
necesita el ADT contenedor  para manipular su elemento  contenido. 
Estas operaciones son las siguientes:

     - Init    - Copy     - Load     - OK
     - Clear   - Move     - Store    - Fix
     - Done    - Equal

Cada una de estas implementaciones del ADT elemental se encuentran 
en un  el archivo  que lleva  un nombre  diferente, pero  en todas 
estas   implementaciones   se   usan   los   mismos   nombres   de 
identificadores,  que  son  "Elem"  para el  nombrar la  unidad, y 
"TElem" para nombrar el tipo de datos.

     El  programa  UseList.pas necesita  una unidad  que se  llama 
Elem.pas,  que contiene  el ADT TElem  con que trabaja.   Para que 
UseList.pas use  una lista  de nmeros  hay que  crear el  archivo 
Elem.pas de forma  que contenga la  implementacin que est  en el 
archivo  ElemI.pas,  que  es  la implementacin  del ADT  TElem de 
nmeros enteros.  La manera rpida obtener esta unidad Elem.pas es 
copiar  el  archivo  ElemI.pas  sobre  el  archivo  Elem.pas.   Al 
recompilar UseList.pas  con Elem.pas  se obtendr  una versin  de 
UseList que manipula nmeros enteros.  El comando DOS para obtener 
esta versin de Elem.pas es el siguiente:

     C:> copy ElemI.pas Elem.pas

Si en lugar de usar una lista nmeros se quiere obtener la versin 
de UseList.pas que usa una lista de letras, entonces hay que  usar 
la unidad ElemC.pas y luego recompilar el programa:

     C:> copy ElemC.pas Elem.pas

     Es natural que si se usa la implementacin ElemI.pas en lugar 
de  ElemC.pas entonces los  resultados desplegados por UseList.pas 
sern diferentes, pues los nmeros se ven diferentes a las  letras 
en la pantalla.  Por eso UseList.pas desplegar letras si Elem.pas 
se obtuvo a partir de ElemC.pas, y desplegar nmeros si se obtuvo 
a partir de ElemI.pas o ElemZ.pas.

     Sin embargo, para que  UseList.pas funcione es necesario  que 
tenga  la capacidad de crear un  valor del ADT elemental que pueda 
ser obtenido  a partir  de nmeros  o letras.   Por eso  la unidad 
Test.pas, que es  la  que  se  encarga  de  generar  el  men  que 
UseList.pas despliega, incluye al procedimiento Lea_Elem(c,i), que 
tiene la cualidad de que puede leer del teclado ya sea un nmero o 
una  letra, y retorna en sus  dos argumentos (c,i) el valor leido. 
Si lo que el  operador digita es la  letra 'a', entonces el  valor 
que Lea_Elem() retorna ser la letra 'a' en el argumento "c", pero 
si  en lugar  de digitar una  letra el operador  digita un nmero, 
etonces ese valor ser retornado en el argumento "i".

     Para  complementar a Lea_Elem(), en  cada ADT elemental se ha 
definido la operacin  Put(e, c,i), que  almacena el valor  de los 
argumentos (c,i) en el ADT "e".  Por ejemplo, la implementacin de 
Put() que est en el archivo ElemC.pas es la siguiente:

     PROCEDURE Put(          { EXPORT }      { ADH }
       {?} VAR e : TElem;    { SELF }
       {+}     c : CHAR;     { letra a meter en e }
       {+}     i : INTEGER   { nmero a meter en e }
     );
     { RESULTADO
       Recibe como entrada las variables "c" e "i"
       y almacena una aproximacin de esos valores
       en "e".
       - Si Ord(c)=0, entonces almacena el valor de
         "i" en "e".
       - Si Ord(c)<>0, entonces almacena el valor de
         "c" en "e".
       - Si los dos son cero, almacena 0.
       Get(e,c,i) en muchos casos retorna el valor
       original [como nmero] de "c" y "i".        }
     BEGIN { Put }
       IF Ord(c) = 0 THEN BEGIN
         e.Rep.c := CHR(ABS(i)+ORD('a')-1);
       END
       ELSE BEGIN
         e.Rep.c := c;
       END;
     END;  { Put }

     Lea_Elem()  y  Put()  estn  sincronizados de  forma que  los 
valores leidos  por Lea_Elem()   puedan despus  ser asignados  al 
elemento por medio de Elem.Put(). Por eso al ejecutar UseList.exe, 
el   operador  del   programa  puede  digitar   letras  o  nmeros 
indistintamente,  pues  la   conjugacin  de  Test.Lea_Elem()    y 
Elem.Put()  le  permite al  programa manipular  tanto letras  como 
nmeros.  Para complementar a Elem.Put(e, c,i)  se ha definido  su 
operacin  inversa Elem.Get(e, c,i), la  que se encarga de obtener 
los valores de los argumento  (c,i) a partir del valor  almacenado 
en el ADT "e".

     El truco para coordinar a Lea_Elem() con Put() es muy simple. 
Cuando  Lea_Elem() lee una letra,  entonces retorna el valor leido 
en el argumento "c",  y le asigna una  valor de cero al  argumento 
"i".   Pero si  lo que Lea_Elem()   lee del teclado  es un nmero, 
entocnes retorna CHAR(0) en el argumento "c", y el nmero leido lo 
retorna  en "i".   O sea, que  los valores que  retorna Lea_Elem() 
siempre son (CHAR(0),  i)   o  (c,  0).   Elem.Put(e,  c,i)   est 
implementado de forma que asigna el valor del elemento "e" tomando 
el valor que no sea cero de sus argumentos (c,i).

     Es natural que el operador del programa digite nmeros cuando 
est usando la  implementacin ElemI.pas, y  que digite letras  si 
usa ElemC.pas. Pero  de hecho el  programa le permitir  hacer las 
cosas  al  revs,  digitando  letras para  nmeros y  nmeros para 
letras. Por eso tambin es que en la especificacin de  Elem.Put() 
se dice que Elem.Get() en  muchos casos retorna el valor  original 
[como  nmero] de "c" y "i", pues  el rango de valores del tipo de 
datos  CHAR es  mucho ms pequeo  que el rango  del tipo INTEGER. 
Este detalle  no  es  importante,  pues  al  usar  UseList.pas  al 
operador no le resulta cmodo usar nmeros muy grandes.

     Como las operaciones Get()  y Put()  son operaciones del  ADT 
elemental,  definidas  en Elem.pas,  entonces toda  esta discusin 
sobre Lea_Elem()   y  Elem.Put()   se  aplica  tanto  al  programa 
UseList.pas  como a UseTree.pas.  Ms  an, toda la martingala con 
los  tipos  CHAR e  INTEGER existe  para que  estos dos  programas 
puedean funcionar, y no tienen sentido fuera de este mbito.   Por 
eso es  que en  cada implementacin  de Elem.pas  la definicin  e 
implementacin  de  estas  operaciones   est  en  un  bloque   de 
compilacin condicional  definido para  la variable  "Learn_ADTs". 
Cuando  esta  variable de  compilacin condicional  est definida, 
entonces  el compilador  procesa las implementaciones  de Get()  y 
Put(),  y  sin  este  no  es  el  caso,  entonces  el   compilador 
simplemente se salta todo el cdigo de estas operaciones.

     Las  otras  dos operaciones  que estn  dentro del  bloque de 
compilacin    condicional   resguardado    por   Learn_ADTs   son 
Elem.Print(e,F)  y Elem.Read(e,F),  que  se  encargan  de  leer  y 
escribir  del archivo de texto "F"  el valor del elemento "e".  No 
es conveniente obligar al programador que usar un ADT  contenedor 
a implementar estas cuatro operaciones para los ADTs que  necesita 
insertar en  el contendor,  pues muchos  ADTs elementales  se usan 
slo  dentro del programa, y  nunca es necesario almacenarlos como 
hileras de caracteres en un archivo de texto.  El uso de bloque de 
compilacin condicional permite evitar hacer obligatorio el uso de 
estas  cuatro  operaciones,  que  tienen una  gran utilidad  en el 
contexto  de los programas UseList.pas  y UseTree.pas, pero que en 
la mayor parte de los programas son superfluas.

     De la misma manera  que existen varias implementaciones  para 
el ADT  elemental, tambin  hay varias  implementaciones para  ADT 
Tlist.  En el  archivo ListC.pas est  la implementacin de  TList 
que usa  una lista  circular, mientras  que en  List2.pas est  la 
implementacin  del mismo ADT, pero en  este caso se usa una lista 
doblemente enlazada.   La ventaja  principal de  la implementacin 
ListC.pas sobre List2.pas es que requiere menos almacenamiento,  y 
su desventaja es que la  operacin List.Prev() tiene un tiempo  de 
ejecucimn  mucho  menor para  List2.pas que  para ListC.pas.   De 
nuevo, para escoger la implementacin  del ADT TList que se  usar 
al compilar UseList.pas es necesario copiar el archivo ListC.pas o 
List2.pas en el  archivo  List.pas,  que  es  el  archivo  que  se 
necesita para compilar el UseList.pas.  El comando DOS para lograr 
crear el archivo es uno de los siguientes:
     C:> copy ListC.pas List.pas
     C:> copy List2.pas List.pas

     En resumen, las  posibilidades  que  existen  para  armar  el 
programas UseList.pas son las suiguientes:

            Rational.pas
            ElemC.pas
            ElemI.pas                        ListC.pas
            ElemZ.pas                        List2.pas
             \     /                          \     /
              \   /                            \   /
             Elem.pas                         List.pas
                                                
                                                
                        Ŀ         
                > UseList.pas <
                         
                                
                                v
                         Ŀ
                          UseList.exe 
                         

     Este diagrama muestra como se pueden obtener 4*2=8  versiones 
diferentes del  programa UseList.pas.   Todas estas  versiones son 
funcionalmente equivalentes, desde el punto de vista de la entrada 
de datos que  pueden manejar, aunque  al desplegar sus  resultados 
uno  desplegarn  letras  y  otros  nmeros,  dependiendo  de   la 
implementacin del ADT elemental que se escoga para recompilar  el 
programa UseList.pas.

     El trmino usado en el argot de los lenguajes de  computacin 
para  denominar a  un ADT que  puede contener a  cualquier tipo de 
elementos se dice que el ADT contenedor es parametrizable, pues el 
tipo del elemento contenido es  un parmetro del ADT.  Desde  esta 
persepectiva, las dos implementaciones del ADT TList contenidas en 
ListC.pas y List2.pas son  parametrizables. El nico problema  que 
tienen estas implementaciones es  que la parametrizacin se  logra 
al escoger astutamente los  nombres de los identificadores  usados 
en  la  implementacin   de  cada  ADTs,   pues  el  lenguaje   de 
programacin no  incluye construcciones  sintcticas que  permitan 
definir algunos nombres  como parmetros. En  los lenguajes C++  y 
Ada se incluyen construcciones sintcticas, llamadas plantillas en 
el primer caso  y  paquetes  genricos  en  el  segundo,  las  que 
permiten definir el  tipo  contenido  en  un  contenedor  como  un 
parrmetro  del ADT.  Trasliterando,  si Pascal tuviera plantillas 
entonces sera  posible  definir  variables  usando  la  siguiente 
notacin:

     VAR
       Li : TList <INTEGER>;
       Lc : TList <CHAR>;

En este caso, "Li" sera una lista de nmeros enteros mientras que 
"Lc" sera una lista de caracteres. Pascal no incluye estas listas 
por dos razones  principales.  Primero, porque  es difcl para  el 
escritor  de  compiladores implementar  las plantillas,  y segundo 
porque  los  esfuerzos  de  la  industria  de  compiladores  estn 
dirigidos a mejorar los lenguajes de moda, que son C++ y Ada.   La 
ventaja principal de conocer  bien cmo lograr la  parametrizacin 
dentro de las restricciones del lenguaje Pascal estriba en que  el 
programador  llega a comprender no slo  el costo que tiene el uso 
de plantillas, sino que aprende a modularizar mejor sus programas.

     Tambin  es posible parametrizar  el programa UseTree.pas con 
el sencillo procedimiento de copiar sobre el archivo Elem.pas  una 
de  las versiones de TElem  disponibles.  En el siguiente diagrama 
se muestra  como  es  posible  obtener  cada  una  de  las  cuatro 
versiones para UseTree.pas a partir de las cuatro implementaciones 
de Elem.pas disponibles:

                           Rational.pas
                            ElemC.pas
                            ElemI.pas
                            ElemZ.pas
                             \     /
                              \   /
                             Elem.pas
                                
                                
                                v
                         Ŀ    Ŀ
                          UseTree.pas <Ĵ Tree.pas 
                             
                                
                                v
                         Ŀ
                          UseTree.exe 
                         


Contenedores de contenedores
============================

     Una de las formas ms convincentes de mostrar la utilidad  de 
la modularizacin que se lograr al implementar las operaciones del 
ADT contenedor en un mdulo separado al del ADT elemental es  usar 
un  ADT  contenedor como  ADT elemental  de otro  contenedor. Para 
lograr este cometido es necesario que el contendor que ser  usado 
como ADT elemental tenga todas las operaciones del ADT  elemental.  
En el caso de los programas UseList.pas y UseTree.pas esto implica 
que las implementaciones  de los ADTs  contenedores TList y  TTree 
deben incluir las operaciones Get() y Put(), y tambin Print()   y 
Read().

     Si para  el programa  UseTree.pas se  usa una  lista como  el 
elemento  contendido  en  el  rbol,  es  necesario  cambiar   los 
identificadores  usados en la implementacin  de la lista, como se 
muestra en el siguiente diagrama:

                                    Ŀ    Ŀ
                                    ListC.pas    ElemC.pas
                                        
                                                       
                                         v              v
   Ŀ   Ŀ   Ŀ   Ŀ
    UseTree.pas > Tree.pas > Elem.pas > Ele1.pas 
            

     Para obtener el  archivo Elem.pas en  este caso es  necesario 
ejecutar  tres pasos. Primero hay  que copiar el archivo ListC.pas 
sobre el archivo Elem.pas, usando el siguiente comando del DOS:

     C:> copy ListC.pas Elem.pas

     Como Elem.pas en este caso  es una lista, es necesario  crear 
un  archivo  que cotenga  al elemento  contenido en  Elem.pas Este 
archivo es el archivos  Ele1.pas,  que  se  obtiene  a  partir  de 
ElemC.pas en este caso, usando el siguiente comando del DOS:

     C:> copy ElemC.pas Ele1.pas

     Ahora es necesario cambiarle el nombre a los indentificadores 
que  aparecen dentro de Elem.pas y  de Ele1.pas, pues los que cada 
uno  de  estos  archivos  contiene son  "List", "TList",  "Elem" y 
"TElem"  en el caso de Elem.pas, y  "Elem" y "TElem" en el caso de 
Ele1.pas.  Para esto  es necesario usar  un editor de  textos para 
editar  los archios Elem.pas y  Ele1.pas para hacer las siguientes 
sustituciones:

     Elem    ==>    Ele1           TElem   ==>   TEle1
     List    ==>    Elem           TList   ==>   TElem

     Definitivamente  es  muy  incmo  tener  que  realizar  estas 
sustituciones con el editor de texto. Precisamente es por eso  que 
los lenguajes  C++  y  Ada  tienen  contrucciones  sintctica  que 
realizan este trabajo  para el progamador.   Como paleativo se  ha 
escrito el programa RPL.exe puede realizar estas sustituciones  en 
un archivo,  al ser  ejecutado desde  la lnea  de comando.   Este 
programa recibe  tres argumentos  desde la  lnea de  comandos del 
DOS, que  son el  nombre del  archivos sobre  el que  se trabajar 
(Elem.pas o  List.pas en  este caso)   y las  palabra que  hay que 
sustituir.  Para obtener una versin de UseTree.pas que maneja  un 
rbol de  listas  de  caracteres  hay  que  ejecutar  la  siguente 
secuencia de comandos DOS:

     C:> copy ListC.pas Elem.pas
     C:> copy ElemC.pas Ele1.pas

     C:> rpl  Elem.pas  Elem  Ele1
     C:> rpl  Elem.pas  List  Elem

     C:> rpl  Elem.pas  TElem TEle1
     C:> rpl  Elem.pas  TList TElem

     C:> rpl  Ele1.pas  TElem TEle1
     C:> rpl  Ele1.pas  TList TElem

     El  orden  en  que  se  hacen  estas  sustituciones  es   muy 
importante, pues si en el archivo Elem.pas se hace la  sustitucin 
(TList=>TElem) antes de hacer (TElem=>TEle1) entonces el resultado 
sera que  los identificadores  para el  contenedor y  el elemento 
contenido  seran  el  mismo.   Como es  tan engorroso  obligar al 
programador a  tomar  estas  precauciones  es  que  los  lenguajes 
modernos  incluyen  plantillas  para  que  sea  el  compilador  el 
encargado de parametrizar mdulos.

     Para recordarle al programador cule son los  identificadores 
que debe  cambiar  para  parametrizar  el  ADT  contenedor  en  la 
interfaz  de cada  ADT hay un  cuadro que tiene  por encabezado la 
palabra  PARAMETERS,  en   donde   est   los   nombres   de   los 
indentificadores que hay que cambiar.

     Para que los  contenedores  TList  y  TTree  puedan  ser  los 
elementos de otros contenedores ha sido necesario incluir en  cada 
implementacin  las  operaciones   Get()    y   Put(),   las   que 
necesariamente deben tomar un nmero o letra y obtener una lista o 
un rbol.  Para el caso de TList, la lista obtenida tiene a  todos 
sus elementos iguales, pero su longitud vara de acuerdo al  valor 
insertado.  En el caso de TTree, lo que se obtiene es un  arbolito 
que tiene una  raz  y  hasta  tres  hijos.   Los  siguientes  son 
ejemplos  de  los   resultados  que  se   obtiene  de  estos   dos 
procedimiento para TList y TTree:

     Argumento "c"     TList         TTree
        'a'           (a a a)       [a [a a a]]
        'c'           (c c c c c)   [c [c c c]]
        'd'           (d)           [d [d d d]]
        'y'           (y y)         [y [y y y]]
        'z'           (z z z)       [z [z z z]]


Elem.bat y Clean.bat
====================

     Los  archivos  de  comandos  Elem.bat  y  Clean.bat  se   han 
programado  para evitarle a quien  use los programas UseList.pas y 
UseTree.pas  tener  que  recordar  cules son  los nombres  de los 
archivos que hay que copiar, y cules son identificadores que  hay 
que sustituir en esos archivos.

     Clean.bat se encarga de eliminar del directorio los  archivos 
Elem.pas y List.pas. Elem.bat se  encarga de copiar alguna de  las 
implementaciones de TElem en el  archivo Elem.pas. En el caso  del 
programa UseList.pas, Elem.bat tambin permite seleccionar el tipo 
de lista que se usar: ListC.pas o List2.pas.

     Para lograr ms comodidad, cada ADT est en un  subdirectorio 
diferente, como se muestra a coninuacin:

     raz
     aho
     elem
     except
     heap
     list
     poly
     rational
     test
     tree

     Como cada ADT est en  su propio directorio, para usarlo  hay 
que entrar  a  ese  directorio  con  el  comando  CD  del  sistema 
operativo. Luego, para escoger una  de las versiones de TElem  hay 
que copiarla del subdirectorio hermano ..\elem:

     C:\>cd list
     C:\list> copy ..\elem\ElemC.pas Elem.pas

     El archivo de comandos list\Elem.bat puede copiar  cualquiera 
de  las versiones de TElem, y  tambin las dos versiones de TList. 
Por ejemplo, la invocacin:

     C:\list> elem 1 c

copia  sobre List.pas  el archivo ListC.pas,  pues el nmero  1 se 
refiere a  ListC.pas (y  el 2  a List2.pas).   El caracter  "c" se 
refiere   ElemC.pas,  (i  a  ElemI.pas,   r  a  Rational.pas  y  z 
ElemZ.pas).

     Adems de copiar los  archivos, Elem.bat tambin incluye  las 
invocaciones al programa RPL.exe, para cambiar los nombres de  los 
identificadores.  Por  ejemplo, la  siguiente es  la secuencia  de 
comandos que se ejecutan  cuando  se  invoca  a  Elem.bat  con  el 
argumento "llc" (lista de listas de caracteres):

     C:\list> elem llc

     C:\list> copy    ListC.pas   List.pas
     C:\list> copy    ListC.pas   Elem.pas

     C:\list> ..\elem\rpl Elem.pas TElem TEle1
     C:\list> ..\elem\rpl Elem.pas TList TElem
     C:\list> ..\elem\rpl Elem.pas Elem  Ele1
     C:\list> ..\elem\rpl Elem.pas List  Elem

     C:\list> copy ..\elem\ElemC.pas Ele1.pas

     C:\list> ..\elem\rpl Ele1.pas TElem TEle1
     C:\list> ..\elem\rpl Ele1.pas Elem  Ele1

     El  programa RPL.exe est en  el subdirectorio "elem", que es 
el que contiene las versiones ElemC.pas, ElemI.pas y ElemZ.pas del 
ADT elemental TElem.


Read() y Print()
===============

     Las operaciones Read(x,F)  y Print(x,F) de  cada ADT son  muy 
tiles en los programas UseList.pas y UseTree.pas, porque permiten 
desplegar en pantalla el valor contenido en el ADT.

     Estas dos operaciones  han  sido  programadas  de  forma  que 
Read(x,F)   puede  reconstruir  el  valor exacto  del ADT  "x" que 
Print(x,F)   grab  en el  archivo "F".   Para esto,  la operacin 
Print(x,F) de la lista y el rbol graba en "F" una hilera de  unos 
y ceros  que  representan  el  comportamiento  del  ADT  "x".   En 
principio lo escrito  con el Print()   de la versin  ListC.pas de 
TList debera poder ser leido por el Read() de List2.pas, pero  en 
la prctica esto  no ocurre, pues  el conjunto de  comportamientos 
que ListC.pas  permite  siempre  es  diferente  al  que  List2.pas 
permite.

     Tanto Print() como Read()  son operaciones que se  encuentran 
dentro  del bloque  de compilacin condicional  resguardado por la 
variable  de  compilacin  Lear_ADTs,  pues al  igual que  Get() y 
Put(),  estas dos operaciones  son muy tiles en  el mbito de los 
programas   UseTree.pas  y   UseList.pas,  pero  no   por  eso  es 
recomendable hacer  obligatoria su  implementacin para  cualquier 
ADT.


Uso de los programas
====================

     Casi todos los compiladores modernos incluyen un Ambiente  de 
Programacin que le permite al programador probar interactivamente 
su programa. Estos ambientes son  muy tiles, pues le permiten  al 
programador trabajar  no  slo  con  los  programas  fuente,  sino 
tambin controlar al ejecucin del programa desde el ambiente, por 
medio del Depurador  Simblico  de  programas.   En  el  caso  del 
compilador  Turbo  Pascal  v5.0   y  posterior,  el  ambiente   de 
programacin  le  permite al  programador realizar  las siguientes 
tres actividades fundamentales sin dejar el ambiente Turbo Pascal:

     - Compilar el programa      Tecla F9
     - Editar el programa        Comandos de edicin
     - Ejecutar el programa      Teclas F4, F7 y F8
     - Examinar variables        Teclas Ctrl-F4 y Ctrl-F7.

     Una forma de entender lo  que hace un programa es  ejecutarlo 
paso  a paso dentro del ambiente  de programacin, y ver el efecto 
que la ejecucin produce en las variables del programa. En el caso 
de UseList.pas  y UseTree.pas  el programador  puede usar  Ctrl-F7 
para abrir la  ventana de variable  (Watch Expression), e  incluir 
ah las variables que desea  ver. Por ejemplo, para entender  cmo 
est  programada la operacin  List.Count(L), el programador puede 
seguir los siguientes pasos:

1) En el editor incorporado, buscar el procedimiento List_Count en 
   el programa UseList.pas

2) Teclear F4 sobre la instruccin Write(... List.Count()).

   Al hacer esto, Turbo Pascal recompilar el programa UseList.pas 
   y proceder  a ejecutarlo,  pero parar  cuando la  instruccin 
   sobre la que se tecle el F4 sea la siguiente a ejecutar.

3) Seleccionar la opcin para insertar varios valores en la lista.

   De esta manera la lista tendr unos cuantos valores.

4) Seleccionar  la   opcin  que   corresponde  al   procedimiento 
   List_Count  de  UseList.pas. El  compilador parar  exactamente 
   sobre la instruccin Write() sobre la que se tecle F4.

5) Teclear  F7,  para  ejecutar  paso  a  paso  el  programa.   La 
   diferencia entre F7 y F8 es que F7  entra a  cada procedimiento 
   que sea invocado, mientras que F8 ejecuta en un solo  paso todo 
   el procedimeinto.

6) Dentro del procedimiento List.Count(L), usar  la tecla  Ctrl-F7 
   dos  veces  examinar  el  valor de  las variables  "p" y  "n" y 
   "L.Rep._last".   Esta  tecla  abre  la  ventana  de  examen  de 
   variables.

7) Pulsar repetidamente F7 y F8  para ver  cmo van  cambiando las 
   variables.

8) Repetir una secuencia similar a  esta para  estudiar las  dems 
   operaciones del ADT.

     Para entender cmo  estn implementados los  ADTs lo que  hay 
que  hacer es ejecutar, paso a  paso, cada una de las operaciones. 
Este  forma de  aprender es muy  til pues el  estudioso puede ver 
inmediatamente  el  resultado que  tiene el  algoritmo sobre  lass 
variables con que trabaja.  La otra manera de aprender es estudiar 
el listado de todos los algoritmos, que tiene la desventaja de que 
hay  que  hacer  un  mayor  esfuerzo  mental  para  ver  que  est 
ocurriendo en cada momento.

     Otra ventaja importante que se deriva del uso del ambiente de 
programacin es que el estudiante puede experimentar cambiando los 
algoritmos.  Por ejemplo, es muy til alterar la implementacin de 
alguna de las opciones de UseList.pas, eliminando por ejemplo  una 
invocacin a List.Init() o List.Done(), para notar  inmediatamente 
el efecto devastador que esto tiene sobre la memoria dinmica.   A 
veces no basta con saber que es importante inicializar y  destruir 
a  todos  los  ADTs,  pero al  ver el  efecto que  tiene sobre  el 
programa este tipo de error es ms fcil comprender porqu es  tan 
importante invocar a los constructores y destructores.

     Aunque es muy conveniente contar con el ambiente Turbo Pascal 
y las implementaciones completas de UseList.pas o UseTree.pas,  el 
estudioso siempre  deber leer  el cdigo  de cada  algoritmo para 
entenderlo  bien. Per sobre  todo, lo que no  es posible evitar es 
pensar constantemente, pues el  mero ejercicio de las  facilidades 
que brinda el depurador simblico no es suficiente para comprender 
todos los detalles  que comporta una  implementacin de un  mdulo 
tan complejo como el ADT TList o TTree.


Bibliografa
============

[1] Aho, Alfred V.; John E.  Hopcroft; Jefrrey  D.  Ullman:  "Data 
    Structures and Algorithms"; 1983. [AHO-83].

[2] Borland; "Turbo Pascal Version 5.5"; 1984.

[3] Liskov, Barbara; Gutag,  John; "Abstraction  and Specification 
    in Program Development"; McGraw-Hill; 1986.

[4] Di Mare, Adolfo:  "Convenciones de  Programacin para  Pascal, 
    Revisin 2"; Reporte tcnico ECCI-01-88, ECCI-UCR, 1988.

[5] Di  Mare, Adolfo:  "Abstraccin de  Datos en  Pascal"; Reporte 
    tcnico PIBDC-01-89, ECCI-UCR, 1991.

[6] Horowitz, E.; Sahni,  S.: "Fundamentals  of Data  Structures"; 
    Computer Science Press; 1982.


               Reportes tcnicos de Adolfo Di Mare
               ===================================

     Los siguientes Reportes Tcnicos, todos confeccionados por el 
mismo autor, describen todos  las implementaciones y algunos  usos 
importantes de los ADTs programados en Turbo Pascal en al  Escuela 
de Ciencias de la Computacin e Informtica, de la Universidad  de 
Costa Rica. 

     Todas estas  implementaciones estn  disponibles en  Internet
por medio de ftp annimo en el directorio:

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

     Los derechos de autor  estn reservados  a nombre  del autor,
Adolfo Di Mare.

     El texto de cada Reporte Tcnico se encuentra  en el  archivo
de texto nombrado entre parntesis cuadrados.

[R1]  "Prueba  interactiva  de  ADTs", Reporte  Tcnico ECCI-94-01
      [Archivo UseADT.doc]; Mayo, 1994.

[R2]  "La Implementacin de Elem.pas"; Reporte  Tcnico ECCI-94-02
      [Archivo Elem.doc]; Mayo 1994.

[R3]  "La   Implementacin   de  Rational.pas";   Reporte  Tcnico
      ECCI-94-03 [Archivo Rational.doc]; Mayo 1994.

[R4]  "La Implementacin de Poly.pas"; Reporte  Tcnico ECCI-94-04
      [Archivo Poly.doc]; Mayo 1994.

[R5]  "La    Implementacin  de   ListAHO.pas";  Reporte   Tcnico
      ECCI-94-05 [Archivo Aho.doc]; Mayo 1994.

[R6]  "La Implementacin de List.pas"; Reporte  Tcnico ECCI-94-06
      [Archivo List.doc]; Mayo 1994.

[R7]  "La Implementacin de Tree.pas"; Reporte  Tcnico ECCI-94-07
      [Archivo Tree.doc]; Mayo 1994.

[R8]  "La Implementacin de Heap.pas"; Reporte  Tcnico ECCI-94-08
      [Archivo Heap.doc]; Mayo 1994.

[R9]  "Uso  de  la  unidad Test.pas";  Reporte Tcnico  ECCI-94-09
      [Archivo Test.doc]; Mayo 1994.

[R10] "Manejo  de excepciones  en Turbo  Pascal"; Reporte  Tcnico
      ECCI-94-10 [Archivo Except.doc]; Mayo 1994.
