Nichtdeterministische Programmierung - Nondeterministic programming

Eine nichtdeterministische Programmiersprache ist eine Sprache, die an bestimmten Stellen im Programm (sogenannten "Auswahlpunkten") verschiedene Alternativen für den Programmablauf angeben kann . Im Gegensatz zu einer if-then-Anweisung wird die Wahlmethode zwischen diesen Alternativen nicht direkt vom Programmierer angegeben; das Programm muss zur Laufzeit zwischen den Alternativen entscheiden, über eine allgemeine Methode, die auf alle Auswahlpunkte angewendet wird. Ein Programmierer gibt eine begrenzte Anzahl von Alternativen an, aber das Programm muss sich später zwischen ihnen entscheiden. ("Choose" ist in der Tat ein typischer Name für den nichtdeterministischen Operator.) Es kann eine Hierarchie von Auswahlpunkten gebildet werden, wobei Auswahlmöglichkeiten höherer Ebene zu Verzweigungen führen, die Auswahlmöglichkeiten niedrigerer Ebene enthalten.

Eine Methode der Wahl wird in Backtracking- Systemen (wie Amb oder Unification in Prolog ) verkörpert, bei denen einige Alternativen "fehlschlagen" können, was dazu führt, dass das Programm zurückverfolgt und andere Alternativen ausprobiert. Wenn alle Alternativen an einem bestimmten Auswahlpunkt fehlschlagen, schlägt eine ganze Verzweigung fehl, und das Programm geht weiter zu einem älteren Auswahlpunkt zurück. Eine Komplikation besteht darin, dass das System in der Lage sein muss, alte Programmzustände wiederherzustellen, indem es Nebeneffekte rückgängig macht, die durch die teilweise Ausführung einer schließlich fehlgeschlagenen Verzweigung verursacht wurden, da jede Wahl vorläufig ist und neu getroffen werden kann.

Eine andere Methode der Wahl ist das Reinforcement Learning, das in Systemen wie Alisp enthalten ist . In solchen Systemen verfolgt das System, anstatt zurückzuverfolgen, ein gewisses Maß an Erfolg und lernt, welche Entscheidungen oft zum Erfolg führen und in welchen Situationen (sowohl der interne Programmzustand als auch die Umgebungseingaben können die Auswahl beeinflussen). Diese Systeme sind für Anwendungen in der Robotik und anderen Bereichen geeignet, in denen das Zurückverfolgen den Versuch beinhalten würde, in einer dynamischen Umgebung ausgeführte Aktionen rückgängig zu machen, was schwierig oder unpraktisch sein kann.

Siehe auch

Verweise