Upload failed. Maybe wrong permissions?

User Tools

Site Tools

The Escher Quine


Well, folks, this is going to be a bit complicated.
  The title is from the names of two gentlemen, of whom the latter one is used as a common noun, let’s start with him. Willard Van Orman Quine (1908–2000), one of the most influential philosophers of the twentieth century, mathematic logician, language philosopher, creator of several important thoughts, like the Quine paradox. This paradox is happening to me when learning a language.

The Quine Paradox

ablakzsiraf.jpgFor example I’m seeing a picture with several things. (This is from children’s lexicon Ablak–Zsiráf, 11th edition, 1971.) This was made for Hungarian native children who can read, the text is designed for their ages and knowledge levels, but let’s imagine I’m viewing it for the purpose of language learning. (I’m really using books written for young native Latvian schoolchildren.) At the middle, for the man dressed in white, there’s PÉK written, and he puts something into something with a peel. Or takes it out. I speak no Hungarian, I don’t know this word, and I can’t recognize what happens on the picture. Possibly I am a child and I never saw a baker in work. Will I make it out that they are maize he is placing in the krāsns and this man is a maiznieks? And this is a simple case since in reality, when a toddler learning their native tongue is hearing the name of something the situation is most frequently ambivalent: mom points at an object, but there are a lot of objects to that direction, and if the child identifies the correct one, maybe mom takes it in her hand: is that word the name of that exact object, or should s/he abstract to a category of objects, and if yes, which one, or to an attribute of the object, or some action regarding to the object? I saw a video about someone who knows the names of one thousand objects, each name is for one individual object, but she cannot abstract from either one to a group or category of objects, any attribute of objects, she is unable for any abstraction. However she is an adult – but a dog. We expect a toddler hearing the word labda to extend the association in a short while from the certain individual object to an abstraction of all objects that are spherical toys, can roll, fly and bounce when thrown, and if s/he is a Hungarian child we expect them to distinguish it from the word and category of object golyó (which also belongs to the vocabulary of their age), what’s not a simple task for an adult native English speaker learning Hungarian, who considers both ball.

The Quines

Professor Quine was working such things, and this gave the motivation for Douglas Hofstadter to use his name for a special form of recursion. His book Gödel, Escher, Bach: An Eternal Golden Braid, published 1979, gives the name quine to computer programs that display their own source codes. For example, the following ZX Spectrum program:
  10 PRINT "This is a text here"
  20 PRINT "(two lines)"
  will display this when run:
  This is a text here
  (two lines)
  So this isn’t a quine. To make it a quine, it should display the text shown in green above. But it will display that only if we type this:
  10 PRINT "10 PRINT ""This is a text here"""
  20 PRINT "20 PRINT ""(two lines)"""
  (we have to type double quotation marks in a quotation mark to display a quotation mark). But by changing the text to this red one, the expectation became the red text to be displayed, not the green one. It would be a quine only that case.
  I believe it’s obvious it isn’t easy to write a quine. However, there are single line quines, like this little program in Python:

print((lambda s:s%s)('print((lambda s:s%%s)(%r))'))

which, when run on a machine knowing Python, will display, of course

print((lambda s:s%s)('print((lambda s:s%%s)(%r))'))

So, to write a quine is an interesting brain exercise, but running it is total boredom, we know exactly what will happen. The same text will appear, seen previously.
  But programmers love to play, so several kinds of additional quines were made.

Quine Variants

Cheating quines. A quine has to create its own source code again, and not to peek in the memory or the disk and read the source. This is what cheating quines do. Of course, any home computer understanding BASIC language, when given a program which consists of


will display


– so this is a quine, but it’s cheating, it doesn’t create the text that goes 1 (space) L I S T, just it reads the program from the memory and lists it.
  Ouroboroses. Ancient Greeks, who had a word for all the things frequently happening in life, ouroboros meant a serpent biting its own tail. I don’t know when do snakes such a thing, but ouroboros programs do. We write a program in a given language (say, C) which produces a source code of a program written in another language (say, Java); and this latter program produces the source code of the original C++ program. But this is simple. [[https://github.com/mame/quine-relay

  10 LET l=10: LET p$=""
  20 FOR n=0 TO 1: RESTORE
  30 READ o,a$: IF n THEN LET p$=p$(o TO )
  40 IF a$="" THEN NEXT n: LET i$=" 150 DATA 1,""""": GO SUB 60: PRINT #1;" RUN ": PAUSE 9: RUN
  50 LET c$="K": LET i$=STR$ l+((" DATA "+STR$ o+",""") AND n): GO SUB 60: LET l=l+10:: GO TO 30
  60 LET l$="": FOR i=1 TO LEN i$: LET l$=l$+i$(i): GO SUB 70: NEXT i: FOR i=1 TO LEN a$: LET l$=l$+a$(i)+("""" AND a$(i)="""" AND n): LET c$="LK"(1+(a$(i)=":" OR a$(i)=" THEN ")): GO SUB 70: NEXT i: LET l$=l$+("""" AND n): GO SUB 70: LET p$=p$+" "( TO 4-LEN STR$ l)+l$+CHR$ 13: CLS : PRINT p$;: RETURN
  70 PRINT #1;AT 1,0;l$; FLASH 1;c$;: PAUSE 10+20*RND: RETURN
  80 DATA 31," LET l=10: LET p$="""""
  90 DATA 25," FOR n=0 TO 1: RESTORE "
 100 DATA 50," READ o,a$: IF n THEN LET p$=p$(o TO )"
 110 DATA 56," IF a$="""" THEN NEXT n: LET i$="" 150 DATA 1,"""""""""": GO SUB 60: PRINT #1;"" RUN "": PAUSE 9: RUN "
 120 DATA 180," LET c$=""K"": LET i$=STR$ l+(("" DATA ""+STR$ o+"","""""") AND n): GO SUB 60: LET l=l+10: GO TO 30"
 130 DATA 79," LET l$="""": FOR i=1 TO LEN i$: LET l$=l$+i$(i): GO SUB 70: NEXT i: FOR i=1 TO LEN a$: LET l$=l$+a$(i)+("""""""" AND a$(i)="""""""" AND n): LET c$=""LK""(1+(a$(i)="":"" OR a$(i)="" THEN "")): GO SUB 70: NEXT i: LET l$=l$+("""""""" AND n): GO SUB 70: LET p$=p$+"" ""( TO 4-LEN STR$ l)+l$+CHR$ 13: CLS : PRINT p$;: RETURN "
 140 DATA 98," PRINT #1;AT 1,0;l$; FLASH 1;c$;: PAUSE 10+20*RND: RETURN "
 150 DATA 1,""

  Let’s see a few details. There’s a part (line 70) that goes PRINT #1;AT 1,0;l$; FLASH 1;c$;: PAUSE 10+20*RND etc. This prints the line as built so far (l$) and the cursor (c$), making the latter flashing (FLASH 1), and all of this into the editor window (PRINT #1). In a real situation this wouldn’t work since actually the cursor can move back and forth in the line being edited, but we’re never editing here, so it suits for the needs. And statement PAUSE waits a short while before continuing, this is the pause between two virtual keypresses.
  It’s typical Spectrumish like the c$ receives a value of the cursor letter: LET c$="LK"(1+(a$(i)=":" OR a$(i)=" THEN ")), meaning “let it be a character of string LK, the first one plus one (so the second one) if a$ has a character at position i being a colon or a keyword THEN” (it’s also a single character on Spectrum). Probably, this part should be changed as LET c$="LKE"(1+(a$(i)=":" OR a$(i)=" THEN ")+(a$(i+1)=" RESTORE " OR a$(i+1)=" DATA " OR a$(i+1)=" READ " OR a$(i+1)="CHR$ " OR a$(i+1)="STR$ " OR a$(i+1)="LEN " OR a$(i+1)=" FLASH ")), and then also cursor E would appear but I don’t dare to claim this for sure without entering it in an emulator.
  The main program is the loop in lines 20 to 50 which reads its own code entered in DATA lines once again, and starts doing magic with it. First, it prints the number of the line and its DATA part by character (i$), then the essential part (a$), this is done by the routine in line 60, and the aforementioned statement PRINT does the printing in line 70, with the flashing cursor and the delay. After each line, we clear the screen and print the source code created so far (p$), like on a real Spectrum. Variable o takes care for that when it doesn’t fit on the screen only the last few lines would be printed. (Here I found a beauty fault: during typing lines 120, 130 and 140, the number of the visible line on the top shifts leftwards, and during typing line 150, an incomplete line is visible above, but these can be corrected by decreasing the appropriate values of o.)
  ===== Futurologic Aspects of the Escher Quine =====
  At this point, quines reached another step of perfection: they were reproducing themselves only passively so far, but Daniel’s quine actively reproduces itself. (No, but it sounds nice.) We can reach the next step only by writing a quine which also virtually creates the equipment writing the quine. It downloads and installs the software environment itself is running in. Maybe draws and animates a robot which types a script on a keyboard, which draws and animate the robot itself.
  But the real quine, the quine of quines is which creates the creator of itself, creating the quine. But this task was already done by Isaac Asimov.
  ===== How Was the Quine Born =====
  Of course, I sent the article to Daniel who very kindly told me the story of writing the quine, I’m letting him to continue. He is right, I really didn’t notice many “cheats.”
  First, this is a “magician’s trick”, I mean, what really happens is not what the (careless) viewer believes to see, but what they believe to see isn’t a wonder, theoretically, it could be realized. In my opinion that sentence isn’t really correct in the article that “Universe as a whole cannot be described by a model simpler than itself.” It isn’t surely true for the universe and surely not for the Spectrum. It would be possible to write an Escher quine in Spectrum BASIC that perfectly looks like as if someone would be typing its source code. My program “cheats” a lot, it’s not the missing cursor E is the only thing it’s “being caught” it’s not about really typing a program. For example there should be a symbol > (line cursor) after the number of the line typed last, which I’ve left out. Keywords written with a cursor K in quotation marks aren’t typed the way as by me, since the cursor doesn’t change in quotation marks to K just because we want to enter a keyword PRINT. Even not after a semicolon. The canonical way (described in the manual) to get a cursor K in quotation marks is entering a keyword THEN, then entering the statement wanted, going back and delete it. Another “catch” is when the program is typing the DATA lines the quotation marks are immediately appearing doubled, not by two presses. And there are several other “cheats”, but these are mostly of the kind the “believeable” process happening on the screen diverts the attention of the viewer from.
  Why did I draw the line at that point? Why didn’t I implement some more things from the above, being exactly aware about they’re lacking and I exactly know how should they be implemented? The reason is in the way the program was made.
  Obviously, it wasn’t created as shown while running: I didn’t sit before the machine and typed the program ready-made at once. The program was made for a challenge (there is a Spectrum BASIC group on Facebook where we’re amusing each other by such things), where the challenge was to write a program which imitates a program being typed and executed by someone. The initiator thought of course about “typing and executing” a simple little program, but I immediately thought how great would it be if it would be done by a quine (really it was a hit). The idea inspired me such much that I was working on it from midnight till three at the morning, until I was satisfied with the result. The process of writing of the program explains why did I stop where I did, and exactly, where did I cut it back exactly till that point (for example, printing > was included at a point, but I removed it).
  Obviously I began by writing a quine which prints itself by line. Its’s a simple loop with two iterations which reads something from DATA lines, and in the first go it prints it with line numbers, and in the second one surrounds it with quotation marks and adds DATA before it. I was ready with this after about 10 minutes. Then I went through the program and copied all of its lines into a DATA line. This took a few minutes more. Then I began to ornament it. For first, I changed the statement PRINT which prints out the lines to a GO SUB and put the PRINT in a subroutine. Then I replaced it with a loop with prints the line by letter (and in the second go, it doubles the quotation marks). And once the moment came when the program could no longer fit on a screen and the automatic listing halted with a question scroll? (this is solved in the ROM with a separate mode for the automatic listing, signed by a bit in a system variable, and then instead of the prompt scroll? it goes on and shifts the place the next automatic listing should be beginning at). So this meant the line where it happened the automatic listing should be done from another line instead of the beginning of the program. Since this happened only in the second go, the line READ a$ was changed to READ o,a$: IF n THEN LET p$=p$(o TO ). Now I was working for about an hour.
  Here the productivity of the work had strongly decreased. I was entering the numbers by hand, adding the length of the respective lines plus 5 and one (4 bytes for the line number + Enter + the first character of a string is number 1).
  They had to be recalculated after every modifications. And it’s very important that the program (without DATA lines) to fit on a screen, otherwise we need to work on both loop iterations with printing the program from a later position, and in both iterations, we should to use different offsets. So, either I had to write an own program to calculate offsets, or to bother with twice as many offsets manually. In both cases, the work would become a lot increased, so I rather took a breath and draw a line what is obviously necessary for credibility and what is what no one will notice. What’s important that the program must fit on a single screen, because if not it takes a lot of work.
  This took nearly two hours of three. I think the result was fairly good. I finished it at three o’clock at dawn, sent the result to the group and went to bed. Next day I went to work lacking the sleep. :)
  Obviously I don’t expect you to describe the whole work process, just that instead of the phrase “Universe as a whole cannot be described by a model simpler than itself.” point the real reason of the compromistic unperfectness: writing a more perfect program would take an unnecessarily larger amount of work, and the greatest virtue of a programmer is laziness. :)
  »»»»»» ++