research-article

Contracts made manifest

Authors:

Michael Greenberg,

Benjamin C. Pierce,

Stephanie WeirichAuthors Info & Claims

POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 353 - 364

https://doi.org/10.1145/1706299.1706341

Published: 17 January 2010 Publication History

Abstract

Since Findler and Felleisen introduced higher-order contracts , many variants have been proposed. Broadly, these fall into two groups: some follow Findler and Felleisen in using latent contracts, purely dynamic checks that are transparent to the type system; others use manifest contracts, where refinement types record the most recent check that has been applied to each value. These two approaches are commonly assumed to be equivalent---different ways of implementing the same idea, one retaining a simple type system, and the other providing more static information. Our goal is to formalize and clarify this folklore understanding.

Our work extends that of Gronski and Flanagan, who defined a latent calculus λ _C and a manifest calculus λ _H, gave a translation φ from λ _C to λ _H, and proved that, if a λ _C term reduces to a constant, then so does its φ-image. We enrich their account with a translation Ψ from λ _H to λ _C and prove an analogous theorem.

We then generalize the whole framework to dependent contracts , whose predicates can mention free variables. This extension is both pragmatically crucial, supporting a much more interesting range of contracts, and theoretically challenging. We define dependent versions of λ _H and two dialects ("lax" and "picky") of λ _C, establish type soundness---a substantial result in itself, for λ _H---and extend φ and Ψ accordingly. Surprisingly, the intuition that the latent and manifest systems are equivalent now breaks down: the extended translations preserve behavior in one direction but, in the other, sometimes yield terms that blame more.

References

[1]

Matthias Blume and David A. McAllester. Sound and complete models of contracts. Journal of Functional Programming, 16(4-5):375--414, 2006.

Digital Library

[2]

Olaf Chitil and Frank Huch. Monadic, prompt lazy assertions in haskell. In APLAS, pages 38--53, 2007.

Digital Library

[3]

Robert Bruce Findler. Contracts as pairs of projections. In Symposium on Logic Programming, pages 226--241, 2006.

Digital Library

[4]

Robert Bruce Findler and Matthias Felleisen. Contracts for higher-order functions. In International Conference on Functional Programming (ICFP), pages 48--59, 2002.

Digital Library

[5]

Cormac Flanagan. Hybrid type checking. In POPL, pages 245--256, 2006.

Digital Library

[6]

Jessica Gronski and Cormac Flanagan. Unifying hybrid types and contracts. In Trends in Functional Programming (TFP), 2007.

[7]

Jessica Gronski, Kenneth Knowles, Aaron Tomb, Stephen N. Freund, and Cormac Flanagan. Sage: Hybrid checking for flexible specifications. In Scheme and Functional Programming Workshop, pages 93--104, 2006.

[8]

Arjun Guha, Jacob Matthews, Robert Bruce Findler, and Shriram Krishnamurthi. Relationally-parametric polymorphic contracts. In DLS, pages 29--40, 2007.

Digital Library

[9]

Ralf Hinze, Johan Jeuring, and Andres L¨oh. Typed contracts for functional programming. In Functional and Logic Programming (FLOPS), pages 208--225, 2006.

Digital Library

[10]

Kenneth Knowles and Cormac Flanagan. Hybrid type checking. To appear in TOPLAS., 2009.

Digital Library

[11]

Bertrand Meyer. Eiffel: the language. Prentice-Hall, Inc., 1992. ISBN 0-13-247925-7.

Digital Library

[12]

Xinming Ou, Gang Tan, Yitzhak Mandelbaum, and DavidWalker. Dynamic typing with dependent types. In IFIP TCS, pages 437--450, 2004.

[13]

Sam Tobin-Hochstadt and Matthias Felleisen. The design and implementation of typed scheme. In Principles of Programming Languages (POPL), pages 395--406, 2008.

Digital Library

[14]

Philip Wadler and Robert Bruce Findler. Well-typed programs can't be blamed. In Workshop on Scheme and Functional Programming, 2007.

[15]

Philip Wadler and Robert Bruce Findler. Well-typed programs can't be blamed. In European Symposium on Programming (ESOP), pages 1--16, 2009.

Digital Library

[16]

Dana N. Xu, Simon Peyton Jones, and Koen Claessen. Static contract checking for haskell. In Principles of Programming Languages (POPL), pages 41--52, 2009.

Digital Library

Cited By

Moy CDimoulas CFelleisen M(2024)Effectful Software ContractsProceedings of the ACM on Programming Languages10.1145/36329308:POPL(2639-2666)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632930
Economou DKrishnaswami NDunfield J(2023)Focusing on Refinement TypingACM Transactions on Programming Languages and Systems10.1145/361040845:4(1-62)Online publication date: 20-Dec-2023
https://dl.acm.org/doi/10.1145/3610408
MOY CFELLEISEN M(2023)Trace contractsJournal of Functional Programming10.1017/S095679682300009633Online publication date: 13-Dec-2023
https://doi.org/10.1017/S0956796823000096
Show More Cited By

Index Terms

Contracts made manifest

Recommendations

Polymorphic Manifest Contracts, Revised and Resolved

Manifest contracts track precise program properties by refining types with predicates—for example, {x:Int∣ x > 0} denotes the positive integers. Contracts and polymorphism make a natural combination: programmers can give strong contracts to abstract ...
Contracts made manifest
POPL '10

Since Findler and Felleisen introduced higher-order contracts , many variants have been proposed. Broadly, these fall into two groups: some follow Findler and Felleisen in using latent contracts, purely dynamic checks that are transparent to the type ...
Contracts made manifest*

Since Findler and Felleisen (Findler, R. B. & Felleisen, M. 2002) introduced higher-order contracts, many variants have been proposed. Broadly, these fall into two groups: some follow Findler and Felleisen (2002) in using latent contracts, purely ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2010

520 pages

ISBN:9781605584799

DOI:10.1145/1706299

General Chair:
Manuel Hermenegildo
IMDEA-Software and T.U. of Madrid, Spain
,
Program Chair:
Jens Palsberg
UCLA, University of California, Los Angeles

ACM SIGPLAN Notices Volume 45, Issue 1
POPL '10
January 2010
500 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1707801
Issue’s Table of Contents

Copyright © 2010 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

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 January 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '10

Sponsor:

SIGPLAN

POPL '10: The 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 17 - 23, 2010

Madrid, Spain

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
411
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)3

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Moy CDimoulas CFelleisen M(2024)Effectful Software ContractsProceedings of the ACM on Programming Languages10.1145/36329308:POPL(2639-2666)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632930
Economou DKrishnaswami NDunfield J(2023)Focusing on Refinement TypingACM Transactions on Programming Languages and Systems10.1145/361040845:4(1-62)Online publication date: 20-Dec-2023
https://dl.acm.org/doi/10.1145/3610408
MOY CFELLEISEN M(2023)Trace contractsJournal of Functional Programming10.1017/S095679682300009633Online publication date: 13-Dec-2023
https://doi.org/10.1017/S0956796823000096
NEW MLICATA DAHMED A(2021)Gradual type theoryJournal of Functional Programming10.1017/S095679682100012531Online publication date: 14-Oct-2021
https://doi.org/10.1017/S0956796821000125
SIEK JTHIEMANN PWADLER P(2021)Blame and coercion: Together again for the first timeJournal of Functional Programming10.1017/S095679682100010131Online publication date: 13-Oct-2021
https://doi.org/10.1017/S0956796821000101
Kuhlenschmidt AAlmahallawi DSiek JMcKinley KFisher K(2019)Toward efficient gradual typing for structural types via coercionsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314627(517-532)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314627
New MLicata DAhmed A(2019)Gradual type theoryProceedings of the ACM on Programming Languages10.1145/32903283:POPL(1-31)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1145/3290328
IGARASHI ATHIEMANN PTSUDA YVASCONCELOS VWADLER P(2019)Gradual session typesJournal of Functional Programming10.1017/S095679681900016929Online publication date: 18-Nov-2019
https://doi.org/10.1017/S0956796819000169
Greenberg M(2019)Space-Efficient Latent ContractsTrends in Functional Programming10.1007/978-3-030-14805-8_1(3-23)Online publication date: 21-Feb-2019
https://doi.org/10.1007/978-3-030-14805-8_1
Vazou NTanter ÉVan Horn D(2018)Gradual liquid type inferenceProceedings of the ACM on Programming Languages10.1145/32765022:OOPSLA(1-25)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276502
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.

Media

Figures

Other

Tables

View Table of Contents