Shed Skin 0.0.14, 1600-line program

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

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

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

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

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

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?

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

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

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

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

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

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

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

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

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

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

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!

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

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

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.