Wie implementiere ich einen Prolog-Interpreter in einer rein funktionalen Sprache?

25

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.

Jimster
quelle
4
Die Implementierung von Prolog (Princeton Series in Computer Science) durch Patrice Boizumault hat Lisp-Implementierung.
Will Ness
Siehe diese Antwort für einen relativ neuen Ansatz.
Falsch

Antworten:

24

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:

Um mehr Kontext zu schaffen, versuche ich, eine Typinferenz zu implementieren. Die komplexen Funktionen im Typensystem meiner Sprache (abhängige Typen, Verfeinerungstypen, lineare Typisierung, um nur einige der weniger verbreiteten Typen zu nennen) geben mir jedoch das Gefühl, dass dies der Fall ist Es ist nützlich, meine Typinferenz auf die Algorithmen zu stützen, die Prolog steuern, um einen sehr allgemeinen Algorithmus zu erhalten. Ich werde bemerken, dass ich völlig Autodidakt bin, so dass mein Wissen in großen Bereichen fehlt.

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

Guy Coder
quelle
1
Guy Coder, Sie sind ein Gentleman und ein Gelehrter! Ihre Hilfe ist äußerst nützlich, und ich kann Ihnen nicht genug danken, dass Sie sich die Zeit genommen haben, diese Frage zu beantworten. = D - Jimsters Kollaborateur und forschungsmüder Freund
Shenzao
Ich danke Ihnen noch einmal, ich habe diese Bücher bereits erhalten (davor nicht wie bei einer schnellen Reise in einen Buchladen).
Jimster
@Jimster Norvigs Code ist nett und klar, passt in eine Seite IIRC. Ich erinnere mich aber nicht, ob es rein ist .
Will Ness
Eine andere gefunden: Vorlesung 26: Typinferenz und Vereinigung
Guy Coder
Von Interesse: unify_P3.py , Teil von Aufgabe 2
Guy Coder