Following suggestion in the Developers Guide (http://docs.python.org/devguide/#index-5) and the rules proposed by Michael Foord (http://mail.python.org/pipermail/python-dev/2010-November/105476.html):
------------
> If a module or package defines __all__ that authoritatively defines the 
public interface. Modules with __all__ SHOULD still respect the naming 
conventions (leading underscore for private members) to avoid confusing 
users. Modules SHOULD NOT export private members in __all__.

> Names imported into a module a never considered part of its public API 
unless documented to be so or included in __all__.

> Methods / functions / classes and module attributes whose names begin 
with a leading underscore are private.

> If a class name begins with a leading underscore none of its members are 
public, whether or not they begin with a leading underscore.

> If a module name in a package begins with a leading underscore none of 
its members are public, whether or not they begin with a leading underscore.

> If a module or package doesn't define __all__ then all names that don't 
start with a leading underscore are public.

> All public members MUST be documented. Public functions, methods and 
classes SHOULD have docstrings. Private members may have docstrings.

> Where in the standard library this means that a module exports stuff 
that isn't helpful or shouldn't be part of the public API we need to 
migrate to private names and follow our deprecation process for the 
public names.
------------

The following deprecation method is adopted:

from warnings import warn as _warn

def no_underscore(<parameters>):
    _warn("The module.no_underscore() function is deprecated",
         DeprecationWarning, 2)
    return _no_underscore(<parameters>)

Note: this is a meta-issue. It should only depend on all individual issues fixing APIs. It's currently dependant only on resolved issue10371.

As I don't think it's reasonable to create an issue per stdlib module, I'm going to group a few modules in issue. However, when submitting patches, please create a patch per module to minimize disturbance. The files to check: Lib/module.py, Lib/test/test_module.py, Doc/library/module.rst

Depends on issue10895

I will be writing a proper task item for this (there's a reason it's a todo item =), but I will read this before writing it so feel free to leave any thoughts or ideas for the future task.

My take on this:
- adding underscores to locally-defined private functions is good. +1
- -0.5 on "from warnings import warn as _warn"; it's useless complication, users should be able to realize warn() is a public API of the warnings module, not whichever else module using it

Oh, by the way, it can be good to check that the APIs are not used too widely. Example for such a query:
http://www.google.com/codesearch?q=lang%3Apython%20do_longs&hl=fr
(in this case, it's clear that only copies of the stdlib reference that function)

So I just closed the dependency on this issue as I figured the potential code breakage wasn't worth this (plus the referenced TODO item from the devguide is gone and was never turned into a proper task).

Now the question becomes do the guidelines SilentGhost wrote out belong somewhere in the docs?

I wonder if the devguide would be a more suitable place for these guidelines. Here is the patch that adds them to stdblibchanges.rst

Much of this is already in PEP 8 and doesn't need repeating.  Also, the tone is somewhat judgmental, heavy handed, restrictive, and over-broad for my tastes.

The last part seems to imply that we're going to change existing code in a way that may break user code.  Our whole goal is to make migrating to Python 3 easier.  The next to last part may create a pressure to document and promise some things that may be implementation specific details.

I think we should let PEP 8 serve as the primary guideline.  For new code, try to be as clear as possible on public versus private.  For existing code, any changes should be considered on a case by case basis to strike the best balance between useful documentation versus over-specification versus breaking existing code by privatizing that which was unintentionally made public.  

Also, when it comes to documentation, there are many things which are public (such as pickling support, every magic method available, etc) which aren't discussed for every single class.  The reason for this is that it tends to fill the documentation with clutter, making it hard for the more useful information to stand out.