Title: Program Challenge Report 3 and Challenge 4

Author: Bob Schmidt

Date: 02 July 2018 16:24:33 +01:00 or Mon, 02 July 2018 16:24:33 +01:00

Summary: Francis Glassborow comments on his last challenge and presents a new one.

Body: 

I am a little disappointed by the (lack of) response to this challenge. I had very carefully phrased the challenge so as not to make it an actual ‘quine’ (self-replicating program), I also avoided mentioning ‘quine’ because that makes it trivial, just search the net.

As in all my challenges, anything not expressly forbidden is permitted. The simple answer which will certainly run on your machine is to write a program that reads in its own source code file and then prints it out.

If you are writing a self-replicating program that will run anywhere (including on my machine) you have an important consideration:

Can my machine execute a program compiled on your machine?

If we assume the answer is ‘no’ then it effectively means that the program has to be delivered as source code. Once you understand the significance of that the problem reverts to writing a program that will produce the correct output on the machine on which it is compiled.

Now I suspect that many of you thought I was asking for a ‘quine’ in C++. Without knowing the name it is very hard to cheat by looking the answer up on the internet. Our ancestors were right in the belief that knowing something’s true name gives you power over it.

Here is the only response I got.

Response from James Holland

I thought one way was to write a very simple C++ program that prints a string that contains the source code of the program, something like the following.

  #include <iostream>
  int main()
  {
    std::cout << "#include <iostream>\nint
    main()\n{\n  std::cout << \"\";\n}\n";
  }

The trouble is the program is not quite complete because its output is as shown below.

  include <iostream>
  int main()
  {
    std::cout << "";
  }

There is nothing in the quoted string so let’s fix that.

  #include <iostream>
  int main()
  {
    std::cout << "#include <iostream>\nint
    main()\n{\n  std::cout << \"#include
    <iostream>\\nint main()\\n{\\n  std::cout 
    << \\\"\\\";\\n}\\n\";\n}\n";
  }

We are not there yet as this program produces the following.

  #include <iostream>
  int main()
  {
    std::cout << "#include <iostream>\nint
    main()\n{\n  std::cout << \"\";\n}\n";
  }

Which produces the following.

  #include <iostream>
  int main()
  {
    std::cout << "";
  }

There is nothing in the quoted string so let’s fix that. But wait. We have been here before. We can keep on adding to the string forever and still not have a program that reproduces itself. This approach is not going to work. This is where I cheated and tried to discover how other people have solved this problem.

Apparently, one method is to divide the program into two parts. The first part contains data that represents the second part of the program. The second part contains code that firstly prints the data as it is presented in the first part of the program and secondly uses the data (again) to print the second part of the program in the form of its source code. (I am sure you are still with me.) The result is a printout of the complete program’s source code. Such a program (one that outputs its own source code) is called a Quine, after Willard Van Orman Quine (1908–2000), or so I have discovered. My attempt is in Listing 1.

const char data[]{
  35, 105, 110, 99, 108, 117, 100, 101, 32, 60,
  105, 111, 115, 116, 114, 101, 97, 109, 62, 13,
  10, 35, 105, 110, 99, 108, 117, 100, 101, 32,
  60, 115, 116, 114, 105, 110, 103, 62, 13, 10,
  13, 10, 105, 110, 116, 32, 109, 97, 105, 110,
  40, 41, 13, 10, 123, 13, 10, 32, 32, 115, 116,
  100, 58, 58, 99, 111, 117, 116, 32, 60, 60, 32,
  34, 99, 111, 110, 115, 116, 32, 99, 104, 97,
  114, 32, 100, 97, 116, 97, 91, 93, 123, 34, 59,
  13, 10, 32, 32, 115, 116, 100, 58, 58, 115,
  116, 114, 105, 110, 103, 32, 115, 101, 112,
  97, 114, 97, 116, 111, 114, 59, 13, 10, 32, 32,
  105, 110, 116, 32, 99, 111, 108, 117, 109, 110,
  95, 99, 111, 117, 110, 116, 32, 61, 32, 48, 59,
  13, 10, 32, 32, 102, 111, 114, 32, 40, 99, 111,
  110, 115, 116, 32, 105, 110, 116, 32, 99, 32,
  58, 32, 100, 97, 116, 97, 41, 13, 10, 32, 32,
  123, 13, 10, 32, 32, 32, 32, 115, 116, 100, 58,
  58, 99, 111, 117, 116, 32, 60, 60, 32, 115,
  101, 112, 97, 114, 97, 116, 111, 114, 32, 60,
  60, 32, 99, 59, 13, 10, 32, 32, 32, 32, 115,
  101, 112, 97, 114, 97, 116, 111, 114, 32, 61,
  32, 34, 44, 32, 34, 59, 13, 10, 32, 32, 32, 32,
  105, 102, 32, 40, 43, 43, 99, 111, 108, 117,
  109, 110, 95, 99, 111, 117, 110, 116, 32, 61,
  61, 32, 49, 54, 41, 13, 10, 32, 32, 32, 32,
  123, 13, 10, 32, 32, 32, 32, 32, 32, 99, 111,
  108, 117, 109, 110, 95, 99, 111, 117, 110, 116,
  32, 61, 32, 48, 59, 13, 10, 32, 32, 32, 32, 32,
  32, 115, 101, 112, 97, 114, 97, 116, 111, 114,
  32, 61, 32, 34, 44, 92, 110, 32, 32, 32, 32,
  32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
  32, 32, 34, 59, 13, 10, 32, 32, 32, 32, 125,
  13, 10, 32, 32, 125, 13, 10, 32, 32, 115, 116,
  100, 58, 58, 99, 111, 117, 116, 32, 60, 60, 32,
  34, 125, 59, 92, 110, 92, 110, 34, 59, 13, 10,
  32, 32, 102, 111, 114, 32, 40, 99, 111, 110,
  115, 116, 32, 97, 117, 116, 111, 32, 99, 32,
  58, 32, 100, 97, 116, 97, 41, 13, 10, 32, 32,
  123, 13, 10, 32, 32, 32, 32, 115, 116, 100, 58,
  58, 99, 111, 117, 116, 32, 60, 60, 32, 99, 59,
  13, 10, 32, 32, 125, 13, 10, 125, 13, 10};

#include <iostream>
#include <string>

int main()
{
  std::cout << "const char data[]{";
  std::string separator;
  int column_count = 0;
  for (const int c : data)
  {
    std::cout << separator << c;
    separator = ", ";
    if (++column_count == 16)
    {
      column_count = 0;
      separator = ",\n                  ";
    }
  }
  std::cout << "};\n\n";
  for (const auto c : data)
  {
    std::cout << c;
  }
}
			

It would be difficult to produce the data by hand and so I have written a small program – see Listing 2 – to do the job for me. It takes as input the program source code (minus the first part) and produces the equivalent in decimal form. The program’s output is then pasted into the original source code to form the complete Quine program.

#include <fstream>
#include <iostream>

int main()
{
  std::ofstream out_file("Quine.dat");
  out_file << "const char data[]{";

  std::ifstream in_file("..//Quine.cpp");

  std::string separator;
  int column_count = 0;
  char c;
  while (in_file.get(c))
  {
    out_file << separator.c_str() << static_cast<int>(c);
    separator = ", ";
    if (++column_count == 16)
    {
      column_count = 0;
      separator = ",\n                  ";
    }
  }
  out_file << "};";
}
			

Francis states there are two categories of solution; one that will run on my computer and one that will run on his computer. I have no idea what computer Francis uses. It should not really matter. All that is required is for the computer to have a standard conformant C++11 compiler and for the source code (Quine.cpp) to be compiled and run. The resultant executable should print its own source code on any system. If the output is directed to a file, the content of the file will be identical to the original source code.

Francis replies

James is quite right up to a point. The problem is that his program assumes that my machine is using ASCII and there is no such requirement in the Standard (nor could there be). I do not have an Apple computer to hand but I strongly suspect that it would fail to produce the required output because it codes End of Line differently. However that is being a little picky. More significantly there are still machines around that use EBCDIC. I leave the reader to research that. It is a common flaw in those writing portable code to assume that all computers use ASCII or Unicode (where the base page is, if I recall correctly, ASCII).

I think that fully portable quine source code is actually quite difficult and almost certainly requires some tool support to deal with variant text coding.

Then there is the point that I think James missed so perhaps it was missed by many readers: A conforming C program is almost certainly going to be a C++ one as well. At least that is one of the objectives of WG21 (The ISO C++ Standards Committee). That objective is very frustrating when developing new core facilities for C++. As we know, C++ can easily add new types via library implementations (think of support for complex numbers) and C has to do that by adding to its basic type system. Where both languages want the same type but both want (need) to do it their way providing a compatible mechanism can be hard.

Now the simplest C quine I know is:

  #include <stdio.h>
  char*s="#include <stdio.h>%cchar*s=%c%s%c;%cint
  main(){printf(s,10,34,s,34,10,10);}%c";
  int main(){printf(s,10,34,s,34,10,10);}

It also depends on the program encoding newline as 10 and double quotes as 34. It has the advantage of having only those two dependencies and so is relatively easy to adapt to systems using other character encodings.

I wonder if anyone can refine the above program so that it becomes independent of the character coding. Careful use of escape sequences might achieve the desired result and so produce a program that will run on any machine.

Challenge 4

I was wondering what to challenge the readers with next. While still undecided I went to the April meeting of the Oxford branch of ACCU. One of the other attendees (sorry I have forgotten who it was) offered this one:

Write a program that outputs the numbers from 1 to 100 without using if, for, switch or while.

I cannot think of a way to do this in C other than the trivial solution of simply writing tedious outputs, but I certainly can manage it in C++. However, I am going to add a small refinement, your program must take two integer inputs: first and last. It must output the integers from the first to the last. Note that I have not specified that the first is lower than the last.

For starters try the simple form where first = 1 and last =100. Some of you may think ‘recursion’, but that requires a conditional to ensure termination, or does it?

There is also a second form of solution that relies on the way that C++ initialises arrays.

Over to you. Please submit your solutions even if they are just partial ones. Sometimes ideas that do not quite work can be refined when others see where you are trying to go.

Notes: 

More fields may be available via dynamicdata ..