SHF:Small:RUI: Semantic Complexity of Advanced Data Types

点击翻译按钮获取中文摘要

Testing of programs has dominated the last 50 years of software development, but the next 50 will see an increased demand for provably correct software. This is partly because modern applications are increasingly safety critical, partly because testing is by its very nature only a partial correctness guarantee, and partly because programming language technology is now at the stage where it is feasible to formally verify critical programs. Language-based verification uses a programming language's type system to help guarantee program correctness: the more program properties a type system can express, the more the compiler can automatically verify. Advanced data types such as Generalized Algebraic Data Types (GADTs) help close the so-called "semantic gap" between what programmers know about programs involving them and what a type system can express about those programs. The key observation underlying this project is that GADTs and other advanced data types are underspecified by their syntax, which often leads to them being used in unjustified ways that undermine their promise for verification. The project's novelty is a fully semantic response to this observation, embodied by the entirely novel notion of the functorial completion of a data type. This notion of functorial completion leads directly to the project's overall impact, which is to change the way programmers understand, and thus program with, GADTs and other advanced data types.The project shows that the way that even ordinary GADTs are currently understood is not formally justifiable and leads to unsafe programming practices, with the obvious consequences for verification, security, and reliability of software systems. It gives a grammar that generates a very general class of GADTs and other advanced data types, and uses the new notion of the functorial completion of a data type to give the data types generated by this grammar the same kind of semantics that has long been the cornerstone of the theory of standard algebraic data types. This ensures that data types generated by the grammar can be used with semantic and computational confidence. Furthermore it allows the data types to be classified according to semantic complexity--a novel notion introduced in this project--that helps programmers better understand a data type's semantic and computational properties. Finally, the project gives a framework for constructing parametric models for polymorphic languages supporting the advanced data types generated by the grammar. This framework is principled, conceptually simple, uniform, comprehensive, and predictive. It is constructed specifically to validate the semantics of the GADTs and other advanced data types generated by the grammar, and the constructs that are derived in a standard way from such semantics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.