Théories unificatrices de la programmation

Les théories unificatrices de la programmation ( UTP ) en informatique traitent de la sémantique des programmes . Elles montrent comment la sémantique dénotationnelle , la sémantique opérationnelle et la sémantique algébrique peuvent être combinées dans un cadre unifié pour la spécification formelle , la conception et la mise en œuvre des programmes et des systèmes informatiques .

L'ouvrage portant ce titre, écrit par CAR Hoare et He Jifeng a été publié dans la collection Prentice Hall International Series in Computer Science en 1998 et est disponible gratuitement sur le Web.

Une série de symposiums UTP a été lancée en 2006.

Théories

Le fondement sémantique de l'UTP repose sur le calcul des prédicats du premier ordre , enrichi de constructions à point fixe issues de la logique du second ordre. Dans la lignée des travaux d' Eric Hehner , les programmes sont des prédicats en UTP, et aucune distinction n'est faite entre programmes et spécifications au niveau sémantique. Comme l'affirme Hoare :

Un programme informatique est identifié par le prédicat le plus fort décrivant chaque observation pertinente qui peut être faite du comportement d'un ordinateur exécutant ce programme.

Dans le jargon UTP, une théorie est un modèle d'un paradigme de programmation particulier. Une théorie UTP est composée de trois éléments :

un alphabet , qui est un ensemble de noms de variables désignant les attributs du paradigme qui peuvent être observés par une entité externe ;
une signature , c'est-à-dire l'ensemble des constructions du langage de programmation intrinsèques au paradigme ; et
un ensemble de conditions de validité , qui définissent l'espace des programmes qui s'inscrivent dans le paradigme. Ces conditions de validité sont généralement exprimées sous forme de transformateurs de prédicats idempotents monotones .

Le perfectionnement des programmes est un concept important dans l'UTP. ${\displaystyle P_{1 <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle P_{1}}</annotation></semantics></math><img src=$ ${\displaystyle P_{2 <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle P_{2}}</annotation></semantics></math><img src=$ ${\displaystyle P_{2 <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle P_{2}}</annotation></semantics></math><img src=$ ${\displaystyle P_{1 <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle P_{1}}</annotation></semantics></math><img src=$

${\displaystyle P_{1}\sqsubseteq P_{2}\quad { ext{if and only if}}\quad \left[P_{2}\Rightarrow P_{1} ight] <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>⊑</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mspace></mspace><mrow><mtext>si et seulement si</mtext></mrow><mspace></mspace><mrow><mo>[</mo><mrow><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mo>⇒</mo><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub></mrow><mo>]</mo></mrow></mstyle></mrow><annotation>{\displaystyle P_{1}\sqsubseteq P_{2}\quad { ext{si et seulement si}}\quad \left[P_{2}\Rightarrow P_{1} ight]}</annotation></semantics></math><img src=$

où ${\displaystyle \left[X ight] <semantics><mrow><mstyle><mrow><mo>[</mo><mi>X</mi><mo>]</mo></mrow></mstyle></mrow><annotation>{\displaystyle \left[X ight]}</annotation></semantics></math><img src=$

Rapports

La théorie UTP la plus élémentaire est le calcul des prédicats alphabétique, qui ne comporte aucune restriction d'alphabet ni condition de validité. La théorie des relations est légèrement plus spécialisée, car l'alphabet d'une relation ne peut comprendre que :

variables non décorées ( ${\displaystyle v <semantics><mrow><mstyle><mi>v</mi></mstyle></mrow><annotation>{\displaystyle v}</annotation></semantics></math><img src=$
variables primées ( ${\displaystyle v' <semantics><mrow><mstyle><msup><mi>v</mi><mo>′</mo></msup></mstyle></mrow><annotation>{\displaystyle v'}</annotation></semantics></math><img src=$

Certaines constructions linguistiques courantes peuvent être définies dans la théorie des relations comme suit :

L'instruction skip, qui ne modifie en aucune façon l'état du programme, est modélisée comme l'identité relationnelle :

${\displaystyle \mathbf {skip} \equiv v'=v <semantics><mrow><mstyle><mrow><mi>s</mi><mi>k</mi><mi>je</mi><mi>p</mi></mrow><mo>≡</mo><msup><mi>v</mi><mo>′</mo></msup><mo>=</mo><mi>v</mi></mstyle></mrow><annotation>{\displaystyle \mathbf {skip} \equiv v'=v}</annotation></semantics></math><img src=$

L'attribution de valeur ${\displaystyle E <semantics><mrow><mstyle><mi>E</mi></mstyle></mrow><annotation>{\displaystyle E}</annotation></semantics></math><img src=$ ${\displaystyle a <semantics><mrow><mstyle><mi>un</mi></mstyle></mrow><annotation>{\displaystyle a}</annotation></semantics></math><img src=$ ${\displaystyle a' <semantics><mrow><mstyle><msup><mi>un</mi><mo>′</mo></msup></mstyle></mrow><annotation>{\displaystyle a'}</annotation></semantics></math><img src=$ ${\displaystyle E <semantics><mrow><mstyle><mi>E</mi></mstyle></mrow><annotation>{\displaystyle E}</annotation></semantics></math><img src=$ ${\displaystyle u <semantics><mrow><mstyle><mi>vous</mi></mstyle></mrow><annotation>{\displaystyle u}</annotation></semantics></math><img src=$

${\displaystyle a:=E\equiv a'=E\land u'=u <semantics><mrow><mstyle><mi>un</mi><mo>:=</mo><mi>E</mi><mo>≡</mo><msup><mi>un</mi><mo>′</mo></msup><mo>=</mo><mi>E</mi><mo>∧</mo><msup><mi>vous</mi><mo>′</mo></msup><mo>=</mo><mi>vous</mi></mstyle></mrow><annotation>{\displaystyle a:=E\equiv a'=E\land u'=u}</annotation></semantics></math><img src=$

La composition séquentielle de deux programmes n'est autre qu'une composition relationnelle d'états intermédiaires :

${\displaystyle P_{1};P_{2}\equiv \exists v_{0}\bullet P_{1}[v_{0}/v']\land P_{2}[v_{0}/v] <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>;</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mo>≡</mo><mi>∃</mi><msub><mi>v</mi><mrow><mn>0</mn></mrow></msub><mo>∙</mo><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>[</mo><msub><mi>v</mi><mrow><mn>0</mn></mrow></msub><mrow><mo>/</mo></mrow><msup><mi>v</mi><mo>′</mo></msup><mo>]</mo><mo>∧</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mo>[</mo><msub><mi>v</mi><mrow><mn>0</mn></mrow></msub><mrow><mo>/</mo></mrow><mi>v</mi><mo>]</mo></mstyle></mrow><annotation>{\displaystyle P_{1};P_{2}\equiv \exists v_{0}\bullet P_{1}[v_{0}/v']\land P_{2}[v_{0}/v]}</annotation></semantics></math><img src=$

Le choix non déterministe entre les programmes constitue leur plus grande limite inférieure :

${\displaystyle P_{1}\sqcap P_{2}\equiv P_{1}\lor P_{2 <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>⊓</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mo>≡</mo><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>∨</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{\displaystyle P_{1}\sqcap P_{2}\equiv P_{1}\lor P_{2}}</annotation></semantics></math><img src=$

Le choix conditionnel entre programmes s'écrit en notation infixe :

${\displaystyle P_{1} riangleleft C riangleright P_{2}\equiv (C\land P_{1})\lor (\lnot C\land P_{2}) <semantics><mrow><mstyle><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>◃</mo><mi>C</mi><mo>▹</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mo>≡</mo><mo>(</mo><mi>C</mi><mo>∧</mo><msub><mi>P</mi><mrow><mn>1</mn></mrow></msub><mo>)</mo><mo>∨</mo><mo>(</mo><mi>¬</mi><mi>C</mi><mo>∧</mo><msub><mi>P</mi><mrow><mn>2</mn></mrow></msub><mo>)</mo></mstyle></mrow><annotation>{\displaystyle P_{1} riangleleft C riangleright P_{2}\equiv (C\land P_{1})\lor (\lnot C\land P_{2})}</annotation></semantics></math><img src=$

La sémantique de la récursivité est donnée par le plus petit point fixe. ${\displaystyle \mu \mathbf {F} <semantics><mrow><mstyle><mi>μ</mi><mrow><mi>F</mi></mrow></mstyle></mrow><annotation>{ displaystyle mu mathbf {F}}</annotation></semantics></math><img src=$ ${\displaystyle \mathbf {F} <semantics><mrow><mstyle><mrow><mi>F</mi></mrow></mstyle></mrow><annotation>{\displaystyle \mathbf {F} }</annotation></semantics></math><img src=$

${\displaystyle \mu X\bullet \mathbf {F} (X)\equiv \sqcap \left\{X\mid \mathbf {F} (X)\sqsubseteq X ight\ <semantics><mrow><mstyle><mi>μ</mi><mi>X</mi><mo>∙</mo><mrow><mi>F</mi></mrow><mo>(</mo><mi>X</mi><mo>)</mo><mo>≡</mo><mo>⊓</mo><mrow><mo>{</mo><mrow><mi>X</mi><mo>∣</mo><mrow><mi>F</mi></mrow><mo>(</mo><mi>X</mi><mo>)</mo><mo>⊑</mo><mi>X</mi></mrow><mo>}</mo></mrow></mstyle></mrow><annotation>{\displaystyle \mu X\bullet \mathbf {F} (X)\equiv \sqcap \left\{X\mid \mathbf {F} (X)\sqsubseteq X ight\}}</annotation></semantics></math><img src=$

. Integrated Formal Methods . Lecture Notes in Computer Science , vol. 2999. Springer. p. 40–66 . doi : 10.1007/978-3-540-24756-2_4 . ISBN 978-3-540-21377-2.

Cavalcanti, Ana et Woodcock, Jim (2006). « Introduction didactique à CSP dans Unifying Theories of Programming » (PDF) . Refinement Techniques in Software Engineering . Lecture Notes in Computer Science. Vol. 3167. Springer. p. 220–268 . doi : 10.1007/11889229_6 . ISBN 978-3-540-46253-8.