The Escher Quine

(magyarul)

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.

For 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.

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.

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

1 LIST

will display

1 LIST

– 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. Yusuke Endoh wrote a program in Ruby language, which produces a program in Rust language, which produces one in Scala language, which produces one in Scheme language, and so on, in alphabetical order till Zsh, then comes A+, Ada, AFNIX and so on through the alphabet, reaching Ruby language, totalling one hundred and twenty-eight programming languages used to get the same Ruby language source code back it was begun with.
  Multiquines. A group of programs written in several different languages, of which every one is able to display the source code of any member of the group (including its own), and we can choose with a parameter which one we want.
  Radiation hardened quines. Quines which can display their source code even if we remove any (single) character, but by replacing that character.
  Obviously, we can invent more of these. Now I’ve just invented the mutating quine, inspired by the radiation hardened one: it displays its source code, but it may happen that one character will be missing, or there will be another one, or one of them will be replaced by another character, but it still is a quine and can display its own source code, but with a chance to changes like these, and so on, so if we run the original quine a hundred times we get a hundred quine children which differ from the original at a single point only, and if we run these a hundred times each we get ten thousand quine grandchildren which differ now at two points, and so on, and so on. I’ve got no idea if such a thing can be written at all. With my programmer’s knowledge I can’t get a hint.
  But all the program types mentioned so far match in one thing. When we run them, we’ll get a text. Their own source code or that of another program, anyhow, a text. You can open it in a text editor, you can read it, you can print it. I wrote this article on a program with an output which isn’t text but action. However, it is a quine, too. It’s the Escher quine.

You can see on the video Daniel A. Nagy typing a program on ZX Spectrum. They do it so on Sinclair machines, there’s an editor window on the bottom of the screen, one line tall, and if it’s filled it grows upwards; when ready (Enter pressed) it jumps to the upper screen part. Typing is very special on the colorful keyboard of Spectrum: the cursor isn’t a line nor a block but a flashing letter, either one of K E L C G, and it depends on the letter which symbol or word gives the key pressed. For example, key N in mode L gives lowercase letter n, in mode C uppercase N, in mode K the statement word NEXT, in mode E the function name INKEY$, and it knows also word OVER and the , comma. This single key. This is a unique speciality of Sinclair machines, it was a pioneering invention at the beginning of the eighties, and by the way, it’s adored by Spectrum fans. At least me. So this is why K and L are changing there all the time, and this is why BASIC words are appearing at once and not letter by letter, because they are single key presses. The keyboard contains all the vocabulary of Spectrum BASIC on purpose.
  
  Now, having explained what happens on the video I tell you it isn’t what happens on the video. It doesn’t show Daniel’s typing of the program but the running of the program. This is a quine since it outputs its own source code, but not as a text but it pretends typing it. Imitation is almost perfect. We can know it’s actually an imitation from that words like RESTORE, READ, DATA, FLASH, LEN, STR$ and CHR$ are appearing without the cursor changing to E, however on a real Spectrum (or even an emulator) these words cannot be reached without changing the cursor (by pressing Caps Shift and Symbol Shift at the same time) to E, and after that we have to move a finger on the key of the respective keyword, what takes time, and E should be visible for a bit of time if Daniel would be typing, himself. But who cares? Universe as a whole cannot be described by a model simpler than itself. Spectrum is a tiny universe, too.

The name Escher-quine was given it by myself. The second gentleman from the title, M. C. Escher created this famous drawing:
  
  Its title is Drawing Hands (Tekenen), published in 1948. Of course, Hofstadter featured this drawing in his book mentioned, Escher’s name is included in its title. But this way, Escher quine, I couldn’t find on the net, so there’s a chance that I’ve invented it.
  According to my definition, an Escher quine is a quine which doesn’t reproduce its source code (its own finished state) but the creation of its own source code. (© Láng Attila D., 2019.)
  The procedure isn’t completely unknown in the history of computing. There are inscriptions in many movies that appear as if a person would be typing them into a computer; for example, in the 1979 movie The Black Hole. In computing literature, once there was a category of magazines which was written and distributed as programs, and in a part of these, the pages weren’t simply displayed but the letters were typed one after another, as if a person would be typing them at that very moment. I wrote one, too. But combining this with a quine, writing a quine which imitates its own entering – this is a world record.

Since my reader’s browser isn’t a Spectrum, it took some effort to describe the Spectrum with a model simpler than itself and to create a listing that looks like on a real Spectrum. At least in the mine it does. It appears on grey background with black letters, with a real Spectrum font. I hope it looks like this at my reader, too. That way it’s the real one.

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.)

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.

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. :)

»»»»»»