Boost logo

Boost :

Subject: Re: [boost] [castor] Interest in Logic Paradigm for C++ ?
From: Roshan (roshan_naik_at_[hidden])
Date: 2010-05-07 05:38:37


On Wed, 05 May 2010 12:57:07 -0600, vicente.botet
<vicente.botet_at_[hidden]> wrote:

> * Separation between relation structure and bindings
[..snip..]
> will build twice the relation generated by the function child. This
> should be an expensive operation if instead of 5 record child had 1000,
> or even more.

This example is only introductory and too simplistic to address your valid
concern. Its purpose is to demonstrate some basic concepts driving this
paradigm and is used
classically in teaching Prolog.

In practice, you will not hard code so many records ... you retrieve it
 from some database/container. Then the relation would
merely return something that references the record-set with ability to
perform enumeration/look-up.

> * Relation structure definition
>
> relation_schema<string,string> father = gender(_1,"male")&& child(_2,_1);
>
> child could be defined as follows:
>
> relation_schema <string, string> child;
>
> child |= eq(_1,"Sam") && eq(_2,"Mary");
> child |= eq(_1,"Denise") && eq(_2,"Mary") ;
> child |= eq(_1,"Sam") && eq(_2,"Frank");
> child |= eq(_1,"Denise") && eq(_2,"Frank");
> child |= eq(_1,"Frank") && eq(_2,"Gary");
>

This style leads to "open ended" relations. Anybody can inject clauses
into child or father...dangerous. then you need protection mechanisms.
The current style ensures "closed" relations by default... which is
similar to C++ functions being "closed".
This design is a deliberate breakaway from Prolog.

_1 , _2 have limitations on arity. relations are direct computational
equivalents in LP to functions
Therefore the current syntax modeled to be closer to around
functions/expressions rather than data.
It allows things like member relations, virtual member relations and
template relations etc. Which in
turn allows us to extend existing OO design patterns to the LP.

Also I feel the syntax

relation child = x || y || z ;

is nicer to read/type than

relation_schema<..> child;
child |= x;
child |= y;
child |= z;

> * Bindings

Think of it in terms currying in the functional paradigm.
When you take a (binary) function and bind one of its argument you still
have a (unary) function.
Same with relations. Don't think of a relation as data... even if the
initial examples in the tutorial
gives you that feeling. think of them as rules perhaps (rather than facts)
..if it helps.

> * Typed relations
> I'm not sure of ot is possible to implement the following, but let me
> continue.
>
> The preceding example uses a type erasure to have untyped relation.
> Castor could also have typed relations. typed_relation<T1,...,Tn>
> can be considered as a container of tuple<lref<T1>,...,lref<Tn>>
>
> typed_relation<string,string> father_child = father(_1, _2);
> for(tuple<lref<string>,lref<string> > r&: father_child) {
> lref<string> f, c;
> tie(f,c) = r;
> cout << c << " is " << f << "'s child\n";
> }
>
> or using iterators
>
> for(typed_relation<string,string>::iterator it= father_child.begin();
> it!=father_child.end();++it) {
> lref<string> f, c;
> tie(f,c) = *it;
> cout << c << " is " << f << "'s child\n";
> }
>
> There are surely a lot of errors on the preceding design, but I think is
> worth see if it is possible to adapt it to your library.

Perhaps, but I don't think I see the motivating benefits. The syntax is
getting poorer.
Will need more fleshed out details with definitions of child(), father() &
ancestor().

If you really like to use "range based for loops" or "iterator style
enumeration" its nicer to :

   for( auto res : iterable(father(x,y)) )
        cout << *x << " " << *y <<"\n";

where iterable adapts an arbitrary relation/coroutine into an iterator.

> * dynamic relations / views
> Example extracted from the tutorial
>
> list<pair<string,string> > genderList = ...;
> // dynamically building a relation
> Disjunctions gender_dyn(lref<string> p, lref<string> g) {
> Disjunctions result;
> list<pair<string,string> >::iterator i;
> for( i=genderList.begin(); i!=genderList.end(); ++i)
> result.push_back(eq(p,i->first) && eq(g,i->second) );
> return result;
> }
>
> What you talk dynamic relations is a transformation from a container to
> a disjonction relation.
> The user could implement a relation directly ensuring the unification.
> E.g.
>
> struct gender_dyn : relation
> ...
> list<pair<string,string> > list_;
> list<pair<string,string> >::iterator current_;
>
> bool operator(lref<string> p, lref<string> g) {
> if (current_==list.end()) return false;
> p= current_->first; // unification
> g= current_->second; // unification
> ++current_;
> return true;
> }
>
> bool operator(string const& p, lref<string> g) {
> while (current_!=list.end() && p!=current_->first)
> ++current_;
> if (current_==list.end()) return false;
> g= current_->second; // unification
> ++current_;
> return true;
> }
> ...
>
> This should be more efficient, ins't it?

The goal of the example is only to demonstrate how to dynamically build
the clauses in a relations. You can make this example more efficient with
some work. For brevity, the existing example is re-used and implemented
differently. Your solution is to define the relation imperatively as
opposed to adding clauses dynamically. That is a valid alternative...
although it requires more work it can often lead to efficiency gains.

BTW: remember in your code above ... unification is not merely assignment.
No need for inheritance either.
It would roughly look as follows:

  struct gender_dyn : Coroutine {
    list<pair<string,string> > list_;
    list<pair<string,string> >::iterator current_;

     gender_dyn(lref<string> p, lref<string> g);

     bool operator() (void) {
        co_begin();
        list_ = loadData();
        for (current_= list_.begin(); current!=list.end(); ++current_ ) {
           .. unify ..
           if(unify succeeds)
              co_yield(true);
        }
        if(p was modified)
            p.reset();

        if(g was modified)
            g.reset();
        co_end();
    }
  };

- Roshan


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk