Ich versuche, eine Logikabfragesprache für Spielzeuglogik zu schreiben, die auf verschiedenen Unterrichtsquellen basiert, einschließlich SICP und The Art of Prolog (AoP). Ich fange gerade an, meine erste Skizze des Vereinigungsalgorithmus auszuarbeiten (das "Herz des Berechnungsmodells der Logikprogrammierung" gemäß AoP), und AoP bemerkt, dass
Wenn der Vereinheitlichungsalgorithmus für eine bestimmte Logikprogrammiersprache implementiert wird, wird die explizite Substitution in den Gleichungen auf dem Stapel und dem Unifier vermieden. Stattdessen werden logische Variablen und andere Terme durch Speicherzellen mit unterschiedlichen Werten dargestellt, und eine variable Bindung wird implementiert, indem der Speicherzelle, die eine logische Variable repräsentiert, eine Referenz auf die Zelle zugewiesen wird, die die Darstellung des Terms enthält, an den die Variable gebunden ist. (1. Auflage, S. 71)
Als ich dies las, wurde mir klar, dass ich nur grob und praktisch verstehe, wie logische Variablen funktionieren, aber ich verstehe nicht wirklich, wie sie implementiert werden. Ich bin mir nicht einmal sicher, was genau die formalen Eigenschaften sind, die logische Variable von den unveränderlichen Variablen unterscheiden, die in anderen Regionen des deklarativen Programmierparadigmas vorkommen. Ich werde dankbar sein für alle erhellenden Erklärungen und lehrreichen Referenzen.
Sehen Sie sich die Warren-abstrakte Maschine an, wenn Sie verstehen möchten, wie Prolog-Compiler und -Dolmetscher implementiert sind.
Die Grundidee für logische Variablen ist, dass sie entweder an einen Ausdruck gebunden sind, frei sind oder an eine andere logische Variable gebunden sind.
Teilantwort, die nur den Begriff logische Variable betrifft.
Eine erste Näherung könnte sein, zu sagen, dass logische Variablen wie mathematische Variablen funktionieren: Sobald ihr Wert gelernt ist, wird er sich nicht ändern. Dies führt zu dem Begriff der einmal zuweisenden Variablen. Dies steht im Gegensatz zu der Vorstellung von Variablen in imperativen Programmiersprachen, wo sie Speicherstellen symbolisch identifizieren, was eine destruktive (und somit) Mehrfachzuweisung erlaubt. Aber zurück zu logischen Variablen wird es besser. Eine logische Variable kann mit einem -Term vereinheitlicht sein, aber dieser Begriff kann selbst Variablen enthalten. Diese Variablen können wiederum später mit anderen Termen vereinheitlicht werden. Betrachten Sie das folgende Beispiel in Prolog:
%Vor% In der zweiten Abfrage wird die Variable V weiter instanziiert, indem die enthaltene Variable Y mit der Ganzzahl 1 vereinigt. Der Operator =/2 ist der Operator Prolog Vereinheitlichung . Vereinheitlichung ist eine logische Operation, die wahr ist, wenn Sie zwei Terme nehmen und sie gleich machen können, möglicherweise durch bindende Variablen in einem Begriff zu einem Unterbegriff in dem anderen Begriff.
Der Hauptunterschied bei der Implementierung ist structure sharing vs structure copying . Googeln dafür bringt viele Ressourcen zur Aufmerksamkeit ...
In meinem Prolog-Interpreter habe ich die gemeinsame Nutzung von Strukturen ausgewählt, daher ist es in unify offensichtlich die Art der detaillierten Übergabe erforderlich (na ja, es ist eine sehr einfachen Geist Ansatz): die meisten der Implementierung ist da, um die Service-Datenstrukturen BindStack und TrailStack nur speichern und wenig mehr ... Als Konsequenz von Bei meinen Entscheidungen muss ein instanziierter Term zusammen mit seiner Umgebung referenziert werden.
Tags und Links prolog