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)