On the shortest Python program

[First published in GOTOXO as Python-XO: On the shortest Python program on December 19, 2007.]

As reported in Caduceus Redux, Robert Bolgar says, “Maybe I should gear up my brain to learn some Python, too. About time I woke up to the computing world.”

I write this note to Josh and Zander Bolgar to provide a suggestion on how to help Dad wake up to the world of computing. Other members of the XO Generation may find it a way to help start their parent’s education on programming as well.

One of the most common sources of error in writing in a program is the failure to properly deal with what are known as “edge cases.” For example, running a loop once too often, or failing to run it far enough.

A further example is whether the program properly deals with the “null,” or empty case.

Since Python is based on set theory, let’s see if the Python compiler handles the case of null input properly. Linux provides many useful features, among them a perpetual source of nothingness in the form of a special device known as “/dev/null”. It appears as a file, but whenever you try to read it you get only the end-of-file signal. There is no data in that file save its end.

The question then is what happens when you execute:

$ python </dev/null

Yes! Python passes this test. Nothing in, nothing out. There is no error message, indicating that the Python compiler correctly recognizes null input as a valid program.

This program is also optimal in that no shorter program can be written, nor can any program take less time to compile and execute. Moreover, it is easy to construct a mathematical proof that this is so. For example,

Theorem: The empty program is the shortest possible program.
Proof: Any program that is not empty has at least one character, and is thus longer than the empty program.

Theorem: No program can be compiled faster than the empty program.
Proof: To read any program that is not empty, you must read at least one character and detect the end of input. The empty program requires only detecting the end of input, and so takes less time to compile than any other program.

Theorem: No program can be executed faster than the empty program.
Proof: The empty program is valid, yet requires no instructions be executed. It has no first instruction, no last instruction; it is just nothing.

I have written before about the shortest and longest sentences in natural language, in which a letter consisting of a single character (“!”) communicated a meaningful message. But Python is even better in that you can write a correct program by writing a program with no characters at all!

Zander and Josh can thus start their dad on his programming career by just having him execute the empty Python program.

If is of course much more fun to write programs that are longer and do some useful work, as I will try to show in future posts in this series. But education in any subject, including programming, must begin with a first step, even if it is just to show that “nothing ventured can still some education gain.”