SiguienteAnteriorContenido

CASO 2. El TAD Cola empleando el TAD Pila

El mecanismo de representaciones será la clave para generación de programas eficientes en diversos lenguajes.  Sin embargo en la versión 3.1 de ManTa, no es completamente operante.

Como ejemplo representaremos el TAD Cola con el TAD Pila, para lo cual primero debe definirse el TAD Cola y después representarse con el TAD Pila.

1.1. Definición del TAD Cola

El TAD Cola es definido en [Vill96] a continuación se presenta una adaptación de dicha definición, en el lenguaje de especificación de ManTa.

Signatura:

Axiomas
 

Defina el TAD COL recién presentado.  Puede hacerlo de forma análoga a la definición del TAD PIL expuesta antes.
 

1.2. La representación

Para representar el TAD COL, con el TAD PIL, debe emplearse una función (llamémosla cp) de PIL sobre COL.  Esta función de representación (que por cierto es sobreyectiva), nos permitirá definir como representaremos las inicializadoras, las constructoras y las selectoras del TAD COL, con las funciones del TAD PIL.

La ventaja de ser tan formales radicará en la posibilidad de demostrar formalmente que los axiomas del TAD COL, siguen valiendo una vez representados con el TAD PIL.
 
Salga del menú de tipos y entre al menú de representaciones.  Elija Nuevo, el sistema le pedirá entonces el TAD que va a representar (para este ejemplo COL), y después el TAD con el cual lo va a representar (en este caso PIL). 

Como nombre de la función de representación puede emplear PC.   Una representación puede definirse como composición de otras dos o de forma inductiva, en nuestro caso haremos una representación inductiva.  El parámetro X del TAD PIL, corresponderá al paramétro X del TAD COL
El sistema entrará al editor de texto y le presentará un plantilla para definir como se representan las funciones del TAD COL (también puede pensarlo como una definición de la función cp).  A estas definicione se les ha dado el nombre de Programas

Los programas de nuestra representación son: 

    inicCOL = PC(inicPIL) 
    adicCOL(PC(P1),X2) = PC(adicPIL(P1,X2)) 
    elimCOL(PC(P1)) = PC(elimPIL(P1)) 
    infoCOL(PC(P1)) = infoPIL(P1) 
    esCOLVacia(PC(P1)) = esPILVacia(P1) 
    EQ_COL(PC(P1),cp(P2)) = EQ_PIL(P1,P2) 
Para que pueda digerir más fácil esta definición basta que piense que va a representar colas con pilas y que la función PC convierte pilas en colas.  Por ejemplo el primer programa indica que la pila vacía inicPIL, es proyectada a la cola vacía iniCola.  

Una vez haya definido la representación, puede comprobar que los axiomas del TAD COL siguen valiendo.  Elija Probar del menu de representaciones

ManTa usará el demostrador para probar que los 10 axiomas del TAD COL valen con la representación.  Después le permitirá examinar las pruebas en el editor de texto configurado.
 
 

 

En la versión 3.1 de ManTa  las representaciones no se usan en el momento de generar código en C.  Esta limitación se solucionará en una próxima versión de ManTa.  Una vez completado el mecanismo, el usuario podrá definir TADs muy complejos y representarlos con TADs incluidos en el sistema que cuenten con una buena implementación en C, entonces el nuevo TAD  tendrá la eficiencia del TAD con el cual se represente.
 


SiguienteAnteriorContenido