Comparing tag scheme variations using an abstract machine generator

ABSTRACT

In this paper we study, in the context of a WAM-based abstract machine for Prolog, how variations in the encoding of type information in tagged words and in their associated basic operations impact performance and memory usage.We use a high-level language to specify encodings and the associated operations. An automatic generator constructs both the abstract machine using this encoding and the associated Prolog-to-bytecode compiler. Annotations in this language make it possible to impose constraints on the final representation of tagged words, such as the effectively addressable space (fixing, for example, the word size of the target processor / architecture), the layout of the tag and value bits inside the tagged word, and how the basic operations are implemented. We evaluate a large number of combinations of the different parameters in two scenarios: a) trying to obtain an optimal general-purpose abstract machine and b) automatically generating a specially-tuned abstract machine for a particular program. We conclude that we are able to automatically generate code featuring all the optimizations present in a hand-written, highly-optimized abstract machine and we can also obtain emulators with larger addressable space and better performance

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: A.-K. Hassan, Integrating data type inheritance into logic programming, Data types and persistence, Springer-Verlag, London, 1988
• 3: K. Appleby , M. Carllson , S. Haridi , D. Sawhlin, Garbarge collection for Prolog based on WAM, Communications of the ACM, v.31 n.6, p.719-741, June 1988 [doi>10.1145/62959.62968]
• 4: F. Bueno, D. Cabeza, M. Carro, M. Hermenegildo, P. López-García, and G. P. (Eds.). The Ciao System. Ref. Manual (v1.13). Technical report, C. S. School (UPM), 2006. Available at http://www.ciaohome.org.
• 5: Manuel Carro , José F. Morales , Henk L. Muller , G. Puebla , M. Hermenegildo, High-level languages for small devices: a case study, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176794]
• 6: Robert Cartwright , Mike Fagan, Soft typing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.278-292, June 24-28, 1991, Toronto, Ontario, Canada
• 7: A. Casas, D. Cabeza, and M. Hermenegildo. A Syntactic Approach to Combining Functional Notation, Lazy Evaluation and Higher-Order in LP Systems. In FLOPS'06, Fuji Susono (Japan), April 2006.
• 8: Bart Demoen , Phuong-Lan Nguyen, So Many WAM Variations, So Little Time, Proceedings of the First International Conference on Computational Logic, p.1240-1254, July 01, 2000
• 9: ECRC. Eclipse User's Guide. European Computer Research Center, 1993.
• 10: Manuel V. Hermenegildo , Germán Puebla , Francisco Bueno , Pedro López-García, Integrated program debugging, verification, and optimization using abstract interpretation (and the Ciao system preprocessor), Science of Computer Programming, v.58 n.1-2, p.115-140, October 2005 [doi>10.1016/j.scico.2005.02.006]
• 11: Simon Marlow , Alexey Rodriguez Yakushev , Simon Peyton Jones, Faster laziness using dynamic pointer tagging, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 12: J. Morales, M. Carro, and M. Hermenegildo. Towards Description and Optimization of Abstract Machines in an Extension of Prolog. In G. Puebla, editor, Logic-Based Program Synthesis and Transformation (LOPSTR'06), number 4407 in LNCS, pages 77--93, July 2007.
• 13: J. Morales, M. Carro, G. Puebla, and M. Hermenegildo. A Generator of Efficient Abstract Machine Implementations and its Application to Emulator Minimization. In M. Gabbrielli and G. Gupta, editors, International Conference on Logic Programming, number 3668 in LNCS, pages 21--36. Springer Verlag, October 2005.
• 14: Armin Rigo, Representation-based just-in-time specialization and the psyco prototype for python, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.15-26, August 24-25, 2004, Verona, Italy [doi>10.1145/1014007.1014010]
• 15: Vítor Santos Costa, Optimising Bytecode Emulation for Prolog, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.261-277, September 29-October 01, 1999
• 16: V. Santos-Costa, L. Damas, R. Reis, and R. Azevedo. The Yap Prolog User's Manual, 2000. Available from http://www.ncc.up.pt/~vsc/Yap.
• 17: Swedish Institute for Computer Science, PO Box 1263, S-164 28 Kista, Sweden. SICStus Prolog 3.8 User's Manual, 3.8 edition, Oct. 1999. Available from http://www.sics.se/sicstus/.
• 18: D. Warren. An Abstract Prolog Instruction Set. Technical Report 309, Artificial Intelligence Center, SRI International, 333 Ravenswood Ave, Menlo Park CA 94025, 1983.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
      D.3.4 Processors
          Subjects: Translator writing systems and compiler generators; Code generation; Optimization

General Terms:
Languages, Performance

Keywords:
Prolog, Warren's abstract machine, compilation, low-level representation optimization, performance