Path: utzoo!utgpu!jarvis.csri.toronto.edu!utcsri!qucis!levison
From: levison@qucis.UUCP (Mike Levison)
Newsgroups: comp.lang.pascal
Subject: Self-replicating programs
Message-ID: <52@qucis.UUCP>
Date: 22 Dec 87 15:53:22 GMT
Article-I.D.: qucis.52
Posted: Tue Dec 22 10:53:22 1987
Organization: Queen's University, Kingston, Ontario, Canada
Lines: 111
Keywords: Self-replication chromosome



This is probably more than you ever wanted to know on self-
replicating programs:

         Self-Reproducing Program (Pascal version)

The  basic idea is  to create within the program an array of
characters  which consists  of the whole  program EXCEPT for
the  assignments which  initialize  the array. The  array is
then used once  for printing the basic program, and a second
for printing the assignments.

Ignore for  a moment  two minor annoyances: line layout, and
the fact  that one cannot  assign or output quotemarks using
c[i]:= ''' or write(''').  Both can be overcome trivially at
the  expense of clarity. Then the program is as follows (the
comments are not part of it):

  program hermaph (input, output);

    const len = ???;        {len is the number of chars in this program
                            without the assignments;  mid is the number
                            up to the assignments. len may be 357, say}
          mid = ???;

    var chrom : array [1..len] of char;
            i : integer;

  begin

    chrom[1]:= 'p';
    chrom[2]:= 'r';
    chrom[3]:= 'o';
    chrom[4]:= 'g';
    ...                     {and another 349 or so}
    chrom[354]:= 'e';
    chrom[355]:= 'n';
    chrom[356]:= 'd';
    chrom[357]:= '.';

    for i:= 1 to mid do write(chrom[i]);

    for i:= 1 to len do
      begin
        writeln("chrom[");
        write(i);
        write("]:= '");
        write(chrom[i]);
        write("';")
      end;

    for i:= mid + 1 to len do write(chrom[i]);
    writeln;

  end.


Note the  three  for-loops. The first and third simply print
the contents  of chrom, and  so  produce the  first and last
parts  of the program.  The second uses chrom in a different
way to generate  the 357 assignment statements. (There is an
interesting analogy with a cell; the chromosome is used once
to construct the body of the cell, and in a different way to
replicate itself.)

In a  language which allows  the  assignment and printing of
whole  strings,  the  body  of  the  above program  is  more
concise, something like:

  {A}
  chrom1:= "program herm   ...  {A}";
  chrom2:= "{B}  ...  end.";

  {B}
  write(chrom1);
  write("chrom1:= &"); write (chrom1) ; write ("&;");
  write("chrom2:= &"); write (chrom2) ; write ("&;");
  write(chrom2)

where  &  is really  supposed to be " (the quotemark problem
again).

As to  the annoyances, the quotemark problem can be bypassed
by storing integers (the ASCII values) instead of chars, and
using chr(chrom[i]) for output. Or one can use & to denote "
in strings, and replace 'write' by a procedure which behaves
like the usual one but prints " when it sees &.

If we want  the  offspring to  be identical to the parent in
layout,  we  could   use   a  special  character  to  denote
'newline',  and  again declare a  new  'write' to  interpret
this.  But  this is  not  really necessary.  Call  the above
program h,  and its output son-of-h. Then certainly son-of-h
may   differ  in  layout  from  h,  but  son-of-son-of-h  is
identical to son-of-h.  So the true self-reproducing program
is son-of-h, rather than h itself.

Finally, typing  the  357 (??)  assignments  in  the  Pascal
version of  h would  be very tedious.  But  this too  can be
avoided. We create  a  datafile shell-of-h,  which is h with
the  assignments omitted. And we create a program mother-of-
h,  similar to  h  but  with  chrom  initialized  by reading
characters from a datafile. Now mother-of-h reads shell-of-h
to create h  as output (and this h will already be identical
to its child in layout.)

As a matter of interest, a discussion on this topic, without
a program or programming language being involved occurred in
the work of John von Neumann on self-reproducing automata in
the early fifties.