A type-safe embedding of SQL into Java using the extensible compiler framework J%

J% is an extension of the Java programming language that efficiently supports the integration of domain-specific languages. In particular, J% allows the embedding of domain-specific language code into Java programs in a syntax-checked and type-safe manner. This paper presents J%׳s support for the sql language. J% checks the syntax and semantics of sql statements at compile-time. It supports query validation against a database schema or through execution to a live database server. The J% compiler generates code that uses standard jdbc api calls, enhancing runtime efficiency and security against sql injection attacks.     

Stress testing of compilers for modula-2

During standardization discussions on Modula-2 the question was raised whether the future standard should need a clause stating a set of minimal requirements for conforming implementations regarding the ‘structuredness’ of lexical, syntactical and run-time constructs in programs written in this language. It was decided to test a number of compilers to find their actual limits on the structuredness of some of these constructs. The test results do not only show these limits, but the inability of some compilers to handle large and complex inputs is shown as well.     

The definition of comments in programming languages

This paper examines the concept of comments in programming languages and answers the questions: Why are they needed? How are they defined and implemented in existing languages? What should be provided in future languages?     

Union and intersection types to support both dynamic and static typing

Although static typing provides undeniable benefits for the development of applications, dynamically typed languages have become increasingly popular for specific scenarios. Since each approach offers different benefits, the StaDyn programming language has been designed to support both dynamic and static typing. This paper describes the minimal core of the StaDyn programming language. Its type system performs type reconstruction over both dynamic and static implicitly typed references. A new interpretation of union and intersection types allows statically gathering the type information of dynamic references, which improves runtime performance and robustness. The evaluation of the generated code has shown how our approach offers an important runtime performance benefit.     

Distinguishing redundant parentheses by syntax

We give a generalized formal schema for designing a context free expression grammar that distinguishes required parentheses from redundant parentheses by means of formal syntax alone. The method applies to expression grammars having binary operators at any number of precedence levels, each level having any number of operators and being either left-associative, right-associative, or (syntactically) non-associative. We give proofs of correct parsing, unambiguity, LR(1)-ness, and the distinction of redundant parentheses. The resulting grammars appear to be LALR(1).     

Producing the left parse during bottom-up parsing

Schmeiser and Barnard described a method for producing the left parse at the end of the bottom-up parsing process. We improve their method in the sense that the left parse is actually produced during the bottom-up parsing process (i.e., with considerably less delay).     

A portable lisp compiler

The programming language LISP is usually implemented via an interpreter, and a compiler is added later as a LISP program. However, all such production compilers known to the authors produce explicit instructions for the given computer being used. This paper describes the development of a portable LISP compiler in the sense that only Standard LISP functions are used in its definition and the output is a sequence of abstract machine codes, easily mapped to instruction sequences on current computers. The resulting code is quite efficient, demonstrating once again the maxim that most compiler optimization is largely machine independent.     

Fortran 77 portability

This paper is the result of a study of the portability problems which might arise in the use of the Fortran 77 language. The study involved both an examination of the text of the Standard and discussions with a number of compiler-writing teams. The paper identifies areas of Fortran 77 which are likely to cause problems, either because of an incomplete language specification, difficulties in compilation, or user inattention. It will be of interest not only to users writing large packages in Fortran, and to Fortran compiler writers, but also to those involved in language standardization and portability in general.     

Compile—time detection of aliasing in euclid programs

Aliasing of variables occurs when two or more identifiers accessible in the same scope refer to the same storage location. When aliasing is present, the meaning of assignments becomes obscure because assignment to one variable identifier may change the value of others. Some of the more obscure kinds of variable aliasing can be the cause of particularly insidious bugs in computer programs. Axiomatic proof systems, such as that used for the Euclid language, assume that no aliasing is present so that the meaning of assignment is clear. For this reason, Euclid requires that no aliasing be present in Euclid programs and requires the compiler to implement checks to ensure this. This paper discusses the features of Euclid that aid in the detection of aliasing. It enumerates the kinds of aliasing that can be present in Euclid programs and gives efficient one-pass algorithms for compile-time detection of potential aliases. Aliasing is related to interference between concurrent processes, and a similar algorithm for detection of inter-process interference in Concurrent Euclid programs is presented.     

The design of a pascal compiler

The development of a compiler for the programming language PASCAL¹ is described in some detail. Design decisions concerning the layout of program and data, the organization of the compiler including its syntax analyser, and the over-all approach to the project are discussed. The compiler is written in its own language and was implemented for the CDC 6000 computer family. The reader is expected to be familiar with Reference 1.     

An analysis/synthesis interface for Pascal compilers

Many Pascal compilers are based upon a model which has two unpleasant properties: a large working set of procedures and lack of flexibility in object code structure. In this paper we analyse the source of these faults and describe an alternative model which avoids them. We then present the details of the key interface in the alternative model, as realized by a particular compiler.     

The portability of the BCPL compiler

Methods of achieving program portability are discussed, with particular reference to the mobility of compilers. The method of transferring the BCPL compiler is then described including the specification of OCODE which is the language used as an interface between the machine independent and machine dependent parts of the compiler.     

Slicing for modern program structures: a theory for eliminating irrelevant loops

Slicing is a program transformation technique with numerous applications, as it allows the user to focus on the parts of a program that are relevant for a given purpose. Ideally, the slice program should have the same termination properties as the original program, but to keep the slices manageable, it might be preferable to slice away loops that do not affect the values of relevant variables. This paper provides the first theoretical foundation to reason about non-termination insensitive slicing without assuming the presence of a unique end node. A slice is required to be closed under data dependence and under a recently proposed variant of control dependence, called weak order dependence. This allows a simulation-based correctness proof for a correctness criterion stating that the observational behavior of the original program must be a prefix of the behavior of the slice program.     

PIT: A macro-implemented implementation language

An implementation technique called PIT, for pseudo instructional technique, is described which utilizes the macro capabilities of most macro assemblers. A low level machine architecture is described via a set of macros that include some ‘high level’ features. Since the macros manipulate computer words, and refer to actual registers, their implementation in a system is relatively efficient, but since they do not reflect any one particular hardware design, they can be implemented by almost any macro assembler. Tests are built into the macros so that a PIT program will run without change on any machine that has defined these macros This technique should provide an alternative to using higher level languages as implementation languages if the object code produced by those compilers is deemed too slow (or too large) for the application that is being programmed.     

A sentence generator for a compiler for PT,a pascal subset

An implementation of a sentence generator system for a compiler for PT, a subset of Pascal, is discussed. Using the syntax definition of PT, the system automatically produces leftmost generations in a pseudorandom fashion. Syntactically correct as well as compile-time correct programs can be generated. In the generation of compile-time correct programs, only those statements that satisfy the contextual constraints imposed by the declarative part of the generated program are generated. The system also provides the facility of producing programs that have lexical or syntactic errors. All the generated programs are printed with appropriate indentations to show structural properties. Furthermore, the number of procedures in the generated program, the number of statements, identifier length and the number of generations can be controlled. The implementation has been successfully used for testing an error recovery parser as well as an intermediate code generator for PT.     

A pure embedding of attribute grammars

Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly semantic analysis of programming languages. Recent attribute grammar systems use dynamic scheduling algorithms to evaluate attributes on demand. In this paper, we show how to remove the need for a generator, by embedding a dynamic approach in a modern, object-oriented and functional programming language. The result is a small, lightweight attribute grammar library that is part of our larger Kiama language processing library. Kiama’s attribute grammar library supports a range of advanced features including cached, uncached, higher order, parameterised and circular attributes. Forwarding is available to modularise higher order attributes and decorators abstract away from the details of attribute value propagation. Kiama also implements new techniques for dynamic extension and variation of attribute equations. We use the Scala programming language because of its support for domain-specific notations and emphasis on scalability. Unlike generators with specialised notation, Kiama attribute grammars use standard Scala notations such as pattern-matching functions for equations, traits and mixins for composition and implicit parameters for forwarding. A benchmarking exercise shows that our approach is practical for realistic language processing.     

The programming language standards scene, ten years on Paper 10: Modula-2

This paper, one of a simultaneously published set, describes the establishment in 1984 of the standards project for the programming language Modula-2, and the progress of the project to the end of 1993. This project, including the language itself and an associated library, enters its final phase in 1994. This paper gives a thumbnail sketch of the language, the history of standardization, and the main consequences of changes made during standardization. New work on object-oriented extensions and a Posix binding is also described.