PyPy

On November 12, 2006 I did the first surviving commit of my RPython based Prolog implementation Pyrolog into the PyPy repository. I had been working on it since spring 2006 already. In that year we were finishing up the first PyPy EU research project and I was finishing up my Bachelor studies at Uni Düsseldorf. Since it's now 20 years later I wanted to write a personal retrospective post on this project. Pyrolog never had any real users, but it still led to some interesting research and influenced a number of other RPython projects.
2006/2007 The first year
2008/2009 JIT developments on the PyPy side
2009-2010 New Pyrolog Architecture: More Continuations
2011/2012 Widening Prolog support
2012/2013 Compressed Terms
2022-2024 RPython implementation of Effekt
As part of the EU project we had promised lots of things, including implementing some constraint programming in PyPy. For this strand of the work I learned Prolog by reading Clocksin and Mellish's Programming Prolog [CM2003] and later the Art of Prolog [SS1994].
In March 2006, the PyPy project partner Logilab organized a sprint in UCLouvain in Louvain-la-Neuve (Belgium), with Peter van Roy and some of the researchers working on Gecode. The plan was to add some kind of unification and constraint solving to PyPy. The Logilab people were quite inspired by the Van Roy/Haridi book [VH2004] and I later studied his Prolog implementation survey paper [VanRoy1994].
In 2006 I also attended my advisor Michael Leuschel's Prolog lectures in Düsseldorf. During that I started working on a Prolog interpreter in RPython, later called Pyrolog. Much of the early commit history is lost unfortunately, it didn't make the Subversion->Mercurial jump correctly and I don't know where the codespeak archives are now.
Pyrolog's first incarnation had a fairly straightforward implementation of unification in object-oriented RPython code. Logical variables stored an index, with their bindings stored in a global array at that index.
Pyrolog Memory Layout from [Bolz2007]
That version represented choice points by having exception handlers on the interpreter level, and backtracking via throwing exceptions, catching them further up. It used a continuation-based architecture for storing the calls left to do. Those success continuations were stored on the heap and continuously allocated and consumed. This approach was taken from Paul Tarau's BinProlog ([TB1990], [Tarau1992]) and also based on some other Prolog papers [Lindgren1994] [Neumerkel1995].
To deal with deep recursion that Prolog programs typically do, that version of Pyrolog relied on RPython's stackless transformation [BR2007D071], which would unwind the host stack (i.e. the C stack) and store its information on the host heap if host stack overflow was getting close. When storing C stack frames on the heap in this way, we also did some amount of tail call optimization. We were super into this idea at the time. However, it turned out not to be too practical, making the binary twice as large and slower, so eventually we removed it again.
I also experimented with using the first RPython JIT on that version of Pyrolog. That JIT was a partial-evaluation-based method JIT and managed to speed up some small Python programs. I don't think it did very much for Pyrolog though.
The performance of that version of Pyrolog was quite disappointing. In my B.Sc. thesis [Bolz2007] I did some measurements against SWI and Sicstus Prolog. Sicstus was often an order of magnitude faster than Pyrolog at this point.
In the thesis I also implemented a way to call into Prolog from Python code and had a case study where I implemented a Tic-Tac-Toe GUI in Python, with the game logic in Prolog.
Shortly after finishing my thesis, I changed the variable representation: instead of indexing into a global binding array, each variable object stored its own binding. The exception-based backtracking architecture stayed in place for another two years.
After the EU project finished we started working on various new architectural ideas for the RPython meta-JIT. Armin Rigo, me and some others wrote two new prototypes. We weren't happy with them, so in 2008 Armin and I started experimenting with a prototype for a new trace-based JIT written in Prolog. We used Prolog because its pattern matching and ease of meta-programming allowed us to experiment more easily with different designs.
Towards the end of 2008 and throughout 2009 Armin, Maciej Fijałkowski, me and others started porting the design back to RPython and called it pyjitpl5 (the "pl" in the name stands for "Prolog"). This is still the base of the current PyPy meta-JIT compiler and became the subject of the second (smaller) PyPy EU project in the Eurostars program.
We eventually published a paper about the Prolog version of the JIT [BLR2010] at LOPSTR 2009.
After working mostly on PyPy and the new JIT in 2008 and 2009 I started working on Pyrolog again over the 2009 Christmas break. Since the stackless transformation wasn't compatible with the new JIT I had to switch to a different architecture, still used today. The first version of the Pyrolog architecture had already stored success continuations on the heap. The goal of this refactoring was to also store the failure continuations as reified RPython objects.
This had the effect that the host stack use is completely flat when interpreting Prolog calls. The state needed to continue with Prolog execution is always stored in continuation objects on the heap. The interpreter is therefore dealing with two continuations, one activated upon success, and one on failure.
Additionally, there is a (segmented) trail object which stores the variable bindings that need to be undone when backtracking. Failure continuations have a reference to the part of the trail they need to backtrack to, when activated.
The downside of this approach is that the interpreter continuously has to allocate heap data for all the success and failure continuations. This puts a lot of pr