Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T23:09:19.976Z Has data issue: false hasContentIssue false
  • English
  • Français

An extended account of contract monitoring strategies as patterns of communication

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 March 2018

CAMERON SWORDS ,
AMR SABRY  and
SAM TOBIN-HOCHSTADT
CAMERON SWORDS
Affiliation:
Computer Science, Indiana University, IN, USA (e-mail: [email protected], [email protected], [email protected])
AMR SABRY
Affiliation:
Computer Science, Indiana University, IN, USA (e-mail: [email protected], [email protected], [email protected])
SAM TOBIN-HOCHSTADT
Affiliation:
Computer Science, Indiana University, IN, USA (e-mail: [email protected], [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Contract systems have come to play a vital role in many aspects of software engineering. This has resulted in a wide variety of approaches to enforcing contracts—ranging from the straightforward pre-condition and post-condition checking of Eiffel to lazy, optional, and parallel enforcement strategies. Each of these approaches has its merits, but each has required ground-up development of an entire contract monitoring system. We present a unified approach to understanding this variety, while also opening the door to as-yet-undiscovered strategies. By observing that contracts are fundamentally about communication between a program and a monitor, we reframe contract checking as communication between concurrent processes. This brings out the underlying relations between widely studied enforcement strategies, including strict and lazy enforcement as well as concurrent approaches, including new contracts and strategies. We show how each of these can be embedded into a core calculus, and demonstrate a proof (via simulation) of correctness for one such encoding. Finally, we show that our approach suggests new monitoring approaches and contracts not previously expressible.

Type
Articles
Information
Journal of Functional Programming , Volume 28 , 2018 , e4
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2018

References

Ahmed, A., Findler, R. B., Siek, J. G. & Wadler, P. (2011) Blame for all. In Proceedings of the 38th Annual Symposium on Principles of Programming Languages, POPL '11. ACM.Google Scholar
Ahmed, A., Jamner, D., Siek, J. G. & Wadler, P. (2017) Theorems for free for free: Parametricity, with and without types. In Proceedings of the 22th International Conference on Functional Programming, ICFP '17. ACM.Google Scholar
Ambler, A. L., Good, D. I., Browne, J. C., Burger, W. F., Choen, R. M., Hoch, C. G., & Wells, R. E. (1977) Gypsy: A language for specification and implementation of verifiable programs. In Proceedings of the ACM Conference on Language Design for Reliable Software, Sigplan, pp. 1–10.CrossRefGoogle Scholar
Barnett, M., Leino, K. R. M. & Schulte, W. (2005) The spec# programming system: An overview. In Proceedings of the 2004 International Conference on Construction and Analysis of Safe, Secure, and Interoperable Smart Devices, CASSIS '04. Springer-Verlag.CrossRefGoogle Scholar
Blume, M. & McAllester, D. (2004) A sound (and complete) model of contracts. In Proceedings of the 9th International Conference on Functional Programming, ICFP '04. ACM.Google Scholar
Chen, F. & Roşu, G. (2007) Mop: An efficient and generic runtime verification framework. In Proceedings of the 22nd Annual Conference on Object-Oriented Programming Systems and Applications, OOPSLA '07. ACM.Google Scholar
Chitil, O. (2012) Practical typed lazy contracts. In Proceedings of the 17th International Conference on Functional Programming, ICFP '12. ACM.Google Scholar
Chitil, O., & Huch, F. (2006) A pattern logic for prompt lazy assertions in haskell. In Proceedings of the Symposium on Implementation and Application of Functional Languages, IFL '06. Springer.Google Scholar
Chitil, O., McNeill, D. & Runciman, C. (2003) Lazy assertions. In Proceedings of the Symposium on Implementation and Application of Functional Languages, IFL '03. Springer-Verlag.Google Scholar
Degen, M., Thiemann, P. & Wehr, S. (2009) True Lies: Lazy contracts for lazy languages (faithfulness is better than laziness) In Proceedings of the Arbeitstagung Programmiersprachen (ATPS), ATPS '09. Springer.Google Scholar
Degen, M., Thiemann, P. & Wehr, S. (2010) Eager and delayed contract monitoring for call-by-value and call-by-name evaluation. J. Log. Algebr. Program. 79 (7), 515–549.Google Scholar
Degen, M., Thiemann, P. & Wehr, S. (2012) The interaction of contracts and laziness. In Proceedings of the 2012 Workshop on Partial Evaluation and Program Manipulation, PEPM '12. ACM.CrossRefGoogle Scholar
Dimoulas, C. & Felleisen, M. (2011) On contract satisfaction in a higher-order world. ACM Trans. Program. Lang. Syst. 33 (5), 16:1–16:29.Google Scholar
Dimoulas, C., Findler, R. B., Flanagan, C. & Felleisen, M. (2011) Correct blame for contracts: No more scapegoating. In Proceedings of the 38th Annual Symposium on Principles of Programming Languages, POPL '11. ACM.Google Scholar
Dimoulas, C., Findler, R. B. & Felleisen, M. (2013) Option contracts. In Proceedings of the 2013 International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA '13. ACM.CrossRefGoogle Scholar
Dimoulas, C., Pucella, R. & Felleisen, M. (2009) Future contracts. In Proceedings of the 11th Conference on Principles and Practice of Declarative Programming, PPDP '09. ACM.Google Scholar
Dimoulas, C., Tobin-Hochstadt, S. & Felleisen, M. (2012) Complete monitors for behavioral contracts. In Proceedings of the European Symposium on Programming, ESOP '12. Springer-Verlag.CrossRefGoogle Scholar
Disney, T., Flanagan, C. & McCarthy, J. (2011) Temporal higher-order contracts. In Proceedings of the 16th International Conference on Functional Programming, ICFP '11. ACM.Google Scholar
Ergün, F., Kannan, S., Kumar, S. R., Rubinfeld, R. & Viswanathan, M. (1998) Spot-checkers. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC '98. ACM.Google Scholar
Findler, R. B. (2014) Behavioral software contracts. In Proceedings of the 19th International Conference on Functional Programming, ICFP '14. ACM.CrossRefGoogle Scholar
Findler, R. B. & Blume, M. (2006) Contracts as pairs of projections. In Proceedings of the 8th International Conference on Functional and Logic Programming, FLOPS '06. Springer-Verlag.Google Scholar
Findler, R. B & Felleisen, M. (2002) Contracts for higher-order functions. In Proceedings of the 7th International Conference on Functional Programming, ICFP '02. ACM.CrossRefGoogle Scholar
Findler, R. B., Guo, S.-Y. & Rogers, A. (2008) Lazy contract checking for immutable data structures. In Proceedings of the Implementation and Application of Functional Languages. Springer-Verlag.Google Scholar
Flanagan, C. (2006) Hybrid type checking. In Proceedings of the Conference Record of the 33rd Symposium on Principles of Programming Languages, POPL '06. ACM.Google Scholar
Flatt, M. & PLT. (2010) Reference: Racket. Technical Report, PLT-TR-2010-1. PLT Inc. http://racket-lang.org/tr1/.Google Scholar
Freeman, Tim. (1994) Refinement Types for ML. (Ph.D. Thesis), Carnegie Mellon University.Google Scholar
Friedman, D. & Wise, D. (1976) The Impact of Applicative Programming on Multiprocessing. Technical Report 52. Indiana University, Computer Science Department.Google Scholar
Greenberg, M. (2015) Space-efficient manifest contracts. In Proceedings of the 42nd Symposium on Principles of Programming Languages, POPL '15. ACM.CrossRefGoogle Scholar
Greenberg, M., Pierce, B. C. & Weirich, S. (2010) Contracts made manifest. In Proceedings of the 37th Symposium on Principles of Programming Languages, POPL '10. ACM.Google Scholar
Guha, A., Matthews, J., Findler, R. B. & Krishnamurthi, S. (2007) Relationally-parametric polymorphic contracts. In Proceedings of the 2007 Symposium on Dynamic Languages, DLS '07. ACM.Google Scholar
Havelund, K. & Rosu, G. (2001) Monitoring Java Programs with Java Pathexplorer. Technical Report, NASA Ames Research Center.Google Scholar
Herman, D., Tomb, A. & Flanagan, C (2007 April) Space-efficient gradual typing. In Trends in Functional Prog, Page XXVIII. TFP '07.Google Scholar
Hickey, R. (2018) Clojure core.spec Documentation [online]. Accessed February 18, 2018. Available at: https://clojure.org/guides/spec.Google Scholar
Hinze, R., Jeuring, J. & Löh, A. (2006) Typed contracts for functional programming. In Proceedings of the 8th International Conference on Functional and Logic Programming, FLOPS '06. Springer-Verlag.Google Scholar
Ingerman, P. Z. (1961) Thunks: A way of compiling procedure statements with some comments on procedure declarations. Commun. ACM 4 (1).CrossRefGoogle Scholar
Jeffrey, A. (1998) Semantics for core Concurrent ML using computation types. Higher Order Operational Techniques in Semantics. Cambridge University Press.Google Scholar
Keil, M. & Thiemann, P. (2015) Blame assignment for higher-order contracts with intersection and union. In Proceedings of the 20th International Conference on Functional Programming, ICFP '15. ACM.Google Scholar
Meyer, B. (1992) Eiffel: The Language. Prentice-Hall, Inc. Google Scholar
Moore, S., Dimoulas, C., Findler, R. B., Flatt, M. & Chong, S. (2016) Extensible access control with authorization contracts. In Proceedings of the 2016 International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '16. ACM.Google Scholar
Nguyen, P. C., Tobin-Hochstadt, S. & Van Horn, D. (2014) Soft contract verification. In Proceedings of the 19th International Conference on Functional Programming, ICFP '14. ACM.Google Scholar
Ou, X., Tan, G., Mandelbaum, Y., & Walker, D. (2004) Dynamic typing with dependent types. Exploring New Frontiers of Theoretical Informatics, Levy, J.-J., Mayr, E. W., & Mitchell, J. C. (eds), Boston, MA: Springer, US, pp. 437–450.Google Scholar
Owens, Z. (2012) Contract monitoring as an effect. Proceedings of the 1st ACM SIGPLAN Workshop on Higher-Order Programming with Effects. HOPE '12. ACM.Google Scholar
Pierce, B. C. (2002) Types and Programming Languages. MIT Press.Google Scholar
Reppy, J. H. (1993) Concurrent ML: Design, application and semantics. In Proceedings of the Functional Programming, Concurrency, Simulation and Automated Reasoning: International Lecture Series 1991-1992, McMaster University, Hamilton, Ontario, Canada. Springer-Verlag.Google Scholar
Reppy, J. H. (1999) Concurrent Programming in ML. Cambridge University Press.Google Scholar
Sekiyama, T., Nishida, Y. & Igarashi, A. (2015) Manifest contracts for datatypes. In Proceedings of the 42nd Symposium on Principles of Programming Languages, POPL '15. ACM.Google Scholar
Shinnar, A. (2011) Safe and Effective Contracts. Technical Report, Harvard University.Google Scholar
Siek, J. G. & Taha, W. (2006) Gradual typing for functional languages. Scheme and Functional Programming Workshop.Google Scholar
Siek, J. G., Garcia, R. & Taha, W. (2009) Exploring the design space of higher-order casts. In Proceedings of the European Symposium on Programming, ESOP '09. Springer-Verlag.Google Scholar
Strickland, T. S., Tobin-Hochstadt, S., Findler, R. B. & Flatt, M. (2012) Chaperones and impersonators: Run-time support for reasonable interposition. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '12. ACM.Google Scholar
Swords, C., Sabry, A. & Tobin-Hochstadt, S. (2015) Expressing contract monitors as patterns of communication. In Proceedings of the 20th International Conference on Functional Programming, ICFP '15. ACM.Google Scholar
Vitousek, M. M., Siek, J. G., Kent, A. & Baker, J. (2014) Design and evaluation of gradual typing for Python. In Proceedings of the Dynamic Languages Symposium, DLS '14.Google Scholar
Wadler, P. & Findler, R. B. (2009) Well-typed programs can't be blamed. In Proceedings of the 18th European Symposium on Programming Languages and Systems. ESOP '09. Springer-Verlag.Google Scholar
Xu, D. N., Peyton Jones, S. & Claessen, K. (2009) Static contract checking for haskell. In Proceedings of the 36th Annual Symposium on Principles of Programming Languages, POPL '09. ACM.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.