Indirekte Rekursion?

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Indirekte Rekursion?

Beitrag von Tillmann » 30. Mai 2007 17:42

Prof. Koch hat geschrieben:Hinweis: Sie müssen dabei direkte Rekursion behandeln (eine Prozedur ruft sich selbst wieder auf), die korrekte Verarbeitung auch indirekter Rekursion ist optional (kann aber zur Aufwertung Ihrer Abgabe führen).
In welcher Form unterstützt denn Triangle indirekte Rekursion?

koch
Dozentin/Dozent
Beiträge: 221
Registriert: 4. Jul 2005 11:08

Re: Indirekte Rekursion?

Beitrag von koch » 1. Jun 2007 14:05

Tillmann hat geschrieben:
Prof. Koch hat geschrieben:Hinweis: Sie müssen dabei direkte Rekursion behandeln (eine Prozedur ruft sich selbst wieder auf), die korrekte Verarbeitung auch indirekter Rekursion ist optional (kann aber zur Aufwertung Ihrer Abgabe führen).
In welcher Form unterstützt denn Triangle indirekte Rekursion?
Prozedur A ruft B auf, B ruft C auf, C ruft A auf. etc

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann » 1. Jun 2007 23:34

koch hat geschrieben:Prozedur A ruft B auf, B ruft C auf, C ruft A auf. etc
Und wie geht das in Triangle? Folgendes geht jedenfalls nicht, weil B im Rumpf von A noch nicht bekannt ist.

Code: Alles auswählen

let proc A() ~ B();
    proc B() ~ A()
in A()

tc> read Examples\test.tri
Syntactic Analysis ...
tc>check
Contextual Analysis ...
ERROR: "B" is not declared 1..1
Umsortieren hilft nicht, denn irgendeine Prozedur muß ja als erster deklariert werden. forward-Deklarationen oder ähnliches gibt es in Triangle nicht. Natürlich könnte indirekte Rekursion über prozedurale Parameter erreicht werden:

Code: Alles auswählen

let proc A(proc B()) ~ B();
    proc B() ~ A(proc B)
in A(proc B)
Aber sollte unsere Analyse damit umgehen können? Was ist das richtige Ergebnis für folgendes Programm?

Code: Alles auswählen

let var x : Integer;
    var y : Integer;
    
    proc foo(proc next()) ~
    begin
      x := 42;
      next()
    end;
    
    proc bar() ~
    begin
      y := 42;
      foo(proc bar)
    end
in bar()
Unsere Analyse liefert:

Code: Alles auswählen

read Examples\test.tri;check
Syntactic Analysis ...
Contextual Analysis ...
tc> genrwset
tc> showast

let ! genrwset: decls {x.0}
    var x : Integer;
    ! genrwset: decls {y.1}
    var y : Integer;
    
    ! genrwset: decls {next} writes {x.0}
    proc foo(proc next()) ~
    begin
      ! genrwset: writes {x.0}
      x := 42;
      ! genrwset:
      next()
    end;
    
    ! genrwset: writes {y.1, x.0}
    proc bar() ~
    begin
      ! genrwset: writes {y.1}
      y := 42;
      ! genrwset: writes {y.1, x.0}
      foo(proc bar)
    end
in ! genrwset: writes {y.1, x.0}
   bar()
Da wir innerhalb von foo nicht wissen, daß next = bar, wird beim next()-Aufruf der Schreibzugriff auf y nicht erkannt. Woher sollten wir auch wissen (in einer statischen Analyse, und ohne auf die Datenflußanalyse vozugreifen), welchen Wert next haben könnte? Dennoch liefern wir für den foo(bar)-Aufruf in bar das richtige Ergebnis (also inkl. Schreibzugriff auf y).

Wieso tauchen solche schwierig zu analysierenden Programme weder in der Spezifikation (als dem Beispiel in der Aufgabenstellung) noch unter den Beispielprogrammen auf? Oder habe ich den Passus überlesen, daß wir prozedurale Parameter ignorieren dürfen, weil die ohnehin von 95% der Triangle-Programmierer nicht verwendet werden.

koch
Dozentin/Dozent
Beiträge: 221
Registriert: 4. Jul 2005 11:08

Beitrag von koch » 5. Jun 2007 14:12

Uups, da habe ich einen Fehler in der Aufgabenstellung (die in diesem Semester teilweise neu ist) gemacht! Sie haben natürlich völlig recht, die von mir angedachte Art der indirekten Rekursion geht in Triangle (eben genau wegen des fehlenden forward gar nicht), und die von Ihnen beschriebene über Funktionspointer sollen Sie natürlich nicht analysieren (viel zu kompliziert).

Vielen Dank für die Überlegung, ich korrigier's für's nächste Mal :oops:

Gruß & Dank,
Andreas Koch

Tobias
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 132
Registriert: 20. Okt 2004 14:17
Kontaktdaten:

Beitrag von Tobias » 5. Jun 2007 20:17

Doch:

Code: Alles auswählen

let
	var x : Integer;
	var y : Integer;
	proc foo() ~ let
		proc bar() ~ begin
			x := y;
			foo()
		end in begin
			y := x;
			bar()
		end
in
	foo()
foo und bar müssten dann die gleichen reads- und writes-Mengen haben.

… unnötig zu erwähnen, dass mir der Testfall erst nach Abgabe eingefallen ist. :roll:
Wise people talk, because they have something to say; fools, because they have to say something. (Plato)

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann » 5. Jun 2007 22:02

Code: Alles auswählen

let
	var x : Integer;
	var y : Integer;
	proc foo() ~ let
		proc bar() ~ begin
			x := y;
			foo()
		end in begin
			y := x;
			bar()
		end
in
	foo()
Tobias hat geschrieben:foo und bar müssten dann die gleichen reads- und writes-Mengen haben.
Gute Idee! Gleich mal ausprobieren, was unser System dazu sagt.

Code: Alles auswählen

tc> read Examples\test.tri;check;genrwset;showast
Syntactic Analysis ...
Contextual Analysis ...

let ! genrwset: decls {x.0}
    var x : Integer;
    ! genrwset: decls {y.1}
    var y : Integer;
    
    ! genrwset: reads {y.1, x.0} writes {y.1, x.0}
    proc foo() ~
      let ! genrwset: reads {y.1, x.0} writes {y.1, x.0}
          proc bar() ~
          begin
            ! genrwset: reads {y.1} writes {x.0}
            x := y;
            ! genrwset: reads {y.1, x.0} writes {y.1, x.0}
            foo()
          end
      in begin
        ! genrwset: reads {x.0} writes {y.1}
        y := x;
        ! genrwset: reads {y.1, x.0} writes {y.1, x.0}
        bar()
      end
in ! genrwset: reads {y.1, x.0} writes {y.1, x.0}
   foo()
Das sieht doch gut aus 8)

Antworten

Zurück zu „Archiv“