| AITEC Contract Research Projects in FY1998 : Proposal |
| Principal Investigator : | Dr. Bruno Buchberger, Professor |
| Research Institute for Symbolic Computation (RISC-Linz) |
Distributed Constraint Solving for Functional Logic Programming (Brushup)
In February 1987, at the occasion of a research visit to ICOT, Prof. Bruno Buchberger proposed using advanced methods in computer algebra (the Groebner bases method, quantifier elimination, etc.) for dealing with nonlinear constraints in logic programming. The use of algebraic methods in non-linear constraint logic programming has meanwhile been pursued by various groups in the world. At RISC-Linz, the emphasis was on non-linear and quantifier constraint solving including the development of distributed and parallel algorithms with a new degree of efficiency in particular in practical examples.
At the same time, at the SCORE group of Professor Ida at Tsukuba University, the research line of functional logic programming was developed in detail, in particular with respect to powerful narrowing techniques. Recently they have developed a new deterministic lazy conditional narrowing strategy and implemented it in the computer algebra system Mathematica.
Based on our combined experience, we pursue in the frame of this project the integration of constraint solving packages developed at RISC-Linz into the lazy narrowing system developed at SCORE such that the functional logic language serves as a ``coordination language'' distributing sets of constraints to a network of constraint solving engine. For this purpose, the functional logic language and its Mathematica implementation are extended by the mechanism to specify non-linear constraints over the real numbers and to formulate parallelism among different clauses of a predicate such that parts of the solution space can be investigated independently of and concurrently with each other.
After the first year of project work, we have set up the basic skeleton of the system by an implementation that supports solving constraints over the domain of complex numbers involving systems of linear and polynomial equations, differential equations and partial differential equations. All solvers are currently implemented by separate Mathematica processes executing in parallel and communicating with the constraint scheduler via the MathLink interface.
Within the next year of the project, we will brush up the software for better utility in a practical context.
Demonstrations: We will develop application examples from various domains such as electrical engineering by which the use of the system will be demonstrated. The demonstrations will be coded in the form of Mathematica notebooks (hypermedia documents) that can serve as tutorials for the use of the system and explain various features of its internal algorithms. The development of a library of such examples will be also of great importance for the research topics sketched below.
Constraint Solvers: For handling more complex examples, we will also integrate external solvers implemented in a compiled language (C/C++) over more powerful constraint domains (as have been developed at RISC-Linz). This will involve the definition of a corresponding communication interface on top of the MathLink protocol for the exchange of constraints between the Mathematica environment and the external solvers.
Concurrent Execution: While the constraint solving engines may run on different processors (of a multi-processor) or different machines (of a computer network), not much emphasis has been yet placed on the efficiency of the system with respect to its concurrent execution. Based on the additional application examples, we will investigate the dynamic behavior of the system in more detail in order to optimize the execution of the scheduler by minimizing communication overheads but still maintaining the potentials of concurrency. In this respect, the parallelization annotations inserted by the programmer into the program play an important role.
Calculus Extensions: For better usability, we intend to enlarge the set of allowable language constraints in two ways:
Both directions require to extend the set of external solvers. For supporting the second extension, we have already introduced a polymorphic type checker and started to experiment its use in classifying the constraints with respect to the domains on which they are defined.
Furthermore, the current inference calculus has various restrictions that we would like to overcome in future versions. For instance, it only allows a restricted form of higher-order functions/predicates and control of parallelism within the program is still rather rudamentary. We will thus continue work on the calculus in close cooperation with Prof. Ida.
| | Name | Affiliation |
|---|---|---|
| Principal investigator | Bruno Buchberger | RISC-Linz |
| Collaborating researchers | Tetsuo Ida | Tsukuba University |
| Wolfgang Schreiner | RISC-Linz | |
| Mircea Marin | RISC-Linz |
Work will be mainly carried out at the RISC-Linz by Mr. Marin under the guidance of Dr. Schreiner and in collaboration with Prof. Ida at Tsukuba university. Mr. Marin is visiting from July to September 1998 the group of Prof. Ida to ensure the exchange of researchr results and the continued interaction.
Distributed Functional Logic Constraint Solver.
The software allows to write programs in a functional logic language based on a variant of narrowing (deterministic lazy conditional narrowing) including the possibility to specify non-linear constraints over real numbers and to formulate parallelism among different branches/clauses of a predicate (AND/OR parallelism). When the language interpreter is started with a program and a query, an external scheduler process is created that contacts a list of hosts and starts constraint solving engines on these hosts.
Program execution proceeds by cooperation between the functional logic language interpreter, scheduler, and the various constraint solving engines. When processing the program, the interpreter repeatedly constructs systems of constraints that it sends to the scheduler; the scheduler classifies and decomposes these constraints and forwards them to the appropriate solvers which return corresponding sets of solutions; the interpreter queries these solutions and prints the corresponding program results.
The software consists of three parts
The resulting software can be considered as part of the Theorema project being pursued by Prof. Buchberger at RISC-Linz that aims at an integrated environment for mathematical problem solving based on the computer algebra system Mathematica. The proposed system will become one component of this environment representing the relationship between functional/logic programming and constraint solving.
The resulting software extends the power of the lazy conditional narrowing system developed at SCORE by facilties for constraint solving (non-linear constraints over the real numbers) and for distributed processing.
For a better understanding of the functionality of the system, we will add the facility to visualize the evolution of the solving process: the functional logic interpreter will be traced in a window, and the scheduling of the particular solvers for solving the sets of constraints will be traced in another one.
The whole system is provided as a collection of Mathematica notebooks. Notebooks corresponds to packages that are being loaded when the system runs. Every notebook contains a short description of the package content, use messages for the functions exported from the package, a manual section for every exported function, and short examples illustrating the use of the functions provided by the package.
We intend to improve the structure and content of the notebooks such that they can be regarded as reference guide for those who want to understand and further develop the system. Also, sample packages written on top of the system will be provided for particular applicative domains (currently a sample package modeling the behavior of electrical circuits is provided).
We work on providing a "tutorial" notebook documenting the successive steps that must be performed for setting up a new equational theory and for using it in solving interesting problems. The final result of applying such steps is a Mathematica package built on top of the system. By loading it, a user can start solving interesting problems in the theory defined inside the package.
The software will be used by researchers in logic programming languages and in functional logic programming languages as well as by researchers in constraint solving who will utilize its expressive power (solving systems of non-linear constraints over the reals within a functional logic programming language) and its computational power (using the power available in local-area computer networks).
The software also represents an interesting experiment by the integration of the computer algebra system Mathematica in distributed applications; a large interest of the huge computer algebra community using Mathematica (and also by Wolfram Research, the developers of Mathematica) is guaranteed. The functional logic programming model provides a high-level interface to engineers and scientists dealing with large systems of constraints as they arise in numerous applications.
The current implementation has integrated solvers for linear, polynomial, differential and partial differential equations over the domain of complex numbers, and all of them were implemented in Mathematica. We will extend the functionality of the system in the following ways:
Of particular interest is also the extension of the calculus to higher order logic. Such extensions are difficult to make because of the huge search space for solutions that has to be considered. We started to investigate efficient implementations of a restricted form of higher order narrowing, and hope that further investigation will boost the constraint solving capability of our system.
The software basis required for the proposed system are
Mathematica is a commercial program; it is available for a wide variety of machines running under different operating systems (Unix, Windows, etc).
The system currently consists of 20 Mathematica notebooks (about 16000 lines of hypertext) which boils down to about 4000 lines of executable Mathematica library code. Further constraint solvers implemented in a few thousand lines of C/C++ code will be added.
The current electronical tutuorial (electrical circuit simulation) consists of about 4500 lines in the form of a Mathematica notebook, this part will be extended and further examples will be added to about 3 times the current size.
The software will be used by researchers in logic programming languages and in functional logic programming languages as well as by researchers in constraint solving who will utilize its expressive power (solving systems of non-linear constraints over the reals within a functional logic programming language) and its computational power (using the power available in local-area computer networks).
The software also represents an interesting experiment by the integration of the computer algebra system Mathematica in distributed applications; a large interest of the huge computer algebra community using Mathematica (and also by Wolfram Research, the developers of Mathematica) is guaranteed. The functional logic programming model provides a high-level interface to engineers and scientists dealing with large systems of constraints as they arise in numerous applications.
The main advantage of the software will be its easy access (large portability by using Mathematica) and the easy accessability of local computing resources (computer networks). Using Mathematica as the programming interface immediately provides all the support of the Mathematica environment concerning presentation and publishing and the reuse of the results in other computations (in contrast to proprietary stand-alone systems not integrated with computer algebra systems).
Furtermore, the open design and modularity of the system will allow its use as a toolkit for own developments in distributed functional logic programming with constraints.