I'm wondering which modules in the stdlib lack pure Python implementations (and could legitimately have one, e.g. sqlite can't really have a pure Python implementation). Once we know how big/small the list is a decision could be made as to whether to take on the effort to bring over some pure Python version from another VM or something for any of these modules.

To start the list:

csv
itertools

array
audioop
binascii
random
re
struct
xml.parsers.expat
cjkcodecs

zlib, bz2, lzma and crypts also can be implemented in pure Python.

hashlib backends (md5, sha1, sha256 / 384 / 512) either through openssl wrappers or implementations based on libtomcrypt.

Would it make sense for this list to be somehow reflected in or be reconstructible from the documentation?

So expat doesn't count as that literally wraps the expat library. Random also requires accessing the system randomization libraries to work properly so I don't think that is a candidate either. As for the compression libraries, those could be re-implemented, but I view those as wrappers around the libraries (same as the crypto stuff). I mean it doesn't have to be that way, but I'm trying to keep this framed in a tractable problem to start.

So to summarize the non-contentious modules (including adding functools) in alphabetical order, that puts us at:

array
audioop
binascii
cjkcodecs
csv
functools
itertools
re
struct

I would be curious to see what frequency these modules are used to know what might be higher priority so that the least used modules could eventually be marked as CPython-specific.

And to answer Chris' question, there is no need to be able to generate this from the docs until there is some PEP listing what modules must be implemented by a VM in order to considers its stdlib complete.

And thanks for the help so far, everyone!

PyPy has a pure Python implementation of sqlite (using ctypes):
https://bitbucket.org/pypy/pypy/src/default/lib_pypy/_sqlite3.py

It most probably works on CPython as well.
Does it belong to this list?

All cryptographic hash function are available as pure Python implementations. Although the Python based variants are super slow (except maybe on PyPy), they still serve as an academic show case.

IIRC PyPy has pure Python implementations of MD5, SHA-1 and SHA-2 family.

No, sqlite does not belong on this list as it wraps a C library. Plus there is an explicit block for ctypes-based modules in the stdlib which would prevent moving over the PyPy implementation.

And I'm sure pure Python versions of all the crypto libraries are out there, but I would be worried about them being implemented wrong, too slow to care, etc. Plus short of PyPy all of the other VMs have access to those crypto libraries in their own standard library so there is no need to provide it in Python's in pure Python.

Agreed with Brett.

zipimport

winreg does not have a pure equivalent, nor could it

So expat doesn't count as that literally wraps the expat library.

XML parser can be implemented in pure Python. There are a lot of XML parsers
implemented in different programming languages.

Random
also requires accessing the system randomization libraries to work
properly so I don't think that is a candidate either.

No, random have C implemented some basic methods only for speed. It uses
time() system function for initial seeding, but time() is accessible from pure
Python too.

Some OS-specific modules (pwd, grp, spwd, resource, ossaudiodev, etc) can be
implemented in pure Python on some platforms (using I/O and ioctl on special
files in /etc, /dev or /proc).

Sure, a general XML parsing library could be written in Python, but they wouldn't be named expat. =) The expat module wraps a specific XML parser (expat) so I still do not consider it applicable for this list.

As for random, you are right that it doesn't use platform-specific random code.

A lot of builtins :)

What's the purpose of these alternate implementations? For education, experiments? As a replacement for other VMs?

Other modules that could be considered:
marshal
operator
unicodedata

Alex: yes, the builtins could almost all be re-implemented in pure Python, but there is a performance consideration vs. benefit (e.g. if we re-implemented map() in Python which VMs would use it vs. implement it in some native way for performance?).

But one place I think there could be a benefit w/o performance issues is the built-in exceptions as you should be able to store references to the classes to help minimize the added cost of startup creating the exceptions from Python code.

Amaury: other VMs and easier extensibility in the future. We might as well all share the burden of maintaining pure Python versions instead of re-implementing the same thing over and over in little VM silos. And if some new thing needs to be added for a module it's easier to do it in Python than C (which then also continues to benefit other VMs).

Should itertools be in the list, as its stated purpose is to provide highly efficient functions?

Eric, I know you didn't just mean to suggest Python != efficient. =)

Yes, it should be in the list because other VMs might not want to re-implement that code in some native language to the VM. And I assume all code in the stdlib tries to be efficient, so that label holds no sway with me.

itertools should be fairly easy as the docs already contain Python equivalents (or near equivalents).

PyPy had a pure python itertools until recently (it's been deleted):

https://bitbucket.org/pypy/pypy/src/c1aa74c06e86/lib_pypy/itertools.py?at=py3k

Oops, sorry I slipped :)

I noticed functools in the list. bpo-14373 was opened somewhat recently to reimplement functools.lru_cache in C. This issue seems to be promoting have more things implemented in pure Python. Someone involved in this issue might want to weigh in on bpo-14373 if that is the case.

The guidelines for this are in PEP-399. Basically, adding 'accelerated' implementations when necessary isn't a bad thing as long as there are pure Python equivalents (unless it's a special case) and both are tested.

bpo-14373's latest patch seems to be following the PEP

I'm involved in both issues and I think it's good to have so much simple Python implementations as possible and to have C accelerators for any performance critical code.

One thing I should say about this list of modules is please don't go nuts porting every single module blindly. There is always a possibility that another VM has already ported the code and has simply not contributed it back and so there is no need to write it from scratch and more just political wrangling to get contributions pushed upstream from other VMs. There might also be reasons to not worry about porting something. Always start a conversation first before starting a port; last thing I want is someone putting in the time to port some code that no one will necessarily use for a while.

There is one additional benefit. I have already implemented audioop module in Python, and due to this it has found many bugs in the current C implementation (bpo-16686).

Also missing a pure-Python implementation:

collections.defaultdict (relatively trivial)
collections.deque

In the spirit of what Brett said, I found that PyPy has an implementation already:

https://bitbucket.org/pypy/pypy/src/default/lib_pypy/_collections.py

Jython and IronPython do not have pure Python implentations:
http://hg.python.org/jython/file/default/src/org/python/modules/_collections
http://ironpython.codeplex.com/SourceControl/changeset/view/99885#1091023

I don't think itertools or collections.deque should go on this list. The other implementations already have these and a pure python versions miss the point of these being high performance tools. AFAICT, there is zero benefit to adding a bunch of extra code that will never get used. It will only complicate my maintenance of those modules.