|
Wie verhält sich der Stack bei einem rekursiven Algorithmus?
Hallo!
Ich habe hier einen mathematischen Parser, der einen String rekursiv zerlegt. Quelltext:
Delphi-Quellcode:
Quelle:
if pos0('+',s)>0 then result:=TTR(anfang(s,'+'))+TTR(ende(s,'+'))
 http://delphi.zsg-rottenburg.de/parser.htmlDabei findet die Funktion "pos0" das erste Rechenzeichen, in unserem obigen Fall das '+' in einem String S. Die Funktion "Anfang" schneidet den Teil des Strings vor dem Rechenzeichen heraus, die Funktion "Ende" dementsprechend den String nach dem Rechenzeichen. Der mathematische Term wird allgemein in ein Editfeld eingegeben! Gehen wir nun einmal von dem Beispiel: 2x^2+1 aus. Der Term wird zunächst in 2x^2 zerlegt, wobei die "1" im Stack gespeichert wird. Anschließend wird x^2 nach meinem Verständnis im Stack gespeichert und die Funktion nur noch mit dem String S='2' aufgerufen. Diesen String kann er nun nicht mehr weiter zerlegen. Er wendet sich nun dem nächsten Teilproblem x^2 zu. Doch wie merkt er sich nun diese 2? Kommt diese auch in den Stack? Oder habe ich das Stackprinzip falsch verstanden? Kann mir mal einer bitte die Funktionsweise des Stacks genau erklären? Danke im Vorraus, Penelopee |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Auf dem Stack liegen erstmal grundsätzlich:
-(alle) Übergabeparameter -(alle) lokale Variablen, und zwar von jeder Instanz -irgendwelche geretteten Register (meist mindestens ebp und esi) -bei jedem Aufruf einer Funktion, die Rücksprungadresse ausgleichend kann man noch sagen, dass im Zuge der Optimierung (bzw. aus anderen Gründen) manche Variablen/Übergabeparameter nie auf dem Stack landen, sondern in Registern gehalten werden. Dass erhöht die Zugriffsgeschwindigkeit, allerdings hat man in umfangreichen Funktionen selten Register übrig. Und Delphi übergibt die ersten 3 Parameter einer Funktion immer in Registern (siehe Aufrufkonvention register; C macht das z.B. nicht; hat vor- und nachteile) Weiterhin gibt es Variablen, die größer sind als 1 Platz im Stack, alos alles was größer als 4 Bytes ist (Strings, Arrays und Records z.B.). Die liegen irgendwo im Speicher (können auch im "Stackbereich" der Funktion liegen, die z.B. den Record angelegt hat) und es wird nur mit Zeigern darauf gearbeitet. Bei einem String ist das generell so, der leigt irgendwo auf dem Heap und in deiner lokalen Variable liegt nur der Zeiger (4 Bytes). So, dann gibts noch die Möglichkeit, Werte im Stack der FPU zu speichern, was im gelegentlich für Fließkommazahlen gemacht wird. Wenn du es mal genau für deine Funktion wissen willst dann debugge sie doch mal und drücke Strg+Alt+C. Am Auszug deiner Funktion würde ich jetzt mal vermuten (muss aber nicht sein), dass jede Instanz von TTR min 8*4Bytes benötigt: -Rücksprungadresse -Rettung von ebp,esi und edi (ebp:Zeiger für lokale Variablen, esi und edi wird für Stringoperationen benötigt -Adresse auf s -Adresse auf anfang -Adresse auf ende -result (was auch immer das jetzt ist) Allerdings könnte es sein, dass ein Strinzeiger in esi gehalten wird. Das kommt letztenendes auf den Compiler an. Wie gesagt schau es dir doch einfach mal an! |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Hallo,
der Stack ist ein Speicherbereich der eigentlich vom System komplett verwaltet wird und auf den der Delphi Programmierer selten zugreifen muss. Ich versuche es einmal so herum: Jede Rekursion wird durch eine Abbruchbedingung beendet. In diesem Fall also, wenn ein 'Atomstring' der nicht weiter zerlegbar ist erreicht wurde. Dieser nun vorhandene 'Atomstring' wird nun in ein vorher bereitgestelltes Array aus Strings gespeichert und der Index auf dieses Array um 1 inkrementiert. Dann geht es in der Rekursion einen Schritt zurück, das Programm holt sich den 'Reststring' vom Stack zurück (damit muss sich der Programmierer gar nicht befassen, das macht das System automatisch) und isoliert den nächsten 'Atomstring'. Der wird dann wieder ins Array abgelegt etc. pp. Wenn die Rekursion dann beendet ist und der komplette String zerlegt wurde liegt dem Programmierer eben dieses sortierte Array an Strings vor das er dann sequentiell abarbeiten kann. Nochmal zum Stack: wenn Delphi eine Funktion oder Prozedur aufruft (z.Bsp. cos (1.5) ) werden automatisch einige Werte auf den Stack gespeichert, z. Bsp. die Aufrufadresse oder das Argument (in diesem fall also 1.5 ). Innerhalb der Funktion kann dann auf das Argument wie auf eine normale Variable zugegriffen werden. Nach Beendigung der Funktion/Prozedur holt sich das System dann die Aufrufadresse zurück und kann damit zur richtigen Stelle im Hauptprogramm zurückspringen, aber damit hat der Programmierer wie gesagt gar nichts zu tun. Hoffe es hilft etwas mfg Matthias |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Danke ersteinmal für eure Hilfe!
Ich habe noch ein paar Fragen zum Beitrag von matwur. Wenn ich dich richtig verstanden habe, so wird der gesamte Strings erstmal in die sogenannten Atomstrings zerlegt, die jeweils in einem Array of String abgespeichert werden. Jetzt mal meine Frage: Woher weiß das Programm, was er mit den einzelnen "Atomstrings" machen soll, also welche er miteinander multiplizieren oder potenzieren, etc. muss. Wo wird das festgehalten? Kannst du vielleicht auch erklären, was es mit dieser Rücksprungadresse auf sich hat? Sorry, dass ich so primitive Fragen stellen muss, aber mein Wissen über den Stack ist doch sehr beschränkt und muss eine Präsentation für den Informatikunterricht vorbereiten, deswegen danke ich für eure Hilfe! Mit freundlichen Grüßen, Penelopee |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
multiplizieren etc. hat nichts mit den Stack direkt zu tun, das ist aufgabe des Programmierss zu wissen was er rechnen will.
Letzendlich ist der Stack ähnlich wie ein Wäschestabel. Man kann nur oben was drauf legen und auch nur von oben was runternehmen. Wenn eine Procedure aufgerufen wird, so wird auf dem Stack eben die Adresse abgelegt wo es nach dem Aufruf der Procedure weiter geht. Bsp.:
Delphi-Quellcode:
Bei Rekursion sieht es nicht anders aus
//Beim Aufruf von ShowMessage wird auf dem Stack "mein Text" abgelegt und die Adresse wo der Befehl "Beep" steht
//Nach dem ShowMessage also fertig ist wird "mein Text" vom Stack runter genommen und dann die Adresse von "Beep" und dort wird dann hinn gesprungen (ist jetzt alles sehr vereinfacht ausgedrückt ShowMessage('mein Text'); beep;
Delphi-Quellcode:
Das ist eine Endlosrekursion und irgendwann läuft der Stack über weil immer wieder eine Rücksprungadresse etc. auf den Stack gelegt wird aber nie wieder was runter genommen wird.
procedure DoSomeThing();
begin DoSomething(); end; |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Also wenn ich das jetzt richtig verstanden habe, würde das für folgendes Beispiel folgendermaßen ablaufen:
String: '2*x^3+1' Der Term wird zunächst in 2*x und 1 zerlegt, wobei die 1 in den Stack kommt. Anschließend wird der String 2*x^3 in die 2 und x^3 zerlegt, wobei x^3 in den Stack kommt. Nun hat man nur noch die 2 und springt mit Hilfe der Rücksprungadresse an die Stelle zurück, an der man sich befand bevor die Funktion ausgelöst wurde, also an die Stelle, wo das Malzeichen steht.
Delphi-Quellcode:
Nun wird der String x^3 in gleicher Weise zerlegt. Gleichzeitig merkt sich das Programm mit Hilfe der Rücksprungadresse, dass es nach der Zerlegung von x^3 den Term mit der 2 multiplizieren muss. Dabei wird der Befehl "multipliziere mit der 2" im Arbeitsspeicher(???) festgehalten. Anschließend holt sich das Programm noch die 1 vom Stack und verfährt in gleicher Weise.
if pos0('*',s)>0 then result:=TTR(anfang(s,'*'))*TTR(ende(s,'*'))
Habe ich das so richtig verstanden? |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
wegen
if pos0('*',s)>0 ... weiss das Programm, das es hier multiplizieren muss. Wenn das Quadrat zerlegt wird schreibt der Parser entsprechend if pos0('^',s)>0 then result:=power(TTR(anfang(s,'^')),TTR(ende(s,'^'))) das Ergebnis wird also direkt nach rekursiver Termbestimmung berechnet, er braucht sich nicht merken welche arithmetische Operation hier ausgeführt wird, das wird gleich gemacht. Beachte das durch die Rekursion die beiden Terme die man für die jeweilige Operation braucht, bereits explizit berechnet sind. Zitat:
- 1. Schritt if pos0('+',s)>0 then TTR(anfang(s,'+'))+TTR(ende(s,'+')) der Term 1.1 ist noch kein Atomstring, also wird der weiter zerlegt 2. Schritt if pos0('*',s)>0 then TTR(anfang(s,'*'))*TTR(ende(s,'*')) der Term 2.1 ist ein Atomstring, der Term 2.2 wird weiter zerlegt 3. Schritt if pos0('^',s)>0 then result:=power(TTR(anfang(s,'^')),TTR(ende(s,'^'))) die Potenz wird berechnet und zurück zum 2. Schritt gesprungen. Das Ergebnis der Operation hier ist das Funktionsergebnis von TTR(ende(s,'*')). 2. Schritt zum zweiten Term 2.1 ist bekannt, Term 2.2 wurde gerade zurückgeliefert also kann gerechnet werden und das jetzige Ergebnis geht als Rückgabewert des Aufrufs TTR(anfang(s,'+')) zurück nach Schritt 1 1 Schritt zum zweiten Term 1.1 ist nun berechnet, Term 1.2 ist ein Atomstring und kann nun direkt addiert werden. Jetzt liegt das Endergebnis vor und wird an das aufrufende Hauptprogramm zurückgeliefert. - im 1. Schritt muss gar nichts zwischengespeichert werden, im 2. Schritt wird der Term 2.1, also der Atomstring kurz auf den Stack gelegt, dann zur Auswertung der Potenz gesprungen. Wenn dieser Funktionsaufruf zurückkehrt wird der Term 2.1 vom Stack geholt und mit dem Ergebnis der Potenz multipliziert. Der Stack ist hier nur ein ganz normaler Speicher für kurzzeitig zu sichernde Zwischenwerte. Genauso verhält es sich mit den Adressen der Funktionsaufrufe. Springst du zum Beispiel aus Schritt 2 heraus zum 3. Schritt (zum potenzieren) merkt sich das Programm die Adresse (den Ort von wo losgesprungen wird). Das diese Adresse dabei auf den Stack kommt ist eigentlich auch nebensächlich :D Wurde die Potenz dann berechnet wird die letzte Adresse vom Stack gelesen und eben dorthin zurückgesprungen. Auf dem Stack liegen natürlich noch andere Adressen von Funktionsaufrufen. Aber es wird immer die letzte Adresse verwendet (und dann der 'Stackpointer', das ist ein Zeiger auf den Stack, korrigiert). Operationen wie 'multipliziere' werden nie auf den Stack gelegt oder gespeichert, die werden direkt berechnet. Eben durch den rekursiven Aufbau des Parsers wird ja sichergestellt das beide benötigten Terme als Atomstrings zurückgeliefert werden und direkt berechnet werden können. Diese Berechnung liefert nun einen nächsten Atomstring der zur vorherigen Operation zurückgegeben wird oder eben das Endergebnis des Gesamtaufrufes darstellt. noch'n Bleistift: if pos0('+',s)>0 then TTR(anfang(s,'+'))+TTR(ende(s,'+')) TTR(anfang(s,'+')) stellt den Aufruf einer Funktion dar. Durch die Rekursion ergibt der Rückgabewert dieser Funktion einen Atomstring (oder einfach eine Zahl, je nach Auffassung). Dieser Atomstring kommt auf den Stack. Nun wird der 2. Funktionswert durch den Aufruf von TTR(ende(s,'+')) bestimmt, ebenso rekursiv, und ebenso ist der Rückgabewert wieder ein Atomstring. Nun wird die Addition explizit ausgeführt und der neue Atomstring ist fertig und wird wieder zurückgegeben. ich hoffe jetzt wird's klarer :angel: mfg Matthias |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Liste der Anhänge anzeigen (Anzahl: 1)
Also ich habe es mal in Inline-ASM probiert. Unter der vorraussetzung, dass alle Zahlen integer sind, benötigt jede Rekursive Instanz 20 Bytes auf dem Stack. Unter dem habe ich es nicht geschafft und auch der Delphi-compiler wird nicht besser sein. Zudem ist es Quatsch bei solchen Aufgaben um jedes Byte Stack zu knausern.
die Stackplatze sind in 4-Byte-Schrittenm belegt von: -Rücksprungadresse -rettung des EBP (als Referenz vür lokale Variablen) -Result der Funktion -String der an die Funktion übergeben wird -der aktuelle Teilstring (aus der Funktion Anfang bzw. Ende --- bei mir getstring) Wenn man statt integer double nehmen würde, wären es nochmal 4 Bytes mehr (bei result) Das Programm liegt im Anhang. ----------------------- Zitat:
Zitat:
Wenn wir aber mal von den "Interna" absehen, hat MatWur schon Recht. |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
hmmm ... wenn Penelopee hauptsächlich den Parser beschreiben soll denke ich das das Problem an der Rekursion liegt, wenn sie aber den Stack beschreiben soll würde ich den Parser ganz raushauen (der Rekursion wegen) und eher den Ablauf eines normalen (nicht rekursiven) Funktionsaufrufes beschreiben. Das ein rekursiver Funktionsaufruf dann entsprechend mehr Speicherplatz auf dem Stack braucht sollte klar sein. Ich habe den Quellcode nur überflogen aber kein Assembler gesehen, alles Hochsprache. Auch einen direkten Bezug zum Stack innerhalb des Parsers (ausser das er implizit genutzt wird) habe ich nicht gefunden. Die Hochsprache soll ja den Programmierer gerade von solchen (maschinenabhängigen) Details befreien.
Vielleicht kann Penelopee noch einmal genauer spezifizieren, was erklärt werden soll... mfg Matthias |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Hallo!
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! Ich wollte eigentlich noch eine Sache fragen, was jetzt aber sirius schon beantwortet hat, nämlich ob bei dem ersten Schritt nicht zumindest die Rücksprungadresse in den Stack kommen muss! 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,'+')). 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. Hoffe, ich habe das dann jetzt einigermaßen verstanden! Danke für eure ganze Mühe, Penelopee |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Zitat:
Zitat:
Zitat:
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:
Und keine Ursache :wink: 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... :sharkylinchen: bis denne mfg Matthias |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
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 |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Liste der Anhänge anzeigen (Anzahl: 1)
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. :mrgreen: |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
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 |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
@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" :zwinker: 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:
Delphi-Quellcode:
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.
//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; mfg Sirius |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Hallo,
ja, sehr schöne Präsentation sirius, ich habe mir die auch mal gespeichert :wink: 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 :D ) und also, also, also, ich bin doch erst 42. Auf so einem 86xx Prozessor gibt es Stack's mit 1 Byte :mrgreen: . 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 :roteyes: 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... :duck: ok, dann auch von mir erst mal ein Danke Sirius und bis denne Matthias |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
Zitat:
Zitat:
Zitat:
Zitat:
|
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
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 :zwinker: bis denne Matthias |
Re: Wie verhält sich der Stack bei einem rekursiven Algorith
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.
|
| Alle Zeitangaben in WEZ +1. Es ist jetzt 23:48 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz