Symbolic Logic:Programming:Value Set Implementation

From Knowino
Jump to: navigation, search

The laws describing Value Sets show that when a function is applied to parameters the result is in the cartesian product of the set of input values for the parameters, and that each value in this result set has a Possible World which is the intersection of the Possible Worlds from which the values came.

This Possible World is then empty if,

The implementation of Value Sets is based on these rules. There is a large overhead with working with Value Sets, and the size of Value Sets may increase exponentially. This needs to be minimized.

Value Sets are not needed in many situations. The implementation of Value Sets is intended for those situations where multiple values may be possible. The CLP should only use Value Sets when they are needed.

The implementation of Value Sets needs to create cartesian products of value sets only when looking at the individual values. Many functions can pass the value sets through to primitive built in functions like + - * /.

Primarily it is the primitive built in operations in the language that need to build cartesian products of value sets.

Contents

[edit] Possible World Class

[edit] Design

Primary possible worlds are constructed for every value for a variable. These Possible Worlds are the parent worlds out of which the other worlds are constructed. They have an identity, and may be empty or not empty.

When a Cartesian product of value sets is constructed Possible Worlds are created from the intersection of Possible Worlds from the source Value Sets. These are secondary Possible Worlds.

A secondary Possible World is always the intersection of a set of possible worlds. A secondary Possible World object has a list of Possible Worlds, called the parent Possible Worlds. A secondary Possible World is the intersection of its parents.

A primary Possible World has an empty list of parent Possible Worlds.

[edit] Checking for duplicate Possible Worlds

The full list of primary Possible Worlds obtained from recursively visiting all the parents of a Possible World identifies it. Before constructing a new Possible World out of a set of we need to check that no Possible World object exists representing the same Possible World.

When we need a world which has a particular set of primary worlds a Hash Map is used to check if a Possible World object has already been created. The key for this look up is the sorted list of primary worlds. A hash function would be formed from this list.

[edit] Testing a Possible World

To test if a Possible World is empty first traverse the Possible Worlds recursively looking for a value of false.

If a false set all the children to false.

[edit] On creating a Possible World

Boolean flags are required for use in testing for Possible Worlds from different values in the same Value Set.

These flags must be cleared at the start of a test.

To test if any two Possible Worlds are from the same Value Set.

Note that only one such test may be performed at a time. If there were multile threads, both performing the same test, the marks would get mixed up, giving wrong results.

[edit] Memory Management for Possible Worlds

Use reference counting for memory management on the Possible Worlds. Because all the references are from the child to the parent there are no reference cycles so reference counting is a satisfactory strategy.

[edit] Completeness

Completeness refers to the ability of the implementation of the Value Set implementation to always detect when a Posibble World is empty.

Value Sets are equivalent to sets. The rules for calculation Value Sets from functions of Value Sets allow any expression to be evaluated.

These calculations give expressions for Value Sets. These expressions form the basis for the representaion of Possible Worlds.

To prove completeness it is necessary to show the equivalence of the representation of a Possible World with the mathematical rules that describe a Possible World.

TO DO - Complete this proof.

[edit] Code

This is design code only at this stage. Not guaranteed correct.

This code is in C++.

A Possible World may be represented as an object with, 

    class PossibleWorld
    {
    private:
        // static
        static HashMap<Vector<PossibleWorld>, PossibleWorld> m_WorldMap;
 
        long m_RefCount; // Used for reference counting memory management.
        bool m_Exists; // Is the Possible World not empty.
        bool m_Mark; // Used for detecting Possible Worlds from different values in a [[Value Set|Value Set]].
        bool m_ResolveMark; // Used for resolving compatibility between Value Sets.
        // Could use the same boolean for both marks, or a bitfield for all 3 booleans.
        ValueSetBase *m_ValueSet;
        PossibleWorld ** m_WorldList; // This Possible World is the intersection of the Possible Worlds in the list.
        long m_NumWorlds;
        long m_MaxNumWorlds;
 
    public:
        // Construct/Destruct
        PossibleWorld(ValueSetBase *valueSet, long maxNumWorlds);
        PossibleWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2);
        PossibleWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2, PossibleWorld *w3);
        ~PossibleWorld();
 
        // Static
        static PossibleWorld *FindWorld(ValueSetBase *valueSet, PossibleWorld *w1);
        static PossibleWorld *FindWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2);
        static PossibleWorld *FindWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2, PossibleWorld *w3);
 
        // Memory management
        long AddRef();
        long Release();
 
        // Primary worlds.
        void AddPrimaryWorldsToVector(Vector<PossibleWorld *> &worldVector);
        Vector<PossibleWorld *> *GetPrimaryVector();
 
        // Parent possible worlds (the intersection of these worlds is this world.
        void AddWorld(PossibleWorld *world);
        void AddWorld(PossibleWorld *w1, PossibleWorld *w2);
        void AddWorld(PossibleWorld *w1, PossibleWorld *w2, PossibleWorld *w3);
        PossibleWorld *GetWorld(long index);
        long GetNumWorlds();
        PossibleWorld *ClearWorlds();
 
        // Test for empty possible worlds
        bool Exists();
        bool SetEmpty();
 
        // Test for Possible Worlds from different values in the same Value Set.
        bool CheckSamePartition();
 
        // Resolution
        void MarkResolve();
        void SweepResolve();
        bool FinaliseResolve();
 
    private:
        bool Mark()
        bool UnMark()
        void EmptyWorld();
    }

[edit] Construct/Destruct 

    PossibleWorld::PossibleWorld(ValueSetBase *valueSet, long maxNumWorlds)
         : m_RefCount(0)
         , m_Empty(false)
         , m_ValueSet(valueSet)
         , m_MaxNumWorlds(1)
         , m_NumWorlds(0)
    {
        CreateWorlds();
    }
    PossibleWorld::PossibleWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2)
         : m_RefCount(0)
         , m_Empty(false)
         , m_ValueSet(valueSet)
         , m_MaxNumWorlds(2)
         , m_NumWorlds(0)
    {
        CreateWorlds();
        AddWorld(w1); AddWorld(w2);
    }
    PossibleWorld::PossibleWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2, PossibleWorld *w3)
         : m_RefCount(0)
         , m_Empty(false)
         , m_ValueSet(valueSet)
         , m_MaxNumWorlds(3)
         , m_NumWorlds(0)
    {
        CreateWorlds();
        AddWorld(w1); AddWorld(w2); AddWorld(w3);
    }
    ~PossibleWorld::PossibleWorld()
    {
        m_WorldMap.Remove(GetPrimaryVector());
        ClearWorlds();
    }

[edit] Statics

Find an existing world with the same set of primary Possible Worlds. Two worlds with the same set of primaries are the same world. So find the existing world, or if not found then create it. 

    /*static*/ HashMap<Vector<PossibleWorld>, PossibleWorld> PossibleWorld::m_WorldMap(&PossibleWorld::HashVector);
 
    /*static*/ PossibleWorld *PossibleWorld::FindWorld(ValueSetBase *valueSet, PossibleWorld *w1)
    {
        return w1;
    }
    /*static*/ PossibleWorld *PossibleWorld::FindWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2)
    {
        Vector<PossibleWorld> primaryWorldVector;
        w1->AddPrimaryWorldsToVector(primaryWorldVector);
        w2->AddPrimaryWorldsToVector(primaryWorldVector);
        PossibleWorld world = m_WorldMap.Find(primaryWorldVector);
        if (!world)
        {
            world = new PossibleWorld(valueSet, w1, w2);
            m_WorldMap.Add(world->GetPrimaryVector(), world);
        }
        else
        {
            world->AddWorld(w1);
            world->AddWorld(w2);
        }
        return world;
    }
 
    /*static*/ PossibleWorld *PossibleWorld::FindWorld(ValueSetBase *valueSet, PossibleWorld *w1, PossibleWorld *w2, PossibleWorld *w3)
    {
        Vector<PossibleWorld> primaryWorldVector;
        w1->AddPrimaryWorldsToVector(primaryWorldVector);
        w2->AddPrimaryWorldsToVector(primaryWorldVector);
        w3->AddPrimaryWorldsToVector(primaryWorldVector);
        PossibleWorld world = m_WorldMap.Find(primaryWorldVector);
        if (!world)
        {
            world = new PossibleWorld(valueSet, w1, w2, w3);
            m_WorldMap.Add(*(world->GetPrimaryVector()), world);
        }
        else
        {
            world->AddWorld(w1);
            world->AddWorld(w2);
            world->AddWorld(w3);
        }
        return world;
    }

[edit] Memory management 

     long PossibleWorld::AddRef()
     {
          ++m_RefCount;
     }
     long PossibleWorld::Release()
     {
          if (!--m_RefCount)
          {
               delete this;
          }
     }

[edit] Primary Worlds

The list of primary worlds uniquely identifies the Possible World. 

    void PossibleWorld::AddPrimaryWorldsToVector(Vector<PossibleWorld *> &worldVector)
    {
        long numWorlds = GetNumWorlds();
        if (numWorlds)
        {
            for (long j=0; j<numWorlds; j++)
            {
                 GetWorld(j)->AddPrimaryWorldsToVector(worldVector);
            }
        }
        else
        {
            worldVector.Add(this);
        }
    }
 
    Vector<PossibleWorld *> *PossibleWorld::GetPrimaryVector()
    {
        Vector<PossibleWorld *> *worldVector;
        AddPrimaryWorldsToVector(*worldVector);
        return worldVector;
    }

[edit] Parent possible worlds

Methods for managing the list of Possible Worlds. This world is the intersection of the list of Possible Worlds. 

     PossibleWorld *PossibleWorld::CreateWorlds()
     {
          assert(!m_WorldList);
          m_WorldList = new (PossibleWorld *)[m_MaxNumWorlds];
          m_NumWorlds = 0;
     }
     PossibleWorld *PossibleWorld::ClearWorlds()
     {
          if (!m_WorldList)
          {
               return;
          }
          for (long j=0; j<GetNumWorlds(); j++)
          {
               GetWorld(j)->Release();
          }
          delete m_WorldList;
          m_WorldList = 0;
     }
     void PossibleWorld::AddWorld(PossibleWorld *world)
     {
          assert(m_WorldList);
          assert(m_NumWorlds < m_MaxNumWorlds);
          world->AddRef(); 
          m_WorldList[m_NumWorlds++);
     }
     void PossibleWorld::AddWorld(PossibleWorld *w1, PossibleWorld *w2)
     {
         AddWorld(w1); AddWorld(w2);
     }
     void PossibleWorld::AddWorld(PossibleWorld *w1, PossibleWorld *w2, PossibleWorld *w3)
     {
         AddWorld(w1); AddWorld(w2); AddWorld(w3);
     }
     PossibleWorld *PossibleWorld::GetWorld()
     {
          assert(m_WorldList);
          assert(j < m_MaxNumWorlds);
          return m_WorldList[j];
     }
     long PossibleWorld::GetNumWorlds()
     {
          assert(m_WorldList);
          return m_NumWorlds;
     }

[edit] Test for empty possible worlds 

    bool PossibleWorld::Exists()
    {
        if (!m_Exists)
        {
            return false;
        }
        for (long j=0; j<GetNumWorlds(); j++)
        {
            if (!GetWorld(j)->Exists())
            {
                EmptyWorld();
                return false;
            }
        }
    }

When a calculated value does not match the expected result, the boolean value is set to false to represent the Possible World being empty. The tagged value is removed from the Value Set. 

    void PossibleWorld::SetEmpty()
    {
        m_Exists = false;
        ClearWorlds(); // Have the value, no need to represent the intersection of worlds.
    }

Because the Possible Worlds from a Value Set form a partition, the intersection of two Possible Worlds from the same Value Set must be empty. 

    bool PossibleWorld::CheckSamePartition()
    {
        if (!UnMark())
        {
            return false;
        }
        return Mark();
    }

[edit] Resolution

Resolution detects values that are incompatible with another source Value Set, using the Resolution Rule. The process starts with a source Value Set.

Mark all the Possible Worlds related to this Possible World. This is used in marking all the Possible Worlds in a Value Set. 

    bool PossibleWorld::MarkResolve()
    {
        m_ResolveMark = true;
        m_ValueSet->MarkResolve();
        for (long j=0; j<GetNumWorlds(); j++)
        {
            if (GetWorld(j)->Exists())
            {
                GetWorld(j)->MarkResolve();
            }
        }
    }

Detect all values in the Value Set whose Possible Worlds are not represented in the source Value Set. The Possible Worlds for these values must be empty by the Resolution Rule. Clear all the marks afterwards. 

    bool PossibleWorld::SweepResolve()
    {
        m_ValueSet->SweepResolve();
        for (long j=0; j<GetNumWorlds(); j++)
        {
            if (GetWorld(j)->Exists())
            {
                GetWorld(j)->SweepResolve();
            }
        }
        m_ResolveMark = false;
    }

Called for every value in the Value Set. If this World is not marked then it is not present in the source Value Set, and must be empty by the Resolution Rule. 

    bool PossibleWorld::FinaliseResolve()
    {
        If (!m_ResolveMark)
        {
            SetEmpty();
        }
    }

[edit] Private Methods

Clear all the marks. But while we are doing it check for any empty worlds. 

    bool PossibleWorld::UnMark()
    {
        if (!m_Exists)
        {
            return false;
        }
        m_Mark = false;
        if (m_ValueSet)
        {
            m_ValueSet->UnMark(*this);
        }
        for (long j=0; j<GetNumWorlds(); j++)
        {
            if (!GetWorld(j)->UnMark())
            {
                EmptyWorld();
                return false;
            }
        }
        return true;
    }

Use the marks to check if Possible Worlds from two values in Value Sets are in the intersection. Because the Possible Worlds from a Value Set form a partition, the intersection of two Possible Worlds from the same Value Set must be empty. 

    bool PossibleWorld::Mark()
    {
        if(m_ValueSet)
        {
            if (m_ValueSet->HasMark() && !m_Mark)
            { // There are Possible Worlds from different Values in the same Value Set.
                return false;
            }
            m_ValueSet->Mark();
        }  
        m_Mark = true;
        for (long j=0; j<GetNumWorlds(); j++)
        {
            if (!GetWorld(j)->Mark())
            {
                return false;
            }
        }
        return true;
    }

Get the Value Set to update its list of values now that this world is empty. 

    void PossibleWorld::EmptyWorld()
    {
        m_Exists = false;
        if (m_ValueSet)
        {
            m_ValueSet->Simplify();
        }
        m_ValueSet = 0;
    }

[edit] Variables

Function calls that cannot immediately be evaluated may need to be delayed. Other calls to functions may need to wait for the variable to be calculated. A variable records if the value is ready yet, and receives the value, once it is calculated.

A variable may need to store one value (the Value class), or multiple values (the Value Set class).

A basic set of types is listed in the table below.

vBool vLong vDouble vString vMyClass
v1<bool> v1<long> v1<double> v1<String> v1<MyClass>
vsBool vsLong vsDouble vsString vsMyClass
vs<bool> vs<long> vs<double> vs<String> vs<MyClass> 
   #define v1 Value
   #define vs ValueSet

[edit] Cardinality

The cardinality is the number of values it may have.

Cardinality can get very large. When the value is very large we only need to know that it is large. 

    class Cardinality
    {
    private:
        long m_Count;
    public:
        enum Constants { Large = 46340, VeryLarge = 1073741824 };
        Cardinality(const long count) : m_Count(count) {};
        Cardinality operator *(const Cardinality &other)
        {
            if (m_Count == 1) return other.m_Count;
            if (other.m_Count == 1) return m_Count;
            if (m_Count >= Large) return Large;
            if (other.m_Count >= Large) return Large;
            return m_Count * other.m_Count;
        }
        Cardinality operator +(const Cardinality &other)
        {
            if (m_Count >= VeryLarge ) return Large;
            if (other.m_Count >= VeryLarge ) return Large;
            return m_Count + other.m_Count;
        }
        Cardinality operator < (const Cardinality &other)
        {
            if (m_Count == Large) return false;
            if (other.m_Count == Large) return true;
            return m_Count < other.m_Count;
        }
    }

[edit] Reference class

This is just an implementation detail. The reference class allows the basic types, bool, long, and double to be used along with pointers to objects. Template specialisation is used to hide the difference. Used in the Value and Tagged Value classes. This is so we can write, vs<bool> and vs<MyClass>. 

    template <class T>
    class Ref
    {
    protected:
        T *m_value;
    public:
        Cardinality TypeCard() { return Cardinality::Large; };
        bool operator <(const Ref<T> &other) { return *m_value < *other.m_value};
    }
 
    template <>
    class Ref<bool> // Need a class specialisation for long, double as well.
    {
    protected:
        bool m_value;
    public:
        Cardinality TypeCard() { return 2; }; // 2 values (true, false) for bool. For long and double use Cardinality::Large.
        bool operator <(const Ref<T> &other) { return m_value < other.m_value};
    }

[edit] Value class

The Value class is used to represent a variable that may only have one value. The implementation uses the Reference class to hide the difference between the basic types bool, long, double and pointers to objects. The Ref class has the member variable m_Value. 

    template <class T>
    class Value : public Ref<T>
    {
    private:
        bool m_Known;
    public:
        // Constructor/Destructor
        ValueSet() : m_Known(false) {};
        ValueSet(const T &value) : m_Value(value), m_Known(true) {};
        ValueSet(const ValueSet<T> &value) : m_Value(value.m_Value), m_Known(value.m_Known) {};
        ValueSet() : m_Known(false) {};
        bool Known() { return m_Known; };
        long Card() { m_Known ? 1 : TypeCard(); };
        T & Value() { return m_Value; };
 
        // For compatility with Value Set lists.
        template <class A>
        void ForEach(A &action)
        {
            action.Process(m_Value, 0);
        }
        long GetNumValues()
        {
            return 1;
        }
        T GetValue(long index)
        {
            assert(index == 0);
            return m_Value;
        }
        PossibleWorld *GetWorld(long index)
        {
            return 0;
        }
    }

[edit] Value Set class

The Value Set class is used to represent a variable that may have mulitple values.

A Value Set class must efficiently implement a set of (value, Possible World) pairs. There is the potential for much memory to be used on storing these lists. Many alternatives were considered. In the end a simple vector approach seems to be the cleanest.

A Value Set is a vector of Tagged Values. Each Value has,

Value Sets must be pruned of unmatched values when unified with other Value Sets. A flag is recorded on the Tagged Value class for this purpose. 

    class ValueSetBase
    {
    public:
        // Test for Possible Worlds from different values in the same Value Set.
        bool HasMark() = 0;
        void Mark() = 0;
        void UnMark() = 0;
 
        // Resolution
        void Resolve(long numValues) = 0;
        void MarkResolve(long numValues) = 0;
        void SweepResolve(long numValues) = 0;
 
        // Utilities
        void Simplify() = 0;
        void Sort() = 0;
    }
 
    template <class T>
    class ValueSet : public ValueSetBase
    {
    private:
        TaggedValue<T> *m_ValueList;
        long m_NumValues;
        bool m_Mark;        // Used in testing for Possible Worlds from different values in the same Value Set.
        bool m_ResolveMark; // In [[Value Set#(D) Resolution|Resolution]] record if this Value Set has been resolved.
    public:
        // Constructor/Destructor
        ValueSet();
        ValueSet(long maxValues);
        ~ValueSet();
        void Init(long maxValues);
        void Create(T &value);
        void Create(T &value1, T &value2);
 
        // Value
        Cardinality Card();
 
        // List operations
        void AddValue(T &value, PossibleWorld *p);
        T GetValue(long index);
        PossibleWorld * GetWorld(long index);
        void AutoResize();
        void Resize(long numValues);
 
        // Test for Possible Worlds from different values in the same Value Set.
        bool HasMark();
        void Mark();
        void UnMark();
 
        // Resolution
        void Resolve(long numValues);
        void MarkResolve(long numValues);
        void SweepResolve(long numValues);
 
        // Utilities
        void Simplify();
        void Sort();
        template <typename A> ForEach(A &a)
    }

[edit] Construct/Destruct 

    template <class T>
    ValueSet<T>::ValueSet()
        : m_NumValues(0)
        , m_ValueList(0)
    {
    }
 
    template <class T>
    ValueSet<T>::ValueSet(long maxValues)
        : m_NumValues(0)
    {
        Init(numValues);
    }
 
    template <class T>
    ~ValueSet<T>::ValueSet()
    {
        delete m_ValueList;
    }
 
    template <class T>
    void ValueSet<T>::Init(long maxValues)
    {
        m_ValueList = new Value<T>[numValues];
    }
 
    template <class T>
    ValueSet<T>::Create(T &value)
    {
        Init(1);
        AddValue(value, new PossibleWorld());
    }
 
    template <class T>
    ValueSet<T>::Create(T &value1, T &value2)
    {
        Init(2);
        AddValue(value1, new PossibleWorld());
        AddValue(value2, new PossibleWorld());
    }

[edit] Value 

    template <class T>
    bool ValueSet<T>::Known()
    {
        return m_ValueList;
    }
 
    template <class T>
    Cardinality ValueSet<T>::Card()
    {
        if (!Known()) return TypeCard();
        Cardinality result = 0;
        for (long j=0; j < m_NumValues; j++)
        {
            result += m_ValueList[j]->Card();
        }
        return result;
    }

[edit] List operations 

    template <class T>
    void ValueSet<T>::AddValue(T &value, PossibleWorld *p)
    {
        assert(Known());
        if (m_NumValues = sizeof(m_ValueList))
        {
            AutoResize();
        }
        m_ValueList[m_NumValues] = new TaggedValue(value, P);
    }
 
    template <class T>
    T ValueSet<T>::GetValue(long index)
    {
        assert(Known());
        assert(0<=index && index<m_NumValues);
        return m_ValueList[j].GetValue();
    }
 
    template <class T>
    T ValueSet<T>::GetWorld(long index)
    {
        assert(Known());
        assert(0<=index && index<m_NumValues);
        return m_ValueList[j].GetWorld();
    }
 
    template <class T>
    void ValueSet<T>::AutoResize()
    {
        assert(Known());
        Resize(sizeof(m_ValueList)*2);
    }
 
    template <class T>
    void ValueSet<T>::Resize(long numValues)
    {
        if (!Known())
        {
            Init(numValues);
            return;
        }
        Value<T> *old = m_ValueList;
        m_ValueList = new Value<T>[numValues];
        if (m_NumValues < numValues)
        {
            m_NumValues = numValues;
        }
        for (long j=0; j<m_NumValues; j++)
        {
            m_ValueList[j] = old[j];
        }
    }

[edit] Test for Possible Worlds from different values in the same Value Set

If a Possible World is the intersection of different worlds from two different worlds with the same Value Set, it is empty. To test for Possible Worlds from different values, mark the Value Set and the Possible World. Before marking test if the Value Set is marked but not the Possible World. In this case a Possible World from a different value has been detected. 

    template <class T>
    bool ValueSet<T>::HasMark()
    {
        return m_Mark;
    }
 
    template <class T>
    void ValueSet<T>::Mark()
    {
        m_Mark = true;
    }
 
    template <class T>
    void ValueSet<T>::UnMark()
    {
        m_Mark = false;
    }

[edit] Resolution

Resolution detects values that are incompatible with another source Value Set, using the Resolution Rule. If a Value Set was used in calculating this Value Set, all the Possible Worlds must be represented in this Value Set or be empty.

The test is performed by marking all the Possible Worlds referenced by this Value Set, and then checking the other Value Sets for unmarked values. 

    template <class T>
    void ValueSet<T>::Resolve(long numValues)
    {
        for (long j=0; j<m_NumValues; j++)
        {
            m_ValueList[j].GetWorld().MarkResolve();
        }
        for (long j=0; j<m_NumValues; j++)
        {
            m_ValueList[j].GetWorld().SweepResolve();
        }
    }
 
    template <class T>
    void ValueSet<T>::MarkResolve(long numValues)
    {
        m_MarkResolve = true;
    }
 
    template <class T>
    void ValueSet<T>::SweepResolve(long numValues)
    {
        if (!m_MarkResolve) return;
        m_MarkResolve = false;
        for (long j=0; j<m_NumValues; j++)
        {
            m_ValueList[j].GetWorld()->FinaliseResolve();
        }
        Simplify();
    }

[edit] Utilities

Remove values with empty Possible Worlds. 

    template <class T>
    void ValueSet<T>::Simplify()
    {
        // Count the values from existing worlds.
        long numValues = 0;
        for (long j=0; j<m_NumValues; j++)
        {
            if (m_ValueList[j].GetWorld()->Exist())
            {
                ++numValues;
            }
        }
        // Allocate new memory.
        Value<T> *old = m_ValueList;
        m_ValueList = new Value<T>[numValues];
        // Copy the values from existing worlds.
        long k = 0;
        for (long j=0; j<m_NumValues; j++)
        {
            if (m_ValueList[j].GetWorld()->Exist())
            {
                m_ValueList[k++] = old[j];
            }
        }
        // Clean up.
        m_NumValues = k;
        delete old;
    }
 
    template <class T>
    void ValueSet<T>::Sort()
    {
        // The QuickSort method would come from a standard library.
        QuickSort<TaggedValue>(m_ValueList, m_NumValues); // Uses the < operator.
    }
 
    template <class T>
    template <typename A> ForEach(A &a)
    {
        for (long j=0; j<m_NumValues; j++)
        {
            a.Process(m_ValueList[j]);
        }
    }

[edit] Tagged Value class

A TaggedValue is a tuple of a typed value and a Possible World. The implementation uses the Reference class to hide the difference between the basic types bool, long, double and pointers to objects. The Ref class has the member variable m_Value. 

    template <class T>
    class TaggedValue : Ref<T>
    {
    private:
        PossibleWorld m_World;
 
    public:
        TaggedValue(T &value, PossibleWorld *world)
            : Ref<T>(value)
            , m_World(world)
        {
            if (m_World)
            {
                m_world.AddRef();
            }
        }
        ~TaggedValue()
        {
            if (m_World)
            {
                m_world.Release();
            }
        }
        // Access
        T & GetValue()
        {
            return m_Value;
        }
        PossibleWorld *GetWorld()
        {
            return m_World;
        }
     }

[edit] Cartesian Products

[edit] Design

The most general situation is where the inputs and outputs all have Value Sets with one or more values. In this case create a new Value Set from two of the Value sets and merge it with the third. Resolution is then applied to remove values from Value Sets who's Possible World has been shown to be empty.

This is code below using C++ template classes (for binary operations). It may be better to generate all this code. In any case this code describes the algorithm.

To represent any operation start with a class representing the method that implements that operation, in the Call method on 3 parameters that are not value sets.

The class Cartesian has a template parameter for the operation class. It inherits the Call method from the operation class and then extends it with overridden Call methods with various combinations of Value Set parameters.

[edit] Code

To multiply 2 values A and B to obtain a third, 

    Cartesian<long, MultiplyOp<long> >::Call(A, B, C);

A, B, and C may or may not be Value Sets. So there are many possibilities.

[edit] Binary Operator Classes

A small class is is used to capture the operation. A class like this would be written for each built in operator.

[edit] Arithmatic Binary Operators
Function Inverse
* / 
  template <class T>
  class MultiplyOp
  {
      typedef T ResultType;
      static Call(T A, T B, T &C)
      {
          C = A * B;
      }
  }
 
  template <class T>
  class DivideOp
  {
      typedef T ResultType;
      static Call(T A, T B, T &C)
      {
          C = A / B;
      }
  }
+ - 
  template <class T>
  class AddOp
  {
      typedef T ResultType;
      static Call(T A, T B, T &C)
      {
          C = A * B;
      }
  }
 
  template <class T>
  class MinusOp
  {
      typedef T ResultType;
      static Call(T A, T B, T &C)
      {
          C = A / B;
      }
  }
Exp Root Log 
  template <class T>
  class PowerOp
  {
      typedef T ResultType;
      static Call(T A, T B, T &C)
      {
          C = Exp(A, B);
      }
  }
 
  template <class T>
  class RootOp
  {
      typedef T ResultType;
      static Call(T C, T B, T &A)
      {
          A = Exp(C, 1/B);
      }
  }
 
  template <class T>
  class LogOp
  {
      typedef T ResultType;
      static Call(T C, T A, T &B)
      {
          B = Log(C, A);
      }
  }
[edit] Logical Binary Operators

The inverse logical operators require a Value Set as the result. This is the problem with logical operators that is solved by using Value Sets.

Function Truth Table Inverse Truth Table 
  class AndOp
  {
     typedef bool ResultType;
     static Call(bool A, bool B, bool &C)
     {
         C = A && B;
     }
  }
A B C
0 0 0
0 1 0
1 0 0
1 1 1 
  class InverseAndOp
  {
      typedef vs<bool> ResultType;
      static Call(bool A, bool B, vs<bool> &C)
      {
          if (A)
          {
              C.Create(B);
          }
          else if (!A and !B)
          {
              C.Create(true, false)
          }
          else
          {
              assert(false);
          }   
      }
  }
A B C
0 0 {0,1}
0 1 {}
1 0 0
1 1 1 
  class OrOp
  {
     typedef bool ResultType;
     static Call(bool A, bool B, bool &C)
     {
         C = A || B;
     }
  }
A B C
0 0 0
0 1 1
1 0 1
1 1 1 
  class InverseOrOp
  {
      typedef vs<bool> ResultType;
      static Call(bool A, bool B, vs<bool> &C)
      {
          if (!A)
          {
              C.Create(B);
          }
          else if (A and B)
          {
              C.Create(true, false)
          }
          else
          {
              assert(false);
          }
      }
  }
A B C
0 0 0
0 1 1
1 0 {}
1 1 {0,1}

[edit] Cartesian Class 

    template <class T, class Op>
    class Cartesian::public Op
    {
    public:
        template <class TA, class TB>
            static void Call(TA &A, TB &B);
        template <class TA, class TB, class TC>
            static void Call(TA &A, TB &B, TC &C);
        template <class TA, class TB, class TC, class TD>
            static void Call(TA &A, TB &B, TC &C, TD &D);
 
    private:
        template <class TA, class TB>
            static void Cart1(TA &A, TB &B);
        template <class TA, class TB, class TC>
            static void Cart2(TA &A, TB &B, TC &C);
        template <class TA, class TB, class TC, class TD>
            static void Cart3(TA &A, TB &B, TC &C, TD &D);
        static void UnifyRight(vs<T> &A, vs<T> &B);
    }

Here is the implementation of the Call function with 3 parameters. The implementations with 1 and 3 parameters are similar. 

    template <class T, class Op>
    template <class TA, class TB, class TC>
    void Cartesian::Call(TA &A, TB &B, TC &C)
    {
        if (C.Known())
        {
            vs<T> result(A.Size(), B.Size());
            Cart2(A, B, result);
            UnifyRight(result, C);
        }
        else
        {
            Cart2(A, B, C);
        }
    }

Construct the output out of the cartesian product of the inputs. This is a simple version. Other versions are given below, using ForEach, 

    template <class T, class Op>
    template <class TA, class TB, class TC>
    void Cartesian::Cart2(TA &A, TB &B, TC &C)
    {
        C.Init((A.GetNumValues()+1) * (B.GetNumValues()+1));
        for (long a=0; a<A.GetNumValues(); a++)
        {
            for (long b=0; b<B.Size(); b++)
            {
                T &vA = A.GetValue(a);
                T &vB = B.GetValue(b);
                PossibleWorld *wA = A.GetWorld(a);
                PossibleWorld *wB = A.GetWorld(b);
                Op.ResultType result;
                Call(vA, vB, result);
                for (long r=0; r<result.GetNumValues(); r++)
                {
                    PossibleWorld *world = new PossibleWorld(wA, wB, wResult);
                    if (world.CheckSamePartition())
                    {
                        C.AddValue(result.GetValue(r), world);
                    }
                }
            }
        }
    }

[edit] Actions

The above implementation has a for loop for the result when maybe none is necessary. Only basic functions that return a result set need this. We would like to use the ForEach method, and have it use a for loop for a ValueSet, and not for a Value.

At times like this I miss closures. I dont really want to code multiple versions of the Cart2 function. It would aggrevate my RSI. If C++ had closures, I could write. 

    template <class TA, class TB, class TC>
    void Call(TA A, TB B, TC C)
    {
        A.ForEach(         // Loop through all A
            B.ForEach(     // Loop through all B
                a | b |    // Get the parameters that the two ForEach calls have left.
                {
                    Op.ResultType result;
                    Call(a, b, result);
                    result.ForEach(r |  // For each value in the result.
                        {
                            PossibleWorld *world = PossibleWorld::FindWorld(a.GetWorld(), b.GetWorld(), r.GetWorld();
                            if (world.CheckSamePartition())
                            {
                                C.AddValue(r.GetValue(), world);
                            }
                        }
                    );
                }
            )
        );
    }

Alas C++ does not have closures. It has template classes. The parameters cant just be picked up from the enclosing scope, but we can construct classes to act like functions with extra parameters.

The Value Set class has the method,

template <typename A> ForEach(A &a)

This method calls the Process method on A passing the value and the possible world. Apologies for what follows. Its not as nice as I would like.

Somewhere to save the results passed into Process. 

    class ActionBase
    {
    public:
        T &value;
        PossibleWorld *world;
    }

A class for the outer ForEach call (on the parameter A). 

    template <class V, class T, class A>
    class ActionForEach : public ActionBase<T>
    {
    private
        const V &valueOrg;
        const A &action;
    public:
        ActionBase *last;
        ActionForEach(T &p_value, A *p_action)
        : value(p_value), action(*p_action) {};
        void Process(T v, PossibleWorld *w)
        {
            value = v;
            world = w;
            action.last = this;
            action.ForEach();
        }
        void ForEach()
        {
            valueOrg.ForEach(this);
        }
    };

A class for the next loop call (on the parameter B). Note that classes ActionCall1 and ActionCall3 are defined similarly. 

    template <class V, class T, class A>
    class ActionCall2 : public ActionForEach<V, T, A>
    {
    public:
        ActionCall2(T &p_value)
        : ActionForEach(T &p_value, 0)
        void Process(T v, PossibleWorld *p)
        {
            ResultType result;
            Call(last->value, v, result);
            action.SetValue(result);
            action.ForEach();
        }
    };

A class for the outer loop call to take the values from the result and put them in the parameter C. Note that classes ActionResult1 and ActionResult3 are defined similarly. 

    template <class V, class T, class A>
    class ActionResult2 : public ActionForEach<V, T, A>
    {
    public:
        ActionCall(T &p_value, A &p_action)
        : ActionForEach(T &p_value, A &p_action)
        void Process(T v, PossibleWorld *w)
        {
            PossibleWorld *world = PossibleWorld::FindWorld(last->last->world, last->world, w);
            if (world.CheckSamePartition())
            {
                valueOrg.AddValue(vR, world);
            }
        }
    };

[edit] Cartesian Product Functions

The new definition of the Cart1 function. 

    template <class T, class Op>
    template <class TA, class TB>
    void Cartesian::Cart1(TA &A, TB &B)
    {
        typedef ActionResult1<T, TC, ActionNone> ActionB;
        typedef ActionCall1<T, TB, ActionResult> ActionA;
        ActionC r(B);
        ActionB a(A, r);
        a.ForEach();
    }

The new definition of the Cart2 function. 

    template <class T, class Op>
    template <class TA, class TB, class TC>
    void Cartesian::Cart2(TA &A, TB &B, TC &C)
    {
        typedef ActionResult2<T, TC, ActionNone> ActionC;
        typedef ActionCall2<T, TB, ActionResult> ActionB;
        typedef ActionForEach<T, TA, ActionCall> ActionA;
        ActionC r(C);
        ActionB b(B, r);
        ActionA a(A, b);
        a.ForEach();
    }

The new definition of the Cart3 function. 

    template <class T, class Op>
    template <class TA, class TB, class TC, class TD>
    void Cartesian::Cart2(TA &A, TB &B, TC &C, TD &D)
    {
        typedef ActionResult3<T, TD, ActionNone> ActionD;
        typedef ActionCall3<T, TC, ActionResult> ActionC;
        typedef ActionForEach<T, TB, ActionCall> ActionB;
        typedef ActionForEach<T, TA, ActionCall> ActionA;
        ActionD r(D);
        ActionC c(C, r);
        ActionB b(B, c);
        ActionA a(A, b);
        a.ForEach();
    }

etcetera

[edit] UnifyRight

When comparing two Value Sets it is faster to sort the Value Sets and then merge the results.

The time to calculate the cartesian product of two value sets is proportional to the product of the number of entries. By first sorting the Value Sets by value, the values sets can be merged in linear time. However the sort takes n log n time.

The resulting merge still needs to create a cartesian product when multiple entries have the same value. 

    void UnifyRight(vs<T> &A, vs<T> &B)
    {
        vs<T> result;
        A.Sort(); B.Sort();
        long a = 0; long b = 0;
        long a_entries = A.Entries(); b_entries = B.Entries();
        while ((a < a_entries) && (b < b_entries))
        {
            Value<T> &vA = A.GetValue(a);
            long k = b;
            Value<T> &vB = B.GetValue(b);
            while (vA.GetValue() == vB.GetValue())
            {
                PossibleWorld *world = new PossibleWorld(vA.GetWorldList(), vB.GetWorldList());
                if (world.Check())
                {
                    result.AddValue(world, vA.GetValue());
                }
                vB = B.GetValue(k++);
            }
            if ((vA.GetValue() < vB.GetValue())
            {
                a++;
            }
            else if (k == b)
            {
                b++;
            }
            else
            {
                a++;
            }
        }
        B = result;
        B.Resolve();
    }
 
    void UnifyRight(v1<T> &A, vs<T> &B)
    {
        bool changed = false;
        for (long j=0; j<B.GetNumValues(); j++)
        {
            if (A.GetValue(j) != B.GetValue(j))
            {
                changed = true;
                B.SetEmpty();
            }
        }
        if (changed)
        {
            B.Resolve();
            B.Simplify();
        }
    }

[edit] Links

Retrieved from "http://knowino.org/wiki/Symbolic_Logic:Programming:Value_Set_Implementation"
Personal tools
Variants
Actions
Navigation
Community
Toolbox