Shed Skin - A (restricted) Python-to-C++ Compiler

Shed Skin 0.9.1

2012-01-18T10:37:00.001-08:00

I have just released version 0.9.1 of Shed Skin, a restricted-Python (2.4-2.6) to C++ compiler. This is a maintenance release, so no new major features were added. Most interesting perhaps are optimizations for itertools.product and str.join. Other than that, it's mostly bugfixes and a new (hq2x image scaling) example. Please see the release notes for more details.

In the meantime, Paul Boddie has succeeded in getting Shed Skin 0.9 accepted into the Debian repositories, which is awesome for me personally.

Shed Skin 0.9

2011-09-10T03:50:00.000-07:00

I have just released version 0.9 of Shed Skin, a restricted-Python to C++ compiler. Looking at the state of things, a 1.0 version is probably not far off. There will probably be several 0.9.x releases first, though.

There were two issues blocking a 1.0 release in my mind, both of which seem to have been fixed with this release.

First, I was not completely happy yet with the type inference scalability. With 0.9, there has been another dramatic improvement in this regard. For example, the C64 emulator is analyzed 10 times faster now (about 3,000 lines in 2 minutes on my PC). But most other example programs are now analyzed much faster. It now seems a realistic option to compile a 10,000 line program.

Second, there were some long standing nasty issues with combining 'incompatible' types (such as for '[[1.0]] == [[1]]', we are comparing different types). Shed Skin 0.9 includes a new framework for dealing with these issues, and the problem seems mostly solved at this point.

There were also some very nice performance optimizations for this release. Francois Boutines greatly optimized file I/O. Complex numbers are now copy-by-value, hence massively faster. And the idiomatic construct 'for .., .. in somedict.iteritems()' should be a lot faster as well now. Thanks to Andreas van Cranenburgh for triggering the latter (as well as some of the type inference improvements) with a nice new example program, a natural language parser.

Shed Skin 0.9 also supports three new modules. Francois Boutines added support for the 'mmap' module. Fahrzin Hemmati added support for 'binascii'. And Tony Veijalainen added support for 'colorsys'.

Further, there has been a massive amount of fixes. Thanks to Jason Ye for triggering several of these. Brent Pedersen fixed some 'set' issues. Francois Boutines fixed a string comparison bug involving \0, and improved 'universal mode' for files. Joris van Zwieten sent in the magic code to only print tracebacks (shedskin -x) for uncaught exceptions.

As usual, more details can be found in the release notes.

In the meantime, Paul Boddie has been at work trying to get Shed Skin 0.9 accepted as an official Debian package. It is already included with Fedora (thanks to Thomas Spura) and some other distributions, but I'm a Debian/Ubuntu user myself, so I would be really pleased to see this happen.

Shed Skin 0.8, Programming Language Benchmark

2011-06-19T04:17:00.001-07:00

I'm happy to announce the release of Shed Skin 0.8, a (restricted-)Python-to-C++ compiler. It must be one of the best releases so far, with help and feedback from many directions. I'm especially thrilled to see an updated version of the C64 emulator example run one of my all-time favorite games.. :-) The emulator is now well over 3,000 lines (sloccount), and still compiling fine every time. The analysis time is in line with the scalability graph I published earlier. The game goes from a few FPS using CPython to a fluent 50 FPS after compilation on my PC.

The emulator triggered me to finally add support for the 'struct' and 'array' modules to Shed Skin. The struct module is now used to load programs from tape, and the array module is used to maintain a packed version of the screen data.

Another interesting new feature, also triggered by the emulator, allows generated code to print tracebacks for every raised exception (shedskin -x). So it's not entirely the same as in CPython (yet), which only does this for uncaught exceptions, but it's a step in the right direction. Unfortunately, I discovered at the last moment this doesn't work in the windows version. Hopefully this can be fixed for 0.9.

More details about the release can be found in the release notes.

Before I could make this announcement, there was a small performance comparison published, comparing different languages and implementations (such as PyPy, Jython and Shed Skin 0.8) for 4 different benchmarks. Unfortunately, Shed Skin 0.8 fails on one, but the problem is already fixed in GIT (regular expression search on empty string). The performance on the dict test can probably be attributed to the currently still slow I/O in Shed Skin. Improving this will be one of the goals for 0.9. Hopefully by the time you read this the comparison will have been updated at least for the failing test.

update: The file I/O bottleneck was fixed (thanks francois), and the performance comparison has been updated. Note that the first two benchmarks can still run a lot faster when disabling index-out-of-bounds checking (shedskin -b). On my PC, they become 30% and 45% faster, respectively..

update 2: the glitches are now also gone from the C64 example in GIT.

Shed Skin 0.7.1, Help needed!

2011-02-20T04:52:00.001-08:00

I have just uploaded the tarball for Shed Skin 0.7.1, which fixes several important problems in 0.7, and adds a few minor features. The Windows version and hopefully the Debian/Fedora packages will follow shortly. As usual, please see the release notes for an overview of all the changes.

There aren't any major new features, because I haven't received much feedback since 0.7. Please let me know if you run into any problem, so it can be fixed, or if you know of some interesting program I could play with! I'd also like to take this opportunity to ask for some help in specific areas.

Excitingly, Thomas Spura was able to get Shed Skin 0.7 accepted in the Fedora repositories! :D Thanks to Thomas for that! Inspired by this, I'd like to hear from anyone who might be interested in assisting/motivating Paul Boddie to get his Debian package accepted in the Debian/Ubuntu repositories. I think if it got past the scrutiny of the Fedora people, this shouldn't be too hard.. :-)

I would also really appreciate to see some description of Shed Skin on Wikipedia (again), because I think it deserves this, especially since the scalability improvements in 0.6. But also of course because it sends lots of users to the homepage. If you'd like to work on this, please see this thread with links to independent blog entries and even a book that describe or benchmark Shed Skin. For a summary of how the type inference part works, please see my recent 0.7 announcement.

Since a while, inspired by the LibreOffice project, there has also been a page in the Shed Skin wiki that lists some easy tasks that one could try and tackle, to hopefully make it easier to start contributing to Shed Skin. I try hard not to fix these problems myself, in the hope someone else will pick them up.

update: I just added another great new example to the 0.7.1 tarball, a quantum monte carlo simulator by Mark Dewing. shedskin takes about 10 minutes on my PC to analyze its 1,200 lines of code (sloccount).

Shed Skin 0.7, Type Inference Scalability

2010-12-16T04:17:00.000-08:00

I have just released version 0.7 of Shed Skin, a (restricted) Python-to-C++ compiler. The new version comes with lots of minor fixes and some optimizations, as well as a new Windows package. The Windows package was upgraded to a recent version of MinGW, which means it now includes GCC 4.5. I hope to package each new release for Windows again from now on.

There are also two nice new examples, one of which is over 1,000 lines (sloccount), for a total of 52 examples. Both are ray tracers, and it's always nice to look at the output of ray tracers. The larger one has a GUI and uses the multiprocessing module in combination with a Shed Skin generated extension module to do its heavy lifting. The other one uses a very slow but more realistic ray tracing technique, for a very nice result. Thanks to Eric Uhrhane and Jonas Wagner for sharing their programs!

I'd like to take the opportunity to talk a bit about type inference scalability. This graph shows the time Shed Skin needs for each of the current examples (seconds versus sloccount; the point on the right is the C64 emulator). I have to mention that two examples are left out here, because of a non-termination issue - that is, Shed Skin aborts after a certain amount of iterations. The reason I haven't looked into fixing this issue yet is that they do compile and run fine after Shed Skin aborts, because the type analysis is already precise enough at this point (though it takes some time). Precisely because of that, I don't think this issue would be hard to fix.

So while the current type analysis is obviously not perfect, I think this graph shows that type inference may not be all that hard as some people would have thought, at least for statically restricted code (the restriction does make it easier!). And I'm sure a team of programmers or someone smarter than me could do a much better job.

For those with some knowledge of the type inference literature, I'd like to explain at this point how Shed Skin achieves this scalability. Who knows this might be useful to people starting out in this area. It is actually quite simple conceptually (but don't think you can implement this correctly in a few weeks or even months for a large language such as Python!).

Shed Skin combines Ole Agesen's Cartesian Product Algorithm (CPA) with the data-polymorphic part of John Plevyak's Iterative Flow Analysis (IFA), both published in 1996 if I'm correct, and as suggested by Agesen. Because the CPA algorithm has a the tendency to explode for larger programs (usually in combination with the first, very imprecise iteration of IFA), Shed Skin 0.6 adds an incremental approach to the mix. It simply repeats its analysis for increasingly larger versions of a program, starting at nothing, essentially, and slowly adding to the callgraph until the whole program is analyzed. This seems to greatly avoid the CPA from exploding.

Shed Skin 0.6

2010-10-16T03:50:00.000-07:00

I have just released version 0.6 of Shedskin, an experimental (restricted-)Python-to-C++ compiler.

Most importantly, this release finally comes with a substantial scalability improvement. Instead of analyzing a whole program at once, Shedskin now repeatedly analyzes an ever increasing version of the program, starting at nothing, essentially, until the whole program is analyzed. It turns out it this is much easier than analyzing programs as a whole. The result is that Shedskin now easily scales to several test programs of over 1,000 lines (sloccount), and needs much less memory to analyze them.

I'd really like to receive programs that Shedskin 0.6 is unabe to analyze within a reasonable amount of time, to get an idea of the actual extent of the improvement, and to be motivated to further improve things. It's hard to be motivated to improve things if all programs you know of work well!

Interestingly, because of the incremental analysis, it also became possible to add a progress bar to Shedskin. It will slow down as we go to 100 percent, and be somewhat inaccurate if parts of a program turn out to be unused, but I for one couldn't be happier with it.

Another area that has seen substantial improvements is the support for generating extension modules. For example, basic (un)pickling of compiled classes should now work, and inheritance and overloading should now be better exposed to the outside world.

The most important bugfix is probably to correct the module/linenumber information for warnings and errors. It turns out the '#{' feature messed up line numbers, and with code spanning several files, Shedskin would often display the wrong module as well. This should all be fixed now.

More details about the release can be found in the release notes.

I would like to thank the following people for contributing to this release: Hakan Ardo, Thomas Spura, Eric Uhrhane, Saravanan Shanmugham, HartsAntler and Douglas McNeil, as well as Plonjers, for sending in the nice test case that triggered the scalability improvement.

update: Just after the release, Danny Milosavljevic sent in a great 50th example program, a Commodore 64 emulator! The emulator itself is a work in progress, but it boots and you can start typing commands. After modifying it a bit so it compiles out-of-the-box with 0.6, I added it to the 0.6 example tarball.

Shed Skin 0.5

2010-08-08T01:44:00.000-07:00

I have just released Shed Skin 0.5, an optimizing (restricted) Python-to-C++ compiler. Looking back at the release notes, I'm happy to see contributions from more people than ever. I'd also like to thank David Ripton again, for sending me his Project Euler solutions (see my previous post), and Jason Ye, for sending in so many issues.

The new release supports 64-bit integers (shedskin -l), which was necessary to get many of the Project Euler solutions to work. I'm wondering if this perhaps should become the default, since by default we want to stay as close to Python as possible.. But I don't think it's really useful that often, and it will probably be slower in many cases, so we'll see.

In comparing the Project Euler solutions with Psyco, it became clear that Shed Skin did not perform very well for certain types of iteration. I found out that exceptions in C++ are extremely slow, greatly slowing down e.g. set iteration. The new release avoids throwing StopIteration most of the time, that is, inside the builtins.

After basing the set implementation on CPython before, FFAO saw my invitation to do the same for the dict implementation, and quickly implemented it. I think Shed Skin was able to beat Psyco on about 5 more euler solutions with this new implementation.

Random number generation (without using shedskin -r) should also be much faster now.

Andy Miller sent in patches to add basic support for MSVC (shedskin -v). Although of course there is still no recent Windows package for Shed Skin. If anyone would like to volunteer, it should be easy to base a 0.5 package on the 0.3 version for Windows, though it would be nice to use a more recent version of MinGW.

Douglas McNeil sent in patches to add support for __future__.print_function and generator methods (as opposed to non-method functions). Thomas Spura optimized printing somewhat, though there is still some room for optimization there. Finally, Michael Elkins sent in some improvements for the socket module (which he originally wrote).

More details about the new release can be found in the release notes.

Shedskin versus Psyco for 131 Project Euler Solutions

2010-05-02T01:55:00.000-07:00

(Shedskin is an experimental (restricted) Python-to-C++ compiler.)

After releasing 0.4 I received a link to a blog post comparing PyPy, Unladen Swallow and Psyco for a set of over 100 project euler solutions. Of course, I decided to ask the author for the source code of these solutions, to have a go with Shedskin. It turned out to be a great test set for spotting performance flaws, and it even convinced me to add 64-bit integer support (shedskin -l), though I'm still not sure how generally useful that is.

Out of 204 solutions in total, I was able to get 131 to compile and run correctly (using the new 64-bit support), at a total of about 5,000 lines (sloccount). In some cases, I had to work around a Shedskin limitation, such as that mixing None and integers or nested functions are not allowed, but these were all very simple changes. While in many cases, it would have been easy to optimize things for Shedskin, I didn't make a single change other than to get things to compile. The other 73 solutions either needed arbitrary-precision arithmetic or use some unsupported module (mostly 'gmpy', whatever that is).

After optimizing Shedskin here and there (though only in generally useful ways, nothing really specific to these tests), I compared the run-time of Shedskin with that of Psyco on these 131 solutions. The graph below shows the relative speedup of Shedskin versus Psyco, taking the shortest time of three runs for each. Shedskin is faster in 109 cases out of 131, and if we take the cumulative time (730 versus 1330 seconds), 45% faster in total. Many of the 22 cases where Psyco wins deal with dictionaries, and I think Shedskin could also win most of these with a better dict implementation (any volunteers?).

A reason why the results may be somewhat flattering for Shedskin, is that quite a few solutions run in only a fraction of a second, and Psyco may suffer from a longer startup time (though I wouldn't know). On the other hand, many of the solutions are quite memory-intensive and spend a lot of time in the python builtins, so Shedskin often doesn't get a chance to shine. I think with a few manual changes to the solutions, many would run much faster using both Psyco and Shedskin, but with a larger speedup for Shedskin.

Unfortunately, Project Euler being semi-competitive and all, I cannot share the solutions. But I will mail the timings for each solution to the discussion group. Anyway, here's the setup I used to calculate the graph:

- shedskin -l (SVN 2010-5-1)
- g++ 4.4.3 -O3 -fprofile-generate/use -march=native -mtune=native -fomit-frame-pointer
- q9550s CPU
- each solution is run three times with Psyco, then three times with Shedskin, with a time.sleep(2) after each run
- the fastest time for each is taken.

So again, if anyone would be interested in rewriting the dict implementation, based on the CPython code (instead of relaying to the STL), that would be great. FFAO did this before for the set implementation, and that helped a lot.

Shed Skin 0.4

2010-03-31T02:05:00.000-07:00

I have just released Shed Skin 0.4, an experimental (restricted-)Python-to-C++ compiler. Thanks again especially to Jeremie Roquet for helping out.

The biggest 'improvement' of this release is perhaps that Windows is no longer supported. Windows users are encouraged to take over maintainership of the MinGW version, or to upgrade to a 'real' operating system, such as Ubuntu, and live in software freedom.

Other improvements include support for generator expressions, real boolean support (instead of integers that print as 0 and 1), support for the 'key' argument of 'min' and 'max', another useful type inference scalability improvement, and support for heapq.{merge, nsmallest, nlargest}. Please see the release notes for the full list of changes.

Four new example programs were also added, for a total of 47 programs:

-pylife, a game of life implementation based on the wonderful hashlife algorithm (David Bau)
-a nice a-star implementation, with a pygame frontend (John Eriksson)
-a simple game of life implementation that gave the type analysis some trouble (Francesco Frassinelli)
-a second genetic algorithm (Stavros Korokithakis)

Please go ahead and try it out, and let me know about any problems. I'm also always very happy to receive new example/test programs to play with, especially if type inference fails (or doesn't terminate) for them!

Shed Skin 0.3

2010-01-13T03:01:00.001-08:00

After 5 years of work, I'm proud to announce Shed Skin 0.3, an experimental (but obviously restricted) Python-to-C++ compiler. Looking over the release notes, I'm convinced this must be the best release so far. I would like to thank especially Jeremie Roquet, for several major contributions to this release, and Thomas Spura, for reorganizing the codebase. Joris van Rantwijk provided the great new 'maximum weighted matching' example, and he and Mike Schrick sent in minor but useful patches.

For me, these are the highlights of the release:

- support for 'itertools', 'heapq' and 'csv', bringing the total set of (mostly) supported library modules to 20
- 4 new example/test programs, bringing the total to 44 examples, at over 10,000 lines in total (sloccount)
- improved type inference scalability (while greatly simplifying the code)
- support for 'map', 'filter' and 'reduce' (yes, finally, go wild.. :-))
- support for the 'with' statement
- support for the 'key' argument to 'sorted' (and 'list.sort')
- reduced the compiler core by about 100 lines (again)
- a distutils-based setup.py (talk about 'finally'!)
- several important optimizations (indexing, slicing, adding 1-length sequences)
- an unusually large number of bug fixes

Please go ahead and try it out, and start sending in those issues. I'm also always very happy to receive new example/test programs to play with, especially if type inference fails (or doesn't terminate) for them!

Shedskin: what next?

2009-11-08T09:40:00.001-08:00

(Shed Skin is an experimental (restricted) Python-to-C++ compiler.)

After playing with Disco for a while, and after that being away for over a month, I'm ready to put some time in Shed Skin again. I've just applied a few patches that I received (thanks!!), fixed some minor issues myself and added a few optimizations. But I'm not really sure which 'big' thing to work on next, and I don't really know of a nice program to test with at the moment (such as Minilight or Disco). I'd love to hear some suggestions!

update: I posted a feature plan for 0.2.1 on the mailing list. thanks for the feedback!

Disco: an elegant Python Go player (update)

2009-08-30T08:17:00.000-07:00

after receiving generous help from 'apt1002' in the datastructure department, I am happy to announce Disco 0.3 (see my previous posting about Disco).

the new version is about ten times faster than 0.2 (from around 600 games per second on my PC to about 6000). in addition it now checks for positional superko (repeated positions), so it can now play on CGOS without making illegal moves half of the games.

interestingly, using CPython there is not much difference in speed between 0.2 and 0.3, while the speedup from using Shedskin goes from about 6 to 75 times! this is probably mostly due to avoiding (re)allocations, which of course aren't much faster in C++ than in CPython.. but the new datastructures are also a bit smarter in maintaining only the most necessary information.

the sourcecode is still only about 400 lines, but now slightly less readable.. I hope to clean this up a bit over the next few months, but other than I will be too busy. in the long-term, it would be interesting to add shape analyses and additions to UCT such as RAVE/AMAF, and try to keep all of that in a pretty package of under 1,000 lines..

Shed Skin 0.2

2009-07-19T06:53:00.000-07:00

I have just released version 0.2 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. It comes with 7 new example programs (for a total of 40 example programs, at over 12,000 lines) and several important improvements/bug fixes. See here for the full changelog.

The new example programs consist of Disco, an elegant go player (see my previous blog post), a larger Voronoi implementation at 800 lines, a TSP algorithm simulating ant colonies, a nicer neural network algorithm and three compressors (Lempel-Ziv, huffman block, and arithmetic).

Other than bug fixes for these programs, this release adds some important optimizations. First and foremost, inlining was greatly improved, resulting in potential speedups across the board. Second, loops such as 'for a, b in enumerate/zip(sequence[, sequence])' should now be dramatically faster (also inside list comprehensions), by avoiding allocation of intermediate tuples. Finally, basic list slicing should now be much faster.

Disco: an elegant Python Go player

2009-07-09T06:21:00.000-07:00

There's this shiny new technique to implement computer Go players, called Monte Carlo UCT. It shocked the Go world by powering the first computer player (Mogo) to beat (quite unexpectedly I think) a professional player in an official match (with only a 7 stone handicap). Ever since hearing about this rather simple new technique, my hands have been itching to implement it in Python and compile the result with Shedskin.

The name of the resulting Go player is Disco (think "staying alive"), and its source code of only 350 lines can be found here. Given enough time, it can play some pretty interesting games on a 9x9 board. And of course you can connect it to a graphical Go board, although I only tested it with Gogui. See the README for installation and configuration details.

It has become quite a nice test case/example for Shedskin. Not only does it become about 5 times faster on my computer after compilation, and shows that you can write a pretty fast Go engine using it, it also shows how easy it is to generate an extension module with Shedskin and effectively use this in a larger program. In this case, there is a Parallel Python wrapper that fires up an abitrary number of processes, each importing and using the extension module to do part of the thinking.

Sometimes everything can come so beautifully together: an elegant Python program of only 350 lines, compiled to an extension module, imported in multiple Python processes, connected to a graphical Go board and playing according to some brilliant but simple new mathematical formula that can somehow make computers play Go! Now if only I would be better at Go myself, so I could really test it..

BTW, Shedskin 0.1.2 should be right around the corner. Obviously I got a bit distracted by the above.. In all, it contains many optimizations and bug fixes and adds 5 other new example programs.

Shed Skin 0.1.1

2009-04-22T06:56:00.000-07:00

I have just released version 0.1.1 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. It comes with 5 new example programs (for a total of 35 example programs, at over 10,000 lines) and several important improvements/bug fixes. See here for the full changelog.

The most interesting new example is minilight, an elegant raytracer (more precisely, a global illumination renderer) that utilizes triangle primitives and an octree spatial index. As shown on the minilight homepage, it becomes up to 100 times faster.

Other new examples are Peter Norvig's sudoku solver (which unfortunately doesn't become faster, but is a cool example anyway), yet another raytracer and a mastermind strategy evaluator by Raymond Hettinger.

The fifth new example, an interactive circle packing program, is especially nice, because it is, well, interactive, but also because it shows how easy it is to generate an extension module with Shed Skin and use this in a larger program (a Pygame application in this case).

The biggest improvement (if you can call it this) for this release was to drop support for generic types. This simply means that functions that can be called with different kinds of types of objects for a single argument are no longer supported (unless these types have a common base-class, of course). Similarly, generic datastructures are no longer supported. Dropping support for generic types made the compiler core a lot simpler (and 10% smaller!), and removed the need for the -i command-line option.

Seeing the compiler core shrink so much, I was inspired to further refactor several messy areas of the compiler for readability (most notably in infer.py). This means the compiler core has also become a lot more readable/hackable with this release. I hope to continue this work of refactoring (and adding docstrings) with each release from now on, and invite anyone to help out here.

In general, I would really like to receive more help. For example, if someone could take over maintainership of the Windows version (and possible upgrade the MingW distribution that is packaged with it), that would be great. A suggestion on the coding side might be to add keyword support to generated extension modules (see extmod.py), or to optimize some builtins (for example, string/list slicing, see lib/builtin.?pp). But I would also be happy to receive more interesting test cases (most come from a single person at the moment) and/or more bug reports (which I get far too few of.)

Minilight Compiled

2009-03-23T08:49:00.000-07:00

(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)

Minilight is an elegant minimal global illumination renderer, or raytracer, that uses triangle primitives and an octree spatial index. The original version consists of about 1,000 lines of C++, but there are several translations available at the homepage, such as ~500 line OCaml and Python versions. The Python version apparently clocks in 173 times later than the C++ version, while the OCaml version is only about 3 times slower.. Wouldn't it be interesting if we could make the Python version run faster than the OCaml version?

After some small changes (splitting up some dynamic variables, replacing calls to 'map', 'type'..), and applying some minor fixes to Shedskin, I was able to compile the Python version to C++ using Shedskin SVN. For the basic Cornell box example, it runs about 35 times faster than the modified Python version (which should again be a bit faster than the original Python version). It's probably still somewhat slower than the OCaml version, but not that much. To try to compile it yourself, you'll probably want to have more than 512 MB of RAM, and use the 'shedskin -i' option. The modified version can be found in /examples/minilight in SVN.

I'm guessing that the Python version can be made a bit faster in itself. What typically happens then is that the C++ version will get relatively even faster, because certain bottlenecks that don't really slow down Python will slow down C++ (such as allocating lots of objects). If you'd like to try and help beat OCaml, I'd be very interested in hearing about potential improvements (where readability doesn't suffer too much, obviously.)

Another program that I managed to compile, while much smaller, is one that solves a well-known chess puzzle. To compile knight2.py, I had to replace the 'key' argument to 'sorted' with a 'cmp' version (as 'key' is not yet supported), and fix a small bug in Shedskin ("'%*d' % (2, 7)" and such did not work yet.)

I'm always interested in hearing about other interesting test cases for Shedskin, as they seem hard to come by. Please also consider sending in bug reports. Both types of feedback are essential for me to keep working on Shedskin!

Update: After some tweaking, it is now more than 60 times faster than the original here. See the comments for more information.

Update 2: I removed the -i option with Shedskin 0.1.1, so it is not necessary anymore.

Shed Skin 0.1

2009-01-25T08:25:00.001-08:00

(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)

After several years of development and thirty releases, I have finally released Shed Skin 0.1. While still experimental, all the basic pieces are now in place:

-type inference that works for many smallish programs
-support for a useful subset of Python
-support for a good subset of the standard libraries (about 17 modules, such as random, re, os, os.path..)
-extension module generation (including extension classes)
-support for the most common platforms

For this release, I was able to add a Jpeg decoder, at 1,200 lines, an iPod Shuffle programmer, at 600 lines, and a mastermind program to the set of example programs. This brings the total number of example programs to 30, at about 9,000 lines in total.

For Shed Skin 0.2, I hope to be able to focus on improving type inference scalability. So far, I've spent surprisingly little time on type inference itself, because what I had worked well enough for most test cases. I have quite a few ideas to further improve scalability, and am sure some of these will help a lot.

This release would not have been possible without the generous help of Google (through their GSOC and GHOP programs) and the following people (please let me know if I missed someone):

-B********e
-Brian Blais
-Paul Boddie
-Djamel Cherif
-Mark Dewing
-James Coughlan
-Michael Elkins
-FFAO
-Luis M. Gonzales
-Karel Heyse
-Denis de Leeuw Duarte
-Van Lindberg
-David Marek
-Jeff Miller
-Joaquin Abian Monux
-Harri Pasanen
-SirNotAppearingInThisTutorial
-Dave Tweed
-Jaroslaw Tworek
-Pavel Vinogradov

Finally, I dedicate this release to Hai Fang Ni. Thanks for all your support, and a happy Chinese newyear!!

Some nice additions to /examples

2008-12-28T09:19:00.000-08:00

(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)

Because the set of example programs available at the Shed Skin homepage (ssprogs.tgz) hasn't changed in a while, I decided to add some nice programs to it. With some relatively simple (but as usual, important) fixes, I was able to add support for a Jpeg decompressor (!), at 1200 lines, an iPod shuffle programmer, at 600 lines, and a multi-module mastermind program, at 300 lines.

I will be adding these programs to ssprogs.tgz with 0.0.31 (or 0.1), but for now they can be found here. They should compile using Shed Skin SVN (see the note in the top of rdb.py; TonyJpegDecoder.py should be run with two arguments, e.g. "python TonyJpegDecoder.py tiger1.jpg tiger1.bmp").

Thanks to ********** for sending me the jpeg decompressor, and the authors of these programs for the nice test cases!

I would have probably added more programs (and fixed more things) if I could find more interesting test cases, but these seem hard to come by. If you happen to know of any nice programs between 500 and, say, 2,000 lines that might be statically compiled, possibly after some minor changes, please let me know. Some more bug reports would also be very welcome.

Shed Skin 0.0.30

2008-12-02T06:34:00.000-08:00

I have just released version 0.0.30 of Shed Skin, an experimental (restricted) Python-to-C++ compiler.

Most importantly, this release adds (efficient) support for user-defined classes in generated extension modules, which should make it much easier to integrate compiled code within larger projects. More specifically, compiled classes can now be instantiated on the CPython side, and instances can be passed freely between CPython and Shed Skin without any conversion taking place. (Instances of builtin classes are still (recursively) copied, though, at the moment..)

Another major improvement was contributed by FFAO: a new 'set' implementation, directly based on the CPython code. While I haven't tested it on many benchmarks, it is clear that is now much faster, and on one benchmark it even outperforms CPython on my system by about 35%.

Other notable changes include complex number support, mapping None to NULL instead of 0 and printing it as 'None', as well as an important type inference fix.

With support for user-defined classes in extension modules, it looks like all the major pieces are now there to do a 0.1 release. The only thing I'd really like to do before that, is to improve support for the 'os' module. Please let me know if you'd like to help out here! Hopefully, with many details out of the way, I can have another good look at type inference for 0.2..

Shed Skin in the News

2008-11-21T06:39:00.000-08:00

(Shed Skin is an experimental (restricted-)Python-to-C++ compiler).

Because a new version (0.0.30) is still some weeks away, I decided to post, in the meantime, some links to other people's blog entries about Shed Skin.

making-python-math-196-faster-with-shedskin
taking-on-shed-skin
more performance python
compiled kamaelia

Please let me know if I have missed an interesting entry.

And if you are really bored, here are also some links to (old) discussions on slashdot and osnews:

slashdot article
osnews article

Shed Skin 0.0.29

2008-09-20T04:06:00.000-07:00

I have just released version 0.0.29 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. It's been a while since the last release (well, just under 4 months), because of work and vacation, but mostly because there have been so many changes.

Thanks to the work of Karel Heyse, Pavel Vinogradov, FFAO and David Marek, there is now a pretty much complete implementation of the datetime module. Thanks to a suggestion by Albert Hofkamp, I added support for most of the ConfigParser module (by compiling it with Shed Skin of course), which led me to fix several outstanding but important problems. For example, support for inheritance hierarchies was greatly improved, and mapping keys should now work, too ('%(key)x..' % some_dict).

Since the previous release, I've also gone through the pains of installing FreeBSD, OpenSolaris and 64-bit Ubuntu on a spare PC and testing Shed Skin on each of them, with the result that these platforms are now 'officially' supported. Please see the updated 'installation' section of the tutorial. I also received some GCC 4.3 patches (Seo Sanghyeon and Winterknight), which should work fine now, too. So I guess most platforms should be covered now.

Some other improvements:

-improved support for importing from nested modules such as os.path
-__init__ methods are much less a special-case
-improved support for calling ancestor methods (e.g. Parent.__init__)
-all example programs (ss-progs) now compile as extension modules
-staticmethod and property decorator support (Seo Sanghyeon)
-Shed Skin doesn't crash on highly dynamic/recursive types anymore, making it easier to debug programs to get them to compile
-several fixes in the re module, e.g. re.sub now accepts a replacement function
-tuple hash caching was disabled, as CPython doesn't do this either

For the full changelog, see the release notes wiki at the Googlecode site. Please try out the new release, and let me know about any problems. Note that I probably won't be very responsive for at least a week or so - it has been a somewhat difficult release, and I could use some rest.. :)

Shed Skin 0.0.28

2008-06-03T11:33:00.000-07:00

I have just released Shed Skin 0.0.28, with the following changes. Thanks to those mentioned for helping out!

- basic 'socket' support (Michael Elkins)
- support for os.{popen3, popen4} under UNIX (Jaroslaw Tworek)
- support for time.strptime under Windows (David Marek)
- options for changing output dir, disabling annotation (Dave Tweed)
- support for 'cmp' and 'reverse' arguments of 'sorted' and 'list.sort'
- fixes for cross-module default arguments
- important fixes for type inference and inheritance
- restore compatibility with Python 2.3
- many minor bugfixes

I would really like to receive more bug reports. Please try out the new version, and let me know about any problems.

With the socket support, 15 common modules are now largely supported. For a 0.1 release, I'd really like to have support for one more module: datetime. Thanks to the GHOP, there is a type model already (lib/datetime.py), so we only still need a C++ implementation..

Shed Skin 0.0.27

2008-02-23T06:12:00.000-08:00

Thanks to the GHOP students, this new release contains support for 're' (via libpcre!), 'time' (except strptime under windows) and 'fnmatch' and 'glob', as well as much improved support for 'os' (POSIX), and also a typemodel for 'datetime'. This means Shed Skin now supports (most of) the following standard library modules:

bisect, collections, copy, fnmatch, getopt, glob, math, os, os.path, random, re, string, sys and time.

If anyone is interested in implementing/bootstrapping 'datetime', 'socket' or in improving 'os' support (esp. under Windows) or other modules, please let me know!

I got more help for this release. Brian Blais helped fix OSX support again, and added support for building extension modules under OSX. And Mark Dewing (in attempts to compile parts of Quameon, a monte carlo quantum atom simulator) sent in several bug reports. Several other people also sent in bug reports.

Of course I have added some things myself, too ;) For one, I added basic support for the 'staticmethod' and 'property' builtins. I also (finally, might I say) split up the compiler core (ss.py) into several files, added many fixes for multi-dir/multi-file projects, further optimized a few builtins, and fixed many minor issues.

In all, I'm very happy with this release, and hope to get as much help for the next release!

Shed Skin 0.0.26

2008-01-16T01:51:00.000-08:00

After my 'rant' about not getting much help with Shed Skin, I received a lot of feedback on how to improve packaging and usability in general. Several people even started helping out with this :-) Most notably, Paul helped me to create a Debian package, and James wrote a tutorial, which has by now replaced the README. Thanks guys!!

Shortly after my rant, somehow I also got involved in the Google GHOP project, in which high school students are paid to help out with open source projects. Some of these students turned out to be a real help, and one of them even managed to add complete 're' support to Shed Skin, using PCRE (perl-compatible-regular-expression library, thanks Cyril for the suggestion; this will be available in the next release!).

All of this, in turn, inspired me to add (almost) complete support for os.path and collections.defaultdict (deque was already supported). The combined result of all this should be a much more 'usable' project, although many things can still be improved of course. For the next release, I am planning on splitting up the compiler core (ss.py), and adding support for time, datetime, socket and as mentioned re.

When all this works well, I think the time has finally come to have another look at type inference scalability. Two ideas that stand out in my mind are iterative deepening (restart after an increasing number of iterations, each time combining everything that was learned) and selector-based filtering (basically, the idea is that for a method call x.bleh(), obviously x can only be of a type that has a bleh method, though it can be generalized further, e.g. for x=y).

Anyway, getting back to the subject, I have just released Shed Skin 0.0.26. It took me a while to get there, but this is mostly because it has many improvements:

-support for:
-most os.path methods (bootstrapped using Shed Skin)
-many os methods (ghop; many still remaining)
-collections.defaultdict (completing collections)
-getopt.gnu_getopt (bootstrapped, completing getopt)
-5 of the last 7 missing str methods (ghop)

-optimized string addition (a+b+c..)
-improved locale support (ghop)
-removed many leading underscores from generated code
-new documentation/tutorial
-added a Debian package
-many minor bugfixes

Additionally, I moved the project from SourceForge (sorry, guys) to Google code hosting. This is the new address:

http://shedskin.googlecode.com

Shed Skin: Call for participation

2007-11-24T09:32:00.000-08:00

Okay, so I have built this pretty cool (restricted) Python-to-C++ compiler, that actually works for many not-too-large programs. It currently builds (simple) extension modules, and shows massive speedups for many programs, often outperforming Psyco by a factor. As I recently showed on my blog, it also integrates nicely with Parallel Python. I would have thought the latter would have given rise to at least one comment..

Am I the only one seeing the potential of an implicitly statically typed Python-like-language that runs at practically the same speed as C++? Is it that being ahead of the time makes you completely misunderstood, even by pretty smart hackers? I remember developing something quite like Wikipedia many years ago, and being unable to convince anyone of why this would be a good idea.. Of course that doesn't mean my compiler is a good idea (I wish), but I'm sure not going to give up as easily this time.

So, once again, I'd like to ask for more participation. Many open source users don't realize, I think, how open source projects, especially new ones, thrive on user feedback. Programming is debugging, and there's nothing more satisfying than fixing particular problems users encounter. Sure, I could find most bugs myself, but I don't want to end up in a nut house, and at some point there has to be some kind of community process. Patches are very useful too, even simple ones, as they often trigger more patches by me. Extension module support, for example, started out as a simple proof-of-concept patch sent in by a user.

I'd very much like to take Shed Skin further forward, but I need your help to do so! Please visit the homepage and send in bug reports or join the mailing list and start some discussions. I can also be hired to work on specific features of course :) So hurry to the homepage:

http://mark.dufour.googlepages.com

Shed Skin and Parallel Python

2007-10-18T01:43:00.001-07:00

Shed Skin is an experimental Python to C++ compiler. Parallel Python allows for clean and simple parallelization of Python processes over multiple cores. Wouldn't it be cool if we could combine the two? Of course I wouldn't be writing this if I hadn't tried. Here's how to do it.

Create an extension module with Shed Skin, containing function(s) you'd like to use in parallel. For example, we might use the partial sum function from the Parallel Python website:

def part_sum(start, end):
..
return sum

For Shed Skin's type inference to work, part_sum must be called from somewhere:

if __name__ == '__main__':
part_sum(1, 1)

Creating an extension module is simple (suppose the module is named meuk.py):

ss -e meuk
make

Because Parallel Python expects pure-Python code, we must call our compiled function via a pure-Python wrapper:

def part_sum(start, end):
import meuk
return meuk.part_sum(start, end)

In order for Parallel Python to find our extension module (at least on my Ubuntu system), we must issue this in advance:

export PYTHONPATH=$pwd

And there you have it. Here are some timings:

no extension module, 1 worker: 11.3 seconds
no extension module, 2 workers: 6.2 seconds
extension module, 1 worker: 0.6 seconds
extension module, 2 workers: 0.3 seconds

Shed Skin 0.0.24, 0.0.25

2007-10-16T02:18:00.000-07:00

I've just released Shed Skin 0.0.25. Together with the (unannounced) 0.0.24 release, there have been some interesting changes. Most importantly perhaps, Shed Skin now caches (most) 1-length strings, which can improve performance dramatically for string-intensive programs. I also performed a long-overdue rewrite of the virtual function detection code, which should work much more reliably now, at least for relatively simple cases :)

0.0.24:
-1-length string caching

0.0.25
-improved detection of virtual functions
-further set optimizations
-fix for extension modules and certain default arguments
-exhaustive checking of C++ keywords
-fix for some combinations of arguments to min, max
-several minor bug fixes

As always, I could really use more help in pushing Shed Skin forward. Let me know if you'd like to help out, but are not sure where to begin.

Shed Skin 0.0.23

2007-08-20T05:48:00.001-07:00

I have just released Shed Skin 0.0.23. It doesn't contain the type inference scalability improvements I was working on, but it does have quite a few bug fixes and minor feature additions. Here's a list of changes:

-support for __iadd__, __imul__ and such (except __ipow__ and __imod__)
-some overdue set optimizations
-fix for string formatting problem (%% did not always work)
-extension module stability fixes
-fix for particular inheritance problem
-other minor bugfixes, cleanups, and error messages

I could really use some systematic help in pushing Shedskin further. Some ideas:

-send in bug reports - these are extremely valuable and motivating to me, yet I don't receive many..
-find out why test 148 is currently broken under windows
-add datetime, re or socket support
-look into supporting custom classes in generated extension modules
-write a Shedskin tutorial for 'novice' programmers
-systemically test performance and suggest and work on improvements
-investigate replacements for std::string and __gnu_cxx::hash_set
-perform janitorial-type work in ss.py and lib/builtin.?pp
-support extension modules under OSX (OSX gives me accute mental RSI)
-add more tests to unit.py

Shed Skin 0.0.22

2007-06-29T02:18:00.000-07:00

after being bogged down with work for a few weeks, I got back to development again. the trigger was a proof-of-concept patch sent in by Harri Pasanen for generating extension modules. previously I was waiting for someone else to fully tackle this, but his patch was quite simple, and I found out it easily works under mingw, too. so I generalised things a bit, and released it as part of version 0.0.22. the process of building an extension module is now quite simply 'ss -e ..' and 'make' (note it doesn't work under OSX, yet).

there are some limitations though as to the way this works:

-only builtin scalar and containers can be passed/returned (int, float, str, list, tuple, dict, set)
-arguments/returned objects are completely copied/converted at call/return time (i.e., including contained objects)
-global variables are considered constant, and converted at module initialization time

consider this simple program, mod_name.py:

some_var = [1,2,3]

def some_func(x):
return 2*x

if __name__ == '__main__':
some_func(1) # obviously, this is needed for type inference to work

to compile this down to an extension module, simply use the new '-e' command-line parameter:

ss -e mod_name
make

that's it. now the program can be used from an arbitrary python program/prompt:

>>>import mod_name
>>>dir(mod_name)
>>>mod_name.some_var
>>>mod_name.some_func(1)

I'm hoping someone else can add support for custom classes and find out how to get this to work under OSX!

Shed Skin 0.0.20 and 0.0.21

2007-03-27T01:10:00.000-07:00

development has been continuing at a steady pace, resulting in two new releases. I haven't gotten around to cleaning up and improving tuple support, as of course I got bogged down into other details. the first release essentially combines many minor fixes:

Release Name: 0.0.20
-improvements to aug-assignments with subscripting ('a[x, y] += 1' and such)
-fixed some problems with slice-assignments ('a[1:-1] = [1,2])
-make integer division (/,//,divmod,floordiv) equal to CPython for negative/positive combinations of arguments
-make printing of floats closer to CPython
-move generic functions/methods to header file
-many small fixes (allow 'self' as function argument, list.extend takes iterable, __delitem__ overloading, raw_input(), 'return' from generator..)
-improved error checking for dynamic types
-optimize expr**2 and expr**3 using __power2 and __power3 functions

the next release is more interesting. first, a problem exhibited in a little program bearophile sent me (I wish there were two bearophiles :-)) gave me the insight that two things I was doing during type inference were more or less the same; this allowed me to generalize things and cut away about 100 lines. second, I added support for 'bisect', 'collections.deque' and improved 'copy' support. finally, there were some important dict optimizations (dict[..] += .. and dict.__getitem__ now only index once):

Release Name: 0.0.21
-important type inference fix/cleanup
-support for 'bisect', 'collections.deque' and 'string.maketrans'
-improved 'copy' support
-support for 'try, else' construction
-some optimizations ('dict[..] += ..', "''.join(sorted(str))")
-several minor bug fixes

Shed Skin 0.0.19

2007-02-12T01:07:00.000-08:00

I have just released 0.0.19, with some interesting changes. Iterators and generators are supported now. Full random support was contributed by a user (thanks Jeff :-)), by converting a Python version to C++ using Shedskin. Interestingly, by default it uses the same random engine (Mersenne Twister) as CPython, so the two behave exactly the same. Jeff is now thinking about how to add fast matrix support, which would be really nice to have.. But there were also many small fixes in this release. Here is the sourceforge changelog:

-iterator and generator support (no generator expressions yet)
-full support for random module (converted from Python version)
-added itertools.{count, repeat, cycle}, dict.{iterkeys, itervalues, iteritems}
-added 3-argument integer version of __builtin__.pow
-logical and, or operations have correct return value now (e.g., '3 and 4')
-lots of minor bug fixes (improved % operator, added math.pow..)

The main focus for 0.0.20 will probably be to add support for tuples, with differently typed elements, of length greater than 2, up to some arbitrary length..

Another Raytracer

2007-01-27T01:49:00.000-08:00

here's the output of a raytracer in python, called yopyra, by carlos gonzales, after being compiled by shedskin. the speedup is about the same as for the pygmy raytracer, that is part of the unit tests (for this picture it is about 60). I will probably add this program to ss-progs, but I need to remove one hack to support it, and bearophile (who sent me the raytracer) is still adding some nice features, like the ability to read scenes from a file, and render parts of a picture, so it's easy to put those multiple cores to use..

http://mark.dufour.googlepages.com/scene.txt.jpg

Shed Skin 0.0.18

2007-01-18T03:15:00.000-08:00

yes, it's the fourth release of shed skin in about a month. can you tell I'm working on it full-time now? :) here's a list of major changes:

-modifications to work on OSX and 64-bit systems
-improved support for class attributes
-classes can now be used prior to their definition
-several optimizations and fixes for strings
-hash value caching for strings and tuple{int,double,str}
-optional bounds checking using --bounds

thanks to jplevyak, larry, gustavo and denis for helping to get SS to work on 64-bit and OSX systems!

note that it's very hard for CPython to cache hash values for tuples (because the elements might be mutable). once types are known however, e.g., for tuple, SS can cache hash values no problem. this can cause quite a speedup.. for example, the following program is now 10 times faster than under CPython (corresponding to the 10 loop iterations):

sign_words = {}
kawamabahana = 10000000*(1,2)
for x in range(10):
hash(kawamabahana)

I'm going to take a few days off now, and think about a strategy to add iterators (and hence generators and generator expressions), and possibly non-uniform tuples of length greater than 2..

24 programs that work

2007-01-16T09:18:00.000-08:00

I'm collecting programs that work out-of-the-box with Shedskin CVS, to add to the homepage before releasing 0.0.18 (which should be out within the next few days). So far, I have 24 programs, at a total of about 6,000 lines:

http://mark.dufour.googlepages.com/ss-progs.tgz

Please let me know if you have an interesting program I might add to this set. If someone else would like to perform some testing (analysis time and comparing performance with CPython and Psyco, for example), that would be great.

update: __tim__ pointed me to the nbody debian language shootout test, which becomes about 100 times faster here. I added it to ss-progs.

Shed Skin 0.0.17

2007-01-11T04:15:00.000-08:00

And here goes 0.0.17, with some interesting fixes:

-support for assignment lists, so e.g. '[[a,b],[c,d]] = matrix' and 'for [[a,b],[c,d]] in matrices: ..' work now
-'_' can be used as special assignment target (expression is not assigned), e.g. '[[a,_],_] = matrix' works now
-support for '__name__' attribute of modules, so e.g. "if '__name__' == '__main__'" works now
-various improvements in exception handling (AssertionError, except some_tuple, ..)
-limit on tuple/list unpacking removed, so e.g. a,b,c,d,e,f = some_tuple works now
-improved printing of floats (using "%g" instead of "%f")

Approaching 0.1

2006-12-29T05:44:00.000-08:00

After 0.0.15 I have quickly released 0.0.16. It essentially adds frozenset and fixes some bugs, as reported by users of 0.0.15. The next release is coming along nicely too, and should be ready within about a week. Here's a list of changes:

-added frozenset
-time.sleep now works on WIN32
-constant-string expressions and __doc__ attributes are made into nice C++ comments
-added --nowrap optimization option to ss.py (disables checking for negative indices)
-several minor bug-fixes reported by users of 0.0.15

Because I have a huge amount of spare time coming up to work on Shed Skin, I have started to think about what is necessary to do a 0.1 release. These are currently the most important shortcomings:

-support for iterators, generators and generator expressions

The first two seem mostly a case of how to do this nicely in C++, and the latter one seems easy.

-support for tuples t of len > 2 and with different types of elements

Again this seem mostly a case of how to do this nicely in C++. I'm looking forward to finding out how to do this.

-scalability of the type analysis

Because of all the details involved in doing a python compiler, I still haven't focused on this too much. The basic techniques seem to work very well, but I have many ideas yet to work out to improve scalability. Based on my work so far, I'm convinced it is possible to quickly analyze most programs up to a few thousands lines, even without any form of profiling.

-two-way integration with CPython

There may be some progress at this front, as another developer has decided to look into using boost.python for this purpose. It's rather exciting to see small fragments of this work already. If anything, it has made me optimistic about having something like this work in the near future.

-some optimizations: strings (replace std::string), indexing (remove wrap-around checks by proving an index expression is always positive), heap allocation (transform heap allocation into stack- and static preallocation, when possible)

While not essential for a 0.1 release, an important goal of Shed Skin is to generate really fast code. Especially the latter optimization would be a great master's thesis subject.. :-)

Shed Skin 0.0.15

2006-12-08T06:52:00.000-08:00

After being distracted by my work for a few months, I'm finally back to Shed Skin development. It's interesting how the same boring programming work is more fun when you don't get paid for it! Anyway, I hope to work on Shed Skin full-time for at least the next three months, which should lead to several interesting improvements. I'm not sure exactly which those will be yet, as I never really plan ahead much.

For starters, I updated Shed Skin to work with the newly released Python version 2.5. As part of this, I added support for the new 'any' and 'all' keywords and for conditional expressions. The new Shed Skin release (0.0.15) also comes with support for several, previously unsupported library functions. IIRC, these are:

os.path.{split, splitext, islink, isdir, isfile, exists}
os.{stat, lstat, rename, chdir}
stat.*
fnmatch.{fnmatch, fnmatchcase}
random.{seed, sample}

Because quite some library modules are now (partially) supported, I moved all of them to a separate 'lib' directory. Because the ugly '_' in filenames is not needed anymore, this makes it much easier to add to the set of libraries supported by Shed Skin (hint, hint!) If you are interested in doing so, please have a look at the updated README file.

The os.path.* and stat.* support was added by running Shed Skin over (slightly modified) pure Python implementations, taken from the PyPy project. I am getting more and more optimistic about this approach, improving the amount of supported library functions, helping me to locate bugs and motivating me to fix them all at the same time. The next module I may look into is the 're' module, which should help me locate a few more bugs, and help me to add support for other modules that make use of it. Please let me know if you're interested in helping out increasing the number of supported libraries, as there's probably lots of low-hanging fruit.

Most of the newly supported functionality was added in anticipation of compiling an interesting program I found. After messing around with Amarok, Gtkpod, Gnu-pod and what not, I finally found a program to reprogram the database on Apple's latest iPod shuffle (the 15.5 gram 1 GB one :D) that actually worked. Needless to say, it was written in Python.. :-) One interesting application is to put it on the shuffle itself, so you can run it from any computer. The downside is the dependency on CPython. Looking through the code, at about 600 lines, it looked like a potential victim for Shed Skin. The author agreed, and hopefully Shed Skin generated code will be on many iPod's in the near future :-) Here's the link to the program:

http://shuffle-db.sourceforge.net/

Shed Skin 0.0.14, 1600-line program

2006-08-12T02:40:00.000-07:00

hi all (two readers :-))

it's been a while, but I've been hard at work improving Shedskin. I actually got paid for about a month, to support a certain 1600-line program. it compiles fine now, so that means it's a new record :-) I'm hoping very much to find another job like this, so if your boss might be interested in paying me to do a 'cheap' translation of some Python program to C++, please let me know. I don't need a lot of money to support myself :-)

okay, so what's new in this release:
- string formatting has been hugely improved, so most combinations of flags and types should give the same result as in Python now
-several new imports are supported now: getopt.getopt, cStringIO.StringIO, string.*, os.{getenv, getcwd}, and shedskin-specific (typed) versions of struct.{pack, unpack}: struct.{pack_ints, unpack_ints}, that may be useful.
-many, many bugfixes, resulting from debugging a 1600-line program :-)

interestingly, getopt.getopt is supported by taking a pure Python implementation (in this case, from the PyPy project) and compiling it to C++ :-) in the future, I think this technique can be used to support several other modules (possibly 're'), helping me locate bugs in Shedskin and improve the amount of supported libraries at the same time.

shortest sudoku solver

2006-07-13T12:32:00.000-07:00

bearophile sent me a link to this really cool program:

def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])

apparently it's a sudoku solver (couldn't you guess?). here's more information about it:
ShortestSudokuSolver

unfortunately, it mixes integers and strings ((i-j).. or a[j]) and arbitrary-size arithmetic (5**18), both of which are currently not supported by shed skin. the arbitrary-size arithmetic could be supported in this case, but I rewrote it for now. here's a version that works with shed skin CVS:

def r(a):
i=a.find('0')
if not ~i: print a; exit()
[m in [a[j] for j in range(81) if not (i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)] or r(a[:i]+m+a[i+1:]) for m in '3814697265625']
from sys import *;r(argv[1])

it's 211 characters, versus the 178 of the one above, so that's not too bad :) and it becomes 18 times faster here.

basic pygame support

2006-07-13T01:35:00.000-07:00

http://mark.dufour.googlepages.com/fysphun.png

this shows an interactive graphical program working with shed skin :-) the user can drag around points, and the connected 'bodies' move around realistically. to get this to work, I had to add basic pygame support (drawing points , lines, event handling). doing this was an interesting experience - I now feel it should be not too difficult to autogenerate bindings to many libraries, based on 1) a simple type model (manually written, see *_.py) and 2) the results of type inference. because my job requires me to implement/bridge some library calls, maybe I can be paid to work on this. hmm..

Shed Skin 0.0.11, give me money

2006-07-03T13:54:00.000-07:00

I have just released Shed Skin 0.0.11. It contains several important fixes again (see test 162). Most notably, lambda support is greatly improved (especially in an OO setting), and casting of incomplete types is re-enabled (so you can do e.g. ()+(5,), a = [[1]]; a = [[]] and such).

In other news, I will probably be paid on a temporary basis this summer, to support a certain 1600-line program. Please let me know if you have a Python program/prototype that you'd like to have converted to C++, and I can probably tell you how much time this would take me.

Shed Skin 0.0.10, Summer of Code 2006

2006-06-15T07:26:00.000-07:00

I have just released Shed Skin 0.0.10. besides several important bug fixes (see test 161), it contains many new error messages for unsupported features and dynamic (sub)types. this should make it much easier to try out Shed Skin and work around basic problems. please try it out and let me know about any problems/successes ^^

in other news, a Shed Skin proposal has again been accepted in this year's Summer of Code. the student will investigate memory optimizations more deeply than I have done for my thesis, and implement both a stack allocation and static preallocation technique. we expect to start discussing the topic on the shed skin mailing list in the coming weeks.

finally, phillip hassey (also a Python SoC mentor) suggested an interesting idea: to automatically create *_.py files from pure C++ library header files, so compiled code can directly use many C++ libraries. this shouldn't be too difficult (the header files contain all type information), and has very interesting potential.. please let me know if you'd like to work on this!

pystone/richards benchmarks, upcoming 0.0.9

2006-05-17T14:29:00.000-07:00

I have been working over the past few days to get the pystone and richards benchmarks compiling well. as they do now, I added them to the test set. both are very simple from a type inference perspective, but they did help me uncover and fix several minor and a few major issues.

the speedups on my computer are about 10 for pystone and 185 (!) for richards. the latter is probably due to the fact that richards is heavily OO, and C++ compilers know how to efficiently implement that! :-)

I hope to release a 0.0.9 version within a few weeks, with these and some other changes. there is one problem that I have observed a few times now, that I would like to fix before that. sometimes, type information is lost during inference, so that results are incomplete.. I think I know what causes the problem.

Shed Skin 0.0.8, new website, Google SoC/Thesis?

2006-05-03T04:46:00.000-07:00

I have just released Shed Skin 0.0.8. for this version, I removed about 1000 lines (mostly memory optimizations - so the compiler is now less than 6000 lines!), cleaned up stuff a bit (it's still a monolithic file though), added/completed more string methods and applied many minor bugfixes and several more error messages, based on Bearophile's list of known bugs. thanks man! :-)

I also created a simple Shed Skin 'homepage' and modified the README, to better introduce Shed Skin to people. please modify any links to my blog or the sourceforge site to this page - see the link on the right. please let me know if you think I should change something.

now that the source code is becoming pretty clean, and there are many largish test programs that run well (see Section 5 of me thesis!), the time seems right to invite other people to join the project, and look into some important aspect I don't have enough time for/interest in. there are three important things that can be investigated relatively separately:

-I removed my simple memory optimizations (turning heap allocation into stack- and static preallocation). this is a fascinating subject, with a lot of existing techniques coming from the Java community. as can be seen from my thesis, it can really help performance as well. I just never had the time to properly investigate it.

-SS currently uses the bloody C++ STL string type, which makes it really slow for string-intensive programs. it would be really nice to have a more efficient (preferrably OO) string type, possibly using Psyco-like techniques. since I never really use strings much, I do not have enough interest in this myself, but I recognize the importance.

-integration of Python code and compiled code remains a hassle. currently, a lot of manual work is needed to provide 'bindings'. it would be great to somehow have a (semi-)automated process, to enable compiled code to at least use the standard library, and to be able to easily call compiled code from Python programs.

if you are interested in any of these three topics, note that the deadline for the Google Summer of Code 2006 is in about a week. since SS got accepted last year, and there will probably be more slots for Python this year, this might be worth a try! let me know, and we can cook up a proposal together.

the first topic (memory optimization) is also a great topic for doing a Master's/PhD Thesis. unfortunately, Robert could not find a mentor for this. please let me know if you are interested, or you know of a compiler-savvy (Master/PhD) student that might be interested!

Master's Thesis

2006-04-25T15:25:00.000-07:00

I haven't been putting as much effort as I'd like into SS development lately, because of writing my Master's Thesis. I have added a link to the resulting document to the links on the right. There are some interesting performance measurements inside. For a benchmark set of 16 programs, SS typically results in a speedup factor of 2-40 versus Psyco, 12 on average, and 2-220 versus CPython, 45 on average.

As for the future, I've decided to drop all memory optimizations (stack and static preallocation), since I never really put much thought into them, and they only help 'marginally' (since I did not do them well :P) I'm also discontinuing my 'char type' work, and any ideas about automatically connecting to the standard library. This is so that I can focus on the core type inference and code generation stuff.. Which I hope to continue soon :-)

Shed Skin 0.0.6

2006-01-27T03:58:00.000-08:00

Here goes 0.0.6.. :)

With the help of Bearophile, I optimized list comprehensions and iteration a bit further. Programs are now also compiled together with the builtins, which can greatly improve performance in some cases. For example, the Pythonchess speed test engine now becomes about 22 times faster on my computer. Please check it out, and let me know about any problems you encounter.

For 0.0.7, I am working on a 'char' type. That is, let the compiler use the C++ 'char' type whenever programs are working with strings of length one. This dramatically improves the speed of programs that use strings of length 1 and/or 'string[index]' a lot. If you'd like to try it out, keep a watch on CVS, because I will commit this change soon, and let me know about any problems.

0.0.6 Update

2006-01-14T00:26:00.000-08:00

Hello there,

Just to let anyone interested know that SS development is alive and kicking; expect me to release 0.0.6 within about a week! Unfortunately, I did not find the time to work on a connection with arbitrary external libraries. There have been many small improvements, though, relative to 0.0.5.9. I also added two new largish programs:

-a stripped-down version of Pythonchess, thanks to Jyrki, the author! (360 lines)
-yet another sudoku solver, that would cause older versions of SS to choke badly (178 lines)

The former becomes about 9 times faster on my PC, but there are probably some simple optimizations I can do to improve this further. The latter really gave the type inferencer a hard time, so I added some simple heuristics to 'guess' types, for use as a starting point of the analysis. This greatly reduced the analysis time for many other tests.

Btw, the raytracer is 65 times faster on my PC at home (X2 4800+), instead of the 40 I measured in China :-)

Shed Skin now correctly compiles about 6000 lines of unit tests. Included in these are the following non-trivial programs:

-satisfiability solver 1
-satisfiability solver 2
-min/max othello player
-neural network simulator
-sudoku solver 1
-sudoku solver 2
-sudoku solver 3
-convex hull
-voronoi
-mandelbrot
-n-queens
-the pygmy raytracer
-tic-tac-toe on arbitrary-size boards
-linear algebra routines
-simple genetic algorithm
-conway game of life
-pythonchess speed test engine

I'm starting to become pretty confident the compiler will work well in general. The speedups are also pretty good in general, but I think it can be much improved still, by tweaking code generation and the C++ versions of the Python builtins. I could really use a hand here! :D

(update: Anyone would like to try and get SS to run using, say, vc++?)

Shed Skin 0.0.5.9

2005-12-15T10:00:00.000-08:00

I have just released Shed Skin 0.0.5.9. It's almost where I want it to be
for 0.0.6. What remains to be coded is some kind of connection to the
standard library (probably a simple one at first: working only for
'opaque handlers'). I also want to improve cases where ints and floats
are mixed, since this is quite common. Some major changes:

-basic exception handling

(support for custom ones, and for some builtins such as ValueError,
KeyError and AssertionError; this will allow for implementation of
iterator objects later on)

-some basic inheritance

(no multiple inheritance yet, or weird stuff; this enabled me to add
the 340-line pygmy raytracer to the test set. it becomes about 40
times faster here..)

-keyword arguments

(this has not been tested very well yet - let me know about any problems)

-many missing minor 'set' features, thanks to reports by bearophile

(it should be practically complete now. the whole set of builtins is
nearing completion :D time to start optimizing stuff..)

-many, many bugfixes again, again mostly thanks to bearophile

I added four new 'big' programs to the test set that (with some minor
modifications) work now: a tic-tac-toe player for arbitrary size
boards, a simple genetics algorithm, a linear algebra program and the
mentioned raytracer. Finally, the README has been improved again,
though it's still pretty bad. After the release of 0.0.6 I plan to
create a web site with performance comparisons between CPython, Psyco
and Shed Skin (perhaps even PyPy :P), because quite some interesting
programs compile now, and Shed Skin is usually a lot faster than Psyco, except when Python builtins are the bottleneck. I guess some more STL magic is required here..

Let the small code fragments that fail flowing!

Shed Skin 0.0.6 Status Update

2005-12-10T05:24:00.000-08:00

Just a small note to anyone interested, that I am hard at work to get Shed Skin version 0.0.6 ready before the end of the year. It already supports an almost unmodified OO raytracer of about 350 lines (pygmy, with a speedup of about 40 on this sempron 2200+), as well as some other larger new programs. Simple inheritance has been improved by a lot. I am currently working on exception handling, which will probably be supported well in 0.0.6. Thanks to bearophile, a huge amount of bugs have additionally been
fixed. I will probably release a 0.0.5.8 or 9 within the coming week.

Please let me know if you have interesting use cases of inheritance and/or exceptions, and I would be glad to look into any problems. In that case, please ask me for the latest version of the compiler first (I have no access to CVS currently.)

Btw, I will probably be working on some method of accessing much not too weird standard library functionality soon, but I'm not sure whether I will manage to get this working well before 0.0.6.

Shed Skin 0.0.5.1 Released

2005-11-30T00:17:00.000-08:00

I have just released Shed Skin 0.0.5.1. It contains many small bug
fixes, but more importantly it enables GC again (argh! :P) This should
make some of bearo's tests run a lot faster. As per his suggestion, I
also copy-pasted float hashing from CPython, which should make his
dict_speed test run much faster. I also made some improvements for
programs consisting of multiple modules. See test 139 for a partial
overview of the smaller bug fixes.

As usual, see shedskin.sourceforge.net for downloading SS.

0.0.5: Major Bugfix Release

2005-11-07T15:26:00.000-08:00

Hi all,

I have just released Shed Skin 0.0.5. It fixes many bugs and adds many minor features to the Python builtins, most notably, the 'set' class. There have also been some optimizations on the C++ side. Finally, the README now better explains the compiler's limitations, and a TODO file has been added containing open bugs.

I would like to invite anyone to try out this new version, especially if there were problems with 0.0.4. If you encounter a bug or missing feature, please send me a small code fragment that exhibits the problem, so I can fix it or add it to the TODO. If you are a C++ programmer, please consider helping out on the C++ side, by sending in patches to improve the C++ implementation of the Python builtins!

For 0.0.6 (a feature release!), the following things are on my list:

- Basic inheritance support
- Automating the connection to the Python standard library
- Better error messages for things SS doesn't handle (Finally?!)

(This release has taken way too long, because I did not have much time this month. 0.0.6 might also take a while, since I will be living in China for the next seven weeks and will be writing my thesis, among other things. I expect to release it a few days after I get back, which would be just before new year.)

Two weeks off

2005-10-13T19:49:00.000-07:00

There are lots of fixes in the pipeline for Shed Skin 0.0.5. Unfortunately, I somehow managed to give away my PC, and I planned some sort of vacation for the next two weeks. So it's going to be very hard to release a new version anytime soon. I'm still very motivated about the compiler, and there's a whole list of things I'm dying to fix, but it's hard to do without my own computer.. :)

Things planned for the next release:

- lots and lots of bug fixes for the builtin types
- several optimizations in the resulting C++ code (e.g. for indexing)
- error messages for anything the compiler doesn't support
- builtin set type (in addition to sets.Set), plus most of its methods

Shed Skin 0.0.2: Easy Windows/OSX Installation

2005-09-18T13:33:00.000-07:00

Shed Skin 0.0.2 is up on SourceForge. It should install easily on Windows 2000/XP and on OSX. Please give it a try and let me know if there are still some problems.

If you would like to help me improve Shed Skin, please send me small code snippets, preferrably extracted from real-life use cases, that the compiler has problems with.

Thanks to everyone who has helped me out, especially Khalid and Luis on python-list, and Denis de Leeuw Duarte right here in the street :-)

Update: 0.0.3 has also been released, with improved support for builtin functions, bug fixes and a Windows package of only 3 MB.

Update: We're on a roll, with 0.0.4. Many improvements again; added several interesting test cases (thanks to bearophile!): convex hull, n-queens problem, pascal triangle and ascii mandelbrot.

Announcement

2005-09-10T07:07:00.000-07:00

First release of Shed Skin, a Python-to-C++ compiler.

After nine months of hard work, I am proud to introduce my baby to the world: an experimental Python-to-C++ compiler. It can convert many Python programs into optimized C++ code, without any user intervention such as adding type declarations. It uses rather advanced static type inference techniques to deduce type information by itself. In addition, it determines whether deduced types may be parameterized, and if so, it generates corresponding C++ generics. Based on deduced type information, it also attempts to convert heap allocation into stack and static preallocation (falling back to libgc in case this
fails.)

The compiler was motivated by the belief that in many cases it should be possible to automatically deduce C++ versions of Python programs, enabling users to enjoy both the productivity of Python and the efficiency of C++. It works best for Python programs written in a relatively static C++-style, in essence enabling users to specify C++ programs at a higher level.

At the moment the compiler correctly handles 124 unit tests, six of which are serious programs of between 100 and 200 lines:

-an othello player
-two satisfiability solvers
-a japanese puzzle solver
-a sudoku solver
-a neural network simulator

Unfortunately I am just a single person, and much work remains to be done. At the moment, there are several limitations to the type of Python programs that the compiler accepts. Even so, there is enough of Python left to be able to remain highly productive in many cases. However, for most larger programs, there are probably some minor problems that need to be fixed first, and some external dependencies to be implemented/bridged in C++.

With this initial release, I hope to attract other people to help me locate remaining problems, help implement external dependencies, and in the end hopefully even to contribute to the compiler itself. I would be very happy to receive small programs that the compiler does or should be able to handle. If you are a C++ template wizard, and you would be interested in working on the C++ implementation of builtin types, I would also love to get in contact with you. Actually, I'd like to talk to anyone even slightly interested in the compiler, as this would be highly motivating to me.

The source code is available at the following site. Please check the README for simple installation/usage instructions. Let me know if you would like to create ebuild/debian packages.

Sourceforge site: http://shedskin.sourceforge.net
Shed Skin blog: http://shed-skin.blogspot.com

Should you reply to this mail, please also reply to me directly. Thanks!

Credits

Parts of the compiler have been sponsored by Google, via its Summer of Code program. I am very grateful to them for keeping me motivated during a difficult period. I am also grateful to the Python Software Foundation for chosing my project for the Summer of Code. Finally, I would like to thank my university advisor Koen Langendoen for guiding this project.

Details

The following describes in a bit more detail various aspects of the compiler. Before seriously using the compiler, please make sure to understand especially its limitations.

Main Features

-very precise, efficient static type inference (iterative object contour splitting, where each iteration performs the cartesian product algorithm)
-stack and static pre-allocation (libgc is used as a fall-back)
-support for list comprehensions, tuple assignments, anonymous funcs
-generation of arbitrarily complex class and function templates (even member templates, or generic, nested list comprehensions)
-binary tuples are internally analyzed
-some understanding of inheritance (e.g. list(dict/list) becomes list(iter(A)))
-hierarchical project support: generation of corresponding C++ hierarchy, including (nested) Makefiles; C++ namespaces
-annotation of source code with deduced types
-builtin classes, functions (enumerate, sum, min, max, range, zip..)
-polymorphic inline caches or virtual vars/calls (not well tested)
-always unbox scalars (compiler bails out with error if scalars are mixed with pointer types)
-full source code available under the MIT license

Main Limitations/TODO's

-Windows support (I don't have Windows, sorry)
-reflection (getattr, hasattr), dynamic inheritance, eval, ..
-mixing scalars with pointer types (e.g. int and None in a single variable)
-mixing unrelated types in single container instance variable other than tuple-2
-holding different types of objects in tuples with length >2; builtin 'zip' can only take 2 arguments.
-exceptions, generators, nested functions, operator overloading
-recursive types (e.g. a = []; a.append(a))
-expect some problems when mixing floats and ints together
-varargs (*x) are not very well supported; keyword args are not supported yet
-arbitrary-size arithmetic
-possible non-termination ('recursive customization', have not encountered it yet)
-profiling will be required for scaling to very large programs
-combining binary-type tuples with single-type tuples (e.g. (1,1.0)+(2,))
-unboxing of small tuples (should form a nice speedup)
-foreign code has to be modeled and implemented/bridged in C++
-some builtins are not implemented yet, e.g. 'reduce' and 'map'

SoC: finished!

2005-09-02T06:12:00.000-07:00

C++ is fantastic. It was very easy to integrate a garbage collector into the compiler: I only needed to add some simple code to a single header file, and it worked. I've also made grateful use of template specializations in redesigning the tuple implementation. In addition to these larger features, I also implemented a huge amount of smaller features over the last two weeks. Apart from several theoretical niceties, such as generation of complex generics, the compiler can now actually handle several relatively large programs as well. In all, I think I have reached all SoC milestones, and much more.

There are now 6 larger programs in the unit test set, written without any static compilation in mind (by friends, or by me, before I wanted to build a python compiler,) that the compiler now handles fine. In total they weigh in at 879 lines of Python code, which the compiler transforms in total into 1749 lines of C++ code (excluding header files, macro expansion, builtin functions, ..) These programs are:

-a simple satisfiability solver (110 lines, complicated list comprehensions)
-a japanese puzzle solver (180 lines, uses some real polymorphism)
-a more advanced satisfiability solver (170 lines)
-a not-too-bad othello player (123 lines, does much with binary tuples)
-a neural network simulator (95 lines, uses classes, badly polluted first iteration)
-a sudoku solver (177 lines)

The compiler generally takes less than 20 seconds to analyze each program on my old athlon XP 1800+. The speedup is in general larger than a factor of 10, often much more.

In fact, I would like to invite any adventurous soul at this point to try out the compiler, and send in anything that doesn't work but should (please, as small as possible), or anything non-trivial that does work (so I can add it to the test set.)

Note that there are currently several important limitations to the type of Python code that is supported:

-Of course, don't use reflection, eval or weird run-time polymorphism that cannot be easily mapped to C++.
-Do not import libraries. Only Set is currently supported. I am working on a simple system that will allow users to add C++ versions of libraries to the compiler.
-Do not mix None and integer types. The compiler will bail out with an error. Use zero or any other special value instead. Do not mix scalar with pointer types. Try to keep things uniform. This is usually more elegant anyway. However, it is often useful to mix types in binary tuples, and the compiler supports this.
-But do not use tuples with different element types with a length greater than 2. Binary tuples with differently types elements can also not be used in addition, etc. 'Zip' only supports two arguments.
-Declaring things before use may sometimes be necessary at this point. For example, classes. I hope to fix this soon.
-Using varargs and kwargs will probably end in tragedy.
-In general, program elegantly, like you would in C++, but without all the type declarations.
-The compiler has not been tested on programs larger than 250 lines.

I still need to fix a non-termination problem I encountered, but this won't occur for most programs under 250 lines. I also need to solve many smaller issues. However, the compiler should work pretty well for many programs. If you're interested, by all means, please try it out and let me know how it went. For any larger program, there are probably a few minor issues or missing builtin functions that I would gladly fix, if I have a use case.

The compiler is currently only available via CVS. I hope to release a packaged version in about a month. Please see the README with instructions on how to use it. In any case, it won't work under Windows. Let me know if you would like to debug this.. :-)

Countdown

2005-08-20T03:08:00.000-07:00

Alright! After almost 8 months of more than full-time hacking the end is in sight. Everything is looking great. I'm hoping to finish the final three features of my soc-todo-list today, except for integrating a GC, which I hope to do tomorrow. The three features are: support for nested tuple assignments, e.g. a,(b,c) = expr (this may also occur inside for loops/list comprehensions), bootstrapping some useful builtins (enumerate, zip, min, max) and supporting untyped constructors that do not flow to any instance variable assignments, e.g. in return [], we may want this to become a list(str), because for example there is a return ['u'] in the same function.

The last thing I would like to do is compile a simple neural network simulator that I wrote a while ago, as the final test case before a 0.1 release. It will require writing C++ versions of some external calls (e.g. math.e, random.random).

In all it seems there are no hard problems left as far as my aims go. Of course I could easily work another few years on the problem, supporting more and more flexible code, extending many features (e.g. internally typed ternary tuples..), work on extreme scalability (by profiling/maintaining object contours) etc. etc. For now I only intend to perform several long-overdue cleanups over the following months, as well as (hopefully) adding programs written by other people to the unit test set and fixing any problems they may have (again, as far as my aims go.)

Hmm, I just realized I practically haven't had a single day off over the last 8 months.. Maybe it's time for that vacation now..

Getting Close

2005-08-09T13:39:00.000-07:00

It took me some time to implement everything that was required by the Othello player. What is nice about it is that it pushes many things a bit further again, relative to the other larger test programs. No large features were required, or any major bugs uncovered, however, but I did have to fix many small problems ('the devil is in the details'). For example, constructs such as 'a = b = c', '[..for.. for..]' and '(1,2) in '[(1,2)]' were not yet well supported, and conversion of None to 0-pointers did not work well with parametric code. In the end, the resulting C++ player now plays about 25 times faster than the Python version. Pre-allocating some 'constant' lists will bring this to around 50.

As I see it, there are now only 5 relatively major features still to be implemented to reach all milestones for the SoC. These are: iterative splitting of user classes (this might work already), more aggressive merging of object contours containing (object contours with) only simple types, generating method templates (C++ function templates inside class templates), integration with a garbage collector and fixing a problem I discovered in the static preallocation code. I think these should not take me more than 10 days to implement. Other than these, there are still many minor issues of course. Maybe (hopefully) I can spend the last 10 days mopping up some minor problems that will need attention before being able to do a decent release.

Back On the Job

2005-08-07T01:31:00.000-07:00

Okay, after a few short days taking off (alright, of writing other Python programs.. :P) and preparing for and meeting with my university advisor, I'm back on the job. Over the last few days, I tried to learn my girl Python, by showing her, step-by-step, how to write a not-too-bad Othello player in under 100 lines. I don't think she could write something like that herself now, but I had a lot of fun :-)

I guess the first thing I will do today is to try and get this Othello player to compile. Programs like this one are perfect test-cases for the compiler: they often require some minor feature additions, which is nice and gives a feeling of progress, and generally uncover a few minor bugs, which are easily traced for such small programs. It will also be a good finger exercise to get going again.. There is still quite some work to do.. !

C++

2005-07-30T14:13:00.000-07:00

C++ makes for a great target language, with its intricate generics and its plethora of other low-level features. We can both succinctly map a high-level language such as Python to its feature set, and leave further optimization to be handled by decades old, mature C++ compilers. In many ways, C++ is really as flexible as Python. The problem is that this flexibility is often hard to achieve, and often results in unreadable code. It's nicer I guess to have a compiler write the C++ code for you :-) Consider the following example:

def flatsie(iter):                
   return [(b,a) for (a,b) in iter]

flatsie([(1,2.1)])         
flatsie({(2,3.141): [1,2,3]})         
flatsie({(11,4.1): None})             
flatsie(((7.7,1),))

There are some interesting things going on here. If we would like to compile this example to C++, the list comprehension has to be compiled to a generic function. But as the list comprehension iterates over both lists/tuples and dictionaries, it is not immediately clear how to write this nicely in C++, because dict is implemented using two template variables, as opposed to one for list and tuple. C++ provides an elegant solution: make iterable classes inherit from a pyiter class with a single template variable, and in case of dict, map the right template variable to it. Finally, we would also like to statically preallocate the result of the list comprehension, but since this is a generic list, we cannot define it globally. C++ again has the solution: use the 'static' keyword inside the function template, to create a parameterizable 'global' variable.

As of today, this example compiles cleanly, without breaking any of the other 95 unit tests. As there are only two types of tuples involved, the iterative analysis nicely ends up with two tuple object contours. These tuples are also modeled internally, or the list comprehensions would cause precision loss. Tuples of length greater than two are not yet internally modeled, but this would be a straight-forward generalization. In order to get here, I had to implement generic list comprehensions, and as a result the template milestones now look almost completed. In any case, it's pretty cool to see the compiler output the following working C++ code :D

template [class A, class B] static inline list[tuple2[B, A] *
     *list_comp_0(list[tuple2[B, A] *] *result,
     pyiter[tuple2[A, B] *] *iter) {
   A a;
   B b;
   tuple2[A, B] *__0;
   result->clear();

   FOR_IN(__0,iter)
       TUPLE_ASSIGN2(a,b,__0,0);
       result->append(new tuple2[B, A](b, a));
   END_FOR_IN
   return result;
}

int main() {
   flatsie(new list[tuple2[int, double] *](2, new
     tuple2[int, double](1, 2.1), new tuple2[int, double]
     (2, 4.1)));
   flatsie(new dict[tuple2[int, double] *, list[int] *]
     (1, new tuple2[tuple2[int, double] *, list[int] *]
     (new tuple2[int, double](2, 3.1),new list[int]
     (3, 1, 2, 3))));
   flatsie(new dict[tuple2[int, double] *, none *](1,
     new tuple2[tuple2[int, double] *, none *](new tuple2
     [int, double](1, 4.1),0)));
   flatsie(new tuple[tuple2[double, int] *](1, new tuple2
     [double, int](7.7, 1)));
}

template [class A, class B] list[tuple2[B, A] *] *flatsie
     (pyiter[tuple2[A, B] *] *iter) {
   static list[tuple2[B, A] *] __1;

   return list_comp_0(&__1, iter);
}

Iterative Progress

2005-07-29T09:59:00.000-07:00

After messing around for a few days getting CVS write access from my mother's XP box (which I finally gave up) and fixing problems caused by differences in GCC versions across three operating systems, I finally got to hacking on the iterative analysis again. I really needed that, since debugging unit tests for more than a week really drained me.

First, I fixed a problem where object contours were merged that could possibly be split later on. The fix logically results in much fewer iterations on the three largest unit tests, while more contours are now created. Additionally, I haven't observed a single unit test failing afterwards, where I would get a seldom failure on test 34 or 66 previously (the analysis is not deterministic.)

Currently, only object contours that contain just monomorphic, atomic instance variables are merged, because these can not cause the merged contour to be split later on. This means that as tighter bounds are deduced during the analysis, more object contours can be merged. It seems that other object contours referencing only such contours can also be merged, because they now also cannot be split later on, i.o.w. mergability looks like a transitive property. I will have to investigate this later, as I don't want CPA to blow up in any way.

Second, I commenced work on other classes than list. Supporting singularly-typed tuples was a breeze. It was also relatively straight-forward to support multiple instance variables: we have to iterate over multiple variables per contour now, and be able to split on each of them; merging decisions have to be made over the entire instance variable state of object contours. Splitting dictionaries seems to work well now. I guess the biggest problem was how to transition everything so that all unit tests still run.. making incremental changes and running all unit tests each time worked pretty well, but took some time (having to wait 5 minutes after each small change can get annoying.)

Next up is supporting internally types tuples again. This was not possible before multiple instance variables were supported. I will have to consider these separately from regular tuples somehow. I still also have to look into internally types tuples with length greater than two, but this will probably have to wait some more.

A problem I did not give much attention before, because I was mostly concerned with lists until now, is that in general the instance variables of a class are unknown! Since the first iteration is so imprecise, classes may end up with many instance variables that will vanish again when the analysis becomes more precise. I think there is not much we can do about splitting on such instance variables, except to assume the instance variables of built-in types to be known (as I do now.) Of course, this break Python semantics.

It remains an interesting approach to perform profiling in order to get good initial object contours (i.o.w., perhaps this could keep us closer to Python semantics.) Something I hadn't thought of myself yet, but Plevyak mentioned, is that it's also possible to maintain information between different runs of the iterative analysis. If the analysis is now run repeatedly during development, the difficulty of analyzing the program can be spread out over these runs. I don't think I will get this far during the SoC, but it sounds plausible that for much larger test examples, such an approach could make using the compiler much more practical.

No debugging for a few days!

2005-07-24T13:44:00.000-07:00

Even though debugging is a much bigger challenge than writing crap programs, I think I prefer writing crap programs. Luckily I now have all 88 unit tests working, except for a seldom failure of test 34 or 66. Test 66 is not so big, so I should be able to locate that problem some time, and hopefully that will fix 34 too :P

Emotionally, this concludes the first milestone that my mentors and I had drafted at the start of the SoC. It seems like it took a long time, but in the mean time I am pretty far with the template generation (milestone three and four), and the second milestone seems much easier now that I have worked on the first. The last milestone, finally (integration with a GC) should not take too much effort. So I am pretty positive at this point about reaching all milestones.

The first milestone required getting 'basic list examples' to work with the iterative analysis, but in the mean time it works (most of the time) for all the unit tests (which contain some list-intensive 100+ line programs). The second milestone (considering other classes than list, and with multiple polymorphic instance variables, among other things) now seems to be a straight-forward generalization, although I may be overlooking some terrible problem of course.

I will be moving to my mother's place tomorrow for some time, and work on the second milestone there. I will bring some unboxing papers, and see if they contain something I might implement after the SoC.

Cleaning Up

2005-07-18T14:40:00.000-07:00

When something just doesn't want to work, it's often a good solution to throw it away. Of course, Python makes this easier than many other languages. A famous quote of Tim Peters springs to mind: 'Python code is easy to throw away.' Additionally, throwing away crappy code can make you feel much better, since your program often becomes cleaner because of it, and you can always get back to the problem later..

Today I commented out the partial unboxing analysis that I had, as well the analysis that tried to work out upper bounds on strings used in reflection. Because now the data flow analysis does not have to consider the allocation sites of simple types anymore, a lot of cruft could be removed from the compiler. I will probably come back to the unboxing analysis after the SoC. The string bounds analysis was intended to help bootstrapping the compiler, but since this will not happen any time soon, I'm not sure if I'll ever revive it.

I intend to spend the following three days or so on getting as much unit tests working again as possible. After that, I will start work on the second milestone. I'm looking forward to that, as it will hopefully be more interesting than fixing bugs all day.. :-)

Unboxing

2005-07-17T09:03:00.000-07:00

I haven't posted here for a few days, as I was modifying my old code for unboxing of integers and floats, and I did not add any new features to the iterative analysis. I did fix a number of old unit tests to compile again with the latest code, but other than that there was nothing noteworthy.

It turns out that unboxing is not as simple as I had assumed. Actually, I never thought about it that much, because the other techniques got most of my attention - so much to do, and so little time. I decided to look into unboxing in depth, because of some undesirable interaction with the iterative analysis (e.g. having to use separate contours for lists with boxed and lists with unboxed integers.)

In the end, I concluded that creating good unboxing support is probably going to take more than just a few days, and, as I don't really have the time for this at the moment, I decided that I will disable the partial unboxing analysis that I have for now. That does not mean no unboxing can be performed: all integers and floats will be unboxed, and a warning will be given whenever they are confused with a pointer type. So for now, it will be the programmer's task not to add such confusions. Templates etc. will still work.

What will not work for now, then, are container objects with integers/floats and pointer types in the same slot, and passing integers/floats into arguments with a pointer type default (such as range(a,b=None) - we will have to provide two builtin C++ functions for this case.) As the latter can't be supported efficiently anyway without generating multiple function duplicates with different defaults, and mixing integers and pointer types for example in a list container is often not a very nice programming style, I feel the compiler could still be pretty useful.

It's always a bad feeling to have to add restrictions to the types of programs the compiler can handle, but hopefully this one will be temporary. In any case, it can still be used to compile programs written in a C++-style to C++. Although this might not sound very impressive, being able to use Python syntax in writing highly efficient programs would still be pretty cool :D

Final Piece of the Puzzle?

2005-07-14T03:43:00.000-07:00

Having to use 0CFA - in other words, no duplication at all of either class types or functions - during the first iteration will become terribly slow for larger programs, but worse, being so imprecise it makes life hard for IFA, causing it to have to split huge contours (consider a single contour for list for larger programs!), making it slow and requiring many iterations.

There are multiple interesting ways of combating this problem. We can selectively apply CPA during the first iterations, by limiting the sizes of cartesian products. Of course fully applying it would make the first iteration even more slow, but selectively applying it would probably not increase precision by much. I think what is really needed is to provide IFA with an initial 'guestimate' of the set of object contours that it should deduce. This does not work for just CPA, because CPA is not data-adaptive, and it would pollute itself if something 'unexpected' happens.

How to get an initial good set of object contours? Of course, heuristics can be applied. A lot of them, especially ugly ones. For example, a [1, 2] constructor could be grouped under a 'list(int)' contour. This becomes messy for more general, and polymorphic constructors - what to do with an [x, y] constructor?

I think a better, and more elegant, solution would be to perform profiling on the program that is to be compiled. Of course, if the program has unit tests, this would be a great match - but that's beside the point. It should be very simple to dump the actual types for each allocation site, possibly even relative to the actual argument types of the current function invocation. This can give us a great starting point. The dumps do not have to be perfect, because IFA will adjust to any imperfections. Best of all, we can enable CPA during all iterations, greatly improving IFA and reducing the number of iterations.

No, I don't mind that people will have to profile their applications. Especially if a simple technique like this turns out to greatly improve scalability.

BTW profiling has another advantage: it can provide type distributions at dynamic calling sites. In case of polymorphic inline caches, we can move the most used types up the ladder.

Bugs

2005-07-13T13:05:00.000-07:00

Today was the first bad day I guess, since starting work on the iterative analysis. As with the generics support I worked on before that, it's not something that you can just paste on the compiler and have it work. Because both required rather intrusive modifications, I did not run the unit tests every day while working on them. The result is long debugging sessions, like today.

Spending the whole day fixing 5 or 6 stupid bugs, or 'semantical typos', gave me somewhat of a desparate feeling, partly because I still have 30 unit tests to fix (those that have broken anyway, no idea how many), and there are some larger programs among those. I think it could easily take another week to fix all tests, and make some more actual modifications to the current iterative analysis, that I would like to finish before considering the first milestone to be reached.

For example, it seems my unboxing technique is not going to work well with contours that can be merged.. I would also very much like to spend more time on the iterative analysis itself (istead of bugfixing :/), i.e. compacting contours together, better cleaning out of the allocation site table, working with lists that never flow to an assignment, and be able to merge non-singleton upper bounds together if it is clear they cannot be split later on.

CVS

2005-07-12T10:29:00.000-07:00

I made several not too interesting changes today. I finally got around to fixing the [x,y] issue though. I also fixed some old unit tests again, and added some more, and spent some time hunting obscure bugs. I added some asserts which will help debug the iterative algorithm later on. Most interestingly though, I started working with CVS, and committed all my changes using this.

I had used CVS before, but I had already forgotten that it was just fun to use, and that it actually helps single-developer teams as well. Having a history can be very useful, especially for chaotic programmers like myself. Because it can be lonely though, using CVS by myself, I am going to force one of my mentors to submit at least one patch :-)

Today was sort of a grunt work day. My plan is to work on adding some new features later today or tomorrow (more aggressively combine contours; compact the contour table; rebuild the allocation site table so that it won't accumulate a mess), and then get all unit tests working, as well as add some more that I should've done before. When all this is done (I'm guestimating about a week), I consider my first milestone to have been reached, and I will start adding non-list classes to the mix, classes with multiple class variables, and be frustrated about how many new bugs this will cause :)

Controlled Explosions

2005-07-11T02:21:00.000-07:00

Type inference is really a simple problem, with a simple solution. Just consider each allocation site separately, apply the cartesian product algorithm and you're done. You will have a simple implementation and almost perfect precision. Unfortunately, there are 'some' scaling issues of course.. Let's compare it to chess. Chess is also a simple problem, with a simple solution. Just calculate all possibilities over the next 100 moves and Kasparov will look like a beginner..

However, while there exist nice AI techniques to make simple computers play chess very well, as far as I know, the scalability problem of type inference methods has not yet been convincingly solved in the scientific literature. It might be just a matter of time, with promising techniques such as CPA and IFA. The chess problem, of course, has been researched over a much longer period of time, and by many more people, so we can be hopeful.

However, combining CPA and IFA will not be as straight-forward as I would have thought (ain't it ever.) By initially using a single contour for non-simple types, CPA doesn't blow up for these types, but because of the single contour many simple types will now become polluted when they interact with such 'overloaded' contours, again blowing up CPA. (Consider getting an int from an int list, then using it as a argument.) A solution might be to limit the size of cartesian products during the first iterations, or perhaps even to use 0CFA..

In any case, I guess my priority right now is to get everything working precisely and (hopefully) correctly. It has to _work_ first for larger programs, before I can fine-tune stuff and incorporate butt-ugly heuristics, as well as the neighbour's dog for improving scalability. I'm trying not to think about other scalability problems presented by larger programs, caused by inheritance and the proportionally increased usage of dynamic features (e.g. reflection).

In other words, I don't think I will be able to bootstrap the compiler any time soon (picture a snake with his tail in his mouth.. do snakes have tails??). I actually thought it would be possible to do during my Master's project. Then again, maybe I would have chosen something UML'ish if I had known the difficulties. IMO, it would be great, however, to actually _have_ an open source engine that is precise and works for not-too-large Python programs (say up to around a few thousand lines), that are programmed in a C++-like style.

Small features, bugfixes

2005-07-10T13:14:00.000-07:00

Today I worked all over the map. Maybe the most interesting aspects are that nested types and truly polymorphic containers don't crash the compiler anymore.. :-) They actually seem to work. The following example compiles and runs fine for example:

def duplll(x):             # x: [list(A)]
    return [x]             # [list(list(A))]

a = duplll([1])            # [list(list(int))]
b = duplll([1.0])          # [list(list(float))]

def ident(x):              # x: [list(list(A))]r
    return x               # [list(list(A))]
def meuk(x):               # x: [list(list(A))]
    return ident(x)        # [list(list(A))]

c = meuk(a)                # [list(list(int))]
d = meuk(b)                # [list(list(float))]

def makel(x):              # x: [list(A)]
    return [x]             # [list(list(A))]

def dupl(x):               # x: [list(list(A))]
    return [makel(x[0])]   # [list(list(list(A)))]

dupl([[1]])                # [list(list(list(int)))]

y = [[('1',)]]             # [list(list(tuple(str)))]
dupl(y)                    # [list(list(list(tuple(str))))]

d = [[1]]                  # [list(list(int))]
d = [[1.0]]                # [list(list(float))]
d                          # [list(list(pyobj))]

It contains a polymorphic call chain ('meuk' and 'ident'), nested (in the first iteration even recursive) types and a truly polymorphic container in the end. It's nice to see all the C++ crap that is generated just for the last assignment, especially considering that in Python often much more involved datastructures are used than a list of lists of floats (I'll show some nice examples later on :-))

d = ((list[list[pyobj *] *] *)(new list[list[double] *>(1,
   new list[double](1, new double(1.0)))));

The cast is necessary because C++ won't (rightly) accept the assignment otherwise, and the float is allocated on the heap, because that's how I currently represent 'confused' objects (it can't be unboxed, because floats and integers are confused inside the container.) I believe it's a nice example of how static type checking gets in the way of programming. I dare not show the entire generated C++ program :-)

Other than the above, I fixed many small bugs, rediscovered my affinity for unit testing, made some old unit tests work again and improved the splitting at confluence points (by actually looking at which creation sites come in via the data flow edges - for example, the two edges may provide the same sets, in which case splitting is not very useful.)

Still, there is so much more to do it makes me feel a bit discouraged at the moment. I'll just have to take it feature by feature and bug by bug at a time.. sometimes I feel like the guy in 'Touching the Void'. Watch the movie and you'll know what I mean :-)

Integration Blues

2005-07-09T13:52:00.000-07:00

Okay, so it took me most of the day to be able to support '[x]'. And it still doesn't work perfectly, for example '[x,y]' will require more work. At least I know where the problems lie now, and '[x]' suffices for debugging the iterative analysis. This is because using '[]' several times makes these allocation sites looks alike, obfuscating debug output. The problem was that I did not anticipate object contours to change during analysis, so in the end I just had to make it a bit more dynamic..

With debugging now much easier, it actually became fun to debug some more problems I found in the iterative analysis. To make debugging even more fun, I picked up my habit again of adding unit tests for every new piece of code that I wrote, especially those causing the tiniest of problems. At the moment, no known bugs remain, just.. let's call them 'missing features'.

I guess tomorrow I will start messing around with finding some corner cases, and see how the algorithm works for truly polymorphic containers (when an instance variable of a container object actually takes on different types during run-time). Of course throwing ints and floats into a single list doesn't have to be very efficiently supported (there are probably cases where it's useful, but I haven't seen them). However, in case of inheritance hierarchies, it would be nice if lists with objects of classes from the same hierarchy don't blow up the analysis.. :)

Scaling up

2005-07-08T11:31:00.000-07:00

I spent most of today debugging silly problems, that started to appear as I was feeding the compiler with larger examples. In a codebase of about 5000 lines simple things can become hard to find. It looks like I found the last of them, as I can't find a smallish 'list' example that doesn't work anymore. For example, an extended version of the example in my previous posting, now with 15 allocation sites and several functions (ident, dupl, makel) nicely converges to these 2 object contours:

1: ImmutableSet([])
2: ImmutableSet([class int_])
3: ImmutableSet([class float_])
4: ImmutableSet([])
5: ImmutableSet([])
unused [4, 5, 1]

As can be seen, in total 5 intermediate object contours are created, as the compiler splits and merges contours during each iteration. Although some steps of the iterative analysis as I've implemented it are slow (for example, by checking whether a tuple of tuples is in some Set), the theoretical complexity of the whole is greatly reduced, as CPA will create a boatload less templates when there are fewer object contours!

My next step will be to clean this stuff up some more, e.g. remove unused contours after each iteration, fix the fact that '[x]' is not supported, and start looking at other classes than list. At some point I will also have to start looking at nested and recursive types, and start thinking about termination issues.. shudder!!

John Plevyak

2005-07-07T13:48:00.000-07:00

Since John Plevyak wrote his PhD thesis almost ten years ago, I decided to ask him how he views the state of the solutions for handling data polymorphism today. Unexpectedly, I received a detailed answer within minutes. It appears he is still (or again) working on his iterative method, and is actually planning to release an open source inference engine at some point in the future. How cool! :D

Administrative Issues

2005-07-07T11:26:00.000-07:00

I spent the day working on various administrative issues. Since allocation sites inside function templates are 'thrown' away after each CPA iteration, we need to record previously deduced type information for them, which have to be inserted again if similar templates are created in the next iteration. This becomes quite some administration, because these allocation may be located in templates created for argument types whose contours may be split or merged in between iterations.

First, each allocation site is given an (AST node, argument product) identifier. Based on this, a (currently global) table is maintained with currently deduced type information for each allocation site, and updated as contours change. The following more complicated example code is now analyzed correctly. The allocation sites inside 'dupl' templates are dependent on the 'y' argument, whose contour at some point is split. It goes too far to explain all this in detail, so here is the code:

def ident(x):                            # x: [list(A)]r
    return x                             # [list(A)]
a = []                                   # [list(int)]
a = []                                   # [list(int)]
a = []                                   # [list(int)]
b = []                                   # [list(float)]

ident(a).append(1)                       # []
ident(b).append(1.0)                     # []

def dupl(y):                             # y: [list(A)]
    k = []                               # [list(float)]
    k.append(1.0)                        # []
    l = []                               # [list(A)]
    l.append(y[0])                       # []
    return l                             # [list(A)]

dupl(a)                                  # [list(int)]
dupl(b)                                  # [list(float)]

All lists in the example contain either integers or floats, so we would expect the analysis to end up with two list contours, one for each type. However, the compiler does not merge contours yet that end up with the same contents. Clearly, it can happen that when a contour becomes more precise because of CPA, there already is another contour available with the same precision. Of course then, these contours should be merged, because sharing of contours is what this whole iterative analysis is about..

In the previous situation, six object contours would have been created (one for each syntactic allocation site), potentially blowing up CPA (as it works with the cross-product of actual arguments). Additionally, the types for 'dupl(a)' and 'dupl(b)' would have been imprecise, because a single contour would be used for the different incarnations of 'l' in the different templates for 'dupl'.. It's already nice to see both improved precision and efficiency, although I still have much to do, and probably especially to debug.. :P

This just in: first results

2005-07-06T13:31:00.000-07:00

After building some further infrastructure for the iterative analysis today, and sanitizing other parts of the compiler to cooperate with it, I have the first simple example compiling ('return [x]' is not supported for now :-)):

def makel(x)
   l = []
   l.append(x)
   return l
print makel(1.0)
print makel(1)

During the first iteration, CPA creates two method templates for 'makel', because it sees that it is called with exactly two different argument products: (float,) and (int,). Since we want to iteratively improve upon imprecise object contours, during this first CPA iteration a single object contour is used for the duplicated allocation sites '[]' inside 'makel' (one for each template.) Consequently, an upper bound of {int, float} is inferred for this object contour.

As I explained earlier, after each iteration, the iterative algorithm tries to resolve such imprecisions by splitting object contours. But splitting is not yet necessary for this example to work. By tracing back dataflow paths from inside the two 'append' templates (conflicting assignments to an instance variable), we can conclude that each '[]' allocation site flows only to one of these. The compiler does just that, and splits the object contour in two. Further, it records the newly gained information about these allocation sites in a global table (still messy atm), so that future CPA iterations can seed these allocation sites with the right object contours as they create their templates.

After one more iteration, the compiler concludes that nothing more can change, and generates the following code (nicely parameterizing the types as well, corresponding to another part of my SoC proposal - btw I renamed template brackets to [ and ] because messing with HTML apparently makes me very sad):

int main() {
   printf("%s\n", CS(makel(1.0)));
   printf("%s\n", CS(makel(1)));
}

template [class A] list[A] *makel(A x) {
   list[A] *l;
   l = new list[A]();
   l->append(x);
   return l;
}

Which compiles and runs just fine. Simple object contour splitting also works already (see two postings earlier):

def ident(x):
   return x
a = []
a = []
b = []
ident(a).append(1)
ident(b).append(1.0)

After the first iteration, the compiler notes the conflicting assignments, and sees that multiple creation points 'flow' to both assignments. It tries to 'resolve' this problem by finding a confluence node (in our case, 'x'), and by splitting the respective object contour along the incoming edges of this node. Here, it nicely splits the 'mother' contour into a contour for the two creation points for 'a' and a contour for the creation point for 'b'. In the next iteration, CPA splits the 'ident' function, because a and b now have different object contours, and the imprecision is gone :-)

Appointments

2005-07-06T02:37:00.000-07:00

After a week of becoming increasingly frustrated by all sorts of daily appointments, I am finally free to work on my compiler for the rest of july and august! :D I hope to divert all potential appointments to some later date, except for my motor cycle lessons, which I just didn't want to quit.. This tax thing looks like it will be needing some attention too.. non-US SoC'ers need to find like 20 different forms, fill them in correctly, and send to different places, in order to avoid losing 30% of the total grant. Problem is, my brain immediately goes in stand-by mode each time I start to think about it..

In all, I guess there should be enough time to build something nice to handle many types of data polymorphism. Two months is a lot. I am a bit overwhelmed though, by the complexity of both the problem and Plevyak's solution. It's not going to be easy..

BTW I made my first release. It's highly unstable, but it's there I guess ;) I will stabilize it later, when datapolymorphism is handled better (at all?). It can be downloaded via the Sourceforge link. How to use it? Edit test.py and add some Python code, or use the hello world example it contains; run python ss.py - this will create two C++ files, test.?pp as well as a Makefile - then make and either make run or ./test. The file test.py (and imported module files) will be annotated with the deduced types. (Not always correctly though, as the annotation code is not perfect.) All the code in unit.py has run well at some point (from the same codebase), but at this moment I guess many of the tests will fail. Okay, back to work..

The Problem of Data Polymorphism

2005-07-01T12:15:00.000-07:00

Parametric polymorphism refers to the ability of functions to be called with different types of arguments in different contexts. The cartesian product algorithm, or CPA, efficiently separates these contexts from each other, by creating templates for each function, based on the cartesian product of the actual arguments provided at each call site. By connecting each context with certain templates during analysis, these templates do not pollute each other with bogus types. The idea behind CPA is that when different call sites provide similar argument types, these templates can be shared. This makes for a very efficient analysis, and also a very precise one, as it is not limited to a certain call-chain length, as earlier analyses such as NCFA.

However, CPA only considers 'simple' types, such as integers and floats. Because integers and floats always have the same 'behaviour', these types may be merged together during dataflow analysis (i.e. when one integer meets another integer). CPA templates can be created eagerly for these types, as everything is known about them at each call site where they pop up - all integers are the same, so a template made for one integer will be valid and precise for all integers that pass by. For polymorphic containers such as 'list' the story becomes more complicated. Data polymorphism refers to the ability of instance variables to contain different types. Different such types may require different templates to be made. For example, the return type of some function may depend on an instance variable of an argument to that function. Unfortunately, instance variable types cannot be fully known at their allocation site! Consider the following simple example:

def ident(x):
   return x
a = []
a = []
b = []
ident(a).append(1)
ident(b).append(1.0)

Do we create one or two templates for the 'ident' function? As the list contents may not be known as these lists reach the function calls, we cannot eagerly create multiple templates. We cannot merge lists either during dataflow analysis, and then split them later, when we find out more about their contents, as this could leave the dataflow network in an inconsistent state.

A naive solution, called 1CFA, is to create separate 'class templates' for each allocation site, in effect giving each allocation site its own type. This slows down the process, and is still not precise, because allocation sites may be duplicated as part of templates, again giving rise to possibly differently used polymorphic containers. Splitting these duplicated allocation sites would quickly make for an intractable computation.

A better solution adapts itself to the actual data polymorphism used in the program (the way CPA adapts itself to the actual parametric polymorphism), so that as many templates as possible can be shared. One solution, already alluded to by Olin Shivers (of NCFA fame), is to iterate the analysis, starting from a very imprecise situation, and trying to improve type information after each iteration. John Plevyak found a practical method to implement this idea. Its first iteration is just 0CFA, which means that all similar types are merged, e.g. all lists. By looking at the dataflow graph in a backward fashion, starting at conflicting assignments to a single instance variable, it is possible to locate so-called 'imprecision points'. In the above example, if we start inside the two append templates (CPA creates one for integer and one for float cases), and we look backwards, we find that there flow types from different allocation sites into the formal argument of 'ident'. By splitting the list type in two, one for each incoming dataflow edge at this imprecision point, the respective imprecision can be 'removed', because CPA will now create different templates for 'ident' during the next iteration! By repeatedly splitting types, based on imprecision points, Plevyak's analysis 'adapts' itself to the data polymorphism in the program. Heuristics are probably needed for splitting decisions, because splitting too little means many iterations, and splitting too much means CPA might blow up.

Actually, when Plevyak developed the above method, CPA did not yet exist. His approach also encompassed means of handling parametric polymorphism precisely, but reportedly it was not very efficient. As the developer of CPA alluded to in his PhD thesis, it would be nice to try and combine Plevyak's data-iterative approach with CPA. Over the following weeks, I will try to implement such a combination, although I am a bit wary about potential problems I might encounter. As the first iteration will be just 0CFA, there will be almost no precision - how to select imprecision points that, when split, will actually help? What if assignment types are not singleton sets, or what if there are many different combinations of assignment types? What about inheritance? How do we maintain information about duplicated allocation sites between iterations? How do we terminate efficiently in the face of many polymorphic containers? I guess I will have to find out..

Summer of Code

2005-06-29T14:32:00.000-07:00

In yet another amazing move, Google has decided to pay 410 students to work on open source software during summer. These students have been selected via 'mentoring organisations', which will guide them through the program, as well as judge their results. Hopefully the program will be a resounding success, and Google will be able to repeat it next year, or even set a new trend!

I was very fortunate to be working on something interesting to one of these organisations (the Python Software Foundation, or PSF) as part of my Master's Thesis project, and that I was just planning on adding several large features this summer. Of course, I would have worked on them anyway, but morale was going down, and receiving a google t-shirt is excellent motivation! (The money comes in handy too..) I am very glad to have been selected.

My mentors will be Jeremy Hylton and Brett Cannon, both well known in the Python community and working for Google at the moment. I look forward to interacting with them during the program, and hopefully learning a lot from them. On the university side, my advisor has been and will be Koen Langendoen, co-author of the book 'Modern Compiler Design'.

During the program, I will try to post an update on my progress and experiences at least once every few days. Thanks for reading, and I appreciate any comments!