Executable codes can be extracted from constructive proofs by using realizability interpretation. However, realizability also generates redundant codes that have no significant computational meaning. This redundancy c...
Executable codes can be extracted from constructive proofs by using realizability interpretation. However, realizability also generates redundant codes that have no significant computational meaning. This redundancy causes heavy runtime overheads and is one of the obstacles in applying realizability to practical systems that realize the mathematical programming paradigm. This paper presents a method to eliminate redundancy by analysing proof trees as preprocessing of realizability interpretation. According to the declaration given to the theorem that is proved, each node of the proof tree is marked automatically to show which part of the realizer is needed. This procedure does not always work well. This paper also gives an analysis of the procedure and techniques to resolve critical cases. The method is studied in simple constructive logic with primitive types, mathematical induction and its q -realizability interpretation. As an example, the extraction of a prime number checker program is given.
This paper describes a new external reference management scheme for KL1, a committed choice logic programming language based on GHC. The significance of the new scheme is that it realizes incremental inter-processor g...
详细信息
This paper describes a new external reference management scheme for KL1, a committed choice logic programming language based on GHC. The significance of the new scheme is that it realizes incremental inter-processor garbage collection. Previous distributed implementations of committed choice languages had not seriously addressed inter-processor garbage collection.
Incremental inter-precessor garbage collection is realized by the Weighted Export Counting (WEC). It is a first attempt to use the weighted reference counting technique in logic programming language implementation, and is also new in that it has introduced export and import tables for making independent local garbage collection possible and reducing the number of inter-processor read requests.
The problems with exhaustion of reference counts and indirect exportation are discussed. Since the binding order rule adopted in our previous implementation for avoiding creation of reference loops is insufficient in the presence of indirect exportation, a new binding order rule is introduced. We prove that avoidance of reference loops is guaranteed and also prove that the unification procedure always terminates for non-circular structures.
We review the design of the concurrent logic language GHC, the basis of the kernel language for the Parallel Inference Machine being developed in the Japanese Fifth generationcomputer Systems project, and the design ...
详细信息
We review the design of the concurrent logic language GHC, the basis of the kernel language for the Parallel Inference Machine being developed in the Japanese Fifth generationcomputer Systems project, and the design of the parallel language KL1, the actual kernel language being implemented and used. The key idea in the design of these languages is the separation of concurrency and parallelism. Clarification of concepts of this kind seems to play an important role in bridging the gap between parallel inference systems and knowledge information processing in a coherent manner. In particular, design of a new kernel language has always encouraged us to re-examine and reorganise various existing notions related to programming and to invent new ones.
This paper presents a computation model and its programming language,A’UM,* as a result of our pursuit of high parallelism and high expressivity for the development of a large scale software. By basing it on streams ...
详细信息
This paper presents a computation model and its programming language,A’UM,* as a result of our pursuit of high parallelism and high expressivity for the development of a large scale software. By basing it on streams and integrating it with objects and relations,A’UM realizes an elegant model, natural representation and efficient execution, all at once, that have never been done by any other approaches.
This paper presents an experimental implementation of a self-applicable partial evaluator in Prolog used for compiler generation and compiler generator generation. The partial evaluator is an extension of a simple met...
详细信息
This paper presents an experimental implementation of a self-applicable partial evaluator in Prolog used for compiler generation and compiler generator generation. The partial evaluator is an extension of a simple meta interpreter for Prolog programs, and its self-application is straightforward because of its simplicity. A method of incremental compilation is also described as a promising application of the partial evaluator for knowledge-based systems.
This paper presents a set of rules for the transformation of GHC (Guarded Horn Clauses) programs based on unfolding. The proposed set of rules, called UR-set, is shown to preserve freedom from deadlock and to preserve...
详细信息
This paper presents a set of rules for the transformation of GHC (Guarded Horn Clauses) programs based on unfolding. The proposed set of rules, called UR-set, is shown to preserve freedom from deadlock and to preserve the set of solutions to be derived. UR-set is expected to give a basis for various program transformations, especially partial evaluation of GHC programs.
This paper presents a formal relationship for probability theory and a class of nonmonotonic reasoning which we call lazy nonmonotonic reasoning. In lazy nonmonotonic reasoning, nonmonotonicity emerges only when new a...
详细信息
A multiple alignment methodology that can produce high-quality alignment is extremely important for predicting the structure of unknown proteins. Nearly all the methodologies developed so far have employed two-way ali...
Multiple sequence alignment is an important problem in the biosciences. To date, most multiple alignment systems have employed a tree-based algorithm, which combines the results of two-way dynamic programming in a tre...
This paper presents some applications of partial evaluation method to a query optimization in deductive database. A Horn clause transformation is used for the partial evaluation of a query in an intensional database, ...
详细信息
This paper presents some applications of partial evaluation method to a query optimization in deductive database. A Horn clause transformation is used for the partial evaluation of a query in an intensional database, and its application to multiple query processing is discussed. Three strategies are presented for the compatible case, ordered case and crossed case. In each case, partial evaluation is used to preprocess the intensional database in order to obtain subqueries which direct access to an extensional database.
暂无评论