Kalkül mit Reflexion

Ich suche nach einem einfachen Kalkül, das die Überlegungen zur Reflexion unterstützt , nämlich die Introspektion und Manipulation von laufenden Programmen.

Gibt es eine untypisierte $\lambda$ Kalkulus-Erweiterung, mit der man $\lambda$ Terme in eine Form umwandeln kann, die syntaktisch manipuliert und anschließend ausgewertet werden kann?

Ich stelle mir vor, dass der Kalkül zwei zusätzliche Hauptbegriffe hat:

• $\mathtt{reflect}\ v$ : nimmt$v$ und erzeugt eine Darstellung$v$ abänderbar zur syntaktischen Manipulation.
• $\mathtt{eval}\ v$ : Nimmt eine syntaktische Darstellung eines Begriffs und wertet ihn aus.

Zur Unterstützung der Reflexion ist eine syntaktische Darstellung von Begriffen erforderlich. Es würde ungefähr so ​​aussehen:

• würde als ein Term ( L A M R ( e ) ) dargestellt , wobei R ( e ) die reflektierte Version von e ist ,$\lambda x.e$$(\mathsf{LAM}\ R(e))$$R(e)$$e$
• würde dargestellt als Term ( A P P R ( e ) R ( e ' ) ) und$e\ e'$$(\mathsf{APP}\ R(e)\ R(e'))$
• würden dargestellt als ( V A R x ) .$x$$(\mathsf{VAR}\ x)$

Mit dieser Darstellung könnte der Mustervergleich zum Manipulieren von Begriffen verwendet werden.

Aber wir stoßen auf ein Problem. und e v a l müssen als Terme codiert werden, ebenso wie Pattern Matching. Der Umgang damit scheint unkompliziert zu sein, wenn Sie R E F L E C T , E V A L und M A T C H hinzufügen. Muss ich jedoch andere Begriffe hinzufügen, um die Manipulation dieser zu unterstützen?$\mathtt{reflect}$$\mathtt{eval}$$\mathsf{REFLECT}$$\mathsf{EVAL}$$\mathsf{MATCH}$

Es gibt Designentscheidungen, die getroffen werden müssen. Was soll die oben erwähnte - Funktion mit dem Körper von r e f l e c t und e v a l tun ? Sollte R ( - ) den Körper transformieren oder nicht?$R(-)$$\mathtt{reflect}$$\mathtt{eval}$$R(-)$

Da ich nicht so sehr daran interessiert bin, Reflexion selbst zu studieren - der Kalkül würde als Vehikel für andere Forschungen dienen - möchte ich das Rad nicht neu erfinden.

Gibt es Kalküle, die mit den oben beschriebenen übereinstimmen?

Soweit ich das beurteilen kann, sind Kalküle wie MetaML, die in einem Kommentar vorgeschlagen wurden, weit fortgeschritten, bieten jedoch nicht die Möglichkeit, bereits erstellte Codefragmente zu strukturieren und zu dekonstruieren.

Eine Sache, die ich tun möchte, ist die folgende:

• $\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x \to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

Führen Sie dann einen Mustervergleich für das Ergebnis durch, um einen völlig anderen Ausdruck zu erstellen.

Dies ist sicherlich keine konservative Erweiterung des Kalküls, und die Metatheorie dürfte hässlich sein, aber dies ist eine Art Punkt für meine Anwendung. Ich möchte λ -Abstraktionen auseinander brechen .$\lambda$$\lambda$

Jean Louis Krivine führte einen abstrakten Kalkül ein, der die "Krivine-Maschine" auf sehr nicht-triviale Weise erweitert (beachten Sie, dass die Krivine-Maschine die call / cc-Anweisung von lisp bereits unterstützt):

Er führt einen „Zitat“ Operator in diesem Artikel auf die folgende Weise definiert: wenn a λ -term, note n & phi; das Bild von φ durch eine Bijektion π : & Lgr; → N von Lambda - Ausdrücke auf natürliche Zahlen. Anmerkung ¯ n ist die Kirchennummer, die n ∈ N entspricht . Krivine definiert den Operator χ durch die Bewertungsregel: χ φ → φ ¯ n $\phi$$\lambda$$n_\phi$$\phi$$\pi: \Lambda \rightarrow \mathbb{N}$$\overline{n}$$n\in\mathbb{N}$$\chi$

Beachten Sie, dass Krivine eine notorisch schwierige Lektüre ist (seien Sie bitte nicht böse, wenn Sie dies lesen, Jean-Louis!), Und einige Forscher haben den karitativen Akt unternommen, um den technischen Inhalt besser lesbar zu machen. Sie könnten versuchen, einen Blick auf diese Notizen von Christophe Raffali zu werfen .

Hoffe das hilft!

Mir fällt ein, dass es einen weiteren Hinweis gibt, der für Ihre Interessen relevant sein könnte: Der Pure Pattern Calculus von Jay und Kesner formalisiert eine Variante des Kalküls, die eine einfache Abstraktion über eine Variable zu einer Abstraktion über ein Muster, das ein Musterkalkül darstellt, erweitert selbst. Dies ist phänomenal aussagekräftig und ermöglicht es insbesondere, eine Anwendung selbst zu dekonstruieren: Wenn ich mich nicht irre, lautet der Begriff:$\lambda$

reduziert sich auf . Auch hier bin ich der Meinung, dass dies mehr als genug ist, um die Operatoren quote und eval zu implementieren .$\lambda x.x\ x$

Dies zu tun ist sehr schwierig, wenn nicht unmöglich, ohne den Zusammenfluss aufzugeben. Das heißt, ich vermute, Sie haben Recht mit einer haarigen Metatheorie. Auf der anderen Seite ist es möglich, eine Kombinationsrechnung zu entwerfen, die alle berechenbaren Funktionen ausdrückt und deren Begriffe vollständig überprüft werden können: siehe Jay und Give-Wilson .

Ich glaube jedoch, dass diese Fähigkeit Ihrer Gleichungstheorie einiges Schlechtes anhaben kann. Insbesondere können Sie in der Regel nur dann beweisen, dass zwei Werte gleich sind, wenn die bis zu Alpha-Äquivalenzen gleich sind.

Ich habe die mit Krivine verknüpfte Papierkodierung noch nicht gelesen, aber ich sollte beachten, dass Sie in der klassischen Logik im Wesentlichen nur zwei Dinge haben: wahr und falsch. Alles ist gleichbedeutend mit einer davon. Das heißt, Sie neigen sowieso dazu, eine zusammengebrochene Gleichungstheorie zu haben.

In der Theorie der Programmiersprachen wird die Funktion, über die Sie sprechen, normalerweise als "Anführungszeichen" bezeichnet. Zum Beispiel hat John Longley in einigen seiner Arbeiten darüber geschrieben, siehe dieses Papier .

Wenn Sie nur theoretischen Überlegungen nachgehen (im Gegensatz zu einer wirklich nützlichen Implementierung), können Sie die Dinge vereinfachen, indem Sie angeben, dass quote(oder reflectwie Sie es nennen) der Typ von Ganzzahlen zugeordnet ist, natindem Sie einen Gödel-Code seines Arguments zurückgeben. Sie können die Zahl dann wie einen abstrakten Syntaxbaum zerlegen. Darüber hinaus brauchen Sie nicht, evalweil das in der Sprache implementiert werden kann - es ist im Wesentlichen ein Dolmetscher für die Sprache.

$n \star m$$\varphi_n(m)$$\varphi_n$$n$$\lambda$quote

Wenn Sie mir sagen, wonach Sie suchen, kann ich Ihnen möglicherweise genauere Referenzen geben.

Hier ist übrigens ein offenes Problem:

$\lambda$quote$\xi$ Regel erhältst.

$\xi$

Hier ist eine alternative Antwort, anstatt meinen nominalen Ansatz zu verwenden, der noch experimentell ist, gibt es einen etablierteren Ansatz, der auf das Papier zurückgeht:

LEAP: Eine Sprache mit Eval und Polymorphismus
Frank Pfenning und Peter Lee
https://www.cs.cmu.edu/~fp/papers/tapsoft89.pdf

Das Papier beginnt mit:

Dies führte uns dann zu der von Reynolds zuerst gestellten Frage, ob stark typisierte Sprachen metazirkuläre Interpreten zulassen. Konventionelle Weisheit schien darauf hinzudeuten, dass die Antwort "Nein" war. Unsere Antwort lautet "Fast".

Bitte beachten Sie, dass LEAP viel stärker ist als das, was das OP will. Zunächst wird es getippt. Und zweitens wird nach Metacircularity gefragt, was zum Beispiel bedeutet, dass eval eine eigene Definition ausführen kann. In Prolog erhalten Sie die Metacircularity for solve / 1:

solve(true).
solve((A,B)) :- solve(A), solve(B).
solve(H) :- clause(H,B), solve(B).

Wenn Sie die folgende Klausel hinzufügen, um / 1 zu lösen:

solve(clause(H,B)) :- clause(H,B).

Und wenn Sie dafür sorgen, gibt Klausel / 2 auch die Klauseln von solve / 1 zurück. Sie können dann solve (solve (...)) aufrufen und sehen, wie solve sich selbst ausführt.

Fragen der Selbstrepräsentation geben noch Anlass zur Recherche, siehe zum Beispiel:

Selbstdarstellung im Girards-System U
Matt Brown, Jens Palsberg
http://compilers.cs.ucla.edu/popl15/popl15-full.pdf

Das Problem wird in der Nähe von Proof-Assistenten wie Coq und Isabelle / HOL identifiziert. Es steht unter dem Akronym HOAS . Es gibt einige Behauptungen um λ-Prolog herum, dass durch den neuen ∇-Quantifizierer solche Dinge getan werden können. Aber ich konnte diese Behauptung noch nicht in den Griff bekommen. Ich denke, die wichtigste Erkenntnis, die ich bisher erhalten habe, ist, dass es keinen bestimmten Ansatz gibt, es gibt ein paar mögliche Ansätze.

Meine eigene Einstellung , die noch nicht fertig ist , ist inspiriert von einem kürzlich erschienenen Artikel von Paulson über den Nachweis von Gödels Unvollständigkeit. Ich würde die Ordner auf Objektebene in Verbindung mit einer Datenstruktur verwenden, die Namen auf Metaebene enthält. Grundsätzlich eine ähnliche, aber unterschiedliche Datenstruktur wie die aus dem OP und mit der Codierung der Kirche, da ich an abhängigen Typen interessiert bin:

datatype Expr = var Name                 /* written as n */
              | app Expr Expr            /* written as s t */
              | abs Name Expr Expr       /* written as λn:s.t */

Die Ausdrücke auf Metaebene können von den Ausdrücken auf Objektebene dadurch unterschieden werden, dass wir die Variablennamen n, m usw. verwenden, um Namen zu bezeichnen. Während wir auf Objektebene die Variablennamen x, y, .. etc .. verwenden. Die Interpretation eines Meta-Terms in der Objektlogik würde dann wie folgt funktionieren. Schreiben wir [t] σ für die Interpretation des Nominalterms t im Nominalkontext σ, der einen Objektterm ergeben soll. Wir hätten dann:

 [n]σ = lookup σ n
 [s t]σ = [s]σ [t]σ
 [λn:s.t]σ = λx:[s]σ.[t]σ,n:x

Das Obige würde definieren, was das OP eine EVAL-Funktion nennt. Kleiner Unterschied zu Paulson, σ ist nur eine endliche Liste und keine funktionale. Meiner Meinung nach wäre es nur möglich, eine EVAL-Funktion und keine REFLECT-Funktion einzuführen. Da auf der Objektebene möglicherweise eine gewisse Gleichheit vorliegt, sind die verschiedenen Lambda-Ausdrücke gleich. Was Sie tun müssten, wäre eval zu nutzen, um möglicherweise auch über Reflexion nachzudenken, wenn Sie das Bedürfnis haben.

Sie müssten zu Extremen wie Prolog gehen, wo nichts erweitert wird, wenn Sie die Mauer zwischen nominal und nicht nominal niederreißen möchten. Aber wie das Beispiel des λ-Prolog-Systems zeigt, gibt es im Fall höherer Ordnung zusätzliche Probleme, die zum Beispiel nur durch die Einführung neuer Mittel wie eines as-Quantifizierers auf logische Weise überwunden werden können!