Multiquay generator
On Habré, the month of Quinys, so I want to share my development, which I did four years ago.
A good multiquine is a piece of engineering, but ...
When you look at the next batch of “interference on the telegraph line,” an ordinary programmer has only the amazement: “how is this even possible”, and “who was that gloomy Teutonic genius.”
I want to break the covers and show how easy it is to write a multiquine of any degree of complexity in any set of programming languages, including whitespace and brainfack.
Since we are dealing with the texts of programs and the results of their execution, it would be natural to look at this business as functions on strings.
What features do we have?
First, it is an interpreter : it takes the program text, compiles it, runs it, and returns the text from the standard output.
Let's call this function simply: RUN .
Since we will not be limited to one language, then, in fact, we have a whole family: RUNpython, RUNc, RUNbrainfuck ...
It is clear that these functions are implemented in different ways, but how exactly - it should not worry us. After all, we do not write our own interpreter of the language, and even more so, in the same language.
In general, the main implementation will now be in our head, because we will solve the string equations.
')
Secondly, an important family of functions are decorators and writers . The decorator takes an arbitrary string and replaces special characters in it, and then the writer frames the string with quotes.
L x = qopen + D x + qclose
An important property of decorators is the additivity of the addition (concatenation) of rows: E (x + y) = Ex + Ey.
By the way, we will immediately agree: for compact recording, the functions will be large letters, the lines are small, Fx - applying the function F to x, FGx - applying F to Gx, or, equivalently, applying the composition FG to x.
If you look at the smallest quine on C,
then we will see a characteristic pattern. Here, two program fragments are repeated two times - once as the text of the top level, another time as the string literal.
So we write:
Exactly in the same way, we can make quine on python:
Or, a little more clearly and verbally:
Substrings a and e are informative, large texts that cannot be programmatically generated; substrings b, c, d - glue, usually consisting of quotation marks, carriage transfers, etc.
Speaking of clarity. It is convenient to consider the program text not as a monolithic string, but as a list of strings. In another article, I will definitely return to this, and show a couple of ways how to work with lists.
In the meantime, back to Quine.
The RUN function is defined for the quine:
That is, a quine is a fixed point of the RUN function.
Let's summarize a little quine. What if we learn to output arbitrary strings in arbitrary ways?
On the same python:
Quine is a solution to the permutation equation:
From where F = E, i.e. the program method of decoration coincides with the decoration according to the rules of the language; fragments of the text - it is clear that with what is the same.
Another digression: even within one language, decorators can be very, very different. We can represent strings as an array of numbers, for example.
Then the output of the “string” 104, 97, 98, 114 is the print '' .join (map (chr), xs), and the output in the decorated form is the print ','. Join (map (str), xs).
Note: RUN and Q functions are defined above strings (Q is generally a higher order function defined above strings and a function), but their implementation lies outside the target programming language in which we write quine. Whereas function E must be implemented as text in the target language!
And now let's look at another, very simple program. This program prints the specified text.
where S is some way of decorated text storage.
Since we can write a printer for completely arbitrary text, we will make a function:
Of course, the invariant:
That is, the printer is a function inverse to the interpreter!
In C:
On python:
That is, the function S here coincides with the good old E. (On the python - even simpler, you don’t have to escape the line feed).
And here - does not match:
The printer P favorably differs from the Q Qine in that its elements — p and r — do not depend on the parameters of the function.
It's easy to make a meta- printer out of a printer: a program that prints a program that prints text.
No one bothers us to make a multilingual printer:
And in general, you can use as many languages as you like ( multi-printer ):
All we need is to learn how to make the composition of the functions of the decorators. (About this - below).
And one more printer, for completeness: this is a null printer P0 (text) = text
Well, now let's cross the printer (or multi-printer) and quine.
This is where a solution to the equation is needed
Let's call these programs ping and pong:
And let ping is a P (pong) printer, and pong is something more intricate. If this were P (ping), then an infinitely expanding string would result, and we want a final solution.
So let pong = Q (F, f, g, h, i, j).
Substitute:
Why so,
The fact is that f and j are specifically designed for recursion: we can easily mention in them fragments of the pong source code (substrings a, b, d, e), while recursion in g, h, i is undesirable.
So we got
and somewhere in the depths of a or e, the function F = SE and the string ESc are hidden.
Note: if e contains ESc, recursion does not occur, because c does not depend on e.
Let us now get rid of these "in the depths of hiding." Take another function.
Let be
So we got:
If you define pong a little differently,
that is, if we get the hang of having a list of string constants, then we'll get rid of the double decoration:
Thus, if we have blanks for
The last thing left for us is to make the composition SE.
Formally, the task sounds like this.
Given: pong programming language; decorators E and S, and E is native to this language, and S is any.
Find: the text of the subroutine in pong language that implements the decorator SE.
And at the same time, implement decorators E and SE in the language of the development environment. After all, we want to automate the generation of multikvaynov?
To do this, let's look at how the decorators are arranged.
The decorator is distributive in addition: F (a + b) = Fa + Fb.
If we break a string into elementary parts - single-character strings, we get
Decorators are associative:
Therefore, we can present the decorator as a coding table of each character, and recalculate the composition into a table with the same number of keys, but with longer values.
Thus, the work plan is the following:
Given:
We act:
Everything!
And since all these steps are too laborious to do manually, then let's write a quine generator.
Here, for a seed, the code on python, which (at the moment) makes multiquains from python and si.
To supplement it with any other languages is a matter of ten minutes.
The source code and its fruits can be found on the bucket: bitbucket.org/nickolaym/quines
Of course, the machine-generated multiquine is not very elegant. Its size is 5438 bytes, most of which is occupied by the codepage.
How to make it more compact (while preserving the universality of the approach and the possibility for machine generation) - I propose to solve this problem on your own.
If you like, I'll write more on this topic:
Also see my stream of consciousness on the RSDN, 4 years ago. http://rsdn.ru/forum/etude/3604693 .
A good multiquine is a piece of engineering, but ...
When you look at the next batch of “interference on the telegraph line,” an ordinary programmer has only the amazement: “how is this even possible”, and “who was that gloomy Teutonic genius.”
I want to break the covers and show how easy it is to write a multiquine of any degree of complexity in any set of programming languages, including whitespace and brainfack.
Since we are dealing with the texts of programs and the results of their execution, it would be natural to look at this business as functions on strings.
Functions
What features do we have?
First, it is an interpreter : it takes the program text, compiles it, runs it, and returns the text from the standard output.
Let's call this function simply: RUN .
Since we will not be limited to one language, then, in fact, we have a whole family: RUNpython, RUNc, RUNbrainfuck ...
It is clear that these functions are implemented in different ways, but how exactly - it should not worry us. After all, we do not write our own interpreter of the language, and even more so, in the same language.
In general, the main implementation will now be in our head, because we will solve the string equations.
')
Secondly, an important family of functions are decorators and writers . The decorator takes an arbitrary string and replaces special characters in it, and then the writer frames the string with quotes.
L x = qopen + D x + qclose
An important property of decorators is the additivity of the addition (concatenation) of rows: E (x + y) = Ex + Ey.
By the way, we will immediately agree: for compact recording, the functions will be large letters, the lines are small, Fx - applying the function F to x, FGx - applying F to Gx, or, equivalently, applying the composition FG to x.
Quineas
If you look at the smallest quine on C,
char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);} then we will see a characteristic pattern. Here, two program fragments are repeated two times - once as the text of the top level, another time as the string literal.
So we write:
quine = a + b + Ea + c + Ee + d + eExactly in the same way, we can make quine on python:
s1,s2 = 's1,s2 = ', "\nprint s1+repr(s1)+', '+repr(s2)+s2" print s1+repr(s1)+', '+repr(s2)+s2 Or, a little more clearly and verbally:
# this is quine s1 = '# this is quine' s2 = 'print s1\nprint "s1="+repr(s1)\nprint "s2="+repr(s2)\nprint s2' print s1 print "s1="+repr(s1) print "s2="+repr(s2) print s2 Substrings a and e are informative, large texts that cannot be programmatically generated; substrings b, c, d - glue, usually consisting of quotation marks, carriage transfers, etc.
Speaking of clarity. It is convenient to consider the program text not as a monolithic string, but as a list of strings. In another article, I will definitely return to this, and show a couple of ways how to work with lists.
In the meantime, back to Quine.
The RUN function is defined for the quine:
RUN quine = quine .That is, a quine is a fixed point of the RUN function.
Let's summarize a little quine. What if we learn to output arbitrary strings in arbitrary ways?
Q(F,f,g,h,i,j) = a + b + Ef + c + Ej + d + e -- a,b,c,d,e - () F g,h,i. RUN Q(F,f,g,h,i,j) = f + g + Ff + h + Fj + i + j On the same python:
# this is Q def F(s) : ''' F ''' s1 = 'Ef' s2 = 'Ej' print s1 + 'Eg' + F(s1) + 'Eh' + F(s2) + 'Ei' + s2 # Ef, Eg, Eh, Ei, Ej — - Quine is a solution to the permutation equation:
RUN Q(F,f,g,h,i,j) = Q(F,f,g,h,i,j) RUN Q(F,f,g,h,i,j) = f + b + Ff + c + Fj + d + e Q(F,f,g,h,i,j) = a + b + Ff + c + Ej + d + e From where F = E, i.e. the program method of decoration coincides with the decoration according to the rules of the language; fragments of the text - it is clear that with what is the same.
Another digression: even within one language, decorators can be very, very different. We can represent strings as an array of numbers, for example.
Then the output of the “string” 104, 97, 98, 114 is the print '' .join (map (chr), xs), and the output in the decorated form is the print ','. Join (map (str), xs).
Note: RUN and Q functions are defined above strings (Q is generally a higher order function defined above strings and a function), but their implementation lies outside the target programming language in which we write quine. Whereas function E must be implemented as text in the target language!
Printers
And now let's look at another, very simple program. This program prints the specified text.
printer = p + Sq + r RUN printer = q where S is some way of decorated text storage.
Since we can write a printer for completely arbitrary text, we will make a function:
P(q) = p + Sq + r Of course, the invariant:
RUN P(q) = qThat is, the printer is a function inverse to the interpreter!
In C:
#include <stdio.h> int main() { printf("%s", "hello\nhabr"); return 0; } On python:
print """ hello RSDN """ That is, the function S here coincides with the good old E. (On the python - even simpler, you don’t have to escape the line feed).
And here - does not match:
#include <stdio.h> int main() { putchar(114);putchar(115);putchar(100);putchar(110); return 0; } The printer P favorably differs from the Q Qine in that its elements — p and r — do not depend on the parameters of the function.
It's easy to make a meta- printer out of a printer: a program that prints a program that prints text.
Pmeta (q) = PPq = P(p + Sq + r) = p + S(p + Sq + r) + r = p + Sp + SSq + Sr + r pmeta = p + Sp Smeta = SS rmeta = Sr + r RUN (RUN( Pmeta(q) )) = q No one bothers us to make a multilingual printer:
Pbilingua(q) = P'P"q = P'(p" + S"q + r") = p' + S'p" + S'S"q + S'r" + r' RUN"(RUN'(Pbilingua(q))) = RUN"(RUN'(P'P"(q))) = RUN"(P"(q)) = q And in general, you can use as many languages as you like ( multi-printer ):
Pmulti(q) = pmulti + Smultiq + rmulti pmulti = p1 + S1p2 + S1S2p3 + S1S2S3p4 Smulti = S1S2S3S4 rmulti = S1S2S3r4 + S1S2r3 + S1r2 + r1 All we need is to learn how to make the composition of the functions of the decorators. (About this - below).
And one more printer, for completeness: this is a null printer P0 (text) = text
p0 = "" r0 = "" S0 = id Ping pong
Well, now let's cross the printer (or multi-printer) and quine.
This is where a solution to the equation is needed
Let's call these programs ping and pong:
RUN ping = pong RUN pong = ping And let ping is a P (pong) printer, and pong is something more intricate. If this were P (ping), then an infinitely expanding string would result, and we want a final solution.
So let pong = Q (F, f, g, h, i, j).
Substitute:
ping = P pong = p + S pong + r = p + S(a + b + Ef + c + Ej + d + e) + r = p + Sa + Sb + SEf + Sc + SEj + Sd + Se + r = (p + Sa + Sb) + SEf + Sc + SEj + (Sd + Se + r) ping = RUN pong = f + g + Ff + h + Fj + i + j Why so,
f = p+Sa+Sb , and not g=Sa+Sb , for example?The fact is that f and j are specifically designed for recursion: we can easily mention in them fragments of the pong source code (substrings a, b, d, e), while recursion in g, h, i is undesirable.
So we got
pong = a+b + E(p+Sa+Sb) + c + E(Sd+Se+r) + d+eand somewhere in the depths of a or e, the function F = SE and the string ESc are hidden.
Note: if e contains ESc, recursion does not occur, because c does not depend on e.
Let us now get rid of these "in the depths of hiding." Take another function.
Let be
pong = R(F,x,y,z) = a + Ex + b + Ez + c + Ey + d RUN R(F,x,y,z) = x + Fx + y + Fz + z P pong = p+Sa + SEx + Sb + SEz + Sc+SEy+Sd+r RUN pong = x + Fx + y + Fz + z So we got:
F = SE x = p+Sa y = Sb z = Sc+SEy+Sd+r = Sc + SESb + Sd + r If you define pong a little differently,
pong = R(F,x,y,z) = a + Ex + b + Ey + b + Ez + c RUN R(F,x,y,z) = x + Fx + y + Fy + y + Fz + z that is, if we get the hang of having a list of string constants, then we'll get rid of the double decoration:
P pong = p+Sa + SEx + Sb + SEy + Sb + SEz + Sc+r RUN pong = x + Fx + y + Fy + y + Fz + z Thus, if we have blanks for
P = {S, p,r} and for R = {E,a,b,c} , then we will immediately turn them into ping-pong. And do not forget that P can be a multi-printer. Then the ping-pong will oscillate with a period of n + 1, where n is the multiplicity of the multiprinter. And if P is a null printer, then ping-pong oscillates with a period of 1 and (who would have thought?) Becomes quine.The last thing left for us is to make the composition SE.
Formally, the task sounds like this.
Given: pong programming language; decorators E and S, and E is native to this language, and S is any.
Find: the text of the subroutine in pong language that implements the decorator SE.
And at the same time, implement decorators E and SE in the language of the development environment. After all, we want to automate the generation of multikvaynov?
To do this, let's look at how the decorators are arranged.
The decorator is distributive in addition: F (a + b) = Fa + Fb.
If we break a string into elementary parts - single-character strings, we get
F(abcd…) = Fa + Fb + Fc + Fd + …Decorators are associative:
FG(abcd…) = FGa + FGb + FGc + FGd + …Therefore, we can present the decorator as a coding table of each character, and recalculate the composition into a table with the same number of keys, but with longer values.
Thus, the work plan is the following:
Given:
- Printers
{Sk,pk,rk}in which languages are unknown (all we need are only table implementations of Sk functions); - pong pattern
{E,a(F),b,c(F)}, where a or d reserve space for an arbitrary codebook F (therefore, a and c are not strings or functions above strings, but functions of higher order).
We act:
- We find the multiprinter
{S,p,r}, calculatingS1S2...according to the tables. - Find the table
F = SE. - If desired, we find the minimum alphabet - the set of symbols that make up p, r, Sa, Sb, Sc, Sd. This is in order not to pile up the coding table of the entire ASCII or, God forbid, unicode.
- Spread the table in a or c.
- We find
x=(p+Sa), y=(Sb), z=(Sc+r). - Form a pong:
a+Ex+b+Ey+b+Ey+c.
Everything!
And since all these steps are too laborious to do manually, then let's write a quine generator.
Here, for a seed, the code on python, which (at the moment) makes multiquains from python and si.
To supplement it with any other languages is a matter of ten minutes.
#-*- coding: utf-8 -*- # - , def I(c) : ''' id-, ''' return c def C(c) : ''' ''' if c=='"' or c=='\\' or ord(c)<32 or ord(c)>126 : return '\\%03o' % ord(c) # , , # , # : \x24bad - chr(0x24BAD), $bad else : return c def decor(F,s) : ''' ''' return ''.join(map(F,s)) # def compose(F,G) : ''' ''' return lambda c : decor(F,G(c)) # - (S,p,r) def make_printer(S, tpl, tag = '<-T->') : ''' ( <-T-> , ) ''' p,r = tpl.split(tag) return S,p,r nul_printer = (I,'','') def show_printer(prn, t) : ''' t ''' S,p,r = prn return p + decor(S,t) + r def meta_printer(prn1, prn2) : ''' ''' S1,p1,r1 = prn1 S2,p2,r2 = prn2 S = compose(S1,S2) p = p1 + decor(S1,p2) r = decor(S1,r2) + r1 return S,p,r # - , - (E, am, b, cm) # am cm - decorator -> string def make_quiner(E, M, tpl, tagX = '<-X->', tagF = '<-F->') : ''' <-X-> x,y,z, <-F-> , F E - , M ''' a,b,b_,c = tpl.split(tagX) assert b==b_ am = lambda F : a.replace(tagF, M(F)) if tagF in a else a cm = lambda F : c.replace(tagF, M(F)) if tagF in c else c return E,am,b,cm def show_quiner(qnr, F,x,y,z) : ''' a,Ex,b,Ey,b,Ez,c -- x,Fx,y,Fy,y,Fz,z -- , (RUN) ''' E,am,b,cm = qnr a,c = am(F), cm(F) ex,ey,ez = decor(E,x), decor(E,y), decor(E,z) return a + ex + b + ey + b + ez + c def show_quiner_printer(qnr,prn) : ''' p+Sa,SEx,Sb,SEy,Sb,SEz,Sc+r -- x , Fx, y , Fy, y , Fz, z -- ''' E,am,b,cm = qnr S,p,r = prn F = compose(S,E) a,c = am(F), cm(F) x = p + decor(S,a) y = decor(S,b) z = decor(S,c) + r ex,ey,ez = decor(E,x), decor(E,y), decor(E,z) return a + ex + b + ey + b + ez + c ############################################################# # : c_quine_tpl = '''/* C quine */ #include <stdio.h> const char* f[128] = {<-F->}; const char* xyz[3] = {"<-X->", "<-X->", "<-X->"}; void ps(const char* s) { while(*s) putchar(*s++); } void pm(const char* s) { while(*s) ps(f[*s++]); } int main() { ps(xyz[0]); /* x */ pm(xyz[0]); /* Fx */ ps(xyz[1]); /* y */ pm(xyz[1]); /* Fy */ ps(xyz[1]); /* y */ pm(xyz[2]); /* Fz */ ps(xyz[2]); /* z */ return 0; } ''' def c_quine_M(F) : ''' - ''' codes = [ '"%s"' % decor(C,decor(F,chr(i))) for i in xrange(128) ] return ', '.join(codes) c_quiner = make_quiner(C, c_quine_M, c_quine_tpl) # , py_quine_tpl = '''#!/usr/bin/python import sys m = [ <-F-> ] xyz = [ "<-X->", "<-X->", "<-X->" ] def ps(s) : sys.stdout.write(s) def pm(s) : for c in s : ps(m[ord(c)]) ps(xyz[0]) pm(xyz[0]) ps(xyz[1]) pm(xyz[1]) ps(xyz[1]) pm(xyz[2]) ps(xyz[2]) ''' py_quiner = make_quiner(C, c_quine_M, py_quine_tpl) # ################### # : c_printer_tpl = '''#include <stdio.h> int main() { printf("%s", "<-T->"); return 0; } ''' c_printer = make_printer(C, c_printer_tpl) py_printer_tpl = '''import sys sys.stdout.write("<-T->") ''' py_printer = make_printer(C, py_printer_tpl) #################### # ! c_c_printer = meta_printer(c_printer, c_printer) py_py_printer = meta_printer(py_printer, py_printer) # 1 c_quine = show_quiner_printer(c_quiner, nul_printer) py_quine = show_quiner_printer(py_quiner, nul_printer) # 2 c_c_quine = show_quiner_printer(c_quiner, c_printer) py_py_quine = show_quiner_printer(py_quiner, py_printer) # 2 - c_py_quine = show_quiner_printer(c_quiner, py_printer) py_c_quine = show_quiner_printer(py_quiner, c_printer) # 3 - - c_c_c_quine = show_quiner_printer(c_quiner, c_c_printer) py_py_py_quine = show_quiner_printer(py_quiner, py_py_printer) c_py_py_quine = show_quiner_printer(c_quiner, py_py_printer) py_c_c_quine = show_quiner_printer(py_quiner, c_c_printer) sys.stdout.write(py_py_py_quine) # , , - ... The source code and its fruits can be found on the bucket: bitbucket.org/nickolaym/quines
Of course, the machine-generated multiquine is not very elegant. Its size is 5438 bytes, most of which is occupied by the codepage.
How to make it more compact (while preserving the universality of the approach and the possibility for machine generation) - I propose to solve this problem on your own.
If you like, I'll write more on this topic:
- programs as list functions
- features of stupid languages like brainfack
Also see my stream of consciousness on the RSDN, 4 years ago. http://rsdn.ru/forum/etude/3604693 .
Source: https://habr.com/ru/post/188852/
All Articles