A portable approach to dynamic optimization in run-time specialization

This paper proposes arun-time bytecode specialization (BCS) technique that analyzes programs and generates specialized programs at run-time in an intermediate language. By using an intermediate language for code generation, a back-end system canoptimize the specialized programs after specialization. The system uses Java virtual machine language (JVML) as the intermediate language, which allows the system to easily achieve practicalportability and to use existing sophisticated just-in-time (JIT) compilers as its back-end. The binding-time analysis algorithm is based on a type system, and covers a non-object-oriented subset of JVML. The specializer generates programs on a per-instruction basis, and can performmethod inlining at run-time. Our performance measurements show that a non-trivial application program specialized at run-time by BCS runs approximately 3–4 times faster than the unspecialized one. Despite the large overhead of JIT compilation of specialized code, we observed that the overall performance of the application can be improved. This paper is an extended version of “A Portable Approach to Generating Optimized Specialized Code”, inProceedings of Second Symposium on Programs as Data Objects (PADO-II), Lecture Notes in Computer Science, vol. 2053, pp. 138–154, Aarhus, Denmark, May 2001.²³) Hidehiko Masuhara, D.Sc.: He is an Assistant Professor at Department of Graphics and Computer Science, Graduate School of Arts and Sciences, University of Tokyo. He received his B.S., M.S. and D.Sc. degrees from Department of Information Science, University of Tokyo in 1992, 1994, and 1999, respectively. His research interests are in programming languages, especially in mechanisms to support flexible and efficient computation such as dynamic optimization and reflection. He received the best-paper award from Information Processing Society of Japan in 1996. Akinori Yonezawa, Ph.D.: He is a Professor of computer science at Department of Computer Science, University of Tokyo. He received Ph.D. in Computer Science from the Massachusetts Institute of Technology in 1977. His current major research interests are in the areas of concurrent/parallel computation models, programming languages, object-oriented computing, and distributed computing. He is the designer of an object-oriented concurrent language ABCL/1 and the editor of several books and served as an associate editor of ACM Transaction of Programming Languages and Systems (TOPLAS). Since 1998, he has been an ACM Fellow.     

On the degeneration of program generators by program composition

One of the main discoveries in the seventies was that the concept of a generating extension covers a very wide class of apparently different program generators. Program specialization, or partial evaluation, is powerful because it provides uniform techniques for the automatic implementation of generating extensions from ordinary programs. The Futamura projections stand as the cornerstone of the development of program specialization. This paper takes the idea of the Futamura projections further. Threedegeneration projections are formulated which tell us how to achieve the reverse goal by program composition, namely turning a generating extension into an ordinary program. The fact that program composition can invert the effect of program specialization shows that these projections are dual in a sense. The degeneration projections complete a missing link between programs and generating extensions and allow for novel applications of program transformation.     

A data-directed approach to program construction

The present paper discusses a method of program construction based on the specification of the data types. The input and output data types and the mapping between them are specified at a high level of abstraction and this non-procedural specification is used to develop a program schema. The data type and mapping specifications are modified to include a concrete representation of the data and these are used to expand the program schema into a program. A graphical representation for data and program specifications is also introduced and it is shown how this can simplify the techniques and be very useful in program construction. The method is illustrated by developing two programs—the line justifier program described by Gries and the bubblesort.     

An architectural approach to improved program maintainability

A programming standard is described, with the emphasis on the visual aspects of the final product rather than on how the programs are engineered.     

Relating the implementation techniques of functional and functional logic languages

Functional logic languages are declarative programming languages that integrate the programming paradigms of functional and logic languages within a single framework. They are extensions of functional languages with principles derived from logic programmingNarrowing, the evaluation mechanism of functional logic languages, can be defined as a generalization ofreduction, the evaluation mechanism of purely functional languages. The unidirectional pattern matching, which is used for parameter passing in functional languages, is simply replaced by the bidirectionalunification known from logic programming languages. We show in this paper, how to extend a reduction machine, that has been designed for the evaluation of purely functional programs to a machine that performs narrowing. The necessary extensions concern the realization of unification and backtracking, for which we fall back upon the methods of Warren’s Prolog engine.²¹⁾ The narrowing machine embodies an optimized treatment of deterministic computations. A complete specification of the reduction and the narrowing machine and of the translation of a sample language into abstract machine code is given. Comparative results of a C-implementation of the reduction and the narrowing machine show that the time overhead of the more complex narrowing evaluation is, in general, less than 10% of the reduction evaluation.     

Coherence approach to logic program revision

In this paper, we present a new approach to the problem of revising extended programs; we base this approach on the coherence theory initially advocated by Gardenfors for belief revision. Our approach resolves contradiction by removing only conflicting information, not the believed source of it, and therefore, keeps information loss minimal. Furthermore, since there is no need to search for problematic assumptions, as is done in the traditional assumption-removal approach, our approach provides a skeptical revision semantics that is tractable. We define the skeptical and credulous coherence semantics and show that both semantics can be characterized in terms of the fixpoint semantics of a revised program using a simple program-revision technique. These semantics provide a suitable framework for knowledge and belief revision in the context of logic programs. Semantical properties and advantages of the proposed revision semantics are also analyzed     

Program transformation system based on generalized partial computation

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, abstract data types of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical partial evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper demonstrates the power of the program transformation system as well as its theorem prover and discusses some future works. Yoshihiko Futamura, Ph.D.: He is Professor of Department of Information and Computer Science and the director of the Institute for Software Production Technology (ISPT) of Waseda University. He received his BS in mathematics from Hokkaido University in 1965, MS in applied mathematics from Harvard University in 1972 and Ph.D. degree from Hokkaido University in 1985. He joined Hitachi Central Research Laboratory in 1965 and moved to Waseda University in 1991. He was a visiting professor of Uppsala University from 1985 to 1986 and a visiting scholar of Harvard University from 1988 to 1989. Automatic generation of computer programs and programming methodology are his main research fields. He is the inventor of the Futamura Projections in partial evaluation and ISO8631 PAD (Problem Analysis Diagram). Zenjiro Konishi: He is a visiting lecturer of Institute for Software Production Technology, Waseda University. He received his M. Sc. degree in mathematics from Waseda University in 1995. His research interests include automated theorem proving. He received JSSST Takahashi Award in 2001. He is a member of JSSST and IPSJ. Robert Glück, Ph.D., Habil.: He is an Associate Professor of Computer Science at the University of Copenhagen. He received his Ph.D. and Habilitation (venia docendi) from the Vienna University of Technology in 1991 and 1997. He was research assistant at the City University of New York and received twice the Erwin-Schrodinger-Fellowship of the Austrian Science Foundation (FWF). After being an Invited Fellow of the Japan Society for the Promotion of Science (JSPS), he is now funded by the PRESTO21 program for basic research of the Japan Science and Technology Corporation (JST) and located at Waseda University in Tokyo. His main research interests are advanced programming languages, theory and practice of program transformation, and metaprogramming.     

A functional approach to non-monotonic logic1

Axiom sets and their extensions are viewed as functions from the set of formulas in the language to a set of four truth values, t, f, u for undefined, and k for contradiction. Such functions form a lattice with “contains less information” as the partial order ?, and “combination of several sources of knowledge” as the least-upper-bound operation ?. Inference rules are expressed as binary relations between such functions. We show that the usual criterium on fixpoints, namely, to be minimal, does not apply correctly in the case of non-monotonic inference rules. A stronger concept, approachable fixpoints, is introduced and proven to be sufficient for the existence of a derivation of the fixpoint. In addition, the usefulness of our approach is demonstrated by concise proofs for some previously known results about normal default rules.     

A program specialiser for meta-level compositions of logic programs

Metal-level compositions of object logic programs are naturally implemented by means of meta-programming techniques. Metainterpreters defining program compositions however suffer from a computational overhead that is due partly to the interpretation layer present in all meta-programs, and partly to the specific interpretation layer needed to deal with program compositions. We show that meta-interpreters implementing compositions of object programs can be fruitfully specialised w.r.t. meta-level queries of the form Demo (E, G), where E denotes a program expression and G denotes a (partially instantiated) object level query. More precisely, we describe the design and implementation of declarative program specialiser that suitably transforms such meta-interpreters so as to sensibly reduce — if not to completely remove — the overhead due to the handling of program compositions. In many cases the specialiser succeeds in eliminating also the overhead due to meta-interpretation. Antonio Brogi, Ph.D.: He is currently assistant professor in the Department of Computer Science at the University of Pisa, Italy. He received his Laurea Degree in Computer Science (1987) and his Ph. D. in Computer Science (1993) from the University of Pisa. His research interests include programming language design and semantics, logic programming, deductive databases, and software coordination. Simone Contiero: He is currently a Ph. D. student at the Department of Computer Science, University of Pisa (Italy). He received his Laurea Degree in Computer Science from the University of Pisa in 1994. His research interests are in high-level programming languages, metaprogramming and logic-based coordination of software.     

A program logic for resources

We introduce a reasoning infrastructure for proving statements about resource consumption in a fragment of the Java Virtual Machine Language (JVML). The infrastructure is based on a small hierarchy of program logics, with increasing levels of abstraction: at the top there is a type system for a high-level language that encodes resource consumption. The infrastructure is designed to be used in a proof-carrying code (PCC) scenario, where mobile programs can be equipped with formal evidence that they have predictable resource behaviour.     

Self-generating program specializers

This paper demonstrates the existence of self-generating program specializers and uses a language-independent projection to obtain them. The projection is considered from the viewpoint of the interpretive approach and a bootstrapping technique is identified by which a specializer can optimize its own implementation. A theorem is presented that equates the set of self-generating specializers and the set of specializers produced by the new projection. A practical consequence of the theorem is that an implementation of a specializer must contain an error if it is not possible to observe self-generation, which requires only a textual program comparison. Self-generation may thus provide a method for testing specializers and self-interpreters while they are under development.     

Programming with narrowing: A tutorial

Narrowing is a computation implemented by some declarative programming languages. Research in the last decade has produced significant results on the theory and foundation of narrowing, but little has been published on the use of narrowing in programming. This paper introduces narrowing from a programmer’s viewpoint; shows, by means of examples, when, why and how to use narrowing in a program; and discusses the impact of narrowing on software development activities such as design and maintenance. The examples are coded in the programming language Curry, which provides narrowing as a first class feature.     

A residualizing semantics for the partial evaluation of functional logic programs

Recent proposals for multi-paradigm declarative programming combine the most important features of functional, logic and concurrent programming into a single framework. The operational semantics of these languages is usually based on a combination of narrowing and residuation. In this paper, we introduce a non-standard, residualizing semantics for multi-paradigm declarative programs and prove its equivalence with a standard operational semantics. Our residualizing semantics is particularly relevant within the area of program transformation where it is useful, e.g., to perform computations during partial evaluation. Thus, the proof of equivalence is a crucial result to demonstrate the correctness of (existing) partial evaluation schemes.     

Access to specific declarative knowledge by expert systems: The impact of logic programming

As part of the operation of an Expert System, a deductive component accesses a database of facts to help simulate the behavior of a human expert in a particular problem domain. The nature of this access is examined, and four access strategies are identified. Features of each of these strategies are addressed within the framework of a logic-based deductive component and the relational model of data.     

Oracle-Based Partial Evaluation

We present Oracle-Based Partial Evaluation (OBPE), a novel approach to on-line Partial Evaluation (PE) which decides the control strategy to use for each call pattern by using an oracle function which compares the results of specializing such call pattern w.r.t. a set of strategies. Our proposal is motivated by Poly-Controlled Partial Evaluation (PCPE), which allows using different control strategies for different call patterns. Given a set of control strategies, the best PCPE specialized programs outperform the specialized programs obtained by traditional PE for any of the control strategies in , especially when resource-aware specialization is performed. Unfortunately, computing all PCPE specialized programs and then choosing a posteriori the best one is too costly in practice. In contrast, in OBPE a single specialized program is computed. We have developed an empirical oracle whose parameters are approximated from a set of training data, by using constraint logic programming. Our experimental results show that the additional cost of OBPE when compared with traditional PE is a constant factor and that, at least in our experiments, OBPE obtains significantly better specializations. We argue that our proposal is relevant in practice and introduces clear improvements over standard PE. Our work is developed in the context of logic programs, though the ideas are in principle of interest to the PE of any programming language.     

An integrated framework for the diagnosis and correction of rule-based programs

We present a generic scheme for the declarative debugging of programs that are written in rewriting-based languages that are equipped with narrowing. Our aim is to provide an integrated development environment in which it is possible to debug a program and then correct it automatically. Our methodology is based on the combination (in a single framework) of a semantics-based diagnoser that identifies those parts of the code that contain errors and an inductive learner that tries to repair them, once the bugs have been located in the program. We develop our methodology in several steps. First, we associate with our programs a semantics that is based on a (continuous) immediate consequence operator, T_R, which models the answers computed by narrowing and is parametric w.r.t. the evaluation strategy, which can be eager or lazy. Then, we show that, given the intended specification of a program R, it is possible to check the correctness of R by a single step of T_R. In order to develop an effective debugging method, we approximate the computed answers semantics of R and derive a finitely terminating bottom-up abstract diagnosis method, which can be used statically. Finally, a bug-correction program synthesis methodology attempts to correct the erroneous components of the wrong code. We propose a hybrid, top-down (unfolding-based) as well as bottom-up (induction-based), correction approach that is driven by a set of evidence examples which are automatically produced as an outcome by the diagnoser. The resulting program is proven to be correct and complete w.r.t. the considered example sets. Our debugging framework does not require the user to provide error symptoms in advance or to answer difficult questions concerning program correctness. An implementation of our debugging system has been undertaken which demonstrates the workability of our approach.     

The applicability of program schema results to programs

Several classes of programs, which are the analogues of previously investigated classes of program schemas, are defined. Decidability and translatability questions are considered for these classes of programs, as well as the applicability of these results to the theories of optimization and program testing. The usefulness of the schema model is studied by considering the inheritability of schema properties by programs, and conversely, the inheritability of program properties by schemas.     

An approach to effortless construction of program animations

Program animation systems have not been as widely adopted by computer science educators as we might expect from the firm belief that they can help in enhancing computer science education. One of the most notable obstacles to their adoption is the considerable effort that the production of program animations represents for the instructor. We present here an approach to reduce such a workload based on the automatic generation of visualizations and animations. The user may customize them in a user-friendly way to construct more expressive program animations. These operations are carried out by means of a user-friendly manipulation based on the metaphor of office documents. We have applied this approach to the functional paradigm by extending the WinHIPE programming environment. Finally, we report on the successful results of an evaluation performed to measure its ease of use.     

One approach for an ergonomics program in a large manufacturing environment

This paper describes the approach the Boeing Company's Everett Division chose to take during development of their ergonomics program. The program covers both factory and office environments, but the approach used in each area is different. The goal of the program was to develop a systematic process efficiently utilizing the available resources. Lessons learned during the three years of this program are also discussed.