Ott

Francesco Zappa Nardelli, Peter Sewell, and Scott Owens

(with Matthew Parkinson, Gilles Peskine, Tom Ridge, Susmit Sarkar, and Rok Strniša)

Ott is a tool for writing definitions of programming languages and calculi. It takes as input a definition of a language syntax and semantics, in a concise and readable ASCII notation that is close to what one would write in informal mathematics. It generates LaTeX to build a typeset version of the definition, and Coq, HOL, and Isabelle versions of the definition. Additionally, it can be run as a filter, taking a LaTeX/Coq/Isabelle/HOL source file with embedded (symbolic) terms of the defined language, parsing them and replacing them by target-system terms. For a simple example, here is an Ott source file for an untyped call-by-value lambda calculus (test10.ott), and the generated LaTeX (compiled to pdf) and (compiled to ps), Coq, Isabelle, and HOL definitions.

Most simply, the tool can be used to aid completely informal LaTeX mathematics. Here it permits the definition, and terms within proofs and exposition, to be written in a clear, editable, ASCII notation, without LaTeX noise. It generates good-quality typeset output. By parsing (and so sort-checking) this input, it quickly catches a range of simple errors, e.g. inconsistent use of judgement forms or metavariable naming conventions.

That same input can be used to generate formal definitions, for Coq, HOL, and Isabelle. It should thereby enable a smooth transition between use of informal and formal mathematics. Additionally, the tool can automatically generate definitions of functions for free variables, single and multiple substitutions, subgrammar checks (e.g. for value subgrammars), and binding auxiliary functions. At present only a fully concrete representation of binding, without quotienting by alpha equivalence, is fully supported. An experimental backend generates a locally-nameless representation of terms for a subset of the Ott metalanguage: details can be found here.

The distribution includes several examples, in varying levels of completeness: untyped and simply typed lambda-calculus, a calculus with ML polymorphism, the POPLmark Fsub with and without records, an ML module system taken from (Leroy, JFP 1996) and equipped with an operational semantics, and LJ, a lightweight Java fragment. More substantially, Ott has been used for work on iJAM and LJAM, Java Module Systems, by Rok Strniša, and semantics for OCaml light, by Scott Owens.

A release of the Ott source is available, and comment and feedback would be much appreciated.

Papers and Documentation

• Ott: Effective Tool Support for the Working Semanticist (pdf). Peter Sewell, Francesco Zappa Nardelli, Scott Owens, Gilles Peskine, Thomas Ridge, Susmit Sarkar, Rok Strniša. Journal of Functional Programming 20(1):71-122, 2010
• Ott: Effective Tool Support for the Working Semanticist (pdf) and (ps) [bib]. In ICFP 2007.
• User Guide (html), (pdf), and (ps)
• Binding and Substitution (draft) (pdf) and (ps)
• The experimental Coq locally-nameless backend (html)

Code

• ott_distro_0.21.2.tar.gz tarball (includes the manual)
• (we no longer provide a Windows binary distribution)
• README file from the distribution
• revision history summary

Bug Tracker

• here

Mailing Lists

• cl-ott-announce announcement mailing list
• cl-ott-discuss discussion mailing list

Examples

(all files except the proof scripts are generated from the Ott sources)

(*) These systems would need explicit alpha conversion in the rules to capture the intended semantics using the fully concrete representation.

[validate]