Solutions to the "self-replicating program" puzzle
- To: mathgroup at yoda.physics.unc.edu
- Subject: Solutions to the "self-replicating program" puzzle
- From: tgayley (Todd Gayley)
- Date: Fri, 15 Apr 1994 16:32:14 -0500
Mathgroupers, A while back I posed a problem: write the shortest "self-replicating" program, defined as a program whose execution results in the printing of the program's code. Here is a summary of my solutions and those that I received. I hope you find it interesting. Here is a statement of the problem: Write a piece of Mathematica code, the evaluation of which results in the exact text of the code being printed to the screen (e.g., using Print). The output must match the code exactly. It does not matter what the code returns. There were a few restrictions on allowable solutions, which I briefly summarize here. First, note that the code must _print_ itself, not _return_ itself, so that simply typing f and having Mathematica return f is not a solution. The behavior of the code cannot depend on some prior state that you have prepared. For example, you can't define f := Print["f"] and then execute the one-character program f. You can certainly set up definitions if you wish, but the definitions themselves must be part of the code that reproduces itself. It must be possible to type your code as the first input in a session. You cannot rely on any external files, and you cannot use any aspects of the "main loop", such as $Pre, $Post, In values, etc. I announced that I had a 41-character solution (and several longer ones), but that was incorrect--it is actually 40 chars. Five people responded with solutions, all of them near to, or better than, 40 chars. The best solution is 26 chars, contributed independently by Michael Trott and Roman Maeder. Solving the problem hinges on producing some form of self-reference in one's code. One way a function or symbol has of accessing its own definition is through DownValues (for functions) and OwnValues (for symbols). If you make an assignment c:=something, then the rule c:>something is stored in the list given by OwnValues[c]. So one method is to write a line that does two things: 1) creates a definition for c that prints its OwnValues, and 2) evaluates c. c := <<< code that prints OwnValues of c, followed by semicolon, c >>> ;c Here are two solutions in that vein: 107 chars (ignore line-wrapping) ------------ Literal[c] := Print[Apply[HoldForm, OwnValues[c]] /. (x_ :> y_) :> (x := y), FromCharacterCode[{59, 99}]];c The above solution uses FromCharacterCode to produce the final ;c. It can be shortened a bit (in hindsight) by writing the ;c as a string and printing the InputForm of the expression. Without the InputForm, the string quotes are not displayed. We get: 102 chars ------------ Literal[c] := Print[Apply[HoldForm[InputForm[#1]] & , OwnValues[c]] /. (x_ :> y_) :> (x := y), ";c"];c Another set of methods uses Information, Definition, or the '?' mechanism to access the definition. 45 chars ----------- Global`c c := (Information[c]; Print["c"]) c This is multi-line input that must be entered in a single cell and submitted for evaluation as one unit. Note that it uses Information to do the printing, which was allowed in the rules. 41 chars (submitted by Terry Robb <tdr at vaxc.cc.monash.edu.au> ) ----------- c := Print[HoldForm[Definition[c]; c]]; c 34 chars (I found this one after the original post) ----------- Global`c c := Print["?c\nc"] ?c c Here are two solutions using a completely different technique: 44 chars (submitted by Nivaldo Muniz <nmuniz at impa.br> ) ----------- Print[#,FullForm at #]&@"Print[#,FullForm at #]&@" which can be shortened by using CForm to: 38 chars (submitted by Tim Adam <adams at maths.mu.oz.au> ) ----------- Print[#,CForm at #]&@"Print[#,CForm at #]&@" The shortest solutions, though, use a different mechanism for self-reference. Everyone is familiar with using #1 and #2 to represent arguments in a pure function, but you can also use #0 to refer to the head of the expression, which is the pure function itself. This allows for some extremely compact self-referential code. The basic idea is that Print[#0]& is a function that prints itself. To get the function body to evaluate, though, you have to apply the function to something, which means that it needs to print itself and what it is being applied to. The solutions below differ in how they cause the function's arguments to be printed. 40 chars (my original best solution) ------------ Print[#0, FromCharacterCode[64], 1] & @1 A better way to do this is: 31 chars (submitted by Roman Maeder <maeder at wri.com> ) ------------ Print[InputForm[#0], "[]"] & [] You could also write: Print[InputForm[#0], "@1"] & @1 Finally, the winner is..... 26 chars (Michael Trott <mtrott at wri.com> and Roman Maeder <maeder at wri.com>) ------------- Print[ToString[#0][]] & [] The ToString wrapped around #0 prevents the endless recursion that would occur with just Print[#0[]] & []. Thanks to all who responded or thought about this problem. I have seen the solution to this problem in C, but I don't remember what it is. If someone out there knows it, I'd appreciate it if they would send it to me. --Todd ------------------------------------------------------------ Todd Gayley tgayley at wri.com Vertical Applications (217) 398-0700 x191 Wolfram Research, Inc. (217) 398-0747 (fax)