Article

Observing intermediate structures in a parallel lazy functional language

Authors:

Alberto de la Encina,

Fernando Rubio,

Mercedes Hidalgo-HerreroAuthors Info & Claims

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

Pages 109 - 120

https://doi.org/10.1145/1273920.1273935

Published: 14 July 2007 Publication History

Abstract

Due to the use of higher-order functions and laziness, debugging lazy functional programs is not a trivial task. Fortunately, several debuggers have appeared during the last years. However, the difficulty of the debugging process is increased when considering parallel extensions of lazy functional languages. Thus, it is necessary not only to develop practical debuggers, but also to provide a clear semantic environment to understand what the debuggers should do. In this paper we present a formal framework for debugging two different parallel extensions of the lazy functional language Haskell. In order to do that, we define an operational semantics model which allows us to deal with side-effects and parallelism. By doing so, we provide a formalization of a parallel debugger we have already implemented by extending the sequential debugger Hood.

References

[1]

C. Baker-Finch, D. King, and P. W. Trinder. An operational semantics for parallel lazy evaluation. In ACM-SIGPLAN Int. Conf. on Functional Programming (ICFP'00), pages 162--173. ACM, 2000.

Digital Library

[2]

M. Cole. Algorithmic Skeletons: Structure Management of Parallel Computations. MIT Press, 1989. Research Monographs in Parallel and Distributed Computing.

Digital Library

[3]

M. Cole. Bringing skeletons out of the closet: A pragmatic manifesto for skeletal parallel programming. Parallel Computing, 30:389--406, 2004.

Digital Library

[4]

A. Encina, L. Llana, and F. Rubio. Introducing debugging capabilities to natural semantics. In Perspectives of System Informatics (PSI'06), LNCS 4378, pages 195--208. Springer-Verlag, 2006.

Digital Library

[5]

A. Encina, L. Llana, and F. Rubio. Introducing debugging capabilities to natural semantics (extended version). Available from authors, 2006.

[6]

A. Encina and R. Peña. Formally deriving an STG machine. In Principles and Practice of Declarative Programming (PPDP'03), pages 102--112. ACM, 2003.

Digital Library

[7]

A. Encina, I. Rodríguez, and F. Rubio. Testing speculative work in a lazy/eager parallel functional language. In Languages and Compilers for Parallel Computing (LCPC'05), LNCS 4339, pages 274--288. Springer-Verlag, 2007.

Digital Library

[8]

A. Gill. Debugging Haskell by observing intermediate data structures. In Proceedings of the 4th Haskell Workshop. Tech. Rep. University of Nottingham, 2000.

[9]

M. Hidalgo-Herrero. Semánticas formales para un lenguaje funcional paralelo. PhD thesis, Universidad Complutense de Madrid, 2004.

[10]

M. Hidalgo-Herrero and Y. Ortega-Mallén. An operational semantics for the parallel language Eden. Parallel Processing Letters, 12(2):211--228, 2002.

[11]

U. Klusik, R. Loogen, S. Priebe, and F. Rubio. Implementation skeletons in Eden: Low-effort parallel programming. In Implementation of Functional Languages (IFL'00), LNCS 2011, pages 71--88. Springer-Verlag, 2001.

Digital Library

[12]

H. W. Loidl, F. Rubio, N. Scaife, K. Hammond, S. Horiguchi, U. Klusik, R. Loogen, G. J. Michaelson, R. Peña, Á. J. Rebón Portillo, S. Priebe, and P. W. Trinder. Comparing parallel functional languages: Programming and performance. Higher-Order and Symbolic Computation, 16(3):203--251, 2003.

Digital Library

[13]

R. Peña and F. Rubio. Parallel functional programming at two levels of abstraction. In Principles and Practice of Declarative Programming (PPDP'01), pages 187--198. ACM, 2001.

Digital Library

[14]

S. L. Peyton Jones and J. Hughes. Report on the programming language Haskell 98. Technical report, 1999. http://www.haskell.org.

[15]

C. Reinke. GHood -- graphical visualization and animation of Haskell object observations. In Proceedings of the 5th Haskell Workshop, volume 59 of ENTCS. Elsevier Science, 2001.

[16]

N. Scaife, H. S., G. Michaelson, and P. Bristow. A parallel SML compiler based on algorithmic skeletons. J. Functional Programming, 15(4):615--650, 2005.

Digital Library

[17]

P. W. Trinder, K. Hammond, J. S. M. Jr., A. S. Partridge, and S. L. P. Jones. GUM: a portable parallel implementation of Haskell. In Programming Language Design and Implementation (PLDI'96), pages 79--88. ACM Press, 1996.

Digital Library

[18]

P. W. Trinder, K. H. Hammond, H. W. Loidl, and S. L. Peyton Jones. Algorithm + Strategy = Parallelism. Journal of Funcional Programming, 8(1):23--60, 1998.

Digital Library

[19]

P. W. Trinder, H. Loidl, and R. Pointon. Parallel and distributed Haskells. Journal of Functional Programming, 12(4-5):469--510, 2002.

Digital Library

Cited By

de la Encina AHidalgo-Herrero MLlana LRubio F(2020)A Semantic Framework to Debug Parallel Lazy Functional LanguagesMathematics10.3390/math80608648:6(864)Online publication date: 26-May-2020
https://doi.org/10.3390/math8060864
Loogen R(2011)Eden --- parallel functional programming with haskellProceedings of the 4th Summer School conference on Central European Functional Programming School10.1007/978-3-642-32096-5_4(142-206)Online publication date: 14-Jun-2011
https://dl.acm.org/doi/10.1007/978-3-642-32096-5_4

Index Terms

Observing intermediate structures in a parallel lazy functional language
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. Formal language definitions
      1. Semantics
      2. Syntax
    2. General programming languages
      1. Language types
        Functional languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics
      1. Operational semantics

Recommendations

Comparing alternative evaluation strategies for stream-based parallel functional languages
IFL'06: Proceedings of the 18th international conference on Implementation and application of functional languages

In parallel functional languages, like Eden, lazy and strict evaluation are commonly mixed. Thus, the parallel performance of these languages depends on the strategy used to fix the degrees of laziness/ strictness. By using an implementation of Eden's ...
Thunk recycling for lazy functional languages: operational semantics and correctness
SAC '15: Proceedings of the 30th Annual ACM Symposium on Applied Computing

Lazy evaluation helps programmers write clear programs. However, it has significant run-time overheads for building many as-yet unevaluated expressions, or thunks. Because thunk allocation is a space-consuming task, it is important to reduce the number ...
To be or not to be ...lazy (In a Parallel Context)

Laziness restricts the exploitation of parallelism because expressions are evaluated only on demand. Thus, parallel extensions of lazy functional languages, like Haskell, usually override laziness to some extent. The purpose of the present work is to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2007

240 pages

ISBN:9781595937698

DOI:10.1145/1273920

General Chair:
Michael Leuschel
University of Düsseldorf, Germany
,
Program Chair:
Andreas Podelski
University of Freiburg, Germany

Copyright © 2007 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: 14 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PPDP07

Sponsor:

PPDP07: Principles and Practice of Declarative Programming

July 14 - 16, 2007

Wroclaw, Poland

Acceptance Rates

Overall Acceptance Rate 230 of 486 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
157
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

de la Encina AHidalgo-Herrero MLlana LRubio F(2020)A Semantic Framework to Debug Parallel Lazy Functional LanguagesMathematics10.3390/math80608648:6(864)Online publication date: 26-May-2020
https://doi.org/10.3390/math8060864
Loogen R(2011)Eden --- parallel functional programming with haskellProceedings of the 4th Summer School conference on Central European Functional Programming School10.1007/978-3-642-32096-5_4(142-206)Online publication date: 14-Jun-2011
https://dl.acm.org/doi/10.1007/978-3-642-32096-5_4

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