Self-optimizing AST Interpreters for rule-based languages using the Truffle framework

Printer-friendly version
Info
Advisors: 
Context: 

Programs written in high-level programming languages can be executed in one of two ways: through interpretation and through compilation. Interpreters tend to be much easier to write. Still, the runtime performance of interpreted programs usually lags far behind that of a compiled version of the same program. For this reason, language developers have to choose between spending a huge amount of engineering effort on building a (JIT-) compiler for their language, or accepting performance that is orders of magnitude slower than the state of the art.

Self-optimizing AST Interpreters

With technologies like the meta-tracing RPython toolchain and the Truffle framework for writing self-optimizing AST interpreters state-of-the-art performance can be reached based on simple interpreters. As a type of AST interpreter, self-optimizing AST interpreters are similar to the interpreters written in the VUB courses Interpretatie van Computerprogramma's I or Programming Language Engineering. The additional self-optimizations remove of the overhead of interpretation by specializing the AST to the execution for a specific program, such that later executions of the program only need to do the most specific operations.

Of course, there is no such thing as a free lunch: Truffle significantly reduces the effort required to build a highly efficient interpreter, but it takes some effort nonetheless. In the paper "Are We There Yet? Simple Language Implementation Techniques for the 21st Century", Stefan Marr et al. describe[2] how they ported the implementation of a Smalltalk dialect to RPython and to Truffle. As mentioned, interpreters for Python are built using such technologies[2], too. And of course, interpreters exist for languages such as Scheme, C++, etc. However, languages with significantly different execution semantics can be interpreted, too. Since our lab has acquired a lot of experience with interpreters for forward-chaining rule engines using the Rete algorithm[4], it seems worthwhile to investigate whether Truffle's self-optimizing techniques can be leveraged to speed up the interpretation of rule-based languages.

Rule-based languages

The main component of rule based programming languages are... rules. Rules can for instance take the form

rule AcceptThesisTopic where {
    Student student (level == "1st Master"),
    ThesisTopic topic (prerequisites ⊆ student.capabilities,
lab == student.specialization),     ¬Student other (taken_topic == topic) } then {     topic.advisor.inform(student, topic,
"I really like this topic, can "\
"we meet to discuss this further?");     student.taken_topic = topic; }

Such a rule would encode the logic that if there is a student whose level is "1st Master", and there is a thesis topic whose prerequisites are met by the student, and the student is supposed to take a thesis from the lab that published that topic, and there is no other student that took that topic, then the student can meet up with the advisor and claim the topic.

While this can of course be solved with a conditional check on a conjunction, implementing this efficiently is rather complicated. This is where rule engines come in: they use algorithms like the Rete algorithm to efficiently store state and react quickly to changes in the state.

Goal & Research Activities: 

This thesis' goal is to investigate whether Truffle's self-optimizing techniques can be leveraged to interpret rule-based languages. Specifically, the Rete algorithm[4] famously comes in a 'compiled' and an 'interpreted' form, where the latter uses the Rete graph similar to how an AST interpreter uses the AST.

Before the thesis can be started proper, the student will have to get acquainted with the Rete algorithm, and with the Truffle framework. The former can be easily managed directly by SOFT members: we've guided many thesis students on related topics, and many of us are working on similar problems. For Truffle, though, we will involve international collaborators such as Stefan Marr, who have previous experience with Truffle and will support the project remotely.

References: 
  1. Würthinger, Thomas, Wöß, Andreas, Stadler, Lukas, Duboscq, Gilles, Simon, Doug and Wimmer, Christian. "Self-Optimizing AST Interpreters." Proceedings of the 8th Dynamic Languages Symposium, 2012.
  2. Stefan Marr, Tobias Pape, and Wolfgang De Meuter. "Are We There Yet?: Simple Language Implementation Techniques for the 21st Century." Software, IEEE 31.5 (2014): 60-67.
  3. Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, and Armin Rigo. "Tracing the meta-level: PyPy's tracing JIT compiler". In Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (ICOOOLPS '09). ACM, USA, (2009): 18-25.
  4. Charles Forgy. "Rete: A fast algorithm for the many pattern/many object pattern match problem" Artificial Intelligences, vol. 19, no. 1, (1982): 17–37.