Python: Why should ‘from import *’ be prohibited?

I believe by “in the middle of your program” you are talking about an import inside a function definition:

def f():
    from module import *    # not allowed

This is not allowed because it would make optimizing the body of the function too hard. The Python implementation wants to know all of the names of function-local variables when it byte-compiles a function, so that it can optimize variable references into operations on the (CPython) virtual machine’s operand stack, or at least to local variable-slot operations rather than lookups in outer namespaces. If you could dump the entire contents of a module into a function’s local namespace, then the compiler would have to assume that any name in the function might possibly refer to a module global, because the list of names brought in by from module import * is only known at runtime.

Putting from module import * in between top-level declarations is poor style, but it’s allowed:

def f():
    ...

from module import *

def g():
    ...

EDIT April 2013: While looking into something else, I discovered that this restriction was introduced in Python 2.1, as a consequence of the “Nested Scopes” feature (PEP 227). Quoting from the link:

One side effect of the change is that the from module import * and exec statements have been made illegal inside a function scope under certain conditions. The Python reference manual has said all along that from module import * is only legal at the top level of a module, but the CPython interpreter has never enforced this before. As part of the implementation of nested scopes, the compiler which turns Python source into bytecodes has to generate different code to access variables in a containing scope. from module import * and exec make it impossible for the compiler to figure this out, because they add names to the local namespace that are unknowable at compile time. Therefore, if a function contains function definitions or lambda expressions with free variables, the compiler will flag this by raising a SyntaxError exception.

This clarifies the Python 3.x vs 2.x behavior discussed in the comments. It is always contrary to the language specification, but CPython 2.1 through 2.7 only issue an error for from module import * within a function if it might affect the compiler’s ability to know whether a variable binds locally or in a containing scope. In 3.x it has been promoted to an unconditional error.

SON OF EDIT: … and apparently flashk pointed this out years ago in another answer, quoting the same paragraph of “What’s New in Python 2.1” yet. Y’all go upvote that now.