Método Algebraico de Especificación. - UMAjmmb/ttaadd/ttaadd3-1.pdf · 2013-11-05 · Cap´ıtulo 3 Método Algebraico de Especificación. Los lenguajes de programación

Capıtulo 3

Metodo Algebraico de

Especificacion.

Los lenguajes de programacion proporcionan habitualmente una signatura basica queincluye los universos siguientes: BOOLEAN, CARDINAL, INTEGER, REAL y CHAR,junto con las operaciones necesarias para poder trabajar con los valores de cada unode ellos —cuyas propiedades son bien conocidas—, ası como ciertos esquemas (enu-meracion, subrango, registro, tabla, conjunto) cuya instanciacion permite ampliar elnumero de universos y operaciones (procedimientos) disponibles en un programa. Losdatos de estos universos se representan de alguna forma y, en general, se puede supo-ner que cada programa opera sobre los elementos de un algebra, correspondiente a lasrepresentaciones concretas de valores y operaciones que existen en la maquina dondese ejecuta el programa, que se comportan como los valores a los que representan.

Si embargo, siguiendo las orientaciones del diseno descendente, los programas sedeben disenar de manera que los datos y las operaciones representen valores y ope-raciones abstractos de universos proximos a los dominios de los problemas o tareasque abordan para poder aplicar los razonamientos propios de dichos dominios. Pa-ra esto es preciso disponer de representaciones adecuadas que se comporten como loscorrespondientes entes abstractos, y para conseguir esto necesitamos primero, una ca-racterizacion lo suficientemente completa del comportamiento de los entes abstractosque permita despues, su adecuada representacion.

Los valores abstractos de los universos de datos y las operaciones que se pretenderepresentar en un programa se puede suponer que tambien constituyen un algebra, yuna de las formas mas extendida para caracterizar o especificar algebras se basa en eluso de ecuaciones para expresar los comportamientos de valores y funciones.

3-43

3-44 CAPITULO 3. METODO ALGEBRAICO DE ESPECIFICACION.

3.1 Construccion de una especificacion

Para facilitar la especificacion de algebras correspondientes a los distintos universosde datos que se utilizan en la programacion utilizaremos relaciones de igualdad entreterminos y relaciones de pertenencia de terminos a universos que se interpretaran dela forma acostumbrada sobre las algebras, y nos serviran para definir los resultadosde operaciones y tambien relaciones de contenido entre universos. En su forma masgeneral estas relaciones pueden estar condicionadas por otras ecuaciones o relacionesde pertenencia, sin condicionar.

Para especificar algebras, se enuncia su correspondiente signatura dando los nom-bres de los distintos universos de terminos (tipos de datos) que intervienen y los nombresde las distintas operaciones junto con sus dominios y recorridos (perfiles), y despues,se establece el comportamiento de cada operacion mediante ecuaciones y/o relacionesde pertenencia de la forma

(∀i ∈ [1..n] · ui = vi) ∧ (∀j ∈ [1..m] · wj : sj) ⇒ t = t′

(∀i ∈ [1..n] · ui = vi) ∧ (∀j ∈ [1..m] · wj : sj) ⇒ t : s,

con n ≥ 0 y m ≥ 0 y todas las variable tipificadas, que son las unicas relacionespermitidas en el metodo algebraico que vamos a utilizar. Veamos un ejemplo.

Ejemplo 3.1 Una especificacion para algebra de valores logicos se podrıa dar de lasiguiente forma:

Universo

Booleanos .

Funciones

v : -> Booleanos .

f : -> Booleanos .

not_ : Booleanos -> Booleanos .

_and_ : Booleanos Booleanos -> Booleanos .

_or_ : Booleanos Booleanos -> Booleanos .

Axiomas

not v = f . not f = v .

X:Booleanos => not (not X) = X .

X:Booleanos => X and v = X .

X:Booleanos => X and f = f .

X,Y:Booleanos => X and Y = Y and X .

X,Y,Z:Booleanos => (X and Y) and Z = X and (Y and Z) .

X:Booleanos => X or v = v .

X:Booleanos => X or f = X .

X,Y:Booleanos => X or Y = Y or X .

3.2. SIGNIFICADO DE UNA ESPECIFICACION 3-45

X,Y,Z:Booleanos => (X or Y) or Z = X or (Y or Z) .

X,Y,Z:Booleanos => X and (Y or Z) = (X and Y) or (X and Z) .

X,Y,Z:Booleanos => X or (Y and Z) = (X or Y) and (X or Z) .

X,Y:Booleanos => not(X and Y) = (not X) or (not Y).

3.2 Significado de una especificacion

La especificacion del ejemplo anterior, en principio, es valida para cualquier algebradonde se cumplan sus ecuaciones, en particular, sirve para un algebra con un solodominio que tenga un unico elemento que sea a la vez interpretacion de v y de f y,tambien, para un algebra A con un unico dominio que tenga tres elementos, dos quesirvan como interpretacion de v y de f respectivamente y un tercer elemento r que secomporte en la forma notAr = r, r andAr = r y r orAr = r. Para descartar modeloscomo estos se introducen dos restricciones sobre los modelos a los que deben referirselas especificaciones:

• Todo elemento de un dominio debe representar el valor de algun termino cons-truido con las funciones de la especificacion, con lo que se excluyen modelos conmas elementos de los necesarios y ademas, permite descargar las especificacionesporque determinadas propiedades pasan a ser demostrables por induccion sobrela estructura de los terminos. A los modelos que tienen esta propiedad se lesllama modelos generados por terminos.

• Dos terminos distintos que se puedan construir a partir de la signatura de laespecificacion deben representar elementos distintos del algebra, salvo que sepueda demostrar a partir de los axiomas que deben ser iguales. De esta forma sehace innecesario el uso de desigualdades para diferenciar terminos. Los modeloscon esta caracterıstica son modelos sin confusion de terminos.

• Cuando se conjugan las dos condiciones anteriores se obtienen los modelos inicia-les. Estos modelos se caracterizan porque son modelos generados por terminoscon el mayor numero de terminos distintos; ademas, todos los modelos inicialesson equivalentes (isomorfos).

Una vez adoptadas estas condiciones, solo hay que preocuparse de establecer elmınimo numero de igualdades entre terminos (generalmente relativas a resultados deoperaciones) y relaciones de pertenencia (normalmente para declarar que ciertos uni-versos estan contenidos en otros o que ciertas operaciones producen resultados de cier-tos universos) que sean necesarias para tener una especificacion consistente (libre decontradicciones) y completa (que recoja todos los comportamientos esperados). Las es-pecificaciones de este tipo donde no se niegan relaciones se denominan especificacionespositivas.


Para razonar con ecuaciones y con relaciones de pertenencia debemos incorporar anuestro sistema deductivo reglas especıficas para tratar con los predicados de igualdady de pertenencia. Para una especificacion con un conjunto de axiomas Γ, estas reglasson

Γ ` t = t(Reflexividad)

Γ ` t = t′

Γ ` t′ = t(Simetrıa)

Γ ` t = t′; Γ ` t′ = t′′

Γ ` t = t′′(Transitividad)

Γ ` t1 = t′1; · · · ; Γ ` tn = t′nΓ ` f(t1, · · · , tn) = f(t′1, · · · , t′n)

(Conguencia)

Para cada formula de Γ:(∀i ∈ [1..n] · ui = vi) ∧ (∀j ∈ [1..m] · wj : sj) ⇒ t = t′

Γ ` ∀i ∈ [1..n] · uiσ = viσ; Γ ` ∀j ∈ [1..m] · wjσ : sj

Γ ` tσ = t′σ(Aplicacion I)

Para cada formula de Γ:(∀i ∈ [1..n] · ui = vi) ∧ (∀j ∈ [1..m] · wj : sj) ⇒ t : s

Γ ` ∀i ∈ [1..n] · uiσ = viσ; Γ ` ∀j ∈ [1..m] · wjσ : sj

Γ ` tσ : s (Aplicacion II)

siendo t, t′, t′′, ui, vi y wj terminos y σ una sustitucion. Y cuando se consideran solomodelos generados por terminos, para que el sistema deductivo sea completo hay queanadir una regla conocida como induccion estructural que permite deducir ecuacionesy pertenencias que se cumplen solo en estos modelos. Esta regla se enuncia

Γ ` ∀t ∈ TΣ,s · (∀t′ ∈ TΣ,s · (t′ ≺ t⇒ P (t′)) ⇒ P (t))Γ ` ∀t ∈ TΣ,s · P (t)

para todos los terminos de un cierto universo s ordenados por la relacion

t′ ≺ t⇔def t′ es un subtermino propio de t

que es un preorden con la propiedad de que ninguna secuencia de terminos estricta-mente decreciente puede ser infinita1, y para una propiedad P (t) expresada como unaformula basada en las relaciones de igualdad y de pertenencia, y establece que dichapropiedad es derivable para todos los terminos de un cierto universo siempre que sepueda demostrar que

1Es un preorden bien fundado.

3.3. TECNICAS PARA LA CONSTRUCCION DE ESPECIFICACIONES 3-47

1. la propiedad es derivable para los terminos en cuya expresion no aparece ningunsubtermino del mismo universo, y

2. la propiedad es derivable para los terminos en cuya expresion aparecen subterminosdel mismo universo cuando se admite como hipotesis (hipotesis de induccion) quela propiedad se cumple para todos estos subterminos.

Ejemplo 3.2 Con las restricciones adoptadas, la especificacion del algebra de valoreslogicos se podrıa reducir a

Universos

Booleanos .

Funciones

v : -> Booleanos .

f : -> Booleanos .

not_ : Booleanos -> Booleanos .

_and_ : Booleanos Booleanos -> Booleanos .

_or_ : Booleanos Booleanos -> Booleanos .

Axiomas

not v = f . not f = v .

X:Booleanos => X and v = X .

X:Booleanos => X and f = f .

X:Booleanos => X or v = v .

X:Booleanos => X or f = X .

pues los demas axiomas son demostrables con ayuda de las reglas de deduccion queacabamos de enunciar. Por ejemplo, podrıamos demostrar, aplicando la induccionestructural, que cualquier termino del universo Booleanos es equivalente a t o f y,ademas que t 6= f, porque su igualdad no es derivable.

3.3 Tecnicas para la construccion de especificaciones

Cuando se trata de especificar un determinado dominio de un algebra A, lo primero quese hace es pensar en el correspondiente universo s (o tipo de datos) y determinar lasoperaciones o funciones asociadas a los elementos de dicho universo. Estas operacionesse pueden clasificar, desde un punto de vista puramente sintactico, en

• constructoras, que son aquellas operaciones que producen valores del universo s;

• de observacion/consulta, que son las que se aplican sobre valores del universo spara producir valores de otros universos (son tıpicas operaciones de consulta lasque producen componentes de estructuras complejas, numero de componentes olas que determinan si una estructura esta vacıa).


Dentro de las funciones constructoras se suele distinguir entre:

• constantes, u operaciones que producen valores del universo s sin actuar sobreningun argumento, corresponden a funciones de la forma f : → s;

• constantes relativas, u operaciones que producen valores del universo s actuandoexclusivamente sobre argumentos de universos distintos a s; y

• de modificacion/transformacion, que son todas las demas constructoras.

3.3.1 Estilo constructivo

Existe un estilo de especificacion, conocido como estilo constructivo, que consiste enseleccionar, para cada universo s, un conjunto mınimo de operaciones constructoras conlas cuales se puedan expresar todos los valores distintos del correspondiente dominio As;es decir, tal que para cada dominio As del algebra que se quiere especificar, el universode terminos sin variables de tipo s cubra todos los valores de As y, ademas, cada terminocorresponda a un valor distinto. Cuando se tiene un conjunto Gs de operaciones conestas caracterısticas se dice que se dispone de una familia libre de generadoras para s,normalmente en estas familias siempre hay alguna constante o constante relativa quese puede tomar como punto de partida para generar inductivamente todos los terminosdel universo s.

En estos casos las demas operaciones se especifican como si estuviesemos dandosus definiciones en un lenguaje funcional; con las operaciones generadoras se obtienenlos diferentes patrones o formas distintas de construir los terminos del universo s y lasoperaciones se especifican dando, mediante ecuaciones, los resultados de su aplicacionsobre los distintos terminos segun su forma —como en un analisis de casos—, procu-rando que dichos resultados converjan a algun termino del universo del resultado. Sepueden enunciar definiciones

• directas, dando directamente el resultado de cada aplicacion;

• recursivas, dando el resultado de una aplicacion en funcion del resultado de otraaplicacion de la misma funcion (sobre argumentos estrictamente menores en algunsentido, para que la definicion sea convergente);

• con funciones auxiliares, expresando el resultado de una aplicacion con ayuda dealguna funcion auxiliar; en esta categorıa entrarıan las definiciones de funcionesmutuamente recursivas y las definiciones con funciones inmersoras.

Para aclarar todos estos conceptos veamos el ejemplo siguiente correspondiente auna especificacion del algebra de los numeros naturales.


Ejemplo 3.3 Para especificar el algebra de los numeros naturales lo primero que debe-mos hacer es plantearnos como podemos generar todos los valores del algebra de formaunica. La forma mas simple es partir de la constante 0 y aplicar una operacion queproduzca los sucesores de cada numero, con lo que llegamos a una especificacion de laforma

Universos

Nat .

Generadoras

0 : -> Nat .

s : Nat -> Nat .

Con esto serıa suficiente para tener todos los valores distintos que se generarıan in-ductivamente en la forma

0, s(0), s(s(0)), s(s(s(0))), s(s(s(s(0)))), s(s(s(s(s(0))))), ...

Sin embargo, el algebra de los numeros naturales dispone de unas operaciones carac-terısticas: la suma y el producto, y de una relacion de orden total. Cada una de estasoperaciones se puede introducir en la especificacion declarando su dominio y recorridoy definiendo los resultados de sus aplicaciones

Operaciones

_+_ : Nat Nat -> Nat .

_*_ : Nat Nat -> Nat .

Axiomas

N : Nat => 0 + N = N . -- def. directa

N M : Nat => s(M) + N = s(M + N) . -- def. recursiva

N : Nat => 0 * N = 0 .

N M : Nat => s(M) * N = (M * N) + N .

Para introducir la relacion de orden necesitamos incorporar a la especificacion el uni-verso Booleanos —junto con sus operaciones generadoras v y f— que figurara comorecorrido de esta relacion —en realidad, es una funcion con valores booleanos—, yquedara especificada por las ecuaciones

N : Nat => 0 =< N = v .

N : Nat => s(N) =< 0 = f .

N M : Nat => s(M) =< s(N) = M =< N .

correspondientes a dos definiciones directas y una recursiva. En todos los casos vistoshasta ahora de definiciones recursivas la aparicion, en el lado derecho de la ecuacion,de la operacion que se esta especificando esta siempre aplicada a subterminos de los


argumentos de partida (lado izquierdo) con uno, al menos, estricto; lo que asegurala convergencia de dichas definiciones si suponemos que los resultados de todas lasoperaciones se pueden reducir siempre a terminos construidos solo con operacionesgeneradoras.

Ejercicio 3.1 Especifıquense las relaciones <, >=, > para el algebra de los numerosnaturales.

En estas especificaciones pueden aparecer operaciones parciales, es decir, operacio-nes que solo esten definidas para unos ciertos valores de sus dominios, sin necesidad deintroducir predicados nuevos para indicar cuando estan definidos los terminos construi-dos con dichas operaciones (como ocurre en las especificaciones de algebras parciales)ni tampoco es necesario un tratamiento de errores. En nuestro caso, la situacion seresuelve introduciendo nuevos universos para ajustar el dominio real de la operaciono para abarcar los resultados indefinidos como si fuesen valores especiales (erroneos).Cuando se opta por la primera alternativa,

1. se introduce un subuniverso del dominio de la operacion y

2. se buscan generadores para este subuniverso;

mientras que cuando se opta por la segunda,

1. se introduce un superuniverso del recorrido,

2. no es necesario buscarle generadores sino que basta con declarar los resultadosde la operacion parcial como pertenecientes al superuniverso, y

3. se indica, mediante un axioma condicionado de pertenencia, cuando se producenvalores correctos;

en ambos casos hay que anadir un axioma condicionado de pertenencia para indicar lacorrespondiente relacion de contenido entre universos. Veamos como se aplican estasideas en el caso de los numeros naturales.

Ejemplo 3.4 Para incorporar a la especificacion del algebra de los numeros naturaleslas operaciones para el calculo de la diferencia —que solo esta definida cuando el mi-nuendo es mayor o igual que el sustraendo— o del cociente de dos numeros —que noesta definido cuando el divisor es 0—, debemos introducir nuevos universos de maneraque cada operacion quede definida en todo su dominio. En el caso del cociente bastacon no considerar 0 como divisor introduciendo el subuniverso de los naturales no nulosNatNz, que se generan con la operacion s, y declararlos como un universo dentro delos naturales mediante las declaraciones


s : Nat -> NatNz .

P : NatNz => P : Nat .

con lo que la division quedara como una operacion total

_div_ : Nat NatNz -> Nat .

En cambio, para la diferencia el problema no se resuelve eliminando un valor del do-minio, pues todos pueden intervenir como sustraendo en una resta siempre que el mi-nuendo sea mayor o igual; en este caso, la solucion pasa por introducir un universomas amplio Nat? que contenga los numeros naturales y todas las posibles expresionesno calculables —expresiones erroneas— que se generen con la diferencia e indicar, paraesta operacion, cuando produce valores del universo Nat, lo que se hace declarando

_-_ : Nat Nat -> Nat? .

N : Nat => N: Nat? .

M N : Nat, N =< M = v => M - N : Nat .

Las ecuaciones de definicion seran

N : Nat => N - 0 = N

M N : Nat => s(M) - s(N) = M - N .

Observese que estas ecuaciones no contemplan todos los posibles casos que se puedenpresentar al restar dos numeros naturales, ello se debe precisamente a que los casos nocontemplados se consideran erroneos y no se reducen a otras expresiones.

Para el cociente las ecuaciones seran

M : Nat, N : NatNz, N =< M = f => M div N = 0 .

M : Nat, N : NatNz, N =< M = v => M div N = s((M - N) div N) .

donde observamos que los dos casos que se contemplan no dependen de la estructura deninguno de los argumentos —como ocurre en las ecuaciones de la diferencia— sino delresultado de aplicarles una funcion booleana, que es otra forma de plantear un analisisde casos. En este caso la convergencia de la definicion recursiva queda aseguradaporque la operacion div aparece en la parte derecha aplicada a un termino M - N quesera estrictamente menor que M respecto a la ordenacion dada por =<.

Respecto a las operaciones auxiliares, algunas veces se utilizan simplemente parafacilitar la especificacion de otras operaciones y otras porque son practicamente impres-cindibles. En este ultimo caso se encuentran ciertas operaciones auxiliares, conocidascomo operaciones inmersoras, que son mas generales (con mas parametros) y mas sim-ples que las que se quiere especificar, y tales que, bajo ciertas condiciones, realizan elmismo calculo. Existen algunas tecnicas, conocidas como tecnicas de inmersion, para


determinar operaciones de este tipo para una operacion f dada cuando se conoce suespecificacion pre/post. Veamos algunas.

Inmersion por debilitamiento de la postcondicion. Esta tecnica se basa enbuscar una operacion que realice un calculo mas simple que f hasta el punto que, enalgun caso extremo, el calculo sea directo, mientras que, en los demas casos, se puedanutilizar los resultados de aplicaciones recursivas mas simples para facilitar el calculo dela aplicacion original.

Se procede debilitando la postcondicion de f , normalmente parametrizando algunasubexpresion que se pueda utilizar para controlar el grado de aproximacion al calculobuscado ası como la simplicidad del calculo necesario, este parametro pasa como argu-mento a la funcion auxiliar, cuya precondicion sera la de f reforzada con las condicionesque deba cumplir el nuevo parametro. Veamos un ejemplo.

Ejemplo 3.5 Consideremos la tarea de especificar una operacion para obtener raıcescuadradas. Esta operacion, raiz (N), se caracteriza porque debe calcular, para cadanumero N , un valor R tal que (R ∗R ≤ N) ∧ (N < (R+ 1) ∗ (R+ 1)) (postcondicionde la funcion). Dicha operacion no admite una definicion recursiva, pero considerandola postcondicion en la forma (R ∗ R ≤ N) ∧ (N < (R + A) ∗ (R + A)) ∧ (A = 1),donde se ha introducido un parametro A que representa el margen de error de la raızcuadrada, podemos pensar en una operacion inmersora recursiva que realice un calculomas general: rz (N,A) con postcondicion (R∗R ≤ N) ∧ (N < (R+A)∗(R+A)) ∧ (A ≥1), es decir, que calcule una aproximacion de la raız cuadrada con margen de errorA ≥ 1. Esta operacion

rz : Nat NatNz -> Nat .

es mas simple de especificar porque, para margenes de error suficientemente grandes,0 es un resultado valido,

N:Nat, A:NatNz, A*A =< N = f => rz(N,A) = 0 .

y se puede obtener una aproximacion para un cierto margen A ≥ 1 a partir de otra conun margen A+A de una manera simple;

N:Nat, A:NatNz, (rz(N,A+A)+A)*(rz(N,A+A)+A) =< N = v

=> rz(N,A) = rz(N,A+A)+A .

N:Nat, A:NatNz, A*A =< N = v, (rz(N,A+A)+A)*(rz(N,A+A)+A) =< N = f

=> rz(N,A) = rz(N,A+A) .

ademas calculara la raız cuadrada cuando el margen de error sea A = 1, es decir, quetendremos raiz(N) = rz(N,s(0)).


Inmersion por refuerzo de la precondicion. Esta tecnica se basa en buscar unaoperacion que realice el mismo calculo que la operacion original, pero disponiendo deinformacion adicional que le llegue mediante parametros auxiliares de manera que, enun caso extremo, la informacion proporcionada por estos parametros sea suficiente paraobtener el resultado mediante un calculo directo, mientras que, en los demas casos, sepueda mejorar la informacion de los parametros auxiliares y pasarla a alguna aplicacionrecursiva que realice el calculo final disponiendo de una mejor informacion.

Se procede aumentando el numero de parametros de f con algun parametro querepresente un calculo parcial o una aproximacion del resultado. Este parametro se sueleobtener a partir de alguna subexpresion de la postcondicion relacionada con el resultadoque pueda servir como acumulador o como aproximacion o cota —en algunos casos seutiliza el mismo resultado como parametro— y la postcondicion se descompone en unaconjuncion de dos formulas, una de las cuales se utiliza para reforzar la precondicion def , que se utiliza para indicar cuando se producen resultados correctos, y la otra paracontrolar el caso base. Veamos un ejemplo tambien con la raız cuadrada.

Ejemplo 3.6 Podemos parametrizar el resultado en la postcondicion de la raız cua-drada, que quedarıa (A∗A ≤ N)∧ (N < (A+1)∗ (A+1)) —donde el nuevo parametroA representa una aproximacion por defecto de la raız—, y podemos tomar A ∗ A ≤ N

como precondicion para una funcion auxiliar

rz’ : Nat Nat -> Nat? .

que no estara definida para todos los valores de sus argumentos —como indica la apa-ricion de Nat? en el recorrido—, y N < (A+ 1) ∗ (A+ 1) para controlar el caso trivialen la definicion de esta funcion

A*A =< N = v, s(A)*s(A) =< N = f => rz’(N,A) = A .

para el caso general, la aproximacion por defecto puede mejorarse simplemente utili-zando el numero siguiente

s(A)*s(A) =< N = v => rz’(N,A) = rz’(N,s(A)) .

La raız cuadrada quedarıa raiz(N) = rz’(N,0).

Para descargar un poco la sintaxis vamos a introducir las siguientes simplificacionesdentro de una especificacion:

1. Ordenacion de universos. Los axiomas de la forma X:T => X:T’, que se utilizanpara declarar que el universo T esta contenido en el universo T’, se pueden omitirescribiendo en su lugar T < T’ en la declaracion de universos.


2. Declaracion de variables. Las declaraciones de tipo para las variables que apa-recen en cada ecuacion se pueden suprimir de las condiciones de las ecuacionesescribiendo una sola declaracion de tipo separada para las variables de cada tipoT que aparezcan en la especificacion, en la forma VAR X ... Z:T.

3. Funciones con el mismo perfil. Las declaraciones de funciones f, g, que tengan elmismo dominio y el mismo recorrido (el mismo perfil) se pueden agrupar en unasola declaracion de la forma f g : T1 ... Tk -> T.

4. Ecuaciones con terminos booleanos. Las ecuaciones de la forma e = v y e = f,siendo e una expresion booleana, que aparezcan en las condiciones de un axiomase pueden escribir como e o not e respectivamente.

5. Construccion alternativa. Cuando en una especificacion aparecen axiomas ecua-cionales, referidos al mismo termino t, de la forma

C, c = v => t = a .

C, c = f => t = b .

donde C representa un conjunto —posiblemente vacıo— de condiciones, se puedeescribir una sola ecuacion de la forma

C => t = SI c ENTONCES a SI NO b FIN .

Ejemplo 3.7 Aplicando simplificaciones anteriores a la especificacion del algebra delos numeros naturales con las operaciones que hemos visto en los distintos ejemplosanteriores tendrıamos la especificacion siguiente

Universos

NatNz < Nat < Nat? .

Booleanos .

Generadoras

0 : -> Nat .

s : Nat -> NatNz .

v f : -> Booleanos .

Operaciones

_+_ _*_ : Nat Nat -> Nat .

_-_ : Nat Nat -> Nat? .

_div_ : Nat NatNz -> Nat .

_=<_ : Nat Nat -> Booleanos .

Axiomas

VAR M N :Nat . VAR P :NatNz .


0 + N = N .

s(M) + N = s(M + N) .

0 * N = 0 .

s(M) * N = (M * N) + N .

0 =< N = v .

s(N) =< 0 = f .

s(M) =< s(N) = M =< N .

N =< M => M - N : Nat .

N - 0 = N

s(M) - s(N) = M - N .

M div P = SI P =< M ENTONCES (M - P) div P

SI NO 0 FIN .

Ejercicio 3.2 Especifıquense en el algebra de los numeros naturales las operaciones

_mod_ : Nat NatNz -> Nat .

par? : Nat -> Booleanos .

la primera de las cuales calcula el resto de la division de dos numeros y la segundadetermina si un numero es par.

Las ventajas mas notables del estilo constructivo de especificacion residen en que

1. Las ecuaciones se construyen para que el resultado de la aplicacion de cada ope-racion (salvo en operaciones parciales que pueden producir resultados erroneos)se pueda reducir a un termino construido solo con operaciones generadoras, quesera la forma irreducible o el “valor” del termino.

2. Se puede controlar la consistencia y la completitud de las especificaciones deuna forma meramente sintactica, pues basta con definir cada operacion medianteecuaciones aplicables a terminos que obedezcan a patrones o casos distintos yconsiderar todos los patrones o casos que se puedan dar.

3. Se simplifica el razonamiento por induccion estructural pues, como los terminosde cada universo se pueden reducir a terminos construidos unicamente con lasoperaciones generadoras, solo hay que tener en cuenta estas formas al aplicardicho razonamiento.

4. Se puede realizar la ejecucion simbolica de las especificaciones, para reducirterminos, considerando las ecuaciones como reglas de reescritura de izquierdaa derecha.

Veamos como se aplica el razonamiento por induccion con un ejemplo sobre elalgebra de los numeros naturales.


Ejemplo 3.8 En el algebra especificada en el Ejemplo 3.7 se cumple la propiedad con-mutativa para la suma. Para demostrarla, procederemos probando primero que se cum-plen las propiedades ∀N : Nat · (N + 0 = N) y ∀M,N : Nat · (M + s(N) = s(M +N)).La primera propiedad se demuestra por induccion sobre la estructura de N ; ası paraN = 0, transformando sucesivamente la ecuacion (preferentemente la parte izquierda),tenemos

N + 0 =? N, por la hipotesis N = 0 queda0 + 0 =? 0, por el axioma 0 +N = N queda

0 = 0, cierto por la reflexividad de =,

y para N = s(X), admitiendo como hipotesis de induccion X + 0 = X, tenemos

N + 0 =? N, por la hipotesis N = s(X) quedas(X) + 0 =? s(X), por el axioma s(M) +N = s(M +N) quedas(X + 0) =? s(X), por la hipotesis de induccion resulta

s(X) = s(X), cierto por la reflexividad de =.

Para demostrar la segunda propiedad procederemos por induccion sobre la estructuradel termino M ; ası para M = 0 tenemos

M + s(N) =? s(M +N), por la hipotesis M = 0 queda0 + s(N) =? s(0 +N), por el axioma 0 +N = N queda0 + s(N) =? s(N), por el axioma 0 +N = N queda

s(N) = s(N), cierto por la reflexividad de =,

y para M = s(X), admitiendo como hipotesis de induccion X + s(N) = s(X + N),tenemos

M + s(N) =? s(M +N), por la hipotesis M = s(X) quedas(X) + s(N) =? s(s(X) +N), por el axioma s(M) +N = s(M +N) quedas(X) + s(N) =? s(s(X +N)), por el axioma s(M) +N = s(M +N) quedas(X + s(N)) =? s(s(X +N)), por la hipotesis de induccion resultas(s(X +N)) = s(s(X +N)), cierto por la reflexividad de =.

Ahora ya se puede abordar la demostracion de la propiedad conmutativa ∀M,N : Nat ·M +N = N +M , para ello se puede proceder por induccion sobre la estructura de M yutilizar las propiedades demostradas anteriormente. Dejamos esta demostracion comoejercicio.

3.3.2 Estilo semiconstructivo

Algunas veces no es posible encontrar una familia libre de operaciones generadoras paraun algebra, sino que, a lo mas, se llega a obtener una familia de operaciones que generanterminos distintos para un mismo valor del algebra. En estos casos hay que introducir


ecuaciones para establecer las identificaciones necesarias entre terminos producidospor las operaciones generadoras; normalmente —aunque no siempre—, ecuaciones quepermitan reducir los distintos terminos construidos con las operaciones generadorasa formas irreducibles. Ası, cada valor del algebra se correspondera con una clasede equivalencia de terminos respecto a la relacion producida por estas ecuaciones y setoman las formas irreducibles —cuando existen, hay una unica para todos los elementosde una misma clase— como representantes, o formas canonicas, de las distintas clases.

Ejemplo 3.9 Consideremos el algebra de los numeros enteros. Los valores de estealgebra se pueden generar a partir de la constante 0 mediante aplicaciones sucesivasde las operaciones sucesor, s:Ent -> Ent, y predecesor, p:Ent -> Ent, que generanrespectivamente, el numero siguiente y el numero anterior de un numero dado; sinembargo, hay terminos distintos generados con estas operaciones que deben representarun mismo numero, por ejemplo, s(0) y s(p(s(0))) deben representar en numero 1.En general tendremos infinitos terminos distintos para cada numero, lo que nos obligaa introducir en la especificacion las ecuaciones

s(p(N)) = N .

p(s(N)) = N .

que permiten identificar representaciones equivalentes, indicando ası que la familia degeneradoras no es libre y que los distintos valores del universo Ent seran las clasesde equivalencia de terminos correspondientes a la relacion definida por las ecuacionesanteriores; ası, por ejemplo, el numero 1 vendra dado por la clase de equivalenciacorrespondiente a los terminos

s(0), s(p(s(0))), p(s(s(0))), s(s(p(0))), ...

todos los cuales se pueden reducir a la forma irreducible s(0) aplicando las ecuacionesanteriores.

En estos casos, aun es posible aplicar las tecnicas de las especificaciones construc-tivas, aunque hay que tener mucho mas cuidado con la consistencia de las ecuacionespues las operaciones realmente deberıan actuar sobre clases de equivalencia y producircomo resultado clases de equivalencia, pero las definiciones de dichas operaciones hayque hacerlas sobre terminos generados con las operaciones generadoras, produciendoterminos. Por ello las definiciones deben hacerse de forma que cuando una opera-cion se aplique a terminos equivalentes los resultados que se obtengan tambien seanequivalentes. Veamos un ejemplo con los numeros enteros.

Ejemplo 3.10 En el algebra de los numeros enteros, las distintas operaciones aritme-ticas _+_, _-_ y _*_ se pueden definir en la forma


_+_ _-_ _*_ : Ent Ent -> Ent .

VAR Z Z’ : Ent .

0 + Z = Z .

s(Z’) + Z = s(Z’ + Z) . -- saca las generadoras s y p fuera

p(Z’) + Z = p(Z’ + Z) . -- del primer argumento

Z - 0 = Z .

Z - s(Z’) = p(Z - Z’) . -- saca las generadoras s y p fuera

Z - p(Z’) = s(Z - Z’) . -- del segundo argumento intercambiadas

0 * Z = 0 .

s(Z’) * Z = (Z’ * Z) + Z . -- reduce productos a sumas o restas

p(Z’) * Z = (Z’ * Z) - Z .

donde las definiciones tienden a reducir los terminos construidos con las operaciones aterminos solo con operaciones generadoras y los resultados de las operaciones se man-tienen equivalentes para argumentos equivalentes. Por ejemplo, s(p(0))+p(s(s(0)))y s(p(0))+s(0) que son sumas de terminos equivalentes se pueden reducir ambas as(0).

En esta especificacion podemos incluir los numeros naturales declarandolos comoun universo dentro de los enteros

NatNz < Nat < Ent .

0 : -> Nat .

N : Nat => s(N) : NatNz .

y utilizarlos para definir una relacion de orden en la forma

_=<_ : Ent Ent -> Booleanos .

VAR Z Z’ : Ent .

Z’ - Z : Nat => Z =< Z’ = v .

Z - Z’ : NatNz => Z =< Z’ = f .

Con las especificaciones semiconstructivas tambien se puede limitar el razonamien-tos por induccion estructural a terminos construidos solo con operaciones generadoras.

Ejercicio 3.3 Demuestrese, aplicando induccion estructural,

1. que la suma definida en Ent tiene la propiedad conmutativa;

2. para Z : Ent se cumple Z = 0 o Z = sn(0) con n > 0, o Z = pn(0) con n > 0;

3. para Z : Ent existe Z ′ : Ent tal que Z = Z ′ + Z ′ o Z = s(Z ′ + Z ′).

Ejercicio 3.4 Especifıquese un universo Dia correspondiente a los dıas de la semanaconsiderando que se generan a partir del lunes (Lu) aplicando la operacion ds:Dia->Dia

que produce el dıa siguiente de cada dıa. Incluyase tambien una operacion da:Dia->Dia

que produzca el dıa anterior.

3.4. PATRONES PARA LA ESPECIFICACION DE TIPOS ABSTRACTOS 3-59

3.4 Patrones para la especificacion de tipos abstractos

Existen unos patrones o formas generales para la especificacion de universos, ya seadirectamente o a partir de otros universos ya definidos —muchos de los cuales estanrecogidos en los modernos lenguajes de programacion fuertemente tipificados bajo laforma de esquemas para la definicion de tipos— que suelen aplicarse a la hora deplantearse la especificacion de un tipo abstracto nuevo correspondiente a un algebra.Veamos los mas comunes.

3.4.1 Enumeracion

Es el patron mas simple y se utiliza para especificar algebras con un numero muyreducido de valores, por ejemplo, v1, · · · , vk. En este caso, lo que se hace es especificarel correspondiente universo junto con una constante por cada valor

Universos

T .

Generadoras

v1 : -> T .

...

vk : -> T .

Un ejemplo tıpico lo constituye la especificacion del algebra de valores logicos. Estepatron se puede identificar con el esquema de definicion de tipos por enumeracion queaparece en algunos lenguajes imperativos de programacion.

Ejercicio 3.5 Enunciese una especificacion correspondiente al algebra de las notasmusicales.

Ejercicio 3.6 Enunciese la especificacion correspondiente al algebra de los dıas de lasemana considerandolos como valores constantes y especifıquense, para este caso, lasoperaciones ds y da.

3.4.2 Suma directa

Este patron T = T1| · · · |Tn se aplica a la especificacion de algebras A que se pue-den considerar como la union disjunta de otras algebras A1, ...,An; es decir, tales quesus elementos son los elementos diferenciados de todas y cada una de estas algebras.Consiste en introducir un universo global T junto con los universos T1,...,Tn, correspon-dientes a las algebras componentes, y declararlos subuniversos de T, manteniendo lasoperaciones generadoras de cada uno de ellos y no incluyendo ninguna operacion quegenere directamente valores del universo T—. Con el uso de formulas de pertenencia


se puede saber la procedencia de cualquier termino del universo T. La especificacionquedarıa en la forma

Universos

T1 < T .

...

Tn < T .

Generadoras

-- las de cada universo T1, ..., Tn

Este patron se suele utilizar para agregar valores especiales a un universo dado, porejemplo, valores de error para desarrollar un tratamiento de errores, o simplementepara anadir mas valores al dominio de una operacion. El patron de enumeracion sepuede considerar un caso particular de suma directa de universos reducidos a un unicovalor.

3.4.3 Producto cartesiano

Este patron T = T1×· · ·×Tn se utiliza para especificar algebras A que se pueden con-siderar como el producto cartesiano de otras algebras A1, ...,An; es decir, tales que suselementos son tuplas de n componentes, cada componente de una de las algebras ante-riores. Cuando se aplica este patron se introduce el universo T junto con los universosT1,...,Tn, correspondientes a las algebras componentes, y sus respectivas operaciones ge-neradoras. Los valores del universo T se generan mediante una unica constante relativaque construye las tuplas a partir de sus componentes, y se anaden operaciones (pro-yecciones) para consultar las distintas componentes de cada valor. El aspecto generalde una especificacion por producto cartesiano es el siguiente

Universos

T1 .

...

Tn .

T .

Generadoras

(_,...,_) : T1 ... Tn -> T .

-- todas las de T1, ..., Tn

Operaciones

pr1 : T -> T1 .

...

prn : T -> Tn .

Axiomas

VAR t1:T1 .

3.4. PATRONES PARA LA ESPECIFICACION DE TIPOS ABSTRACTOS 3-61

...

VAR tn:Tn .

pr1 (t1,...,tn) = t1 .

...

prn (t1,...,tn) = tn .

Este patron coincide con el esquema para la definicion de registros de los lenguajesimperativos de programacion, en los que los nombres de los distintos campos hacen elpapel de las proyecciones pr, y cuando se combina con la suma directa, se obtienenpatrones mixtos como T = (T1|T2) × T2 × · · · × Tn equivalente a un esquema para ladefinicion de registros con variantes.

Ejercicio 3.7 Especifıquese el algebra de vectores del plano con coordenadas enterascon sus operaciones tıpicas (limitadas a numeros enteros) y con operaciones

_||_ : Vect2 Vect2 -> Booleanos .

_-|_ : Vect2 Vect2 -> Booleanos .

para determinar si dos vectores son paralelos o si son perpendiculares.

Ejercicio 3.8 Amplıese la especificacion anterior con un universo para los puntos delplano con coordenadas enteras y con operaciones

vector : Punto Punto -> Vector .

trasl : Punto Vect2 -> Punto .

scentral : Punto Punto -> Punto .

para producir el vector determinado por dos puntos, el punto producido al aplicar unvector a un punto y el punto simetrico de otro respecto a un centro de simetrıa dadopor el segundo argumento.

Ejercicio 3.9 Enunciese una especificacion para el algebra de los numeros racionales,basada en los numeros enteros y los naturales no nulos, con las cuatro operacionesaritmeticas.

3.4.4 Cociente

Este patron T = T ′/ ∼= se utiliza para especificar algebras A que se pueden considerarcomo el cociente de otras algebras A′ respecto a una relacion de equivalencia ∼= definidaentre sus elementos; es decir, tales que sus elementos se pueden considerar clases deequivalencia de elementos de las algebras A′. Para dar una especificacion siguiendo estepatron, se introducen los generos T y T’ junto con las operaciones generadoras de T’ yse establece la relacion de equivalencia entre los terminos de T’ como ecuaciones en elapartado de axiomas. Este patron es propio de las especificaciones semiconstructivas,aunque en dichas especificaciones se omite la mencion explıcita del universo T ′.


Ejercicio 3.10 Enunciese una especificacion para el algebra de los numeros raciona-les a partir del producto cartesiano Ent × NatNz con sus operaciones aritmeticas yrelaciones de orden tıpicas.

Ejercicio 3.11 Amplıese la especificacion del Ejercicio 3.8 anadiendo un universo pa-ra las rectas dadas como pares (punto,vector), estableciendo con cuidado las ecuacionesentre las distintas representaciones equivalentes de una misma recta, y definiendo larelacion de pertenencia entre puntos y rectas.

3.4.5 Recursion

El uso de la recursion da lugar a una infinidad de patrones caracterısticos de aquellasalgebras cuyos valores se obtienen mediante constructoras aplicadas a valores de lamisma algebra. Los patrones recursivos aparecen cuando un universo se define comosuma directa de otros universos en cuyas definiciones aparece el propio universo; enestos casos es necesario que en alguno de los sumandos de la suma directa no aparezca eluniverso que se define para que la recursion tenga sentido. Tienen patrones recursivosNat , que se puede considerar que obedece al patron Cero | s(Nat), las listas de numerosnaturales ListaNat que obedecen al patron Nil | (Nat×Lista) y los arboles binarios connumeros naturales en las hojas ArbolHNat que obedecen al patron Nat | (ArbolHNat ×ArbolHNat).

Combinando patrones recursivos con cocientes se obtienen especificaciones para con-juntos, bolsas, aplicaciones y grafos. Tambien se pueden construir patrones utilizandorecursion mutua como ocurre con el siguiente patron, que se utiliza para la especifica-cion de arboles generales de numeros naturales ArbolGNat , donde estos arboles se defi-nen conjuntamente con listas de arboles o BosqueNat siguiendo los esquemas siguientesArbolGNat = Nat× BosqueNat y BosqueNat = Nil | (ArbolGNat × BosqueNat).

Ejercicio 3.12 Enunciad especificaciones para bolsas y conjuntos de numeros natura-les limitando la especificacion a las operaciones generadoras y sus ecuaciones.

Ejercicio 3.13 Enunciad especificaciones para relaciones binarias con numeros natu-rales, para relaciones simetricas y para aplicaciones.

3.5. ORGANIZACION MODULAR DE LAS ESPECIFICACIONES 3-63

3.5 Organizacion modular de las especificaciones

A la hora de especificar algebras complejas con varios dominios se puede llegar a tenerespecificaciones demasiado extensas difıciles de controlar; en estos casos conviene pro-ceder por partes, construyendo primero especificaciones simples, posiblemente corres-pondientes a dominios individuales, y, sobre ellas, otras especificaciones mas complejashasta llegar a la especificacion pretendida. Esta labor se facilita enormemente dispo-niendo de algun mecanismo sintactico para individualizar partes de una especificaciony para incorporar o integrar unas partes en otras sin tener que volver a escribirlas. Paraesto aparecen los lenguajes modulares de especificacion que permiten localizar especi-ficaciones en modulos y permiten tambien que distintos modulos se puedan integrardentro otros mediante algun mecanismo de importacion. De esta forma, definiendomodulos correspondientes a universos individualizables dentro de una especificaciony estableciendo relaciones de importacion de unos modulos sobre otros se consigueestructurar especificaciones muy extensas en piezas (modulos) pequenas, facilmentemanejables. Las especificaciones obtenidas mediante un mecanismo de este tipo —siempre que no se establezcan dependencias circulares entre modulos— se denominanespecificaciones jerarquizadas.

La idea de los patrones de especificacion que hemos visto de una manera informalen la seccion 3.4 se puede formalizar de una manera mas detallada y sobre la base deun lenguaje modular de especificacion. La idea surge de que, a veces, determinadasespecificaciones jerarquizadas —especialmente las correspondientes a tipos de datosestructurados— tienen una apariencia comun diferenciandose solo en algun universoo grupo de operaciones importado. Para manejar estos casos de una forma unificadaresulta conveniente que el lenguaje de especificacion permita la definicion de “funcio-nes” entre especificaciones o, como se suelen denominar generalmente, especificacionesgenericas parametrizadas en otras especificaciones, tales que, a partir de una de ellas sepuedan conseguir distintas especificaciones con una misma estructura simplemente ins-tanciando, mediante algun mecanismo de instanciacion, las especificaciones parametroque, en el caso de los lenguajes modulares vienen dadas por modulos.

En adelante nos ocuparemos del estudio de uno de estos lenguajes modulares deespecificacion. Se trata del lenguaje MAUDE desarrollado en el SRI International porun equipo de investigadores encabezado por J. Meseguer.

Documents

Método Algebraico de Especificación. - UMAjmmb/ttaadd/ttaadd3-1.pdf · 2013-11-05 · Cap´ıtulo 3 Método Algebraico de Especificación. Los lenguajes de programación