This article traces in broad strokes the evolution of the intimate relationship between mathematical logic and computer science. The emphasis is on turning points in this relationship, i.e., moments when new directions of research were opened and new connections were established between the two fie lds. The article is not a comprehensive account and history of the relationship, but a personal perspective of a profoundly changed, and still changing, inter-dependence between two mainstays of the mathematical disciplines.

Recent work on integration of SDNs with application-layer systems like Hadoop has created a class of system, SDN-Enabled Applications, which implement application-specific functionality on the network layer by exposing network monitoring and control semantics to application developers. This requires domain-specific knowledge to correctly reason about network behavior and properties, as the SDN is now tightly coupled to the larger system. Existing tools for SDN verification and analysis are insufficiently expressive to capture this composition of network and domain models. Unfortunately, it is exactly this kind of automated reasoning and verification that is necessary to develop robust SDN-enabled applications for real-world systems. In this paper, we present ongoing work on Verificare, a verification platform being built to enable formal verification of SDNs as components of a larger domain-specific system. SLA, safety, and security requirements can selected from a variety of formal libraries and automatically verified using a variety of off-the-shelf tools. This approach not only extends the flexibility of existing SDN verification systems, but can actually provide more fine-grained analysis of possible network states due to extra information supplied by the domain model.

The papers included in this special issue of Mathematical Structures in Computer Science were selected from a larger set we solicited from leading research groups on both sides of the Atlantic. They cover a wide spectrum of tutorials, recent results and surveys in the area of lightweight and practical formal methods in the design and analysis of safety-critical systems. All the papers we received were submitted to a rigorous process of review and revision, based on which we made our final selection.

Have formal methods in computer science come of age? While the contributions to this special issue of Mathematical Structures in Computer Science attest to their importance in the design and analysis of particular software systems, their relevance to the field as a whole is far wider. In recent years, formal methods have become more accessible and easier to use, more directly related to practical problems and more adaptable to imperfect and/or approximate specifications in real-life applications. As a result, they are now a central component of computer-science education and research.

Desirable application performance is typically guaranteed through the use of Service Level Agreements (SLAs) that specify fixed fractions of resource capacities that must be allocated for unencumbered use by the application. The mapping between what constitutes desirable performance and SLAs is not unique: multiple SLA expressions might be functionally equivalent. Having the flexibility to transform SLAs from one form to another in a manner that is provably safe would enable hosting solutions to achieve significant efficiencies. This paper demonstrates the promise of such an approach by proposing a type-theoretic framework for the representation and safe transformation of SLAs. Based on that framework, the paper describes a methodical approach for the inference of efficient and safe mappings of periodic, real-time tasks to the physical and virtual hosts that constitute a hierarchical scheduler. Extensive experimental results support the conclusion that the flexibility afforded by safe SLA transformations has the potential to yield significant savings.

NetSketch is a tool for the specification of constrained-flow applications and the certification of desirable safety properties imposed thereon. NetSketch assists system integrators in two types of activities: modeling and design. As a modeling tool, it enables the abstraction of an existing system while retaining sufficient information about it to carry out future analysis of safety properties. As a design tool, NetSketch enables the exploration of alternative safe designs as well as the identification of minimal requirements for outsourced subsystems. NetSketch embodies a lightweight formal verification philosophy, whereby the power (but not the heavy machinery) of a rigorous formalism is made accessible to users via a friendly interface. NetSketch does so by exposing tradeoffs between exactness of analysis and scalability, and by combining traditional whole-system analysis with a more flexible compositional analysis. The compositional analysis is based on a strongly-typed Domain-Specific Language (DSL) for describing and reasoning about constrained-flow networks at various levels of sketchiness along with invariants that need to be enforced thereupon. In this paper, we define the formal system underlying the operation of NetSketch, in particular the DSL behind NetSketch's user-interface when used in "sketch mode", and prove its soundness relative to appropriately-defined notions of validity. In a companion paper [7], we overview NetSketch, highlight its salient features, and illustrate how it could be used in applications that include: the management/shaping of traffic flows in a vehicular network (as a proxy for cyber-physical systems (CPS) applications) and a streaming media network (as a proxy for Internet applications).

Desirable application performance is typically guaranteed through the use of Service Level Agreements (SLAs) that specify fixed fractions of resource capacities that must be allocated for unencumbered use by the application. The mapping between what constitutes desirable performance and SLAs is not unique: multiple SLA expressions might be functionally equivalent. Having the flexibility to transform SLAs from one form to another in a manner that is provably safe would enable hosting solutions to achieve significant efficiencies. This paper demonstrates the promise of such an approach by proposing a type-theoretic framework for the representation and safe transformation of SLAs. Based on that framework, the paper describes a methodical approach for the inference of efficient and safe mappings of periodic, real-time tasks to the physical and virtual hosts that constitute a hierarchical scheduler. Extensive experimental results support the conclusion that the flexibility afforded by safe SLA transformations has the potential to yield significant savings.

Interdomain routing on the Internet is performed using route preference policies specified independently and arbitrarily by each autonomous system (AS) in the network. These policies are used in the border gateway protocol (BGP) by each AS when selec

Weak references are references that do not prevent the object they point to from being garbage collected. Many realistic languages, including Java, SML/NJ, and Haskell to name a few, support weak references. However, there is no generally accepted formal semantics for weak references. Without such a formal semantics it becomes impossible to formally prove properties of such a language and the programs written in it.We give a formal semantics for a calculus called λweak that includes weak references and is derived from Morrisett, Felleisen, and Harper's λgc. The semantics is used to examine several issues involving weak references. We use the framework to formalize the semantics for the key/value weak references found in Haskell. Furthermore, we consider a type system for the language and show how to extend the earlier result that type inference can be used to collect reachable garbage. In addition we show how to allow collection of weakly referenced garbage without incurring the computational overhead often associated with collecting a weak reference which may be later used. Lastly, we address the non-determinism of the semantics by providing both an effectively decidable syntactic restriction and a more general semantic criterion, which guarantee a unique result of evaluation.

We envision future Sensor Networks (SNs) that will be composed of a hybrid collection of a variety of sensing devices embedded into shared environments. In such environments it follows that the embedded SN infrastructure would also be shared by various users, occupants, or administrators of these shared spaces. As such a clear need emerges to virtualize the SN, sharing the resources of the SN across various tasks executing simultaneously. To achieve this goal, we present the snBench (SN Workbench). The snBench abstracts a collection of dissimilar and disjoint resources into a shared virtual SN. The snBench provides an accessible high-level programming language that enables users to write "macro-level" program for their own virtual SN (i.e., programs are written at the scope of the SN rather than its individual components and specific details of the components or deployment need not be specified by the developer). To this end snBench provides execution environments and a run-time support infrastructure to provide each user a Virtual Sensor Network characterized by efficient automated program deployment, resource management, and a truly extensible architecture. In this paper we present an overview of the snBench, detailing its salient functionalities that support the entire life-cycle of a SN application.

The heterogeneity and open nature of network systems make analysis of compositions of components quite challenging, making the design and implementation of robust network services largely inaccessible to the average programmer. We propose the development of a novel type system and practical type spaces which reflect simplified representations of the results and conclusions which can be derived from complex compositional theories in more accessible ways, essentially allowing the system architect or programmer to be exposed only to the inputs and output of compositional analysis without having to be familiar with the ins and outs of its internals. Toward this end, we present the TRAFFIC (typed representation and analysis of flows for interoperability checks) framework, a simple flow-composition and typing language with corresponding type system. We then discuss and demonstrate the expressive power of a type space for TRAFFIC derived from the network calculus, allowing us to reason about and infer such properties as data arrival, transit, and loss rates in large composite network applications

Documentation of the HTTP protocol includes precise descriptions of the syntax of the protocol, but lacks similarly precise specification of the semantics of messages and message bodies. Semantics are stated in English prose; while this makes the document more intuitively accessible, it makes any sort of formal claims of correctness or interoperability difficult to derive from the specification itself. We propose "layered types", a formal description of the interpretive semantics of HTTP message bodies based upon the stacked type syntax. This model allows us to formally declare semantics for content-related HTTP headers and offers a precise way of characterizing interoperability between current and future protocol revisions and extensions.

Formal correctness of complex multi-party protocols can be difficult to verify. While models of specific sign constraints, protocols which lend themselves to arbitrarily many compositions of agents -such as the chaining of proxies or the peering of routers- are more difficult to verify because they represent potentially infinite state spaces and may exhibit emergent behaviors which may not materialize under particular fixed compositions. We address this challenge by developing an algebraic approach that enables us to reduce arbitrary compositions of network agents into a behaviorally-equivalent (with respect to some correctness property) compact, conical representation, which is amenable to mechanical verification. Our approach consists of an algebra and a set of property-preserving rewrite rules for the canonical homomorphic abstraction of infinite network protocol composition (CHAIN). Using CHAIN, an expression over our algebra (i.e., a set of configurations of network protocol agents) can be reduced to another behaviorally-equivalent expression (i.e., a smaller set of configurations). Repeated applications of such rewrite rules produce a canonical expression which can be checked mechanically. We demonstrate our approach by characterizing deadlock-prone configurations of HTTP agents, as well as establishing useful properties of an overlay protocol for scheduling MPEG frames, and of a protocol for Web intracache consistency.

We embed the standard λ-calculus, denoted ∧, into two larger λ-calculi, denoted ∧∧ and &∧∧. The standard notion of β-reduction for ∧ corresponds to two new notions of reduction, β∧ for ∧∧ and &β∧ for &∧∧. A distinctive feature of our new calculus ∧∧ (resp., &∧∧) is that, in every function application, an argument is used at most once (resp. exactly once) in the body of the function). We establish various connections between the three notions of reduction, β, β∧ and &β∧. As a consequence, we provide an alternative framework to study the relationship between β-weak normalization and β-strong normalization, and give a new proof of the oft-mentioned equivalence between β-strong normalization of standard λ-terms and typability in a system of 'intersection types'.

We investigate finite-rank intersection type systems, analyzing the complexity of their type inference problems and their relation to the problem of recognizing semantically equivalent terms. Intersection types allow something of type τ1 Λ τ2 to be used in some places at type τ1 and in other places at type τ2. A finite-rank intersection type system bounds how deeply the Λ can appear in type expressions. Such type systems enjoy strong normalization, subject reduction, and computable type inference, and they support a pragmatics for implementing parametric polymorphism. As a consequence, they provide a conceptually simple and tractable alternative to the impredicative polymorphism of System F and its extensions, while typing many more programs than the Hindley-Milner type system found in ML and Haskell.While type inference is computable at every rank, we show that its complexity grows exponentially as rank increases. Let K(0, n) = n and K(t + 1, n) = 2K(t,n); we prove that recognizing the pure λ-terms of size n that are typable at rank k is complete for DTIME[K(k−1, n)]. We then consider the problem of deciding whether two λ-terms typable at rank k have the same normal form, generalizing a well-known result of Statman from simple types to finite-rank intersection types. We show that the equivalence problem is DTIME[K(K(k − 1, n), 2)]-complete. This relationship between the complexity of typability and expressiveness is identical in wellknown decidable type systems such as simple types and Hindley-Milner types, but seems to fail for System F and its generalizations. The correspondence gives rise to a conjecture that if Τ is a predicative type system where typability has complexity t(n) and expressiveness has complexity e(n), then t(n) = Ω(log* e(n)).

We consider type systems that combine universal types, recursive types, and object types. We study type inference in these systems under a rank restriction, following Leivant's notion of rank. To motivate our work, we present several examples showing how our systems can be used to type programs encountered in practice. We show that type inference in the rank-k system is decidable for k/spl les/2 and undecidable for k/spl ges/3. (Similar results based on different techniques are known to hold for System F, without recursive types and object types.) Our undecidability result is obtained by a reduction from a particular adaptation (which we call "regular") of the semi-unification problem and whose undecidability is, interestingly, obtained by methods totally different from those used in the case of standard (or finite) semi-unification.

Principality of typings is the property that for each typable term, there is a typing from which all other typings are obtained via some set of operations. Type inference is the problem of finding a typing for a given term, if possible. We define an intersection type system which has principal typings and types exactly the strongly normalizable α-terms. More interestingly, every finite-rank restriction of this system (using Leivant's first notion of rank) has principal typings and also has decidable type inference. This is in contrast to System F where the finite rank restriction for every finite rank at 3 and above has neither principal typings nor decidable type inference. This is also in contrast to earlier presentations of intersection types where the status (decidable or undecidable) of these properties is unknown for the finite-rank restrictions at 3 and above. Furthermore, the notion of principal typings for our system involves only one operation, substitution, rather than several operations (not all substitution-based) as in earlier presentations of principality for intersection types (without rank restrictions). In our system the earlier notion of expansion is integrated in the form of expansion variables, which are subject to substitution as are ordinary variables. A unification-based type inference algorithm is presented using a new form of unification, β-unification.

There are two results in this paper. We first prove that alpha-conversion on types can be eliminated from the second-order λ -calculus F of Girard and Reynolds without affecting the typing power of the system. On the other hand we show that it is impossible to eliminate alpha-conversion on universally quantified variables in the higher-order λ -calculus F ω of Girard, by exhibiting a term which is typable in F ω with alpha-conversion but not typable in F ω without alpha-conversion.

We generalize the pebble game to infinite directed acyclic graphs and use this generalization to give new and shorter proofs of the following well-known results: (1) that unbounded memory increases the power of logics of programs, and (2) that there exists a context-free grammar with infinite index.

Two notions of reduction for terms of the /spl lambda/-calculus are introduced and the question of whether a /spl lambda/-term is /spl beta/-strongly normalizing is reduced to the question of whether a /spl lambda/-term is merely normalizing under one of the notions of reduction. This gives a method to prove strong /spl beta/-normalization for typed /spl lambda/-calculi. Instead of the usual semantic proof style based on Tait's realizability or Girard's "candidats de reductibilite", termination can be proved using a decreasing metric over a well-founded ordering. This proof method is applied to the simply-typed /spl lambda/-calculus and the system of intersection types, giving the first non-semantic proof for a polymorphic extension of the /spl lambda/-calculus.

We carry out an analysis of typability of terms in ML. Our main result is that this problem is DEXPTIME-hard, where by DEXPTIME we mean DTIME(2 n 0(1) ). This, together with the known exponential-time algorithm that solves the problem, yields the DEXPTIME-completeness result. This settles an open problem of P. Kanellakis and J. C. Mitchell. Part of our analysis is an algebraic characterization of ML typability in terms of a restricted form of semi-unification, which we identify as acyclic semi-unification . We prove that ML typability and acyclic semi-unification can be reduced to each other in polynomial time. We believe this result is of independent interest.

We study the problem of type-checking functional programs in three extensions of ML.One distinguishing feature of these extensions is that they allow recursive definitions to be polymorphically typed.Although the motivation for these extensions comes from pragmatic considera-

The prove that the problem of type reconstruction in the polymorphic λ-calculus of rank 2 is polynomial-time equivalent to the problem of type reconstruction in ML, and is therefore DEXPTIME-complete. We also prove that for every k > 2, the problem of type reconstruction in the polymorphic λ-calculus of rank k, extended with suitably chosen constants with types of rank 1, is undecidable.

Finitely typed functional programs are naturally classified by their levels. This syntactic classification of functional programs corresponds to a semantical classification: the higher the level of functional programs, the more functions they can compute. We call FL the language of finitely typed functional programs. The halting problem on finite interpretations is elementary recursive for every FL program, i.e. for every FL program P there is an elementary recursive procedure to decide for every finite interpretation I whether P halts on I. The well-known programming language ML is essentially FL, augmented with the polymorphic let-in constructor. We show that ML computes the same class of functions as FL. As a consequence.

It is proven that the problem of type reconstruction in the polymorphic lambda -calculus of rank two is polynomial-time equivalent to the problem of type reconstruction in ML, and is therefore DEXPTIME-complete. It is also proven that for every k>2, the problem of type reconstruction in the polymorphic lambda -calculus of rank k, extended with suitably chosen constants with types of rank one, is undecidable.>

The Semi-Unification Problem (SUP) is a natural generalization of both first-order unification and matching.The problem arises in various branches of computer science and logic.Although several special cases of SUP are known to be decidable, the problem in general has been open for several years.We show that SUP in general is undecidable, by reducing what we call the "boundedness problem" of Turing machines to SUP.The undecidability of this boundedness problem is established by a technique developed in the mid-1960's to prove related results about Turing machines,

A generalization of first-order unification, called semiunification, is studied with two goals in mind: (1) type-checking functional programs relative to an improved polymorphic type discipline; and (2) deciding the typability of terms in a restricted form of the polymorphic lambda -calculus.>

ML/sup +/ is an extension of the functional language ML that allows the actual parameters of recursively called functions to have types that are generic instances of the (derived) types of corresponding formal parameters. It is shown that the polymorphism allowed by the original ML can be eliminated without loss of computational power, specifically, it is shown that its computational power (in all interpretations) is the same as that of finitely typed functional programs. It is proved that the polymorphism of ML/sup +/ cannot be eliminated, in that its computational power far exceeds that of finitely typed functional programs and therefore that of the original ML too.>

We extend the functional language ML by allowing the recursive calls to a function F on the right-hand side of its definition to be at different types, all generic instances of the (derived) type of F on the left-hand side of its definition. The original definition of ML does not allow this feature. This extension does not produce new types beyond the usual universal polymorphic types of ML and satisfies the properties already enjoyed by ML: the principal-type property and the effective type-assignment property.

It is well known that most questions of interest about the behavior of programs--such as equivalence, halting, optimization, and other problems--are undecidable. On the other hand, it is possible to make some or all of these questions decidable by introducing appropriate restrictions on the programming language under consideration. And once such restrictions are made, the next step is to ask how hard it is to solve these problems for programming languages for which they are decidable.This analysis of programming languages has been undertaken by others, in particular by Jones and Muchnick [4], who choose to restrict their programs to operate over finite memory. Our approach starts from the language of loop-programs, as defined by Meyer and Ritchie [1], in which we in fact allow more general arithmetical operations. Unlike Jones and Muchnick, we do not place any restriction on memory here; instead, we (primarily) restrict our attention to loop-programs without nested loops.