Quines: self-replicating programs (2005) | Hacker News Reader

Quines: self-replicating programs (2005)

madore.org

71 pointslelf28 comments

Open articleView on HN

Particularly good past quiney things:

2013 https://news.ycombinator.com/item?id=6048761

2014 https://news.ycombinator.com/item?id=7276976

2016 https://news.ycombinator.com/item?id=12492812

2019 https://news.ycombinator.com/item?id=19752317 and https://news.ycombinator.com/item?id=20094866

among many others: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

looked through all those to see if Quine Relay was mentioned, it was one of the earlier submissions. But to add something totally new I didn’t see in any comments, that developer made another quine that animates a rotating globe in the terminal: https://github.com/knoxknox/qlobe

Maybe it's because I haven't yet had my morning coffee but I find his first example overly complicated. A much simpler and immediately obvious one [from this article](http://www.nyx.net/~gthompso/quine.htm):

     char*f="char*f=%c%s%c;main()
     {printf(f,34,f,34,10);}%c";
     main(){printf(f,34,f,34,10);}

I watched this video recently: https://www.youtube.com/watch?v=6avJHaC3C2U - and it's one of the best programming related ones I've seen in recent times. Really well presented as well - and he talks about various Quines - I won't spoil it for anyone.

You can do this way easier if the language has an "exec" function. Here's a python example:

  x="""def f():
    print("x=" + '"'*3 + x + '"'*3)
    print("exec(x)")
    print("f()")"""
  exec(x)
  f()

I mean, obviously. I would say it counts as cheating though. It’s on the same level as opening the source code file and printing it out.

No it's not on the same level, it's subtly different. The file could be altered during the brief instant between when you execute the file and when the program loads itself. Or the whole thing could be run from the REPL with no "file" at all.

Not cheating as in “it might not work,” cheating as in “it trivializes the exercise.” The point of making a quine is a programming challenge. If python had a function called “quine()”, I would still call it cheating even if it worked 100% of the time.

Sure, which is why I said "way easier". If you were assigning quine as a python homework exercise, and you wanted an "exec" solution ruled out, you would need to explicitly rule it out in the text of the exercise.

>If python had a function called "quine()"...

If we wanted to REALLY trivialize it, just use the blank program (which prints nothing, thus prints itself). :)

People consider this cheating but idk

  print(open(__file__).read())

What’s not to know?

> ...but idk [if it really is cheating]

Maybe that's what they meant

... if I agree with the consensus about what constitutes "cheating." For example the wikipedia page suggests that "eval" is okay but accessing the filesystem is not -- folks here seem to regard eval as cheating for some reason that escapes me. These decisions seem arbitrary to me

They are arbitrary.

They are a matter of taste.

Eval. Reading the source.

These are quines by some narrow technical definitions which skates along the surface, but misses all of the beauty.

Maybe the aren’t cheating. But they aren’t special. They might not be disqualified, but they score — at best — 2/10.

Beauty is in the eye of the beholder. I actually find eval-based quines MORE beautiful because they highlight the philosophically interesting aspects of quines, such as...

* ...the blurring of the distinction between output and code.

* ...the distinction between name and thing-being-named. (The different "x"'s in my example, within different levels of nested quotes.)

* ...leaky context (local variables defined inside the eval scope ending up outside the eval scope, and vice versa).

Harder quines tend to hide all that behind layers of tedious encoding.

If you're really interested in hard quines, you might be interested in trying to dig up some fully-detailed proofs of Godel's incompleteness theorems. It's the same story there: elegant and beautiful ideas, drowned under mountains of tedious encoding.

Very good points on eval. Can the read() example be similarly redeemed?

Good question, I had to think about it for awhile. I think it would take some elaborate mental gymnastics to try to redeem the read example. The read example is sort of like an appeal to a higher-power oracle. It isn't self-contained; it wouldn't work in the REPL.

As a compromise, one could imagine a quine which works by writing programs to disk and then reading those programs (as opposed to reading itself). This would be kind of silly, since the same data could be written to/read from RAM much easier.

Another way of cheating, with reader macros in Common Lisp:

    USER> #1=(LAMBDA () (WRITE '#1# :CIRCLE T) NIL)                                                                                                                                                
    #<FUNCTION (LAMBDA ()) {540F153B}>

The function, when evaluated, prints its code:

    USER> (funcall *)                                                                                                                                                                             
    #1=(LAMBDA () (WRITE '#1# :CIRCLE T) NIL)

If you read back the printed string, you have an identical function as the first one. The '#n=' binds a reader label n to the AST that follows, and '#n#' is replaced by the AST bound to n, which means your AST can be a circular data-structure. I added :circle t so that circular structure are printed readably, and the (write ...) is followed by NIL so that the structure is not printed to the REPL during interactive evaluation.

You could also write:

    #1=(lambda () (eval '#1#))

When you evaluate the expression you have a #1={function, which, when called, returns a #1#}.

What would be a practical use of this?

A computer worm

Not directly a quine per se, but suppose you want to write a computer program which writes computer programs. And you want all these programs (both the one writing them, and the ones written) to be 100% self-contained, no importing from a util file or anything like that. Then if a util function shall be used in the writing program as well as in the written programs, then it'll need to be "injected" into the written programs in a Quine-like way.

Here's an extreme example, a program which writes programs, each of which writes programs, each of which writes programs, ..., each program being fully self-contained: https://raw.githubusercontent.com/semitrivial/ions/master/sr...

(For the context behind that program, see: https://github.com/semitrivial/IONs)

The existence of quines is a nice proof that biology isn't magic. Consider an alternate history in which computer science develops before organic chemistry. Prior to the development of organic chemistry, some common beliefs about life were, for example, that living matter was fundamentally distinct from nonliving matter, and life could not arise from non-living components; and that obviously no mechanism could contain its own description, so the only way biological reproduction could work is if, say, sperm actually contained miniature complete organisms, which in turn contained even smaller complete organisms, in an infinite regress (see https://en.wikipedia.org/wiki/Preformationism).

If, however, you can construct a quine, those beliefs are no longer "obvious". If you can write a program that replicates itself, then you can build a machine that replicates itself--and living organisms might well be such machines.

I'm not sure the analogy quite works. The DNA of children is physically copied from parents, there's no quine-like encoding of DNA contents inside the DNA itself. In other words, life is more like a cheating quine that's allowed to say "read my source code from disk and print it" :-)

Sure, except in this case the "source code reader" is also built from the source in question. More analogous, perhaps, to a self-hosting compiler.

True, but the point is not to produce a direct analogy--merely an existence proof.

There might be no practical uses for this but it exemplifies programming as some sort of self-referential Ouroboros-type art. I think it's cool.

It makes it simple to fulfil copyleft obligations to distribute source. Also helps avoid losing source to old programs - a custom vending machine firmware I know embeds source.

It would be cool if someone made a cargo-quine rust crate that bundled and compressed everything for a --source argument, maybe with "cargo vendor" as an option. Probably not _that_ much extra program size.

This could be an evolution of software.

Reply on news.ycombinator.com