Any idea about constructing a higher order Quine program?

Question

Here is a special Haskell program which outputs a Python program that outputs a Ruby program that outputs the original Haskell program (from http://blog.sigfpe.com/2008/02/third-order-quine-in-three-languages.html)

To be more exactly, the output is of this Haskell program

q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']
main=q "q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']" "def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'" "def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end"

is a Python program,

$ runhaskell test.hs
def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'
q("def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'","def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end","q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']")

which outputs a Ruby program after running,

$ runhaskell test.hs | python
def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end
q("def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end","q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']","def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'")

and finally the Ruby program prints the original Haskell program.

$ runhaskell test.hs | python | ruby
q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']
main=q "q a b c=putStrLn $ b ++ [toEnum 10,'q','('] ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']" "def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'" "def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end"

Since a traditional quine program can be constructed by separating a program in two parts in which partA contains a description of partB and partB computes A from the description.

But how was such a three-order quine constructed?

Answer 1

First, wrap your head around this programming assignment. Believe me, it's actually not that difficult once you spend some time on it. The idea is that you can write a program that can take another program as input and spit out a third program as output that combines the two programs and also understands its own text. It's a sort of higher order quine. If you understand the structure of all three programming languages, you can take the ideas from this assignment and extend them further.

Answer 2

Kleene's recursion theorem in theory makes it possible to construct a quine in almost any language. (More information here.) Though I myself haven't so far managed to get it to work.

For a higher order quine, the function to consider is the composition of the languages' evaluation mechanisms. If you can get a basic quine out of KRT, maybe you could have a go at getting a higher order quine out of it.

Answer 3

In the first paragraph of that article I wrote a brief explanation. I recommend starting there.

I learnt some of these techniques from the book Vicious Circles by Barwise and Moss.

Answer 4

I'm not a programmer (!) but sounds like this to me:

... -> C -> A -> B -> C-> A-> B -> C -> ...

a (triangle) circle vicious without real beggining or ending.

Program A cointain a description of B which contains a description of C.

Program B cointain a description of C which contains a description of A.

Program C cointain a description of A which contains a description of B.

Probably going deeper you can make with many different languages getting more corners on the circle.