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.
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.
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 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.
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.
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.
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
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.
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.
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.
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 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
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.
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 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.
| 
