Programmüberlegungen zum eigenen Quellcode

15

Die Inspiration für diese Frage ist die folgende (vage) Frage: Was sind die programmiersprachlichen / logischen Grundlagen für eine KI, die über ihren eigenen Quellcode nachdenken und ihn modifizieren könnte?

Das ist überhaupt nicht streng, also hier ist mein Versuch, eine konkrete Frage daraus zu extrahieren. Es gibt zwei Dinge, die mich interessieren:

(A) Eine Programmiersprache P, die ihre eigenen Programme als Datentyp Programm darstellen und manipulieren kann (zB als AST). (Falls gewünscht, kann ein Objekt vom Typ Programm in einen String konvertiert werden. Dies ist der Text eines gültigen Programms in dieser Sprache. Dies ist das Gegenteil von dem, was ein Compiler tut.)

(B) Eine Methode, um zu überlegen, was ein Programm in der Sprache P macht. Hier sind zwei Ebenen, über die ich nachdenke:

  1. Eine andere Sprache Q (mit Theoremprüfungsfähigkeiten), die modelliert, was ein P-Programm tut. Es sollte in der Lage sein, Aussagen wie "das Ergebnis der Ausführung von Programm p ist foo" auszudrücken und zu beweisen.
  2. Eine Möglichkeit zu überlegen, was ein Programm p tut: Programm in der Sprache P selbst. (Also nehmen wir P = Q oben.)

Inwieweit wurde so etwas umgesetzt, oder wie ist der Fortschritt in diese Richtung? Was sind die praktischen Hindernisse? Wie lässt sich das Problem angesichts der ursprünglichen Fragestellung am besten formalisieren?

*

Wie die Antworten zeigen (danke!), Können sowohl (A) als auch (B1) separat durchgeführt werden, obwohl es eher eine Forschungsfrage zu sein scheint, wenn sie zusammen durchgeführt werden.

Hier sind einige meiner ersten Gedanken zu dieser Frage (Warnung: ziemlich vage). Siehe auch meine Kommentare zu Martin Bergers Antwort.

Ich interessiere mich für die Programmiersprache, die dieselbe Programmiersprache modelliert , und nicht für eine einfachere (also P = Q oben). Dies wäre ein "Proof of Concept" für ein Programm, das "über seinen eigenen Quellcode nachdenken kann". Abhängig getippte Programmiersprachen können Garantien für die Ausgabe ihrer Funktionen geben, aber dies gilt nicht mehr als "Begründen des eigenen Quellcodes" als "Hallo Welt!" Zählt als Quine in einer Sprache, die automatisch einen nackten String ausgibt - es muss eine Art Zitat / Selbstreferenz geben. Das Analoge hier ist ein Datentyp, der Program darstellt.

Es scheint ein ziemlich großes Projekt zu sein - je einfacher die Sprache, desto schwieriger ist es, alles darin auszudrücken; je komplizierter die sprache, desto mehr arbeit muss geleistet werden, um die sprache zu modellieren.

Im Geiste des Rekursionssatzes kann ein Programm dann seinen eigenen Quellcode "holen" und ihn modifizieren (dh eine modifizierte Version von sich selbst ausgeben). (B2) sagt uns dann, dass das Programm in der Lage sein sollte, eine Garantie für das geänderte Programm auszudrücken (dies sollte wiederverwendbar sein, dh es sollte in der Lage sein, etwas über alle zukünftigen Änderungen auszudrücken-?).

Holden Lee
quelle
1
Warum muss die Sprache als Theorembeweiser fungieren, um festzustellen, dass "das Ergebnis der Ausführung von Programm p foo ist"? Die Sprache könnte einfach p! Genau das passiert.
Martin Berger
3
Beachten Sie, dass im Prinzip jede Sprache, die einen Dolmetscher für sich selbst implementieren kann, die von Ihnen gewünschten Aufgaben ausführen kann. In mathematischer Hinsicht gilt der Rekursionssatz für jedes ausreichend starke Rechenmodell. Einige Programmiersprachen machen es einfach einfacher, indem sie eingebaut werden. Dasselbe gilt für die Argumentation: Sie können jedes Argumentationssystem innerhalb dieser Sprachen implementieren. Natürlich kann man nicht erwarten, alles zu begründen, zB das Halteproblem für die Programme.
Kaveh,
2
Ich denke, die Frage ist nicht sehr klar. Sie sollten sich die Programmiersprachen wie Python, Java und die von Martin in seiner Antwort erwähnten ansehen und die Frage klären, damit entweder klar ist, dass sie dem entsprechen, wonach Sie suchen, oder wenn nicht, warum nicht.
Kaveh,
1
@HoldenLee In Bezug auf "P = Q" ist die etablierte Terminologie "homogene Metaprogrammierung", die der "heterogenen Metaprogrammierung" entgegengesetzt ist, bei der P Q.
Martin Berger

Antworten:

14

Ich denke, Sie fragen nach zwei verschiedenen Dingen.

  • Die Fähigkeit einer Programmiersprache, alle ihre Programme als Daten darzustellen.
  • Argumentation über Programme als Daten.

Für analytische Zwecke ist es nützlich, sie getrennt zu halten. Ich werde mich auf Ersteres konzentrieren.

Die Fähigkeit eines Programmiersprachen darzustellen, zu manipulieren (und Lauf) ihre Programme als Daten unter Begriffen wie gehen Meta-Programmierung oder Homoikonizität .

Auf (umständliche) Weise können alle bekannten Programmiersprachen Metaprogramme erstellen, indem sie den Datentyp string zusammen mit der Möglichkeit verwenden, externe Programme (Compiler, Linker usw.) für Strings aufzurufen (z. B. indem sie in die Datei geschrieben werden) System zuerst). Das meinen Sie aber wahrscheinlich nicht. Sie haben wahrscheinlich eine gute Syntax im Sinn. Strings sind keine gute Syntax für die Programmdarstellung, da fast alle Strings keine Programme darstellen, dh der Datentyp "string" enthält eine Menge "Junk", wenn er als Mechanismus für die Programmdarstellung angesehen wird. Erschwerend kommt hinzu, dass die Algebra der Zeichenfolgenoperationen im Wesentlichen keinen Zusammenhang mit der Algebra der Programmkonstruktion hat.

Was Sie wahrscheinlich im Sinn haben, ist etwas viel Schöneres. Zum Beispiel , wenn ein Programm ist, dann P ist P , sondern als Daten zur Hand zur Manipulation und Analyse. Dies wird oft als Zitat bezeichnet . In der Praxis ist das Zitat unflexibel, daher verwenden wir stattdessen das Quasi-Zitat , eine Verallgemeinerung des Zitats, bei der das Zitat "Lücken" aufweisen kann, in denen Programme ausgeführt werden können, die Daten zum "Füllen" der Lücken bereitstellen. Zum Beispiel i fPPP ist ein quasi-Zitat ein bedingtes darstelltdem anstelle einer Bedingungwir ein Loch [ ] . Wenn das Programm M auswertetum die Datenx > 0 , danndas quasi-Zitati f

ichf[]then7else8+9
[]Mx>0 auswertetum die Dateni f
ichf[M]then7else8+9
ichfx>0then7else8+9.

(Beachten Sie, dass ein normales Programm ist (kein Programm als Daten), das ein in Anführungszeichen gesetztes Programm zurückgibt, dh Programm als Daten.) Damit dies funktioniert, benötigen Sie einen Datentyp, um Programme darzustellen. Typischerweise heißt dieser Datentyp AST (abstract syntax tree), und Sie können (quasi) Anführungszeichen als Abkürzungsmechanismen für ASTs sehen.M

Mehrere Programmiersprachen bieten Quasi-Anführungszeichen und andere Funktionen für die Metaprogrammierung. Es war Lisp mit seiner Makrofunktionalität, das diese Fähigkeit, Programme als Daten zu behandeln, zum Pionier machte. Möglicherweise beruhte die Leistung von Lisp-basierten Makros lange Zeit weitgehend auf Lisps minimalistischer Syntax. Erst mit MetaML (1) wurde gezeigt, dass eine moderne, syntaktisch reiche Sprache zur Metaprogrammierung fähig ist. Seitdem sind MetaOCaml (2) (ein Nachkomme von MetaML, wichtig für seinen Durchbruch bei der noch andauernden Suche nach einer Lösung für das Problem der Typisierung von Programmen als Daten), Template Haskell (3) und Converge (4) (die erste Sprache von MetaML) Ich habe gezeigt, dass eine Vielzahl moderner Programmiersprachen Metaprogramme aufnehmen kann. Es ist wichtig zu erkennen, dass wir nehmen könnenjede Programmiersprache und verwandle sie in eine Meta-Programmiersprache L m p , die L ist, zusammen mit der Fähigkeit, ihre eigenen Programme als Daten darzustellen (und auszuwerten).LLmpL

eveinl()PPPPeveinl(P)PP

In Bezug auf die zweite Dimension werden Argumente zu Programmen als Daten angegeben. Sobald Sie Programme in Daten konvertieren können, handelt es sich um "normale" Daten, die als Daten interpretiert werden können. Sie können jede Art von Beweistechnologie verwenden, z. B. abhängige Typen oder Verträge oder interaktive Theorembeweiser oder automatisierte Werkzeuge, wie Joshua ausgeführt hat. Sie müssen jedoch die Semantik Ihrer Sprache im Argumentationsprozess darstellen. Wenn diese Sprache, wie Sie es wünschen, über Fähigkeiten zur Metaprogrammierung verfügt, können die Dinge etwas kompliziert werden und es wurde nicht viel in diese Richtung gearbeitet, wobei (5) die einzige Programmlogik für diesen Zweck ist. Es gibt auch Curry-Howard-basierte Arbeiten zur Argumentation über Meta-Programmierung (6, 7, 8). Beachten Sie, dass diese logikbasierten Ansätze, und der typbasierte Ansatz (2) kann tatsächlich Eigenschaften ausdrücken, die für alle zukünftigen Metaprogrammierungsstufen gelten. Abgesehen von (2) wurde keines dieser Papiere umgesetzt.

Zusammenfassend lässt sich sagen, dass das, wonach Sie gefragt haben, implementiert wurde, aber recht subtil ist und es noch offene Fragen gibt, insbesondere im Zusammenhang mit Typen und rationalisiertem Denken.


  1. W. Taha. Mehrstufige Programmierung: Theorie und Anwendungen .

  2. W. Taha und MF Nielsen. Umgebungsklassifikatoren .

  3. T. Sheard und S. Peyton Jones. Template-Metaprogrammierung für Haskell .

  4. L. Tratt. Metaprogrammierung zur Kompilierungszeit in einer dynamisch typisierten OO-Sprache .

  5. M. Berger, L. Tratt, Programmlogik für homogene Metaprogrammierung .

  6. R. Davies, F. Pfenning, Eine Modalanalyse der Stufenberechnung .

  7. R. Davies, Ein zeitlogischer Ansatz zur Bindungszeitanalyse .

  8. T. Tsukada, A. Igarashi. Eine logische Grundlage für Umgebungsklassifizierer .

Martin Berger
quelle
Sie haben Recht - die Programmiersprache P kann sich von der Sprache Q unterscheiden, die Sätze / Beweise über Programme in dieser Sprache ausdrückt (zum Beispiel in Coq). Der Satz, über den ich nachdenke, lautet wie folgt: Angenommen, wir haben ein sorgfältig entworfenes Programm A_1. Thm: Für jedes n gilt: Programm A_n wird ausgegeben (m_n, A_ {n + 1}), wobei m_n eine ganze Zahl ist, A_ {n + 1} ein anderes Programm ist (z. B. erhalten durch Modifizieren von A_n auf irgendeine Weise). und für alle n gilt m_n> 0.
Holden Lee
(Die Science-Fiction-Version davon ist, dass wir einen "Beweis" haben, dass ein Programm, das sich ständig ändert, niemals den Knopf drücken wird, der eine nukleare Rakete abfeuert, oder dass das Programm immer eine bestimmte Menge optimiert.)
Holden Lee
Aus diesem Grund wollte ich zwischen dem Ausführen des Programms und der Überlegung, was das Programm ausgeben soll, unterscheiden. Wir möchten wissen, welche Eigenschaften es hat, bevor es ausgeführt wird, ohne es auszuführen. Beachten Sie, dass wenn A_n in der Lage sein soll, "seinen Quellcode zu ändern", um A_ {n + 1} zu erzeugen, P notwendigerweise über Metaprogrammierfähigkeiten verfügt (was uns in die Position von (5) versetzt).
Holden Lee
Es scheint mir immer noch interessant für P = Q zu sein. Hypothetisch ist A ein KI-Programm, und die Art und Weise, wie es sich ändern würde, ist, über seinen eigenen Code nachzudenken - z. B. Sätze über Codebits aufzuschreiben, sie zu beweisen und erst dann seinen Code zu ändern. Dann scheint es, dass P die Fähigkeiten von Q haben muss.
Holden Lee
@HoldenLee Es ist möglich, Programme wie A_n zu schreiben. Wenn Sie Zeichenfolgen als Vertreter von Programmen verwenden, kann dies in jeder beliebigen Sprache erfolgen. Wenn Sie Quasi-Anführungszeichen oder Ähnliches wünschen, ist dies beispielsweise in Converge möglich. Ich verstehe die Rolle von m_n in der Konstruktion nicht.
Martin Berger
6

Nein, es gibt kein aktuelles System, das alle vier Schritte in Ihrem System ausführt. Wenn Sie ein System entwerfen möchten, ist eine der ersten Anforderungen die homoikonische Sprache. Zumindest möchten Sie, dass Ihre Kernprogrammiersprache so klein wie möglich ist, damit sie funktioniert, wenn Sie das System betreten und beginnen, es selbst interpretieren zu lassen. Sie möchten also einen Metacircular-Interpreter, der Pionierarbeit geleistet hat. Andere Sprachen haben es auch getan, aber es gibt eine enorme Menge vorhandener Forschung über Lispeln.

Der erste Schritt, wenn Sie dies tun möchten, ist eine homoikonische Sprache wie Lisp oder ein Framework, in dem Sie über ein laufendes Programm nachdenken können. Lisp wird hierfür nur aus dem Grund verwendet, dass Sie einen Metacircular-Interpreter in der Sprache definieren oder Ihren Code einfach als Daten behandeln können. Das Wichtigste ist, den Code als Daten zu behandeln. Es wird diskutiert, was Homoiconic im c2-Wiki bedeutet.

In Lisp ist Ihr "Programm" -Datentyp beispielsweise ein gültiges Lisp-Programm. Sie übergeben die lisp-Programme an einen Interpreter und dieser berechnet etwas. Es wird vom Interpreter abgelehnt, wenn Sie kein gültiges "Programm" programmieren.

Daher erfüllt eine homoikonische Sprache drei Ihrer Anforderungen. Sie können sogar die Idee eines formalen Programms in Lisp definieren.

Können Sie lisp inside lisp modellieren? Ja, dies wird häufig hauptsächlich als Übung am Ende eines Lisp-Programmierbuchs durchgeführt, um Ihre Fähigkeiten zu testen. SICP

Zur Zeit ist die vierte Ausgabe eine Forschungsfrage und unten habe ich festgestellt, dass versucht wird, diese Frage zu beantworten.

Ich würde sagen, dass es viele Arten von Programmen gibt, die dies versuchen. Nachfolgend finden Sie alle mir bekannten Programme.

  • JSLint ist ein Beispiel für statische Analysatoren, die Maschinencode oder eine andere Sprache verwenden und explizit nach Fehlern suchen. Dann fordert es einen Programmierer auf, dies zu korrigieren.

  • Coq ist eine Umgebung, in der Sie Proofs mithilfe einer Programmiersprache angeben können. Es gibt auch Taktiken, mit denen Sie das Problem lösen können. Trotzdem erwartet dies, dass ein Mensch die Arbeit erledigt. Coq arbeitet mit abhängigen Typen und ist daher sehr typentheoretisch. Es ist sehr beliebt bei Informatikern und Leuten, die an der Homotopietypentheorie arbeiten.

  • ACL2 hingegen ist ein automatisierter Theorembeweiser. Dieses System prüft Aussagen, die auf etwas basieren, das Sie programmieren.

  • ACL2 und Coq haben ein Software-Plugin, das ihr System mit einem maschinellen Lernsystem verbindet . Was zum Trainieren dieser Systeme verwendet wird, sind zuvor geschriebene Programme. Nach meinem Verständnis fügen diese Systeme ein weiteres Merkmal hinzu, bei dem Sie nicht nur Ihre Taktik, sondern auch Theoreme vorgeschlagen haben, die bei der Beweisentwicklung helfen.

Im Folgenden finden Sie eine grundlegende Beschreibung Ihrer Frage.

  • gcc ist ein Beispiel für einen Optimierungs-Compiler, der sich selbst als Eingabe nehmen und dann eine optimierte Version von sich selbst ausgeben kann. Die Idee eines Compilers, der Programme von einer Darstellung in eine andere übersetzt und die Geschwindigkeit aufgrund eines Optimierungskennzeichens verbessert, ist sehr gut verstanden. Sobald Sie den Compiler gebootet haben und er gültigen Maschinencode generiert, können Sie eine Optimierung hinzufügen und den Compiler neu kompilieren. Dadurch wird eine effizientere Version von sich selbst erstellt.
Joshua Herman
quelle
1
Es ist nicht erforderlich, die Sprache so minimal wie möglich zu halten. Sie können jeder Sprache die relevanten Metaprogrammierfunktionen hinzufügen. Die MetaML-Arbeit von Taha hat dies gezeigt. In der Tat ist das Hinzufügen von Metaprogrammierfähigkeiten mechanisch.
Martin Berger
1
Ich bin auch anderer Meinung als "kein aktuelles System, das alle vier Schritte durchführt". Frage 4 befasst sich nur mit dem Ausführen von Programmen, die als Code angegeben sind. Das ist durchaus möglich, ja sogar die Auswertung von Javascript macht es.
Martin Berger
@MartinBerger Ich meine, du machst den Kernel so minimal wie möglich. Auch wenn Sie anfangen zu hoffen, dass Ihr System # 4 funktioniert, möchten Sie ein System, mit dem Sie nicht nur Menschen, sondern auch Computer trainieren können, sodass Sie von einem minimalen System profitieren, in dem Bibliotheken codiert sind das System wie eine Meta-Programmiervorlage
Joshua Herman
Es kommt darauf an, wovon (4) wir sprechen. Die ursprüngliche Frage enthält zwei Ausführungen davon. Das erste ist trivial, Sie führen nur das Programm aus. Die zweite kann von der Logik behandelt werden, die ich als (5) in meiner Antwort des Schreibsystems (2) zitiert habe. Letzteres ist in MetaOCaml implementiert. Es gibt jedoch noch Raum für weitere Untersuchungen: Weder (2) noch (5) können sich mit beliebigen Formen der Metaprogrammierung befassen, und die durch (2) garantierten Eigenschaften sind etwas schwach (schließlich handelt es sich um ein Typisierungssystem mit Typinferenz). .
Martin Berger
1
Bezüglich "Sie machen den Kernel so minimal wie möglich": Das ist nicht erforderlich. Sie können jeder Sprache eine vollständige Metaprogrammierung hinzufügen.
Martin Berger
5

In der Antwort von @ user217281728 heißt es , dass es eine Art von Maschinen gibt, die mehr mit Inferenz und KI zu tun haben , nämlich Gödel Machines

Eine Gödel-Maschine ist ein sich selbst verbesserndes Computerprogramm, das Jürgen Schmidhuber erfunden hat und das Probleme optimal löst. Es verwendet ein rekursives Selbstverbesserungsprotokoll, in dem es seinen eigenen Code umschreibt, wenn nachgewiesen werden kann, dass der neue Code eine optimalere Strategie bietet. Die Maschine wurde von Jürgen Schmidhuber erfunden, ist aber nach Kurt Gödel benannt, der die mathematischen Theorien inspirierte.

Die zitierte Veröffentlichung von Jürgen Schmidhuber über "Goedel-Maschinen: Selbstreferenzielle universelle Problemlöser, die nachweislich optimale Selbstverbesserungen bewirken" (2006), arXiv: cs / 0309048v5

Die Art und Weise, wie die Maschine arbeitet, um Meta-Lernen zu implementieren , besteht aus zwei Phasen:

  1. Aus Daten lernen (Stufe 1, lernen)
  2. Verwendung erlernter Daten zum Ändern / Optimieren des Quellcodes / Algorithmus (Stufe 2, Lernen lernen)

Da die Maschine ihre eigene Quelle ändert, ist sie selbstreferenziell, dh sie hat die Eigenschaft der Selbstmodifikation (siehe auch hier ).

In diesem Sinne kann es den Lernalgorithmus selbst im strengen Sinne modifizieren (als Beweis für optimale Selbstmodifikationen). Es gibt die Probleme mit Selbstreferenz und Unentscheidbarkeit, die in diesem Fall die Form annehmen:

..eine Gödel-Maschine mit unbegrenzten Rechenressourcen muss diejenigen Selbstverbesserungen ignorieren, deren Wirksamkeit sie nicht nachweisen kann

Andere Sprachen (und ihre zugeordneten Interpreter-Maschinen), die die Eigenschaft der Selbstmodifikation haben, sind beispielsweise LISP .

In LISP sind Code und Daten austauschbar, oder der Quellcode AST ist als Daten im LISP-Programm verfügbar und kann als Daten geändert werden. Andererseits können Daten für einige Quellcodes als AST angesehen werden.

aktualisieren

Es gibt auch andere Maschinen , wie beispielsweise Selbstprogrammiermaschinen , die Selbstreferenz , Selbstreproduktion und Selbstprogrammierung kombinieren .

Ein interessanter Aspekt der obigen Ausführungen ist, dass die Selbstreferenz überhaupt nicht problematisch ist , sondern ein notwendiges Element in Automaten zur Selbstreproduktion / Selbstprogrammierung ist .

Weitere Einzelheiten (und weitere Veröffentlichungen) finden Sie in JP Moulin, CR Biologies 329 (2006).

abstrakt

Lebende Systeme sind in der Lage, auf unvorhersehbare Umgebungen angemessen zu reagieren. Diese Art der Selbstorganisation scheint als Selbstprogrammierungsmaschine zu funktionieren, dh als eine Organisation, die sich selbst modifizieren kann. Als Modelle der Selbstorganisation von Lebewesen werden bisher Funktionslösungen von Differenzialsystemen oder Übergangsfunktionen von Automaten vorgeschlagen. Diese Funktionen sind fest und diese Modelle können daher ihre Organisation nicht ändern. Andererseits schlägt die Informatik viele Modelle vor, die die Eigenschaften adaptiver Systeme von Lebewesen haben, aber alle diese Modelle hängen vom Vergleich zwischen einem Ziel und den Ergebnissen und der ausgeklügelten Auswahl von Parametern durch Programmierer ab, während es keine Absicht des Programmierers gibt noch Wahl in den lebenden Systemen.mspMsp

Nikos M.
quelle
3

Dieser Artikel von Jürgen Schmidthuber könnte Sie interessieren:

http://arxiv.org/pdf/cs/0309048.pdf

NietzscheanAI
quelle
Bitte geben Sie mindestens eine Zusammenfassung
vzn