OFAI

Technical Reports - Query Results

Your query term was 'all = clp'
26 reports found
Reports are sorted by descending number

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

Citation: Holzbaur C., Menezes F., Barahona P.: Defasibility in CLP(Q) through Generalized Slack Variables, Proc. of the Second International Conference on Principles and Practice of Consstraint Programming (CP96), Cambridge, Massachusetts, USA, August 19-22, 1996.


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

Citation: El Fattah Y.: Constraint Logic Programming for Qualitative Reasoning about Dynamic Behavior, Austrian Research Institute for Artificial Intelligence, Vienna, TR-95-24, 1995.


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

Citation: Holzbaur C.: OEFAI clp(q,r) Manual Rev. 1.3.2, Austrian Research Institute for Artificial Intelligence, Vienna, TR-95-09, 1995.


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

Citation: El Fattah Y., Holzbaur C.: A CLP approach to Detection and Identification of Control System Component Failures, Austrian Research Institute for Artificial Intelligence, Vienna, TR-94-25, 1994.


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

Citation: El Fattah Y.: Constraint Logic Programming for Structure-Based Reasoning about Dynamic Physical System, Austrian Research Institute for Artificial Intelligence, Vienna, TR-94-17, 1994.


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

Citation: Holzbaur C.: A Specialized, Incremental Solved Form Algorithm for Systems of Linear Inequalities, Austrian Research Institute for Artificial Intelligence, Vienna, TR-94-07, 1994.


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

Citation: Trost H., Matiasek J.: Morphology with a Null-Interface, Proc. COLING-94


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

Citation: Matiasek J., Heinz W.: A CLP Based Approach to HPSG, Austrian Research Institute for Artificial Intelligence, Vienna, TR-93-26, 1993.


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

Citation: Mozetic I., Novak F., Santo-Zarnik M., Biasizzo A.: Diagnosing Analog Circuits Designed-for-Testability by Using CLPR, Proc. 4th Intl. Workshop on Principles of Diagnosis, DX-93, pp. 105-120, University of Wales, Aberystwyth, September 6-8, 1993.


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

Citation: Mozetic I., Holzbaur C.: Interval Arithmetic with CLPR, Austrian Research Institute for Artificial Intelligence, Vienna, TR-93-19, 1993.


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

Citation: Matiasek J.: CLP based HPSG Parsing, Austrian Research Institute for Artificial Intelligence, Vienna, TR-93-02, 1993.


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

Citation: Pfahringer B., Matiasek J.: A CLP Schema to Integrate Specialized Solvers and its Application to Natural Language Processing, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-37, 1992.


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

Citation: Pfahringer B.: How to Integrate Specialized Solvers: A CLP Approach, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-31, 1992.


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

Citation: Holzbaur C.: Attributed Equivalence Classes in Prolog Implementations of CLP Languages, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-27, 1992.


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

Citation: Mozetic I.: A Polynomial-Time Algorithm for Model-Based Diagnosis, Extended version of a paper in Proc. 10th European Conf. on Artificial Intelligence, ECAI-92, pp. 729-733, Vienna, Austria, John Wiley and Sons, 1992.


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

Citation: Holzbaur C.: DMCAI CLP Reference Manual, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-24, 1992.


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

Citation: Holzbaur C.: Metastructures vs. Attributed Variables in the Context of Extensible Unification, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-23, 1992.


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

Citation: Holzbaur C.: Extensible Unification as Basis for the Implementation of CLP Languages, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-11, 1992.


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

Citation: Pfahringer B.: CLP(gRel): Explicit Manipulation of (ground) Relational Dependencies in Logic Programming, Austrian Research Institute for Artificial Intelligence, Vienna, TR-92-03, 1992.


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

Citation: Mozetic I., Holzbaur C., Novak F., Santo-Zarnik M.: Model-Based Analogue Circuit Diagnosis with CLP(Re), Proc. 4th Intl. GI Congress (W. Brauer, D. Hernandez, Eds.), pp. 343-353, München, Germany, October 23-24, 1991, Springer-Verlag, Berlin.


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

Citation: Mozetic I., Holzbaur C.: Model-Based Diagnosis with Constraint Logic Programs, Proc. 7th Austrian Conf. on AI (H. Kaindl, Ed.), pp. 168-180, September 24-27, 1991, Vienna, Austria, Springer-Verlag, Berlin.


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

Citation: Mozetic I., Holzbaur C.: Controlling the Complexity in Model-Based Diagnosis, Annals of Mathematics and Artificial Intelligence 11 (1-4), pp. 297-314, 1994.


OFAI-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: ,

Citation: Mozetic I., Holzbaur C.: Integrating Numerical and Qualitative Models within Constraint Logic Programming, Proc. 1991 Intl. Logic Programming Symposium, ILPS-91 (V. Saraswat, K. Ueda, Eds.), pp. 678-693, San Diego, CA, October 28-31, 1991, The MIT Press.


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

Citation: Mozetic I., Holzbaur C.: Extending Explanation-Based Generalization by Abstraction Operators, Proc. European Working Session on Learning, EWSL-91, pp. 282-297, Porto, Portugal, March 6-8, 1991, Springer-Verlag.


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

Citation: Holzbaur C.: Implementation of Constraint Based Inference Mechanisms through Semantic Unification, Austrian Research Institute for Artificial Intelligence, Vienna, TR-90-08, 1990.


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

Citation: Holzbaur C.: Metastructures as a Basis for the Implementation of Constraint Logic Programming Techniques, Austrian Research Institute for Artificial Intelligence, Vienna, TR-90-02, 1990.