Kennt sich jeman mit python aus...?

[new Account()]

Wo hier gerade Python Thema des Threads ist, sei auf Stackless Python verwiesen.

Und Python Interpreter und Stackless Python zusammen … ?
War auch nur ein Hinweis, dass letztendlich alles rekursiv arbeitet.

Die Frage ist, ob du dann wirklich auch alle (versuchst) zu berechnen, d.h. eine Endlosrekursion machst, die nicht aufhört.
Die Programmiersprache gaukelt dir das vielleicht in der Definition vor, aber wie auch immer das in Scheme umgesetzt wird, in einer anderen funktionalen Sprache wird einfach lazy evaluation gemacht. Die Abstraktion kann man sich in (fast) jeder Sprache bauen.

Von daher könnte immer noch sagen, dass zwar theoretische Rekursion OK ist, frei laufende Rekursion aber tdm immer noch keinen Sinn macht.
Dann kamen mir aber rekursiv definierte (Hardware) Timer. Die machen definitiv Sinn, sind aber tatsächlich rekursiv.

Macht es Sinn die generelle Unsinnigkeit für stackbasierte Rekursion zu beschränken?

 

[andy_m4]

War auch nur ein Hinweis, dass letztendlich alles rekursiv arbeitet.

Stimmt aber nicht.

Die Frage ist, ob du dann wirklich auch alle (versuchst) zu berechnen, d.h. eine Endlosrekursion machst, die nicht aufhört.

Theoretisch könnte man es machen, hat aber keinen Sinn. Vor allem weil Du ab gewissen Zahlengrößen Probleme bekommen wirst die darzustellen. Eine "endlos große Zahl" braucht halt auch endlos großen Speicher.
Und das ist hier das primärproblem und nicht das Dir Stackspace ausgehen könnte (ja; auch das kann passieren, muss aber nicht).

Die Programmiersprache gaukelt dir das vielleicht in der Definition vor,

Ne Programmiersprache gaukelt Dir ohnehin was vor. Letztlich spricht die CPU nur Maschinensprache. Und selbst die gaukelt Dir was vor, da einzelne CPU-Instruktions oftmals noch mal intern in Mikroprogrammen umgesetzt werden.

aber wie auch immer das in Scheme umgesetzt wird, in einer anderen funktionalen Sprache wird einfach lazy evaluation gemacht. Die Abstraktion kann man sich in (fast) jeder Sprache bauen.

Ja. Kann man. Aber das ist auch gar nicht der Punkt.
Das sind alles Nebenkriegsschauplätze die sich aus der Diskussion um die Rekursion ergeben haben.

Von daher könnte immer noch sagen, dass zwar theoretische Rekursion OK ist, frei laufende Rekursion aber tdm immer noch keinen Sinn macht.

Ob etwas Sinn macht oder nicht, darüber kann man trefflich streiten. Genauso wie man darüber streiten kann, ob while-Schleifen Sinn machen (ich brauch sie z.B. nie; egal ob endlos oder nicht).
Es ging mir auch nicht um ein besser oder schlechter. Es ging mir um Deine Aussage die so in ihrer Verallgemeinerung einfach nicht haltbar ist.

Das es dann in einer ganz konkreten Situation Sinn machen kann, eher auf das Eine oder auf das Andere zu setzen, bleibt ja davon unberührt.

 

[new Account()]

Theoretisch könnte man es machen, hat aber keinen Sinn.

Genau nichts anderes habe ich gesagt.

Eine "endlos große Zahl" braucht halt auch endlos großen Speicher.
Und das ist hier das primärproblem und nicht das Dir Stackspace ausgehen könnte (ja; auch das kann passieren, muss aber nicht).

Dass der Stackspace ausgeht, ist immer ein Problem. Oder hat man plötzlich beim Stack kein Problem mehr, wenn man das Ausgabeproblem nicht beachtet?

Stimmt aber nicht.

Auf Turing-Maschine-orientiertes Rechnen bezogen auch nicht?


-> Stackbasierte Rekursion ist unsinnig?

 

[andy_m4]

Ich fang mal von unten nach oben an, weil es für den Erklären besser ist. :-)

Stackbasierte Rekursion ist unsinnig?

Wie gesagt. Man muss Arbeit mit Stack und Rekursion auseinanderhalten.

Zunächst einmal ist RAM als Stack zu nutzen in allererster Linie ein Design-Pattern. Also eine Art, wie man RAM nutzt.

(Das muss nicht mal von der Hardware/CPU vorgesehen sein (obwohl es heute üblich ist CPU-Instructions dafür zu haben; aber nicht weil es anders nicht ginge, sondern weil es ein häufiges Pattern ist und es Performancevorteile bringt dies dann auch "in Hardware" zu unterstützen.)

Es ist eine einfache Variante der relativen Adressierung. So in der Art, den letzten Wert den Du da reinschreibst, ist auch der erste Wert der bei einem Lesevorgang wieder ausgelesen wird.

Eine beliebte Anwendung dafür sind Funktionsaufrufe. DIe Argumente, die der Funktion übergeben werden sollen werden auf dem Stack gespeichert und dann halt in umgekehrter Reihenfolge von der Funktion selbst wieder gelesen.

Durch die relative Art der Adressierung gibt es auch keine Konflikte, wenn man andere Funktionen aufruft oder (wie bei einer Rekursion die Funktion sich selbst, weil jeder seine eigene Kopie der Argumente hat und auf die trotzdem in gleicher Weise zugreifen kann ohne sich mit verschiedenen Adressen herumschlagen zu müssen.

Man hat aber ein Problem. Dadurch, dass jeder Funktionsaufruf eine eigene Kopie der Argumente vorhält, kann es bei einer Verkettung von Funktionsaufrufen (die müssen nicht zwangsläufig rekursiv sein aber hier baut man am ehesten Code der in der Praxis zu Problemen führt), dass eben einem der RAM oder von mir aus auch nur der Speicher der als Stack vorgesehen ist aus geht.

Das einem speziell Stackspeicher ausgehen kann, ist aber eben auch nur ein Problem, wenn man Funktionen wie in der hier beschriebenen Weise umsetzt. Man muss es aber nicht so handhaben das man Funktionsparameter über den Stack übergibt. Man kann es natürlich auch anders machen.

Aber auch dann hast Du halt ein Problem mit dem RAM-Verbrauch, wenn Du die Eigenschaft "jeder Funktionsaufruf hat seine eigene Kopie der Argumente" erhalten willst.

Der Ansatz das zu lösen wäre eben, diese Eigenschaft nicht oder eben nicht in allen Fällen zuzusichern.

Beispiel Fakultätsberechnung (das ist immer so das klassische Beispiel, wenns darum geht, Rekursion zu vermitteln; wohl auch das es gerne mathematisch rekursiv definitiert wird).

function fakultät(n) {
  if (n==0)
      return 1;
    else
      return n*fakultät(n-1);
}

Wenn Du faktultät(10) aufrufst, werden halt jeweils die Argumentwerte für n im Speicher vorgehalten (also konkret die Zahlen 0 bis 10), obwohls ja für die eigentliche Berechnung gar keine Notwendigkeit gibt diese Werte zu speichern. Würde man ja bei einer iterativen Umsetzung der Funktion, also via Schleife, auch nicht machen. Und genau hier könnte ein Compiler ansetzen, in dem er quasi eine rekursive Variante in die äquivalente iterative Variante umformt.
Damit könnte man die elegante rekursive Formulierung im Quelltext beibehalten ohne in Speicherverbrauchsprobleme zu laufen.

Und tatsächlich bieten verschiedene Compiler (i.d.R. aus dem funktionalen Umfeld) solche Optimierungen an. Teilweise automatisch (was den Programmierer aber dann auch in die Pflicht nimmt ggf. drauf zu achten). Teilweise auch "auf Hinweis".

Stackbasierte Rekursion (ohne Optimierung) ist aber natürlich trotzdem nicht per se unsinnig. Denn in vielen Fällen will man ja genau die Argumente bzw. Zustände speichern. Und Stacks sind oftmals eine hinreichend gute Möglichkeit das zu tun.
Das typische Beispiel, was dann immer kommt ist der Backtracking-Alorithmus.

Auf Turing-Maschine-orientiertes Rechnen bezogen auch nicht?

Ähm die Turing-Maschine ist lediglich ein mathematisches Modell für die Berechenbarkeit von Alorithmen und ohnehin keine Vorlage für eine technische Umsetzung.
Wenn man sagt, dass eine Programmiersprache oder ein System turing-vollständig ist, meint das, dass man dort alle Probleme lösen kann die auch auf die Turing-Maschine lösbar sind. Es heißt aber nicht, dass sie wie auf der Turing-Maschine gelöst werden.

Genau nichts anderes habe ich gesagt.

Es macht keinen Sinn wenn Du immer Sachen aus dem Kontext rausreißt und dann bewertest.

 

[new Account()]

(Das muss nicht mal von der Hardware/CPU vorgesehen sein (obwohl es heute üblich ist CPU-Instructions dafür zu haben; aber nicht weil es anders nicht ginge, sondern weil es ein häufiges Pattern ist und es Performancevorteile bringt dies dann auch "in Hardware" zu unterstützen.)

Gerade weil es üblich ist, beschränke ich mich auf diese Sichtweise. Der Rest hat nichts mit dem Statement/These zu tun:

Damit könnte man die elegante rekursive Formulierung im Quelltext beibehalten ohne in Speicherverbrauchsprobleme zu laufen.

Und damit hat man auch keine Rekursion mehr.

das man Funktionsparameter über den Stack übergibt. Man kann es natürlich auch anders machen.

Dann ist es aber nicht mehr stackbasiert. Die Umsetzung, die den Stack aber ablöst und endlos Rekursion sinnvoll macht, würde ich gern sehen.

Nochmal als Zusammenfassung:
generell nicht endende Rekursion als unsinnig zu bezeichnen, ist nicht O.K., da z.B. vor allem in der Theorie diese wichtig ist (wie z.B., dass man in Scheme oder in der Mathematik diese definieren kann).
Die Sinnigkeit endlos-Rekursion in einer beliebigen technischen Umsetzung (d.h. wo sie wirklich präsent ist, d.h. nicht irgendwie wegoptimiert wird, o.ä.) ist immer noch nicht geklärt. (Mein Timerbeispiel ist, wie ich fälschlicherweise behauptet habe, nach meinem Verständnis eigentlich keine Rekursion - bin mir aber nicht 100% sicher)
Wie soll das überhaupt aussehen? Das Programm müsste ewig laufen - d.h. ich schalte heut meinen Computer ein, starte das Programm und stoppe es nie (sonst würde es ja keine Endlosrekursion machen).

Die Unsinnigkeit von endlos Rekursion mit einer stackbasierten Umsetzung ist auch noch nicht widerlegt: den Stack zu umgehen, oder die Rekursion wegzunehmen widerlegt dies nicht.

Hinweis 1:

Stackbasierte Rekursion (ohne Optimierung) ist aber natürlich trotzdem nicht per se unsinnig. Denn in vielen Fällen will man ja genau die Argumente bzw. Zustände speichern. Und Stacks sind oftmals eine hinreichend gute Möglichkeit das zu tun.
Das typische Beispiel, was dann immer kommt ist der Backtracking-Alorithmus.

Es geht immer noch um ENDLOS laufende Rekursion. Der Backtracking Algorithmus würde garnicht funktionieren, wenn die Rekursion endlos tief gehen würde.

Hinweis 2:
Ein konkretes Beispiel, das die Sinnigkeit zeigt, reicht aus.

Anmerkung: Deine Ausführungen sind sehr interessant, aber irgendwie bleiben die nicht beim Thema.

 

[andy_m4]

Gerade weil es üblich ist, beschränke ich mich auf diese Sichtweise.

Kann man machen. Ist aber nicht verkehrt, wenn man darauf hinweist, dass es eben nicht allgemeingültig ist.
Und das soll ja auch kein wie auch immer gearteter Vorwurf sein. Den (als Ergänzung gedachten) Hinweis habe ich ja gegeben und damit ist die "Mission" erfüllt. :-)

Und damit hat man auch keine Rekursion mehr.

Stimmt. Ist aber unerheblich. Den die Vorgehensweise die der Quelltext beschreibst ist ohnehin nie, wie sie dann in der Hardware stattfindet.
Genau das ist ja auch der Sinn einer (höheren) Programmiersprache. Das man eben Dinge auf einem (höherem/anderen) Level formulieren kann und dem Compiler/Interpreter die konkrete Umsetzung überlässt.

Dann ist es aber nicht mehr stackbasiert.

Hat ja auch keiner behauptet. Aber das war ja auch gar nicht der Punkt.
Ich finde solche Einwürfe die sich irgendeinen einzelnen Aspekt rauspicken auch immer eher verwirrend. Ich hab dann immer das Gefühl, dass Du gar nicht verstanden hast, was Du sagen willst und die Einzelaspekte auch so teilweise keinen wirklichen Sinn ergeben.

Wie hier eben. Es ging nicht um stackbasiert oder nicht. Es ging um Rekursion und die Tatsache, dass Rekursion nicht automatisch den Stack belasten muss. Sozusagen um eine Auftrennung der Konzepte Stack und Rekursion. Weil sie halt nicht zusammen gehören, auch wenn es so scheint weil sie gerade im Mainstream häufig so anzutreffen sind.

Das worauf ich hinaus wollte ist das aufzubrechen und zu zeigen, dass es verschiedene Dinge sind und man sie zwar zusammenpacken kann aber nicht muss.

Die Umsetzung, die den Stack aber ablöst und endlos Rekursion sinnvoll macht, würde ich gern sehen.

Naja sinnvoll ist immer so ne Frage. Ich meine, ich hatte ja zu einer Endlos-Rekursion ein Beispiel gegeben. Und in Scheme hast Du halt auch kein Äquivalent Wirkliches zu while, weshalb Du zur Rekursion greifen musst (wobei die Abwesenheit von while auch nicht als Makel empfunden wird; man braucht es nicht; auch nicht im Falle einer Endlosschleife).

Ansonsten muss man sich bei solchen Endlos-Schleifen (egal ob iterativ oder rekursiv) eigentlich grundlegender fragen, ob die sinnvoll ist. Denn kein Code soll ja wirklich bis in alle Ewigkeit laufen. Irgendeine Abbruchbedingung hat man ja zumindest indirekt immer. Oftmals sind Lösungen mit Endlosschleifen eher ein Hack.

Und wenn man sie dann doch nimmt, sollte man überlegen, wie man es am besten umsetzt.
Eine Umsetzugn a-la while true ist natürlich auch immer so ein bisschen Missbrauch von while, da man einfach ne Bedingung setzt die in jedem Fall wahr ist.

Ich würde dahin tendieren für Endlosschleifen ein generisches Makro zu schreiben (jetzt mal unabhängig davon, ob man es iterativ oder rekursiv löst):

(define-syntax-rule (infinite-loop body ...)
  (let loop ()
    body
    ...
    (loop)))

Damit kann man nu an benötigter Stelle einfach schreiben:

(infinite-loop 
  (do)
  (somthing))

und es geht klar und unmissverständlich aus dem Quelltext hervor, dass hier eine Endlosschleife abgearbeitet wird.

Und das wäre eigentlich an der Stelle auch noch der wichtigere (zumindest aber genauso wichtige) Hinweis. Das man sich bemüht den Quelltext so zu schreiben, dass klar wird, was da geschieht. Notfalls auch mit Kommentaren.

Die Sinnigkeit endlos-Rekursion in einer beliebigen technischen Umsetzung (d.h. wo sie wirklich präsent ist, d.h. nicht irgendwie wegoptimiert wird, o.ä.) ist immer noch nicht geklärt.

Ich hoffe im Rahmen dieses Postings ist die Frage geklärt.

Ansonsten ist es mit Sinnfragen halt immer ein wenig kompliziert. Ich kann genauso gut argumentieren, dass man keine while-Schleifen braucht und tatsächlich wird sich auch kein Problem konstruieren lassen, welches zwingend auf while angewiesen ist.

Abseits davon ist Sinn aber trotzdem noch unscharf definiert.
Präziser meint es ja eigentlich, welche Vor- und Nachteile haben die jeweiligen Implementationsvarianten insbesondere hinblicklich der Kriterien Performance, Speicherplatzverbrauch, Aufwand der Implementierung, Lesbarkeit des Codes.

Im Allgemeinen wird keiner der beiden Lösungen (Endlosschleife vs. Endlosrekursion) die "sinnvollere" Wahl sein.
Viel mehr manifestiert sich sich ne Antwort dann, wenn man festlegt, in welcher Programmiersprache man sich bewegt und/oder welchen Skill der Programmierer hat.
Und bei Scheme endet das halt dann bei Rekursion. Bei beispielsweise Java würde dagegen die Lösung eher Schleife heißen (wegen Stacküberlaufgefahr).

(Mein Timerbeispiel ist, wie ich fälschlicherweise behauptet habe, nach meinem Verständnis eigentlich keine Rekursion - bin mir aber nicht 100% sicher)

Eher nicht. Der Hardware-Timer ist ja eher nur ein Zähler der gekoppelt an ein ein gleichmäßig schwingendes System (Oszillator). Bei jedem "Peak" wird sozusagen der Zähler um eins hochgezählt.

Wie soll das überhaupt aussehen? Das Programm müsste ewig laufen - d.h. ich schalte heut meinen Computer ein, starte das Programm und stoppe es nie (sonst würde es ja keine Endlosrekursion machen).

Ja. Das Problem der Unendlichkeit habe ich ja weiter oben diskutiert. Das es sie ja eigentlich nicht gibt und das es eher ein Hilfskonstrukt für die Problemlösung ist, aber es nicht darum geht, dass etwas unendlich mal ausgeführt werden soll bzw. unendlich lange läuft.

Bezogen auf den Hardwaretimer (der aber ohne Rekursion auskommt) ist es halt so: Kein Strom -> kein Zählvorgang
Allerdings haben alle modernen PCs heutzutage eine Batterie die u.a. halt auch die Uhr am laufen hält.

Es geht immer noch um ENDLOS laufende Rekursion. Der Backtracking Algorithmus würde garnicht funktionieren, wenn die Rekursion endlos tief gehen würde.

Auch hier wieder die Thematik verfehlt. Es ging bei der Erläuterung gar nicht um Unendlichkeit. Es war ein Beispiel, für eine Rekursion mit Zustandsspeicherung Sinn macht.

Anmerkung: Deine Ausführungen sind sehr interessant, aber irgendwie bleiben die nicht beim Thema.

Mir war auch nicht ganz klar, worum es Dir ging weil eben viele Fragen kamen, die damit nur indirekt was zu tun hatten oder wo Verständnisprobleme zu sein schienen.
Und die Frage nach dem Sinn würde ja eigentlich schon längst beantwortet. Ich hab versucht es nochmals in diesem Posting klar zu machen.