More Web Proxy on the site http://driver.im/

research-article

Pattern minimization problems over recursive data types

Author:

Alexander KraussAuthors Info & Claims

ACM SIGPLAN Notices, Volume 43, Issue 9

Pages 267 - 274

https://doi.org/10.1145/1411203.1411242

Published: 20 September 2008 Publication History

Abstract

In the context of program verification in an interactive theorem prover, we study the problem of transforming function definitions with ML-style (possibly overlapping) pattern matching into minimal sets of independent equations. Since independent equations are valid unconditionally, they are better suited for the equational proof style using induction and rewriting, which is often found in proofs in theorem provers or on paper.

We relate the problem to the well-known minimization problem for propositional DNF formulas and show that it is £P/2-complete. We then develop a concrete algorithm to compute minimal patterns, which naturally generalizes the standard Quine-McCluskey procedure to the domain of term patterns.

Supplementary Material

JPG File (1411242.jpg)

Download
14.31 KB

index.html (index.html)

Slides from the presentation

Download
.98 KB

ZIP File (p267-slides.zip)

Supplemental material for: Pattern minimization problems over recursive data types

Download
13.52 MB

Audio only (1411242.mp3)

Download
9.42 MB

Video (1411242.mp4)

Download
130.47 MB

References

[1]

Lennart Augustsson. Compiling pattern matching. In FPCA'85, pages 368--381, 1985.

Digital Library

[2]

Marianne Baudinet and David MacQueen. Tree pattern matching for ML. URL http://www.smlnj.org/compiler-notes/85-note-baudinet.ps. Unpublished, 1985.

[3]

R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston, MA, 1984.

Digital Library

[4]

Amine Chaieb. Verifying mixed real-integer quantifier elimination. In Ulrich Furbach and Natarajan Shankar, editors, Automated Reasoning, Third International Joint Conference, LNAI 4130, pages 528--540. Springer, 2006. ISBN 3-540-37187-7.

Digital Library

[5]

Amine Chaieb. Automated methods for formal proofs in simple arithmetics and algebra. D thesis, Technische Universität München, Germany, April 2008.

[6]

Fabrice Le Fessant and Luc Maranget. Optimizing pattern matching. In ICFP, pages 26--37, 2001.

Digital Library

[7]

Michael Gordon and Tom Melham, editors. Introduction to HOL: A theorem proving environment for higher order logic. Cambridge University Press, 1993.

Digital Library

[8]

Gérard Huet. Confluent reductions: Abstract properties and applications to term rewriting systems. J. ACM, 27 (4): 797--821, 1980.

Digital Library

[9]

John Hughes. The Design of a Pretty-printing Library. In J. Jeuring and E. Meijer, editors, Advanced Functional Programming, volume 925 of LNCS. Springer Verlag, 1995.

Digital Library

[10]

Randy H. Katz and Gaetano Borriello. Contemporary Logic Design. Prentice Hall, 2005.

Digital Library

[11]

E. J. McCluskey. Logic Design Principles. Prentice Hall, 1986.

[12]

E. J. McCluskey. Minimization of boolean formulas. Bell Lab. Tech. J., 35 (6): 1417--1444, Nov 1956.

[13]

Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. Isabelle/HOL - A Proof Assistant for Higher-Order Logic. LNCS 2283. Springer, 2002.

Digital Library

[14]

Chris Okasaki. Red-black trees in a functional setting. J. Funct. Program., 9 (4): 471--477, 1999.

Digital Library

[15]

Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, New York, 1994.

[16]

Markus Schaefer and Christopher Umans. Completeness in the polynomial-time hierarchy: Part I: A compendium. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 33, 2002.

[17]

Konrad Slind. Reasoning About Terminating Functional Programs. D thesis, Institut für Informatik, TU München, 1999.

[18]

Tadeusz Strzemecki. Polynomial-time algorithms for generation of prime implicants. J. Complexity, 8 (1): 37--63, 1992.

Digital Library

[19]

Simon Thompson. Haskell: The Craft of Functional Programming (2nd Edition). Addison-Wesley, 1999.

Digital Library

[20]

Christopher Umans. Approximability and completeness in the polynomial hierarchy. D thesis, University of California, Berkeley, 2000.

Digital Library

[21]

Christopher Umans, Tiziano Villa, and Alberto L. Sangiovanni-Vincentelli. Complexity of two-level logic minimization. IEEE Trans. on CAD of Integrated Circuits and Systems, 25 (7): 1230--1246, 2006.

Digital Library

[22]

Philip Wadler. Efficient compilation of pattern-matching. In S. L. Peyton Jones, The Implementation of Functional Programming Languages, chapter 5. Prentice-Hall International, 1987.

[23]

Lyndon While and Tony Field. Optimising parallel pattern-matching by source-level program transformation. In Vladimir Estivill-Castro, editor, ACSC, volume 38 of CRPIT, pages 239--248. Australian Computer Society, 2005. ISBN 1-920682-20-1.

Digital Library

Cited By

Cirstea HLermusiaux PMoreau P(2023)Generic Encodings and Static Analysis of Constructor Rewriting Systems2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC61333.2023.00056(1-4)Online publication date: 11-Sep-2023
https://doi.org/10.1109/SYNASC61333.2023.00056
Lermusiaux PMontagu B(2024)Detection of Uncaught Exceptions in Functional Programs by Abstract InterpretationProgramming Languages and Systems10.1007/978-3-031-57267-8_15(391-420)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57267-8_15
Cirstea HMoreau PKomendantskaya E(2019)Generic Encodings of Constructor Rewriting SystemsProceedings of the 21st International Symposium on Principles and Practice of Declarative Programming10.1145/3354166.3354173(1-12)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1145/3354166.3354173
Show More Cited By

Index Terms

Pattern minimization problems over recursive data types
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Pattern minimization problems over recursive data types
ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming

In the context of program verification in an interactive theorem prover, we study the problem of transforming function definitions with ML-style (possibly overlapping) pattern matching into minimal sets of independent equations. Since independent ...
Completeness and Cut-elimination in the Intuitionistic Theory of Types

In this paper we define a model theory and give a semantic proof of cut-elimination for ICTT, an intuitionistic formulation of Church's theory of types defined by Miller et al. and the basis for the λProlog programming language. Our approach, extending ...
Polymorphic lemmas and definitions in $\lambda$Prolog and Twelf

$\lambda$Prolog is known to be well-suited for expressing and implementing logics and inference systems. We show that lemmas and definitions in such logics can be implemented with a great economy of expression. We encode a higher-order logic using an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 43, Issue 9

ICFP '08

September 2008

399 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1411203

Issue’s Table of Contents

ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming
September 2008
422 pages
ISBN:9781595939197
DOI:10.1145/1411204
General Chair:
James Hook
Portland State University, USA
,
Program Chair:
Peter Thiemann
Universität Freiburg, Germany

Copyright © 2008 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 September 2008

Published in SIGPLAN Volume 43, Issue 9

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
286
Total Downloads

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

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cirstea HLermusiaux PMoreau P(2023)Generic Encodings and Static Analysis of Constructor Rewriting Systems2023 25th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)10.1109/SYNASC61333.2023.00056(1-4)Online publication date: 11-Sep-2023
https://doi.org/10.1109/SYNASC61333.2023.00056
Lermusiaux PMontagu B(2024)Detection of Uncaught Exceptions in Functional Programs by Abstract InterpretationProgramming Languages and Systems10.1007/978-3-031-57267-8_15(391-420)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57267-8_15
Cirstea HMoreau PKomendantskaya E(2019)Generic Encodings of Constructor Rewriting SystemsProceedings of the 21st International Symposium on Principles and Practice of Declarative Programming10.1145/3354166.3354173(1-12)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1145/3354166.3354173
Antoy SHanus M(2016)Default Rules for CurryPractical Aspects of Declarative Languages10.1007/978-3-319-28228-2_5(65-82)Online publication date: 9-Jan-2016
https://doi.org/10.1007/978-3-319-28228-2_5

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.

Media

Figures

Other

Tables

View Issue’s Table of Contents