Boolska uttryck
5.1 Tillståndsbaserade specifikationer
Specifikationer baserade på tillstånd beskriver programvarusystem i termer av tillstånd och effekter av operationer på tillstånd. Sådana specifikationer stöds av flera specifikationsspråk, som vi grupperat i två uppsättningar: klassiska specifikationsspråk, t.ex. Z , B och VDM , och assertionsspråk, t.ex. Eiffel , JML (Java Modeling Language) och Peters och Parnas’ tabeller . Medan klassiska specifikationsspråk definierar tillstånd och övergångar oberoende av genomförandet, anger assertionsspråk tillstånd och övergångar som uttalanden eller anteckningar i källprogrammet.
Specifikationer baserade på tillstånd används som testorakel genom att verifiera att testutförandena överensstämmer med specifikationerna. Huvudproblemet med att generera testorakel från tillståndsbaserade specifikationer beror på de olika abstraktionsnivåerna mellan specifikationerna och de operationer som övervakas under testutförandet, vilket innebär att specifikationerna för operationerna kommer att översättas till en kontrollerbar form. Specifikationsspråken är vanligtvis tillräckligt uttrycksfulla för att representera olika datastrukturer och tillståndsbaserade egenskaper, men deras uttrycksfullhet försvårar översättningen till körbar form. Ofta gör översättningen vissa förenklande antaganden, som att begränsa oändliga mängder, till exempel den oändliga mängden naturliga tal, och att hantera icke-exekverbara element endast delvis och ibland kräva ett visst mänskligt ingripande.
Här diskuterar vi de viktigaste tillvägagångssätten för att översätta tillståndsbaserade specifikationer till en exekverbar form. Översättningen av Z-, B- och VDM-specifikationer innebär samma problem med oändliga datastrukturer, delvis definierade uttryck och objektorienterade strukturer. Översättningen av Eiffel, JML och andra assertionsspråk till kontrollerbar form innebär liknande problem men på en annan abstraktionsnivå. Nedan presenteras de viktigaste metoderna för att översätta tillståndsbaserade specifikationer till kontrollerbar form med hänvisning till Z. Metoderna för andra språk är likartade. Därefter diskuterar vi problemen med att kompilera påståenden till kontrollerbar form med hänvisning till Eiffel, JML och Peters och Parnas tabeller.
Den schemapredikatkompilator som föreslagits av Mikk kompilerar Z-specifikationer till C-kod. För varje Z-schema, som är den grundläggande enheten i Z, genererar metoden en C-funktion som utvärderar schemapredikaten med hjälp av det programtillstånd som överlämnats till funktionen som en parameter. Den genererade koden utvärderar schemats predikat med en ”brute force”-strategi: Med ett tillstånd ersätter koden i huvudsak uttryck med deras värden, utvärderar formler i propositionell kalkyl med hjälp av sanningstabeller och utvärderar kvantifieringar och mängdkonstruktioner genom att iterera genom datastrukturerna. För att minska komplexiteten hos de genererade C-funktionerna föreslås ett optimeringssteg för att se till att den genererade C-koden alltid avslutas. För att optimera koden definierar tekniken en ”körbar” delmängd av Z-språket. Delmängden består av ändliga predikat, t.ex. formler för propositionell kalkyl, kvantifieringar över ändliga mängder och mängdkonstruktioner baserade på ändlig iteration. Tekniken utökar uppsättningen exekverbara predikat med en uppsättning regler för att omvandla särskilda icke-exekverbara predikat som uppfyller vissa villkor till exekverbara predikat utan att ändra deras semantik. Följande två regler eliminerar till exempel kvantifieringarna:
varvid M är en mängd, variabeln x representerar ett element i M och P är ett predikat. Operatören -, även känd som ”Z-notationsfläck”, betyder ”så att” när den används med kvantifieringen ∃ och ”att,” när den används med kvantifieringen ∀. Till exempel betyder ∃ x : M – P att det finns minst ett värde x i M så att predikatet P är sant. Villkoret NotOccur(x, P) anger att x inte är en fri variabel i predikatet P. Även om mängden M kan vara oändlig kan kompilatorn ändå kompilera specifikationer som använder kvantifierare över M så länge kvantifierarna kan elimineras genom att tillämpa ovanstående regler. För användardefinierade funktioner som kan införas genom axiomatiska eller generiska definitioner kräver kompilatorn att användaren tillhandahåller motsvarande kod. Mikk föreslår också en lösning på problemet med delvis definierade specifikationer. Han använder VDM-SL som en mellanform och VDM-SL-kompilatorn som utvecklats av Schmidt och Hörcher för att översätta Z-specifikationer till C-kod . När det gäller delvis definierade uttryck, dvs. antingen funktioner eller relationer som kan utvärderas odefinierat (betecknas ⊥) när de utvärderas utanför sitt definitionsområde, genererar metoden undantagshanterare.
Objektorienterade utvidgningar av Z, som Object-Z, förvärrar problemen. McDonald et al. översätter Ojbect-Z-specifikationer av containerklasser till C++-kod i tre steg: optimering, strukturell mappning och predikatöversättning . I optimeringsfasen omorganiserar de specifikationen för att förenkla den efterföljande översättningen genom flera steg, bland annat genom att ersätta konstanta variabler med deras värden och ta bort sekundära variabler och schemaberikningar. I det strukturella kartläggningsskedet kartlägger de strukturer i Object-Z-specifikationen till motsvarande kodelement: Specifikationens konstanter och variabler till variabler med korrekta initialiseringar och variabeltyper till primitiva C++-typer eller motsvarande klasser i Z-verktygslådans bibliotek som används av tekniken. Till exempel mappar de heltals- och boolska typer till int, och typen av heltalsuppsättningar till z_set<int >. De mappar initialiseringsschemat till en konstruktör och operationsscheman till medlemsfunktioner, skapar en särskild medlemsfunktion, inv(), för att kontrollera klassens invariant och genererar en undantagsklass för varje undantagsschema.
I översättningen av predikatet DeepL fokuserar tekniken på hur man genererar kod för att kontrollera programtillståndet, istället för att utvärdera predikat. Översättningen förhindrar till exempel att funktionen inv() anropar någon annan medlemsfunktion för att undvika oändlig rekursion. I en konstruktör kontrolleras klassens invariant när den avslutas.
Richardson et al. fokuserar på tidskritiska system, hanterar en kombination av Z- och temporal intervalllogik och föreslår en översättning av specifikationer till testorakel med hjälp av symbolisk tolkning. Symbolisk tolkning tilldelar de symboliska namnen i specifikationerna till stimulusingångarna och de initiala tillståndsvariablerna genom att hänvisa till data- och kontrollmappningar. Därefter tolkar symbolisk tolkning varje kontrollväg i specifikationerna, dvs. den skapar ett påstående som uttrycker villkoret för specifikationsdata baserat på det symboliska tillståndet vid varje kontrollpunkt i specifikationen. En specifikationskontrollpunkt är ett relevant element, t.ex. en parameteriserad händelse, en övergång och en operation. Efter den symboliska tolkningen av Z-specifikationen representeras orakelinformationen som en lista över relevanta Z-scheman och deras motsvarande påståenden, som kontrolleras om schemat åberopas. Utförandet av ett testfall hänvisar till en konkret testinmatning från vilken konkreta variabler och händelser är bundna till sina motsvarigheter i testklassen (varje testklass är en partition av testinmatningen). Genom utförandet av testfallet produceras en utförandeprofil, och de konkreta händelser och värden på variabler som ingår i utförandeprofilen mappas till orakelnivån för att kontrollera deras överensstämmelse med orakelinformationen.
Assestionsspråk sammanfogar specifikationerna med källkoden, vilket förenklar men inte eliminerar översättningsproblemet. Assertioner stöds av olika språk och metoder. Design by contract är ett paradigm för programvarudesign där man förutsätter en gemensam design av kod och påståenden. Design by contract föreslogs av Meyer och stöds fullt ut av programmeringsspråket Eiffel . Till skillnad från allmänna specifikationsspråk, som Z, är specifikationerna i Eiffel, som kallas kontrakt, inlagda i källkoden och definierar skyldigheter och fördelar för de programvarukomponenter som kommunicerar via väl utformade gränssnitt. I språk som stöder kontrakt uttrycks klientens skyldigheter och fördelar som för- och eftervillkor för tjänsteleverantörerna. Källkoden berikas med invarianter som representerar tillståndsegenskaper som måste gälla under varje interaktion.
Kontrakt har utvidgats till många språk. iContract har varit det första verktyget som stöder kontrakt i Java . I iContract skrivs kontrakt som kodkommentarer med särskilda taggar. De kontrakt som stöds av iContract är boolska uttryck som överensstämmer med Javas syntax, med undantag för några få syntaktiska utvidgningar som inkluderar den universella kvantifieringen (∀), den existentiella kvantifieringen (∃) och implikationen (→). Dessa utvidgningar är utformade för att förenkla översättningen till Javakod. Till exempel, the syntax of ∀ is forall < Class >< var > in < Enum >< Exp_var >, where < Class > is the type of the variable < var >, which represents an element of < Enum >. A reasonable translation of the ∀ expression is to use a Java loop to iterate over the enumeration < Enum > and evaluate the boolean expression < Exp_var > in each iteration. The existential quantification is translated similarly. An implication expression C implies I can be simply translated into an if statement: ”Förutom den enkla översättningen av booleska uttryck tar iContract upp frågor som rör objektens livscykel, variablers räckvidd och arv, varav de flesta är specifika för objektorienterad programmering. De viktigaste reglerna som rör objektens livscykel är följande:
I en objektkonstruktion måste förutsättningarna kontrolleras i början av konstruktionen, medan invarianterna och eftervillkoren kontrolleras endast om konstruktionen avslutas normalt (utan undantag).
För normala metodinvokationer på objekt kontrolleras för- och eftervillkoren vid inmatning och utmatning av de åberopade metoderna och invarianter kontrolleras inte för privata metoder.
Inför destruktion av objekt krävs ingen kontroll. Därför införs ingen kontrollkod i finalize()-metoderna.
De predikat som används i eftervillkoren hänvisar ofta både till metodens returvärde och till det ”gamla” värdet (eller ”ingångsvärdet”) för vissa variabler. iContract skapar en pseudovariabel, kallad return, för att representera returvärdet, lagrar variabelvärdena vid ingången och gör dem åtkomliga som variabelnamn med postfixet @pre. Detta kan leda till potentiella oändliga rekursioner vid kontroll av invarianter. För att lösa detta problem håller iContract reda på rekursionsdjupet för varje objekt inom varje tråd och kontrollerar endast invarianter med djup 0. Typutvidgningsmekanismerna i Java har flera implikationer på hur kontrakt för typerna bör hanteras. iContract propagerar kontrakt genom att följa dessa regler:
Invarianter konjunkteras, det vill säga, invariant för en undertyp är konjunktionen av invarianterna för alla dess supertyper.
Postconditions are conjuncted, that is, the postcondition of a subtype is the conjunction of the postconditions of all its supertypes.
Preconditions are disjuncted, that is, the precondition of a subtype is the disjunction of the preconditions of all its supertypes.
JML är ett populärt språk för beteendespecifikation som stödjer Design by Contract i Java . JML-kontrakt har formen av särskilda kommentarer i Java. JML uttrycker förutsättningar, eftervillkor och invarianter som boolska uttryck som föregås av nyckelorden requires, ensures respektive invariant, och använder den inbyggda metoden \ old(x) för att representera värdet av x före en operation. I likhet med ▵-notationen i Z tillhandahåller JML nyckelordet modifies för att ange de variabler som ändras i en metodkropp. Dessutom behandlar JML flera objektorienterade egenskaper, t.ex. synlighet och arv.
JML ligger till grund för många metoder för generering av testorakel. Bhorkar föreslog en teknik för att översätta JML-kontrakt till Java-säkringar . Även om tekniken endast stöder preconditions, tar den upp frågor som rör specifikationsvariabler, förfining, specifikationsarv och sekretess. I likhet med iContract hanterar tekniken arv av kontrakt genom att konjunktera och disjunktera kontrakten i enlighet med deras typer. Tekniken använder också en hashtabell (per tråd) för att undvika rekursioner i körtidskontrollen. Uttryck som använder kvantifierare betraktas som icke-utförbara av tekniken, och ingen Javakod genereras för sådana uttryck.
Korat föreslog en teknik för att generera både testfall och orakel från JML-specifikationer . Korats teknik genererar testfall från förutsättningar och invarianter och orakel från eftervillkor och invarianter. Araujo et al. utökade JML genom att lägga till samtidiga kontrakt och föreslog ett runtime-stöd för att möjliggöra runtime-kontroll av påståenden som specificerar samtidiga egenskaper.
Peters och Parnas introducerade ett tillvägagångssätt för att generera testorakler från formell dokumentation . Dokumentationen ges i en tabellform som består av relationer som specificerar förfarandets gränssnitt och översätts till orakel i C- och C++-kod. Kärnan i den formella dokumentationen består av predikatuttryck skrivna i en variant av predikatlogik med särskilda konstruktioner för att hantera partiella funktioner. I likhet med andra specifikationsbaserade orakeltekniker behandlar denna teknik kvantifierare genom att begränsa dem till ändliga mängder.
För att möjliggöra iterationer över mängder av element med kvantifierare inför Peters och Parnas induktivt definierade predikat. För en mängd S (som ska användas i kvantifieringar) definieras ett induktivt definierat predikat P med tre element I, G och Q. Den ursprungliga mängden I innehåller ett ändligt antal element, G är en funktion, kallad ”generatorfunktion”, som genererar elementen i mängden och Q är ett predikat som karakteriserar egenskaperna hos mängden. Mängden S definieras som den minsta mängd som konstrueras i de induktiva stegen nedan:
S0 = I
Sn + 1 = Sn ∪ {G(x)|x ∈ Sn ∧ Q(x)}
I, G och Q måste definieras så att de uppfyller ett särskilt villkor som säkerställer att den konstruerade mängden S är ändlig.
Peters och Parnas föreslår ett tillvägagångssätt för att översätta tabelldokumentation till C-kod. Eftersom formen för de uttryck som används i dokumentationen är väldefinierad sker översättningen systematiskt.
Andra tillståndsbaserade specifikationer används också för att härleda testorakel. UML-modeller är i allmänhet informella, men Bouquet et al. har ändå definierat en delmängd av UML 2.1, kallad UML-MBT, som är tillräckligt exakt för att automatiskt generera testfall. UML-MBT innehåller klassdiagram, tillståndsmaskiner och en delmängd av OCL 2.0. Bouquet et al. använder specifikationer som är skrivna i VDM-SL för att generera testorakel.