Register allocation via coloring

Register allocation may be viewed as a graph coloring problem. Each node in the graph stands for a computed quantity that resides in a machine register, and two nodes are connected by an edge if the quantities interfere with each other, that is, if they are simultaneously live at some point in the object program. This approach, though mentioned in the literature, was never implemented before. Preliminary results of an experimental implementation in a PL/I optimizing compiler suggest that global register allocation approaching that of hand-coded assembly language may be attainable.     

An algorithm for constructing Darboux transformations of type I for third-order hyperbolic operators of two variables

Darboux transformations of type I are invertible Darboux transformations with explicit short formulas for inverse transformations. These transformations are invariant with respect to gauge transformations, and, for gauge transformations acting on third-order hyperbolic operators of two variables, a general-form system of generating differential invariants is known. In the paper, first-order Darboux transformations of type I for this class of operators are considered. The corresponding operator orbits are directed graphs with at most three edges originating from each vertex. In the paper, an algorithm for constructing such orbits is suggested. We have derived criteria for existence of first-order Darboux transformations of type I in terms of the generating invariants, formulas for transforming invariants, and the so-called “triangle rule” property of orbits. The corresponding implementation in the LPDO package is described. The orbits are constructed in two different forms, one of which outputs the graph in the format of the well-known built-in Maple package Graph Theory.     

Design and implementation of data abstraction definition facility

This paper describes the Implementation model of a data definition facility for abstract data types, implemented as an extension to PL/1. The facility is based on a modified version of the cluster mechanism for the implementation of types. The proposed version tries to address the issues of efficiency and portability in connection with the goal of systematic programming.     

Formal foundation of consistent EMF model transformations by algebraic graph transformation

Model transformation is one of the key activities in model-driven software development. An increasingly popular technology to define modeling languages is provided by the Eclipse Modeling Framework (EMF). Several EMF model transformation approaches have been developed, focusing on different transformation aspects. To validate model transformations with respect to functional behavior and correctness, a formal foundation is needed. In this paper, we define consistent EMF model transformations as a restricted class of typed graph transformations using node type inheritance. Containment constraints of EMF model transformations are translated to a special kind of graph transformation rules such that their application leads to consistent transformation results only. Thus, consistent EMF model transformations behave like algebraic graph transformations and the rich theory of algebraic graph transformation can be applied to these EMF model transformations to show functional behavior and correctness. Furthermore, we propose parallel graph transformation as a suitable framework for modeling EMF model transformations with multi-object structures. Rules extended by multi-object structures can specify a flexible number of recurring structures. The actual number of recurring structures is dependent on the application context of such a rule. We illustrate our approach by selected refactorings of simplified statechart models. Finally, we discuss the implementation of our concepts in a tool environment for EMF model transformations.     

FOPE：一个面向FORTRAN的程序设计环境

本文介绍一个面向ＦＯＲＴＲＡＮ的程序设计环境ＦＯＰＥ（ＦＯＲＴＲＡＮＯｒｉｅｎｔｅｄＰｒｏｇｒａｍｍｉｎｇＥｎｖｉｒｏｎｍｅｎｔ）。ＦＯＰＥ提供对ＦＯＲＴＲＡＮ程序的静态分析、动态分析、程序变换、ＤＯ循环变换、文档生成等功能，文中详细地介绍了这些功能。ＦＯＰＥ的一个重要特点是可视化。可视化工具有程序调用关系图、过程控制流图和数据依赖图三种，它能做到对程序的静态结构和动态运行过程用图形显示。ＦＯＰＥ环境以Ｘ－Ｗｉｎｄｏｗ为基础，建立了窗口用户界面，大大地方便了使用。     

分布式数据库系统中数据一致性维护方法

讨论了在分布式数据系统中，对于各个数据库副本维护数据一致性的问题，介绍了Oracle8i数据库系统中数据复制的基本概念，基本原理，复制配置以及数据复制的基本配置和实现方法。     

Implementation of a PASCAL compiler for the IBM 360

The implementation of a compiler for a subject of PASCAL on the IBM 360 is reported. Some difficulties encountered using PL/I for the bootstrap are discussed.     

A model-driven engineering framework for embedded systems design

This work presents a Model-Driven Engineering (MDE) framework to improve embedded system design. The framework adopts concepts from MDE for the automatic generation of a control and data flow internal representation, starting from the functional specification of an embedded application described using UML class and sequence diagrams. By means of transformations rules applied on the UML model of the embedded system, an MOF-based (Meta Object Facility is a standard representation for meta-models and models proposed by OMG) internal representation is automatically obtained, which is iteratively mapped into a hardware/software implementation by means of model transformations. This mapping is optimized by a design space exploration (DSE) method based on a categorical graph product. The model transformations have also as input a platform model, which specifies the available hardware, software and interface resources, and produce an implementation model, on which software synthesis, communication synthesis and high-level synthesis algorithms are applied to generate the final implementation. A case study is described to illustrate the application of the framework.     

A schedule of join operations to reduce I/O cost in spatial database systems

In this paper, we propose a graph-based cluster-sequencing method to minimize the I/O cost in spatial join processing. We first define the maximum overlapping (MO) order in a graph, proving that the problem of finding an MO order in a graph is NP-complete. Then, we propose an algorithm to find an approximation to MO order in a graph. We also prove that the approximation to MO order obtained from our method is close to the optimal result. Simulations have been conducted to demonstrate the saving of I/O cost in spatial join by using our method.     

Casting Petri Nets into Programs

A programming system has been implemented in which annotated Petri nets are used as machine-processable high-evel design representations. The nets can be used to express the parallelism and the dynamic sequential dependencies found in complex software. They can then be interactively fired to facilitate debugging of the design. The nets are processed into a procedure language, called XL/1, to which a variety of transformations are applied in order to produce more efficient programs. These programs are generated for either a serial or a parallel processing environment. Finally, the XL/1 programs may be translated into PL/I or PL/S. The serial processing versions have been compiled and run successfully, but the parallel processing versions have not yet been run in a parallel processing environment.     

Declarative RDF graph generation from heterogeneous (semi-)structured data: A systematic literature review

More and more data in various formats are integrated into knowledge graphs. However, there is no overview of existing approaches for generating knowledge graphs from heterogeneous (semi-)structured data, making it difficult to select the right one for a certain use case. To support better decision making, we study the existing approaches for generating knowledge graphs from heterogeneous (semi-)structured data relying on mapping languages. In this paper, we investigated existing mapping languages for schema and data transformations, and corresponding materialization and virtualization systems that generate knowledge graphs. We gather and unify 52 articles regarding knowledge graph generation from heterogeneous (semi-)structured data. We assess 15 characteristics on mapping languages for schema transformations, 5 characteristics for data transformations, and 14 characteristics for systems. Our survey paper provides an overview of the mapping languages and systems proposed the past two decades. Our work paves the way towards a better adoption of knowledge graph generation, as the right mapping language and system can be selected for each use case.     

Transformational design of real-time systems. Part II: From program specifications to programs

In the two parts of this article we present a transformational approach to the design of real-time systems. The overall starting point are requirements formulated in a subset of Duration Calculus called implementables and the target are programs in an OCCAM dialect PL. In the first part we have shown how the level of program specifications represented by a language SL can be reached. SL combines regular expressions with action systems and time conditions. In this part we show the transformation from SL to PL. It relies on the ‘Expansion strategy’ by which certain transformations can be applied in an almost automatic fashion. In many places transformations consist of algebraic reasoning by laws for operations on programs. Both parts of our transformational calculus rely on the mixed term techniques in which syntax pieces of two languages are mixed in a semantically coherent manner. In the first part of the article mixed terms between implementables and SL have been used, in the present part mixed terms between SL and PL are used. The approach is illustrated by the example of a computer controlled gas burner from part I again. Received 23 July 1996 / 13 February 1998     

Supporting the structured development of complex PL/I software systems

The methodology of top-down (structured) programming has emerged in the last few years as a practical approach to the problem of developing reliable software systems. The methodology, however, places certain demands on the language used for actual system implementation. In this paper we discuss the implications of these demands on a specific language, PL/I. From this discussion the basic objectives of a PL/I support system are deduced. These objectives deal primarily with: (1) specifying intermodule relationships; (2) propagating module modifications; and (3) maintaining consistency in the realization of abstractions. Finally, the essential elements of a system that realizes these objectives are described.     

From software extensions to product lines of dataflow programs

Dataflow programs are widely used. Each program is a directed graph where nodes are computations and edges indicate the flow of data. In prior work, we reverse-engineered legacy dataflow programs by deriving their optimized implementations from a simple specification graph using graph transformations called refinements and optimizations. In MDE speak, our derivations were PIM-to-PSM mappings. In this paper, we show how extensions complement refinements, optimizations, and PIM-to-PSM derivations to make the process of reverse engineering complex legacy dataflow programs tractable. We explain how optional functionality in transformations can be encoded, thereby enabling us to encode product lines of transformations as well as product lines of dataflow programs. We describe the implementation of extensions in the \(\mathtt{ReFlO}\) tool and present two non-trivial case studies as evidence of our work’s generality.     

嵌入一致图语法的依赖图

图语法将字符串上的形式文法扩充为图上的形式文法,提供一种能够使用精确的数学方法来模拟图变换的机制.提出了几种新的基于一致图语法的方法来表示控制流图、数据流图、控制数据流图、二分图和超图,并说明如何通过图重写来自动生成依赖图并挖掘并行性,从而协助并行编译器和并行语言的设计和实现.     

Implementation of language enhancements

Data abstractions have been proposed as a means to enhance program modularity. The implementation of such new features to an existing language is typically handled by either rewriting large portions of an existing compiler or by using a preprocessor to translate the extensions into the standard language. The first technique is expensive to implement while the latter is usually slow and clumsy to use. In this paper a data abstraction addition to PL 1 is described and a hybrid implementation is given. A minimal set of primitive features are added to the compiler and the other extensions are added via an internal macro processor that expands the new syntax into the existing language.     

A numerical profile of commercial PL/I programs

A sample of 120 production PL/I programs from several commercial computing installations has been studied. Data about the programs in the sample have been extracted by a PL/I scanning program. The statistical results of the study are presented in this document The paper concentrates on statistical data and not on general conclusions. The data are only interpreted to the extent that it is not ill-defined and misleading. The data profile the use of basic PL/I elements and the structure of programs written in PL/I. The reader of this report will get a better understanding of how PL/I has been used in the commercial environment up to 1974.     

Six PL/I compilers

This paper describes an experimental evaluation of the execution speed of object programs produced by six PL/I compilers. A set of 139 representative PL/I statements were compiled and executed under the PL/I Optimizing, PL/I(F), PL/C, PL/I Checkout, SP/k and PLUTO compilers. An analysis is made of the relative speed of the object code produced by each compiler and also of the relative execution speed of each statement.     

一种基于快速分解模拟退火算法的数据聚类算法

把求解数据聚类问题转换为一个图形分割寻优问题,提出一种基于快速分解模拟退火算法的数据聚类算法。实验结果证明,快速分解模拟退火算法退火时间短,收敛速度快,磁盘开销小,把它应用于数据聚类中,可以获得较好的聚类结果。I/O     

Trading uninitialized space for time

The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time for the initialization of an adjacency-matrix representation. We describe an alternative representation of static directed graphs taking Θ(n+m) initialization time and using Θ(n²) space, which supports the efficient implementation of all usual operations on static graphs. The sparse graph representation allows the design of efficient graph algorithms using both iteration over all vertices adjacent with a given vertex and edge-existence operations, although at the expense of additional (uninitialized) space which may, nevertheless, be used for other purposes. To the best of our knowledge, the representation leads to the first graph algorithms with the disconcerting property that the time complexity is better than the space complexity.