Article

A semantics for tracing declarative multi-paradigm programs

Authors:

G. VidalAuthors Info & Claims

PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming

Pages 179 - 190

https://doi.org/10.1145/1013963.1013984

Published: 24 August 2004 Publication History

Abstract

We introduce the theoretical basis for tracing lazy functional logic computations in a declarative multi-paradigm language like Curry. Tracing computations is a difficult task due to the subtleties of the underlying operational semantics which combines laziness and non-determinism. In this work, we define an instrumented operational semantics that generates not only the computed values and bindings but also an appropriate data structure---a sort of redex trail---which can be used to trace computations at an adequate level of abstraction. In contrast to previous approaches, which rely solely on a transformation to instrument source programs, the formal definition of a tracing semantics improves the understanding of the tracing process. Furthermore, it allows us to formally prove the correctness of the computed trail. A prototype implementation of a tracer based on this semantics demonstrates the usefulness of our approach.

References

[1]

E. Albert, M. Hanus, F. Huch, J. Oliver, and G. Vidal. Operational Semantics for Declarative Multi-Paradigm Languages. To appear in Journal of Symbolic Computation, 2004.]]

Digital Library

[2]

S. Antoy. Constructor-based Conditional Narrowing. In Proc. of the 3rd Int'l Conference on Principles and Practice of Declarative Programming (PPDP 2001), pages 199--206. ACM Press, 2001.]]

Digital Library

[3]

B. Braßel, O. Chitil, M. Hanus, and F. Huch. Observing Functional Logic Computations. In Proc. of the Sixth Int'l Symposium on Practical Aspects of Declarative Languages (PADL'04), pages 193--208. Springer LNCS 3057, 2004.]]

[4]

L. Byrd. Understanding the control flow of prolog programs. In Proc. of the Workshop on Logic Programming, Debrecen, 1980.]]

[5]

O. Chitil. A Semantics for Tracing. In 13th Int'l Workshop on Implementation of Functional Languages (IFL 2001), pages 249--254. Ericsson CSL, 2001.]]

[6]

R. Echahed and J. Janodet. Admissible Graph Rewriting and Narrowing. In Proc. of the 1998 Joint Int'l Conf. and Symp. on Logic Programming, pages 325--340. MIT Press, 1998.]]

Digital Library

[7]

A. Gill. Debugging Haskell by Observing Intermediate Data Structures. In Proc. of the 4th Haskell Workshop. University of Nottingham, 2000.]]

[8]

J.C. González-Moreno, M.T. Hortalá-González, F.J. López-Fraguas, and M. Rodríguez-Artalejo. An Approach to Declarative Programming based on a Rewriting Logic. Journal of Logic Programming, 40:47--87, 1999.]]

[9]

M. Hanus. A Unified Computation Model for Functional and Logic Programming. In Proc. of the 24th ACM Symp. on Principles of Programming Languages (POPL'97), pages 80--93. ACM, 1997.]]

Digital Library

[10]

M. Hanus and C. Prehofer. Higher-Order Narrowing with Definitional Trees. Journal of Functional Programming, 9(1):33--75, 1999.]]

Digital Library

[11]

M. Hanus (ed.). Curry: An Integrated Functional Logic Language. Available at: http://www.informatik.uni-kiel.de/~curry/.]]

[12]

J. Launchbury. A Natural Semantics for Lazy Evaluation. In Proc. of the ACM Symp. on Principles of Programming Languages (POPL'93), pages 144--154. ACM Press, 1993.]]

Digital Library

[13]

F. López-Fraguas and J. Sánchez-Hernández. TOY: A Multiparadigm Declarative System. In Proc. of the Int'l Conf. on Rewriting Techniques and Applications (RTA'99), pages 244--247. Springer LNCS 1631, 1999.]]

Digital Library

[14]

H. Nilsson and P. Fritzson. Algorithmic debugging for lazy functional languages. Journal of Functional Programming, 4(3):337--370, 1994.]]

[15]

H. Nilsson and J. Sparud. The Evaluation Dependence Tree as a Basis for Lazy Functional Debugging. Automated Software Engineering, 4(2):121--150, 1997.]]

Digital Library

[16]

S. Peyton Jones, editor. Haskell 98 Language and Libraries : The Revised Report. Cambridge University Press, 2003.]]

[17]

E.Y. Shapiro. Algorithmic Programming Debugging. MIT Press, 1983.]]

Digital Library

[18]

J. Sparud and C. Runciman. Tracing Lazy Functional Computations Using Redex Trails. In Proc. of the 9th Int'l Symp. on Programming Languages, Implementations, Logics and Programs (PLILP'97), pages 291--308. Springer LNCS 1292, 1997.]]

Digital Library

[19]

M. Wallace, O. Chitil, T. Brehm, and C. Runciman. Multiple-View Tracing for Haskell: a New Hat. In Proc. of the 2001 ACM SIGPLAN Haskell Workshop. Universiteit Utrecht UU-CS-2001-23, 2001.]]

Cited By

Hanus M(2013)Functional Logic Programming: From Theory to CurryProgramming Logics10.1007/978-3-642-37651-1_6(123-168)Online publication date: 2013
https://doi.org/10.1007/978-3-642-37651-1_6
Llorens MOliver JSilva JTamarit S(2011)Graph Generation to Statically Represent CSP ProcessesLogic-Based Program Synthesis and Transformation10.1007/978-3-642-20551-4_4(52-66)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20551-4_4
Llorens MOliver JSilva JTamarit S(2010)Graph generation to statically represent CSP processesProceedings of the 20th international conference on Logic-based program synthesis and transformation10.5555/2008282.2008286(52-66)Online publication date: 23-Jul-2010
https://dl.acm.org/doi/10.5555/2008282.2008286
Show More Cited By

Index Terms

A semantics for tracing declarative multi-paradigm programs

Recommendations

Operational semantics for declarative multi-paradigm languages

Declarative multi-paradigm languages combine the most important features of functional, logic and concurrent programming. The computational model of such integrated languages is usually based on a combination of two different operational principles: ...
Declarative semantics of transactions in ORM

In order to specify databases completely at the conceptual level, conceptual database specification languages should contain a data definition (sub)language (DDL), for specifying data structures (+constraints), a data retrieval (sub)language (DRL), for ...
Equivalence of Two Formal Semantics for Functional Logic Programs

A distinctive feature of modern functional logic languages like Toy or Curry is the possibility of programming non-strict and non-deterministic functions with call-time choice semantics. For almost ten years the CRWL framework [J.C. Gonzalez-Moreno, T. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming

August 2004

260 pages

ISBN:1581138199

DOI:10.1145/1013963

General Chair:
Eugenio Moggi
University of Genova, Italy
,
Program Chair:
David S. Warren
Stony Brook University & XSB, Inc., USA

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PPDP04

Sponsor:

PPDP04: Principles and Practice of Declarative Programming 2004

August 24 - 26, 2004

Verona, Italy

Acceptance Rates

Overall Acceptance Rate 230 of 486 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
158
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hanus M(2013)Functional Logic Programming: From Theory to CurryProgramming Logics10.1007/978-3-642-37651-1_6(123-168)Online publication date: 2013
https://doi.org/10.1007/978-3-642-37651-1_6
Llorens MOliver JSilva JTamarit S(2011)Graph Generation to Statically Represent CSP ProcessesLogic-Based Program Synthesis and Transformation10.1007/978-3-642-20551-4_4(52-66)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20551-4_4
Llorens MOliver JSilva JTamarit S(2010)Graph generation to statically represent CSP processesProceedings of the 20th international conference on Logic-based program synthesis and transformation10.5555/2008282.2008286(52-66)Online publication date: 23-Jul-2010
https://dl.acm.org/doi/10.5555/2008282.2008286
Llorens MOliver JSilva JTamarit S(2010)A tracking semantics for CSPProceedings of the 10th international conference on Mathematics of program construction10.5555/1886619.1886636(248-270)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1886619.1886636
Llorens MOliver JSilva JTamarit S(2010)A Tracking Semantics for CSPMathematics of Program Construction10.1007/978-3-642-13321-3_15(248-270)Online publication date: 2010
https://doi.org/10.1007/978-3-642-13321-3_15
Braßel B(2009)A Technique to Build Debugging Tools for Lazy Functional Logic LanguagesElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2009.07.014246(39-53)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.entcs.2009.07.014
Caballero RArtalejo MDel Vado Vírseda R(2008)Declarative diagnosis of missing answers in constraint functional-logic programmingProceedings of the 9th international conference on Functional and logic programming10.5555/1788446.1788478(305-321)Online publication date: 14-Apr-2008
https://dl.acm.org/doi/10.5555/1788446.1788478
Ochoa CSilva JVidal G(2008)Dynamic slicing of lazy functional programs based on redex trailsHigher-Order and Symbolic Computation10.1007/s10990-008-9023-721:1-2(147-192)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/s10990-008-9023-7
Caballero RRodríguez Artalejo Mdel Vado Vírseda R(2008)Declarative Diagnosis of Missing Answers in Constraint Functional-Logic ProgrammingFunctional and Logic Programming10.1007/978-3-540-78969-7_22(305-321)Online publication date: 2008
https://doi.org/10.1007/978-3-540-78969-7_22
Silva JVidal G(2007)Forward slicing of functional logic programs by partial evaluationTheory and Practice of Logic Programming10.5555/1230960.12309687:1-2(215-247)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1230960.1230968
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten