Quine In Stratego

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
    ; <print>(stdout, [<id>])
    ; <exit> 0
-----------------------------------

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; <print>(stdout, [<id>]); <exit> 0"]
    ; \ [x, y] -> [x, x, y, y] \ 
    ; concat-strings
    ; <print>(stdout, [<id>])
    ; <exit> 0
------------------------------------------------------------------------------------------

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; <print>(stdout, [<id>]); <exit> 0]; \ [x, y] -> 
[x, x, y, y] \; concat-strings; <print>(stdout, [<id>]); <exit> 0
------------------------------------------------------------------

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; <print>(stdout, [<id>]); <exit> 0"]
    ; \ [x, y] -> [x, x, "\",\"", y, y] \ 
    ; concat-strings
    ; <print>(stdout, [<id>])
    ; <exit> 0
------------------------------------------------------------------------------------------

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; <print>(stdout, [<id>]); <exit> 0"]; \ [x, y] -> 
[x, x, y, y] \; concat-strings; <print>(stdout, [<id>]); <exit> 0
------------------------------------------------------------------

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, <escape>x, \"\\\",\\\"\", <escape>y, y] \\; concat-strings; <print>(stdout, [<id>]); <exit> 0"]
    ; \ [x, y] -> [x, <escape>x, "\",\"", <escape>y, y] \ 
    ; concat-strings
    ; <print>(stdout, [<id>])
    ; <exit> 0
------------------------------------------------------------------------------------------

This produces (without the newlines)

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

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.