An optimizing compiler for the icon programming language

Compiling code for the Icon programming language presents several challenges, particularly in dealing with types and goal-directed expression evaluation. In order to produce optimized code, it is necessary for the compiler to know much more about operations than is necessary for the compilation of most programming languages. This paper describes the organization of the Icon compiler and the way it acquires and maintains information about operations. The Icon compiler generates C code, which makes it portable to a wide variety of platforms and also allows the use of existing C compilers for performing routine optimizations on the final code. A specially designed implementation language, which is a superset of C, is used for writing Icon's run-time system. This language allows the inclusion of information about the abstract semantics of Icon operations and their type-checking and conversion requirements. A translator converts code written in the run-time language to C code to provide an object library for linking with the code produced by the Icon compiler. The translation process also automatically produces a database that contains the information the Icon compiler needs to generate and optimize code. This approach allows easy extension of Icon's computational repertoire, alternate computational extensions, and cross compilation.     

An operational semantics for Icon: Implementation of a procedural goal-directed language

The generation of compiled code for expressions in programming languages such as Icon that support goal-directed evaluation in addition to traditional control structures presents more of a challenge than generating code for traditional imperative programming languages. This paper describes a code-generation technique for translating Icon programs into a traditional high-level language. Translations into both Pascal and C are discussed. However, any language that provides function parameters and recursion is sufficient. The technique described here has been used in the implementation of an optimizing compiler for Icon.     

Logicon: An integration of prolog into icon

This paper describes the coupling of logic programming with Icon, which is a programming language aimed at string processing. Icon and Prolog have many similarities and their integration is feasible and desirable because the weaknesses of one can be compensated for by the strengths of the other. In our case, a Prolog interpreter was written as an Icon procedure that can be linked and called by an Icon program. This interpreter deals with all Icon data types and can be called in the context of the goal-directed evaluation of Icon. We give an example showing the power of this symbiosis between these two languages where a Prolog call in Icon is a generator and an Icon call in a Prolog clause is a built-in predicate.     

The implementation of generators and goal-directed evaluation in icon

Two features of the Icon programming language strongly influence its implementation: generators and goal-directed evaluation. A generator is an expression that is capable of producing a sequence of results. In goal-directed evaluation, the results of generators are produced automatically in an attempt to complete computations successfully. This paper describes the generated code and run-time support for generators, goal-directed evaluation, and related control structures.     

Chicon—a Chinese text manipulation language

Text processing is an important computer application. Due to its importance, a number of text manipulation programming languages have been devised (e.g. Icon). These programming languages are very useful for applications such as natural language processing, text analysis, text editing, document formatting, text generation, etc. However, they were mainly designed to handle English texts, and are ineffective for Chinese. This is because English and Chinese texts are represented very differently in a computer. An English character is mainly represented in 7-bit ASCII, and its Chinese counterpart commonly in 16-bit GB or BIG-5. This difference makes direct application of English-based text manipulation programming languages to Chinese erroneous, e.g. application of Icon to reverse a string of Chinese characters. In this paper, a new dialect of Icon, referred to as Chicon (i.e. Chinese Icon), is proposed. In the design of Chicon, new data types were introduced to differentiate pure English and English/Chinese mixed texts. In addition, existing Icon text manipulation functions were modified to account for Chinese texts. Experiments have shown that Chicon not only could overcome the problems of Chinese processing in Icon, but its execution speed was actually superior to Icon in handling Chinese. Furthermore, application of Chicon to a real sized problem, namely word segmentation, has proved that the language is practical. © 1998 John Wiley & Sons, Ltd.     

A unifying approach to goal-directed evaluation

Goal-directed evaluation, as embodied in Icon and Snobol, is built on the notions of backtracking and of generating successive results, and therefore it has always been something of a challenge to specify and implement. In this article, we address this challenge using computational monads and partial evaluation. We consider a subset of Icon and we specify it with a monadic semantics and a list monad. We then consider a spectrum of monads that also fit the bill, and we relate them to each other. For example, we derive a continuation monad as a Church encoding of the list monad. The resulting semantics coincides with Gudeman’s continuation semantics of Icon. We then compile Icon programs by specializing their interpreter (i.e., by using the first Futamura projection), using type-directed partial evaluation. Through various back ends, including a run-time code generator, we generate ML code, C code, and OCaml byte code. Binding-time analysis and partial evaluation of the continuation-based interpreter automatically give rise to C programs that coincide with the result of Proebsting’s optimized compiler. Basic Research in Computer Science (www.brics. dk), funded by the Danish National Research Foundation. Olivier Danvy, Ph.D., Habilitation: He is an Associate Professor at the Department of Computer Science at the University of Aarhus, in Denmark. He obtained his Ph.D. degree in 1986 and his Habilitation in 1993 from the Université Pierre et Marie Curie (Paris VI), France. His research interests are in Programming Languages in general and in Partial Evaluation and Continuations in particular. He has published over 75 refereed research papers and edited several proceedings. He has both served on and chaired program committees of scientific meetings in the area of Programming Languages. He is presently chairing the PEPM steering committee at ACM SIGPLAN and serving as external reviewer in computer science for the Danish Universities, as board member in the BRICS PhD School, and as co-Editor-in-Chief of the journal Higher-Order and Symbolic Computation (http://www.wkap.nl/journals/hosc). Bernd Grobauer, M.Sc.: He is a Ph.D. student at the BRICS International Ph.D. school, University of Aarhus, Denmark, and will graduate in the summer of 2001. He obtained his Masters degree from the Munich University of Technology (TUM), Germany. His research interests are in formal methods (especially theorem proving) and programming languages (semantics of programming languages, program analysis, program transformation, types). He serves as editorial assistant for the journal Higher-Order and Symbolic Computation and as chairman of the BRICS Juniorklubben. Morten Rhiger, M.Sc.: He is a Ph.D. student at the BRICS International Ph.D. school, University of Aarhus, Denmark, and will graduate in the summer of 2001. He obtained his Masters degree from the University of Aarhus in 1998. His research interests are in the semantics and implementation of programming languages.     

A portable storage management system for the icon programming language

Icon is a new programming language designed primarily for non-numerical applications. Its roots are in SNOBOL4 and SL5; as in those languages, execution-time flexibility is an important attribute of Icon, although some aspects of programs are bound at compile time to improve efficiency. Icon, which is implemented in Ratfor, is also intended to be portable and suitable for 16-bit computers. The storage management system in Icon is designed to meet the goals of portability, flexibility and efficiency. This is accomplished by subdividing the storage management system into a set of type-specific storage management subsystems. This paper describes the implementation of these subsystems, their interaction, and their performance.     

A Function-Composition Approach to Synthesize Fortran 90 Array Operations

An increasing number of programming languages, such as Fortran 90 and APL, are providing a rich set of intrinsic array functions and array expressions. These constructs which constitute an important part of data parallel languages provide excellent opportunities for compiler optimizations. In this paper, we present a new approach to combine consecutive array operations or array expressions into a composite access function of the source arrays. Our scheme is based on the composition of access functions, which is analogous to a composition of mathematic functions. Our new scheme can handle not only data movements of arrays with different numbers of dimensions and with multiple-clause array operations but also masked array expressions and multiple-source array operations. As a result, our proposed scheme is the first synthesis scheme which can collectively synthesize Fortran 90 RESHAPE, EOSHIFT, MERGE, array reduction operations, and WHERE constructs. In addition, we also discuss the case that the synthesis scheme may result in a performance anomaly in the presence of common subexpressions and one-to-many array operations. A solution is proposed to avoid such a performance anomaly. Experimental results show speedups from 1.21 to 2.95 over the base code for code fragments from real applications on a Sequent multiprocessor machine and also show comparable performance improvements on an 8-node SGI Power Challenge by incorporating our proposed optimizations     

The Alamo Execution Monitor Architecture

Future programming environments will incorporate a tighter coupling between language runtime systems and the monitoring tools that are used to debug, tune, visualize, and understand them. Many innovations that are developed first in higher level programming language environments will migrate into mainstream languages once their properties are understood and generalized.

The Alamo execution monitor architecture was developed to facilitate rapid development of execution monitors, especially visualization tools that are instrumental in understanding complex runtime system interactions in higher level languages. Alamo simplifies the development of such tools by solving the low-level access, control, and intrusion problems inherent in monitoring.

Alamo was implemented first for the very high-level imperative goal-directed language Icon. The architecture was then implemented for ANSI C in order to broaden the impact of the work. This paper describes the ANSI C implementation of Alamo and the monitoring services it provides.     

Keyword programming in Java

Keyword programming is a novel technique for reducing the need to remember details of programming language syntax and APIs, by translating a small number of unordered keywords provided by the user into a valid expression. In a sense, the keywords act as a query that searches the space of expressions that are valid in the given context. Prior work has demonstrated the feasibility and merit of this approach in limited domains. This paper explores the potential for employing this technique in much larger domains, specifically general-purpose programming languages like Java. We present an algorithm for translating keywords into Java method call expressions. When tested on keywords extracted from existing method calls in Java code, the algorithm can accurately reconstruct over 90% of the original expressions. We tested the algorithm on keywords provided by users in a web-based study. The results suggest that users can obtain correct Java code using keyword queries as accurately as they can write the correct Java code themselves. We implemented the algorithm in an Eclipse plug-in as an extension to the autocomplete mechanism and deployed it in a preliminary field study of several users, with mixed results. One interesting result of this work is that most of the information in Java method call expressions lies in the keywords, and details of punctuation and even parameter ordering can often be inferred automatically.     

HTEL: a HyperText Expression Language

In general, an expression language provides a means to indicate non‐constant values in expressions. It includes operations to combine values, but these will normally disappear when the expression is evaluated. HTEL is an expression language to produce HTML‐documents. It is presented to stimulate a discussion about the structure of hypertext expression languages. The operations have been chosen in agreement with what is strongly suggested, but not defined, by the HTML‐standard. The HTEL‐interpreter can be used for cgi‐programs, i.e. to describe reactions when data from a ‘form’ in an HTML‐document has been submitted. A special tool has been used to build the HTEL‐interpreter, as an example belonging to a family of interpreters for domain‐specific languages. Members of that family have characteristics that are closely related to structural patterns found in the mark‐ups of HTML. HTEL should also be seen as a substantial example to witness the applicability and relevance of the principles that are applied in the tool used for constructing its interpreter. Copyright © 1999 John Wiley & Sons, Ltd.     

A Space-Efficient Optimization of Call-by-Need

Call-by-need is widely regarded as an optimal (to within a constant factor) parameter passing mechanism for functional programming languages. Except for certain special cases involving higher order functions, call-by-need is optimal with respect to time. However, call-by-need is far from optimal with respect to space. We examine some of the space problems which can arise with call-by-need and other parameter passing mechanisms. A simple optimizing technique, based on work by Mycroft [1], is proposed. If it can be determined both that an expression must be evaluated eventually and that the evaluation of the expression is likely to reduce the space required by the program, then the evaluation is performed as soon as possible. This optimization does not result in optimal space performance in all cases. However, in most of the common cases where call-by-need causes a problem the proposed optimization avoids the problem. Since our technique is not always optimal, it is likely to be of greatest advantage in situations where efficiency is important but not critical. For example, functional languages with call-by-name semantics are increasingly being used as specification languages. Since such a specification is runnable, it may be used as a prototype. This makes it possible to experiment with a program and refine the specification before the implementation in the target language is started.     

Proving Congruence of Bisimulation in Functional Programming Languages

We give a method for proving congruence of bisimulation-like equivalences in functional programming languages. The method applies to languages that can be presented as a set of expressions together with an evaluation relation. We use this method to show that some generalizations of Abramsky's applicative bisimulation are congruences whenever evaluation can be specified by a certain natural form of structured operational semantics. One of the generalizations handles nondeterminism and diverging computations.     

An empirical analysis of spreadsheet calculation

Spreadsheet calculation is a powerful tool in simple administrative data processing. Formulae in spreadsheets have similar forms to expressions in traditional programming languages, but the implementation of control structures is totally different. This paper contains an analysis of 101 spreadsheets made and used in business and government. The analysis concerns general properties, such as cell contents and referencing, the role of input, output and computation, and the different ways iteration is implemented. Finally some effects of expertise are studied. The results show that less than half of the available functions are really used, only one cell in 25 contains computation, and iteration is implemented in at least four different ways. Formulae are found to differ in their contents from expressions of programming languages, as control structures are implemented differently in these systems. Summation with a constant skip is suggested to be included in the set of functions of spreadsheet calculation.     

Privacy and security in information systems using programming language features

This paper describes a specification and implementation scheme for providing an integrated approach to security and privacy rules and shows how they may be achieved with a formal specification language that permits the association of operations with logical conditions. The implementation of these rules is shown in the programming language PLAIN. In this way, the access and notification control that has typically been performed by operating systems, database management systems, and programming languages is brought together in an integrated programming environment.     

Characterizations of regular and context-free matrices

The u-v theorem for context-free languages is extended to prove an intercalation theorem for the family of context-free matrix languages. A row-wise iteration factor theorem is proved for the families of regular and context-free matrix languages. Characterizations of regular and context-free matrix languages are given in terms of vertical regular sequences and simple operations on vertical regular sequences. Closure of regular and context-free matrix languages under array nondeterministic finite state transducer mappings is established and an image theorem proved. This is used to give another characterization of regular matrix languages. Further it is shown that the family of regular matrix languages is a principal abstract family of matrices (AFM). The effect of string control and array control on these families are examined.     

Instant replay debugging of concurrent logic programs

One problem with debugging (committed choice) concurrent logic programs is that their behaviour may be non-deterministic, in that successive executions of the same program may produce different results. We describe a scheme, based on the ‘Instant Replay’ scheme developed for more conventional parallel languages, that allows us to reproduce the execution behaviour of a concurrent logic program on subsequent executions, so that the execution may be examined for debugging purposes. The properties of concurrent logic programming languages allow us to simplify our scheme greatly. We have demonstrated our scheme with KLIC, and KL1 on the PIM multiprocessors, but it can also be applied to other committed choice concurrent logic programming languages.     

A simple system for constructing distributed,mixed-language programs

The Mixed-Language Programming (MLP) System is a simple system that facilitates construction of sequential programs in which procedures can be written in different programming languages to exploit heterogeneity in language functionality. In addition, MLP provides a simple remote procedure call (RPC) facility that allows heterogeneity in machine functionality to be exploited. To minimize implementation cost, the system does not solve all of the problems related to mixed-language programming; rather, MLP is designed to handle common situations well. Among the unique aspects of MLP are its advanced facilities, which allow complex situations to be handled with user intervention; for example, these facilities allow arguments of a type not defined by a language to be used by procedures written in that language. This paper overviews the use of MLP and describes its implementation. In addition, two programs that have been written using the MLP system—a small database system and a collection of plot routines—are discussed. The system executes on a collection of Vaxes and Suns running Berkeley UNIX. Currently supported languages are C, Pascal and Icon.