Hierarchical development of programming languages

The experience in designing large software systems shows that even the definitions of a programming language can be seen as the application of specific implementation and formalization techniques rather than as the result of a «designing art». In this context, a formalism is proposed here as a tool for defining conventional high level programming languages. The formalism is an algebraic model supporting the definition of representational entities such as types. A Type is a set of data and operations on them. An isomorphism between language components and types realizes an isomorphism between the language and its specification on the model. Then, the definition of a language can be performed by stepwise definitions of the types representing the language components. So the model is also a language development tool. Stepwise definition methodologies are also investigated and two are the proposed ones: the horizontal, methodology and the vertical methodology. In particular, the vertical methodology defines languages by the development of a hierarchy of abstraction levels, each corresponding to one class of languages: The last class only contains the language being defined.     

On function languages and parallel computers

This paper is a discussion of functional languages and parallel computers. It is aimed at an audience that has a background in computer architecture, but not necessarily in the area of functional languages. It therefore constitutes an introductory survey of functional languages, on the one hand, and a non-introductory discussion of parallel computers, on the other. The aim is to highlight some important issues regarding the use of adequacy of these languages and also on the design of parallel computers to interpret them. The concluding thesis of put forth is twofold: one, that to widen their scope of applicability, functional languages need to include more features of nondeterminism and may need to be integrated with features from conventional languages; two, that the right sort of architectures for such extended languages may well be less-specialised ones with a von Neumann flavour.     

Surface tree languages and parallel derivation trees

The surface tree languages obtained by top-down finite state transformation of monadic trees are exactly the frontier-preserving homomorphic images of sets of derivation trees of ETOL systems. The corresponding class of tree transformation languages is therefore equal to the class of ETOL languages.     

Generative languages,codes and parallel processing

A special class of context-sensitive generative languages (CSGLs) that can be used as an indexation in parallel computing is described. The languages are recursively generated, and the algorithm for interprocesses communication is based on the positive resolution of the post correspondence problem (PCP) within CSGLs. This fact follows from the main result that a constructed CSGL has a complete set of production rules, i.e. no new rule can be added to the set without destroying the integrity of the CSGL.     

Subword complexities of various classes of deterministic developmental languages with interactions

Lee has shown that ifL is aDOL language, then ink(L) <C · k² for some constantC, where ink(L) denotes the number of subwords of lengthk inL. We show that the result does not hold forDIL languages. It is also shown that each everywhere growing (uniform)DIL language is the image under a coding of an everywhere growing (uniform)DOL language. A similar result holds for languages generated by systems with tables. These enable us to solve the subword complexity problems for developmental languages with interactions.This paper is based on part of K.P.L.'s Ph.D. thesis.     

Design issues in parallel simulation languages

The authors address several key issues in designing languages for parallel discrete-event simulation and survey the state-of-the-art techniques aimed at solving these problems. Attention is given to issues that are specific to parallel simulation, e.g., the parallel synchronization schemes, or issues that have not previously been a problem for sequential simulation, e.g., termination. Various specialized PSLs (parallel simulation languages) may also have quite different design issues. The problem of achieving transparency is addressed. In particular it is observed that a major difficulty in achieving the design criteria is the overhead introduced by the methods for solving the problems considered. In some cases making the design criteria less constrained appears to be unavoidable. The authors also propose several useful high-level language constructs to facilitate modeling in order to have the simulation system deal with the low-level details transparently. They show that extending the capability of an existing programming language is the simplest available technique for designing a PSL     

Decomposition abstraction in parallel rule languages

Decomposition abstraction is the process of organizing and specifying decomposition strategies for the exploitation of parallelism available in an application. In this paper we develop and evaluate declarative primitives for rule-based programs that expand opportunities for parallel execution. These primitives make explicit, implicit relations among the data and similarly among the rules. The semantics of the primitives are presented in a general object-based framework such that they may be applied to most rule-based programming languages. We show how the additional information provided by the decomposition primitives can be incorporated into a semantic-based dependency analysis technique. The resulting analysis reveals parallelism at compile time that is very difficult, if not impossible, to discover by traditional syntactic analysis techniques. Simulation results demonstrate scalable and broadly available parallelism     

A remark on regularity of parallel languages

It is shown to be decidable of any given regular language R and FTOL language L, whether or not R = L     

Compile-time granularity analysis for parallel logic programming languages

The paper describes a simple compiler analysis method for determining the “weight” of procedures in parallel logic programming languages. Using Flat Guarded Horn Clauses (FGHC) as an example, the analysis algorithm is described. Consideration of weights has been incorporated in the scheduler of a real-parallel FGHC emulator running on the Sequent Symmetry multiprocessor. Alternative demand-distribution methods are discussed, includingoldest-first andheaviest-first distributions. Performance measurements, collected from a group of non-trivial benchmarks on eight processors, show that the new schemes donot perform significantly faster than conventional distribution methods. This result is attributed to a combination of factors overshadowing the benefits of the new method: high system overheads, the low cost of spawning a goal on a shared memory multiprocessor, and the increase in synchronization caused by the new methods. Directions of further research are discussed, indicating where further speedup can be attained.     

Hierarchical structures of optimization packages

Conclusions The expanding operational potential of application packages (interactive and multiprocessing disciplines, application in systems with complex environment, processing of large volumes of data) necessitated a transition from the one-level to a hierarchical package model, in line with the increasing complexity of the package structure.Not all the levels are necessarily present in the design of specific packages. For example, packages executing in the batch mode without multiprocessing and user-initiated dialog do not need the process synchronization level, whereas the top level-the process level-is realized by a single process (in the operating system sense) with the structure described in [1–3]. Packages whose programs always fit into the main memory do not need the data management level, i.e., the cluster is realized by an abstract application module. The application program level is missing in those packages where the application programs are prepared in advance, rather than being generated in run time.The proposed structure is not restricted to optimization packages: it may be used to typify other classes of method-oriented packages. Structure-driven package design ensures that the package has the required properties, makes it possible to implement the software-engineering approach to the design process, avoids gross design errors, and simplifies package adaptation to different environments. Moreover, the hierarchical package structure allows a more technological approach to the development process, as it leads to more effective application of the methods of hierarchical, modular, and structured programming.Translated from Kibernetika, No. 2, pp. 35–39, March–April, 1982.     

Efficient handling of data structures in definitional languages

Implementations of operations on general data structures in definitional languages often lead to excessive copying and storage requirements. To partially overcome this problem, users are given facilities to select efficient storage structures or to guide storage allocation. This contradicts the spirit of definitional languages, requiring the user to get involved with implementation details.

This paper presents a method for automatically recognizing excessive copying and optimizing the storage for data structures. Based on analysis of data dependencies, the storage may be reduced from an entire structure to individual elements of the structure. The benefits are especially significant in incremental structures, where only a constant number of elements of a large data structure is modified in each operation. For incremental structures, copying of unchanged parts of the structure is avoided, and unnecessary iterations are eliminated, without involving the user in this consideration. The user is thus relieved of considering the inefficiencies inherent in specifications in definitional languages. The method is applicable to a variety of language processors and computer architectures. The proposed optimization method produces better results than those obtained by explicit storage references.

The paper describes the implementation of the method in the compiler of the MODEL definitional language. First, criteria are presented for recognizing structures that may be optimized. Then, a transformation that removes iterations implied by the operations on incremental structures is described. The method is exemplified by its application to the non-recursive iteration computation of the Ackermann's function.     

Do parallel languages respond to the needs of scientificprogrammers?

Parallel programming is considered from the viewpoint of scientific researchers, with particular reference to their requirements for language support. The questions of how scientists go about developing parallel applications, what role language plays in determining the success of their programming efforts, how much scientific programmers should be expected to know about parallel languages and machines and what computer scientists can do to facilitate parallel scientific programming are addressed. The discussion centers on the `mainline' supercomputers for scientific and engineering applications: vector and scalar MIMD (multiple instruction, multiple data) multiprocessors. New research efforts that are tackling the problems facing scientific programmers are discussed     

Hierarchical growing cell structures: TreeGCS

We propose a hierarchical clustering algorithm (TreeGCS) based upon the Growing Cell Structure (GCS) neural network of B. Fritzke (1993). Our algorithm refines and builds upon the GCS base, overcoming an inconsistency in the original GCS algorithm, where the network topology is susceptible to the ordering of the input vectors. Our algorithm is unsupervised, flexible, and dynamic and we have imposed no additional parameters on the underlying GCS algorithm. Our ultimate aim is a hierarchical clustering neural network that is both consistent and stable and identifies the innate hierarchical structure present in vector-based data. We demonstrate improved stability of the GCS foundation and evaluate our algorithm against the hierarchy generated by an ascendant hierarchical clustering dendogram. Our approach emulates the hierarchical clustering of the dendogram. It demonstrates the importance of the parameter settings for GCS and how they affect the stability of the clustering     

Hierarchical interface-based supervisory control-part II: parallel case

In this paper, we present a hierarchical method that decomposes a discrete-event system (DES) into a high-level subsystem which communicates with n/spl ges/1 parallel low-level subsystems, through separate interfaces which restrict the interaction of the subsystems. It is a generalization of the serial case (n=1) described in Part I of this paper, where we define an interface and a set of interface consistency properties that can be used to verify if a DES is nonblocking and controllable. Each clause of the definition can be verified using a single subsystem; thus the complete system model never needs to be stored in memory, offering potentially significant savings in computational resources. We provide algorithms for verifying these new properties, and briefly discuss the computational complexity of the method. Finally, we present an application to a large manufacturing example with an estimated worst-case closed-loop state-space size of 2.9/spl times/10/sup 21/.