10.IldebuggingdiastrazioniAA2016-2017

1

Astrazionisuida3:specifica

  Ingredien33picidiunaastrazionesuida3  Uninsiemediastrazioniproceduralichedefinisconotu?imodiperu3lizzareuninsiemedivalorio  Creareo  Manipolareo  Osservare

  CreatorieproduDori:meccanismiprimi3via?allaprogrammazionedelladefinizionedinuovivalori

  Mutator:modificanoilvalore(manonhannoeffeDosu==,nonoperanopereffe?laterali)

  Osservatori:strumentolinguis3coperselezionarevalori

2

Implementazionevs.Specifica

Representa)onInvariant:Object→booleano  Stabilisceseunaistanzaèbenformatao  Stabiliscel’insiemeconcretodeivaloridell’astrazione(ovveroquelli

chesonounaimplementazionedeivaloriastra?)o  Guidaperchiimplementa/modifica/verifical’implementazionedelle

astrazioni:nessunogge@odeveviolarerepinvariantAbstrac)onFunc)on:Object→abstractvalue

o  StabiliscecomeinterpretarelastruDurada3concretadellaimplementazione

o  ÈdefinitasolamentesuivaloricherispeDanol’invariantedirappresentazione

o  Guidaperchiimplementa/modifical’astrazione:ognioperazionedevefare“lacosagiusta”conlarappresentazioneconcreta

3

Esempio:CharSet

// Overview: CharSet insieme finito modificabile di // Characters

// @effects: crea un CharSet nuovo e vuoto public CharSet( ) {...}

// @modifies: this // @effects: thispost = thispre U {c} public void insert(Character c) {...}

// @modifies: this // @effects: thispost = thispre \ {c} public void delete(Character c) {...}

// @effects: return (c ∈ this) public boolean member(Character c) {...}

// @effects: return cardinalita’ di this (this.size( )) public int size( ) {...}

4

CharSet:implementazione?

class CharSet { private List<Character> elts =

new ArrayList<Character>( );

public void insert(Character c) { if (elts.add(c)){return;}

} public void delete(Character c) {

int i = elts.indexOf(c); if (i > -1) elst.remove(i); } public boolean member(Character c) {

return elts.contains(c); } public int size( ) {

return elts.size( ); } }

5

CharSet:implementazione?

class CharSet { private List<Character> elts =

new ArrayList<Character>( );

public void insert(Character c) { if (elts.add(c)){return;}

} public void delete(Character c) {

int i = elts.indexOf(c); if (i > -1) elst.remove(i); } public boolean member(Character c) {

return elts.contains(c); } public int size( ) {

return elts.size( ); } }

6

Doveènascostol’errore?

class CharSet { private List<Character> elts =

new ArrayList<Character>( );

public void insert(Character c) { if (elts.add(c)){return;}

} public void delete(Character c) {

int i = elts.indexOf(c); if (i > -1) elst.remove(i); } public boolean member(Character c) {

return elts.contains(c); } public int size( ) {

return elts.size( ); } }

7

CharSet s = new CharSet( ); Character a = new Character('a'); s.insert(a); s.insert(a); s.delete(a); if (s.member(a)) System.out.print("wrong"); else System.out.print("right");

CharSet:implementazione?

class CharSet { private List<Character> elts =

new ArrayList<Character>( );

public void insert(Character c) { if (elts.add(c)){return;}

} public void delete(Character c) {

int i = elts.indexOf(c); if (i > -1) elst.remove(i); } public boolean member(Character c) {

return elts.contains(c); } public int size( ) {

return elts.size( ); } }

8

Doveènascostol’errore?

CharSet s = new CharSet( ); Character a = new Character('a'); s.insert(a); s.insert(a); s.delete(a); if (s.member(a)) System.out.print("wrong"); else System.out.print("right");

CharSet:implementazione?

Cerchiamol’errore

  Primotenta5vo:deleteèsbagliatao  controllal’appartenenzamarimuovetuDeleoccorrenze?

  Secondotenta5vo:insertèsbagliatao  nondovrebbeinserireuncaraDerequandoègiàpresente

  Comeoperiamo?o  u3lizziamorepresenta3oninvariantpermuovercieeliminarel’erroreo  ilcodicebendocumentatoeglistrumen3dispecificaformaleci

aiutanonell’operazionediindividuazioneerimozionedell’errore

9

Invariantedirappresentazione  class CharSet { // Rep invariant: // elts non contiene elementi null e non // contiene duplicati private List<Character> elts = ... ...

Possiamoscriverloancheformalmente(conglistrumen3diLPP): ∀ indice i di elts . elts.elementAt(i) ≠ null ∀ indice i, j di elts . i ≠ j ⇒ ¬ elts.elementAt(i).equals(elts.elementAt(j)) Notare che ArrayList ammette null !!!

10

Oralocalizziamol’errore

// Rep invariant: // elts: no null e no duplicati public void insert(Character c) { if (elts.add(c)){return;}

} public void delete(Character c) { int i = elts.indexOf(c);

if (i > -1) elst.remove(c); }

11

Comesifaildebugging

L’ideacheintendiamoperseguireèlaseguente:

Proge:atedelcodiceinmodotalechetu:eleoperazionidi“bug-checking”sianoimplementateu5lizzandocomeguidal’invariantedi

rappresentazione

12

Verificadelrepinvariant

Ideaderivatadalletecnichediprova:controllareingressoeuscitadaimetodi

public void delete(Character c) { checkRep( ); // alternativa: invocare repOK( )

int i = elts.indexOf(c); if (i > -1) elst.remove(c); // Come garantire che venga sempre invocata? // (usiamo un blocco finally) checkRep( ); } ... /** elts no duplicati. */ private void checkRep( ) { ... }

13

defensiveprogramming

  Assunzione:programmareèunprocessodi3po“trialanderror”

  ProgeDaredelcodiceinmodotalecheo  allachiamatadeimetodi

! verificarepinvariant! verificapre-condizioni

o  all’uscitadelmetodo! verificarepinvariant! verificapost-condizioni

  Verificarerepinvariant=verificarelapresenzadierrori

  Ragionaresulrepinvariant=evitaredifareerrori

14

SempreCharSet

AggiungiamounmetodoaCharSet

// restituisce una lista degli elementi che // appartengono a this. public List<Character> getElts( );

Implementazione

// Rep invariant: elts no null e no dupl. public List<Character> getElts( ) { return elts; }

L’implementazionedigetEltspreservarepinvariant?

Mah?!….

15

Esporrelarappresentazione

Consideriamouncliente(semprediCharSet)CharSet s = new CharSet( ); Character a = new Character('a'); s.insert(a); s.getElts( ).add(a); // usiamo add in modo liberale s.delete(a); if (s.member(a)) ...

 AbbiamounaesposizionedellarappresentazioneconunaccessoindireDo(tramiteilmetodogetElts)

 Problema:bugdaevitareo  progeDarel’astrazioneinmododaevitarequestoproblemao  progeDaredeitestconclien3“malevoli”:usarevalorimutabilipercapire

cosaavvieneneldeDaglio

16

Comesievita?

  Perevitarel’esposizionedellarappresentazioneunaprimatecnicaèquelladifarecopiedeida3cheoltepassonolabarrieradell’astrazioneo  copiain[parametrichediventanovaloridellarappresentazione]o  copiaout[risulta3chesonopartedell’implementazione]

  Esempio:PointADTmodificabile

class Line { private Point s, e; public Line(Point s, Point e) { this.s = new Point(s.x,s.y); this.e = new Point(e.x,e.y); } public Point getStart( ) { return new Point(this.s.x,this.s.y); } ...

}

17

deepcopying

Unacopiashallow(operazionisuipuntatori)nonèsufficienteacausadell’aliasing!!!

Analizzarequestocodiceclass PointSet { private List<Point> points = ...

public List<Point> getElts( ) { return new ArrayList<Point>(points);

} }

18

Unasecondasoluzione

  UsarestruDureda3nonmodificabili

  Esempio:Point(nonmodificabile) class Line { private Point s, e; public Line(Point s, Point e) {

this.s = s; this.e = e;

} public Point getStart( ) {

return this.s; } ...

19

StruDurenonmodificabili

  Vantaggio  l’aliasingnonèunproblemao  nonènecessariofarecopieo  repinvariantnonpuòessere“roDo”

  RichiedetuDaviasceltediprogrammazionedifferen3void raiseLine(double deltaY) { this.s = new Point(s.x, s.y+deltaY); this.e = new Point(e.x, e.y+deltaY);

}

  Classiimmutabilinellalibreria:String,Character,Integer,...

20

AncorailcasogetElts

class CharSet { // rep invariant: elts: no null e no dupl. private List<Character> elts = ...

// returns: elts nell’insieme corrente public List<Character> getElts( ) {

return new ArrayList<Character>(elts); //copy out } ... }

21

Alterna3ve

// returns: ... public List<Character> getElts( ) { // versione 1 return new ArrayList<Character>(elts); //copy out! }

public List<Character> getElts( ) { // versione 2 return Collections.unmodifiableList<Character>(elts); }

JavaDoc:Collections.unmodifiableList:Returnsanunmodifiableviewofthespecifiedlist.Thismethodallowsmodulestoprovideuserswith"read-only"accesstointernallists.Queryopera5onsonthereturnedlist"readthrough"tothespecifiedlist,anda:emptstomodifythereturnedlist…resultinanUnsupportedOperationException.

22

Somegoodnews

public List<Character> getElts( ) { // versione 2 return Collections.unmodifiableList<Character>(elts); }

o iclien3nonpossonospezzareilrepinvarianto selalistaèdidimensionielevateèpiùefficientedellatecnicadelcopyouto siusanolibreriestandard(sempreunabuonacosa)

23

Somebadnews

public List<Character> getElts( ) { // versione 1 return new ArrayList<Character>(elts);//copy out! }

public List<Character> getElts( ) { // versione 2 return Collections.unmodifiableList<Character>(elts); }Ledueimplementazionisonodifferen3!!!

o entrambepermeDonodievitaredirompereilrepinvarianto entramberes3tuisconounalistadielemen3

Ma... xs = s.getElts( ); s.insert('a'); xs.contains('a');

Laversione2permeDediosservarelarappresentazione!!

24

Implementazionevs.Specifica

Representa)onInvariant:Object→booleano  Stabilisceseunaistanzaèbenformatao  Stabiliscel’insiemeconcretodeivaloridell’astrazione(ovveroquelli

chesonounaimplementazionedeivaloriastra?)o  Guidaperchiimplementa/modifica/verifical’implementazionedelle

astrazioni:nessunogge@odeveviolare

Abstrac)onFunc)on:Object→abstractvalueo  StabiliscecomeinterpretarelastruDurada3concretadella

implementazioneo  ÈdefinitasolamentesuivaloricherispeDanol’invariantedi

rappresentazioneo  Guidaperchiimplementa/modifical’astrazione:ognioperazione

devefare“lacosagiusta”conlarappresentazioneconcreta

25

Repinv.vincolalastruDura

Implementazionediinsertchepreservarepinvariantpublic void insert(Character c) { Character cc = new Character(encrypt(c)); if (!elts.contains(cc)) elts.addElement(cc); } public boolean member(Character c) { return elts.contains(c); }

Ilprogrammapresentadeicomportamen3nonadegua3

26

Repinv.vincolalastruDura

Implementazionediinsertchepreservarepinvariantpublic void insert(Character c) { Character cc = new Character(encrypt(c)); if (!elts.contains(cc)) elts.addElement(cc); } public boolean member(Character c) { return elts.contains(c); }

Ilprogrammapresentadeicomportamen3nonadegua3

27

CharSet s = new CharSet( ); s.insert('a'); if (s.member('a')) ...

Lafunzionediastrazione(AF)

Laabstrac3onfunc3onassocialarappresentazioneconcretaaivaloriastra?AF:Object→abstractvalueAF(CharSetthis)={c|cappar3eneathis.elts}

“insiemedeicaraDeriinthis.elts”o  nonèeseguibile:èun“valore”conceDualedellaastrazioneo  tuDavia,lafunzionediastrazionecipermeDediragionaresulle

modalitàconlequaliimetodioperanointerminidellavisioneastraDa(chehannoiclien3)

28

Ilcasoinsert

Laspecificadiinsert// modifies: this // effects: thispost = thispre U {c} public void insert (Character c) {…}

LaAFcidiceeffe?vamentecosasignificailrepinvariantAF(CharSetthis)={c|cappartenen3athis.elts}

Invochiamoinsert

All’ingressodelmetodovaleAF(thispre)≈eltspreAll’uscitaAF(thispost)=AF(thispre)U{encrypt('a')}

MegliousarequestaAFalterna3va

AF(this)={c|encrypt(c)appartenen3athis.elts}={decrypt(c)|cappartenen3athis.elts}

29

Esempio:AFperStack

30

new() 0 0 0

push(17) 17 0 0

Top=1

push(-9) 17 -9 0

Top=2

Top=0

stack=<>

stack=<17>

stack=<17,-9>

pop() 17 -9 0

stack=<17>Top=1

Sta3astra?stack=<17>=<17>

Sta3concre3

<[17,0,0], top=1> ≠

<[17,-9,0], top=1>

AFèunafunzioneL’inversodiAFnonloè

31

Riassuntofinale

Repinvarianto  Qualisonoivaloriconcre3cherappresentanovaloriastra?

Abstrac3onfunc3ono  Perognivaloreconcretores3tuisceilcorrispondentevaloreastraDo

Obie?vocomune:sonoentrambeindispensabilipercontrollarela

correDezzadell’astrazioneDisolito,ladocumentazionefavederesolamenteilrepinvariant

32