A language for generic programming in the large

Generic programming is an effective methodology for developing reusable software libraries. Many programming languages provide generics and have features for describing interfaces, but none completely support the idioms used in generic programming. To address this need we developed the language G. The central feature of G is the concept, a mechanism for organizing constraints on generics that is inspired by the needs of modern C++ libraries. G provides modular type checking and separate compilation (even of generics). These characteristics support modular software development, especially the smooth integration of independently developed components. In this article we present the rationale for the design of G and demonstrate the expressiveness of G with two case studies: porting the Standard Template Library and the Boost Graph Library from C++ to G. The design of G shares much in common with the concept extension proposed for the next C++ Standard (the authors participated in its design) but there are important differences described in this article.     

PiDuce — A project for experimenting Web services technologies

The PiDuce project comprises a programming language and a distributed runtime environment devised for experimenting Web services technologies by relying on solid theories about process calculi and formal languages for XML documents and schemas.The language features values and datatypes that extend XML documents and schemas with channels, an expressive type system with subtyping, a pattern matching mechanism for deconstructing XML values, and control constructs that are based on Milner’s asynchronous pi calculus. The runtime environment supports the execution of PiDuce processes over networks by relying on state-of-the-art technologies, such as XML schema and WSDL, thus enabling interoperability with existing Web services.We thoroughly describe the PiDuce project: the programming language and its semantics, the architecture of the distributed runtime and its implementation.     

Design and evaluation of C++ open multi-methods

Multiple dispatch-the selection of a function to be invoked based on the dynamic type of two or more arguments-is a solution to several classical problems in object-oriented programming. Open multi-methods generalize multiple dispatch towards open-class extensions, which improve separation of concerns and provisions for retroactive design. We present the rationale, design, implementation, performance, programming guidelines, and experiences of working with a language feature, called open multi-methods, for C++. Our open multi-methods support both repeated and virtual inheritance. Our call resolution rules generalize both virtual function dispatch and overload resolution semantics. After using all information from argument types, these rules can resolve further ambiguities by using covariant return types. Care was taken to integrate open multi-methods with existing C++ language features and rules. We describe a model implementation and compare its performance and space requirements to existing open multi-method extensions and work-around techniques for C++. Compared to these techniques, our approach is simpler to use, catches more user mistakes, and resolves more ambiguities through link-time analysis, is comparable in memory usage, and runs significantly faster. In particular, the runtime cost of calling an open multi-method is constant and less than the cost of a double dispatch (two virtual function calls). Finally, we provide a sketch of a design for open multi-methods in the presence of dynamic loading and linking of libraries.     

Telescoping Languages: A Strategy for Automatic Generation of Scientific Problem-Solving Systems from Annotated Libraries

As machines and programs have become more complex, the process of programming applications that can exploit the power of high-performance systems has become more difficult and correspondingly more labor-intensive. This has substantially widened the software gap—the discrepancy between the need for new software and the aggregate capacity of the workforce to produce it. This problem has been compounded by the slow growth of programming productivity, especially for high-performance programs, over the past two decades. One way to bridge this gap is to make it possible for end users to develop programs in high-level domain-specific programming systems. In the past, a major impediment to the acceptance of such systems has been the poor performance of the resulting applications. To address this problem, we are developing a new compiler-based infrastructure, called TeleGen, that will make it practical to construct efficient domain-specific high-level languages from annotated component libraries. We call these languages telescoping languages, because they can be nested within one another. For programs written in telescoping languages, high performance and reasonable compilation times can be achieved by exhaustively analyzing the component libraries in advance to produce a language processor that recognizes and optimizes library operations as primitives in the language. The key to making this strategy practical is to keep compile times low by generating a custom compiler with extensive built-in knowledge of the underlying libraries. The goal is to achieve compile times that are linearly proportional to the size of the program presented by the user, rather than to the aggregate size of that program plus the base libraries.     

LibVM: an architecture for shared library sandboxing

Many software applications extend their functionality by dynamically loading libraries into their allocated address space. However, shared libraries are also often of unknown provenance and quality and may contain accidental bugs or, in some cases, deliberately malicious code. Most sandboxing techniques that address these issues require recompilation of the libraries using custom tool chains, require significant modifications to the libraries, do not retain the benefits of single address space programming, do not completely isolate guest code, or incur substantial performance overheads. In this paper, we present LibVM, a sandboxing architecture for isolating libraries within a host application without requiring any modifications to the shared libraries themselves, while still retaining the benefits of a single address space and also introducing a system call inter‐positioning layer that allows complete arbitration over a shared library's functionality. We show how to utilize contemporary hardware‐virtualization support towards this end with reasonable performance overheads, and, in the absence of such hardware support, our model can also be implemented using a software‐based mechanism. We ensure that our implementation conforms as closely as possible to existing shared library manipulation functions, minimizing the amount of effort needed to apply such isolation to existing programs. Our experimental results show that it is easy to gain immediate benefits in scenarios where the goal is to guard the host application against unintentional programming errors when using shared libraries, as well as in more complex scenarios, where a shared library is suspected of being actively hostile. In both cases, no changes are required to the shared libraries themselves. Copyright © 2014 John Wiley & Sons, Ltd.     

Asynchronous Stream Processing with S-Net

We present the rationale and design of S-Net, a coordination language for asynchronous stream processing. The language achieves a near-complete separation between the application code, written in any conventional programming language, and the coordination/communication code written in S-Net. Our approach supports a component technology with flexible software reuse. No extension of the conventional language is required. The interface between S-Net and the application code is in terms of one additional library function. The application code is componentised and presented to S-Net as a set of components, called boxes, each encapsulating a single tuple-to-tuple function. Apart from the boxes defined using an external compute language, S-Net features two built-in boxes: one for network housekeeping and one for data-flow style synchronisation. Streaming network composition under S-Net is based on four network combinators, which have both deterministic and nondeterministic versions. Flexible software reuse is comprehensive, with the box interfaces and even the network structure being subject to subtyping. We propose an inheritance mechanism, named flow inheritance, that is specifically geared towards stream processing. The paper summarises the essential language constructs and type concepts and gives a short application example.     

Interfaces for parallel numerical linear algebra libraries in high level languages

In many high performance engineering and scientific applications there is a need to use parallel software libraries. Researchers behind these applications find it difficult to understand the interfaces to these libraries because they carry arguments that are related to the parallel environment and performance in addition to arguments related to the problem at hand. In this paper we introduce the use of high level user interfaces for ScaLAPACK. Concretely, a Python-based interface to ScaLAPACK is proposed. Numerical experiments comparing traditional programming practices with our proposed approach are presented. These experiments evaluate not only the performance of the Python interfaces but also how user friendlier they are, compared to the original calls, and show that PyScaLAPACK does not hinder the performance deliverance of ScaLAPACK. Finally, an example of a real scientific application code, whose functionality can be prototyped or extended with the use of PyScaLAPACK, is presented.     

支持软件重用的程序设计语言

本文提出一种支持软件重用的程序语言并给出了重用描述语言翻译器的工作原理。该语言是在宿主语言Ｃ＋＋中加入“重用描述”成分和“装配语句”而形成的。该文件以软件重用库为依托,重用描述用于表达用户在程序中对部件的要求,重用描述语言翻译器则分析这些需求,自动在库中查找提出部件来适应用户。     

A representation theorem for minmax regret policies

Decision making under uncertainty is one of the central tasks of artificial agents. Due to their simplicity and ease of specification, qualitative decision tools are popular in artificial intelligence. Brafman and Tennenholtz [R.I. Brafman, M. Tennenholtz, An axiomatic treatment of three qualitative decision criteria, J. ACM 47 (3) (2000) 452-482] model an agent's uncertain knowledge as her local state, which consists of states of the world that she deems possible. A policy determines for each local state a total preorder of the set of actions, which represents the agent's preference over these actions. It is known that a policy is maximin representable if and only if it is closed under unions and satisfies a certain acyclicity condition.In this paper we show that the above conditions, although necessary, are insufficient for minmax regret and competitive ratio policies. A complete characterization of these policies is obtained by introducing the best-equally strictness.     

Multi-engine Horn Clause Prolog

We extend Horn Clause Prolog with two new primitives, new_engine (+Goal, +Answer, -Engine) and new_answer(+Engine, -Answer) for creating and exploring answer spaces of multiple interpreters (engines). We show that despite its ontological parsimony, the resulting language is comparable in practical expressiveness with conventional full Prolog, by allowing compact definitions for negation, if-then-else, all solution predicates, I/O and reflective meta-interpreters. While not really needed anymore as a workaround for the lack of expressiveness of pure Prolog, a form of dynamic database operations can be emulated as well, using the state of multiple engines. With multiple engines laying the foundation for multi-threaded execution models of logic programming languages, the surprising result that a minimal extension of Horn Clauses (with LD resolution) in fact bridges the gap to full Prolog, is significant as a basis for lightweight implementations of embedabble logic programming components. Our constructs have been used in the design of small footprint mobile code interpreters for a commercial multi-threaded agent programming language - Jinni - available from http://www.binnetcorp.com/Jinni”.     

Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.     

Reo + mCRL2 : A framework for model-checking dataflow in service compositions

The paradigm of service-oriented computing revolutionized the field of software engineering. According to this paradigm, new systems are composed of existing stand-alone services to support complex cross-organizational business processes. Correct communication of these services is not possible without a proper coordination mechanism. The Reo coordination language is a channel-based modeling language that introduces various types of channels and their composition rules. By composing Reo channels, one can specify Reo connectors that realize arbitrary complex behavioral protocols. Several formalisms have been introduced to give semantics to Reo. In their most basic form, they reflect service synchronization and dataflow constraints imposed by connectors. To ensure that the composed system behaves as intended, we need a wide range of automated verification tools to assist service composition designers. In this paper, we present our framework for the verification of Reo using the mCRL2{{\tt mCRL2}} toolset. We unify our previous work on mapping various semantic models for Reo, namely, constraint automata, timed constraint automata, coloring semantics and the newly developed action constraint automata, to the process algebraic specification language of mCRL2{{\tt mCRL2}}, address the correctness of this mapping, discuss tool support, and present a detailed example that illustrates the use of Reo empowered with mCRL2{{\tt mCRL2}} for the analysis of dataflow in service-based process models.     

Model-checking software library API usage rules

Modern software increasingly relies on using third-party libraries which are accessed via application programming interfaces (APIs). Libraries usually impose constraints on how API functions can be used (API usage rules) and programmers have to obey these API usage rules. However, API usage rules often are not well documented or documented informally. In this work, we show how to use the SCTPL and SLTPL logics to precisely and formally specify API usage rules in libraries, where SCTPL/SLTPL can be seen as an extension of the branching/linear temporal logic CTL/LTL with variables, quantifiers and predicates over the stack. This allows library providers to formally describe API usage rules without knowing how their libraries will be used by programmers. We propose an automated approach to check whether programs using libraries violate API usage rules or not. Our approach consists in modeling programs as pushdown systems (PDSs) and checking API usage rules by SCTPL/SLTPL model-checking for PDSs. To make the model-checking procedure more efficient and precise, we propose an abstraction that reduces drastically the size of the program model and integrate may-alias analysis into our approach to reduce false alarms. Moreover, we characterize two sublogics rSCTPL and rSLTPL of SCTPL and SLTPL that are preserved by the abstraction. We implement our techniques in a tool and apply the tool to check several open-source programs. Our tool finds several previously unknown bugs in several programs. The may-alias analysis avoids most of the false alarms that occur using SCTPL or SLTPL model-checking techniques without may-alias analysis.     

基于C共享库的MATLAB与Visual C#混合编程

MATLAB具有很强的数值计算能力,而Visual C#具有强大的图形用户界面的开发能力,两者的互补结合可以快速和高效地开发专业计算软件。为此,以实例的方式展示了由MATLAB生成C共享库,并在Visual C#中调用此C共享库来实现两者之间的混合编程。另外,对在Visual C#中调用C共享库时的一些需要注意的问题进行了讨论,并给出了外部程序调用由MATLAB生成的C共享库的一般步骤。实例证明通过C共享库来实现MATLAB与Visual C#混合编程的方法是行之有效的。     

Open-Source Model Checking

We present GMC², a software model checker for GCC, the open-source compiler from the Free Software Foundation (FSF). GMC², which is part of the GMC static-analysis and model-checking tool suite for GCC under development at SUNY Stony Brook, can be seen as an extension of Monte Carlo model checking to the setting of concurrent, procedural programming languages. Monte Carlo model checking is a newly developed technique that utilizes the theory of geometric random variables, statistical hypothesis testing, and random sampling of lassos in Büchi automata to realize a one- sided error, randomized algorithm for LTL model checking. To handle the function call/return mechanisms inherent in procedural languages such as C/C++, the version of Monte Carlo model checking implemented in GMC² is optimized for pushdown-automaton models. Our experimental results demonstrate that this approach yields an efficient and scalable software model checker for GCC.     

On Migrating Threads

Based on the notion of persistent threads in Tycoon (Matthes and Schmidt, 1994), we investigate thread migration as a programming construct for building activity-oriented distributed applications. We first show how a straight-forward extension of a higher-order persistent language can be used to define activities that span multiple (semi-) autonomous nodes in heterogeneous networks. In particular, we discuss the intricate binding issues that arise in systems where threads are first-class language citizens that may access local and remote, mobile and immobile resources.We also describe how our system model can be understood as a promising generalization of the more static architecture of first-order and higher-order distributed object systems. Finally, we give some insight into the implementation of persistent and migrating threads and we explain how to represent bindings to ubiquitous resources present at each node visited by a migrating thread on the network to avoid excessive communication or storage costs.     

STLlint: lifting static checking from languages to libraries

Traditional static checking centers around finding bugs in programs by isolating cases where the language has been used incorrectly. These language‐based checkers do not understand the semantics of software libraries, and therefore cannot be used to detect errors in the use of libraries. In this paper, we introduce STLlint, a program analysis we have implemented for the C++ Standard Template Library and similar, generic software libraries, and we present the general approach that underlies STLlint. We show that static checking of library semantics differs greatly from checking of language semantics, requiring new representations of program behavior and new algorithms. Major challenges include checking the use of generic algorithms, loop analysis for interfaces, and organizing behavioral specifications for extensibility. Copyright © 2005 John Wiley & Sons, Ltd.     

Clifford and Graßmann Hopf algebras via the BIGEBRA package for Maple

Hopf algebraic structures will replace groups and group representations as the leading paradigm in forthcoming times. K-theory, co-homology, entanglement, statistics, representation categories, quantized or twisted structures as well as more geometric topics of invariant theory, e.g., the Graßmann-Cayley bracket algebra, are all covered by the Hopf algebraic framework. The new branch of experimental mathematics allows one to easily enter these fields through direct calculations using symbolic manipulation and computer algebra system (CAS). We discuss problems which were solved when building the BIGEBRA package for Maple and CLIFFORD to handle tensor products, Graßmann and Clifford algebras, coalgebras and Hopf algebras. Recent results showing the usefulness of CAS for investigating new and involved mathematics provide us with examples. An outlook on further developments is given.     

glsim: A general library for numerical simulation

We describe glsim, a C++ library designed to provide routines to perform basic housekeeping tasks common to a very wide range of simulation programs, such as reading simulation parameters or reading and writing self-describing binary files with simulation data. The design also provides a framework to add features to the library while preserving its structure and interfaces.