A demand driven computation strategy for lazy narrowing | SpringerLink
Skip to main content
Springer Nature Link
Log in

A demand driven computation strategy for lazy narrowing

  • Conference paper
  • First Online:
Progamming Language Implementation and Logic Programming (PLILP 1993)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 714))

Abstract

Many recent proposals for the integration of functional and logic programming use conditional term rewriting systems (CTRS) as programs and narrowing as goal solving mechanism. This paper specifies a computation strategy for lazy conditional narrowing, based on the idea of transforming patterns into decision trees to control the computation. The specification is presented as a translation of CTRS into Prolog, which makes it executable and portable. Moreover, in comparison to related approaches, our method works for a wider class of CTRS.

This research has been partially supported by the Spanish National Project TIC92-0793 “PDR”, the Esprit BRA Working Group Nr. 6028 “CCL” and the grant In 20/6-1 from the German Research Community.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Antoy: Lazy Evaluation in Logic, Symp. on Programming Language Implementation and Logic Programming 1991, LNCS 528, Springer Verlag 1991, 371–382.

    Google Scholar 

  2. S. Antoy: Definitional Trees, Int. Conf. on Algebraic and Logic Programming (ALP) 92, LNCS 632, Springer Verlag 1992, 143–157.

    Google Scholar 

  3. P.G. Bosco, C. Cecchi, and C. Moiso: An extension of WAM for K-LEAF, 6th Int. Conf. on Logic Programming, Lisboa, 1989, 318–333.

    Google Scholar 

  4. M. M. T. Chakravarty, H. C. R. Lock: The Implementation of Lazy Narrowing, Symp. on Programming Language Implementation and Logic Programming 1991, LNCS 528, Springer Verlag 1991, 123–134.

    Google Scholar 

  5. P.H. Cheong: Compiling lazy narrowing into Prolog, Technical Report 25, LIENS, 1990, to appear in: Journal of New Generation Computing.

    Google Scholar 

  6. P.H. Cheong and L. Fribourg: A survey of the implementations of narrowing, in: J. Darlington and R. Dietrich (eds.) Declarative Programming. Workshops in Computing, Springer Verlag & BCS, 1992, 177–187.

    Google Scholar 

  7. M. Dershowitz, M. Okada: A rationale for conditional equational rewriting, Theoret. Comput. Sci. 75(1/2),1990,11–137.

    Google Scholar 

  8. E. Giovannetti, G. Levi, C. Moiso, C. Palamidessi: Kernel LEAF: A Logic plus Functional Language, Journal of Computer and System Sciences, Vol. 42, No. 2, Academic Press 1991, 139–185.

    Google Scholar 

  9. J.C. González Moreno, M.T. Hortalá González, M. Rodríguez Artalejo: On the Completeness of Narrowing as the Operational Semantics of Functional Logic Programming, to appear in: Computer Science Logic (CSL) 92, LNCS 702, Springer Verlag 1993 (15 pp.).

    Google Scholar 

  10. W. Hans, R. Loogen, St. Winkler: On the Interaction of Lazy Evaluation and Backtracking, Int. Symp. on Programming Language Implementation and Logic Programming (PLILP) 92, LNCS 631, Springer Verlag 1992.

    Google Scholar 

  11. J.A. Jiménez Martín, J. Mariño Carballo, J.J. Moreno Navarro: Efficient Compilation of Lazy Narrowing into Prolog, LOPSTR 92, LNCS, Springer Verlag 1992.

    Google Scholar 

  12. R. Loogen: From reduction machines to narrowing machines, TAPSOFT 91, CCPSD, LNCS 494, Springer Verlag 1991, 438–457.

    Google Scholar 

  13. R. Loogen, St. Winkler: Dynamic Detection of Determinism in Functional Logic Languages, Int. Symp. on Programming Language Implementation and Logic Programming (PLILP) 91, LNCS 528, Springer Verlag 1991, 335–346 (revised version to appear in TCS).

    Google Scholar 

  14. R. Loogen, F. J. López Fraguas, M. Rodríguez Artalejo: A Demand Driven Computation Strategy for Lazy Narrowing, Tech. Rep. Dep. Informática y Automática, UCM, Madrid, 1993.

    Google Scholar 

  15. J. J. Moreno Navarro, M. Rodríguez Artalejo: Logic Programming with Functions and Predicates: The Language BABEL, Journal of Logic Programming Vol. 12, North Holland 1992, 191–223.

    Google Scholar 

  16. J.J. Moreno-Navarro, H. Kuchen, R. Loogen and M. Rodríguez-Artalejo: Lazy narrowing in a graph machine, Conf. on Algebraic and Logic Programming (ALP 90), LNCS 463, Springer Verlag 1990, 298–317.

    Google Scholar 

  17. S. Narain: A technique for doing lazy evaluation in logic, The Journal of Logic Programming, 3, 1986, 259–276.

    Google Scholar 

  18. U.S. Reddy: Narrowing as the operational semantics of functional languages, IEEE Symp. on Logic Programming, IEEE Comp. Soc. Press 1985, 138–151.

    Google Scholar 

  19. P. Wadler: Efficient Compilation of Pattern-Matching, Chapter 5 in: S. PeytonJones: The Implementation of Functional Programming Languages, Prentice Hall 1987.

    Google Scholar 

  20. D.H.D. Warren: An abstract Prolog instruction set, Technical Report 309, SRI International 1983.

    Google Scholar 

  21. D. Wolz: Design of a compiler for lazy pattern driven narrowing, 7th. Workshop on Specification of ADTs, LNCS 534, Springer Verlag 1991, 362–379.

    Google Scholar 

  22. J. H. You: Enumerating Outer Narrowing Derivations for Constructor-Based Term Rewriting Systems, Journal of Symbolic Computation 7, 1989, 319–341.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Lehrstuhl für Informatik II, RWTH Aachen, 52056, Aachen, Germany

    Rita Loogen

  2. Departamento de Informática y Automática Facultad de C.C. Matemáticas, Universidad Complutense de Madrid, Av. Complutense s/n, 28040, Madrid, Spain

    Francisco López Fraguas & Mario Rodríguez Artalejo

Authors
  1. Rita Loogen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francisco López Fraguas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mario Rodríguez Artalejo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Maurice Bruynooghe Jaan Penjam

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Loogen, R., Fraguas, F.L., Artalejo, M.R. (1993). A demand driven computation strategy for lazy narrowing. In: Bruynooghe, M., Penjam, J. (eds) Progamming Language Implementation and Logic Programming. PLILP 1993. Lecture Notes in Computer Science, vol 714. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57186-8_79

Download citation

  • DOI: https://doi.org/10.1007/3-540-57186-8_79

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-57186-5

  • Online ISBN: 978-3-540-47945-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation