Le théorème de la récursion de Kleene (voir p.ex. Machtey & Young, An introduction to the general theory of algorithms, th 3.4.1) garantit l'existence, dans tout système acceptable de programmation, de programmes dont l'exécution imprime leur propre code source (et ce bien sûr sans aller chercher leur code source dans un quelconque système de fichiers).

Douglas Hofstadter a nommé ce genre de programmes des « quines », par allusion à un philosophe logicien bien connu (enfin, sauf en France). L'article Wikipédia sur le sujet liste des « quines » astucieusements construits à la main. Pour ma part, j'ai voulu en construire un effectivement par application de la construction du point fixe.

J'ai besoin pour cela d'une machine universelle, Invoke.eval(x, y) qui lance le programme x sur l'entrée y : pour cela, je lance le compilateur Java et je charge la classe résultante, et d'une fonction auxiliaire JavaUtil.writeEscaped qui « échappe » les chaînes de caractères (plus précisément, qui transforme une chaîne de caractères en un lexème littéral qui représente cette chaîne). Sinon, c'est du Java 6 standard. Par commodité, un programme est supposé avoir une fonction public static String run(String x).

Voici le « quine » obtenu. Tous les fichiers ayant servi à sa préparation sont disponibles.

class Recursor {
  public static String run(String y) {
    final String x = "class Composed {\n  static class First {\n      public static String run(String x) {\n  	try {\n  	    java.io.StringWriter out = new java.io.StringWriter();\n  	    out.write(\"class Printer {\\n\");\n  	    out.write(\"  public static String run(String dummy) {\\n\");\n  	    out.write(\"    return \\\"\");\n  	    JavaUtil.writeEscaped(out, x);\n  	    out.write(\"\\\";\\n\");\n  	    out.write(\"  }\\n\");\n  	    out.write(\"}\\n\");\n  	    return out.toString();\n  	} catch (java.io.IOException exn) {\n  	    throw new RuntimeException(\"printer\", exn);\n  	}\n      }    \n  }\n  static class Second {\n      static String run(String x) {\n  	try {\n  	    java.io.StringWriter out = new java.io.StringWriter();\n  	    out.write(\"class Recursor {\\n\");\n  	    out.write(\"  public static String run(String y) {\\n\");\n  	    out.write(\"    final String x = \\\"\");\n  	    JavaUtil.writeEscaped(out, x);\n  	    out.write(\"\\\";\\n\");\n  	    out.write(\"    return Invoke.eval(Invoke.eval(x, new String[] { x }), new String[] { y });\\n\");\n  	    out.write(\"  }\\n\");\n  	    out.write(\"}\\n\");\n  	    return out.toString();\n  	} catch (java.io.IOException exn) {\n  	    throw new RuntimeException(\"fixpoint\", exn);\n  	}\n      }\n  }\n  public static String run(final String x) {\n    return First.run(Second.run(x));\n  }\n}\n";
    return Invoke.eval(Invoke.eval(x, new String[] { x }), new String[] { y });
  }
}