Specification
MINERVA superseeded IF/Prolog. Please see http://www.ifcomputer.co.jp/MINERVA for details.

We discontinued to sell IF/Prolog Dec 31. 2003. For current customers, we continue to provide professional support for IF/Prolog until Dec 31, 2008.

The Constraint Technology Package allows almost any resource allocation task to be handled in a declarative and efficient manner.

Constraint Problem Solving in IF/Prolog

The Constraint Technology Package (Option of IF/Prolog) introduces the latest "constraint based problem solv- ing" paradigm into IF/Prolog. This allows IF/Prolog applications to address previously "too complex" problems in an extended problem domain. Problems encompassing almost any resource allocation task such as dynamic vehicle scheduling for airlines or railways, production planning and crew rostering can now be handled in a declarative and efficient manner.

The programming package groups different constraint classes into different Prolog modules. The modularity is a significant feature for IF/Prolog and has proved well in industrial appli- cations. Furthermore it ensures compatibility with existing application code.

Operational Applications Provide Expertise

There are currently a number of applications under development or in productive use in var- ious problem domains. The technology has though been proven and improved by close co- operation with the following industrial systems:

Railway signaling and traffic control: a prototype development for re-scheduling a rail timetable based on real time informa- tion.

System Verification Tool: SVE (System Verification Environment) is a tool to cope with the economic validation of current technical system by means of formal verification. Used by several Siemens industrial units.

Circuit Verification Tool: CVE (Circuit Verification Environment) is a tool to ensure that newly developed cir- cuits are logically correct. In operational use at ASIC Design Centres of Siemens.

The Constraint Technology Package in Brief

Main Features

The Constraint Technology Package incorporates five additional domains of computation to those provided within the Prolog programming language.

Big integers and rationals: Exact arithmetic with integers of arbitrary length and rationals.

Coroutines: Data driven computation activated upon the instantiation of a variable.

Linear constraints: Solving systems of linear equations and inequations over rationals, including high level predicates for accumulation, disjunction, minimization, maximization ...

Finite domains: Narrowing actively the range of possible values associated with a variable this tech- nique significantly reduces the search space by considering only a valid set of possible values.

Boolean constraints: Relations formulated with boolean expressions provide efficient decision tree manipulation.

Together with the very high level language Prolog these constructs allow for both easier programming and faster execution of the same problems. Details on the improvements can be found below.

Integrated Development Environment

The IF/Prolog development environment has been extended to facilitate the debugging and tracing of constraint based applications. The debugger and tracer extend upon the traditional four port debug model to clearly illustrate the suspension and activation of constraints. This incorporates a new ten port semantic model to allow easy access to run-time operations. Together with a hypertext-style on-line help this environment significantly improves pro- grammer productivity.

This environment is available as both ASCII and Motif variants with an hypertext-style on- line help facility available under Motif.

The Constraint Technology Package is compatible with all database interfaces, programming language interfaces, character-sets and graphical windowing systems used in conjunction with IF/Prolog. The package is available as an option on all IF/Prolog hardware platforms.

Improving Programmer Productivity

The integrated development environment of the Constraint Technology Package is only one of the basics improving programmer productivity. Using the Constraint Technology Package, programming becomes more declarative. Its enhanced problem solving capabilities allow simpler programming of complex tasks.

Increased Execution Efficiency

Significant enhancements have not only been achieved in respect of the development envi- ronment but also in respect of the time required for program execution. Due to the fact that all additional internal data-areas required for constraint solving are automatically resized and garbage collected transparent to the user appli- cation so that they can be executed more ef- ficiently. The Constraint Technology Package forms a central part of the system kernel and represents a state of the art implementation of the constraint technology.

How much the Constraint Technology Package accelerates the problem solving can be seen in the following table. Implemented in IF/Prolog V4.1 and IF/Prolog V5.0 on a Sun SPARC- station IPX hardware platform the execution times for toy programs are compared. Program- ming the IF/Prolog V5.0 solution with and without the Constraint Technology Package shows the degree of enhancement achieved by applying constraint problem solving methods. 

     _______________________________________________ 
    |                   |  (1)      |  (2)   | (3)  |
    |___________________|___________|________|______| 
    |  Eight-Queens     |  30.13    | 18.01  | 4.19 |
    |___________________|___________|________|______|
    |  Farmer           |   4.50    |  3.42  | 0.98 |
    |___________________|___________|________|______|
    |  SEND MORE MONEY  |  65.50    | 53.47  | 0.85 |
    |___________________|___________|________|______|


    (1) Traditional Prolog IF/Prolog V4.1
    (2) Traditional Prolog IF/Prolog V5.0
    (3) Constraint Solving IF/Prolog V5.0 


    CPU time given in Seconds per 100 evaluations

Standards

The Constraint Technology Package is written in ANSI standard compatible C . Predicates provided within this package conform to the same style and rigour as those defined in the ISO Prolog standard.

History of Development

This new programming package is based on the theoretical research system CHIP developed by the ECRC (European Computer Research Centre). The package is directly derived from SNI Prolog 3.1 and includes additional develop- ment of the constraint technology together with all what was prototyped in the former CHIP system. Great care has been taken to pack- age this technology in a modular, industrial oriented manner, consistent with the product as a whole.

Programming with the Constraint Technology Package

The Constraint Technology Package provides four constraint classes: coroutines, linear con- straints, constraints for finite domains and boolean constraints. For all constraint classes Prolog modules offer a great variety of built-in predicates. It is not possible to illustrate here every predicate contained in the constraint classes. Those used in the examples below are just a few out of the wide range of built-in predicates offered by IF/Prolog.

Big Integers and Rationals for Higher Precision

The range of terms which are interpreted as numbers in IF/Prolog has been extended to in- clude big integers and rational numbers. Big integers may take near arbitrary values, re- stricted to approximately 300000 decimal places. Rationals are represented as an uncancelled fraction of two big integers and provide very high precision arithmetic.

Coroutines Enhance Declarative Programming

Coroutines constitute a separate class of constraints. They are the basic mechanism to initiate the evaluation of a goal under data control and allow you to write Prolog programs in a more declarative fashion. Using built-in predicates it is possible to delay the evaluation of a goal until one or more variables are instantiated.

However coroutines are not sufficient as a general constraint mechanism since, as is the case in standard Prolog, they test consistency conditions passively. The more efficient method is to restrict the domain of a variable in advance which allows active handling of consistency conditions. Coroutines are though useful to define more complex constraints.

[Example]

The following queries give a good example for the improved declarative programming capa- bilities provided by the use of coroutines. In accordance with the proof model, Prolog proves subgoals procedurally from left to right. This may result in cases which, from the declarative point of view, are not correct: 

[user]  ?-  A  \=  a,  A  =  b.
no
[user]  ?-  A  =  b,  A  \=  a.
            A  =  b
    yes
From the logical viewpoint, the order of subgoals is 
equivalent with respect to satisfiability.
Using freeze/2 , a built-in predicate of the coroutine 
constraint class, it is possible to delay
the proof of the first goal ( A \= a ) until the 
variable A is instantiated.
[user]  ?-  freeze(A,  A  \=  a),  A  =  b.
            A = b
yes

Linear Constraints for Linear Optimization

Using linear constraints it is possible to solve "non-discrete" optimization problems where there are potentially an infinite number of solutions. Linear constraints are a set of equations and inequations which are solved by an incremental algorithm.

Finite Domains for Discrete Problem Solving

The class of constraints for finite domains is particularly useful for solving discrete prob- lems. Discrete means that only a finite number of values satisfy the conditions which can be expressed by the constraints for finite domains. The traditional Prolog "generate and test" programming paradigm can be replaced by one where only possible values are generated.

A finite domain variable may be any integer restricted as an interval, enumeration or se- quence. The variable may then only take a value present in its restricted domain. Within the class of constraints for finite domains it is possible to specify arithmetic as well as symbolic constraints between variables. Furthermore, cumulative constraints are provided.

Boolean Constraints for Scheduling

Boolean constraints are particularly suited to scheduling or decision based applications where no quantitative measure is required. They operate over the binary domain of truth values and can therefore be used to efficiently determine conditional values.

During execution truth values are propagated over a number of "logical-built-in" predicates. The boolean unification algorithm operates over the truth domain allowing decisions to be combined easily.

Up read on...