TAD CjtoEnteros es Vacío, Insertar, Suprimir, Miembro, EsVacío, Unión, Intersección, Cardinalidad Descripción Los CjtoEnteros son conjuntos matemáticos modificables, que almacenan valores enteros. Operaciones Operación Vacío (sal CjtoEnteros) Calcula: Devuelve un conjunto de enteros vacío. Operación Insertar (ent c: CjtoEnteros; x: entero) Modifica: c. Calcula: Añade x a los elementos de c. Después de la inserción, el nuevo conjunto es c U {x}. … Fin CjtoEnteros.
TAD ListaEnteros es Crear, Insertar, Primero, Ultimo, Cabeza, Cola, EsVacío, Igual Descripción Las ListaEnteros son listas de enteros modificables. Las listas se crean con las operaciones Crear e Insertar… Operaciones Operación Crear (sal ListaEnteros) Calcula: Devuelve una lista de enteros vacía. Operación Insertar (ent l: ListaEnteros; x: entero) Modifica: l. Calcula: Añade x a la lista l en la primera posición. … Fin ListaEnteros.
Generalización (parametrización de tipo): El tipo se define en función de otro tipo pasado como parámetro. Útil para definir tipos contenedores o colecciones. P. ej. Listas, pilas, colas, arrays, conjuntos, etc. En lugar de: ? Tenemos: ListaEnteros Lista[T] ListaCadenas ListaReales …. Instanciación: Lista[entero], Lista[cadena],…
TAD Conjunto[T: tipo] es Vacío, Insertar, Suprimir, Miembro, EsVacío, Unión, Intersección, Cardinalidad Descripción Los Conjunto[T] son conjuntos matemáticos modificables, que almacenan valores de tipo T. Operaciones Operación Vacío (sal Conjunto[T]) … Operación Insertar (ent c: Conjunto[T]; x: T) … Operación Suprimir (ent c: Conjunto[T]; x: T) … Operación Miembro (ent c: Conjunto[T]; x: T; sal booleano) … Fin Conjunto.
TAD Lista[T] es Crear, Insertar, Primero, Ultimo, Cabeza, Cola, EsVacío, Igual Descripción Las Lista[T] son listas modificables de valores de tipo T. Las listas se crean con las operaciones Crear e Insertar… Operaciones Operación Crear (sal Lista[T]) … Operación Insertar (ent l: Lista[T]; x: entero) … Operación Primero (ent l: Lista[T]; sal Lista[T]) … Fin Lista.
En C++ es posible definir tipos parametrizados. Plantillas template: template class Pila { private: int tope; int maxDatos; T *datos; public: Pila (int maximo); Push (T valor); T Pop (); }
Abstracciones de iteradores. Ejemplo: Sobre el TAD CjtoEnteros queremos añadir operaciones para calcular la suma, el producto, …
Operación suma_conj (ent c: CjtoEnteros; sal entero) Calcula: Devuelve la suma de los elementos de c. …. Operación producto_conj (ent c: CjtoEnteros; sal entero) …. Operación varianza_conj (ent c: CjtoEnteros; sal real) …. Especificaciones informales.
Necesitamos abstracciones de la forma: para cada elemento i del conjunto A hacer acción sobre i para cada elemento i de la lista L hacer acción sobre i para cada i de la cola C tal que P(i) hacer acción sobre i D:= Seleccionar todos los i de C tal que P(i) Abstracción de iteradores: permiten definir un recorrido abstracto sobre los elementos de una colección.
La abstracción de iteradores no es soportada por los lenguajes de programación. Posibles definiciones: Como una abstracción funcional:
Iterador ParaTodoHacer [T: tipo] (ent C: Conjunto[T]; accion: Operacion) Requiere: accion debe ser una operación que recibe un parámetro de tipo T y no devuelve nada, accion(ent T). Calcula: Recorre todos los elementos c del conjunto C, aplicando sobre ellos la operación accion(c).
Como una abstracción de datos:
TipoIterador IteradorPreorden [T: tipo] es Iniciar, Actual, Avanzar, EsUltimo Descripción Los valores de tipo IteradorPreorden[T] son iteradores definidos sobre árboles binarios de cualquier tipo T. Los elementos del árbol son devueltos en preorden. El iterador se debe inicializar con Iniciar. Operaciones Operación Iniciar (ent A: ArbolBinario[T]; sal IteradorPreorden) Calcula: Devuelve un iterador nuevo, colocado sobre la raíz de A. Operación Actual (ent iter: IteradorPreorden; sal T) … Fin IteradorPreorden.
var A: ArbolBinario[T]; i: IteradorPreorden[T]; begin … i:= Iniciar(A); while Not EsUltimo(i) do begin Acción sobre Actual(i); i:= Avanzar(i); end; …
Las especificaciones en lenguaje natural son ambiguas e imprecisas. Especificaciones formales: definen un TAD o una operación de manera precisa, utilizando un lenguaje matemático. Ventajas de una especificación formal: Prototipado. Las especificaciones formales pueden llegar a ser ejecutables. Corrección del programa. Verificación automática y formal de que el programa funciona correctamente. Reusabilidad. Posibilidad de usar la especificación formal en distintos ámbitos. Especificaciones formales.
Notación La descripción formal constará de cuatro partes: NOMBRE. Nombre genérico del TAD. CONJUNTOS. Conjuntos de datos que intervienen en la definición. SINTAXIS. Signatura de las operaciones definidas. SEMÁNTICA. Indica el significado de las operaciones, cuál es su resultado. +
Sintaxis: : ?
Los distintas notaciones formales difieren en la forma de definir la semántica: Método axiomático o algebraico. Se establece el significado de las operaciones a través de relaciones entre operaciones (axiomas). Significado implícito de las operaciones. Método constructivo u operacional. Se define cada operación por sí misma, independientemente de las otras, basándose en un modelo subyacente. Significado explícito de las operaciones.
La semántica de las operaciones se define a través de un conjunto de axiomas. Un axioma es una regla que establece la igualdad de dos expresiones: = Por ejemplo: Suma (dos, dos) = Producto (dos, dos) Tope (Push (x, pila)) = x OR (verdadero, b) = verdadero Método axiomático (o algebraico).
¿Qué axiomas introducir en la semántica? Los axiomas deben ser los necesarios para satisfacer dos propiedades: Completitud: Los axiomas deben ser los suficientes para poder deducir el significado de cualquier expresión. Corrección: A partir de una expresión sólo se puede obtener un resultado.
Ejemplo: TAD Natural de los números naturales. NOMBRE Natural CONJUNTOS N Conjunto de naturales Bool Conjunto de booleanos {true, false} SINTAXIS cero: ? N sucesor: N ? N suma: N x N ? N esCero: N ? Bool esIgual: N x N ? Bool
SEMANTICA ? m, n ? N 1. suma (cero, n) = n 2. suma (sucesor (m), n) = sucesor (suma (m, n)) 3. esCero (cero) = true 4. esCero (sucesor (n)) = false 5. esIgual (cero, n) = esCero (n) 6. esIgual (sucesor (n), cero) = false 7. esIgual(sucesor(n), sucesor(m)) = esIgual(n, m)
Ejecución de una especificación algebraica: aplicar sucesivamente las reglas de la semántica hasta que no se puedan aplicar más.
Ejemplo. ¿Cuánto valen las siguientes expresiones?
a) suma (suma(sucesor(cero), cero), sucesor (cero) )
b) esIgual (sucesor (sucesor (cero)), suma (suma (sucesor (cero), cero), sucesor (cero) ) )
Supongamos un TAD, T. Tipos de operaciones: Constructores. Conjunto mínimo de operaciones del TAD, a partir del cual se puede obtener cualquier valor del tipo T. c1: ? T, c2: V ? T, c3: V1x…xVn ? T Modificación. A partir de un valor del tipo obtienen otro valor del tipo T, y no son constructores. m1: T ? T, m2: TxV ? T, m3: V1x…xVn ? T Consulta. Devuelven un valor que no es del tipo T. o1: T ? V, o2: TxV ? V’, o3: V1x…xVn ? Vn+1
La ejecución de una expresión acaba al expresarla en función de los constructores. ¿Cómo garantizar que una especificación es completa y correcta? Definir los axiomas suficientes para relacionar las operaciones de modificación y consulta con los constructores. No incluir axiomas que se puedan deducir de otros existentes.
Ejemplo: Especificación del TAD genérico pila.
NOMBRE Pila [T] CONJUNTOS P Conjunto de pilas T Conjunto de elementos que pueden ser almacenados Bool Conjunto de booleanos {true, false} SINTAXIS pilaVacía: ? P esVacía: P ? Bool pop: P ? P tope: P ? T push: T x P ? P
En el caso de tope: P ? T, ¿qué pasa si la pila está vacía? Se puede añadir un conjunto de mensajes en CONJUNTOS, de la forma:
M Conjunto de mensajes {“Error. La pila está vacía”}
Y cambiar en la parte de SINTAXIS la operación tope:
tope: P ? T U M
esVacía(pilaVacía) = esVacía(push(t, p)) = pop(pilaVacía) = pop(push(t, p)) = tope(pilaVacía) = tope(push(t, p)) =
SEMANTICA ? t ? T; ? p ? P 1. esVacía (pilaVacía) = true 2. esVacía (push (t, p)) = false 3. pop (pilaVacía) = pilaVacía 4. pop (push (t, p)) = p 5. tope (pilaVacía) = “Error. La pila está vacía” 6. tope (push (t, p)) = t
Calcular: a) pop(push(3, push(2, pop(pilaVacía)))) b) tope(pop(push(1, push(2, pilaVacía)))) Añadir una operación esIgual para comparar dos pilas. Modificar la operación pop, para que devuelva un error si la pila está vacía. ¿Cómo hacer que la operación pop devuelva el tope de la pila y al mismo tiempo lo saque de la pila?
Para facilitar la escritura de la expresión del resultado en la semántica, se pueden emplear condicionales de la forma: SI ? | Ejemplo: Especificación algebraica del TAD bolsa. NOMBRE Bolsa[I] CONJUNTOS B Conjunto de bolsas I Conjunto de elementos Bool Conjunto de booleanos {true, false} N Conjunto de naturales SINTAXIS bolsaVacía: ? B poner: I x B ? B esVacía: B ? Bool cuántos: I x B ? N
Incluir una operación quitar, que saque un elemento dado de la bolsa. ¿Y si queremos que los saque todos? Incluir una operación esIgual, de comparación de bolsas.
Conclusiones: Las operaciones no se describen de manera explícita, sino implícitamente relacionando el resultado de unas con otras. La construcción de los axiomas se basa en un razonamiento inductivo. ¿Cómo se podría especificar, por ejemplo, un procedimiento de ordenación?
Para cada operación, se establecen las precondiciones y las postcondiciones. Precondición: Relación que se debe cumplir con los datos de entrada para que la operación se pueda aplicar. Postcondición: Relaciones que se cumplen después de ejecutar la operación. Método constructivo (operacional).
Notación En la semántica, para cada operación : pre-()::= post-(;)::=
Ejemplo: operación máximo, que tiene como entrada dos números reales y da como salida el mayor de los dos. máximo: R x R ? R (SINTAXIS) pre-máximo(x, y) ::= true (SEMANTICA) post-máximo(x, y; r) ::= (r ? x) ? (r ? y) ? (r=x ? r=y)
Ejemplo: operación máximo sobre números reales, pero restringida a números positivos. máximop: R x R ? R pre-máximop(x, y) ::= (x ? 0) ? (y ? 0) post-máximop(x, y; r) ::= (r ? x) ? (r ? y) ? (r=x ? r=y)
¿Qué sucedería si x o y no son mayores que 0? No se cumple la precondición ? No podemos asegurar que se cumpla la postcondición.
Implementación en C++ de pre- y post-condiciones. máximop: R x R ? R pre-máximop(x, y) ::= (x ? 0) ? (y ? 0) post-máximop(x, y; r) ::= (r ? x) ? (r ? y) ? (r=x ? r=y)
float maximop (float x, float y) { assert(x>=0 && y>=0); // Precondición double r; if (x>y) r= x; else r= y; assert(r>=x && r>=y && (r==x || r==y)); //Postcond return r; }
Otra posibilidad: Definir un conjunto M (de mensajes de error) y cambiar la imagen. Modificar la sintaxis y la semántica: máximop2: R x R ? R U M pre-máximop2(x, y) ::= true post-máximop2(x, y; r) ::= SI (x ? 0) ? (y ? 0) ? (r ? x) ? (r ? y) ? (r=x ? r=y) | r = “Fuera de rango”
¿Cuál es la mejor opción?
¿Cuál es la mejor solución? La especificación como un contrato. Contrato de una operación: Si se cumplen unas condiciones en los parámetros de entrada, entonces garantiza una obtención correcta del resultado.
Dos puntos de vista del contrato (especificación): Implementador. Obligación: Cumplir la postcondición. Derechos: Sabe que se cumple la precondición. Usuario. Obligación: Cumplir la precondición. Derechos: Sabe que se cumple la postcondición.
Idea: La operación no trata todos los casos de error, sino que hace uso de las precondiciones. La responsabilidad de comprobar la precondición es del que usa la operación.
| Página siguiente |