Jitting Attributed Variables and Coroutines in Pyrolog
Sven Hager and Carl Friedrich Bolz
Heinrich-Heine Universität Düsseldorf,
STUPS Group,
Germany
Adding advanced features to C-based Prolog implementations can be a difficult task which complicates further experimentation. In the last few months the Pyrolog Prolog interpreter has been extended with SWI-compatible attributed variables and a set of coroutining predicates. The results show that the high-level approach of Pyrolog can compete with mature WAM-based Prolog systems.
Introduction
Nowadays, there exist many mature Prolog systems, for example SWI-Prolog1, SICStus Prolog2 and YAProlog3. To achieve good performance, these interpreters are WAM-based and written in low-level languages like C [8]. Unfortunately, the usage of C has some disadvantages:
- Large C programs are hard to write and debug.
- C does not provide a garbage collector.
- C programs tend to be much larger than equivalents written in high-level languages.
The Pyrolog interpreter follows a different approach [3]. It is written in RPython, a statically typed subset of the Python language [1]. RPython programs can be translated to C code using a translation toolchain, which is provided by the PyPy project4. PyPy [6] tries to facilitate the efficient implementation of interpreters for dynamic languages in RPython.
These interpreters can then be translated into a C-based VM by the toolchain, which also adds a garbage collector (GC) to the executable. Furthermore, a tracing just-in-time compiler (JIT) can be generated to speed up often executed code paths in the interpreted program [2].
It is important to stress that low-level details like the GC or the JIT do not have to be implemented manually: All the interpreter author has to do is to provide a number of hints in the RPython code to enable the generation of the JIT.
2 Attributed Variables in Pyrolog
In contrast to the WAM-based interpreters mentioned above, Pyrolog makes use of continuations to execute Prolog code [3]. Continuations hold the current state of execution and become activated to execute the next bit of Prolog code.
In Pyrolog, attributed variables are treated as special Prolog variables. In fact, attributed variables can be regarded as Prolog variables + attributes + enhanced unification.
There are two main challenges that come with attributed variables:
- The standard Prolog unification mechanism has to be extended in such a manner that the unification of attributed variables
can trigger the execution of so called hook predicates. - An efficient way of accessing the attributes is needed.
If an attributed variable X is unified with a non-variable or another attributed variable, then for each attribute on X a hook predicate in a certain Prolog module should be executed.
In order to execute the correct hook predicates, Pyrolog pushes the unified attributed variables on a stack during the activation of a continuation. After the activation has finished, a hook execution function is called which pops all variables from the stack and calls the corresponding hook predicates. If this function is called often enough, the JIT will inline it and unroll the loop which processes the attributes. The most basic approach to store attributes on attributed variables is to use a dictionary (hash-map) on the underlying objects on the interpreter level.
Unfortunately, lookups in these dictionaries are comparatively slow since the JIT compiler is not able to perform certain optimizations like constant folding due to the mutability of the dictionaries. That in turn means that the most basic operations on attributed variables like storing and reading attributes are not very efficient. Hence, another approach is needed.
What comes into play here is the observation that many attributed variables carry the same set of attribute names. Moreover, often attributed variables have only one attribute. For example, the implementation of the when/2 coroutining predicate always puts the attribute
(when, SomeData)
on attributed variables. Based on this observation, it is reasonable to put the description of the stored attributes in a data structure called Map.
Maps are a well known technique that comes from the efficient implementation of dynamic languages [4].
When using Maps, an atttributed variable is split into two parts: The (immutable) Map, which stores the names of the attributes, and the storage, which stores their values. Variables with the same set of attribute names share the same Map. If the attribute name set on X changes, then the Map assigned to X changes, too [5].
Due to the immutability of the Map, the JIT is able to remove the dictionary lookups in the Map. Given that few Maps are needed and that attributed variables seldom change their attribute name set, a good speedup can be achieved when accessing attributes. On the other hand, the approach retains full generality for an arbitrary number of attributes.
This usage of Maps can be related to the use of structure sharing to represent Prolog terms in older Prolog implementations [7]. It can also be seen as a Binding Time Improvement in the sense of partial evaluation.
3 Evaluation
Figure 1 shows the results of some microbenchmarks with regard to attributed variables. The performance of Pyrolog is compared to those of SWI-Prolog and SICStus Prolog. Each benchmark was executed 30 times.
Figure 1: Attributed Variables Steady-State Execution Times
The results indicate that Pyrolog’s approach of implementing attributed variables is reasonable. Nevertheless, it must be mentioned that the JIT typically needs a few iterations to trace and to generate fast machine code.
Pyrolog’s coroutining functionality, which is implemented on top of attributed variables in Prolog, performs similarly to SWI-Prolog’s Prolog-based coroutining predicates. In contrast, SICStus Prolog clearly outperforms both Pyrolog and SWI when it comes to coroutining predicates. In contrast to Pyrolog and SWI, SICStus does not implement those predicates in Prolog but in C. For a more detailed performance evaluation, see the first author’s bachelor thesis [5].
4 Conclusion
In summary it can be said that the RPython approach is an interesting alternative to the usual C implementations of the Prolog language. As compared to mature Prolog implementations which have evolved over years, Pyrolog performs well when it comes to attributed variables.
The provided coroutining functionality is not as fast as the one implemented by SICStus, but can still be optimized. It is very likely that further experiments on Pyrolog with particular emphasis on the JIT will increase performance of the coroutining predicates.
References
- [1] D. Ancona, M. Ancona, A. Cuni, and N. D. Matsakis, RPython: a step towards reconciling dynamically and statically typed OO languages, in Proceedings of the 2007 symposium on Dynamic languages, DLS ’07, New York., NY, USA, 2007, ACM, pp. 53-64.
- [2] C. F. Bolz, A. Cuni, M. Fijalkowski, and A. Rigo, Tracing the meta-level: PyPy’s tracing JIT compiler, in ICOOOLPS, 2009.
- [3] C. F. Bolz, M. Leuschel, and D. Schneider, Towards a jitting VM for Prolog execution, PPDP, (2010).
- [4] C. Chambers, D. Ungar, and E. Lee, An efficient implementation of SELF, a dynamically-typed object-oriented language based on prototypes, SIGPLAN Not., 24 (1989), pp. 49-70.
- [5] S. Hager, Coroutines and Modules for Pyrolog. http://cobra.cs.uni-duesseldorf.de/w/Coroutines_and_Modules_for_Pyrolog, 2011.
- [6] A. Rigo and S. Pedroni, Pypy’s approach to virtual machine construction, in Companion to the 21st ACM SIGPLAN symposium on Object-oriented programming systems, languages, and applications, OOPSLA ’06, New York, NY, USA, 2006, ACM, pp. 944-953.
- [7] P. Van Roy, 1983-1993: The wonder years of sequential Prolog implementation, Journal of Logic Programming, 19,20 (1994), pp. 385-441.
- [8] D. H. D. Warren, An abstract Prolog instruction set, Tech. Rep. 309, AI Center, SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025, Oct 1983.
Footnotes:
2http://www.sics.se/isl/sicstuswww/site/index.html