Type systems provide specifications and enable reasoning about the programs. Among other benefits, type systems provide guarantees of the absence of certain (ill-typed) program behaviors. Refinement types further enrich the expressiveness of type systems by allowing a predicate alongside the type. The crucial divide by zero and null pointer errors are safely eliminated with refinement types. Interestingly, Correctness-by-Construction (CbC) also provides a way to set specifications for the programs. The specifications are provided for the smaller modules. Larger programs are built by composing the functionally correct smaller modules. Therefore, CbC naturally results in verified and correct programs following the program specifications. In this short paper, we highlight that CbC meets refinement types in a sense that both approaches provide specifications for program correctness and larger programs are built by composing the functionally correct smaller modules.
Subtyping is a concept frequently encountered in many programming languages and calculi. Various forms of subtyping exist for different type system features, including intersection types, union types or bounded quantification. Normally these features are designed independently of each other, without exploiting obvious similarities (or dualities) between features.
This paper proposes a novel methodology for designing subtyping relations that exploits duality between features. At the core of our methodology is a generalization of subtyping relations, which we call Duotyping. Duotyping is parameterized by the mode of the relation. One of these modes is the usual subtyping, while another mode is supertyping (the dual of subtyping). Using the mode it is possible to generalize the usual rules of subtyping to account not only for the intended behaviour of one particular language construct, but also of its dual. Duotyping brings multiple benefits, including: shorter specifications and implementations, dual features that come essentially for free, as well as new proof techniques for various properties of subtyping. To evaluate a design based on Duotyping against traditional designs, we formalized various calculi with common OOP features (including union types, intersection types and bounded quantification) in Coq in both styles. Our results show that the metatheory when using Duotyping does not come at a significant cost: the metatheory with Duotyping has similar complexity and size compared to the metatheory for traditional designs. However, we discover new features as duals to well-known features. Furthermore, we also show that Duotyping can significantly simplify transitivity proofs for many of the calculi studied by us.
This artifact contains the Coq formalization associated with the paper The Duality of Subtyping submitted in ECOOP 2020. This document explains how to run the Coq formalization. Artifact can either be compiled in the pre-built docker image with all the dependencies installed or it could be built from the scratch. Sections 1-7 explain the basic information about the artifact. Section A explains how to get the docker image for the artifact. Section B explains the prerequisites and the steps to run coq files from scratch. Section C explains coq files briefly. Section D shows the correspondence between important lemmas discussed in paper and their respective Coq formalization. The term MonoTyping used in artifact corresponds to the standard subtyping systems.
'/%3e%3cuse xlink:href='%23a' transform='translate(0 -400)'/%3e%3cuse xlink:href='%23a' transform='translate(0 -600)'/%3e%3cuse xlink:href='%23a' transform='translate(0 -800)'/%3e%3cuse xlink:href='%23a' transform='translate(0 -1000)'/%3e%3cuse xlink:href='%23a' transform='translate(0 -1200)'/%3e%3cpath d='M0 0h1400v800H0z' style='fill:%23010066'/%3e%3cpath d='M576 100c-166.146 0-301 134.406-301 300s134.854 300 301 300c60.027 0 115.955-17.564 162.927-47.783-27.353 9.44-56.71 14.602-87.271 14.602-147.327 0-266.897-119.172-266.897-266.01 0-146.837 119.57-266.01 266.897-266.01 32.558 0 63.746 5.815 92.602 16.468C696.217 118.91 638.305 100 576 100z' style='fill:%23fc0'/%3e%3cpath d='m914.286 471.429-99.538-53.25 29.43 108.982-66.575-91.165-20.77 110.96-20.428-111.024-66.857 90.96L699.314 418l-99.701 52.943 74.065-85.192-112.8 4.441 103.694-44.62-103.555-44.94L673.8 305.42 600 220l99.538 53.25-29.43-108.982 66.575 91.165 20.77-110.96 20.428 111.023 66.857-90.959L814.97 273.43l99.702-52.944-74.065 85.193 112.8-4.441-103.694 44.62 103.555 44.94-112.785-4.79z' style='fill:%23fc0' transform='matrix(1.2738 0 0 1.2423 -89.443 -29.478)'/%3e%3c/svg%3e)
'/%3e%3cpath fill='%23fff' d='m8.751-17.959 10.11 11.373L3.997-9.844l13.94-6.1-7.692 13.129z'/%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='rotate(23.036 .093 25.536)'/%3e%3cuse xlink:href='%23a' transform='rotate(45.87 1.273 16.18)'/%3e%3cuse xlink:href='%23a' transform='rotate(69.945 .996 12.078)'/%3e%3cuse xlink:href='%23a' transform='rotate(20.66 -19.689 31.932)'/%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='rotate(144 450 300)'/%3e%3cuse xlink:href='%23a' transform='rotate(216 450 300)'/%3e%3cuse xlink:href='%23a' transform='rotate(288 450 300)'/%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='translate(288.889 -214.211)'/%3e%3cuse xlink:href='%23a' transform='translate(108 342.749)'/%3e%3cuse xlink:href='%23a' transform='translate(469.189 342.749)'/%3e%3c/svg%3e)
'%3e%3cg id='b'%3e%3cpath id='a' stroke='%23000' stroke-width='2' d='M-6-25H6m-12 3H6m-12 3H6'/%3e%3cuse xlink:href='%23a' y='44'/%3e%3c/g%3e%3cpath stroke='%23fff' d='M0 17v10'/%3e%3ccircle r='12' fill='%23cd2e3a'/%3e%3cpath fill='%230047a0' d='M0-12A6 6 0 0 0 0 0a6 6 0 0 1 0 12 12 12 0 0 1 0-24z'/%3e%3c/g%3e%3cg transform='rotate(-123.69)'%3e%3cuse xlink:href='%23b'/%3e%3cpath stroke='%23fff' d='M0-23.5v3M0 17v3.5m0 3v3'/%3e%3c/g%3e%3c/svg%3e)