Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Rekursionstyp der Prozedur bzw. des Prozesses
Hallo,
Kann mir jemand erklaeren was der Unterschied zwischen dem Rekursionstyp der Prozedur und dem Prozesses ist?
Nach dem was ich aus den alten Klausuraufgaben rausgelesen hab gilt:
| Rek. Typ der Prozedur | Rek. Typ des Prozesses |
|---|---|
| linear rekursiv | linear rekursiv |
| endrekursiv | iterativ |
| baumrekursiv | baumrekursiv |
wo wuerdet die Tree- bzw. Baumrekursion einordnen?
edit: ach je, steht ja auf der naechsten Seite…
wahrscheinlich muss man sich das einfach merken, dass wenn der typ der prozedur endrekursiv ist, der typ des prozesses iterativ ist.
wtf? Seite im Script?
und ist nicht Prozedur = Algorithmus, Prozess = Ausgeführte Instanz? (Abstrakt gedacht ^^)
Ich geh mal davon aus, dass der Prozess, der ausgefuehrt wird, gewisse Optimierungen vom Compiler/Interpreter verpasst bekommt und daher die Rekursion bei der endrekursiven Variante verloren geht weil immer wieder der Speicher das vorhergehenden Aufrufs verwendet werden kann und sich der Prozess verhaelt, als ob er iterativ waere, obwohls der Code auf dem Papier erstmal nicht ist.
[edit]
Papier…sos laesst grueszen 
[/edit]
Kapitel 1.2 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html
und Aufgabe 3 hier:
http://www8.informatik.uni-erlangen.de/IMMD8/Lectures/Algo2/Uebung/SS2006/algo_120_03-05.pdf
Naja ich denk rekursive Prozedur bedeutet dass die Funktion sich selbst aufruft.
Rekursiver Prozess bedeutet, dass der Stack waechst bis zum Rekursionsende und dann wieder schrumpft.
Dass bei den endrekursiven Prozeduren der Stack nicht waechst hat nicht so sehr mit optimierung was zu tun sondern eher, dass das erste was die Funktion aufruft sie selbst ist und es somit keine Gelegenheit gab was auf den Stack zu legen.
Also ich weiss etz net obs über Prolog oder Scheme geht…aber:
in meinem Prolog-Buch steht:
Wenn Sie jetzt meinen, das was ich hier schrieb sei keine Prozedur, dann denken Sie nochmal drüber nach was eine Prozedur eigentlich ist. Ist eine Prozedur ein Algorithmus? Nein, sicherlich nicht…
Nehmt das ganze nicht so ernst. IIRC ist schon sowas in die Richtung gemeint:
Prozedur ist ne Implementation bzw Ausprägung eines Algorithmus und der “Prozess” ist ein Modell für die Ausführung dieser Prozedur.
Das ist auf dem Niveau alles noch verdammt schwammig und nützt imo auch nichts. Wenn ich mich recht entsinne soll das dem Leser so ein bisschen “operational semantics” (also wie das auf ner abstrakten Maschine so ablaufen würde; ihr kennt doch solche Vergleiche mit Turingmaschinen um ein Programm “mathematisch” zu fassen aus ThI) zu seinen Implementierungen geben, mehr nicht.
Generell ist das eine Funktion wie jede andere: Parameter pushen, Returnadresse pushen, Framepointer sichern, Platz fuer lokale Variablen schaffen gehoert dazu. Wenn das weggelassen wird, weil man es kann, ist das eine Optimierung. Scheme verlangt in Sprachstandard afair, dass die Interpreter das automatisch machen.
In C kommts auf den Compiler an.
Darauf wollte ich in meinem ersten Beitrag auch hinaus.
so hab nun auch mal eine frage:
Unterschiede let let* und letrec
let: variable wird initialisiert/geändert, aber erst nach der let-Anweisung:
(let (a 1)
let((a 2)(b a)
(* a b)))ergibt also 2, da a den Wert “2” erst nach der Zuweisung von a annimmt, richtig???
(let ((a 1))
(let* ((a 2)(b a))
(* a b)))ergibt 4, da a zuerst den Wert “2” annimmt, und dann b auch den wert annimmt…, richtig??? (also der STK stimmt mir zu ;))
aber was macht letrec???
es ist eigentlich das gleiche wie let*, nur folgendes funktioniert eben bei letrec nicht:
(let ((a 1))
(letrec ((b a)(a 2))
(* a b)))kommt eben “undefined” (vgl. Übung 3-3)
heißt das so viel wie letrec ist so richtig pedantisch und macht stur von links nach rechts?
und let* macht das zwar auch, aber wenn er was sucht, geht er einfach weiter ???
HILFE!!!
Ich geb mal die Transformationen von let* und letrec an, damit sollten solche Aufgaben ein Kinderspiel sein (vorrausgesetzt man ist mit let und set! vertraut :>):
(let* ((a1 b1) (as bs) …) body) <=> (let ((a1 b1)) (let* ((as bs) …) body))
Heißt konkret:
(let ((a 1))
(let* ((a 2)(b a))
(* a b)))ist äquivalent zu
(let ((a 1))
(let ((a 2))
(let ((b a))
(* a b)))(letrec ((as bs) …) body) <=> (let ((as #undefined) …) (set! as bs) … body)
Also konkret
(let ((a 1))
(letrec ((b a)(a 2))
(* a b)))ist äquivalent zu
(let ((a 1))
(let ((b #undefined) (a #undefined))
(set! b a) (set! a 2)
(* a b)))Aus R5RS letrec-semantics: “The variables are bound to fresh locations holding undefined values, the inits are evaluated in the resulting environment (in some unspecified order), each variable is assigned to the result of the corresponding init, the body is evaluated in the resulting evironment, and the values of the last expression in body is returned. Each binding of a variable has the entier letrec-expression as its region, making it possible to define mutually recursive procedures.
One restriction on letrec is very important: it must be possible to evaluate each init without assigning or refering to the value of any variable (was hier passiert!). If this restriction is violated, then it is an error.”
Diese Einschränkung rührt natürlich von call-by-value bzw applikativer Reduktionsordnung her. Kann man sich recht leicht merken wenn man weiß das im letrec eben keine spezifizierte Ordnung zwischen den Definitionen besteht, also ist das eigentlich nur für inits brauchbar die lambda-Ausdrücke oder ähnliches sind und dafür ists ja auch gedacht.
Denke das sollte jetzt doch klarer werden. Wurde das in den Übungen nie angesprochen?!
Nochmal kurz zusammengefasst:
let für “unabhängige” bindings
let* für “sequentiell-abhängige” bindings, realisiert durch verschachtelte lets
letrec für “rekursiv-abhängige” bindings, realisiert durch Erzeugen von temporären (undefinierten Bindungen) die später (in undefinierter Reihenfolge) abgesättigt werden. (Hrhr das klingt wie dyn Binden in SoS ^^)
Soweit ich mich entsinnen kann (auch und vor allem) was die Vorlesung angeht wurden die ganzen Befehle nie wirklich vorgeführt, also deren Arbeitsweise oder genaue Spezifikation gezeit. Ich hab daheim eigentlich immer erst mal die Hilfe vom DrScheme angeworfen oder im Internet nachgeschaut… Von daher vermute ich, dass wir sowas nicht explizit gemacht haben!
Ohh man, was hat Stoyan dann eigentlich explizit gemacht?! oO
Wenns noch mehr solche Unklarheiten gibt, dann fragt unbedingt. Es gibt nichts dümmeres als wenn man in der Klausur mit ner ungewöhnlichen Anwendung konfrontiert wird und nur schwammige Vorstellungen von der Semantik hat.
Das gilt übrigens auch für Prolog!
Bei Scheme is ziemlich unklar was verlangt is und was nicht…in diversen Uebungsloesungen kommen sie dann schon mal an mit Sachen/Prozeduren die man so aus dem Skript nicht kennt.
Ein anderes Beispiel waeren die ganzen Stringfunktionen…
Zu Stringfunktionen nur eins: string->list, mach deine Funktion auf der Listen von Zeichen und dann wieder list->string. Würde sogar sagen Listenfunktionen bzw Funktionen auf cons-Paaren sind das einzige was für die Klausur wirklich von Bedeutung ist.