Pattern Specialization Based on Partial Evaluation

Design pattern enables software architecture generality and reusability, but which depresses the high performance. The pattern specialization was built on partial evaluation technology to reduce the overheads of design pattern. The design patterns were classified to extract the common features, and the corresponding pattern specializations were constructed. In the pattern specialization, the optimization opportunities were identified, and the specialization methods and conditions were described. The syntax of binding time analysis was defined, and the semantic depicted the invariant of usage context. The virtual invocation and dispatch were eliminated, which enhances the running efficiency. This pattern specialization is a high-level specialization for improving the performance of software aimed at design level that is orthogonal with the low-level code optimization.

Performance improvement of software component with partial evaluation

To avoid the complexity and inefficiency for specific applications of the current software architecture, a novel approach using partial evaluation is proposed to improve the running performance of components. The generic program was specialized into domain-specific realization for the known knowledge and environments. The syntax and semantic(adj.) were analyzed based on byte code instruction sequences, and partial evaluation rules depicted how to perform the specialization. The partial evaluation for object-oriented programs was implemented. The experimental results show that partial evaluation is effective to speed up the running efficiency. The more generality and scalability can be obtained by the integration of partial evaluation with the favorable design mechanisms and compiler optimization technology.

Using partial evaluation in holistic subgraph search

Because of its wide application, the subgraph matching problem has been studied extensively during the past decade. However, most existing solutions assume that a data graph is a vertex/edge-labeled graph （i.e., each vertex/edge has a simple label）. These solutions build structural indices by considering the vertex labels. However, some real graphs contain rich-content vertices such as user profiles in social networks and HTML pages on the World Wide Web. In this study, we consider the problem of subgraph matching using a more general scenario. We build a structural index that does not depend on any vertex content. Based on the index, we design a holistic subgraph matching algorithm that considers the query graph as a whole and finds one match at a time. In order to further improve efficiency, we propose a ＂partial evaluation and assembly＂ framework to find sub- graph matches over large graphs. Last but not least, our index has light maintenance overhead. Therefore, our method can work well on dynamic graphs. Extensive experiments on real graphs show that our method outperforms the state-of-the-art algorithms.

An Action Analysis for Combining Partial Evaluation

This paper proposes an action analysis for implementing combining partial evaluation efficiently. By analyzing the results of binding time analysis, on erations, which should be used in the combining partial evaluation, are determined in advance, so that the computation in the combination of specialized programs is reduced effectively.

Automatic Generation of Very Efficient Programs by Generalized Partial Computation

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, properties 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 discusses the power of the program transformation system, its theorem prover and future works.

A Partial Evaluator for A Parallel Lambda Language

This paper describes theoretical and practical aspects of a partial evaluator that treats a parallel lambda language. The parallel language presented is a combination of lambda calculus and message passing communication mechanism. This parallel language can be used to write a programming language's denotational semantics which extracts the parallelism in the program. From this denotational definition of the programming language, the partial evaluator can generate parallel compiler of the language by self application.The key technique of partial evaluation is binding time analysis that determines in advance which parts of the source program can be evaluated during partial evaluation, and which parts cannot. A binding time analysis is described based upon type inference. A new type chcode is introduced into the type system, which denotes the type of those expressions containing residual channel operations. A well-formedness criterion is given which ensures that partial evaluation not only doesn't commit type errors but also doesn't change the sequence of channel operations. Before binding time analysis, channel analysis is used to analyze the communication relationship between send and receive processes.

A New Integrated System of Logic Programming and Relational Database

Based on the study of the current two methods—interpretation and compilation—for the integration of logic programming and relational database,a new precompilation-based interpretive approach is proposed.It inherits the advantages of both methods,but overcomes the drawbacks of theirs.A new integrated system based on this approach is presented,which has been implemented on Micro VAX Ⅱ and applied to practise as the kernel of the GKBMS knowledge base management system.Also discussed are the key implementation techniques,including the coupling of logic and relational database systems,the compound of logic and relational database languages,the partial evaluation and static optimization of user's programs,fact scheduling and version management in problem-solving.