bluuebunny/crossref_metadata_2025 huggingface dataset:
A study of the application of compiler techniques to the generation of micro-code
Authors: Tirrell A. Keith
Published: November 2005

With the advent of writable control memories, the opportunity for using “firmware” to implement software systems increases dramatically. This paper presents one approach to the problem of constructing a micro-program compiler which uses a machine-independent language.

While this kind of compiler language may not generate micro-programs as efficient as those constructed by assembly language, the improvement in documentation, the ease of locating logic errors, and the possibility of using micro-programs on different computer systems make a micro-programming compiler a useful tool.
Towards a specification of syntax and semantics for languages for horizontally microprogrammed machines
Authors: Rauscher Tomlinson G.
Published: November 2005

Horizontally microprogrammable computers provide the potential for efficient use of hardware through parallel operation of internal resources. Present languages for microprogramming such computers, however, contain unnatural symbolism, inflexible format requirements, and additional constraints that are unnecessary for the functions the languages perform. The intrinsic characteristics of horizontally microprogrammable machines suggest the use of operator precedence languages to program them. We formally describe the syntax of a language, ANIMIL, along these lines and discuss some initial ideas on semantics of languages for horizontally microprogrammable machines. A brief report on present status and thoughts for future work conclude the paper.
A microprogrammed satellite graphics system
Authors: Stabler George M. , Carlbom Ingrid , Magel Ken
Published: November 2005

A coordinated research effort in the area of interactive computer graphics using a host-satellite configuration is described. Central to the project is the use of a high-level programming language and two microprogrammable processors. The system as a whole is discussed, as well as the areas of interaction between the design of the satellite's instruction sets and the design of its operating system and the compiler.
A COBOL Machine
Authors: Chevance R. J.
Published: November 2005

This paper describes a research project undertaken by CII. This project is sponsored by the “Comité de Recherches en Informatique” contract No CRI 72-11.

In this study, we have to define a COBOL Machine and a Compilation Machine and to implement them on a medium-scale microprogrammed computer. The expected results are : performance evaluation of these machines, code compaction, COBOL compiler characteristics, operating system implications...
MEMBERS - a Microprogrammed Experimental Machine with a Basic Executive for Real-time Systems
Authors: Broadbent J. K. , Coulouris G. F.
Published: November 2005

The aims and methods of a project investigating the direct interpretation of a high level language and operating system by microprogram on a small machine are outlined. Some features of the language specifically designed for interpretation by microprogram are described in the context of other related work. Some factors involved in the use of microprogramming as a system development method are discussed.
EVA: an explicit vector language
Authors: Dekeyser J. , Marquet Ph. , Pruex Ph.
Published: November 2005

Fortran is the main language used on supercomputer today. Indeed, all supercomputers compilers have extensions, providing language features for explicit vector handling, to Fortran 77. These extensions are different on each machine and their functions are limited. Even with the next standard Fortran 8x, vector syntax is incomplete. EVA is an explicit vector language with powerful vector handling tools. Taking into account the billion of dollars invested in productive Fortran 77 programs, EVA has been designed keeping in mind Fortran and C interface facilities.
Influences on the design of exception handling
Authors: Ryder Barbara G. , Soffa Mary Lou
Published: November 2005

There has long been a close association between research in software engineering and the design of programming languages. Part of the IMPACT project involves an exploration of the interrelations of these two fields and documentation in a report of how fundamental research in software engineering has been a valuable resource for programming language features commonly used today. The resulting report investigates the relationship by considering features in currently used languages, including exceptions, control and data abstractions, types, inheritance, concurrency and visualization mechanisms.This paper, exerpted from the report, focuses on the influence of software engineering research on the development of exceptions. The paper demonstrates that there is a symbiotic relationship between software engineering research and the design of exception handing in programming languages. Publication of these partial results is aimed at soliciting feedback and comments from both the programming languages and software engineering communities.
Register allocation across procedure and module boundaries
Authors: Santhanam Vatsa , Odnert Daryl
Published: November 2005

This paper describes a method for compiling programs using interprocedural register allocation. A strategy for handling programs built from multiple modules is presented, as well as algorithms for
global variable promotion
and register
spill code motion
. These algorithms attempt to address some of the shortcomings of previous interprocedural register allocation strategies. Results are given for an implementation on a single register file RISC-based architecture.
Fast breakpoints: design and implementation
Authors: Kessler Peter B.
Published: November 2005

We have designed and implemented a fast breakpoint facility. Breakpoints are usually thought of as a feature of an interactive debugger, in which case the breakpoints need not be particularly fast. In our environment breakpoints are often used for non-interactive information gathering; for example, procedure call count and statement execution count profiling [Swinehart, et al.]. When used non-interactively, breakpoints should be as fast as possible, so as to perturb the execution of the program as little as possible. Even in interactive debuggers, a conditional breakpoint facility would benefit from breakpoints that could transfer to the evaluation of the condition rapidly, and continue expeditiously if the condition were not satisfied. Such conditional breakpoints could be used to check assertions,
etc.
Program advising could also make use of fast breakpoints [Teitelman]. Examples of advising include tracing, timing, and even animation, all of which should be part of an advanced programming environment.

We have ported the Cedar environment from a machine with microcode support for breakpoints [Lampson and Pier] to commercial platforms running C code [Atkinson, et al.]. Most of our ports run under the Unix
*
operating system, so one choice for implementing breakpoints for Cedar was to use the breakpoint facility provided by that system. The breakpoints provided by the Unix operating system are several orders of magnitude too slow (and also several process switches too complicated) for the applications we have in mind. So we designed a breakpoint system that was fast enough for our purposes.

Breakpoints for uni-processors running single threads of control used to be fast and simple to implement. This paper shows that breakpoints can still be fast, even with multiple threads of control on multi-processors. This paper describes problems in the design of a breakpoint package for modern computer architectures and programming styles, and our solutions to them for a particular architecture.
How to read floating point numbers accurately
Authors: Clinger William D.
Published: November 2005

Consider the problem of converting decimal scientific notation for a number into the best binary floating point approximation to that number, for some fixed precision. This problem cannot be solved using arithmetic of any fixed precision. Hence the
IEEE Standard for Binary Floating-Point Arithmetic
does not require the result of such a conversion to be the best approximation.

This paper presents an efficient algorithm that always finds the best approximation. The algorithm uses a few extra bits of precision to compute an IEEE-conforming approximation while testing an intermediate result to determine whether the approximation could be other than the best. If the approximation might not be the best, then the best approximation is determined by a few simple operations on multiple-precision integers, where the precision is determined by the input. When using 64 bits of precision to compute IEEE double precision results, the algorithm avoids higher-precision arithmetic over 99% of the time.

The input problem considered by this paper is the inverse of an output problem considered by Steele and White: Given a binary floating point number, print a correctly rounded decimal representation of it using the smallest number of digits that will allow the number to be read without loss of accuracy. The Steele and White algorithm assumes that the input problem is solved; an imperfect solution to the input problem, as allowed by the IEEE standard and ubiquitous in current practice, defeats the purpose of their algorithm.
How to print floating-point numbers accurately
Authors: Steele Guy L. , White Jon L.
Published: November 2005

We present algorithms for accurately converting floating-point numbers to decimal representation. The key idea is to carry along with the computation an explicit representation of the required rounding accuracy.

We begin with the simpler problem of converting fixed-point fractions. A modification of the well-known algorithm for radix-conversion of fixed-point fractions by multiplication explicitly determines when to terminate the conversion process; a variable number of digits are produced. The algorithm has these properties:

No information is lost; the original fraction can be recovered from the output by rounding.

No “garbage digits” are produced.

The output is correctly rounded.

It is never necessary to propagate carries on rounding.

We then derive two algorithms for
free-formal
output of floating-point numbers. The first simply scales the given floating-point number to an appropriate fractional range and then applies the algorithm for fractions. This is quite fast and simple to code but has inaccuracies stemming from round-off errors and oversimplification. The second algorithm guarantees mathematical accuracy by using multiple-precision integer arithmetic and handling special cases. Both algorithms produce no more digits than necessary (intuitively, the “1.3 prints as 1.2999999” problem does not occur).

Finally, we modify the free-format conversion algorithm for use in
fixed-format
applications. Information may be lost if the fixed format provides too few digit positions, but the output is always correctly rounded. On the other hand, no “garbage digits” are ever produced, even if the fixed format specifies too many digit positions (intuitively, the “4/3 prints as 1.333333328366279602” problem does not occur).
Type-dependent parameter inference
Authors: Cormack Gordon V. , Wright Andrew K.
Published: November 2005

An algorithm is presented to infer the type and operation parameters of polymorphic functions. Operation parameters are named and typed at the function definition, but are selected from the set of overloaded definitions available wherever the function is used. These parameters are always implicit, implying that the complexity of using a function does not increase with the generality of its type.
Compilation of Haskell array comprehensions for scientific computing
Authors: Anderson Steven , Hudak Paul
Published: November 2005

Monolithic approaches to functional language arrays, such as Haskell
array comprehensions
, define elements all at once, at the time the array is created, instead of incrementally. Although monolithic arrays are elegant, a naive implementation can be very inefficient. For example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests. If a compiler does not know inter-element data dependencies, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array.

Subscript analysis, originally developed for imperative language vectorizing and parallelizing compilers, can be adapted to provide a functional language compiler with the information needed for efficient compilation of monolithic arrays. Our contribution is to develop the number-theoretic basis of subscript analysis with assumptions appropriate to functional arrays, detail the kinds of dependence information subscript analysis can uncover, and apply that dependence information to sequential efficient compilation of functional arrays.
Iterative type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs
Authors: Chambers Craig , Ungar David
Published: November 2005

Object-oriented languages have suffered from poor performance caused by frequent and slow dynamically-bound procedure calls. The best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented procedure calls without static receiver type information precludes inlining.
Iterative type analysis
and
extended message splitting
are new compilation techniques that extract much of the necessary type information and make it possible to hoist run-time type tests out of loops.

Our system compiles code on-the-fly that is customized to the actual data types used by a running program. The compiler constructs a control flow graph annotated with type information by simultaneously performing type analysis and inlining. Extended message splitting preserves type information that would otherwise be lost by a control-flow merge by duplicating all the code between the merge and the place that uses the information. Iterative type analysis computes the types of variables used in a loop by repeatedly recompiling the loop until the computed types reach a fix-point. Together these two techniques enable our SELF compiler to split off a copy of an entire loop, optimized for the common-case types.

By the time our SELF compiler generates code for the graph, it has eliminated many dynamically-dispatched procedure calls and type tests. The resulting machine code is twice as fast as that generated by the previous SELF compiler, four times faster than ParcPlace Systems Smalltalk-80,
*
the fastest commercially available dynamically-typed object-oriented language implementation, and nearly half the speed of optimized C. Iterative type analysis and extended message splitting have cut the performance penalty for dynamically-typed object-oriented languages in half.
Generators and the replicator control structure in the parallel environment of ALLOY
Authors: Mitsolides Thanasis , Harrison Malcolm
Published: November 2005

The need for searching a space of solutions appears often. Many problems, such as iteration over a dynamically created domain, can be expressed most naturally using a generate-and-process style. Serial programming languages typically support solutions of these problems by providing some form of generators or backtracking.

A parallel programming language is more demanding since it needs to be able to express parallel generation and processing of elements. Failure driven computation is no longer sufficient and neither is multiple-assignment to generated values.

We describe the
replicator
control operator used in the high level parallel programming language ALLOY. The replicator control operator provides a new view of generators which deals with these problems.
The University of Washington illustrating compiler
Authors: Henry Robert R. , Whaley Kenneth M. , Forstall Bruce
Published: November 2005

The University of Washington illustrating compiler (UWPI) automatically illustrates the data structures used in simple programs written in a subset of Pascal
2
. A UWPI user submits a program to UWPI, and can then watch a graphical display show time varying illustrations of the data structures and program source code. UWPI uses the information latent in the program to determine how to illustrate the program. UWPI infers the abstract data types directly from the declarations and operations used in the source program, and then lays out the illustration in a natural way by instantiating well-known layouts for the abstracts types. UWPI solves program illustration using compile-time pattern matching and type inferencing to link anticipated execution events to display events, rather than relying on user assistance or specialized programming techniques. UWPI has been used to automatically illustrate didactic sorting and searching examples, and can be used to help teach basic data structures, or to help when debugging programs.
Dynamic program slicing
Authors: Agrawal Hiralal , Horgan Joseph R.
Published: November 2005

Program slices are useful in debugging, testing, maintenance, and understanding of programs. The conventional notion of a program slice, the
static slice
, is the set of all statements that
might
affect the value of a given variable occurrence. In this paper, we investigate the concept of the
dynamic slice
consisting of all statements that
actually
affect the value of a variable occurrence for a given program input. The sensitivity of dynamic slicing to particular program inputs makes it more useful in program debugging and testing than static slicing. Several approaches for computing dynamic slices are examined. The notion of a Dynamic Dependence Graph and its use in computing dynamic slices is discussed. The Dynamic Dependence Graph may be unbounded in length; therefore, we introduce the economical concept of a Reduced Dynamic Dependence Graph, which is proportional in size to the number of dynamic slices arising during the program execution.
The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages
Authors: Ottenstein Karl J. , Ballance Robert A. , MacCabe Arthur B.
Published: November 2005

The Program Dependence Web (PDW) is a program representation that can be directly interpreted using control-, data-, or demand-driven models of execution. A PDW combines a single-assignment version of the program with explicit operators that manage the flow of data values. The PDW can be viewed as an augmented
Program Dependence Graph
. Translation to the PDW representation provides the basis for projects to compile Fortran onto dynamic dataflow architectures and simulators. A second application of the PDW is the construction of various compositional semantics for program dependence graphs.
Automatic recognition of induction variables and recurrence relations by abstract interpretation
Authors: Ammarguellat Zahira , Harrison W. L.
Published: November 2005

The recognition of recurrence relations is important in several ways to the compilation of programs. Induction variables, the simplest form of recurrence, are pivotal in loop optimizations and dependence testing. Many recurrence relations, although expressed sequentially by the programmer, lend themselves to efficient vector or parallel computation. Despite the importance of recurrences, vectorizing and parallelizing compilers to date have recognized them only in an ad-hoc fashion. In this paper we put forth a systematic method for recognizing recurrence relations automatically. Our method has two parts. First, abstract interpretation [CC77, CC79] is used to construct a map that associates each variable assigned in a loop with a symbolic form (expression) of its value. Second, the elements of this map are matched with patterns that describe recurrence relations. The scheme is easily extensible by the addition of templates, and is able to recognize nested recurrences by the propagation of the closed forms of recurrences from inner loops. We present some applications of this method and a proof of its correctness.
An overview of nonprocedural languages
Authors: Leavenoworth Burt M. , Sammet Jean E.
Published: November 2005

This paper attempts to describe some of the basic characteristics and issues involving the class of programming languages commonly referred to as “nonprocedural” or “very high level”. The paper discusses major issues such as terminology, relativeness, and arbitrary sequencing. Five features of nonprocedural languages are described, and a number of specific languages are discussed briefly. A short history of the subject is included.
An interactive business definition system
Authors: Hammer M. M. , Howe W. G. , Wladawsky I.
Published: November 2005

This paper presents a structured approach for describing business applications and a programming language that embodies the approach. This language provides business oriented building blocks for formally specifying the applications. The language is the nucleus of a Business Definition System in which users define their problems by interacting with application models in a question-answer mode.
High level operations in automatic programming
Authors: Earley Jay
Published: November 2005

We discuss the thesis that one good way of achieving non-procedural or problem-oriented languages is by constructing higher and higher level procedural languages. We present a set of operations embedded in a programming language VERS2 which represent a higher level of description than currently exists. These include iterators (operations which, if written out, would normally involve an iteration over a group of objects), pattern matching facilities, implicitly specified data structures, and the ability to place constraints on data structures.
Automatic and semiautomatic optimization of SETL
Authors: Schwartz J. T.
Published: November 2005

The compilation of SETL, a programming language of high level based upon the dictions and semantic concepts of the mathematical theory of sets, raises optimization problems connected with the copying, representation, type-checking and indexing of composite data objects and subobjects. Methods are prescribed for treating some of these problems by adapting known techniques of global program analysis and optimization. A programmer-assisted approach to related, less tractable optimization problems is suggested.
Continuous system simulation languages
Authors: Fairley Richard E.
Published: November 2005

Continuous system simulation languages are very high level programming languages which facilitate modelling and simulation of systems characterized by ordinary and partial differential equations. This paper discusses design principles and implementation techniques for continuous system simulation languages.

Following a brief introduction to very high level languages, design principles for continuous system simulation languages are presented. These principles are illustrated by examples from the Continuous System Modelling Program (CSMP) and the Partial Differential Equation Language (PDEL). A typical program in each language is included.

Batch and interactive implementation techniques for continuous system simulation languages are discussed. The classical batch implementation technique is to provide a preprocessor which translates the simulation language into an algorithmic language such as FORTRAN or PL/1. The PL/1 preprocessor is described as a useful language for the implementation of very high level language translators.

The final section of the paper presents an interactive implementation technique which interfaces a batch program processor to interactive graphics display and updating routines. In this manner, efficient simulation code is interfaced to flexible interaction routines. In addition, the batch processor is preserved intact, thus requiring only one implementation of the language for both batch and interactive applications.
Speakeasy-an evolutionary system
Authors: Cohen S.
Published: November 2005

Speakeasy is a very high level user-oriented language imbedded in a modular computer system. This system, designed for use with attached libraries for its information base, is an evolutionary development constantly being augmented in power by its user community. This paper describes the basic structure of the system and demonstrates some of its capabilities.
An introduction to the UMTA specification language
Authors: Ziegler E. W.
Published: November 2005

Many of the problems in the implementation and maintenance of computer programs occur during the transition from detailed functional specifications to reliable computer code (i.e., in the detailed design, coding, testing, and integration of the computer program). A study for the U.S. Air Force found that approximately 65 percent of the software effort in several large systems went into these transitional activities.(1) In other words, about twice as much software effort went into getting the computer programs to work reliably as went into determining what functions the programs should perform. This paper describes a tool to improve that ratio.

The Urban Mass Transportation Administration (UMTA) is employing a highly systematic approach to the management of computer software development. Part of this approach is the documentation and review of detailed technical specifications for computer programs. This review helps assure that the computer programs, when implemented, will do the job they are intended to do. The review takes place prior to any coding of the computer programs to reduce the amount of redesign and recoding during programming.
Embedding a relational data sublanguage in a general purpose programming language
Authors: Allman Eric , Stonebraker Michael , Held Gerald
Published: November 2005

This paper describes EQUEL, a programming language which embeds the relational data sublanguage QUEL into the general purpose programming language “C”. Both QUEL and EQUEL are operational parts of the INGRES relational data base management system at Berkeley. Also briefly described are two operational subsystems written in this combined language. Lastly some of the language oriented shortcomings that have been observed in QUEL and EQUEL are discussed.
Data abstractions for data bases
Authors: Hammer Michael
Published: November 2005

The concept of abstract data types has emerged from programming language research as a device to encourage and facilitate structured and modular programming [1]. It separates the abstraction of a data object from its implementation. The user of an abstract data type only concerns himself with the behavioral semantics of the type: what meaningful operations can be applied to objects of the type; the internal representation and structure of the type is unknown to him. In this way, irrelevent detail is suppressed and meaningfulness of programs enhanced.

What application does this concept have to the area of data bases? There are some obvious similarities between the principle of abstraction and the concept of data independence of data bases [2]. Data independence means that application programs that utilize a data base do not need to know either the physical or the structural organization of the data base, but can relate to it purely on a logical plane. As with data abstractions, the goal is clarity and modifiability of programs, resulting from concentration on semantics rather than representation.
Toward foundations for the understanding of type
Authors: Ross Douglas T.
Published: November 2005

I have now written, have available from SofTech, and have submitted for publication elsewhere, the first two of a series of deep philosophical papers [1, 2] about Plex [3]. Among other things, I believe these papers begin to provide a proper foundation for our endeavors in computer science and software engineering. The trend of these developments is indicated in the following, which I call
The Proem
of Plex1 and Plex2 [“Proem: 1.) A preliminary discourse to a longer piece of writing. 2.) An introductory comment before a speech. 3.) Something that opens or begins.”—Webster's].
Research directions in abstract data structures
Authors: Shaw Mary
Published: November 2005

A number of interesting research problems arise from current attempts to incorporate abstraction mechanisms in programming languages. Some of them are central issues in current research projects and others are direct extensions of current work. Several problems in each of these areas are outlined below. A third section presents a series of speculations about how this work might evolve in the future.

Since this is supposed to be a session to spark research ideas, I have written brief descriptions of a number of topics and not delved very deeply into any one. Most of these problems can probably be solved in more than one way. Hence the fact that a problem is being worked on should not deter anyone from looking at it from another viewpoint.
A next step in data structuring for programming languages
Authors: Mitchell Jim , Wegbreit Ben
Published: November 2005

An abstraction provides a statement of the properties of a data type without any commitment to a specific implementation. Programs which use abstractions can be developed and verified without regard to how the abstraction will be realized. Any type which fulfills the requirements of the abstraction can be bound in its place without affecting the program's correctness or its proof.

In [4], the notion of a scheme as a model for a set of types is developed. A scheme is written as a module which takes normal values plus types as formal parameters. Instantiating a scheme with actual parameters yields a
scheme instance
which is a data type. For example, one can write a scheme for AVL trees [5] which takes the type of the keys in the tree as a parameter. An instance of this scheme, for example, AVL trees of strings, is a normal data type.
Data base abstraction
Authors: Smith John M. , Smith Diane C. P.
Published: November 2005

Real-world systems modelled by data bases are often quite complex. It is essential that the data base be structured in a way which supports a users abstractions about the real-world system. The “relation” data type is introduced as a structuring primitive for relational data bases The relation data type has similar abstraction properties to the “record” data type of PASCAL. A data base defined via relation data types is structured as a hierarchy of n-ary relations. It is shown that the consistency of this hierarchic structure can be preserved during update operations by two simple rules. A top-down methodology for data base design with relation data types is developed. This methodology minimizes the number of details with which a designer must contend at one time. In particular, the methodology allows the separation of decisions concerning abstract structure from decisions concerning key identification. The separation simplifies both types of decision making for the data base designer.
Abstract data types and the development of data structures
Authors: Guttag John
Published: November 2005

Abstract data types can play a significant role in the development of software that is reliable, efficient, and flexible. This paper presents and discusses the application of an algebraic technique for the specification of abstract data types. Among the examples presented is a top-down development of a symbol table for a block structured language, including a discussion of the proof of its correctness. The paper also contains a brief discussion of the problems involved in constructing algebraic specifications that are both consistent and sufficiently-complete.
Programming without pointer variables
Authors: Kieburtz Richard B.
Published: November 2005

The presence of pointer variables in high level programming languages constitutes an artifact originally introduced to support the representation of recursive data structures. Programming practice has come to rely on pointer variables for their originally intended use, and for several others as well. Their use adds to the complexity of stating algorithms by forcing one to conceptualize data representations in which storage addressing is made manifest. In addition, the use of pointer variables allows one to refer to a common data object by a multiplicity of names, a phenomenon we call the alias variable problem, Alias variables make the verification of program behavior substanially more difficult, and frustrate the goals of modular decomposition.

In this paper, we consider alternatives to the use of pointer variables in programming. One of these alternatives is the inclusion of a class of data abstractions based on recursively defined data types. The representational power of the proposed data types is characterized formally, and some issues of implementation and efficiency of programs are discussed.
On the use of bit maps for multiple key retrieval
Authors: Vallarino Oscar
Published: November 2005

The traditional file structures used to support fast response to complex user queries have been based on the inverted list organization, using either the pointer or bit string representation. In this paper, the use of bit maps for executing multiple key searches is studied. Bit maps turn out to be less precise inverted lists Where the inversion is kept for a quantization of attribute domains and the objects referenced are blocks of data records. The goal is to reduce the total number of I/O accesses required to execute a retrieval based on a Boolean qualification. An evaluation of the method is given for both storage space and expected retrieval time under simplified assumptions. Key Words and Phrases: Multiple key retrieval, inverted lists, bit strings, bit maps, Boolean queries, data base management. CR Categories: 3.70, 3.71, 3.73, 3.74, 4.33, 4.34
Correctness of data representations (Extended Abstract)
Authors: Berry D. M. , Erlich Z. , Lucena C. J.
Published: November 2005

At present, there is considerable debate whether, in light of what is being learned about construction of reliable software, pointers are desirable in high level programming languages. One side [Hoa73, Hoa75] maintains that

1) Pointers are like the goto in that they are an invitation to create spaghetti in one's program [Hoa75].

2) In some languages, e.g., PL/1 [Wlk71], the use of pointers can lead to serious type violations, for example, the compiler believes that a given pointer will be pointing to an integer when in fact, it will be pointing to a real.

3) The indiscriminate use of pointers may confound the attempts of hardware pipelining and use of cache memory to speed up computations [Hoa73, Hoa75].

4) A pointer may be left dangling, that is, a pointer may point to a variable or other datum which has been deallocated [Bry71, CDMPS73, Bry74].
DIAM II
Authors: Senko Michael E.
Published: November 2005

The notion of dividing complex problems into hierarchic levels of abstraction has a long history. Recently this approach under the name, structured programming, has been used in a pragmatic way to simplify the structure of procedural programs. The notion has also been used in the data base area - notable early papers include those of Madnick (1) and Meltzer (2). In these early papers, level structures (for example, involving logical and physical levels) were also relatively pragmatic creations.

One new aspect of the DIAM I architecture (3) was that it defined a detailed, relatively formal basis for four levels of abstraction and the mappings between these levels. Each level had a small set of primitive generalized building blocks, each with its own small permanent set of parameters. By specifying values for these parameters, the user could define essentially any reasonable data structure and file organization he wished for his stored information.
A high-level data manipulation language for hierarchical data structures
Authors: Housel Barron C. , Shu Nan C.
Published: November 2005

In this paper we assert that the hierarchical view of data will continue to be popular for a broad class of applications and users. In particular, some of these applications require complex data manipulation which, heretofore, has been dealt with procedurally. In this light, a nonprocedural language, CONVERT, is proposed as a high-level DBMS interface. CONVERT is meant to provide users with a tool for performing complex data manipulation and query of hierarchical data abstractions, called “Forms”. Included in the paper are a description of the Form data abstraction and the CONVERT language, as well as a complete illustrative sample application.
Visibility and types
Authors: Koster Cornelis H.A.
Published: November 2005

In this paper it is argued that there is a strong connection between the issue of abstract types and the more general issue of information hiding in large program systems, since abstraction has to be enforced by the careful and controlled hiding of details. In the first part of the paper, the notions of visibility and interface are discussed. In the second part, it is shown how, by careful control of visibility through interfaces, data abstraction can be achieved. Finally a comparison is made between this approach and the class approach.
The economics, politics, and sociology of two-dimensional systems
Authors: Klerer Melvin
Published: November 2005

The various factors contributing to the superiority of two-dimensional systems over linear programming systems in terms of their economic advantages is discussed. The failure of 2-D systems to affect current praxis is analyzed in terms of the social and political milieu that characterized computer science research during the previous decade.
Shape coefficients for polygons
Authors: Morrison D. R. , Allen R. C.
Published: November 2005

Functions are derived which quantify the shape of rectifiable simple closed curves, which form boundaries of black objects in a white background. The functions are products of coefficients in a Fourier series which defines a tracing of the curve. The functions are useful in describing the shape of a polygon which approximates a component of the boundary. They map curves into complex n-shape in such a way that commonly used descriptors such as “round”, “square”, “rectangular”, “symmetric” correspond to particular regions in n-space. The shape functions are all continuous in each corner of the polygon, so that polygons that are nearly identical are mapped into near-by points in n-space. Although there are a countably infinite set of shape functions, only a few are needed to recognize reasonably simple figures. Numerals can be recognized by evaluating three of the shape coefficients.
An extensible system for drawing block diagrams
Authors: Kulsrud H. E.
Published: November 2005

This paper describes a system whose purpose is to accept input in a variety of languages and to produce block diagrams, such as flowcharts, as output. A special feature of the system is its use of syntax directed compilation techniques to process the various input languages. Through the use of incremental compilation, the system is able to offer extensibility of modules as well as extensibility of the entire system. A number of graphic output devices can be utilized. This system has been used to draw flowcharts of programs written in an ALGOL type language, FORTRAN, and a special flowcharting language and draw other diagrams composed of connecting blocks.
PICASSO a general graphics modeling program
Authors: Holmes H. H. , Austin D. M.
Published: November 2005

A new two-dimensional graphics modeling program which has been fully implemented is introduced. Features include a generalized extendable graphics editor, an open-ended library of elements, a translator -macro processor for interface with a wide range of analysis routines, and on-line operating system control.
SCRATCHPAD
Authors: Griesmer James H. , Jenks Richard D.
Published: November 2005

SCRATCHPAD is an interactive system for algebraic manipulation available under the CP/CMS time-sharing system at Yorktown Heights. It features an extensible declarative language for the interactive formulation of symbolic computations. The system is a large and complex body of LISP programs incorporating significant portions of other symbolic systems.

Here we present a capsule view of SCRATCHPAD, its language and its capabilities. This is followed by an example which illustrates its use in an application involving the solution of an integral equation.
A report on the use of FORTRAN-coded EXPLOR for the teaching of computer graphics and computer art
Authors: Knowlton Ken
Published: November 2005

A FORTRAN-coded version of my EXPLOR language (for the production of images from
ex
plicit
p
atterns,
l
ocal
o
perations and
r
andomness) has been used to teach computer graphics and computer art to a collection of undergraduate students in art and computer science at the University of California at Santa Cruz. My conclusions are (1) that this particular language makes it possible for relatively inexperienced programmers readily to produce a wide variety of interesting designs, (2) that a rather significant scope and quality of computer graphics can be done with simply a line printer as the output device (other equipment became available during the program) and (3) that teaching of the important concepts of computing can be facilitated by the use of graphic output - i.e. graphics can be considered an effective approach to computing as well as vice versa.
Programming on a tablet
Authors: Anderson Robert H.
Published: November 2005

A new notation is proposed for program specifications hand-printed on an interactive data tablet. The notation represents control statements such as
do-end
and
if-then-else
by graphic symbols which allow the representation to be both more succinct and more easily readable. A translation algorithm is given for linearizing the two-dimensional display form of the notation into a traditional string language form for subsequent compilation and execution.
Implementation and applications of Scott's logic for computable functions
Authors: Milner Robin
Published: November 2005

The basis for this paper is a logic designed by Dana Scott [1] in 1969 for formalizing arguments about computable functions of higher type. This logic uses typed combinators, and we give a more or less direct translation into typed λ-calculus, which is an easier formalism to use, though not so easy for the metatheory because of the presence of bound variables. We then describe, by example only, a proof-checker program which has been implemented for this logic; the program is fully described in [2]. We relate the induction rule which is central to the logic to two more familiar rules - Recursion Induction and Structural Induction - showing that the former is a theorem of the logic, and that for recursively defined structures the latter is a derived rule of the logic. Finally we show how the syntax and semantics of a simple programming language may be described completely in the logic, and we give an example of a theorem which relates syntactic and semantic properties of programs and which can be stated and proved within the logic.
The definition and validation of the radix sorting technique
Authors: Lee John A. N.
Published: November 2005

Based on the formal definition techniques of Lucas et al
[1]
which have been applied to the description of programming languages, this paper defines the algorithm of radix sorting and develops a proof of its validity.
The equivalence of models of tasking
Authors: Berry Daniel M.
Published: November 2005

A technique for proving the equivalence of implementations of multi-tasking programming languages is developed and applied to proving the equivalence of the contour model and a multi-tasking version of the copy rule.
The “most recent” error
Authors: McGowan Clement L.
Published: November 2005

The notion of a general block structured programming language and the “most recent” evaluation strategy for such a language are formalized and their relationship investigated. Sufficient conditions for “most recent” correctness are obtained.
Babel, an application of extensible compilers
Authors: Scowen R. S.
Published: November 2005

The normal approach in providing an extensible programming language seems to be to design and implement a base language which has facilities enabling the programmer to define and use extensions. This paper discusses a solution using an alternative approach in which extensions are made by changing the compiler. Of course, in theory, any compiler can be altered (it is only a computer program); in practice it is probably not so easy since difficulties will arise if the compiler has been designed for one fixed standard language on one particular computer. If a compiler is to be altered, it must possess various properties; there should be no danger of accidentally invalidating an existing program, and it must be clear what changes are required to make a desired extension. It is also desirable that only a small number of changes should be required to make an extension.

The method of writing compilers which is described below satisfies these conditions and has been adopted in three different applications:-

(1) Babel, a conventional high level programming language.

(2) SOAP, a program which documents and edits an ALGOL 60 program.

(3) PL516, a high level assembly language for the Honeywell DDP516 computer.
A short presentation of the main features of AEPL - an extensible programming language
Authors: Katzenelson J. , Milgrom E.
Published: November 2005

AEPL is a programming system designed as a tool for the implementation of problem-oriented languages. It is based on a small number of simple but powerful concepts described briefly below.

The AEPL system is not yet implemented at the present time; it has been used, however, to define - on paper - a language for the manipulation of graphs. The extensibility of the system stems from the ability to create new data types and from the ability to modify some of the language structures dynamically (syntax and associated semantic as well as some control structures).
Macros in higher-level languages
Authors: Bowlden Henry J.
Published: November 2005

The concept of macros, as a tool to extend the expressive capability of a symbolic language by techniques of string substitution, has existed in the lexicon of programming languages for many years. It has been used most effectively in connection with assemblers; in some cases capabilities not too far short of the range commonly attributed to “higher-level languages” have been provided by this means. Attempts to extend higher-level languages by similar tools have, however, not been quite as well received. In this presentation we consider the lessons which have been learned in the course of a six-year experiment with a macro preprocessor for a dialect of ALGOL 60. The factors which we find of interest are those of user convenience, flexibility, efficiency, and syntactic integrity. We attempt to relate these, in the framework of our own experience, to the independent variables of base language power, user orientation, and design goals. It is not our purpose to arrive at any sweeping generalizations; rather, we will content ourselves with drawing tentative conclusions with respect to fruitful avenues of development from a rather limited base with the help of some specific examples.
Syntax translation with context macros or macros without arguments
Authors: Grant Charles A.
Published: November 2005

A conceptually language independent macro facility with the following properties is described here:

1)Each macro gathers its own arguments from the text in which the call is embedded (the context).

2) A macro may modify its context an arbitrary distance from the actual string which represents the call.

3) A macro may specify the precise point from which scanning is to continue after the macro returns.

The objective of this work is to define a simple user facility for conveniently and powerfully modifying the syntax of programming languages.