Skip to content
Print

Useless Hackery: A Scala Quine

30
Apr
2008

Warning: This post has little-to-no practical value.  Waste time at your own risk…

While double-checking the terms for my previous post, I came across the Wikipedia definition of a polyglot program:

In the context of computing, a polyglot is a computer program or script written in a valid form of multiple programming languages, which performs the same operations or output independently of the programming language used to compile or interpret it.

Not precisely the same as the definition which has now come into common use (referring to the use of multiple languages in a single application).  The article goes on to give two examples of a polyglot, one in PHP/C/Bash and one in Haskell/OCaml/Scheme (I don’t count the Perl/DOS example since it doesn’t perform the same function in both languages).  These examples are quite interesting, but what really caught my eye were the additional properties of the second example: not only is it a polyglot, but it is also a quine:

In computing, a quine is a program, a form of metaprogram, that produces its complete source code as its only output.

Think about that for just a second: A program which produces itself as its only output.  I think that’s probably the most profound brain-teaser that I’ve run across in months.  Consider for a moment just how one would accomplish this.  For example, we could try a naive implementation in Ruby:

puts "puts \"puts \\\"..."

You’ll notice that we have run into a bit of a problem.  In fact, the infinitely recursive nature of the definition is precisely what makes quines so interesting.  Of course, I’m aware that there are already a number of very clever Ruby quines, but that’s not the point.  After all, what good is a puzzle if someone else gives you the solution?

By putting a little thought into this, we can devise a slightly more advanced attempt which brings us a bit closer to quine-ness:

s = "s = \"#{s}\"; puts s"
puts s

We’re getting closer, anyway.  We still have a serious problem in that string declaration (hint: it has something to do with the whole recursiveness thing).  We have to somehow include the string within itself once explicitly, but on the inner recursion only include a textual reference to itself.  This is by no means trivial to accomplish.

One technique we can employ is string formatting.  Old C salts will certainly be familiar with the printf function.  There’s a clever little trick we can employ which allows us to format a string using itself as the format string.  This is one way to provide single-level recursion in the string resolution:

char *s = "char *s = \"%s\"; printf(s, s);";
printf(s, s);

Note that I’m cheating a bit on the formatting to make things more readable.  There’s really nothing preventing this sample from formatting a bit more correctly (newline, etc).

We’re almost there now.  Our only remaining problem is the fact that the second recursion of the string will have improperly quoted double-quotes.  Gary Thompson shows a fully fleshed-out C quine which gets around this problem by exploiting the int/char duality in the language.  However, this little trick isn’t precisely available in languages like Scala.  Well, it is, but there are problems with the printf formatting which obviate the possibility.  Specifically, Scala’s printf method does not allow for the standard %s-style formatting (even though the scaladoc claims that it does).  All that this function allows us are simple substitutions, but it turns out that this is enough to (finally) complete our quine in Scala (formatted for easy reading):

object Q extends Application {
  val s = "object Q extends Application'{'val s={0}{2}{0};printf(s,{0}{1}{0}{0},{0}{1}{1}{0},s)}"
  printf(s, "\"", "\\", s)
}

Even with the reformatting, the second line still overflows the formatting on most browsers (sorry about that).  I’ve uploaded the unformatted, “true quine” here.

It’s somewhat interesting that Scala’s syntax is concise enough (especially with type inference) that this sort of thing is possible in only 149 characters.  If you look around for Java quines (there are a few of them), you’ll see that most of them take a similar approach, but they usually have trouble with the encumbrances of Java’s highly-verbose syntax.  It’s sort-of depressing to condense your code when you have to type “public static void main” regardless.

Anyway, I’m certainly not an expert on the ins-and-outs of the Scala library.  Suggestions welcome on how to golf this down a bit.   Or better yet, an extremely clever solution which eluded me entirely.

Comments

  1. Nope, you can do better in Java, look at this beauty with 135 characters:

    enum S{T;System y;String s=”enum S{T;System y;String s=%c%s%1$c;{y.out.printf(s,34,s);y.exit(0);}}”;{y.out.printf(s,34,s);y.exit(0);}}

    Landei Wednesday, April 30, 2008 at 5:03 am
  2. Doesn’t count, because you can’t actually compile and run it (no main method).

    Daniel Spiewak Wednesday, April 30, 2008 at 10:12 am
  3. Quines are somewhat entertaining. I actually managed to wreak some havoc with one:

    http://kaioa.com/node/48

    But for the most part it’s indeed just a pointless brain teaser. :)

    Jos Hirth Wednesday, April 30, 2008 at 11:34 pm
  4. Quines are more than just entertaining, the idea is the foundation of Godel’s incompleteness theorem.

    Cliff Vick Thursday, May 1, 2008 at 6:57 am
  5. Actually you can compile and run it, it uses an initialiser instead of main. The JVM loads the class then tries to call main. In this case it doesn’t get as far as calling main, because the initialiser exits.

    Ricky Clarkson Thursday, May 1, 2008 at 8:04 am
  6. Wow, you’re right! That’s pretty clever actually.

    Daniel Spiewak Thursday, May 1, 2008 at 9:56 am
  7. Just for the record, combining our approaches gives a 112 char Scala quine, and I see no easy way to get it shorter:

    object Q extends Application{val s=”object Q extends Application{val s=%c%s%1$c;printf(s,34,s)}”;printf(s,34,s)}

    Landei Wednesday, August 20, 2008 at 2:20 am

Post a Comment

Comments are automatically formatted. Markup are either stripped or will cause large blocks of text to be eaten, depending on the phase of the moon. Code snippets should be wrapped in <pre>...</pre> tags. Indentation within pre tags will be preserved, and most instances of "<" and ">" will work without a problem.

Please note that first-time commenters are moderated, so don't panic if your comment doesn't appear immediately.

*
*