Generic bidirectional typing for dependent type theories

Overview

• Bidirectional typing is a technique for controlling the flow of type information in typing rules and specifying how they should be used.
• Bidirectional typing has been studied and applied to many type theories, but the formal development has been confined to specific theories.
• This work presents a generic approach to bidirectional typing for a broad class of dependent type theories.

Plain English Explanation

Bidirectional typing is a way of breaking down the typing process into two steps: inference and checking. In the inference step, the system tries to figure out the type of an expression based on the context. In the checking step, the system verifies that the expression actually has the type it inferred.

This separation of inference and checking allows for more control over how type information flows through the typing rules. It's like having a traffic cop directing the flow of cars (type information) through an intersection (the typing rules), making sure everything goes smoothly.

The authors of this paper wanted to develop a general framework for bidirectional typing that could be applied to a wide range of type theories, rather than being limited to a specific theory. This would make it easier to use bidirectional typing in different settings and allow for more flexibility and reuse.

Technical Explanation

The paper first provides a general definition of type theories, which can be thought of as a logical framework for defining different type systems. The authors then define both a declarative type system and a bidirectional type system within this framework.

They then prove that the declarative and bidirectional type systems are equivalent, meaning they produce the same typing judgments. This is an important result because it shows that the bidirectional system is a sound and complete implementation of the declarative system.

The authors also use this equivalence to establish the decidability of typing for weakly normalizing type theories, meaning there is a guaranteed algorithm for determining the type of an expression. They have implemented this algorithm in a prototype and used it with various type theories in practice.

Critical Analysis

The paper presents a robust and general framework for bidirectional typing, which is a significant contribution to the field. By developing a theory-independent approach, the authors have made bidirectional typing more accessible and easier to apply to a wider range of type systems.

However, the paper does not address the performance implications of the bidirectional typing algorithm. While it is guaranteed to terminate, the actual efficiency of the algorithm is not discussed. Additionally, the paper does not provide any empirical evaluation of the algorithm's performance in practice.

Furthermore, the paper focuses on the theoretical development of the framework and does not delve into potential applications or use cases. Exploring how this generic bidirectional typing approach can benefit real-world type systems and programming languages would be a valuable next step.

Conclusion

This paper presents a comprehensive, theory-independent approach to bidirectional typing, which is an important technique for controlling the flow of type information in typing rules. By proving the equivalence between declarative and bidirectional type systems, the authors have laid the groundwork for developing efficient and reliable type-checking algorithms that can be applied across a wide range of type theories. While further research is needed to assess the practical performance and potential applications of this framework, the work represents a significant advancement in the formal understanding and implementation of bidirectional typing.