Can Python be written in Python?

[Chermside, Michael]

> Can python be written in python? (a la scheme or lisp)
        [...]
> The psyco web page [...] said that theoretically, and
> counter-intuitivally, that this could lead to a speed up in the interpreter by
> several multiples. Is this true? If so its beautiful and fascinating!)

Yes, Python can be written in python. No one has done much on it,
but it's clearly theoretically possible.

However, my opinion is that this is NOT likely to speed up Python...
more likely to slow it down. Of course, I hesitate to contradict
Armin (primary author of psyco) on this, as he is clearly far more
expert than I. But I'll muddle through with my best understanding
and let those more knowledgeable write in to correct me.

Some languages are "faster" than others. This can mean a number of
different things. The most significant factor in speed of any
program is what algorithm you choose to use. Thus Tim Peter's 
tongue-in-cheek statement:

  Any Python program using a dict is 1000x faster than any C program.

So using a language which encourages better algorithms will tend
to yield faster programs.

However, mostly when people talk about languages being "faster",
they mean something completely different. If you look at something
like the Great Computer Language Shootout 
(http://www.bagley.org/~doug/shootout/) you'll see people comparing
the SAME algorithm written in different languages. (see
http://www.bagley.org/~doug/shootout/method.shtml#sameway in particular).

With this kind of comparison, it tends to come down to how similar
the language is to the underlying machine. I suppose that if you
compared an algorithm using dicts written in both Java and Python,
then Python's blazingly fast dicts might count for something. But
normally, you compare things that use no complex data structures
but just manipulate simple strings, ints, and so forth.

And *that* is where Psyco comes in. Psyco attempts to do something
marvelous -- it takes bits of Python code and replaces them with
machine code (which isn't all that different from replacing it with
C code, so we'll pretend it's the same thing). Now Guido and the 
rest of the gang write pretty good C code, so I'm quite confident
that Psyco can't generate code that does Python more efficiently
than the version that's been "hand-written" in C.

But Psyco doesn't have to generate C code that does "all of python".
It only has to generate C code that does YOUR PROGRAM. And it's
likely that (for example) your program loops through a large list
of integers, none of which are actually int subclasses with a custom
__add__ method. Python can't assume this... it has to check every
time. Psyco DOES assume this (and if it's wrong I believe it backs
up and fixes the problem).

So for any *particular* program, particularly ones that use simple
data types a lot and don't make much use of Python's dynamic
properties, Psyco may help a GREAT DEAL. But it's got a limitation --
it can only work its magic on code that's been written in Python.
Code which has been written in C has to be run as written. So if
only more of Python were written in Python (and less in C) then
Psyco could do a better job. And (for reasons I only vaguely grasp
and would have difficulty explaining here) it may do a BETTER job
on the SAME program if less of the language were implemented in C.

HOWEVER, there are some things I'm pretty confident it won't speed
up. It won't speed up the reading of a file using the idiom

    f = file("filename.txt")
    for line in f:
        process(line)

It won't speed up the internals of Dicts or lists, or carefully
coded things like list.sort().

Setting aside the question of Psyco, re-writing much of Python in 
Python will *definitely* slow Python down. The developers already
try to do this wherever they can (I don't think I'm going out on
a limb to state that EVERY SINGLE member of the core python
development team prefers writing in Python to writing in C --
that's why they work on it!). And there's little opportunity for
algorithm improvement (a la Tim Peter's comment), because where
Python has a facility (like dicts) they already use it (except in
a few cases where bootstrapping or module independence prevents
it).

But there *IS* some possibility that writing more of Python in
Python will make Psyco work better. And then the result might
be faster overall. Which is definitely (as you put it), "beautiful
and fascinating".

-- Michael Chermside