Abstrakt. Metoder som ifrågasätter tillståndet i en datastruktur returnerar ofta identiska eller likvärdiga värden så länge som datastrukturen inte förändras. Programverifiering beror på detta faktum, men det har varit svårt att specificera och verifiera sådana likvärdiga resultat metoder och deras anropare. I detta dokument presenteras en kodning från vilken man kan bestämma likvärdiga resultat metoder för att vara deterministisk modulo ett användardefinierat ekvivalensförhållande. Den presenterar också en teknik för att kontrollera att en frågemetod returnerar likvärdiga resultat och se till att resultatet endast beror på en användardefinierad influence set. Tekniken är allmän, t.ex. den stöder användardefinierade ekvivalensrelationer baserade på Equals metoder och den stöder frågemetoder som returnerar nytilldelade objekt. I dokumentet diskuteras också implementeringen av tekniken i samband med Spec# statiska programkontrollanten. Datorprogram innehåller många metoder som ifrågasätter tillståndet i en datastruktur och returnerar ett värde baserat på detta tillstånd. Så länge datastrukturen är oförändrad förväntar man sig olika anspelningar på frågemetoden för att producera likvärdiga returvärden. För metoder som returnerar skalärvärden förväntas avkastningsvärdena vara desamma. För metoder som returnerar objektreferenser är de mest intressanta ekvivalenserna referensjämlikhet och ekvivalens baserat på Equals-metoden. Ett enkelt och vanligt exempel på en frågemetod är grevmetoden för en samlingsklass, som List in Fig. 0, där för en viss samling metoden returnerar antalet element som lagras i samlingen. Uppenbarligen förväntar man sig att greven returnerar identiska värden när de kallas två gånger på samma samling. Ett annat exempel visas i kalenderklassen i bild. 2, Där anrop av GetEarliestAppointment kommer att ge likvärdiga resultat så länge tillståndet i kalendern inte ändras. Men eftersom GetEarliestAppointment returnerar ett nytilldelat objekt kommer resultaten inte att vara identiska. På grund av objektallokering kan frågemetoder inte förväntas vara deterministiska. Deras resultat förväntas dock vara likvärdiga. Därför kommer vi att hänvisa till sådana frågemetoder som likvärdiga resultatmetoder. Frågemetoder (även kallade rena metoder) är särskilt viktiga i påståendespråk som JML [15] eller Spec# [1] eftersom de gör det möjligt att uttrycka påståenden på ett abstrakt, implementationsoberoende sätt. Till exempel, Count används i förutsättningen för GetItem (Fig. 0) Att hänvisa till antalet element i förteckningen utan att lämna några närmare uppgifter om genomförandet. Det är dock svårt att resonera om påståenden som innehåller frågemetoder. Kundprogrammet i Bild. 1 illustrerar problemet. Den använder en
Lyckligtvis har detta fall endast inträffat för fastighetssamlare vars kropp returnerar ett nytilldelat objekt (se REF för en teknik som gör det möjligt att betrakta sådana metoder som observationsmässigt rena).
Verification of Equivalent-Results Methods
{'venue': 'ESOP', 'journal': None, 'mag_field_of_study': ['Computer Science']}