A B formális nyelv (B-method, B formal method)

Nyelvi elemek

Lexikális egységek

A B-ben a következő kategóriába sorolhatók a lexikális egységek:

A B operátorai sokszor a megjelenítés szempontjából nem ASCII karakterekből állnak, de a valóságban ASCII karakterekkel vannak reprezentálva. Például az eleme jel a referenciában (és ebben a leírásban is) így jelenik meg: ∈, a forrásfájlban viszont valójában egy kettőspont lesz tárolva. A fejlesztőkörnyezetek egy része a kettőspont helyett valóban egy ∈ szimbólumot jelenít meg, a kettőspont lenyomására pedig azt fogjuk látni, hogy egy ∈ szimbólum íródott be a szövegbe (miközben a háttérben egy kettőspont lett beírva).

Azaz ne gondoljuk azt, hogy ezek a szimbólumok Unicode-szimbólumok lennének és a B Unicode szimbólumokkal dolgozna. A példaprogramok úgy vannak elkészítve, ahogy egy fejlesztőkörnyezetben látszana (és ahogyan könnyen olvasható), és nem úgy, ahogy be kell őket gépelni. A legfontosabbak szimbólumok, amik ASCII karakterekkel vannak reprezentálva:

Szimbólum ASCII Jelentés
! minden
# létezik
& és
or vagy
× * Descartes-szorzat
--> függvény (pl. f∈ A→B)
<-- művelet (pl. result←gcd(a,b))
=> implikáció
<=> ekvivalencia
/= nem egyenlő
: eleme
<: részhalmaza
<= kisebb-egyenlő
>= nagyobb-egyenlő
dupla szárú Z INTEGER egész számok halmaza
dupla szárú N NAT természetes számok halmaza
dupla szárú P POW hatványhalmaz
{} üres halmaz

Egyebek:

Típusok

A B típusai

A nyelv típusrendszere a halmazelméletre épül. A B-nek van néhány alaptípusa és néhány alap-típuskonstrukciója. Ezekből származtatható a többi beépített típus és a többi típuskonstrukció.

Az alaptípusok: Az alap-típuskonstrukciók, és a konstruált típus típusértékhalmaza: Az ezen alaptípusok és alap-típuskonstrukciók segítségével képzett típusokra megszorításokat is tehetünk, így új típusokat (igazából altípusokat) kapunk. Például a NAT az a halmaz, ami a Z-nek a nullánál nagyobb elemeit tartalmazza. Sok más típuskonstrukció is van, például az S→T az S-ből a T-be képező függvények halmaza.

Típuslevezetés

Amikor egy konstanst vagy változót írunk le, nem írjuk ki explicit a típusát, csak állításokat írunk le rá. Ezekből az állításokból a fordító le tudja vezetni a konstans vagy változó típusát. A következő példában az elemző le fogja vezeteni a maxelemszam típusát abból, hogy milyen megszorítást tettünk rá:

MACHINE halmaz(maxelemszam) CONSTRAINTS maxelemszam∈0..10 END

Az állítások (elsőrendű logikai állítások) tartalmazhatnak kvantorokat és kvantált változókat. Mivel az elemzőnek ezen (matematikai) változók típusát is le kell tudni vezetni, az egzisztenciálisan kvantált állításokat mindig "és"-sel, az univerzálisan kvantáltakat pedig vaggyal kell kezdeni. Például:

∀x (x∈0..10 ⇒ f(x)>0) /* rendben: x egy egész */ ∃x (x∈0..10 ∧ f(x)>0) /* rendben: x egy egész */ ∃x (x∈0..10 ∨ f(x)>0) /* rossz */
A konstans kifejezések típusát is ki tudja találni az elemző, például:

Absztrakt gépek

A B nyelv objektumalapú, de nem objektumelvű. A B-módszerben absztrakt gépek segítségével modellezzük a megoldandó feladatot. Az absztrakt gépeket specifikáljuk és implementáljuk, a működésüket különböző szinteken írjuk le. Az absztrakt gép specifikációja a megoldandó feladat specifikációja, az absztrakt gép implementációja pedig a feladatot megoldó program. Az absztrakt gépek sokban hasonlítanak, de nem feleltethetőek meg az osztályoknak, illetve objektumoknak, de azok működése szimulálható vele.

Az absztrakt gépek szintjei

Az absztrakt gépek működését több szinten írjuk le:

A specifikáció az absztrakt gép működésének legabsztraktabb leírása matematikai formalizmus (halmazelmélet és elsőrendű logika) segítségével. Ebben fogalmazzuk meg azt, hogy mit várunk el a rendszertől. Leírjuk a programban található változókat (azaz az állapotteret), a változók kezdeti értékeit, a program tulajdonságait (például az invariánsokat), a végezhető műveleteket. A változók inicializálását és a végezhető műveleteket általánosított értékadások formájában írjuk le.

A leírás közbülső szintjei a finomítások. Egy finomítás vagy egy specifikáció finomítása, vagy egy másik finomításé. A finomításnak rendelkeznie kell az eredeti komponens összes tulajdonságával. Állapotterének altere az eredeti komponens állapottere. A finomítás során az eredeti komponens absztrakt tulajdonságai egyre konkrétabbakká, nemdeterminisztikus értékadásai egyre determinisztikusabbá válnak.

A legalsó szint az implementáció. Ez egy finomítást, vagy közvetlenül egy specifikációt implementál. Az implementáció hasonlít egy konkrét programozási nyelvre abban, hogy a műveletek belsejében általánosított értékadások helyett szekvenciákat, elágazásokat és ciklusokat tartalmaz. (A bizonyítások miatt a ciklusok rendelkeznek variáns függvénnyel és invariáns tulajdonsággal.) Mivel az implementációban az inicializáció és műveletek szerkezete hasonlít a klasszikus programozási nyelvekhez, ezért automatikusan lehet transzformálni a konkrét programozási nyelvekre (például Ada-ra, C\#-ra, Java-ra).

A legfelső és legalsó szintre megszorítások vannak. A specifikációban nem használható szekvencia és ciklus, viszont nagyon általános értékadások és adatszerkezetek állnak rendelkezésünkre. Az implementációban az ilyen általános értékadások nem megengedett eszközök. Az implementációban nem szerepelhet sem nemdeterminisztikus, sem párhuzamos értékadás, csak egy változónak konkrét értéket adó értékadás, azaz egy változónak értékül adhatunk egy másik változót, egy aritmetikai kifejezést vagy egy művelet visszatérési értékét. Az adatszerkezeteknek is konkrét adatszerkezeteknek kell lenniük. Emellett az implementáció tartalmazhat szekvenciákat, elágazásokat, ciklusokat. A specifikációra vonatkozó megszorítások biztosítják, hogy elég absztrakt módon fogalmazzuk meg a feladatot, a megvalósításra vonatkozó megszorítás pedig azt teszi lehetővé, hogy valóban le lehessen fordítani valamilyen konkrét programozási nyelvre a B nyelvű implementációt.

Egy absztrakt gép egy szintjét egy fájlba írjuk, és a gép egy komponensének nevezzük. A komponensek felépítése:

Specifikáció gépek leírása

Egy specifikációban meg kell adnunk a gép nevét és paramétereit (utóbbiak nem biztos, hogy vannak).
MACHINE gép_neve[(paraméternevek_felsorolása)] gép_törzse END

A gép_törzse különböző dolgokat tartalmazhat különböző dolgokat: invariánsokat, megszorításokat, műveleteket stb. Mindegyik ilyen dolgot egy kulcsszó vezet be. A következő lehetőségeink vannak (mindegyik egyszer szerepelhet egy absztrakt gépben):

Finomító gépek leírása

Egy finomító gép egy specifikációt vagy egy másik finomítást finomít. Egy finomító gép a következőképpen néz ki:

REFINEMENT finomító_gép_neve[(paraméternevek_felsorolása)] REFINES finomítandó_gép_neve gép_törzse END

A paraméterek meg kell feleljenek a finomatandó gép paramétereinek.

A gép_törzse a következőket tartalmazhatja:

Implementáció gépek leírása

Egy implementáció gép a következőképpen néz ki:

IMPLEMENTATION implementáció_gép_neve[(paraméternevek_felsorolása)] REFINES finomítandó_gép_neve gép_törzse END

A paraméterek meg kell feleljenek a finomatandó gép paramétereinek.

A gép_törzse a következőket tartalmazhatja:

Utasítások, vezérlési szerkezetek

Az utasítások - mint minden más is - géptípusonként mások és mások lehetnek. Alaputasítás az üres utasítás (skip;) és a blokkutasítás (BEGIN .... END).

Értékadás

Elágazás

Ciklusok

Lokális változók deklarációja implementáció gépeknél

Műveletek (alprogramok)

A lehetséges változatok:
OPERATIONS név= BEGIN Helyettesítések felsorolása END END

OPERATIONS név(paraméterek)= PRE Előfeltétel BEGIN Helyettesítések felsorolása END END

OPERATIONS visszatérésiérték<--név(paraméterek)= PRE Előfeltétel THEN Helyettesítések felsorolása visszatérésiérték:=E END END

Alapgépeknél így használhatóak fel, implementáció gépeknél a PRE előfeltételeket nem kell és nem is lehet megadni, a specifikáció gép szerint ellenőrzi őket, ugyanígy aszerint ellenőrzi a működést.

Komponensek

Az absztrakt gépek című részben már szerepeltek azok a fogalmak és nyelvi elemek, amiknek segíségével egy B model komponenseit megadjuk. Ebben a részben pontosítjuk, és részletezzük ezekt a fogalmakat és nyelvi elemeket. A B nyelv teljes egésszében a sepecifikáció hierarchikus leírására szolgál. A legfelső szint, amit absztrakt modelnek is nevezünk. Ezt a modelt, absztrakt gépet, finomítjuk lépésenként, ezek a finomított modelek. A finomítás során a specifikáció egyre konkrétabbá válik abban az értelemben is, hogy közelebb kerűl a szokásos programnyelvekhez. A finomítás legalsó szintje a megvalósítható, vagy implementációs model, amelyből automatikusan futtatható forráskód generálható. Egy feladat modelje több komponensből épül föl. Ezek között a gépek között különböző kapcsolatok lehetnek. Az absztrakt gép, a finomítások, beleértve a megvalósítható modelt is, egy feladat specifikációjának a különböző szintjei. Egy összetett feladat megoldására több különböző absztrakt modelből és finomításaiból álló rendszer alkalmas. Ennek a rendszernek a komponensei közötti kapcsolatok leírásával is foglakozunk a továbbiakban. Bár utalni fogunk a objektum elvű nyelvekhez kapcsolódó analógiákra, a B mint biztonság kritikus feladatok megoldására szolgáló eszköz, alapvetően nem objektum elvű. Például nincs öröklődés. Ez csökkenti a hatékonyságot, de növeli a megbízhatóságot.

Absztrakt gépek

Fejrész

Finomított modell

Megvalósítható modell

CONSTRAINTS elem

REFINES elem

IMPORTS elem

SEES elem

INCLUDES elem

PROMOTES elem

EXTENDS elem

USES elem

SETS elem

CONCRETE_CONSTANTS elem

ABSTRACT_CONSTANTS elem

VALUES elem

CONCRETE_VARIABLES elem

ABSTRACT_VARIABLES elem

INVARIANT elem

ASSERTIONS elem

INITIALISATION elem

OPERATIONS elem

LOCAL_OPERATIONS elem