4 ms·

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 po

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 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/e4d210c16c734a37f7765a497522345ffb2ba79d https://github.com/ggerganov/diff-challenge/commit/e4d210c16...

Pompidou 5y ago
I suppose it would be posssible with a lisp.
alar44 5y ago
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.
kazinator 5y ago
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.
- ggerganov 5y ago
  Awesome! Thanks for showing me this approach. Having $0 available does seem to help a lot to solve the challenge.
  - ggerganov 5y ago
    Replying to some old comment of mine to demonstrate hnreplies [0] functionality [0] https://news.ycombinator.com/item?id=30014298 https://news.ycombinator.com/item?id=30014298

Pompidou 5y ago

I suppose it would be posssible with a lisp.

alar44 5y ago

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.

kazinator 5y ago

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.

ggerganov 5y ago
Awesome! Thanks for showing me this approach. Having $0 available does seem to help a lot to solve the challenge.
- ggerganov 5y ago
  Replying to some old comment of mine to demonstrate hnreplies [0] functionality [0] https://news.ycombinator.com/item?id=30014298 https://news.ycombinator.com/item?id=30014298