Lösungshinweise Übung 3

[~usz]

Hallo,

drei Fragen zu den Lösungshinweisen:

Müsste bei Aufgabe 1c) die unterste Anomalie in der Tabelle (givenReferences, 35-...-51) nicht eine ur-Anomalie sein? Ihr habt den Pfad dort als du-Anomalie klassifiziert. Es gibt aber im gesamten Graphen kein d(givenReferences), also kann das irgendwie nicht richtig sein?

Zeile 60 im Code "children.next();" wird im Graph mit d(children) markiert (siehe auch Datenflussgraph in der Augabenstellung). Die Frage ist hier, warum es sich um eine Zuweisung handelt? Man könnte das so verstehen dass der "Wert" von children verändert wird, weil die Operation next() den Zustand der Variable ändert. Das ist aber auch streng genommen nicht garantiert, da man nie wissen kann, ob eine Operation den Zustand eine Objektes verändert oder nicht. Bei next() hilft man sich wohl über die Benamung, aber was wäre bei foo.bar() ?
Dann nehmt ihr an der Stelle noch verwirrenderweise Bezug auf einen Hinweis in der Aufgabenstellung: Dort steht aber nur, dass next() eine berechnende Operation (c) ist. Stünde dort "zustandsverändernde Operation" wäre es klarer, aber so? Wir hatten das damals auch in der Abgabe unserer Übung bemerkt, und der Tutor hat auch geschrieben das es richtig ist, aber den angegebenen Grund können wir leider nicht entziffern

1f) Warum geht der Rückwärtsslice über 46, 45, 43? Dafür müsste es eine Datenflusskante von 45 nach 46 geben. Es gibt diese Kante aber nicht im Graphen (was auch korrekt ist). Unserer Meinung nach müsste der Slice 46, 43, 38, 36, 35 sein.

[saller]

Hi,

Müsste bei Aufgabe 1c) die unterste Anomalie in der Tabelle (givenReferences, 35-...-51) nicht eine ur-Anomalie sein? Ihr habt den Pfad dort als du-Anomalie klassifiziert. Es gibt aber im gesamten Graphen kein d(givenReferences), also kann das irgendwie nicht richtig sein?

Danke für den Hinweis - hier hast Du einen Fehler gefunden - das ist tatsächlich eine ur-Anomalie.

Zeile 60 im Code "children.next();" wird im Graph mit d(children) markiert (siehe auch Datenflussgraph in der Augabenstellung). Die Frage ist hier, warum es sich um eine Zuweisung handelt? Man könnte das so verstehen dass der "Wert" von children verändert wird, weil die Operation next() den Zustand der Variable ändert. Das ist aber auch streng genommen nicht garantiert, da man nie wissen kann, ob eine Operation den Zustand eine Objektes verändert oder nicht. Bei next() hilft man sich wohl über die Benamung, aber was wäre bei foo.bar() ?
Dann nehmt ihr an der Stelle noch verwirrenderweise Bezug auf einen Hinweis in der Aufgabenstellung: Dort steht aber nur, dass next() eine berechnende Operation (c) ist. Stünde dort "zustandsverändernde Operation" wäre es klarer, aber so? Wir hatten das damals auch in der Abgabe unserer Übung bemerkt, und der Tutor hat auch geschrieben das es richtig ist, aber den angegebenen Grund können wir leider nicht entziffern

Da hast Du vollkommen recht - man könnte es als eine Zustandsverändernde Operation sehen (damit wäre es ein d(children)) oder man behandelt Methoden eines Objektes als Black-Box und verwendet einen einfachen c-Operator. Beides ist in diesem Falle korrekt, da beide Argumentationen zulässig sind. Ich habe den Hinweis in dem Lösungsvorschlag entsprechend angepasst, damit dies hoffentlich klarer wird.

1f) Warum geht der Rückwärtsslice über 46, 45, 43? Dafür müsste es eine Datenflusskante von 45 nach 46 geben. Es gibt diese Kante aber nicht im Graphen (was auch korrekt ist). Unserer Meinung nach müsste der Slice 46, 43, 38, 36, 35 sein.

Der Rückwärtsslice über den Knoten 45 wird nur klar, wenn man den Datenflussgraphen mit den Kontrollflussverzweigungen angereichert hat. Die Bedingung in 45 beeinflusst auch den Wert des Knotens 46 und halt auch 48. Ein Datenfluss besteht nicht, das sit korrekt, aber der Wert der Bedingung beinflusst auch den Ausgangsknoten 48. Damit gehört 45 in den Rückwärtsslice und es müssen auch alle Knoten aufgenommen werden, die wiederum 45 beeinflussen.
Kurz: Bei einem Rückwärsslice muss ein vollständiger Abhängigkeitsgraph vorliegen und es müssen nicht nur die Datenfluss sondern auch die Abhängigkeitskanten betrachtet werden.

Gruß
Karsten

[~usz]

Der Rückwärtsslice über den Knoten 45 wird nur klar, wenn man den Datenflussgraphen mit den Kontrollflussverzweigungen angereichert hat. Die Bedingung in 45 beeinflusst auch den Wert des Knotens 46 und halt auch 48. Ein Datenfluss besteht nicht, das sit korrekt, aber der Wert der Bedingung beinflusst auch den Ausgangsknoten 48. Damit gehört 45 in den Rückwärtsslice und es müssen auch alle Knoten aufgenommen werden, die wiederum 45 beeinflussen.
Kurz: Bei einem Rückwärsslice muss ein vollständiger Abhängigkeitsgraph vorliegen und es müssen nicht nur die Datenfluss sondern auch die Abhängigkeitskanten betrachtet werden.

Ja, du hast recht, danke

[s!mon]

Habe auch noch eine Frage zu der Übung. Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?

Bei der Operation refCount++ lese ich doch den alten Wert von refCount und weise das dann als neuen Wert refCount zu. Ich habe also die Reihenfolge c(refCount), d(refCount). Warum gibt es dann eine Kante im Graphen dafür? Imo dürfte nur bei einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen.

Need help

edit: außerdem frage ich mich noch wieso bei dem Kontrollflussgraphen im Knoten 64-66 ein u(v,e, children) vorkommt. Das undefined erfolgt doch schon bei Knoten 62?!

[oren78]

Habe auch noch eine Frage zu der Übung. Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?

Bei der Operation refCount++ lese ich doch den alten Wert von refCount und weise das dann als neuen Wert refCount zu. Ich habe also die Reihenfolge c(refCount), d(refCount). Warum gibt es dann eine Kante im Graphen dafür? Imo dürfte nur bei einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen.

In der Tat etwas seltsam, im Skript, Seite: 201 steht ja unter Punkt 3. folgendes:

3. für alle Anweisungen \(n\) auf Pfad \(p\) (ohne \(n_1\)) gilt nicht \(d(v)\) für \(n\):
\(n\) ändert also nicht den bei \(n_1\) festgelegten Wert von \(v\)

Meiner Meinung nach dürfen weder bei \(46, 58\) noch bei \(60\) die Knoten eine Kante zu sich selbst besitzen,
da innerhalb des selben Knotens der Wert der jeweiligen Variable \(v\) mittels \(d(v)\) geändert wird!

Im Prinzip widerspricht sich hier also die Definition 3. mit der Musterlösung insofern das ja gesagt wird:
ohne \(n_1\) wobei \(n_1\) der einzige knoten ist !!!

[Mojito Mix]

Hallo,
hab auch noch eine Frage zu dieser Übung...Bei der Tabelle zu den Anomalien (Aufgabenteil c) wird für die Variabel e eine dd-Anomalie angegeben. Laut dem Graph kann es aber durch den Knoten 62 keine dd-Anomalie geben? In jeder Iteration der while-Schleife wird laut dem Graph die Variable auf undefined gesetzt. Damit eine dd-Anomalie vorhanden ist, darf laut Skript bis zur nächsten Definitionsstelle die Variable nicht benutzt (u|r|d) werden?
Ist der Knoten 62 überhaupt notwendig oder kann man die Variable e bereits im Knoten 45, also im Schleifenkopf, auf undefined setzen?

[saller]

Hi,

Laut dem Graph kann es aber durch den Knoten 62 keine dd-Anomalie geben?

NEIN - da hast du einen Fehler aufgespürt. Laut Script darf auf dem Pfad einer dd-Anomalie kein lesender oder natürlich auch 'undefinierender' zugriff erfolgen. Damit fliegt diese Anomalie raus...

Ist der Knoten 62 überhaupt notwendig oder kann man die Variable e bereits im Knoten 45, also im Schleifenkopf, auf undefined setzen?

Das geht leider nicht, da man sonst mit dem Kontrollfluss durcheinander kommt und man würde beim ersten Schleifendurchlauf automatisch ein undefine von einem noch nicht existierenden Attribut machen. Es muss also explizit am Ende der Schleife / Kontrollblockes ausgeführt werden.

Gruß
Karsten

[s!mon]

- Aber beim Funktionskopf macht man das doch genauso (um beispielsweise ur Anomalien zu bestimmen von Variablen die nie definiert wurden). Also da wird doch auch u(var) angegeben obwohl das Attribut noch gar nicht existieren kann?!

Wollte auch nur noch mal darauf hinweisen, dass ich auch noch eine Frage gestellt habe (weil ich befürchte, dass du sie überlesen hast, weil du die Frage ganz unten beantwortet hast ):

- Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?
Bei der Operation refCount++ lese ich doch den alten Wert von refCount und weise das dann als neuen Wert refCount zu. Ich habe also die Reihenfolge c(refCount), d(refCount). Warum gibt es dann eine Kante im Graphen dafür? Imo dürfte nur bei einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen.

- Außerdem frage ich mich noch wieso bei dem Kontrollflussgraphen im Knoten 64-66 ein u(v,e, children) vorkommt. Das undefined erfolgt doch schon bei Knoten 62?!

Need help

[saller]

Ups - Sorry - da hab ich wohl was überlesen - gut also zu Deinen Fragen:

- Aber beim Funktionskopf macht man das doch genauso (um beispielsweise ur Anomalien zu bestimmen von Variablen die nie definiert wurden). Also da wird doch auch u(var) angegeben obwohl das Attribut noch gar nicht existieren kann?!

Das ist ein Sonderfall, der so eigentlich nicht definiert ist. Normalerweise liegt ja auch der komplette Quellcode vor und nicht nur Teile daraus.
In der Übung hatte ich gesagt, dass es als korrekt angesehen wird (im Hinblick auf die Korrektur). Wichtig war mir vor Allem, dass erkannt wird, das eine UR-Annomalie vorliegt. Wo man das U gesetzt hat (Methodenbeginn oder vor direkt dem R) war dabei irrelevant.
In der Klausur würde dieser Spezialfall - ein Attribut wird niemals direkt undefined - nicht auftreten, da wir ihn "offiziell" nicht behandelt haben. Sprich man hätte immer ein undefine wie "String s;".

Was sollen denn diese rekursiven Kanten im Datenflussgraph (zum Beispiel bei Knoten 58 von refCount auf refCount)?

Beim nächsten Schleifendurchlauf liest du aber von dieser Definitionsstelle, daher liest es soz. von sich selbst. Ich habe jetzt allerdings gesehen, dass refCount ja in der Schleife definiert wird. Daher ist diese Kante tatsächlich falsch. Daten fließen somit nur von 51 und 54 nach 58. Wäre diese "starke" Definition allerdings nicht gegeben (z.B. die Initialisierung in Zeile 51 würde in 39 vorgenommen werden), wäre der rekursive Datenfluss allerdings korrekt. Bei sowas muss man immer Aufpassen.

einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen

Das ist Korrekt - hier hast du einen direkten Datenfluss. Es ist aber - wie oben erwähnt - nicht der einzige Fall.

Außerdem frage ich mich noch wieso bei dem Kontrollflussgraphen im Knoten 64-66 ein u(v,e, children) vorkommt. Das undefined erfolgt doch schon bei Knoten 62?!

Verfluchtes Copy&Paste - für solche Arbeiten sollte man das ausschalten können. Du hast hiermit Recht - ein doppeltes undefine der Attribute v,e,children macht natürlich keinen Sinn.

Danke für die Hinweise und viele Grüße
Karsten

[s!mon]

Beim nächsten Schleifendurchlauf liest du aber von dieser Definitionsstelle, daher liest es soz. von sich selbst. Ich habe jetzt allerdings gesehen, dass refCount ja in der Schleife definiert wird. Daher ist diese Kante tatsächlich falsch. Daten fließen somit nur von 51 und 54 nach 58. Wäre diese "starke" Definition allerdings nicht gegeben (z.B. die Initialisierung in Zeile 51 würde in 39 vorgenommen werden), wäre der rekursive Datenfluss allerdings korrekt. Bei sowas muss man immer Aufpassen.

Ja die Definition aus 51 war das, was mich gestört hatte. Alles klar, vielen Dank.

[nogood]

Hi,

mir ist jetzt auch noch eine kleine Kleinigkeit an der Lösung 3 aufgefallen ^^.

Für die Variablen dag und givenRefernces wird im ersten Knoten des Kontrollflussgraphen ein u(dag,givenReferences) angegeben,
ein explizites d|u(dag|givenReferences) findet nicht statt.
Das Selbe gilt für die Variable visitor, die müsste dann doch auch noch mit u(visitor) in den ersten Knoten aufgenommen werden?

Mir ist auch nicht ganz klar was alles jetzt abschließend noch auf undefined gesetzt werden muss. Alles was nicht schon undefined ist? Oder evtl auch alles was irgendwann mal verwendet wurde obwohl es noch nie definiert worden ist wie visitor, dag und givenReferences?
Aus dem Lösungsvorschlag geht der erste Fall hervor, aber wäre schön da sicher zu sein.

Hoffe mich kann da jemand aufklären

Ich habe auch noch ein Verständnisproblem mit dem ++Refcount Beispiel:

einer Zuweisung wie ++RefCount sowas im Datenflussgraphen vorkommen

Das ist Korrekt - hier hast du einen direkten Datenfluss. Es ist aber - wie oben erwähnt - nicht der einzige Fall.

Wenn ich die Diskussion richtig verstanden habe seit ihr der Meinung, dass für den Fall ++refcount für den entsprechenden Knoten eine rekursive Schleife angelegt werden müsste? Wenn nicht dann ignoriert den Rest einfach

Es ist doch so dass ++refcount bzw. refcount++ lediglich etwas syntaktischen Zucker darstellen um eine verkürzte Schreibweise für zwei Zuweisungsanwendungsfälle bereitzustellen:
Sodass

Code: Alles auswählen

int d = refcount++;
=>
int d = refcount;
int refcount = refcount +1;

und

Code: Alles auswählen

int d = ++refcount;
=>
int d = refcount +1 ;
refcount = refcount + 1;
bzw. 
refcount = refcount + 1;
int d = refcount;

In beiden Fällen muss aber zuerst ein c(refcount) vor einem d(refcount) ausgeführt werden, sodass lediglich im Fall einer Zuweisung an eine weitere Variable eine rekursive Schleife entstehen würde?

[saller]

Hi,

Das Selbe gilt für die Variable visitor, die müsste dann doch auch noch mit u(visitor) in den ersten Knoten aufgenommen werden?

Hmm - war vielleicht etwas schlecht gewählt ohne den direkten Hintergrund der Übungsdiskussion. In der Pbung wurde darüber diskutiert, dass man ja nicht wissen kann, ob diese Variablen gegeben sind (z.B. als globale Attribute) definiert sind oder auch nicht initialisiert wurden. In unserer Übung betrachten wir ja immer nur einen Codeausschnitt. Der Konsistenz halber sollte hier also auch u(visitor) stehen.

Wenn ich die Diskussion richtig verstanden habe seit ihr der Meinung, dass für den Fall ++refcount für den entsprechenden Knoten eine rekursive Schleife angelegt werden müsste? Wenn nicht dann ignoriert den Rest einfach

Also nur um das kurz klar zu stellen: Eine rekursive Schleife wird hier Prinzip nicht angelegt, sondern der Selbstverweis deutet auf einen Datenfluss zu sich selbst hin. Sprich ich definiere und lese diese Definition irgendwann evtl. später.

++refcount bzw. refcount++ lediglich etwas syntaktischen Zucker darstellen

Hehe - japp da hast Du recht. Es wird immer ein c und dann erst ein d von refCount gemacht. Manchmal sollte man Feierabend machen, wenn es Zeit dafür ist
Aber um meine Ehre zu Verteigien - das Beispiel könnte entsprechend erweitert werden:
Bei

Code: Alles auswählen

System.out.println(++refCount); 

Hätten wir immer einen Selbstverweis auf sich: c(refCount), d(RefCount), c(refCount)
Im Gegensatz zu:

Code: Alles auswählen

System.out.println(refCount++); 

Hier wird erst refCount ausgegeben, bevor es neu definiert wird: c(refCount), (c(refCount) da bin ich mir jetzt nicht sicher ob notwendig), d(refCount).

Gruß
Karsten

[nogood]

Danke für die Klarstellung

[s!mon]

Eigentlich wollte ich mit dem Ausdruck nur darauf hinweisen, dass die Reihenfolge von Auswertung und Zuweisung wichtig ist und man nicht immer gleich eine rekursive Kante einführen darf. Dass das mit ++refCount (alleinstehend) gar nicht funktioniert ist mir jetzt aber nicht aufgefallen, danke

[Omen]

Ich habe eine Frage zur "Erweiterung zu einem Abhängigkeitsgraphen" Hinweise zum 3. Aufgabenblatt Seite 27:
Müsste es nicht einen Erweiterungspfad vom Knoten "n10" zum Knoten "n37" geben? Ist das nicht vergleichbar mit n20---->n33?