Level: Introductory David Mertz (mertz@gnosis.cx), President, Gnosis Software, Inc.
01 Oct 2000 What most programmers probably think of when they talk about "Python" is the specific implementation sometimes called "CPython" (because it is implemented in C). However, Python as a language specification has been implemented several times in parallel with the evolution of Guido van Rossum's reference implementation. This article consists of annotated interviews with the creators of two of the non-standard Pythons -- Stackless and Vyper. By my count, there are four implementations of Python that you
can download and run today, and one more implementation is being created. Each implementation has
interesting reasons for existing, which you can read about here in the words
of the implementation developers themselves. Recompiling a compiler or interpreter to a different platform produces an implementation that is only trivially different (there might be minor conditional
compilations and changes), but the most interesting implementations (to me) are those that transcend platform issues.
In fact, the Python implementations we'll look at in this article are mostly
multiplatform themselves. The idea of an implementation is
also different from that of a version. All the
implementations treated here are basically at the same language
version (1.5.2) in terms of the language features. Obviously
CPython 1.6/2.0/3000 already has a partially new underlying
implementation, but the other implementations can equally match
the features at these language levels. Which programming languages get re-implemented, how often, for what reason, and
by whom? It's hard to characterize this group of languages. Some popular languages in roughly the same niche as
Python -- such as Perl, REBOL, and PHP -- have only one
implementation (compiled to many platforms). TCL is mostly
similar to Perl/PHP, but there is a Java-platform version
called Jacl. At the other extreme, languages like C, Awk,
Cobol, REXX, and Java have each been implemented almost
countless times. But those re-implementations have tended to
come out of licensing and marketing concerns rather than
conceptual and abstract issues about implementations.
Languages of particular academic interest seem to get
re-implemented a lot (especially functional, logical, or
hyper-pure OOP languages like Smalltalk and Eiffel). Lisp has
dozens, if not hundreds, of implementations and descendants. Unlike the Python implementations we will look at, descendants
of Lisp tend to introduce a lot of novel language features
along with new implementations. For the most part, the Python
implementations implement the same Python language as the
main CPython version. And all the current versions are open
source cooperative efforts, where innovations have little
to do with market positioning, or even with the license battles
that sometimes divide open source projects. Furthermore, a different Python version is not really a fork in a
traditional sense, but is rather a focus on different concepts that manifests itself as a Python implementation. The two implementations not addressed in detail are JPython and Python.NET. JPython is a
compiler written in Java that compiles Python source code to
Java bytecodes. The Python application is ultimately run in a
JVM (with the user perhaps having no idea it was written in
Python source code rather than Java, nor needing to care).
Python.NET is an implementation yet to ship, but that will
be -- at least in structure -- similar to JPython. Python.NET will let Python participate in Microsoft's .NET project, which
basically amounts to a non-Java VM that can run programs
written in a variety of languages (such as the new C#, Visual
Basic, C++, and also Python). Stay tuned for what the
developers of those implementations have to say. Below, we hear from the developers of two
theoretically fascinating implementations: John Max Skaller on Vyper and Christian Tismer on Stackless Python. Vyper: An interview with creator John Max Skaller
Vyper is an implementation of the Python language written in
the functional language Ocaml (3.00). In contrast to other
Python implementations, Vyper provides a number of (optional)
language extensions: more powerful scoping rules and some
new functional features. Vyper is not being actively developed
anymore, but it might be enhanced later (see Resources for
obtaining Vyper, including its source code). I asked Vyper's
creator, John Max Skaller, about his motives in creating Vyper.
Skaller: There were two reasons for building Vyper: First, I like Python, especially the simplicity. But I
dislike the lack of scoping, and the need to resort to hacks
to do anything advanced. So I decided to fix these problems
by building a much more advanced programming language with
some of the concepts of functional programming languages
built in, while retaining compatibility with Python.
The second reason is performance. I have a major
Python program, namely interscript, a literate programming (LP)
tool, which not only suffers from the lack of good structure
in Python (as mentioned above), but also from performance
problems.
Mertz: It would be helpful for readers if you could say a word or two about what literate programming is, since that
was a motivation for creating Vyper.
Skaller: The idea is that you do not document programs (after the fact), but write documents that contain the programs. [It was] invented by Donald Knuth.
Interscript is typesetter and programming
language independent, and it can be extended in document by
arbitrary executable code, written in Python. That is, one
can generate both code and documentation arbitrarily,
although a large number of prebuilt constructions are made
available for "everyday" needs.
But LP will never be accepted as a mainstream
technology unless it is FAST. I put a lot of work into
making it fast, but in the end, Python isn't fast enough to
do what needs to be done: processing strings character by
character in an interpreted language just cannot be made
fast. So the idea was to build a Python compiler,
which could at least generate machine binaries that could
optimize this kind of code. This is one of the reasons for
some of the Vyper extensions, to make optimization possible. I never did write the compiler; the idea was to
write an interpreter that would load all the modules
of a program at compile time, and then freeze the resulting
dictionaries into executable binaries. Vyper today is the
interpreter, but I had a lot of fun extending the language,
and then I got a paying job writing a compiler and now have
no time to continue the work.
Mertz: A particularly novel feature of Vyper is its
implementation in Ocaml. A lot of readers probably assume a
compiler/interpreter would be implemented in C (to get close
to the metal); or maybe for a defined machine, a compiler
could be done in Python itself. Why use Ocaml?
Skaller: Ocaml generates machine code directly. It
performs quite well compared with C, faster for some kinds of
work. It also comes with a garbage collector. Ocaml is a
high-level language, unlike C, C++, Python, or most other
so-called "high-level" languages. Ocaml is a mixed functional/imperative language, like Python. Vyper emphasizes the functional aspects of
Python more strongly than Python does. It corrects glaring
design faults, particularly lack of lexical scoping.
In practice, there is strong theory behind
functional programming, whereas there is NO theory for
imperative programming. This means functional programming
languages are generally miles better than any imperative
ones, from the point of view of development, but often lack
the performance of systems closer to the imperative
architecture of the underlying hardware.
Interestingly, the next implementation, although coming from a different direction, in some ways supersedes Vyper:
Skaller: The other big killer of the project was Stackless Python. It does something the compiler I am currently working on does, and which Vyper probably could never do: make the implementation of "ultra-lightweight threads" (cooperative multitasking driven by an event dispatcher) possible. Vyper is implemented in Ocaml which uses the machine stack; this must be avoided, since stack switching (for handling many clients at once from a server) is extremely expensive.
Stackless Python: An interview with creator Christian Tismer
At first brush, Stackless Python might seem like a minor fork
to CPython. In terms of coding, Stackless makes just a few
changes to the actual Python C code (and redefines "truth").
The concept that Christian Tismer (the creator of Stackless
Python) introduces with Stackless is quite profound, however.
It is the concept of "continuations" (and a way to program them
in Python). To attempt to explain it in the simplest terms, a continuation is a
representation, at a particular point in a program, of
everything the program is capable of doing subsequently. A
continuation is a potential that depends on initial conditions.
Rather than loop in a traditional way, it is possible to invoke
the same continuation recursively with different initial
conditions. One broad claim I have read is that
continuations, in a theoretical sense, are more fundamental and
underlie every other control structure. Don't worry if these
ideas cause your brain to melt; that is a normal reaction.
Reading Tismer's background article in the Resources is a good
start for further understanding. Pursuing his references is a
good way to continue from there. But for now, let's talk with
Tismer at a more general level:
Mertz: Exactly what is Stackless Python? Is there something a beginner can get his or her mind around that explains what is different about Stackless?
Tismer: Stackless Python is a Python implementation that does not save state on the C stack. It does have stacks -- as many as you want -- but these are Python stacks. The C stack cannot be modified in a clean way from
a language like C, unless you do it in the expected order.
It imposes a big obligation on you: You will come back,
exactly here, exactly in the reverse way as you went off.
"Normal" programmers do not see this as a
restriction in the first place. They have
to learn to push their minds onto stacks from the outset.
There is nothing bad about stacks, and usually their imposed
execution order is the way to go, but that does not mean that
we have to wait for one such stack sequence to complete before we can run a different one. Programmers realize this when they have to do
non-blocking calls and callbacks. Suddenly the stack is in
the way, we must use threads, or explicitly store state in
objects, or build explicit, switchable stacks, and so on.
The aim of Stackless is to deliver the programmer from these
problems.
Mertz: The goal of Stackless is to be 100% binary
compatible with CPython. Is it?
Tismer: Stackless is 100% binary compatible at the moment.
That means: You install Python 1.5.2, you replace
Python15.dll with mine, and everything still works, including
every extension module. It is not a goal, it was a demand,
since I didn't want to take care about all the extensions.
Mertz: Stackless Python has been absolutely fascinating
to read about for me. Like most earthbound programmers, I
have trouble getting my mind wholly around it, but that is
part of what makes it so interesting.
Tismer: Well, I'm earthbound, too, and you might imagine
how difficult it was to implement such a thing, without any
idea what a continuation is and what it should look like in
Python. Getting myself into doing something that I wasn't
able to think was my big challenge. After it's done, it is
easy to think, also to redesign. But of those six months of
full-time work, I guess five were spent goggling into my
screen and banging my head onto the keyboard. Continuations are hard to sell. Coroutines and
generators, and especially microthreads are easier. All of
the above can be implemented without having explicit
continuations. But when you have continuations already, you
find that the step to these other structures is quite small,
and continuations are the way to go. So I'm going to change
my marketing strategy and not try any longer to sell the
continuations, but their outcome. Continuations will still
be there for those who can see the light.
Mertz: There is a joke about American engineers and French engineers. The American team brings a prototype to the
French team. The French team's response is: "Well, it works
fine in practice; but how will it hold up in theory?" I
think the joke is probably meant to poke fun at a "French"
style, but in my own mind I completely identify with the
"French" reaction. Bracketing any specific national
stereotypes in the joke, it is my identification in it that
draws me to Stackless. CPython works in practice, but
Stackless works in theory! (In other words, the abstract
purity of continuations is more interesting to me personally
than is the context switch speedups of microthreads, for
example).
Tismer: My feeling is a bit similar. After realizing that
CPython can be implemented without the C stack involved, I
was sure that it must be implemented this way; everything
else looks insane to me. CPython already pays for the
overhead of frame objects, but it throws all their freedom
away by tying them to the C stack. I felt I had to liberate
Python. :-) I started the project in May 1999. Sam Rushing
was playing with a hardware coroutine implementation, and a
discussion on Python-dev began. Such a stack copying hack
would never make it into Python, that was clear. But a
portable, clean implementation of coroutines would, possibly.
Unfortunately, this is impossible. Steve Majewski gave up
five years ago, after he realized that he could not solve
this problem without completely rewriting Python.
That was the challenge. I had to find out.
Either it is possible, and I would implement it; or it is
not, and I would prove the impossibility. Not much later,
after first thoughts and attempts, Sam told me about call/cc
and how powerful it was. At this time, I had no idea in what
way they could be more powerful than coroutines, but I
believed him and implemented them; after six or seven times,
always a complete rewrite, I understood more.
Ultimately I wanted to create threads at blinding
speed, but my primary intent was to find out how far I can
reach at all.
Mertz: On the practical side, just what performance
improvements is Stackless likely to have? How great are
these improvements in the current implementation? How much
more is possible with tweaking? What specific sorts of
applications are most likely to benefit from Stackless?
Tismer: With the current implementation, there is no
large advantage for Stackless over the traditional calling
scheme. Normal Python starts a recursion to a new
interpreter. Stackless unwinds up to a dispatcher and starts
an interpreter from there. This is nearly the same. Real
improvements are there for implementations of coroutines and
threads. They need to be simulated by classes, or to be real
threads in Standard Python, while they can be implemented
much more directly with Stackless. Much more improvement of the core doesn't seem
possible without dramatic changes to the opcode set. But a
re-implementation, with more built-in support for continuations
et. al., can improve the speed of these quite a lot. Specific applications that might benefit greatly
are possibly Swarm simulations, or multiuser games with
very many actors performing tiny tasks. One example is the
EVE game (see Resources below), which is under development, using Stackless Python.
Mertz: What do you think about incorporating Stackless into the CPython trunk? Is Stackless just as good as an
available branch, or does something get better if it becomes
the core version?
Tismer: There are arguments for and against it. Against: As long as I'm sitting on the Stackless implementation, it is
mine, and I do not need to discuss the hows and whys. But at
the same time, I'm struggling (and don't manage) to keep up
with CVS. Better to have other people doing this. Other Python users, who aren't necessarily
interested in kinky stuff, won't
recognize Stackless at all; just the fact that it happens to
be faster, and that the maximum recursion level now is an
option and not a hardware limit. And there is another
promise for every user: There will be pickleable execution
states. That means you can save your program while it is
running, send it to a friend, and continue running it. Finally, I'm all for it, provided that all my
stuff makes it into the core; at the same time, I do not
want to see a half-baked solution, as has been proposed
several times.
Mertz: Any thoughts on future directions for Stackless? Anything new and different expected down the pipeline?
Stackless still suffers from some recursions. Will they
vanish?
Tismer: Pickling support will be partially implemented. This will be working first for microthreads since they
provide the cleanest abstraction at the moment. They are
living in a "clean room" where the remaining recursion
problem doesn't exist. My final goal is to remove all interpreter recursion from Python. Some parts of Stackless still have recursions, especially all the predefined
__xxx__
methods of objects. This is very hard to finalize since we need to change quite a few things, add new opcodes, unroll
certain internal calling sequences, and so on.
Resources
About the author  | 
| | Since conceptions without intuitions are empty, and intuitions
without conceptions, blind, David Mertz wants a cast sculpture
of Milton for his office. Start planning for his birthday.
David may be reached at mertz@gnosis.cx; his life pored over at
http://gnosis.cx/dW/. Suggestions and recommendations on
this, past, or future, columns are welcomed. |
Rate this page
| 
