A semantics-based determinacy analysis for prolog with cut | SpringerLink
Skip to main content
Springer Nature Link
Log in

A semantics-based determinacy analysis for prolog with cut

  • Conference paper
  • First Online:
Perspectives of System Informatics (PSI 1996)

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

  • 150 Accesses

Abstract

At PEPM'91 Sahlin presented a determinacy analysis for Prolog with cut. The analysis was, however, not justified in any kind of semantics for Prolog, so correctness was argued with respect to an intuitive idea of the behaviour of Prolog programs.

We now start with a denotational semantics of Prolog and derive a variant of Sahlins analysis as an abstraction of this. We observe that we avoid some problems Sahlin had, and in addition get rid of some redundant domain elements, which our semantics show can not be distinguished by any context.

To obtain better precision in the abstract interpretation we do fixed-point iteration in two steps: First we find the least equivalence class using a powedomain ordering, then we find the least fixed-point within that equivalence class using the subset ordering. We believe this method is original.

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. Abramsky and C. Hankin, Abstract Interpretation of Declarative Languages, Chichester: Ellis Horwood, 1987.

    Google Scholar 

  2. A. de Bruin and E.P. de Vink, Continuation Semantics for PROLOG with Cut, Proceedings of TAPSOFT'89, Springer LNCS 351, pp. 178–192, 1989.

    Google Scholar 

  3. S. K. Debray and P. Mishra, Denotational and Operational Semantics for Prolog, Journal of Logic Programming 5, pp. 61–91, 1988.

    Google Scholar 

  4. N. D. Jones and A. Mycroft, Stepwise Development of Operational and Denotational Semantics for PROLOG, 1984 International Symposium on Logic Programming, pp. 281–288, IEEE Computer Society Press 1984.

    Google Scholar 

  5. G. D. Plotkin, A Powerdomain Construction, SIAM J. of Computing, Vol 5, No.3, September 1976.

    Google Scholar 

  6. D. Sahlin, Determinacy Analysis for Full Prolog, Proceedings of PEPM'91, pp. 23–30, ACM Press 1991.

    Google Scholar 

  7. SICStus Prolog User's Manual (v. 2.1), SICS, 1983

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DIKU, University of Copenhagen, Universitetsparken 1, DK2100, København Ø, Denmark

    Torben Æ. Mogensen

Authors
  1. Torben Æ. Mogensen
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Dines Bjørner Manfred Broy Igor V. Pottosin

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Mogensen, T.Æ. (1996). A semantics-based determinacy analysis for prolog with cut. In: Bjørner, D., Broy, M., Pottosin, I.V. (eds) Perspectives of System Informatics. PSI 1996. Lecture Notes in Computer Science, vol 1181. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62064-8_31

Download citation

  • DOI: https://doi.org/10.1007/3-540-62064-8_31

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-62064-8

  • Online ISBN: 978-3-540-49637-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics