Abstract Functional languages are suitable for transformational developments of programs. However, accumulative functions, or in particular tail-recursive functions, are known to be less suitable for manipulation. In this paper, we propose a program transformation named “IO swapping” that swaps call-time and return-time computations. It moves computations in accumulative parameters to results and thereby enables interesting transformations. We demonstrate effectiveness of IO swapping by several applications: deforestation, higher order removal, program inversion, and manipulation of circular programs.

It is often convenient to write a function and apply it to a specific input. However, a program developed in this way may be inefficient to evaluate and difficult to analyze due to its generality. In this paper, we propose a technique of new specialization for a class of XML transformations, in which no output of a function can be decomposed or traversed. Our specialization is type-based in the sense that it uses the structures of input types; types are described by regular hedge grammars and subtyping is defined set-theoretically. The specialization always terminates, resulting in a program where every function is fully specialized and only accepts its rigid input. We present several interesting applications of our new specialization, especially for injectivity analysis.

Parallel programs on lists have been intensively studied. It is well known that associativity provides a good characterization for divide-and-conquer parallel programs. In particular, the third homomorphism theorem is not only useful for systematic development of parallel programs on lists, but it is also suitable for automatic parallelization. The theorem states that if two sequential programs iterate the same list leftward and rightward, respectively, and compute the same value, then there exists a divide-and-conquer parallel program that computes the same value as the sequential programs.While there have been many studies on lists, few have been done for characterizing and developing of parallel programs on trees. Naive divide-and-conquer programs, which divide a tree at the root and compute independent subtrees in parallel, take time that is proportional to the height of the input tree and have poor scalability with respect to the number of processors when the input tree is ill-balanced.In this paper, we develop a method for systematically constructing scalable divide-and-conquer parallel programs on trees, in which two sequential programs lead to a scalable divide-andconquer parallel program. We focus on paths instead of trees so as to utilize rich results on lists and demonstrate that associativity provides good characterization for scalable divide-and-conquer parallel programs on trees. Moreover, we generalize the third homomorphism theorem from lists to trees.We demonstrate the effectiveness of our method with various examples. Our results, being generalizations of known results for lists, are generic in the sense that they work well for all polynomial data structures.

Modern development environments often involve models with complex consistency relations. Some of the relations can be automatically established through "fixing procedures". When users update some parts of the model and cause inconsistency, a fixing procedure dynamically propagates the update to other parts to fix the inconsistency. Existing fixing procedures are manually implemented, which requires a lot of efforts and the correctness of a fixing procedure is not guaranteed.

Bidirectional transformation is a pair of transformations: a view function and a backward transformation. A view function maps one data structure called source onto another called view. The corresponding backward transformation reflects changes in the view to the source. Its practically useful applications include replicated data synchronization, presentation-oriented editor development, tracing software development, and view updating in the database community. However, developing a bidirectional transformation is hard, because one has to give two mappings that satisfy the bidirectional properties for system consistency.

The metamodel techniques and model transformation techniques provide a standard way to represent and transform data, especially the software artifacts in software development. However, after a transformation is applied, the source model and the target model usually co-exist and evolve independently. How to propagate modifications across models in different formats still remains as an open problem.

XQuery is a powerful functional language to query XML data. This paper gives a bidirectional interpretation of XQuery to address the problem of updating XML data through materialized XQuery views. We first design an expressive bidirectional transformation language, and then translate XQuery expressions into the code of this language. As a result, an XQuery expression can execute in two directions: in the forward direction, it generates a materialized view from the source XML data; while in the backward direction, it updates the source data by putting back the updates on the view. we have implemented our approach and applied it to some XQuery use cases from a W3C draft, which confirms the practicability of this approach.

Divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions on lists, which match very well with the divide-and-conquer paradigm. However, direct programming with list homomorphisms is a challenge for many programmers. In this paper, we propose and implement a novel systemthat can automatically derive cost-optimal list homomorphisms from a pair of sequential programs, based on the third homomorphism theorem. Our idea is to reduce extraction of list homomorphisms to derivation of weak right inverses. We show that a weak right inverse always exists and can be automatically generated from a wide class of sequential programs. We demonstrate our system with several nontrivial examples, including the maximum prefix sum problem, the prefix sum computation, the maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiency of our automatic parallelization algorithm and good speedups of the generated parallel programs.

Tree contraction algorithms, whose idea was first proposed by Miller and Reif, are important parallel algorithms to implement efficient parallel programs manipulating trees. Despite their efficiency, the tree contraction algorithms have not been widely used due to the difficulties in deriving the tree contracting operations. In particular, the derivation of the tree contracting operations is much difficult when multiple values are referred and updated in each step of the contractions. Such computations often appear in dynamic programming problems on trees. In this paper, we propose an algebraic approach to deriving tree contraction programs from recursive tree programs, by focusing on the properties of commutative semirings. We formalize a new condition for implementing tree reductions with the tree contraction algorithms, and give a systematic derivation of the tree contracting operations. Based on it, we implemented a code generator for tree reductions, which has an optimization mechanism that can remove unnecessary computations in the derived parallel programs. As far as we are aware, this is the first step towards an automatic parallelization system for the development of efficient tree programs.

In the domain of XML authoring, there have been many tools to help users to edit XML documents. These tools make it easier to produce complex documents by using such technologies as syntax-directed or presentation-oriented editing, etc. However, when an XML document contains data with some computation dependency among them, these tools cannot free users from the burden of maintaining this dependency relationship. By computation dependency, we mean that some data are gotten by computing from other data in the same document.In this paper, we present an environment for authoring XML document, in which users can express the data dependency relationship in one document explicitly rather than implicitly in their minds. Under this environment, the dependent parts of the document are represented as expressions, which in turn can be evaluated to generate the dependent data. Therefore, users need not to compute the dependent data first and then input them manually, as required by the current authoring tools.

No abstract available.

This paper presents a novel editor supporting interactive refinement in the development of structured documents. The user performs a sequence of editing operations on the document view, and the editor automatically derives an efficient and reliable document source and a transformation that produces the document view. The editor is unique in its programmability, in the sense that the transformation can be obtained through editing operations. The main tricks behind are the utilization of the view-updating technique developed in the database community, and a new bidirectional transformation language that cannot only describe the relationship between the document source and its view, but also data dependency in the view.

As mobile computing and communications have become popular, predictive text entry systems have become an increasingly important technology. Existing methods still need refinement, though, with respect to personalization, especially how to acquire vocabulary not pre-registered in the system dictionary. In this paper, we report on an automatic method that dynamically obtains a user specific vocabulary from the user's unanalyzed documents. When a user makes an entry, the system dynamically extracts the corresponding chunks from the user text and suggests them along with words suggested by the dictionary. With our method, texts in a particular style or concerning a specific domain can be entered using a predictive text entry system. We verified that a large amount of words not registered in the dictionary can be entered using our method.

In this paper we propose a new method for deriving a practical linear-time algorithm from the specification of a maximum-weightsum problem: From the elements of a data structure x, find a subset which satisfies a certain property p and whose weightsum is maximum. Previously proposed methods for automatically generating linear-time algorithms are theoretically appealing, but the algorithms generated are hardly useful in practice due to a huge constant factor for space and time. The key points of our approach are to express the property p by a recursive boolean function over the structure x rather than a usual logical predicate and to apply program transformation techniques to reduce the constant factor. We present an optimization theorem, give a calculational strategy for applying the theorem, and demonstrate the effectiveness of our approach through several nontrivial examples which would be difficult to deal with when using the methods previously available.

This paper evaluates the effects of IP packet loss and picture frame reduction on MPEG1 subjective quality in order to clarify how to apply quality-guaranteed techniques such as RSVP (resource reservation protocol) to the Internet. Subjective assessment tests showed that IP packet loss was the dominant factor in MPEG1 audio-visual quality degradation compared with picture frame reduction. Moreover, there was no difference between individual audio-visual quality contributions to the overall MPEG1 quality.

The problems involved in developing efficient parallel programs have proved harder than those in developing efficient sequential ones, both for programmers and for compilers. Although program calculation has been found to be a promising way to solve these problems in the sequential world, we believe that it needs much more effort to study its effective use in the parallel world. In this paper, we propose a calculational framework for the derivation of efficient parallel programs with two main innovations:. -We propose a novel inductive synthesis lemma based on which an elementary but powerful parallelization theorem is developed. -We make the first attempt to construct a calculational algorithm for parallelization, deriving associative operators from data type definition and making full use of existing fusion and tupling calculations.Being more constructive, our method is not only helpful in the design of efficient parallel programs in general but also promising in the construction of parallelizing compiler. Several interesting examples are used for illustration.

Tupling is a well-known transformation tactic to obtain new efficient recursive functions by grouping some recursive functions into a tuple. It may be applied to eliminate multiple traversals over the common data structure. The major difficulty in tupling transformation is to find what functions are to be tupled and how to transform the tupled function into an efficient one. Previous approaches to tupling transformation are essentially based on fold/unfold transformation. Though general, they suffer from the high cost of keeping track of function calls to avoid infinite unfolding, which prevents them from being used in a compiler.To remedy this situation, we propose a new method to expose recursive structures in recursive definitions and show how this structural information can be explored for calculating out efficient programs by means of tupling. Our new tupling calculation algorithm can eliminate most of multiple data traversals and is easy to be implemented.

It has been attracting much attention to make use of list homomorphisms in parallel programming because they ideally suit the divide-and-conquer parallel paradigm. However, they have been usually treated rather informally and ad hoc in the development of efficient parallel programs. What is worse is that some interesting functions, e.g., the maximum segment sum problem, are basically not list homomorphisms. In this article, we propose a systematic and formal way for the construction of a list homomorphism for a given problem so that an efficient parallel program is derived. We show, with several well-known but nontrivial problems, how a straightforward, and “obviously” correct, but quite inefficient solution to the problem can be successfully turned into a semantically equivalent “almost list homomorphism.” The derivation is based on two transformations, namely tupling and fusion, which are defined according to the specific recursive structures of list homomorphisms.

... this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.