Report
Teaser, summary, work performed and final results
Periodic Reporting for period 1 - InfTy (Infinitary Rewriting for Type Systems)
Teaser
Infinite objects are ubiquitous in computer science. For instance, an interactive program may be modelled as taking for input a stream (an infinite list) of requests and producing a stream of responses. Infinite objects also naturally appear in lazy functional programming...
Summary
Infinite objects are ubiquitous in computer science. For instance, an interactive program may be modelled as taking for input a stream (an infinite list) of requests and producing a stream of responses. Infinite objects also naturally appear in lazy functional programming languages like e.g. Haskell where infinite lazy lists may be manipulated. In theoretical computer science infinite objects play an important role e.g. in automata theory and exact real number arithmetic. Representing and reasoning about infinite computations is crucial in designing safe software systems.
The objective of InfTy is to devise mathematical methods for reasoning about programs manipulating infinite objects, developing compositional typed formalisms and integrating them with infinitary rewriting techniques. Our methods are compositional and applicable to higher-order programs, while still adopting the operational perspective of rewriting. We devise an infinitary rewriting interpretation of coinductive types, i.e., of types of infinite objects. We thus provide a simple theory for type systems with infinite objects and unify previous type-based and rewriting-based work on productivity. We develop algorithms to check correctness of programs manipulating infinite objects.
Recently, a coinductive approach to infinitary rewriting has been proposed by Endrullis et al., and coinductive proofs for some results in infinitary rewriting have been developed. The coinductive approach simplifies investigations in infinitary rewriting and thus it is our chosen methodology. This approach, which we further develop, is by itself of high interest.
Work performed
We formulated an infinitary rewriting semantics for type systems with higher-order inductive and coinductive types. In other words, we devised a programming formalism in which programs manipulating infinite objects may be written, and we provided a semantic infinitary rewriting interpretation for this formalism. The interpretation provides a natural and easy to understand correctness criterion which generalises the notion of productivity from term rewriting theory. We proved that well-typed programs in our system are correct in this sense. We devised practical algorithms to check the well-typedness of the programs and to infer minimal types.
On a technical side, we further developed the coinductive proof methodology for infinitary rewriting. We formalised some results in infinitary lambda-calculus, clarifying their coinductive foundations. Our work on the formalisation and further development of coinductive foundations of infinitary rewriting also led to advances in automation in proof assistants and to a solution of a long-standing open problem in the field of term rewriting.
The results of the project have been disseminated through open-access journal publications (two publications currently under review for Logical Methods in Computer Science, one accepted to LIPIcs, vol. 97, open postproceedings of TYPES 2016), through conference publications (two publications at Formal Structures for Computation and Deduction, one at the Conference on Intelligent Computer Mathematics), invited talks (invited talk at the EUTYPES 2018 meeting, keynote address at the CoqPL 2018 workshop), and research visits.
Final results
In comparison to our setting, the infinite data structures considered before in the term rewriting literature are very simple. We generalised the notion of productivity from term rewriting to a setting with higher-order functions and nested inductive and coinductive definitions. Our work opens up a line of research on combining infinitary rewriting with typed formalisms. Prior research in this direction had been very limited.
In order to clarify and further develop the coinductive proof methodology we formalised some results in the Coq proof assistant, including a formalisation of the confluence of infinitary lambda-calculus. This is the largest formalisation of results in infinitary lambda-calculus carried out so far. The automation techniques developed as part of the formalisation process are of interest to a broader community. In particular, they are of high interest to the programming languages community, as evidenced by a keynote address at the Coq for Programming Languages (CoqPL) 2018 workshop.
Our work on confluence also led to a formal solution of a long-standing problem in the field of term rewriting.
Website & more info
More info: http://www.mimuw.edu.pl/.