A Novel Implementation of the Extended Andorra Model

  • Ricardo Lopes
  • Vítor Santos Costa
  • Fernando Silva
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1990)


Logic programming is based on the idea that computation is controlled inference. The Extended Andorra Model provides a very powerful framework that supports both co-routining and parallelism. We present the BEAM, a design that builds upon David H. D.Warren’s original EAM with Implicit Control. The BEAM supports Warren’s original EAM rewrite rules plus eager splitting and sequential conjunctions. We discuss the main issues in the implementation of the BEAM and show that the EAM with Implicit Control can perform quite well when compared with other implementations that use the Andorra principle.


Logic Programming Execution Mechanisms Language Implementation 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    K. A. M. Ali and R. Karlsson. The Muse Or-parallel Prolog Model and its Performance. In NACLP’90, MIT Press, 757–776, October 1990.Google Scholar
  2. [2]
    F. Bueno and M. V. Hermenegildo. An Automatic Translations Scheme from Prolog to the Andorra Kernel Language. In International Conference on Fifth Generation Computer Systems 1992, 759–769. ICOT, Tokyo, Japan, June 1992.Google Scholar
  3. [3]
    B. Carlson, S. Haridi, and S. Janson. AKL(FD)-A concurrent language for FD programming. In ILPS’94, MIT Press, 521–535, 1994.Google Scholar
  4. [4]
    K. L. Clark, F. G. McCabe, and S. Gregory. IC-PROLOG-language features. In Logic Programming, 253–266. Academic Press, 1982.Google Scholar
  5. [5]
    A. Colmerauer. Theoretical Model of Prolog II. In Logic Programming and its Applications, 3–31. Ablex Publishing Corporation, 1986.Google Scholar
  6. [6]
    J. A. Crammond. The abstract machine and implementation of parallel parlog. New Generation Computing, 10(4):385–422, 1992.Google Scholar
  7. [7]
    L. Damas, V. Santos Costa, R. Reis, and R. Azevedo. YAP User’s Guide and Reference Manual, 1998.Google Scholar
  8. [8]
    G. Gupta and E. Pontelli. Extended dynamic dependent And-parallelism in ACE. In PASCO’ 97, ACM Press, 68–79, July 1997.Google Scholar
  9. [9]
    G. Gupta and D. Warren. An Interpreter for the Extended Andorra Model. Internal report, University of Bristol, 1991.Google Scholar
  10. [10]
    M. V. Hermenegildo and K. Greene. &-Prolog and its Performance: Exploiting Independent And-Parallelism. New Generation Computing, 9(3,4):233–257, 1991.Google Scholar
  11. [11]
    S. Janson. AKL-A Multiparadigm Programming Language. SICS Dissertation Series 14, Uppsala University, 1994.Google Scholar
  12. [12]
    R. Jones and R. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley and Sons, July 1996. Reprinted February 1997.Google Scholar
  13. [13]
    R. Lopes and V. S. Costa. The BEAM: Towards a first EAM Implementation. In Parallelism and Implementation of Logic and Constraint Programming, 87–106. Nova Sicence, 1999.Google Scholar
  14. [14]
    R. Lopes and V. Santos Costa. Memory Management for the BEAM. In CL2000 First Workshop on Memory Management in Logic Programs, Technical Report of Dept. Comp. Science, K.U.Leuven, July 2000.Google Scholar
  15. [15]
    R. Lopes, F. Silva, V. Santos Costa, and S. Abreu. The RAINBOW: Towards a Parallel Beam. In Workshop on Parallelism and Implementation Technology for (Constraint) Logic Languages, July 2000.Google Scholar
  16. [16]
    E. Lusk, et. al., The Aurora or-parallel Prolog system. New Generation Computing, 7(2,3):243–271, 1990.CrossRefGoogle Scholar
  17. [17]
    J. Montelius and K. A. M. Ali. An And/Or-Parallel Implementation of AKL. New Generation Computing, 13(4), 1995.Google Scholar
  18. [18]
    R. Moolenaar and B. Demoen. Hybrid tree search in the Andorra Model. In ICLP’94, MIT Press, 110–123, June 1994.Google Scholar
  19. [19]
    L. Naish. Negation and Control in Prolog. Springer-Verlag, LNCS 238, 1985.Google Scholar
  20. [20]
    K. F. Sagonas, T. Swift, D. S. Warren, J. Freire, and P. Rao. The XSB programmer’s manual. Technical report, State University of New York at Stony Brook, 1997.Google Scholar
  21. [21]
    V. Santos Costa, D. H. D. Warren, and R. Yang. Andorra-I: A Parallel Prolog System that Transparently Exploits both And-and Or-Parallelism. In ACM SIGPLAN Notices, vol 26(7), July 1991.Google Scholar
  22. [22]
    V. Santos Costa, D. H. D. Warren, and R. Yang. The Andorra-I Preprocessor: Supporting full Prolog on the Basic Andorra model. In ICLP’91, MIT Press, 443–456, June 1991.Google Scholar
  23. [23]
    E. Shapiro. The family of Concurrent Logic Programming Languages. ACM computing surveys, 21(3):412–510, 1989.CrossRefGoogle Scholar
  24. [24]
    D. H. D. Warren. The Andorra model. Presented at Gigalips Project workshop, University of Manchester, March 1988.Google Scholar
  25. [25]
    D. H. D. Warren. The Extended Andorra Model with Implicit Control. Presented at ICLP’90 Workshop on Parallel Logic Programming, Eilat, Israel, June 1990Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Ricardo Lopes
    • 1
  • Vítor Santos Costa
    • 2
  • Fernando Silva
    • 1
  1. 1.DCC-FC and LIACCUniversidade do PortoPortugal
  2. 2.COPPE-SistemasUniversidade Federal do Rio de JaneiroBrasil

Personalised recommendations