Search

lundi 13 mars 2017

Quine: double quine (6)

Context

Now that our quine is done, let's solve another quine-related problem.
There are programs named quine chains, or quine relays: a program in a language A generates some source code in a language B, that generates some source code in a language C, that generates ... until it generates the same program in language A. See this page for an incredible quine relay that chains about 100 different programming languages !!
Here, we'll use a slightly simpler chain, with 2 programs written using BF. The idea is to have 2 (different) source codes, each one generating the other.
Again, we can apply the fixed point theorem to prove its existence. For any Turing-complete language, and for any string chains X and Y, there is a program able to generate its own source code, preceded by string X and followed by string Y.
Therefore

  • we can have a program A that will be a simple "Print B", B being another program
  • then, program B will be "Print A", or in other words, Print "Print B"
This is just pseudo-code of course, but we can see here that, X being Print "Print  and Y being ", we can find a B such as B prints A and A prints B

Initial state

  • Memory: empty
  • Cursor: first cell
  • Input: empty

Process

  • Let's start to leave 4 empty cells, then store some data (to be generated afterwards)
  • Print > 4 times (for the 4 emptys cells mentionned above)
  • Print some code that generates the same data
    • Go on first data cell
    • Print + as many times as needed
    • Print >
  • Print some code that print some code that generates the same data ^^
    • Code is (see above): go on first cell, print + as many times as needed, print >
    • We just need to write those same instructions, instead of executing them
  • Print some code that print instructions based on data
    • In our simple quine, it was just going through the data and displayed them as characters
    • Here, we need to print some code that do the same
  • Once it's done, take all the code after data generation part, convert it (see what we did for quine), and put it inside our code
  • And that's all. There is obviously no need to write the second program : it'll be automatically generated by this one :)

Code - "first" program - try it

>>>>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+>+>+>+>+>+>+>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>+>+>+>+>+>+>+>+>++++++++++++++++++++>+>+>+>+>+>+>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++>++++>++++>++++>++++>++++++++++++++++++++>+>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>+>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>++++++++++++++++++++>+>++++++++++++++++++++>+>++++++++++++++++++++>+>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>++++++++++++++++++++>+>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++>+++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+>+>++++++++++++++++++++>+>+>+>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>+>++++++++++++++++++++>+>+>++++++++++++++++++++>+>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+>++++++++++++++++++>+++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++>++++>++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++>++++>++++>++++>++++>++++>++++>++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++>++++>++++>++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++>++++>++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++>++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++>++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++><[<]<<+++++++[->+++++++++>++++++<<]>-....>+>[[-<.<<+>>>]<[-<<+>>>+<]<.[->+<]>>>]<<<<[<]>[-.>]

Code - "second" program - try it

>>>>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+>+>+>+>+>+>+>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>+>+>+>+>+>+>+>+>++++++++++++++++++++>+>+>+>+>+>+>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++>++++>++++>++++>++++>++++++++++++++++++++>+>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>+>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>++++++++++++++++++++>+>++++++++++++++++++++>+>++++++++++++++++++++>+>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>++++++++++++++++++++>+>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++>+++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+>+>++++++++++++++++++++>+>+>+>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++++>+>+>++++++++++++++++++++>+>+>++++++++++++++++++++>+>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++>+++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>+>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+>++++++++++++++++++>+++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++>++++>++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++>++++>++++>++++>++++>++++>++++>++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++>++++>++++>++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++>++++>++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++>++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++>++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>++++>++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>++++>+++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++>++++++++++++++++++>++++++++++++++++++>++++++++++++++++++>++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++++++++++++++++++>++++><[<]<<+++++++[->+++++++++>++++++<<]>-....>+>[[-<.<<+>>>]<[->+<]<.[->+<]>>>]<[->>+>+>+<<<<]<[->+>+<<]>-->>>++>+++[->++>++>+<<<]>>>[-<<<+>>>]<+<-[<]>.>>>>>.[<]>.[>]<.[<]>..>>.......>>>.<<.<<.>.........<.>......<<..[>]<.<<<<<.>>.>....<<<.>.<.>>>>..<<.<<<.>>>>.<<<<..>>.<...[>]<.[<]>.>>>>>.<<.<<<..>>.<...>.<<.[>]<.[<]>.>>>>.>.<<.<<.>.<<.[>]<.<<<<<...[>]<.[<]>....>>>>>.[<]>.[>]<.<<<<<.>>>>.<<.>.<<<.>>>>>.  

Final state

  • Memory: our data and some extra chars
  • Cursor: somewhere after data (according to the code we executed)
  • Input: unchanged
  • Output : the other code 

Aucun commentaire:

Enregistrer un commentaire