Not logged in. · Lost password · Register

phil
Member since May 2006
34 posts
Subject: 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.
This post was edited on 2006-09-14, 16:59 by phil.
_MC_
Member since Jun 2005
416 posts
wtf? Seite im Script?
und ist nicht Prozedur = Algorithmus, Prozess = Ausgeführte Instanz? (Abstrakt gedacht ^^)
chrham
Member since Oct 2005
208 posts
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]
This post was edited on 2006-09-14, 23:01 by chrham.
phil
Member since May 2006
34 posts
In reply to post #2
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/Algo…

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.
This post was edited on 2006-09-14, 23:06 by phil.
MuMu
Member since Oct 2005
305 posts
Also ich weiss etz net obs über Prolog oder Scheme geht...aber:

Prozedur = Algorithmus, Prozess = Ausgeführte Instanz? (

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.....
andy
your local λ-dealer
Member since Oct 2005
248 posts
In reply to post #4
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.
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 2 times, last on 2006-09-15, 00:05 by andy.
chrham
Member since Oct 2005
208 posts
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.
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.
Prozedur ist ne Implementation bzw Ausprägung eines Algorithmus und der "Prozess" ist ein Modell für die Ausführung dieser Prozedur.
Darauf wollte ich in meinem ersten Beitrag auch hinaus.
MuMu
Member since Oct 2005
305 posts
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!!!
andy
your local λ-dealer
Member since Oct 2005
248 posts
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 ^^)
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 4 times, last on 2006-09-15, 17:26 by andy.
vielleicht
Philipp Caliebe
Member since Oct 2005
259 posts
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!
andy
your local λ-dealer
Member since Oct 2005
248 posts
Quote by vielleicht:
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!
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited on 2006-09-15, 17:22 by andy.
Comrade
THI-Survivor
Avatar
Member since Nov 2005
623 posts
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...
"My uzi weighs a ton..."
andy
your local λ-dealer
Member since Oct 2005
248 posts
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.
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited on 2006-09-15, 17:43 by andy.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen