Search

jeudi 2 mars 2017

Quine: introduction and mechanisms (1)

A quine is a program that has the ability to print its own source code. A non-cheating quine (a true one actually) has this property without having to look at the source code file, of course.

It can be proved that every Turing-complete programming language has an infinity of quines, and I would suggest to read this excellent article prior to this post.

In order to create a quine, we need 2 distinct parts

  • some data that represents the code
  • some code that prints the data, then prints the code using the data
The problem is that BrainFuck needs code in order to generate data (well, any language does, but BrainFuck needs operations like at least + and > in order to store values in memory).

To solve this, let's use only + and > to generate the data. One instruction N from the code will be encoded in the data using as many + operations as needed to reach N's ASCII code.

To make it a bit more clear:
  • Our program generates data (using only > and +), data contents to be defined
  • Then, program generates symbols + and > and go through data
    • for each value N
      • print + N times
      • then print > as many times as needed to enter next data cell
    • then, go back to array start and for each value N
      • print N
In other words, let's our data be ABC: the code + 65 times then > then + 66 times, then > then + 67 times generates [A][B][C] in memory.
Once it's done, go back to A (value 65) and print + as many times as this value (so 65 times), then >, then do the same with B and C.
And finally, go back to A and print it, same with B and C.

Our output will look like
  • first, the data generation part (unchanged)
  • and then ABC
And here is the trick! If we want to build a quine, then we just have to define the data as a representation of the source code; using this formalism, instead of ABC.
Each instruction in our code will be converted: PLUS into 43 + then >, GT using 62 + then >, LT using 60 + then >, ...

To be continued...

1 commentaire:

  1. Slot Games at JTR - Hendon Mob Garage
    We have 속초 출장샵 a large variety of video 속초 출장마사지 slots available to play and you'll 경상남도 출장샵 love our selection 광주광역 출장샵 of high quality software that suits all 서산 출장안마 types of

    RépondreSupprimer