Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-25T05:08:16.789Z Has data issue: false hasContentIssue false
  • English
  • Français

The BinProlog experience: Architecture and implementation choices for continuation passing Prolog and first-class logic engines

Published online by Cambridge University Press:  12 September 2011

PAUL TARAU
PAUL TARAU*
Affiliation:
Department of Computer Science and Engineering, University of North Texas, Denton, Texas 76203-6886, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe the BinProlog system's compilation technology, runtime system and its extensions supporting first-class Logic Engines while providing a short history of its development, details of some of its newer re-implementations as well as an overview of the most important architectural choices involved in their design. With focus on its differences with conventional Warren Abstract Machine (WAM) implementations, we explain key details of BinProlog's compilation technique, which replaces the WAM with a simplified continuation passing runtime system (the “BinWAM”), based on a mapping of full Prolog to binary logic programs. This is followed by a description of a term compression technique using a “tag-on-data” representation. Later derivatives, the Java-based Jinni Prolog compiler and the recently developed Lean Prolog system refine the BinProlog architecture with first-class Logic Engines, made generic through the use of an Interactor interface. An overview of their applications with focus on the ability to express at source level a wide variety of Prolog built-ins and extensions covers these newer developments.

Keywords

Prologlogic programming systemcontinuation passing style compilationimplementation of Prologfirst-class logic enginesdata-representations for Prolog runtime systems
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 12 , Special Issue 1-2: Prolog Systems , January 2012 , pp. 97 - 126
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aït-Kaci, H. 1991. Warren's Abstract Machine: A Tutorial Reconstruction. MIT Press, Cambridge, MA, USA. ISBN: 0-262-51058-8 978-0-262-51058-5.CrossRefGoogle Scholar
Bolz, C. F., Leuschel, M. and Schneider, D. 2010. Towards a Jitting VM for Prolog execution. In Proc. of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP '10). ACM, New York, NY, USA, 99–108.Google Scholar
Carlsson, M., Widen, J., Andersson, J., Andersson, S., Boortz, K., Nilsson, H. and Sjoland, T. 2009. SICStus Prolog user's manual. SICS, Kista, Sweden.Google Scholar
Carro, M. and Hermenegildo, M. V. 1999. Concurrency in Prolog using threads and a shared database. In Proc. of the International Conference on Logic Programming (ICLP), 320–334.Google Scholar
Casas, A., Carro, M. and Hermenegildo, M. 2007. Towards a high-level implementation of flexible parallelism primitives for symbolic languages. In Proc. of the 2007 International Workshop on Parallel Symbolic Computation. ACM, New York, NY, USA, 93–94.CrossRefGoogle Scholar
Clark, D. W. and Green, C. C. 1977. An empirical study of list structure in Lisp. Communications of the ACM 20, 78–87.CrossRefGoogle Scholar
Conway, M. E. 1963. Design of a separable transition-diagram compiler. Communications of the ACM 6, 7, 396–408.CrossRefGoogle Scholar
Dahl, V., Tarau, P. and Li, R. 1997. Assumption grammars for processing natural language. In Proc. of the 14th International Conference on Logic Programming, Naish, L., Ed. MIT Press, Cambridge, MA, USA, 256–270.Google Scholar
da Silva, A. F. and Costa, V. S. 2006. The design and implementation of the yap compiler: An optimizing compiler for logic programming languages. In Proc. of the International Conference on Logic Programming (ICLP), Etalle, S. and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 4079. Springer, Berlin, Heidelberg, 461–462.Google Scholar
De Bosschere, K. and Tarau, P. January 1996. Blackboard-based extensions in Prolog. Software—Practice and Experience 26, 1, 49–69.3.0.CO;2-C>CrossRefGoogle Scholar
Demoen, B. 1992. On the transformation of a prolog program to a more efficient binary program. In Proc. of the International Workshop on Logic Program Synthesis and Transformation (LOPSTR), 242–252.Google Scholar
Demoen, B., Engels, G. and Tarau, P. 1996. Segment preserving copying garbage collection for WAM based Prolog. In Proc. of the 1996 ACM Symposium on Applied Computing. ACM Press, Philadelphia, PA, USA, 380–386.CrossRefGoogle Scholar
Demoen, B. and Mariën, A. 1992. Implementation of Prolog as binary definite programs. In Proc. of the First Russian Conference on Logic Programming (RCLP), Voronkov, A., Ed. Lecture Notes in Artificial Intelligence, vol. 592. Springer-Verlag, Berlin, Heidelberg, 165–176.Google Scholar
Demoen, B. and Nguyen, P.-L. 2000. So many WAM variations, so little time. In Proc. of the First International Conference on Computational Logic (CL '00). Springer-Verlag, London, UK, 1240–1254.Google Scholar
Deransart, P., Ed-Dbali, A. and Cervoni, L. 1996. Prolog: The Standard, Springer-Verlag, Berlin. ISBN: 3-540-59304-7.CrossRefGoogle Scholar
Diaz, D. and Codognet, P. 2001. Design and implementation of the GNU Prolog system. Journal of Functional and Logic Programming 2001, 6, 1–29.Google Scholar
FIPA. 1997. FIPA 97 specification part 2: Agent communication language. Version 2.0.Google Scholar
Hermenegildo, M. V. 1986. An abstract machine for restricted and-parallel execution of logic programs. In Proc. of the Third International Conference on Logic Programming. Springer-Verlag, New York, NY, USA, 25–39.CrossRefGoogle Scholar
Lindgren, T. 1994. A continuation-passing style for prolog. In Proc. of the 1994 International Symposium on Logic programming (ILPS '94). MIT Press, Cambridge, MA, USA, 603–617.Google Scholar
Liskov, B., Atkinson, R. R., Bloom, T., Moss, J. E. B., Schaffert, C., Scheifler, R. and Snyder, A. 1981. CLU Reference Manual. Lecture Notes in Computer Science, vol. 114. Springer, Berlin, Heidelberg.Google Scholar
Lloyd, J. 1987. Foundations of Logic Programming (Symbolic Computation/Artificial Intelligence), 2nd ed.Springer-Verlag, Berlin.CrossRefGoogle Scholar
Lusk, E., Mudambi, S., Gmbh, E. and Overbeek, R. 1993. Applications of the aurora parallel Prolog system to computational molecular biology. In Proc. of the Post-Conference Joint Workshop on Distributed and Parallel Implementations of Logic Programming Systems (JICSLP '92), Washington DC. MIT Press.Google Scholar
Nässén, H., Carlsson, M. and Sagonas, K. 2001. Instruction merging and specialization in the sicstus prolog virtual machine. In Proc. of the 3rd ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP '01). ACM, New York, NY, USA, 49–60.Google Scholar
Neumerkel, U. 1992. Specialization of Prolog Programs with Partially Static Goals and Binarization. PhD Thesis, Technische Universität Wien.Google Scholar
Shapiro, E. 1989. The family of concurrent logic programming languages. ACM Computing Serveys 21, 3, 413–510.CrossRefGoogle Scholar
Swift, T. and Warren, D. S. 1994. An abstract machine for SLG resolution: Definite programs. In Proc. of the 1994 International Symposium on Logic Programming, Bruynooghe, M., Ed. MIT Press, Massachusetts Institute of Technology, 633–652.Google Scholar
Tarau, P. 1991. A simplified abstract machine for the execution of binary metaprograms. In Proc. of the Logic Programming Conference '91. ICOT, Tokyo, 119–128.Google Scholar
Tarau, P. 1992. Ecological memory management in a continuation passing Prolog engine. In Proc. of the International Workshop on Memory Management(IWMM '92), Bekkers, Y. and Cohen, J., Eds. Lecture Notes in Computer Science, vol. 637. Springer, Berlin, Heidelberg, 344–356.Google Scholar
Tarau, P. 1998. Towards inference and computation mobility: The Jinni experiment. In Proc. of the European Workshop on Logics in Artificial Intelligence (JELIA '98), Dix, J. and Furbach, U., Eds. Lecture Notes in Artificial Intelligence, vol. 1489. Springer, Dagstuhl, Germany, 385–390. Invited talk.Google Scholar
Tarau, P. 1999a. Inference and computation mobility with jinni. In The Logic Programming Paradigm: A 25 Year Perspective, Apt, K., Marek, V. and Truszczynski, M., Eds. Springer, Berlin, Heidelberg, 33–48. ISBN 3-540-65463-1.CrossRefGoogle Scholar
Tarau, P. 1999b. Intelligent Mobile Agent Programming at the Intersection of Java and Prolog. In Proc. of the Fourth International Conference on the Practical Application of Intelligent Agents and Multi-Agents, London, UK, 109–123.Google Scholar
Tarau, P. 1999c. Multi-engine horn clause Prolog. In Proc. of the Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages, Las Cruces, NM, USA, Gupta, G. and Pontelli, E., Eds.Google Scholar
Tarau, P. 2000. Fluents: A refactoring of Prolog for uniform reflection and interoperation with external objects. In Proc. of the First International Conference on Computational Logic (CL '00), Lloyd, J., Ed. Lecture Notes in Computer Science, vol. 1861. Springer-Verlag, London, UK.Google Scholar
Tarau, P. 2004a. Agent oriented logic programming constructs in jinni 2004. In Proc. of the 20th International Conference on Logic Programming (ICLP '04), Demoen, B. and Lifschitz, V., Eds. Lecture Notes in Computer Science, vol. 3132. Springer, Saint-Malo, France, 477–478.Google Scholar
Tarau, P. 2004b. Orthogonal language constructs for agent oriented logic programming. In Proc. of the Fourth Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS '04), Carro, M. and Morales, J. F., Eds. Springer, Saint-Malo, France.Google Scholar
Tarau, P. 2006. BinProlog 11.x Professional Edition: Advanced BinProlog Programming and Extensions Guide. Technical Report. BinNet Corp.Google Scholar
Tarau, P. 2008a. Logic engines as interactors. In Proc. of the 24th International Conference on Logic Programming, de la Banda, M. Garcia and Pontelli, E., Eds. Lecture Notes in Computer Science. Springer, Udine, Italy, 703–707.Google Scholar
Tarau, P. 2008b. The Jinni Prolog Compiler: A fast and flexible Prolog-in-Java [online]. Accessed 2008. URL: http://www.binnetcorp.com/download/jinnidemo/JinniUserGuide.htmlGoogle Scholar
Tarau, P. 2011. Concurrent programming constructs in multi-engine prolog. In Proc. of the ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming (DAMP '11). ACM, New York, NY, USA.Google Scholar
Tarau, P. and Boyer, M. 1990. Elementary logic programs. In Proc. of the Programming Language Implementation and Logic Programming, Deransart, P. and Maluszyński, J., Eds. Lecture Notes in Computer Science, vol. 456. Springer, Berlin, Heidelberg, 159–173.CrossRefGoogle Scholar
Tarau, P. and Boyer, M. 1993. Nonstandard answers of elementary logic programs. In Constructing Logic Programs, Jacquet, J., Ed. J. Wiley, Hoboken, NJ, 279–300.Google Scholar
Tarau, P. and Dahl, V. 1994. Logic programming and logic grammars with first-order continuations. In Proc. of the International Workshop on Logic Program Synthesis and Transformation (LOPSTR '94), Lecture Notes in Computer Science. Springer, Pisa.Google Scholar
Tarau, P. and Dahl, V. 1998. Mobile threads through first order continuations. In Proc. of the APPAI-GULP-PRODE '98, Coruna, Spain.Google Scholar
Tarau, P. and Dahl, V. May 2001. High-level networking with mobile code and first order AND-continuations. Theory and Practice of Logic Programming 1, 3, 359–380. Cambridge University Press.CrossRefGoogle Scholar
Tarau, P. and De Bosschere, K. 1993a. Blackboard based logic programming in BinProlog. In Proc. of the Fifth University of New Brunswick Artificial Intelligence Symposium, Goldfarb, L., Ed. Fredericton, NB, 137–147.Google Scholar
Tarau, P. and De Bosschere, K. 1993b. Memoing with abstract answers and Delphi lemmas. In Logic Program Synthesis and Transformation, Deville, Y., Ed. Springer-Verlag, Louvain-la-Neuve, 196–209.Google Scholar
Tarau, P., De Bosschere, K., Dahl, V. and Rochefort, S. March 1999. LogiMOO: An extensible multi-user virtual world with natural language control. Journal of Logic Programming 38, 3, 331–353.CrossRefGoogle Scholar
Tarau, P., De Bosschere, K. and Demoen, B. November 1996. Partial translation: Towards a portable and efficient Prolog implementation technology. Journal of Logic Programming 29, 1–3, 65–83.CrossRefGoogle Scholar
Tarau, P., De Bosschere, K. and Demoen, B. February 1997. On Delphi lemmas and other memoing techniques for deterministic logic programs. Journal of Logic Programming 30, 2, 145–163.CrossRefGoogle Scholar
Tarau, P., Demoen, B. and De Bosschere, K. 1994. The power of partial translation: An experiment with the C-ification of binary Prolog. In Proc. of the First COMPULOG-NOE Area Meeting on Parallelism and Implementation Technology, Madrid/Spain, de la Banda, M. García, J. and Hermenegildo, M., Eds, Bordeau, France, 3–17.Google Scholar
Tarau, P. and Majumdar, A. 2009. Interoperating logic engines. In Proc. of the 11th International Symposium on Practical Aspects of Declarative Languages (PADL '09). Lecture Notes in Computer Science, vol. 5418. Springer, Savannah, Georgia, 137–151.Google Scholar
Tarau, P. and Neumerkel, U. November 1993. Compact Representation of Terms and Instructions in the BinWAM. Technical Report 93-3, Department of d'Informatique, Université de Moncton. Available by ftp from clement.info.umoncton.caGoogle Scholar
Tyagi, S. and Tarau, P. 2001. A most specific method finding algorithm for reflection based dynamic Prolog-to-Java interfaces. In Proc. of the International Symposium on Practical Aspects of Declarative Languages (PADL '01), Ramakrishan, I. and Gupta, G., Eds. Springer-Verlag, Las Vegas, NV, USA.Google Scholar
Ueda, K. 1985. Guarded horn clauses. In Proc. of the Fourth Conference on Logic Programming, Tokyo, Japan, July 1-3, 1985, Wada, E., Ed. Lecture Notes in Computer Science, vol. 221. Springer, 168–179.Google Scholar
Van Roy, P. 1994. 1983-1993: The wonder years of sequential prolog implementation. Journal of Logic Programming 19, 20, 385–441.CrossRefGoogle Scholar
Wadler, P. 1990. Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science 73, 2, 231–248.CrossRefGoogle Scholar
Warren, D. H. D. October 1983. An abstract Prolog instruction set. Technical Note 309, SRI International.Google Scholar
Wielemaker, J. 2003. Native preemptive threads in SWI-Prolog. In Proc. of the International Conference on Logic Programming (ICLP), Palamidessi, C., Ed. Lecture Notes in Computer Science, vol. 2916. Springer, 331–345.Google Scholar
Zhou, N.-F. 2007. A register-free abstract prolog machine with jumbo instructions. In Proc. of the International Conference on Logic Programming (ICLP), Dahl, V. and Niemelä, I., Eds. Lecture Notes in Computer Science, vol. 4670. Springer, Berlin, Heidelberg, 455–457.Google Scholar
Zhou, N.-F., Takagi, T. and Ushijima, K. 1990. A matching tree oriented abstract machine for Prolog. Logic Programming. MIT Press, Cambridge, MA, USA, 159–173. ISBN: 0-262-73090-1.Google Scholar