bluuebunny/crossref_metadata_2025 huggingface dataset:
Ownership types for safe region-based memory management in real-time Java
Authors: Boyapati Chandrasekhar , Salcianu Alexandru , Beebee William , Rinard Martin
Published: November 2005

The Real Time Specification for Java (RTSJ) allows a program to create real-time threads with hard real-time constraints. Real-time threads use region-based memory management to avoid unbounded pauses caused by interference from the garbage collector. The RTSJ uses runtime checks to ensure that deleting a region does not create dangling references and that real-time threads do not access references to objects allocated in the garbage-collected heap. This paper presents a static type system that guarantees that these runtime checks will never fail for well-typed programs. Our type system therefore 1) provides an important safety guarantee for real-time programs and 2) makes it possible to eliminate the runtime checks and their associated overhead.Our system also makes several contributions over previous work on region types. For object-oriented programs, it combines the benefits of region types and ownership types in a unified type system framework. For multithreaded programs, it allows long-lived threads to share objects without using the heap and without memory leaks. For real-time programs, it ensures that real-time threads do not interfere with the garbage collector. Our experience indicates that our type system is sufficiently expressive and requires little programming overhead, and that eliminating the RTSJ runtime checks using a static type system can significantly decrease the execution time of real-time programs.
Experience with an automatic code generator generator
Authors: Landwehr Rudolf , Jansohn Hans-Stephan , Goos Gerhard
Published: November 2005

We implemented an automatic code generator generator based on the approach of Glanville and Graham. We describe our experience with this system and compare the generated code with that of a conventional Pascal compiler.
A forward move algorithm for LL and LR parsers
Authors: Mauney Jon , Fischer Charles N.
Published: November 2005

A wide variety of algorithms have been suggested for the repair of syntactic errors in a computer program. Since there is usually more than one possible repair for any syntax error, many algorithms employ a cost function to guide the the repair, and some [1,3,4,6], guarantee that the repair chosen will be least-cost, according to some definition. (The others, although guided by costs, do not guarantee least-cost in all cases.) Fischer et al. [4,6,7] define a “locally least-cost” repair using insertions and deletions, and provide algorithms for LL and LR parsers. A locally least-cost repair is a least-cost sequence of deletions and insertions such that one more symbol in the original string will be accepted by the parser. Backhouse [2,3] uses a similar definition. In both cases, the repair algorithms operate by examining a single symbol in the input at any time.
Tailoring testing to a specific compiler—experiences
Authors: Seyfer Harlan K.
Published: November 2005

The testing of the Univac UCS-Pascal compiler is described. Tests were acquired from various sources, converted from existing tests, and developed in house. Test development and execution using the Univac Test Controller System is illustrated with examples. The experiences gained from this and other compiler testing efforts are described.
LINGUIST-86
Authors: Farrow Rodney
Published: November 2005

LINGUIST-86 is a commercially-developed translator-writing-system based on attribute grammars [K]. From an input attribute grammar it generates a set of high-level language source modules that form an alternating-pass attribute evaluator [JW]. LINGUIST-86 generates attribute evaluators efficient enough to run on a microcomputer at speeds competitive with other translators on the system. The Attributed Program Tree is kept on secondary storage rather than in randomly-accessed memory, thus allowing non-trivial inputs to be evaluated on a microcomputer system. LINGUIST-86 also applies an optimization called static subsumption that eliminates many copy rules from the generated evaluators. LINGUIST-86 is itself written as an 1800 line attribute grammar and is self-generating.
A truly generative semantics-directed compiler generator
Authors: Ganzinger Harald , Giegerich Robert , Möncke Ulrich , Wilhelm Reinhard
Published: November 2005

This paper describes semantic processing in the compiler generating system MUG2. MUG2 accepts high-level descriptions of the semantics of a programming language including full runtime semantics, data flow analysis, and optimizing transformations. This distinguishes MUG2 from systems such as YACC [Joh75], HLP [HLP78], PQCC [PQC79], or its own former version [GRW77] with respect to expressive power and convenience. In this respect, MUG2 comes close to semantics-directed systems such as [Mos76], [JoS80], [Set81], [Pau82]. In contrast to these, MUG2 is not a universal translator system where program independent semantic properties have to be evaluated at compilation time. The description concepts of MUG2 allow a far reaching separation of language vs. program dependent semantics, thus constituting a truly generative approach to
semantics-directed
compiler generation.
Engineering a production code generator
Authors: Crawford John
Published: November 2005

This paper describes the structure of a code generator formed by merging the best aspects of three code generation techniques: Graham-Glanville parser-driven code generation [G] [GG] [GR] [HG], the register allocation/spill mechanism from the Portable C Compiler [J], and a code template expander [W]. The Graham-Glanville method was modified to use a standard LALR parser and table builder, and the register allocation method was extended in several significant ways in order to make optimal use of a machine with characterized registers.

This code generator is a part of the Pascal-86 compiler developed by Intel Corporation as one of several compilers supporting its iAPX-86 (8086) microprocessor family. The language supported by the compiler is an extension of the Draft International Standard Pascal, level 0. Object code generated by this method compares favorably to code produced by other compilers for the 8086, as well as Pascal compilers for other machines. Since its release in March 1981, the code generator has proved to be quite reliable and easy to maintain.
Experience with an experimental compiler generator based on denotational semantics
Authors: Bodwin James , Bradley Laurette , Kanda Kohji , Litle Diane , Pleban Uwe
Published: November 2005

Compiler generation based on formal semantics has received considerable attention in recent years from a number of semanticists. Compiler writers, on the other hand, know relatively little about these efforts. This paper tries to remedy this situation by discussing our experimentation with the Semantics Implementation System (SIS) of Peter Mosses. SIS allows the user to generate a complete compiler from a formal specification of the syntax and semantics of a programming language. In particular, the translator component of a compiler is obtained by directly implementing a denotational semantics. Consequently, a compiler is expressed as a higher order function. A program is compiled by formally applying the compiler to a tree representation of the program and simplifying this application. The experimentation with SIS indicates that compiler generation based on denotational semantics is feasible, though not yet viable. We argue that SIS constitutes an important first step toward the automatic construction of provably correct, complete, and reasonably efficient compilers from formal syntactic and semantic specifications.
Control flow aspects of semantics directed compiling (Summary)
Authors: Sethi Ravi
Published: November 2005

We focus on the part of a compiler between syntax analysis and code generation. A language is specified by adding semantic rules in a functional notation to the syntax of the language. Starting with a small sublanguage of while statements, the semantics of the statement constructs of C is built up incrementally. Using a small ad hoc code generator, a compiler has automatically been constructed from the semantics. The semantic description is analogous to a syntax directed construction of a flow diagram for a program. In analogy with grammars and parser generators, minimal knowledge of the underlying theory is required.

For the control flow aspects of languages, efficient compilers can quickly be generated.
An applicative compiler for a parallel machine
Authors: Moor Ian W.
Published: November 2005

A compiler for the applicative language HOPE is described. The compiler is itself written in HOPE and generates a machine independent compiler target language, suitable for execution on the parallel reduction machine ALICE. The advantages of writing a compiler in a very high level applicative language are discussed, and the use of program transformation and other techniques to turn the initial 'runnable specification' into a more efficient (if less clear) program are outlined. Extensions to the HOPE language and the compiler which can exploit the parallelism and various execution modes of ALICE are described.
The document editor
Authors: Walker Janet H.
Published: November 2005

As understanding of a particular problem domain matures, its tools become more specialized, moving from general low-level tools to more specialized high-level tools. Early work in a field applies the same set of low-level aids to all problems. Gradually more specialized tools emerge as we come to better understand the problem and the tools that are best for it.

Since the emergence of the first program editors in the early 1960s we have learned a lot about the editing process and about building editors. Recently several editors specialized for editing program sources, text, and data structures have been developed. To date, little work has been reported on specialized document editors for editing complex text. This paper describes a research effort into identifying the requirements for an interactive environment for editing complex documents and an initial implementation for the environment.
Checking for spelling and typographical errors in computer-based text
Authors: Turba Thomas N.
Published: November 2005

This paper addresses the problems and techniques of checking for spelling and typographical errors in computer-based text. To some extent, the paper is a combination of a report of work done by the author and a survey of other work which, although not all used by the author, is of equal value and interest. Some of the material presented is related to other aspects of text processing such as data compaction and the efficient searching of very large dictionaries.
Computer aids for writers
Authors: Cherry Lorinda
Published: November 2005

For many people, writing is painful and editing one's own prose is difficult, tedious, and error-prone. It is often hard to see which parts of a document are difficult to read or how to transform a wordy sentence into a more concise one. It is even harder to discover that one overuses a particular linguistic construct. The system of programs described here helps writers to evaluate documents and to produce better written and more readable prose. The system consists of programs to measure surface features of text that are important to good writing style as well as programs to do some of the tedious jobs of a copy editor. Some of the surface features measured are readability, sentence and word length, sentence type, word usage, and sentence openers. The copy editing programs find spelling errors, wordy phrases, bad diction, some punctuation errors, double words, and split infinitives.
JANUS
Authors: Chamberlin Donald D. , King James C. , Slutz Donald R. , Todd Stephen J.P. , Wade Bradford W.
Published: November 2005

This paper describes the architecture of a proposed document composition system named JANUS, which is intended to provide support for authors of complex documents containing mixtures of text, line art, and tone art. The JANUS system is highly interactive, providing authors with immediate feedback and direct electronic control over page layouts, using a special two-display workstation. Authors communicate with the system by marking up their documents with high-level descriptive “tags”. A tag definition language is provided whereby new tags may be defined and the format of each tagged object may be controlled.
Data abstraction
Authors: Morris James B.
Published: November 2005

A description of the implementation of the data abstraction mechanism for the Model programming language is discussed. The Model programming language utilizes a “static” approach to data abstraction in that abstract concepts are expanded by early phases of the compiler in a controlled fashion into base language concepts. Thus, the final phase of the compiler sees only base language constructions. Exemplified are generic procedures accepting parameters of several different data types. A discussion is given of the problem of “parameter explosion”, a problem traditionally inherent in languages implementing open (inline) procedures.
Code generation in a machine-independent compiler
Authors: Cattell Roderic G.G. , Newcomer Joseph M. , Leverett Bruce W.
Published: November 2005

This paper presents some code generation issues in the context of the PQCC Production-Quality Compiler-Compiler project [8]. The approach taken is unusual in several ways. The machine-dependent information for selection of code sequences, register assignments, etc., has been separated throughout, in tabular form, from the machine-independent algorithms. This not only greatly simplifies the development of code generators for new machines or languages, but paves the way for automatic generation of these tables from formal machine descriptions such as ISP [1]. A parse-tree-like internal program representation is used, facilitating the use of context and data dependency information about expressions. The code generation process has been broken into several phases. This leads to simplification and better understanding of the code generation process, and also allows important improvements in the quality of generated code. The algorithms for preliminary determination of addressing modes, allocation of registers and other locations, and the code selection case analysis are discussed. The algorithms described in the paper are being implemented and used in the PQCC compiler.
Implementation of an Interactive Programming System
Authors: Kahrs Mark
Published: November 2005

Design and implementation experience with an Interactive Programming System are described. Reflections are made on various design decisions and on the effect of using a Tree Factored Interpreter as the core of the system.
Porting the Zed compiler
Authors: Bonkowski G. B. , Gentleman W. M. , Malcolm M. A.
Published: November 2005

Zed is the base language used to implement the portable realtime operating system Thoth[7], and to write commands, utilities, application programs, and other software which run under Thoth. (Zed is similar to C, although language details are not important in this paper.) One of the founding principles of Thoth is our experience that the hardest problems in porting programs usually arise when interfacing to different operating systems. By porting the whole operating system first, we ensure that other programs see the same system interface. Hence, with a modicum of care in programming, programs can be machine independent in that, without change, they can be compiled for any machine to which Thoth has been ported. Since the Zed compiler is a program which runs under the Thoth operating system, it is portable in this sense, and the same source serves to produce either native mode or cross compilers because it does not depend on the machine on which the compiler will run.

Compilers, in common with certain other “system software”, are, however, machine specific in that the output from executing a compiler must be different depending upon the machine on which that output is destined to be run. Clearly, for Thoth to be ported to many machines, the compiler should be portable in this second sense: as much as possible of the source of the compiler should be machine invariant, that is, independent of the target machine, and for those parts which are machine specific, there must be a well organized scheme to assist realizing versions for new machines. The Zed compiler is designed to ease such ports. Actually, the objective is broader than that, because the initial port is only part of the problem: once versions of the compiler are available for several machines, we still have the problems of maintaining all these different versions, enhancing them, and evolving them to follow changes in the language. To do this, we need a structure that is easy to understand and to work with. We also want to minimize the amount of source code for which multiple versions must exist.
Machine-independent PASCAL code optimization
Authors: Perkins Daniel R. , Sites Richard L.
Published: November 2005

A variant of PASCAL pseudo-code which is suitable for optimization is presented. This new language, Universal pseudo-code, is designed to be easily extended to meet the needs of a variety of target machines. The language is further designed such that only one optimizer need be written for it. This approach lends itself well to the portable software spirit of PASCAL. The problems and opportunities associated with optimization at this level are discussed.
The design of a global optimizer
Authors: Mintz Ronald J. , Fisher Gerald A. , Sharir Micha
Published: November 2005

We are constructing a compiler for a high level systems and applications programming language. Because the compiler is required to generate efficient object code, a global optimization phase and register allocation phase are an integral part of the design. It was determined that the familiar optimizations of code motion, redundant expression elimination, and dead code removal would be sufficient.

The optimizer design was to be based on the most recent applicable theoretical results, yet simple and straightforward to implement. Traditional approaches were considered inadequate because they assume a primitive intermediate code representation (quadruples), elaborate flow graph constructions, and numerous special cases. High level data flow analysis as proposed by Rosen [1,2] provided the framework we sought. Using his approach, the parse tree of the program, with its high level control structures intact, becomes a suitable intermediate representation. Complex statement structures are analyzed quickly in two tree traversals to determine the solutions to data flow problems.
Generalized procedure calling and content-directed invocation
Authors: Davis Randall
Published: November 2005

We suggest that the concept of a
strategy
can profitably be viewed as
knowledge about how to select from among a set of plausibly useful knowledge sources
, and explore the framework for knowledge organization which this implies. We describe
meta rules
, a means of encoding strategies that has been implemented in a program called TEIRESIAS, and explore their utility and contribution to problem solving performance.

Meta rules are also considered in the broader context of a tool for programming. We show that they can be considered a medium for expressing the criteria for retrieval of knowledge sources in a program, and hence can be used to define control regimes. The utility of this as a programming mechanism is considered.

Finally, we describe the technique of
content-directed invocation
used by meta rules, and consider its use as a way of implementing strategies. It is also considered in historical perspective as a knowledge source invocation technique, and its advantage over some existing mechanisms like goal-directed invocation is considered.

This work was supported in part by the Bureau of Health Sciences Research and Evaluation of HEW under Grant HS-01544 and by the Advanced Research Projects Agency under ARPA Order 2494. It was carried out on the SUMEX Computer System, supported by the NIH under Grant RR-00785. The views expressed are solely those of the author.
Language facilities for programmable backtracking
Authors: Griswold Ralph E. , Hanson David R.
Published: November 2005

Most languages intended for artificial intelligence applications include a search and backtracking facility. While built-in backtracking facilities are convenient, they are often too inflexible for use beyond a limited range of applicability. Other mechanisms, such as those based on explicit manipulations of bindings or stack frames, tend to be very unstructured, and give the programmer little control over the backtracking process. This paper describes the SL5 programming language and its use for “programmable backtracking.” SL5 includes a general procedure mechanism that permits procedures to be used as recursive functions or as coroutines. Using this mechanism, the programmer can construct control hierarchies that are tailored to the specific application. A string pattern-matching facility is given as an example of the use of the SL5 facilities.
AMORD explicit control of reasoning
Authors: Kleer Johan de , Doyle Jon , Steele Guy L. , Sussman Gerald Jay
Published: November 2005

The construction of expert problem-solving systems requires the development of techniques for using modular representations of knowledge without encountering combinatorial explosions in the solution effort. This report describes an approach to dealing with this problem based on making some knowledge which is usually implicitly part of an expert problem solver explicit, thus allowing this knowledge about control to be manipulated and reasoned about. The basic components of this approach involve using explicit representations of the control structure of the problem solver, and linking this and other knowledge manipulated by the expert by means of explicit data dependencies.
ALGOL 68 might-have-beens
Authors: van der Meulen S. G.
Published: November 2005

This paper discusses some language features which might have been in ALGOL68. They would not have complicated the compiler to any considerable extent. They would certainly have contributed to the expressive power of the language. In fact their desirability emerged from the practice of ALGOL68 programming (cf. {4}). “Might-have-beens” are small super-language features and some of them could even be considered as “might-be”s in the sense that they still might be incorporated in existing compilers without (great) difficulty.

A few of these “lost chances” have deeper roots and may contribute to the development of future languages.
'Run-time profiling of Algol 68-R programs using DIDYMUS and SCAMP'
Authors: Brailsford D. F. , Foxley E. , Mander K. C. , Morgan D. J.
Published: November 2005

Information concerning the run-time behaviour of programs (“program profiling”) can be of the greatest assistance in improving program efficiency. Two software devices have been developed for use on ICL 1900 Series machines to provide such information.

DIDYMUS is probabilistic in approach and uses multitasking facilities to sample the instruction addresses used by a program at run time. It will work regardless of the source language of the program and matches the detected addresses against a loader map to produce a histogram.

SCAMP is restricted to profiling Algol 68-R programs, but provides deterministic information concerning those language constructs that are monitored. Procedure calls to appropriate counting routines are inserted into the source text in a pre-pass prior to compilation. The profile information is printed out at the end of the program run.

It has been found that these two approaches complement each other very effectively.
Some remarks on new instances and garbage collection
Authors: Szöke Péter
Published: November 2005

Some questions of run-time storage management for ALGOL 68 are discussed. In the first section it is shown that in many cases copying of already existing values is not necessary, in spite of the fact that the Report prescribes this. The second section gives a new approach for finding the starting points for tracing the lists of values during garbage collection. In the third section we introduce a new area (in addition to the stack and the heap) for making the garbage collection process less expensive. The fourth section describes the general memory organization: stack, heap and bubble.
Storage management for ALGOL68
Authors: Birrell A. C.
Published: November 2005

This paper describes some of the techniques which can be used for managing the run time storage required for an ALGOL68 program. The emphasis is on stack storage, since garbage collection techniques would require another paper. The problems caused by some ALGOL68 constructs are described: the solutions given are mainly those adopted in the Cambridge ALGOL68C system.
A transportation of ALGOL68C
Authors: Gardner P. J.
Published: November 2005

This paper describes the problems and solutions of a particular “pulled” bootstrap transportation of the Cambridge ALGOL68C compiler; in particular, the problems encountered in making the external appearance of the compiler system conform to the conventions of the object machine's operating system interface.
The Berlin ALGOL 68 implementation
Authors: Koch Wilfried , Oeters Christoph
Published: November 2005

This paper is an introduction to the portable ALGOL 68 implementation currently developed at the Technical University of Berlin. An overview over the compiler and the other system components is given and the facilities for separate compilation and precompilation are described. Finally, the current state of the implementation is sketched.
Geometric modelling in ALGOL 68
Authors: Braid I. C. , Hillyard R. C.
Published: November 2005

The paper describes the experiences of a small team in writing a substantial ALGOL 68 program to model the shapes of engineering components. The application derives much advantage from structures, operators and the heap. It includes a command interpreter, graphics package, vector and matrix routines, and procedures for moving data structures on the heap to and from disc. A system has been devised to ensure safe, selective compilation of program segments.
A Multi Radar Tracking simulation using ALGOL 68'R
Authors: West P. R.
Published: November 2005

The paper outlines the use of ALGOL 68R in the production of a series of simulation models for a Multi Radar Tracking feasibility study. Particular reference is made to the use of
structures
, the chaining mechanisms used and the modularity of the models. The multi-radar tracking models were developed in ALGOL 68'R by Plessey Radar Ltd. and run on their 1906S under George 3/MOP.
Is Pascal a logical subset of Algol68 or not? Part One
Authors: Edwards Roy
Published: November 2005

It is often believed that Pascal is - Algol68 in miniature - well “structured”.

It will be argued in Part One of this paper that both beliefs are badly founded.
On a transportable high level language for minicomputers
Authors: Stocks A Ian , Krishnaswamy Jayant
Published: November 2005

This paper describes a high-level, PASCAL-based language, which is easily implementable on minicomputers with limited amounts of memory. The added features include a machine and operating system—independent formalism for describing file structures, and allow either compile time or run-time specification of the actual-formal file correspondence. A similar formalism for handling program overlays is described. These constructs are implemented in a manner consistent with the underlying language PASCAL, and allow one to easily write operating systems components.
The Datasaab FCPU microprogramming language
Authors: Lawson Harold W. , Blomberg Lars
Published: November 2005

This paper describes the high level microprogramming language (ML) used in microprogramming the FCPU (Flexible Central Processing Unit) developed by the Datasaab sector of Saab-Scania AB. The background of the use of machine dependent high level languages is discussed. The global structure and microinstruction organization of the FCPU are presented. The structure of the ML and microprograms are introduced followed by an example of the use of ML. A summary of the syntactical structure of FCPU microinstruction statements and the FCPU facilities are presented in an appendix.
Direct microprogrammed execution of the intermediate text from a high-level language compiler
Authors: Broca Francois Robert , Merwin Richard E.
Published: November 2005

Microprogramming commonly executed operations can improve the computational speed of data processing systems. This paper describes how microprogramming may be used to execute directly the intermediate text generated by a high-level language compiler after syntactic and semantic analysis of the input source program.

Direct microprogrammed execution of common forms of intermediate text - i.e.: quadruples, triples, and duos - has been simulated. A comparison is made, in terms of storage requirements and execution time, of this direct microprogrammed system scheme with the present methods which result in machine language representation and execution of the intermediate text. Direct generation of a microprogram from the high-level language statements is also examined.

Timing assumptions for comparative purposes have been based on the IBM 360 MOD 50 system. Simulation and timing estimates for the microprograms have been carried out on a microprogram directed simulator which closely represents the architectural organization of the MOD 50.
Some deficiencies of C++ in teaching CS1 and CS2
Authors: Bergin Joe , Agarwal Achla , Agarwal Krishna
Published: November 2005

C++ is a popular programming language for the introductory level (CS1) and at the advance level (CS2) at many community colleges and universities in the USA. While teaching CS1 and CS2, we observed some deficiencies of C++, which are discussed in this paper. Students and instructors should be aware of these problems in CS1 and CS2. Selecting the "right" language for pedagogical purposes can be made easier if these pitfalls are observed.
Translating EXPRESS language model into C language model
Authors: ChunYan Yu , Minghui Wu , Nairuo Liu , Yueting Zhuang , Yunhe Pan
Published: November 2005

EXPRESS is a powerful object-oriented data model descriptive language and independent of any platform. However, it is a kind of descriptive language rather than a programming language. This brings difficulty to implement the EXPRESS data model on a computer and it also undoubtedly brings a big problem with the STEP data model processing so that we have to translate EXPRESS language model into a certain programming language model. In this paper, an approach is presented to translate the EXPRESS language model into the C language model. In addition, this paper proves the validity of this translation theoretically.
The scope of imported identifiers in Modula-2
Authors: Anderson Terry L.
Published: November 2005

An extension to Modula-2 is proposed that allows better control of the scope of the unqualified form of imported identifiers. In the current language an imported identifier can be unqualified only for an entire module. Ada allows a more precise control of the scope. A fairly minor syntactic change to Modula-2 would allow a similar convenience.
Profile guided code positioning
Authors: Pettis Karl , Hansen Robert C.
Published: November 2005

This paper presents the results of our investigation of code positioning techniques using execution profile data as input into the compilation process. The primary objective of the positioning is to reduce the overhead of the instruction memory hierarchy.

After initial investigation in the literature, we decided to implement two prototypes for the Hewlett-Packard Precision Architecture (PA-RISC). The first, built on top of the linker, positions code based on whole procedures. This prototype has the ability to move procedures into an order that is determined by a “closest is best” strategy.

The second prototype, built on top of an existing optimizer package, positions code based on basic blocks within procedures. Groups of basic blocks that would be better as straight-line sequences are identified as
chains
. These chains are then ordered according to branch heuristics. Code that is never executed during the data collection runs can be physically separated from the primary code of a procedure by a technique we devised called
procedure splitting
.

The algorithms we implemented are described through examples in this paper. The performance improvements from our work are also summarized in various tables and charts.
Two-directional record layout for multiple inheritance
Authors: Pugh William , Weddell Grant
Published: November 2005

Much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. In such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple inheritance. Methods currently used make field extraction 3-5 times slower, which can produce a significant overall performance slowdown.

We describe a record layout algorithm that allows us to assign a fixed offset to each field name. This allows field extraction to done just as quickly as in systems that do not provide multiple inheritance. Assigning fixed offsets may require us to leave gaps in some records (and waste space). However, by placing fields at both positive and negative offsets we can drastically reduce the amount of wasted space. Finding an optimal layout is NP-hard, so we propose and analyze heuristic algorithms for producing good two-direction record layouts.

In a trial run, our algorithm produced a fixed layout for the instance variables of the 563 flavors of a Lisp Flavors system; this fixed layout only wastes 6% of the total space consumed by a collection of one instance of each flavor.
Type declarations as subtype constraints in logic programming
Authors: Jacobs Dean
Published: November 2005

This paper presents a type system for logic programs that supports parametric polymorphism and subtypes. This system follows most knowledge representation and object-oriented schemes in that subtyping is
name-based
, i.e.,
τ
1
is considered to be a subtype of
τ
2
iff it is declared as such. We take this as a fundamental principle in the sense that type declarations have the form of subtype constraints. Types are assigned meaning by viewing such constraints as Horn clauses that, together with a few basic axioms, define a subtype predicate. This technique provides a (least) model for types and, at the same time, a sound and complete proof system for deriving subtypes. Using this proof system, we define well-typedness conditions which ensure that a logic program/query respects a set of predicate types. We prove that these conditions are consistent in the sense that every atom of every resolvent produced during the execution of a well-typed program is consistent with its type.
Identifying the semantic and textual differences between two versions of a program
Authors: Horwitz Susan
Published: November 2005

Text-based file comparators (
e.g.
, the Unix utility
diff
), are very general tools that can be applied to arbitrary files. However, using such tools to compare
programs
can be unsatisfactory because their
only
notion of change is based on program
text
rather than program
behavior
. This paper describes a technique for comparing two versions of a program, determining which program components represents changes, and classifying each changed component as representing either a
semantic
or a
textual
change.
Compiling programs for a linear systolic array
Authors: Tseng Ping-Sheng
Published: November 2005

This paper describes an AL compiler for the Warp systolic array. AL is a programming language in which the user programs a systolic array as if it were a sequential computer and relies on the compiler to generate parallel code. This paper introduces the notion of data relations in compiling programs for systolic arrays. Unlike dependence relations among statements of a program, data relations define compatibility relations among data objects of a program. The AL compiler uses data relations to compute data compatibility classes, determine data distribution, and distribute loop iterations. The AL compiler can generate efficient parallel code almost identical to what the user would have written by hand. For example, the AL compiler generates parallel code for the LINPACK LU decomposition (SGEFA) and QR decomposition (SQRDC) routines with a nearly 8-fold speedup on the 10-cell Warp array for matrices of size 180 × 180.
English as a very high level language for simulation programming
Authors: Heidorn George E.
Published: November 2005

An automatic programming system which produces simulation programs from information obtained through natural language dialogue has been implemented under CP/CMS on the IBM 360/67. In the current version the information obtained from an English conversation about a simple queuing problem is used to build a language independent entity-attribute-value data structure. From this structure both an English description of the problem and a GPSS simulation program for it can be produced. This processing is done by a FORTRAN program which interprets sets of decoding and encoding rules written in a specially developed grammar-rule language. The paper includes a complete sample problem with a discussion of its processing and examples of decoding and encoding rules.
An outline of a mathematical model for the definition and manipulation of data
Authors: Nordström Bengt
Published: November 2005

This paper presents a constructive model for data which suggests some precise definitions of notions like type, name, constants, declarations etc. The model is based on an old idea of looking at data as a mapping from a set of names to a set of values. We will study two different kinds of assignments and also show how the model can be used to give some hints for new data structuring methods. In particular we have given a definition of a sequence and we have shown how this data structure can be used to give constructive definitions of structures like stacks, files and queues. We have also studied tree traversals i.e. the correspondence between various trees and sequences.
Some desirable properties of data abstraction facilities
Authors: Horning J. J.
Published: November 2005

It is currently popular to say that programming languages need “data abstraction facilities,” and to assert that the provision of such facilities would provide conceptual and practical advantages in the domain of data structures akin to the advantages provided by procedures in the domain of computational structures. This note explores some of the implications of this metaphor, without attempting to make it precise. I shall use the term
capsule
to refer to the data analog of
procedure
. [Those who are familiar with the SIMULA
class
, the CLU
cluster
, or the ALPHARD
form
, may use any of these as an approximation to
capsule
; I use a neutral term to avoid implying the details of any particular language.]

First, what are the advantages provided by procedures (subroutines, functions, macros)? I can think of at least eight (highly interrelated) categories: 1) avoidance of repetition, 2) modular program structure, 3) a basis for structured programming, 4) conceptual units for understanding and reasoning about programs, 5) clearly defined interfaces that may be precisely specified, 6) units of maintenance and improvement, 7) a language extension mechanism, and 8) units for separate compilation. Let us consider each of these in turn.
Towards the construction of verifiable software systems
Authors: Flon L. , Habermann A. N.
Published: November 2005

Data types are an important design tool because they allow freedom of abstraction. Thus, they are useful for constructing large software systems, including operating systems. It is shown that when dealing with problems of concurrency, the use of path expressions, which are associated with data, makes the task of verification simpler than when the synchronization conditions are associated with programs.
Fundamentals of the AMBIT/L list-processing language
Authors: Wolfberg Michael S.
Published: November 2005

This paper introduces the reader to the fundamentals of AMBIT/L, a diagrammatic list-processing language, by presenting its solution to a canonical programming problem.
The terminal control language for the madcap programming language
Authors: Devaney Marjorie J. , Hudgins Jeanne
Published: November 2005

This paper describes the hardware and software associated with a keyboard based, storage scope terminal interactive facility currently under development at Los Alamos. The terminal commands are given by single character operators. Editing on a line or character basis and interaction with an executing program is included. The overall approach has been one of command language and source language unification.
TWO-D
Authors: Haag James N. , Kelly Michael A. , Sherman Paul F.
Published: November 2005

A programming system, permitting the user to think 100% that he is programming with flowchart symbols, is described. This description includes the TWO-D syntax, the user's view-point, the CRT-terminal output, the overall structure of the simply-designed programming system, the file structure used, some design decisions faced, and the flowchart of the supervisory program.
An algebraic description of programs with assertions, verification and simulation
Authors: Burstall Rod M.
Published: November 2005

A program in flow diagram form is described by a function from a free category to the category of sets and relations. Attaching assertions to it is described as a natural transformation and so is simulation of one program by another with the same shape of flow diagram. These notions are used to prove the theorems justifying Floyd's method of proving correctness by verification and Milner's method of proving simulation, restricted to programs of similar form. The treatment is novel but the results are not new, except that non-deterministic programs are dealt with throughout.
Derivation of axiomatic definitions of programming languages from algorithmic definitions
Authors: Allen C David
Published: November 2005

Language definitions by abstract interpreters are appropriate to the design and development of a language. Axiomatic definitions are more appropriate to proving program properties and verification of compilers. The proof methods of Manna and Ashcroft can be applied to an algorithmic definition in, e.g. the Vienna Definition Language to deduce theorems which constitute an axiomatic definition of precisely the same language.

The process and techniques are explained, and illustrated on a simple language of assignment statements.
Translating recursion schemes into program schemes
Authors: Garland Stephen J. , Luckham David C.
Published: November 2005

Here and in a further paper [2] we study translations between schemes and related equivalence problems, i.e., problems of determining whether two schemes in a given class are equivalent. In particular, we are concerned with the question of developing methods for attacking these problems. It seems to us that some “general methods” ought to exist or, at least, a general form ought to be given to the existing “tricks”. In these papers we present four methods: applying the theory of formal languages, programming, measuring the complexity of a computation, and “cutting and pasting” (roughly speaking, the application of a method due to Rabin and Scott [8] to bound the search necessary to determine if two schemes will behave differently).

Although a few of the results are true for some general notion of scheme, we have nearly always had in mind, for the sake of illustration, just three specific classes of schemes: program schemes, program schemes augmented with counters, and recursively defined schemes. The greater part of the study is restricted to monadic schemes (i.e., schemes containing only functions and predicates of a single argument), and in the case of recursively defined schemes, we are concerned almost exclusively with the single variable monadic recursion schemes introduced by de Bakker and Scott in [1].
Properties preserved under recursion removal
Authors: Strong H. R. , Walker S. A.
Published: November 2005

In this paper we report research which is going on at present. Rather than presenting major results, we have selected a number of partial results and techniques in order to indicate a direction we think is promising. In the first section we review methods for converting a program with a calling structure involving recursion into one without such a structure. In the second section we discuss the separation of the aspects of control and storage in this recursion removal process. We show, by example, how the separation provides the possibility of preserving properties other than functional equivalence. These two sections provide a slight generalization of and complement work presented in the expository paper [S2]. In this third section we illustrate implications of invertibility of operations with respect to the recursion removal process. The central example of this section is the Ackerman functional, obtained by schematizing a version of the Ackerman function. With this example, we note that a recursion need not be convertible to a primitive recursion in order to be removable.
Lambda calculus schemata
Authors: Fischer Michael J.
Published: November 2005

A lambda calculus schema is an expression of the lambda calculus augmented by uninterpreted constant and function symbols and thus is an abstraction of programming languages such as LISP which permit functions to be passed to or returned from other functions. We then consider two natural implementation strategies: the retention strategy in which all variable bindings are retained until no longer needed (implying the use of some sort of garbage collected store) and the deletion strategy, modelled after the usual stack implementation of ALGOL-60, in which variable bindings are destroyed when control leaves the procedure (or block) in which they were created. Berry shows that the deletion strategy implementation is not “correct” for a wide class of languages in the sense that it is not equivalent to natural extensions of the copy rule of ALGOL to such languages, whereas the retention strategy is correct in that sense. We show, however, that no real power is lost in restricting oneself to a deletion strategy implementation, for any program can be translated into an equivalent one which will work correctly under such an implementation. The proof makes no use of the particular primitive functions and data of the language and hence is true of the corresponding schemata under all interpretations.
The Contour Model Lambda Calculus Machine
Authors: McGowan Clement
Published: November 2005

Much work has been done towards characterizing the semantics of block structured programming languages using the lambda calculus
[
2
]
. Johnston
[
3
]
recently introduced a cell-based approach, called the contour model, for specifying the execution semantics of such languages. This paper relates the two approaches by giving a contour model evaluator for compiled lambda expressions.

Section 2 gives the basic definitions needed from the lambda calculus to make the paper self-contained. Section 3 defines the Contour Model Lambda Calculus Machine (CMLCM). Unfortunately publication limitations preclude some worked examples which would greatly aid the reader's understanding. They will be provided in the talk itself and in an expanded version of this paper for the Tutorial Conference on Semantic Models of Computation. Section 4 outlines the structure of the proof of the CMLCM's correctness. And Section 5 is a set of concluding remarks on the significance of the CMLCM.
A boundary between decidability and undecidability for parallel program schemata (Extended Abstract)
Authors: Miller Raymond E.
Published: November 2005

Some theorems showing undecidability for computational commutativity, boundedness, termination and determinacy of parallel program schemata are given. These results are then compared with contrasting decidability results in [1] showing that the deletion of the hypothesis of repetition-freeness from the decidability theorems produces undecidability.