Dispel: A run-time debugging language

Dispel is a language designed to aid communication between an interactive user and a run-time, symbolic debugging system. Important attributes of Dispel are that it provides a small set of primitive debugging actions, most traditional debugging aids (such as variable traces and postmortem dumps) are written in terms of these primitives as debugging routines, and Dispel serves both as an interactive debugging command language and as a special-purpose programming language. The syntax and semantics of Dispel are explained and examples of Dispel commands and routines are presented.     

rbFeatures: Feature-oriented programming with Ruby

Features are pieces of core functionality of a program that is relevant to particular stakeholders. Features pose dependencies and constraints among each other. These dependencies and constraints describe the possible number of variants of the program: A valid feature configuration generates a specific variant with unique behavior. Feature-Oriented Programming is used to implement features as program units. This paper introduces rbFeatures, a feature-oriented programming language implemented on top of the dynamic programming language Ruby. With rbFeatures, programmers use software product lines, variants, and features as first-class entities. This allows several runtime reflection and modification capabilities, including the extension of the product line with new features and the provision of multiple variants. The paper gives a broad overview to the implementation and application of rbFeatures. We explain how features as first-class entities are designed and implemented, and discuss how the semantics of features are carefully added to Ruby programs. We show two case studies: The expression product line, a common example in feature-oriented programming, and a web application.     

A type-safe embedding of SQL into Java using the extensible compiler framework J%

J% is an extension of the Java programming language that efficiently supports the integration of domain-specific languages. In particular, J% allows the embedding of domain-specific language code into Java programs in a syntax-checked and type-safe manner. This paper presents J%׳s support for the sql language. J% checks the syntax and semantics of sql statements at compile-time. It supports query validation against a database schema or through execution to a live database server. The J% compiler generates code that uses standard jdbc api calls, enhancing runtime efficiency and security against sql injection attacks.     

A semantic view of ALGOL 68

This article presents a semantic view of the programming language ALGOL 68 [1]. The presentation emphasizes those elements of the language which form the basis for viewing an ALGOL 68 program as a composite expression, built-up through embedded expression layers. It is intended to give a glimpse of the semantic issues present in ALGOL 68 rather than a tutorial or general introduction. This discussion of the language defined by the Revised Report follows the treatment given by Branquart, Lewi, Sintzoff and Wodon [2] for the language defined by the original Report [3].     

Unary finite automata vs. arithmetic progressions

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.     

Programming Languages in Economics

Young economists sometimes ask which computer programming languages they should learn. This paper answers that question by suggesting that they begin with a high level language like GAUSS, GAMS, Mathematica, Maple or MATLAB depending on their field of specialization in economics. Then they should work down to one of the low level languages such as Fortran, Basic, C, C++ or Java depending on the planned areas of application. Finally, they should proceed to the languages which are used to develop graphical interfaces and internet applications, viz. Visual Basic, C, C++ or Java.     

A comparison of programming languages for software engineering

Four programming languages (Fortran, Cobol, Jovial and the proposed DoD standard) are compared in the light of modern ideas of good software engineering practice. The comparison begins by identifying a core for each language that captures the essential properties of the language and the intent of the language designers. These core languages then serve as a basis for the discussion of the language philosophies and the impact of the language on gross program organization and on the use of individual statements.     

Case studies in asynchronous data parallelism

Is the owner-computes style of parallelism, captured in a variety of data parallel languages, attractive as a paradigm for designing explicit control parallel codes? This question gives rise to a number of others. Will such use be unwieldy? Will the resulting code run well? What can such an approach offer beyond merely replicating, in a more labor intensive way, the services and coverage of data parallel languages? We investigate these questions via a simple example and “real world” case studies developed using C-Linda, a language for explicit parallel programming formed by the merger of C with the Linda coordination language. The results demonstrate owner-computes is an effective design strategy in Linda.     

Improving workflow modularity using a concern-specific layer on top of Unify

Workflows are a popular means of automating processes in many domains, ranging from high-level business process modeling to lower-level web service orchestration. However, state-of-the-art workflow languages offer a limited set of modularization mechanisms. This results in monolithic workflow specifications, in which different concerns are scattered across the workflow and tangled with one another. This hinders the design, evolution, and reusability of workflows expressed in these languages. We address this problem through the Unify framework. This framework enables uniform modularization of workflows by supporting the specification of all workflow concerns – including crosscutting ones – in isolation of each other. These independently specified workflow concerns are connected to each other using workflow-specific connectors. In order to further facilitate the development of workflows, we enable the definition of concern-specific languages (CSLs) on top of the Unify framework. A CSL facilitates the expression of a family of workflow concerns by offering abstractions that map well to the concerns' domain. Thus, domain experts can add concerns to a workflow using concern-specific language constructs. We exemplify the specification of a workflow in Unify, and show the definition and application of two concern-specific languages built on top of Unify.     

Equality sets of prefix morphisms and regular star languages

We consider equality sets of prefix morphisms, that is, sets E(g₁,g₂)={w|g₁(w)=g₂(w)}, where g₁ and g₂ are prefix morphisms. Recall that a morphism g is prefix if, for all different letters a and b, g(a) is not a prefix of g(b). We prove a rather surprising equality on families of languages, namely, that the family of regular star languages coincides with the family of languages of form πA(E(g₁,g₂)) for some prefix morphisms g₁ and g₂, and a projection πA which deletes the letters not in A.     

Semiotic perspectives on interactive languages for life on the screen

Cross-disciplinary research involving semiotics and computer science is rare. With the Web 2.0, contemporary activities of users can be properly described as real ‘life on the screen’. One of the challenges for the design of interactive languages is to support these activities and to express the much wider variety of meanings that users want to exchange through and with software. As the discipline whose aim is to investigate meanings, through representation and interpretation processes, semiotics is remarkably well-positioned to contribute with new knowledge in our field. This viewpoint article examines the reasons why in spite of this positioning, semiotics remains unpopular among researchers interested in interactive computer languages. In particular, it proposes that a semiotic approach can help us think about computer languages to represent our individual and collective ‘selves’ on the screen.     

The Evaluation Dependence Tree as a Basis for Lazy Functional Debugging

Lazy functional languages are declarative and allow the programmer to write programs where operational issues such as the evaluation order are left implicit. This should be reflected in the design of debuggers for such languages to avoid burdening the programmer with operational details, e.g. concerning the actual evaluation order. Conventional debugging techniques tend to focus too much on operational aspects to be suitable in this context. A record of the execution that only captures the declarative aspects of the execution, leaving out operational details, would be a viable basis for debugging lazy functional programs. Various declarative debugging tools could then be developed on top of such records. In this paper we propose a structure which we call the Evaluation Dependence Tree (EDT) for this purpose, and we describe two different construction methods. Performance problems are discussed along with possible solutions.     

How well does a vanilla loop fit into a frame?

The frame language FRL is compared with some newer object-oriented languages, namely LOOPS, the Flavor System and the Poor Man's Flavor System. The kernel features are investigated in detail and a simulation of FRL in the Flavor System is performed. The conclusion is that in general the object-oriented languages cannot be easily utilized as a substitute for FRL frames because of the different view these languages have of objects, but there are important special cases where object-oriented languages are very similar to FRL.     

Carla: A rule language for specifying communications architectures

Due to the unique requirements of a series of projects to specify communications architectures using graphical representations (Cara and MFD), we have developed the communications-oriented rule-based language Carla (Cara Rule Language), which provides an executable specification of the architecture being developed. Carla is designed to provide the ability to specify and simulate high-level, possibly incomplete, specifications of communications architectures, and to allow the developer to refine the specification through the addition of behavior-describing rules. Carla is also well-suited to creating black-box specifications of any system whose behavior depends on input/output history. We describe the features of the language, discuss various design issues, and provide examples of various communications protocols specified in Carla.     

A counterexample to a conjecture concerning concatenation hierarchies

We give a counterexample to the conjecture which was originally formulated by Straubing in 1986 concerning a certain algebraic characterization of regular languages of level 2 in the Straubing-Thérien concatenation hierarchy of star-free languages.     

Generalizing input-driven languages: Theoretical and practical benefits

Regular languages (RL) are the simplest family in Chomsky’s hierarchy. Thanks to their simplicity they enjoy various nice algebraic and logic properties that have been successfully exploited in many application fields. Practically all of their related problems are decidable, so that they support automatic verification algorithms. Also, they can be recognized in real-time.Context-free languages (CFL) are another major family well-suited to formalize programming, natural, and many other classes of languages; their increased generative power w.r.t. RL, however, causes the loss of several closure properties and of the decidability of important problems; furthermore they need complex parsing algorithms. Thus, various subclasses thereof have been defined with different goals, spanning from efficient, deterministic parsing to closure properties, logic characterization and automatic verification techniques.Among CFL subclasses, so-called structured ones, i.e., those where the typical tree-structure is visible in the sentences, exhibit many of the algebraic and logic properties of RL, whereas deterministic CFL have been thoroughly exploited in compiler construction and other application fields.After surveying and comparing the main properties of those various language families, we go back to operator precedence languages (OPL), an old family through which R. Floyd pioneered deterministic parsing, and we show that they offer unexpected properties in two fields so far investigated in totally independent ways: they enable parsing parallelization in a more effective way than traditional sequential parsers, and exhibit the same algebraic and logic properties so far obtained only for less expressive language families.     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.