Típus-tesztelés

A feladat

Adott a lista modulja: a helyes Pascal unit-implementációja.
Végezze el a helyességvizsgálatot úgy, hogy a tanult lista-axiómák teljesülését vizsgáló programot megírja!
A helyességet vizsgáló program „filozófiáját” később olvashatja.

Vegye sorra az axiómákat, készítse el a Lista unit olyan hibás változatait, amelyekben éppen az adott axiómában előforduló műveletek hibásak!

 Type
   TElem  = String;
   Mut    = ^TlistaElem;
   TListaElem= Record
                 szoveg :TElem;
                 kov,elo:Mut
               End;
   TLista = Record
              fej,akt:Mut;
              hiba   :Boolean;
              db     :Integer;
            End;

 Const UresLista:TLista = (fej:Nil; akt:Nil; hiba:False; db:0);

 Const UresLista:TLista = (fej:Nil; akt:Nil; hiba:False; {db:0});

 //a unit elején, a tesztelés kedvéért létrehozott „konstans”:
 Var falsElem:TListaElem=(szoveg:'';kov:Nil;elo:Nil);
 Const UresLista:TLista = (fej:@falsElem; akt:Nil; hiba:False; db:0);

Tehát egy tesztelő program írandó meg. Ezt összeszerkeszti egy-egy próbaként elrontott unit-változattal, és futtatja.
Azt figyeli árgus szemekkel, hogy a unitba beletett hibákra hogyan reagál: kimutatja-e hibákat.

A megoldáshoz

Az axiómákban, ill. a unitban szereplő fogalmak (azonosítók) némileg különböznek, ezért megadom az egymáshoz rendelésüket:

A tesztelő program „filozófiája”:

1. Mindenek előtt lássa, milyen egyszerű dologra kell gondolni: töltse le, és indítsa el!
2. Minden vizsgált axiómát egy függvény teszteli: visszaadja annak a kérdésnek a logikai értékét, hogy teljesül-e az adott axióma.
   A függvény szerkezete az alábbi:

    Function Axioma_x:Boolean;//az x. axióma
    //... az axióma rövid, formális leírása ...
      Var
        l:TLista;//a szükséges lista(k)
        e:TElem;//a szükséges elem(ek)
        h:Integer;//a szükséges hossz(ak)
    Begin
      ... a tesztelés ...
      Axioma_x:=... a tesztelés eredménye ...;
    End;

   Példa

   Az 1. axióma (l=Üres → Üres?(l)) tesztelésére az alábbi függvény alkalmas lehet:

    Function Axioma_1:Boolean;//implikáció
    //l=Üres -> Üres?(l)
      Var
        l:TLista;
    Begin
      l:=UresLista;//garantáljuk az implikáció bal oldalának a teljesülését:
                   //létrehozunk l-ben egy üres listát
      Axioma_1:=UresE(l) and (l.hiba=False);//előállítjuk a jobb oldal logikai értékét
                                            //(és ez lesz a függvény értéke, hiszen 
                                            //IMPLIKÁCIÓról van szó!)
    End;

   A példában látszik, hogy az axióma-tesztelő függvényben csak azon lista-műveletek fordulnak elő, amelyek az axiómában.
   Továbbá a lista reprezentációjához közvetlenül nyúltunk. Igaz nagy-nagy megfontoltsággal, hogy véletlenül se okozzunk hibát!


3. Az axiómák egymástól függetlenek, tehát minden szükséges adatot, adatszerkezetet, amelyet használnak az egyes függvények, lokálisan kell deklarálni és létrehozni.


4. Hogy egységesítsük és leegyszerűsítsük a főprogramot, használja az alábbi kiíró eljárást:

    Procedure Ellenorzes(Const ax:Integer {az axióma azonosításához kell};
                         Const l:Boolean {az axióma teljesülésének logikai értéke});
      Const //hogy magyarul jelenjen meg a logikai érték:
        Igaz_Hamis:Array [Boolean] of String=('Hamis','Igaz');
    Begin
      Writeln('A(z) ',ax,'. axióma teljesül? = ',Igaz_Hamis[l]);
    End;

   Az első paramétere az axióma sorszáma, a második az axióma teljesülésének igazságtartalma.


5. Így a főprogram kb. az alábbi:

    Begin
      UjLap(cim);
      Ellenorzes(1,Axioma_1);
      Ellenorzes(2,Axioma_2);
      Ellenorzes(3,Axioma_3);
      Ellenorzes(5,Axioma_5);
      //...
      BillreVar;
    End.

6. Egy hiba-axióma esetén az axióma akkor teljesül, ha pontosan akkor kerül hiba-állapotban a lista, amikor az axióma NemDef-et ír elő!


7. Az igazságtartalmat egy nem hiba-axióma esetében is befolyásolja a hiba-állapot. Az axióma nem teljesülhet, ha a tesztelés során Igaz hiba-állapotba jutott az érintett lista!
   Tehát ne felejtse el ezt is figyelembe venni az igazságtartalom megadásánál! (L. a fenti példában a kékkel jelölt részt!)


8. Az adott axióma teszteléshez „le kell gyártani” egy vagy több listát. Ezt kétféle koncepció szerint végezheti.
   i) A felhasználja a lista unitbeli konstruktor műveleteket,
   ii) vagy csak azon műveletekkel operál, amelyek az adott axiómában szerephez jutnak.
   Az i)-t könnyebb programozni, de nehezebb az általa kapott eredményt értékelni, hiszen az eredménybe belejátszanak az éppen nem vizsgált konstruktor műveletek esetleges hibái is. Az ii) programozása időnként ügyeskedést kíván, de a kapott eredmény tisztább. Persze ügyelni kell, hogy az „ügyeskedés” programozási szempontból hibamentes legyen.
   
   
   1. Tekintsünk egy példát!
      Példa

      A 2. axióma (Üres?(l) ↔ Hossz(l)=0) esetében az ekvivalencia miatt két dolog teljesülését ellenőrizük:
      A) Üres?(l) → (Hossz(l)=0) és
      B) ¬Üres?(l) → (Hossz(l)≠0)
      Az A) a korábbi fenti példához hasonlóan megoldható. A B)-hez viszont elő kell állítani a lista egy nem 0 elemű állapotát. Ezt az állapotot a listába elemet betevő műveletekkel érjük el. (Mégpedig mindkét „filozófiájával”. Vitatható?!?)
      

       Function Axioma_2:Boolean;//Ekvivalencia
       //Üres?(l) <-> ElemSzám(l)=0
         Var
           l:TLista;
           bA,bB:Boolean;//a fenti A) és B) eset logikai értéke
       Begin
         //bA := ( üres-lista -> 0 eleme van ):
         l:=UresLista; 
         bA:=UresE(l) and (Hossz(l)=0) and not HibasE(l);
         //bB := ( nem üres-lista -> 0< eleme van ):
         ///a nem üres listát a Beilleszt-tel létrehozva:
         l:=UresLista; 
         Beilleszt(l,'1'); bB:=not UresE(l) and (Hossz(l)>0) and not HibasE(l);
         ///a nem üres listát a BeillesztEle-vel létrehozva:
         l:=UresLista; 
         BeillesztEle(l,'1'); bB:=bB and not UresE(l) and (Hossz(l)>0);
         Axioma_2:=bA and bB;
       End;

      
      
   2. Itt a célt kell szem előtt tartani, hogy az axiómában szereplő műveleteknek (és csak azoknak) az együttműködését vizsgáljuk!
      Így minden –egyébként „elvtelennek” minősülő– módosítása az adatszerkezetnek megengedett! Nyúlhatunk, sőt alighanem nyúlnunk kell a reprezentációhoz, hiszen csak így kerülhetők el az axiómában éppen nem szereplő (konstrukciós) műveletek.
      E ritka esetben egyetértőleg idézem: „a cél szentesíti az eszközt!”
      
      Példa

      A 2. axióma (Üres?(l) ↔ Hossz(l)=0) esetében az ekvivalencia miatt két dolog teljesülését kell ellenőrizni:
      A) Üres?(l) = (Hossz(l)=0) és
      B) ¬Üres?(l) = (Hossz(l)≠0)
      Az A) a korábbi fenti példához hasonlóan megoldható. A B)-hez viszont elő kell állítani a lista egy nem 0 elemű állapotát. Ezt az állapotot azonban nem lehet a listába elemet betevő műveletekkel elérni, mert azok esetleg hibásak, és így az axióma igazságtartalma nem a benne előfordulók miatt lesz hamis.
      Ekkor a kívánt nem „üres” állapotot „direkt” módon érjük el, pl. ahogy feljebb a fals elem bevezetésével tettük. Fontos, hogy a „direkt” módon kapott kód egyszerű, garantáltan hibamantes legyen! Hiszen csak hibátlan tesztelő programmal mutathatunk ki valódi hibákat.
      

       Function Axioma_2:Boolean;//Ekvivalencia
       //Üres?(l) <-> ElemSzám(l)=0
         Var
           l1,l2:TLista;
       Begin
         //az A)-hoz:
         l1:=UresLista;
         //a B)-hez:
         l2.fej:=... valami nem Nil érték ...; //pl. falsElem
         l2.akt:=l2.fej;
         l2.db:=1;
         l2.hiba:=False;
         Axioma_2:=UresE(l1)=(Hossz(l1)=0) and (l1.hiba=False) {A)-hoz} and
                   (not UresE(l2))=(Hossz(l2)<>0) and (l2.hiba=False) {B)-hez};
       End;

      Persze világos, hogy így is jó (és egyszerűbb):

         ...	
         Axioma_2:=... and
                   UresE(l2)=(Hossz(l2)=0) {B)-hez};//miért nem kell az 
                                                    //'and (l2.hiba=False)'?

Kiindulópontként ajánlom: Lista_Teszt_Unitok.zip. Tartalma:

A unitok első sorában található sorszámok megadják, hogy mely sorok lettek elrontva.

Világos, hogy a fenti „módszer” nem nyújt abszolút biztonságot a hibák kimutatása terén.
Annyit jelenthetünk csak ki –hibátlan tesztelő program esetén–, hogy amelyik axióma hibásnak mutatkozik, az abban szereplő műveletek legalább egyike hibás.

Gondolkodjon el azon, hogy preparálható-e olyan hibás kódú Lista unit, amelyben egyes hibák az Ön által elkészített tesztelő program számára kimutatlanok maradnak? Mutasson ilyeneket, ha van!

Házi feladat

Készítsen a fenti elveken alapuló tesztelő programot egy saját, típus-konstrukciót megvalósító Pascal unithoz!
Akár választhatja a vermet vagy a sort is. Nem ragaszkodom a láncolt ábrázoláshoz sem.
Az axiómáit megtalálja itt: verem, sor.