Wie kann ich zirkuläre Logik oder Rekursion in einem benutzerdefinierten Ausdrucksauswerter erkennen?

Question

Ich habe einen experimentellen Funktionsauswerter geschrieben, der es mir ermöglicht, einfache Funktionen so zu verknüpfen, dass bei einer Änderung der Variablen alle Funktionen, die sich auf diese Variablen stützen (und die Funktionen, die sich auf diese Funktionen stützen, usw.), gleichzeitig aktualisiert werden. Anstatt die Funktion sofort bei der Eingabe auszuwerten, speichere ich die Funktion. Erst wenn ein Ausgabewert angefordert wird, werte ich die Funktion aus, und zwar jedes Mal, wenn ein Ausgabewert angefordert wird.

Zum Beispiel:

pi = 3.14159
rad = 5
area = pi * rad * rad
perim = 2 * pi * rad

Ich definiere "pi" und "rad" als Variablen (also als Funktionen, die eine Konstante zurückgeben) und "area" und "perim" als Funktionen. Jedes Mal, wenn sich 'pi' oder 'rad' ändern, erwarte ich, dass sich auch die Ergebnisse von 'area' und 'perim' entsprechend ändern. Wenn es Funktionen gäbe, die von "area" oder "perim" abhängen, würden sich auch die Ergebnisse dieser Funktionen ändern.

Dies alles funktioniert wie erwartet. Das Problem ist hier, wenn der Benutzer eine Rekursion einführt - entweder versehentlich oder absichtlich. Es gibt keine Logik in meiner Grammatik - es ist einfach ein Evaluator - also kann ich dem Benutzer keine Möglichkeit geben, aus der Rekursion "auszubrechen". Ich möchte verhindern, dass dies überhaupt geschieht, was bedeutet, dass ich eine Möglichkeit brauche, dies zu erkennen und die beanstandete Eingabe als ungültig zu deklarieren.

Zum Beispiel:

a = b
b = c
c = a

Im Moment führt die Auswertung der letzten Zeile zu einer StackOverflowException (während die ersten beiden Zeilen zu '0' ausgewertet werden - eine nicht deklarierte Variable/Funktion ist gleich 0). Ich möchte die Situation der zirkulären Logik erkennen und dem Benutzer die Eingabe einer solchen Anweisung untersagen. Ich möchte dies unabhängig davon tun, wie tief die zirkuläre Logik versteckt ist, aber ich habe keine Ahnung, wie ich das anstellen soll.

Hinter den Kulissen werden Eingabestrings übrigens über einen einfachen Scanner in Token umgewandelt, dann über einen handgeschriebenen rekursiven Descent-Parser in einen abstrakten Syntaxbaum, und dann wird der AST ausgewertet. Die Sprache ist C#, aber ich bin nicht auf der Suche nach einer Code-Lösung - Logik allein reicht aus.

Hinweis: Dies ist ein persönliches Projekt, das ich verwende, um zu lernen, wie Parser und Compiler funktionieren, so dass es nicht unternehmenskritisch ist - aber das Wissen, das ich weg von diesem nehmen ich planen, um im wirklichen Leben irgendwann zu arbeiten. Für jede Hilfe, die Sie mir geben können, wäre ich Ihnen sehr dankbar =)

Edit: Für den Fall, dass jemand neugierig ist, dieser Beitrag in meinem Blog beschreibt, warum ich versuche, dies zu lernen, und was ich dabei herausfinde.

Answer 1

Ich hatte in der Vergangenheit ein ähnliches Problem wie dieses. Meine Lösung war es, Variablennamen auf einen Stapel zu schieben, während ich durch die Ausdrücke rekursierte, um die Syntax zu überprüfen, und sie zu löschen, wenn ich eine Rekursionsebene verließ.

Bevor ich jeden Variablennamen auf den Stapel schob, prüfte ich, ob er dort bereits vorhanden war. War dies der Fall, handelte es sich um eine zirkuläre Referenz. Ich war sogar in der Lage, die Namen der Variablen in der zirkulären Referenzkette anzuzeigen (da sie sich auf dem Stack befanden und nacheinander weggeschoben werden konnten, bis ich den fraglichen Namen erreichte).

EDIT: Das war natürlich für einzelne Formeln... Für Ihr Problem wäre ein zyklischer Graph von Variablenzuweisungen der bessere Weg.

Answer 2

Eine (wahrscheinlich nicht die beste) Lösung ist die Erstellung eines Abhängigkeitsdiagramms.

Jedes Mal, wenn eine Funktion hinzugefügt oder geändert wird, wird der Abhängigkeitsgraph auf Zylzitäten überprüft.

Dies kann abgekürzt werden. Jedes Mal, wenn eine Funktion hinzugefügt oder geändert wird, kennzeichnen Sie sie. Wenn die Auswertung zu einem Aufruf der markierten Funktion führt, haben Sie einen Zyklus.

Beispiel:

a = b

• Kennzeichen a
• eval b (nicht gefunden)
• Rücknahme der Markierung a

b = c

• Flagge b
• eval c (nicht gefunden)
• b entflaggen

c = a

• Flagge c
• eval a
• eval b
• eval c (flagged) -> Zyklus, Änderung in c verwerfen!
• c entflaggen

Answer 3

Als Antwort auf den Kommentar zu Antwort zwei:

(Tut mir leid, ich habe gerade meine Openid-Erstellung verpfuscht, also werde ich die alten Sachen später verlinken müssen...)

Wenn Sie "flag" mit "push" und "unflag" mit "pop" vertauschen, ist es so ziemlich das Gleiche :) Der einzige Vorteil der Verwendung des Stacks ist die Möglichkeit, detaillierte Informationen über den Zyklus zu liefern, unabhängig von der Tiefe. (Nützlich für Fehlermeldungen :) )

Andrew