The next talk in the Galois Tech Seminar series:

• Date: Tuesday, October 13th, 2009
• Title: Constructing A Universal Domain for Reasoning About Haskell Datatypes
• Speaker: Brian Huffman
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/10/06/huffman-universal/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

Presented by Adam Foltzer.

Interpreters offer a convenient and intuitive way for programmers to reason about language behavior through denotational semantics. However in a setting like Coq, where all recursive functions must provably terminate, it is impossible to write interpreters for non-terminating languages. The standard alternative is to inductively define operational semantics, but this can yield proofs that are difficult to automate, particularly in the presence of changing language features.

This talk presents a combined approach, where an interpreter is used in combination with operational semantics to prove type preservation of a small functional language. To demonstrate the scalability of the Coq development, let expressions and a pair types will be added and preservation will be proved again with only one extra line of proof script.

This technique and development are adapted from Greg Morrisett's lectures at the 2011 Oregon Programming Languages Summer School, and are available at his web site.

abstract:

CH2O is the PhD project of Robbert Krebbers and has as its goal a formal version of the ISO standard of the C programming language. A problem with this is that the C standard is fundamentally inconsistent.

There are three versions of the CH2O semantics: a (small step) operational semantics, an executable semantics, and an axiomatic semantics (a separation logic for C). The most important properties — soundness and completeness results, subject reduction and progress, correctness of the type checker — have all been proved. All definitions and proofs have been fully formalized in Coq, without any axioms and on top of a non-trivial support library.

The CH2O project has two abstract C-like languages. A significant subset of C called “CH2O abstract C” is translated into a simplified language called “CH2O core C”. This translation is written in Coq and implicitly gives a semantics to CH2O abstract C. The rest of the formalization is all about CH2O core C.

The executable CH2O semantics has been extracted to OCaml and combined with the CIL parser to a standalone “interpreter”. This tool can be used to explore all behaviors of a program according to the C standard. Although the CH2O semantics does not yet support I/O (nor the exit function), a small hack allows the CH2O interpreter to still explore programs that call printf.

The CH2O semantics has been specifically designed to be compatible with the CompCert semantics for C. Significant differences between CompCert and CH2O are that the CH2O semantics has explicit typing judgments for everything, and that CH2O applies to any ISO compliant compiler.

bio:

I have a master degree in mathematics (my thesis was about conformal supergravity), and a PhD in computer science, both from the University of Amsterdam. I also worked as a system administrator at the University of Utrecht.

Currently I’m an assistant professor of computer science at the Radboud University Nijmegen. My research has been mainly about formalization of mathematics using interactive theorem provers, but recently I have been getting interested in practical program verification, where interactive proof is used when automation doesn’t cut it.

At the moment I am an alternate member of WG14, and I won a price in the IOCCC twice. And my favorite project is the CakeML/verified-HOL Light project.

Abstract: Lean is an interactive theorem prover and functional programming language. Lean implements a version of the Calculus of Inductive Constructions. Its elaborator and unification algorithms are designed around the use of type classes, which support algebraic reasoning, programming abstractions, and other generally useful means of expression. Lean has parallel compilation and checking of proofs, and provides a server mode that supports a continuous compilation and rich user interaction in editing environments such as Visual Studio Code, Monaco, Emacs, and Vim. In the first part of this talk, we provide a short introduction to Lean, its applications, and its metaprogramming framework. We also describe how this framework extends Lean’s object language with an API to many of Lean’s internal structures and procedures, and provides ways of reflecting object-level expressions into the metalanguage. We provide evidence to show that our implementation is efficient, and that it provides a convenient and flexible way of writing not only metaprograms and small-scale interactive tactics, but also more substantial kinds of automation. In the second part, we describe our plans for the system, and what we are currently working on.

More information about Lean can be found at http://leanprover.github.io. The interactive book “Theorem Proving in Lean” is the standard reference for Lean. The book is available in PDF and HTML formats. In the HTML version, all examples and exercises can be executed in the reader’s web browser.

Bio: I’m a Principal Researcher in the RiSE group at Microsoft Research. I joined Microsoft in 2006, before that I was a Computer Scientist at SRI International. I obtained my PhD at PUC-Rio in 2000. My research areas are automated reasoning, theorem proving, decision procedures, SAT and SMT. I’m the main architect of Lean, Z3, Yices 1.0 and SAL. Lean is an open source theorem prover and programming language. Sebastian Ullrich and I are currently developing the next version (Lean 4). Z3 and Yices are SMT solvers, and SAL (the Symbolic Analysis Laboratory) is an open source tool suite that includes symbolic and bounded model checkers, and automatic test generators. Z3 has been open sourced (under the MIT license) in the beginning of 2015. I received the Haifa Verification Conference Award in 2010. In 2014, the TACAS conference (Tools and Algorithms for the Construction and Analysis of Systems) has given an award for “The most influential tool paper in the first 20 years of TACAS” to the Z3 paper: Z3: An Efficient SMT Solver. 14th International Conference, TACAS 2008, vol. 4963 of Lecture Notes in Computer Science. In 2015, Z3 received the Programming Languages Software Award from ACM SIGPLAN. In 2017, the International Conference on Automated Deduction (CADE) presented the Skolem Award for my paper “Efficient E-Matching for SMT Solvers” that has passed the test of time, by being a most influential paper in the field. In 2018, the ETAPS conference has given the test of time award to the Z3 paper: Z3: An Efficient SMT Solver. You can see more about me at https://leodemoura.github.io/about.html