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.