More Like this

1. Soundly Handling Linearity

   https://doi.org/10.1145/3632896  

   Tang, Wenhao; Hillerström, Daniel; Lindley, Sam; Morris, J. Garrett (January 2024, Proceedings of the ACM on Programming Languages)

   Hicks, Michael (Ed.)

   We propose a novel approach to soundly combining linear types with multi-shot effect handlers. Linear type systems statically ensure that resources such as file handles and communication channels are used exactly once. Effect handlers provide a rich modular programming abstraction for implementing features ranging from exceptions to concurrency to backtracking. Whereas conventional linear type systems bake in the assumption that continuations are invoked exactly once, effect handlers allow continuations to be discarded (e.g. for exceptions) or invoked more than once (e.g. for backtracking). This mismatch leads to soundness bugs in existing systems such as the programming language Links, which combines linearity (for session types) with effect handlers. We introduce control-flow linearity as a means to ensure that continuations are used in accordance with the linearity of any resources they capture, ruling out such soundness bugs. We formalise the notion of control-flow linearity in a System F-style core calculus Feff∘, equipped with linear types, an effect type system, and effect handlers. We define a linearity-aware semantics in order to formally prove that Feff∘ preserves the integrity of linear values in the sense that no linear value is discarded or duplicated. In order to show that control-flow linearity can be made practical, we adapt Links based on the design of Feff∘, in doing so fixing a long-standing soundness bug. Finally, to better expose the potential of control-flow linearity, we define an ML-style core calculus Qeff∘, based on qualified types, which requires no programmer provided annotations, and instead relies entirely on type inference to infer control-flow linearity. Both linearity and effects are captured by qualified types. Qeff∘ overcomes a number of practical limitations of Feff∘, supporting abstraction over linearity, linearity dependencies between type variables, and a much more fine-grained notion of control-flow linearity. 

   more » « less
2. Phase-type bounds on network performance

   https://doi.org/10.1109/CISS.2018.8362284  

   Boroujeny, Massieh Kordi; Ephraim, Yariv; Mark, Brian L. (March 2018, 52nd Annual Conference on Information Sciences and Systems (CISS))

   Evaluation of end-to-end network performance using realistic traffic models is a challenging problem in networking. The classical theory of queueing networks is feasible only under rather restrictive assumptions on the input traffic models and network elements. An alternative approach, first proposed in the late 1980s, is to impose deterministic bounds on the input traffic that can be used as a basis for a network calculus to compute end-to-end network delay bounds. Such deterministic bounds are inherently loose as they must accommodate worst case scenarios. Since the early 1990s, efforts have shifted to development of a stochastic network calculus to provide probabilistic end-to-end performance bounds. In this paper, we capitalize on the approach of stochastically bounded burstiness (SBB) which was developed for a general class of bounding functions, and was demonstrated for a bound that is based on a mixture distribution. We specialize the SBB bounds to bounds based on the class of phase-type distributions, which includes mixture distributions as a particular case. We develop the phase-type bounds and demonstrate their performance. 

   more » « less
3. Internalizing Indistinguishability with Dependent Types

   https://doi.org/10.1145/3632886  

   Liu, Yiyun; Chan, Jonathan; Shi, Jessica; Weirich, Stephanie (January 2024, Proceedings of the ACM on Programming Languages)

   In type systems with dependency tracking, programmers can assign an ordered set of levels to computations and prevent information flow from high-level computations to the low-level ones. The key notion in such systems isindistinguishability: a definition of program equivalence that takes into account the parts of the program that an observer may depend on. In this paper, we investigate the use of dependency tracking in the context of dependently-typed languages. We present the Dependent Calculus of Indistinguishability (DCOI), a system that adopts indistinguishability as the definition of equality used by the type checker. DCOI also internalizes that relation as an observer-indexed propositional equality type, so that programmers may reason about indistinguishability within the language. Our design generalizes and extends prior systems that combine dependency tracking with dependent types and is the first to support conversion and propositional equality at arbitrary observer levels. We have proven type soundness and noninterference theorems for DCOI and have developed a prototype implementation of its type checker. 

   more » « less
4. The Refinement Calculus of Reactive Systems Toolset

   https://doi.org/10.1007/s10009-020-00561-4  

   Dragomir, Iulia; Preoteasa, Viorel; Tripakis, Stavros (April 2020, International Journal on Software Tools for Technology Transfer)

   We present the Refinement Calculus of Reactive Systems Toolset, an environment for compositional formal modeling and reasoning about reactive systems, built around Isabelle, Simulink, and Python. The toolset implements the Refinement Calculus of Reactive Systems (RCRS), a contract-based refinement framework inspired by the classic refinement calculus and interface theories. The toolset formalizes the entire RCRS theory in about 30000 lines of Isabelle code. The toolset also contains a translator of Simulink diagrams and a formal analyzer implemented on top of Isabelle. We present the main functionalities of the RCRS Toolset via a series of pedagogical examples and also describe a larger case study from the automotive domain. 

   more » « less
5. Data flow refinement type inference

   https://doi.org/10.1145/3434300  

   Pavlinovic, Zvonimir; Su, Yusen; Wies, Thomas (January 2021, Proceedings of the ACM on Programming Languages)

   Refinement types enable lightweight verification of functional programs. Algorithms for statically inferring refinement types typically work by reduction to solving systems of constrained Horn clauses extracted from typing derivations. An example is Liquid type inference, which solves the extracted constraints using predicate abstraction. However, the reduction to constraint solving in itself already signifies an abstraction of the program semantics that affects the precision of the overall static analysis. To better understand this issue, we study the type inference problem in its entirety through the lens of abstract interpretation. We propose a new refinement type system that is parametric with the choice of the abstract domain of type refinements as well as the degree to which it tracks context-sensitive control flow information. We then derive an accompanying parametric inference algorithm as an abstract interpretation of a novel data flow semantics of functional programs. We further show that the type system is sound and complete with respect to the constructed abstract semantics. Our theoretical development reveals the key abstraction steps inherent in refinement type inference algorithms. The trade-off between precision and efficiency of these abstraction steps is controlled by the parameters of the type system. Existing refinement type systems and their respective inference algorithms, such as Liquid types, are captured by concrete parameter instantiations. We have implemented our framework in a prototype tool and evaluated it for a range of new parameter instantiations (e.g., using octagons and polyhedra for expressing type refinements). The tool compares favorably against other existing tools. Our evaluation indicates that our approach can be used to systematically construct new refinement type inference algorithms that are both robust and precise. 

   more » « less