Can you Meta Quine?

Question

Similar to other quine puzzles (more specifically, this one), write a program that produces the source for itself.

Here's the new twist: The code produced should NOT be identical to the source. Rather, it should output a different program that will create the first.

The challenge linked to above achieved that by jumping between two languages. I'm thinking this one would be done in just one language, but the two (or more) versions of the source should be significantly different (see rules below). With this constraint, single character answers would be disallowed, thus requiring a little more thought be put into a final submission.

---

RULES

1. Your code must be produced in just one language. (Multiple submissions, one for each language is perfectly acceptable.)
2. Your different code versions must be syntactically distinct. In other words, if you were to draw out an abstract syntax tree for your code, there should be at least one node different.
   • Supplying an AST will not be necessary, but if you feel inclined to provide one for each of your programs, it would help in judging.
3. You may produce as many iterations as you wish, as long as they all remain syntactically distinct. (More will help your score, see below.)

---

SCORING

Your final score will be the mean length of all your programs, divided by the number of programs.

Example 1:

A (source for B) = 50 characters
B (source for A) = 75 characters
Final Score = 31.25

Example 2:

A (source for B) = 50 characters
B (source for C) = 75 characters
C (source for A) = 100 characters
Final Score = 25

Answer 1

Python, 0 (limit of (68+3 n )/(16ⁿ))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(0x%XL+1)%%0x10...0L;print r%%(r,n)';n=(0xF...FL+1)%0x10...0L;print r%(r,n)

there are 16ⁿ programs of length at most 68+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s="""
print 's='+'"'+'"'+'"'+s+'"'+'"'+'"'
n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0]
print s[:112]
t=n(t)
print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1)
for i in range(len(t)-1):
    print i*' '+'for i in range(2):'
    print ' '+i*' '+['pass','t=n(t)'][t[i+1]]
print s[113:-1]
"""

print 's='+'"'+'"'+'"'+s+'"'+'"'+'"'
n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0]
print s[:112]
t=(0,)+(0,)*10
for i in range(2):
 t=n(t)
 for i in range(2):
  t=n(t)
  for i in range(2):
   t=n(t)
   for i in range(2):
    t=n(t)
    for i in range(2):
     pass
     for i in range(2):
      t=n(t)
      for i in range(2):
       pass
       for i in range(2):
        pass
        for i in range(2):
         pass
         for i in range(2):
          t=n(t)
t=n(t)
print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1)
for i in range(len(t)-1):
    print i*' '+'for i in range(2):'
    print ' '+i*' '+['pass','t=n(t)'][t[i+1]]
print s[113:-1]

Answer 2

C++, score of 0.734194

The following source code prints a meta quine of order 999 to the console (explanation below):

#define X 1*(1+1)
#include<iostream>
#include<vector>
#define Q(S)auto q=#S;S
Q( \
  main() \
  { \
      using namespace std; \
      cout<<"#define X 1"; \
      int x=X==2?1000:X-1; \
      vector<int> factors; \
      for ( int p = 2; p <= x; ++p) \
      { \
        while ( x % p == 0 ) \
        { \
          factors.push_back( p ); \
          x /= p; \
        } \
      } \
      for ( int factor : factors ) \
      { \
        cout<<"*(1"; \
        for ( int i=1;i<factor;++i) \
          cout<<"+1"; \
        cout<<")"; \
      } \
      cout<<"\n#include<iostream>\n#include<vector>\n#define Q(S)auto q=#S;S\nQ("<<q<<")"; \
  })

The only line that changes is the first line. The value of X will be 1000, 999, 998, ..., 3, 2 and then it will start again. However, in order to get different syntax trees every time, X is represented in terms of its prime factorization, where every prime is written as a sum of 1s. The ASTs are different, because the prime factorization of integers is different for every value.

The program will print itself, except that the first line is changed and the backslashes, line breaks and indentations that are within Q(...) will be removed.

The following program calculates the score of my answer:

#include <iostream>

const int n = 1000;

int getProgramLength( int n )
{
  int sum = 442;
  for ( int p = 2; p*p <= n; ++p )
  {
    while ( n % p == 0 )
    {
      sum += 2 * ( 1 + p );
      n /= p;
    }
  }
  if ( n > 1 )
    sum += 2 * ( 1 + n );
  return sum;
}

int main()
{
  int sum = 0;
  for ( int i = 2; i <= n; ++i )
    sum += getProgramLength( i );
  std::cout << (double)sum/(n-1)/(n-1) << '\n';
}

It printed 0.734194 to the console. Obviously, 1000 can be replaced by larger integers and the score will approach 0 as its limit. The mathematical proof involves Riemann's Zeta function is somewhat convoluted. I leave it as an exercise to the reader. ;)

Answer 3

Perl, score of 110.25

I have to admit, I'm not very good with quines. I'm 100% certain that there is room for improvement. The solution is based off of the same principle of the Element solution below.

The first program is 264 characters.

$s='$a=chr(39);print"\$s=$a$s$a;";$s=reverse$s;for(1..87){chop$s}$s=reverse$s;print$s;$f++;if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}';$a=chr(39);print"\$s=$a$s$a;";$s=reverse$s;for(1..87){chop$s}$s=reverse$s;print$s;$f++;if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}

The second program is 177 characters.

$s='$a=chr(39);print"\$s=$a$s$a;";$s=reverse$s;for(1..87){chop$s}$s=reverse$s;print$s;$f++;if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}';if($f==0){$a=chr(39);print"\$s=$a$s$a;$s"}

I'm working on the AST for this entry (and the Element entry).

---

Element, score of 47.25

The first program is 105 characters.

\ \3\:\$\'\[\\\\\`\(\`\]\#\2\1\'\[\(\#\]\`\ \3\:\$\'\[\\\\\`\(\`\]\#\` 3:$'[\\`(`]#21'[(#]` 3:$'[\\`(`]#`

The second program is 84 characters.

\ \3\:\$\'\[\\\\\`\(\`\]\#\2\1\'\[\(\#\]\`\ \3\:\$\'\[\\\\\`\(\`\]\#\` 3:$'[\\`(`]#`

I'm sure that there is a lot of room for improvement.

In the first program there is one string (in which every character is escaped, despite a lot of redundancy) followed by executable parts A and B. Part A does several things: prints the string and escapes out of every character, prints the last half of the string (which is the source for part B), and then prevents the part B that follows it from doing anything.

The second program is the same string followed by part B. Part B is based off of a simple quine; it prints a string preceded by an escaped version of it. This means it prints the string, and both parts A and B.

Answer 4

VBA: (251+216)/2/2 = 116.75

251

Sub a()
r=vbCrLf:c="If b.Lines(4, 4) = c Then"&r &"b.InsertLines 8, d"&r &"b.DeleteLines 4, 4"&r &"End If":d="b.InsertLines 6, c"&r &"b.DeleteLines 4, 2"
Set b=Modules("Q")
If b.Lines(4, 4) = c Then
b.InsertLines 8, d
b.DeleteLines 4, 4
End If
End Sub

216

Sub a()
r=vbCrLf:c="If b.Lines(4, 4) = c Then"&r &"b.InsertLines 8, d"&r &"b.DeleteLines 4, 4"&r &"End If":d="b.InsertLines 6, c"&r &"b.DeleteLines 4, 2"
Set b=Modules("Q")
b.InsertLines 6,c
b.DeleteLines 4,2
End Sub

This is run in MSAccess to make use of the Module object. The module is named "Q" for golfing. The difference in syntax comes from the If ... Then missing from the shorter version.

Answer 5

J - (24+30)/2 / 2 = 13.5 pts

Note that strings in J are not the backslash-escaped, but quote-escaped à la Pascal: 'I can''t breathe!'.

30$(,5#{.)'''30$(,5#{.)'         NB. program 1, 24 char
'30$(,5#{.)''''''30$(,5#{.)'''   NB. program 2, 30 char

Program 1 has AST noun verb hook noun and program 2 has AST noun. Program 2 is a quoted version of program 1, which will just return program 1 when run, so this method can't be extended to three copies that easily :P

Program 1 operates by taking a copy of the code portion of the source, with a quote appended at the front, and adding five of those quotes to the end ((,5#{.)). Then, it cyclically takes 30 characters from this 16-character string, which gives exactly Program 2 as a result.

Answer 6

JavaScript, 84.5 64 61

Two programs, both length 169 128 122.

(function c(){alert(/*
2/*/1/**/);return ('('+c+')()').replace(/\/([/\*])/,function(m,a){return a=='*'?'/\/':'/\*'});
})()

Before I golfed it, for your viewing pleasure:

(function c() {
    var r = /\/([/\*])/;
    var f = function(m, a) { return a === '*' ? '/\/' : '/\*' };
    var p = '(' + c + ')();';
    p = p.replace(r, f);
    /* This is just a comment!
    console.log('Quine, part two!'); /*/
    console.log('Quine, part one!'); /**/
    return p;
})();

Returns the new program and outputs the current part! I could probably make it shorter without the function regex, but... I don't want to.