                  Abstraccin de Datos en Pascal

                               por

                          Adolfo Di Mare

                   Reporte Tcnico PIBDC-03-91
                       Proyecto 326-89-019
                           Revisin 2.0


Resumen:
=======

El principal objetivo de este trabajo es presentar un conjunto  de 
convenciones  que permitan usar abstraccin  de datos en el mbito 
del  lenguaje Pascal (para  aquellas implementaciones que incluyen 
compilacin  separada por medio  de unidades).  Mltiples ejemplos 
ilustran  los  alcances  de  esta  tcnica.   Este  trabajo   est 
orientado al compilador Turbo Pascal v5.0, aunque la misma tcnica 
tambin puede usarse para Modula-2 o en otras versiones de Pascal.

Las  convenciones aqu  elaboradas permiten que  las instancias de 
los  objetos,  aun de  los que  son contenedores,  tengan asignada 
memoria  en la  pila de ejecucin  del programa.  A  diferencia de 
otras propuestas, no obligan a  usar punteros a las instancias  de 
los  objetos  en  memoria  dinmica,  con  lo  que  se  logra  una 
significativa mejora  en  la  eficiencia  de  programas  que  usan 
abstraccin de datos.


Abstract:
========

We explain a  set of conventions  that allow data  abstraction for 
the  Pascal  language  (for  those  implementations  that  support 
separate compilation through units).  Complete examples illustrate 
the  applicability  of this  technique. This  work is  oriented to 
Turbo Pascal v5.0, even  though  these  ideas  can  be  used  with 
Modula-2 or with other versions of Pascal.

These  conventions  allow object  instances, even  those that  are 
containers,  to use stack memory.   As other proposals require the 
use of pointers and dynamic  memory, the use of these  conventions 
can  mean a significant improvement  in the efficiency of programs 
that use data abstraction.


Esta investigacin se realiz dentro del proyecto de investigacin 
326-89-019 "Estudios en la tecnologa de programacin por  objetos 
y  C++"  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.


                  Abstraccin de Datos en Pascal
                  ==============================

     La  ingeniera  de  sistemas  de  informacin  ha  progresado 
gracias a  la  introduccin  de  nuevas  tcnicas  para  construir 
programas.   El primer  gran avance lo  constituye la programacin 
modular, complementada  con la  programacin estructurada.   Otros 
logros lo constituyen los llamados lenguajes de cuarta generacin, 
que   permiten   desarrollar   sistemas   en   un   lenguaje   muy 
especializado.

     Pero  conforme  avanza  la  tecnologa  de  computadores   es 
necesario crear programas cada vez ms sofisticados.  En la ltima 
dcada ha tomado gran auge el uso de la programacin por  objetos, 
que tiene como  requisito la abstraccin  de datos, y  que implica 
una  nueva  manera de  disear programas.   El lenguaje  Smalltalk 
[Goldberg-83] ha causado gran revuelo, hasta tal punto que existen 
compiladores  para  lenguajes como  C++ [Stroustrup-86a],  que han 
sacado  la  programacin  por  objetos  de  los  laboratorios   de 
investigacin, para ser  utilizados en el  quehacer diario de  las 
empresas.   (Una  excelente  discusin  de  los  alcances  de   la 
programacin por objetos puede encontrarse en [Stroustrup-88]).

     El lenguaje Pascal fue definido por el profesor Niklaus Wirth 
a principios de los 70s.  Tuvo gran aceptacin, pues incorpora  la 
mayor parte de las  construcciones sintcticas necesarias para  la 
programacin  estructurada, y como Pascal  es un lenguaje simple y 
elegante,  es   posible  escribir   compiladores  muy   rpidos  y 
eficientes para l.  En el contexto de las micro computadoras,  la 
implementacin de Phillipe Kahn del lenguaje Pascal, conocido como 
Turbo  Pascal  [Borland-88],  ha  literalmente  revolucionado   el 
desarrollo  de  programas.   Su  aceptacin  y  uso  en   nuestras 
universidades junto con  la falta de  difusin de las  tcnicas de 
abstraccin de  datos  en  nuestro  medio,  hacen  necesario  este 
artculo.

     Aqu se  discuten primero  los conceptos  generales de  tipos 
abstractos de datos (ADTs) y luego se explican los "trucos" usados 
para  implementar  ADTs  en  Turbo  Pascal  5.0  o  en   Modula-2. 
Finalmente  se incluyen algunos  ejemplos de implementaciones.  En 
todo el  artculo  se  siguen  las  convenciones  de  programacin 
descritas en [Di Mare-88], que son ampliadas en este trabajo.


1. Abstraccin de procedimientos
================================

     Fundamentalmente, la programacin  modular es abstraccin  de 
procedimientos.  La idea meter un conjunto de instrucciones en  un 
mdulo, que tiene una  interfaz claramente definida.  Mediante  la 
abstraccin de procedimientos el programador separa claramente  el 
cmo  del  qu: una  subrutina contiene  la lgica  necesaria para 
ejecutar una tarea, y sus parmetros definen los objetos sobre los 
que trabaja.

     Los primeros lenguajes de programacin (Fortran, Lisp,  Basic 
y Cobol)  no soportan adecuadamente abstraccin de  procedimientos 
pues,  aunque  en  ellos   es  posible  definir  argumentos   para 
subrutinas, no es necesario especificar tipos de datos, por lo que 
muchos  errores  de interfaz,  que podran  ser detectados  por el 
compilador,  deben ser eliminados  manualmente por el programador. 
Cuando  estos  lenguajes  fueron   definidos,  lo  comn  era   no 
especificar la interfaz entre mdulos, y hacerlo era visto por los 
programadores  como  un trabajo  poco creativo  y engorroso.   Los 
programadores se rehusaban a disear adecuadamente sus  programas. 
La "documentacin" era labor de funcionarios de poco sueldo, y  se 
crea que lo ms importante era escribir el cdigo del programa.

     Con el advenimiento de Algol, y luego de Pascal, poco a  poco 
ha  cambiado  esta  mala  percepcin  sobre  la  especificacin  y 
documentacin de programas.  Se introdujo la verificacin de tipos 
en tiempo de compilacin, en  los argumentos de cada rutina,  como 
una herramienta  para  reducir  el  tiempo  de  desarrollo  de  un 
programa,  con gran xito.  Sin  embargo, todava no se reconocan 
las grandes ventajas de especificar procedimientos.

==================================================================
PROCEDURE Lea_Arbol_Menu(  { EXPORT }       { Adolfo Di Mare }
  {+} VAR f     : TEXT;    { archivo de lineas de men       }
  {+}     mprin : Linea_P; { linea leda por el llamador     }
  {-} VAR ultLn : Linea_P  { puntero a la ltima lnea leda }
);
{ RESULTADO
  Lee el archivo que describe los menes de la aplicacin.
  En ultLn se retorna un puntero al ltimo tem ledo que
  no corresponde a mprin, sino que es hermano de mprin o
  tal vez hermano de algn tem con nivel menor que el de
  mprin (ie, que corresponde a un men ms cercano al
  principal que mprin).                                      }
{ REQUIERE
  mprin debe apuntar a un registro de men, o mprim = NIL.
  El llamado a Lea_Arbol_Menu se debe hacer para leer todos
  los tems del men mprin.                                  }

                             Figura 1
==================================================================

     La Figura  1  es  un  ejemplo  de  la  especificacin  de  un 
procedimiento,   escrito   de  acuerdo   a  las   convenciones  de 
programacin  definidas  en  [Di  Mare-88].   Este  es  el  tpico 
procedimiento que  encontramos en  un programa.   A diferencia  de 
otros  ejemplos,  la  especificacin  de  este  procedimiento   es 
bastante  completa:  la  mayora   de  los  programadores  no   se 
molestaran en escribir tanto para una "esculida" subrutina.

     En el procedimiento Lea_Arbol_Menu se oculta cmo se logra el 
objetivo descrito en la  clusula RESULTADO de la  especificacin. 
Un  programador  puede usar  este procedimiento  sin necesidad  de 
conocer  el cdigo fuente  de la rutina, con  slo disponer de una 
copia del cdigo objeto producido al compilarla.  Obviamente, debe 
asegurarse  de que la  clusula REQUIERE se cumpla  de hecho, o su 
programa  estara incorrecto.  Las  bibliotecas de programas estn 
formadas por procedimientos como ste.

     Es un poco difcil entender lo que Lea_Arbol_Menu hace.   Por 
ejemplo,  no  se explica  en ningn  lado qu  es un  men, o  una 
Linea_P (o  sea, un  puntero a  una Linea_T).   Es cierto  que los 
identificadores son significativos, pero eso no es suficiente para 
lograr  incorporar este  procedimiento en un  programa real.  Hace 
falta mucho ms informacin.

     Las bibliotecas de programas comerciales generalmente proveen 
informacin adicional  al programador,  en la  que se  describe el 
contexto de uso de cada procedimiento.

     De  este ejemplo  se pueden sacar  dos conclusiones: primero, 
que el no usar abstraccin de procedimientos es  contraproducente.  
Una rutina como sta realmente ayuda a partir un problema complejo 
en  partes  manejables, lo  que garantiza  no slo  una conclusin 
rpida del  proceso  de  programacin,  sino  que  adems  permite 
reutilizar programas en la forma de procedimientos.  C [Kernighan- 
86], el lenguaje  usado en el  sistema operativo UNIX  [Kernighan- 
87], ha logrado  gran aceptacin precisamente  por contar con  una 
amplia   biblioteca   de   procedimientos   disponible   para   el 
programador.

     Lo segundo  que  se  puede  concluir  es  que  no  basta  con 
describir  lo  que  el  subprograma  hace  para  que  sea  posible 
utilizarlo.   Tambin  es necesario  describir los  datos con  que 
trabaja cada procedimiento. Esto se logra mediante la  abstraccin 
de datos.


2. Abstraccin de datos
=======================

     La  programacin  que  utiliza  abstraccin  de  datos  (data 
hiding)   se  basa en  el hecho  de que  en un  programa se  deben 
integrar  y combinar  los tipos bsicos  de datos, como  nmeros y 
caracteres, para formar estructuras de datos ms complejas, y  as 
representar informacin dentro del computador.  En general  existe 
una  fuerte  relacin  entre  todos los  datos manipulados  por un 
programa,  por  lo  que  es  conveniente  que  esa  relacin  est 
claramente especificada y controlada, de forma que cada parte  del 
programa "vea" slo lo que necesita.

     Esto ltimo  es muy  importante para  separar el  programa en 
partes independientes, o mdulos, evitando as que cambios en  una 
parte produzcan errores en otras partes del programa. Por ejemplo, 
en un programa que usa  varios arreglos y matrices para  almacenar 
informacin, es  frecuente  que  al  aumentar  el  tamao  de  una 
dimensin se olvide aumentar la de los dems arreglos, con lo  que 
el mantenimiento del  programa se hace  ms difcil.  El  objetivo 
perseguido al  usar abstraccin  de datos  es lograr  aislar todas 
estas dependencias, de forma que los cambios puedan ser hechos con 
un  mnimo de esfuerzo  y en una forma  localizada.  En nada ayuda 
tener  que buscar por todo el  programa en qu lugar deben hacerse 
los cambios.

     Tambin es importante especificar  qu es cada estructura  de 
datos, mediante la abstraccin de datos.  Una lista, por  ejemplo, 
es una estructura  de datos que  tiene un comportamiento  muy bien 
definido:  pueden  insertrsele  nuevos  elementos,  recorrrsela, 
encontrar  el primer y ltimo  elemento, etc.  Al usar abstraccin 
de datos, el programador decide cules procedimientos se necesitan 
para  manipular una lista, y  define su interrelacin.  Un usuario 
del tipo de datos "lista"  no necesitar entonces conocer cmo  se 
interrelacionan  (a  nivel de  implementacin)  los  datos ni  los 
procedimientos  que  manipulan listas.   Para usar  una lista,  un 
programador  no necesita descubrir de  nuevo el concepto de lista: 
simplemente lo puede importar de una biblioteca.

     Al usar abstraccin de datos el programador define cmo puede 
comportarse  cada una de las variables  de su programa.  O sea que 
adems de  usar abstraccin  de procedimientos  para construir  el 
programa modularmente, deben especificarse las operaciones vlidas 
sobre los datos.  El objetivo es programar un mdulo que defina un 
nuevo tipo de  datos, y adems  que incluya varios  procedimientos 
que permitan manipularlo.  Este do procedimiento-dato es un  Tipo 
Abstracto de  Datos, o  Abstract Data  Type en  Ingls (ADT).   El 
programador-usuario del ADT podr manipular las variables del tipo 
de datos nicamente por medio de sus procedimientos asociados.  En 
un slo mdulo se "encapsula" el nuevo tipo de datos junto con sus 
procedimientos.

     Entonces, para implementar un ADT deben definirse dos  cosas: 
primero, los campos  que se necesitan  para almacenar los  valores 
del dato, y segundo los procedimientos que permiten utilizarlo.

     El asociar  un tipo  de datos  con sus  procedimientos en  un 
mdulo   se   conoce   como   encapsulamiento.    En   Pascal   el 
encapsulamiento se simula mendiante unidades, y en Modula-2 usando 
mdulos.  En  otros lenguajes,  como Smalltalk,  Simula y  C++, el 
lenguaje   incluye   construcciones   sintcticas   que   permiten 
encapsular un tipo  de datos, tambin  llamado una clase,  con sus 
procedimientos.  En este caso,  los procedimientos se conocen  por 
los nombres "operacin", "procedimiento miembro" o "mtodo".

==================================================================
                        Tabla de sinnimos
                        ==================

Encapsulacin     Procedimiento   Tipo de Dato        Mensaje
Abstraccin       Subrutina       Objeto              Parmetro
Especificacin    Rutina          Clase               Argumento
Diseo            Mtodo          ADT
Ocultamiento      Operacin       Tipo Abstracto de Datos

                             Figura 2
==================================================================

     Desgraciadamente  los  computlogos tenemos  la costumbre  de 
crear muchos nuevos trminos para viejos conceptos.  Los  trminos 
estructura  de  datos,  tipo  de datos,  tipo abstracto  de datos, 
objeto,  clase  y  variable  son  muy  similares.   Todos   sirven 
bsicamente para  lo mismo:  definir variables  en un  programa, o 
sea,  instancias  del tipo  de datos  (aunque tiene  ms prestigio 
hablar de "objetos" o de ADTs, que de simples tipos). La Figura  2 
es  una lista de  los trminos usados para  referirse a los mismos 
conceptos (aunque no todos son sinnimos exactos). Sin embargo, el 
contexto del  discurso es  muy importante:  al hablar  de ADTs  en 
Smalltalk necesariamente  debe suponerse  que el  concepto incluye 
cualidades  como  herencia  y  funciones  virtuales.   Las  mismas 
palabras dichas  en el  contexto de  Pascal o  Modula-2 no  pueden 
significar ms que abstraccin de datos.

     Entonces, una operacin es una rutina que est asociada a  un 
tipo de datos, y que permite manipularlo, examinarlo y  cambiarlo.  
El trmino "mtodo" es sinnimo de operacin y, aunque es bastante 
confuso, es el utilizado en ambientes Smalltalk (aunque s  existe 
una buena razn para usar ese trmino, no la discutiremos).

     Intrnsecamente  ligado  al  concepto  de  encapsulamiento  y 
abstraccin est el concepto de ocultamiento de datos.  Al ocultar 
datos,  bsicamente  lo   que  se  persigue   es  evitar  que   la 
representacin  usada para un ADT  sea accesible a un programador- 
usuario.  Por ejemplo, al implementar el ADT pila puede usarse una 
lista de nodos con punteros,  o un arreglo.  Si la  representacin 
del  ADT es privada,  entonces al usar una  pila el programador no 
podra saber si la implementacin que usa es una o la otra.

     El ocultamiento de  datos es muy  importante para lograr  una 
mejor modularizacin, pues garantiza que el programador descuidado 
tenga  acceso controlado a las  campos que conforman una instancia 
de un ADT,  evitando  as  que  destruya  inadvertidamente  alguna 
relacin necesaria entre esos campos.  Paradjicamente,  Smalltalk 
y Simula son lenguajes que soportan abstraccin y  encapsulamiento 
de datos, pero que no soportan ocultamiento de datos.  Es evidente 
que los diseadores de esos lenguajes no consideraron necesario el 
ocultamiento de datos, lo que amerita su defensa.

     Tal  vez  pueda   pensarse   que   los   programadores,   por 
antonomasia,   no   son  "descuidados".    Sin  embargo,   el  ser 
"cuidadoso" requiere de un esfuerzo mental grande, a veces enorme, 
principalmente  cuando   se  trabaja   en  grandes   proyectos  de 
programacin. Si el compilador, la mquina computacional, el robot 
automtico puede verificar que se sigan procedimientos  adecuados, 
para  qu  cargar entonces  al programador  con esta  innecesaria 
responsabilidad?  Como se ha mencionado anteriormente, gran  parte 
del xito de Pascal  como  lenguaje  radica  en  su  capacidad  de 
verificar tipos, que  en realidad es  una de esas  actividades que 
podra  hacerse  manualmente. Al  ser sto  responsabilidad de  la 
mquina, se  obtiene  una  significativa  reduccin  del  esfuerzo 
requerido para construir  un programa, lo  que decrece su  costo y 
tiempo de programacin.

     El lector debe saber que la programacin que usa  abstraccin 
de datos requiere de  un  mayor  esfuerzo  en  el  diseo  de  los 
programas, pues no basta simplemente con partir en subproblemas el 
problema a resolver, tal y como se hace al descomponer el cdigo y 
el  diseo del programa de  arriba hacia abajo (top-down).  Cuando 
se programa de arriba hacia abajo el programador deja para despus 
decisiones  de  diseo, pues  cada nueva  incgnita representa  un 
nuevo procedimiento, en el que se oculta la respuesta correcta. Al 
final  del  diseo lo  que queda  es un  rbol de  dependencias de 
procedimientos. Desgraciadamente, en muchos casos la particin as 
definida  no es  la ms adecuada  para alcanzar los  objetivos del 
programa.

     Algunos autores han  escrito  muchos  artculos  en  los  que 
exponen el diseo de arriba hacia abajo claramente, y han  logrado 
convencer a  los tericos  de la  programacin de  que es  posible 
llegar a un excelente programa  con slo partirlo de arriba  hacia 
abajo.  La verdad es que el proceso de programacin es  iterativo, 
y requiere de  muchas  revisiones  en  todos  los  niveles  de  un 
programa.   La  abstraccin  de  datos  permite  descomponer   ms 
adecuadamente un problema, a partir de los objetos que usa.  (Esto 
ltimo  es  lo  que  esta nueva  tecnologa promete:  todava debe 
usarse mucho antes de decidir si la anterior afirmacin es cierta, 
o si no lo es, bajo qu condiciones s puede serlo).

     En este artculo no se busca desprestigiar a las metodologas 
de   diseo   de   arriba   hacia  abajo.    Ms  bien   se  busca 
complementarlas, pues el proceso de programacin es una  actividad 
intelectual muy difcil, en la que los pocos avances  tecnolgicos 
que se han  alcanzado todava no  son suficientes para  satisfacer 
las   crecientes   demandas  de   sistemas  computacionales.    Es 
simplemente ilusorio olvidar una  tcnica que en muchos  contextos 
ha  dado  muy  buenos  resultados, para  sustituirla por  otra que 
todava no est bien difundida.  Pero como con el uso disciplinado 
de abstraccin de datos se han obtenido muchos xitos, es el deber 
de todo profesional o acadmico conocer esta novel tcnica.

     Al usar abstraccin  de datos es  necesario disear mejor  el 
programa, con lo que se logra una mayor modularidad, que es una de 
las  medidas de calidad en  programacin.  El programa queda mejor 
modularizado   que  si  hubiera   sido  hecho  simplemente  usando 
abstraccin de procedimientos, pero el precio de este beneficio es 
que el programador puede tardar  ms en terminar su programa  (ms 
an si no sabe  bien lo que es  un ADT).  Un programa  escrito sin 
usar abstraccin  de datos  es ms  difcil de  mantener, pues  su 
estructura est oscurecida por la maraa de procedimientos que  lo 
componen.  Por eso al usar abstraccin de datos se logra  escribir 
programas ms modulares.

     La alta modularizacin alcanzada al usar ADTs permite que  el 
mantenimiento del programa sea mucho ms simple.  Sin embargo,  en 
un ambiente de desarrollo de  programas es difcil que esta  nueva 
tecnologa sea aceptada, pues un administrador miope va a preferir 
que sus sistemas  sean  programados  muy  rpidamente,  aunque  el 
posterior mantenimiento sea ms difcil.  Con el correr del tiempo 
el mercado aprender  a apreciar la  calidad de los  programas, lo 
que obligar a los programadores a usar tecnologas nuevas que les 
permitan crear mejores productos a un precio ms bajo.

     Una  de las ventajas  ms importantes de usar  ADTs es que un 
programador especializado puede dedicarse a depurar totalmente los 
procedimientos de un ADT especfico.  Esta persona se asegurar no 
slo de que  la implementacin sea  correcta, sino tambin  de que 
sea eficiente. De esta manera un programador-usuario del ADT tiene 
acceso a rutinas  de alta calidad  y confiabilidad.  Se  evita as 
reprogramar los "trucos" que permiten implementar, eficientemente, 
una estructura de datos cada vez que se la necesite.

==================================================================
UNIT Stack_T;
INTERFACE
USES Elem_T;
CONST SSize = 20000;  { capacidad de la pila }
TYPE
  Rep_Stack = RECORD  { representacin privada del ADT }
     elem   : ARRAY [1..SSize] OF Elem_ADT;
     ultimo : INTEGER;
  END;
  Stack_P   = ^Stack_ADT;
  Stack_ADT = RECORD
    Rep : Rep_Stack;
  END;
{ PARAMETERS
  (Stack_T Stack_ADT Stack_P SSize)   (Elem_T Elem_ADT)  }

PROCEDURE Init   ( {-} VAR s : Stack_ADT);
PROCEDURE Clear  ( {?} VAR s : Stack_ADT);
PROCEDURE Done   ( {?} VAR s : Stack_ADT);
FUNCTION  OK     ( {+} VAR s : Stack_ADT) {>>>>>>>} : BOOLEAN;

PROCEDURE Copy   ( {?} VAR x : Stack_ADT; {+} VAR y : Stack_ADT);
PROCEDURE Move   ( {?} VAR x : Stack_ADT; {?} VAR y : Stack_ADT);
FUNCTION  Equal  ( {+} VAR x, y: Stack_ADT) {>>>>>} : BOOLEAN;

PROCEDURE Load   ( {?} VAR s : Stack_ADT; {+} VAR F : FILE);
PROCEDURE Store  ( {+} VAR s : Stack_ADT; {?} VAR F : FILE);

FUNCTION  Empty  ( {+} VAR s : Stack_ADT) {>>>>>>>} : BOOLEAN;
FUNCTION  Full   ( {+} VAR s : Stack_ADT) {>>>>>>>} : BOOLEAN;

PROCEDURE Push   ( {?} VAR s : Stack_ADT; {+} VAR e : Elem_ADT);
PROCEDURE Pop    ( {?} VAR s : Stack_ADT; {-} VAR e : Elem_ADT);

IMPLEMENTATION
{...}
END.
                             Figura 3
==================================================================

     Para  entender  todos estos  nuevos conceptos  es conveniente 
enmarcarlos en un ejemplo especfico.   Para esto es til usar  la 
especificacin  del  ADT  pila,  que  es  el  ejemplo   usualmente 
presentado  al principiante.  Una pila es  un tipo de datos de los 
llamados  contenedores, en  el que el  ltimo dato en  entrar a la 
pila es el primero que sale: el programador necesita que ese orden 
de entrada-salida sea  el comportamiento de  una variable de  tipo 
pila.   Los ADTs cuya funcin es  contener a otros datos se llaman 
contenedores.  La Figura 3 es un extracto de la especificacin del 
ADT pila, usando una unidad Turbo Pascal.

     Es muy conveniente usar  convenciones para programar un  ADT: 
el  nombre de la unidad que  contiene las declaraciones de tipos y 
el  cdigo de las operaciones del  ADT deben tener el sufijo "_T", 
que  indica que contiene  un ADT.  Adems, el  nombre del tipo del 
ADT es igual al de la unidad en que est contenido, pero se usa el 
sufijo "_ADT".  El usar una unidad Pascal para implementar un  ADT 
es muy cmodo, pues  en  ella  es  posible  incluir  no  slo  las 
operaciones del ADT,  sino  tambin  las  declaraciones  de  tipos 
necesarias  para  definir los  campos que  permiten almacenar  una 
instancia del ADT.  Los trucos  de este artculo pueden usarse  en 
las  versiones de Pascal  que no soporten el  uso de unidades (que 
desgraciadamente son  la  mayora),  pero  es  entonces  necesario 
simular su  efecto, a  costa de  un mayor  esfuerzo por  parte del 
programador.

==================================================================
      VAR
        s  : Stack_ADT; { pila para invertir t }
        ch : CHAR;      { temporal             }
        t  : STRING;    { tira a invertir      }
        i  : INTEGER;   { contador             }
      BEGIN
        Init(s);  { inicializa s }
        ReadLn(t);
        FOR i:= 1 TO Length(t) DO BEGIN
          Push(s,t[i]);
        END;
        WHILE NOT Empty(s) DO BEGIN
          Pop(s,ch);
          Write(ch);
        END;
        Done(s); { libera s }
      END;
                             Figura 4
==================================================================

     Las operaciones  de la  unidad Stack_T  tienen argumentos  de 
tipo Stack_ADT: cuando el programador quiere declarar una variable 
que  sea una pila,  o sea, cuando necesita  usar una instancia del 
objeto  pila,  lo  que  hace  es  declarar  la  variable  de  tipo 
Stack_ADT, como se hace con la variable "s" en la Figura 4.

     Para  manipular  una   variable   de   tipo   Stack_ADT,   el 
programador-usuario  puede  nicamente  usar  los   procedimientos 
exportados por la  unidad Stack_T.  Por  ejemplo, el cdigo  de la 
Figura 4  lee una  tira de  caracteres, y  la invierte  usando una 
pila.  Ntese que bastan los procedimientos de la pila para lograr 
el  objetivo deseado.  (En  este ejemplo se supone  que el tipo de 
datos Elem_ADT a almacenar en la pila es CHAR).


3. Implementacin de ADTs en Pascal
===================================

==================================================================
VAR
  e : Elem_ADT;
  s : Stack_ADT;   { "s" es la pila que usar el programador.   }
  r : Rep_Stack ;  { debe cualificarse el nombre, pues cada ADT }
    {...}          { posee su propio tipo Rep_Stack.            }
BEGIN
  s := r;    { error de compilacin: tipos incompatibles }
  r := s.Rep;             { OK: son del mismo tipo       }
  s := Stack_ADT(r);      { OK, usado muy pocas veces    }
  Push(s, e);  { OK }
  Pop (s, e);  { OK }
  Push(r, e);  { error: r no es de tipo Stack_ADT }
  Pop (r, e);  { error: r no es de tipo Stack_ADT }
  IF NOT Empty(s) THEN BEGIN  { OK }
    {...}
  END;
                             Figura 5
==================================================================

     A primera vista la definicin del tipo Stack_ADT en la Figura 
5 parece muy extraa: para qu se necesita el registro  Rep_Stack 
y un registro  que nicamente contiene  un campo llamado  Rep?  El 
tipo Rep_Stack define cules son los campos, registros o  arreglos 
que  se  necesitan para  implementar la  pila, esto  es, la  parte 
interna  o  privada del  ADT.  Por  otro lado,  el tipo  Stack_ADT 
contiene un nico campo que se llama Rep (Rep_resentacin), que es 
el campo que contiene la representacin interna del ADT.

     La palabra "Rep" se ha tomado del lenguaje CLU, en donde esta 
palabra no  es, como  en Pascal,  un identificador  ms, sino  que 
forma  parte del  lenguaje.  Coloquialmente se  dice "metrsele al 
Rep" al acto de accesar los campos privados que componen un ADT.

     Un programador usuario del ADT no necesita el tipo  Rep_Stack 
en  absoluto,  pues  su  inters debe  centrarse en  manipular las 
variables de  tipo Stack_ADT  por medio  de las  operaciones Init, 
Clear,  Done,  OK, Copy,  Move, Equal,  Empty, Full,  Load, Store, 
Push, Pop, y nada ms.

     Si    un   programador   define    una   variable   de   tipo 
Stack_T.Rep_Stack  (lo  que  es  vlido),  no  podr  usarla  como 
argumento en ninguno de los procedimientos del ADT pila.  Con esto 
se logra evitar que  el programador, inadvertidamente, cambie  los 
valores  privados  de  una  pila.   Si  lo  hiciera,  entonces  el 
compilador  respondera  con "error  de tipo  de datos",  pues una 
variable de  tipo "Rep_Stack"  no es  compatible con  una de  tipo 
"Stack_ADT". De esta forma se simula en Pascal el ocultamiento  de 
datos,  pues con este truco se  logra que el compilador, por medio 
de la verificacin de tipos, resguarde la parte interna del ADT.

     El usar  el tipo  Rep_Stack para  construir Stack_ADT  es una 
manera elegante de lograr ocultamiento de datos.  Una variable  de 
tipo Stack_ADT tiene exactamente el  mismo tamao que una de  tipo 
Rep_Stack.  En  la  implementacin  de  Stack_ADT  ser  necesario 
usaaaar  muchas  sentencias  que  usen el  campo Rep  del registro 
Stack_ADT,  que es vlido.  Pero  si un programador-usuario del la 
unidad  Stack_T  usa  ese  campo, su  programa quedar  plagado de 
referencias a "Rep", las que son muy fciles de detectar por medio 
del  programa GREP.   Este programa busca  todas las lneas  en un 
archivo de texto que contienen un patrn de caracteres, por lo que 
al ejecutar el comando:
                      GREP Rep PROGRAMA.PAS
Si  al  ejecutar  GREP  ste despliega  alguna lnea,  entonces el 
programador-usuario  del  ADT Stack  sabr que  est violando  las 
partes privadas del ADT. Lo mismo sucedera si usara transferencia 
de tipos desde Stack_ADT a Rep_Stack. La transferencia de tipos es 
una facilidad de  muchos lenguajes, como  es el caso  de Modula-2, 
Turbo Pascal y C.

     De esta manera el  usuario del ADT est  forzado a no ver  la 
representacin interna de  la pila; si  quiere "metrsele al  Rep" 
deber  entonces usar la palabra Rep  al referirse a alguno de los 
campos de una variable de tipo Stack_ADT.  La Figura 5 ilustra  la 
reaccin del compilador al uso del Rep para implementar un ADT.

     En  el ejemplo de la Figura 5  la variable "s" es la pila que 
el  programador podr  usar, depositando y  recuperando objetos de 
tipo Elem_ADT.  El tipo Rep_Stack es la representacin, interna  y 
privada,   del  ADT.    Es  posible  definir   variables  de  tipo 
Stack_T.Rep_Stack, como es el caso de la variable r, pero lo usual 
es hacerlo nicamente  al escribir el  cdigo que implementa  cada 
una de las operaciones  de un ADT.  En  un lenguaje como C++,  que 
tiene  un mejor soporte para  ocultamiento de datos, sera posible 
impedir que el programador usuario del Stack_ADT tuviera acceso  a 
la representacin interna del tipo de datos abstracto pila.   Como 
Pascal no fue diseado para implementar ADTs, no es posible  hacer 
sto.  Debe confiarse  en que el  programador no abusar  del ADT, 
metindosele  al  Rep.  (La  versin 6.0  de Turbo  Pascal permite 
definir campos privados, pues ste compilador ya tiene un  soporte 
bastante adecuado para programacin por objetos).

     Cuando se usa abstraccin de datos sin ocultamiento de datos, 
es  muy comn que el novicio con  frecuencia se le mete al Rep por 
pereza  de  definir y  usar las  respectivas operaciones.   Es ms 
cmodo violentar el ADT, que usar sus operaciones. La tentacin es 
ms fuerte cuando es el mismo programador quien ha definido un ADT 
y, para ahorrar tiempo al digitar su programa, simplemente usa  la 
parte  interna del tipo de datos.   En general, es difcil no usar 
cada campo "directamente".

     Pero  el no  usar ocultamiento de  datos es contraproducente, 
pues  entonces  el compilador  podr hacer  menos trabajo  para el 
programador.   Adems,  si la  implementacin del  ADT cambia,  un 
programa que lo  use  deber  tambin  modificarse.   Pero  si  un 
programa nicamente  usa las  operaciones del  ADT, siguiendo  las 
reglas de su especificacin, y nunca se le mete al Rep, al cambiar 
la implementacin del ADT bastar recompilar el programa junto  al 
nuevo  ADT.   De  esta  manera  se  logra  mejorar  o  cambiar  la 
implementacin de un ADT, sin modificar los programas que lo usan. 
Esta  es,  en  mayor  cuenta, la  modularizacin adicional  que se 
deriva del uso  de  abstraccin  de  datos  respecto  del  uso  de 
programacin estructurada.

     Para implementar  las  operaciones  del  ADT  el  programador 
deber  usar mucho la transferencia de  tipos.  En el caso del ADT 
pila, deber transformar variables del tipo Stack_ADT en variables 
tipo  Rep_Stack.    Cada  operacin   del  ADT   contendr  muchas 
instrucciones  en que  aparecer Rep_Stack, o  simplemente Rep.  A 
primera vista incomoda un poco ver Rep tantas veces, pero es fcil 
aceptar este hecho  al reconocer que  cada vez que  se usa Rep  es 
porque  se tiene acceso  a la parte interna  del ADT.  Visto desde 
este sesgado punto de vista, el  uso de Rep ayuda a documentar  el 
cdigo del programa, en lugar de opacar su claridad.

     En la experience del autor, para aceptar el uso de la palabra 
Rep en los programas  se requiere de tres  semanas, en las que  se 
produce un serio conflicto personal en contra de Rep. Al principio 
los  programas se ven feos, y  llenos de garabatos que estorban la 
vista. Pero al llegar la cuarta semana, el cerebro se acostumbra a 
ver  lo que  debe ser, y  la palabra Rep  pasa a ser  una molestia 
necesaria y aceptable.

     Como  es costoso  usar cada una  de las operaciones  del ADT, 
pues hay que hacer  un llamado de subrutina,  se objeta el uso  de 
ocultamiento de datos por esta prdida de eficiencia. Esto mueve a 
muchos programadores a no usar el truco del Rep por "eficiencia".

     Lo cierto es que un programa debe estar correcto antes de ser 
eficiente.  El sobretrabajo que  implica usar las operaciones  del 
ADT  en  muy pocos  casos justifica  romper la  modularidad de  un 
sistema. Adems, pronto comenzaremos a ver versiones de Pascal que 
permitan desarrollar el cdigo de una subrutina en lnea (inline), 
que es un  proceso por el  cual se sustituye  la invocacin a  una 
rutina por el cuerpo que la implementa, como si fuera una "macro".  
Con esto se lograra que el  acceso a los componentes del ADT  sea 
tan   eficiente   como  usar   directamente  los   campos  de   la 
representacin privada del dato, lo  que dara al traste con  esta 
objecin. Esto es el curso seguido al definir C++.

     El truco  del Rep  le permite  a cualquier  programador tener 
acceso a la parte interna del ADT, si as lo desea.  Para lograrlo 
deber usar la palabra Rep, ya sea al declarar una variable  (como 
es el  caso  al  declarar  r  en  el  ejemplo),  o  al  hacer  una 
transferencia  de  tipos, que  es el  caso de  la asignacin  a la 
variable r en la Figura 5.  Al mencionar explcitamente la palabra 
Rep, el programador de hecho reconoce que est irrumpiendo en  las 
partes privadas del ADT, y que es consciente de sus actos.

     Muchas  veces   sucede  que   dos  o   ms  ADTs   estn  muy 
relacionados; en  esos casos  se puede  acceso a  cada una  de sus 
partes internas desde  el  otro  sin  mayor  problema,  usando  la 
cualificacin  de identificadores para  los tipos Rep respectivos.  
Por  ejemplo,  si  se  definen  juntos  los  tipos  Matriz_ADT   y 
Vector_ADT,  es de suponer  que cada uno de  ellos uno pueda tener 
acceso a la representacin interna del otro, en aras de mejorar la 
eficiencia  de  la  implementacin.   En este  caso, dentro  de la 
unidad Matriz_T se  puede usar el  Rep del Vector_ADT  simplemente 
declarando y  usando variables  de tipo  Vector_T.Rep_Vector. Otro 
ejemplo  lo  constituyen  los  iteradores,  que  se  discuten  ms 
adelante.

     Usando el truco del Rep es posible implementar el concepto de 
"tipos amigos"  de  C++.   Un  tipo  es  amigo  de  otro,  si  sus 
operaciones  tienen  acceso a  las partes  privadas del  otro.  En 
general, la "amistad" no es un relacin simtrica. No es tan usual 
encontrar tipos amigos en programas Pascal como lo es en programas 
C++, debido a sus limitaciones como lenguaje de computacin.


4. ADTs elementales y ADTs contenedores
=======================================

     El ADT  pila es  un tipo  especial de  dato, pues  su funcin 
primordial es contener a otros datos. No puede concebirse una pila 
que no contenga  elementos (que no  es lo mismo  que una pila  que 
est, en cierto momento, vaca). Los ADTs cuya funcin es contener 
a otros datos se llaman  "contenedores".  En este artculo se  usa 
mucho el trmino "ADT contenedor", del que la pila es un  ejemplo, 
o  "ADT  contenido", que  en la  mayora de  los casos  es un  ADT 
elemental.  Ambos trminos son necesarios para diferenciar bien el 
papel de cada ADT.

     En general, en todo programa se usan muchos ADTs  elementales 
y contenedores.  Por  ejemplo,  si  se  escribe  un  programa  que 
permita  simular  las vas  de la  ciudad capital,  con el  fin de 
determinar el tiempo que una persona debe invertir para viajar  de 
un   punto  a   otro,  entonces  debern   definirse  varios  ADTs 
elementales: Persona_ADT, Lugar_ADT, Hora_ADT, etc. Adems,  deben 
usarse muchos tipos de ADTs contenedores, como Bus_ADT,  Auto_ADT, 
Moto_ADT, Calle_ADT,  Ruta_ADT, etc.   Cada uno  de estos  ltimos 
contiene a otro ADT: el auto, el bus y la moto contienen personas, 
la ruta contiene varias calles y la calle contiene buses, autos  y 
motos. De este ejemplo se desprende que algunos contenedores, como 
el Bus_ADT, tambin pueden ser el elemento contenido en otro  ADT. 
En general, un  programa consta de  sus ADTs, y  de procedimientos 
que los manipulan  para  obtener  el  resultado  esperado.   Estos 
procedimientos son la "goma"  que pega a los  ADTs, y son los  que 
contienen la "lgica" que implementa un sistema.

     Existen varios tipos importantes de ADTs contenedores,  entre 
los que se  destacan la pila,  la cola, el  arreglo, la lista,  el 
rbol, el grafo y el conjunto.  Algunos de estos ADTs forman parte 
intrnseca  del lenguaje Pascal, que es  el caso de los arreglos y 
los conjuntos de escalares,  mientras que otros deben  programarse 
en una unidad aparte, como en el caso de la lista o la pila. Estos 
ADTs contenedores son sumamente importantes, hasta el punto de que 
se han escrito muchos libros para describirlos y estudiarlos, pues 
prcticamente todas las  estructuras  de  datos  interesantes  son 
trucos para implementar ADTs contenedores, o son mezclas de ellos. 
Por ejemplo, una multilista es un ADT en que cada objeto pertenece 
a varias listas.

     Entonces el mundo de los tipos de datos est dividido en  dos 
grandes clases: los  contenedores y los  elementales.  A veces  un 
contenedor  contiene a otro.  Por  ejemplo, puede hacerse una pila 
que contenga colas de rboles de listas de arreglos de matrices de 
personas.   La gran ventaja de usar  ADTs es que esta maraa puede 
definirse de  una forma  relativamente mecnica,  usando cada  ADT 
como un elemento contenido en otro ADT contenedor.


5. Implementacin de Elem_T
===========================

     Es  natural que  los ADTs elementales  tengan propiedades ms 
simples que los contenedores, por lo que deben estudiarse primero.  
Para  esto  lo  ms  simple  es  referirse  a  una  implementacin 
especfica, que se presenta en los Listados 1 y 2.  Estos listados 
contienen dos posibles implementaciones para la unidad Elem_T, que 
se usa  para describir  los datos  contenidos en  una pila.   Esta 
ltima tiene su  implementacin  en  la  unidad  Stack_T,  que  se 
discute ms adelante.

     Las  operaciones  de  la  unidad  Elem_T  son  muy   simples: 
inicializar un  dato, almacenarle  el valor  correspondiente a  un 
nmero entero, imprimirlo, copiar valores de y a variables de tipo 
Elem_ADT,  escribirlo  o  leerlo   de  un  archivo,  etc.    Estas 
operaciones  son comunes  a todos los  tipos de datos,  por lo que 
esta unidad  puede usarse  como plantilla  para definir  cualquier 
tipo abstracto de datos simple.

==================================================================
                 Operaciones de un ADT Elemental

PROCEDURE Init    (VAR {-} e : Elem_ADT);
PROCEDURE Clear   (VAR {?} e : Elem_ADT);
PROCEDURE Done    (VAR {?} e : Elem_ADT);
FUNCTION  OK      (VAR {+} e : Elem_ADT) {>>>>} : BOOLEAN;

PROCEDURE Copy    (VAR {?} x : Elem_ADT; VAR {+} y : Elem_ADT);
PROCEDURE Move    (VAR {?} x : Elem_ADT; VAR {?} y : Elem_ADT);
FUNCTION  Equal   (VAR {+} x, y : Elem_ADT) {>>>>} : BOOLEAN;

PROCEDURE Load    (VAR {?} e : Elem_ADT; VAR {+} F: FILE);
PROCEDURE Store   (VAR {+} e : Elem_ADT; VAR {?} F: FILE);

PROCEDURE Get     (VAR {+} e : Elem_ADT; VAR {+} .......);
PROCEDURE Put     (VAR {?} e : Elem_ADT; VAR {+} .......);

PROCEDURE Print   (VAR {+} e : Elem_ADT);

                             Figura 6
==================================================================

     Es  importante  que  cualquier  ADT  tenga,  al  menos,   las 
operaciones definidas en la Figura 6 [Realmente este es un defecto 
del enfoque presentado en  este artculo, pero removerlo  requiere 
del uso de una gran cantidad de trucos que sern discutidos en  un 
otro  escrito]. De  esta manera, ese  ADT puede ser  usado como el 
elemento  contenido  en  cualquier  ADT  contenedor.   Adems,  al 
incluir todas estas  operaciones bsicas se  logra definir al  ADT 
mejor, y  se evita  que la  implementacin quede  incompleta.  Por 
ejemplo, para  definir Person_ADT  pueden seguirse  los siguientes 
pasos:

     Primero,  copiar  el archivo  "Elem_T.pas" a  "Person_T.pas", 
usando un comando del sistema operativo.

     Despus  basta sustituir (por medio  del editor de texto)  la 
palabra "Elem_" por "Person_" en toda la unidad Person_T.

     El  siguiente  paso  es   incluir  en  el  registro   llamado 
Rep_Person los campos relevantes a una variable de tipo Person_ADT 
(que podran ser nombre, edad, sexo, etc.).

     Por  ltimo, el programador  debe reprogramar las operaciones 
Copy, Move, etc., adecuadamente, en los casos que sea necesario.

     Con  este artculo se  incluyen dos posibles implementaciones 
para Elem_ADT: la del Listado 1 usa caracteres y la del Listado  2 
usa  nmeros enteros.  Las dos  implementaciones de Elem_T son muy 
similares, pero no todas  las implementaciones de operaciones  son 
iguales: como los  Reps son diferentes,  las operaciones Get  y el 
Put difieren notablemente.

     En una unidad que implemente un ADT contenedor los objetos de 
tipo Elem_ADT se obtienen nicamente por medio de las  operaciones 
de la  Figura 6.   Esto permite  reutilizar el  cdigo Pascal  que 
implementa el ADT contenedor, pues como slo usa esas  operaciones 
de Elem_T,  entonces  el  cdigo  fuente  del  ADT  contenedor  es 
independiente del  cdigo del  ADT contenido,  por lo  que es  muy 
fcil  crear una  nueva versin del  ADT contenedor para  un nuevo 
tipo de  datos contenido.   O sea,  es posible  crear una  unidad, 
Stack_T por ejemplo, que implementa el ADT pila, y luego usar  esa 
unidad como  plantilla para  obtener una  pila de  nmeros reales, 
enteros, Person_ADTs, o de "pilas de colas de rboles de listas de 
arreglos de matrices de personas".

     Las operaciones de la Figura 6 son las que se necesitan  para 
manipular los elementos contenidos en un ADT contenedor.  Como una 
de las  ms importantes  razones que  justifican el  uso de  tipos 
abstractos de datos es el reutilizar componentes de programas,  es 
muy  importante  que  estas   operaciones  bsicas  de  los   ADTs 
elementales estn claramente especificadas  y que formen parte  de 
cualquier implementacin  de un  ADT.  De  esta manera  es posible 
reutilizar   el   cdigo  que   implementa  los   diferentes  ADTs 
contenedores, que son  la base de  todas las estructuras  de datos 
que  se usan en computacin.  As  se logra abaratar el proceso de 
programacin, logrando al  mismo  tiempo  una  mejor  calidad  del 
producto obtenido.

     Las operaciones de Elem_T implican cierto sobretrabajo,  pues 
como Pascal  no cuenta  con procedimientos  que se  desarrollen en 
lnea, en ocasiones ser ms eficiente no usar una subrutina  para 
implementar las operaciones del ADT.  Por ejemplo, si Elem_ADT  es 
un  caracter,  al  copiarlo  hay  que  invocar  el   procedimiento 
Elem_T.Copy(x,y), cuando sera mucho ms rpido simplemente copiar 
el  caracter "y" sobre  "x" usando la asignacin  "x := y;".  Esta 
operacin  Copy  puede  implementarse  muy  eficientemente,   pues 
requiere tal vez de  dos  o  tres  instrucciones  en  lenguaje  de 
mquina, y los consiguientes accesos a la memoria principal,  pero 
como es necesario hacer un  llamado a una subrutina para  mantener 
la  modularidad del ADT, el resultado  es que Copy cuesta veinte o 
treinta  instrucciones  de mquina  por ejecucin.   Por eso  para 
incrementar  la eficiencia  es importante que  el compilador pueda 
desarrollar en cdigo en lnea.

     La capacidad de  poder definir exactamente  un tipo de  datos 
que pueda ser utilizado en cualquier contexto justifica plenamente 
la pequea ineficiencia en que se incurre al llamar a la subrutina 
que implementa cada operacin del ADT.  Es este el precio que debe 
pagarse para lograr  reutilizar cdigo.  Para  un defensor de  los 
ADTs es fcil  afirmar  que  son  pocos  los  casos  en  que  este 
sobretrabajo  afecta sensiblemente el  rendimiento de un programa; 
es difcil estimar  qu  tan  cercana  a  la  realidad  est  esta 
afirmacin.

     Pero si se acepta la heurstica de que el 20% del programa es 
el que se ejecuta  el  80%  del  tiempo,  entonces  puede  tambin 
afirmarse que las "ineficiencias" producto del uso de  abstraccin 
de datos estarn  muy  "localizadas",  por  lo  que  ser  posible 
"optimizar" una pequea parte del programa para lograr un programa 
"eficiente". Estas afirmaciones son producto de la intuicin,  que 
no  ha sido  verificada cientficamente por  el autor: seguramente 
las mejoras en los compiladores harn inatinentes estas preguntas. 
Lo mejor es  usar  desde  ya  abstraccin  de  datos,  aunque  los 
compiladores que la soporten no estn todava disponibles.

     Los lenguajes que tienen amplio soporte para ocultamiento  de 
datos, como  CLU  [Liskov-86],  ADA  [Ichbiah-79]  y  Pascal  Plus 
[Bustard-88], automticamente generan  algunos de las  operaciones 
que  se mencionan en  Elem_T (con lo que  tambin pueden evitar el 
sobretrabajo que significa el llamar a la subrutina que implementa 
cada operacin). En C++, el uso de cdigo que se expande en lnea, 
que  tiene el mismo efecto de  los macros en C, elimina totalmente 
esta  ineficiencia.   En  Pascal,  si  se  necesita  expander  una 
subrutina  en  lnea, por  razones de  eficiencia, el  programador 
tiene que hacerlo manualmente.

     En general, para cualquier tipo de datos es necesario  contar 
con todas las operaciones definidas en la Figura 6, salvo tal  vez 
la  operacin Print y, en en  casos muy calificados, Load y Store.  
A   continuacin  se  discuten  en   detalle  cada  una  de  estas 
operaciones. Cabe destacar que los nombres utilizados son los  que 
Borland usa en  sus  ejemplos  (e  ir  contra  Borland,  en  estos 
momentos, es ir contra corriente...).

Init(e):  inicializa la variable  "e", posiblemente usando memoria 
     dinmica o dando valores  a  los  campos  del  Rep  del  ADT.  
     Muchos ADTs se implementan usando punteros que deben tener el 
     valor apropiado antes de que puedan ser utilizados.

     La  regla general,  y casi absoluta,  es que es  vital que el 
     programador inicialice todos los objetos o variables que usa. 
     "Init"  y  "Done"  son  tan importantes  que hasta  tienen su 
     propio   nombre:   son   conocidos   como   constructores   y 
     destructores.

     La operacin  Init(e) puede  implicar desde  poner en  "0" el 
     Rep(e)  hasta crear  una complicada estructura  de datos bajo 
     "e".  Debe hacerse exactamente  un llamado a esta  operacin, 
     preferiblemente  al  principio del  procedimiento en  que "e" 
     est  definida.  Adems, si el  espacio para "e" fue obtenido 
     mediante la operacin NEW, entonces inmediatamente despus de 
     esa invocacin debe estar el llamado a Init.

     Init deja a su argumento  en un estado inicial vlido,  listo 
     para utilizarlo  en  cualquier  operacin.   En  el  caso  de 
     objetos simples, como  punteros  o  nmeros,  el  Init  puede 
     limitarse  a asignar  a "e" un  valor nulo, como  NIL o cero.  
     Pero si  el Elem_ADT  es una  estructura complicada,  el Init 
     tiene  la  misin  de  dejar al  objeto en  un estado  que le 
     permita funcionar.  Por ejemplo,  puede que se asigne  cierta 
     memoria adicional a  la variable "e"  antes de que  pueda ser 
     utilizada, o que ciertos de sus campos tengan algunos valores 
     especiales.

     Todas las operaciones  de un ADT  trabajan sobre objetos  que 
     han sido  adecuadamente inicializados  mediante Init.   Todos 
     los programadores conocen tan bien esta regla que lo usual es 
     no mencionarla siquiera.  No inicializar un ADT es un  pecado 
     mortal,  hasta el  punto de que  el inicializar correctamente 
     las variables es una de las primeras reglas que aprende  cada 
     programador.  Como todo el mundo "sabe" esto, lo usual es  no 
     repetirlo en cada clusula REQUIERE.

Done(e):  destructor  para   "e".   Generalmente  esta   operacin 
     devuelve al  sistema  la  memoria  (dinmica)   que  ha  sido 
     asignada a "e".  Done es el inverso de Init.  Es una  funcin 
     totalmente terminante, pues deja completamente inservible  el 
     objeto "e", hasta el punto de que para volver a utilizarlo es 
     necesario inicializarlo  con  Init.   Init  y  Done  son  muy 
     importantes principalmente  para  ADTs  contenedores,  aunque 
     tambin deben incluirse estas operaciones para cualquier  ADT 
     elemental.

     Para toda variable debe hacerse exactamente una invocacin  a 
     Done.  Si la variable "e"  est definida en un procedimiento, 
     dentro  del bloque de definicin  VAR, entonces debe haber un 
     llamado  a  Done(e)  al  final  del  procedimiento.   Si  fue 
     definida usando NEW, entonces el llamado a Done debe preceder 
     inmediatamente al  llamado  a  DISPOSE  correspondiente.   En 
     algunos casos un programador diestro puede retardar el uso de 
     Init, o adelantar el de Done: pero esto debe hacerse con sumo 
     cuidado.  La  correccin de  errores de  programacin que  se 
     derivan de usar objetos inadecuadamente inicializados es  muy 
     compleja,  slo secundaria  en dificultad a  la depuracin de 
     programas que utilizan procesos concurrentes (en [Bustard-88] 
     esto se discute "grosso modo").

     Desgraciadamente, en  Pascal  el  programador  debe  ser  muy 
     disciplinado,  hacendoso  y   organizado  al  inicializar   y 
     destruir cada instancia  de un ADT,  de tal modo  que siempre 
     incluya exactamente un llamado a Init y otro a Done para cada 
     instancia de  un  ADT.   De  lo  contrario  el  uso  del  ADT 
     ocasionara  serios  problemas.  En  C++ y  Pascal Plus  este 
     problema no existe, pues el compilador se encarga de insertar 
     en  el cdigo generado  el llamado a Init  (y Done) para cada 
     variable.

     Un error muy  comn es usar  una variable no  inicializada, o 
     devolver varias  veces al  sistema la  misma localizacin  de 
     memoria. Stroustrup dice que C++ "soporta" la abstraccin  de 
     datos, mientras que Pascal simplemente la "permite", pues  en 
     Pascal el programador  debe  ser  "cuidadoso"  y  no  olvidar 
     invocar a los constructores  y destructores, mientras que  en 
     C++ el compilador  tiene  la  responsabilidad  de  hacer  los 
     llamados a Init y Done para cada variable que lo requiera.

Clear(e): reinicializa la variable "e".  El valor anterior de  "e" 
     se  pierde, y su  valor actual pasa a  ser exactamente el que 
     tena despus de que se ejecut Init(e).  O sea, que Clear es 
     un Done suave, pues no inutiliza totalmente a "e", aunque  si 
     "borra" su anterior contenido.

     En muchos casos las tres operaciones Init, Clear y Done hacen 
     exactamente  lo  mismo. Pero  cuando el  Elem_ADT es  un poco 
     complejo, puede que el ejecutar un Clear sea mucho ms barato 
     (en  trminos de tiempo de  ejecucin)  que ejecutar un Done.  
     Para evitar problemas, al programar un ADT debe usarse Done y 
     Init  slo  una  vez  en cada  variable, y  el Clear  se debe 
     utilizar   cuando   es    necesario   limpiar   un    objeto.  
     Conceptualmente, el efecto de Clear es equivalente a un  Done 
     seguido inmediatamente de un Init.

OK(e): esta operacin  verifica  que  la  invariante  del  ADT  se 
     cumpla,  sin cambiar el valor  de la instancia. La invariante 
     es  un predicado, a veces  expresado en forma matemtica, que 
     siempre  se cumple para una  instancia del ADT.  Por ejemplo, 
     en una  lista  la  invariante  puede  ser  que  a  cado  nodo 
     siguiente  el  apunta el  anterior, y  que la  lista nula  se 
     representa como NIL.  En este ejemplo, OK(L)  ser  verdadero 
     siempre  que la lista L  est correctamente construida, y que 
     tambin lo estn sus elementos.

     La operacin  OK es  en general  muy difcil  de implementar, 
     pues lo natural es que  funcione aun cuando la instancia  del 
     ADT est quebrada.  La experiencia del autor es que  arreglar 
     un ADT roto es muy difcil, por lo que es mejor definir el OK 
     como  una  operacin  que  siempre  retorna  TRUE  cuando  la 
     instancia del ADT  cumple con su  invariante, y cuando  no es 
     as hace "lo  posible" por retornar  el valor FALSE.  Pero en 
     este ltimo caso  puede  ser  que  OK  simplemente  no  pueda 
     sobreponerse a la destruccin de  la instancia del ADT, y  el 
     resultado sea un programa incorrecto o interminable.

     El  autor  ha tenido  la tentacin  de definir  una operacin 
     llamada  FIX, que se encarge  de des-quebrar una instancia de 
     ADT  que est  quebrada.  Pero parece  que es conceptualmente 
     impropio darle a un programador herramientas que le  permitan 
     ser  descuidado al programar; mejor  es exigir calidad en los 
     programas. Sin  embargo, existen  muchas aplicaciones  en que 
     sera ms fcil implementar  programas robuztos si se  cuenta 
     con una operacin como FIX.

Copy(X,Y): este procedimiento retorna en X un duplicado del objeto 
     Y.   Al copiar objetos el  programador desea que al modificar 
     el  objeto  X  no  se  modifique  ni  Y  ni  alguno  de   sus 
     componentes.  Esto  significa que  no hay  memoria compartida 
     por  X y  Y, pues estos  dos objetos deben  ocupar un espacio 
     diferente  en la memoria del  computador. Lo primero que casi 
     todas  las  implementaciones  de  Copy  hacen  es  limpiar  X 
     invocando a Clear(X).

     Siempre que el  programador escribe "X  := Y;" en  Pascal, el 
     cdigo  generado por el compilador  es duplicar, bit por bit, 
     todo el contenido de la  variable "Y" sobre la variable  "X".  
     Aunque  no es  el caso de  las implementaciones de  Elem_T en 
     este artculo, muchas  veces  no  es  suficiente  simplemente 
     copiar  bits,  como lo  hace una  asignacin de  Pascal, para 
     copiar un objeto.   Por eso es  muy importante que  la unidad 
     Elem_T  contenga  la operacin  Copy, que  permite copiar  un 
     Elem_ADT sobre otro.

     Cuando se trabaja con objetos complejos, lo usual es que  una 
     parte  de  ellos est  en memoria  dinmica.  En  estos casos 
     hacer  una copia superficial bit por  bit de un objeto a otro 
     no  es suficiente.  Para copiar estos  objetos complejos, que 
     son  los ms "interesantes", es  necesario copiar no slo las 
     posiciones de  memoria de  una variable,  sino todas  las que 
     estn conectadas con ella, pero que aparecen en otra parte de 
     la memoria.

     Por ejemplo,  si el  objeto por  copiar es  un rbol  con una 
     complicada  estructura  de punteros,  al copiarlo  habra que 
     recorrerlo todo y reproducir cada uno de sus nodos y cada una 
     de sus conexiones.  Al copiar  el rbol no basta slo  copiar 
     la raz, pues es necesario  tambin copiar todos los nodos  a 
     ella  conectados.   Si para  hacer el  duplicado se  usara la 
     instruccin de asignacin  Pascal  "X  :=  Y;",  se  copiara 
     nicamente el nodo raz, y el resultado sera dos nodos  raz 
     que apuntan al mismo conjunto de nodos.  No se obtendria en X 
     una copia del arbol Y, sino dos races apuntando a los mismos 
     descendientes, que no es lo que se quiere.

     Como la  operacin  Copy  no  es  trivial  de  programar,  el 
     programador  debe  ser cuidadoso  al implementarla.  Un error 
     usual  es implementar un Copy que  no copia, pues no crea una 
     instancia totalmente  nueva de  cada objeto.  En estos  casos 
     puede  que el programa funcione  bien por mucho tiempo, hasta 
     que llegue a una parte en  que el no usar una copia  produzca 
     una falla. Lo malo es que estos errores son muy difciles  de 
     detectar, pues la falla puede ocurrir mucho despus de que la 
     copia de un objeto se ha hecho.

     A veces hay que evitar copiar objetos, por el costo en uso de 
     memoria y tiempo de ejecucin  que Copy implica.  En el  caso 
     del rbol  muchos veces  no es  necesario copiarlo  completo, 
     pues basta con trasladarlo de una variable a otra.  En  estos 
     casos, tiene sentido usar el Move en lugar del Copy.

Move(X,Y):  Esta operacin permite trasladar  el objeto Y para que 
     quede almacenado en la variable X. Los valores previos de X y 
     Y se pierden  irremisiblemente. El nuevo  valor de X  ser el 
     que Y tena.  El  valor de Y ser  el de una variable  que ha 
     sido recin  inicializada  con  Clear.   De  hecho,  aparecen 
     llamados   a  Clear(X)    y  Clear(Y)   en   casi  todas  las 
     implementaciones de Move.

     En  el caso de  tipos de datos muy  simples esta operacin se 
     implementa con una simple asignacin (Copy).  Pero la ventaja 
     que tiene el Move sobre el Copy es que el primero puede tomar 
     mucho  menos tiempo para objetos  muy grandes y de estructura 
     muy complicada.  Piense  el  lector  en  el  caso  del  rbol 
     mencionado anteriormente: trasladar el objeto de Y a X  puede 
     lograrse copiando nicamente  el nodo raz  Y sobre X,  y tal 
     vez actualizando algunos punteros que antes apuntaban hacia Y 
     para que apunten a X. El trabajo total sera mucho menor  que 
     el necesario  para hacer  un Copy  completo.  Adems,  muchas 
     veces no  se quieren  tener varias  copias del  mismo objeto, 
     sino que el objeto aparezca slo una vez en la memoria.

     El Move puede  verse  como  un  truco  de  programacin,  que 
     permite pasar  un objeto  de un  lugar a  otro de  una manera 
     rpida ("eficiente").  Es til si se desea meter  rpidamente 
     dentro  de un ADT contenedor  un objeto, invalidando la copia 
     original (posiblemente porque no se necesita ms).

Equal(X,Y): Retorna el valor TRUE cuando el objeto X es igual a Y. 
     Existen al menos dos definiciones de igualdad.  La ms  comn 
     es que dos objetos sean iguales cuando tienen el mismo valor: 
     si X y Y  son  dos  variables  que  contienen  el  nmero  3, 
     entonces Equal(X,Y) ser verdadero.  Si Elem_ADT es un  rbol 
     o cualquier otra estructura de similar complejidad,  entonces 
     el  procedimiento  que   determina  igualdad  podra   exigir 
     nicamente que  los  nodos  de  los  rboles  X  y  Y  fueran 
     "isomrficos", o que  tuvieran  cualquier  propiedad  por  el 
     estilo.   En general  es importante que  la implementacin de 
     Equal  sea "razonable",  de forma que  el programador usuario 
     del ADT no necesite ver la implementacin para adivinar si el 
     concepto  de  igualdad implementado  con Equal  es el  que l 
     espera.

     Es posible ser ms exigentes para definir igualdad.  En  Lisp 
     existen dos funciones bien definidas a este efecto: (Eq X  Y)  
     es  verdadero  slo  cuando  X y  Y son  punteros a  la misma 
     localizacin  de  memoria; (Equal  X Y)  es verdadero  si los 
     valores de X y Y son iguales.  En la mayora de las ocasiones 
     la  definicin de igualdad que  el programador necesita es la 
     segunda.

Load(X,F) y Store(X,F): Estas operaciones permiten almacenar en  y 
     recuperar de un  archivo  al  objeto  X.   Necesariamente  el 
     programador usuario debe haber abierto el archivo F. De  esta 
     manera es posible escribir y restaurar X, lo que le brinda al 
     programador usuario una gran flexibilidad para programar.  En 
     muchas ocasiones  un programador  necesita guardar  el estado 
     actual de una  variable, pero su  estructura de datos  es tan 
     complicada que opta por reconstruirla.  Precisamente es  sta 
     la  razn  que  justifica  programar  estas  dos  importantes 
     operaciones.   Adems, esta facilidad  permite enviar, de una 
     mquina a otra,  copias de objetos,  lo que es  muy apreciado 
     cuando se construyen programas realmente grandes.

     A primera vista parece  que el implementar estas  operaciones 
     es tarea  fcil.  Este  es el  caso para  ADTs simples,  como 
     enteros  o  nmeros  reales.   Pero  si  el  ADT  tiene   una 
     intrincada  estructura,  como es  el caso  de un  rbol o  un 
     grafo,  entonces el  programador deber ser  muy cuidadoso al 
     almacenar  las partes de X en  F, pues debe asegurarse de que 
     sea posible reconstruirlo adecuadamente.

     En el caso del compilador Turbo Pascal, necesariamente F debe 
     ser un archivo sin tipo, pues el tamao y forma del objeto  X 
     no puede determinarse de antemano.  En estas implementaciones 
     es  prcticamente  obligatorio el  uso de  los procedimientos 
     BlockRead  y BlockWrite  de la biblioteca  Turbo Pascal, como 
     puede verse en los  Listados  4  y  5.   Para  Modula-2  debe 
     utilizarse la biblioteca  respectiva,  que  depende  de  cada 
     compilador.

     Las operaciones Load  y  Store  de  un  ADT  le  permiten  al 
     programador  usuario  archivar  en  memoria  permanente   una 
     instancia  de  un objeto.  Pero no  es razonable  esperar que 
     quien implementa un ADT tambin defina un sofisticado sistema 
     de archivo para almacenar instancias  del ADT, por lo que  el 
     programador  usuario  deber hacerlo  cuando as  lo necesite 
     (que  posiblemente  sea  en  muy  pocas  ocasiones).  Por  lo 
     anterior, el programador  usuario no debe  esperar que F  sea 
     algo ms que un archivo secuencial.

Get(X,...)   y  Put(X,...):  en  general,  estas  dos  operaciones 
     permiten leer y cambiar los campos o componentes del ADT.  En 
     muchos casos se tienen muchas operaciones a este efecto, y lo 
     usual es que  un ADT contenedor  nunca use estas  operaciones 
     del ADT contenido.

     Estas dos  operaciones son  las mejores  candidatas para  ser 
     implementados en  lnea, pues  generalmente lo  que hacen  es 
     leer o cambiar  un campo del  Rep del ADT.   Si un ADT  tiene 
     muchos  campos, entonces necesitar  muchas operaciones Get y 
     Put: una pareja para cada campo.  Como puede resultar tedioso 
     definir tantos procedimientos, a veces se agrupa en uno  slo 
     el  acceso  a varios  campos, aunque  esto implique  una leve 
     prdida de eficiencia.

Print(X): esta  operacin permite  imprimir el  objeto X.   En los 
     listados adjuntos se incluye, aunque en la prctica es  mejor 
     no incluir esta operacin para el ADT, principalmente  porque 
     un objeto puede imprimirse de muchsimas formas diferentes.

     En general  es difcil  definir cmo  debe imprimirse  un ADT 
elemental. Una alternativa es que el programador usario use el Get 
para sacar cada campo relevante, y que luego lo imprima con  Write 
y WriteLn.  Otra es definir una unidad amiga del ADT, que contenga 
varias opciones diferentes de impresin para el ADT.  An otra  es 
definir una operacin que transforme X en una tira de  caracteres, 
o  en  un  arreglo  de  tiras,  que  pueda  luego  ser  desplegado 
cmodamente usando WriteLn.

     Es   muy  importante  destacar   que  los  ADTs  contenedores 
generalmente usan todas  las  operaciones  de  la  Figura  6  para 
manipular el ADT contenido,  salvo  Get,  Put  y  Print.   Es  muy 
importante que todo ADT tenga definidas estas operaciones, pues de 
lo contrario, en algunos casos no podr ser el elemento  contenido 
en un ADT contenedor.

     Una sana  regla para  definir las  operaciones de  un ADT  es 
incluir todas  las  mencionadas  en  esta  seccin,  y  otras  que 
completen la  implementacin.   Esto  quiere  decir  que  no  debe 
dejarse por fuera una operacin que luego obligue a un programador 
usuario del ADT a implementarla.  Por ejemplo, si se implementa la 
unidad BCD_T, de nmeros decimales, entonces sera un error  dejar 
por  fuera la funcin de  comparacin Less(X,Y), o alguna similar.  
Por la  misma razn,  es necesario  que se  implementen nicamente 
aquellas  operaciones  que puedan  ser ejecutadas  eficientemente, 
pues  de lo contrario el  programador usuario tendr problemas con 
el rendimiento de su programa si usa el ADT.


6. Operaciones bsicas de un ADT contenedor
===========================================

==================================================================
                 Operaciones de un ADT contenedor

PROCEDURE Init     ( VAR {-} C : Cont_ADT);
PROCEDURE Clear    ( VAR {?} e : Cont_ADT);
PROCEDURE Done     ( VAR {?} C : Cont_ADT);
FUNCTION  OK       ( VAR {+} e  Cont_ADT ) {>>>>>} : BOOLEAN;

PROCEDURE Copy     ( VAR {?} x : Cont_ADT; VAR {+} y : Cont_ADT );
PROCEDURE Move     ( VAR {?} x : Cont_ADT; VAR {?} y : Cont_ADT );
FUNCTION  Equal    ( VAR {+} x, y : Cont_ADT ) {>>>>>} : BOOLEAN;

PROCEDURE Load     ( VAR {?} C : Cont_ADT; VAR {+} F : FILE );
PROCEDURE Store    ( VAR {+} C : Cont_ADT; VAR {?} F : FILE );

FUNCTION  Empty    ( VAR {+} C : Cont_ADT) {>>>} : BOOLEAN;
FUNCTION  Full     ( VAR {+} C : Cont_ADT) {>>>} : BOOLEAN;

PROCEDURE Insert   ( VAR {?} C : Cont_ADT; VAR {+} e : Elem_ADT );
PROCEDURE Delete   ( VAR {?} C : Cont_ADT; VAR {?} p : Pos_T );
PROCEDURE Retrieve ( VAR {+} C : Cont_ADT;     {+} p : Pos_T )
          {>>>>>}  : Elem_P;
FUNCTION  Locate   ( VAR {+} C : Cont_ADT; VAR {+} e : Elem_ADT )
          {>>>>>}  : Pos_T;

PROCEDURE Print    ( VAR {+} C : Cont_ADT );

                             Figura 7
==================================================================

     Despus  de  examinar  las  operaciones  bsicas  de  un  ADT 
elemental,  es  interesante conocer  las operaciones  de los  ADTs 
contenedores, que se muestran en  la Figura 7. Obviamente, el  ADT 
contenedor debe tener al menos  las operaciones bsicas de un  ADT 
elemental, ms otras operaciones para meter y sacar elementos  del 
ADT,  como son el Push y Pop en  el caso de la pila, el En_Queue y 
De_Queue en la cola, o el Insert y Delete en el conjunto.

     Init y Done ya han sido discutidos ampliamente.  Clear  tiene 
ms aplicacin en el contexto de contenedores que de ADTs simples, 
pues en  las implementaciones  de los  primeros con  frecuencia es 
necesario  mover elementos de un lugar  a otro usando Move, por lo 
que debe usarse Clear con frecuencia.

     Como  el tipo de datos por  almacenar en un ADT contenedor no 
puede determinarse de  antemano, el programador  del ADT debe  ser 
muy cuidadoso  al programar  las operaciones  Init, Clear  y Done, 
pues es relativamente difcil probar cada operacin adecuadamente.

==================================================================
      PROCEDURE Clear(  { EXPORT }          { Adolfo }
        {-} VAR S : Stack_ADT
      );
      VAR
        p,q : Rep_Stack;           { PILA DE PUNTEROS }
      BEGIN { Clear }              {==================}
        p := S.Rep;
        WHILE p <> NIL DO BEGIN
          q := p^.next;
          Elem_T.Done(p^.elem);
          DISPOSE(p);
          p := q;                  { evita usar p }
        END;
        S.Rep := NIL;
      END; { Clear }

                             Figura 8
==================================================================

     En la Figura 8 se muestra la implementacin del Clear del ADT 
pila implementado por punteros.  Antes  de destruir un nodo de  la 
lista  de  nodos, debe  destruirse el  elemento contenido.   Si el 
elemento contenido fuera, a su vez, un ADT contenedor, entonces el 
Clear de la pila estara iniciando una cadena de llamados para los 
destructores  de  los ADTs  contenidos, lo  que es  necesario para 
recuperar toda la memoria asignada a ellos. Pero cabe destacar que 
en la implementacin de una pila  por medio de arreglos no se  usa 
Elem_T.Done(),  pues  se  limpia  cada  entrada  de  la  pila  con 
Elem_T.Clear(), como se muestra en  la Figura 9.  En este  segundo 
caso el programador puede escoger  entre dejar la pila en  "estado 
Clear" o en "estado Done";  pero para la implementacin por  medio 
de punteros slo cabe usar el "estado Done".

==================================================================
      PROCEDURE Clear(          { EXPORT } { Adolfo }
        {-} VAR S : Stack_ADT   { Pila a limpiar.   }
      );
      VAR
        i : INTEGER;                   { PILA DE VECTORES }
      BEGIN { Clear }                  {==================}
        FOR i := S.Rep.ultimo-1 DOWNTO 0 DO BEGIN
          Elem_T.Clear(S.Rep.elem[i]);
        END;
        S.Rep.ultimo := 0;
      END; { Clear }

                             Figura 9
==================================================================

     La implementacin  de la  Figura 9  evita destruir  y recrear 
cada elem[i] cuando se hace un  Push o un Pop, pues mantiene  toda 
la pila inicializada  con todos los  elem[i]'s en su  estado vaco 
(Clear).   El mantener los  elem[i]'s inicializados puede requerir 
ms  memoria que  si se mantuvieran  en un estado  no inicializado 
(que es el estado en que los dejara Done). Pero de esta manera se 
evitara llamar a Elem_T.Init para  cada Push, y a Elem_T.Done  en 
cada  Pop, con lo que se  cambia espacio por tiempo, para aquellos 
Elem_ADTs  en que el estado Clear  ocupe ms espacio que el estado 
Done.

     El manejo  de memoria  dinmica tiene,  en general,  un costo 
significativo, por lo menos al compararlo con el uso de memoria en 
la pila  de  ejecucin  del  programa.   Esto  es  as  porque  el 
administrador  de  memoria dinmica (heap manager)  debe  mantener 
listas  de  espacio libre y espacio ocupado,  las  que  deben  ser 
recorridas  para  asignar  o desasignar  memoria.  En  una  prueba 
informal  hecha  por estudiantes,  se encontr que este tiempo  es 
significativo  en el caso del ADT pila,  cuando  deben  efectuarse 
muchas  operaciones  Push y Pop.  En esa evaluacin  informal,  se 
generaron  20,000  operaciones Push y Pop,  alternadas  con  otros 
operaciones  de  asignacin de memoria dinmica,  y el  tiempo  de 
corrida  del  programa que us la implementacin con punteros  fue 
hasta  dos  veces  mayor  que  el utilizado  por  el  que  us  la 
implementacin de vectores.

     Si hay  que  hacer  tanto  malabarismo  con  constructores  y 
destructores, valdr la  pena  el  esfuerzo  de  aprender  tantos 
detalles para  usar ADTs?   La razn  primordial de  usar ADTs  es 
lograr  una  alta modularizacin,  que permita  reutilizar cdigo. 
Para esto se necesita lograr que cada ADT sea independiente de los 
dems  mdulos  que  conforman  un  programa,  lo  que  tiene  por 
requisito el definir bien el papel de cada una de las  operaciones 
bsicas  del ADT.   El programador bisoo  puede encontrar difcil 
digerir esta tcnica  (pues  es  difcil),  aunque  para  l  ser 
difcil lo nuevo.   El  programar,  definitivamente,  no  es  para 
colegiales. Es una tarea difcil, reservada para profesionales.

     Al insertar  un elemento  en un  ADT contenedor  es necesario 
decidir si se usa el Elem_T.Copy o el Elem_T.Move.  Qu  criterio 
debe  usarse  para escoger  uno u  otro?  Obviamente  la respuesta 
depende del contexto de programacin, y es el programador  usuario 
del ADT contenedor quien debe decidir cul de las dos  operaciones 
usar.  En principio, el  programador-usuario de un ADT  contenedor 
debera poder escoger entre las dos alternativas, aunque el  costo 
de implementar  tanto  flexibilidad  puede  ser  prohibitivo.   Lo 
perfecto, es, enemigo de lo bueno.

     Como puede verse en la implementacin del la unidad  Stack_T, 
en los Listados 4 y 5,  en la implementacin de la operacin  Push 
se usa el vocable "Elem_T.Copy{_Move}": entre llaves de comentario 
est  la alternativa de usar Move  por Copy para insertar un nuevo 
elemento en la pila.  Si  el programador usuario necesita usar  el 
Move,  basta que  reemplace (usando un  editor de texto)   la tira 
"Copy{_Move}"  por "Move{_Copy}", en  todo el archivo Stack_T.pas, 
que contiene el cdigo fuente del ADT pila.

     Load(X,F)  y Store(X,F): La  implementacin del Load y  Store 
en un contenedor necesariamente debe hacer uso de las  operaciones 
Elem_T.Load()  y  Elem_T.Store().  Tal  vez el  mayor problema  al 
grabar en F un contenedor  es incluir ciertas marcas que  permitan 
reconstruir el objeto salvado.  Por ejemplo, en la  implementacin 
del Store de la pila se incluye un nmero de secuencia que permite 
determinar cuando se ha llegado al ltimo elemento de la pila.

     Empty  y   Full  son   operaciones  booleanas   que  permiten 
determinar si el contenedor est lleno o vaco.

     El siguiente grupo de  operaciones permite insertar y  borrar 
elementos del  contenedor.   La  operacin  Retrieve  recibe  como 
entrada  una  posicin,  que  es  un  indicador  dentro  del   ADT 
contenedor, y que apunta a uno de sus elementos.  Devuelve, no  un 
objeto,  sino ms  bien un puntero  al objeto contenido  en el ADT 
(pues el tipo regresado tiene  el sufijo "_P"), para evitar  hacer 
una copia del mismo.  Para sacar un elemento del contenedor,  debe 
usarse primero el Retrieve, luego el Copy o el Move, y por  ltimo 
el  Delete  (el  valor  de  p  despus  de  la  invocacin   queda 
indefinido).  En algunos contextos pueden ser ms elegante definir 
Retrieve  como un procedimiento, y no  como una funcin (que es el 
caso del Pop en Stack_T).

     El  clsico ejemplo de  un ADT contenedor es  la lista, de la 
que se incluye un extracto de su especificacin en el Listado 6.


7. Implementacin del programa UsaPila
======================================

     En esta seccin  se discute el  cdigo del programa  UsaPila, 
que es el  Listado 3.  Este  programa lee una  tira y la  invierte 
usando una pila.   Lo importante en  este ejemplo es  demostrar la 
separacin  que  existe  entre  la  interfaz  del  Stack_T  y   su 
implementacin.  En  UsaPila el  mismo cdigo  corre tanto  con la 
implementacin  de la pila  por medio de arreglos,  como con la de 
punteros.  El lector  puede  hacer  la  prueba,  sustituyendo  una 
implementacin por la otra.

     Lo nico que cambia al trocar una implementacin por la  otra 
es  la cantidad de tiempo de  ejecucin y de espacio requerido por 
el programa.

     El programa UsaPila  est basado en  el cdigo para  invertir 
una tira (Figura  4), pero no  se supone que  el tipo Elem_ADT  es 
CHAR. Necesita que exista una unidad adicional, llamada Elem_T, en 
donde se define el ADT contenido en la pila, y en el que el Rep de 
Elem_ADT es  CHAR.  Lo  importante es  que el  mismo cdigo  de la 
unidad Stack_T pueda  ser usada para  implementar el ADT  pila con 
diferentes tipos de datos, mediante la recompilacin las  unidades 
Stack_T y Elem_T.  Por ejemplo,  para hacer una pila que  almacene 
variables de tipo Person_ADT, basta  que en el tipo Rep_Stack,  el 
tipo Elem_ADT sea sustituido por Person_ADT.  Lo ms importante es 
que  el cdigo  fuente que implementa  la pila no  sea modificado, 
aunque la nueva unidad si debe ser recompilada.  Con esto se logra 
parametrizar  el tipo de datos  pila, pues la misma implementacin 
de Stack_T sirve para diferentes tipos de datos.

     En  la  implementacin de  la unidad  Stack_T, ya  sea en  la 
versin de punteros o vectores, se usa la operaciones  Elem_T.Copy 
y Elem_T.Move para insertar un nuevo elemento dentro de la pila.


8. Instanciacin de Stack_T
===========================

     Cmo logra un programador obtener una pila, ya no de enteros 
o caracteres, sino de matrices, o vectores? Cmo obtener una pila 
de pilas  de  personas  (o  sea,  una  en  la  que  los  elementos 
contenidos sean  a su  vez pilas  de personas)?   Lo nico  que el 
programador  debe  hacer para  esto es  instanciar dos  copias del 
archivo Stack_T.pas, que contiene el cdigo que implementa el  ADT 
pila, para el nuevo tipo de dato contenido.

     Para obtener  un  nuevo  tipo  de  datos  de  contenedor,  el 
programador debe copiar  uno o varios  archivos, y sustituir  unos 
identificadores.  Este proceso se conoce como instanciar un ADT, y 
es un proceso automtico en lenguajes como CLU, ADA y Pascal  Plus 
(el trmino instanciacin  tambin se utiliza  cuando se crea  una 
variable en memoria dinmica:  indica obtener una nueva  instancia 
de un tipo  de  datos).   En  Turbo  Pascal  el  programador  debe 
instanciar manualmente sus ADTs.

     La instanciacin del archivo Stack_T.pas se logra copiando el 
cdigo de "Stack_T.pas"  a  dos  nuevos  archivos:  "SS_Per_T.pas" 
(pila  de pilas de personas),  y "S_Per_T.pas" (pila de personas). 
En el archivo "SS_Per_T.pas" es necesario sustituir, por medio del 
editor, la tira  de caracteres "Stack_"  por "SS_Per_", y  "Elem_" 
por "S_Per_".
En el archivo "S_Per.pas" debe sustituirse "Stack_" por "S_Per_" y 
"Elem_" por "Person_".

     Como  "Elem_T.pas"  es  una  plantilla  para  cualquier   ADT 
elemental,  para  obtener el  Person_ADT basta  copiar el  archivo 
"Elem_T.pas" a otro, llamado "Person_T.pas", sustituir "Elem_" por 
"Person_", y luego reprogramar todas las operaciones bsicas de un 
ADT elemental, si fuera necesario.

==================================================================
         Instanciacin de un contenedor usando el editor

{ PARAMETERS
  (Stack_T Stack_ADT Stack_P [SSize])   (Elem_T Elem_ADT)  }

PLANTILLA           Pila de Pilas            Pila de Personas

Stack_T.pas:        SS_Per_T.pas              S_Per_T.pas
                   Stack_ ----> SS_Per_     Stack_ ----> S_Per_
                   Elem_  ----> S_Per_      Elem_  ----> Person_

ElemT.pas:         Person_T.pas
                   Elem_  ----> Person_

                            Figura 10
==================================================================

     La  Figura  10 es  un diagrama  de las  sustituciones que  se 
necesitan hacer  en el  archivo Stack_T.pas  y Elem_T.pas.   Estos 
archivos  son  plantillas  que   permiten  utilizar  el  ADT   que 
implementan, por medio de la instanciacin de identificadores.

     Los  identificadores  a  sustituir  manualmente  mediante  el 
editor en  un archivo  que contiene  la implementacin  de un  ADT 
contenedor son  los que  aparecen baja  el encabezado  PARAMETERS, 
como se muestra en las Figuras 3 y 10.  En el prrafo anterior  se 
mencionan  las  sustituciones ms  importantes para  instanciar el 
Stack_T, pues deben sustituirse todos los identificadores listados 
bajo PARAMETERS.  Si en el ejemplo de la pila de pilas de personas 
se usa la implementacin del Listado 4, que usa vectores,  tambin 
ser necesario darle un valor a la constante SSize, que no aparece 
del todo en el Listado 5 (pila con punteros).  Como el proceso  de 
instanciar un ADT  contenedor es manual,  el programador debe,  de 
nuevo, ser "cuidadoso" al hacerlo, para evitar errores. La ventaja 
es que ste es un procedimiento muy simple, que no requiere pensar 
mucho,  por lo que la costumbre  de hacerlo evitar que se cometen 
errores.    (Aunque   ya  los   compiladores  de   ADA  lo   hacen 
automticamente por medio  de  tipos  genricos,  es  difcil  que 
llegue   el  da   en  que  estas   facilidades  sean  ampliamente 
disponibles para Pascal).

     Como en la implementacin de Stack_T se usa el  procedimiento 
Copy  del ADT  contenido, y no  el ":=" del  compilador de Pascal, 
entonces cada vez que es necesario copiar elementos se hace de  la 
forma  correcta usando  S_Per_T.Copy o SS_Per_T.Copy:  cada uno de 
estos  Copys "sabe" copiar adecuadamente  (pues de hecho llaman al 
Copy del elemento contenido). Lo mismo puede decirse de todas  las 
dems operaciones  que manipulan  al elemento  contenido.  Es  por 
esto  que  el  mismo   cdigo  programado  en  Stack_T.pas   puede 
utilizarse para implementar pilas de cualquier tipo de datos,  aun 
cuando el  ADT contenido  sea una  estructuras de  datos altamente 
complicada.  Si se  necesita una pila  de enteros, basta  usar, en 
lugar de la unidad Elem_T, una en que el Rep sea un entero.  Si se 
necesita  una pila de  "pilas de personas", entonces  el Rep en el 
sustituo de Elem_T deber ser "pilas de personas": S_Per_T.

     En los Listados 4  y  5  se  incluye  el  cdigo  Pascal  que 
implementa  el  tipo  abstracto  de datos  pila usando  arreglos y 
punteros,  que son  las dos formas  clsicas de hacerlo.   Como es 
lgico, cada implementacin de Stack_T se programa diferente  (NEW 
slo se usa en la  implementacin con punteros), pero la  interfaz 
de ambas  implementaciones es  exactamente la  misma. Esto  quiere 
decir que el programador usuario del ADT puede utilizar cualquiera 
de las dos implementaciones en su programa, con el objetivo de que 
use aquella que lo haga ms eficiente.  Lo importante es que  este 
afinamiento  de  la eficiencia  del programa  se hace  en un  slo 
mdulo,  que  es  la  unidad  Stack_T.   Esto  quiere  decir   que 
efectivamente se est  logrando  que  cada  ADT  sea  una  barrera 
protectora para un tipo de datos,  lo que ayuda a que el  programa 
producido sea ms robusto y que sea ms fcil darle mantenimiento.

     UsaPila ha sido diseado  para que pueda utilizar  cualquiera 
de  las versiones  de Elem_T de  los Listados 1  y 2, para  lo que 
utiliza el  procedimiento Elem_T.Put.   El lector  puede comprobar 
que si cambia una versin de Stack_T por la otra, o de Elem_T  por 
lo  otra, UsaPila contina haciendo  exactamente lo mismo.  Lo que 
este   ejercicio    muestra    es    que    los    tres    mdulos 
Elem_T+Stack_T+UsaPila son realmente independientes, pues de hecho 
UsaPila puede implementarse de cuatro formas diferentes.

     Las diferencias entre las dos implementaciones de Elem_T  son 
muy pequeas.  Las variaciones se dan nicamente dentro la  unidad 
Elem_T, por lo que no afectan a la unidad Stack_T (haga el  lector 
la prueba, cambiando  una  versin  de  Elem_T  por  la  otra:  el 
resultado obtenido es el mismo).

     Precisamente el  poder escoger  entre varias  alternativas de 
implementacin  es  la razn  principal para  usar abstraccin  de 
datos: los  detalles de  implementacin quedan  totalmente ocultos 
dentro de las barreras del ADT, y es posible hacer  modificaciones 
locales,  generalmente para  mejorar la eficiencia,  que no tengan 
una repercusin global.  Por eso el uso de abstraccin de datos da 
dividendos cuando se le da mantenimiento a los programas.


9. Polimorfismo: uso de referencias a objetos
=============================================

     Una pila es un tipo abstracto de datos que contiene elementos 
de  otro tipo.  Por ejemplo, en  un programa puede usarse una pila 
que  contiene nmeros enteros, y  otra de caracteres. Este segundo 
tipo puede verse como un parmetro necesario para definir el  tipo 
de  datos pila.  En la Figura  3 se incluye la clusula PARAMETERS 
que sirve, precisamente, para indicarle al programador cules  son 
los  identificadores,  dentro  de  la  unidad  Stack_T,  que  debe 
utilizar para definir el tipo de datos contenido en la pila.  Cabe 
destacar que es muy  usual que un ADT  sea definido en trmino  de 
otro u  otros: lo  natural al  hacer programacin  por objetos  es 
crear  una red  de ADTs y  procedimientos que conforman  juntos el 
programa.

     En la Figura 3 la  declaracin del los procedimientos Push  y 
Pop, y tambin la del tipo Rep, necesitan que el programador  haya 
definido una  unidad llamada  Elem_T que  contenga un  ADT llamado 
Elem_ADT.   Elem_T contiene la declaracin  de los tipos de objeto 
que  el  programador  desea  almacenar  en  su  Stack_ADT.    Esta 
parametrizacin del tipo  Elem_ADT evita amarrar  el Stack_T a  un 
tipo de datos, pues la misma implementacin de Stack_T sirve  para 
cualquier tipo de datos Elem_ADT.

     Al parametrizar el tipo Elem_ADT  en la definicin de Rep  se 
logra que la misma  unidad,  Stack_T  en  este  caso,  sirva  para 
producir  varios tipos  de pila.  Por  ejemplo, si Elem_ADT  es un 
nmero  real, el  resultado de compilar  Stack_T ser una  pila de 
nmeros  reales;  si  es  un  entero,  lo  ser  de  enteros.   Lo 
interesante es  que basta  copiar y  recompilar la  unidad Stack_T 
para obtener una pila de uno y otro tipo.

     A diferencia del  lenguaje ADA, que  tiene un amplio  soporte 
para  parametrizacin  de  mdulos  por  medio  de  los   paquetes 
genricos, en Pascal el programador debe hacer uso de un editor de 
texto para producir, con base en una unidad que implementa un  ADT 
parametrizado, una instanciacin del ADT para el tipo abstracto de 
datos.  El proceso es relativamente simple, pero no es automtico, 
y tiene la  desventaja  que  se  obtiene  una  nueva  unidad,  que 
contiene una copia completa del cdigo de la unidad.

     Por ejemplo, sera  muy cmodo que  en Pascal el  programador 
pudiera declarar una pila con capacidad de 350 nmeros enteros  de 
la  siguiente  manera: VAR  s_int :  Stack_ADT<INTEGER,350>.  Esto 
implicara  que el tipo Elem_ADT sera  INTEGER, y que el valor de 
la constante SSize  debe ser 350,  y no 20000  como aparece en  la 
Figura 3.  Si el programador necesitara, en el mismo programa, una 
pila de nmeros reales con  capacidad de 50 nmero, la  declarara 
as: VAR  s_real :  Stack_ADT<REAL,50>.  En  ADA el  compilador se 
encarga de sustituir  en cada caso  el identificador Elem_ADT  por 
INTEGER o REAL;  en Pascal el  programador debe hacerlo  usando un 
editor de texto.

     Ms an, en Pascal el programador deber hacer dos copias  de 
la unidad Stack_T, llamadas, por ejemplo, StackI_T y STackR_T,  en 
las  que luego sustituya el  identificador Elem_ADT por INTEGER en 
el primero caso, y REAL en el segundo. As obtendr dos copias  de 
la unidad, una  para cada tipo  de datos.  El  programador tambin 
debe  producir  dos  unidades  llamadas  ElemI_T  y  ElemR_T,  que 
contengan las  operaciones que  las unidades  StackI_T y  STackR_T 
necesitan: el proceso  es  simple,  tedioso,  y  requiere  que  el 
programador  sepa   lo  que   est  haciendo.    Esta  duplicacin 
innecesaria de cdigo es una limitacin del truco de  programacin 
expuesto en este  artculo  para  usar  abstraccin  de  datos  en 
Pascal. Pero no es el unico.

     La tcnica  del Rep  permite definir  un ADT  en trminos  de 
otro. Pero  tiene la  gran desventaja  de que  un objeto  no puede 
estar  en  ms  de  un  contenedor.   Por  ejemplo,  si   Elem_ADT 
corresponde  a un registro de  Person_ADT, entonces esa persona no 
puede estar en ms de una  lista.  Lo que puede hacerse es  tener, 
en varias instancias del ADT  lista, copias del mismo registro  de 
la persona, pero no es posible que el mismo registro se  encuentre 
en todas las listas.

     La solucin a estos dos  problemas es usar punteros.  En  CLU 
se habla de semntica de referencia para decir que un objeto no es 
el objeto en s, como s lo es en Pascal, sino que un objeto es un 
puntero  a  la  parte  de  la  memoria  en  que  sus  datos  estn 
almacenados.   Usando   punteros  es   posible  meter   en  varios 
contenedores el mismo objeto, y si se le cambia de alguna  manera, 
entonces el cambio  ser visible desde  todos los punteros  que lo 
referencian.

     Existe    otra    gran    ventaja    al    usar     punteros.  
Independientemente  del  objeto  referenciado,  un  puntero  tiene 
siempre  el mismo tamao. Esta  ventaja la aprovecha Modula-2 para 
definir sus  tipos "opacos".   Esto implica  que el  compilador no 
tiene  problemas al  asignar memoria para  una variable que  es un 
puntero, lo que resulta en una gran flexibilidad para definir ADTs 
en  trminos  de  otros  ADTs.   Adems,  la  operacin  Move   se 
implementa  simplemente  como  una  asignacin  de  puntero.   Las 
convenciones expuestas en  este  artculo  se  basan  en  que  los 
objetos  de tipo Rep_Stack y  Stack_ADT tiene exactamente el mismo 
tamao,  lo que  permite usar la  transferencia de tipos,  pues el 
compilador debe saber cunta  memoria reservar para una  instancia 
de cada ADT.

     La capacidad de definir un tipo abstracto de datos en trmino 
de otro, o  de  varios  otros,  se  conoce  en  el  mbito  de  la 
programacin  por objetos como  parametrizacin. La idea principal 
es  que el tipo del ADT  contenedor sea independiente del tipo del 
ADT contenido,  hasta  el  punto  de  que  varias  instancias  del 
contenedor  puedan hacer uso del  mismo cdigo que implementa cada 
operacin.  En este sentido, el ADT contenido es un parmetro  que 
sirve para definir al ADT contenedor.  Como se ver ms  adelante, 
sto es ms difcil de hacer si el objeto en s, y no una variable 
que le apunta, es lo que est almacenado en la instancia del  tipo 
contenedor, bsicamente porque objetos diferentes tienen tamaos y 
operaciones diferentes.

     Si se  implementa la  parametrizacin usando  punteros a  los 
objetos   contenidos  en  el  ADT,   entonces  el  cdigo  de  las 
operaciones del ADT contenedor puede ser compartido por todos  las 
instancias del tipo contenedor.  Por ejemplo, si el contenedor  es 
una lista, entonces todas las listas usarn el mismo procedimiento 
Insert o Delete, independientemente del tipo de datos contenido en 
la lista.  La razn es la siguiente: una lista de nmeros  enteros 
realmente es una lista que contiene punteros de un tipo  especial, 
o sea punteros a enteros.  Pero todos los punteros son bsicamente 
iguales,  ocupan  la  misma  cantidad de  memoria, y  el manipular 
punteros a enteros es igual  que manipular punteros a personas,  o 
listas,  o lo  que sea.  En  la implementacin de  List_T no hara 
falta saber el tipo de Elem_ADT, pues para insertar o borrar en la 
lista bastara insertar o borrar un puntero.

     Por lo mismo no sera necesario usar procedimientos de Copy y 
Move  especiales para  cada tipo contenido:  basta copiar punteros 
para lograr el efecto de insertar o borrar un objeto contenido  en 
el ADT parametrizado.

     Se llama polimrfico al tipo abstracto de datos contenedor en 
que  todas sus instancias comparten  el cdigo que implementa cada 
una  de  las  operaciones  del  ADT,  independientemente  del  ADT 
contenido. El concepto  de parametrizacin es  ms general que  el 
trmino polimorfismo, pues  al  usar  el  segundo  en  general  se 
sobreentiende  que  la  implementacin  del  ADT  contenedor   usa 
punteros  a  los objetos  contenidos.  En  cambio, si  un lenguaje 
realmente soporta parametrizacin  de tipos, como  es el caso  con 
ADA y CLU,  entonces la implementacin  del ADT no  necesariamente 
usar  punteros.  En  el caso especfico  de ADA es  posible crear 
tipos  de datos  contenedores que no  usan punteros a  sus objetos 
mediante  el  uso  de  paquetes  genricos;  en  estos  casos   el 
compilador se encarga de crear varias copias del cdigo  necesario 
para  implementar  cada  operacin,  en aquellos  casos en  que es 
necesario hacerlo.

     Si un ADT es polimrfico, entonces todas las operaciones  del 
ADT pueden usarse en cualquiera que sea el objeto contenido,  pues 
se implementan moviendo y copiando  punteros.  O sea que en  mucho 
polimorfismo   significa   implementar   parametrizacin    usando 
punteros.  Parametrizacin implica el definir una ADT en  trminos 
de otro.  Estos dos conceptos estn muy ligados a la forma en  que 
pueden  ser  implementados:  el  polimorfismo  permite   compartir 
cdigo,  y  la parametrizacin  permite definir  mdulos que  usan 
tipos   como  si   fueran  argumentos.   Los   dos  conceptos  son 
complementarios  pues permiten la  reutilizacin de componentes de 
programas.

     El  precio que tiene la  flexibilidad de usar polimorfismo es 
que  debe agregarse a la memoria  usada por cada objeto el espacio 
usado  para  almacenar su  puntero.  Adems,  para accesarlo  debe 
hacerse  una indireccin  adicional.  Pero cuando  el mismo objeto 
debe aparecer en  varios contenedores, lo  que es usual  en muchos 
programas, no queda ms que usar punteros, lo que adems cubre  el 
costo de usar polimorfismo.

     Otro problema con el polimorfismo es que las operaciones Load 
y Save deben implementarse de manera diferente, pues de nada  vale 
almacenar en disco una cadena de punteros a objetos contenidos  en 
memoria real. Esto se resuelve fcilmente, almacenando los objetos 
y no sus punteros. Pero si un objeto est en ms de un contenedor, 
y varios  contenedores son  almacenados en  el disco,  cuando sean 
recuperados se obtendrn  varias  copias  del  mismo  objeto  (una 
diferente para cada contenedor).  Este problema no tiene solucin, 
pero pocas veces necesita  el programador guardar tan  complicadas 
estructuras.   (Una manera  ruda de solucionar  este programar, es 
almacenar en el disco todo el contenido de la memoria).

Pero ahora surge otra dificultad al usar polimorfismo en el mbito 
de Turbo Pascal: el programador debe invalidar la verificacin  de 
tipos  al  usar las  operaciones del  ADT, que  contendr punteros 
genricos, compatibles con cualquier tipo de puntero. O sea que el 
compilador no verificar, por ejemplo, que en una pila de  enteros 
se  metan  punteros a  nmeros reales.   Es efectivamente  posible 
escribir un programa  que  meta  en  una  pila  polimrfica  tanto 
enteros  como  caracteres.  Si  no hay  verificacin de  tipos, el 
programador debe ser muy cuidados al usar ADTs polimrficos.

Si se mezclan diferentes  tipos  de  punteros  en  la  misma  pila 
polimrfica,  es necesario que en  todo momento el programa "sepa" 
que tipo de dato esperar.  Para esto lo usual es incluir un  campo 
en el Rep de Elem_ADT que indique el tipo del objeto contenido.

     No es  usual  mezclar  en  el  mismo  contendor  tipos  "muy" 
dismiles. Cuando se hace programacin por objetos, es usual  usar 
listas que tienen varios objetos que difieren poco unos de  otros.  
Por ejemplo, un programa puede  manipular una la lista de  figuras 
geomtricas,  en  que sus  partes internas  difieran poco  unas de 
otras.  Lo malo es que  para lograr esto cmodamente es  necesario 
usar dos  tcnicas que  son muy  difciles de  simular en  Pascal: 
herencia y funciones virtuales.   La programacin por objetos  es, 
bsicamente, usar  ADTs polimricos  para accesar  contenedores de 
elementos similares que se han obtenido unos de otros mediante  de 
herencia de tipos. En [Stroustrup-88] se discute en detalle sto.

==================================================================
    UNIT StackI_T;  { Interfaz de enteros para la pila genrica }
    INTERFACE
    TYPE
      INTEGER_P = INTEGER; { Puntero a enteros    }
    {...}
    IMPLEMENTATION
    USES Stack_T;   { Pila Polimrfica             }
    {...}
    PROCEDURE Push_INTEGER(  { EXPORT }   { Adolfo }
      {?} VAR s : Stack_ADT; { Pila a procesar     }
      {+}     e : INTEGER_P  { Puntero a un entero }
    );
    { RESULTADO
      Mete el entero apuntado por e en la pila s   }
    BEGIN { Push_INTEGER }
      Stack_T.Push(s, POINTER(e));
    END; { Push_INTEGER }
    {...}
    END.
                               Figura 11
==================================================================

     Si se desea  evitar  perder  el  chequeo  de  tipos  al  usar 
polimorfismo en Pascal, entonces basta definir una unidad que haga 
la transformacin de punteros para cada tipo contenido en el  ADT.  
En la Figura 11 se  muestra la operacin Push_INTEGER, que  recibe 
un puntero, y lo transforma a un puntero a enteros antes de llamar 
al procedimiento genrico Push del ADT Stack_T.  El problema ahora 
estriba  en  que para  ejecutar la  operacin Push  de la  pila se 
necesitan  dos  llamados...  Si  Pascal, como  C++, permitiera  la 
sobrecarga de identificadores y procedimientos que se  desarrollen 
en lnea, este sobretrabajo prodra evitarse.  Casi que dan  ganas 
de   escribir  un   preprocesador  de  Pascal   que  elimine  este 
sobretrabajo, como ya ha sido hecho en el caso de C++.


10. Parametrizacin: objetos de tamaos diferentes
==================================================

     Despus de discutir el  concepto de polimorfismo, es  posible 
discutir  ms  a  fondo  la  parametrizacin  de  tipos  sin  usar 
punteros.  Para  esto hay  que estudiar  la Figura  12, en  que se 
presentan dos instancias del ADT pila, una de enteros y la otra de 
caracteres.

     En  este ejemplo se  presentan dos instanciaciones diferentes 
de la "misma" pila con objetos de diferentes tipo.  Como en el Rep 
de  la pila se  menciona a Elem_ADT, entonces  los tamaos de cada 
pila  son  diferentes.   Ms  an, ya  se ha  visto que  el copiar 
objetos  de  tipo Elem_ADT  puede no  ser trivial,  por lo  que el 
programador usuario  del ADT  pila debe  haber definido  en Elem_T 
operaciones que permitan  copiar  instancias  del  tipo  Elem_ADT. 
Estas  operaciones se usan para insertar  en la pila copias de los 
objetos  a almacenar.  Por  ejemplo, en el caso  del ADT pila cuya 
implementacin aparece en los Listado 4 y 5, las operaciones Push, 
Pop,  etc.,  usan  el  Copy  o  Move  definido  en  Elem_T.   Como 
contraste,  la   implementacin  polimrfica   del  ADT   pila  no 
necesitara hacer referencia a esos procedimientos.

==================================================================
              S1                              S2
      +------------------+         +----------------------+
      |                  |         |                      |
      | +---+---+  +---+ |         | +---+---+  +---+---+ |
      | |   3   |  | A | |         | |   2   |  |  3245 | |
      | +---+---+  +---+ |         | +---+---+  +---+---+ |
      |     |      | B | |         |     \----->|  7880 | |
      |     |      +---+ |         |            +---+---+ |
      |     \----->| D | |         |            |       | |
      |            +---+ |         |            +---+---+ |
      +------------------+         +----------------------+
        StackC_T [CHAR]               StackI_T  [INTEGER]
       2 + 3*1 = 5 Bytes               2 + 3*2 = 8 Bytes
         ElmCHR_T.pas                    ElmINT_T.pas

                            Figura 12
==================================================================

     La Figura 12 muestra como se ve la memoria si se  implementa, 
por medio  de un  arreglo, una  pila de  caracteres versus  una de 
enteros. La  disposicin  de  los  elementos  en  la  memoria  es, 
bsicamente, la misma.  Pero una variable de tipo StackC_ADT (pila 
de caracteres) ocupa 5 bytes, mientras que una de tipo  StackI_ADT 
(pila  de  enteros)   necesita  8.   El  cdigo  generado  por  el 
compilador  para un tipo  de pila no sirve  para manipular el otro 
tipo. Es por esto que si el programador necesita usar dos tipos de 
pila en  su  programa,  deber  entonces  usar  dos  unidades  que 
diferirn  nicamente  el en  tipo de  datos que  usan: una  usar 
enteros y la otra caracteres.  Sin embargo, la lgica plasmada  en 
la implementacin de ambas unidades ser exactamente la misma.  El 
polimorfismo es  muy utilizado  precisamente porque  al usarlo  se 
puede  evitar esta  proliferacin innecesaria de  copias del mismo 
cdigo.

     Las diferencias entre StackC_T  y StackI_T son realmente  muy 
pequeas, y sus operaciones son prcticamente iguales.  Pero  como 
StackC_ADT  y  StackI_ADT tienen  tamao diferente,  el compilador 
debe tratarlas diferente.   Es  posible  que  ambos  tipos  puedan 
utilizar las mismas operaciones, pero efectivamente lograr esto es 
difcil. Requiere usar punteros a procedimientos para ejecutar las 
operaciones  del  ADT  contenido.   Por  ejemplo,  debe  haber  un 
procedimiento  Copy para enteros y  otro para caracteres, de forma 
que cuando se invoque a Copy  se haga de forma indirecta a  travs 
de  ese puntero.  Cada instancia  del Stack_T debera mantener una 
tabla con  los  punteros  a  los  procedimientos  necesarios  para 
manipular el ADT contenido.

     En  ADA se puede usar  paquetes genricos para implementar el 
ADT pila.  En ese  caso, el  compilador de  ADA sabe  que un  tipo 
parametrizado  necesita  definir  objetos  que  tienen   diferente 
tamao, y diferentes operaciones.  Quiere esto decir que el  mismo 
cdigo para un tipo de datos se podra usar para diferentes  tipos 
de Elem_ADTs. El compilador de ADA es quien se encarga de hacer la 
copia de un mdulo,  si es necesario, y  de coordinar el acceso  a 
los Elem_ADTs por medio de sus operaciones.  En Pascal, que es  un 
lenguaje  que no  soporta paquetes genricos,  el programador debe 
hacer la copia "a pie".

     El  lector astuto puede ahora  ver que es posible implementar 
en Pascal un ADT parametrizado que no sea polimrfico.  Para crear 
el tipo abstracto de datos  pila que permita almacenar objetos  de 
diferente tamao, es necesario que el programador usuario del  ADT 
provea,  al usar la  operacin Init de la  pila, direcciones a los 
procedimientos  que implementen todas  las operaciones bsicas del 
ADT contenido, como Copy y Move del Elem_ADT, y tambin el  tamao 
del Elem_ADT (SizeOf(Rep)) como se muestra en la Figura 13.  S_chr 
es una pila de caracteres, y S_int de enteros. Ambas variables son 
del  mismo  tipo:  Stack_ADT.    La  diferencia  estriba  en   los 
procedimientos mencionados en el Init.  Dentro de Stack_T.Rep debe 
haber espacio para guardar las direcciones de las del  operaciones 
del Elem_ADT almacenado en la pila.

==================================================================
TYPE
  CONST SSize = 500;       { tamao de la pila }
  Rep_Stack   = RECORD
    ult, size : INTEGER;   { ultimo byte usado, SizeOf(Elem_ADT) }
    elem      : ARRAY[1..SSize] OF BYTE;  { contenido de la pila }

    { Punteros a las operaciones de Elem_ADT }
    P_Init, P_Clear, P_Done : PROCEDURE(VAR e);
    P_Copy,   P_Move             : PROCEDURE(VAR x; VAR y);
    P_Equal            : FUNCTION (VAR x; VAR y) : BOOLEAN;
  END; { Rep }

  Stack_ADT = RECORD
    Rep : Rep_Stack;
  END;
VAR
  S_chr, S_int : Stack_ADT;

BEGIN
  Init(S_chr, SizeOf(INTEGER), Int_Copy, Int_Move, {.....});
  Init(S_int, SizeOf(CHAR),    Chr_Copy, Chr_Move, {.....});
END;
                            Figura 13
==================================================================

     La implementacin del  Stack_T mencinado en  la Figura 13  es 
necesariamente mucho ms complicada que la de los Listados 4 y  5, 
pues es necesario manejar, a nivel de byte, la memoria asignada.

==================================================================
    PROCEDURE Push( { EXPORT }           { ADOLFO }
      {?} VAR S : Stack_ADT; { Pila polimrfica   }
      {+} VAR e              { argumento SIN tipo }
    );
    { RESULTADO
      Agrega a la pila S el elemento e.           }
    { REQUIERE
      Que S no este llena ( Full(S)=FALSE )
      Todos los elementos "e" deben ser del
      mismo tamao: Rep(S).size.                  }
    BEGIN { Push }
      IF (S.Rep.sultimo+S.Rep.size) < SizeOf(Rep) THEN BEGIN
        S.Rep.P_Copy{_Move}(S.Rep.elem[S.Rep.ultimo], e);
        S.Rep.ultimo := S.Rep.ultimo + S.Rep.size;
      END;
    END; { Push }

                            Figura 14
==================================================================

     Por ejemplo,  al hacer  un Push  en S_chr,  por el  valor del 
argumento SizeOf(Chr_T.Rep_Chr)  se sabe que debe incrementarse en 
uno  el  puntero al  ltimo byte  usado, y  luego se  procedera a 
insertar el  caracter en  la pila  usando el  procedimiento P_Copy 
(esta  variable  es un  puntero al  procedimiento que  "sabe" cmo 
copiar caracteres). En el caso de S_int, el incremento se hara de 
dos en dos. Como es lgico, caben ms caracteres que enteros en el 
mismo espacio, por lo que la  capacidad de S_chr ser la mitad  de 
S_int, dado que  ambas  variables  tienen  diferente  tamao.   La 
Figura  14 muestra un extracto de  la operacin Push de esta pila, 
que es polimrfica (pues se  usa el mismo cdigo para  implementar 
todas las operaciones de cualquiera de las instancias de la  pila) 
pero que no almacena punteros a los objetos que contiene.

     La mayora de los  lenguajes que permiten parametrizacin  la 
implementan  por medio  de punteros (o  sea, que realmente  lo que 
hacen es  polimorfismo  pero  sin  abandonar  la  verificacin  de 
tipos). Uno de los factores que han contribuido significativamente 
a  para que no  existan muchos compiladores de  ADA es que permite 
mdulos  genricos.   Como  se  ha demostrado  aqu, en  Pascal es 
posible  implementar  tipos genricos,  pero el  peso del  trabajo 
recae sobre el  programador.  En ADA,  el compilador debe  ser muy 
complejo para evitarle todas estas molestias al programador.

     El  uso  de  estas  sofisticadas  tcnicas  de  polimorfismo, 
requiere  de  un alto  dominio de  la tcnica  aqu expuesta.   El 
programador bisoo  no debe  usarlas, y  si lo  hace debe  ser muy 
cuidadoso.   Si algo es muy difcil  de hacer, es ms probable que 
no resulte correcto.

     Existen entonces varios niveles de parametrizacin: la  mayor 
flexibilidad   se  obtiene  un   tipo  contenedor  puede  contener 
diferentes  tipos  de datos.   Un ejemplo  de esto  sera una  una 
instancia  del ADT lista que  pueda contener tanto nmeros enteros 
como caracteres, personas e inclusive otras listas.  El  siguiente 
nivel de flexibilidad se da usando polimorfismo y el ltimo  nivel 
se alcanza cuando la implementacin del ADT contiene los  objetos, 
y no punteros a ellos.

     Recapitulando, la parametrizacin es la flexibilidad de  usar 
el mismo tipo abstracto de  datos para diferentes tipos de  datos.  
Es  una facilidad de un lenguaje  que permite que la definicin de 
un tipo  reciba  como  parmetro  a  otro  tipo.   La  ms  cmoda 
implementacin   de   parametrizacin  se   logra  por   medio  de 
polimorfismo,  en  que  se  logra  compartir  cdigo   almacenando 
punteros a objetos.  El polimorfismo  es la base de los  lenguajes 
que soportan programacin por objetos.


11. Anidamiento de ADTs
=======================

     El  anidar  un ADT  dentro de  otro es  muy importante,  pues 
permite  definir  un   ADT  en  trminos   de  otro.   Todos   los 
contenedores tienen un ADT anidado.  Pero al anidar ADTs en  Turbo 
Pascal  se debe resolver un  serio problema de referencia circular 
de unidades.   Para  la  exposicin  es  conveniente  utilizar  un 
ejemplo.

     Al  implementar el  ADT rbol, en  donde cada nodo  tiene una 
lista de sus hijos, se encuentra el siguiente problema.

- El rbol necesita usar a la lista, pues los punteros a sus nodos 
  hijos deben estar almacenados en una lista.

- La lista necesita  usar al  rbol, pues  la lista  de cada  nodo 
  contiene los punteros a los nodos hijos, que son rboles.

==================================================================
UNIT Tree_T;                 UNIT Tlist_T;
USES Tlist_T, Elem_T         USES Tree_T;
TYPE                         TYPE
  Rep_Tree     =    RECORD               Rep_Tlist    =     RECORD
    e : Elem_ADT;                n : INTEGER;
    h : Tlist_ADT;  {<<**>>}     e : ARRAY [1..LSize] OF Tree_ADT;
  END;                         END;
  Tree_ADT = RECORD            Tlist_ADT = RECORD
    Rep : Rep_Tree;             Rep : Rep_Tlist;
  END;                         END;

                            Figura 15
==================================================================

  Como se muestra en la Figura  15, lo que sucede entonces es  que 
  hay una referencia circular entre las unidades Tree_T y Tlist_T, 
  que puede resolverse de varias maneras:

- Usar polimorfismo: El campo  de  tipo  Tree_ADT  en  el  Rep  de 
  Tlist_ADT  puede definirse como POINTER,  de forma que la unidad 
  Tlist_T no necesite usar a Tree_T, pues ya "sabe" que el Rep  en 
  Tree_T es un puntero.

- Se  puede  sacar  la  definicin  de  Tree_T.Rep  a  un  archivo 
  especial, Tree_T.Rep, e incluirlo (usando {$INCLUDE Tree_T.Rep}) 
  tanto en Tree_T.pas como en Tlist_T.pas.  Esta segunda  solucin 
  es fea, pues todo el cdigo que implementa el ADT rbol deja  de 
  estar contenido en un slo archivo.

     La primera solucin parece ms elegante, y ha sido  utilizada 
por el autor para implementar Tree_T con base a List_T: el chequeo 
de tipos en este caso es un impedimento para lograr la modularidad 
del  programa.   Como  Pascal   realmente  no  soporta  ADTs,   el 
programador  debe estar pendiente de todo  lo que hace, so pena de 
terminar con una maraa realmente complicada.


12. Convenciones para implementar ADTs con unidades
===================================================

     Las convenciones que se deben usar para implementar ADTs, que 
han   sido  bsicamente   expuestas  en  los   ejemplos,  son  las 
siguientes:

- Cada ADT estar contenido en  una unidad.  Es vlido que un  ADT 
  haga uso de otro.

- En  la  parte  de  interfaz  de  la  unidad  deben  listarse  la 
  declaracin del tipo del ADT y sus operaciones.  Para esto  debe 
  incluirse nicamente el  nombre  de  cada  procedimiento  y  sus 
  argumentos,  sin copiar  las clusulas REQUIERE  o RESULTADO que 
  forman parte de la especificacin.

- Debe incluirse en la seccin de PARAMETERS una indicacin de los 
  identificadores que deben usarse para obtener una instancia  del 
  ADT,  si  es  necesario.  El  programdor  usuario  luego   puede 
  sustituir  esos   identificadores  por   los  que   necesita  al 
  instanciar el ADT. La idea es que cada ADT sea un plantilla base 
  para el programador usuario.

- El nombre de  la unidad que implementa  un ADT debe terminar  en 
  "_T"  (por  tipo), y  el nombre  del ADT  tendr la  terminacin 
  "_ADT".  Por ejemplo,  para una pila  el nombre de  la unidad es 
  Stack_T y el del tipo de datos es Stack_ADT.

- La representacin interna  del  ADT  debe  definirse  usando  el 
  identificador  Rep.   En los  ejemplos que  se incluyen  en este 
  escrito se resaltan en un cuadro los campos del Rep.

- Cada  procedimiento  que  sea  una operacin  del ADT  tendr la 
  anotacin  EXPORT, que  as lo indica,  y tambin el  nombre del 
  programador que lo escribi.

- El primer argumento de todas las operaciones de un ADT debe  ser 
  la instancia sobre la que se opera.  Todas estas variables  debe 
  pasarse como parmetros de referencia (VAR).

- Para definir una instancia del ADT, el programador usuario  debe 
  utilizar el identificador cuyo sufijo es "_ADT".

- Es conveniente  incluir en  la seccin  de implementacin  de la 
  unidad una explicacin  detallada  de  cmo  se  interrelacionan 
  todos los datos y campos que  forman el ADT.  El uso de  dibujos 
  puede ayudar mucho en esta documentacin.

- Como  es usual  que cada ADT  tenga operaciones llamadas  Init y 
  Done, que sirven para inicializar y destruir cada instancia  del 
  ADT,  es  importante que  al usar  el ADT  estos identificadores 
  estn  cualificados  con  el  nombre  de  la  unidad  a  la  que 
  pertenecen,  no vaya a ser que  el compilador tome un nombre por 
  otro.  Esto es  difcil  que  ocurra,  pues  generalmente  estas 
  operaciones tiene parmetros diferentes.

- Si una operacin puede implementarse de forma simple con base en 
  otras,  es mejor  eliminarla de la  implementacin. Sin embargo, 
  debe  incluirse todas las  operaciones necesarias para manipular 
  adecuadamente las  intancias del  ADT. Las  operaciones del  ADT 
  deben estar completas.

- Deben incluirse  todas las operaciones  bsicas para el  ADT, de 
  forma que el programador usuario no se vea obligado a cambiar el 
  ADT para usarlo.

     El lector ya  debe haber notado  que no todos  los argumentos 
para las operaciones  de  un  ADT  son  siempre  necesarios.   Por 
ejemplo, en algunas implementaciones  de la lista usando  punteros 
Insert(e,L)   no  necesita  usar  la  variable  L.   Pero  en   la 
implementacin  de  listas usando  vectores es  necesario usar  L.  
Para lograr consistencia al implementar ADTs, es necesario siempre 
incluir como argumento el objeto sobre el que acta la  operacin.  
El  omitir  estos argumentos  "innecesarios" es  contraproducente, 
pues hace la interfaz del mdulo dependiente de la implementacin.

     Todas  estas reglas pueden entenderse  bien en el contexto de 
un  ejemplo completo.   Para eso se  incluyen dos implementaciones 
diferentes del ADT  pila  en  los  Listados  4  y  5:  la  primera 
implementa la pila con vectores, y la segunda usando punteros.


13. Iteradores en Pascal
========================

     Como  en  la mayora  de los  programas se  usan muchos  ADTs 
contenedores,  surge  entonces  la  necesidad  de  establecer   un 
mecanismo para  accesar a  todos esos  elementos.  Este  mecanismo 
puede  implementarse bsicamente  de dos formas:  definiendo en el 
ADT contenedor operaciones que permitan recorrerlo, o por medio de 
iteradores.

==================================================================
                   p := Endl(L);
                   WHILE p <> First(L) DO BEGIN
                     p := Prev(p,L);
                     Procese(p);
                   END;

                            Figura 16
==================================================================

     El Listado 6 es un extracto de la definicin del ADT lista de 
[Aho-85].  Se incluyen operaciones que permiten recorrer la lista, 
como Next(p,L), First(L) o Prev(p,L).   El cdigo de la Figura  16 
recorre una lista hacia atrs, usando esas operaciones.

     Esto es vlido hacerlo, y es lo que procede en muchos  casos.  
El lector suspicaz puede ver  de este ejemplo que, dependiendo  de 
la implementacin de la lista, es posible que su recorrido sea muy 
ineficiente.  Por ejemplo, si la lista est implementada con nodos 
enlazados por  punteros  hacia  adelante,  entonces  encontrar  el 
predecesor de cada nodo requiere  recorrer toda la lista desde  el 
principio.  Esto es  ineficiente;  en  otras  implementaciones  no 
existira este problema  ([Aho-85]  incluye  una  buena  discusin 
sobre sto).

     La idea al definir un iterador es lograr encapsular una forma 
de acceso eficiente  a todos los  elementos de un  ADT contenedor.  
Para esto el  iterador debe proveer  al usuario programador  de un 
tipo  de datos  y varias operaciones  para recorrer el  ADT.  Como 
convencin, el tipo del iterador  debe terminar en "_ITR", y  debe 
estar en una unidad Pascal aparte cuyo nombre termina en "_I".  La 
Figura  17 es el extracto de  la especificacin de un iterador que 
recorre  hacia  atrs  una  lista.  En  [Liskov-86] se  discute en 
detalle  el  uso  de  iteradores; la  convencin descrita  en esta 
seccin sigue las sugerencias de ese texto.

     Es obvio que un iterador accesa la representacin interna del 
ADT. En general, el programador que crea un ADT tambin debe crear 
iteradores para recorrerlo.  Luego los programadores usuarios  del 
ADT los pueden usar para construir sus programas.  Los  iteradores 
deben  implementarse  como  tipos   amigos  del  ADT,  usando   la 
terminologa de C++.

     Cualquier  iterador consta de  cinco operaciones, que siempre 
tienen  los mismo parmetros.  Las  operaciones Init y Done tienen 
el mismo uso que en ADTs.

     Clear inicializa  el iterador  para recorrer  un ADT.   En el 
caso de  una lista  implementada con  punteros hacia  adelante, el 
Init podra consistir  en crear en  memoria dinmica un  vector de 
punteros  en  orden  inverso  a  la  lista  original.   El   Clear 
inicializara adecuadamente el vector de punteros, y finalmente el 
Done devolvera la memoria dinmica usada para almacenar el vector 
de  punteros.  En el  caso de una lista  implementada por medio de 
vectores, el iterador podra limitarse a llevar un contador de  la 
ltima  posicin accesada  en la lista.   Ms an, el  iterador se 
podra programar  independientemente  de  List_T.Rep,  usando  las 
operaciones Next y Prev.

     La operacin Finished retorna un valor booleano que indica si 
faltan de  procesar  elementos  del  ADT.   Esta  operacin  puede 
invocarse  cuantas veces sea necesario,  pues no modifica el valor 
del iterador.

==================================================================
UNIT BackL_I;
USES List_T, Elem_T;
CONST  Max = 20000;
{[])====================================================([]}
{[])  IMPLEMENTATION:                                   ([]}
{[])====================================================([]}
{[]}  TYPE                                              {[]}
{[]}    BackL_ITR = RECORD                              {[]}
{[]}      Rep : ARRAY[1..Max] OF Lpos_T;                {[]}
{[]}    END;                                            {[]}
{[])====================================================([]}


{[])====================================================([]}
{[])  PARAMETERS:    LISTA USANDO PUNTEROS              ([]}
{[])====================================================([]}
{[])  BackL_T       ( nombre de la unidad )             ([]}
{[])  BackL_ITR     ( nombre del iterador )             ([]}
{[])  List_T        ( nombre de unidad    )             ([]}
{[])  List_ADT      ( nombre del ADT      )             ([]}
{[])  Elem_T        ( nombre de unidad    )             ([]}
{[])  Max           ( tamao del iterador )             ([]}
{[])====================================================([]}

PROCEDURE Init(     {-} VAR I : BackL_ITR);
PROCEDURE Clear(    {?} VAR I : BackL_ITR; {+} VAR L : List_ADT);
PROCEDURE Done(     {?} VAR I : BackL_ITR);
FUNCTION  Next(     {?} VAR I : BackL_ITR; {+} VAR L : List_ADT);
                    {>>>>>>>} : Elem_P;
FUNCTION Finished(  {+} VAR I : BackL_ITR; {+} VAR L : List_ADT);
                    {>>>>>>>} : BOOLEAN;

                            Figura 17
==================================================================

     La operacin Next  avanza el iterador,  y retorna un  puntero 
hacia el siguiente elemento contenido en el ADT.  Es necesario que 
en  la unidad Elem_T, en donde  se define el tipo bsico contenido 
en  el ADT que  el iterador recorre, se  defina Elem_P = Elem_ADT.  
La Figura  18 contiene  el cdigo  para recorrer  hacia atrs  una 
lista, usando el iterador definido en la Figura 17.

==================================================================
                BackL_I.Init(I);
                { ... }
                BackL_I.Clear(I,L);
                WHILE NOT BackL_I.Finished(I,L) DO BEGIN
                  p := BackL_I.Next(I,L);
                  Procese(p);
                END;
                { ... }
                BackL_I.Done(I);

                            Figura 18
==================================================================

     En  la  Figura 18  todas las  operaciones del  iterador estn 
calificadas con el nombre de  la unidad que contiene el  iterador. 
Esto  debe  ser as  porque los  nombres usados  para denotar  las 
operaciones  de un  iterador son muy  comunes y se  usan en muchos 
ADTs. Adems, como cada iterador siempre usa estos mismos nombres, 
es necesario  calificarlos para  evitar errores  de sintaxis.   En 
otros lenguajes sera  posible usar el  mismo nombre para  denotar 
diferentes procedimientos, usando sobrecarga de nombres.  Como  el 
soporte de Pascal para ocultamiento  de datos no es muy  completo, 
entonces no es posible sobrecargar los nombres de las operaciones.

     El  Rep del iterador de la  Figura 17 debe ser una estructura 
de  datos  que  permita  recorrer  todos  los  elementos  del  ADT 
contenedor  de  una manera  eficiente.  Esta  estructura de  datos 
depender  de la forma en que  el ADT est implementado, aunque no 
es necesario que esto sea  as.  Por ejemplo, el iterador  BackL_I 
puede implementarse  usando las  operaciones Endl  y Prev  del ADT 
Lista, aunque no resulte sto en la ms eficiente  implementacin. 
Es  el  programador del  ADT quien  debe decidir,  al escribir  la 
implementacin del iterador, cul tcnica debe utilizar.

     El programador usuario debe evitar cambiar un ADT mientras lo 
recorre usando  un iterador.   Si lo  cambia, en  el mejor  de los 
casos, el estado del iterador ser indefinido. En el caso peor  se 
podra producir una falla fatal.  Un iterador permite examinar los 
elementos  contenidos en un ADT  contenedor.  Es vlido cambiar un 
elemento contenido, pero no lo es cambiar al contenedor.

     Los iteradores tiene muchas aplicaciones.  Por ejemplo, puede 
definirse uno para nmeros enteros que retorne el siguiente nmero 
primo  en  cada llamado.   Si el  ADT utilizado  es un  rbol, los 
clsicos  recorridos   infijo,  posfijo   y  prefijo   pueden  ser 
implementados cmodamente con un iterador. Es fcil implementar un 
iterador que recorre  nicamente las hojas  del rbol, o  slo los 
nodos internos, etc. Lo mismo puede decirse del ADT conjunto,  que 
es muy utilizado.


14. Transferencia de tipos
==========================

     Puede  que  al   novicio  le  preocupe   que  al  hacer   una 
transferencia   de   tipos  se   incurra  en   algn  sobretrabajo 
innecesario,  pero  lo  cierto  es   que  esto  no  es  as.    La 
transferencia de tipos no tiene costo alguno. En la Figura 5 estn 
las siguientes asignaciones:

     r := Rep_Stack(s);  { Bien: transferencia de tipos }
     s := Stack_ADT(r);  { Bien }

     En  ambos  casos  el  cdigo  generado  se  limita  a  copiar 
SizeOf(Rep)  bytes de un lugar de memoria a otro.  Desde el  punto 
de vista del compilador, lo importante al definir un nuevo tipo de 
datos es saber  cunta memoria se  necesita para almacenarlo.   Es 
esa informacin la que le proporcionamos al decirle cunta memoria 
debe reservar para una variable de tipo Stack_ADT: exactamente  la 
misma  que  ocupara  una  variable  de  tipo  Rep_Stack.   En  la 
implementacin  de   la  operacin   Push  puede   encontrarse  la 
instruccin:

     Inc(S.Rep.ultimo); { Incrementa el tope de la pila }

El cdigo  generado por  el compilador  en este  caso se  limita a 
accesar el campo .ultimo en  la variable s.  Exactamente el  mismo 
cdigo  hubiera  sido generado  si el  identificador Rep  no fuera 
necesario:

     Inc(S.ultimo); { Incrementa el tope de la pila }

     En este  ltimo caso,  no se  estara usando  ocultamiento de 
datos.  El  nico sobretrabajo  real que  existe al  usar ADTs  en 
Pascal  es  el  llamado  a cada  procedimiento que  implementa una 
operacin del ADT.


15. Comparacin con otros mtodos para implementar ADTs
=======================================================

     En [Liskov-86; cap.  7]  se describe extensamente otro  truco 
para  implementar ADTs  en Pascal que  requiere, al igual  que los 
tipos  opacos de Modula-2, definir  un puntero para cada instancia 
del ADT.  Lo  malo de esa  propuesta es que  est orientada a  que 
todos  los objetos manipulados por  un programa sean accesados por 
medio  de  punteros.   Este  excecivo uso  de punteros  resulta en 
programas  innecesariamente  ineficientes,  que  deben  pagar   un 
sobretrabajo significativo para cada instancia de un objeto,  pues 
se necesita un puntero que lo referencie.

     La  ventaja principal  de las convenciones  descritas en este 
artculo es  que se  logra que  el mecanismo  de chequeo  de tipos 
ayude al programador  a  construir  abstracciones  de  datos.   En 
contraposicin, la tcnica de Liskov  y Gutag no protege la  parte 
interna del ADT.

     Otro inconveniente de las convenciones de [Liskov-86] es  que 
el cdigo de un ADT se ve plagado de "chimbolitos" de puntero: por 
todo lado aparecen expresiones como s.campo que no significan nada 
para  el  programador.   Si  se  usan  las  convenciones  de  este 
artculo, en la implementacin  del ADT aparecen expresiones  como 
Rep(s).campo, que  indican  claramente  que  el  programador  est 
accesando la parte interna del ADT.

     Desgraciadamente  el mtodo  de Liskov, y  el aqu propuesto, 
incurren en la  ineficiencia  producida  por  el  sobretrabajo  de 
llamar a  las operaciones  del ADT.   La ventaja  principal de  la 
tcnica aqu discutida  es que sta  es la nica  penalizacin que 
debe pagarse.

     Un  gran inconveniente de esta  manera de implementar ADTs es 
que el programador usuario necesita, en general, acceso al  cdigo 
fuente que implementa  el ADT. Esto  implica que ser  difcil que 
compaas especializadas  desarrollen ADTs,  pues debern  tambin 
ceder el cdigo fuente.  Esta  debe haber sido la razn  principal 
que motiv el que ADA tenga paquetes genricos.

     Estas convenciones requieren de  un compilador de Pascal  que 
permita:

- Uso de unidades
- Uso de transferencia de tipos
- Uso de cualificadores para los identificadores de una unidad

     Para una implementacin de Pascal que no soporte unidades, se 
pueden utilizar  las convenciones  aqu descritas  sustituyendo la 
calificacin  de  procedimientos  por  medio de  la unidad  en que 
aparecen,  por  un prefijo.   Por ejemplo,  en lugar  de escribir: 
Stack_T.Push(S,e); el  programador  escribira  Stack_T_Push(S,e). 
Todas las  operaciones deberan  estar adecuadamente  calificadas. 
Adems, en lugar de usar unidades sera necesario usar  directivas 
de  compilador  {$INCLUDE Stack_T.inc}.   El mtodo  ya no  es tan 
elegante como para Turbo Pascal o Modula-2, pero funciona.


16. Conclusiones

     Usando estas  convenciones el  programador puede  implementar 
tipos abstractos de datos cmodamente, an cuando el compilador de 
Pascal usado no posea unidades.  A diferencia de las  convenciones 
de [Liskov-86], stas  permiten  que  la  memoria  usada  por  las 
instancias del ADT est en la pila de ejecucin del programa, y no 
en  memoria dinmica, con  lo que se logra  una gran eficiencia al 
usar ADTs.

     El uso de  esta tcnica permitir  al programador comenzar  a 
utilizar  ADTs en su quehacer  diario.  Especficamente en el caso 
del  compilador  Turbo  Pascal  5.0,  es  vlido  decir  que   las 
cualidades que  presenta para  usar abstraccin  de datos  no slo 
igualan a las de Modula-2, sino que le sobrepasan. En opinin  del 
autor, al usar estas convenciones no existe razn alguna para usar 
Modula-2   para   programacin  de   aplicaciones,  al   menos  en 
computadores para los que existe una versin del Turbo Pascal 5.0.

     El lector interesado debe  comprender que el lenguaje  Pascal 
no soporta programacin  por objetos en  la forma que  la soportan 
C++  y Smalltalk.  Pero,  de hecho, casi que  est al mismo nivel 
que ADA! (Slo falta automatizar la instanciacin de unidades).

     Estas convenciones estn orientadas a que el programador  use 
parametrizacin para sus ADTs, no polimorfismo. Si se  implementan 
ADTs  contenedores usando  punteros a los  objetos, el programador 
debe tomar  muy en  cuenta que  puede ser  necesario invalidar  la 
verificacin de tipos del compilador, por lo que el compilador  no 
le podr ayudar a encontrar errores en tiempo de compilacin.

     Este  trabajo ha sido inspirado en  gran parte en el libro de 
Liskov  y Gutag.   Se ha explicado  cmo implementar en  Pascal la 
mayora de las cualidades de CLU, en el contexto de un lenguaje de 
amplio  uso, y  sin sacrificar eficiencia  en espacio y  tiempo de 
ejecucin.   Mientras   CLU  es   un  lenguaje   usado  en   pocas 
universidades (en Costa Rica es inasequible), Pascal es usado  por 
muchos programadores profesionales.  Estas tcnicas les permitirn 
obtener  todas  las ventajas  del uso  de abstraccin,  pagando un 
precio muy pequeo en eficiencia del programa.

     Aunque  usar  ADTs es  ms difcil  que no  hacerlo, pues  en 
algunos casos se dura  el  doble  programando,  vale  la  pena  el 
esfuerzo, pues la calidad de los programas producidos es mucho ms 
alta.  Ojal los programadores acepten este mensaje.


                           BIBLIOGRAFIA

[Aho-84]  Aho, Alfred V.  et  al: "Data Structures and Algorithms" 
     Addisson Wesley Publishing Co. U.S.A. 1984.

[Borland-88]   Borland  International:   "Turbo  Pascal  Reference 
     Manual"; Borland International. California, U.S.A.  1988.

[Bustard-88] Bustard, David; Elder, John; Welsh, Jim:  "Concurrent 
     Program Structures; Prentice-Hall; 1988.

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

[Goldberg-83] Goldberg,  Adele; Robson,  David: Smalltalk-80,  the 
     Language and its Implementation; Addison-Wesley, 1983.

[Ichbiah-79] Ichbiah, J.D et al: "Rationale for the Design of  the 
     ADA  Programming Language";  SigPlan Notices, Vol  14; No. 6, 
     Junio 1979.

[Kernighan-86] Kernighan, Brian: "El lenguaje de programacin  C"; 
     Prentice Hall; 1986.

[Kernighan-87]   Kernighan,   B.;  Pike,   Rob:  "El   entorno  de 
     programacin UNIX"; Prentice Hall; 1987.

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

[Stroustrup-86a]  Stroustrup,   Bjarne:   "The   C++   Programming 
     Language"; Addison-Wesley; 1986.

[Stroustrup-86b] Stroustrup, Bjarne: "An Overview of C++"; Sigplan 
     notices; Octubre 1986.

[Stroustrup-88]  Stroustrup,  Bjarne:  "What  is   Object-Oriented 
     Programming"; IEEE Transactions on Software Engineering; Mayo 
     1988.

[Wiener-88] Wiener, Richard S.; Pinson, Lewis J.: "An Introduction 
     to  Object-Oriented  Programming  and  C++";  Addison-Wesley, 
     1988.

[Wirth-82]  Wirth,  Niklaus:  "Programming  in  Modula-2,   Second 
     Edition";  R.R.   Donnelley &  Sons, Harrisonburg;  Virginia, 
     U.S.A.  1982.


            L I S T A D O S   D E   P R O G R A M A S
            =========================================

     Por razones  de espacio,  no se  incluyen todos  los listados 
completos,  sino  aquellas  partes  ms  representativas  de  cada 
implementacin.   Si  desea  obtener  todos  los  programas   aqu 
mencionados, puede enviar  un sobre con  porte de correo  pagado y 
con  un diskette  preformateado IBM/pc del  5 1/4" a  la siguiente 
direccin:

                       Prof Adolfo Di Mare
                    Escuela de Ciencias de la
                    Computacin e Informtica
                    Universidad de Costa Rica
                          ADTs en Pascal

Listado 1 [ElemC.pas]:    Interfaz del Elem_ADT de caracteres
Listado 2 [ElemI_T.pas]:  Interfaz del Elem_ADT de enteros
Listado 3 [UsaPila.pas]:  Programa que usa el ADT pila
Listado 4 [StackV_T.pas]: Implementacin del ADT pila con vectores
Listado 5 [StackP_T.pas]: Implementacin del ADT pila con punteros
Listado 6 [ListC.pas]:    Interfaz del ADT lista

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