Coding rules are customarily used to constrain the use (or abuse) of certain constructions in a programming language. Standard coding rule sets exist that target different languages and application domains. However, these rules are usually written using a natural language, which is intrinsically ambiguous, and which may hinder their automatic application. This short paper presents some early work aiming at defining a framework to formalise and check for coding rule conformance using logic programming. We show how a certain class of rules -- structural rules -- can be reformulated as logic programs. Some real examples, including Prolog code formalising them, are shown and discussed.
We present a model checker for verifying distributed programs written in the Erlang programming language. Providing a model checker for Erlang is especially rewarding since the language is by now being seen as a very capable platform for developing industrial strength distributed applications with excellent failure tolerance characteristics. In contrast to most other Erlang verification attempts, we provide support for a very substantial part of the language. The model checker has full Erlang data type support, support for general process communication, node semantics (inter-process behave subtly different from intra-process communication), fault detection and fault tolerance through process linking, and can verify programs written using the OTP Erlang component library (used by most modern Erlang programs). As the model checking tool is itself implemented in Erlang we benefit from the advantages that a (dynamically typed) functional programming language offers: easy prototyping and experimentation with new verification algorithms, rich executable models that use complex data structures directly programmed in Erlang, the ability to treat executable models interchangeably as programs (to be executed directly by the Erlang interpreter) and data, and not least the possibility to cleanly structure and to cleanly combine various verification sub-tasks. In the paper we discuss the design of the tool and provide early indications on its performance.
In order to formally reason about distributed Erlang systems, it is necessary to have a formal semantics. In a previous paper we have proposed such a semantics for distributed Erlang. However, recent work with a model checker for Erlang revealed that the previous attempt was not good enough. In this paper we present a more accurate semantics includes several modifications and additions to the semantics for distributed Erlang proposed by Claesson and Svensson in 2005, which in turn is an extension to Fredlund's formal single-node semantics for Erlang. The most distinct addition to the previous semantics is the possibility to correctly model disconnected nodes.
We investigate the distributed part of the Erlang programming language, with an aim to develop robust distributed systems and algorithms running on top of Erlang runtime systems. Although the step to convert an application running on a single node to a fully distributed (multi-node) application is deceptively simple (changing calls to spawn so that processes are spawned on different nodes), there are some corner cases in the Erlang language and API where the introduction of distribution can cause problems. In this paper we discuss a number of such pitfalls, where the semantics of communicating processes differs significantly depending if the processes reside on the same node or not, we also provide some guidelines for safe programming of distributed systems.
Proceedings of the 2007 ACM SIGPLAN Erlang Workshop.
A parametric algebraic data type is a functor when we can apply a function to its data components while satisfying certain equations. We investigate whether parametric abstract data types can be functors. We provide a general definition for their map operation that needs only satisfy one equation. The definability of this map depends on properties of interfaces and is a sufficient condition for functoriality. Instances of the definition for particular abstract types can then be constructed using their axiomatic semantics. The definition and the equation can be adapted to determine, necessarily and sufficiently, whether an ADT is a functor for a given implementation
Coding rules are customarily used to constrain the use (or abuse) of certain constructions in a programming language. Standard coding rule sets exist that target different languages and application domains. However, these rules are usually written using a natural language, which is intrinsically ambiguous, and which may hinder their automatic application. This short paper presents some early work aiming at defining a framework to formalise and check for coding rule conformance using logic programming. We show how a certain class of rules -- structural rules -- can be reformulated as logic programs. Some real examples, including Prolog code formalising them, are shown and discussed.
This short paper presents some early work in the context of an European project aiming at defining a framework to formalise and check for coding rule conformance using logic programming. We show how a certain class of rules -- structural rules -- can be reformulated as logic programs. This provides both a framework for formal specification and also for automatic conformance checking using a Prolog engine.
A parametric algebraic data type is a functor when we can apply a function to its data components while satisfying certain equations. We investigate whether parametric abstract data types can be functors. We provide a general definition for their map operation that needs only satisfy one equation. The definability of this map depends on properties of interfaces and is a sufficient condition for functoriality. Instances of the definition for particular abstract types can then be constructed using their axiomatic semantics. The definition and the equation can be adapted to determine, necessarily and sufficiently, whether an ADT is a functor for a given implementation
The main main subject of the chapter is how design patterns can be described as class operations. Additionally, we describe two possible applications: how to reason about design patterns, and how a design can be automatically refactored using design patterns.
The article describes a method to obtain performance measurements from complex distributed systems using a model checking approach. We illustrate the approach by applying it to a video-on-demand application developed in Erlang. To obtain performance measurements concerning e.g. streaming capacity, and identify system bottlenecks, we used the McErlang model checker which implements a large part of the Erlang API. Answers to capacity queries are computed as measures over paths in the system state graph, and the combination of an on-the-fly model checker (not requiring the generation of the complete state graph) with a powerful language (Erlang itself) for expressing correctness claims, made it possible to analyse substantially sized systems.
In this paper we introduce Fresh Logic, a natural deduction style first-order logic extended with term-formers and quantifiers derived from the FM-sets model of names and binding in abstract syntax. Fresh Logic can be classical or intuitionistic depending on whether we include a law of excluded middle; we present a proof-normalisation procedure for the intuitionistic case and a semantics based on Kripke models in FM-sets for which it is sound and complete.
We introduce FMG (Fraenkel-Mostowski Generalised) set theory, a generalisation of FM set theory which allows binding of infinitely many names instead of just finitely many names. We apply this generalisation to show how three presentations of syntax--de Bruijn indices, FM sets, and name-carrying syntax--have a relation generalising to all sets and not only sets of syntax trees. We also give syntax-free accounts of Barendregt representatives, scope extrusion, and other phenomena associated to α-equivalence. Our presentation uses a novel presentation based not on a theory but on a concrete model U.
Nominal rewriting is based on the observation that if we add support for α-equivalence to first-order syntax using the nominal-set approach, then systems with binding, including higher-order reduction schemes such as λ-calculus beta-reduction, can be smoothly represented. Nominal rewriting maintains a strict distinction between variables of the object-language (atoms) and of the meta-language (variables or unknowns). Atoms may be bound by a special abstraction operation, but variables cannot be bound, giving the framework a pronounced first-order character, since substitution of terms for variables is not capture-avoiding. We show how good properties of first-order rewriting survive the extension, by giving an efficient rewriting algorithm, a critical pair lemma, and a confluence theorem for orthogonal systems.
Nominal rewriting introduced a novel method of specifying rewriting on syntax-with-binding. We extend this treatment of rewriting with hierarchy of variables representing increasingly 'meta-level' variables, e.g. in hierarchical nominal term rewriting the meta-level unknowns (representing unknown terms) in a rewrite rule can be 'folded into' the syntax itself (and rewritten). To the extent that rewriting is a mathematical meta-framework for logic and computation, and nominal rewriting is a framework with native support for binders, hierarchical nominal term rewriting is a meta-to-the-omega level framework for logic and computation with binders.
In informal mathematical usage we often reason using languages with binding. We usually find ourselves placing capture-avoidance constraints on where variables can and cannot occur free. We describe a logical derivation system which allows a direct formalisation of such assertions, along with a direct formalisation of their constraints. We base our logic on equality, probably the simplest available judgement form. In spite of this, we can axiomatise systems of logic and computation such as first-order logic or the lambda-calculus in a very direct and natural way. We investigate the theory of derivations, prove a suitable semantics sound and complete, and discuss existing and future research.
We describe the introduction of disequality constraints over algebraic data terms in the functional logic language Curry, and their implementation in Sloth, our Curry compiler. This addition extends the standard definition of Curry in several ways. On one hand, we provide a disequality counterpart to the constraint equality operator (=:=). Secondly, boolean equality operators are also redefined to cope with constructive disequality information, which leads to a more symmetric design w.r.t. the existing one. Semantically speaking, our implementation is very similar to previous proposals, although there are some novel aspects. One of them is that the implementation is partly based on an existing finite domain (FD) constraint solver, which provides a more efficient execution in some examples and, more important, the first complete implementation of disequality constraints over finite types. A detailed description of the finite type case is provided, including: (i) the use of the FD solver; (ii) an algorithm for analysing cardinality of types, and (iii) how to deal with cardinality information at run time. Some benchmarks, an operational semantics minimally extending the one in the Curry draft, and a moderately detailed description of the implementation complete the paper.
We present a model checker for verifying distributed programs written in the Erlang programming language. Providing a model checker for Erlang is especially rewarding since the language is by now being seen as a very capable platform for developing industrial strength distributed applications with excellent failure tolerance characteristics. In contrast to most other Erlang verification attempts, we provide support for a very substantial part of the language. The model checker has full Erlang data type support, support for general process communication, node semantics (inter-process behave subtly different from intra-process communication), fault detection and fault tolerance through process linking, and can verify programs written using the OTP Erlang component library (used by most modern Erlang programs). As the model checking tool is itself implemented in Erlang we benefit from the advantages that a (dynamically typed) functional programming language offers: easy prototyping and experimentation with new verification algorithms, rich executable models that use complex data structures directly programmed in Erlang, the ability to treat executable models interchangeably as programs (to be executed directly by the Erlang interpreter) and data, and not least the possibility to cleanly structure and to cleanly combine various verification sub-tasks. In the paper we discuss the design of the tool and provide early indications on its performance.
This file was generated by bibtex2html 1.98.