Theme 1: Debugging Tools for KL1
A debugging mechanism for nondeterministic programs in KL1 has been designed. It records nondeterministic choices, and runs the same program again forcing the choices made in the recorded run.
The amount of the recorded information has been effectively minimized through static program analyses. To allow casual users of the KL1 language system to use the debugging mechanism more easily, the mechanism should be built into KL1 language systems.
For the second year, we feel that integration of the debugging mechanism into KLIC is desirable. To allow this, the static analyzer, currently written in Prolog, should better be recoded in KL1 itself. Further research on more sophisticated debugging policies is also expected.
To clarify the above-mentioned goal, we propose adding a sentence to the second paragraph of Article 2.1 of Attachment A, such that the paragraph reads:
In this research, ways to make such a debugger practical by reducing the search space are investigated, making use of A.I. search techniques. Ways to integrate the debugger into KL1 language systems are also investigated and evaluated. The results of this research will be a report on basic theories and implementation methods.
Theme 2: Parallel Constraint Logic Programming System
A system called CHUKL (Constraint Handling Under KL1) is proposed for handling finite domain constraints by using KL1. CHUKL employs and- and or- parallelism that can be found in finite domain constraint handling. The final aim of CHUKL is to accept representative finite domain constraint logic programming language CHIP as its output.
Since KL1 is a committed choice language, it has no built-in search mechanism. To construct a system for handling finite domain constraints, search is crucial for finding a consistent combination of values for constraint variables. CHUKL realizes this kind of search. Besides, CHUKL employs both and- and or-parallelism that are inherently embedded in finite domain constraint handling.
CHUKL adopts no heuristics for improving efficiency of finite domain constraint handling. Nevertheless, its efficiency is higher than expected for absence of heuristics. As the next step, introduction of heuristics into CHUKL will certainly be important to achieve higher efficiency.
For the second year, integration of CHUKL and heuristics for efficient handling of finite domain constraints is expected. A study of appropriateness of known heuristics for parallel handling of constraints is also expected. Further, a comparison between CHUKL and other parallel finite domain constraint handling is desirable.
Again to clarify the above-mentioned goal, we propose adding a sentence to the second paragraph of Article 2.2 of Attachment A, such that the paragraph reads:
In this research, ways to make a parallel constraint logic programming language for finite domain constraints on top of KL1 are investigated. For reducing search space, heuristics for this language is also investigated. The results of this research will be a report on basic theories and implementation methods for the constraint logic programming language.