Wie viele Grundelemente werden benötigt, um ein Fort-System zu implementieren?

1992 fand ein weiterer Wettbewerb für verschleierte Programmierung in der Sprache C statt . Eines der vorgestellten Projekte war ein kleines Fortsystem . Mir ist aufgefallen, dass die virtuelle Maschine in nur 794 Byte C-Code implementiert wurde. Der Rest des Fortsystems wurde von der Quelle auf das Fort geladen. Nach dem Studium des Projekts gab die anfängliche Aufregung der Enttäuschung Platz, da der Autor einen nicht ganz "ehrlichen" Trick verwendete: Er verwendete die Funktion scanf (), um die befestigte Quelle zu analysieren. Von diesem Moment an wurde ich von der Frage gequält: Wie viele Primitive werden benötigt, um ein Fort-System ohne solche Tricks zu implementieren?



Nach einer Weile wurde ich in das von Lennart Benschop geschriebene sod32- Fort-System eingeführt . Dieses Fort-System verfügt über eine in C geschriebene virtuelle Maschine, und das in die virtuelle Maschine geladene Binärbild hängt nicht von der Bytereihenfolge im Worthostsystem ab. sod32 hat 32 Grundelemente, hier sind sie:

NOOP	( --- )	Do nothing
SWAP	( x1 x2 --- x2 x1 )	Swap the two top items on the stack.
ROT	( x1 x2 x3 --- x2 x3 x1 )	Rotate the three top items on the stack.
0=	( x --- f)	f is true if and only if x is 0.
NEGATE	( n1 --- -n1)	Negate top number on the stack.
UM*	( u1 u2 --- ud )	Multiply two unsigned numbers, giving double result.
C@	( c-addr --- c)	Fetch character c at c-addr.
@	( a-addr --- x)	Fetch cell x at a-addr.
+	( w1 w2 --- w3)	Add the top two numbers on the stack.
AND	( x1 x2 --- x3)	Bitwise and of the top two cells on the stack.
OR	( x1 x2 --- x3)	Bitwise or of the top two cells on the stack.
XOR	( x1 x2 --- x3)	Bitwise exclusive or of the top two cells on the stack.
U<	( u1 u2 ---- f)	f is true if and only if unsigned number u1 is less than u2.
<	( n1 n2 --- f)	f is true if and only if signed number n1 is less than n2.
LSHIFT	( x1 u --- x2)	Shift x1 left by u bits, zeros are added to the right.
RSHIFT	( x1 u --- x2)	Shift x1 right by u bits, zeros are added to the left.
UM/MOD	( ud u1 --- urem uquot)	Divide the unsigned double number ud by u1, giving unsigned quotient and remainder.
+CY	( n1 n2 cy1 --- n3 cy2)	Add n1 and n2 and the carry flag cy1 (must be 0 or 1) giving sum n3 and carry flag cy2. (n3 cy2 can be seen as a double number)
SCAN1	( x d --- u)	Scan x for the first 1 bit. u is the position of that bit (counted from the scan direction) and 32 if x=0. d is the scan direction, 0 is left-to-right, 1 is right-to-left.
SPECIAL	( x ---)	Any of a large number of special instructions, indicated by x.
DROP	( x ---)	Discard the top item on the stack.
>R	( x ---)	Push x on the return stack.
C!A	( c c-addr --- c-addr)	Store character c at c-addr, keep address.
!A	( x a-addr --- a-addr)	Store cell x at a-addr, keep address.
DUP	( x --- x x )	Duplicate the top cell on the stack.
OVER	( x1 x2 --- x1 x2 x1)	Copy the second cell of the stack.
R@	( --- x)	x is a copy of the top of the return stack.
R>	( --- x)	Pop the top of the return stack and place it on the stack.
0	( --- 0)	The constant number 0.
1	( --- 1)	The constant number 1.
4	( --- 4)	The constant number 4.
LIT	( --- lit)	Push literal on the stack (literal number is in-line).

Ich erkannte, dass ich die Möglichkeit hatte, die Antwort auf meine Frage zu finden, und begann, Primitive in Definitionen auf hoher Ebene umzuwandeln. Ich möchte sofort darauf hinweisen, dass all diese Aktivitäten eine rein akademische Bedeutung haben. Es ist unwahrscheinlich, dass die aufgrund des Leistungsverlusts erzielten Ergebnisse in der Praxis angewendet werden können. Während ich experimentierte, verfolgte ich die Größe der Fort-System-Binärdatei und die Laufzeit der John Hayes-Testsuite. Ich habe mit dem Befehl ein neues Binärbild erstellt

echo 'S" extend-cross.4" INCLUDED '|./sod32 kernel.img
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

und führte die Tests wie folgt aus:

time ./sod32 kernel.img <<< $(echo -e 'S" tester.fr" INCLUDED\n12345\nBYE')
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

In der folgenden Tabelle können Sie sehen, wie sich jede Änderung auf Größe und Leistung auswirkt. Links aus der Spalte "Ändern" führen zum entsprechenden Commit im Github.



Infolgedessen stieg die Größe des Binärbildes des Fort-Systems von 10164 auf 15912 (+ 57%), die Leistung sank um das 708-fache (fast 3 Größenordnungen). Vielleicht könnte die Leistung durch Profilierung des Codes und Optimierung von Engpässen verbessert werden, aber ich bin sicher, dass das Ergebnis im Vergleich zum ursprünglichen sod32 immer noch sehr langsam sein wird.



Aus 32 Grundelementen plus zusätzlicher Logik im internen Interpreter ergab sich 7: nop, nand,!, @, Um +, special, lit. Der interne Interpreter behält die Logik zum Ausführen von Grundelementen und Definitionen auf hoher Ebene (Aufruf) sowie die Logik zum Vervollständigen der Definitionen auf hoher Ebene (Weiter) bei. Ich fand die Antwort auf meine Frage: Ein Fort-System kann auf der Basis von 9 Grundelementen aufgebaut werden (oder 8, wenn nop kein Grundelement sein muss). Ich bin verwirrt über die Tatsache, dass es bis zu 3 Grundelemente für den Speicherzugriff gibt: @ ,! und beleuchtet, aber ich habe nicht herausgefunden, wie ich es vermeiden kann. Ich hätte etwas übersehen können. Wenn Sie also wissen, wie Sie eine große Anzahl von Grundelementen loswerden können, schreiben Sie bitte in die Kommentare.