Sjednocující teorie programování - Unifying Theories of Programming - Wikipedia

Sjednocující teorie programování (UTP) v počítačová věda vypořádat se programová sémantika. Ukazuje to jak denotační sémantika, operační sémantika a algebraická sémantika lze kombinovat do jednotného rámce pro formální specifikace, návrh a implementace programy a počítačové systémy.

Kniha tohoto titulu od AUTO. Hoare a On Jifeng byla zveřejněna v Prentice Hall International Series in Computer Science v roce 1998 a nyní je volně dostupný na webu.^[1]

Teorie

Sémantickým základem UTP je predikátový počet prvního řádu, rozšířené o konstrukty s pevným bodem z logiky druhého řádu. V návaznosti na tradici Eric Hehner, programy jsou predikáty v UTP a na sémantické úrovni není žádný rozdíl mezi programy a specifikacemi. Podle slov Hoare:

Počítačový program je označen nejsilnějším predikátem popisujícím každé relevantní pozorování, které lze provést z chování počítače provádějícího tento program.^[2]

V UTP řeči, a teorie je model konkrétního paradigmatu programování. Teorie UTP se skládá ze tří složek:

an abeceda, což je sada názvů proměnných označujících atributy paradigmatu, které lze pozorovat externí entitou;
A podpis, což je sada konstruktů programovacího jazyka, které jsou vlastní paradigmatu; a
sbírka zdravotní podmínky, které definují prostor programů, které zapadají do paradigmatu. Tyto zdravotní podmínky jsou obvykle vyjádřeny jako monotóní idempotentní predikátové transformátory.

Upřesnění programu je důležitým konceptem v UTP. Program ${ displaystyle P_ {1}}$ je rafinován ${ displaystyle P_ {2}}$ právě když každé pozorování, z něhož lze učinit ${ displaystyle P_ {2}}$ je také pozorováním ${ displaystyle P_ {1}}$ Definice upřesnění je v teoriích UTP běžná:

${ displaystyle P_ {1} sqsubseteq P_ {2} quad { text {tehdy a jen tehdy}} quad left [P_ {2} Rightarrow P_ {1} right]}$

kde ${ displaystyle left [X right]}$ označuje^[3] the univerzální uzavření všech proměnných v abecedě.

Vztahy

Nejzákladnější teorií UTP je abecední predikátový počet, který nemá žádná abecední omezení ani zdravotní podmínky. Teorie vztahů je poněkud specializovanější, protože abeceda vztahu se může skládat pouze z:

nedekorované proměnné ( ${ displaystyle v}$ ), modelování pozorování programu na začátku jeho provádění; a
primované proměnné ( ${ displaystyle v '}$ ), modelování pozorování programu v pozdější fázi jeho provádění.

Některé konstrukty společného jazyka lze v teorii vztahů definovat takto:

Příkaz skip, který žádným způsobem nemění stav programu, je modelován jako relační identita:

${ displaystyle mathbf {přeskočit} equiv v '= v}$

Přiřazení hodnoty ${ displaystyle E}$ do proměnné ${ displaystyle a}$ je modelován jako nastavení ${ displaystyle a '}$ na ${ displaystyle E}$ a uchování všech ostatních proměnných (označených ${ displaystyle u}$ ) konstantní:

${ displaystyle a: = E equiv a '= E land u' = u}$

The sekvenční složení dvou programů je spravedlivý relační složení střední stav:

${ displaystyle P_ {1}; P_ {2} equiv existuje v_ {0} odrážka P_ {1} [v_ {0} / v '] land P_ {2} [v_ {0} / v]}$

Nedeterministická volba mezi programy je jejich největší dolní mez:

${ displaystyle P_ {1} sqcap P_ {2} equiv P_ {1} lor P_ {2}}$

Podmíněný výběr mezi programy se zapisuje pomocí infixové notace:

${ displaystyle P_ {1} triangleleft C triangleright P_ {2} equiv (C land P_ {1}) lor ( lnot C land P_ {2})}$

Sémantika pro rekurze je dán nejméně pevný bod ${ displaystyle mu mathbf {F}}$ monotónního predikátového transformátoru ${ displaystyle mathbf {F}}$ :

${ displaystyle mu X kulka mathbf {F} (X) ekviv sqcap levý {X střední mathbf {F} (X) sqsubseteq X pravý }}$

Reference

^ Hoare, C. A. R .; Jifeng, He (1. dubna 1998). Sjednocující teorie programování. Divize Prentice Hall College. p. 320. ISBN 978-0-13-458761-5. Citováno 17. září 2014.
^ AUTO. Hoare „Programování: Čarodějnictví nebo věda? Software IEEE, 1 (2): 5–16, duben 1984. ISSN 0740-7459. doi:10.1109 / MS.1984.234042.
^ Edsger W. Dijkstra a Carel S. Scholten. Predikční počet a programová sémantika. Texty a monografie v informatice. Springer-Verlag New York, Inc., New York, NY, USA, 1990. ISBN 0-387-96957-8.

Další čtení

Jim Woodcock a Ana Cavalcanti. Výukový úvod k návrhům v Unifying Theories of Programming. v Integrované formální metody, svazek 2999 z Přednášky z informatiky, strany 40–66. Springer Berlín / Heidelberg, 2004. ISBN 978-3-540-21377-2. doi:10.1007/978-3-540-24756-2_4 CiteSeer^X: 10.1.1.99.2929 papír
Ana Cavalcanti a Jim Woodcock. Výukový úvod do CSP v Unifying Theories of Programming. v Techniky zdokonalování v softwarovém inženýrství, svazek 3167 přednášek z informatiky, strany 220–268. Springer Berlin / Heidelberg, 2006. doi:10.1007/11889229_6 CiteSeer^X: 10.1.1.97.3469 papír

externí odkazy

[1] Hoare, C. A. R .; Jifeng, He (1. dubna 1998). Sjednocující teorie programování. Divize Prentice Hall College. p. 320. ISBN 978-0-13-458761-5. Citováno 17. září 2014.

[2] AUTO. Hoare „Programování: Čarodějnictví nebo věda? Software IEEE, 1 (2): 5–16, duben 1984. ISSN 0740-7459. doi:10.1109 / MS.1984.234042.

[3] Edsger W. Dijkstra a Carel S. Scholten. Predikční počet a programová sémantika. Texty a monografie v informatice. Springer-Verlag New York, Inc., New York, NY, USA, 1990. ISBN 0-387-96957-8.

[1]

[2]

[3]