Skip to content
7 October 32011 / Robin Wellner

The Déjà Vu virtual machine

It has been a while since I posted here. Not that I’ve been sitting on my hands. A lot has happened the past three months.

For example, I took up Déjà Vu again. The implementation had some problems, or rather one big problem: the C stack.

You see, the Déjà interpreter has two functions step_eval and getnextnode which call each other recursively, while walking the source tree. A simple function in Déjà Vu is often three or four nodes deep, so calling a function in Déjà Vu can easily add eight functions that are called recursively. CPython uses the C stack for that. The C stack is rather limited in size, so the interpreter usually can’t handle more than a node depth of a few hundred nodes, and that includes recursive function calls.

Now, there are other implementations of Python that don’t have that limitation, but I don’t want to require the user to use Stackless or PyPy or something else. It is possible to increase the size of the C stack, but that’s a workaround and only works for applications of less than an arbitrary size. I deemed neither solution acceptable.

So what then?

My reasoning was as follows: the recursion of the interpreter is the problem, so I have to make it not recurse any more. Thus I wrote a function called flatten, which made the tree a list of instructions. (Actually, some parts kept a tree shape, but those were limited and unlikely to cause problems). Then I did nothing with it for several months.

When I got started on it again, I decided the code to flatten the tree could easily be used to generate byte code. I then spent a while thinking of useful opcodes and other low-level decisions. When that was done, I had a pretty good idea how I wanted to do the byte code and the virtual machine. I wrote several functions and adapted flatten, to produce proper byte code.

Although this byte code is a binary format, I wrote it for portability, so the compiler would not be needed by users of Déjà Vu programs.

I started writing a virtual machine in C, in code as clean and portable as possible.

As regular readers* will know, I am a high-level thinking guy, so C isn’t my forte, especially for writing virtual machines. I found a sensible way to implement stacks and values that can have multiple types, and I think I know how I can handle return stacks and closure stacks, but there’s still a long road ahead.

At the current state, it has a garbage collector: reference counting plus the synchronous method of cycle collection described in Concurrent Cycle Collection in Reference Counted Systems.

* Ha! As if!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: