Teorías unificadas de la programación

Las Teorías Unificadas de Programación (UTP) en ciencias de la computación se ocupan de la semántica de los programas. Muestra cómo la semántica denotacional, la semántica operativa y la semántica algebraica se pueden combinar en un marco unificado para la especificación formal, diseño e implementación de programas y sistemas informáticos .

El libro de este título de C.A.R. Hoare y He Jifeng se publicó en la Serie Internacional de Ciencias de la Computación Prentice Hall en 1998 y ahora está disponible gratuitamente en la web.

Teorías

La base semántica de la UTP es el cálculo de predicados de primer orden, aumentado con construcciones de punto fijo a partir de la lógica de segundo orden. Siguiendo la tradición de Eric Hehner, los programas son predicados en el UTP, y no hay distinción entre programas y especificaciones a nivel semántico. En palabras de Hoare :

Un programa de computadora se identifica con el predicado más fuerte que describe cada observación relevante que se puede hacer sobre el comportamiento de una computadora que ejecuta ese programa.

En el lenguaje UTP, una teoría es un modelo de un paradigma de programación particular. Una teoría UTP se compone de tres ingredientes:

• un alfabeto, que es un conjunto de nombres de variables que denotan los atributos del paradigma que puede observar una entidad externa;
• una firma, que es el conjunto de construcciones de lenguaje de programación intrínsecas al paradigma; y
• una colección de condiciones de salubridad, que definen el espacio de programas que se ajustan al paradigma. Estas condiciones de salubridad generalmente se expresan como transformadores monotónicos de predicados idempotentes .

El refinamiento de un programa es un concepto importante en la UTP. Un programa $P_1$ es refinado por $P_2$ si y solo si cada observación que se pueda hacer de $P_2$ es también una observación de $P_1$. La definición de refinamiento es común en todas las teorías UTP:

$P_1⊑P_2\text{si y solo si}[P_2\Rightarrow P_1]$

dónde $\left[X\right]$ denota el cierre universal de todas las variables en el alfabeto.

Relaciones

La teoría UTP más básica es el cálculo del predicado alfabetizado, que no tiene restricciones alfabéticas ni condiciones de salubridad. La teoría de las relaciones es un poco más especializada, ya que el alfabeto de una relación puede consistir solo en:

• variables no decoradas ($v$), modelando una observación del programa al comienzo de su ejecución; y
• variables preparadas ($v^{\prime }$), modelando una observación del programa en una etapa posterior de su ejecución.

Algunas construcciones de lenguaje comunes se pueden definir en la teoría de las relaciones de la siguiente manera:

• La declaración de omisión, que no altera el estado del programa de ninguna manera, se modela como la identidad relacional:

$𝐬𝐤𝐢𝐩\equiv v^{\prime }=v$

• La asignación de valor $E$ a una variable $a$ se modela como configuración $a^{\prime }$ a $E$ y mantener todas las demás variables (denotadas por $u$ ) constante:

$a:=E\equiv a^{\prime }=E\wedge u^{\prime }=u$

• La composición secuencial de dos programas es solo una composición relacional de estado intermedio:

$P_1;P_2\equiv \mathrm{\exists }{v}_0\bullet P_1[v_0/v^{\prime }]\wedge P_2[v_0/v]$

• La elección no determinista entre programas es su mayor límite inferior:

$P_1\sqcap P_2\equiv P_1\vee P_2$

• La elección condicional entre programas se escribe usando notación infija:

$P_1◃C▹P_2\equiv (C\wedge P_1)\vee (\mathrm{\neg }C\wedge P_2)$

• Una semántica para la recursividad viene dada por el punto menos fijo $\mu 𝐅$ de un transformador predicado monotónico $𝐅$ :

$\mu X\bullet 𝐅(X)\equiv \sqcap \{X\mid 𝐅(X)⊑X\}$

Otras lecturas

• Jim Woodcock y Ana Cavalcanti. Una introducción tutorial a los diseños con UTP. En Integrated Formal Methods, volumen 2999 de Lecture Notes in Computer Science, páginas 40–66. Springer Berlin / Heidelberg, 2004. Plantilla:ISBN. Plantilla:Doi   paper
• Ana Cavalcanti y Jim Woodcock. Una introducción tutorial a CSP en UTP. En Refinement Techniques in Software Engineering, volumen 3167 de Lecture Notes in Computer Science, páginas 220–268. Springer Berlin / Heidelberg, 2006. Plantilla:Doi   paper

Enlaces externos

• Sitio web del libro UTP
• Libro de UTP en Archive.org