levison@qucis.UUCP (Mike Levison) (12/22/87)
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.djones@megatest.UUCP (Dave Jones) (12/26/87)
in article <52@qucis.UUCP>, levison@qucis.UUCP (Mike Levison) says: > > > > 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): [...] The "quotemark" problem is the only hard problem. How do you make this program character-set independant? (The one I posted will work just as well on an EBCDIC machine as on an ASCII machine. This posting does not contain everything I want ot know on self-replicating programs. Dave Jones Megatest Corp. 880 Fox Lane San Jose, CA. 95131 (408) 437-9700 Ext 3227 UUCP: ucbvax!sun!megatest!djones ARPA: megatest!djones@riacs.ARPA
luc@kulcs.UUCP (Luc Van Braekel) (12/29/87)
In article <188@goofy.megatest.UUCP>, djones@megatest.UUCP (Dave Jones) writes: > The "quotemark" problem is the only hard problem. How do you make > this program character-set independant? (The one I posted will > work just as well on an EBCDIC machine as on an ASCII machine. > This posting does not contain everything I want ot know on > self-replicating programs. The quotemark problem is not so difficult to solve. Here is a slightly modified version of the program I posted some time ago. This version is character-set independant. Again, this is an ugly but very short Pascal program that doesn't use external files etc. At least one thing that's shorter in Pascal than in C ! :-) program self (output); const q = ''''; var i,j: integer; a: array[1..8] of packed array[1..59] of char; begin a[1] := 'program self (output); const q = ''''''''; '; a[2] := 'var i,j: integer; '; a[3] := ' a: array[1..8] of packed array[1..59] of char; begin '; a[4] := 'for i := 1 to 3 do writeln(a[i]); '; a[5] := 'for i := 1 to 8 do begin write('' a['',i:0,''] := '',q); '; a[6] := 'for j := 1 to 59 do begin write(a[i][j]);if a[i][j]=q '; a[7] := 'then write(a[i][j]) end; writeln(q,'';'') end; '; a[8] := 'for i := 4 to 8 do writeln(a[i]) end. '; for i := 1 to 3 do writeln(a[i]); for i := 1 to 8 do begin write(' a[',i:0,'] := ',q); for j := 1 to 59 do begin write(a[i][j]);if a[i][j]=q then write(a[i][j]) end; writeln(q,';') end; for i := 4 to 8 do writeln(a[i]) end. +-----------------------------------+------------------------------------+ | Name : Luc Van Braekel | Katholieke Universiteit Leuven | | UUCP : luc@kulcs.UUCP | Department of Computer Science | | BITNET : luc@blekul60.bitnet | Celestijnenlaan 200 A | | Phone : +(32) 16 20 0656 x3563 | B-3030 Leuven (Heverlee) | | Telex : 23674 kuleuv b | Belgium | +-----------------------------------+------------------------------------+