Gibt es eine klare Referenz mit Pseudocode, wie man einen Prolog-Interpreter in einer rein funktionalen Sprache implementiert? Was ich bisher gefunden habe, scheint sich nur mit imperativen Sprachen zu befassen, ist lediglich eine Demonstration von Prolog, das in sich selbst implementiert ist, oder bietet keinen konkreten Algorithmus zur Interpretation. Ich wäre sehr dankbar für eine Antwort.
25
Antworten:
Seit Prolog = Syntaktische Vereinigung + Rückwärtsverkettung + REPL
Alle drei Teile sind in Künstliche Intelligenz zu finden: Strukturen und Strategien zur komplexen Problemlösung von George F. Luger. In der vierten Ausgabe des Buches sind alle drei Teile in LISP implementiert ( siehe Abschnitt 15.8, Logikprogrammierung in LISP). Er schreibt den gleichen Code auch in seine anderen Bücher, aber ich habe nicht alle, um das hier zu bemerken. Den Code für seine Bücher finden Sie hier .
Eine weitere Quelle mit allen drei Teilen findet sich in Paradigmen der Programmierung künstlicher Intelligenz: Fallstudien in Common Lisp von Peter Norvig. Siehe Kapitel 11, Logikprogrammierung und 12, Kompilieren von Logikprogrammen. Den Code für sein Buch finden Sie hier .
Eine weitere Quelle ist Struktur und Interpretation von Computerprogrammen von Hal Abelson, Jerry Sussman und Julie Sussman. Siehe Abschnitt 4.4 Logikprogrammierung. Die Site für das Buch ist hier und der Code für das Buch ist hier .
Es ist nicht ungewöhnlich, den in vielen Anwendungen implementierten Vereinigungsalgorithmus mit Rückverkettung zu finden, wenn Sie wissen, wo Sie suchen müssen. es ist besonders häufig bei der Typinferenz in funktionalen Compilern. Die Verwendung der Schlüsselwörter Unification oder Tritt auf, um die Funktionen zu erkennen. Auch die meisten Implementierungen verwenden unif als Namen für die Vereinigungsfunktion.
Für eine Version von Prolog, abzüglich der in OCaml durchgeführten REPL, siehe Code und Ressourcen für "Handbuch der praktischen Logik und des automatisierten Denkens " - prolog.ml
Eine Übersetzung des Buchcodes in F # finden Sie hier . Eine Übersetzung des Buchcodes nach Haskell finden Sie hier .
In Bezug auf das Auffinden des Codes ist der Vereinheitlichungsalgorithmus am einfachsten zu finden, dann Implementierungen mit in Anwendungen eingebetteter Rückverkettung. Am schwierigsten ist es, eine voll funktionsfähige Implementierung von Prolog in einer funktionalen Sprache mit einer REPL zu finden. In den meisten Fällen liegt der Code nicht in einem Format vor, das direkt in PROLOG verwendet werden kann. Es ist stark angepasst, um die Leistung zu verbessern, sodass Sie möglicherweise den Code finden, aber es ist den Preis nicht wert, die gewünschten Teile herauszuprügeln. Mein Rat wäre, Lugers Buch zu lesen und es von Grund auf in der Sprache Ihrer Wahl aufzubauen, auch wenn es bedeutet, LISP zu installieren, zu lernen und zu übersetzen.
BEARBEITEN
Da dies eine doppelte Frage von StackOverflow ist und das OP neu ist und in den Kommentaren heißt:
Ich werde dies hier näher erläutern, aber mir ist klar, dass das OP eine neue Frage stellen sollte.
Für einige Intro-Sachen siehe Implementieren von Typinferenz .
Das beste Buch, das ich dazu kenne, sind Typen und Programmiersprachen von Benjamin C. Pierce. Die Website des Buches ist hier . Die Ressourcen mit Links zu OCaml-Code finden Sie hier . Und die vor kurzem begonnene, aber größtenteils vollständige Übersetzung dieser in F # ist hier .
Abhängige Typen: pg. 462 Veredelungsarten: pg. 207 Lineare Logik- und Typensysteme: pg. 109
quelle
Sehen Sie sich die Implementierung von miniprolog in meinem Programmiersprachen-Zoo an , es ist das letzte auf der Liste. Sie können den Quellcode online sehen , der Code ist gut dokumentiert.
quelle