Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-21T07:55:27.008Z Has data issue: false hasContentIssue false
  • English
  • Français

Ott: Effective tool support for the working semanticist

Part of: JFP Research Articles

Published online by Cambridge University Press:  26 January 2010

PETER SEWELL ,
FRANCESCO ZAPPA NARDELLI ,
SCOTT OWENS ,
GILLES PESKINE ,
THOMAS RIDGE ,
SUSMIT SARKAR  and
ROK STRNIŠA
PETER SEWELL
Affiliation:
University of Cambridge, Computer Laboratory, William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, United Kingdom (e-mail: Peter.Sewell@cl.cam.ac.uk)
FRANCESCO ZAPPA NARDELLI
Affiliation:
INRIA Paris-Rocquencourt, B.P. 105, 78153 Le Chesnay Cedex, France
SCOTT OWENS
Affiliation:
University of Cambridge, Computer Laboratory, William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, United Kingdom (e-mail: Peter.Sewell@cl.cam.ac.uk)
GILLES PESKINE
Affiliation:
University of Cambridge, Computer Laboratory, William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, United Kingdom (e-mail: Peter.Sewell@cl.cam.ac.uk)
THOMAS RIDGE
Affiliation:
University of Cambridge, Computer Laboratory, William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, United Kingdom (e-mail: Peter.Sewell@cl.cam.ac.uk)
SUSMIT SARKAR
Affiliation:
University of Cambridge, Computer Laboratory, William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, United Kingdom (e-mail: Peter.Sewell@cl.cam.ac.uk)
ROK STRNIŠA
Affiliation:
University of Cambridge, Computer Laboratory, William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD, United Kingdom (e-mail: Peter.Sewell@cl.cam.ac.uk)
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.

Semantic definitions of full-scale programming languages are rarely given, despite the many potential benefits. Partly this is because the available metalanguages for expressing semantics – usually either for informal mathematics or the formal mathematics of a proof assistant – make it much harder than necessary to work with large definitions. We present a metalanguage specifically designed for this problem, and a tool, Ott, that sanity-checks such definitions and compiles them into proof assistant code for Coq, HOL, and Isabelle/HOL, together with code for production-quality typesetting, and OCaml boilerplate. The main innovations are (1) metalanguage design to make definitions concise, and easy to read and edit; (2) an expressive but intuitive metalanguage for specifying binding structures; and (3) compilation to proof assistant code. This has been tested in substantial case studies, including modular specifications of calculi from the TAPL text, a Lightweight Java with Java JSR 277/294 module system proposals, and a large fragment of OCaml (OCamllight, 310 rules), with mechanised proofs of various soundness results. Our aim with this work is to enable a phase change: making it feasible to work routinely, without heroic effort, with rigorous semantic definitions of realistic languages.

Type
Articles
Information
Journal of Functional Programming , Volume 20 , Issue 1 , January 2010 , pp. 71 - 122
Copyright
Copyright © Cambridge University Press 2010

References

Aldrich, J., Simmons, R. J. & Shin, K. (2008) SASyLF: An Educational Proof Assistant for Language Theory. In Proceedings of the 2008 International Workshop on Functional and Declarative Programming in Education (FDPE '08). ACM, Victoria, BC, pp. 31–40.CrossRefGoogle Scholar
Aspinall, D. (2000) Proof general: A generic tool for proof development. In Tools and Algorithms for Construction and Analysis of Systems, 6th International Conference, TACAS 2000, Proceedings, Graf, S. & Schwartzbach, M. I. (eds), Lecture Notes in Computer Science, vol. 1785. Springer-Verlag, Berlin, pp. 38–42.Google Scholar
Aydemir, B. E., Bohannon, A., Fairbairn, M., Foster, J. N., Pierce, B. C., Sewell, P., Vytiniotis, D., Washburn, G., Weirich, S. & Zdancewic, S. (2005) Mechanized metatheory for the masses: The POPLmark challenge. In Theorem Proving in Higher Order Logics, 18th International Conference, TPHOLs 2005, Proceedings, Hurd, J. & Melham, T. F. (eds), Lecture Notes in Computer Science, vol. 3603, Springer, Oxford, pp. 50–65.Google Scholar
Aydemir, B., Charguéraud, A., Pierce, B. C., Pollack, R. & Weirich, S. (2008) Engineering Formal Metatheory. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '08). ACM, San Francisco, pp. 3–15.CrossRefGoogle Scholar
Aydemir, B. & Weirich, S. (2009) LNgen: Tool support for locally nameless representation. Available at: http://www.cis.upenn.edu/baydemir/papers/lngen/ Accessed 8 January 2010.Google Scholar
Barthe, G., Dufay, G., Huisman, M. & de Sousa, S. M. (2001) Jakarta: A toolset to reason about the javacard platform. In Smart Card Programming and Security, International Conference on Research in Smart Cards, E-smart 2001, Proceedings, Attali, I. & Jensen, T. (eds), Lecture Notes in Computer Science, vol. 2140. Springer-Verlag, Cannes, pp. 2–18.Google Scholar
Benton, N. & Koutavas, V. (2007) A mechanized bisimulation for the nu-calculus. Available at: http://research.microsoft.com/en-us/um/people/nick/nubisim.pdf Accessed 8 January 2010.Google Scholar
Berghofer, S. & Urban, C. (2006) A head-to-head comparison of de Bruijn indices and names. In Proceedings of International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP), ENTCS 174(5), pp. 53–67.Google Scholar
Blazy, S. & Leroy, X. (2009) Mechanized semantics for the Clight subset of the C language, J. Autom. Reasoning, 43 (3): 263–288.CrossRefGoogle Scholar
Blazy, S., Dargaye, Z. & Leroy, X. (2006) Formal Verification of a C compiler front-end. In FM 2006: Formal Methods, 14th International Symposium on Formal Methods, Misra, J., Nipkow, T. & Sekerinski, E. (eds), Lecture Notes in Computer Science, vol. 4085. Springer-Verlag, Hamilton, Canada, pp. 460–475.CrossRefGoogle Scholar
Borras, P., Clément, D., Despeyroux, T., Incerpi, J., Kahn, G., Lang, B. & Pascual, V. (1988) CENTAUR: The system. In Proceedings of the third ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (SDE 3). ACM, pp. 14–24.CrossRefGoogle Scholar
Boulton, R. J. (1997) A tool to support formal reasoning about computer languages. In Tools and Algorithms for the Construction and Analysis of Systems, Third International Workshop, TACAS '97, Proceedings, Brinksma, E. (ed), Lecture Notes in Computer Science, vol. 1217. Springer, Enschede, The Netherlands, pp. 81–95.Google Scholar
Cardelli, L., Martini, S., Mitchell, J. C. & Scedrov, A. (1994) An extension of system F with subtyping, Inf. Comput., 109 (1/2): 4–56.CrossRefGoogle Scholar
Charguéraud, A. (2006) Annotated bibliography for formalization of lambda-calculus and type theory. Available at: http://arthur.chargueraud.org/projects/binders/biblio.php Accessed 8 January 2010.Google Scholar
Cheney, J. & Urban, C. (2004) Alpha-Prolog: A logic programming language with names, binding and alpha-equivalence. In Logic Programming, 20th International Conference, ICLP 2004, Proceedings, Demoen, B. & Lifschitz, V. (eds), Lecture Notes in Computer Science, no. 3132. Springer-Verlag, Saint-Malo, France, pp. 269–283.Google Scholar
Coq. (2008). The Coq proof assistant, v.8.1. Available at: http://coq.inria.fr/ Accessed 8 January 2010.Google Scholar
Curien, P.-L. & Ghelli, G. (1991) Subtyping + Extensionality: Confluence of beta-eta-top reduction in F<=. In Theoretical Aspects of Computer Software, International Conference, TACS '91, Proceedings, Ito, T. & Meyer, A. R. (eds), Lecture Notes in Computer Science, vol. 526. Springer, Sendai, Japan, pp. 731–749.CrossRefGoogle Scholar
Delaware, B., Cook, W. & Batory, D. (2009) A machine-checked model of safe composition. In Proceedings of the 8th Workshop on Foundations of Aspect-Oriented Languages (FOAL), Charlottesville, Virginia, ACM pp. 31–35.CrossRefGoogle Scholar
Dijkstra, A. & Swierstra, S. D. (2006) Ruler: Programming type rules. In Functional and Logic Programming, 8th International Symposium, FLOPS 2006, Proceedings, Hagiya, M. & Wadler, P. (eds), Lecture Notes in Computer Science, vol. 3945. Springer, Fuji-Susono, Japan, pp. 30–46.Google Scholar
Fournet, C., Gonthier, G., Lévy, J.-J., Maranget, L. & Rémy, D. (1996) A calculus of mobile agents. In CONCUR '96, Concurrency Theory, 7th International Conference, Proceedings, Montanari, U. & Sassone, V. (eds), Lecture Notes in Computer Science, vol. 1119. Springer, Pisa, pp. 406–421.CrossRefGoogle Scholar
Fournet, C., Guts, N. & Zappa Nardelli, F. (2008) A formal implementation of value commitment. In Programming Languages and Systems, 17th European Symposium on Programming, ESOP 2008, Proceedings, Drossopoulou, S. (ed.), Lecture Notes in Computer Science, vol. 4960. Springer, Budapest, pp. 383–397.Google Scholar
Gray, K. E. (2008) Safe cross-language inheritance. In ECOOP 2008 – Object-Oriented Programming, 22nd European Conference, Proceedings, Vitek, J. (ed.), Lecture Notes in Computer Science, vol. 5142. Springer, Paphos, Cyprus, pp. 52–75.CrossRefGoogle Scholar
Greenberg, M., Pierce, B. & Weirich, S. Contracts made manifest. In Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL). ACM, Madrid. 2009.Google Scholar
Gunter, E. & Maharaj, S. (1995) Studying the ML module system in HOL. The Computer Journal: Special Issue on Theorem Proving in Higher Order Logics, 38 (2): 142–151.CrossRefGoogle Scholar
HOL. (2007) The HOL 4 system, Kananaskis-4 release. Available at: http://hol.sourceforge.net/ Accessed 8 January 2010.Google Scholar
Isabelle. (2008) Isabelle 2008. Available at: http://isabelle.in.tum.de/ Accessed 8 January 2010.Google Scholar
Jia, L., Zhao, J., Sjöberg, V. & Weirich, S. Dependent types and program equivalence. In Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL). ACM, Madrid. 2009.Google Scholar
Kahrs, S. (1993) Mistakes and Ambiguities in the Definition of Standard ML. Tech. Rep., ECS-LFCS-93-257. University of Edinburgh.Google Scholar
Klein, G. & Nipkow, T. (2006) A machine-checked model for a Java-like language, virtual machine, and compiler, ACM Trans. Program. Lang. Syst., 28 (4): 619–695.CrossRefGoogle Scholar
Klein, G., Nipkow, T. & Paulson, L. (eds) (2009) The archive of formal proofs. Available at: http://afp.sf.net Accessed 8 January 2010.Google Scholar
Klint, P. (1993) A meta-environment for generating programming environments, ACM Trans. Softw. Eng. Method., 2 (2): 176–201.CrossRefGoogle Scholar
Lakin, M. R. & Pitts, A. M. (2007) A Metalanguage for Structural Operational Semantics. In Trends in Functional Programming, Eighth Symposium on Trends in Functional Programming (TFP 2007). Draft proceedings, Morazán, M. T. (ed.), vol. 8, Intellect, New York, pp. 19–35.Google Scholar
Lee, D. K., Crary, K. & Harper, R. (2007) Towards a Mechanized Metatheory of Standard ML. In Proceedings 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). ACM, Nice, pp. 173–184.CrossRefGoogle Scholar
Lee, P., Pfenning, F., Rollins, G. & Scherlis, W. (1988) The Ergo Support System: An integrated set of tools for prototyping integrated environments. In Proceedings of ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, ACM, Boston, pp. 25–34.CrossRefGoogle Scholar
Leroy, X., Doligez, D., Garrigue, J., Rémy, D. & Vouillon, J. (2005) The Objective Caml System Release 3.09 Documentation and User's Manual. URL http://caml.inria.fr/pub/docs/manual-ocaml/(3.11 from 2008) Accessed 8 January 2010.Google Scholar
Leroy, X. (1996) A syntactic theory of type generativity and sharing, J. Funct. Program., 6 (5): 667–698.CrossRefGoogle Scholar
Levin, M. Y. & Pierce, B. C. (2003) Tinkertype: A language for playing with formal systems, J. Funct. Program., 13 (2). 295–316.CrossRefGoogle Scholar
Matthews, J., Findler, R. B., Flatt, M. & Felleisen, M. (2004) A visual environment for developing Context-sensitive term rewriting systems. In Rewriting Techniques and Applications, 15th International Conference, RTA 2004, Proceedings, van Oostrom, V. (ed.), Lecture Notes in Computer Science, vol. 3091. Springer, Aachen, Germany, pp. 301–311.Google Scholar
McPeak, S. & Necula, G. C. (2004) Elkhound: A fast, practical GLR parser generator. In Compiler Construction, 13th International Conference, CC 2004, Proceedings, Duesterwald, E. (ed.), Lecture Notes in Computer Science, vol. 2985. Springer, Barcelona, pp. 73–88.Google Scholar
Milner, R. (1972) Implementation and applications of Scott's logic for computable functions. In Proceedings ACM Conference on Proving Assertions About Programs, ACM, Las Cruces, New Mexico, pp. 1–6.Google Scholar
Milner, R., Tofte, M. & Harper, R. (1990) The Definition of Standard ML. MIT Press.Google Scholar
Moors, A., Piessens, F. & Odersky, M. (2008) Safe type-level abstraction in Scala. International Workshop on Foundations of Object-Oriented Languages. FOOL workshop, San Francisco. http://fool08.kuis.kyoto-u.ac.jp/program.html Accessed 8 January 2010.Google Scholar
Mosses, P. D. (2002) Pragmatics of modular SOS. In Proceedings of 9th International Conference on Algebraic Methodology and Software Technology (AMAST '02), LNCS 2442, Kirchner, H. & Ringeissen, C. (eds), Lecture Notes in Computer Science, vol. 2422. Springer, Saint-Gilles-les-Bains, pp. 21–40.CrossRefGoogle Scholar
Norrish, M. (1999) Deterministic expressions in C. In Programming Languages and Systems, 8th European Symposium on Programming, ESOP'99, Proceedings, Swierstra, S. D. (ed.), Lecture Notes in Computer Science, vol. 1576. Springer, Amsterdam, pp. 147–161.CrossRefGoogle Scholar
Owens, C. (1995) Coding binding and substitution explicitly in Isabelle. In Proceedings of the First Isabelle Users Workshop, Cambridge, pp. 36–52. Available at: http://www.cl.cam.ac.uk/lp15/papers/Workshop/ Accessed 8 January 2010.Google Scholar
Owens, S. (2008) A sound semantics for OCamllight. In Programming Languages and Systems, 17th European Symposium on Programming, ESOP 2008, Proceedings, Drossopoulou, S. (ed.), Lecture Notes in Computer Science, vol. 4960. Springer, Budapest, pp. 1–15.Google Scholar
Owens, S. & Flatt, M. (2006) From structures and functors to modules and units. In Proceedings of 11th ACM SIGPLAN International Conference on Functional Programming (ICFP 2006). ACM, Portland, Oregon, pp. 87–98.CrossRefGoogle Scholar
Peskine, G., Sarkar, S., Sewell, P. & Zappa Nardelli, F. (2007) Binding and substitution (note). Available at: http://www.cl.cam.ac.uk/users/pes20/ott/ Accessed 8 January 2010.Google Scholar
Peyton Jones, S. (ed) (2003) Haskell 98 Language and Libraries. The Revised Report. Cambridge University Press.Google Scholar
Pierce, B. C. (2002) Types and Programming Languages. MIT Press.Google Scholar
Pitts, A. M. & Stark, I. D. B. (1993) Observable properties of higher order functions that dynamically create local names, or: What's new? In Mathematical Foundations of Computer Science, 18th International Symposium, MFCS'93, Proceedings, Borzyszkowski, A. M., & Sokolowski, S. (eds), Lecture Notes in Computer Science, vol. 711. Springer-Verlag, Gdansk, Poland, pp. 122–141.Google Scholar
Pollack, R. (2006) Reasoning about languages with binding. Available at: http://homepages.inf.ed.ac.uk/rpollack/export/bindingChallenge_slides.pdf. Slides. Accessed 8 January 2010.Google Scholar
Pottier, F. (2006) An overview of Cαml. In ACM Workshop on ML, ENTCS, vol. 148, no. 2, pp. 27–52.CrossRefGoogle Scholar
Rekers, J. (1992) Parser Generation for Interactive Environments. Ph.D. Thesis, University of Amsterdam.Google Scholar
Reps, T. & Teitelbaum, T. (1984) The synthesizer generator. In Proceedings of the first ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (SDE 1), Pittsburgh, pp. 42–48. http://portal.acm.org/citation.cfm?id=390010.808247 Accessed 8 January 2010.CrossRefGoogle Scholar
Rossberg, A. (2001) Defects in the Revised Definition of Standard ML. Tech. Rep., Saarland University. Updated 2007/01/22.Google Scholar
Sewell, P., Leifer, J. J., Wansbrough, K., Allen-Williams, M., Zappa Nardelli, F., Habouzit, P. & Vafeiadis, V. (2004) Acute: High-Level Programming Language Design for Distributed Computation. Design Rationale and Language Definition. Tech. Rep., UCAM-CL-TR-605. University of Cambridge Computer Laboratory.Google Scholar
Sewell, P., Leifer, J. J., Wansbrough, K., Zappa Nardelli, F., Allen-Williams, M., Habouzit, P. & Vafeiadis, V. (2007a) Acute: High-level programming language design for distributed computation, J. Funct. Program., 17 (4–5): 547–612. Invited submission for an ICFP 2005 special issue.CrossRefGoogle Scholar
Sewell, P. & Zappa Nardelli, F. (2007) Ott, Freiburg. Available at: http://www.cl.cam.ac.uk/users/pes20/ott/ Accessed 8 January 2010.Google Scholar
Sewell, P., Zappa Nardelli, F., Owens, S., Peskine, G., Ridge, T., Sarkar, S. & Strniša, R. (2007b) Ott: Effective tool support for the working semanticist. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP 2007). ACM, pp. 1–12.CrossRefGoogle Scholar
Shinwell, M. R., Pitts, A. M. & Gabbay, M. J. (2003) FreshML: Programming with binders made simple. In Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003). ACM, Uppsala, pp. 263–274.CrossRefGoogle Scholar
Sperber, M., Dybvig, R. K., Flatt, M., Anton Van Straaten, K., Richard, C., William, J. R. (eds), Revised5 Report on the Algorithmic Language Scheme, Findler, R. B. & Jacob M. (Authors, formal semantics). (2007) Revised6 report on the algorithmic language Scheme. Available at: http://www.r6rs.org/ Accessed 8 January 2010.Google Scholar
Strachey, C. (1966) Towards a formal semantics. In Formal Language Description Languages for Computer Programming. North Holland, pp. 198–220.Google Scholar
Strniša, R., Sewell, P. & Parkinson, M. (2007) The Java module system: Core design and semantic definition. In Proceedings of ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA 2007). ACM, Montreal, pp. 499–514.CrossRefGoogle Scholar
Syme, D. (1993) Reasoning with the formal definition of standard ML in HOL. In Higher Order Logic Theorem Proving and its Applications, 6th International Workshop, HUG '93, Proceedings, Joyce, J. J. & Seger, C.-J. H. (eds), Lecture Notes in Computer Science, vol. 780. Springer-Verlag, Vancouver, pp. 43–59.Google Scholar
Terrasse, D. (1995) Encoding natural semantics in Coq. In Algebraic Methodology and Software Technology, 4th International Conference, AMAST '95, Proceedings, Alagar, V. S. & Nivat, M. (eds), Lecture Notes in Computer Science, vol. 936. Springer, Montreal, pp. 230–244.CrossRefGoogle Scholar
Tse, S. & Zdancewic, S. (2008) Concise Concrete Syntax. Tech. Rep., MS-CIS-08-11. University of Pennsylvania. Available at: http://www.cis.upenn.edu/stevez/papers/TZ08tr.pdf Accessed 8 January 2010.Google Scholar
Twelf. (2005). Twelf 1.5. Available at: http://www.cs.cmu.edu/twelf/ Accessed 8 January 2010.Google Scholar
Urban, C. (2008) Nominal techniques in Isabelle/HOL, J. Autom. Reasoning, 40 (4): 327–356.CrossRefGoogle Scholar
Vafeiadis, V. & Parkinson, M. (2007) A marriage of rely/guarantee and separation logic. In CONCUR 2007 - Concurrency Theory, 18th International Conference, Proceedings, Caires, L. & Vasconcelos, V. T. (eds), Lecture Notes in Computer Science, vol. 4703. Springer, Lisbon, pp. 256–271.CrossRefGoogle Scholar
VanInwegen, M. (1996) The Machine-Assisted Proof of Programming Language Properties. Ph.D. Thesis, University of Pennsylvania. Computer and Information Science Tech Report MS-CIS-96-31.Google Scholar
Visser, E. (1997) Syntax Definition for Language Prototyping. Ph.D. Thesis, University of Amsterdam.Google Scholar
Xiao, Y., Ariola, Z & Mauny, M. (2000) From syntactic theories to interpreters: A specification language and its compilation. In First International Workshop on Rule-Based Programming (RULE 2000), Derschowitz, N. & Kirchner, C. (eds). Available at: http://arxiv.org/abs/cs.PL/0009030 Accessed 8 January 2010.Google Scholar
Xiao, Y., Sabry, A. & Ariola, Z. M. (2001) From syntactic theories to interpreters: Automating the proof of unique decomposition, Higher Order Symbol. Comput., 14 (4): 387–409.CrossRefGoogle Scholar
Zalewski, M. (2008) A Semantic Definition of Separate Type Checking in C++ with Concepts—Abstract Syntax and Complete Semantic Definition. Tech. Rep., 2008:12. Department of Computer Science and Engineering, Chalmers University.Google Scholar
Zalewski, M. & Schupp, S. (2009) A semantic definition of Separate type checking in C++ with concepts. J. Object Technol. 8 (5): 105–132.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.