20 Years of Pyrolog

This personal retrospective follows Pyrolog, an RPython-based Prolog interpreter begun in 2006 as part of PyPy’s research work. Its first design used exception-driven backtracking, heap-allocated success continuations, and a stackless transformation to handle deep recursion. Performance was initially poor: Sicstus could be an order of magnitude faster, and an early partial-evaluation JIT offered little benefit. A later redesign represented both success and failure continuations as heap objects and kept Prolog execution off the host stack. That made the interpreter easier for PyPy’s tracing JIT to optimize, sometimes allowing it to outperform Sicstus on microbenchmarks. But the gains depended on predictable control flow; realistic backtracking often caused continuations to escape optimization, creating sharp performance drops.

Pyrolog also became a testbed for broader work. Prototyping PyPy’s trace-based JIT in Prolog helped shape pyjitpl5, the foundation of PyPy’s current meta-JIT. Later work added modules, DCGs, attributed variables, freeze and when, and tested an ARM JIT backend. The interpreter also supported research into cyclic-term unification and compressed terms, an effort to reduce memory use by sharing descriptions of repeated structures. Although Pyrolog never gained real users, its implementation and experiments informed research and other RPython projects, including work on Pycket and Effekt. The retrospective presents the project as valuable less for its adoption than for the ideas and technical lessons it generated.