For the sake of this post, I’m going to pretend to know what metaprogramming* is.  Yeah, so tinypy** totally has that.  At least, since the parser and compiler in tinypy is written in tinypy, you are able to modify those modules on-the-fly and add new features into the tinypy language.  (Not that you’d want to, but certain other languages get so uppity about being able to do that, I figured I’d plug for tinypy here.)

For example, (at present) tinypy doesn’t have support for decorators.  I’ve always liked decorators, so I made this code (a zip of main.py, deco.py***, and test.py) so that if you have a main.py:

import deco
import test

When the deco module is loaded, it cleanly**** adds decorator support into the tokenize, parse, and encode modules of tinypy.  Then when the test module is loaded, it is able to use decorator syntax.  Yay!  This mostly thanks to the top down operator precedence implementation in tinypy.

So now, if say, you have some crazy idea for how the $ operator should be used in bigpy, you can go ahead and use metaprogramming to add it into tinypy and show all your friends how awful your new syntax looks and have a working proof-of-concept!  Yay!

* feel free to enlighten me
** it’s got a mailing list now, join in on all the fun!!
*** only 611 bytes :)  They were pretty simple to implement, since they really just mean: “given ‘@a \n def b …’ do ‘def b … \n b=a(b)’”
**** Since all the language features are stored in dictionaries, it’s “pretty easy” to add new symbols / operators.  (Or remove features, or whatever!)

Its been a long two months getting this project to the 1.0 state. Here it is:

tinypy1.zip | tinypy.tgz | svn://www.imitationpickles.org/tinypy/tags/1.0.0

$ python build.py
$ ./tinypy-sdl julia.py *
$ ./tinypy your-program-goes-here.py

The win32.zip includes the tinypy.exe and tinypy-sdl.exe binaries, so you can skip the building process.

Features include the ability to parse and compile to bytecode a pretty decent subset of python code. Its got a pretty simple API, incremental garbage collection, and a handful of builtin functions. The vm supports strings, dicts, lists, numbers, functions, methods, and custom data types. tinypy even has exotic features like list comprehensions, variable and named function arguments, inheritance, and exceptions with tracebacks. All this in just 64k** of code!!

I also had some fun this past weekend testing tinypy “in the field” making an OpenGL tetris knock-off. My apologies to Alexey Pajitnov for my misguided contribution of tinypy to the open source stack. win32.zip | svn://www.imitationpickles.org/ld105/trunk

I hope you enjoy checking out tinypy - I’ve had a pretty wild ride building it.

*julia.py included is a low-res “realtime” jula fractal demo. I felt like rendering a mandelbrot for this article.

**See README.txt for my definition of 64k. It’s close enough.

Updates - I’ve got it all fitting in 64k*. It’s amazing how many functions that don’t do anything you can come across if you look around long enough. Not to mention how many little things you can trim out that don’t actually do anything. I have no idea where all this cruft comes from, but having a nice suite of tests sure is helpful for re-working stuff. I also cut out a bunch of stupid features nobody would ever use**. I was able to reduce the number of native types from 9 to 7.

One of the challenges I faced was trying to fix up the incremental garbage collection. My initial implementation was rather inefficient and caused some odd problems with how I wanted to code things. I was using a dict to store all the “white” items, which caused loads of dict hash lookups.

So in my mind I crafted a grand vision on how to accomplish this goal. I would adjust all objects (sans numbers) to contain a pointer to some data which would have some header data for the GC to do some bookkeeping in. Great! However, when I implemented this, I found that a number of problems presented themselves: I had to perform a malloc for each and every string that I used, which killed performance, actually making things 2-3x slower. I also noticed that the weird struct I defined was maybe a bit less standards compliant. This attempt was a wash.

So I re-crafted my grand vision. This time I would do the same thing. Brilliant aren’t I? Anyway, the results were basically the same. Who’d've thunk? It was slower again, this time I was quite confused by it, since I had worked around some of the string issues. I also found that the API for creating new strings wasn’t quite as “clean” as my original simple one. This caused some issues in the exception handling mechanism. I had to toss this try as well.

At this point, having re-mangled the code twice and having poor results, I suspected something else might be wrong. My brain was turning into mush. Each time I had completely edited my “tp.h” with all my struct changes in one go. I decided to make a final attempt at reworking tinypy, this time *one* data type at a time. After each data type I added I was able to see if my changes caused any performance issues. I found that my function data type was the culprit. My hashing function (borrowed from lua) wasn’t getting enough entropy and was generating massive collision cases! A few tweaks later, this was resolved. I was able to also craft the string interface to be backwards compatible with the original string interface while also working with the new garbage collection. This “step by step” approach got me to my goal. All said and done, with a bit more tweaking, I was able to *double* the speed of tinypy

Lesson learned - even if it’s only 64k, it’s better to do changes step by step instead of in one big go. valgrind and callgrind are your friends. (Although I found that tinypy doesn’t entirely agree with callgrind … ideas anyone?)

To wrap up this excessively long post about me trying to get code to work — this weekend I’m hosting a Ludum Dare warmup compo. I’m going to give tinypy a run in the “real world”. Here’s to hoping! Next week I plan on releasing the 1.0 version of tinypy.

I’m also thinking about renaming some of my files. And although pylang, dumbparse, and dump2vm have a certain rustic charm, I wonder if I’d do better with names like goat, gorilla, and sausage. Or maybe more descriptive names like tokenator, parsalizer, and bytecodatron.

svn://www.imitationpickles.org/tinypy/trunk for the brave. If you want a zip or an exe, check back in a week. I’ll have all those and more (a game!) Note that I’ve split the SDL dependency out of the main tinypy code. tinypy-sdl.c lets you run my julia.py example. The bootstrapping process also has a final step of compiling with -O3, which I think might not work for everyone. It gives pretty good speed gains on my system, so if it works for you, great!

*python mk64k.py will do a bit of search-n-replace to cut it down to size. I’ve resisted doing anything really ghastly, the code is still indented and readable. See README.txt for more disgusting details on how I cheat to pretend this is 64k.

**Okay, I’ve used some of those features. But hey, this is a 64k implementation, I’ve got to trim the fat.

So.. hey, it’s done. Basically. tinypy is a 64k implementation of a subset of python. It can bootstrap itself into a single executable that can compile python files to bytecode and run them on a VM. Thanks to everyone who gave feedback thus far on this project. Double thanks to allefant who listened to me blab about it endlessly on irc for the last month

I found all the stuff people told me about for parsing was a huge help. This article http://javascript.crockford.com/tdop/tdop.html was what I ended basing it on. It’s almost like magic, but it makes for a really simple easy to follow parser. The VM is based on stuff I read about the lua VM.

So what’s next? I need to let it sit around for a week and then I’ll do a “release” I guess. I’ve gotta pick a license or something for it (probably MIT? I’m open for suggestions.) I’m also mulling over possible names. Maybe “tinypy” .. or “wedge” .. or “cupcake” .. or “garter”. Hmmn.

Anyway - I’m sure I’ll be tweaking it a bit over time, but I’m pretty happy to have it to this point now. I probably won’t do much with it until I try making a game with it. Right now it depends on libgc for garbage collection. If someone clever out there can implement a garbage collector for it that works in like 2-4k, that’d be better. My brain is pretty spent.

For the brave: svn://www.imitationpickles.org/tinypy/trunk or tinypy.zip. The following is only tested under linux, but I bet it would work in any bash environment. Maybe.

$ python boot.py

Will run the 3-phase testing + bootstrapping process. It will first use python to generate the .tpc files for the compiler. Second phase uses the VM to generate those same files. Third phase uses the bootstrapped tinypy executable to “re-bootstrap” tinypy to get the final version. The -nopos option strips out debug info from the .tpc files.

$ ./tinypy julia.py

Run the julia demo without dependence on *anything* but the tinypy executable.

$ ./tinypy your_own_code.py

Will do something! Probably print out a pretty traceback about how you tried to use a python feature / module that tinypy doesn’t support “batteries not included”

Well, I got two of my favorite python features added in - list comprehensions [x*x for x in range(1,5)] and fancy arguments test(1,2,a=3,*c,**d).

Adding list comprehensions was painless, took only a few minutes. The arguments change was rather difficult because I had to add more rules to the parser, change how the bytecode was outputted, and rework all the internal calling stuff in the VM. Now every function takes a single argument of type ‘params’ which can contain all the details of a call.

I’ve also added in better error handling. Errors print out a backtrace of the function calls and lines of code. This is making debugging everything much easier.

I’m also finding that the more features I add, well, the slower things get. I’m also coming up against my 64k limit, so I’ve moved my tests out of the core code into a separate tests.py file to ensure that I don’t “trim down the tests” to give myself more space The tests I’ve made have been invaluable in making it possible to do big changes fairly quickly.

Next on the agenda - either bootstrapping, or making a game with it

For the brave: svn://www.imitationpickles.org/tinypy/trunk ; python tests.py ; ./run_julia_o3 (not very fast)

I’ve managed to build a simple VM into tinypy - modeled after the lua VM. It’s register based and “stackless” in the “it doesn’t use the C-stack” sense of the word. (Not in the, it does anything fancy like “stackless python” does sense.)

‘ve just reached the 64k mark, so that means anything I add into the code will require me to clean up other code to save space. I’ve already done a bit of that with good results. The one rule I follow in shortening code is that the code must retain readability, if not improve it.

Garbage collection is rather complicated, so I think I’ve decided to continue to leave that to libgc. I read some literature on the matter, and it sounds like I could write one, but it probably wouldn’t be very good. I’ve put it at the bottom of my TODO.txt list in the section labeled “Probably not going to happen”.

At present tinypy supports basic python code with functions and loops and lists and dicts and classes. At least, in some basic form. I’m looking towards adding in list comprehensions and *args **nargs to tinypy as those are two of my favorite python features. After that I’ve got a handful of functions I want to write and then some packaging work.

For the curious svn://www.imitationpickles.org/tinypy/trunk - ./run_julia_o3 to see it all happen. It depends on python to compile the bytecode (we’re not bootstrapped yet), libgc, and SDL.

Well, things continue to come along with tinypy. I’ve been experimenting with a lot of different things with this. Some things I’ve tried:

- Assumed all infix operations were for numbers - was able to get quite a bit of speed at the sacrifice of things being “obvious”. I’ve disabled this for now, since I figure if you really want speed, you’d be using C anyways, not “tinypy”.

- Tried switching from passing around 16 byte structures to pointers to those structures. This didn’t work so well, because given my simple implementation it meant that any time any operation happened, another 16 bytes had to be allocated to store my floats. Not so hot for rendering fractals This caused a 10x slow-down. I reverted that out, but I copied that stuff to a branch for reference.

- I learned more about how libgc works. Basically, you need to use the GC_MALLOC and GC_REALLOC functions instead of the libc ones. libgc takes care of the rest. Also, if you integrate with libsdl (or some such library), you’ll need to do the memory management for it. There is hope - gc.h includes a function called GC_REGISTER_FINALIZER which makes it possible to trigger finalizers when an object is about to be freed. I’ve added some code to do this to tp.c, but haven’t tested it yet. That’ll get more testing when I start using libsdl for a game.

At present I’m debating between two options — leaving tinypy as-is and just cleaning it up, thus using it as a C code generator. Or changing it into a bytecode generator and writing a simple VM to run the bytecode. Advantages and disadvantages as I see them:

C code generator:

• Quite simple and reasonably fast. Optimizations and goodies come from the compiler.
• Really swell “FFI” (all functions are accessed directly and available as functions in C. Really, this means, no notable FFI at all.)
• No need to do much more than tweaking stuff, etc.
• No “eval” unless I use tinycc. Even then, no “safety”.

Bytecode + VM:

• I’d be able to implement exceptions and tracebacks and stuff
• I’d be able to build a “safe” environment for running scripts “eval”
• Things would be a bit slower, but not much
• FFI would be more complex (but I could probably work around that by auto-generating some goodies for people)

I’ll have to think about it for a bit .. I might just try making a fun little game with tinypy as-is, and work to keep the FFI really clean. And if I feel like upgrading tinypy, try to do it in such a way as to not break my “clean” FFI.

If you care to take a peak: svn://www.imitationpickles.org/tinypy/trunk - ./run_julia to see the julia demo. Must have libsdl and libgc installed. It’s sort of slow, but if you want to see it “fast” set JIT_DISABLE = False at the top of dumpout.py

So .. I had a hard time resisting working on my 64k version of “python”. I’ve been able to get quite a few features into it and I’ve gotten my julia demo up to near-C speed as well as tamed the crazy memory problems I was having.
I suppose the question I ponder is “why bother”? Well:

• It’s fun
• I’m learning the basics of parsing, code generation.
• It might even be somewhat useful!

The first two don’t require much explanation, the third (usefulness?):

• By keeping the codebase < 64k, it will be readable by mortals
• By generating C code, it can build self-contained binaries easily
• It has a really simple “FFI” which auto-generates many of the “FFI” wrappers for you
• It’s sort of fast now (no promises for anything real)

It, of course, isn’t python, it just looks a bit like it. Notable differences are:

• Access to members is like lua / javascript. x["y"] and x.y mean the same thing.
• Most infix operators only work with numbers. “x”+”y” won’t work. (Rational: makes numerical math fast)
• It’s missing (and will never have) a bunch of really nice features. Syntax checking is notably weak. Maybe I should scrap my parser, etc and just use python’s.
• No exception handling. Incorrect use of anything will result in a seg fault.

Notable similarities:

• Language contains separate list and dict types. I thought about doing like lua / javascript / php and having a single type, but it just didn’t feel right.
• It’s indented (duh)
• Garbage collection via libgc

Well .. that’s about it. I expect before I’m done I’ll make a game with it, to see how it works in the real world. I’ve got a few more things on my TODO list to get done first. If you are brave, check out svn://www.imitationpickles.org/tinypy/trunk and run ./run_julia (linux) to see the julia demo.

Oh, and for all you “test first” folks, I’ve (more or less) been doing that. It’s made development considerably easier. See the bottom of “pylang.py” “dumbparse.py” and “dumpout.py” for all the testing fun.

To satisfy some sick curiosity of mine, I decided to write a miniature version of python in less than 64k of code. The code includes a tokenizer (which works rather well) a parser (which sort of works ) a translator (which does the job). All of those bits are written in python. The last bit is the C library I wrote to handle all the grit. That part isn’t so good.

To sum up, my implementation does very little, and what it does, it does very slowly. Most of the speed is spent up in memory allocation (my best guess). I wish I had a julia screenshot to show you, but I don’t think I have the patience, nor the RAM, to provide you with the pleasure.

If you wish to witness the horrors, feel free to check out svn://www.imitationpickles.org/tinypy/trunk … Please don’t look too closely. I think if I really want to work on this sort of stuff my time would be better spent either:

• Learning the python C API or ctypes so I can do stuff without SWIG. (I’ve liked SWIG, but all the magic makes me nervous.)
• Contribute to shed-skin, and add some features I’d like to it
• Contribute to PyPy-Rpython, and add some features I’d like to it
• Wait for py3k, where hopefully someone will write some magic code that uses the swell function annotation features to make fast things happen.

Of my options, learning the C-Python API (or maybe ctypes) is probably the easiest answer - I’d get all the fun of python, and I’d get my C speed. Between working on shed-skin and PyPy — my feeling is that I really wish shed-skin generated C code or that PyPy-Rpython wasn’t so huge and scary. All that said, I’ll probably just wait for py3k and hope

*today is opposite day!

My last post explained my frustration trying to get pyrex to do *anything*. Since then, several people posted solutions and e-mailed me with more ideas (thanks allefant and Filip Wasilewski). My review was focused on the usability of pyrex as a python->C translator, since that’s what I was working on with both shed-skin and pypy/rpython. It didn’t hold up so well. This is because … pyrex ISN’T a python->C translator.

pyrex is its own special language that contains both python and C stuff. pyrex does not do type inference. What pyrex provides is a way to mix both python and python-like C code together in the same files. The trick to understanding pyrex is to know where the line between python and C is in pyrex.

Here are some of the gotchas I experienced. I wasn’t able to detail them in my previous post because I didn’t really “get it”. Now I think I do, so I’ll explain some stuff so you can try out pyrex without getting confused the way I did:

Gotcha #1: float() is a python function

cdef int a
cdef float b
a = 3
b = float(a)

Solution: use pyrex’s casting to avoid massive object-conversion speed penalties

b = <float>a

Gotcha #2: pyrex doesn’t do type inference

def set_video(int w, int h):
    s = Surface()
    s.surf = SDL_SetVideoMode(w,h,32,0)
    return s

pyrex: Cannot convert 'SDL_Surface *' to Python object

Solution: to access your C-members you must declare the variable’s type first

def set_video(int w, int h):
    cdef Surface s
    s = Surface()
    s.surf = SDL_SetVideoMode(w,h,32,0)
    return s

Gotcha #3: def makes python functions - which are slow

def set_pixel(self,int x, int y, int color)

Solution: To be able to access a fast version of a method in C and be able to access the same method in python you must define two versions of it

cdef _set_pixel(self,int x, int y, int color):
    pass # do this really fast

def set_pixel(self,int x, int y, int color):
    return self._set_pixel(x,y,color)

All that said, I think pyrex is really neat for writing extensions!  One of the best features it has is properties (which are like descriptors, only easier).  Just be careful if you use it to not mistake it for python.  Lastly, by using those tips I was able to get my julia example to be full speed.