Die logische Quine

8

Die Herausforderung

Schreiben Sie einfach ein Programm, das seinen eigenen Quellcode ausgibt.

Nichts weiter als eine normale Quine.

Das Problem

Wir haben keinen Computer, daher müssen wir das Programm auf einem programmierbaren Logikgerät (wie einem FPGA, einer CPLD, einem Gate-Array ...) ausführen.

Die Regeln

  • Jedes auf dem Markt erhältliche Gerät (z. B. ein über den Centronics-Anschluss angeschlossener Drucker, eine LED-Anzeige, ein RS232-Anschluss ...), der an das Logikgerät angeschlossen ist, kann zur Ausgabe des Programms verwendet werden.
  • Wenn Sie ein programmierbares Gerät als Ausgabegerät verwenden, dürfen Sie dort keine Programmlogik einfügen!

    Beispiel: Wenn Sie RS232 zum Senden von Daten an einen Computer verwenden, darf der Computer nur die vom RS232 empfangenen Daten anzeigen. Sie können jedoch RS232-Optionen wie das Zurücksenden von Daten an das Logikgerät aktivieren, wenn ein vorhandenes Terminalprogramm über diese Funktion verfügt.

  • Jede (aktuelle oder historische) "Standard" -Codierung (ASCII, UNICODE, EBCDIC, Morsecode ...) kann verwendet werden.

  • Das Programm muss nur seinen eigenen Quellcode ausgeben. Die Datei, die nur die Zuordnung zwischen VHDL / Verilog / ... "Wires" und den tatsächlichen E / A-Pins enthält, die Datei mit den Compilereinstellungen und ähnlichen Dateien gelten nicht als "Quellcode" und müssen nicht geschrieben werden.
  • Sie haben einen Takteingangspin mit der Frequenz Ihrer Wahl (falls erforderlich).
  • On-Chip-Einheiten (wie On-Chip-SRAM oder On-Chip-Multiplikatoren) dürfen nicht verwendet werden.
  • Zum Testen des Codes können Sie das Ausgabegerät mit zusätzlichem Code simulieren. Natürlich können Sie auch das Logikgerät simulieren (wenn Sie kein echtes haben).
  • Es gelten Standardlücken.

Der Gewinner

  • Zur Berechnung der Programmgröße wird davon ausgegangen, dass das reale Ausgabegerät (z. B. der Drucker) mit einigen E / A-Pins des Logikgeräts verbunden ist.
  • Der Code, der die wenigsten "LE" -Zellen auf meinem FPGA (Altera EP2C20F484C7) benötigt, gewinnt.
  • Wenn mein FPGA zu klein ist (= nicht groß genug für die kleinste Lösung), kompilieren wir für das größte mit Zellen vom Typ "LE" (EP4CGX150DF31I7).
  • Wenn dies immer noch nicht ausreicht, versuchen wir es mit dem größten, der vom kostenlosen Compiler (EP2AGX260FF35I5) unterstützt wird.
  • Wenn das Gerät immer noch zu klein ist, zählt die Größe des Quellcodes.

Hinweis

Bei der Suche nach "quine VHDL" in Google habe ich auf der ersten Seite mindestens drei in VHDL geschriebene quines gefunden!

Leider funktioniert keiner von ihnen auf einem echten Logikgerät, sondern nur im Emulator, da der Standardausgang (des Emulators) verwendet wird.

Viel Glück!

Martin Rosenau
quelle

Antworten:

6

Verilog, flächenoptimiert, 130 LE-Tore

Das Quine selbst (die eigentliche Datei ist in DEC SIXBIT codiert ):

module q(s,d);inout s,d;wire[0:1023]v=1024'b0110111100101001011001111110110110010110100100001111011010010111010101110101010110010110111100101001011001111110110100100110100100001111011010100111010101110110111000011100111100111010011001111011100000001001000111011010100111000101100111111010100111010111010100100110101101101110111010011111010110111000011011001101111000011110011100111000000010001100001011111100111001011001001001111001010000001100110010011010011001100010001010100111100101010010011000101001011001111010011011100000001010010111011010010010110100010110111010100111011010100001100100011111100000011010010111110101110110100100010110111001011011101001000000001001011011001100111001010000001010100111011010100010110100010110111001011011101001001011011011111001001101011011001001010000000000000000101101101111100100110101101100100101000000110001001000110011001100100100001001011011101001101110101111110101110100000000110011001100100100011011110111101001110010100101111011010000011010010001010000010010010011111101110110011101010001010000010010010100000111100010;reg[9:0]i=759;reg[2:0]j=7;assign d=j<6?j==2:v[i];always@(posedge s)if(j>5)begin i=i+1;j=j&1^!i?7:1;end else j=j+1;endmodule

Lesbare Version mit Kommentaren und einer Testbench:

module q(s,d);
   // Declare the ports. Making them both "inout" is shortest.
   inout s,d;
   // Data storage for the program.
   wire[0:1023]v=1024'b{DATA GOES HERE};
   // i is the current bit number within the program.
   // This is relative to the /end of the data storage/ (not to the start
   // of the program), so it starts at a nonzero value so that the output
   // starts at the start of the program.
   reg[9:0]i=759;
   // When expanding bits to (6-bit) bytes, j is the bit number within
   // the expansion, from 1 for the first bit up to 6 for the last.
   // When not expanding, j is always 7.
   // DEC SIXBIT encoding for 0 is (from MSB to LSB) 010 000.
   // DEC SIXBIT encoding for 1 is (from MSB to LSB) 010 001.
   // We use SSI encoding for the output, so the MSB is sent first.
   reg[2:0]j=7;
   assign d=j<6?j==2:v[i];
   // When we get a strobe:
   always@(posedge s)
     // If we just output a bit, move onto the next bit.
     // We may also need to reset j.
     if(j>5)
       begin 
          i=i+1;
          j=j&1^!i?7:1;
       end 
     else 
       // If we're inside a bit, continue to output that bit.
       j=j+1;
endmodule
// {TESTBENCH BELOW HERE}

`timescale 10ns / 1ns
module testbench();
   reg clock = 0;
   wire data, strobe;

   always
     #1 clock <= !clock;
   initial
     #14304 $finish;

   assign strobe = clock;
   q testquine(.s(strobe),.d(data));

   always @(negedge strobe)
      $display("%d", data);

endmodule // testbench

Durch die Verwendung von Verilog habe ich erheblich mehr Kontrolle über die Details auf niedriger Ebene als mit Verity. Insbesondere kann ich damit die Uhr steuern und die Regeln selbst zurücksetzen. Dieses Programm ist für eine synchrone serielle Verbindung mit Strobe-Eingang sund Datenausgang vorgesehend. Obwohl jedes nur in einer Richtung verwendet wird, habe ich beide als bidirektional deklariert, um einige Bytes zu sparen. Ich musste die Nicht-Daten-Teile des Programms auf 1024 Bit reduzieren, um 10-Bit-Logikgatter intern verwenden zu können (zusätzliche Bits wären flächenmäßig teurer), und es kratzt nur knapp unter 1008, also Einsparungen wie das ist wichtig. Um eine beträchtliche Menge an Code zu sparen, verlasse ich mich auf die Hardware-Reset-Schaltung des FPGA, anstatt meine eigene hinzuzufügen, und füge die Strobe- und Clock-Eingänge zusammen (ein alter Trick, der heutzutage verpönt ist, weil er es schwierig macht um den Uhrenbaum bei hohen Taktraten im Gleichgewicht zu halten, aber es ist nützlich zum Golfen.) Ich hoffe, das ist synthetisierbar; Ich weiß nicht, wie gut Verilog-Synthesizer mit der Verwendung eines bidirektionalen Ports als Uhr umgehen können.

Die Quelle ist in DEC SIXBIT codiert (ich gehe hier davon aus, dass wir das einzelne Buchstabenalphabet als Kleinbuchstaben interpretieren; ein Verilog-Synthesizer hätte keinen Grund, eine Großbuchstabeninterpretation zu verwenden). Ich habe in meiner anderen Lösung intern einen Sechs-Bit-Zeichensatz verwendet und dann Bytes verschwendet, um ihn zu konvertieren. Es ist besser, einen Zeichensatz zu verwenden, der "natürlich" sechs Bit breit ist, damit keine Konvertierung erforderlich ist. Ich habe diesen speziellen Sechs-Bit-Zeichensatz ausgewählt, weil 0und 1sich nur in ihrem niedrigstwertigen Bit unterscheiden und nur ein anderes Bit gesetzt ist, was bedeutet, dass die Schaltung zum Konvertieren einer Binärziffer in DEC SIXBIT (dh "Escape" einer Zeichenfolge) sehr sein kann einfach. Interessanterweise fehlt dem fraglichen Zeichensatz ein Zeilenumbruchzeichen. Das ursprüngliche Programm ist nicht nur in einer Zeileum das Generieren zu vereinfachen, aber das Codieren zu ermöglichen! Es ist gut, dass Verilog sich hauptsächlich nicht um Leerzeichen kümmert.

Das Protokoll zum Senden von Daten an den Host basiert auf der synchronen seriellen Schnittstelle. Ich habe es ausgewählt, weil es getaktet ist (was mir erlaubt, den Clock / Strobe-Trick zu verwenden und ein tragbares Programm zu schreiben, das nicht auf On-Chip-Timing-Geräten basiert) und weil es sehr einfach ist (also nicht müssen viel Code verschwenden, um es zu implementieren). Dieses Protokoll gibt keine Methode zum Festlegen an, wo die Nachricht endet (der Host soll es wissen). In diesem speziellen Fall habe ich die Ausgabe mit Null-Bits (insgesamt 16 Füllbits) auf ein Vielfaches von 1024 Bits aufgefüllt. Danach wird die Nachricht (wie von SSI gefordert) neu gestartet. (Ich implementiere keinen Timer für den Leerlaufmodus. Er dient dazu zu bestimmen, ob eine neue Nachricht gesendet oder die vorherige Nachricht wiederholt werden soll. Da dieses Programm immer seinen eigenen Quellcode als Nachricht sendet, ist die Unterscheidung nicht sichtbar Sie können es als Länge 0 betrachten,

In Bezug auf die tatsächliche Logik ist das Interessanteste die Art und Weise, wie ich die Variablen aufteile, um die auf dem Chip benötigte Fläche zu reduzieren. iDas größere Register enthält die aktuelle "Adresse" in den Programmdaten und wird immer nur durch Inkrementieren geändert. Dies bedeutet, dass seine Logik mithilfe der Halbaddierer-Konstruktion synthetisiert werden kann (die, wie der Name schon sagt, nur die Hälfte der Ressourcen eines Addierers verbraucht; dies ist meist nur bei den kleinsten FPGAs von Bedeutung, bei größeren mit 3 Eingängen oder sogar 4-Eingangs-LUTs, die so leistungsfähig sind, dass sie viel verschwendete Kapazität haben, um einen Halbaddierer zu synthetisieren. Das kleinere Register,jist im Grunde ein Zustandsmaschinenzustand und behandelt daher den größten Teil der komplexen Logik des Programms. Es ist klein genug, dass es vollständig über eine Nachschlagetabelle auf einem größeren FPGA verarbeitet werden kann (wodurch die Logik im Grunde verschwindet). Für den Fall, dass das Programm für ein kleines FPGA synthetisiert wird, habe ich seine Codierung so gewählt, dass sich nur wenige Teile des Codes um alle drei Bits gleichzeitig kümmern.

Es ist auch erwähnenswert, dass ich den Datenspeicher zyklisch permutiert habe. Wir können iüberall darauf zeigen, nicht unbedingt am Anfang. Mit der hier gezeigten Anordnung können wir idirekt vom Anfangswert bis zum Ende drucken, dann das gesamte Array maskieren und dann vom Anfang bis zum Anfangswert von idrucken, um alle Teile der Daten im zu drucken richtige Orte, ohne den Wert von speichern und wiederherstellen zu müssen i. (Dieser Trick kann auch für Quines in anderen Sprachen nützlich sein.)

Die Quelle ist 1192 6-Bit-Bytes lang, was 894 8-Bit-Bytes entspricht. Es ist irgendwie peinlich, dass dies weniger Quellbytes enthält als meine Verity-Übermittlung, obwohl es für etwas ganz anderes optimiert wurde. Dies liegt hauptsächlich daran, dass Verilog Zeichenfolgen hat und Verity nicht, was bedeutet, dass ich jedes Byte des Programms codieren kann, obwohl ich das Programm eher binär als oktal codiert habe (was in Bezug auf die Quellcodegröße wesentlich weniger effizient ist) Verwenden von sechs Sechs-Bit-Zeichen (eines für jedes Bit) anstelle von acht Acht-Bit-Zeichen (vier für jede Oktalstelle). Eine Verilog-Übermittlung, die das Programm in Oktal codiert, wäre wahrscheinlich kleiner in Bezug auf die Quellcode-Größe, aber mit ziemlicher Sicherheit größer in der Fläche.

Ich weiß nicht, wie viel Fläche dieses Programm letztendlich nutzen wird. Dies hängt stark davon ab, wie leistungsfähig der Optimierer in Ihrem Verilog-Synthesizer ist (da das Minimierungsproblem beim Konvertieren der gespeicherten Daten in eine Reihe von Logikgattern im Synthesizer selbst ausgeführt wird. Wenn Sie die Arbeit auf den Synthesizer übertragen, wird der Quellcode selbst erstellt viel kürzer und reduziert somit die zum Speichern benötigte Fläche). Es sollte jedoch eine Komplexität von O (n log n) haben und daher viel kleiner sein als das O (n²) des anderen Programms. Es würde mich interessieren, wie das OP versucht, es auf seinem FPGA auszuführen. (Die Synthese kann jedoch einige Zeit in Anspruch nehmen. Sie können verschiedene Schritte ausführen, um ein Programm für die Kompilierungszeit zu optimieren, aber ich habe hier keine Schritte unternommen, da dies zu einem größeren Programm = größerer Fläche führen würde.)


quelle
1
Der erste Compilerlauf besagt, dass nur 130 LE-Gates verwendet werden. Da ein LE-Gatter nur 2 Datenbits speichern kann und Sie einen ~ 750-Bit-Datenstrom verwenden, kann dies bedeuten, dass der Compiler die Daten komprimiert hat oder dass beim Kompilieren ein Fehler aufgetreten ist. Morgen früh werde ich überprüfen, ob das Compiler-Ergebnis korrekt ist.
Martin Rosenau
Bei dieser Konstruktion wird ein Großteil der Daten im Verbindungsmuster zwischen den Gates und nicht den Gates selbst gespeichert, sodass ich glauben kann, dass 130 LE-Gates korrekt sind. (Der Synthesizer erzwingt im Grunde genommen eine Formel, die einen 10-Bit-Index einem 1-Bit-Wert zuordnet. Ich habe die Formel im Verilog-Programm mithilfe einer Nachschlagetabelle mit 1024 Einträgen angegeben, aber der Synthesizer verwendet sehr wahrscheinlich mehr Effiziente Darstellung basierend auf so etwas wie einer K-Map-Minimierung.)
Oh, Sie sollten wahrscheinlich auch überprüfen, ob der Compiler einen Teil des Codes nicht in einen Block-RAM oder Block-ROM optimiert hat (von der Frage nicht zugelassen). Ich habe keinen angefordert und den Code nicht in einer Form geschrieben, die einen impliziert (ich habe darauf geachtet, die Nachschlagetabelle kombinatorisch zu gestalten), aber manchmal machen Compiler-Optimierungen seltsame Dinge. Wenn eine Optimierung dies stört, müssen Sie die Optimierung deaktivieren.
1
OK. Ich habe die Probleme mit den Pins jetzt geschafft. Der Code scheint gut zu funktionieren. Hervorragend. Nur 130 LE-Zellen! RAM, ROM usw. wird nicht verwendet. Ich denke, der Compiler führt einige Optimierungen ähnlich wie bei KV-Diagrammen durch, um die Daten zu "komprimieren".
Martin Rosenau
1
Du gewinnst! Herzliche Glückwünsche.
Martin Rosenau
3

Verity 0.10, optimiert für die Quellcodegröße (1944 Bytes)

Ich habe die Frage ursprünglich falsch verstanden und als interpretiert. Das war wahrscheinlich das Beste, da es unter den Einschränkungen in der Frage viel einfacher ist, eine Quine mit kurzem Quellcode als kurzen Objektcode zu schreiben. Das machte die Frage so einfach, dass ich das Gefühl hatte, eine vernünftige Antwort liefern zu können und als Sprungbrett auf dem Weg zu einer besseren Antwort zu fungieren. Es veranlasste mich auch, eine höhere Sprache für die Eingabe zu verwenden, was bedeutet, dass ich im Programm selbst weniger ausdrücken müsste. Ich habe Verity nicht als Golfsprache für Hardware erstellt (ich wurde tatsächlich vor einiger Zeit beauftragt, es in einem völlig anderen Kontext zu erstellen), aber es gibt dort eine ziemliche Reminiszenz (z. B. ist es wesentlich höher als ein typisches HDL, und das ist es auch hat viel weniger Boilerplate; es ist auch viel tragbarer als das typische HDL).

Ich bin mir ziemlich sicher, dass die richtige Lösung für kurzen Objektcode darin besteht, die Daten in einer Baumstruktur zu speichern, da die Frage die Verwendung des Block-ROMs verbietet, in dem Sie sie normalerweise in einem praktischen Programm speichern würden. Ich könnte versuchen, irgendwann ein Programm zu schreiben, das dieses Prinzip verwendet (nicht sicher, welche Sprache, vielleicht Verity, vielleicht Verilog; VHDL hat zu viel Boilerplate, um für diese Art von Problem wahrscheinlich optimal zu sein). Das würde bedeuten, dass Sie nicht jedes Bit des Quellcodes an jedes Bit Ihres "manuell erstellten ROM" übergeben müssen. Der Verity-Compiler synthetisiert derzeit jedoch die Struktur der Ausgabe basierend auf der Priorität und Assoziativität der Eingabe, was bedeutet, dass er den Befehlszeiger (also den Index zur Nachschlagetabelle) effektiv in unär darstellt.

Das Programm selbst:

import <print>new x:=0$1296in(\p.\z.\a.new y:=(-a 5-a 1-a 1-a 2-a 4-a 2-a 3-a 2-a 6-a 2-a 0-a 3-a 0-a 4-a 4-a 7-a 4-a 2-a 6-a 2-a 5-a 1-a 2-a 2-a 0-a 3-a 6-a 7-a 2-a 2-a 1-a 1-a 3-a 3-a 0-a 4-a 4-a 3-a 2-a 7-a 5-a 7-a 0-a 6-a 4-a 4-a 1-a 6-a 2-a 6-a 1-a 7-a 6-a 6-a 5-a 1-a 2-a 2-a 0-a 5-a 0-a 0-a 4-a 2-a 6-a 5-a 0-a 0-a 6-a 3-a 6-a 5-a 0-a 0-a 5-a 0-a 6-a 5-a 2-a 2-a 1-a 1-a 3-a 3-a 0-a 4-a 5-a 3-a 2-a 7-a 5-a 7-a 0-a 5-a 5-a 5-a 1-a 4-a 4-a 3-a 1-a 5-a 5-a 1-a 2-a 2-a 0-a 4-a 3-a 3-a 4-a 1-a 5-a 1-a 0-a 2-a 1-a 1-a 1-a 4-a 4-a 3-a 6-a 7-a 0-a 6-a 0-a 1-a 3-a 2-a 0-a 5-a 4-a 2-a 0-a 5-a 5-a 1-a 2-a 1-a 0-a 4-a 6-a 3-a 4-a 7-a 3-a 6-a 2-a 6-a 0-a 3-a 4-a 1-a 1-a 1-a 2-a 2-a 0-a 4-a 6-a 3-a 3-a 5-a 1-a 7-a 2-a 6-a 1-a 1-a 0-a 2-a 7-a 2-a 1-a 1-a 0-a 4-a 6-a 3-a 1-a 5-a 3-a 7-a 5-a 1-a 2-a 1-a 0-a 4-a 6-a 3-a 5-a 7-a 5-a 7-a 4-a 6-a 5-a 6-a 0-a 3-a 4-a 1-a 1-a 1-a 2-a 2-a 0-a 4-a 3-a 3-a 4-a 1-a 5-a 1-a 0-a 2-a 1-a 1-a 1-a 4-a 5-a 3-a 6-a 7-a 0-a 6-a 0-a 1-a 3-a 2-a 0-a 5-a 4-a 2-a 0-a 4-a 1-a 7-a 7-a 6-a 3-a 7-a 4-a 2-a 0-a 4-a 3-a 6-a 2-a 6-a 3-a 7-a 4-a 2-a 0-a 5-a 4-a 6-a 0-a 7-a 2-a 0-a 1-a 4-a 5-a 3-a 4-a 4-a 4-a 4-a 3-a 6-a 4-a 4-a 4-a 4-a 3-a 6-a 2-a 6-a 1-a 5-a 3-a 7-a 4-a 2-a 0-a 4-a 4-a 6-a 5-a 6-a 3-a 7-a 5-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 5-a 3-a 6-a 7-a 6-a 7-a 3-a 6-a 1-a 5-a 1-a 1-a 0-a 2-a 7-a 2-a 1-a 1-a 0-a 4-a 7-a 2-a 7-a 1-a 5-a 1-a 4-a 2-a 3-a 7-a 4-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 4-a 3-a 6-a 7-a 6-a 7-a 6-a 6-a 1-a 5-a 1-a 5-a 4-a 2-a 6-a 2-a 5-a 1-a 2-a 2-a 0-a 3-a 0-a 5-a 1-a 4-a 4-a 3-a 4-a 4-a 4-a 4-a 6-a 6-a 4-a 4-a 4-a 4-a 3-a 6-a 2-a 6-a 1-a 5-a 0-a 5-a 0-a 0-a 0-a 1-a 6-a 5-a 4-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 4-a 3-a 6-a 7-a 6-a 7-a 3-a 6-a 2-a 0-a 0-a 1-a 4-a 7-a 4-a 7-a 1-a 6-a 2-a 6-a 1-a 7-a 3-a 6-a 3-a 7-a 0-a 6-a 1-a 5-!x)in while!x>0do(p(if z<32then z+92else z);if z==45then while!y>0do(p 97;p 32;p(48^!y$$3$$32);p 45;y:=!y>>3)else skip;x:=!x>>6))print(!x$$6$$32)(\d.x:=!x>>3^d<<1293;0)

Besser lesbar:

import <print>
new x := 0$1296 in
(\p.\z.\a.
  new y := (-a 5-a 1-
            # a ton of calls to a() omitted...
            -a 1-a 5-!x) in
  while !x>0 do (
    p(if z<32 then z+92 else z);
    if z==45
    then while !y>0 do (
      p 97;
      p 32;
      p(48^!y$$3$$32);
      p 45;
      y:=!y>>3 )
    else skip;
    x:=!x>>6
  )
)(print)(!x$$6$$32)(\d.x:=!x>>3^d<<1293;0)

Die Grundidee ist, dass wir die gesamten Daten in der Variablen speichern x. (Wie bei einem Quine üblich, haben wir einen Codeabschnitt und einen Datenabschnitt. Die Daten codieren den Text des Codes und können auch zum Neuerstellen des Textes der Daten verwendet werden.) Leider lässt Verity derzeit keine sehr großen Daten zu Konstanten, die in den Quellcode geschrieben werden sollen (es werden OCaml-Ganzzahlen während der Kompilierung verwendet, um Ganzzahlen in der Quelle darzustellen, was in einer Sprache, die beliebig breite Ganzzahltypen unterstützt, eindeutig nicht korrekt ist) - und außerdem erlaubt es keine Konstanten in oktal angegeben - also generieren wir den Wert von xzur Laufzeit durch wiederholte Aufrufe einer Funktiona. Wir könnten eine void-Funktion erstellen und sie wiederholt als separate Anweisungen aufrufen, aber das würde es schwierig machen zu identifizieren, wo mit der Ausgabe des Textes des Datenabschnitts begonnen werden soll. Also habe ich stattdessen aeine Ganzzahl zurückgegeben und die Daten mit Arithmetik gespeichert (Verity garantiert, dass die Arithmetik von links nach rechts ausgewertet wird). Der Datenabschnitt wird xmit einem einzelnen -Vorzeichen codiert . Wenn dies zur Laufzeit auftritt, wird es -a 5-a 1-über die Verwendung von vollständig usw. erweitert y.

Das Initialisieren yals Kopie von xist hier ziemlich subtil. Da aspeziell Null zurückgegeben wird, ist der größte Teil der Summe nur Null minus Null minus… und bricht sich selbst ab. Wir enden mit !x(dh "dem Wert von x"; in Verity wie in OCaml funktioniert der Name einer Variablen eher wie ein Zeiger als alles andere, und Sie müssen ihn explizit dereferenzieren, um den Wert der Variablen zu erhalten). Veritys Regeln für unäres Minus sind ein wenig komplex - das unäre Minus von vwird als geschrieben (-v)- (-0-0-0-!x)analysiert also als (-(0-0-0-!x)), was gleich ist !x, und wir werden am Ende yals Kopie von initialisiert x. (Es ist auch erwähnenswert, dass Verity nicht istCall-by-Value, sondern ermöglicht es Funktionen und Operatoren, die Reihenfolge zu wählen, in der sie die Dinge bewerten. -bewertet das linke Argument vor dem rechten Argument, und insbesondere wenn das linke Argument Nebenwirkungen hat, werden diese sichtbar, wenn das rechte Argument ausgewertet wird.)

Jedes Zeichen des Quellcodes wird mit zwei Oktalziffern dargestellt. Dies bedeutet, dass der Quellcode auf 64 verschiedene Zeichen beschränkt ist, sodass ich meine eigene Codepage für den internen Gebrauch erstellen musste. Die Ausgabe erfolgt in ASCII, daher musste ich intern konvertieren. Dafür ist das da (if z<32 then z+92 else z). Hier ist der Zeichensatz, den ich in der internen Darstellung verwendet habe, in numerischer Reihenfolge (dh \hat Codepunkt 0, ?hat Codepunkt 63):

\]^_`abcdefghijklmnopqrstuvwxyz{ !"#$%&'()*+,-./0123456789:;<=>?

Dieser Zeichensatz gibt uns die meisten für Verity wichtigen Zeichen. Bemerkenswerte fehlende Zeichen sind }(was bedeutet, dass wir keinen Block mit erstellen können {}, aber zum Glück sind alle Anweisungen Ausdrücke, sodass wir ()stattdessen verwenden können); und |(aus diesem Grund musste ich beim Erstellen des Werts von ein exklusives statt einschließendes ODER verwenden x, was bedeutet, dass ich es auf 0 initialisieren muss; ich musste jedoch angeben, wie groß es trotzdem war). Einige der kritischen Zeichen, die ich sicherstellen wollte, befanden sich im Zeichensatz: <>(für Importe, auch Verschiebungen) ()(sehr schwer zu schreiben, ein Programm, das ohne diese analysiert werden kann), $(für alles, was mit Bitbreite zu tun hat) und \( Für Lambdas könnten wir theoretisch damit umgehenlet…in aber es wäre viel ausführlicher).

Um das Programm etwas kürzer zu machen, habe ich Abkürzungen für printund für !x$$6$$32(dh "die unteren 6 Bits von !x, die für die printBibliothek verwendbar sind ) erstellt , indem ich sie vorübergehend an Lambda-Argumente gebunden habe.

Schließlich gibt es das Problem der Ausgabe. Verity bietet eine printBibliothek, die für die Debug-Ausgabe vorgesehen ist. Auf einem Simulator werden die ASCII-Codes auf die Standardausgabe gedruckt, die perfekt zum Testen des Programms verwendet werden kann. Auf einer physischen Leiterplatte hängt es davon ab, dass eine printBibliothek für den bestimmten Chip und die Platine geschrieben wurde, die sie umgeben. printIn der Verity-Distribution befindet sich eine Bibliothek für eine Evaluierungskarte, auf die ich Zugriff hatte und die die Ausgabe auf Sieben-Segment-Displays druckt. Angesichts der Tatsache, dass die Bibliothek am Ende Platz auf der resultierenden Leiterplatte beansprucht, kann es sinnvoll sein, eine andere Sprache für eine optimierte Lösung dieses Problems zu verwenden, damit wir die Bits der Ausgabe direkt auf Drähten ausgeben können.

Übrigens ist dieses Programm auf der Hardware O (n²), was bedeutet, dass es auf einem Simulator viel schlimmer ist (ich vermute O (n⁴); ich bin mir zwar nicht sicher, aber es war schwer genug zu simulieren, dass es unwahrscheinlich ist, dass es überhaupt kubisch ist und basierend darauf, wie die Zeit auf meine Änderungen reagierte, als ich das Programm schrieb, scheint die Funktion tatsächlich sehr schnell zu wachsen. Der Verity-Compiler benötigte 436 Optimierungsdurchläufe (was viel, viel mehr ist als normalerweise), um das Programm zu optimieren, und selbst danach war es für meinen Laptop sehr schwierig, es zu simulieren. Der vollständige Kompilierungs- und Simulationslauf dauerte folgende Zeit:

real  112m6.096s
user  105m25.136s
sys   0m14.080s

und erreichte einen Höchstwert von 2740232 Kibibyte Speicher. Das Programm benötigt insgesamt 213646 Taktzyklen. Es funktioniert aber!

Wie auch immer, diese Antwort erfüllt die Frage nicht wirklich, da ich für das Falsche optimiert habe, aber da es noch keine anderen Antworten gibt, ist dies standardmäßig die beste (und es ist schön zu sehen, wie eine Golf-Quine aussehen würde eine Hardwaresprache). Ich bin mir derzeit nicht sicher, ob ich an einem Programm arbeiten werde, das darauf abzielt, einen optimierten Ausgang auf dem Chip zu erzeugen. (Es wäre wahrscheinlich viel größer in Bezug auf die Quelle, da eine O (n) -Datencodierung ziemlich komplexer wäre als die hier gezeigte.)


quelle
Was ist die Punktzahl für das primäre Kriterium (LE-Gatter, die auf dem angegebenen FPGA verwendet werden)?
Mego
Nein, ich meine, welche Punktzahl erreicht diese Lösung?
Mego
@ Mego Ich versuche nur, den Compiler von veritygos.orgzu überprüfen ...
Martin Rosenau
@ Mego: Keine Ahnung; Verity selbst ist eine portable Sprache, aber für die Verity-Implementierung ist wahrscheinlich noch kein Toplevel für den angegebenen Chip implementiert, und ich habe derzeit ohnehin keinen FPGA-Synthesizer zur Hand. Mein Simulator sagt, dass es 6328084 gesteuerte Signale gibt; Das sollte eine annähernd lineare Beziehung zur Anzahl der benötigten LE-Gatter haben, aber ich weiß nicht, was der konstante Faktor ist. (Im Allgemeinen würde ein Kriterium in Bezug auf etwas, das objektiv auf einem Simulator überprüft werden könnte, die Dinge hier einfacher machen.)
1
Der Synthese geht der Speicher aus - was nicht unbedingt bedeutet, dass es nicht funktionieren würde. Die vom Verity-Compiler generierte VHDL-Zwischendatei hat jedoch eine Größe von> 1 MB, während Ihre Verilog-Lösung nur 2 KB groß ist. Daher bezweifle ich, dass die Verity-Lösung weniger Logikzellen benötigt als die Verity-Lösung.
Martin Rosenau