Bases Formales de la Computación - Javeriana Calicic.puj.edu.co/wiki/lib/exe/fetch.php?media=materias:bfc:... · 2011-01-24 · Gerardo M. Sarria M. Introducci on Especi caci on

Gerardo M.Sarria M.

Introduccion

EspecificacionFormal con B

Introduccion

Lenguaje deEspecificacion

Java ModelingLanguage(JML)

Sintaxis ySemantica

Especificacion deProgramas

Bases Formales de la Computacion

Gerardo M. Sarria M.

Pontificia Universidad Javeriana

22 de agosto de 2008

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


VERIFICACION

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Contenido

1 Introduccion

2 Especificacion Formal con BIntroduccionLenguaje de Especificacion

3 Java Modeling Language (JML)Sintaxis y SemanticaEspecificacion de Programas

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Sistemas

Los Sistemas de Software se han convertido en una pieza clavede nuestras vidas:

Sistemas de transaccion bancarias

Aplicaciones comerciales en internet

Tarjetas inteligentes

Los Sistemas de Software son mas importantes ahora ya quehan penetrado en nuestro entorno y tanto los proveedores comolos clientes de dichos sistemas se estan comenzando apreocupar por su correctitud.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Sistemas

Sin embargo, dado que los Sistemas de Software . . .

son cada vez mas complejos,

tienen comportamientos disımiles,

admiten multiples puntos de vista

son propensos a fallar

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Sistemas

Sin embargo, dado que los Sistemas de Software . . .

son cada vez mas complejos,

tienen comportamientos disımiles,

admiten multiples puntos de vista

son propensos a fallar

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Sistemas

Las fallas son inaceptables en los sistemas de software actuales.

No es bueno apagar un sistema que no funcione bien paravolver a un estado seguro

Hay que pensar en los sistemas crıticos en donde hay vidashumanas envueltas

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Sistemas

Errores en sistemas de hardware y software que han sido muycostosos:

El bug aritmetico de punto flotante del Intel Pentiumcosto $500M (1994)

El cohete Ariane 5 perdio $7B (1996)

El choque del Mars Polar Lander costo $120M (2000)

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Verificacion

La verificacion es usada en diferentes contextos. Como . . .

un proceso para obtener la prueba de correctitud formal deun sistema por medio de deducciones (theorem proving)

cualquier accion tomada para encontrar errores en unprograma usando verificacion automatica (model-checking)

La Etapa de Pruebas en ingenierıa de software:

No es un un tecnica de verificacion

Es mas cercana a un muestreo que a una prueba decorrectitud exhaustiva

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Verificacion

La verificacion es usada en diferentes contextos. Como . . .

un proceso para obtener la prueba de correctitud formal deun sistema por medio de deducciones (theorem proving)

cualquier accion tomada para encontrar errores en unprograma usando verificacion automatica (model-checking)

La Etapa de Pruebas en ingenierıa de software:

No es un un tecnica de verificacion

Es mas cercana a un muestreo que a una prueba decorrectitud exhaustiva

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Limitaciones

Los metodos de verificacion no garantizan la correctituddel codigo actual. Ellos verifican un modelo abstracto.

Las pruebas de correctitud pueden ser de por sı incorrectas

El proceso de verificacion solo captura un pequena partede la funcionalidad de un sistema

La verificacion se hace con respecto a una especificaciondada, la cual se forma de manera manual, y puede estarincompleta

Las tecnicas de verificacion automatica (model-checking)estan restrigidas a sistemas de estado finito

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Limitaciones






Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Limitaciones






Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Limitaciones






Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Limitaciones






Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Prejuicios

Los metodos formales solo pueden ser usados pormatematicos

El uso de metodos formales haran lentos los proyectos

No es visual (faltan flechas y cajas)

El proceso de verificacion de por sı propenso a errores,ası que ¿por que molestarse con ellos?

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Dificultades Reales

Se debe pensar mucho antes de programar

Como incorporar esto en el proceso de desarrollo

La construccion de modelos no es facil

Tecnologıa de pruebas automaticas debe mejorar

Mala calidad de los documentos de requerimientos

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Aplicacion

Modelado Convertir un diseno en un formalismo. Se puedenecesitar abstraer elementos irrelevantes odetalles sin importancia.

Especificacion Indicar las propiedades que debe satisfacer eldiseno. La especificacion es dada usando unformalismo logico (logica temporal). Es necesarioque la especificacion este completa, es decir,cubra todas las propiedades que el sistema debesatisfacer.

Verificacion Ideal serıa que fuera completamente automatica.En la practica necesita asistencia humana: analisisde los resultados.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Aplicacion




Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Aplicacion




Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Sistemas

Los Sistemas de Software son modelos de sistemas reales quetienen un comportamiento coherente.

Cada caracterıstica que se elige observar de un sistema real serepresenta mediante una variable.

El valor de estas variables para todos los objetos del sistema enun momento dado es una observacion.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Observaciones

Ejemplo:Suponga que un sistema consta de tres objetos.De ellos se observa una caracterıstica que se representa por unavariable pi .

Una observacion podrıa ser:

p1 = 3 ∧ p2 = 9 ∧ p3 = 2

Definir los objetos y las caracterısticas observables correspondea la parte estatica de la descripcion de un sistema.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Observaciones

Ejemplo:Suponga que un sistema consta de tres objetos.De ellos se observa una caracterıstica que se representa por unavariable pi .

Una observacion podrıa ser:

p1 = 3 ∧ p2 = 9 ∧ p3 = 2

Definir los objetos y las caracterısticas observables correspondea la parte estatica de la descripcion de un sistema.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Observaciones

El numero de observaciones de un sistema puede ser inmenso(o infinito!).

Ejemplo:Suponga que en el mismo sistema se ha decidido observarcaracterısticas representadas por una variable z y una variabley .Se recolectan las siguientes observaciones:

z = 2 ∧ y = 0,707

z = 7 ∧ y = 0,378

z = 9 ∧ y = 0,33

z = 10 ∧ y = 0,316

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Observaciones

Los datos anteriores no permiten formarse una idea delfuncionamiento del sistema.

Solucion: Una propiedad o invariante del sistema

Para el caso anterior:√

z × y = 1

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Observaciones




z × y = 1

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Observaciones




z × y = 1

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Dinamica de los Sistemas

Pero un sistema NO es, en general, estatico.

¿Como evoluciona un sistema?

¿Que ocasiona un cambio en las observaciones?

EVENTOS

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica






EVENTOS

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica






EVENTOS

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos

Ejemplo:Un evento puede ocasionar un incremento en el valor de lavariable x del sistema anterior.

Ese mismo evento, entonces, tiene que ocasionar unamodificacion del valor de y , de modo que el invariante se sigacumpliendo.

Incrementar:begin

z , y ∶= z + 1, 1/√

z + 1end

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos

Ejemplo:Un evento puede ocasionar un incremento en el valor de lavariable x del sistema anterior.

Ese mismo evento, entonces, tiene que ocasionar unamodificacion del valor de y , de modo que el invariante se sigacumpliendo.

Incrementar:begin

z , y ∶= z + 1, 1/√

z + 1end

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Descripcion Completa de un Sistema

Parte Estatica:

Variables (caracterısticas observables)

Invariante

Parte Dinamica:

Conjunto de Eventos

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


B

B es una metodologıa para especificar, disenar y codificarSistemas.

La descripcion del sistema se hace de esta manera:

El invariante es un predicado

Los eventos son de la forma:

GUARDA

ACCION

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos

Los eventos podran ser de la siguiente forma basica:

nombre =ANY x , y , z , . . . WHERE

P(x , y , . . . , v , w , . . .)THEN

S(x , y , . . . , v , w , . . .)END

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos

La operacion del evento anterior corresponderıa a los siguientespasos:

1 Escoja valores para las variables locales x , y , . . . de maneraque para esos valores escogidos y para los valores acutalesde las variables del sistema, P(x , y , . . . , v , w , . . .) secumpla.

2 Si no fue posible escoger dichos valores, el evento no seactiva

3 Si la escogencia fue posible, ejecute la accionS(x , y , . . . , v , w , . . .)

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos





Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos





Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Eventos





Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Rodin

Rodin es una herramienta para el desarrollo riguroso desistemas de software complejos.

La descripcion de un sistema se hace de la siguiente manera:

1 Se describe un contexto

2 Se describe una maquina abstracta

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Ejemplo: Sistema MIO

Hay una cierta cantidad de buses

Hay una cierta cantidad de estaciones

En un momento dado, en una estacion puede estar un bus

Se observa la llegada y salidad de buses a las estaciones

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Componentes Estaticos - Contexto

Constante n: Numero total de buses

Constante m: Numero total de estaciones

Para estas constantes se definen axiomas que establecen suspropiedades:

variable tipon n ∈ N1

m m ∈ N1

Constantes, Conjuntos y sus Propiedades forman el Contextodel sistema

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Componentes Estaticos - Contexto

CONTEXT buses estacionesCONSTANTS

nm

AXIOMSaxm1 ∶ m ∶ N1

axm2 ∶ n ∶ N1

END

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Componentes Estaticos - Abstraccion

Variable be: Numero de buses en estaciones

Propiedades (tipo) de la variable:

be ∈ N

Observaciones de be obedecen a un INVARIANTE

be ≤ n ∧ be ≤ m

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Componentes Estaticos - Abstraccion

Variable be: Numero de buses en estaciones

Propiedades (tipo) de la variable:

be ∈ N

Observaciones de be obedecen a un INVARIANTE

be ≤ n ∧ be ≤ m

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Componentes Dinamicos

Inicializacion:be ∶= 0

Entra un bus a una estacion:

where be < n ∧ be < m then be ∶= be + 1 end

Sale un bus de una estacion:

where be > 0 then be ∶= be − 1 end

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica








Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica








Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Especificacion

MACHINE mioSEES buses estacionesVARIABLES

beINVARIANT

inv1 ∶ be ∶ Ninv2 ∶ be ≤ ninv3 ∶ be ≤ m

. . .

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Especificacion

EVENTSinitialisation

thenact1 ∶ be ∶= 0

end. . .

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


MIO: Especificacion

llegawhere

grd1 ∶ be < ngrd2 ∶ be < m

thenact1 ∶ be ∶= be + 1

endsale

wheregrd1 ∶ be > 0

thenact1 ∶ be ∶= be − 1

endEND

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Consistencia

El invariante representa los valores validos de las variables delsistema (estado).

Las acciones de los eventos modifican el estado.

El nuevo estado debe satisfacer el invariante.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Consistencia

Para un modelo con una variable v e invariante I (v), y unevento de la forma:

ANY x WHEREP(x , v)

THENv ∶= E(x , v)

END

la sentencia a probar es

I (v) ∧ P(x , v)⇒ I (E(x , v))

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Consistencia

Para el caso del MIO, se tiene

P(m, n) = m ∈ N1 ∧ n ∈ N1

I (m, n, be) = be ∈ N ∧ be ≤ n ∧ be ≤ m

Factibilidad de la inicializacion:

m ∈ N1 ∧ n ∈ N1 ⇒ ∃be.be = 0

Inicializacion satisface el invariante:

m ∈ N1 ∧ n ∈ N1 ⇒ 0 ∈ N ∧ 0 ≤ n ∧ 0 ≤ m

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Consistencia

Para el caso del MIO, se tiene

P(m, n) = m ∈ N1 ∧ n ∈ N1

I (m, n, be) = be ∈ N ∧ be ≤ n ∧ be ≤ m

Factibilidad de la inicializacion:

m ∈ N1 ∧ n ∈ N1 ⇒ ∃be.be = 0

Inicializacion satisface el invariante:

m ∈ N1 ∧ n ∈ N1 ⇒ 0 ∈ N ∧ 0 ≤ n ∧ 0 ≤ m

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Ejemplo: Partido de Futbol

Se observan personas. Unas estan adentro y otras afueradel campo

Una persona de afuera puede entrar al campo (comienzodel juego)

Una persona del campo puede cambiarse por una de afuera

Una persona de adentro puede salir (expulsion)

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Partido de Futbol - Contexto

CONTEXT partidoSETS

PERSONASAXIOMS

axm1 ∶ finite(PERSONAS)END

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Partido de Futbol - Variables e Invariante

VARIABLES adentro, afueraINVARIANT

inv1 ∶ adentro ⊆ PERSONASinv2 ∶ afuera ⊆ PERSONASinv1 ∶ adentro ∩ afuera = ∅inv1 ∶ adentro ∪ afuera = PERSONAS

. . .

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Partido de Futbol - Eventos

EVENTSinitialisation

thenact1 ∶ adentro ∶= ∅

act2 ∶ afuera ∶= PERSONASend

. . .

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica



entraany jwhere

grd1 ∶ afuera ≠ ∅grd2 ∶ j ∈ afuera

thenact1 ∶ afuera ∶= afuera/{j}act2 ∶ adentro ∶= adentro ∪ {j}

end. . .

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica



expulsadoany jwhere

grd1 ∶ adentro ≠ ∅

grd2 ∶ j ∈ adentrothen

act1 ∶ adentro ∶= adentro/{j}act2 ∶ afuera ∶= afuera ∪ {j}

end. . .

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica



cambioany e, swhere

grd1 ∶ adentro ≠ ∅

grd2 ∶ afuera ≠ ∅grd3 ∶ s ∈ adentrogrd4 ∶ e ∈ afuera

thenact1 ∶ adentro ∶= (adentro/{s}) ∪ {e}act2 ∶ afuera ∶= (afuera/{e}) ∪ {s}

endEND

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Partido de Futbol

Ejercicio:Considere otra especificacion del partido de futbol, quedistingue, entre las personas que estan adentro, a los jueces.

Obviamente a quien expulsan no puede ser un juez

Tampoco se puede cambiar un jugador por un juez

Especifique este sistema

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


JML

JML es un lenguaje de especificacion formal para programasescritos en Java.

La idea es:

Tener un registro de las desiciones de diseno eimplementacion

Especificar el comportamiento de las clases

Las especificaciones JML describen:

interfaces (nombres e informacion estatica)

comportamiento (como las clases e interfaces actuancuando son usadas)

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


JML

Las especificaciones JML son:

Predicados en logica de primer orden

Expresiones booleanas de Java

Las especificaciones se adicionan entre /*@ . . . @*/, o despuesde //@ en codigo Java

precondiciones

postcondiciones

invariantes

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Operadores

Operadores logicos de Java (∣∣, &&, !)

Operadores de relacion y corrimiento de Java (<, <=, . . . ,<<, >>)

Implicaciones logicas (==>, <==)

Equivalencias logicas (<==>, <=! =>)

Cuantificacion universal y existencial (/forall, /exists)

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Predicados

Los predicados de JML se expresan en logica de primer orden,construidos usando

Booleanos de Java,

otros operadores (/old, /result, /forall, /exists,/max, etc.),

y algunas palabras clave (requires, ensures,invariant, etc.).

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Predicados

Ejemplo:

p u b l i c c l a s s IntMathOps {/*@ pub l i c no rma l b eha v i o r

@ r e q u i r e s y >= 0 ;@ a s s i g n a b l e \ no th i ng ;@ en s u r e s 0 <= \ r e s u l t &&@ \ r e s u l t * \ r e s u l t <= y &&@ y < (\ r e s u l t + 1) * (\ r e s u l t + 1 ) ;@*/

p u b l i c s t a t i c i n t i s q r t ( i n t y ){

r e t u r n ( i n t ) Math . s q r t ( u ) ;}

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Predicados

requires. Se usa para especificar precondiciones.

ensures. Se usa para especificar postcondiciones.

normal behavior. El metodo termina normalmente, sinlanzar una excepcion.

exceptional behavior. El metodo lanza una excepcion.

behavior. El metodo podrıa terminar normal oabruptamente.

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Especificaciones Livianas

No usan el predicado behavior

Se escriben en lineas individuales despues de //@

p u b l i c c l a s s IntMathOps {//@ r e q u i r e s y >= 0 ;p u b l i c s t a t i c i n t i s q r t ( i n t y ){

r e t u r n ( i n t ) Math . s q r t ( y ) ;}

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Especificaciones Livianas

Si una palabra clave requires es olvidada, unaespecificacion requires true; se asume

Si una palabra clave assignable es olvidada, unaespecificacion assignable /everything; se asume

Si una palabra clave ensures es olvidada, unaespecificacion ensures true; se asume

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


JML y Diseno por Contrato

Las precondiciones y postcondiciones de los metodos definenun contrato entre el metodo (la clase) y el objeto que llama elmetodo.

Este contrato estipula que

1 Los metodos pueden asumir precondiciones y tienen queasegurar postcondiciones

2 Los clientes tienen que asegurar precondiciones y puedenasumir poscondiciones

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Contratos y Pruebas Obligatorias

c l a s s Decimal {i n t i n tPa r t , decPar t ;//@ i n v a r i a n t decPar t >= 0 ;

/*@ r e q u i r e s m != n u l l ;@ en s u r e s decPar t == m. decPar t &&@ i n tP a r t == \ o l d ( i n t P a r t ) ;@*/

vo id s e tDec ima l ( Decimal m) {decPar t = m. decPar t ;

}}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica



Para el metodo setDecimal:

Si m != null y m.decPart >= 0 entonces

decPart == m.decPart, yintPart == /old(intPart)

Para el objeto que hace el llamado:

o != null y o.decPart >= 0 tiene que ser cierto entodo sitio donde se haga el llamado al metodosetDecimal(o)

La postcondicion de setDecimal debe ser asumida enaquellos sitios

Adicionalmente:

decPart >= 0 debe ser una invariante de la claseDecimal

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica









Adicionalmente:


Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica









Adicionalmente:


Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Ejemplo: Clase Decimal

p u b l i c c l a s s Decimal extends Object {p u b l i c s t a t i c f i n a l s h o r t MAX DECIMAL NUMBER = ( s h o r t ) 32767 ;p u b l i c s t a t i c f i n a l s h o r t PRECISION = ( s h o r t ) 1 0 0 0 ;p r i v a t e s h o r t i n t P a r t = ( s h o r t ) 0 ;p r i v a t e s h o r t d e c P a r t = ( s h o r t ) 0 ;

p u b l i c Decimal s e t V a l u e ( Decimal d ) throws D e c i m a l E x c e p t i o n {r e t u r n s e t V a l u e ( d . g e t I n t P a r t ( ) , d . getDecPart ( ) ) ;

}

p u b l i c Decimal s e t V a l u e ( s h o r t i , s h o r t d ) throws D e c i m a l E x c e p t i o n {i f ( i < 0 | | d < 0) d e c i m a l e x c e p t i o n . t h r o w I t (DECIMAL OVERFLOW ) ;i n t P a r t = i ;d e c P a r t = d ;r e t u r n t h i s ;

}. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


/forall y /exists

(/forall int i; a[i] != null);

(/forall int i; (0 <= i && i < length) ==>src[srcOff + i] == dest[destOff + i]);

(/exists int i; (0 <= i && < length) &&(/forall int j; (0 <= j && j < i) ==>

src[srcOff + j] == dest[destOff + j]));

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


assert

assert P:

P tiene que ser cierto en un cierto punto en el cuerpo deun metodo

P es un propiedad JML valida en la logica

i f ( i <= 0 | | j < 0) {. . .

}e l s e i f ( j < 5) {

//@ a s s e r t i > 0 && 0 < j && j < 5 ;. . .

}e l s e {

//@ a s s e r t i > 0 && j > 5 ;. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


assert

assert P:

P tiene que ser cierto en un cierto punto en el cuerpo deun metodo

P es un propiedad JML valida en la logica

i f ( i <= 0 | | j < 0) {. . .

}e l s e i f ( j < 5) {

//@ a s s e r t i > 0 && 0 < j && j < 5 ;. . .

}e l s e {

//@ a s s e r t i > 0 && j > 5 ;. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


assert

JML no permite campos private en especificaciones public

Poner / ∗@ spec public @ ∗ / antes de una declaracion decampo private causa que el campo sea incluido en el alcancede toda especificacion

p u b l i c c l a s s Decimal extends Object {p u b l i c s t a t i c f i n a l s h o r t MAX DECIMAL NUMBER = ( s h o r t ) 32767 ;p u b l i c s t a t i c f i n a l s h o r t PRECISION = ( s h o r t ) 1 0 0 0 ;/*@ s p e c p u b l i c @*/ p r i v a t e s h o r t i n t P a r t = ( s h o r t ) 0 ;/*@ s p e c p u b l i c @*/ p r i v a t e s h o r t d e c P a r t = ( s h o r t ) 0 ;. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


assert

JML no permite campos private en especificaciones public

Poner / ∗@ spec public @ ∗ / antes de una declaracion decampo private causa que el campo sea incluido en el alcancede toda especificacion

p u b l i c c l a s s Decimal extends Object {p u b l i c s t a t i c f i n a l s h o r t MAX DECIMAL NUMBER = ( s h o r t ) 32767 ;p u b l i c s t a t i c f i n a l s h o r t PRECISION = ( s h o r t ) 1 0 0 0 ;/*@ s p e c p u b l i c @*/ p r i v a t e s h o r t i n t P a r t = ( s h o r t ) 0 ;/*@ s p e c p u b l i c @*/ p r i v a t e s h o r t d e c P a r t = ( s h o r t ) 0 ;. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


requires, ensures y normal behavior

requires RPrecondicion R

ensures QPostcondicion QQ tiene que ser cierto si el metodo termina normalmente(i.e. sin lanzar una java.lang.Exception)

normal behavior(total correctness)Si la precondicion es cierta el estado previo, entonces elmetodo termina en un estado normal, y la postcondiciones cierta en este estado

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica



p u b l i c c l a s s Decimal extends Object {/*@ n o r m a l b e h a v i o r ;

@ r e q u i r e s i >=0 && d>=0;@ e n s u r e s i n t P a r t == i && d e c P a r t == d ;@*/

p u b l i c Decimal s e t V a l u e ( s h o r t i , s h o r t d ) throws D e c i m a l E x c e p t i o n {i f ( i < 0 | | d < 0) E x c e p t i o n . t h r o w I t (DECIMAL OVERFLOW ) ;i n t P a r t = i ;d e c P a r t = d ;r e t u r n t h i s ;

}}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


signals y exceptional behavior

signals (E e) RPostcondicion Excepcional RR tiene que ser cierto si el metodo lanza una excepcion eque es subclase de E

exceptional behavior(total correctness)Si la precondicion es cierta el estado previo, entonces elmetodo terminara en un estado excepcional lanzando unajava.lang.Exception, y la postcondicion excepcional escierta en este estado

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica



p u b l i c c l a s s Decimal extends Object {/*@ e x c e p t i o n a l b e h a v i o r ;

@ r e q u i r e s i >=0 && d>=0;@ s i g n a l s ( D e c i m a l E x c e p t i o n e ) t r u e ;@*/


}}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


assignable

assignable L:

Un metodo solo puede modificar el conjunto deubicaciones de memoria denotadas por L

Cualquier otra ubicacion no listada puede entonces no sermodificada

esto es cierto para postcondiciones normal y excepcional


@ r e q u i r e s i >=0 && d>=0;@ a s s i g n a b l e i n t P a r t , d e c P a r t ;@ e n s u r e s t r u e ;@*/


}}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


assignable

assignable L:

Un metodo solo puede modificar el conjunto deubicaciones de memoria denotadas por L

Cualquier otra ubicacion no listada puede entonces no sermodificada

esto es cierto para postcondiciones normal y excepcional


@ r e q u i r e s i >=0 && d>=0;@ a s s i g n a b l e i n t P a r t , d e c P a r t ;@ e n s u r e s t r u e ;@*/


}}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


/old y /fresh

/old(e)Valor de una expresion r en el estado previo

/fresh(x)x no es nulo y no fue declarado en el estado previo

/*@ b e h a v i o r@ r e q u i r e s t r u e ;@ a s s i g n a b l e d e c i m a l ;@ e n s u r e s d e c i m a l == i * PRECISION + d ;@ s i g n a l s ( D e c i m a l E x c e p t i o n e ) ( i <0 | | d<0) &&@ d e c i m a l == \o l d ( d e c i m a l ) &&@ \ f r e s h ( e ) ;@*/

p u b l i c Decimal s e t V a l u e ( s h o r t i , s h o r t d ) throws D e c i m a l E x c e p t i o n {. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


/old y /fresh

/old(e)Valor de una expresion r en el estado previo

/fresh(x)x no es nulo y no fue declarado en el estado previo

/*@ b e h a v i o r@ r e q u i r e s t r u e ;@ a s s i g n a b l e d e c i m a l ;@ e n s u r e s d e c i m a l == i * PRECISION + d ;@ s i g n a l s ( D e c i m a l E x c e p t i o n e ) ( i <0 | | d<0) &&@ d e c i m a l == \o l d ( d e c i m a l ) &&@ \ f r e s h ( e ) ;@*/

p u b l i c Decimal s e t V a l u e ( s h o r t i , s h o r t d ) throws D e c i m a l E x c e p t i o n {. . .

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


/result

Representa el valor retornado por un metodo y tiene el mismotipo que el metodo

/*@ normal b e h a v i o r@ r e q u i r e s t r u e ;@ e n s u r e s \ r e s u l t <==>@ (\ e x i s t s i n t i ; i >=0 && i<MAX DATA && data [ i ]==c u r ) ;@*/

boolean c o n t e n s ( byte c u r ) {boolean r e s u = f a l s e ;byte i = ( byte ) 0 ;boolean found = f a l s e ;w h i l e ( i < MAX DATA && ! r e s u ) {

i f ( data [ i ] == c u r ) r e s u = t r u e ;e l s e i ++;

}r e t u r n r e s u ;

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


/result

Representa el valor retornado por un metodo y tiene el mismotipo que el metodo

/*@ normal b e h a v i o r@ r e q u i r e s t r u e ;@ e n s u r e s \ r e s u l t <==>@ (\ e x i s t s i n t i ; i >=0 && i<MAX DATA && data [ i ]==c u r ) ;@*/

boolean c o n t e n s ( byte c u r ) {boolean r e s u = f a l s e ;byte i = ( byte ) 0 ;boolean found = f a l s e ;w h i l e ( i < MAX DATA && ! r e s u ) {

i f ( data [ i ] == c u r ) r e s u = t r u e ;e l s e i ++;

}r e t u r n r e s u ;

}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


invariante

Tiene que ser cierto en todos los estados visibles:

El comienzo y final de cualquier invocacion a un metodo

El final de la invocacion a un constructor

Se asume de manera implıcita en el comienzo de unadeclaracion de metodo, y no tiene que ser cierto durante laejecuon de un metodo (i.e. puede ser temporalmente falso)

p u b l i c c l a s s Decimal extends Object {p u b l i c s t a t i c f i n a l s h o r t MAX DECIMAL NUMBER = ( s h o r t ) 32767 ;p u b l i c s t a t i c f i n a l s h o r t PRECISION = ( s h o r t ) 1 0 0 0 ;p u b l i c s h o r t i n t P a r t = ( s h o r t ) 0 ;p u b l i c s h o r t d e c P a r t = ( s h o r t ) 0 ;

/*@ i n v a r i a n t 0 <= i n t P a r t && i n t P a r t <= MAX DECIMAL NUMBER &&@ 0 <= d e c P a r t && d e c P a r t < PRECISION ;@*/

. . .}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


invariante

Tiene que ser cierto en todos los estados visibles:

El comienzo y final de cualquier invocacion a un metodo

El final de la invocacion a un constructor

Se asume de manera implıcita en el comienzo de unadeclaracion de metodo, y no tiene que ser cierto durante laejecuon de un metodo (i.e. puede ser temporalmente falso)

p u b l i c c l a s s Decimal extends Object {p u b l i c s t a t i c f i n a l s h o r t MAX DECIMAL NUMBER = ( s h o r t ) 32767 ;p u b l i c s t a t i c f i n a l s h o r t PRECISION = ( s h o r t ) 1 0 0 0 ;p u b l i c s h o r t i n t P a r t = ( s h o r t ) 0 ;p u b l i c s h o r t d e c P a r t = ( s h o r t ) 0 ;

/*@ i n v a r i a n t 0 <= i n t P a r t && i n t P a r t <= MAX DECIMAL NUMBER &&@ 0 <= d e c P a r t && d e c P a r t < PRECISION ;@*/

. . .}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


non null

Reemplaza un especificacion de invariante sobre un objeto nonulo

p u b l i c c l a s s S a l e r I D extends Object implements P a r t n e r I D {. . .

//@ i n v a r i a n t data != n u l l ;p u b l i c byte [ ] data = new byte [ ID LENGTH ] ;

. . .}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


non null

Reemplaza un especificacion de invariante sobre un objeto nonulo

p u b l i c c l a s s S a l e r I D extends Object implements P a r t n e r I D {. . .

p u b l i c /*@ non n u l l @*/ byte [ ] data = new byte [ ID LENGTH ] ;

. . .}

Gerardo M.Sarria M.

Introduccion


Introduccion



Sintaxis ySemantica


Fin de la Presentacion

Documents

Bases Formales de la Computación - Javeriana Calicic.puj.edu.co/wiki/lib/exe/fetch.php?media=materias:bfc:... · 2011-01-24 · Gerardo M. Sarria M. Introducci on Especi caci on