                  Abstraccin de Datos en Pascal

                               por

                          Adolfo Di Mare

                   Reporte Tcnico PIBDC-01-89
                       Proyecto 326-86-053


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  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 used with  Modula-2 
or with other versions of Pascal.

This conventions allow  object  instances,  even  those  that  are 
containers,  to use stack memory.   As other proposals require the 
use of pointers and dynamic  memory, 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-86-053  "Conversin   automtica  de   programas  despus   de 
reestructurar una base de datos" inscrito ante la Vicerrectora de 
Investigacin  de  la Universidad  de Costa  Rica.  La  Escuela de 
Ciencias de la Computacin e Informtica tambin ha aportado
fondos para realizar este trabajo.


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


     La  ingeniera  de  sistemas  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 definir sistemas en un lenguaje altamente especializado.

     Pero conforme  avanza ms  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 tcnicas  de 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.

     En el artculo 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 es envolver 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, con 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 el verificar los tipos de 
los argumentos  de cada  rutina como  una herramienta  para lograr 
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  descritas  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 bastane 
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  puede 
lograrse  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 lenguaje objeto producido al compilarla. 
Obviamente, debe seguir las reglas del juego, y asegurarse de  que 
la  clusula REQUIERE  se cumpla de  hecho, o el  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 mucha ms informacin.

     Las bibliotecas de programas comerciales generalmente proveen 
informacin adicional  al programador,  en la  que se  describe el 
contexto de uso de un 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 pedazos  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 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 muy 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 
buscar por  todo el  programa el  lugar en  que deben  hacerse los 
cambios.

     Tambin mediante la abstraccin de datos se logra especificar 
qu  es cada estructura 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  de  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  debe 
existir una buena razn para usar ese trmino).

     Intrnsecamente  ligado  al  concepto  de  encapsulamiento  y 
abstraccin est  el  concepto  de  ocultamiento  de  datos  (data 
hiding).   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 otro.

     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,  que  es  lo  que  se  hace  al  aplicar  la 
metodologa  de diseo y programacin  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  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 Top-Down muy claramente, y han logrado convencer 
a  los  tericos  de  la  programacin  (quienes  saben   escribir 
compiladores, pero no son programadores) 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, lo que redunda en una mejor calidad.  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 tarda ms en  terminar su programa (ms an si 
no   sabe  bien  lo  que  es   un  ADT).   Sin  embargo,  la  alta 
modularizacin alcanzada permite que el mantenimiento del programa 
sea mucho ms simple. 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  (un  sistema  mejor  modularizado  es  ms  fcil  de 
mantener).  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 ms  importantes ventajas 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);

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.   La Figura  3 es un  extracto de la  especificacin del ADT 
pila, usando una unidad Turbo Pascal.

     Se deben usar ciertas convenciones para programar un ADT:  el 
nombre  de la unidad que contiene  las declaraciones de tipos y el 
cdigo de las operaciones del ADT debe incluir 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 
costas 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
===================================

     A  primera vista la definicin  del tipo Stack_ADT 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, 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.  Como  Stack_ADT  y  Rep_Stack  son  tipos  diferentes, 
entonces  no pueden  mezclarse en el  programa, pero como  son del 
mismo tamao,  puede  enmascararse  uno  como  si  fuera  el  otro 
mediante una transferencia de tipos, similar a la provista en C  y 
Modula-2.  Tanto en Turbo Pascal como en Modula-2 la transferencia 
de  tipos se  logra escribiendo el  nombre del tipo  y la variable 
entre parntesis, como en Rep_Stack(s). El uso de transferencia de 
tipos  no   implica  sobretrabajo   alguno  (overhead),   pues  el 
compilador simplemente genera cdigo para copiar bits de un  lugar 
a  otro de  memoria, invalidando el  chequeo de tipos.   (En Turbo 
Pascal es vlido usar transferencia de tipos en la parte izquierda 
de una asignacin,  como en "Rep_Stack(s)  := r;" mientras  que en 
Modula-2 sto no se permite).  La transferencia de tipos no  tiene 
costo computacional en tiempo de ejecucin.

==================================================================
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 }
 {...}             { define su propio tipo Rep_Stack            }
BEGIN
  s := r; { error de compilacin: tipos incompatibles   }
  r := Rep_Stack(s);   { OK: transferencia de tipos     }
  s := Stack_ADT(r);   { OK, usado en la implementacin }
  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
==================================================================

     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 mscara Rep_Stack en una transferencia  de 
tipos.  La  Figura 5  ilustra cules  transferencias de  tipos son 
vlidas.

     En  el ejemplo de la Figura 5  la variable "s" es la pila que 
el programador podr usar, metindole y sacndole 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.

     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  ahorrarse   unos  segundos  al   digitar  su  programa, 
simplemente usa la parte interna del tipo de datos. En general, es 
difcil no usar cada campo "directamente".

     Pero  la  prctica de  evitar 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.

     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 de  esta 
manera,  el uso de Rep ayuda  a documentar el cdigo del programa, 
en lugar de opacar su claridad.

     En la experience del autor, para aceptar a Rep en un programa 
se requieren  tres  semanas,  en  las  que  se  produce  un  serio 
conflicto persona  entre la  mente y  Rep.  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 valiosa ayuda de documentacin.

     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 lo que se ha hecho en C++.

     El truco  del Rep  le permite  a cualquier  programador tener 
acceso a la parte interna del ADT, si as lo desea.  Sin  embargo, 
deber  usar la palabra Rep para  lograrlo, 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  tiene  buen  control  sobre  las 
consecuencias 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, 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  dems.   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 el elemento contenido en un 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);

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.   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 Rep's son diferentes,  el Get y el Put difieren 
notablemente.

     En una unidad que implemente un ADT contenedor los objetos de 
tipo  Elem_ADT se accesan 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_ADT's, 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 sera 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.

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  complicada estructura,  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.

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 conecciones.  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  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. Por  ejemplo, 
     en el caso del rbol  muchos veces no es necesario  copiarlo, 
     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 quiere tener varias copias del mismo objeto, sino 
     que ms bien se desea 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 compilaro 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
===========================================

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

PROCEDURE Init     ( VAR {-} C : Cont_ADT);
PROCEDURE Clear    ( VAR {?} e : Cont_ADT);
PROCEDURE Done     ( VAR {?} C : Cont_ADT);

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
      );
      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 
(estado  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. Todo ADT contenedor  debe permitirle al programador  usuario 
escoger una de las dos alternativas.

     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 es  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  debe   ser 
modificado,  aunque la nueva unidad  si debe ser recompilada.  Con 
esto  se logra que el tipo  de datos pila est parametrizado, 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 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,  usando copias de  archivos y el  editor de 
texto.

     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  que  debe  ser  sustituidos  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  Figura 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 Copy's "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.   Quiero  esto  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).

==================================================================
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 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.

==================================================================
                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
==================================================================

     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.

     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  excesivo 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.

      BORLAND: Por favor implemente procedimientos INLINE!


                           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: Elem_ADT de caracteres

Listado 2: Elem_ADT de enteros

Listado 3: Programa que usa el ADT pila

PROGRAM UsaPila;
{ RESULTADO
  Permite invertir nombres usando el ADT pila  }
{ PROGRAMADORES:                Adolfo Di Mare }

USES
  Stack_T, Elem_T;

PROCEDURE Invierte(              { Adolfo }
  {+} VAR t  : STRING;  { tira de entrada }
  {-} VAR ti : STRING   { tira invertida  }
);
{ RESULTADO
  Invierte el orden de los caracteres de
  la tira t. Tomado de Rich-88 pg 75      }
VAR
  s1,s2,s3 : Stack_ADT;
  dummy,
  i     : INTEGER;
  c     : CHAR;
  e     : Elem_ADT;  { temporal, para meter cada letra }
  F     : FILE;
BEGIN { Invierte }
  Assign(F,'t.bak');
  Rewrite(F,1);
  Stack_T.Init(s1);  Stack_T.Init(s2);  Stack_T.Init(s3);
  { independientemente de lo que sea Elem_ADT, }
  { Put lo almacena en e. Luego el valor se    }
  { recupera por medio de Get.                 }
  FOR i := 1 TO Length(t) DO BEGIN
    Put(e, t[i], 0);
    Push(s1, e);
  END;
  Stack_T.Copy(s2,s1);
  IF NOT Stack_T.Equal(s1,s2) THEN BEGIN
    WriteLn('s1<>s2');
  END;
  Stack_T.Store(s2,F);
  Close(F);
  System.Clear(F,1);
  Stack_T.Load(s3,F);
  IF NOT Stack_T.Equal(s1,s3) THEN BEGIN
    WriteLn('No funciona Store, Load o Copy');
    WriteLn; WriteLn;
  END;
  ti := '';
  WHILE NOT Empty(s3) DO BEGIN
    Pop(s3,e);
    Get(e, c, dummy);
    ti := ti + c;
  END;
  Stack_T.Done(s1); Stack_T.Done(s2); Stack_T.Done(s3);
END; { Invierte }
VAR
  t, s: STRING;
BEGIN  { UsaPila }
  WriteLn;
  Write('Entre la tira a invertir: ');
  Read(t);
  Invierte(t,s);
  WriteLn;
  WriteLn('La tira invertida es: ', s);
  ReadLn(t); ReadLn(t);
END. { UsaPila }

Listado 4: Implementacin del ADT pila con vectores

Listado 5: Implementacin del ADT pila con punteros

Listado 6: Extracto del ADT lista
