Quine In Stratego

Tonight I was reminiscing with Tijs van der Storm about conferences of the past, in particular the day that I wrote a Quine in Stratego at OOPSLA 2004. I reported about that in my pre-blog and at the Stratego/XT site, but not in this blog. Since it was a fun example, I thought it deserved a place on my official blog. Here goes:

After GPCE/OOPSLA in Vancouver Tijs van der Storm challenged me to write a Stratego program that prints its own source. So I set to work, with the following result. I’ll make it educational and reconstruct the design process.

The basic idea

The core of a self printing program is that it should contain its own source and duplicate that. The following program implements this idea, but with ‘prefix’ and ‘suffix’ instead of the

----------------------------------
module quine 
imports lib
strategies
  main =
    !["prefix", "suffix"]
    ; \ [x, y] -> [x, x, y, y] \ 
    ; concat-strings
    ; (stdout, [])
    ;  0
-----------------------------------
</pre>

Compiling and running this program produces:

prefixprefixsuffixsuffix


Quoting the source

Next we replace 'prefix' and 'suffix' by the prefix and suffix of the program
with respect to the list. Note that we don't bother with the layout of the
quoted fragment. Note that the backslashes of the anonymous rewrite rule need
to be escaped in the string.

------------------------------------------------------------------------------------------
module quine 
imports lib
strategies
  main =
    !["module quine imports lib strategies main = ![", 
      "]; \\ [x, y] -> [x, x, y, y] \\; concat-strings; (stdout, []);  0"]
    ; \ [x, y] -> [x, x, y, y] \ 
    ; concat-strings
    ; (stdout, [])
    ;  0
------------------------------------------------------------------------------------------
</pre>

The output of this program is

------------------------------------------------------------------
module quine imports lib strategies main = ![module quine 
imports lib strategies main = ![]; \ [x, y] -> [x, x, y, y] \; 
concat-strings; (stdout, []);  0]; \ [x, y] -> 
[x, x, y, y] \; concat-strings; (stdout, []);  0
------------------------------------------------------------------
</pre>

which is starting to look good, but not quite there, since it doesn't compile.

Getting the quotes right

What we have to do now is introduce quotes in the printed program, such that the pieces
of code in the list are actually parsed as strings.

------------------------------------------------------------------------------------------
module quine 
imports lib
strategies
  main =
    !["module quine imports lib strategies main = ![\"", 
      "\"]; \\ [x, y] -> [x, x, y, y] \\; concat-strings; (stdout, []);  0"]
    ; \ [x, y] -> [x, x, "\",\"", y, y] \ 
    ; concat-strings
    ; (stdout, [])
    ;  0
------------------------------------------------------------------------------------------
</pre>

The output of this program is

------------------------------------------------------------------
module quine imports lib strategies main = !["module quine 
imports lib strategies main = !["",""]; \ [x, y] -> [x, x, y, y] \; 
concat-strings; (stdout, []);  0"]; \ [x, y] -> 
[x, x, y, y] \; concat-strings; (stdout, []);  0
------------------------------------------------------------------
</pre>

which still does not compile because of the doublequotes embedded in the string.

Getting the quotes more right

We need to escape the embedded strings. This can be achieved easily by using the
escape strategy from the library, which escapes doublequotes and backslashes.

------------------------------------------------------------------------------------------
module quine 
imports lib
strategies
  main =
    !["module quine imports lib strategies main = ![\"", 
      "\"]; \\ [x, y] -> [x, x, \"\\\",\\\"\", y, y] \\; concat-strings; (stdout, []);  0"]
    ; \ [x, y] -> [x, x, "\",\"", y, y] \ 
    ; concat-strings
    ; (stdout, [])
    ;  0
------------------------------------------------------------------------------------------
</pre>

This produces (without the newlines)

-----------------------------------------------------------------------------
module quine imports lib strategies main = !["module quine imports 
lib strategies main = ![\"","\"]; \\ [x, y] -> [x, x,
 \"\\\",\\\"\", y, y] \\; concat-strings; (stdout
, []);  0"]; \ [x, y] -> [x, x, "\",\"", y, y] \; 
concat-strings; (stdout, []);  0
-----------------------------------------------------------------------------
</pre>

Bootstrapping

Now the last program is not exactly the same as its predecessor, but if we
compile and run it, it produces its own source literally.