Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!dimacs.rutgers.edu!aramis.rutgers.edu!athos.rutgers.edu!nanotech From: josh@cs.rutgers.edu Newsgroups: sci.nanotech Subject: Self-Reproducing Program Contest Results Message-ID: Date: 3 Apr 91 23:42:09 GMT Sender: nanotech@athos.rutgers.edu Lines: 410 Approved: nanotech@aramis.rutgers.edu **************************************************************** THE BOOBY PRIZE is won by this program submitted by lanai!bcc@uunet.uu.net (Brian Cooper) and djn@craycos.com (Darragh Nagle) in Basic: 10 LIST **************************************************************** MOST POPULAR, this program or syntactic variants thereof (this seems to be a local optimum in C, and has probably been reinvented many times) submitted by: John Hagerman Tony Lezard cooper@adhara.crd.ge.com (Clark Cooper) pjs@euclid.jpl.nasa.gov (Peter Scott) Robert E. Webber quoting jaw@ames.UUCP (James A. Woods) char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);} The same idea done in FORTRAN by radford@ai.toronto.edu (Radford Neal) character a*55 dataa/55h(6x14hcharacter a*55/6x9hdataa/55h,a,1h//6x9hprint a,a)/ print a,a **************************************************************** MOTHT ELEGANT: From Olin.Shivers@cosmos.vlsi.cs.cmu.edu ((lambda (lambda) `(,lambda ',lambda)) '(lambda (lambda) `(,lambda ',lambda))) **************************************************************** LEAST EFFICIENT has to be among these in "sh" by ediger@rtgds1.den.mmc.com (Bruce Ediger) entry 1: very short version st='echo st=$sq${st}$sq;echo dq=$sq${dq}$sq;echo sq=$dq${sq}$dq;echo $st' dq='"' sq="'" echo st=$sq${st}$sq;echo dq=$sq${dq}$sq;echo sq=$dq${sq}$dq;echo $st entry 2: st='echo st=$sq${st}$sq > $1;echo dq=$sq${dq}$sq >> $1; echo sq=$dq${sq}$dq >> $1;echo $st >> $1; chmod +x $1' dq='"' sq="'" echo st=$sq${st}$sq > $1;echo dq=$sq${dq}$sq >> $1;\ echo sq=$dq${sq}$dq >> $1;echo $st >> $1; chmod +x $1 Number 2 doesn't even require you to redirect output. It's also interesting in that the 2nd generation is a mutant version of the first. The offspring of the second generation is identical to the 2nd generation. entry 3: st='echo st=$sq${st}$sq > $1.1;echo dq=$sq${dq}$sq >> $1.1; echo sq=$dq${sq}$dq >> $1.1;echo $st >> $1.1; chmod +x $1.1; echo st=$sq${st}$sq > $1.2;echo dq=$sq${dq}$sq >> $1.2; echo sq=$dq${sq}$dq >> $1.2;echo $st >> $1.2; chmod +x $1.2' dq='"' sq="'" echo st=$sq${st}$sq > $1.1;echo dq=$sq${dq}$sq >> $1.1; echo sq=$dq${sq}$dq >> $1.1;echo $st >> $1.1; chmod +x $1.1; echo st=$sq${st}$sq > $1.2;echo dq=$sq${dq}$sq >> $1.2; echo sq=$dq${sq}$dq >> $1.2;echo $st >> $1.2; chmod +x $1.2 Number 3 is roughly the same as no. 2. It does make two children per execution, though. entry 4: a='echo a=$c${a}$c > $$;echo b=$c${b}$c >> $$;echo c=$b${c}$b >> $$; echo $a >> $$; chmod +x $$; ./$$' b='"' c="'" echo a=$c${a}$c > $$;echo b=$c${b}$c >> $$; echo c=$b${c}$b >> $$;echo $a >> $$; chmod +x $$; ./$$ i can't advise running no. 4. I think it would fill your disk rather rapidly. entry 5: st='echo st=$sq${st}$sq > $0.1;echo dq=$sq${dq}$sq >> $0.1; echo sq=$dq${sq}$dq >> $0.1;echo $st >> $0.1; chmod +x $0.1; echo st=$sq${st}$sq > $0.2;echo dq=$sq${dq}$sq >> $0.2; echo sq=$dq${sq}$dq >> $0.2;echo $st >> $0.2; chmod +x $0.2' dq='"' sq="'" echo st=$sq${st}$sq > $0.1;echo dq=$sq${dq}$sq >> $0.1; echo sq=$dq${sq}$dq >> $0.1;echo $st >> $0.1; chmod +x $0.1; echo st=$sq${st}$sq > $0.2;echo dq=$sq${dq}$sq >> $0.2; echo sq=$dq${sq}$dq >> $0.2;echo $st >> $0.2; chmod +x $0.2 another variation on a theme: 2 offspring per generation, doesn't require a file name on the command line. **************************************************************** EARTHIEST (try reading it aloud): Dave English char x[]=" main() { int i; putchar(99); putchar(104); putchar(97); putchar(114); putchar(32); putchar(120); putchar(91); putchar(93); putchar(61); putchar(34); for(i=0; i sent in this program by Michael Mauldin: char *x="\";\nmain ()\n{ char *s;\n printf (\"char *x=\\\"\");\n for(s=x;*s;s++)\n { printf (*s=='\\\\'?\"\\\\\\\\\":*s=='\\\"'?\"\\\\\\\"\":*s=='\\n'?\"\\\\n\":\"%c\", *s); }\n printf (\"%s\", x);\n}\n"; main () { char *s; printf ("char *x=\""); for(s=x;*s;s++) { printf (*s=='\\'?"\\\\":*s=='\"'?"\\\"":*s=='\n'?"\\n":"%c", *s); } printf ("%s", x); } **************************************************************** THE WINNER because it was the only entry to address the question of using the syntactic structure of the language in the encoding of the program, is John Hagerman's own entry using C's preprocessor: #define p(s) printf("%s\n",s); #define q(v,s) printf("r(%s,%s)\n",#v,s); #define r(v,s) char*v=#s; #define m main(){p(x)p(y)p(z)p(n)q(x,x)q(y,y)q(z,z)q(n,n)p("m")} r(x,#define p(s) printf("%s\n",s);) r(y,#define q(v,s) printf("r(%s,%s)\n",#v,s);) r(z,#define r(v,s) char*v=#s;) r(n,#define m main(){p(x)p(y)p(z)p(n)q(x,x)q(y,y)q(z,z)q(n,n)p("m")}) m **************************************************************** Not rated as previously published; rar@ads.com (Bob Riemenschneider) sends: Here are some examples in Common Lisp and Scheme from a recent article by Peter Norvig in _Lisp Pointers_. Most are "classic", but he came up with a few interesting new ones too. % First, a classic that works in any Lisp ((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote)) x)))) % Or, more succinctly, in any Lisp with backquote ((lambda (x) (list `',x)) '(lambda (x) (list x `',x))) % This one relies on the dreaded two-namespace hack, and thus works % in Common Lisp but not in Scheme ((lambda (list) (list list `',list)) '(lambda (list) (list list `',list))) % This one works in any Scheme where the printed representation of a % function is its source code ((lambda (x) (list x x)) (lambda (x) (list x x))) % Here's the novel Common Lisp example #1=(setq *print-circle* '#1#) % Or, if you insist on a self-evaluating function, #1=((lambda () (setq *print-circle* '#1#))) % If *print-circle* is non-nil in the environment, the first can be % shortened to #1='#1# % and the second to #1=((lambda () '#1#)) % Typing to a CL read-eval-print loop, the following is self-reproducing % (the variable - is bound to the current input, and is the only atomic % expression guaranteed to be self-evaluating) - % Or, if you insist on something non-atomic, (identity -) **************************************************************** LAST and LEAST and LEAST LEAST These are my own entries, (not judged, but I will note, of the non-cheating programs, the shortest and the longest respectively): in "J": ".a=.'''".a=.'',q,q,~a#~1+a=q=.39{a.' in C (this one attempts to do coding that reflects C syntax): #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'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')