The Classic C Quine (2003) | Hacker News Reader

The Classic C Quine (2003)

susam.net

30 pointssusam17 comments

Tangentially related to quines - some time ago I was wondering if a certain program can be modified so that it prints its diff with it's previous version. If possible, you can keep modifying the program this way many times. At the end, you can reconstruct the entire history of modifications by running the program and applying the diffs iteratively.

I pondered a bit on this and thought it's impossible, but still, I made this repo as a challenge:

https://github.com/ggerganov/diff-challenge

Amazingly, someone managed recently to propose a solution for the first step [0]. Not sure if a next step is possible though..

[0] https://github.com/ggerganov/diff-challenge/commit/e4d210c16...

The next step is basically a quine with a template of diff cruft around it. It has to output this, where N is the number of lines in the program:

  1,Nc1,3
  < HERE IT REPRODUCES
  < ITS OWN N-LINE IMAGE
  < ...
  ---
  > #!/bin/sh
  > head -n2 $0 | diff - /dev/null
  > exit 0

Since "quining" via $0 is evidently fair game, that simplifies things a lot. Here you go:

  #!/bin/sh
  sed -e 's/^X//' <<!
  X1,9c1,3
  $(sed -e s'/^/< /' $0)
  X---
  X> #!/bin/sh
  X> head -n2 \$0 | diff - /dev/null
  X> exit 0
  !

On first try, I didn't escape the dollar sigil on $0, so that got expanded to ./x3.sh, resulting in a minor difference. But since we are not doing any true quining, all I had to do was add the backslash without having to rack my brain on how to compensate for that character elsewhere; the "reproduce self accurately" requirement is trivially taken care of with $0.

With the above template, you can diff back to any body of text, so it can be easily continued.

Awesome! Thanks for showing me this approach.

Having $0 available does seem to help a lot to solve the challenge.

Replying to some old comment of mine to demonstrate hnreplies [0] functionality

[0] https://news.ycombinator.com/item?id=30014298

I think this is what you're trying to do:

Y = (X + information) + X diff Y (This is kind of golden ratio-ish, imo)

It seems to be self referential which doesn't make it impossible, just maybe impossible.

I think the trick here would be calculating the lower bound of a massive block of text that could be encoded somehow to produce a sort of hash collision.

The program would essentially just read from a big chunk of text, and reconstruct the actual source code.

You'd have a separate program to read the previous text, read your program, and find a collision in your encoding scheme that satisfied your changes and also diffed correctly.

What that encoding algorithm is, I don't know, and I'm not sure it can exist. But if it does, I think you'd have to have to have a pretty big chunk of data to collide to even write a hello world program.

This is a pretty interesting problem, but I bet it can be reduced to a simpler computability/information theory deal. I'll be thinking about this all day.

I suppose it would be posssible with a lisp.

The quine (through 128 languages in total): https://github.com/mame/quine-relay

If you don't like those hard-coded character constants, lack of newlines, and compiler warnings, here's a C quine on similar lines:

  #include<stdio.h>
  int main(){
    char q='"',n='\n',b='\\';
    char*f="#include<stdio.h>%cint main(){%c  char q='%c',n='%cn',b='%c%c';%c  char*f=%c%s%c;%c  printf(f,n,n,q,b,b,b,n,q,f,q,n,n,n);%c}%c";
    printf(f,n,n,q,b,b,b,n,q,f,q,n,n,n);
  }

My favorite quine is just "#!/usr/bin/cat". Not sure what programming language I would say that is written in though...

That is a polyglot which is written in two languages.

It is written and interpreted using the cat language, which is an interpreted language in which every possible byte stands for a self-printing action, and those actions are carried out in order for all bytes of the input.

It is also written in the hash-bang language, which is placed into a file to specify to the OS kernel what interpreter to use for the file.

So first this is interpreted as a hash-bang language statement, which then causes the cat interpreter to be applied, causing it to be a cat language statement.

The hash-bang interpretation is what induces the binding between the cat interpreter and the hash-bang statement, evoking the cat language interpretation.

You are writing in Text [1], where every program is a quine.

[1] https://esolangs.org/wiki/Text

Thus hash-bang is an delivery mechanism, which allows Text programmers to produce stand-alone executables. Usually, Text programmers need to include a slight bit of complexity to conceal the hash bang line, in order to produce just the intended text, like

  #!/bin/sed 1d
  Hello, World!

But if the complexity of sed 1d is replaced by the pure cat implementation of the Text language which omits nothing, then self-reproducing behavior is obtained in stand-alone delivery form.

I like it, although if one is going for pure code-golf, then an executable empty file is a quine too :)

  touch foo && chmod +x foo
  ./foo

Unless one considers the commands to create & invoke it (as above) to be a part of the "source code" of course...

Quines are an interesting subject. If you want an example in your language then its maybe to be found here http://www.nyx.net/~gthompso/quine.htm

More modern and up-to-date references: https://rosettacode.org/wiki/Quine

For esoteric programming languages this might be more complete: https://esolangs.org/wiki/List_of_quines

David Madore's treatment [1] is my go-to introduction to quines.

[1] http://www.madore.org/~david/computers/quine.html

Willard Van Orman Quine:

  yields falsehood when preceded by its quotation

Some people seem to like Quine's prose; I found it deliberately obscure and over-elaborate.

Reply on news.ycombinator.com