Rekursive Funktionen

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Antworten
braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Rekursive Funktionen

Beitrag von braunbär »

Hallo!

ich habe gröbere Probleme mit einer rekursiven Funktion. Ich probiere schon eine Weile herum, das Ding hat in Delphi einwandfrei funktioniert, ich habe allerdings bei der Umstellung auf FPC das Ganze etwas umgestellt, sodass schon auch ein Fehler meinerseits vorliegen könnte. Aber ich schaffe es nicht, den Programmablauf im Debugger zu verfolgen.

Es handelt sich um einen einfachen Expression scanner mit den Funktionen expression, term und factor, wobei expression term aufruft, term ruft faktor auf, und faktor ruft, wenn eine öffnende Klammer gefunden wird, rekursiv wieder expression auf. Ab der zweiten Rekursionsstufe komme ich per Debugger nicht mehr per single Step in die rekursiv aufgerufene Funktion hinein, ich lande nach Drücken der F7 Taste nicht mehr am Anfang der aufgerufenen Funktion.

Bevor ich das Problem weiter verfolge, würde ich gerne wissen, ob Free Pascal irgend welche speziellen Compilereinstellungen braucht, um Rekursionen richtig zu kompilieren und anschließend richtig zu debuggen, das gab es, wenn ich mich richtig erinnere, in irgend welchen Versionen von Turbo Pascal. Wenn so etwas die Problemursache sein sollte, brauche ich nicht länger suchen. In der Dokumentation habe ich aber keinen Hinweis darauf gefunden, dass da irgend welche spezielle Einstellungen nötig wären.

Michl
Beiträge: 2505
Registriert: Di 19. Jun 2012, 12:54

Re: Rekursive Funktionen

Beitrag von Michl »

Ich habe mal das hier kurz getestet:

Code: Alles auswählen

program Project1;
 
  procedure Test(AValue: Integer);
  var
    i: Integer;
  begin
    i := AValue;
    if i > 0 then
      Test(i - 1);
  end;
 
begin
  Test(10);
end

Dabei kann ich problemlos mit dem Debugger in die Rekursion hineinsteppen. Mein System: 64bit Windows 7, Lazarus 1.9.0 r55664M FPC 3.0.4 i386-win32-win32/win64, Debugger GDB 7.7.1

AFAIK unter Windows hat sich der Stand noch nicht geändert, daß man mit einem 32bit Lazarus besser debuggen kann, als mit einem 64bit Lazarus bzw. FPC.

Du könntest jetzt noch andere GDB-Versionen testen und schauen, ob sich das Debugverhalten mit einer anderen Debuginfo verbessert (Projekt -> Projekteinstellungen -> Debuggen -> Debugging-Info-Typ ändern (Dwarf2 (-gw2) fuktioniert hier am besten)).

Code: Alles auswählen

type
  TLiveSelection = (lsMoney, lsChilds, lsTime);
  TLive = Array[0..1] of TLiveSelection; 

Mathias
Beiträge: 6160
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Rekursive Funktionen

Beitrag von Mathias »

Aber ich schaffe es nicht, den Programmablauf im Debugger zu verfolgen.

Die einfachste Variante etwas zu Debuggen, geht nach meiner Meinung mit einem einfachen Writeln();. Dazu ist muss man nur ein Konsole-Fenster öffnen. :wink:
Diese einfache Variante hat mir schon recht viel weiter geholfen.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Rekursive Funktionen

Beitrag von wp_xyz »

Ehrlich gesagt, WriteLn ist die Debugging-Methode des letzten Jahrtausends. Jeder Eingriff in den Quelltext zum Debuggen,Profilen etc. ist unschön, weil man vielleicht in der Eile des Gefechts etwas kaputt macht, oder später vergisst, das WriteLn wieder zu entfernen. Allerdings lässt einem der mit Lazarus mitgelieferte gdb oft keine andere Wahl.

Zu überlegen wäre, statt WriteLn eine der vielen Varianten von debugln aus der Unit LazLogger zu nehmen (http://wiki.freepascal.org/LazLogger). Hier kann man die Ausgabe durch Compilerparameter abschalten bzw. in eine Datei schreiben (Logdatei vom Kunden?).

mse
Beiträge: 2013
Registriert: Do 16. Okt 2008, 10:22
OS, Lazarus, FPC: Linux,Windows,FreeBSD,(MSEide+MSEgui 4.6,git master FPC 3.0.4,fixes_3_0)
CPU-Target: x86,x64,ARM

Re: Rekursive Funktionen

Beitrag von mse »

braunbär hat geschrieben:Bevor ich das Problem weiter verfolge, würde ich gerne wissen, ob Free Pascal irgend welche speziellen Compilereinstellungen braucht, um Rekursionen richtig zu kompilieren und anschließend richtig zu debuggen, das gab es, wenn ich mich richtig erinnere, in irgend welchen Versionen von Turbo Pascal. Wenn so etwas die Problemursache sein sollte, brauche ich nicht länger suchen. In der Dokumentation habe ich aber keinen Hinweis darauf gefunden, dass da irgend welche spezielle Einstellungen nötig wären.

Zum debuggen sollte man "-gl -O-" verwenden.
https://www.freepascal.org/docs-html/cu ... 3-17000010

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Rekursive Funktionen

Beitrag von braunbär »

Ich habe mit allen möglichen Debug Einstellungen herumprobiert, und komme immer mehr zum Schluss, dass Lazarus/FPC da irgend einen gröberen Fehler hat und nicht nur der Debugger ein Problem.
Kann natürlich sein, dass da noch ein Programmfehler von mir ist, aber ich glaube eher nicht.

Ich habe jetzt das ganze Projekt auf das absolute Minimum reduziert (alles in einer Unit, kein extra Package, der Parser kennt nur ganze Zahlen, Klammern und die Operatoren +,-,*,/, mod) und lade es jetzt hoch.
Es sind 3 Dateien, eine lpr-Datei und ein pas-File mit zugehöriger Formulardefinition.

Das Programm macht mit der in der Eingabemaske vorgegeben Formel (1+1) schon Mist.
Beim Debuggen wird der Reihe nach expression, term und factor aufgerufen.
Factor erkennt in Zeile 70 die öffnende Klammer und entfernt sie.
Bis dahin funktioniert es.
Aber dann sollte factor rekursiv in Zeile 71 wieder expression aufrufen. Das passiert allem Anschein nach nicht, das Programm macht statt dessen mit operand(')') in zeile 72 weiter und wirft in der Folge eine Exception, weil die eingegebene Formel so natürlich nicht richtig abgearbeitet wird.
Dateianhänge
Test.rar
(2.11 KiB) 94-mal heruntergeladen

Michl
Beiträge: 2505
Registriert: Di 19. Jun 2012, 12:54

Re: Rekursive Funktionen

Beitrag von Michl »

Ja mit Subproceduren/-funktionen hat der Debugger auch Probleme hier. Um trotzdem den Verlauf nachvollziehen zu können, könntest du sowas machen:

Code: Alles auswählen

var
  FExpressionString: String;
 
function GetExpressionString: string;
begin
  Result := FExpressionString;
  writeln('GetExpressionstring ', Result);
end;
Damit siehst du, welche Werte dein globaler ExpressionString hat. Ein Breakpoint dort und den Aufrufstack beobachtet gibt sicherlich Aufschluss über den Verlauf.

Warum verwendest du eigentlich eine globale ExpressionString Variable?
Warum baust du nicht eine Klasse dafür?

BTW: Kennst du den TFPExpressionParser, der mit FPC mitkommt (der sollte diese Aufgabe gut lösen können)? Einfaches Bsp, was ich schnell mal in dein Projekt eingefügt habe:

Code: Alles auswählen

uses ..., fpexprpars;
...
  TForm1 = class(TForm)
...
    function ExpressionResult(const AStr: String): Double;
  end;
...
procedure TForm1.Button2Click(Sender: TObject);
begin
  ShowMessage(FormatFloat('#,##0.00', ExpressionResult(Edit1.text)));
end;
 
function TForm1.ExpressionResult(const AStr: String): Double;
var
  Parser: TFPExpressionParser;
begin
  Result := 0;
  if Length(AStr) > 0 then begin
    Parser := TFPExpressionParser.Create(nil);
    try
      Parser.BuiltIns := [bcMath];
      Parser.Expression := AStr;
      case Parser.ResultType of
        rtFloat:   Result := Parser.Evaluate.ResFloat;
        rtInteger: Result := Parser.Evaluate.ResInteger;
        else       Result := 0;
      end;
    except
      on e: Exception do
        ShowMessage('Ungültige Eingabe: ' + AStr + LineEnding + e.Message);
    end;
    Parser.Free;
  end;
end;

Code: Alles auswählen

type
  TLiveSelection = (lsMoney, lsChilds, lsTime);
  TLive = Array[0..1] of TLiveSelection; 

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Rekursive Funktionen

Beitrag von wp_xyz »

Wie immer bin ich argwöhnisch, wenn Leute behaupten, Fehler müssten an Lazarus/FPC liegen, weil er nicht in ihrem eigenen Code stecken könne...

Ich weiß nicht, ob du so alt bist, dass du Turbo Pascal noch erlebt hast. Damals gab es noch nicht die Möglichkeit, in einer Funktion den Bezeichner Result für den Rückgabewert der Funktion zu verwenden; stattdessen musste das Ergebnis der Funktion an einen Bezeichner übergeben werden, der den Namen der Funktion trug. Eine Funktion, die z.B. die Summe zweier Zahlen berechnete, war damals folgendermaßen geschrieben:

Code: Alles auswählen

function Sum(a, b: Integer): Integer;
begin
  Sum := a + b;
end;

Heute würde man schreiben: "Result := a + b". Aber die alte Schreibweise funktioniert immer noch und wird immer noch verwendet (siehe z.B. massiv in fpc's numlib).

Wenn du jetzt in einer rekursiven Funktion EXPRESSION den Bezeichner EXPRESSION verwendest, dann wird nicht die Funktion rekursiv erneut aufgerufen, sondern der bisher erhaltene Funktionswert verwendet! Schreibst du stattdessen EXPRESSION(), so ist klar, dass du diese Funktion erneut aufrufen willst, und dein Programm läuft.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Rekursive Funktionen

Beitrag von braunbär »

Danke für den Hinweis, das könnte tatsächlich die Lösung des Problems sein. Ich muss das noch checken, aber es klingt sehr plausibel.

Es ist allerdings meines Erachtens ein böser Fehler des Compilers, weil das überhaupt nicht dem Pascal-Standard entspricht.
Der Funktionsname konnte auch zu Turbo Pascal Zeiten nicht zum Speichern und Wiederverwenden von "Zwischenergebnissen" verwendet werden, sondern immer nur zum Zuweisen eines (u.U. provisorischen) Endergebnisses. Das war ja der Hauptgrund für die Einführung des Bezeichners Result.

Die Verwendung des Funktionsnamens an anderer Stelle als auf der linken Seite einer Zuweisung ist im Pascal Standard immer ein rekursiver Aufruf. Delphi folgt hier übrigens dem Standard, dort funktioniert der rekursive Aufruf von expression ohne Klammern einwandfrei.

Ich kenne Pascal sogar noch aus der Zeit der Implementierung auf einem Control-Data "Großrechner" (die hatten allerdings deutlich weniger Rechenleistung als heute mein Handy), und damals hätte er dir bei einem "expression()" einen Syntaxfehler um die Ohren gehaut. Ich finde das Konstrukt mit öffnenden und schließenden Klammern ohne etwas drin scheußlich (ist wohl Gewohnheit), aber wenn es anders nicht geht, dann bleibt mir hier wohl nichts übrig.

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Rekursive Funktionen

Beitrag von wp_xyz »

Pascal-Standard? Was ist das denn? Da hält sich ja keiner dran...

Ersetze im Kopf der Unit das {$Mode objpas} durch {$Mode Delphi}. Damit hast du das Delphi-Verhalten zurück, und das Testprogramm funktioniert ohne die ().

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Rekursive Funktionen

Beitrag von braunbär »

wp_xyz hat geschrieben:Pascal-Standard? Was ist das denn? Da hält sich ja keiner dran...

In den moderneren "Dialekten" von Pascal wird der Standard zwar erweitert, aber mir fallen nicht viele Beispiele von Spracherweiterungen ein, bei denen bestehender, den Standard-Pascal Regeln folgender Code gebrochen wird - abgesehen von der Einführung von ein paar neuen reservierten Bezeichnern, das wird aber schon zur Compile-Zeit erkannt.

wp_xyz hat geschrieben:Ersetze im Kopf der Unit das {$Mode objpas} durch {$Mode Delphi}. Damit hast du das Delphi-Verhalten zurück, und das Testprogramm funktioniert ohne die ().

Ich habe bei der Umstellung von meinem Delphi Code sonst überall {$Mode Delphi} vorne eingetragen, das habe ich bei dieser Unit tatsächlich vergessen. Auf die Idee, dass der FPC hier ganz normalen Pascal-Code auf exotische Weise umsetzen könnte, und das noch dazu offenbar "by design" und nicht irrtümlich, wäre ich nicht gekommen. Naja, wieder etwas dazu gelernt...

Michl hat geschrieben:Warum verwendest du eigentlich eine globale ExpressionString Variable?
Warum baust du nicht eine Klasse dafür?

Welchen Nutzen würde hier eine Klasse bringen, außer erhöhten Overhead für den, der die Funktion in seinem Programm verwendet, und erhöhtem Overhead zur Laufzeit? Das Programm hat schon zu Turbo-Pascal Zeiten gute Dienste geleistet, ich habe es dann auf Delphi übertragen und jetzt auf FPC. Der Code, den ich gepostet habe, ist eine stark reduzierte Version des kompletten Parsers, die nur dazu gedacht war, den Fehler zu zeigen.
Die Variable ist zwar global, aber sie sitzt im implementation Bereich der Unit und ist dadurch nicht "sehr" global. Alles andere wäre mit deutlich größerem Overhead ohne jeden Nutzen verbunden.

Michl hat geschrieben:BTW: Kennst du den TFPExpressionParser, der mit FPC mitkommt (der sollte diese Aufgabe gut lösen können)?

Kenne ich noch nicht, werde ich mir gelegentlich anschauen - danke für den Hinweis. Aber mein Parser ist um einiges komplexer als das Ding, das ich gepostet habe, und kann unter anderem auf "Variablennamen" der jeweiligen Anwendung zugreifen. Und an sich funktioniert das Programm ja seit vielen Jahren einwandfrei, die Funktionalität in einen anderen Parser einzubauen, wäre sicher mehr Aufwand als die Umstellung des bestehenden Programms auf Free-Pascal - auch wenn mich das fehlende {$Mode Delphi} eine ganze Menge Stunden Zeit gekostet hat.

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: Rekursive Funktionen

Beitrag von wp_xyz »

braunbär hat geschrieben:
Michl hat geschrieben:BTW: Kennst du den TFPExpressionParser, der mit FPC mitkommt (der sollte diese Aufgabe gut lösen können)?

Kenne ich noch nicht, werde ich mir gelegentlich anschauen - danke für den Hinweis. Aber mein Parser ist um einiges komplexer als das Ding, das ich gepostet habe, und kann unter anderem auf "Variablennamen" der jeweiligen Anwendung zugreifen. Und an sich funktioniert das Programm ja seit vielen Jahren einwandfrei, die Funktionalität in einen anderen Parser einzubauen, wäre sicher mehr Aufwand als die Umstellung des bestehenden Programms auf Free-Pascal - auch wenn mich das fehlende {$Mode Delphi} eine ganze Menge Stunden Zeit gekostet hat.

Um noch etwa "Werbung" für the fpexprparser zu machen: Mit Variablen kann er natürlich auch umgehen, und man kann sogar die Liste der erlaubten Funktionen um eigene Funktionen erweitern, ohne in den Quellcode eingreifen zu müssen.

braunbär hat geschrieben:
Michl hat geschrieben:Warum verwendest du eigentlich eine globale ExpressionString Variable?

Die Variable ist zwar global, aber sie sitzt im implementation Bereich der Unit und ist dadurch nicht "sehr" global. Alles andere wäre mit deutlich größerem Overhead ohne jeden Nutzen verbunden.

Das ist eine unnötige globale Variable. Erstens funktioniert dein Parser nicht mehr in Threads, und zweitens wärst du ohne sie nicht über die Problematik mit dem Funktionsnamen auf der rechten Seite gestolpert, denn normalerweise würde ich den Expression-String als Funktionsparameter von Aufruf zu Aufruf weiterreichen, und dann hätte auch der objpas-Mode automatisch an den vorhandenen Klammern erkannt, dass nun ein rekursiver Funktionsaufruf erfolgt. - Es war eine Sache von weniger als 5 Minuten, deiner Funktion "Expression" einen var-Parameter "Expressionstring:string" mitzugeben und noch ein paar Compilerfehler auszubessern, so dass dein Parser ohne globale Variable läuft.

Code: Alles auswählen

unit TestMain;
 
//{$mode objfpc}{$H+}
{$mode Delphi}
 
interface
 
uses
  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;
 
 
type
  EWrongExpression = Class(Exception);
 
  TForm1 = class(TForm)
    Button1: TButton;
    Edit1: TEdit;
    procedure Button1Click(Sender: TObject);
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.lfm}
 
//var
//  expressionstring: string;
 
 
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
//  Expression
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
 
FUNCTION EXPRESSION(var Expressionstring: String): integer;
 
  function NEXTNUMBER: integer;
  var
    i: integer;
  begin
    result:=0;
    for i:=1 to length(expressionstring) do
      case expressionstring[1] of
        '0'..'9':
          begin
            result := 10*result + ord(expressionstring[1])-ord('0');
            delete(expressionstring,1,1);
          end;
      else
         exit;
      end (* case *);
  end;
 
  function operand(const o: string): boolean;
  // Liefert true wenn im expressionstring vorne der übergebene Operand steht
  // und entfernt den Operand aus dem String
  begin
    Expressionstring:=trimleft(Expressionstring);
    result := Expressionstring.StartsWith(o);
    if result then delete(Expressionstring,1,length(o));
  end;
 
  FUNCTION FACTOR: integer;
  var
    minus :boolean;
  begin  // Factor
    if OPERAND ('(') then begin
       result:=EXPRESSION(ExpressionString);
       operand (')');
       exit
    end;
 
    // jetzt muss eine Zahl kommen
 
    if OPERAND('+') then minus := false
                    else minus := OPERAND ('-');
 
    if expressionstring='' then
      raise EWrongExpression.Create('Die Formel ist unvollständig');
 
    if not (expressionstring[1] in ['0'..'9']) then
      raise EWrongExpression.Create('Zahl oder Teilausdruck erwartet: '+expressionstring);
 
    if minus then result:=-NEXTNUMBER else result:=NEXTNUMBER;
  end;
 
  FUNCTION TERM: integer;
  var
    h: integer;
 
    procedure chk0(const x: integer);
    begin
      if x = 0 then
        raise EWrongExpression.Create ('Division durch 0 ist nicht möglich');
    end;
 
  BEGIN  // Term
    Result:=FACTOR;
    repeat
      if OPERAND ('mod') then begin
        h:=factor;
        chk0(h);
        result:= result MOD h
      end else
      if OPERAND ('/') then begin
        h:=factor;
        chk0(h);
        result:= result div h
      end else
      if OPERAND ('*') then
        result:=result*FACTOR
      else
        exit;
    until false;
  END;
 
BEGIN  // Expression
  WriteLn('Expression');
 
  Result:=TERM;
  repeat
  if OPERAND('-') then
    Result:=result-term
  else
  if OPERAND('+') then
    result:=result+term
  else
    break;
  until OPERAND(')');
END;
 
(******************************************************************************)
(******************************************************************************)
//
// Auswertung
//
(******************************************************************************)
(******************************************************************************)
 
FUNCTION CheckKlammern(const ExpressionString: String): boolean;
var c: integer; ch: char;
BEGIN
Result:=false; c:=0;
for ch in expressionstring do case ch of
   '(': inc(c);
   ')': if c>0 then dec(c) else exit;
   // Hier alle anderen Zeichen ignorieren, nur Klammern werden überprüft
   end (* case *);
Result:=c=0;
end;
 
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//
//  Auswertung / Rahmenprogramm
//
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
 
function auswertung(const Formel:string): string;
var
  expressionstring: String;
begin
  expressionstring:=lowercase(Formel);
  Result:='';
  if not CheckKlammern(Expressionstring) then raise EWrongExpression.Create
            ('Öffnende und schließende Klammern der Formel passen nicht zusammen');
  result:=inttostr(Expression(expressionstring));
  if expressionstring<>'' then raise EWrongExpression.Create('Ungültig: '+expressionstring);
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
 showmessage(auswertung(edit1.text));
end;
 
end.

braunbär
Beiträge: 369
Registriert: Do 8. Jun 2017, 18:21
OS, Lazarus, FPC: Windows 10 64bit, Lazarus 2.0.10, FPC 3.2.0
CPU-Target: 64Bit
Wohnort: Wien

Re: Rekursive Funktionen

Beitrag von braunbär »

Ich habe noch von Turbo Pascal im Kopf, dass der Compiler für den Zugriff auf lokale und globale Variable optimiert ist, während der Code für den Zugriff auf lokale Variable und Parameter übergeordneter Prozeduren recht aufwändig und ineffizient ist, die Adressen wurden da bei jedem Zugriff mühsam über den Aufrufstack ermittelt. Deshalb die globale Variable, auch wenn das Argument natürlich auf aktuellen Computern nicht mehr sonderlich relevant ist und der FPC vielleicht sogar schon etwas effizienteren Code produzieren kann.

Threadsicherheit war bislang auch kein Thema, weil wir den Parser nur zum Parsen von Strings umittelbar, nachdem sie eingegeben worden sind, verwendet haben. Aber du hast Recht, mit dem expressionstring als Parameter schaut der Code besser aus.

Antworten