bluuebunny/crossref_metadata_2025 huggingface dataset:
The SCRATCHPAD language
Authors: Jenks R. D.
Published: November 2005

SCRATCHPAD is an interactive system for symbolic mathematical computation. Its user language, originally intended as a special-purpose non-procedural language, was designed to capture the style and succinctness of common mathematical notations, and to serve as a useful, effective tool for on-line problem solving. This paper describes extensions to the language which enable it to serve also as a high-level programming language, both for the formal description of mathematical algorithms and their efficient implementation.
Abstract data types in the Model programming language
Authors: Johnson Robert T. , Morris James B.
Published: November 2005

The concept of an abstract data type is available in the Model programming language as a proposed improvement to current ideas of programming methodology. In structured programming the principal technique is refinement of procedures. In Model, the analogue is refinement of data types. An abstract data type consists of a data structure and an associated set of operations. The characteristics and suggested uses for this mechanism are discussed. Also presented are several examples culminating in a parallel version of the Fast Fourier Transform.
High level domain definition in a relational date base system
Authors: McLeod Dennis J.
Published: November 2005

A relational data base is herein defined as a collection of normalized relations (relations in first normal form) and a collection of domains. A normalized relation may be viewed as a table, wherein each row of the table corresponds to a tuple of the relation, and the entries in a given column belong to the set of values constituting the domain underlying that column. The domains of a data base have an abstract existence apart from the data base relations.

The data base also includes various types of semantic integrity rules, which specify additional properties of the data in the data base. One such type of semantic integrity rule is the domain definition. A domain definition includes the precise description of the set of values (objects) constituting the domain. In a normalized data base, all domains are sets of atomic data values. A domain definition also includes a specification of the ordering on the values in a domain, for comparability purposes. In addition, a domain definition contains a specification of the action that is to occur if an attempt is made to violate the restriction that every entry in each column of a relation must be from the underlying domain of that column.

A nonprocedural language permitting the high level expression of domain definitions is defined. Language details and examples are presented, and the syntax and informal semantics of the domain definition language are given. This approach to domain definition is analyzed in terms of its impact on other aspects of data base semantic integrity. The relationship with the data base system in general is outlined. An analysis of intradomain and interdomain comparability is included. An introduction to relevant implementation issues is also presented. Emphasis is placed on a general approach to implementation and implementation techniques, rather than on a specific system.
From information requirements to DBTG-data structures
Authors: Bubenko J. A. , Berild S. , Lindencrona-Ohlin E. , Nachmens S.
Published: November 2005

The problem of determining, analysis and description of a particular application's information structure (and relations) and the process of mapping the information structure to a “good” data structure (in this case a DBTG-type structure) is considered. The applicability of a top-down oriented design procedure to a relatively large practical data base design case is demonstrated. A conceptual framework and a notation to be used for determining and definition of information requirements, information structure and information relations is suggested. A systematic and partly formalized approach to map an information structure to a DBTG-type data structure is discussed. The problem of analysis and evaluation of alternative DBTG-type structures is also considered.
A technique for implementing a set processor
Authors: Hardgrave W. T.
Published: November 2005

Extended set theory is an effective method for describing the complex data structures needed to support large-scale data base applications. This paper describes the incorporation of the salient concepts of extended set theory into a general tool for the design and implementation of large-scale database systems. This tool is called a set processor. This implementation is based on the representation of sets of positive integers as bit strings and the application of the Cauchy/Cantor Diagonal Method.
Some ideas on data types in high level languages
Authors: Gries David , Gehani Narain
Published: November 2005

We explore some new and old ideas concerning data types; what a data type is, overloading operators, when and how implicit conversions between programmer data types should be allowed and so forth. The current notion that a data type is a set of values
together
with basic operations on that set leads us to conclude that formal parameter types need not be so explicitly stated. Given a formal parameter X with operations σ
1
,...,σ
n
being performed on X within a procedure, one should be able to supply, as actual parameters in a call, a variable of any type which has operations σ
1
,...,σ
n
defined on it. We introduce a notation for this, using PASCAL as a base language, illustrate the added flexibility it gives us, and show briefly how to implement the idea efficiently.
Abstract types defined as classes of variables
Authors: Parnas D. L. , Shore John E. , Weiss David
Published: November 2005

The concept of “type” has been used without a precise definition in discussions about programming languages for 20 years. Before the concept of user defined data types was introduced, a definition was not necessary for discussions of specific programming languages. The meaning of the term was implicit in the small list of possible types supported by the language. There was even enough similarity between different languages so that this form of definition allowed discussions of languages in general. The need for a widely accepted definition of type became clear in discussions of languages that allow users to add to the set of possible types without altering the compiler. In such languages, the concept of type is no longer implicitly defined by the set of built-in types. A consistent language must be based on a clearer definition of the notion of type than we now have.
Graphical systems and two-dimensional mathematical expressions
Authors: George James E.
Published: November 2005

The additional facilities needed to generate two-dimensional mathematical expression displays and their implications to a graphical language system are discussed and result in a linguistic based graphical system. An elementary mathematical expression display system is used to motivate and illustrate these additional facilities and is defined utilizing a linguistic based graphical meta system. The use of the elementary system is illustrated for the evaluation of expressions, the display of expressions on different display devices and the use of the entire elementary system by a text formatting program to produce linear and two-dimensional text.
GRAPHOS
Authors: Lazik George L.
Published: November 2005

A system is presented which translates two-dimensional syntax into a one-dimensional form. The concept of a macro is extended so as to be applicable to these two-dimensional forms. The translation process is controlled by a set of user-defined graphical-macros or “graphos”. These graphos are interactively defined on a graphics terminal and placed in a set of master tables. Two-dimensional expressions are then constructed on the graphics terminal. The system translates these expressions by interpreting the user's grapho definitions. These definitions specify the final form of the output which is one-dimensional text suitable as source input to a higher-level language processor. The organization of the GRAPHOS system is discussed, and examples of grapho definitions and their expansions are presented.
The two-dimensional interface of an interactive system for molecular studies
Authors: Wright W. V.
Published: November 2005

The man-machine interface of a special-purpose interactive system for modeling protein molecules is described. This interface makes use of two-dimensional communication via a vector graphic display unit.
Inductive methods for proving properties of programs
Authors: Manna Zohar , Ness Stephen , Vuillemin Jean
Published: November 2005

We have two main purposes in this paper. First, we clarify and extend known results about computation of recursive programs, emphasizing the difference between the theoretical and practical approaches. Secondly, we present and examine various known methods for proving properties of recursive programs. We discuss in detail two powerful inductive methods, computational induction and structural induction, illustrating their applications by various examples. We also briefly discuss some other related methods.

Our aim in this work is to introduce inductive methods to as wide a class of readers as possible and to demonstrate their power as practical techniques. We ask the forgiveness of our more theoretical-minded colleagues for our occasional choice of clarity over precision.
Program correctness methods and language definition
Authors: Ashcroft E. A.
Published: November 2005

The development of the method of proving correctness of programs is considered in relation to methods of defining programming languages. Informal methods are given for checking proposed adaptations of the correctness method to new programming languages. It is shown how correctness-formulae can be considered as semantic definitions of programs, and how Burstall's logical language definitions can be considered as correctness formulae.
Decision problems in computational models
Authors: Paterson Michael S.
Published: November 2005

Some of the assertions about programs which we might be interested in proving are concerned with correctness, equivalence, accessibility of subroutines and guarantees of termination. We should like to develop techniques for determining such properties efficiently and intelligently wherever possible. Though theory tells us that for a realistic programming language almost any interesting property of the behaviour is effectively undecidable, this situation may not be intolerable in practice. An unsolvability result just gives us warning that we may not be able to solve all of the problems we are presented with, and that some of the ones we can solve will be very hard.

In such circumstances it is very reasonable to try and determine necessary or sufficient conditions on programs for our techniques to be assured of success; however, in this paper we shall discuss a more qualitative, indirect, approach. We consider a range of more or less simplified computer models, chosen judiciously to exemplify some particular feature or features of computation. A demonstration of unsolvability in such a model reveals more accurately those sources which can contribute to unsolvability in a more complicated structure. On the other hand a decision procedure may illustrate a technique of practical use. It is our thesis that this kind of strategy of exploration can and will yield insight and practical advances in the theory of computation. Provided that the model retains some practical relevance, the dividends are the greater the nearer the decision problem lies to the frontier between solvability and unsolvability.
Operational semantics of programming languages
Authors: Wegner Peter
Published: November 2005

A framework is developed for the operational characterization of the semantics of computational formalisms such as programming languages, digital computers and automata. Operational semantics is contrasted with input-output semantics and it is shown that input-output semantics is inappropriate to the study of certain important implementation-dependent attributes of computational formalisms. Notions of equivalence are developed for a very general class of operational models called information structure models. The structure of proofs of compiler correctness and interpreter equivalence is discussed independently of the form of the states and state transitions of a specific interpreter. These techniques are then applied to defining a correctness criterion for block structure implementations and to correctness proofs of interpreters for block structure languages.
Calculating properties of programs by valuations on specific models
Authors: Sintzoff Michel
Published: November 2005

The proof that a program verifies some property is carried out by the valuation of the program in a model characterizing that property. Specific models are given for sufficient conditions of the correctness of types, locations and asynchronous computations; a hypothetical programming language is used, which includes functions and locations and allows their recursive composition. The application of the method in studying termination or correctness problems is discussed on particular programs.
On a laboratory for the study of automating programming
Authors: Cheatham T. E. , Wegbreit Ben
Published: November 2005

At the present time there is considerable interest in the general question of “automating programming:” there are a number of people actively doing research concerned with various aspects of the question and even a few projects exploring various practical issues via experimental implementations. The area encompassed by “automating programming” is a very broad one, particularly if one understands “programming” to include the entire spectrum of activities concerned with producing algorithms which are correct and effective in terms of certain design specifications. It is therefore to be expected that comparison of various techniques and integration of those techniques and the experimental facilities developed in a variety of institutions will be difficult and expensive unless there is some coordinated effort to provide a common framework to support such activities. We would note that at present it is relatively expensive just to construct sufficient programs to permit the investigation of and experimentation with some proposed technique of program automation; because of this many studies in the general area of programming automation are primarily “paper studies”.

It is the purpose of this note to provide an overview of the project currently under way at Harvard's Center for Research in Computing Technology, directed toward the implementation of a laboratory for the study of programming automation techniques. A more detailed discussion of our approach is provided in [1]. In the four sections which follow we will discuss briefly our view of the use of a program automation laboratory, the basis for and basic components of the facility currently being implemented, and finally, suggest that there are a variety of research areas which are strongly related to the question of automating programming in which the laboratory might be employed as a research tool.
The implementation of ALGOL N
Authors: Suzuki N. , Fujisaki T. , Kakehi K. , Wada E. , Simauti T.
Published: November 2005

Recent expansion of new techniques invented a great number of application areas in which computers are used in the ways which have not been dreamed of a decade ago. Since the usage of computers was controlled by programs stored in computers, the production of programs has been increasing in enormous rate. In order to ease programming efforts, many programming devices have been invented and organized to become an operating system and a programming system. Nowadays the operating system serves as an interface between the hardware and the programming system or a programmer. They are designed as a multipurpose program so as to be able to handle any usage of the computer. The programming system is, on the other hand, the tool for the programmer to make a program. It serves as an interface between a programmer and the operating system or the hardware. Since there are peculiar notions in each application area, different programming languages are invented for each application area so that programs become short and easy to write. The nucleus of the programming system is the language processor, so the programming system is expanding in terms of language processors. It now becomes necessary to find an easy way to create programming systems which can be expanded easily.

There are three main approaches to resolving this problem. The first approach is to make a universal language and to write all programs in this language. Only one language processor is necessary for one computer. But this has never been realized. PL/I is supposed to serve as a higher programming language version of a universal language. The second approach is to make one compiler-compiler and to generate all compilers for different programming languages by that compiler-compiler. Strong tools for defining the syntax of the language already exist, but it is still not easy to define semantics. So it is very difficult to generate a good compiler with a good optimization facility. The third approach, now becoming more attractive, is the attempt to make a language extensible. An extensible language is the language which can introduce new syntax, practically in the form of operators, and new data structures. So if a programmer wants special operators and data structures, he can declare them before the program and can program in terms of them. This approach is promising since the programmer can make a program constructively.
Grammatical inference for defining extensions
Authors: Reghizzi S. Crespi
Published: November 2005

Extensions to a language need be defined by a grammar, or by any conceivable method which is apt to discriminate valid from unwanted extensions and to provide efficient parsing and translation.

Context-free grammars - a traditional choice - have a major drawback with respect to practical use. Namely, the unsophisticated user of an extensible system would find it hard to formulate an appropriate BNF definition of the constructions he wants.
Syntactic definition mechanisms
Authors: Gils Teun van
Published: November 2005

The structure of a good syntax is derived from the requirement to understand and therefore to analyse a language easily. Every language possesses an abstract, representation-independent syntax. From this the operator precedence method and other complementary or alternative methods of analysis are deduced. It is possible to construct syntactic definition mechanisms by means of which for any abstract syntax different concrete languages can be defined, which are concise, surveyable, unambiguous and easily analysable. Incorporated in a programming language these syntactic definition mechanisms make that language syntactic extensible.
Transition functions
Authors: Leavenworth B. M.
Published: November 2005

Syntactic extension methods (see, for example (5)) usually involve the following steps:

(1) recognize a syntactic pattern in the program and find its (string) parameters

(2) call the appropriate string function, substituting actual for formal parameters

(3) execute the result of the string function

The specification of syntactic extensions results in modifying the translator incrementally. We will not be further concerned with syntactic extensions in this paper.
Interpreter/compiler integration in ECL
Authors: Holloway Glenn H.
Published: November 2005

As mentioned in [1], a primary design objective of the ECL programming system [2, 3] has been to maximize the flexibility afforded its user, particularly during the design and debugging of his programs, without sacrificing the efficiency of his final product. The programmer is given the facility first to tailor the system to his needs, then to shed unneeded variability in exchange for increased efficiency.

To this end, ECL includes both an interpreter and a compiler for the language EL1. The integration of two compatible language processors in a single system is achieved with a minimum of duplicate syntactic or semantic analysis.
Application of extensible languages to specialized application languages
Authors: Sammet Jean E.
Published: November 2005

It is becoming increasingly clear that one of the major thrusts of the programming language field is in the direction of specialized application languages - sometimes called special purpose languages. These specialized application languages have already been developed for such diverse fields as civil engineering, electrical engineering, computer assisted instruction, systems programming, equipment checkout, movie animation, etc. Of the roughly 165 languages currently in use in the United States, approximately 85 of them might be classified as specialized. (See the list in Reference 1.) For description and illustration of many of these, see Chapter 9 in Reference 2.

All languages are applications oriented. In fact, this is probably the best way to categorize the set of programming languages. However, some application areas are obviously larger than others, e.g., scientific computation (numeric and non-numeric) and business data processing. The main concern here is with the more specialized languages. While each person may have a different idea of what the categories of specialization should be, there can be little dispute about the wide diversity and large number of them.
PPL - an extensible language that failed
Authors: Standish Thomas A.
Published: November 2005

PPL, a conversational extensible language, has been running on the DEC PDP-10 for over a year now. Its applications have included: matrix, vector, polynomial, rational and complex arithmetic; formula, list, string, tree and graph manipulation; significant programs in real-time radar air traffic control simulation and parser generation for context-free languages; and a host of useful conversational tasks in population biology, algebra word problems and optimization of programs. Indeed, the parser for another extensible language(ECL) was generated in PPL(using the De Remer algorithm). PPL is now used by over 450 students in Harvard's introductory programming course. Needless to say, for me and a number of others, PPL is the preferred medium for writing programs and serves as an important and enjoyable tool of thought. To me, PPL is rich, highly versatile and easy to use As is the case for most other languages, PPL evokes both adoring remarks from its proponents and the usual scorn from its detractors. In analogy to the process of stellar evolution, if there is such a thing as a “main sequence” for the life of programming languages, PPL seems well launched on it (though programming languages probably die by fizzling out, not by exploding).

Yet PPL is a failure. A few years ago, the vision of extensible languages held by some was that users could rapidly and cheaply extend the base of an extensible language to encompass the data, the operations, the notation and the control natural to many diverse application areas. In short, one was supposed to be able to manufacture personalized languages of reasonable efficiency and substantial utility with great ease just by applying some easily learned extension techniques. It was thought that just as programmers decree the organization of processes (by defining and calling subroutines),they should also decree appropriate organizations for data and for notation, in order to attain more clarity and efficiency.
The programming language PS440 as a tool for implementing a time-sharing system
Authors: Sapper Gerd R.
Published: November 2005

The use of assembly language for the programming of basic software of a large operating system often proves inflexible and impractical. Writing the programs in assembly language is time-consuming and expensive. Furthermore, the programs are hard to read and difficult to modify. Nevertheless, assembly languages have facilities which must be preserved when higher level programming languages are to be used for basic software. A programming language, “PS440”, is described which provides many of the advantages of higher level languages while at the same time maintaining some needed facilities of assembly language.
Reflections on a systems programming language
Authors: Wulf W. , Geschke C. , Wile D. , Apperson J.
Published: November 2005

A particular systems implementation language, Bliss, has been in active use at Carnegie-Mellon for over two years. At this point the language has been used for several compilers, a conversational programming system, an i/o support system, a discrete event simulation system, and other diverse applications. The authors, together with others, have been responsible for the design, implementation, evolution, and evaluation of the language. Drawing on the past two years' experience this paper attempts a critical evaluation of the language - its failures as well as its successes - with an eye toward the development of future systems implementation languages.
Inferred syntax and semantics of PL/S
Authors: Wiederhold Gio , Ehrman John
Published: November 2005

This is an attempt to describe a language developed and used by IBM Corporation to support the writing of system programs. It is a PL/1-like language specifically oriented towards the kind of operations required In writing operating systems.

The language was referred to originally as BSL, and is now called PL/S. By March 1971 development had proceeded to a version numbered 12.11. I t is this and shortly preceding versions that are described here.
Formal definition of programming language standards
Authors: Pronk C. , Schönhacker M.
Published: November 2005

This short note emphasizes the long standing use of formal techniques for the definition of programming languages.
Migration of enterprise JavaBeans with ProActive Interposition Objects
Authors: Xu Baomin , Lian Weimin , Gao Qiang
Published: November 2005

This paper presents a kind of distribution support, component migration, which is not supported by the currently available component infrastructure such as CORBA, EJB. All this is done in scalable and secure way based-on ProActive Interposition Objects. The biggest strength of our implementation is that the details of migration are completely hidden from the application programmer. The potential importance of component migration is to gain improved performance and flexibility of distributed applications via dynamic load balancing and dynamic deployment of distributed applications.
Templates-based portable just-in-time compiler
Authors: Iliasov Alex
Published: November 2005

Usage of the platform-neutral bytecode interpreters is often limited by their restricted performance. Just-in-time compilers effectively solve this problem. However they are hard to develop and retarget. This paper demonstrates that dynamic code generation from the templates created by a C compiler can be used to build a simple and highly-portable JIT compiler.
Discriminative sum types locate the source of type errors
Authors: Neubauer Matthias , Thiemann Peter
Published: November 2005

We propose a type system for locating the source of type errors in an applied lambda calculus with ML-style polymorphism. The system is based on discriminative sum types---known from work on soft typing---with annotation subtyping and recursive types. This way, type clashes can be registered in the type for later reporting. The annotations track the potential producers and consumers for each value so that clashes can be traced to their cause.Every term is typeable in our system and type inference is decidable. A type derivation in our system describes all type errors present in the program, so that a principal derivation yields a principal description of all type errors present. Error messages are derived from completed type derivations. Thus, error messages are independent of the particular algorithm used for type inference, provided it constructs such a derivation.
Compiling regular patterns
Authors: Levin Michael Y.
Published: November 2005

Pattern matching mechanisms based on regular expressions feature in a number of recent languages for processing tree-structured data such as XML. A compiler for such a language must address not only the familiar problems of pattern optimization for ML-style algebraic datatypes and pattern matching, but also some new ones, arising principally from the use of recursion in patterns. We identify several factors playing a significant role in the quality of the generated code, propose two pattern compilers---one generating backtracking target programs, the other non-backtracking---and sketch proofs of their correctness.
Software is discrete mathematics
Authors: Page Rex L.
Published: November 2005

A three-year study collected information bearing on the question of whether studying mathematics improves programming skills. An analysis of the data revealed significant differences in the programming effectiveness of two populations of students: (1) those who studied discrete mathematics through examples focused on reasoning about software and (2) those who studied the same mathematical topics illustrated with more traditional examples. Functional programming played a central role in the study because it provides a straightforward framework for the presentation of concepts such as predicate logic and proof by induction. Such topics can be covered in depth, staying almost entirely within the context of reasoning about software. The intricate complexities in logic that mutable variables carry with them need not arise, early on, to confuse novices struggling to understand new ideas. In addition, because functional languages provide useful and compact ways to express mathematical concepts, and because the choice of notation in mathematics courses is often at the discretion of the instructor (in contrast to the notational restrictions often fiercely guarded by the faculty in programming courses), discrete mathematics courses, as they are found in most computer science programs, provide an easy opportunity to enhance the education of students by exposing them to functional programming concepts.
Dynamic rebinding for marshalling and update, with destruct-time ?
Authors: Bierman Gavin , Hicks Michael , Sewell Peter , Stoyle Gareth , Wansbrough Keith
Published: November 2005

Most programming languages adopt static binding, but for distributed programming an exclusive reliance on static binding is too restrictive: dynamic binding is required in various guises, for example when a marshalled value is received from the network, containing identifiers that must be rebound to local resources. Typically it is provided only by ad-hoc mechanisms that lack clean semantics.In this paper we adopt a foundational approach, developing core dynamic rebinding mechanisms as extensions to simply-typed call-by-value ? -calculus. To do so we must first explore refinements of the call-by-value reduction strategy that delay instantiation, to ensure computations make use of the most recent versions of rebound definitions. We introduce
redex-time
and
destruct-time
strategies. The latter forms the basis for a ?
marsh
calculus that supports dynamic rebinding of marshalled values, while remaining as far as possible statically-typed. We sketch an extension of ? marsh with concurrency and communication, giving examples showing how wrappers for encapsulating untrusted code can be expressed. Finally, we show that a high-level semantics for dynamic updating can also be based on the destruct-time strategy, defining a ?
marsh
calculus with simple primitives to provide type-safe updating of running code. We thereby establish primitives and a common semantic foundation for a variety of real-world dynamic rebinding requirements.
Dependency-style generic haskell
Authors: Löh Andres , Clarke Dave , Jeuring Johan
Published: November 2005

Generic Haskell is an extension of Haskell that supports the construction of generic programs. During the development of several applications, such as an XML editor and compressor, we encountered a number of limitations with the existing (Classic) Generic Haskell language, as implemented by the current Generic Haskell compiler. Specifically, generic definitions become disproportionately more difficult to write as their complexity increases, such as when one generic function uses another, because recursion is implicit in generic definitions. In the current implementation, writing such functions suffers the burden of a large administrative overhead and is at times counter-intuitive. Furthermore, the absence of type checking in the current implementation can make Generic Haskell hard to use.In this paper we develop the foundations of
Dependency-style Generic Haskell
which addresses the above problems, shifting the burden from the programmer to the compiler. These foundations consist of a full type system for Dependency-style Generic Haskell's core language and appropriate reduction rules. The type system enables the programmer to write generic functions in a more natural style, taking care of dependency details which were previously the programmer's responsibility.
Functional automatic differentiation with dirac impulses
Authors: Nilsson Henrik
Published: November 2005

Functional Reactive Programming (FRP) is a framework for reactive programming in a functional setting. FRP has been applied to a number of domains, such as graphical animation, graphical user interfaces, robotics, and computer vision. Recently, we have been interested in applying FRP-like principles to hybrid modeling and simulation of physical systems. As a step in that direction, we have extended an existing FRP implementation,
Yampa
, in two new ways that make it possible to express certain models in a very natural way, and reduces the amount of work needed to put modeling equations into a suitable form for simulation. First, we have added
Dirac impulses
that allow certain types of discontinuities to be handled in an easy yet rigorous manner. Second, we have adapted
automatic differentiation
to the setting of Yampa, and
generalized
it to work correctly with Dirac impulses. This allows derivatives of piecewise continuous signals to be well-defined at all points. This paper reviews the basic ideas behind automatic differentiation, in particular Jerzy Karczmarczuk's elegant version for a lazy functional language with overloading, and then considers the integration with Yampa and the addition of Dirac impulses.
A static type system for JVM access control
Authors: Higuchi Tomoyuki , Ohori Atsushi
Published: November 2005

This paper presents a static type system for JAVA Virtual Machine (JVM) code that enforces an access control mechanism similar to the one found, for example, in a JAVA implementation. In addition to verifying type consistency of a given JVM code, the type system statically verifies that the code accesses only those resources that are granted by the prescribed access policy. The type system is proved to be sound with respect to an operational semantics that enforces access control dynamically, similarly to JAVA stack inspection. This result ensures that "well typed code cannot violate access policy." The paper then develops a type inference algorithm and shows that it is sound with respect to the type system and that it always infers a minimal set of access privileges. These results allows us to develop a static system for JVM access control without resorting to costly runtime stack inspection.
Boxes go bananas
Authors: Washburn Geoffrey , Weirich Stephanie
Published: November 2005

Higher-order abstract syntax is a simple technique for implementing languages with functional programming. Object variables and binders are implemented by variables and binders in the host language. By using this technique, one can avoid implementing common and tricky routines dealing with variables, such as capture-avoiding substitution. However, despite the advantages this technique provides, it is not commonly used because it is difficult to write sound elimination forms (such as folds or catamorphisms) for higher-order abstract syntax. To fold over such a datatype, one must either simultaneously define an inverse operation (which may not exist) or show that all functions embedded in the datatype are parametri.In this paper, we show how first-class polymorphism can be used to guarantee the parametricity of functions embedded in higher-order abstract syntax. With this restriction, we implement a library of iteration operators over data-structures containing functionals. From this implementation, we derive "fusion laws" that functional programmers may use to reason about the iteration operator. Finally, we show how this use of parametric polymorphism corresponds to the Schürmann, Despeyroux and Pfenning method of enforcing parametricity through modal types. We do so by using this library to give a sound and complete encoding of their calculus into System F
?
. This encoding can serve as a starting point for reasoning about higher-order structures in polymorphic languages.
Meta-programming through typeful code representation
Authors: Chen Chiyan , Xi Hongwei
Published: November 2005

By allowing the programmer to write code that can generate code at run-time, meta-programming offers a powerful approach to program construction. For instance, meta-programming can often be employed to enhance program efficiency and facilitate the construction of generic programs. However, meta-programming, especially in an untyped setting, is notoriously error-prone. In this paper, we aim at making meta-programming less error-prone by providing a type system to facilitate the construction of correct meta-programs. We first introduce some code constructors for constructing typeful code representation in which program variables are replaced with deBruijn indices, and then formally demonstrate how such typeful code representation can be used to support meta-programming. The main contribution of the paper lies in recognition and then formalization of a novel approach to typed meta-programming that is practical, general and flexible.
Simplifying ADA by removing limitations
Authors: Boute Raymond T.
Published: November 2005

As presently proposed, ADA contains several rather arbitrary restrictions making the language unnecessarily complex, lacking in orthogonality and difficult to extend. This note illustrates how the elimination of such restrictions yields a simpler yet more powerful language. Particular topics are the following. A more flexible and natural interpretation of type equivalence removes the stringent limitations of the ADA name equivalence approach. Providing a uniform view on types, subprograms and modules solves most parameterization problems and dispenses with the need for a "generic" construct. Finally, a more complete specification for subprograms (and modules) removes some difficulties with side-effects and exception handling.
The external consistency of abstract data types
Authors: Silberschatz A. , Kieburtz R. B.
Published: November 2005

In the definition of an abstract data type, much attention is given to specifying how instances of the type are to behave when they are used as intended. Such specifications are used to guide the choice of a representation for the type, and to verify that an implementation is correct. An equally important task, but one that has been relatively overlooked until now, is to specify clearly what are the circumstances of intended use of the type. These specifications must also be made use of if one is to certify that an implementation will produce the behavior that is anticipated. This paper addresses the specification of the environment and the mode of use to be made of instances of an abstract type, and shows how these can be incorporated into the type definition itself.
Structured programming is reductionistic!
Authors: Crowley Charles
Published: November 2005

It is not necessary to define structured programming in detail, but allow me to characterize it in terms that will be useful later. Structured programming is a way to reduce the complexity of the programming process by several means. First, it limits the allowed control structures to sequencing, looping, and alternation. These structures all have the property of one input and one output. Closely related to this is the idea of block structure, or localization of actions that are only relevant to a particular part of the computation. Similarly connected is the idea of closed subroutines and modules which do specific functions and can be understood independently of the context of the program in which they appear.
A new modula compiler for the LSI-11
Authors: Mahjoub Ahmed
Published: November 2005

This note contains a brief description of a new Modula compiler developed at Philips Laboratories. The compiler generates code for the LSI-11 microprocessor. It is written in Pascal and operates under control of the U.C.S.D. system. Philips Laboratories Modula (PL Modula) differs slightly from original Modula as defined by Wirth. These differences are outlined in section 3.
Functions for manipulating floating-point numbers
Authors: Reid J. K.
Published: November 2005

Floating-point arithmetic is used for most scientific and engineering calculations and needs frequently arise for determining the precision of a given floating-point number, for detailed access to its component parts and for reconstructing it from its parts, much as for complex numbers. We give detailed definitions of three suitable functions in the hope that their wide use will enhance portability. They are first given without reference to any particular language and then made specific to Fortran.This note has been discussed by IFIP WG 2.5 on Numerical Software and has been approved by the working group, but does not constitute an official IFIP document.
Comments on ADA process communication
Authors: van den Bos Jan
Published: November 2005

In this note a brief overview of the process communication primitives in ADA is followed by a critical review of the facilities. Where applicable suggestions for improvement are given.
Some common misconceptions about Lucid
Authors: Ashcroft Ed , Wadge Bill
Published: November 2005

This paper attempts to clear up several misconceptions about the language Lucid. In the process we claim that Lucid is in fact a real programming language, and indicate various ways in which implementations might be feasible.
An experience with parallelism in Ada
Authors: Notkin David S.
Published: November 2005

One of the more interesting and controversial features of Ada is the tasking structure. The Ada tasking facility provides high level mechanisms for communication and synchronization among tasks executing in parallel. The open question about these mechanisms is whether they provide programmers with both the appropriate level of abstraction and also the necessary level of control.This paper describes in detail the implementation of a system using parallelism that was written during the Ada test and evaluation process.
Overloading in preliminary Ada
Authors: Persch Guido , Winterstein Georg , Dausmann Manfred , Drossopoulou Sophia
Published: November 2005

Ada permits the overloading of enumeration literals, aggregates, subprograms and operators, i.e. the declaration of the same designator with different meanings in the same scope. This leads to difficulties during the semantic analysis of expressions and subprogram calls. For selecting the meaning not only the designator but also the types of its operands or parameters and the type of its result must be used. We show that the identification of expressions is possible in two passes, the first bottom-up, the second top-down.
Type resolution in Ada
Authors: Belmont Peter A.
Published: November 2005

Various features of Ada [Ichbiah 79, Honeywell 80] make type resolution an interesting and difficult as implemented in a semantic analyzer for Ada built in 1979--80.First, a straightforward algorithm, similar to that of Ganzinger and Ripken [Ganzinger 80], is discussed. Next an optimized version of this algorithm is presented.The optimization is based on the idea that, in a tree-walking analysis in which the information developed on one branch can affect the analysis elsewhere, and where the difficulty of analysis is not uniform, analysis should be performed a little at a time wherever it is most likely to be useful rather than according to any data-independent, pre-planned method such as bottom-up or top-down. This raises the likelihood that the analysis of "simple" branches will occur early and so ease the computational cost of analyzing the more difficult branches.
A flexible semantic analyzer for Ada
Authors: Sherman Mark S. , Borkan Martha S.
Published: November 2005

A technique for writing semantic analysis phases of compilers is described. The technique uses Simula classes and virtual procedures to create a flexible and modular program.The technique is used to implement a semantic analysis phase of a compiler front end for the preliminary Ada language. Because the design is extremely flexible and modular, the front end is able to accommodate changes in the Ada language and its semantics as they are publishedSeveral problems were encountered when implementing Ada's semantics. These problems are described and their solutions presented.The front end also produces TCOL
Ada'
the specified intermediate language for various Ada compiler contracts. This output has been used by an experimental compiler back end. [9]The front end is written as two programs which perform lexical analysis, syntactic analysis, semantic analysis, and TCOL
Ada
generation. The front end is coded in Simula, and has been runnig on DEC Tops-10 and Tops-20 systems since September 1979.
Evolving toward Ada in real time systems
Authors: MacLaren Lee
Published: November 2005

The Ada view of multitasking represents a radical departure from the traditional "cyclic executive" approach to real time operating systems. Since system designers must by necessity be conservative, it would be unrealistic to expect an abrupt change of this magnitude in engineering practice. Instead, this paper outlines a sequence of intermediate steps designed so that the advantages and familiar structures of cyclic systems may be retained, while the capabilities of Ada multitasking are gradually incorporated. A scale of increasing scheduling complexity provides the justification for this sequence. the discussion of each step then briefly mentions some of the related benefits and costs. The paper draws some conclusions about the use of Ada in real time systems.
The rendezvous and monitor concepts
Authors: Eventoff W. , Harvey D. , Price R. J.
Published: November 2005

The efficiency of Ada's rendezvous concept is compared with Concurrent Pascal's monitor concept. The differences between the two approaches, as well as a number of issues relating to their implementation, are presented. The results indicate that a concurrent programming language should provide both types of concepts.
On a formal model of the tasking concept in Ada
Authors: Løvengreen Hans Henrik , Bjørner Dines
Published: November 2005

This paper describes the August 1980 state of the development of a formal model of the Ada tasking concept. The model is being developed at the Department of Computer Science, Technical university of Denmark in collaboration with the Danish Datamatics Centre as part of a full Ada compiler development project summarized below. The paper includes a short characterization of the (present) tasking concepts in Ada on which the model is based. The model description is rather informal to let you have a idea about the modelling principles. In appendix A a detailed example is given, unfolding the course of a rendezvous. The paper ends with a sketch of how an implementation can be systematically derived from the formal model.
APL and Algo168, the correspondence and the differences, especially in applications of graph-analysis
Authors: Siero P. L. J.
Published: November 2005

In this presentation the characteristics of both languages will be presented. Typical features and facilities of Algo168 will be compared with the most important facilities of APL. Some other complicated features of Algo168 are considered and their possibilities for applications.Applications in the field of graph theory have been coded for the two languages.