Technical Reports - Query Results
Your query term was 'all = clp'26 reports found
Reports are sorted by descending number
- ÖFAI-TR-96-21 (
53kB g-zipped PostScript file)Defasibility in CLP(Q) through Generalized Slack Variables
- Christian Holzbaur, Francisco Menezes, Pedro Barahona
- This paper presents a defeasible constraint solver
for the domain of linear equations, disequations and inequalities over
the body of rational/real numbers.
As extra requirements resulting from the incorporation
of the solver into an Incremental Hierarchical Constraint Solver
(IHCS) scenario we identified: a)the ability to refer to individual
constraints by a label, b) the ability to report the (minimal)
cause for the unsatisfiability of a set of constraints, and c) the
ability to undo the effects of a formerly activated constraint.
We develop the new functionalities after starting the presentation with a general architecture for defeasible constraint solving, through a solved form algorithm that utilizes a generalized, incremental variant of the Simplex algorithm, where the domain of a variable can be restricted to an arbitrary interval. We demonstrate how generalized slacks form the basis for the computation of explanations regarding the cause of unsatisfiability and/or entailment in terms of the constraints told, and the possible deactivation of constraints as demanded by the hierarchy handler.
Keywords: Constraint Logic Programming, Linear Programming, Defeasible Constraint Solving
- This paper presents a defeasible constraint solver
for the domain of linear equations, disequations and inequalities over
the body of rational/real numbers.
As extra requirements resulting from the incorporation
of the solver into an Incremental Hierarchical Constraint Solver
(IHCS) scenario we identified: a)the ability to refer to individual
constraints by a label, b) the ability to report the (minimal)
cause for the unsatisfiability of a set of constraints, and c) the
ability to undo the effects of a formerly activated constraint.
- ÖFAI-TR-95-24
Constraint Logic Programming for Qualitative Reasoning about Dynamic Behavior
- Yousri El Fattah
- The paper shows how constraint logic programming over the real domain, CLP(R), can be used for qualitative reasoning (QR) about dynamic behavior. The main result is a procedure for computing qualitative solutions of ordinary differential equations (ODEs). The procedure is described for linear systems and is based on partitioning the quantity space into disjoint sub-spaces where each sub-space corresponds to a qualitatively distinct relation between variables and their derivatives. Examples are given to illustrate how the procedure can be utilized for qualitative simulation and analysis of dynamic behavior.
- ÖFAI-TR-95-09 ( 46kB g-zipped PostScript file,
160kB PDF file)OEFAI clp(q,r) Manual Rev. 1.3.2
- Christian Holzbaur
- This Manual documents a Prolog implementation of clp(q,r), based on SICStus featuring extensible unification via attributed variables. The system described in this document is an instance of the general Constraint Logic Programming scheme introduced by [Jaffar and Michaylov 87]. The implementation is at least as complete as other existing clp(r) implementations: It solves linear equations over rational or real valued variables, covers the lazy treatment of nonlinear equations, features a decision algorithm for linear inequalities that detects implied equations, removes redundancies, performs projections (quantifier elimination), allows for linear dis-equations, and provides for linear optimization.
- ÖFAI-TR-94-25 ( 49kB g-zipped PostScript file)
A CLP approach to Detection and Identification of Control System Component Failures
- Yousri El Fattah, Christian Holzbaur
- One approach to fault detection and identification (FDI) in control systems is based on computing the so-called parity relations for sensors and actuators. We state the problem of generating those parity relations in the language of constraints, and describe an implementation of a parity solver in the Constraint Programming Language CLP(Re). The solver adopts a discrete linear time-invariant (LTI) model of control systems, and outputs a set of single-component parity relations. We describe a FDI procedure, also in CLP(Re), that monitors system behavior and computes single-fault diagnoses. The CLP approach enhances the naturalness of representation of system relations, and makes use of the resolution capability of CLP both for deriving parity relations and for making diagnostic decisions. An example is given to illustrate the viability of the CLP approach.
- ÖFAI-TR-94-17 ( 56kB g-zipped PostScript file)
Constraint Logic Programming for Structure-Based Reasoning about Dynamic Physical System
- Yousri El Fattah
- The paper describes a framework for reasoning about dynamic physical systems based on structure. The framework integrates the language of bond graphs (BG) with the language of constraint logic programming (CLP). The advantage of such integration is twofold. First, to exploit the wealth of reasoning methods developed in the BG area within system dynamics. Second, to enhance the naturalness of representation of system relations and possibly increase solution efficiency via CLP. The paper describes methods for causal modeling of dynamic physical system including the generation of causal explanations.
- ÖFAI-TR-94-07 ( 54kB g-zipped PostScript file)
A Specialized, Incremental Solved Form Algorithm for Systems of Linear Inequalities
- Christian Holzbaur
- We present a computationally improved incremental solved form algorithm for systems of linear equations and inequalities. The algorithm is of the pivotal algebra type. It benefits (computationally) from a specialization of the classical Simplex algorithm that treats inequalities of dimension one, i.e. of the shape kx + d <= 0, special. In particular, the introduction of a slack variables is avoided in this case, which results in a basis that consists of higher dimensional inequality constraints only. Although the classical results concerning the complexity results for the Simplex algorithm apply, in particular in the worst case, the specialization is justified on the basis that even in the unlikely case that the special cases should not occur in practical programs, the average complexity is not higher than that of the classical algorithm. The proposed algorithm matches and advances current activities in the CLP area that try to restrict the use of general and expensive decision methods to the cases where they are unavoidable.
- ÖFAI-TR-94-02 ( 53kB g-zipped PostScript file)
Morphology with a Null-Interface
- Harald Trost, Johannes Matiasek
- We present an integrated architecture for word-level and sentence-level processing in a unification-based paradigm. The system is built upon a unification engine implemented in a CLP language supporting types and definite relations as part of feature descriptions. In this framework an HPSG-style grammar is implemented. Word-level processing uses X2MorF a morphological component based on an extended version of two-level morphology. This component is tightly integrated with the grammar as a specialized relation. This architecture has computational as well as linguistic advantages. Integrating morphology and morphophonology directly into the grammar is in the spirit of HPSG which views grammar as a relation between the phonological (or graphemic) form of an utterance and its syntactic/semantic representation. This way also the treatment of phenomena transcending the boundary between morphology and syntax is made possible. On the implementation side, the practical problems of interfacing two inherently different modules are eliminated. For applications this means that using a morphological component is made easy. Nevertheless, this tight integration still leaves morphology and syntax/semantics as autonomous components, enabling direct use of existing data sets describing morphophonology in terms of the two-level paradigm.
- ÖFAI-TR-93-26 ( 79kB g-zipped PostScript file)
A CLP Based Approach to HPSG
- Johannes Matiasek, Wolfgang Heinz
- In this paper we present a CLP based method for the direct implementation of HPSG, a grammar formalism employing strongly typed feature structures and principles to constrain them. We interpret unification of typed feature structures under the restrictions of principled constraints as constraint solving in the CLP paradigm. The aim of our implementation method is to operationalize the declarative grammar specification without having to account for processing aspects, i.e. to clearly separate grammar and processing model. To achieve this goal we employ a lazy instantiation technique which maintains well-typedness of feature structures at every instantiation stage. This method is complemented with a delay mechanism enabling the constraints arising from grammar principles to cope with uninstantiated structures. Applicability conditions of grammar principles may be specified conditionally, viewing them as licensing conditions on every node of a feature structure. This also allows for the reformulation of disjunctive constraints into a conjunction of conditional constraints, thereby reducing the search space.
- ÖFAI-TR-93-21 ( 79kB g-zipped PostScript file)
Diagnosing Analog Circuits Designed-for-Testability by Using CLPR
- Igor Mozetic, Franc Novak, Marina Santo-Zarnik, Anton Biasizzo
- Recently, a design-for-test (DFT) methodology for active analog filters was proposed with the primary goal in increased controllability and observability. We operationalize and extend the DFT methodology by using CLPR to model and diagnose analog circuits. CLPR is a logic programming language with the capability to solve systems of linear equations and inequalities. It is well suited to model parameter tolerances and to diagnose soft faults, i.e., deviations from nominal values. The diagnostic algorithm uses different DFT test modes and results of voltage measurements for different frequencies and computes a set of suspected components. Ranking of suspected components is based on a measure of (normalized) standard deviations from predicted mean values of component parameters. Presented case studies on a real circuit show encouraging results in isolation of soft faults for a given low pass biquad filter.
- ÖFAI-TR-93-19 ( 36kB g-zipped PostScript file)
Interval Arithmetic with CLPR
- Igor Mozetic, Christian Holzbaur
- We describe two extensions of CLPR, motivated by an application to model-based diagnosis of active analog filters. The first extension addresses the problem of rounding errors in CLPR. We represent Reals with floating-point intervals which are computed by outward rounding. The second extension increases the expressiveness of linear CLPR. Constants in linear expressions can now be intervals, which enables reasoning with imprecise model parameters (tolerances). Bounds (sup and inf) for individual variables are computed by the linear optimization via modified Simplex. Both extensions are implemented in a CLP shell --- an adaptation of SICStus Prolog, which allows for easy and fast developments and modifications of CLP languages.
- ÖFAI-TR-93-02 ( 46kB g-zipped PostScript file)
CLP based HPSG Parsing
- Johannes Matiasek
- We describe a system for principle based parsing of HPSG employing constraint logic programming techniques. Typed features structures are implemented as constraints on PROLOG variables and are instantiated in a lazy fashion. Grammar principles as well as relational constraints are stated in a declarative way by means of conditional constraints on feature structures. The procedural interpretation given to these conditional constraints together with the data driven delay mechanism implemented yields efficient parsing behavior.
- ÖFAI-TR-92-37 ( 48kB g-zipped PostScript file)
A CLP Schema to Integrate Specialized Solvers and its Application to Natural Language Processing
- Bernhard Pfahringer, Johannes Matiasek
- The problem of combining different constraint solvers has been
mentioned among others by (Schroedl 1991, Holzbaur 1990, Lim and Stuckey
1990, Nelson and Oppen 1980) without giving satisfactory solutions. We propose
a general framework for implementing specialized reasoners/constraint
solvers in a logic programming environment using semantic unification.
It allows for a modular and declarative definition of the interactions
of such reasoners. This is achieved by using `attributed variables'
(Huitouze 1990) as a data-structure relating a variable to the `set of all'
constraints for this variable. `Conditional rewrite rules' specify
simplification and possible interactions of these constraints. A few
examples will demonstrate constraints relating to single variables and
interactions thereof. We will demonstrate, how this framework leads to
a very natural and concise formulation of principles, grammar and
lexicon in a HPSG-like formalism. Furthermore the necessity of extending
the framework to handle constraints relating two or more variables will
be discussed.
Keywords: , Constraints, Logic Programming, HPSG
- The problem of combining different constraint solvers has been
mentioned among others by (Schroedl 1991, Holzbaur 1990, Lim and Stuckey
1990, Nelson and Oppen 1980) without giving satisfactory solutions. We propose
a general framework for implementing specialized reasoners/constraint
solvers in a logic programming environment using semantic unification.
It allows for a modular and declarative definition of the interactions
of such reasoners. This is achieved by using `attributed variables'
(Huitouze 1990) as a data-structure relating a variable to the `set of all'
constraints for this variable. `Conditional rewrite rules' specify
simplification and possible interactions of these constraints. A few
examples will demonstrate constraints relating to single variables and
interactions thereof. We will demonstrate, how this framework leads to
a very natural and concise formulation of principles, grammar and
lexicon in a HPSG-like formalism. Furthermore the necessity of extending
the framework to handle constraints relating two or more variables will
be discussed.
- ÖFAI-TR-92-31
How to Integrate Specialized Solvers: A CLP Approach
- Bernhard Pfahringer
- The problem of combining different constraint solvers has been
mentioned by among others (Schroedl 1991, Holzbaur 1990, Lim and Stuckey
1990, Nelson and Oppen 1980) without giving satisfactory solutions. We
will outline a general framework, that if followed when implementing
specialized reasoners/constraint solvers in a logic programming
environment using semantic unification, allows for a modular and
declarative definition of the interactions of such reasoners. This is
achieved by using `attributed variables' (Huitouze 1990) as a
data-structure relating a variable to the `set of all' constraints
for this variable. `Conditional rewrite rules' specify interaction
and simplification of these constraints. A few very simple examples
will demonstrate constraints relating to single variables and
interactions thereof. We will further discuss the necessity of
extending the framework to handle constraints relating two or more
variables. A proof-of-concept implementation has been done and is
currently being optimized.
Keywords: , Semantic Unification, Constraints, Logic Programming
- The problem of combining different constraint solvers has been
mentioned by among others (Schroedl 1991, Holzbaur 1990, Lim and Stuckey
1990, Nelson and Oppen 1980) without giving satisfactory solutions. We
will outline a general framework, that if followed when implementing
specialized reasoners/constraint solvers in a logic programming
environment using semantic unification, allows for a modular and
declarative definition of the interactions of such reasoners. This is
achieved by using `attributed variables' (Huitouze 1990) as a
data-structure relating a variable to the `set of all' constraints
for this variable. `Conditional rewrite rules' specify interaction
and simplification of these constraints. A few very simple examples
will demonstrate constraints relating to single variables and
interactions thereof. We will further discuss the necessity of
extending the framework to handle constraints relating two or more
variables. A proof-of-concept implementation has been done and is
currently being optimized.
- ÖFAI-TR-92-27 ( 47kB g-zipped PostScript file)
Attributed Equivalence Classes in Prolog Implementations of CLP Languages
- Christian Holzbaur
- We introduce attributed equivalence classes as an explicit abstract data type for the representation and manipulation of general equation systems where the decision algorithm is based on quantifier elimination. The partition of quantifiers into equivalence classes results very naturally from a simple abstraction that separates the equation solving process in the object domain from global manipulation of equation systems. We propose and report on an implementation of a linear complexity equivalence relation maintenance algorithm within the framework of logic programming, based on extensible unification. The explicit representation of global aspects of equation systems leads to an object oriented approach to equation solving.
- ÖFAI-TR-92-26 ( 76kB g-zipped PostScript file)
A Polynomial-Time Algorithm for Model-Based Diagnosis
- Igor Mozetic
- We present IDA --- an Incremental Diagnostic Algorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence, by using a `weak' fault model, the worst-case complexity of the algorithm to compute the k+1-st minimal diagnosis is O(n^(2k)), where n is the number of components. On the practical side, an experimental evaluation indicates that the algorithm can efficiently diagnose devices consisting of a few thousand components. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. This fits well into the Constraint Logic Programming modeling paradigm where, for example, combinatorial circuits are modeled by CLPB, analog circuits by CLPR, and physiological models in medicine by constraints over finite domains.
- ÖFAI-TR-92-24 ( 45kB g-zipped PostScript file)
DMCAI CLP Reference Manual
- Christian Holzbaur
- Within the version of SICStus Prolog documented in this manual, the
unification mechanism has been changed in such a way that the user
may introduce interpreted terms and specify their unification through
Prolog predicates. Extensible unification in turn, aims at the
implementation of instances of the general constraint logic
programming (CLP) scheme.
Keywords: , Unification, Implementation, Constraints
- Within the version of SICStus Prolog documented in this manual, the
unification mechanism has been changed in such a way that the user
may introduce interpreted terms and specify their unification through
Prolog predicates. Extensible unification in turn, aims at the
implementation of instances of the general constraint logic
programming (CLP) scheme.
- ÖFAI-TR-92-23 ( 42kB g-zipped PostScript file)
Metastructures vs. Attributed Variables in the Context of Extensible Unification
- Christian Holzbaur
- We relate two mechanisms which aim at the extension of logic
programming languages. The first mechanism directly extends syntactic
unification through the introduction of a data type, whose
(unification) semantics are specified through user-defined predicates.
The second mechanism was utilized for the implementation of
coroutining facilities, and was independently derived with optimal
memory management for various Prolog extensions in mind. Experience
from the application of both mechanisms to the realization of CLP
languages, without leaving the logic programming context, enables us
to reveal similarities and the potential with respect to this task.
Constructive measures that narrow or close the gap between the two
conceptual schemes are provided.
Keywords: , Unification, Implementation, Constraints
- We relate two mechanisms which aim at the extension of logic
programming languages. The first mechanism directly extends syntactic
unification through the introduction of a data type, whose
(unification) semantics are specified through user-defined predicates.
The second mechanism was utilized for the implementation of
coroutining facilities, and was independently derived with optimal
memory management for various Prolog extensions in mind. Experience
from the application of both mechanisms to the realization of CLP
languages, without leaving the logic programming context, enables us
to reveal similarities and the potential with respect to this task.
Constructive measures that narrow or close the gap between the two
conceptual schemes are provided.
- ÖFAI-TR-92-11
Extensible Unification as Basis for the Implementation of CLP Languages
- Christian Holzbaur
- We address various aspects of the proposal to use user-defined
extensible unification as the basic formalism for the implementation
of constraint logic programming (CLP) languages. The close connection
between unification theory and CLP, exhibited through the theoretical
work of Jaffar et al., justifies the proposed step to make this link
explicit and, particularly, operational. We sketch how this can be
done via extensible unification, a single, simple mechanism which
automatically induces a minimum of uniformity in the realization of
CLP languages. If CLP languages are implemented via extensible
unification, they will inherit the capability of being extended on a
sound basis, leading to the attractive construction of towers of
metacircular CLP languages. In the conclusion we report on earlier
and recent work that provides empirical evidence for the feasibility
of the mechanism.
Keywords: , Logic Prog., Unification, Constraints
- We address various aspects of the proposal to use user-defined
extensible unification as the basic formalism for the implementation
of constraint logic programming (CLP) languages. The close connection
between unification theory and CLP, exhibited through the theoretical
work of Jaffar et al., justifies the proposed step to make this link
explicit and, particularly, operational. We sketch how this can be
done via extensible unification, a single, simple mechanism which
automatically induces a minimum of uniformity in the realization of
CLP languages. If CLP languages are implemented via extensible
unification, they will inherit the capability of being extended on a
sound basis, leading to the attractive construction of towers of
metacircular CLP languages. In the conclusion we report on earlier
and recent work that provides empirical evidence for the feasibility
of the mechanism.
- ÖFAI-TR-92-03 ( 34kB g-zipped PostScript file)
CLP(gRel): Explicit Manipulation of (ground) Relational Dependencies in Logic Programming
- Bernhard Pfahringer
- In this paper we introduce CLP(gRel), a kind of CLP language allowing
for explicit manipulation of relational dependencies between
variables. It is a straight-forward generalization of domain
variables, a successful constraint propagation technique
introduced by Van Hentenryck (1989). Domain variables are the special
case of arity one. Unification is extended to handle variables ranging
over relations correctly (and efficiently). Constraints
expressed by variables ranging over relations can be used to
actively prune the search space by detecting combinations of values
that are bound to fail early (cf forward checking (Van
Hentenryck, 1989)). The benefit of relations is demonstrated in
the context of a non-toy problem: diagnostic usage of the KARDIO
system, a qualitative simulation model of the electrical activity of
the heart, is sped up considerably.
Keywords: , Automated Reasoning, Constraint Logic Programming
- In this paper we introduce CLP(gRel), a kind of CLP language allowing
for explicit manipulation of relational dependencies between
variables. It is a straight-forward generalization of domain
variables, a successful constraint propagation technique
introduced by Van Hentenryck (1989). Domain variables are the special
case of arity one. Unification is extended to handle variables ranging
over relations correctly (and efficiently). Constraints
expressed by variables ranging over relations can be used to
actively prune the search space by detecting combinations of values
that are bound to fail early (cf forward checking (Van
Hentenryck, 1989)). The benefit of relations is demonstrated in
the context of a non-toy problem: diagnostic usage of the KARDIO
system, a qualitative simulation model of the electrical activity of
the heart, is sped up considerably.
- ÖFAI-TR-91-17 ( 56kB g-zipped PostScript file)
Model-Based Analogue Circuit Diagnosis with CLP(Re)
- Igor Mozetic, Christian Holzbaur, Franc Novak, Marina Santo-Zarnik
- Model-based diagnosis is the activity of locating malfunctioning components of a system solely on the basis of its structure and behavior. Diagnostic systems usually rely on qualitative models and reason by local constraint propagation methods. However, there is a large class of applications where ATMS-like systems or pure logic programs are unpractical since they are unable to solve simultaneous equations. In particular, modeling real-valued system parameters with tolerances requires some degree of numerical processing, and feedback loops in general cannot be resolved by local constraint propagation methods. Examples of such systems are analogue circuits, e.g., amplifiers or filters. In the paper we describe the role of Constraint Logic Programs over the domain of reals (CLP(Re)) in representing both, qualitative and numerical models. CLP(Re) is a logic programming system extended with a solver for systems of linear equations and inequalities over real-valued variables.
- ÖFAI-TR-91-13 ( 54kB g-zipped PostScript file)
Model-Based Diagnosis with Constraint Logic Programs
- Igor Mozetic, Christian Holzbaur
- Model-based diagnosis is the activity of locating malfunctioning components of a system solely on the basis of its structure and behavior. In the paper we describe the role of Constraint Logic Programming (CLP) in representing models and the search space of minimal diagnoses. In particular, we concentrate on two instances of the CLP scheme: CLP(cal B) and CLP(Re). CLP(cal B) extends the standard computational domain of logic programs by boolean expressions, while CLP(Re) comprises a solver for systems of linear equations and inequalities over real-valued variables.
- ÖFAI-TR-91-03 ( 73kB g-zipped PostScript file)
Controlling the Complexity in Model-Based Diagnosis
- Igor Mozetic, Christian Holzbaur
- We present IDA --- an Incremental Diagnostic Algorithm which computes minimal diagnoses from diagnoses, and not from conflicts. As a consequence of this, and by using different models, one can control the computational complexity. In particular, we show that by using a model of the normal behavior, the worst-case complexity of the algorithm to compute the k+1-st minimal diagnosis is O(n^(2k)), where n is the number of components. On the practical side, an experimental evaluation indicates that the algorithm can efficiently diagnose devices consisting of a few thousand components. We propose to use a hierarchy of models: first a structural model to compute all minimal diagnoses, then a normal behavior model to find the additional diagnoses if needed, and only then a fault model for their verification. IDA separates model interpretation from the search for minimal diagnoses in the sense that the model interpreter is replaceable. In particular, we show that in some domains it is advantageous to use the Constraint Logic Programming system CLPB instead of a logic programming system like Prolog.
- ÖFAI-TR-91-02 ( 54kB g-zipped PostScript file)
Integrating Numerical and Qualitative Models within Constraint Logic Programming
- Igor Mozetic, Christian Holzbaur
- The paper describes an interplay between numerical and qualitative
models in the context of model-based diagnosis. A detailed, numerical
model is used to discriminate between competing diagnoses at the
abstract, qualitative level. Specifically, an abstract diagnosis is
refined in all possible ways, and each refinement is verified at the
detailed level. A distinguishing feature of our approach is that the
abstract proof is used to guide the verification at the detailed
level, and to refute impossible refinements as soon as possible by
introducing additional constraints on the variables. Both, numerical
and qualitative models are interpreted within the same, Constraint
Logic Programming framework. An implemented instance of this
framework, CLP(Re) which is used in the paper, comprises a solver for
systems of linear equations and inequalities over real-valued
variables.
Keywords: ,
- The paper describes an interplay between numerical and qualitative
models in the context of model-based diagnosis. A detailed, numerical
model is used to discriminate between competing diagnoses at the
abstract, qualitative level. Specifically, an abstract diagnosis is
refined in all possible ways, and each refinement is verified at the
detailed level. A distinguishing feature of our approach is that the
abstract proof is used to guide the verification at the detailed
level, and to refute impossible refinements as soon as possible by
introducing additional constraints on the variables. Both, numerical
and qualitative models are interpreted within the same, Constraint
Logic Programming framework. An implemented instance of this
framework, CLP(Re) which is used in the paper, comprises a solver for
systems of linear equations and inequalities over real-valued
variables.
- ÖFAI-TR-90-16 ( 51kB g-zipped PostScript file)
Extending Explanation-Based Generalization by Abstraction Operators
- Igor Mozetic, Christian Holzbaur
- We present two contributions to the explanation-based generalization techniques. First, the operationality criterion is extended by abstraction operators. These allow for the goal concept to be reformulated not only in terms of operational predicates, but also allow to delete irrelevant arguments, and to collapse indistinguishable constants. The abstraction algorithm is presented and illustrated by an example. Second, the domain theory is not restricted to variables with finite (discrete) domains, but can deal with infinite (e.g., real-valued) domains as well. The interpretation and abstraction are effectively handled through constraint logic programming mechanisms. In the paper we concentrate on the role of CLP(R) - a solver for systems of linear equations and inequalities over reals.
- ÖFAI-TR-90-08
Implementation of Constraint Based Inference Mechanisms through Semantic Unification
- Christian Holzbaur
- We present an extension to unification as a general means to smoothly integrate a variety of control and constraint-based inference mechanisms into PROLOG: freeze, forward checking, CLP(B), CLP(R), ... The proposed extension entails virtually no overhead to programs which do not use it, provided the hook into unification is installed properly. The extension does not disable the standard optimization techniques like clause indexing and last call optimization. A distinguishing feature of our approach is that extended theories themselves are implemented in PROLOG - in contrast to the majority of current implementations in C. The advantages are obvious - the time needed for implementation and modification is reduced, and the resulting programs are in a high-level, transparent language. On the other hand, the efficiency reduction is much lower then expected. We outline our implementation of the extended unification in a standard PROLOG interpreter, and an implementation of two extended theories: forward checking and CLP(R). Our experiments with a partial implementation of CLP(R) indicate that a modern compiler with decent garbage collection would achieve almost the same efficiency as a dedicated implementation in C.
- ÖFAI-TR-90-02
Metastructures as a Basis for the Implementation of Constraint Logic Programming Techniques
- Christian Holzbaur
- The aim of this paper is to show that a simple extension to ordinary
unification is sufficient to implement a variety of constraint
programming techniques. The nonstandard part of the extended
unification algorithm is formulated in PROLOG as opposed to most of
the current implementations of extensions - which are either emulated
by metainterpreters or are coded in the implementation language of
the corresponding PROLOG system. The proposed extension is
conservative in the sense that, given the hook into unification is
installed properly, it entails virtually no costs to programs that
don't use the extension. The extension does not disable standard
optimization techniques like clause indexing and last call
optimization. A definition of a metainterpreter is presented to be
used as a specification of the extension. Unfortunately it cannot be
used directly or folded into application programs, because it rests so
deep in the bowels of the computation and has to be applied to each
and every predicate. As the proposed implementation provides just a
hook into unification, the efforts to provide it should be modest on
a variety of PROLOG implementations. The extensions to syntactical
unification are specified in the language the user is already
familiar with. The implementation of fully general nondeterministic
unification and/or the implementation of CLP solvers should become
more portable, more reliable and easier to debug and maintain.
Keywords: , Constraints, Unification, Metaprogramming
- The aim of this paper is to show that a simple extension to ordinary
unification is sufficient to implement a variety of constraint
programming techniques. The nonstandard part of the extended
unification algorithm is formulated in PROLOG as opposed to most of
the current implementations of extensions - which are either emulated
by metainterpreters or are coded in the implementation language of
the corresponding PROLOG system. The proposed extension is
conservative in the sense that, given the hook into unification is
installed properly, it entails virtually no costs to programs that
don't use the extension. The extension does not disable standard
optimization techniques like clause indexing and last call
optimization. A definition of a metainterpreter is presented to be
used as a specification of the extension. Unfortunately it cannot be
used directly or folded into application programs, because it rests so
deep in the bowels of the computation and has to be applied to each
and every predicate. As the proposed implementation provides just a
hook into unification, the efforts to provide it should be modest on
a variety of PROLOG implementations. The extensions to syntactical
unification are specified in the language the user is already
familiar with. The implementation of fully general nondeterministic
unification and/or the implementation of CLP solvers should become
more portable, more reliable and easier to debug and maintain.