A classic programming challenge, in Python

It has become a tradition for computer scientists to create various self referential ‘strange loops’. Traditions such as writing a compiler in the language it compiles are actually quite useful – and also very interesting. This tradition also branched to another one (also mentioned in the linked article) of writing programs that output their own source (without disk access and other dirty tricks).

The challenge is obviously to write such a program in Python, in as few lines as possible. Here is my solution, which is at two lines. I urge you to try it for yourself before looking, it is a very educating challenge. I’ll be very much interested in seeing a one-liner for this problem, or a proof that such a one-liner does not exist.

If you are interested in the bigger challenge, of writing an interpreter for Python in Python itself, go check out PyPy first.

For those interested in other ‘strange loops’, find a copy of ‘Godel Escher Bach’. If you happen to live in Israel, and can come to Haifa, I might even lend you my copy (once I get it back :)

This entry was posted in Challenges, computer science, Programming Philosophy, Python and tagged , , . Bookmark the permalink.

6 Responses to A classic programming challenge, in Python

  1. Imri, I think you need to define one-liner more precisely.
    But anyway the solution will depend on the lanaguage.
    For C you I’m quite sure you can prove impossibility by case
    analysis of all I/O functions.

    But you can “cheat”, e.g. take Python++, where the string class has the
    following method:

    def foo(self):
    return self + ‘ % “‘ + self + “.foo()”

    >>> print ‘%s’ % “print ‘%s’”.foo()
    print ‘%s’ % “print ‘%s’”.foo()

  2. lorg says:

    I agree, the solution obviously depends on the language. I was really referring to regular Python, were a one-liner is just one line of python code – in this case probably a print statement.

    With cheating you can achieve the following (which I think were discussed in literature):
    1. The empty program, if legal in your language of choice, is a valid solution (if you consider it a one-liner and not a zero-liner), as it prints a copy of itself: nothing at all.
    2. You can write a new language in which the interpreter prints the source of the program before running it, or a compiler that adds a part that prints the source of the program when run. In both cases, any program may be easily considered self-printing. (The second case is very reminiscent of the article I linked to, “Reflections on Trusting Trust”).

  3. Erez says:

    Here is my one-liner:

    print [s % repr(s) for s in ['print [s %% repr(s) for s in [%s]][0]‘]][0]

    Though I think I once wrote a better one. I’ll try to dig it up.

  4. lorg says:

    A really good idea using list comprehension. Excellent!

  5. Matteo says:

    You mean quines?

    (couldn’t read the Bell Labs page, the server is down ATM…)

    Here’s a C one liner:

    int main() { char *s = “int main() { char *s = %c%s%c; printf(s, 34, s, 34); }”; printf(s, 34, s, 34); }

    (couldn’t try that, I’m on windows at the moment and it complains about missing definition for printf, I know gcc only spits a warning normally…)

    I found it at:

    http://en.wikipedia.org/wiki/Quine_%28computing%29

    See also:

    http://www.nyx.net/~gthompso/quine.htm

    Cheers,
    Matteo

  6. lorg says:

    I was talking about a one-liner in Python, but yes, I meant quines.
    The article was the well-known “Reflections on Trusting Trust” by Ken Thompson.