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

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Details

The purpose of this milestone is to implement the core of the logical resolution process used to answer queries: the unification 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 find a set of substitutions for variables that will make two expressions equivalent. This process is called unification.

 

For example consider two vt-prolog expressions

 

and

 

as expression trees. Unification will

 

find 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, unification acts like a test for equality. For example

and f(a,g(b,c)) unify under the empty substitution. Unification 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 unification. 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 unification algorithm returns a result consisting of a Boolean flag indicating if unification succeeded and if true the associated substitution. We can easily define 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

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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