VOLUME 24 NUMBER 3 2000
Abstracts:
Attribute Grammars as Record Calculus - A Structure-Oriented Denotational Semantics of Attribute Grammars by Using Cardelli's Record Calculus
Katsuhiko
Gondow
Dept. of
Information Science, Japan Advanced Inst. of Science and Technology, 1-1
Asahidai Tatsunokuchi Nomi Ishikawa, 923-1292, Japan gondow@jaist.ac.jp
Takuya
Katayama
Dept. of
Information Science, Japan Advanced Inst. of Science and Technology, 1-1
Asahidai Tatsunokuchi Nomi Ishikawa, 923-1292 katayama@jaist.ac.jp
In this paper, we present a new denotational semantics of attribute grammars (AGs) by using Cardelli's record calculus. This new denotational semantics is simple, natural and structure-oriented. AGs have been considered useful in describing interactive programming environments as well as in specifying the semantics of programming languages. Using AGs, interactive programming environments are often described as attributed trees with several AG extensions, e.g., higher-order features, subtree replacement, and remote access. Unfortunately, it was not easy to compare various definitions for these extensions in a formal way. One of the reasons is that previous studies for AG semantics are not structure-oriented, that is, they are based on attribute valuation, not an attributed tree itself. For example, AG semantics based on attribute valuation can not deal directly with program transformation such as a ´ (b + c) Þ a ´ b + a ´ c.
In our new semantics, an attributed tree is represented as a nested record to preserve the structural information of the attributed tree. This enables us to deal directly with attributed trees rather than attribute valuation as AG semantics. We also represent higher-order AGs, recursive AGs and OOAG as record calculus by extending the semantics to show that our semantics can formalize such AG extensions. Both of higher-order AGs and OOAG are computational models to deal with tree transformation depending on attribute values. (pp. 287-299)
Keywords: attribute grammars, Cardelli's record calculus, structure-oriented denotational semantics
Görel
Hedin
Dept. of
Computer Science, Lund University, Sweden Gorel.Hedin@cs.lth.se
An object-oriented extension to canonical attribute grammars is described, permitting attributes to be references to arbitrary nodes in the syntax tree, and attributes to be accessed via the reference attributes. Important practical problems such as name and type analysis for object-oriented languages can be expressed in a concise and modular manner in these grammars, and an optimal evaluation algorithm is available. An extensive example is given, capturing all the key constructs in object-oriented languages including block structure, classes, inheritance, qualified use, and assignment compatibility in the presence of subtyping. The formalism and algorithm have been implemented in APPLAB, an interactive language development tool. (pp. 301-317)
Keywords: Attribute Grammars, Object-Oriented Languages, Reference Attributes, Remote Attribute Access}
Multiple Attribute Grammar Inheritance
Marjan
Mernik, Mitja Lenic, Enis Avdicausevic and Viljem Zumer
University of
Maribor, Faculty of Electrical Engineering and Computer Science, Smetanova 17,
2000 Maribor, Slovenia marjan.mernik@uni-mb.si
The language design process should be supported by modularity and abstraction in a manner that allows incremental changes as easily as possible. To at least partially fulfill this ambitious goal a new object-oriented attribute grammar specification language which supports multiple attribute grammar inheritance is introduced. Multiple attribute grammar inheritance is a structural organization of attribute grammars where the attribute grammar inherits the specifications from ancestor attribute grammars, may add new specifications or may override some specifications from ancestor specifications. With the proposed approach a language designer has the chance to design incrementally a language or reuse some fragments from other programming language specifications. The multiple attribute grammar inheritance is first introduced using an example, and thereafter by a formal model. The proposed approach is successfully implemented in the compiler/interpreter generator tool LISA ver. 2.0. (pp. 319-328)
Keywords: object-oriented attribute grammars, inheritance, incremental language design
First-class Attribute Grammars
Oege de
Moor and Kevin Backhouse
Programming
Research Group, Wolfson Building, Parks Road, Oxford OX1 3QD, UK {oege,kevinb}@comlab.ox.ac.uk
S. Doaitse
Swierstra
Department of
Computer Science, PO Box 80.089, 3508 TB Utrecht, The Netherlands doaitse@cs.uu.nl
In this paper, we show how attribute grammars can be divided into components. We introduce three types of component, called families, rules and aspects. We use the programming language Haskell [4] to give these components (and their composition) a concise executable semantics. We also show how our semantics makes it easy to define a number of generic attribution patterns such as chained attributes [16]. (pp. 329-341)
Keywords: Attribute Grammar, Functional Programming, Component, Aspect
Loïc
Correnson
INRIA –
Rocquencourt Correnson@polytechnique.org
Attribute grammars are well-designed to construct complex algorithms by composing several ones together. Actually, there exists a powerful transformation called descriptional composition which highly simplifies the composition of two attribute grammars by removing useless intermediate constructions. However, most of non-linear algorithms can not be expressed with attribute grammars. Thus, many compositions can not be simplified by the decriptional composition. In this paper, we present Equational Semantics, a formalism largely inspired by attribute grammars but where non-linear algorithms can be encoded. More precisely, instead of being restricted to one input static tree as it is the case for attribute grammars, an algorithm encoded with Equational Semantics may use dynamically constructed trees. This formalism consists in an very poor abstract syntax. We present its semantics and some of its transformations such as partial evaluation and decriptional composition (also called deforestation). In some sense, Equational Semantics is a kind of lambda-calculus dedicated to program transformations. (pp. 343-353)
Keywords: program transformation, partial evaluation, deforestation
Two-dimensional Approximation Coverage
Jörg Harm
Universität
Rostock, Fachbereich Informatik, 18051 Rostock, Germany jh@informatik.uni-rostock.de
Ralf
Lämmel
CWI, P.O. Box
94079, 1090 GB Amsterdam, The Netherlands ralf@cwi.nl
The notion of approximation coverage is developed. It is applicable to first-order declarative programs (e.g., logic programs, constructive algebraic specifications, and attribute grammars) in two dimensions in a natural way. For an attribute grammar, for example, there is a syntactic dimension corresponding to the underlying context-free grammar, and there is also a semantic dimension corresponding to the attributes, conditions, and computations. The coverage notion is based on an abstract interpretation scheme. The paper also develops a generator algorithm for test sets achieving coverage. The coverage notion facilitates testing of declarative programs, and assessment of test sets. The test set generator facilitates automated testing. A language definition based on an attribute grammar specification is used as an illustrative example. (pp. 355-369)
Keywords: testing, coverage, attribute grammars, declarative programming
A Multi-phase Parallel Algorithm for the Eigenelements Problem
Abdelhamid
Benaini and David Laiymani
Faculté des
Sciences du Havre, 25, Rue
Philippe Lebon, 76058 Le Havre Cedex. France benaini@univ-lehavre.fr
This paper presents a parallel implementation of a variant of the QR method for the eigenelements problem. This method consists in factorizing a symmetric matrix A in the form A = Q ´ QT where Q is an orthonormal matrix and X has nonzeros components only on main and cross diagonals. We present a multi-phase parallel implementation of this method onto a reconfigurable machine. We decompose this method into a series of standard parallel computations and for each of them we choose the best interconnection topology in order to speed up the communication time. Numerical tests corroborate nicely a theoretical evaluation of our parallel algorithm. (pp.371-377)
Keywords: eigenelements, sub-spaces method, parallel reconfigurable machine, multi-phase model
DD-Mod: A library for distributed programming
Jesús M.
Milán-Franco
Facultad de
Informática, Universidad Complutense de Madrid, Madrid 28040, Spain milanjm@sip.ucm.es
Ricardo
Jiménez-Peris and Marta Patiño-Martínez
Facultad de
Informática. Universidad Politécnica de Madrid, Boadilla del Monte, Madrid
28060, Spain (rjimenez,mpatino)@fi.upm.es
DD-Mod is a Modula-2 library for teaching concurrent and distributed programming. The use of this library, together with Modula-2, instead of the traditional socket interface and C, makes it possible to propose programming projects in a distributed programming course. Teaching tools based on high-level languages, such as DD-Mod (based on Modula-2), allow students to focus on the main topics of the course. In this way, it is avoided the waste of time with details related to the low-level interface of C and Unix. (pp. 379-389)
Keywords: distributed programming, concurrent programming, Modula-2
A Technique for Computing Watermarks from Digital Images
Chin-Chen
Chang and Chwei-Shyong Tsai
Department of
Computer Science and Information Engineering, National Chung Cheng University,
Chaiyi, Taiwan 621, R. O. C. {ccc,
tsaics}@cs.ccu.edu.tw
The new watermarking scheme in this paper solves the problem of digital copyright protection in computer network society. The proposed scheme coalesces both the technique of vector quantization (VQ) and the technique of principal component analysis (PCA). Therefore, it can effectively embed and extract watermarks. The proposed scheme is an invisible, robust, secure, multiple and blind watermarking technique. After various attacks such as JPEG lossy compression, blurring, cropping, rotating, and sharpening, the proposed scheme still provides robust watermarks. (pp. 391-396)
Keywords: Digital watermark, intellectual property protection, vector quantization
A Program-Algebraic Approach to Eliminating Common Subexpressions
James M.
Boyle
Technology
Development Division, Argonne National Laboratory, Argonne, IL 60439, USA boyle@td.anl.gov
R. Daniel
Resler
Dept. of
Mathematical Sciences, Virginia Commonwealth University, Richmond, VA 23284--2014,
USA dresler@vcu.edu
An operation often performed by optimizing compilers for higher-level languages is common - subexpression elimination. Traditionally, common - subexpression elimination is performed on a directed, acyclic graph representing the expression or program. This paper shows how common - subexpression elimination can be expressed algebraically, using a "program algebra" incorporating the syntax of typical higher-level language expressions plus l-expressions from the l calculus and functional programming. This approach has two major advantage - it is intuitive and easy to understand and it uses transformations for which correctness-preservation is easy to prove. (pp. 397-408)
Keywords: programming languages, optimizing
An Assessment of Incomplete - LU Preconditioners for Nonsymmetric Linear Systems
John R.
Gilbert
Xerox Palo Alto
Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304, USA gilbert@parc.xerox.com
Sivan
Toledo
School of
Computer Science,Tel-Aviv University, Tel-Aviv 69978, Israel sivan@math.tau.ac.il
We report on an extensive experiment to compare an iterative solver preconditioned by several versions of incomplete LU factorization with a sparse direct solver using LU factorization with partial pivoting. Our test suite is 24 nonsymmetric matrices drawn from benchmark sets in the literature. On a few matrices, the best iterative method is more than 5 times as fast and more than 10 times as memory-efficient as the direct method. Nonetheless, in most cases the iterative methods are slower; in many cases they do not save memory; and in general they are less reliable. Our primary conclusion is that a direct method is currently more appropriate than an iterative method for a general-purpose black-box nonsymmetric linear solver.
We draw several other conclusions about these nonsymmetric problems: pivoting is even more important for incomplete than for complete factorizations; the best iterative solutions almost always take only 8 to 16 iterations; a drop-tolerance strategy is superior to a column-count strategy; and column MMD ordering is superior to RCM ordering.
The reader is advised to keep in mind that our conclusions are drawn from experiments with 24 matrices; other test suites might have given somewhat different results. Nonetheless, we are not aware of any other studies more extensive than ours. (pp. 409-425)
Keywords: Sparse nonsymmetric linear systems, iterative methods,
direct methods, incomplete-LU preconditioners, pivoting