TEMA:

Semántica Axiomática

Semántica Denotacional

Semántica Operacional

FECHA:

01 de Marzo del 2011

CICLO:

2011 A

MATERIA:

Lenguajes de Programación Comparados

PROFESORA:

María Magdalena Murillo Leaño

ALUMNO:

Jéssica Araceli Cervantes Núñez

1

Equipo #

Integrantes:

Alvarado rubio Jorge Gerardo.Cervantes Núñez Jessica Araceli. (D04)

Larios Montes María Guadalupe.López Salazar Jessica.

Luna Rincón Yesenia Nayeli.Mendoza Sánchez Roberto.

Murillo Carranza Alejandro. (D04)Patiño Muñoz Francisco Jesús. (D04)

2

SEMÁNTICA AXIOMÁTICA

El semántica axiomática es un enfoque basado en el lógica matemática quién sirve para probar que uno programa informático este correcto.

Esta semántica tiende a considerar un programa como un transformador de propiedades lógicas, es decir el significado otorgado al programa es un conjunto de predicados que son comprobados por el estado de la máquina (caracterizado por su memoria) que realizó el programa, a condición de que se haya comprobado un otro conjunto de predicados antes de la ejecución.

Lo que está en juego es en general encontrar la semántica axiomática más fina posible: dada una especificación de salida que se quiere en general el más fuerte (restrictiva) posible, se buscan las precondiciones más escasas (amplios) que consiguen este resultado.

La lengua: la lógica de Hoare

Las propiedades de semántica axiomática se expresan, en general, en forma de expresiones de lógica de Hoare :

{p} S {q}

dónde p y q son propiedades expresadas en la lógica de los predicados, p supuesto compruebase por la memoria antes de la ejecución del programa S (inglés: statement), y q delante de ser comprobado después de ejecución de S sobre una máquina que comprueba p. Debido a que la ejecución del programa no termina inevitablemente, hay en realidad 2 interpretaciones de una expresión de la lógica de Hoare:

{p} S {q} quiere decir “si el estado de la memoria satisfecha p y S termine, entonces, después de ejecución, el estado de la memoria satisfecha q. » : corrección parcial

[p] S [q] quiere decir “si el estado de la memoria satisfecha p, entonces S termine y después de ejecución, el estado de la memoria satisfecha q. » : corrección total

Estas dos interpretaciones conducen a semánticos axiomáticos diferentes.

Pruebas

Dar la semántica axiomática de un programa, es realizar el prueba de algunas propiedades sobre éste. Esta semántica, esta prueba, puede ser representada, en general, por dos métodos: o por el árbol de inferencia que utiliza explícitamente el normas de inferencia específicos a la semántica axiomática de la lengua informática utilizada (prueba a Hoare), esté por la redacción del programa en su totalidad, pero decorado de predicados entre cada instrucción (prueba a Floyd).

3

La prueba al Floyd da más de un método sistemático muy práctico para obtener esta prueba en los programas imperativos secuenciales: se va de lo que debe comprobarse después del programa, luego se remonta instrucción por instrucción buscando a cada paso la precondición más escasa.

Ejemplo: prueba al Floyd dealgoritmo de Euclide ancho

Esto es el algoritmo de Euclide ancho, que calcula el pgcd entradas a y b, así como los coeficientes p y q deidentidad de Bézout :

a0 = tiene;b0 = b;p = 1; q = 0;r = 0; s = 1;¡mientras b! = 0 hacer c = tiene módulo b;cociente = tiene/b;a = b;b = c;nouveau_r = p - cociente * r;nouveau_s = q - cociente * s;p = r;q = s;r = nouveau_r;s = nouveau_s;hecho

Una de las propiedades queridas al final es: a = p*a0 + q*b0. Vamos a remontar el programa instrucción por instrucción para obtener la prueba (al Floyd) que se comprueba bien eso.

// que debe completarse //

4

SEMÁNTICA DENOTACIONAL

La semántica denotacional define unas aplicaciones (funciones) de valoración semántica que asignan a cada construcción denotada tal objeto matemático que modela su significado.Se dice que la construcción denota tal objeto o que este objeto es la denotación de dicha construcción. En otras palabras, la semántica denotacional indica que función matemática se obtiene a la salida ante unas entradas del programa, sin preocuparse de la ejecución paso a paso del programa. Existe una variante de esta semántica que es la semántica algebraica, en la que se utiliza conceptos algebraicos a la hora de modelar el significado de las construcciones. El primer paso a realizar en la definición de la semántica denotacional de un determinado lenguaje es el establecimiento de un dominio semántico al que pertenecerán los resultados obtenidos de la evaluación de las construcciones del lenguaje. Esta evaluación es proporcionada por un conjunto de funciones de significado cuyo dominio esta constituido por el conjunto de construcciones del lenguaje y cuyo rango (o imajen) viene dado por el dominio semántico.Este tipo de semántica dotan de significado a los elementos del lenguaje de una manera mas formal y abstracta, pero sin embargo también necesitan un mayor conocimiento de conceptos matemáticos, que no tienen por que ser básicos ni elementales.

5

SEMÁNTICA OPERACIONAL

En informática, semántica operacional es una manera de dar el significado a programas de computadora de una manera matemáticamente rigurosa (véase semántica formal de lenguajes de programación).

La semántica operacional para un lenguaje de programación describe cómo un programa válido se interpreta como secuencias de pasos de cómputo. Estas secuencias entonces sea el significado del programa. En el contexto de programas funcionales, el paso final en una secuencia que termina vuelve el valor del programa. (En general puede haber muchas secuencias del cómputo y muchos vuelven los valores para un solo programa, porque el programa podría ser no determinista.)

Una manera común riguroso de definir la semántica operacional, iniciada cerca Gordon Plotkin en su papel 1981 “un acercamiento estructural a la semántica operacional”, es proporcionar a sistema de la transición del estado para la lengua del interés. Tal definición permite un análisis formal de una lengua, permitiendo el estudio de relaciones entre los programas. Las relaciones importantes incluyen la simulación preorders y bisimulation. Éstos son especialmente útiles en el contexto de concurrencia.

Definir la semántica operacional a través de un sistema de la transición del estado es hecha generalmente dando definición inductiva del sistema de transiciones posibles. Esto toma generalmente la forma de un sistema de reglas de inferencia cuáles definen las transiciones válidas en el sistema.

La primera semántica operacional era la de cálculo de la lambda. Máquinas abstractas en la tradición del Máquina de SECD se relacionan de cerca.

6