Subclasses of linear inequalities where each inequality has at most two variables are popular in abstract interpretation and model checking, because they strike a balance between what can be described and what can be efficiently computed. This paper focuses on the TVPI class of inequalities, for which each coefficient of each two variable inequality is unrestricted. An implied TVPI inequality can be generated from a pair of TVPI inequalities by eliminating a given common variable (echoing resolution on clauses). This operation, called result, can be applied to derive TVPI inequalities which are entailed (implied) by a given TVPI system. The key operation on TVPI is calculating closure: satisfiability can be observed from a closed system and a closed system also simplifies the calculation of other operations. A closed system can be derived by repeatedly applying the result operator. The process of adding a single TVPI inequality to an already closed input TVPI system and then finding the closure of this augmented system is called incremental closure. This too can be calculated by the repeated application of the result operator. This paper studies the calculus defined by result, the structure of result derivations, and how derivations can be combined and controlled. A series of lemmata on derivations are presented that, collectively, provide a pathway for synthesising an algorithm for incremental closure. The complexity of the incremental closure algorithm is analysed and found to be O((n2+m2)lg⁡(m)), where n is the number of variables and m the number of inequalities of the input TVPI system.

Flexible records are a powerful concept in type systems that form the basis of, for instance, objects in dynamically typed languages. One caveat of using flexible records is that a program may try to access a record field that does not exist. We present a type inference algorithm that checks for these runtime errors. The novelty of our algorithm is that it satisfies a clear notion of completeness: The inferred types are optimal in the sense that type annotations cannot increase the set of typeable programs. Under certain assumptions, our algorithm guarantees the following stronger property: it rejects a program if and only if it contains a path from an empty record to a field access on which the field has not been added. We derive this optimal algorithm by abstracting a semantics to types. The derived inference rules use a novel combination of type terms and Boolean functions that retains the simplicity of unification-based type inference but adds the ability of Boolean functions to express implications, thereby addressing the challenge of combining implications and types. By following our derivation method, we show how various operations such as record concatenation and branching if a field exists lead to Boolean satisfiability problems of different complexity. Analogously, we show that more expressive type systems give rise to SMT problems. On the practical side, we present an implementation of the select and update operations and give practical evidence that these are sufficient in real-world applications.

We present a translation scheme from a pure functional domain-specific language (DSL) to C. The over-arching idea of this scheme is to preserve the structure of the input program as much as possible. This includes, among other things, to refrain from inlining user-written functions and to retain variable names as much as possible. We apply this translation scheme to GDSL, a DSL used for the specification of decoders for machine instructions. GDSL offers non-trivial language features such as monadic actions that our translation scheme maps one-to-one to C statements, resulting in code that closely resembles hand-written C code. Indeed, it is feasible to debug and profile the program at the C level and to interface the generated code with existing C code without marshaling data. Our translation scheme is therefore an attractive starting point for a light-weight DSL since no other language-specific tools besides the compiler are necessary. Moreover, the generated code is amenable to compiler optimizations found in off-the-shelf C compilers. This is illustrated by the performance achieved by a decoder for x86 machine instructions implemented in GDSL which is as fast as a production-quality decoding library shipped by Intel.

Type inference and program analysis both infer static properties about a program. Yet, they are constructed using very different techniques. We reconcile both approaches by deriving a type inference from a denotational semantics using abstract interpretation. We observe that completeness results in the abstract interpretation literature can be used to derive type inferences that are backward complete, a property akin to the inference of principal typings. The resulting algorithm is similar to that of Milner-Mycroft, that is, it infers Hindley-Milner types while allowing for polymorphic recursion. Instead of type schemes, it uses expansion to instantiate types. Since our expansion operator is agnostic to the abstract domain, we are able to apply it not only to types. We illustrate this by inferring the size of vector types using systems of linear equalities.