Views: a way for pattern matching to cohabit with data abstraction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Views: a way for pattern matching to cohabit with data abstraction

Full text

Pdf (727 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages table of contents

Munich, West Germany

Pages: 307 - 313

Year of Publication: 1987

ISBN:0-89791-215-2

Author

P. Wadler

Programming Research Group, Oxford University, UK and Programming Methodology Group, Chalmers University, Sweden

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 66, Citation Count: 43

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/41625.41653 What is a DOI?

ABSTRACT

Pattern matching and data abstraction are important concepts in designing programs, but they do not fit well together. Pattern matching depends on making public a free data type representation, while data abstraction depends on hiding the representation. This paper proposes the views mechanism as a means of reconciling this conflict. A view allows any type to be viewed as a free data type, thus combining the clarity of pattern matching with the efficiency of data abstraction.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Aug84	Lennart Augustsson, A compiler for lazy ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.218-227, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802038]
	Aug85	Lennart Augustsson, Compiling pattern matching, Proc. of a conference on Functional programming languages and computer architecture, p.368-381, January 1985, Nancy, France
	BD77	R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
	Bir86	R.S. Bird. An introduction to the theory of lists. In Marktoberdory Workshop on Logics of ProgrammingI August 1985.
	BMS80	R. Buretall, D. MacQueen, and D. Sanella. Hope: An ezpe~/mental applicatiee lancua~c. Technical Report Report CSR-62-80, Edinburgh University, Computer Science Dept., 1980.
	Bur69	R.M. Bur~taU. Proving properties of programs by structural induction. The Comp~tter Journal, 12(1), February 1969.
	FGJM85	Kokichi Futatsugi , Joseph A. Goguen , Jean-Pierre Jouannaud , José Meseguer, Principles of OBJ2, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.52-66, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318610]
	FW86	Jon Fairbairn , Stuart C. Wray, Code generation techniques for functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.94-104, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319853]
	HK84	Paul Hudak , David Kranz, A combinator-based compiler for a functional language, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.122-132, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800523]
	Joh85	Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
	Mee84	L. Meertene. Algorithmlcs: Towards programming as a mathematical activity. In J. W. de Bskker, et. al., editors, Mathematics and Competer Science, North-Holland, 1984.
	Pey87	S.L. Peyton-Jonee. Implementing Functional Languafes udng Graph Redttction. Prentice-Hall, 1987.
	SH82	M.R. Sleep and S. HolmetrBm. A short note concerning lazy reduction rules of append. Sofltvare Practice and Ezpcr/ence, 12(11):1082--4, November 1982.
	Tho86	Simon Thompson, Laws in Miranda, Proceedings of the 1986 ACM conference on LISP and functional programming, p.1-12, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319839]
	Tur81	D.A. Turner. Recuraion equatio~ as a programming language. In J. Darlington, P. Henderson, and D. Turner, editors, Fur, ction~l Procmmming and lt~ Applications, Cambridge University Press, 1981.
	Tur85	D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
	Wad87	P.L. Wadler. Compiling pattera matching; Lkt comprehenalone. In {Peyg?}.

CITED BY 43

	Steven Prestwich, Online partial deduction of logic programs, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.111-118, June 14-16, 1993, Copenhagen, Denmark
	Pedro Palao Gostanza , Ricardo Peña , Manuel Núñez, A new look at pattern matching in abstract data types, ACM SIGPLAN Notices, v.31 n.6, p.110-121, June 15, 1996
	Ralf Hinze, A simple implementation technique for priority search queues, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Dominic Duggan, Type-based hot swapping of running modules (extended abstract), ACM SIGPLAN Notices, v.36 n.10, October 2001
	Franklyn Turbak , J. B. Wells, Cycle therapy: a prescription for fold and unfold on regular trees, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.137-149, September 05-07, 2001, Florence, Italy
	Chris Okasaki, Breadth-first numbering: lessons from a small exercise in algorithm design, ACM SIGPLAN Notices, v.35 n.9, p.131-136, Sept. 2000
	Bjorn N. Freeman-Benson, Kaleidoscope: mixing objects, constraints, and imperative programming, ACM SIGPLAN Notices, v.25 n.10, p.77-88, Oct. 1990
	Manuel Fähndrich , John Boyland, Statically checkable pattern abstractions, ACM SIGPLAN Notices, v.32 n.8, p.75-84, Aug. 1997
	Chris Okasaki, Purely functional random-access lists, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.86-95, June 26-28, 1995, La Jolla, California, United States
	Chris Okasaki, Catenable double-ended queues, ACM SIGPLAN Notices, v.32 n.8, p.66-74, Aug. 1997
	Cordelia V. Hall, Using Hindley-Milner type inference to optimise list representation, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.162-172, July-Sept. 1994
	Zhong Shao , John H. Reppy , Andrew W. Appel, Unrolling lists, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.185-195, July-Sept. 1994
	Lyndon While , Greg Mildenhall, An implementation of parallel pattern-matching via concurrent haskell, Australian Computer Science Communications, v.24 n.1, p.293-302, January-February 2002
	Josef Svenningsson, Shortcut fusion for accumulating parameters & zip-like functions, ACM SIGPLAN Notices, v.37 n.9, p.124-132, September 2002
	John Launchbury , Jeffrey R. Lewis , Byron Cook, On embedding a microarchitectural design language within Haskell, ACM SIGPLAN Notices, v.34 n.9, p.60-69, Sept. 1999
	Paul Hudak, Conception, evolution, and application of functional programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.359-411, Sep. 1989
	Martin Erwig, Functional programming with graphs, ACM SIGPLAN Notices, v.32 n.8, p.52-65, Aug. 1997
	J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bi-directional tree transformations: a linguistic approach to the view update problem, ACM SIGPLAN Notices, v.40 n.1, p.233-246, January 2005
	Bruno C. d. S. Oliveira , Jeremy Gibbons, TypeCase: a design pattern for type-indexed functions, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.98-109, September 30-30, 2005, Tallinn, Estonia
	Claude Kirchner , Pierre-Etienne Moreau , Antoine Reilles, Formal validation of pattern matching code, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.187-197, July 11-13, 2005, Lisbon, Portugal
	Shay Artzi , Michael D. Ernst, Using predicate fields in a highly flexible industrial control system, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
	Iavor S. Diatchki , Mark P. Jones , Rebekah Leslie, High-level views on low-level representations, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Todd Millstein, Practical predicate dispatch, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Don Syme , Gregory Neverov , James Margetson, Extensible pattern matching via a lightweight language extension, ACM SIGPLAN Notices, v.42 n.9, September 2007
	Koji Kagawa, Polymorphic variants in Haskell, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA
	Don Syme, Leveraging .NET meta-programming components from F#: integrated queries and interoperable heterogeneous execution, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA
	Jean-Christophe Filliâtre , Sylvain Conchon, Type-safe modular hash-consing, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA
	Paul Hudak , John Hughes , Simon Peyton Jones , Philip Wadler, A history of Haskell: being lazy with class, Proceedings of the third ACM SIGPLAN conference on History of programming languages, p.12-1-12-55, June 09-10, 2007, San Diego, California
	J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.3, p.17-es, May 2007
	Roberto Di Cosmo, A short survey of isomorphisms of types, Mathematical Structures in Computer Science, v.15 n.5, p.825-838, October 2005
	Gilles Barthe, A computational view of implicit coercions in type theory, Mathematical Structures in Computer Science, v.15 n.5, p.839-874, October 2005
	P Wadler, A critique of Abelson and Sussman or why calculating is better than scheming, ACM SIGPLAN Notices, v.22 n.3, p.83-94, March 1987
	J. C. Royer, A new set interpretation of the inheritance relation and its checking, ACM SIGPLAN OOPS Messenger, v.3 n.3, p.22-40, July 1992
	Martin Erwig, Inductive graphs and functional graph algorithms, Journal of Functional Programming, v.11 n.5, p.467-492, September 2001
	Hélène Kirchner , Pierre-Etienne Moreau, Promoting rewriting to a programming language: a compiler for non-deterministic rewrite programs in associative-commutative theories, Journal of Functional Programming, v.11 n.2, p.207-251, March 2001
	Conor McBride , James McKinna, The view from the left, Journal of Functional Programming, v.14 n.1, p.69-111, January 2004
	P. Jouvelot , B. Dehbonei, Recursive Pattern Matching on concrete data types, ACM SIGPLAN Notices, v.24 n.11, p.84-93, Nov. 1989
	Kazutaka Matsuda , Zhenjiang Hu , Keisuke Nakano , Makoto Hamana , Masato Takeichi, Bidirectionalization transformation based on automatic derivation of view complement functions, ACM SIGPLAN Notices, v.42 n.9, September 2007
	Geoffrey Mainland, Why it's nice to be quoted: quasiquoting for haskell, Proceedings of the ACM SIGPLAN workshop on Haskell workshop, September 30-30, 2007, Freiburg, Germany
	Nicolas Oury , Wouter Swierstra, The power of Pi, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Pablo Nogueira , Juan José Moreno-Navarro, Bialgebra views: a way for polytypic programming to cohabit with data abstraction, Proceedings of the ACM SIGPLAN workshop on Generic programming, September 20-20, 2008, Victoria, BC, Canada
	Morten Rhiger, Type-safe pattern combinators, Journal of Functional Programming, v.19 n.2, p.145-156, March 2009
	Xin Qi , Andrew C. Myers, Sharing classes between families, ACM SIGPLAN Notices, v.44 n.6, June 2009