bluuebunny/crossref_metadata_2025 huggingface dataset:
A language-based approach to functionally correct imperative programming
Authors: Westbrook Edwin , Stump Aaron , Wehrman Ian
Published: November 2005

In this paper a language-based approach to functionally correct imperative programming is proposed. The approach is based on a programming language called RSP1, which combines dependent types, general recursion, and imperative features in a type-safe way, while preserving decidability of type checking. The methodology used is that of internal verification, where programs manipulate programmer-supplied proofs explicitly as data. The fundamental technical idea of RSP1 is to identify problematic operations as impure, and keep them out of dependent types. The resulting language is powerful enough to verify statically non-trivial properties of imperative and functional programs. The paper presents the ideas through the examples of statically verified merge sort, statically verified imperative binary search trees, and statically verified directed acyclic graphs.
Monadic augment and generalised short cut fusion
Authors: Ghani Neil , Johann Patricia , Uustalu Tarmo , Vene Varmo
Published: November 2005

Monads are commonplace programming devices that are used to uniformly structure computations with effects such as state, exceptions, and I/O. This paper further develops the monadic programming paradigm by investigating the extent to which monadic computations can be optimised by using generalisations of short cut fusion to eliminate monadic structures whose sole purpose is to "glue together" monadic program components.We make several contributions. First, we show that
every
inductive type has an associated build combinator and an associated short cut fusion rule. Second, we introduce the notion of an
inductive monad
to describe those monads that give rise to inductive types, and we give examples of such monads which are widely used in functional programming. Third, we generalise the standard augment combinators and cata/augment fusion rules for algebraic data types to types induced by inductive monads. This allows us to give the first cata/augment rules for some common data types, such as rose trees. Fourth, we demonstrate the practical applicability of our generalisations by providing Haskell implementations for all concepts and examples in the paper. Finally, we offer deep theoretical insights by showing that the augment combinators are monadic in nature, and thus that our cata/build and cata/augment rules are arguably the best generally applicable fusion rules obtainable.
Poly
AML
Authors: Dantas Daniel S. , Walker David , Washburn Geoffrey , Weirich Stephanie
Published: November 2005

This paper defines Poly
AML
, a typed functional, aspect-oriented programming language. The main contribution of PolyAML is the seamless integration of polymorphism, run-time type analysis and aspect-oriented programming language features. In particular, PolyAML allows programmers to define type-safe polymorphic advice using pointcuts constructed from a collection of polymorphic join points. PolyAML also comes equipped with a type inference algorithm that conservatively extends Hindley-Milner type inference. To support first-class polymorphic point-cut designators, a crucial feature for developing aspect-oriented profiling or logging libraries, the algorithm blends the conventional Hindley-Milner type inference algorithm with a simple form of local type inference.We give our language operational meaning via a type-directed translation into an expressive type-safe intermediate language. Many complexities of the source language are eliminated in this translation, leading to a modular specification of its semantics. One of the novelties of the intermediate language is the definition of polymorphic labels for marking control-flow points. These labels are organized in a tree structure such that a parent in the tree serves as a representative for all of its children. Type safety requires that the type of each child is less polymorphic than its parent type. Similarly, when a set of labels is assembled as a pointcut, the type of each label is an instance of the type of the pointcut.
Aspectual Caml
Authors: Masuhara Hidehiko , Tatsuzawa Hideaki , Yonezawa Akinori
Published: November 2005

We propose an aspect-oriented programming (AOP) language called
Aspectual Caml
based on a strongly-typed functional language Objective Caml with two AOP mechanisms similar to those in AspectJ language. This paper describes the design and implementation issues of those AOP mechanisms that give us insights into the interaction between AOP features and common features in strongly-typed functional languages such as type inference, polymorphic types and curried functions. We implemented a prototype compiler of the language and used the language for separating crosscutting concerns in application programs, including for separating descriptions of a type system from compiler descriptions.
Executing the formal definition of Ada
Authors: Fantechi A. , Gnesi S. , Leggio F. , Talini P.
Published: November 2005

The results of a study on the effectiveness of an execution environment for the formal definition of Ada are presented. The environment is based on a logic programming approach, that is the translation of the formal definition into an executable logic program. Some experimental performance measurements for a prototype execution environment which has been developed using the same approach for a simple concurrent language are given, and their usefulness in predicting the performance of the environment for the formal definition of Ada is discussed.
Implementing C function calls in rules for an expert system shell
Authors: Madhav B. I. B. , Hegde Narayan
Published: November 2005

In this paper, we report on the implementation of C function calls in rules for an expert system shell. The rule language supports calls to C functions in both antecedents and consequents, meta rules and queries to a relational database. The output of the compiler can be directly loaded or stored as a file. A loader and an inference engine are also provided.
SetLog, a tool for experimenting with new semantics
Authors: Pellegrini Marco , Sepe Raimondo
Published: November 2005

SetLog is a software system that can be used to experiment on several semantics for extensions of Prolog with sets. A first prototype of SetLog has been implemented including the features of a standard Prolog interpreter and of an interpreter for finite set expressions (SETL). Examples of uses of the system are also presented.
Programming language RIGAL as a compiler writing tool
Authors: Auguston M. I.
Published: November 2005

A new programming language for compiler writing is described briefly in this paper. The main data structures are atoms, lists and trees. The control structures are based on a advanced pattern matching. All phases of compilation, including parsing, optimization and code generation, can be programmed in this language in short and readable form.
A comparison of module constructs in programming languages
Authors: Calliss Frank W.
Published: November 2005

Modules are constructs that help implement the principle of information hiding. Some languages provide general purpose modules, while others provide modules that are more specialised. This paper compares the modules that are provided by some languages.
Cluster
Authors: Lujun Shang
Published: November 2005

Cluster is a newly designed and implemented object-oriented programming language. This report gives an outline of the language by examples, explanations, comments, and the comparison with other languages. Though incomplete and informal, it shows interesting results in many aspects of the language.
Essential language el(α)—a reduced expression set language for system programming
Authors: Watanabe Tan , Sakuma Kazuko , Arai Hideyuki , Umetani Kohbun
Published: November 2005

Essential Language el(α) is developed as a "Reduced Expression Set Language" which is simple and yet satisfies conditions for efficient programming and efficient execution. The grammar of el(α) is determined by unifying a machine model applicable to almost all computers and a language model with features essential for system programming. Much efforts are exerted to make the language machine independent and to eliminate execution-time overhead. Its simple syntax drawn in 2 diagrams covers from the module interface specifications to low level operations required for embedded software. Descriptive power of the language and object code efficiency of the compiler are certified by its applications for production programming.
Preliminary Ideas of a Conceptual Programming Language
Authors: Zhai Cheng-xiang
Published: November 2005

This paper presents the preliminary ideas of a relational conceptual programming language CONPL (CONceptual Programming Language). CONPL allows users to use their own concepts instead of computer-related concepts to construct the program. It can also be used as a knowledge representation language. The paper gives the formal description of CONPL and discusses some implementation issues. The paper also explores its potential applications.
Erhard Konrad
Authors: Zuse Horst , Bollmann Peter
Published: November 2005

This paper is the reply to the paper "Erhard Konrad: Software Metrics, Measurement Theory, and Viewpoints - Critical Remarks on a New Approach", which was published in SIGPLAN Notices in March 1991. Konrad imputes that the authors of /ZUSE89/ misapply measurement theory, and confuse reality with mathematics. The statements of Konrad are wrong. It will be shown that Konrad misunderstood important concepts of measurement theory. Konrad's critical statements to our approach deny theoretical investigations of software complexity metrics. That has fatal consequences for the use of software complexity metrics in practice, to make statistics, and to calculate correlations.
Substring parsing for arbitrary context-free grammars
Authors: Rekers Jan , Koorn Wilco
Published: November 2005

A substring recognizer for a language
L
determines whether a string
s
is a substring of a sentence in
L
, i.e.,
substring-recognize(s)
succeeds if and only if ∃
v, w
:
vsw
∈
L
. The algorithm for substring recognition presented here accepts general context-free grammars and uses the same parse tables as the general context-free parsing algorithm from which it was derived. Substring recognition can be useful for noncorrecting syntax error recovery and for incremental parsing. By extending the substring
recognizer
with the ability to generate trees for the possible contextual completions of the substring, we obtain a substring
parser
, which can be used in a syntax-directed editor to complete fragments of sentences.
Another defence of enumerated types
Authors: Sakkinen Markku
Published: November 2005

I claim that enumerations, while of course not strictly necessary, are an elegant and useful facility in modern programming languages. I try to show that arguments recently given against them are weak at best and bogus a t worst, for general-purpose programming. Some related issues on types in programming languages are touched as well. These make it even more questionable whether Oberon marks progress or regress in language design.
Reflection facilities and realistic programming
Authors: Ishikawa Yutaka
Published: November 2005

We propose a new reflection model called2-dimensional hierarchical reflection. The model naturally describes reflective facilities which enable us to change the language semantics as well as the underlying environment, i.e., memory management and cpu scheduling. The concurrent object-oriented programming language called AL-1 has been designed based on the model. The language is an adaptable/extensible system in the sense that the system's bevavior is dynamically changed by the way of reflection. In order to demonstrate how the language is adapted in user's demand, the typical reflective programming in the language is presented.
Detection of version features in distributed systems
Authors: Wong K. C.
Published: November 2005

In this paper we demonstrate how version features can be defined, detected, and used to determine language versions. Using the BNF notation, distinct features can be conveniently specified in the context-free grammar global to all of the versions. A feature matrix specifying the relationship maintained by terminal features is proposed to implement the global grammar, on which determining language versions is based.
Compiler structure engineering with attribute grammars
Authors: Miloucheva Ilka , Loeper Hans
Published: November 2005

In this paper are discussed theconcepts of a compiler structure design system and its prototype implementation.In order to obtain the pass structure based on the properties of the deterministic left to right evaluable attribute grammars we useshort pathalgorithms for directed graphs. An algorithm for assignment of attributes to separate passes is shown. We propose a method for extension of the deterministic left to right evaluable attribute grammars withglobal data. Futher we describe the approach of asyntax oriented modularizationfor specifying the compiler structure.Using this research as a base we developed theCSD system (Compiler Structure Design). The CSD system isa compiler engineering toolproviding facilities for specification of compilers and for design of their pass, intermediate program and module structure. The main components of the system are also shown and its use for development of aCOBOLcompiler are discussed.
USSA—universal syntax and semantics analyzer
Authors: Burshteyn Boris
Published: November 2005

This article presents a new tool for defining syntax and semantics of formal systems, called USSA (
Universal Syntax and Semantics Analyzer
). USSA is based on modifiable grammars introduced in [1, 2]. While parsing or generating the source text, USSA applies context-free rules from the current set of rules and modifies this set on the fly. The USSA concepts are illustrated by a rich variety of syntax and semantic constructions from programming languages.
Four Dimensions of programming-language independence
Authors: Salomon Daniel J.
Published: November 2005

The features of programming languages can be evaluated according to how they affect programming-language independence in four dimensions. The four dimensions are: 1) machine independence, 2) problem independence, 3) human independence, and 4) time independence. This paper presents a definition of
independence
, and shows how that definition applies to each of the dimensions. By organizing language features in this way, the strengths and weaknesses of many language designs can be identified, and new directions for programming-language research become apparent. This paper also presents the advantages of, and methods of achieving, independence in these dimensions, and occasionally presents the disadvantages of independence.Each of the four dimensions is treated as a discrete domain, and the elements of each domain are classified according to their properties. The elements of the
machine
domain are classified according to (a) architecture, (b) machine size, (c) peripheral devices, and (d) operating system. The
problem
domain is classified according to (a) discipline, (b) problem context, (c) system mode, and (d) problem-solving methods. The
human
domain is classified according to (a) user qualifications, (b) natural language spoken, (c) the three classes
designers, implementors
, and
users
, and (d) independence in the class
implementors
is considered alone. Finally the
time
dimension is treated in three time scales: (a) program processing, (b) project development, and (c) language evolution.
Empirical study of motivation in a entry level programming course
Authors: Mamone Salvatore
Published: November 2005

This paper will address the issue of motivation in an entry level programming course. Does the reason a student takes a course dictate the grade he can hope to achieve? Will a student who needs to take a course perform better than a student who wants to take a course? This paper will attempt to answer these questions using the results gained over three years of teaching a program language course at two New York universities and cover seven semesters and 126 students.
The treadmill
Authors: Baker Henry G.
Published: November 2005

A simple real-time garbage collection algorithm is presented which does not copy, thereby avoiding some of the problems caused by the asynchronous motion of objects. This in-place "treadmill" garbage collection scheme has approximately the same complexity as other non-moving garbage collectors, thus making it usable in a high-level language implementation where some pointers cannot be traced. The treadmill is currently being used in a Lisp system built in Ada.
Enhancing program comprehension
Authors: Arab Mouloud
Published: November 2005

In order to make computer programs more readable, presentation and documentation of program source texts need to be enhanced. In this paper, we propose a presentation scheme which highlights the structure of the program and we present some aspects concerning the internal documentation (comments) which enhance the program comprehension. This presentation facilitates error correction and makes the program more readable for other programmers. We propose an automatic formatting and documenting tool which takes into account human factors in man/machine interaction aspect. It provides satisfactory results, programmers produce structured programs which help them in detecting bad constructs and in achieving homogeneity of their programs' presentation and internal documentation.
A new language for multicomputer programming
Authors: García Carrasco José M.
Published: November 2005

In this paper we present an extension of the Pascal language: the Distributed Pascal, suitable for MIMD computers with message-passing. This extension is simple, elegant, flexible and powerful. This language is very suited for numerical algorithms. A complex mathematical algorithm is shown as an example of this. Up to date, we have developed the compiler's front-end and we are running a program in this language by means of simulation.
Guarded attribute grammars
Authors: Frost Richard A.
Published: November 2005

It is widely believed that top down parsing is incompatible with left recursive grammars. We show that this is not true. We describe a novel device by which left recursive productions can be directly compiled into executable interpreters that use a top down parsing strategy. We show how our technique can be used to construct executable attribute grammars that are both modular and expressively natural. We have implemented the technique as an extension to an attribute grammar programming environment which has been tested on a number of projects including the development of theorem provers, natural language processors, and database query processors.
On understanding type declarations in C
Authors: Mody R. P.
Published: November 2005

A small set of rules is given to produce and decipher complicated types in C.
Noised or filtered programming? (about enumerated types)
Authors: Gauthier Michel
Published: November 2005

This paper is yet another contribution to a debate where many people contributed recently [Delft 89, Meek 90, Sakkinen 91, and others...], the ones pleading for considering enumerated types as harmful, and the others as important. But the debate will probably be more useful if levels --- layers --- of programming are taken into account. The good answer has no reason to be the same in real life and at machine level. From my point of view, programming includes an untyping process from the former to the latter. I claim here that enumerated types do give right answers to very real questions in programming, but that they would be yet more useful if they were restricted enough to become closer to real life, as it can be done with Ada private types.
Efficient instruction scheduling for a pipelined architecture
Authors: Gibbons Philip B. , Muchnick Steven S.
Published: November 2005

As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.

Previous algorithms for reducing pipeline interlocks have had worst-case runtimes of at least
O
(
n
4
). By using a dag representation which prevents scheduling deadlocks and a selection method that requires no lookahead, the resulting algorithm reorganizes instructions almost as effectively in practice, while having an
O
(
n
2
) worst-case runtime.
Compilation for a high-performance systolic array
Authors: Gross Thomas , Lam Monica S.
Published: November 2005

We report on a compiler for Warp, a high-performance systolic array developed at Carnegie Mellon. This compiler enhances the usefulness of Warp significantly and allows application programmers to code substantial algorithms.

The compiler combines a novel programming model, which is based on a model of skewed computation for the array, with powerful optimization techniques. Programming in W2 (the language accepted by the compiler) is orders of magnitude easier than coding in microcode, the only alternative available previously.
Efficient incremental evaluation of aggregate values in attribute grammars
Authors: Hoover Roger , Teitelbaum Tim
Published: November 2005

Aggregate valued attributes, which store collections of keyed elements, are required in attribute grammars to communicate information from multiple definition sites to multiple use locations. For syntax directed editors and incremental compilers, symbol tables are represented as aggregate values. We present efficient algorithms for incrementally maintaining these aggregate values and give an incremental evaluation algorithm that restricts attribute propagation to attributes dependent only upon information within the aggregate value that has changed.
EPIC - a retargetable, highly optimizing Lisp compiler
Authors: Kessler R. R. , Peterson J. C. , Carr H. , Duggan G. P. , Knell J.
Published: November 2005

The Experimental Portable Standard Lisp Compiler (EPIC) is a compiler testbed for experimentation with, and development of, Lisp compilation strategies. EPIC uses an architectural description of the target machine to increase portability, and performs extensive optimizations in the form of source-to-source transformations, register allocation, and peephole optimization. It introduces machine-specific instructions early to enable machine-specific optimizations in the initial passes. EPIC produces better code than the original Portable Standard Lisp compiler, has an improved portability model, and is easier to maintain.
Interprocedural dependence analysis and parallelization
Authors: Burke Michael , Cytron Ron
Published: November 2005

We present a method that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures. The method is more efficient than existing methods: we reduce many tests, performed separately by existing methods, to a single test. The method is more precise than existing methods with respect to references to multi-dimensional arrays and dependence information hidden by procedure calls. The method is more general than existing methods: we accommodate potentially aliased variables and structures of differing shapes that share storage. We accomplish the above through a unified approach that integrates subscript analysis with aliasing and interprocedural information.
Direct parallelization of call statements
Authors: Triolet Rémi , Irigoin Francois , Feautrier Paul
Published: November 2005

Asynchronous CALL statements are necessary in order to use more than one processor in current multiprocessors. Detecting CALL statements that may be executed in parallel is one way to fill this need. This approach requires accurate approximations of called procedure effects. This is achieved by using new objects called
Region
and
Execution Context
. An algorithm to find asynchronous CALL statements is given. It involves a new dependence test to compute data dependence graphs, which provides better results than previous ones even when no CALL statements are involved. This method has been implemented in Parafrase and preliminary results are encouraging.
Efficient compilation of linear recursive functions into object level loops
Authors: Harrison Peter , Khoshnevisan Hessam
Published: November 2005

Whilst widely recognised as an excellent means for solving problems and for designing software, functional programming languages have suffered from their inefficient implementations on conventional computers. A route to improved runtime performance is to transform recursively defined functions into programs which execute more quickly and/or consume less space. We derive equivalent imperative programming language loops for a large class of linear recursive functions of which the tail-recursive functions form a very small subset. We first identify a small set of primitive function defining expressions for which we determine the corresponding loop-expressions. We then determine the loop-expressions for linear functions defined by any expressions which are formed from those primitives. In this way, a very general class of linear functions can be transformed automatically into loops in the parsing phase of a compiler, since the parser has in any case to determine the hierarchical structure of function definitions. Further transformation may involve specific properties of particular defining expressions, and adopt previous schemes. In addition, equivalent linear functions can be found for many non-linear ones which can therefore also be transformed into loops.
A retargetable instruction reorganizer
Authors: Davidson Jack W.
Published: November 2005

Extant peephole optimizers can perform many optimizations that are handled by higher-level optimizers. This paper describes a retargetable instruction reorganizer that performs targeting and evaluation order determination by applying a well known algorithm for optimal code generation for expressions to object code. By applying the algorithm to object code after code generation and optimization, a phase ordering problem often encountered by higher-level optimizers is avoided. It minimizes the number of registers and temporaries required to compile expressions by rearranging machine instructions. For some machines, this can result in smaller and faster programs. By generalizing its operation, the reorganizer can also be used to reorder instructions to avoid delays in pipelined machines. For one pipelined machine, it has provided a 5 to 10 percent improvement in the execution speed of benchmark programs.
Less complex elementary functions
Authors: Baker Henry G.
Published: November 2005

The "textbook" definitions of complex elementary functions---e.g., sin(z)---are usually given in terms of formulae which involve complex operations. In this paper, we give formulae for complex elementary functions in which the real and imaginary parts can be computed separately using only real operations. Many of these formulae are obvious, but some---e.g., asin(z), acos(z), atan(z), asinh(z), acosh(z), atanh(z)---are not obvious and/or not well-known.
Unification based FP interpreters
Authors: Fickert Chris , Sudkamp Thomas
Published: November 2005

A specification is given for the functional programming language FP using an attribute grammar formalism that defines a message passing protocol. Derivations in the grammar specify the complete evaluation of an FP program. The message passing provides a functional type checking capability. To avoid the overhead associated with message passing, the grammar is designed so that each FP primitive function and functional form receives and transmits a single message during the compilation. The language specification provides the framework for the construction of two FP interpreters.An interpreter using an innermost first evaluation strategy, the standard evaluation approach for functional composition, is implemented in Prolog. The rules of the language specification are directly translated into Prolog grammar rules. The message passing and type checking are achieved using the unification of variables in the Prolog grammar rules.The innermost first strategy requires the compilation and evaluation of the subfunctions and functional forms that comprise an FP function. A second interpreter, using the parallel logic programming language PARLOG, was constructed to incorporate eager evaluation into the analysis of an FP function. Eager evaluation is accomplished by transmitting partial results (incompletely constructed lists) throughout the evaluation structure. Whenever the partial results contain sufficient information to determine a value, these are used as input to the subfunctions that comprise the FP function being evaluated. Adding eager evaluation alters the degree of error preservation and requires a modification of the definition of FP.
Industrial strength compiler construction with equations
Authors: Hamel Lutz H.
Published: November 2005

Industrial strength compilers need not only be robust and efficient but also understandable, maintainable, and extensible. To make compilers more manageable there has been a strong trend towards the high-level specification of the different phases of the compilation process. However, the high-level specification of one phase - the semantic analysis - has not been very successful in terms of production quality standards. In this paper we propose the use of a language based on equations for the specification of the semantic analysis phase of compilers.
An overview of the ISO/VDM-SL standard
Authors: Plat Nico , Larsen Peter Gorm
Published: November 2005

VDM-SL, the notation incorporated in the formal method VDM, is currently being standardized under auspices of the International Standards Institution (ISO) and the British Standards Institution (BSI). It is one of the few formal languages of which the syntax and the semantics have been completely formally defined. In this paper we present an overview of the standard, including a report on the current status of the standardization effort.
Application of measurement theory to software metrics
Authors: Konrad Erhard
Published: November 2005

In this paper, Bollmann and Zuse's reply to a criticism of their approach to software metrics will be examined. As a result it will be shown that they have failed to achieve their goal of refuting this criticism.
Reply to Ehrad Konrad
Authors: Zuse Horst , Bollmann-Sdorra Peter
Published: November 2005

This paper is the reply to the paper "Erhard Konrad: Application of Measurement Theory to Software Metrics - Comments on the Bollmann-Zuse Approach" which is also published in this issue (November 92) of SlGPLAN Notices. Konrad is criticizing our approach: "Horst Zuse; Peter Bollmann: Using Measurement Theory to Describe the Properties and Scales of Software Complexity Metrics", which was published in SlGPLAN Notices (8)89. Konrad criticized the first time our paper in SIGPLAN Notices in March 1991. We replied in SlGPLAN Notices May 1991 to this criticism. In this issue (November 1992) Konrad imputes again that we have failed to achieve our goals of refuting his criticism. We will show that Konrad has a totally different view of established concepts of measurement theory as treated by Roberts, Krantz, Luce, Suppes and Tversky.
The metric based compiler
Authors: Dumke Reiner , Neumann Kerstin , Stoeffler Kerstin
Published: November 2005

This paper describes the situation in the use of software metrics for the development of software. Today many basic metrics - including code metrics - are applied in very different tools for the development of software. But the user is not sure to obtain the correct instructions for the most efficient implementation in the sense of the lowest psychological complexity. The application of the classical code metrics (Halstead's software science and McCabe's cyclomatic number) is not possible for all languages.Therefore it is necessary that the compiler writer or the compiler writing systems includes the meaningful code metrics in the process of the compiler construction. The compiler writer must know this metrics for "his" language.This paper gives some directions for the derivation of code metrics for different languages and their use as metric based software tools.
Inlining semantics for subroutines which are recursive
Authors: Baker Henry G.
Published: November 2005

Many modern programming languages offer a facility for "inlining" designated procedure and function calls, but this process is not well defined in most language standards documents. We offer a model for inlining which has the property that the resulting code does not depend upon the presentation of the order of function definitions, and which also provides a finite and consistent interpretation for the inlining of mutually recursive functions. Finally, when used on "tail-recursive" functions, our model of inlining provides for the equivalent of "loop unrolling".
Combining objects and relations
Authors: Razek Gottfried
Published: November 2005

Whereas the object oriented paradigm is best suited for the modelling of self contained objects it is not suited for the modelling of relations between objects. For the logic oriented paradigm on the other hand the converse is true. This paper shows that objects and their relations can be modelled in an integrated way by combining both paradigms.
A concurrent compiler for Modula-2+
Authors: Wortman David B. , Junkin Michael D.
Published: November 2005

In this paper we describe a collection of techniques for the design and implementation of concurrent compilers. We begin by describing a technique for dividing a source program into many
streams
so that each stream can be compiled concurrently. We discuss several compiler design issues unique to concurrent compilers including source program partitioning, symbol table management, compiler task scheduling and information flow constraints. The application of our techniques is illustrated by a complete design for a concurrent Modula-2+ compiler. After describing the structure of this compiler's performance that demonstrates that significant improvements in compilation time can be achieved through the use of concurrency.
An abstract machine for CLP(
R
)
Authors: Jaffar Joxan , Stuckey Peter J. , Michaylov Spiro , Yap Roland H. C.
Published: November 2005

An abstract machine is described for the CLP(ℜ) programming language. It is intended as a first step toward enabling CLP(ℜ) programs to be executed with efficiency approaching that of conventional languages. The core Constraint Logic Arithmetic Machine (CLAM) extends the Warren Abstract Machine (WAM) for compiling Prolog with facilities for handling real arithmetic constraints. The full CLAM includes facilities for taking advantage of information obtained from global program analysis.
A general framework for iteration-reordering loop transformations
Authors: Sarkar Vivek , Thekkath Radhika
Published: November 2005

This paper describes a general framework for representing iteration-reordering transformations. These transformations can be both matrix-based and non-matrix-based. Transformations are defined by rules for mapping dependence vectors, rules for mapping loop bound expressions, and rules for creating new initialization statements. The framework is extensible, and can be used to represent any iteration-reordering transformation. Mapping rules for several common transformations are included in the paper.
A dynamic scheduling method for irregular parallel programs
Authors: Lucco Steven
Published: November 2005

This paper develops a methodology for compiling and executing
irregular
parallel programs. Such programs implement parallel operations whose size and work distribution depend on input data. We show a fundamental relationship between three quantities that characterize an irregular parallel computation: the total available parallelism, the optimal grain size, and the statistical variance of execution times for individual tasks. This relationship yields a dynamic scheduling algorithm that substantially reduces the overhead of executing irregular parallel operations.

We incorporated this algorithm into an extended Fortran compiler. The compiler accepts as input a subset of Fortran D which includes blocked and cyclic decompositions and perfect alignment; it outputs Fortran 77 augmented with calls to library routines written in C. For irregular parallel operations, the compiled code gathers information about available parallelism and task execution time variance and uses this information to schedule the operation. On distributed memory architectures, the compiler encodes information about data access patterns for the runtime scheduling system so that it can preserve communication locality.

We evaluated these compilation techniques using a set of application programs including climate modeling, circuit simulation, and x-ray tomography, that contain irregular parallel operations. The results demonstrate that, for these applications, the dynamic techniques described here achieve near-optimal efficiency on large numbers of processors. In addition, they perform significantly better, on these problems, than any previously proposed static or dynamic scheduling algorithm.
Alphonse
Authors: Hoover Roger
Published: November 2005

Alphonse is a program transformation system that uses dynamic dependency analysis and incremental computation techniques to automatically generate efficient dynamic implementations from simple exhaustive imperative program specifications.
Sentinel scheduling for VLIW and superscalar processors
Authors: Mahlke Scott A. , Chen William Y. , Hwu Wen-mei W. , Rau B. Ramakrishna , Schlansker Michael S.
Published: November 2005

Speculative execution is an important source of parallelism for VLIW and superscalar processors. A serious challenge with compiler-controlled speculative execution is to accurately detect and report all program execution errors at the time of occurrence. In this paper, a set of architectural features and compile-time scheduling support referred to as
sentinel scheduling
is introduced. Sentinel scheduling provides an effective framework for compiler-controlled speculative execution that accurately detects and reports all exceptions. Sentinel scheduling also supports speculative execution of store instructions by providing a store buffer which allows probationary entries. Experimental results show that sentinel scheduling is highly effective for a wide range of VLIW and superscalar processors.
Are LR parsers too powerful?
Authors: Machanick P
Published: November 2005

The general trend in the development of parser theory is in the direction of exploring implementing methods of increasing power. In particular, ways of improving the efficiency of LR parsers and the generation of LR tables have been receiving a lot of attention. The value of increasingly powerful tools is questioned from the point-of-view of the need to keep definitions of languages understandable to the programmer. Consideration is given to Wirth's contention that recursive descent is the method of choice and alternatives are suggested.
Universal closure operator for prolog
Authors: Vasak T
Published: November 2005

A powerful, second-order universal closure operator is proposed and its usefulness in constructing clear, efficient programs is demonstrated.
Compared anatomy of the programming languages Pascal and C
Authors: Hayward V
Published: November 2005

The programming languages PASCAL and C belong to the class of algorithmic compiled languages, and feature comparable facilities. The syntax of C is more regular and enjoys less restrictions than that of PASCAL. Consequently, the syntax of C is significantly simpler than that of the PASCAL language. The design differences are particularly apparent as far as data types, operators, and system interface are concerned. PASCAL implements abstract data types (booleans, sets), whereas C defines data types that reflect the architecture of currently available computers. For PASCAL, the system interface is implemented via functions built in the language and is therefore not extensible by the user. Most of the practical implementations of the language require non standard extensions. In C, system calls and libraries of subroutines and macro instructions are provided to handle the system interface. The portability of applications then depends on the libraries and not on the compiler. A greater flexibility is thus achieved. The use of pointers and the rich set of operators of the C language make it more general than PASCAL, while retaining the principles of structured programming. Separate compilation is a standard feature of C, not of PASCAL. PASCAL compilers are often complex, while C compilers are simple and compact. C compilers include a macro processor, and the program verifier is a separate tool. The application programmers have more responsibility programming in C than in PASCAL, conversely, applications depend less on compilers in C than in PASCAL.
TRC: An expert system compiler
Authors: Kary D D , Juell P L
Published: November 2005

TRC is a compiler that is useful in building expert systems. The input is a rule based language. The output is a set of C language procedures. The principal advantages of TRC over existing expert system construction tools are speed of execution and portability of the code generated by TRC. The name TRC is an acronym for Translate Rules to C.
Experience with a FORTH-like language
Authors: Jonak J E
Published: November 2005

Extensible and threaded code language FORTH is very popular among amateur programmers but only few professionals admit they use it or are prepared to describe their experience.The author has been using a directly threaded variation of FORTH, called F, for development of a couple of software products. And although convinced of the language usefulness as an implementation tool he would like to point out a few problem areas which he encountered during the development and life time of these products.
A comparative feature-analysis of microcomputer prolog implementations
Authors: Weeks J , Berghel H
Published: November 2005

In recent years, no programming language has received the international attention of PROLOG. Currently the Japanese Fifth Generation computing Systems Project (ICOT) is attempting to build an entire series of computers around this language in order to implement a new generation of computers based on symbolic inferencing techniques. In the United States and Europe, PROLOG is being used in relational database applications, natural language processing, theorem proving and automated reasoning, and a variety of other artificial intelligence applications.In this article, we compare several of the newer PROLOG interpreters and compilers with regard to their functionality. This information is useful to researchers in selecting the product which will be the most relevant to their applications.
RELFUN: A relational/functional integration with valued clauses
Authors: Boley H
Published: November 2005

The RELFUN programming language is introduced as an attempt to integrate the capabilities of the relational and functional styles. Definitions of functions and relations are specified uniformly by valued Horn clauses, where rules return the value of their rightmost premise. Functional nestings are flattened to relational conjunctions, using a purified version of PROLOG's is-primitive. RELFUN functions may have non-ground arguments, like relations, and/or return non-ground values; their input and output arguments can be inverted like those of relations. Higher-order functions are definable as (function-) valued clauses, with funarg problems being avoided by the standard renaming of clause variables. RELFUN's operational semantics is specified as an abstract machine, which also yields its first (e-mailable) FRANZ LISP implementation.
Programming pascal with physical units
Authors: Dreiheller A , Mohr B , Moerschbacher M
Published: November 2005

In /Mä86/ (SIGPLAN Notices 3/1986) Männer proposes an extension of Pascal permitting the use of physical units in programs. We discuss his issues in this paper and describe our own somewhat different approach. Our language extension PHYSCAL of Pascal not merely satisfies the requirements suggested by /Mä86/, but also supports predefined units (International Standard), thorough realisation of the concept of scale factors, input/output facilities for numbers with units. The new concepts are motivated, and the language description is given formally and by examples. Finally we discuss some details of the realised language implementation by a PHYSCAL-to-Pascal preprocessor in an UNIX environment.
Up-down parsing with prefix grammars
Authors: Turner P K
Published: November 2005

A powerful method of parsing is presented, that suits particularly well the Graham-Glanville code generation methodology. This parsing method can be applied to any prefix grammar. It is shown how a table is generated and used to achieve parsing efficiency.
Introduction to the programming language convert
Authors: Cisneros G , McIntosh H V
Published: November 2005

We present an introductory description of Convert, a programming language applicable to symbol manipulation problems whose solution may be expressed in terms of transformation rules. We discuss the experience derived from our use of the language and mention some future applications.
A definition of an ISWIM-like language via scheme
Authors: Ivanovic Mirjana , Budimac Zoran
Published: November 2005

A full definition of a purely functional lSWIM-like language is given in the paper. A set of transformation rules for the translation of ISWlM expressions to expressions of a widely accepted Scheme programming language is given. The paper is supported with appropriate examples of equivalent expressions in both languages.
Adapting a debugger for optimised programs
Authors: Shu William S.
Published: November 2005

An interactive source-level debugger for optimised programs is built where the features of either debugger or optimiser may be fully expressed without undue hindrance from each other, nor degradation when they are used separately. Tracker is the link between the tools that assures this. Its role is to correct for any distortions introduced by optimisation in the debugging process. It stems from a view that opfimisation and debugging perform the same actions on a program code, albeit for different purposes. This paper discusses implementation aspects in adapting a debugger and an optimiser in this model for debugging optimised programs.
CRL/Pascal
Authors: Baowen Xu
Published: November 2005

CRL/Pascal, a Pascal-oriented program cross reference language, is used to describe the definition and use information of entities in Pascal programs. In this paper, we shall introduce its design ideas, program structure and facilities, and generating tools, and then discuss the relationship between CRL/Pascal and PIDL/Pascal and Pascal-oriented program interface description language developed by the auther).
Infant mortality and generational garbage collection
Authors: Baker Henry G.
Published: November 2005

Generation-based garbage collection has been advocated by appealing to the intuitive but vague notion that "young objects are more likely to die than old objects". The intuition is, that if a generation-based garbage collection scheme focuses its effort on scanning recently created objects, then its scanning efforts will pay off more in the form of more recovered garbage, than if it scanned older objects. In this note, we show a counterexample of a system in which "infant mortality" is as high as you please, but for which generational garbage collection is ineffective for improving the average mark/cons ratio. Other benefits, such as better locality and a smaller number of large delays, may still make generational garbage collection attractive for such a system, however.