Programminversionsalgorithmen für Programme höherer Ordnung

Der Begriff Programminversion hat mehrere Bedeutungsschattierungen, wurde aber wahrscheinlich mit J. McCarthys 1956er Arbeit The Inversion of Functions Defined by Turing Machines im Kontext der KI begonnen. Inzwischen wurden viele Zusammenhänge zwischen Programminversion und anderen Bereichen entdeckt, z. B. reversible Programmierung (physikalisch und logisch), Teilbewertung, Verifizierung, bidirektionale Programmierung, Logikprogrammierung und maschinelles Lernen.

Was ist Programminversion? In erster Näherung ist es ungefähr so: Wenn ein Programm Argumente vom Typ und Ergebnisse vom Typ zurückgibt, erzeugen Sie ein Programm , das "irgendwie" die Umkehrung von . Ich bin hier absichtlich vage, da das Konzept auf verschiedene Weise geklärt werden kann (und wird): z. B. muss injektiv sein? Sollte alle oder nur einige so dass ?A B P - 1 P P P - 1 ( b ) a P ( a ) = $P : A \rightarrow B$$A$$B$$P^{-1}$$P$$P$$P^{-1}(b)$$a$$P(a) = b$

Es gibt generische Möglichkeiten, ein Programm zu invertieren, z. B. die Diagonalisierung, wie bereits von McCarthy ausgeführt, oder die teilweise Bewertung, aber sie sind in der Regel nicht effizient. Außerdem scheinen sich die meisten mir bekannten Arbeiten zur Programminversion nicht mit vollständigen Programmiersprachen höherer Ordnung (dh -calculi) zu befassen.$\lambda$

Referenzanfrage. Was ist der Stand der Technik bei expliziten Algorithmen zur Programminversion von -calculi (ohne Einschränkung der höheren Orderness)?$\lambda$

Es gab nicht viel Arbeit in diesem Raum, aber welche Arbeit es gibt, ist ziemlich interessant.

1. Torben Mogensen hat an diesem Problem gearbeitet. Hier sind zwei Papiere von ihm.

   Das erste Papier enthält einen Algorithmus für Funktionsprogramme erster Ordnung und das zweite erweitert ihn auf Funktionen höherer Ordnung. Die genaue Charakterisierung, wann dieser Algorithmus erfolgreich sein wird, bleibt der zukünftigen Arbeit überlassen.

   • Halbinversion von geschützten Gleichungen
   • Halbinversion von Funktionsparametern

2. Tetsuo Yokoyama, Holger Bock Axelsen und Robert Glück.

   Dies beschreibt die RFun-Programmiersprache, die Funktionsprogramme erster Ordnung invertiert, jedoch Einschränkungen hinsichtlich Injektivität und Rückwärtsdeterminismus erzwingt, die sicherstellen, dass die Rückwärtsauswertung so schnell wie vorwärts ist. (Sie haben eine Reihe anderer Artikel zu diesem Thema geschrieben, die ich nur schwer bekommen konnte.)

   • Auf dem Weg zu einer reversiblen funktionalen Sprache.

3. Stefan Bohne und Baltasar Trancón Widemann.

   Dies ist ein wirklich ordentliches Papier! Es wird festgestellt, dass (a) Sie eine Kategorie erstellen können, in der die Morphismen Funktionen sind, die mit ihrer Umkehrung gepaart sind (für jeden bestimmten Begriff der Umkehrung, den Sie verwenden), und (b) diese Kategorie eine kompakte Dolchstruktur aufweist. Dies bedeutet, dass Sie ein Programm mit einer leicht funky linearen Disziplin schreiben und dann die Vorwärts- und Rückwärtsinterpretationen aus der Semantik ablesen können.

   Sie geben eine funktionale Sprache mit einer ziemlich wilden Syntax: Nahezu willkürliche Ausdrücke können als Muster verwendet werden, und Reversibilität macht es sinnvoll.

   • Ein Ansatz für die verallgemeinerte reversible Funktionsprogrammierung

4. Francesco Tiezzia, Nobuko Yoshida

   Ich habe diesen Artikel nicht gelesen, sondern erst entdeckt, als ich nach den anderen Zeitungen gegoogelt habe. Angesichts der Autoren und des Themas vermute ich, dass dies genau das Richtige für Sie ist!

   • Reversibler sitzungsbasierter Pi-Kalkül