Click here to Skip to main content
14,244,034 members

Primeh.h : Higher Order Predicate Logic

Rate this:
4.00 (1 vote)
Please Sign up or sign in to vote.
4.00 (1 vote)
21 May 2015BSD
Policy based higher order predicate logic library. Distributed parallel operations with hash number are available.

Introduction

I am a reader of the book 'MODERN C++ DESIGN' written by ALEXANDRESCU, ANDREI. written about 'Policy based design' on which this library is based. I am the author of 'Primec.h:Curry-Howard Style 1st Order Predicate' in which I referred lambda calculus in fact the book 'Lambda-Calculus and Combinators, an Introduction' written by J. Roger Hindley and Jonathan P. Seldin. In this book Lambda cube is explained and I picked up a part of its feature(lambda P) and wrote the article. But the rest of that was untouched then I write this article about lambda 2 and lambda omega respectively. the lambda cube is a deeper and complicated topics and so if you want to write codes similar to this library, you had better buy the book. Anyway don't be afraid. Notions are very abstractive but practices are so definitive that we should not confuse when a certain policy choice is changed caused by the program's requirements change. In this library remembering all policy choices is the easiest way to use. In short what is interesting is concepts are classified in policy manner. Yes, it's the policy based design.
 

Background

It is not a better way and I sorry for the persons who didn't chose a lambda calculus course but I start from this question 'what is lambda cube?'. 'Some classification method' is probably the easiest answer. Classification means the existence of matter and so we should know matter(s) but where we have learned? In fact we remind that in specification sheets of  a especially programing language. Lambda 2 and lambda omega correspond to (poly-)morphism and recursion in c++. I suppose this article readers naturally use these features but possibly
knows when explain these features to beginners they response "why and when we use?" More general the concept is getting to, both easier we use and more difficult we consider. But policy based design is very practical. Input value and output value are decided so the policy choice is limited to semantically valid. We can skip explaining abstractive concepts to read compile error messages. And in many case the messages say 'type mismatch' and so you only check requirement docs.(And find bugs in design docs not programing.) Consequently this policy based design prevent from writing semantically buggy codes. It's a main benefit of this library.
 

Using the code

'primeh.h' is a policy based library so policies and their choices should be explained first.

Policy choices:
Primeh2 product:
(IIa:*.a->a):*
(If you don't know lambda cube, ignore it.)
If you choose Void, you need not or should not write the pure virtual function Second(). Library executes no additional calculation and copies input to output directly. Why this feature is chosen is probably to use Primeh3 and Primeh5 features(Curry function,FIFO etc.). If you choose Cast, you must write the pure virtual function Second(). What in function is 'function' itself. In particular if you want to implement a 2-Operand function,you must return the functor in which first operand value is owned. Then this functor is called with second operand value then return result. This technique is known as Currying especially by Haskell programer.

Primeh3 product:
(*->*):[]
If you choose Creational, whole class primeh composes the creational pattern. Preparing pure virtual function Create() makes it possible to pass a created object to the primeh2 input. The implicit serial number of a created object is available when work with primeh5. If you chose Construct, primeh class offers a 1-operand function. This choice makes me think the execution intuitively and because it is 1-operand,you should remember a (type)
converter. If you choose Curry, you can get a 2-operand function. But in this library it is achieved by Currying so that you must prepare the functor owns the parameter op1 info., the functor is called with the parameter op2, and the return value of it is this library's one. Functors are not defined declaratively so you must send functor in class T::Inhabited * type and you must indicate the downcast type U that has the operator overload member function
operator ()(class T::Inhabited *).

Primeh5 axiom:
there is no x such that
suc(x)=0
where suc() is successor function.
Choices in here give additional feature FIFO and the choice decide the behavior of FIFO writing. FIFO Works after the consequent object of primeh2 and primeh3 returned. Using Front() function in spite of operator =(Term) for copying, the deep copy is under the FIFO management with its serial number. Calling Write() function when modification of the copy object completes the ownership of the copy is killed and the object changes FIFO internal.
Calling Read() function cause a retake of the object but in order.(This library is for concurrent use.) Erase() function is called when the read copy is no use. If you choose InOrderConstruct, FIFO size is limited 1and it behaves like on-by-one object passing is also like mutex. IF you chose RedorderConstruct,Front() function setups the copied object sequentially but its modification codes can run concurrently. Then Write() function call get the object in FIFO and because it is FIFO, read() function reads out in Front() function called time order. If you choose StableInOrderConstruct, it behaves quite the same as ReorderConstruct except the number of the object between Front() function and Write() function is limited to the size that you can set to EagerSize() function. If you choose
StableReorderConstruct, it behaves quit the same as ReorderConstruct except the number of the object between Front() function and Read() function is limited to EagerSize() function called. If you choose StableDelayConstruct, it behaves quit the same as ReorderConstruct except the number of the object between Write() function and Read() function is limited to EagerSize() function called.

Template<> class And and Template class Or is the 2-operand operators that return the intersection and the union of the aggregations under the limited condition. In detail class T::Inhabited defined in class Primec<...T> of primec.h compatible class is needed. It offers class types and functions as follows.

template <typename A,typename R>
class PrimecInhabited
{
public:
    virtual class PrimecInhabited *Clone() const =0;
    virtual R Inhabit(A &as)=0;
    PrimecInhabited() {}
    virtual ~PrimecInhabited() {}
    ...
};

template<Key_,...> class PrimecSet
{
     class Keys
    {
    public:
        enum {
            Constant=0,
            Wild,
            Except,
            MoreEqual,
             More
        } isWild_;
        Key_ k_;
    };
    class Result {
    public:
        int isIterative_;
        int isEqual_;
        Key_ key_;
        ...
    };
    class Assumption_ {
    public:
        enum {
            Current=0,
            Less=1,
            SkipIsKey=2,
            Value=3,
            RemoteId=4,
            Increment=5,
            EraseIncrement=6,
            SkipLess=7,
            EraseSkipLess=8
        } isIncrement_;
        int isEquals_;
        class Keys *ks_;
        Assumption_() {isEquals_=1;}
    };
    class Assumption : public Assumption_ {
    public:
        class PrimecInhabited<Assumption,Result> *big_;
    };
    enum {Column=...};
    typedef class PrimecInhabited<Assumption,Result> Inhabited;
    ...
};

Frankly speaking, pure virtual function Inhabit() is implemented and semantically valid by environmental functions, type definitions, and responses of enumerated parameters. In the Primec container case returned iterator Inhabit() is the interface from aggregate to elements then through calling Inhabit() another Inhabit() is prepared by the operator as the bool logic result aggregation. You can write codes such like 'v=and(or(x,y),z);' and so 'v' is
treated as the database answer stream handle. Anyway this expression works in lazy evaluation manner so after 'v.Iterate()', candidate element is searched back in operand iterators.

Another supported feature is hashed numbered distributed memory parallel database.Why we can is quite simple.If
HashedNumbered(hn,f(x))=f(HashedNumbered(hn,x))
is always true, the elements of a certain hash number is operated with the same hash number element and returns the same hash number element. When every hashed data is stored in distributed memory with core, such type operation completes by each internal memory access so the global bus bandwidth is not used. This is also parallelism. But detail is complicated because remote procedure call used by distributed memory machines
is not standardized and difficult to standardize machine dependency. Machine dependencies in this library at most
is encapsulated in class Hasher prepared by library user programer and used as the template parameter of template<class Branch,template <class,class> class Hasher,class BranchType,typename Alloc> class PrimehHash. In class Haser you must define many types as fellows.(main.c)

...
template <class Branch,class BranchType>
class Hasher4
{
public:
    typedef typename Branch::Key Key;
    typedef class Branch::Keys Keys;
    class Parameter : public Branch::Parameter {
    public:
        Parameter() : Branch::Parameter() {}
        Parameter(Keys *ks) : Branch::Parameter(ks) {}
        Parameter(const class Parameter &parent) : Branch::Parameter(parent) {}
        class Parameter *Clone() const {return (class Parameter *)Branch::Parameter::Clone();}
    };
    class Result : public Branch::Result {};
    class Assumption_ : public Branch::Assumption_ {};
    enum {
        Column=Branch::Column
    };
    enum {
        Procedure=2
    };
    typedef void *HasherId;
    typedef void *BranchId;

    class RBranch : public Branch {
    public:
        typedef class Branch::Inhabited Inhabited;
        typedef class Branch::Iterator::Term Term;
        class Pool : public RPCPool<Hasher4,RBranch> {};
        class Iterator : public Branch::Iterator {
        public:
            Iterator(class RBranch &cont) : Branch::Iterator(cont) {}
            Iterator(class RBranch::Inhabited *trm) : Branch::Iterator(trm) {}
            Iterator(const Term &trm) : Branch::Iterator(trm) {}
        };
    };
    class ROr : public Or<InOrderConstruct,Branch> {
    public:
        typedef class Or<InOrderConstruct,Branch>::Iterator::Term Term;
        class Pool : public RPCPool<Hasher4,ROr> {};
        class Iterator : public Or<InOrderConstruct,Branch>::Iterator {
        public:
            Iterator(class ROr &cont) : Or<InOrderConstruct,Branch>::Iterator(cont) {}
        };
    };
    class RAnd : public And<InOrderConstruct,Branch> {
    public:
        typedef class And<InOrderConstruct,Branch>::Iterator::Term Term;
        class Pool : public RPCPool<Hasher4,RAnd> {};
        class Iterator : public And<InOrderConstruct,Branch>::Iterator {
        public:
            Iterator(class RAnd &cont) : And<InOrderConstruct,Branch>::Iterator(cont) {}
        };
    };
    static int HashNo(const Keys &ks) {
        const char *p;
        int i,hn;
        hn=0;
        for(i=0;i<Column;i++) {
            p=(&ks)[i].k_.k_;
            while(*p!=0) {
                putchar(*p);
                hn+=*(p++);
            }
        }
        printf(":%dツ・n",hn%Procedure);
        return hn%Procedure;
    }
    ...
    static void NToO021(char *this_,HasherId &k,HasherId &ok,BranchId &bitr) {
        this_=MempcpySrc(&k,this_,sizeof(HasherId));
        this_=MempcpySrc(&ok,this_,sizeof(HasherId));
        this_=MempcpySrc(&bitr,this_,sizeof(BranchId));
    }
    static char *OToN021(HasherId k,HasherId ok,BranchId bitr) {
        char *p,*q;
        p=new char[sizeof(HasherId)*2+sizeof(BranchId)];
        q=p;
        p=MempcpyDst(p,&k,sizeof(HasherId));
        p=MempcpyDst(p,&ok,sizeof(HasherId));
        p=MempcpyDst(p,&bitr,sizeof(BranchId));
        return q;
    }
    ...
};

Now that the hashing codes solely make groups without understanding their algorithms, the type of container type T in class T::Inhabited and type of inputs and outputs of its Inhabit() function are inherited. Hash numbers are
between 0 and enum Procedure-1. HasherId is pointer of local(Hasher) machine in remote machine and BranchId is pointer of remote(Branch) machine in local machine. Class RBranch, class RAnd and class ROr are objects in the remote machines and why declarations are needed is that hashed class of hashed class is also available if you write remote's remote machine's local's ones in this remote ones. class Pool declarations in these classes contribute Remote Procedure Call mechanism encapsulated in template class RPCPool.(But main.c example is for SMP pthread.h.) static int HashNo() function is the hash number calculator. Last static void NToO021() and static char *OToN021() andother function pairs are needed to convert between the network packet data and each objects in both local and remote machines. For example NToO021() converts network data to 0 int,2 HasherId,1 BranchId values.(Casting HasherId and/or BranchId to pointer depends on the function is used in whether local machine or remote one.)

Class Primeh requires both type Branch and type BranchId. Class Branch exists in remote but the types are for local machine. Class BranchId only needs the enum {TypeId=...} is the unique number to every container type, but as the
numbers conflict, the remote machines can't distinguish which is my local type.(Encapsulated networks loose right address and port although main.c program sample runs on the SMP model machine and ignore this Id because of
the static bindings offered by c++ compiler.)

class HashAnd and class HashOr are class And and class Or for hashed iterators. These Hashing perfectly depends on the container class PrimehHash and class Hasher is used through class PrimehHash.(Remember ROr and RAnd are declared in class Hasher although class Hasher is for the container class.)

The sample program main.c is a 4-tuple concurrent database accessed through telnet the same as main.c in Primec article except Primeh support &,|,() in addition.("()" in Primec is changed to "{}") First main.c is executed with local port No. Then 'Telnet localhost <local port no.>' is executed. You can enter commands and examples follow.
Input           Meaning
{x,y,z,a}       insert tuple
:{x,y,z,*}      list matching tuple
:{x,y,z,*}|{*,y2,z2,a}
         list the union of {x,y,z,*} and {*,y2,z2,a}
:{!x,*,*,*}&({x2,y2,z2,*}|{x3,y3,*,*})
         list the intersection of {!x,*,*,*} and the one which is the
         union of {x2,y2,z2,*} and {x3,y3,*,*}
:={?,?,*,*}({tbl2,const2,*,*}|{tbl3,const2,*,*}){*,*,*,!except}
         list the first element in Domain<q1,q2,b3,b4> defined
         {<q1,q2>|All b3,b4 of (<tbl2,const2,b3,b4> and
         <tbl3,const2,b3,b4>) included (<q1,q2,*,*> except
         <q1,q2,*,except>)}
:?{?,2,*,*}{tbl2,*,*,*}{*,*,*,1}
         list the first element in Domain<q1,2,b3,b4> defined
         {<q1>|Exist b3 b4 of <tbl2,2,b3,b4> included
          <q1,2,*,1>}

 

Points of Interest

First, class And and class Or are simple enough to write the operations of aggregations accessed through Inhabit() iterators. Iterators are assumed both finite and infinite so that there is a chance to treat these as streams and to fit to dataflow programing paradigm although a empty aggregation runs infinite loop because this library doesn't offer mathematical proofs themselves. Second, but the most inquisitive feature is hash number parallelism runs in distributed memory parallel machines. Parallelism iterator own a vector of every remote machines' iterators and operations such like HashAnd and HashOr own a vector of answers' iterators in Remote machines. Then function Copy() works very efficiently because copied values is also the same hash numbered so all of the calculation runs inside the every remote machine. Absolutely all kinds of operators suffice this hash numbered operation conditions, but decomposing its algorithm make accelerate in some degree. A traditional example is calculate sum and you can see

HashedNumbered(hn,PartialSum(x))=PartialSum(HashedNumbered(hn,x))
then after the parallel summing completes you should only calculate sum of partial sums. But unfortunately predicate logic with quantify is not in this case and the local machine occupies the communication bandwidth. If you use predicate logic,you should better moving And inside the quantify scope so you can reduce answer candidates passed between local and remote machines. Beside them environment about remote procedure call(RPC) is bad. Generalization is seem to suspended and we must write data byte level primitives. Any solution is
expected.

Additional ownership semantics is introduced to correspond to ownership about FIFO.

int funcA(class T&trg)
{
    trg.do();
    trg.something();
    return 0;
}

void main()
{
    class T *owned;
    owned=new classT;
    funcA(*owned);
...
    class T lend;
    lend=&(*owned);
    lend.funcA_();
    owned->erase(lend);
...
}

int T::funcA_()
{
    do();
    something();
    return 0;
}

In C++ language reference type like class T &trg is allowed when the function is called. This don't cause ownership problems because when in a subroutine all the data including ownership and owned data passed as reference and until out of the subroutine caller don't operate the object. But reference type in general dosen't support ownership control primitives so operator overload & is invented. operator &() returns some kind of pointer(only limited to semantically valid of value pointings) and operator=(class Somekind *) receives the shallow copy pointer and the object behave the same as the owner object except ownership related operations. when shallow copy is useless owner is informed the lend copy is ending. These semantics make it available for containers like FIFO to encapsulate their ownership managings.
 

History

Ver 0.1        May. 2015
 

 

License

This article, along with any associated source code and files, is licensed under The BSD License

Share

About the Author

T. Ogawa 2012
Software Developer
Japan Japan
I'm an old programer. My Skill starts from i8085 assembler
coding. The Object oriented programing is over 20 years
and I achived the Policy based programing. Latest interests
are pthreads and pararell programings.

Comments and Discussions

 
-- There are no messages in this forum --
Article
Posted 21 May 2015

Stats

6.2K views
52 downloads
6 bookmarked