_DIRECTED ACYCLIC GRAPH UNIFICATION_
by David Perelman-Hall

Listing One

/*************************************************************************
       Base Value class and ValuePtr class 
       Copyright David Perelman-Hall & Jamshid Afshar 1994.
*************************************************************************/

#ifndef VALUE_H
#define VALUE_H

#include "misc.h"    // GATHERED INCLUDES.  HELPS WITH PRE-COMPILED HEADERS.

// Forward References
class SubstitutionList;
class Value;

// Pointer (or Reference) class to a Value
class ValuePtr {
friend ostream& operator << (ostream& os, const ValuePtr& vp);
private:
   Value* _ptr;
public:
   ValuePtr();
   ValuePtr(const ValuePtr& vp);
   ValuePtr(const Value& v);
   ~ValuePtr();
   void operator=(const ValuePtr& vp);
   bool operator==(const ValuePtr& vp) const;
   bool operator!=(const ValuePtr& vp) const;
   const Value* operator->() const;
   const Value& operator*() const;
   operator const void*() const { return _ptr; }
};
// FORWARD REFERENCES TO CLASSES DERIVING FROM VALUE
class AtomicValue;
class VariableValue;
class DagValue;
class Value {
   public:
      //void CTOR
      Value() {}
      virtual Value* copy() const = 0;
      virtual void write(ostream& os, int level=0) const = 0;
      virtual bool operator == (const Value& value) const = 0;
      virtual bool operator == (const AtomicValue&) const { return FALSE; }
      virtual bool operator == (const VariableValue&) const { return FALSE; }
      virtual bool operator == (const DagValue&) const { return FALSE; }
      virtual bool unify(const Value& value, SubstitutionList&, 
                                                          ValuePtr&) const = 0;
      virtual bool unify(const AtomicValue&, SubstitutionList&, 
                                                              ValuePtr&) const;
      virtual bool unify(const VariableValue&, SubstitutionList&, 
                                                              ValuePtr&) const;
      virtual bool unify(const DagValue&, SubstitutionList&, ValuePtr&) const;
      virtual ValuePtr substitute(const SubstitutionList& substList) const = 0;
};
inline
ostream& operator << (ostream& os, const Value& v)
{
   v.write(os);
   return os;
}
inline ValuePtr::ValuePtr() : _ptr(0) { }
inline ValuePtr::ValuePtr(const ValuePtr& vp) : _ptr(vp._ptr->copy()) { }
inline ValuePtr::ValuePtr(const Value& v) : _ptr(v.copy()) { }
inline ValuePtr::~ValuePtr() { delete _ptr; _ptr=0; }
inline void ValuePtr::operator=(const ValuePtr& vp){
   if(_ptr!=0)
      delete _ptr; 
   if(vp._ptr != 0)
      _ptr = vp._ptr->copy();
   else
      _ptr = 0;
}
inline bool ValuePtr::operator==(const ValuePtr& vp) const
   { return (*_ptr) == *(vp._ptr); }
inline bool ValuePtr::operator!=(const ValuePtr& vp) const
   { return !( *this == vp ); }
inline const Value* ValuePtr::operator->() const { assert(_ptr != 0); 
                                                                return _ptr; }
inline const Value& ValuePtr::operator*() const { assert(_ptr != 0); 
                                                                return *_ptr; }
inline ostream& operator << (ostream& os, const ValuePtr& vp)
{
   assert(vp._ptr != 0);
   os << *(vp._ptr);
   return os;
}
#endif


Listing Two

#include "misc.h"    // GATHERED INCLUDES.  HELPS WITH PRE-COMPILED HEADERS
#pragma hdrstop      // END OF PRE-COMPILED HEADER INCLUDES

//PROTOTYPED FOR EACH DERIVED CLASS
bool Value::unify(const AtomicValue&, SubstitutionList&, ValuePtr&) const
   { return FALSE; }
bool Value::unify(const VariableValue&, SubstitutionList&, ValuePtr&) const
   { return FALSE; }
bool Value::unify(const DagValue&, SubstitutionList&, ValuePtr&) const
   { return FALSE; }


Listing Three

/*************************************************************************
   AtomicValue class -- Copyright David Perelman-Hall & Jamshid Afshar 1994.
*************************************************************************/

#ifndef ATOMIC_H
#define ATOMIC_H

#include <cstring.h>    // BORLAND HEADER
#include "value.h"      // BASE VALUE & VALUEPTR CLASSES

typedef string String;
#define Atomic String

class AtomicValue : public Value, public Atomic {
   public:
      //EMPTY CTOR
      AtomicValue(){}
      //COPY CTOR
      AtomicValue( const AtomicValue& value ) : Atomic(value) { }
      //CONSTRUCTOR
      AtomicValue( const String& str ) : Atomic(str) { }
      //CONSTRUCTOR
      AtomicValue( const char* s ) : Atomic(s) { }
      //RETURN POINTER TO NEW ATOMIC VALUE COPY CONSTRUCTED FROM THIS
      Value* copy() const { return new AtomicValue(*this); }
      // EXPLICIT STRING CONVERSION
      const String& str() const { return (const Atomic&)*this; }
      //ASSIGNMENT OPERATOR
      void operator = (const AtomicValue& value) { Atomic::operator=(value); }
      //EQUALITY
      virtual bool operator == (const Value& value) const;
      virtual bool operator == (const AtomicValue& value) const;
      // UNIFY
      virtual bool unify(const Value& value, SubstitutionList& subst, 
                                                      ValuePtr& result) const;
      virtual bool unify(const AtomicValue& value, SubstitutionList& /*subst*/,
                                                      ValuePtr& result) const;
      // OUTPUT
      virtual void write(ostream& os, int level) const 
                                                { os << (const Atomic&)*this; }
      // SUBSTITUTE
      virtual ValuePtr substitute(const SubstitutionList& /*substList*/) const
         {  return *this; }
};
#endif


Listing Four

#include "misc.h"
#pragma hdrstop

//PROTOTYPED FOR BASE CLASS
bool AtomicValue::operator == (const Value& value) const
   { return value==*this; }
//PROTOTYPED FOR ATOMIC VALUE
bool AtomicValue::operator == (const AtomicValue& value) const
   { return (Atomic&)*this == (Atomic&)value; }
//PROTOTYPED FOR BASE CLASS
bool AtomicValue::unify(const Value& value, SubstitutionList& subst, 
                                                       ValuePtr& result) const
      { return value.unify(*this, subst, result); }
//PROTOTYPED FOR ATOMIC VALUE
bool AtomicValue::unify(const AtomicValue& value, SubstitutionList& /*subst*/,
                                                        ValuePtr& result) const
{ 
   if (value == *this) {
      result = *this;
      return TRUE; 
   }
   else {
      return FALSE; 
   }
}


Listing Five

/*************************************************************************
VariableValue class -- Copyright David Perelman-Hall & Jamshid Afshar 1994.
*************************************************************************/

#ifndef VARIABLE_H
#define VARIABLE_H

#include <cstring.h>    // BORLAND HEADER
#include "value.h"      // BASE VALUE CLASS

typedef string Variable;  // BORLAND

Variable gensym();

class VariableValue : public Value {
private:
   Variable _v;
public:
   //empty constructor
   VariableValue(){}
   //copy constructor
   VariableValue( const VariableValue& value ) : _v(value._v) { }
   VariableValue( const Variable& var ) : _v(var) { }
   Value* copy() const { return new VariableValue(*this); }
   const Variable& str() const { return _v; }

   //assignment operator
   void operator = (const VariableValue& value) { _v = value._v; }
   virtual bool operator == (const Value& value) const;
   virtual bool operator == (const VariableValue& value) const;
   virtual bool unify(const Value& value, SubstitutionList& subst, 
                                                       ValuePtr& result) const;
   virtual bool unify(const AtomicValue&, SubstitutionList&, 
                                                       ValuePtr& result) const;
   virtual bool unify(const VariableValue& var, SubstitutionList& subst, 
                                                       ValuePtr& result) const;
   virtual bool unify(const DagValue&, SubstitutionList&, 
                                                       ValuePtr& result) const;
   virtual void write(ostream& os, int level) const { os << _v; }
   virtual void read(istream& is) { is >> _v; }
   virtual ValuePtr substitute(const SubstitutionList& substList) const;
};
#endif


Listing Six

#include "misc.h"
#pragma hdrstop
#include <stdio.h>

Variable gensym()
{
   static unsigned i = 0;
   char sym[20];
   sprintf(sym, "_X%ud", i++);
   return Variable(sym);
}
bool VariableValue::unify(const Value& value, SubstitutionList& subst, 
                                                        ValuePtr& result) const
{ 
   if (!value.unify(*this, subst, result)) {
      if (!subst.set(_v, value)) 
         return FALSE;
      result = value;
   }
  return TRUE;
}
bool VariableValue::unify(const AtomicValue& value, SubstitutionList& subst, 
                                                        ValuePtr& result) const
{ 
   if( !subst.set(_v, value) )
      return FALSE;
  result = value; 
  return TRUE;
}
bool VariableValue::unify(const VariableValue& var, SubstitutionList& subst, 
                                                        ValuePtr& result) const
{ 
   if( !subst.set_identical(_v, var.str()) ) {
      //cerr << "unify vars (" << *this << "," << var << ")\n"; //##
      return FALSE;
   }
   result = var; 
   return TRUE;
}
bool VariableValue::unify(const DagValue& value, SubstitutionList& subst, 
                                                        ValuePtr& result) const
{
   if( !subst.set(_v, value) )
      return FALSE;
   result = value; 
   return TRUE; 
}
ValuePtr VariableValue::substitute(const SubstitutionList& substList) const
{ 
   if( substList.contains(_v) )
      return substList.val(_v);
   else
      return VariableValue(_v);
}
bool VariableValue::operator == (const Value& value) const
{ return value==*this; }
bool VariableValue::operator == (const VariableValue& /*value*/) const
{ return TRUE;/*## _v == value._v;*/ }


Listing Seven

/*************************************************************************
   DagValue class -- Copyright David Perelman-Hall & Jamshid Afshar 1994.
*************************************************************************/

#ifndef DAG_H
#define DAG_H

#include "misc.h"
#include "value.h"
#include "atomic.h"
#include "variable.h"

typedef MapOf<Feature, ValuePtr> FVList;
typedef MapOfIter<Feature, ValuePtr> FVListIter;

class Dag {
public:
   // CONSTRUCTOR
   Dag():_datap(new Data){}
   // COPY CONSTRUCTOR 
   Dag(const Dag& dag): _datap(dag._datap){}
   // DESTRUCTOR
   ~Dag(){}
   // ASSIGNMENT OPERATOR
   void operator=(const Dag& dag){_datap=dag._datap;}
   // ADD A FEATURE-VALUE PAIR TO THIS DAG
   void add(const Feature& f, const ValuePtr& vp){own_fvlist().enter(f,vp);}
   // EQUALITY OPERATORS
   bool operator==(const Dag& dag) const;
   bool operator!=(const Dag& dag) const {return !operator==(dag);}
   // CLEAR DATA FROM THIS DAG
   void clear(void){own_fvlist().clear();}
   // TEST FOR EXISTENCE OF FEATURE IN THIS DAG
   bool contains(const Feature& feature) const {
      return fvlist().contains(feature);
   }
   // RETRIEVE VALUE ASSOCIATED WITH FEATURE 
   ValuePtr value(const Feature& feature) const {
      if(!fvlist().contains(feature)){
         cerr << "Dag " << *this << " does not have feature " << feature
         << endl;
      }
      assert(fvlist().contains(feature));
      return fvlist().valueOf(feature);
   }
   // RETRIEVE THE LIST OF FEATURES OF THIS DAG
   FeatureSet list_features() const;
   // SET SUBSTITUTION FOR VARIABLES 
   Dag substitute(const SubstitutionList& substList) const;
   // APPLY SUBSTITUTION
   static Dag apply_substitution(const Dag& dag,
      const SubstitutionList& substList){return dag.substitute(substList);}
   // OUTPUT OPERATOR
   void write(ostream& os, int level) const;
   // IOSTREAM OPERATORS
   friend ostream& operator << ( ostream& os, const Dag& dag );
   //friend istream& operator >> ( istream& is, Dag& dag );
private:
   struct Data {
      FVList fvs;
      Data() {}
      Data(const FVList& map) : fvs(map) {}
   };
   Data *_datap;
   const FVList& fvlist() const {return _datap->fvs;}
   FVList& own_fvlist() {return _datap->fvs;}
};
/*
inline
istream& operator >> ( istream& is, Dag& dag )
{ 
   is >> dag.own_fvlist(); 
   return is;
}
*/
// DECLARATION OF GLOBAL UNIFY WHICH ACTUALLY UNIFIES TWO DAGs
bool unify(const Dag& dag1, const Dag& dag2, SubstitutionList& subst,
                                                                  Dag& result);
// DECLARATION & DEFINITION OF GLOBAL UNIFY TAKING TWO DAG REFERENCES,
// DOES NOT ACTUALLY UNIFY, BUT RETURNS BOOLEAN TEST ON THEIR UNIFICATION
inline
bool unify(const Dag& dag1, const Dag& dag2){
   SubstitutionList subst;
   Dag result;
   return unify(dag1, dag2, subst, result);
}
// MAKE DAG_LIST CLASS
typedef ListOf<Dag> DagList;
typedef ListOfIter<Dag> DagIter;

ostream& operator<<(ostream& os, const ListOf<Dag>& list);

class DagValue : public Value {
private:
   Dag _d;
public:
   //empty constructor
   DagValue(){}
   //copy constructor
   DagValue( const DagValue& value ) : _d(value._d) { }
   DagValue( const Dag& dag ) : _d(dag) { }
   Value* copy() const { return new DagValue(*this); }
   //assignment operator
   void operator = (const DagValue& value) { _d = value._d; }

   virtual bool operator == (const Value& value) const
      { return value==*this; }
   virtual bool operator == (const DagValue& value) const
      { return _d==value._d; }
   virtual bool unify(const Value& value, SubstitutionList& subst, 
                                                        ValuePtr& result) const
      { return value.unify(*this, subst, result); }
   virtual bool unify(const DagValue& value, SubstitutionList& subst, 
                                                       ValuePtr& result) const;
   virtual void write(ostream& os, int level) const;
   //virtual void read(istream& is) { is >> _d; }
   virtual ValuePtr substitute(const SubstitutionList& substList) const;
};
#endif


Listing Eight

#include "misc.h"
#pragma hdrstop

// DAG SPECIFIC OSTREAM OPERATOR
ostream& operator << ( ostream& os, const Dag& dag )
{
   dag.write(os, 0);
   return os;
}
// DAG SPECIFIC OUTPUT OPERATOR
void Dag::write(ostream& os, int level) const
{
   os << "[";
   for (FVListIter i(&fvlist()); !i.offEnd(); i.next()) {
      os << i.key() << " : ";
      i.value()->write(os, level+1);
      if (!i.last()) {
               os << "\n";
               for (int i=0; i<level; i++)
                  os << "   ";
               os << " ";
         os << " | ";
         }
      }
   os << "]";
}
// RETRIEVE THE LIST OF FEATURES OF THIS DAG
FeatureSet Dag::list_features() const 
{
   // CREATE A SET OF KEYS TO RETURN
   FeatureSet tmp_features(fvlist().keys(),fvlist().size());
   // RETURN IT
   return tmp_features;
}
// EQUALITY OPERATOR
bool Dag::operator==(const Dag& d) const
{
   // TYPEDEF AN ITERATOR OVER A MAP FROM FEATURES TO VALUE POINTERS
   typedef MapOfIter<Feature, ValuePtr> FVIter;
   // STEP SIUMULTANEOUSLY THROUGH LIST OF FEATURES 
   for (FVIter fv1(&this->fvlist()), fv2(&d.fvlist()); 
                       !fv1.offEnd() && !fv2.offEnd(); fv1.next(), fv2.next()){
      // IF EITHER CURRENT FEATURES OR CURRENT VALUES DON'T MATCH, RETURN FALSE
      if (fv1.key()!=fv2.key() || fv1.value()!=fv2.value())
         return FALSE;
   }
   // RETURN TRUE IF STEPPED ENTIRELY THROUGH BOTH LISTS, ELSE RETURN FALSE
   return fv1.offEnd() && fv2.offEnd();
}
// SUBSTITUTE
Dag Dag::substitute(const SubstitutionList& substList) const
{
   // RETURN DAG
   Dag tmpDag;
   // LIST OF FEATURES IN THIS DAG
   FeatureSet features=list_features();
   // STEP THROUGH LIST OF FEATURES FROM THIS DAG
   for (SetOfIter<Feature> feature(&features); feature; ++feature)
      // ADD TO RETURN DAG THE FEATURE AND ANY VALUE LISTED FOR IT IN THE
      // SUBSTITUTION LIST, AS FOLLOWS:
      // 1) IF THERE IS A SUBSTITUTION FOR IT AND THE VALUE IS A
      //    VARIABLE, ADD WHATEVER EXISTS IN THE SUBSTITUTION LIST
      //    FOR THAT VARIABLE,
      // 2) IF THERE IS NO SUBSTITUTION FOR IT AND THE VALUE IS A
      //    VARIABLE, ADD THE VARIABLE,
      tmpDag.add(feature(),value(feature())->substitute(substList));
   // RETURN THE CREATED DAG
   return tmpDag;
}
// OUTPUT OPERATOR FOR A DAGVALUE
void DagValue::write(ostream& os, int level) const
{
   _d.write(os, level);
}
bool DagValue::unify(const DagValue& value, SubstitutionList& subst, 
                                                        ValuePtr& result) const
{
   Dag unification;
   // CALL GLOBAL FUNCTION, PASSING 2 DAGs
   if (::unify(_d, value._d, subst, unification)) {
      result = DagValue(unification);
      return TRUE;
   }
   else {
      return FALSE;
   }
}
ValuePtr DagValue::substitute(const SubstitutionList& substList) const
{ return DagValue(_d.substitute(substList)); }
// GLOBAL UNIFY FUNCTION
bool unify(const Dag& dag1,const Dag& dag2,SubstitutionList& subst,Dag& result)
{
   // GET SET OF ALL FEATURES FROM BOTH DGAS
   FeatureSet features = dag1.list_features() + dag2.list_features();
   {
   for (SetOfIter<Feature> feature(&features); feature; ++feature) {
      // TRY TO UNIFY VALUES WHERE FEATURE IS COMMON TO BOTH DAGS
      if (dag1.contains(feature()) && dag2.contains(feature())) {
         // cout << "Attempting to unify feature " << feature() 
                                                   << " in both dags." << endl;
         ValuePtr unified_value; // HOLD THE RESULT OF SUCCESSFUL UNIFICATION

         // CALL VALUE::UNIFY THROUGH VALUEPTR WRAPPER, BUILD UP SUBSTITUTION 
         // LIST & RESULTING DAG
         if (dag1.value(feature())->unify(*(dag2.value(feature())), subst, 
                                                              unified_value)) {
            result.add(feature(), unified_value);
         }
         else { // FAILED TO UNIFY VALUES FOR FEATURE COMMON TO BOTH DAGS
            cout << dag1.value(feature()) << " and " << dag2.value(feature()) 
                                                  << " did not unify." << endl;
            return FALSE;
            }
      }
      else { // ADD FEATURE-VALUE WHERE EXISTS IN ONE DAG ONLY
         if(dag1.contains(feature()))
            result.add(feature(), dag1.value(feature()));
         else
            result.add(feature(), dag2.value(feature()));
      }
   }
   }
   Dag result_with_subst;
   {
   // DO VARIABLE SUBSTITUTIONS BUILT UP IN PREVIOUS LOOP
   for (SetOfIter<Feature> feature(&features); feature; ++feature) {
      result_with_subst.add(feature(), 
                                   result.value(feature())->substitute(subst));
   }
   }
   result = result_with_subst;
   return TRUE;
}


Example 1: Grammar 1.

S -> NP VP      (Sentence may be written as Noun Phrase then Verb Phrase)
VP -> V NP      (Verb Phrase may be writen as Verb then Noun Phrase)
NP -> DET N     (Noun Phrase may be written as Determiner then Noun)
N -> "cow"      (Noun may be written as "cow")
N -> "grass"        (Noun may be written as "grass")
V -> "eats"     (Verb may be written as "eats")
DET -> "the"        (Determiner may be written as "the")


Example 2:

S -> NP VP
<NP number>=<VP number>


Example 3: Grammar 2.

S -> NP VP
<NP agreement> = <VP agreement>
<NP case> = nominative
<VP subcat> = transitive
VP -> V
<VP agreement> = <V agreement>
<VP subcat> = <instransitive>
<VP subcat> = <V subcat>
VP -> V NP
<VP agreement> = <V agreement>
<VP subcat> = <transitive>
<VP subcat> = <V subcat>
NP -> DET N
<NP agreement> = <N agreement>
<NP agreement number> = <DET number>
N -> "cow"
<N number> = <singular>
N -> "grass"
<N number> = <singular>
V -> "eat"
<V number> = <plural>
<VP subcat> = <transitive>
V -> "eats"
<V number> = <singular>
<VP subcat> = <transitive>
DET -> "the"
<N number> = <N agreement>