Wie verhält sich der Stack bei einem rekursiven Algorithmus?

[MatWur]

Zitat von Penelopee:

...
Also ein Assembler ist definitiv nicht in meinem Programmtext, alles "Hochsprache" (kenne mich Assembler-Code überhaupt nicht aus).
Ich muss wie gesagt hauptsächlich die Funktionsweise des Parsers vorstellen. Aber mir wurde gesagt, dass ich dabei auch auf die Aufgabe des Stacks eingehen soll!
...

ok, das ist deutlich

Zitat von Penelopee:

...
Ansonsten habe ich es so verstanden, dass wenn er ein Teilproblem gelöst hat (also z.B. den Wert 2*x^3) gelöst hat, so wird dieses Ergebnis an die vorhergehende Funktion geschickt und ersetzt praktisch die Anweisung: TTR(anfang(s,'+')).
...

Exakt. Man kann sogar noch weiter gehen und den Funktionsaufruf TTR selber als Zahl ansehen. Wenn diese Zahl halt noch nicht berechnet ist wird zu dem Programmteil gesprungen (mit Stacknutzung, dazu gleich mehr) der die Berechnung vornimmt und der Rückgabewert *ist* dann die Funktion.

Zitat von Penelopee:

...
Springt er nun also zurück zu der Zeile, liest das Programm praktisch (nehmen wir jetzt mal x=1 an und berechnen den Term, wobei man als Ergebnis 2 erhält):

2 + TTR(ende(s,'+'))

Da TTR(ende(s,'+')) ein Atomstring ist, wird das sofort berechnet, man erhält als Ergebnis: 3.
...

hier würde ich etwa so formulieren: In TTR(ende(s,'+')) wird sofort ein Atomstring festgestellt und die Zahl die dieser Atomstring repräsentiert wird direkt zurückgegeben.
D.h. der Funktionsaufruf findet statt, das Programm verzweigt 'kurz' wieder in die Funktion TTR, ermittelt quasi sofort den Zahlwert des Atomstrings und gibt diesen zurück (bzw. ersetzt den Funktionsaufruf durch diese Zahl)

Zitat von Penelopee:

...
Hoffe, ich habe das dann jetzt einigermaßen verstanden!

Danke für eure ganze Mühe,

Penelopee

jo, klingt ganz verständlich so.
Und keine Ursache

Zum Stack würde ich in etwas folgendes sagen:
Der Stack (zu deutsch: Stapel) ist ein Speicherbereich, dessen Verwaltung komplett vom Betriebssystem übernommen wird. Im wesentlichen wird zur Verwaltung und zur Beschreibung lediglich der SP (StackPointer) benötigt, der einfach einen Zeiger auf das erste frei Byte im Stack enthält. Ein Stack funktioniert nach dem 'lifo'-Prinzip (Last In - First Out) das man sich sehr gut mit einem Stapel Karten vorstellen kann. Auf jeder Karte kann genau ein Byte geschrieben werden. Schreibt man nun ein Byte in den Stack passiert folgendes: das Betriebssytem liest den SP, weiss dadurch wo das Byte hinkommt, schreibt es dorthin und erhöht den SP-Zeiger um eins, so das er wieder auf das erste freie Byte zeigt. (Eine Karte wird beschrieben und auf den Tisch bzw. auf den schon existierenden Kartenstapel oben drauf gelegt). Beim lesen eines Bytes verringert das Betriebssytem den SP um 1, erhält so den Zeiger auf das zuletzt geschrieben Byte und liest es aus. (Oberste Karte vom Stapel nehmen, darauf notierten Byte-wert verwenden und Karte wegschmeissen)
Der Stack wird vor allem bei Prozedur- und Funktionsaufrufen verwendet, am Beispiel eines einfachen Funktionsaufrufes sei dies hier beschrieben:

y := cos (0.5);

hmmm, meine family brüllt irgendwas von 'Kaffee', noch 3 Sätze dann muss ich weg. Heute abend evtl. noch mal was wenn noch was unklar ist.

also, das Programm muss der Variablen y eine Zahl zuordnen, es erkennt das dazu der Aufruf eines Unterprogramms namens 'cos' nötig ist. Dazu wiederum braucht es erst das Argument der Funktion (die 0.5). Das Argument liegt explizit vor, dafür ist also kein Funktionsaufruf nötig. Nun nimmt das programm die Adresse hinter dem cos-Aufruf (also nach der schliessenden Klammer) und legt diese Adresse auf den Stack. Zu dieser Adresse soll das Unterprogramm nach getaner Arbeit zurückspringen. Der Zeiger wird der Anzahl der Bytes solch einer Adresse entsprechend erhöht (wie Sirius sagte bei den Win32 Systemen im Normalfall um 4). Dann wird noch das Argument auf den Stack gelegt und der SP-Zeiger wieder entsprechend des Speicherbedarfs des Arguments erhöht. Nun wird in die Unterroutine 'cos' gesprungen.

Die Unterroutine weiss erst mal gar nichts ausser, das sie aufgerufen wurde. Daher weiss sie, das auf dem Stack ein Argument liegt. Also wird der SP-Zeiger entsprechend verringert und dann das Argument ausgelesen. Nun wird der cos aus dem Argument berechnet. Nun weiss die Unterroutine noch das auch die rücksprungadresse auf dem Stack liegen muss, also SP um 4 verringern und diese Adresse vom Stack lesen. Jetzt wird das Ergebnis der Berechnung (also der cos) auf den Stack geschrieben und der Sp wieder entsprechend erhöht. Auf dem Stack wird die Rücksprungadresse also überschrieben, aber das Unterprogramm hat sie sich natürlich gemerkt. Genau zu dieser Adresse springt nun das Unterprogramm (zurück).

Zurück in der Hauptroutine.... die weiss gar nichts ausser das gerade der vorhergehende Aufruf des cos-Unterprogramms zurückgekehrt ist und deswegen auf dem Stack das Ergebnis liegen muss. Also den SP-Zeiger wieder verringern und das Ergebnis vom Stack lesen. Dem y zuordnen, fertig.

So, der letzte meiner 3 Sätze:
Noch ein paar Anmerkungen
- die Implementierung des Stacks ist Maschinenabhängig. Z. Bsp. kann die SP-Korrektur nach dem Schreiben/vor dem Lesen erfolgen, sie könnte aber auch vor dem Schreiben/nach dem Lesen erfolgen.
- neben dem SP legt das Programm bei jedem Funktionsaufruf noch andere Werte auf den Stack
- erfolgt ein Funktionsaufruf rekursiv, wie in dem besprochenen Parser, kann es bei entsprechender Rekursionstiefe und Argumentgrösse vorkommen, das der Speicherplatz des Stacks nicht ausreicht.

- und @ sirius: ich schaue mir nachher dein Post noch mal an, aber die Interna sind mir tatsächlich auch weniger geläufig, einfach weil für mich nie ein Bedarf bestand den Stack irgendwie direkt zu manipulieren... auf die Schnelle fällt mir folgende Frage auf: Wird der Speicherplatz für das Funktionsergebnis tatsächlich vor dem Funktionsaufruf auf dem Stack reserviert?

die können laut brüllen...

bis denne

mfg

Matthias

[Penelopee]

Vielen dank für eure Hilfe und Mühe, ihr habt mir wirklich weitergeholfen.

Die Veränderung des Stacks klingt ziemlich verwoben und kompliziert, da ja nicht nur die Zahlen in den Stack kommen, sondern ganze Funktionswerte samt Rücksprungadresse.
Bin grad am überlegen wie ich das graphisch, z.B. mit Powerpoint darstellen bzw. veranschaulichen soll/kann? Hättet ihr da auf Anhieb eine Idee?

MfG,

Penelopee

[sirius]

Angaben ohne Gewähr.
Schau dir mal den Anhang an.


Edit: Da meine Tochter gestern etwas drängelte, komme ich erst jetzt zur Fehlerkorrektur. Es waren 3 kleine Schönheitsfehler. Aber man will ja perfekt sein, deswegen habe ich sie behoben.

[Penelopee]

Vielen Dank für diese ausführliche Präsentation!
Sieht doch schon sehr ansprechend aus und hat mein Verständnis noch vertieft.

Allesdings werde ich das für meine Präsentation ein bisschen vereinfachen, da es doch schon sehr komplex ausschaut!

MfG,

Penelopee

[sirius]

@Matthias

Erstmal eine kleine Korrektur: Nicht das Betriebssystem organisiert den Stackpointer, sondern die CPU. Wie auch alle anderen Register. Nur wenn ich will, dann kann ich auch den Stackpointer einfach verändern. Ist ja ein normales Register. Dasselbe kann und macht natürlich dann auch das Betriebssystem.

Und das zweite was ich anmerken möchte: Das LIFO-Prinzip auf dem Stack ist richtig. Man sollte allerdings nicht vergessen, dass man auch den Stack frei adressieren und irgendwo darin lesen und schreiben kann. Und das wird normalerweise auch so genutzt, dafür ist ja der BasePointer (BP bzw. EBP)

Und ...ähm..., dass der Stack in Byte-Schritten bewegt wurde ist sehr lange her. War zumindest nicht zu meiner "aktiven Phase"


Wie sieht es nun mit der Übergabe von Werten an Funktionen und Prozeduren aus (und die Rückgabe von Funktionsergebnissen)?
Wenn du in ASM programmierst ist es dir vollkommen selbst überlassen, wie du das gestaltest. Ums mal extrem zu machen: Du kannst sie auch auf die Festplatte schreiben. Für gewöhnlich wird dies aber nicht so gemacht. Die meisten Programmiersprachen legen die Parameter auf den Stack, dabei kann die Reihenolge auch verschieden sein. In Delphi werden die ersten 3 Parameter meist in die Register EAX, EDX und ECX gelegt (je nachdem ob sie reinpassen). Wenn du das selber festlegen willst oder musst, schreibst du ja diese Aufrufkonventionen dazu (--> siehe "stdcall", "register", "cdecl"). Delphi nimmt wie gesagt, normalerweise Register, C nimmt cdecl und Microsoft stdcall. Mit diesen Konventionen legst du ja auch fest, wer den Stack aufräumt.
Rückgabewerte gehen fast immer über EAX, bei jedem Compiler.


In meinem Beispiel in ASM und in der Präsentation habe ich es nun im Gegensatz zu Delphi immer auf den Stack gelegt. Wäre also als wenn man die Funktion TTR mit "stdcall" deklariert. Das liegt nun an den Vor- und Nachteilen der einzelnen Aufrufkonventionen. Die Variante register ist eigentlich nur sinnvoll, wenn ich nachher gleich mit der Variablen im Register weiterarbeite. In unserer Funktion hätte ich sie aber trotzdem auf den Stack legen müssen. Es war in dem Fall also egal, ob die aufrufende Funktion den wert auf den Stack legt oder erst die aufgerufene Funktion. Denn zwischenspeichern muss sich die aufgerufeene Funktion den Wert irgendwo. Und sowas geht nur im Stack (bis auf wenige Ausnahmen).

Im Grunde genommen landet eigentlich alles, was du dir irgendwie merken musst auf dem Stack. Wenn dzu zum Beispiel eine Klasse instanzierst liegt die zwar irgendwo im Speicher mit ihren Eigenschaften, aber der Zeiger, der auf die Instanz zeigt, liegt bei dir auf dem Stack. so ist das mit allen anderen Sachen auch. Irgendwo musst du dir ja merken, wo was liegt. Einen anderen Speicher hast du ja nicht.


Edit: Hab gad gemerkt, dass ich dir auf deine direkte Frage wahrscheinlich noch nicht wirklich geantwortet habe:

Zitat:

Wird der Speicherplatz für das Funktionsergebnis tatsächlich vor dem Funktionsaufruf auf dem Stack reserviert?

Naja, du hast ja lokale Variablen. Auch in einer Funktion, in der du keine deklarierst legt dir Delphi die Variable "result" bereit. Und lokale Variablen legt man standardmäßig (auch Delphi macht das) auf den Stack. Wenn du selber ASM programmierst, kannst du dir evtl. überlegen, trotz einer lokalen Variable, keinen Stackplatz zu reservieren. Ein Compiler hat allerdings einen Algorithmus und der ist nicht menschlich. Er macht zwar (hoffentlich) keine Fehler kann aber auch nicht perfekt optimieren. Delphi macht das zwar und legt besonders Schleifenvariablen nicht auf den Stack, aber alles kann der Compiler auch nicht. Vielleicht schafft er es auch manchmal mit Result. Aber was bedeutet es, wenn du eine lokale Variable nicht auf den Stack legst. Du brauchst ein freies Register. Entweder du hast es nicht, oder du musst es dir erst frei machen, was bedeutet du musst dir den Inhalt auf den Stack legen --> wieder keinen Stackplatz gespart. Ok, soweit dazu, noch ein kurzes Beipsiel, wie sowas funktioniert:

Delphi-Quellcode:

//Beispiel zur Verwendung von lokalen Variablen
function test:integer;
{und im Beispiel für 4 Variablen (à 4 Bytes) 
var a,b,c,d:integer;}
asm
  push ebp     //jedes Register was du manipulierst musst du vorher speichern (ausser eax,edx und ecx)
  mov  ebp,esp //aktuellen stackpointer als Referenz in Basisregister
  sub  esp,20  //jetzt Platz schaffen für 4 Variablen+result =20 Bytes 
               //in wirklichkeit legt man nicht oben auf den Stack drauf, sondern schiebt unten rein,
               //deswegen Subtraktion
               //Variable a liegt jetzt bei [ebp-4], b bei [ebp-8] ... ; So heißen die Variablen
               //dann nach dem Compiler
               //result liegt bei [ebp-20]
//hier kann man jetzt rechnen und was sonst noch und wenn ein weiterer Funktionsuafruf hier kommt, ist der Stackpointer bereits hinter unseren lokalen Variablen, sodass die nicht verändert werden und die aufrufende Funktion ist verpflichtet unser ebp zu retten, so wie wir es auch für die uns übergeordnete Funktion getan haben
//Beispiel für Funktionsaufruf
  push [ebp-4]  //Variable a wird übergeben (auf den Stack gelegt)
                //in Delphi würde sie eher über eax übergeben, also: mov eax,[ebp-4]
  call meineFunktion  //Funktionsaufruf (implizit wird Rücksprungadresse gesetzt)
  mov [ebp-8],eax  //Funktionsergebnis (aus EAX) wird in b gespeichert
//in delphi sehe das so aus: b:=meineFunktion(a);


//Am Ende müssen wir natürlich wieder alles herrichten
  mov eax,[ebp-20]  //result nach eax, wie gesagt, wenn man eax sonst nicht benötigt, 
                    //was sehr unwahrscheinlich ist, könnte man result gleich in eax vorhalten
  mov esp,ebp
  pop ebp      //das dürfte jetzt klar sein   
end;

Noch ein kleine Korrektur aus deinem Text: Es wird erst der Stackpointer erhöht (oder wie eben gesehen erniedrigt) und dann der Wert reingeschrieben, so dass der Stackpointer nicht auf einen leeren Platz, sondern auf den letzten benutzten Platz zeigt.


mfg
Sirius

[MatWur]

Hallo,

ja, sehr schöne Präsentation sirius, ich habe mir die auch mal gespeichert
auch Penelopees Version würde mich interessieren wenn sie fertig ist.

Und du hast natürlich Recht, die CPU übernimmt die Verwaltung des Stacks, ich habe ja geschrieben das die Maschinen abhängig ist (und dann das das BS die Verwaltung übernimmt.... intelligent )

und also, also, also, ich bin doch erst 42. Auf so einem 86xx Prozessor gibt es Stack's mit 1 Byte . Meine Nutzung von Assembler beschränkt sich normalerweise auf kurze Routinen zur Beschleunigung einfacher Operationen. Ich musste schon jahrelang nicht mehr den Stack selbst manipulieren. In der Tat war mir selbst der Aufbau von oben nach unten des Stacks nicht mehr bewusst. Eigentlich müsste es dann ja 'Stack underflow' heissen
Ich habe gerade mal nachgeschaut, ich habe noch den MS-MASM 6.1 (1992) in Originalversion hier mit Büchern, der Push Befehl hatte tatsächlich schon auf der 88/86 - CPU ein mindestens 16 Bit Argument. Ich schweb' geistig wohl noch in Brotkasten-Zeiten...

ok, dann auch von mir erst mal ein Danke Sirius und

bis denne

Matthias

[sirius]

Zitat von MatWur:

ja, sehr schöne Präsentation sirius, ich habe mir die auch mal gespeichert

Danke! Hat durch diese Animationen auch etwas länger gedauert als ich dachte. Vor allem die Bewegung des Stackpointers war ein Kraus, da mir Powerpoint immer "helfen" wollte und dabei nur Unsinn anstellte.

Zitat von MatWur:

In der Tat war mir selbst der Aufbau von oben nach unten des Stacks nicht mehr bewusst. Eigentlich müsste es dann ja 'Stack underflow' heissen

Ja, aber zum Erklären eines Stapel eignet sich die "nicht richtige" Variante besser, hab ich ja in der Präsentation auch so gemacht

Zitat von MatWur:

Ich habe gerade mal nachgeschaut, ich habe noch den MS-MASM 6.1 (1992) in Originalversion hier mit Büchern, der Push Befehl hatte tatsächlich schon auf der 88/86 - CPU ein mindestens 16 Bit Argument. Ich schweb' geistig wohl noch in Brotkasten-Zeiten...

Das habe ich gemerkt. Deswegen hast du auch nie ein "E" vor die Registerbezeichnungen geschrieben. Aber um dich gleich wieder uptodate zu bringen Mittlerweile steht da anstatt des "E"s ein "R" (64bit )

Zitat von MatWur:

und also, also, also, ich bin doch erst 42. Auf so einem 86xx Prozessor gibt es Stack's mit 1 Byte

Das ist aber älter als so manch anderer hier (z.B. ich ) Und ich hab erst ab 286 eingesetzt. Also abgesehen von den Zeiten an einem "robotron KC87". Der dürfte auch auf 8bit gewesen sein. Nur da bin ich noch nicht so tief in die Materie eingesteigen.

[MatWur]

hihi,

'hilfreiche' Programme wie PP können hartnäckig sein. Oder wie ich zu sagen pflege: 'C++ ist *die* Hochsprache, die es *am allerbesten* schafft einfache Pascal Programme unverständlich darzustellen'
Und ja ich habe schon ein paar Prozessorgenerationen mitgemacht. Du erinnerst mich daran, das ich in diesem Jahr wohl noch auf ein 64-Bit System umsteigen muss/möchte/werde/kann. Mal bei den Vistanern reinschauen und ein bischen informieren, evtl. ein paar wohlsortierte Noobfragen stellen *g*
Aber jetzt Laberei Ende hier, sonst komm' ich noch in Spamverdacht

bis denne

Matthias

[sirius]

Falls dem einen oder anderen etwas in der PPP komisch vorkommt, ich hab da mal etwas aktualisiert. Natürlich bleiben noch einige Fragen offen, aber alles kann man auch nicht unterbringen.