Title: How do you make quines and self-referential programs?A Basic StrategyA basic strategy for building a quine is to write a program in two phases as follows. In the first phase, you first specify a special character or phrase such as !#%&. Next, you create a string variable str storing the value !#%&. Then, you substitute str's string value for the first occurrence of !#%& in str's string value. Finally, you print the result. See the following pseudo code: 1) String str = !#%&; In the second phase, you take the code you wrote and substitute it for !#%&. See the result below: 1) String str = "String str = !#%&; Substitute str for the first occurrence of !#%& in str; print the result as output;"; The preceding pseudo code represents a valid quine. However, depending on the programming language, there are at least three issues that may come up. (1) How do you appropriately handle quotation marks for string assignment? A Simple QuineWe will discuss a simple quine that we made in HTML and JavaScript. View its code and run it here: A Simple Quine. We first resolve issue (3) by making functions for safely displaying special characters and appropriately displaying spacing in HTML. /* Safely replaces html special characters */ We resolve issues (1) and (2) by introducing encode and decode functions that safely convert special characters to and from strings of hexadecimal numbers. Actually, we only need to use the decode function. /* Decodes a hex string */ Next, we do the string assignment as in phase 1, make the substitution, and print the result. /* The hex encoding of the partial source code */ It's important to note that the replace function only replaces the first occurrence of !#%& with hex. Finally, to get the quine, we proceed to phase 2 where we encode the phase 1 source code in hex using a string to hex tool (such as String-Functions or OnlineHexTools) and update the string assignment: /* The hex encoding of the partial source code */ A Simpler QuineIf you found the previous Quine to be a little too complicated, then you might want to take a look at: A Simpler Quine. Implementing the Recursion TheoremWe can use the preceding two phase method to create a program that computes its own source code. But, can a program do anything more after it computes its own source code? To refresh your memory, our version of the recursion theorem says that given any computable function G(x,y) there exists a source code e computing a function E such that E(n) = G(e,n) for all inputs n. All we have to do to get the source code e is add code for computing the function G at the end of phase 1. Then, we proceed with phase 2 as normal. We made a simple example where G(x,y) prints y and then prints x. Take a look at our example and make sure to view the code for the following function. /* This program computes E such that E(str) = G(e,str) */ You could replace G(x,y)'s code with whatever you choose and then repeat phase 2. You could even make a program where you enter G's JavaScript code as input and it computes the corresponding self-referential program's code. We implemented such a program and you're welcome to test it here. Feel free to share any interesting self-referential programs that you've made. :) |