Type-safe cast

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Type-safe cast: (functional pearl)

Full text

Pdf (372 KB)

Source

International Conference on Functional Programming archive
Proceedings of the fifth ACM SIGPLAN international conference on Functional programming table of contents

Pages: 58 - 67

Year of Publication: 2000

ISBN:1-58113-202-6

Also published in ...

Author

Stephanie Weirich

Department of Computer Science, Cornell University, Ithaca, NY

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 35, Citation Count: 20

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/351240.351246 What is a DOI?

ABSTRACT

In a language with non-parametric or ad-hoc polymorphism, it is possible to determine the identity of a type variable at run-time. With this facility, we can write a function to convert a term from one abstract type to another, if the two hidden types are identical. However, the naive implementation of this function requires that the term be destructed and rebuilt. In this paper, we show how to eliminate this overhead using higher-order type abstraction. We demonstrate this solution in two frameworks for ad-hoc polymorphism: intensional type analysis and type classes.

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.

	1	Martín Abadi , Luca Cardelli , Benjamin Pierce , Gordon Plotkin, Dynamic typing in a statically typed language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.237-268, April 1991 [doi>10.1145/103135.103138]
	2	Karl Crary , Stephanie Weirich , Greg Morrisett, Intensional polymorphism in type-erasure semantics, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.301-312, September 26-29, 1998, Baltimore, Maryland, United States
	3	Catherine Dubois , François Rouaix , Pierre Weis, Extensional polymorphism, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.118-129, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199473]
	4	J.-Y. Girard. Interpretation fonctionelle et elimination des coupures de l'arithmetique d'ordre superieur. PhD thesis, Universite Paris VII, 1972.
	5	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	6	Robert Harper , Greg Morrisett, Compiling polymorphism using intensional type analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199475]
	7	Fritz Henglein, Dynamic typing, Symposium proceedings on 4th European symposium on programming, p.233-253, January 1992, Rennes, France
	8	M. P. Jones. A system of constructor classes: overloading and implicit higher-order polymorphism. Journal of Functional Programming, 5(1), Jan. 1995.
	9	Xavier Leroy , Michel Mauny, Dynamics in ML, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.406-426, June 1991, Cambridge, Massachusetts, United States
	10	Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
	11	Yasuhiko Minamide , Greg Morrisett , Robert Harper, Typed closure conversion, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.271-283, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237791]
	12	John C. Mitchell , Gordon D. Plotkin, Abstract types have existential type, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.3, p.470-502, July 1988 [doi>10.1145/44501.45065]
	13	S. Peyton Jones and J. Hughes (editors). Report on the programming language Haskell 98, a non-strict purely functional language. Technical Report YALEU/DCS/RR-1106, Yale University, Department of Computer Science, Feb. 1999. Available from http://www.haskell.org/definition/.
	14	John C. Reynolds, Towards a theory of type structure, Programming Symposium, Proceedings Colloque sur la Programmation, p.408-423, April 09-11, 1974
	15	Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
	16	P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
	17	S. Weeks. NJ PearLS dynamically extensible data structures in Standard ML. Talk presented at New Jersey Programming Languages and Systems Seminar, Sept. 1998. Transparencies available at http://www.star-lab.com/sweeks/talks.html. 65

CITED BY 20

	Manuel M. T. Chakravarty , Gabriele Keller, Functional array fusion, ACM SIGPLAN Notices, v.36 n.10, October 2001
	James Cheney , Ralf Hinze, A lightweight implementation of generics and dynamics, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.90-104, October 03, 2002, Pittsburgh, Pennsylvania
	Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate: a practical design pattern for generic programming, ACM SIGPLAN Notices, v.38 n.3, March 2003
	Bratin Saha , Valery Trifonov , Zhong Shao, Intensional analysis of quantified types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.2, p.159-209, March 2003
	Dan Russell , Dominic Steinitz , Chris Reade, Haskell: language for business systems, Trends in functional programming, Intellect Books, Exeter, UK, 2002
	James J. Leifer , Gilles Peskine , Peter Sewell , Keith Wansbrough, Global abstraction-safe marshalling with hash types, ACM SIGPLAN Notices, v.38 n.9, p.87-98, September 2003
	Andreas Rossberg, Generativity and dynamic opacity for abstract types, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.241-252, August 27-29, 2003, Uppsala, Sweden
	André Pang , Don Stewart , Sean Seefried , Manuel M. T. Chakravarty, Plugging Haskell in, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA
	Arthur I. Baars , S. Doaitse Swierstra, Typing dynamic typing, ACM SIGPLAN Notices, v.37 n.9, p.157-166, September 2002
	Manuel M. T. Chakravarty , Gabriele Keller , Simon Peyton Jones , Simon Marlow, Associated types with class, ACM SIGPLAN Notices, v.40 n.1, p.1-13, January 2005
	Ralf Lämmel , Simon Peyton Jones, Scrap more boilerplate: reflection, zips, and generalised casts, ACM SIGPLAN Notices, v.39 n.9, September 2004
	Tim Sheard, Languages of the future, ACM SIGPLAN Notices, v.39 n.12, December 2004
	Oleg Kiselyov , Ralf Lämmel , Keean Schupke, Strongly typed heterogeneous collections, Proceedings of the 2004 ACM SIGPLAN workshop on Haskell, September 22-22, 2004, Snowbird, Utah, USA
	Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate with class: extensible generic functions, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Tim Sheard, Putting curry-howard to work, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.74-85, September 30-30, 2005, Tallinn, Estonia
	Vincent Simonet , François Pottier, A constraint-based approach to guarded algebraic data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.1-es, January 2007
	Martin Sulzmann , Manuel M. T. Chakravarty , Simon Peyton Jones , Kevin Donnelly, System F with type equality coercions, Proceedings of the 2007 ACM SIGPLAN international workshop on Types in languages design and implementation, January 16-16, 2007, Nice, Nice, France
	Tom Murphy, VII, ML grid programming with ConCert, Proceedings of the 2006 workshop on ML, September 16-16, 2006, Portland, Oregon, USA
	Arthur I. Baars , S. Doaitse Swierstra , Marcos Viera, Typed transformations of typed abstract syntax, Proceedings of the 4th international workshop on Types in language design and implementation, January 24-24, 2009, Savannah, GA, USA
	Tim Sheard , Emir Pasalic, Meta-programming With Built-in Type Equality, Electronic Notes in Theoretical Computer Science (ENTCS), 199, p.49-65, February, 2008