asfman
android developer
posts - 90,  comments - 213,  trackbacks - 0
program which duplicates itself


    One day, several years ago, I came across an article in an old Byte on "self-reproducing programs".  I was a curious lad, and looked to see what the article was about.  It said, "Listing 1 is a C program which duplicates itself.  When the program is run it produces (on the standard output) a file containing an exact copy of its own source code".  I was hooked immediately--these guys must be geniuses!  I copied the article at once, and tried to figure it out, but I didn't know C at the time.  Soon after, I found another article, this one in Creative Computing.  It had listings in BASIC, and I was ecstatic.  I soon realized that anyone could write self-reproducing programs, and made a few in BASIC, Pascal, and Forth.
    Later that year I finally got a PC, and quickly forgot about the programs I had written on my old TI-994/A.  Then, last year, as I was skimming through the Jargon file, I saw an entry I had not noticed before:

:quine: /kwi:n/ /n./ [from the name of the logician Willard van Orman Quine, via Douglas Hofstadter] A program that generates a copy of its own source text as its complete output. Devising the shortest possible quine in some given programming language is a common hackish amusement. Here is one classic quine: 

     ((lambda (x)
       (list x (list (quote quote) x)))
      (quote
         (lambda (x)
           (list x (list (quote quote) x)))))
This one works in LISP or Scheme. It's relatively easy to write quines in other languages such as Postscript which readily handle programs as data; much harder (and thus more challenging!) in languages like C which do not. Here is a classic C quine for ASCII machines: 
     char*f="char*f=%c%s%c;main()
     {printf(f,34,f,34,10);}%c";
     main(){printf(f,34,f,34,10);}
For excruciatingly exact quinishness, remove the interior line breaks. Some infamous Obfuscated C Contest entries have been quines that reproduced in exotic ways.

    "Wow.  A 'common hackish amusement'.  I've seen the Beer List, and the Hello World page, there must be a Quine Page.  I'll have to look around, that should be pretty neat to see what must be hundreds of quines."
    I was half right.  There were hundreds of quines, just no quine page.  Admittedly, there were a few attempts, but none had more than ten or so.  I had found over fifty by the time I came across any of these pages.
    Here is (hopefully) the definitive page.  You can check out the plain quine section, the self-reproduction variations section, and bibliography.  If you've visited before, browse the what's new section. Take a look at the want list of languages I'm specifically looking for. Finally, you can browse a list of links.

What's New

6/21/99   New Languages: ABC, J, Haskell, Oberon.  I've created an other section for stuff that doesn't fit anywhere
               else.  This page now mirrored on grex.cyberspace.org --support Not-for-profit net access & free shells. Also got rid of those nasty gifs and replaced them with nice PNG's
3/28/99   New Languages: False, Javascript.  Lots of pascal entries for some reason...I'm now listed
               on Yahoo!
3/1/99     New Languages: RPL, ML, snack, inform.  A couple of new palindromes in C, and as
                 usual, several miscellaneous entries.  Linked to my (very small) polyglot page.
2/20/99   New Languages: APL, CAML, dBASE, lua, prolog, Smalltalk.  A bunch of new iterating
                quines.  Sorry it's taken so long to put up all the new code everyone has given me.
12/27/98 New languages: Forth, Rexx, Scheme, Logo, Modula-2, TSE.  New variation:
                object-printing programs.  Linked to IOCCC and GEB FAQ.  A ton of new code.
12/23/98 Added another Intercal program, and did some minor fixes.
12/22/98 Everything
 

Plain (single language) Quines

    I define a quine as a program which reproduces itself on an output device without inputting its source.  For programs of that nature, see the cheats section.
    Included in these pages are some minor variations (.sigs, backwards printing programs, palindromes) which may at some point be given their own categories.

 ABC
 Ada
 Algol
 APL
 Assembly
 Awk
 BASIC
 BeFunge
 BlooP
 BrainF***
 C
 C++
 Objective CAML
 dBASE
 Emacs Lisp
 False
 Forth
 Fortran
 Haskell
 HP 48 RPL
 Icon
 Inform
 Intercal
 Interpol
 J
 Java
 More Java
 Javascript
 LISP
 Logo
 Lpc
 Lua
 Miranda
 ML
 Modula-2
 MUMPS
 Oberon
 Pascal
 Perl
 More Perl
 Postscript
 POV-Ray
 Prolog
 Python
 Rexx
 Scheme
 SGML
 Smalltalk
 Snack
 SNOBOL 4
 Tcl
 TeX
 TSE
 Unix Shell
 Vi

Variations


 Multiple Languages(polyglots)
 Iterating Quines
 Quine Generating Programs
 Kimian Self Reproduction
 Object Printing Programs
 Other

Cheats (right now these are in the language entries.  They'll soon have their own category)
 
 

Bibliography

 

Want List

Anything you have...
    I am especially looking for the major classic (or infamous) languages: COBOL (I'll freely withhold the name of the programmer if they wish ;) ), Jovial, PL/I, SIMULA, Teco, etc.

    I should probably point you to my submissions page.  Also, if you wrote one of these programs and are angry that I 'stole' it see my copyright page.
 

Links

The Free Compilers list
indexes compilers, interpreters, and language-related tools available free and in source on the Internet. You can download or search it from here.

The Language List
is a historically-oriented list of over 2300 languages which also includes pointers to sources. You can download or search it from here.

You can also use anonymous FTP from rtfm.mit.edu in the `/usenet/comp.lang.misc' directory to obtain either of these lists.

The Jargon File
A collection of Internet slang, folklore, and history. One of the most fascinating documents I have ever seen.  Read it.  Buy the book too.

The Beer List
List of implementations of a program to print out the entire lyrics of "99 Bottles Of Beer On The Wall" in different programming languages.  I think of it and the Hello World page as a wish list.  Someday this collection will be that big!

The "Hello, World" Page
Like the above, but for "Hello, World".  Better organized too.

The Retrocomputing Museum
A great resource of old, legendary computing programs compiled by the editor of the Jargon File.  Everything from APL written by Ken Thompson to Wumpus.  I also stole part of his links section ;)

 The IOCCC Headquarters
Short for "International Obfuscated C Code Contest"  this is a wonderful rescource of really, really ugly code.  Several entries have been quines or variations thereof.

 alt.fan.hofstadter and GEB FAQ
Lots of neat stuff here.  Self-reference galore.

 The Search for Self-Documenting Code
A paper on how to write quines.  Well written.  I have another written by Terry Reedy I
need to put up sometime.

The Polyglot List
Compiled by yours truly, the several multiple language programs I have.

Yahoo! list of quine pages
Pretty self-explanitory

posted on 2006-04-06 13:58 汪杰 阅读(436) 评论(6)  编辑 收藏 引用

FeedBack:
# re: program which duplicates itself
2006-04-06 14:03 | 汪杰
<script>
a=new Array();a[0]='a=new Array();'; a[1]='['; a[2]=']'; a[3]='\''; a[4]='\\'; a[5]='='; a[6]='a'; a[7]=';'; a[8]='';
a[9]='for(i=0;i<10;i++)document.writeln((i==0?a[0]:a[8])+a[6]+a[1]+i+a[2]+a[5]+a[3]+((i==3||i==4)?a[4]:a[8])+a[i]+a[3]+a[7]+(i==9?a[9]:a[8]))';
for(i=0;i<10;i++)
document.writeln((i==0?a[0]:a[8])+a[6]+a[1]+i+a[2]+a[5]+a[3]+((i==3||i==4)?a[4]:a[8])+a[i]+a[3]+a[7]+(i==9?a[9]:a[8]))
</script>  回复  更多评论
  
# re: program which duplicates itself
2006-04-06 14:03 | 汪杰
<script>(function(){alert("<script>"+arguments.callee+"()<\/script>")})()</script>  回复  更多评论
  
# re: program which duplicates itself
2006-04-06 14:03 | 汪杰
<script>
function a() { document.write(a, "a()");}a()
</script>  回复  更多评论
  
# re: program which duplicates itself
2006-04-06 14:04 | 汪杰

呵呵，没听说过贝尔实验室有这样的题目，绝对是假的。
不过，这样的程序我倒是见过一些：

char*f="char*f=%c%s%c;main()
{printf(f,34,f,34,10);}%c";
main(){printf(f,34,f,34,10);}

另一个：

void a(char*b,int d,int e,int f){char*c=b;for(;*c;c++){if(!d&*c==68)putchar(
92),putchar('\n');if(!d&*c==92)putchar(92);if(*c==d)a(b,0,0,0);else putchar(
*c==e?34:*c==f?'\n':*c);}}main(){char p[]=/*
andelion '94 */
"void a(char*b,int d,int e,int f){char*c=b;for(;*c;c++){if(!d&*c==68)putchar(\
D92),putchar('\\n');if(!d&*c==92)putchar(92);if(*c==d)a(b,0,0,0);else putchar(\
D*c==e?34:*c==f?'\\n':*c);}}main(){char p[]=/* \
Dandelion '94 */\
DCAC;a(p,65,67,68);}";a(p,65,67,68);}

这个比较长：

#include "stdio.h"

char *stack[2000], buf[2000], chrtab[128][2], *defns[128];

char dna[ ]="stdio.h_X#include X\"__\n\
char 4_Cstack_Sbuf_Bchrtab[4]_Hdefns[4]_V5[4]_]5, 4_,4;_;*4_*2000_K128_L\n\

_/SK]*BK],LH2]LV*,,C;__5==4_%5=4_=dna_DD ]@\"=C;__54_.copy(4)_K\n\
_/strlen(4)_Astrcpy(54,)_E4++_^5+4_+200_X'4'_'5*^4=_Z5;/4._!for (7;6;5)4_F\n\
_/if (5) 4_G{/4/}/_}return(4);/_R(char`*)malloc(4)_M\\\\_$`\"'_Y\n\
_/5 || 4_| c*t^*c^*=Yc*%$'c*%|t$'ZG\\n.'c*%ttt\\n.\\.\"EA+=G;!}F_W\n\
_/cK*Cc*Ct*q*,CqtXcA+M==!tYZ!W!tYZ.t0Z!qR!}!__(4)_~\n\
_/construct(4)_Iarg_J4**_$int 4_Nswitch(5)4}_Odefault: 4_P5-4_-p1-~*_Q\n\
_/break_Ucase 5: 4;/U_:5<4_<5>4_>5 && 4_&4*8'<4*3'>&_?else 4_XqB=Jp=!_W\n\
_/Wtc*V=t*t^t?kpt*-3'+=~J<Jk=Gqqqk*EA+=!;}Gqt*ZX;.}F!q*0=.pJ=!pBA1+MZBE!;_W\n\
_/c*``'p*^ ^c.*H=:YQQK=:!`@'pDZ:!c?p*^c*H=U!;}GP!W.O_W\n\
_/n0=kS=,kp<nnk*^A+=4F_U Uqn1+M=!qn+k*EU!qR!_O\n\
_/cI*Cc*CJ$p$,k$,t*,q*,CnN!pS=c*c^W}F!O.}!__\n\
_/nH5]4=_Ostrncpy(654,,)_Eputs(4)_P923+_T4t.*T%_T\n\
_/xt=D=t*t^ Tqtx-1+M=qxtx-E!qx-t+~*0=! ^TqIPG!t*VqI=X!xt1+=!;}G}F_Q\n\
_/main()/t*x*,q*,CnN!n0=nL<n^0nO10O!nVnH=!;}F!Q.}__";


char *copy(c)
char *c;
{

char *t, *q;
q=t=(char*)malloc(200+strlen(c));
*t++='"';
for ( ;*c;*t++=*c++){
if ('"'==*c || '\\'==*c) *t++='\\';
if ('\n'==*c) t=t+strlen(strcpy(t, "\\n\\")); }
*t++='"';
*t++=0;
return(q);

}

char *construct(c)
char *c;
{

char **arg, **p, **k, *t, *q;
int n;
for (p=stack;*c;c++){
switch(*c){
case '`': *p++=chrtab[* ++c];
break;
case '"': *(p-1)=copy(*(p-1));
break;
case '@': *p++=dna;
break;
default: if (*c<'8' && *c>'3') {
*p++=chrtab[*c];
break;
}
q=buf;
arg=p;
for (t=defns[*c];*t;t++){
if (*t<'8' && *t>'3') {
if ((k=p-*t+'3')<arg) arg=k;
q=q+strlen(strcpy(q, *k));
}
else *q++=*t;
}
*q=0;
p=arg;
strcpy(*p++=(char*)malloc(strlen(buf)+1), buf); }

}
for (n=0, k=stack;k<p;n=n+strlen(*k++)) ; q=(char*)malloc(n+1);
for (n=0, k=stack;k<p;n=n+strlen(*k++))strcpy(q+n, *k); return(q);

}

main()
{

char *t, *x, *q;
int n;

for (n=0;n<128;n++){
chrtab[n][0]=n;
chrtab[n][1]=0;


defns[n]=chrtab[n];
}
for (x=t=dna;*t;t++){
if (* t==92+3) {
q=(char*)malloc(t-x+1);
strncpy(q, x, t-x);
*(q-x+t)=0;
if (* ++t==92+3) puts(construct(q));
else defns[*t]=construct(q);
x=t+1;
}

}

}
  回复  更多评论
  
# re: program which duplicates itself
2006-04-06 14:04 | 汪杰

char*f="char*f=%c%s%c;%cmain(){printf(f,34,f,34,10,10);}%c";
main(){printf(f,34,f,34,10,10);}
  回复  更多评论
  
# re: program which duplicates itself
2006-04-06 14:04 | 汪杰

这个是国际编程竞赛的， www.ioccc.org 上面很多。
这里有一个
#include<stdio.h>
main()
{
char *c="#include<stdio.h>%cmain()%c{%cchar *c=%c%s%c;%cprintf(c,10,10,10,34,c,34,10,10);%c}";
printf(c,10,10,10,34,c,34,10,10);
}
  回复  更多评论
  
只有注册用户登录后才能发表评论。

<2006年4月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(15)

随笔分类(1)

随笔档案(90)

文章分类(727)

文章档案(712)

相册

收藏夹

http://blog.csdn.net/prodigynonsense

友情链接

最新随笔

搜索

  •  

积分与排名

  • 积分 - 467490
  • 排名 - 6

最新随笔

最新评论

阅读排行榜

评论排行榜

Copyright ©2024 汪杰 Powered By博客园 模板提供：沪江博客