20 Years of Pyrolog

Context¶

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.

2006/2007 The first year¶

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.

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.

2008/2009 JIT developments on the PyPy side¶

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.

2009-2010 New Pyrolog Architecture: More Continuations¶

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.

# the simplified main interpreter loop

def interpret(sc, fc, trail):
    while not sc.is_done():
        try:
            sc, fc, trail = sc.activate(fc, trail)
        except UnificationFailed:
            sc, fc, trail = fc.fail(trail)

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 pressure on the RPython GC. Also, term unification still uses the host stack, so unifying very deep terms can still be a problem and lead to implementation-level recursion errors.

JIT support¶

The real goal of the refactoring was to make the interpreter more JIT-friendly. Since the interpreter doesn't use recursion for Prolog calls any more, the loops at the Prolog level (expressed as recursion) can be traced by the JIT. All the continuous allocations of continuations can be optimized by the allocation removal of the RPython JIT. If all this works correctly, the performance of Pyrolog becomes very good, often beating Sicstus by a significant factor on suitable microbenchmarks.

Unfortunately this is mainly the case for code with very predictable control flow, ideally with nice loops. Since the main appeal of Prolog is to do backtracking search, control flow is typically not very predictable for interesting more Prolog-like programs. As soon as the control flow becomes too complicated and unpredictable, the continuations survive beyond the region that the JIT optimizes and have to be allocated on the heap again. Therefore Pyrolog has quite extreme performance cliffs.

We wrote a paper about this version of Pyrolog for PPDP 2010 [BLS2010] (together with Michael Leuschel and my later colleague David Schneider). That conference was super interesting and important for me. I met Paul Tarau (who invented BinProlog, one of the inspirations of Pyrolog. He later gave an excellent Prolog talk at the virtual machine summer school in 2016), Olivier Danvy (whose paper [BD2004] I should have cited. Genuinely one of the nicest people), Kenichi Asai (who had worked on partial evaluation and reflection) and several others. At that point during my PhD I was feeling relatively demotivated, and my chats with these researchers were incredibly encouraging.

On the bus trip to Gmunden, where the conference dinner took place, somebody explained how to implement unification of cyclic terms (i.e. rational trees) to me. Unfortunately I am not quite sure who it was any more, I think it might have been Thierry Martinez. This led to me implementing support for cyclic term unification. I still like that trick a lot and tried to explain it to Phil Zucker earlier this year. I hope to blog about it eventually. For a fun use case see my blog post on rational tree unification for dfa minimization.

2011/2012 Widening Prolog support¶

During 2011 and 2012 I supervised several Bachelor/Master theses that worked on adding features to Pyrolog. In the process we added support for Prolog modules, DCGs, attributed variables, freeze and when. All these were done by my excellent students Sven Hager and René Bartelmus. This left the fundamental execution model intact (with some small additions). I also spent some time improving the error messages of Pyrolog to for example show backtraces on Prolog exceptions.

Pyrolog also served as an early test case for David Schneider's ARM JIT backend. In January 2011, he could already run Pyrolog microbenchmarks with the JIT on a BeagleBoard, while the backend still needed debugging before running more complex Python benchmarks.

In 2012 I mostly wrote my PhD thesis [Bolz2012]. It contains a chapter on Pyrolog based on the PPDP 2010 paper. That chapter argues that the fact that Pyrolog works relatively well demonstrates that the RPython meta-JIT can be used for quite a wide variety of languages.

There was also another chapter that compared how a meta-tracing JIT works with more classical partial evaluation approaches. The code of that was again written in Prolog and originally presented here on the blog.

At this point I left Düsseldorf. In the winter semester 2012/13 I spent half a year in Berlin at Hasso-Plattner-Institute with my PhD co-advisor Robert Hirschfeld as a postdoc. In 2013 I started working with Laurie Tratt at King's College.

At this point the main Pyrolog story kind of ends. There were only some small improvements happening in the succeeding years. However, Pyrolog ideas led to followup research in other projects, and I want to discuss some of them.

2012/2013 Compressed Terms¶

One experiment that I had tried to get working in Pyrolog in 2010 and 2011, but ended up never merging, was compressed terms. The idea comes from the observation that certain patterns of terms occur repeatedly. For example an association list has terms of the form [A/B|C] repeated. Instead of allocating separate list and pair objects for every entry, the plan was to share a description of that structure, the "shape", and store each entry's keys and values in a flat storage data structure. This would make every entry have less indirection and use fewer words of memory.

However, I had never managed to get that working in Prolog, because variable bindings can create these patterns after the fact. A field that initially contained an unbound variable could later refer to a whole structured term, so the opportunities for compression changed after construction, and again on backtracking.

When I was at HPI for six months in winter 2012/2013 I worked with Tobias Pape to implement the same compression idea for a simpler functional language called lamb, later Theseus. Tobias pushed this approach much further in the following years [PBH2015], [PBH2017]. My hope was to eventually understand the problem well enough to be able to port it back to Pyrolog. But that part never happened. We did eventually try those ideas in Pycket though.

2013 Unipycation¶

In 2013 I started working in London. The goal of our research project there was "language composition". Edd Barrett, Laurie Tratt and I implemented combined RPython implementations of PyPy plus another language, with a way to integrate the two involved languages. The first pair we tried was combining PyPy and Pyrolog in a project called Unipycation [BBT2013]. The project made it possible to call into Prolog from Python and vice versa. The RPython meta-JIT can optimize across this language boundary and even perform cross-language inlining. Unfortunately we never found super compelling use-cases for this combination.

2013 Pycket¶

Also in 2013 I started working on Pycket, an RPython implementation of Racket, together with Sam Tobin-Hochstadt and Jeremy Siek. Later Tobias Pape and Spenser Bauman also joined. The Pycket architecture was indirectly inspired by the Pyrolog continuation approach. We implemented the CEK machine relatively directly in RPython. This also used a flat host stack and it made implementing things like call/cc relatively straightforward [Pycket2015].

One of the great new ideas we adopted in Pycket was "false loop filtering", originally from IBM Research [HWISN2011]. This takes calling context into account when tracing function calls and prevents the tracing JIT from recognizing "false loops", which would never run for more than one iteration. I always wanted to port this idea back to Pyrolog and implemented a prototype, but never really polished it enough to be able to merge it.

Another implementation technique in Pycket was to make continuation objects much smaller, to make the case of them escaping to the heap less bad. This approach did make it back to Pyrolog.

2022-2024 RPython implementation of Effekt¶

I left King's College in 2016 and have been back at Uni Düsseldorf (half-time) since 2017. In 2022 I started working with Marcial Gaißert and Jonathan Brachthäuser on an RPython implementation of Effekt and related languages. This was an implementation of a JIT for effect handlers in RPython [GBB2025]. Again, it uses the approach of having reified stack frames/continuations which can then be manipulated by the interpreter, adding effect handlers on top of it.

2026 Git Conversion¶

This fall, I got an email by a researcher about Pyrolog and realized that it was 20 years old this year. Subsequently I merged various strands of the surviving mercurial history into a new Github repo, fixed some bugs and implemented some convenience features.

Conclusion¶

Pyrolog has always been a much more researchy project than PyPy itself. While PyPy tries to be an open source project and "product", Pyrolog never had any users and even I never used it for anything beyond small demos, some research prototypes, and benchmarking. While some quite interesting research came out of Pyrolog, I think having some real applications running on top of it would have given me a much more concrete goal to improve it towards.

Implementation wise, Pyrolog inherited some of the problems of PyPy. In PyPy we were quite strongly focused on peak performance in the first few years, leading to performance cliffs. Pyrolog also had those in even stronger form, due to the constant allocations of the interpreter.

Some very interesting interaction between Pyrolog, various Prolog JIT prototypes and the PyPy/RPython meta-JIT emerged. Pyrolog forced the RPython JIT to support quite different execution models which made it applicable to other languages than just object-oriented imperative ones.

I still have no concrete use case for Pyrolog so it's kind of unlikely that I will work much more on it right now. But my development on this project was always quite bursty, so I am bound to return to it at some point in the future.

I would like to end with thanking all the contributors, my other collaborators and the long line of Prolog researchers that inspired and encouraged me.

Bibliography¶