hirai@swatsun (Eiji "A.G." Hirai) (11/22/87)
Hi: In our recent ACM programming contest (regionals), one of the problems was to write a self-replicating program. That is, we had to write a program whose output was itself, the source code. No alterations of the original code during execution was allowed (I think). Does anyone have any code for this problem? We have one but it looks inelegant. I've also see bery bery short Prolog code for this. Help, we are looking for good codes to study! And yes, the contest is over (we ain't cheating). Oh thank you so much! -ag hirai eagerly waiting at my email box... -- Eiji "A.G." Hirai @ Swarthmore College, Swarthmore PA 19081 | Tel. 215-543-9855 UUCP: {rutgers, ihnp4, cbosgd}!bpa!swatsun!hirai | "All Cretans are liars." Bitnet: vu-vlsi!swatsun!hirai@psuvax1.bitnet | -Epimenides Internet: bpa!swatsun!hirai@rutgers.edu | of Cnossus, Crete
luc@kulcs.UUCP (Luc Van Braekel) (12/09/87)
In article <1400@tulum.swatsun.UUCP>, hirai@swatsun (Eiji "A.G." Hirai) writes: > In our recent ACM programming contest (regionals), one of the > problems was to write a self-replicating program. That is, we had to > write a program whose output was itself, the source code. No alterations > of the original code during execution was allowed (I think). > Does anyone have any code for this problem? We have one but > it looks inelegant. I've also see bery bery short Prolog code for this. > Help, we are looking for good codes to study! And yes, the contest is > over (we ain't cheating). Here is a self-replicating Pascal program I wrote a few years ago. The program looks dirty but it works ! program self (output); var i,j: integer; a: array[1..8] of packed array[1..59] of char; begin a[1] := 'program self (output); '; 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,''] := '',chr(39));'; a[6] := 'for j := 1 to 59 do begin write(a[i][j]);if a[i][j]=chr(39)'; a[7] := 'then write(a[i][j]) end; writeln(chr(39),'';'') 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,'] := ',chr(39)); for j := 1 to 59 do begin write(a[i][j]);if a[i][j]=chr(39) then write(a[i][j]) end; writeln(chr(39),';') 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 | +-----------------------------------+------------------------------------+
djones@megatest.UUCP (Dave Jones) (12/17/87)
in article <1070@kulcs.UUCP>, luc@kulcs.UUCP (Luc Van Braekel) says: > > In article <1400@tulum.swatsun.UUCP>, hirai@swatsun (Eiji "A.G." Hirai) writes: >> In our recent ACM programming contest (regionals), one of the >> problems was to write a self-replicating program. That is, we had to >> write a program whose output was itself, the source code. No alterations >> of the original code during execution was allowed (I think). >> Does anyone have any code for this problem? We have one but >> it looks inelegant. I've also see bery bery short Prolog code for this. >> Help, we are looking for good codes to study! And yes, the contest is >> over (we ain't cheating). > > Here is a self-replicating Pascal program I wrote a few years ago. > The program looks dirty but it works ! > > program self (output); > var i,j: integer; > a: array[1..8] of packed array[1..59] of char; begin > a[1] := 'program self (output); '; > 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,''] := '',chr(39));'; > a[6] := 'for j := 1 to 59 do begin write(a[i][j]);if a[i][j]=chr(39)'; > a[7] := 'then write(a[i][j]) end; writeln(chr(39),'';'') 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,'] := ',chr(39)); > for j := 1 to 59 do begin write(a[i][j]);if a[i][j]=chr(39) > then write(a[i][j]) end; writeln(chr(39),';') 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 | > +-----------------------------------+------------------------------------+ It's real easy to do in C. It's a bit more of a challenge to make it character-set independent. In the example you give, for example, the chr(39) is the ascii code for a single quote mark. The program will not work on an ebcdic machine. Here's a character-set independant one I did a couple of years ago. I wrote a program to write it. It is fully commented, and replicates its comments. A shell-archive, including the program which builds the self-replicating program follows, for all you unix owners. It is quite instructive. /* This program prints its source. */ main(argc, argv) char** argv; { char * dna = "/* This program prints its source. */\n\nmain(argc, argv)\n\ char** argv;\n{\n char * dna =\n\nZ;\n\n\n express(dna)\ ;\n exit(0);\n}\n\n\n/* Express the string, substituting a\ quotation of the string \n** for the character 'Z'. Break\ s the literal into lines of no\n** more than 60 chars.\n*/\n\ express(str)\n char* str;\n{\n char* ptr = str;\n char c\ h;\n int is_quoted = 0;\n\n while(ch = *ptr++)\n {\n\n\ if(ch == 'Z' && !is_quoted)\n\t{\n\t int count = 1;\n\ \t char* ptr = str;\n\t char ch;\n\t putchar('\"');\n\t \ while(ch = *ptr++)\n\t {\n\t switch(ch)\n\t {\ \n\t\tcase '\\n': printf(\"\\\\n\"); count +=2; break;\n\t\ \tcase '\\t': printf(\"\\\\t\"); count +=2; break;\n\t\tca\ se '\\\\': printf(\"\\\\\\\\\"); count +=2; break;\n\t\tcas\ e '\"': printf(\"\\\\\\\"\"); count +=2; break;\n\t\tdefau\ lt: putchar(ch); count +=1; break;\n\t }\n\t \ if(count >= 59)\n\t\t{ printf(\"\\\\\\n\");\n\t\t count =\ 0;\n\t\t}\n\t }\n\t putchar('\"');\n\t}\n\n else \ putchar(ch);\n is_quoted = ( ch == '\\'');\n }\n}\n\ "; express(dna); exit(0); } /* Express the string, substituting a quotation of the string ** for the character 'Z'. Breaks the literal into lines of no ** more than 60 chars. */ express(str) char* str; { char* ptr = str; char ch; int is_quoted = 0; while(ch = *ptr++) { if(ch == 'Z' && !is_quoted) { int count = 1; char* ptr = str; char ch; putchar('"'); while(ch = *ptr++) { switch(ch) { case '\n': printf("\\n"); count +=2; break; case '\t': printf("\\t"); count +=2; break; case '\\': printf("\\\\"); count +=2; break; case '"': printf("\\\""); count +=2; break; default: putchar(ch); count +=1; break; } if(count >= 59) { printf("\\\n"); count = 0; } } putchar('"'); } else putchar(ch); is_quoted = ( ch == '\''); } } # CUT HERE ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ # # This is a shell-achive. # # UNPACKING INSTRUCTIONS # # 1. Remove everything above the "CUT HERE" line. # 2. Move the resulting text (this archive) to an empty directory. # 3. Change (cd) to that directory. # 4. Type "/bin/sh" followed by the archive name. Example: # # /bin/sh archive # # The archived files are: # # selfrep.c # Makefile # buffered_file.c # express.c # conprog.c # soup.Z # #****************************************************************** if /bin/test -f selfrep.c then echo File \"selfrep.c\" already exists. Not overwritten. else # # echo x - selfrep.c sed 's/^XX//' > selfrep.c <<'@//E*O*F selfrep.c//' XX/* This program prints its source. */ XX XXmain(argc, argv) XX char** argv; XX{ XX char * dna = XX XX"/* This program prints its source. */\n\nmain(argc, argv)\n\ XX char** argv;\n{\n char * dna =\n\nZ;\n\n\n express(dna)\ XX;\n exit(0);\n}\n\n\n/* Express the string, substituting a\ XX quotation of the string \n** for the character 'Z'. Break\ XXs the literal into lines of no\n** more than 60 chars.\n*/\n\ XXexpress(str)\n char* str;\n{\n char* ptr = str;\n char c\ XXh;\n int is_quoted = 0;\n\n while(ch = *ptr++)\n {\n\n\ XX if(ch == 'Z' && !is_quoted)\n\t{\n\t int count = 1;\n\ XX\t char* ptr = str;\n\t char ch;\n\t putchar('\"');\n\t \ XX while(ch = *ptr++)\n\t {\n\t switch(ch)\n\t {\ XX\n\t case '\\n': printf(\"\\\\n\"); count +=2; break\ XX;\n\t\tcase '\\t': printf(\"\\\\t\"); count +=2; break;\n\t\ XX case '\\\\': printf(\"\\\\\\\\\"); count +=2; break\ XX;\n\t case '\"': printf(\"\\\\\\\"\"); count +=2; br\ XXeak;\n\t default: putchar(ch); count += 1; break;\n\t\ XX }\n\t if(count >= 59)\n\t\t{ printf(\"\\\\\\n\")\ XX;\n\t\t count = 0;\n\t\t}\n\t }\n\t putchar('\"');\n\t\ XX}\n\n else putchar(ch);\n is_quoted = ( ch == '\\\ XX'');\n }\n}\n"; XX XX XX express(dna); XX exit(0); XX} XX XX XX/* Express the string, substituting a quotation of the string XX** for the character 'Z'. Breaks the literal into lines of no XX** more than 60 chars. XX*/ XXexpress(str) XX char* str; XX{ XX char* ptr = str; XX char ch; XX int is_quoted = 0; XX XX while(ch = *ptr++) XX { XX XX if(ch == 'Z' && !is_quoted) XX { XX int count = 1; XX char* ptr = str; XX char ch; XX putchar('"'); XX while(ch = *ptr++) XX { XX switch(ch) XX { XX case '\n': printf("\\n"); count +=2; break; XX case '\t': printf("\\t"); count +=2; break; XX case '\\': printf("\\\\"); count +=2; break; XX case '"': printf("\\\""); count +=2; break; XX default: putchar(ch); count += 1; break; XX } XX if(count >= 59) XX { printf("\\\n"); XX count = 0; XX } XX } XX putchar('"'); XX } XX XX else putchar(ch); XX is_quoted = ( ch == '\''); XX } XX} @//E*O*F selfrep.c// fi if /bin/test -f Makefile then echo File \"Makefile\" already exists. Not overwritten. else # # echo x - Makefile sed 's/^XX//' > Makefile <<'@//E*O*F Makefile//' XX XXproof: selfrep XX selfrep > temp.c; diff temp.c selfrep.c; rm -f temp.c XX XXselfrep: selfrep.c XX cc selfrep.c -o selfrep XX XXselfrep.c: soup.Z conprog express.c XX /lib/cpp -P -C soup.Z > tempfile; conprog tempfile > selfrep.c; \ XX rm -f tempfile XX XXconprog: conprog.o express.o buffered_file.o XX cc conprog.o express.o buffered_file.o -o conprog XX XXclean: XX -rm -f selfrep selfrep.c conprog *.o @//E*O*F Makefile// fi if /bin/test -f buffered_file.c then echo File \"buffered_file.c\" already exists. Not overwritten. else # # echo x - buffered_file.c sed 's/^XX//' > buffered_file.c <<'@//E*O*F buffered_file.c//' XX#include <sys/param.h> XX#include <sys/file.h> XX#include <sys/dir.h> XX#include <sys/stat.h> XX#include <errno.h> XX XX/************************************************************************* XX** This procedure buffers up a named file, and returns a pointer to the XX** buffer. If something goes wrong, it returns NULL, and errno will have XX** been set. XX*/ XX XXchar* XXbuffered_file(file_name) XX char* file_name; XX XX{ XX XX char* file_buffer; XX struct stat stat_buf; XX int fd = open(file_name, O_RDONLY, 0); XX XX if (fd < 0 || fstat( fd, &stat_buf) == -1) XX return 0; XX XX file_buffer = (char*)malloc(stat_buf.st_size + 1); XX XX if(file_buffer == 0) XX return 0; XX XX if( read( fd, file_buffer, stat_buf.st_size ) != stat_buf.st_size ) XX { XX int error = errno; XX close(fd); XX free(file_buffer); XX errno = error; XX return 0; XX } XX XX file_buffer[stat_buf.st_size] = '\0'; XX XX close(fd); XX XX return file_buffer; XX XX} /* end.. buffered_file */ XX/****************************************************************************/ XX XX XX @//E*O*F buffered_file.c// fi if /bin/test -f express.c then echo File \"express.c\" already exists. Not overwritten. else # # echo x - express.c sed 's/^XX//' > express.c <<'@//E*O*F express.c//' XX/* Express the string, substituting a quotation of the string XX** for the character 'Z'. Breaks the literal into lines of no XX** more than 60 chars. XX*/ XXexpress(str) XX char* str; XX{ XX char* ptr = str; XX char ch; XX int is_quoted = 0; XX XX while(ch = *ptr++) XX { XX XX if(ch == 'Z' && !is_quoted) XX { XX int count = 1; XX char* ptr = str; XX char ch; XX putchar('"'); XX while(ch = *ptr++) XX { XX switch(ch) XX { XX case '\n': printf("\\n"); count +=2; break; XX case '\t': printf("\\t"); count +=2; break; XX case '\\': printf("\\\\"); count +=2; break; XX case '"': printf("\\\""); count +=2; break; XX default: putchar(ch); count += 1; break; XX } XX if(count >= 59) XX { printf("\\\n"); XX count = 0; XX } XX } XX putchar('"'); XX } XX XX else putchar(ch); XX is_quoted = ( ch == '\''); XX } XX} @//E*O*F express.c// fi if /bin/test -f conprog.c then echo File \"conprog.c\" already exists. Not overwritten. else # # echo x - conprog.c sed 's/^XX//' > conprog.c <<'@//E*O*F conprog.c//' XX XXmain(argc, argv) XX char** argv; XX{ XX express(buffered_file(argv[1])); XX exit(0); XX} @//E*O*F conprog.c// fi if /bin/test -f soup.Z then echo File \"soup.Z\" already exists. Not overwritten. else # # echo x - soup.Z sed 's/^XX//' > soup.Z <<'@//E*O*F soup.Z//' XX/* This program prints its source. */ XX XXmain(argc, argv) XX char** argv; XX{ XX char * dna = XX XXZ; XX XX XX express(dna); XX exit(0); XX} XX XX#include "express.c" @//E*O*F soup.Z// fi echo finished # # END OF ARCHIVE