(5/5)

Details

The purpose of this milestone is to implement the core of the logical resolution process used to answer queries: the uniﬁcation algorithm.

Unification in First-Order Logic

Over the next three milestones we will be implementing the ability make queries against a knowledge-

base by implementing the

member of the

class. An important step in the process

will be to ﬁnd a set of substitutions for variables that will make two expressions equivalent. This process is called uniﬁcation.

For example consider two vt-prolog expressions

and

as expression trees. Uniﬁcation will

ﬁnd an assignment of the variable that will make the two trees (and thus expressions) identical. This

is obviously X/a in this simple example, where the slash is read as “substituted by”, i.e. “X substituted

by a” or f(a) and unify under the substitution .

Substitutions can replace whole subtrees as well. For example, trying to unify and f(X,b)

succeeds under the substitution the two expressions equivalent.

, i.e. the variable

must be replaced by the tree g(a) to make

In some cases, when there are no variables, uniﬁcation acts like a test for equality. For example

and f(a,g(b,c)) unify under the empty substitution. Uniﬁcation can also fail, for example

by trying to unify f(a,b) and .

Finally, when we have multiple expressions, as in the clauses of a knowledge-base, we might have multiple valid substitutions. For example given the simple knowledge-base consisting of just facts:

should unify with two of the three expressions, giving the substitution complicated in the case of rules, which we postpone to milestone 9.

Thus we see that we need to next implement two new pieces of code: a data structure to hold (possibly multiple) substitutions, and an algorithm to perform uniﬁcation. That is the focus of this

milestone, which will introduce a new module:

, and

with associated

unit tests .

Substitution Set

The data structure for holding substitutions needs to be able to map from expression trees, to multiple, arbitrary trees as fast as possible. We will need to be able to insert a substitution, lookup substitutions, and iterate through the set of substitutions. You should choose an appropriate container from the

standard library and typedef it to the type .

You should then implement, in the namespace vtpl, the class with the following interface:

class Substitution { public:

typedef typename SubstitutionData::iterator IteratorType;

typedef typename SubstitutionData::const_iterator ConstIteratorType;

// lookup an expression key in the substitution set and return a list of Expressions

// the key maps to, or a list of size zero if no mapping exists

std::list<ExpressionTreeNode> lookup(const ExpressionTreeNode& key) const;

// insert a mapping from Expression key to Expression value, appending it if a mapping already exists. void insert(const ExpressionTreeNode & key, const ExpressionTreeNode & value);

// return an iterator to the first element of the arbitrarily ordered set IteratorType begin();

// return an iterator to one past the last element of the arbitrarily ordered set IteratorType end();

// return a const iterator to the first element of the arbitrarily ordered set ConstIteratorType constBegin() const;

// return an const iterator to one past the last element of the arbitrarily ordered set ConstIteratorType constEnd() const;

private:

// TODO

};

Unification Algorithm

The uniﬁcation algorithm returns a result consisting of a Boolean ﬂag indicating if uniﬁcation succeeded and if true the associated substitution. We can easily deﬁne a type to hold this as follows:

The following function should take two expression trees and an initial substitution set, and attempt to

unify them, modifying the passed

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of