I’ve learned a lot about python by implementing tinypy. Today I was thinking over my re-work of classes, objects, and inheritance in tinypy (not in trunk yet). I noted how in tinypy, I will be able to change the class of an object via a function call (a-la lua):

class A: pass
class B: pass
x = A() # x is an instance of A
setmeta(x,B) # x is now an instance of B !!!

So I thought to myself, I wonder if python can do that. Well, it can, and as per usual, its solution is quite elegant:

class A: pass
class B: pass
x = A() # x is an instance of A
x.__class__ = B # x is now an instance of B !!!

So, lesson of the day — you can dynamically change the class of an object in bigpy. Which, actually, I’ve sometimes wanted to do, I just didn’t realize I *could* do it.

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!)

1. The only bit I remember from that conversation is all the stuff about Canadian global domination.  Let me tell you, if Mike Fletcher has his way, we’re doomed!  (Maybe we’re doomed either way, but be sure your passport is ready when we have to head north!)
2. I remember peaking into the pycon-dev room at one point and Doug was giving a lecture on menu structures in websites.  He said the pycon navigation was stored completely independently of all the modules used by pycon.  I think that’s great.  I’ve been thinking about it ever since.
3. I do most all my dev at home on my linux system.  My laptop last year was loaded with XP and I found it painful to do work on at pycon.  So this year, the day before pycon, I loaded it up with Ubuntu.  Which was a mistake.  It *sort* of worked, in a kind of the network didn’t exactly always work and the video driver didn’t always work .. and then it got worse .. but I won’t name names
4. Which brings me to two happier points, which are points 5 and 6 in this list.
5. Sean was quite swell and set me up a personal hard-line during the sprints when I needed to get some work done :)  Yay!
6. I was told about PyPE, which is a nifty python editor for windows :)  I’m having to do some win32 dev lately (see previous post), so having that on hand is great!  I like it.  I was able to do about 5 hours of dev on it this evening, and I think the main complaint I had was I was using a laptop keyboard.  If you like kate, this is the editor for you.

So I thought of an idea for pycon2009 … A GONG SHOW!  Here’s how it would work:

• People sign up for 5 minute slots.
• A panel of 3 judges preside.
• Each person gets 1 minute to get into their talk.
• After that point, the panel is free to “gong” the person any time it gets dull or uninteresting or for any other reason.
• Each judge will score each talk on a 1-10 scale.
• The winner will get a prize!

Good idea?  Comments?  I think it would be a fun thing to do in addition to the normal lightning talks.  Maybe I’ll propose it for a 45 minute talk space next year.

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.

Yay - I got incremental garbage collection added into tinypy. It took a good deal of troubleshooting, but thanks to valgrind (and thanks to the people who pointed me to it) after some work I got all the memory leaks and crashes worked out. This is a nice step forward, since it enabled me to eliminate the libgc dependency.

tinypy is slightly larger than 64k, but I have vague hopes that will be remedied* at some point. In the meantime, I’m going to take a bit of a break from it. On Feb. 23rd, the Ludum Dare community is having a “warm-up” compo, and I shall give tinypy a real try at that point. After that I will probably put out the 1.0 release.

All that said, its been quite a learning experience for me. I learned how to tokenize, parse, generate byte code, build a virtual machine, and do garbage collection. I’m hoping this will make looking at the innards of other languages seem less intimidating in the future.

* if you’re a clever C / python coder and feel like taking a look at the tinypy code and give me ideas on how to compact the code a bit, I’d sure appreciate it. It’s 4k too big right now, and I’d really like to fix that. I’m cool with any suggestions though I won’t implement anything unless it leaves the code just as (if not more) readable. Please examine the README.txt to find out how I calculate the code size first.

svn://www.imitationpickles.org/tinypy/trunk or tinypy.zip for the brave. I’ve managed to compile it under mingw32 (Minimalist GCC for windows) as well as using GCC under MacOSX. Perhaps for the 1.0 release I’ll include binaries

For giggles I tried to write a garbage collector to replace libgc in tinypy. I tried doing a tri-color incremental collector. I couldn’t get it to work, so I ended up switching it to be more of a tri-color mark and sweep collector.

The result of my mark and sweep collector was a 40% reduction in speed. I’m guessing ol’ libgc was designed with a bit more cleverness than mine Anyway, for now I’ve moved my “tgc” development into a branch of tinypy svn://www.imitationpickles.org/tinypy/branches/tgc if you want to see it in action.

Stuff to read: Memory Management Reference and libgc.

Needless to say, the Hairy Chestival is probably one of the most influential video games of all time.  Which is why, of course, BRAWNDO’s new commercial includes it!

Not to mention, it includes the world’s most bzawesome goat, CUZCO!!

So if you’re still sitting here NOT watching the video, maybe you should start WATCHING IT!!

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”

I’ve been out of town for the last few days, so I haven’t done much to tinypy. However, I have realized that my current “dumbparse” module is pretty dumb. Two things are wrong with it:

• It’s slow. Noticeably so with 8k modules, etc.
• It’s dumb. It doesn’t give “useful” parsing errors.

I’ve read up a bit on LR, LL, top-down, and a whole bunch of kinds of parsers and it all sounds a bit magical to me. I’d be glad for some suggestions or ideas on where I could go from here. My requirements are:

• must be pretty compact (I want my parser to be < 12k in size)
• must not get exponentially slower on larger files (but it doesn’t have to be blindingly fast, just decent)
• must be able to notice where a syntax error is (indicated by token - I’ve got a good tokenizer already)
• must parse “basic” python and be written in that as well (see my current files for examples)

Thanks! svn://www.imitationpickles.org/tinypy/trunk - for the brave