sexta-feira, 14 de outubro de 2005

Quine: Self-reproducing programs

Last week, I saw something that is, at least, an excentricity. There is some of Logic and Computer Theory inside of such things, but not necessarily you must to read a lot of Mathematics theory books to understand it. And that is the funniest thing in see this examples!
Tell me, what the program below, written in C language, is wanting to do? It seems, at first, not so difficult...

char a[] = "int main(){ printf(b,34,a,34,10,34,b,34,10,10,a,10); }";
char b[] = "char a[] = %c%s%c;%cchar b[] = %c%s%c;%c%c%s%c";

int main(){ printf(b,34,a,34,10,34,b,34,10,10,a,10); }
We can see two variable declarations. Next thing we observe is that these variables are characters arrays. And the content of the first variable (named "a"), seems to follow a familiar syntax, which computer hackers frequently uses for writing computer programs. So, the application above is doing only one thing: it is writing itself! It is interesting to pay attention to how these great programmers deals with the high an lows of the languages... (such as, variable scope, the time between the instant the variables starts living, and the moment the variable would not be referenced anymore). Maybe another example, only to show how it works... (coded using the Python language)

a = ['print "a =", a', 'for s in a: print s']
print "a =", a
for s in a: print s
(Author: Omar Antolin - omar@galois.fciencias.unam.mx)
Or another great quine example in C language (it is not only a self-printing, it is a palindrome too!):

/**/char q='"',*a="*//**/char q='%c',*a=%c%s%c*/};)b(stup;]d[b=]d-852
[b)--d(elihw;)q,a,q,q,2+a,b(ftnirps{)(niam;031=d tni;]952[b,",b[259];
int d=130;main(){sprintf(b,a+2,q,q,a,q);while(d--)b[258-d]=b[d];puts(
b);}/*c%s%c%=a*,'c%'=q rahc/**//*"=a*,'"'=q rahc/**/
Author: Dan Hoey

Maybe you think that it is not a great problem. But, can you make a program that can write its own contents? We may consider a major difficulty: you will write a program, and you will try to not do it so difficulty, because you want to print all source code on the screen - as much code you write, much more work you will have to print the contents. Remembering that you must to write everything, including all commands and instruction used to print and to present results on the screen! :)
Self-reproducing programs are not a so recent idea, and a very famous phylosopher and logician, called Willard van Orman Quine (1908-2000). He made many contributions to the phylosophy of language and phylosophy of Logic. He made a lot of works, such an improved normalization methodology enabling better optimization of SQL queries, for example. And was he that give his name to the concept of a program that can reproduce itself, or its own source code...
You can see a lot of references (and source codes) in this site, illustrating "quine": http://www.nyx.net/~gthompso/quine.htm