{"article":{"slug":"20-years-of-pyrolog","title":"20 Years of Pyrolog","subtitle":null,"summary":"CF Bolz-Tereick looks back on 20 years of Pyrolog, an RPython-based Prolog implementation begun in 2006 inside PyPy, covering its role in PyPy's JIT work, continuation-based architecture, compressed terms, Unipycation, Pycket, Effekt and a 2026 git conversion.","content_type":"blog_post","language":"en","canonical_url":"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html","author":{"name":"CF Bolz-Tereick","url":"https://pypy.org/authors/cf-bolz-tereick.html","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"PyPy","url":"https://pypy.org/","listing_slug":null,"listing":null},"topics":[{"name":"programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"open-source","slug":"open-source","url":"https://listedarticles.com/topics/open-source"},{"name":"compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"},{"name":"research","slug":"research","url":"https://listedarticles.com/topics/research"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":3070,"reading_minutes":13,"published_at":"2026-11-12T08:16:45.000Z","added_at":"2026-11-12T17:13:14.504Z","updated_at":"2026-11-12T17:13:14.504Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/20-years-of-pyrolog","markdown_url":"https://listedarticles.com/articles/20-years-of-pyrolog.md","example":false,"citation":"CF Bolz-Tereick, PyPy. \"20 Years of Pyrolog.\" 12 Nov 2026. https://pypy.org/posts/2026/11/20-years-of-pyrolog.html (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html"},"body_markdown":"On November 12, 2006 I did the [first surviving commit](https://github.com/cfbolz/pyrolog/commit/6653a22) of my RPython based\nProlog implementation **Pyrolog** into the PyPy repository. I had been working\non it since spring 2006 already. In that year we were finishing up the first\nPyPy EU research project and I was finishing up my Bachelor studies at Uni\nDüsseldorf. Since it's now 20 years later I wanted to write a personal\nretrospective post on this project. Pyrolog never had any real users, but it\nstill led to some interesting research and influenced a number of other RPython\nprojects.\n\n## Context\n\nAs part of the EU project we had promised lots of things, including\nimplementing some constraint programming in PyPy. For this strand of the work I\nlearned Prolog by reading Clocksin and Mellish's Programming Prolog [[CM2003]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#cm2003)\nand later the Art of Prolog [[SS1994]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#ss1994).\n\nIn March 2006, the PyPy project partner [Logilab](https://www.logilab.fr/) organized a sprint in UCLouvain\nin Louvain-la-Neuve (Belgium), with [Peter van Roy](https://webperso.info.ucl.ac.be/~pvr/) and some of the researchers\nworking on [Gecode](https://www.gecode.org/). The plan was to add some kind of unification and constraint\nsolving to PyPy. The Logilab people were quite inspired by the Van Roy/Haridi\nbook [[VH2004]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#vh2004) and I later studied his Prolog implementation survey paper\n[[VanRoy1994]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#vanroy1994).\n\nIn 2006 I also attended my advisor [Michael Leuschel's](https://www.cs.hhu.de/en/research-groups/software-engineering-and-programming-languages/our-team/team/michael-leuschel/) Prolog lectures in\nDüsseldorf. During that I started working on a Prolog interpreter in RPython,\nlater called Pyrolog. Much of the early commit history is lost unfortunately,\nit didn't make the [Subversion->Mercurial](https://pypy.org/posts/2010/12/pypy-migrates-to-mercurial-3308736161543832134.html) jump correctly and I don't know\nwhere the codespeak archives are now.\n\n## 2006/2007 The first year\n\nPyrolog's first incarnation had a fairly straightforward implementation of\nunification in object-oriented RPython code. Logical variables stored an index,\nwith their bindings stored in a global array at that index.\n\n![Memory layout of the interpreter](https://pypy.org/images/2026-pyrolog-memory-orig.svg)\n\nPyrolog Memory Layout from [[Bolz2007]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bolz2007)\n\nThat version represented choice points by having exception handlers on the\ninterpreter level, and backtracking via throwing exceptions, catching them\nfurther up. It used a continuation-based architecture for storing the calls\nleft to do. Those success continuations were stored on the heap and\ncontinuously allocated and consumed. This approach was taken from Paul Tarau's\nBinProlog ([[TB1990]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#tb1990), [[Tarau1992]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#tarau1992)) and also based on some other Prolog papers\n[[Lindgren1994]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#lindgren1994) [[Neumerkel1995]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#neumerkel1995).\n\nTo deal with deep recursion that Prolog programs typically do, that version of\nPyrolog relied on RPython's *stackless transformation* [[BR2007D071]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#br2007d071), which\nwould unwind the host stack (i.e. the C stack) and store its information on the\nhost heap if host stack overflow was getting close. When storing C stack frames\non the heap in this way, we also did some amount of tail call optimization. We\nwere super into this idea at the time. However, it turned out not to be too\npractical, making the binary twice as large and slower, so eventually we\nremoved it again.\n\nI also experimented with using the first RPython JIT on that version of\nPyrolog. That JIT was a partial-evaluation-based method JIT and managed to\nspeed up some small Python programs. I don't think it did very much for Pyrolog\nthough.\n\nThe performance of that version of Pyrolog was quite disappointing. In my B.Sc.\nthesis [[Bolz2007]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bolz2007) I did some measurements against [SWI](https://www.swi-prolog.org/) and [Sicstus Prolog](https://sicstus.sics.se/).\nSicstus was often an order of magnitude faster than Pyrolog at this point.\n\nIn the thesis I also implemented a way to call into Prolog from Python code and\nhad a case study where I implemented a Tic-Tac-Toe GUI in Python, with the game\nlogic in Prolog.\n\nShortly after finishing my thesis, I [changed the variable representation](https://github.com/cfbolz/pyrolog/commit/04307d2):\ninstead of indexing into a global binding array, each variable object stored\nits own binding. The exception-based backtracking architecture stayed in place\nfor another two years.\n\n## 2008/2009 JIT developments on the PyPy side\n\nAfter the EU project finished we started working on various new architectural\nideas for the RPython meta-JIT. Armin Rigo, me and some others wrote two new\nprototypes. We weren't happy with them, so in 2008 Armin and I started\nexperimenting with a prototype for a new trace-based JIT [written in Prolog](https://pypy.org/posts/2008/06/hi-all-some-news-from-jit-front-7534695765973581706.html). We\nused Prolog because its pattern matching and ease of meta-programming allowed\nus to experiment more easily with different designs.\n\nTowards the end of 2008 and\nthroughout 2009 Armin, Maciej Fijałkowski, me and others started porting the\ndesign back to RPython and called it [pyjitpl5](https://github.com/pypy/pypy/commit/bbb1996550b) (the \"pl\" in the name stands for\n\"Prolog\"). This is still the base of the current PyPy meta-JIT compiler and\nbecame the subject of the second (smaller) PyPy EU project in the [Eurostars](https://pypy.org/posts/2010/12/oh-and-btw-pypy-gets-funding-through.html)\nprogram.\n\nWe eventually published a paper about the Prolog version of the JIT [[BLR2010]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#blr2010)\nat LOPSTR 2009.\n\n## 2009-2010 New Pyrolog Architecture: More Continuations\n\nAfter working mostly on PyPy and the new JIT in 2008 and 2009 I started working\non Pyrolog again over the 2009 Christmas break. Since the stackless\ntransformation wasn't compatible with the new JIT I had to switch to a\ndifferent architecture, still used today. The first version of the Pyrolog\narchitecture had already stored success continuations on the heap. The goal of this\nrefactoring was to also store the *failure continuations* as [reified RPython\nobjects](https://github.com/cfbolz/pyrolog/commit/fc1a4f9).\n\n```\n# the simplified main interpreter loop\n\ndef interpret(sc, fc, trail):\n    while not sc.is_done():\n        try:\n            sc, fc, trail = sc.activate(fc, trail)\n        except UnificationFailed:\n            sc, fc, trail = fc.fail(trail)\n```\n\nThis had the effect that the host stack use is completely flat when\ninterpreting Prolog calls. The state needed to continue with Prolog execution is always\nstored in continuation objects on the heap. The interpreter is therefore\ndealing with two continuations, one activated upon success, and one on failure.\n\nAdditionally, there is a (segmented) trail object which stores the variable\nbindings that need to be undone when backtracking. Failure continuations have a\nreference to the part of the trail they need to backtrack to, when activated.\n\nThe downside of this approach is that the interpreter continuously has to\nallocate heap data for all the success and failure continuations. This puts a\nlot of pressure on the RPython GC. Also, term unification still uses the host\nstack, so unifying very deep terms can still be a problem and lead to\nimplementation-level recursion errors.\n\n### JIT support\n\nThe real goal of the refactoring was to make the interpreter more JIT-friendly.\nSince the interpreter doesn't use recursion for Prolog calls any more, the loops at the Prolog\nlevel (expressed as recursion) can be traced by the JIT. All the continuous\nallocations of continuations can be optimized by the allocation removal of the\nRPython JIT. If all this works correctly, the performance of Pyrolog becomes\nvery good, often beating Sicstus by a significant factor on suitable\nmicrobenchmarks.\n\n![/images/2026-pyrolog-vmgen.svg](https://pypy.org/images/2026-pyrolog-vmgen.svg)\n\nPyrolog VM Generation vs. Runtime from [[BLS2010]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bls2010)\n\nUnfortunately this is mainly the case for code with very predictable control\nflow, ideally with nice loops. Since the main appeal of Prolog is to do\nbacktracking search, control flow is typically not very predictable for\ninteresting more Prolog-like programs. As soon as the control flow becomes too\ncomplicated and unpredictable, the continuations survive beyond the region that\nthe JIT optimizes and have to be allocated on the heap again. Therefore Pyrolog has\nquite extreme performance cliffs.\n\nWe wrote a paper about this version of Pyrolog for PPDP 2010 [[BLS2010]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bls2010) (together with\nMichael Leuschel and my later colleague David Schneider). That conference\nwas super interesting and important for me. I met Paul Tarau (who invented\nBinProlog, one of the inspirations of Pyrolog. He later gave an excellent [Prolog\ntalk](https://www.youtube.com/watch?v=SRYAMt8iQSw) at the virtual machine summer school in 2016), Olivier Danvy (whose\npaper [[BD2004]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bd2004) I should have cited. Genuinely one of the nicest people),\nKenichi Asai (who had worked on partial evaluation and reflection) and several\nothers. At that point during my PhD I was feeling relatively demotivated, and\nmy chats with these researchers were incredibly encouraging.\n\n![https://www3.risc.jku.at/conferences/ppdp2010/photos/img_8487.jpg](https://www3.risc.jku.at/conferences/ppdp2010/photos/img_8487.jpg)\n\n[Group photo at PPDP 2010](https://www3.risc.jku.at/conferences/ppdp2010/photos/index.html)\n\nOn the bus trip to Gmunden, where the conference dinner took place, somebody\nexplained how to implement unification of cyclic terms (i.e. rational trees) to\nme. Unfortunately I am not quite sure who it was any more, I think it might\nhave been Thierry Martinez. This led to me [implementing support for cyclic\nterm unification](https://github.com/cfbolz/pyrolog/commit/8d51938). I still like that trick a lot and tried to explain it to\n[Phil Zucker](https://www.philipzucker.com/) earlier this year. I hope to blog about it eventually. For a fun\nuse case see my blog post on [rational tree unification for dfa minimization](https://cfbolz.de/posts/dfa-minimization-using-rational-trees-in-prolog/).\n\n## 2011/2012 Widening Prolog support\n\nDuring 2011 and 2012 I supervised several Bachelor/Master theses that worked on\nadding features to Pyrolog. In the process we added support for Prolog modules,\n[DCGs](https://www.swi-prolog.org/pldoc/man?section=DCG), [attributed variables](https://www.swi-prolog.org/pldoc/man?section=attvar), `freeze` and `when`. All these were done by my\nexcellent students Sven Hager and René Bartelmus. This left the fundamental\nexecution model intact (with some small additions). I also spent some time\nimproving the error messages of Pyrolog to for example show backtraces on\nProlog exceptions.\n\nPyrolog also served as an [early test case](https://pypy.org/posts/2011/01/jit-backend-for-arm-processors-5994810755839586463.html) for David Schneider's ARM JIT\nbackend. In January 2011, he could already run Pyrolog microbenchmarks with the\nJIT on a BeagleBoard, while the backend still needed debugging before running\nmore complex Python benchmarks.\n\nIn 2012 I mostly wrote my PhD thesis [[Bolz2012]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bolz2012). It contains a chapter on Pyrolog based\non the PPDP 2010 paper. That chapter argues that the fact that Pyrolog works\nrelatively well demonstrates that the RPython meta-JIT can be used for quite a\nwide variety of languages.\n\nThere was also another chapter that compared how a meta-tracing JIT works with\nmore classical partial evaluation approaches. The code of that was again\nwritten in Prolog and [originally](https://pypy.org/posts/2012/01/simple-tracer-for-flow-graph-language-6930951890987229484.html) [presented](https://pypy.org/posts/2012/02/optimizing-traces-of-flow-graph-4169388883059419385.html) [here on the blog](https://pypy.org/posts/2012/02/larger-example-for-flow-graph-language-6139699450091061040.html).\n\nAt this point I left Düsseldorf. In the winter semester 2012/13 I spent half a\nyear in Berlin at [Hasso-Plattner-Institute](https://hpi.de/) with my PhD co-advisor [Robert\nHirschfeld](https://hirschfeld.org/) as a postdoc. In 2013 I started working with [Laurie Tratt](https://tratt.net/laurie/) at\nKing's College.\n\nAt this point the main Pyrolog story kind of ends. There were only some small\nimprovements happening in the succeeding years. However, Pyrolog ideas led to\nfollowup research in other projects, and I want to discuss some of them.\n\n## 2012/2013 Compressed Terms\n\nOne experiment that I had tried to get working in Pyrolog in 2010 and 2011, but\nended up never merging, was compressed terms. The idea comes from the\nobservation that certain patterns of terms occur repeatedly. For example an\nassociation list has terms of the form `[A/B|C]` repeated. Instead of\nallocating separate list and pair objects for every entry, the plan was to\nshare a description of that structure, the \"shape\", and store each entry's keys\nand values in a flat storage data structure. This would make every entry have\nless indirection and use fewer words of memory.\n\nHowever, I had never managed to get that working in Prolog, because variable\nbindings can create these patterns after the fact. A field that initially\ncontained an unbound variable could later refer to a whole structured term, so\nthe opportunities for compression changed after construction, and again on\nbacktracking.\n\nWhen I was at HPI for six months in winter 2012/2013 I worked with Tobias Pape to\nimplement the same compression idea for a simpler functional language called\nlamb, later [Theseus](https://github.com/shiplift/theseus/). Tobias pushed this approach much further in the following years\n[[PBH2015]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#pbh2015), [[PBH2017]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#pbh2017). My hope was to eventually understand the problem well\nenough to be able to port it back to Pyrolog. But that part never happened. We\ndid eventually try those ideas in Pycket though.\n\n## 2013 Unipycation\n\nIn 2013 I started working in London. The goal of our research project there was\n\"language composition\". Edd Barrett, Laurie Tratt and I implemented combined\nRPython implementations of PyPy plus another language, with a way to integrate\nthe two involved languages. The first pair we tried was combining PyPy and\nPyrolog in a project called Unipycation [[BBT2013]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bbt2013). The project made it\npossible to call into Prolog from Python and vice versa. The RPython meta-JIT\ncan optimize across this language boundary and even perform cross-language\ninlining. Unfortunately we never found super compelling use-cases for this\ncombination.\n\n## 2013 Pycket\n\nAlso in 2013 I started working on [Pycket](https://github.com/pycket/pycket), an RPython implementation of Racket,\ntogether with [Sam Tobin-Hochstadt](https://samth.github.io/) and [Jeremy Siek](https://luddy.iu.edu/people/siek-jeremy.html). Later Tobias Pape and\nSpenser Bauman also joined. The Pycket architecture was indirectly inspired by\nthe Pyrolog continuation approach. We implemented the CEK machine relatively\ndirectly in RPython. This also used a flat host stack and it made implementing\nthings like `call/cc` relatively straightforward [[Pycket2015]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#pycket2015).\n\nOne of the great new ideas we adopted in Pycket was \"false loop filtering\",\noriginally from IBM Research [[HWISN2011]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#hwisn2011). This takes calling context into\naccount when tracing function calls and prevents the tracing JIT from\nrecognizing \"false loops\", which would never run for more than one iteration. I\nalways wanted to port this idea back to Pyrolog and implemented a prototype,\nbut never really polished it enough to be able to merge it.\n\nAnother implementation technique in Pycket was to make continuation objects\nmuch smaller, to make the case of them escaping to the heap less bad. This\napproach *did* [make it back to Pyrolog](https://github.com/cfbolz/pyrolog/commit/59fb825).\n\n## 2022-2024 RPython implementation of Effekt\n\nI left King's College in 2016 and have been back at Uni Düsseldorf (half-time)\nsince 2017. In 2022 I started working with [Marcial Gaißert](https://pl.cs.uni-tuebingen.de/team/gaissert/) and [Jonathan\nBrachthäuser](https://b-studios.de/about) on an RPython implementation of [Effekt](https://effekt-lang.org/) and related languages.\nThis was an implementation of a JIT for [effect handlers](https://effekt-lang.org/docs/concepts/effect-handlers) in RPython [[GBB2025]](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#gbb2025).\nAgain, it uses the approach of having reified stack frames/continuations which\ncan then be manipulated by the interpreter, adding effect handlers on top of it.\n\n## 2026 Git Conversion\n\nThis fall, I got an email by a researcher about Pyrolog and realized that it\nwas 20 years old this year. Subsequently I merged various strands of the\nsurviving mercurial history into a new [Github repo](https://github.com/cfbolz/pyrolog), fixed some bugs and\nimplemented some convenience features.\n\n![/images/2026-pyrolog-screenshot.png](https://pypy.org/images/2026-pyrolog-screenshot.png)\n\nScreenshot of Pyrolog\n\n## Conclusion\n\n![/images/2026-pyrolog-activity-by-month-authors.svg](https://pypy.org/images/2026-pyrolog-activity-by-month-authors.svg)\n\ncommits per month on the main branch, by author\n\nPyrolog has always been a much more researchy project than PyPy itself. While\nPyPy tries to be an open source project and \"product\", Pyrolog never had any\nusers and even I never used it for anything beyond small demos, some\nresearch prototypes, and benchmarking. While some quite interesting research\ncame out of Pyrolog, I think having some real applications running on top of it\nwould have given me a much more concrete goal to improve it towards.\n\nImplementation wise, Pyrolog inherited some of the problems of PyPy. In PyPy we\nwere quite strongly focused on peak performance in the first few years, leading\nto performance cliffs. Pyrolog also had those in even stronger form, due to the\nconstant allocations of the interpreter.\n\nSome very interesting interaction between Pyrolog, various Prolog JIT\nprototypes and the PyPy/RPython meta-JIT emerged. Pyrolog forced the RPython\nJIT to support quite different execution models which made it applicable to\nother languages than just object-oriented imperative ones.\n\nI still have no concrete use case for Pyrolog so it's kind of unlikely that I\nwill work much more on it right now. But my development on this project was\nalways quite bursty, so I am bound to return to it at some point in the future.\n\nI would like to end with thanking all the contributors, my other collaborators\nand the long line of Prolog researchers that inspired and encouraged me.\n\n## Bibliography\n\n[[TB1990](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-6)]\n\nP. Tarau, M. Boyer.\n*Elementary logic programs*. PLILP 1990, LNCS 456, pp. 159–173.\n[DOI](https://doi.org/10.1007/BFb0024183).\n\n[[Tarau1992](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-7)]\n\nPaul Tarau.\n*BinProlog: a continuation passing style Prolog engine*.\nPLILP 1992, LNCS 631, pp. 479–480. Poster.\n\n[[SS1994](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-2)]\n\nLeon S. Sterling, Ehud Y. Shapiro.\n*The Art of Prolog: Advanced Programming Techniques*.\n2nd edition, MIT Press, 1994.\n[Publisher page](https://mitpress.mit.edu/9780262691635/the-art-of-prolog/).\n\n[[Lindgren1994](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-8)]\n\nThomas Lindgren.\n*A Continuation-Passing Style for Prolog*.\nInternational Logic Programming Symposium, 1994, pp. 603–617.\n\n[[VanRoy1994](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-4)]\n\nPeter Van Roy.\n*1983–1993: The Wonder Years of Sequential Prolog Implementation*.\nJournal of Logic Programming 19–20, 1994, pp. 385–441.\n[DOI](https://doi.org/10.1016/0743-1066(94)90031-0);\n[author-hosted technical report PDF](https://webperso.info.ucl.ac.be/~pvr/PRL-TR-36.pdf)\n(DEC Paris Research Laboratory report 36, December 1993).\n\n[[Neumerkel1995](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-9)]\n\nUlrich Neumerkel.\n*Continuation Prolog: A new intermediary language for WAM and BinWAM\ncode generation*. Post-ILPS 1995 Workshop on Implementation of Logic\nProgramming Languages, 1995.\n[PDF](https://www.complang.tuwien.ac.at/ulrich/papers/PDF/contp95.pdf).\n\n[[CM2003](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-1)]\n\nWilliam F. Clocksin, Christopher S. Mellish.\n*Programming in Prolog: Using the ISO Standard*.\n5th edition, Springer, 2003.\n[DOI](https://doi.org/10.1007/978-3-642-55481-0).\n\n[[VH2004](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-3)]\n\nPeter Van Roy, Seif Haridi.\n*Concepts, Techniques, and Models of Computer Programming*.\nMIT Press, 2004. ISBN 9780262220699.\n[Publisher page](https://mitpress.mit.edu/9780262220699/concepts-techniques-and-models-of-computer-programming/);\n[author's book page](https://webperso.info.ucl.ac.be/~pvr/book.html).\n\n[[BD2004](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-15)]\n\nDariusz Biernacki, Olivier Danvy.\n*From Interpreter to Logic Engine by Defunctionalization*.\nLOPSTR 2003, revised selected papers, published 2004, pp. 143–159.\n[DOI](https://doi.org/10.1007/978-3-540-25938-1_13),\n[PDF](https://ii.uni.wroc.pl/~dabi/publications/LOPSTR03/biernacki-danvy-lopstr03.pdf).\n\n[[BR2007D071](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-10)]\n\nCF Bolz, Armin Rigo.\n*Support for massive parallelism, optimisation results, practical\nusages and approaches for translation aspects*.\nPyPy Consortium, EU deliverable D07.1, 28 February 2007.\nListed by PyPy as *Massive Parallelism and Translation Aspects*.\n[Official report index](https://doc.pypy.org/index-report.html);\n[report PDF](https://foss.heptapod.net/pypy/extradoc/-/blob/branch/extradoc/eu-report/D07.1_Massive_Parallelism_and_Translation_Aspects-2007-02-28.pdf).\n\n[Bolz2007]\n([1](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-5),[2](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-11))\n\nCF Bolz.\n*A Prolog Interpreter in Python*. Bachelor thesis,\nHeinrich Heine University Düsseldorf, 2007.\n[PDF](https://cfbolz.de/Bolz2007-Bachelorarbeit.pdf).\n\n[[BLR2010](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-12)]\n\nCF Bolz, Michael Leuschel, Armin Rigo.\n*Towards Just-In-Time Partial Evaluation of Prolog*.\nLOPSTR 2009, revised selected papers, LNCS 6037, 2010, pp. 158–172.\n[DOI](https://doi.org/10.1007/978-3-642-12592-8_12);\n[author manuscript](https://stups.hhu-hosting.de/downloads/pdf/BoLeRi09_235.pdf).\n\n[BLS2010]\n([1](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-13),[2](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-14))\n\nCF Bolz, Michael Leuschel, David Schneider.\n*Towards a Jitting VM for Prolog Execution*. PPDP 2010, pp. 99–108.\n[DOI](https://doi.org/10.1145/1836089.1836102);\n[author manuscript](https://stups.hhu-hosting.de/downloads/pdf/BoLeSch2010.pdf).\n\n[[HWISN2011](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-21)]\n\nHiroshige Hayashizaki, Peng Wu, Hiroshi Inoue,\nMauricio J. Serrano, Toshio Nakatani.\n*Improving the Performance of Trace-based Systems by False Loop Filtering*.\nASPLOS XVI, 2011, pp. 405–418.\n[DOI](https://doi.org/10.1145/1950365.1950412);\n[IBM Research publication page](https://research.ibm.com/publications/improving-the-performance-of-trace-based-systems-by-false-loop-filtering).\n\n[[Bolz2012](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-16)]\n\nCF Bolz.\n*Meta-Tracing Just-in-Time Compilation for RPython*.\nPhD thesis, Heinrich-Heine-Universität Düsseldorf, September 2012.\n[Author's thesis page](https://cfbolz.de/phdthesis/);\n[PDF](https://cfbolz.de/stuff/cfbolz-meta-tracing.pdf);\n[university repository](https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=30464).\n\n[[BBT2013](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-19)]\n\nEdd Barrett, CF Bolz, Laurence Tratt.\n*Unipycation: A Case Study in Cross-Language Tracing*.\nVMIL 2013, pp. 31–40.\n[DOI](https://doi.org/10.1145/2542142.2542146);\n[author manuscript](https://tratt.net/laurie/research/pubs/papers/barrett_bolz_tratt__unipycation_a_study_in_cross_language_tracing.pdf).\n\n[[Pycket2015](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-20)]\n\nSpenser Bauman, CF Bolz, Robert Hirschfeld,\nVasily Kirilichev, Tobias Pape, Jeremy G. Siek, Sam Tobin-Hochstadt.\n*Pycket: A Tracing JIT for a Functional Language*.\nICFP 2015, pp. 22–34.\n[DOI](https://doi.org/10.1145/2784731.2784740);\n[author manuscript](https://soft-dev.org/pubs/pdf/bauman_bolz_hirschfeld_kirilichev_pape_siek_tobin_hochstadt__pycket_a_tracing_jit_for_a_functional_language.pdf).\n\n[[PBH2015](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-17)]\n\nTobias Pape, CF Bolz, Robert Hirschfeld.\n*Adaptive Just-in-time Value Class Optimization: Transparent Data\nStructure Inlining for Fast Execution*. SAC 2015.\n[DOI](https://doi.org/10.1145/2695664.2695837);\n[PDF](https://www.hirschfeld.org/writings/media/PapeBolzHirschfeld_2015_AdaptiveJustInTimeValueClassOptimization_AcmDL.pdf).\n\n[[PBH2017](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-18)]\n\nTobias Pape, CF Bolz, Robert Hirschfeld.\n*Adaptive just-in-time value class optimization for lowering memory\nconsumption and improving execution time performance*.\nScience of Computer Programming 140, 2017, pp. 17–29.\nPublished online in 2016.\n[DOI](https://doi.org/10.1016/j.scico.2016.08.003);\n[PDF](https://www.hirschfeld.org/writings/media/PapeBolzHirschfeld_2017_AdaptiveJustInTimeValueClassOptimizationForLoweringMemoryConsumptionAndImprovingExecutionTimePerformance_Elsevier.pdf).\n\n[[GBB2025](https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-22)]\n\nMarcial Gaißert, CF Bolz-Tereick,\nJonathan Immanuel Brachthäuser.\n*Tracing Just-in-Time Compilation for Effects and Handlers*.\nProceedings of the ACM on Programming Languages 9 (OOPSLA2),\nArticle 307, October 2025.\n[DOI](https://doi.org/10.1145/3763085);\n[author publication page](https://pl.cs.uni-tuebingen.de/publications/gaissert2025tracing/);\n[technical report](https://pl.cs.uni-tuebingen.de/publications/gaissert2025tracing.pdf).\n","body_html":"<p>On November 12, 2006 I did the <a href=\"https://github.com/cfbolz/pyrolog/commit/6653a22\" rel=\"nofollow ugc noopener\">first surviving commit</a> of my RPython based\nProlog implementation <strong>Pyrolog</strong> into the PyPy repository. I had been working\non it since spring 2006 already. In that year we were finishing up the first\nPyPy EU research project and I was finishing up my Bachelor studies at Uni\nDüsseldorf. Since it&#39;s now 20 years later I wanted to write a personal\nretrospective post on this project. Pyrolog never had any real users, but it\nstill led to some interesting research and influenced a number of other RPython\nprojects.</p>\n<h2 id=\"context\">Context</h2>\n<p>As part of the EU project we had promised lots of things, including\nimplementing some constraint programming in PyPy. For this strand of the work I\nlearned Prolog by reading Clocksin and Mellish&#39;s Programming Prolog <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#cm2003\" rel=\"nofollow ugc noopener\">[CM2003]</a>\nand later the Art of Prolog <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#ss1994\" rel=\"nofollow ugc noopener\">[SS1994]</a>.</p>\n<p>In March 2006, the PyPy project partner <a href=\"https://www.logilab.fr/\" rel=\"nofollow ugc noopener\">Logilab</a> organized a sprint in UCLouvain\nin Louvain-la-Neuve (Belgium), with <a href=\"https://webperso.info.ucl.ac.be/~pvr/\" rel=\"nofollow ugc noopener\">Peter van Roy</a> and some of the researchers\nworking on <a href=\"https://www.gecode.org/\" rel=\"nofollow ugc noopener\">Gecode</a>. The plan was to add some kind of unification and constraint\nsolving to PyPy. The Logilab people were quite inspired by the Van Roy/Haridi\nbook <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#vh2004\" rel=\"nofollow ugc noopener\">[VH2004]</a> and I later studied his Prolog implementation survey paper\n<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#vanroy1994\" rel=\"nofollow ugc noopener\">[VanRoy1994]</a>.</p>\n<p>In 2006 I also attended my advisor <a href=\"https://www.cs.hhu.de/en/research-groups/software-engineering-and-programming-languages/our-team/team/michael-leuschel/\" rel=\"nofollow ugc noopener\">Michael Leuschel&#39;s</a> Prolog lectures in\nDüsseldorf. During that I started working on a Prolog interpreter in RPython,\nlater called Pyrolog. Much of the early commit history is lost unfortunately,\nit didn&#39;t make the <a href=\"https://pypy.org/posts/2010/12/pypy-migrates-to-mercurial-3308736161543832134.html\" rel=\"nofollow ugc noopener\">Subversion-&gt;Mercurial</a> jump correctly and I don&#39;t know\nwhere the codespeak archives are now.</p>\n<h2 id=\"2006-2007-the-first-year\">2006/2007 The first year</h2>\n<p>Pyrolog&#39;s first incarnation had a fairly straightforward implementation of\nunification in object-oriented RPython code. Logical variables stored an index,\nwith their bindings stored in a global array at that index.</p>\n<figure><img src=\"https://pypy.org/images/2026-pyrolog-memory-orig.svg\" alt=\"Memory layout of the interpreter\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Pyrolog Memory Layout from <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bolz2007\" rel=\"nofollow ugc noopener\">[Bolz2007]</a></p>\n<p>That version represented choice points by having exception handlers on the\ninterpreter level, and backtracking via throwing exceptions, catching them\nfurther up. It used a continuation-based architecture for storing the calls\nleft to do. Those success continuations were stored on the heap and\ncontinuously allocated and consumed. This approach was taken from Paul Tarau&#39;s\nBinProlog (<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#tb1990\" rel=\"nofollow ugc noopener\">[TB1990]</a>, <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#tarau1992\" rel=\"nofollow ugc noopener\">[Tarau1992]</a>) and also based on some other Prolog papers\n<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#lindgren1994\" rel=\"nofollow ugc noopener\">[Lindgren1994]</a> <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#neumerkel1995\" rel=\"nofollow ugc noopener\">[Neumerkel1995]</a>.</p>\n<p>To deal with deep recursion that Prolog programs typically do, that version of\nPyrolog relied on RPython&#39;s <em>stackless transformation</em> <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#br2007d071\" rel=\"nofollow ugc noopener\">[BR2007D071]</a>, which\nwould unwind the host stack (i.e. the C stack) and store its information on the\nhost heap if host stack overflow was getting close. When storing C stack frames\non the heap in this way, we also did some amount of tail call optimization. We\nwere super into this idea at the time. However, it turned out not to be too\npractical, making the binary twice as large and slower, so eventually we\nremoved it again.</p>\n<p>I also experimented with using the first RPython JIT on that version of\nPyrolog. That JIT was a partial-evaluation-based method JIT and managed to\nspeed up some small Python programs. I don&#39;t think it did very much for Pyrolog\nthough.</p>\n<p>The performance of that version of Pyrolog was quite disappointing. In my B.Sc.\nthesis <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bolz2007\" rel=\"nofollow ugc noopener\">[Bolz2007]</a> I did some measurements against <a href=\"https://www.swi-prolog.org/\" rel=\"nofollow ugc noopener\">SWI</a> and <a href=\"https://sicstus.sics.se/\" rel=\"nofollow ugc noopener\">Sicstus Prolog</a>.\nSicstus was often an order of magnitude faster than Pyrolog at this point.</p>\n<p>In the thesis I also implemented a way to call into Prolog from Python code and\nhad a case study where I implemented a Tic-Tac-Toe GUI in Python, with the game\nlogic in Prolog.</p>\n<p>Shortly after finishing my thesis, I <a href=\"https://github.com/cfbolz/pyrolog/commit/04307d2\" rel=\"nofollow ugc noopener\">changed the variable representation</a>:\ninstead of indexing into a global binding array, each variable object stored\nits own binding. The exception-based backtracking architecture stayed in place\nfor another two years.</p>\n<h2 id=\"2008-2009-jit-developments-on-the-pypy-side\">2008/2009 JIT developments on the PyPy side</h2>\n<p>After the EU project finished we started working on various new architectural\nideas for the RPython meta-JIT. Armin Rigo, me and some others wrote two new\nprototypes. We weren&#39;t happy with them, so in 2008 Armin and I started\nexperimenting with a prototype for a new trace-based JIT <a href=\"https://pypy.org/posts/2008/06/hi-all-some-news-from-jit-front-7534695765973581706.html\" rel=\"nofollow ugc noopener\">written in Prolog</a>. We\nused Prolog because its pattern matching and ease of meta-programming allowed\nus to experiment more easily with different designs.</p>\n<p>Towards the end of 2008 and\nthroughout 2009 Armin, Maciej Fijałkowski, me and others started porting the\ndesign back to RPython and called it <a href=\"https://github.com/pypy/pypy/commit/bbb1996550b\" rel=\"nofollow ugc noopener\">pyjitpl5</a> (the &quot;pl&quot; in the name stands for\n&quot;Prolog&quot;). This is still the base of the current PyPy meta-JIT compiler and\nbecame the subject of the second (smaller) PyPy EU project in the <a href=\"https://pypy.org/posts/2010/12/oh-and-btw-pypy-gets-funding-through.html\" rel=\"nofollow ugc noopener\">Eurostars</a>\nprogram.</p>\n<p>We eventually published a paper about the Prolog version of the JIT <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#blr2010\" rel=\"nofollow ugc noopener\">[BLR2010]</a>\nat LOPSTR 2009.</p>\n<h2 id=\"2009-2010-new-pyrolog-architecture-more-continuations\">2009-2010 New Pyrolog Architecture: More Continuations</h2>\n<p>After working mostly on PyPy and the new JIT in 2008 and 2009 I started working\non Pyrolog again over the 2009 Christmas break. Since the stackless\ntransformation wasn&#39;t compatible with the new JIT I had to switch to a\ndifferent architecture, still used today. The first version of the Pyrolog\narchitecture had already stored success continuations on the heap. The goal of this\nrefactoring was to also store the <em>failure continuations</em> as <a href=\"https://github.com/cfbolz/pyrolog/commit/fc1a4f9\" rel=\"nofollow ugc noopener\">reified RPython\nobjects</a>.</p>\n<pre><code># the simplified main interpreter loop\n\ndef interpret(sc, fc, trail):\n    while not sc.is_done():\n        try:\n            sc, fc, trail = sc.activate(fc, trail)\n        except UnificationFailed:\n            sc, fc, trail = fc.fail(trail)</code></pre>\n<p>This had the effect that the host stack use is completely flat when\ninterpreting Prolog calls. The state needed to continue with Prolog execution is always\nstored in continuation objects on the heap. The interpreter is therefore\ndealing with two continuations, one activated upon success, and one on failure.</p>\n<p>Additionally, there is a (segmented) trail object which stores the variable\nbindings that need to be undone when backtracking. Failure continuations have a\nreference to the part of the trail they need to backtrack to, when activated.</p>\n<p>The downside of this approach is that the interpreter continuously has to\nallocate heap data for all the success and failure continuations. This puts a\nlot of pressure on the RPython GC. Also, term unification still uses the host\nstack, so unifying very deep terms can still be a problem and lead to\nimplementation-level recursion errors.</p>\n<h3 id=\"jit-support\">JIT support</h3>\n<p>The real goal of the refactoring was to make the interpreter more JIT-friendly.\nSince the interpreter doesn&#39;t use recursion for Prolog calls any more, the loops at the Prolog\nlevel (expressed as recursion) can be traced by the JIT. All the continuous\nallocations of continuations can be optimized by the allocation removal of the\nRPython JIT. If all this works correctly, the performance of Pyrolog becomes\nvery good, often beating Sicstus by a significant factor on suitable\nmicrobenchmarks.</p>\n<figure><img src=\"https://pypy.org/images/2026-pyrolog-vmgen.svg\" alt=\"/images/2026-pyrolog-vmgen.svg\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Pyrolog VM Generation vs. Runtime from <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bls2010\" rel=\"nofollow ugc noopener\">[BLS2010]</a></p>\n<p>Unfortunately this is mainly the case for code with very predictable control\nflow, ideally with nice loops. Since the main appeal of Prolog is to do\nbacktracking search, control flow is typically not very predictable for\ninteresting more Prolog-like programs. As soon as the control flow becomes too\ncomplicated and unpredictable, the continuations survive beyond the region that\nthe JIT optimizes and have to be allocated on the heap again. Therefore Pyrolog has\nquite extreme performance cliffs.</p>\n<p>We wrote a paper about this version of Pyrolog for PPDP 2010 <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bls2010\" rel=\"nofollow ugc noopener\">[BLS2010]</a> (together with\nMichael Leuschel and my later colleague David Schneider). That conference\nwas super interesting and important for me. I met Paul Tarau (who invented\nBinProlog, one of the inspirations of Pyrolog. He later gave an excellent <a href=\"https://www.youtube.com/watch?v=SRYAMt8iQSw\" rel=\"nofollow ugc noopener\">Prolog\ntalk</a> at the virtual machine summer school in 2016), Olivier Danvy (whose\npaper <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bd2004\" rel=\"nofollow ugc noopener\">[BD2004]</a> I should have cited. Genuinely one of the nicest people),\nKenichi Asai (who had worked on partial evaluation and reflection) and several\nothers. At that point during my PhD I was feeling relatively demotivated, and\nmy chats with these researchers were incredibly encouraging.</p>\n<figure><img src=\"https://www3.risc.jku.at/conferences/ppdp2010/photos/img_8487.jpg\" alt=\"https://www3.risc.jku.at/conferences/ppdp2010/photos/img_8487.jpg\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p><a href=\"https://www3.risc.jku.at/conferences/ppdp2010/photos/index.html\" rel=\"nofollow ugc noopener\">Group photo at PPDP 2010</a></p>\n<p>On the bus trip to Gmunden, where the conference dinner took place, somebody\nexplained how to implement unification of cyclic terms (i.e. rational trees) to\nme. Unfortunately I am not quite sure who it was any more, I think it might\nhave been Thierry Martinez. This led to me <a href=\"https://github.com/cfbolz/pyrolog/commit/8d51938\" rel=\"nofollow ugc noopener\">implementing support for cyclic\nterm unification</a>. I still like that trick a lot and tried to explain it to\n<a href=\"https://www.philipzucker.com/\" rel=\"nofollow ugc noopener\">Phil Zucker</a> earlier this year. I hope to blog about it eventually. For a fun\nuse case see my blog post on <a href=\"https://cfbolz.de/posts/dfa-minimization-using-rational-trees-in-prolog/\" rel=\"nofollow ugc noopener\">rational tree unification for dfa minimization</a>.</p>\n<h2 id=\"2011-2012-widening-prolog-support\">2011/2012 Widening Prolog support</h2>\n<p>During 2011 and 2012 I supervised several Bachelor/Master theses that worked on\nadding features to Pyrolog. In the process we added support for Prolog modules,\n<a href=\"https://www.swi-prolog.org/pldoc/man?section=DCG\" rel=\"nofollow ugc noopener\">DCGs</a>, <a href=\"https://www.swi-prolog.org/pldoc/man?section=attvar\" rel=\"nofollow ugc noopener\">attributed variables</a>, <code>freeze</code> and <code>when</code>. All these were done by my\nexcellent students Sven Hager and René Bartelmus. This left the fundamental\nexecution model intact (with some small additions). I also spent some time\nimproving the error messages of Pyrolog to for example show backtraces on\nProlog exceptions.</p>\n<p>Pyrolog also served as an <a href=\"https://pypy.org/posts/2011/01/jit-backend-for-arm-processors-5994810755839586463.html\" rel=\"nofollow ugc noopener\">early test case</a> for David Schneider&#39;s ARM JIT\nbackend. In January 2011, he could already run Pyrolog microbenchmarks with the\nJIT on a BeagleBoard, while the backend still needed debugging before running\nmore complex Python benchmarks.</p>\n<p>In 2012 I mostly wrote my PhD thesis <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bolz2012\" rel=\"nofollow ugc noopener\">[Bolz2012]</a>. It contains a chapter on Pyrolog based\non the PPDP 2010 paper. That chapter argues that the fact that Pyrolog works\nrelatively well demonstrates that the RPython meta-JIT can be used for quite a\nwide variety of languages.</p>\n<p>There was also another chapter that compared how a meta-tracing JIT works with\nmore classical partial evaluation approaches. The code of that was again\nwritten in Prolog and <a href=\"https://pypy.org/posts/2012/01/simple-tracer-for-flow-graph-language-6930951890987229484.html\" rel=\"nofollow ugc noopener\">originally</a> <a href=\"https://pypy.org/posts/2012/02/optimizing-traces-of-flow-graph-4169388883059419385.html\" rel=\"nofollow ugc noopener\">presented</a> <a href=\"https://pypy.org/posts/2012/02/larger-example-for-flow-graph-language-6139699450091061040.html\" rel=\"nofollow ugc noopener\">here on the blog</a>.</p>\n<p>At this point I left Düsseldorf. In the winter semester 2012/13 I spent half a\nyear in Berlin at <a href=\"https://hpi.de/\" rel=\"nofollow ugc noopener\">Hasso-Plattner-Institute</a> with my PhD co-advisor <a href=\"https://hirschfeld.org/\" rel=\"nofollow ugc noopener\">Robert\nHirschfeld</a> as a postdoc. In 2013 I started working with <a href=\"https://tratt.net/laurie/\" rel=\"nofollow ugc noopener\">Laurie Tratt</a> at\nKing&#39;s College.</p>\n<p>At this point the main Pyrolog story kind of ends. There were only some small\nimprovements happening in the succeeding years. However, Pyrolog ideas led to\nfollowup research in other projects, and I want to discuss some of them.</p>\n<h2 id=\"2012-2013-compressed-terms\">2012/2013 Compressed Terms</h2>\n<p>One experiment that I had tried to get working in Pyrolog in 2010 and 2011, but\nended up never merging, was compressed terms. The idea comes from the\nobservation that certain patterns of terms occur repeatedly. For example an\nassociation list has terms of the form <code>[A/B|C]</code> repeated. Instead of\nallocating separate list and pair objects for every entry, the plan was to\nshare a description of that structure, the &quot;shape&quot;, and store each entry&#39;s keys\nand values in a flat storage data structure. This would make every entry have\nless indirection and use fewer words of memory.</p>\n<p>However, I had never managed to get that working in Prolog, because variable\nbindings can create these patterns after the fact. A field that initially\ncontained an unbound variable could later refer to a whole structured term, so\nthe opportunities for compression changed after construction, and again on\nbacktracking.</p>\n<p>When I was at HPI for six months in winter 2012/2013 I worked with Tobias Pape to\nimplement the same compression idea for a simpler functional language called\nlamb, later <a href=\"https://github.com/shiplift/theseus/\" rel=\"nofollow ugc noopener\">Theseus</a>. Tobias pushed this approach much further in the following years\n<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#pbh2015\" rel=\"nofollow ugc noopener\">[PBH2015]</a>, <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#pbh2017\" rel=\"nofollow ugc noopener\">[PBH2017]</a>. My hope was to eventually understand the problem well\nenough to be able to port it back to Pyrolog. But that part never happened. We\ndid eventually try those ideas in Pycket though.</p>\n<h2 id=\"2013-unipycation\">2013 Unipycation</h2>\n<p>In 2013 I started working in London. The goal of our research project there was\n&quot;language composition&quot;. Edd Barrett, Laurie Tratt and I implemented combined\nRPython implementations of PyPy plus another language, with a way to integrate\nthe two involved languages. The first pair we tried was combining PyPy and\nPyrolog in a project called Unipycation <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#bbt2013\" rel=\"nofollow ugc noopener\">[BBT2013]</a>. The project made it\npossible to call into Prolog from Python and vice versa. The RPython meta-JIT\ncan optimize across this language boundary and even perform cross-language\ninlining. Unfortunately we never found super compelling use-cases for this\ncombination.</p>\n<h2 id=\"2013-pycket\">2013 Pycket</h2>\n<p>Also in 2013 I started working on <a href=\"https://github.com/pycket/pycket\" rel=\"nofollow ugc noopener\">Pycket</a>, an RPython implementation of Racket,\ntogether with <a href=\"https://samth.github.io/\" rel=\"nofollow ugc noopener\">Sam Tobin-Hochstadt</a> and <a href=\"https://luddy.iu.edu/people/siek-jeremy.html\" rel=\"nofollow ugc noopener\">Jeremy Siek</a>. Later Tobias Pape and\nSpenser Bauman also joined. The Pycket architecture was indirectly inspired by\nthe Pyrolog continuation approach. We implemented the CEK machine relatively\ndirectly in RPython. This also used a flat host stack and it made implementing\nthings like <code>call/cc</code> relatively straightforward <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#pycket2015\" rel=\"nofollow ugc noopener\">[Pycket2015]</a>.</p>\n<p>One of the great new ideas we adopted in Pycket was &quot;false loop filtering&quot;,\noriginally from IBM Research <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#hwisn2011\" rel=\"nofollow ugc noopener\">[HWISN2011]</a>. This takes calling context into\naccount when tracing function calls and prevents the tracing JIT from\nrecognizing &quot;false loops&quot;, which would never run for more than one iteration. I\nalways wanted to port this idea back to Pyrolog and implemented a prototype,\nbut never really polished it enough to be able to merge it.</p>\n<p>Another implementation technique in Pycket was to make continuation objects\nmuch smaller, to make the case of them escaping to the heap less bad. This\napproach <em>did</em> <a href=\"https://github.com/cfbolz/pyrolog/commit/59fb825\" rel=\"nofollow ugc noopener\">make it back to Pyrolog</a>.</p>\n<h2 id=\"2022-2024-rpython-implementation-of-effekt\">2022-2024 RPython implementation of Effekt</h2>\n<p>I left King&#39;s College in 2016 and have been back at Uni Düsseldorf (half-time)\nsince 2017. In 2022 I started working with <a href=\"https://pl.cs.uni-tuebingen.de/team/gaissert/\" rel=\"nofollow ugc noopener\">Marcial Gaißert</a> and <a href=\"https://b-studios.de/about\" rel=\"nofollow ugc noopener\">Jonathan\nBrachthäuser</a> on an RPython implementation of <a href=\"https://effekt-lang.org/\" rel=\"nofollow ugc noopener\">Effekt</a> and related languages.\nThis was an implementation of a JIT for <a href=\"https://effekt-lang.org/docs/concepts/effect-handlers\" rel=\"nofollow ugc noopener\">effect handlers</a> in RPython <a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#gbb2025\" rel=\"nofollow ugc noopener\">[GBB2025]</a>.\nAgain, it uses the approach of having reified stack frames/continuations which\ncan then be manipulated by the interpreter, adding effect handlers on top of it.</p>\n<h2 id=\"2026-git-conversion\">2026 Git Conversion</h2>\n<p>This fall, I got an email by a researcher about Pyrolog and realized that it\nwas 20 years old this year. Subsequently I merged various strands of the\nsurviving mercurial history into a new <a href=\"https://github.com/cfbolz/pyrolog\" rel=\"nofollow ugc noopener\">Github repo</a>, fixed some bugs and\nimplemented some convenience features.</p>\n<figure><img src=\"https://pypy.org/images/2026-pyrolog-screenshot.png\" alt=\"/images/2026-pyrolog-screenshot.png\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>Screenshot of Pyrolog</p>\n<h2 id=\"conclusion\">Conclusion</h2>\n<figure><img src=\"https://pypy.org/images/2026-pyrolog-activity-by-month-authors.svg\" alt=\"/images/2026-pyrolog-activity-by-month-authors.svg\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p>commits per month on the main branch, by author</p>\n<p>Pyrolog has always been a much more researchy project than PyPy itself. While\nPyPy tries to be an open source project and &quot;product&quot;, Pyrolog never had any\nusers and even I never used it for anything beyond small demos, some\nresearch prototypes, and benchmarking. While some quite interesting research\ncame out of Pyrolog, I think having some real applications running on top of it\nwould have given me a much more concrete goal to improve it towards.</p>\n<p>Implementation wise, Pyrolog inherited some of the problems of PyPy. In PyPy we\nwere quite strongly focused on peak performance in the first few years, leading\nto performance cliffs. Pyrolog also had those in even stronger form, due to the\nconstant allocations of the interpreter.</p>\n<p>Some very interesting interaction between Pyrolog, various Prolog JIT\nprototypes and the PyPy/RPython meta-JIT emerged. Pyrolog forced the RPython\nJIT to support quite different execution models which made it applicable to\nother languages than just object-oriented imperative ones.</p>\n<p>I still have no concrete use case for Pyrolog so it&#39;s kind of unlikely that I\nwill work much more on it right now. But my development on this project was\nalways quite bursty, so I am bound to return to it at some point in the future.</p>\n<p>I would like to end with thanking all the contributors, my other collaborators\nand the long line of Prolog researchers that inspired and encouraged me.</p>\n<h2 id=\"bibliography\">Bibliography</h2>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-6\" rel=\"nofollow ugc noopener\">TB1990</a>]</p>\n<p>P. Tarau, M. Boyer.\n<em>Elementary logic programs</em>. PLILP 1990, LNCS 456, pp. 159–173.\n<a href=\"https://doi.org/10.1007/BFb0024183\" rel=\"nofollow ugc noopener\">DOI</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-7\" rel=\"nofollow ugc noopener\">Tarau1992</a>]</p>\n<p>Paul Tarau.\n<em>BinProlog: a continuation passing style Prolog engine</em>.\nPLILP 1992, LNCS 631, pp. 479–480. Poster.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-2\" rel=\"nofollow ugc noopener\">SS1994</a>]</p>\n<p>Leon S. Sterling, Ehud Y. Shapiro.\n<em>The Art of Prolog: Advanced Programming Techniques</em>.\n2nd edition, MIT Press, 1994.\n<a href=\"https://mitpress.mit.edu/9780262691635/the-art-of-prolog/\" rel=\"nofollow ugc noopener\">Publisher page</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-8\" rel=\"nofollow ugc noopener\">Lindgren1994</a>]</p>\n<p>Thomas Lindgren.\n<em>A Continuation-Passing Style for Prolog</em>.\nInternational Logic Programming Symposium, 1994, pp. 603–617.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-4\" rel=\"nofollow ugc noopener\">VanRoy1994</a>]</p>\n<p>Peter Van Roy.\n<em>1983–1993: The Wonder Years of Sequential Prolog Implementation</em>.\nJournal of Logic Programming 19–20, 1994, pp. 385–441.\n<a href=\"https://doi.org/10.1016/0743-1066(94)90031-0\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://webperso.info.ucl.ac.be/~pvr/PRL-TR-36.pdf\" rel=\"nofollow ugc noopener\">author-hosted technical report PDF</a>\n(DEC Paris Research Laboratory report 36, December 1993).</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-9\" rel=\"nofollow ugc noopener\">Neumerkel1995</a>]</p>\n<p>Ulrich Neumerkel.\n*Continuation Prolog: A new intermediary language for WAM and BinWAM\ncode generation*. Post-ILPS 1995 Workshop on Implementation of Logic\nProgramming Languages, 1995.\n<a href=\"https://www.complang.tuwien.ac.at/ulrich/papers/PDF/contp95.pdf\" rel=\"nofollow ugc noopener\">PDF</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-1\" rel=\"nofollow ugc noopener\">CM2003</a>]</p>\n<p>William F. Clocksin, Christopher S. Mellish.\n<em>Programming in Prolog: Using the ISO Standard</em>.\n5th edition, Springer, 2003.\n<a href=\"https://doi.org/10.1007/978-3-642-55481-0\" rel=\"nofollow ugc noopener\">DOI</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-3\" rel=\"nofollow ugc noopener\">VH2004</a>]</p>\n<p>Peter Van Roy, Seif Haridi.\n<em>Concepts, Techniques, and Models of Computer Programming</em>.\nMIT Press, 2004. ISBN 9780262220699.\n<a href=\"https://mitpress.mit.edu/9780262220699/concepts-techniques-and-models-of-computer-programming/\" rel=\"nofollow ugc noopener\">Publisher page</a>;\n<a href=\"https://webperso.info.ucl.ac.be/~pvr/book.html\" rel=\"nofollow ugc noopener\">author&#39;s book page</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-15\" rel=\"nofollow ugc noopener\">BD2004</a>]</p>\n<p>Dariusz Biernacki, Olivier Danvy.\n<em>From Interpreter to Logic Engine by Defunctionalization</em>.\nLOPSTR 2003, revised selected papers, published 2004, pp. 143–159.\n<a href=\"https://doi.org/10.1007/978-3-540-25938-1_13\" rel=\"nofollow ugc noopener\">DOI</a>,\n<a href=\"https://ii.uni.wroc.pl/~dabi/publications/LOPSTR03/biernacki-danvy-lopstr03.pdf\" rel=\"nofollow ugc noopener\">PDF</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-10\" rel=\"nofollow ugc noopener\">BR2007D071</a>]</p>\n<p>CF Bolz, Armin Rigo.\n*Support for massive parallelism, optimisation results, practical\nusages and approaches for translation aspects*.\nPyPy Consortium, EU deliverable D07.1, 28 February 2007.\nListed by PyPy as <em>Massive Parallelism and Translation Aspects</em>.\n<a href=\"https://doc.pypy.org/index-report.html\" rel=\"nofollow ugc noopener\">Official report index</a>;\n<a href=\"https://foss.heptapod.net/pypy/extradoc/-/blob/branch/extradoc/eu-report/D07.1_Massive_Parallelism_and_Translation_Aspects-2007-02-28.pdf\" rel=\"nofollow ugc noopener\">report PDF</a>.</p>\n<p>[Bolz2007]\n(<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-5\" rel=\"nofollow ugc noopener\">1</a>,<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-11\" rel=\"nofollow ugc noopener\">2</a>)</p>\n<p>CF Bolz.\n<em>A Prolog Interpreter in Python</em>. Bachelor thesis,\nHeinrich Heine University Düsseldorf, 2007.\n<a href=\"https://cfbolz.de/Bolz2007-Bachelorarbeit.pdf\" rel=\"nofollow ugc noopener\">PDF</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-12\" rel=\"nofollow ugc noopener\">BLR2010</a>]</p>\n<p>CF Bolz, Michael Leuschel, Armin Rigo.\n<em>Towards Just-In-Time Partial Evaluation of Prolog</em>.\nLOPSTR 2009, revised selected papers, LNCS 6037, 2010, pp. 158–172.\n<a href=\"https://doi.org/10.1007/978-3-642-12592-8_12\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://stups.hhu-hosting.de/downloads/pdf/BoLeRi09_235.pdf\" rel=\"nofollow ugc noopener\">author manuscript</a>.</p>\n<p>[BLS2010]\n(<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-13\" rel=\"nofollow ugc noopener\">1</a>,<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-14\" rel=\"nofollow ugc noopener\">2</a>)</p>\n<p>CF Bolz, Michael Leuschel, David Schneider.\n<em>Towards a Jitting VM for Prolog Execution</em>. PPDP 2010, pp. 99–108.\n<a href=\"https://doi.org/10.1145/1836089.1836102\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://stups.hhu-hosting.de/downloads/pdf/BoLeSch2010.pdf\" rel=\"nofollow ugc noopener\">author manuscript</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-21\" rel=\"nofollow ugc noopener\">HWISN2011</a>]</p>\n<p>Hiroshige Hayashizaki, Peng Wu, Hiroshi Inoue,\nMauricio J. Serrano, Toshio Nakatani.\n<em>Improving the Performance of Trace-based Systems by False Loop Filtering</em>.\nASPLOS XVI, 2011, pp. 405–418.\n<a href=\"https://doi.org/10.1145/1950365.1950412\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://research.ibm.com/publications/improving-the-performance-of-trace-based-systems-by-false-loop-filtering\" rel=\"nofollow ugc noopener\">IBM Research publication page</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-16\" rel=\"nofollow ugc noopener\">Bolz2012</a>]</p>\n<p>CF Bolz.\n<em>Meta-Tracing Just-in-Time Compilation for RPython</em>.\nPhD thesis, Heinrich-Heine-Universität Düsseldorf, September 2012.\n<a href=\"https://cfbolz.de/phdthesis/\" rel=\"nofollow ugc noopener\">Author&#39;s thesis page</a>;\n<a href=\"https://cfbolz.de/stuff/cfbolz-meta-tracing.pdf\" rel=\"nofollow ugc noopener\">PDF</a>;\n<a href=\"https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=30464\" rel=\"nofollow ugc noopener\">university repository</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-19\" rel=\"nofollow ugc noopener\">BBT2013</a>]</p>\n<p>Edd Barrett, CF Bolz, Laurence Tratt.\n<em>Unipycation: A Case Study in Cross-Language Tracing</em>.\nVMIL 2013, pp. 31–40.\n<a href=\"https://doi.org/10.1145/2542142.2542146\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://tratt.net/laurie/research/pubs/papers/barrett_bolz_tratt__unipycation_a_study_in_cross_language_tracing.pdf\" rel=\"nofollow ugc noopener\">author manuscript</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-20\" rel=\"nofollow ugc noopener\">Pycket2015</a>]</p>\n<p>Spenser Bauman, CF Bolz, Robert Hirschfeld,\nVasily Kirilichev, Tobias Pape, Jeremy G. Siek, Sam Tobin-Hochstadt.\n<em>Pycket: A Tracing JIT for a Functional Language</em>.\nICFP 2015, pp. 22–34.\n<a href=\"https://doi.org/10.1145/2784731.2784740\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://soft-dev.org/pubs/pdf/bauman_bolz_hirschfeld_kirilichev_pape_siek_tobin_hochstadt__pycket_a_tracing_jit_for_a_functional_language.pdf\" rel=\"nofollow ugc noopener\">author manuscript</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-17\" rel=\"nofollow ugc noopener\">PBH2015</a>]</p>\n<p>Tobias Pape, CF Bolz, Robert Hirschfeld.\n*Adaptive Just-in-time Value Class Optimization: Transparent Data\nStructure Inlining for Fast Execution*. SAC 2015.\n<a href=\"https://doi.org/10.1145/2695664.2695837\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://www.hirschfeld.org/writings/media/PapeBolzHirschfeld_2015_AdaptiveJustInTimeValueClassOptimization_AcmDL.pdf\" rel=\"nofollow ugc noopener\">PDF</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-18\" rel=\"nofollow ugc noopener\">PBH2017</a>]</p>\n<p>Tobias Pape, CF Bolz, Robert Hirschfeld.\n*Adaptive just-in-time value class optimization for lowering memory\nconsumption and improving execution time performance*.\nScience of Computer Programming 140, 2017, pp. 17–29.\nPublished online in 2016.\n<a href=\"https://doi.org/10.1016/j.scico.2016.08.003\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://www.hirschfeld.org/writings/media/PapeBolzHirschfeld_2017_AdaptiveJustInTimeValueClassOptimizationForLoweringMemoryConsumptionAndImprovingExecutionTimePerformance_Elsevier.pdf\" rel=\"nofollow ugc noopener\">PDF</a>.</p>\n<p>[<a href=\"https://pypy.org/posts/2026/11/20-years-of-pyrolog.html#citation-reference-22\" rel=\"nofollow ugc noopener\">GBB2025</a>]</p>\n<p>Marcial Gaißert, CF Bolz-Tereick,\nJonathan Immanuel Brachthäuser.\n<em>Tracing Just-in-Time Compilation for Effects and Handlers</em>.\nProceedings of the ACM on Programming Languages 9 (OOPSLA2),\nArticle 307, October 2025.\n<a href=\"https://doi.org/10.1145/3763085\" rel=\"nofollow ugc noopener\">DOI</a>;\n<a href=\"https://pl.cs.uni-tuebingen.de/publications/gaissert2025tracing/\" rel=\"nofollow ugc noopener\">author publication page</a>;\n<a href=\"https://pl.cs.uni-tuebingen.de/publications/gaissert2025tracing.pdf\" rel=\"nofollow ugc noopener\">technical report</a>.</p>","headings":[{"level":2,"text":"Context","id":"context"},{"level":2,"text":"2006/2007 The first year","id":"2006-2007-the-first-year"},{"level":2,"text":"2008/2009 JIT developments on the PyPy side","id":"2008-2009-jit-developments-on-the-pypy-side"},{"level":2,"text":"2009-2010 New Pyrolog Architecture: More Continuations","id":"2009-2010-new-pyrolog-architecture-more-continuations"},{"level":3,"text":"JIT support","id":"jit-support"},{"level":2,"text":"2011/2012 Widening Prolog support","id":"2011-2012-widening-prolog-support"},{"level":2,"text":"2012/2013 Compressed Terms","id":"2012-2013-compressed-terms"},{"level":2,"text":"2013 Unipycation","id":"2013-unipycation"},{"level":2,"text":"2013 Pycket","id":"2013-pycket"},{"level":2,"text":"2022-2024 RPython implementation of Effekt","id":"2022-2024-rpython-implementation-of-effekt"},{"level":2,"text":"2026 Git Conversion","id":"2026-git-conversion"},{"level":2,"text":"Conclusion","id":"conclusion"},{"level":2,"text":"Bibliography","id":"bibliography"}]}}