Geht es auch ohne "goto"?



  • Morgen beschreibe ich die Problematik im Detail.

    Jetzt nur mal soviel, ich benötige während einer Rekursion den vollen Zugriff auf den Stack und muss je nach Situation auch im Stack "umherspringen". Das bedeutet dass ein Thread von Rekursionstiefe 10 direkt in Rekursionstiefe 4 springen muss, ohne des Stack abzubauen.

    Man kann es zwar biegen und brechen mit bestimmten Systemfunktionen (glaube ich). Aber wäre es hier nicht besser einen eigenen Stack in Form eines Arrays zu verwalten und statt rekursiv zu rechnen, iterativ zu rechnen.

    Das bedeutet die komplette Berechnung in eine "grosse" Schleife zu packen und zwischen den Labels zu springen. Den Abbau eines Stack zu emulieren ist ja kein Problem. Man muss nur mittels switch-case Return-Points einrichten.

    Das ganze klappt auch und ist im Bereich Dynamic-Tree-Splitting eine bekannte Technik zur Parallelisierung von Suchalgorithmen in Spielen wie Schach, Shogi oder Go.

    Nur ist meine Frage, ob vielleicht den Experten hier bessere, respektive elegantere (und performante) Lösungen für dieses Problem bekannt sind?

    Wäre nett hier ein paar Meinungen zum Thema "Entrekursivierung" einzuholen.

    Viele Grüße und gute nacht,
    T.

    PS. Morgen gibts ein Beispiel...



  • denk stack pointer kann man doch einfach per asm setzen oder 😕



  • Es gibt eine Header Datei names setjmp.h. Mit diesen Funktionen kann man in den Sacks herumspringen. Habe jedoch keine Erfahrungen mit diesen Funktionen.



  • Morgen beschreibe ich die Problematik im Detail.

    Dann warte doch solange.

    Nur ist meine Frage, ob vielleicht den Experten hier bessere, respektive elegantere (und performante) Lösungen für dieses Problem bekannt sind?

    Du hast das Problem nicht beschrieben, sondern nur gesagt, was du brauchst fuer eine bestimmte Implementation, die vorwiegend in deinem Kopf existiert.

    Wäre nett hier ein paar Meinungen zum Thema "Entrekursivierung" einzuholen.

    Wie waere es mit Endrekursion ueber Einbettung.

    Das ganze klappt auch und ist im Bereich Dynamic-Tree-Splitting eine bekannte Technik zur Parallelisierung von Suchalgorithmen in Spielen wie Schach, Shogi oder Go.

    Es gibt ein Paper, in der Alpha-Beta-Suche mittels semi-impliziter Parallelisierung in Haskell realisiert wurde. Deine erwaehnte "Technik" ist mir voellig unbekannt.



  • also ich hab nicht wirklich eine ahnung, was dein programm können muss, aber wie mein infolehrer zu sagen pflegte: es geht immer ohne goto-befehl.
    falls du verschiedene, immer wieder auftretende zustände hast, ist im allgemeinen das einfachste ein sog. automat. man macht eine endlosschleife und überprüft per einfacher int-variable in welchem zustand man sich befindet und geht dann in den dazugehörigen arbeitsschritt rein. vllt hilft dir das ja



  • Azrael89 schrieb:

    ohne goto

    Azrael89 schrieb:

    überprüft per einfacher int-variable in welchem zustand man sich befindet

    bool fertig=false;
    do{
      switch(i){
        case 0: 
          cout<<"hello";
          i-=-1;
          break;
        case 1: 
          cout<<' ';
          i-=-1;
          break;
        case 2: 
          cout<<"world";
          i-=-1;
          break;
        case 3:
          fertig=true;
          break;
      }
    }while(!fertig);
    


  • volkard schrieb:

    bool fertig=false;
    do{
      switch(i){
        case 0: 
          cout<<"hello";
          fertig-=-1;
          break;
        case 1: 
          cout<<' ';
          fertig-=-1;
          break;
        case 2: 
          cout<<"world";
          fertig-=-1;
          break;
        case 3:
          fertig=true;
          fertig-=-1;
          break;
      }
    }while(!fertig);
    

    Ich vermisse die Pointe. Ist das jetzt witzig, C++ Trashcode hier reinzustellen? 🙄



  • pointercrash() schrieb:

    volkard schrieb:

    int i=0;
    bool fertig=false;
    do{
      switch(i){
        case 0: 
          cout<<"hello";
          i-=-1;
          break;
        case 1: 
          cout<<' ';
          i-=-1;
          break;
        case 2: 
          cout<<"world";
          i-=-1;
          break;
        case 3:
          fertig=true;
          break;
      }
    }while(!fertig);
    

    Ich vermisse die Pointe. Ist das jetzt witzig, C++ Trashcode hier reinzustellen? 🙄

    Ich habe wie vorgeschlagen den Instruction-Pointer durch einen int ersetzt, goto durch ändern des status. und mal geschaut, wie es sich anfühlt.
    aber ein Programmierfehlerchen war drin, das sich eingeschlichen hatte, als ich den Code an die Zielgruppe angepaßt hatte, und die pascaloide Schleife drumgefummelt hatte. Ich machs mal raus.



  • volkard schrieb:

    ... goto durch ändern des status. und mal geschaut, wie es sich anfühlt.
    aber ein Programmierfehlerchen war drin, das sich eingeschlichen hatte, als ich den Code an die Zielgruppe angepaßt hatte, und die pascaloide Schleife drumgefummelt hatte. Ich machs mal raus.

    Achnee, jetzt ist die Zielgruppe schuld, daß Du nichtmal mehr ein paar korrekte Zeilen in C hinkriegst? 🙄
    Gemeint hattest Du wohl das da:

    #include <stdbool.h>
    
    int main(void)
    {
    	int i=0;
    	bool fertig=false;
    do{
      switch(i){
        case 0:
          printf("hello");
          i-=-1;
          break;
        case 1:
          printf(" ");
          i-=-1;
          break;
        case 2:
          printf("world");
          i-=-1;
          break;
        case 3:
          fertig=true;
          break;
      }
    }while(!fertig); 
    }
    

    Jetzt sind wir verdammt nah an der kontrovers diskutierten switch- Schleife, was? 😃
    OK, eine FSM ist zumindest eine gute Idee, aber ich stricke mir die eher aus "gefädelten" Pointern zusammen und spare mir die Schwitzer- Käse- Konstruktion mit Schleifchen.

    void functionHello(void);
    void functionWorld(void);
    static void (*nextfunction) (void) = NULL;
    static char end = 0;
    static int counter = 0;
    
    void functionHello(void)
    {
    	printf("Hello ");
    	nextfunction = functionWorld;
    }
    void functionWorld(void)
    {
    	printf("World!\n");
    	nextfunction = functionHello;
    	counter++;
    	if (counter >= 3)
    	{
    		printf("hangup\n");
    		end = 1;
    	}
    }
    
    int main(int argc, char *argv[])
    {
    	nextfunction = functionHello;
    	while(!end) nextfunction();
    }
    

    Spart die Vergleicherei, ist performanter und läßt sich ganz prima in Interrupts unterbringen, was mir sehr wichtig ist. 😉
    EDIT: Achja, der Stack wird dabei auch nur um eine Return- Adresse belastet 🙂



  • Wobei auch Du an die Zielguppe angepaßt hast und end dazugefrickelt hast, statt den Folgestatus auf NULL oder &functionEnd zu setzen.



  • void *functionWorld(void){
      printf("World!\n");
      return 0;
    }
    
    void *functionHello(void){
      printf("Hello ");
      return functionWorld;
    }
    
    int main(void){
      void (*call)(void) = functionHello;
      while((call = call()));
      return 0;
    }
    


  • wow sind da viele fehler drin 😡



  • madLol schrieb:

    wow sind da viele fehler drin 😡

    Ich nehme an, Du meinst die hier.

    #include<stdio.h>
    
    void*(*functionWorld(void))(void){
      printf("World!\n");
      return 0;
    }
    
    void*(*functionHello(void))(void){
      printf("Hello ");
      return functionWorld;
    }
    
    int main(void){
      void*(*call)(void) = functionHello;
      while((call = call()));
      return 0;
    }
    

    Ja, jetzt ist es konzeptionell sehr einfach. Geradezu enorm einfach. Nur syntaktisch ist damals ein kleines Unglück passiert.



  • volkard schrieb:

    Wobei auch Du an die Zielguppe angepaßt hast und end dazugefrickelt hast, statt den Folgestatus auf NULL oder &functionEnd zu setzen.

    Ganz klares Jein. 😃
    Eine voll ausgebaute FSM hat Eingänge, Zustände und Ausgänge. Rein theoretisch besser, man mixt das nicht und geht über eine Zustandstabelle. Da aber FSM- Tables überwiegend aus "don't care"s bestehen, dachte ich mir, ich laß' das als exit drin. Darf jeder drüber denken, wie er will. War eh' nur als funktionsfähige Spielwiese gedacht 😃



  • Hallo zusammen,

    ich weiß ja nicht wer diese Gerücht in die Welt gesetzt hat,
    daß mein kein goto verwenden darf ...

    Ich finde, es gibt nichts einfacheres als den goto Befehl.
    Er ist leicht zu verstehen, einfach zu lesen und unmissverständlich 😉

    Naja wer ums goto herum kommen möchte kann vieles andere verwenden,
    jedoch ist das manchmal umständlicher.

    Schön ist auch das switch case Konstrukt.
    Die Labels sind zwar sichtbar aber man hat diese Konstrukte
    (bisher) noch nicht zerredet.

    Was soll es, wenn goto das einfachste,
    übersichtlichste und schnellste ist nehme ich das natürlich.

    Viel Spass noch mit dem Thema,

    Gruß Frank



  • Frank Erdorf schrieb:

    Hallo zusammen,
    ich weiß ja nicht wer diese Gerücht in die Welt gesetzt hat,
    daß mein kein goto verwenden darf ...

    Das war nicht nur einer. Da haben viele mitgewirkt.
    Aber kannst als Schuldigen durchaus Dijkstra nennen, man wird selten widersprechen.
    http://www.u.arizona.edu/~rubinson/copyright_violations/Go_To_Considered_Harmful.html



  • Frank Erdorf schrieb:

    Naja wer ums goto herum kommen möchte kann vieles andere verwenden,jedoch ist das manchmal umständlicher.

    Nicht manchmal, sondern immer. Wenn man nicht solche Lachnummen wie E-Lab produziert, ist ein goto, das Stacks abräumt die coolste Möglichkeit, cleanups durchzuführen. Tut gar nicht weh, echt.

    Frank Erdorf schrieb:

    Schön ist auch das switch case Konstrukt.Die Labels sind zwar sichtbar aber man hat diese Konstrukte(bisher) noch nicht zerredet.

    Na, dann wird's ja echt Zeit, Schwitzkäse in die Tonne zu hauen oder doch nicht, weil's dann doch manchmal praktisch ist 😉



  • an sich sind goto-befehle und pointer ja auch ne tolle sache. nur wenn man ein paar seiten quelltext hat und den soll jmd anders weiterbearbeiten, machen goto-befehle das ziemlich kompliziert und sind deshalb in der industrie nicht gern gesehen(so hat man uns das in meiner firma verklickert^^).
    und pointer, ja, sind nützlich und oft unumgänglich, aber auch risikoreich, da man damit wenn mans ganz dumm anfängt wichtigen speicher überschreiben kann, was wohl nicht soo toll ist 😃 aber man sagt ja auch von globalen variablen, dass diese "gefährlich" sind, und trotzdem benutzt sie jeder.
    ergo, wenn das prg nur für dich ist und sich keiner damit auseinandersetzten muss, pack einfach rein, was du willst 😉



  • Azrael89 schrieb:

    an sich sind goto-befehle und pointer ja auch ne tolle sache. nur wenn man ein paar seiten quelltext hat und den soll jmd anders weiterbearbeiten, machen goto-befehle das ziemlich kompliziert und sind deshalb in der industrie nicht gern gesehen(so hat man uns das in meiner firma verklickert^^).

    das zeigt eher auf ein schlechtes design (aufteilen in funktionen) da "gotos" nur funktions lokal gültig sind ist das bei gutem design (eine funktion nicht länger als ne seite...) kein problem.

    Azrael89 schrieb:

    und pointer, ja, sind nützlich und oft unumgänglich, aber auch risikoreich, da man damit wenn mans ganz dumm anfängt wichtigen speicher überschreiben kann, was wohl nicht soo toll ist

    das kannst in c überall wo du "arrays" verwendest also so gut wie immer... das hat nur indirekt was mit pointern zu tun ist aber eine eigenheit der sprache und nicht der pointer wobei auch das wieder zusammen hängt.

    Azrael89 schrieb:

    aber man sagt ja auch von globalen variablen, dass diese "gefährlich" sind, und trotzdem benutzt sie jeder.

    manchmal kann man sie nicht vermeiden, dann kann/soll man sie auch verwenden zeigen idr. aber auch auf ein schlechtes design (vor allem wenn sie in zu großer anzahl vorkommen).

    fazit: es ist nicht das letzte glied in der kette schuld, sondern die gesamte kette und dann kanns auch das letzte glied nicht mehr raus reißen 😉

    @edit: ne buch seite hat idr 30 zeilen...
    @edit2: eher rein reißen 😃



  • So sehen zB die Return-Points einer iterativen Vertiefung aus, die in der Literatur als Rekursion implementiert wird:

    enum {
      PHASE_ROOT_START,
      PHASE_ROOT_LOOP,
      PHASE_ROOT_RESEARCH,
      PHASE_ROOT_UNDO,
      // more...
    };
    

    Das ist zB mein eigener Stack:

    struct my_stack_c {
      int phase;
      int depth;  // r
      int ply;    // r
      int check;  // r
      int node;   // r
      int alpha;  // r+w
      int beta;   // r
      int move;
      // more...
    };
    

    Und so sieht die Endlosschleife mit den Return-Points aus:

    while (true) {
        switch (stack[size].phase) {
    
        // root-search return points
    
        case PHASE_ROOT_START: goto ROOT_START;
        case PHASE_ROOT_LOOP: goto ROOT_LOOP;
        case PHASE_ROOT_RESEARCH: goto ROOT_RESEARCH;
        case PHASE_ROOT_UNDO: goto ROOT_UNDO;
    

    Die einzelnen Phasen werden mit Label angesprungen:

    ROOT_START:
        tree.search.nodes++;
        tree.search.current=0;
        tree.search.value_best=VALUE_NONE;
        goto ROOT_LOOP;
    
        // next phase
    
    ROOT_START:
        tree.search.nodes++;
        tree.search.current=0;
        tree.search.value_best=VALUE_NONE;
        goto ROOT_LOOP;
    

    Wenn ich die "Rekursion" beginne sieht es zB so aus:

    if (tree.search.iteration <= ITERATION_SORT) {
          stack[size].phase=PHASE_ROOT_UNDO;
          stack[size+1].depth=stack[size].depth+stack[size].extensions;
          stack[size+1].ply=stack[size].ply+1;
          stack[size+1].node=NODE_PV;
          stack[size+1].alpha=-stack[size].beta;
          stack[size+1].beta=-stack[size].alpha;
          goto TREE_START;
        }
    

    Und der Abbau des "Stacks" sieht zB so aus:

    TREE_START:
        size++;
        if (stack[size].depth <= 0) {
          value=search_q_w(tree, stack[size].ply, stack[size].alpha, stack[size].beta);
          size--;
          stack[size].value=-value;
          continue;
        }
    

    Ich versuche mal ein einfacheres Beispiel zu bauen und die analoge Rekursion dem gegenüberzustellen.

    Übrigens war/ist Hydra von Donninger nach dem iterativen Prinzip aufgebaut, um bis zu 64 Threads in einem Schachbaum rechnen zu lassen. Die Threads müssen ihren Stack nicht mehr abbauen, sondern können im Baum dort hinspringen, wo Arbeit ansteht. Im Falle eine Cuts verlassen alle beteiligten Threads den Subtree und verteilen sich wieder im Suchbaum.

    Dieses Young Brothers Wait Conzept (YBWC) ist rekursiv kaum zu implementieren. Ich habs jedenfalls nicht geschafft. 🙄

    Mir gefällt mein Code aber nicht sonderlich. Der Ansatz mit den Functions-Pointers sieht auch ganz interessant aus. Wenn die States allerdings zu klein sind, dann wird's möglicherweise teuer, da Funktionspointer vermutlich nicht in inline-Funktionen umgewandelt werden können?

    Oder bin ich jetzt am Thema vorbei? 😕

    Gruss
    T.


Log in to reply