#include "structures.h" #define monotonic 1 #define non_monotonic 0 #define incomplete 0 #define complete 1 int last_prop=0; int pid; int unique_name=1000; /************************************************************************* ************************************************************************** ************************ ignore this part********************************* *************************************************************************/ /* these definitions are put here to keep the compiler happy- ignore them, they are replicated (sometimes in commented form) where they belong */ static struct proposition *true; struct clause_list {struct tms_clause *cl; struct tms_clause_element *c_e; struct clause_list *next; }; struct clause_list *cons_cl(); void stabilize(); void set(); void make_monotonic_tms_clause(); void return_list(); void reset(); void set(); struct proposition *make_primitive_prop(module_ptr agent, term_ptr id); void add_definite_tms_clause(); struct literal_list *get_l_cell(); void return_cell(); void insert_t_prop(); struct proposition *make_unique_prop(); struct tms_clause_element *cons_ce(p,private,fire,list) struct proposition *p; int private,fire; struct tms_clause_element *list; { struct tms_clause_element *temp; temp=(struct tms_clause_element *)malloc(sizeof(struct tms_clause_element)); if (temp==NULL) { printf("alocatin error - aborting"); exit(0); }; temp->prop=p; temp->private_counter=private; temp->firing=fire; temp->next=list; return temp; } /*************************************************************** **************************************************************** ******************** the tms_clause stack ************************** **************************************************************** ***************************************************************/ /* two stacks of tms_clauses used for holding the non_mon tms_clauses which might need to be updated */ /* ============================================================ | greater_priority() | |----------------------------------------------------------| | Params : 1) a non-monotonic tms clause | | 2) a non-monotonic tms clause | | Desc : compares the priority of the two clauses | | | | Returns:TRUE if the first clause is higher priority than the second, FALSE otherwise |==========================================================| */ int lower_priority(struct tms_clause *c1, struct tms_clause *c2) { return (c1->cl.non_mon.prioritycl.non_mon.priority); } int higher_priority(struct tms_clause *c1, struct tms_clause *c2) { return (c1->cl.non_mon.priority>c2->cl.non_mon.priority); } struct list *firing_stack=NULL; struct list *non_firing_stack=NULL; extern void sorted_insert(struct list **address, void *element, comp_funct greater); /* obvious !*/ void push_tms_clause(struct tms_clause *c) { if (c->cl.non_mon.firing) sorted_insert(&firing_stack,c,(comp_funct)higher_priority); else sorted_insert(&non_firing_stack,c,(comp_funct)lower_priority); } struct tms_clause *pop_firing_stack() { struct tms_clause *temp = NULL; if (firing_stack!=NULL) { struct list * garbage; temp=firing_stack->object; garbage=firing_stack; firing_stack=firing_stack->next; free(garbage); } return temp; } struct tms_clause *pop_non_firing_stack() { struct tms_clause *temp = NULL; if (non_firing_stack!=NULL) { struct list * garbage; temp=non_firing_stack->object; garbage=non_firing_stack; non_firing_stack=non_firing_stack->next; free(garbage); } return temp; } /***************************************************************** ****************************************************************** ********************** the action queue ************************** ****************************************************************** *****************************************************************/ /* holds the action propositions which have possibly become true */ struct literal_list *front; struct literal_list *back; void push_action(p) struct proposition *p; { front->next=get_l_cell(); front=front->next; front->prop=p; } struct proposition *pop_action() { struct literal_list *temp; struct proposition *p; if (front != back) { temp=back; back=back->next; return_cell(temp); return back->prop; } else return NULL; } struct list *non_prop_front; struct list *non_prop_back; void push_non_prop_action(module_ptr agent, struct term *term) { struct agent_term *action= (struct agent_term *)malloc(sizeof(struct agent_term)); action->agent=agent; action->term=term; non_prop_front->next=cons(action,NULL); non_prop_front=non_prop_front->next; } struct agent_term *pop_non_prop_action() { struct list *temp; struct agent_term *p; if (non_prop_front != non_prop_back) { temp=non_prop_back; non_prop_back=non_prop_back->next; free(temp); return non_prop_back->object; } else return NULL; } struct agent_term *next_action() { struct proposition *p=pop_action(); while (p !=NULL&&p->state!=1) { p=pop_action(); } if(p!=NULL) { struct agent_term *result; result=(struct agent_term *)malloc(sizeof(struct agent_term)); result->agent=p->agent; result->term=p->term; return result; } else return pop_non_prop_action(); } /*************************************************************** ********************* adding and deleting tms_clauses **************/ void make_binary_tms_clause(pos_prop,neg_prop) struct proposition *pos_prop; struct proposition *neg_prop; { make_monotonic_tms_clause(cons_literal(1,pos_prop,cons_literal(0,neg_prop,NULL))); } void weaken_tms_clause(prop,c) struct proposition *prop; struct tms_clause *c; { int sat,count; struct tms_clause_element *temp; sat=prop->negation->state; count=c->cl.mon.counter+(1-sat); c->cl.mon.counter=count; c->cl.mon.c_e=cons_ce(prop,sat,0,c->cl.mon.c_e); prop->negation->in_body_list= cons_cl(c,c->cl.mon.c_e,prop->negation->in_body_list); if (count<=2) { temp=c->cl.mon.c_e; while (temp) { if (temp->firing) { if (temp->private_counter+count > 1) { --(temp->firing); --(temp->prop->counter); if (temp->prop->counter==0) reset(temp->prop); } } else if (temp->private_counter+count==1) { ++(temp->firing); ++(temp->prop->counter); set(temp->prop); } temp=temp->next; } } } void make_monotonic_tms_clause(lit_list) struct literal_list *lit_list; { struct literal_list *original_lit_list=lit_list; short int count; struct tms_clause *c; struct proposition *p; int sat; struct tms_clause_element *temp=NULL; c=(struct tms_clause *)malloc(sizeof(struct tms_clause)); if (c==NULL) { printf("allocation error - aborting"); exit(0); } c-> c_type =monotonic; count=length(lit_list); while (lit_list) { if (lit_list->sign) {p=lit_list->prop;} else {p=lit_list->prop->negation;} if (p->negation->state) { sat=1; count--; } else sat=0; temp=cons_ce(p,sat,0,temp); p->negation->in_body_list=cons_cl(c,temp,p->negation->in_body_list); lit_list=lit_list->next; } c->cl.mon.counter=count; c->cl.mon.c_e=temp; if (count<=1) { while (temp) { if (temp->private_counter+count==1) { ++(temp->firing); ++(temp->prop->counter); set(temp->prop); } temp=temp->next; } } } void make_non_monotonic_tms_clause(abn,abn_bar) struct proposition *abn; struct proposition *abn_bar; {struct tms_clause *c; if ((c=(struct tms_clause *)malloc(sizeof(struct tms_clause)))==NULL) {printf("allocation error - aborting"); exit(0);} c-> c_type = non_monotonic; ((c->cl).non_mon).ab=abn; ((c->cl).non_mon).ab_bar=abn_bar; c->cl.non_mon.firing=0; c->cl.non_mon.priority=sym_table[abn->term->functor]->priority; abn->in_body_list=cons_cl(c,NULL,abn->in_body_list); push_tms_clause(c); } int next_id() { int id; id=unique_name++; return id; } extern int justify_trace; void *print_justification(struct literal_list *c) { printf("*********************************************************\n"); if (c->sign==1) print_prop(c->prop); else printf("false\n"); c=c->next; while (c) { printf(" "); print_prop(c->prop); c=c->next; } printf("*********************************************************\n"); } void add_horn_tms_clause(struct literal_list *c) { struct literal_list *temp=c; if ((c->sign==1)&& !(c->prop->is_abducible) && !(c->prop->is_incomplete)) {add_definite_tms_clause(c);} else { make_monotonic_tms_clause(c); } } /* adds a definite tms_clause, and its meta-completion, as tms_clauses. The first element of the tms_clause should be the head, and the rest the body */ void add_definite_tms_clause(c) struct literal_list *c; { struct proposition *cl_unique; struct proposition *temp_meta; struct proposition *head=c->prop; struct literal_list *body=c->next; struct tms_clause *meta_completion; meta_completion=head->meta->in_body_list->cl; cl_unique=make_unique_prop(); while (body) { make_binary_tms_clause(body->prop->meta,cl_unique); body=body->next; } weaken_tms_clause(cl_unique,meta_completion); make_monotonic_tms_clause(c); } struct proposition *make_abducible(agent,id,p_type) module_ptr agent; struct term *id; int p_type; { struct proposition *ab; ab=make_primitive_prop(agent,id); ab->meta=ab; ab->is_abducible=1; ab->is_action=p_type; make_non_monotonic_tms_clause(ab,ab->negation); return ab; } void print_tms_clause(c) struct tms_clause *c; { struct tms_clause_element *temp; temp=c->cl.mon.c_e; if (c->c_type==monotonic) { printf("\n counter:%d literals ", c->cl.mon.counter); while (temp) { print_prop_id(temp->prop); printf(" "); temp=temp->next; } } else { printf("\n firing:%d literals ", c->cl.non_mon.firing); print_prop_id(c->cl.non_mon.ab_bar); print_prop_id(c->cl.non_mon.ab); } } /*********************************************************************** ************************************************************************ *********************** tms_clause list ********************************** *********************************************************************/ /* 'tms_clause-list' is used to record the tms_clauses in which the negation of a proposition occurs. Elements of 'tms_clause-list' are structures containing a pointer to the tms_clause, and a pointer to the negation of the proposition in that tms_clause */ /* struct clause_list {struct tms_clause *cl; struct tms_clause_element *c_e; struct clause_list *next; }; */ struct clause_list *cons_cl(c,ce,list) struct tms_clause *c; struct tms_clause_element *ce; struct clause_list *list; { struct clause_list *temp; temp=(struct clause_list *)malloc(sizeof(struct clause_list)); if (temp==NULL) { printf("alocatin error - aborting"); exit(0); } temp->cl=c; temp->c_e=ce; temp->next=list; return temp; } /************************************************************************** *************************************************************************** ***************************** propositions ******************************** *************************************************************************** *************************************************************************/ /*'in_body_list' is the list of tms_clauses in which the negation of a proposition appears. 'counter' is the number of tms_clauses with 'prop' at their head which are firing. */ /* struct proposition { struct term *id; struct proposition *negation; struct proposition *meta; struct clause_list *in_body_list; short int counter; unsigned int state: 1; unsigned int is_meta:1; unsigned int is_negative:1; unsigned int is_abducible:1; unsigned int processed:1; unsigned int is_incomplete:1; unsigned int is_action:1; }; */ struct proposition *make_primitive_prop(agent,prop_id) module_ptr agent; struct term *prop_id; { struct proposition *c; struct proposition *c_bar; if ((c=(struct proposition *)malloc(sizeof(struct proposition)))==NULL) {printf("allocation error - aborting"); exit(0);} if ((c_bar=(struct proposition *)malloc(sizeof(struct proposition)))==NULL) {printf("allocation error - aborting"); exit(0);} c->agent=agent; c->term=prop_id; c->negation=c_bar; c->meta=NULL; c->is_negative=NULL; c->in_body_list=NULL; c->counter=NULL; c->state=NULL; c->is_meta=NULL; c->is_abducible=NULL; c->is_incomplete=NULL; c->is_action=NULL; c->processed=NULL; c->is_unique=FALSE; c->spy_id=0; c_bar->agent=agent; c_bar->term=prop_id; c_bar->negation=c; c_bar->meta=NULL; c_bar->is_negative=1; c_bar->in_body_list=NULL; c_bar->counter=NULL; c_bar->state=NULL; c_bar->is_meta=NULL; c_bar->is_abducible=NULL; c_bar->is_incomplete=NULL; c_bar->is_action=NULL; c_bar->processed=NULL; c_bar->is_unique=FALSE; c_bar->spy_id=0; return c; } struct proposition *make_unique_prop() { struct proposition *c; struct proposition *c_bar; int id; if ((c=(struct proposition *)malloc(sizeof(struct proposition)))==NULL) {printf("allocation error - aborting"); exit(0);} if ((c_bar=(struct proposition *)malloc(sizeof(struct proposition)))==NULL) {printf("allocation error - aborting"); exit(0);} id=next_id(); c->term=(struct term *) id; c->negation=c_bar; c->meta=NULL; c->is_negative=NULL; c->in_body_list=NULL; c->counter=NULL; c->state=NULL; c->is_meta=NULL; c->is_abducible=NULL; c->is_incomplete=NULL; c->is_action=NULL; c->processed=NULL; c->is_unique=TRUE; c->spy_id=0; c_bar->term=c->term; c_bar->negation=c; c_bar->meta=NULL; c_bar->is_negative=1; c_bar->in_body_list=NULL; c_bar->counter=NULL; c_bar->state=NULL; c_bar->is_meta=NULL; c_bar->is_abducible=NULL; c_bar->is_incomplete=NULL; c_bar->is_action=NULL; c_bar->processed=NULL; c_bar->is_unique=TRUE; c_bar->spy_id=0; return c; } /* makes a complete proposition of a given type, its negation, the corresponding meta-prop, and its negation with the given id */ struct proposition *make_complete(agent,id,p_type) module_ptr agent; struct term *id; int p_type; { struct proposition *c; struct proposition *c_meta; c=make_primitive_prop(agent,id); c_meta=make_primitive_prop(agent,id); c->meta=c_meta; c_meta->is_meta=1; c_meta->negation->is_meta=1; make_monotonic_tms_clause(cons_literal(0,c_meta,NULL)); c->is_incomplete=0; c->is_action=p_type; return c; } /* change an incomplete proposition to a false complete */ void change_to_false_complete(struct proposition *prop) { if (prop->is_incomplete) { make_monotonic_tms_clause(cons_literal(0,prop->meta,NULL)); prop->is_incomplete=FALSE; make_monotonic_tms_clause(cons_literal(0,prop,NULL)); printf("making proposition false\n"); print_prop(prop); } } /* makes an incomplete proposition of a given type, its negation, the corresponding meta-prop, and its negation with the given id */ struct proposition *make_incomplete(agent,id,p_type) module_ptr agent; struct term *id; int p_type; { struct proposition *c; struct proposition *c_meta; c=make_primitive_prop(agent,id); c_meta=make_primitive_prop(agent,id); c->meta=c_meta; c_meta->is_meta=1; c_meta->negation->is_meta=1; c->is_incomplete=1; c->is_action=p_type; return c; } int is_processed(p) struct proposition *p; {return p->processed;} void set_processed(p) struct proposition *p; { p->processed=1; } void make_goal(struct proposition *p) { struct proposition *goal_cond=make_primitive_prop(p->agent,NULL); set(goal_cond); p->meta->meta=goal_cond; /* the meta field of a meta prop represents the conditional prop for that goal */ make_monotonic_tms_clause(cons_literal(1, p->meta,cons_literal(0, goal_cond, NULL))); } void unrequest_goal(struct proposition *p) { reset(p->meta->meta); } void make_fact(struct proposition *p) { add_horn_tms_clause(cons_literal(1,p,NULL)); } void print_prop_id(struct proposition *prop) { char *sign,*meta; if (prop->is_negative) {sign="-";} else {sign="";} if (prop->is_meta) {meta="*";} else {meta="";} printf("%s%s",sign,meta); if (prop->is_unique) { printf("u%d ",(int) prop->term); } else print_term(prop->term,sym_table); printf("\n"); } /* prints a proposition */ void print_prop(p) struct proposition *p; { struct clause_list *temp=p->in_body_list; if (p) { printf("%s:",p->agent->name); print_prop_id(p); #if FULL_PROP while (temp) { print_tms_clause(temp->cl); temp=temp->next; } #endif printf("\n"); } } /**************************************************************************** ***************************************************************************** *************************** literal list ******************************** ***************************************************************************** ****************************************************************************/ /* Lists are used to represent bodies of tms_clauses. Since these are only used at the time of adding the tms_clause and are not used again, to avoid the problem of garbage genearation they are recycled. */ /* struct literal_list { unsigned int sign: 1; struct proposition *prop; struct literal_list *next; }; */ /* free_list points to the list of available l_list cells */ struct literal_list *my_free_list = NULL; /* get_l_cell is used to get a l_cell for list construction. If possible, it tries to use a re-cycled cell rather than a new cell */ struct literal_list *get_l_cell() { struct literal_list *temp; if (my_free_list) { temp=my_free_list; my_free_list=my_free_list->next; } else { temp=(struct literal_list *)malloc(sizeof(struct literal_list)); if (temp==NULL) { printf("allocation error - aborting"); exit(0); } } temp->sign=NULL; temp->prop=NULL; temp->next=NULL; return temp; } /* add a literal to a literal_list */ struct literal_list *cons_literal(int s, struct proposition *p, struct literal_list *list) { struct literal_list *temp; temp=get_l_cell(); temp->next=list; temp->sign=s; temp->prop=p; return temp; } /* print a literal_list */ void print_lit_list(list) struct literal_list *list; { printf("\n literal list "); while (list) { if (list->sign) printf("+"); else printf("-"); print_term(list->prop->term,sym_table); list=list->next; } printf("\n"); } /* when a literal cell is no longer necessary, it is returned for re-cycling via return_cell */ void return_cell(cell) struct literal_list *cell; { cell->next=my_free_list; my_free_list=cell; } /* when a list of literals is no longer necessary, it is returned for re-cycling via return_list */ void return_list(struct literal_list *list) { struct literal_list *first; if (list) { first=list; while (list->next) list=list->next; list->next=my_free_list; my_free_list=first; } } /* determines the length of a list of literals */ int length(list) struct literal_list *list; { int temp=0; while (list) { temp++; list=list->next; } return temp; } /******************************************************************* ******************** the propagation routines ********************** ******************************************************************** *******************************************************************/ void dummy() { printf("got there"); } void decrease_one(c_l) struct clause_list *c_l; { struct tms_clause *c=c_l->cl; if ((c->c_type)==monotonic) { struct tms_clause_element *temp=c->cl.mon.c_e; --(c->cl.mon.counter); ++(c_l->c_e->private_counter); if (c->cl.mon.counter <= 1) { while (temp) { if ((temp->private_counter+c->cl.mon.counter==1)&& (temp->firing==0)) { ++(temp->firing); ++(temp->prop->counter); set(temp->prop); } temp=temp->next; } } } else { if (c->cl.non_mon.firing==1) push_tms_clause(c); } } void decrease_all(c_list) struct clause_list *c_list; { while (c_list) { decrease_one(c_list); c_list =c_list -> next; } } struct list *just_set_props; void push_set_prop(struct proposition * p) { just_set_props=cons(p,just_set_props); } struct proposition *pop_set_prop() { struct proposition *p; if (just_set_props!=NULL) { struct list *temp; p=just_set_props->object; temp=just_set_props; just_set_props=just_set_props->next; free(temp); return p; } else return NULL; } void set(struct proposition *p) { void spy_state(int agent_id,int id, int state); if (p-> state == 0) { p -> state = 1; if (p->spy_id!=0) spy_state(p->agent->agent_functor,p->spy_id,1); if (p->is_action) push_action(p); if(!p->is_unique && p->term !=NULL) push_set_prop(p); decrease_all(p->in_body_list); } } void increase_one(c_l) struct clause_list *c_l; { int ctr; struct tms_clause *c; c=c_l->cl; if ((c->c_type)==monotonic) { struct tms_clause_element *temp; temp=c->cl.mon.c_e; --(c_l->c_e->private_counter); ++(c->cl.mon.counter); ctr=c->cl.mon.counter; if (ctr==1) { while (temp) { if ((temp->private_counter)&&(temp->firing)) { --(temp->firing); --(temp->prop->counter); if (temp->prop->counter==0) reset(temp->prop); } temp=temp->next; } } else if (ctr==2) { while (temp) { if (temp->firing) { --(temp->firing); --(temp->prop->counter); if (temp->prop->counter==0) reset (temp->prop); break; } temp=temp->next; } } } else { if (c->cl.non_mon.firing==0) push_tms_clause(c); } } void increase_all(c_list) struct clause_list *c_list; { while (c_list) { increase_one(c_list); c_list = c_list -> next; } } void reset(p) struct proposition *p; { void spy_state(int agent_id,int id, int state); if (p-> state ==1) { p->state = 0; if (p->spy_id!=0) spy_state(p->agent->agent_functor,p->spy_id,0); increase_all(p->in_body_list); } } /*********************************************************************** ************************************************************************ **************************** stabilization routine ********************* ************************************************************************ ***********************************************************************/ /* takes one potentially altered non-monotonic tms_clause, and if necessary propagates the changes resulting from its activation */ void process_ab(c) struct tms_clause *c; { if ((c->cl).non_mon.firing==1-((c->cl).non_mon.ab)->state) {return;} else { if ((c->cl).non_mon.firing) { (c->cl).non_mon.firing = 0; --(((c->cl).non_mon.ab_bar)->counter); if (((c->cl).non_mon.ab_bar)->counter ==0) { reset((c->cl).non_mon.ab_bar); } } else { (c->cl).non_mon.firing = 1; ++(((c->cl).non_mon.ab_bar)->counter); if (((c->cl).non_mon.ab_bar)->counter ==1) { set((c->cl).non_mon.ab_bar); } } } } /* iterates until the network stabilizes */ extern void forward_direct_chain(module_ptr agent, struct term *atom); void stabilize() { while(firing_stack) { process_ab(pop_firing_stack()); } while (non_firing_stack) { struct tms_clause *c; while(firing_stack) process_ab(pop_firing_stack()); process_ab(pop_non_firing_stack()); } while(just_set_props) { struct proposition *p; p=pop_set_prop(); if (p->state==1) forward_direct_chain(p->agent, p->term); } } void initialize_tms() { front=get_l_cell(); back=front; non_prop_front=cons(NULL,NULL); non_prop_back=non_prop_front; just_set_props=NULL; } void print_state(p) struct proposition *p; { print_prop(p); print_prop(p->negation); if (!(p->is_abducible)) { print_prop(p->meta); print_prop(p->meta->negation); } printf("\n"); } void print_ab(struct tms_clause *c) { print_prop(c->cl.non_mon.ab); } char *ta[]={"s","f","am","af1","af2"}; void psm(char *agent_name,int count,char **symbols) { module_ptr agent=sym_table[functor_string(agent_name)]->agent_ref; int i; struct proposition *p; for(i=0;iprop_table[functor_string(symbols[i])]->object; printf("%-5s %d%d%d%d\n",symbols[i], p->state, p->meta->state, p->negation->state, p->meta->negation->state); } } /* ============================================================ | spy_state() | |----------------------------------------------------------| | Params : 1)the id of the spy window | | 2) the state of the proposition | | Desc : sends the appropriate message to update the spy window |==========================================================| */ void spy_state(int agent_id, int window_id, int state) { void write_window_pipe(term_ptr term); term_ptr term_template(char *template); term_ptr spy_term=term_template("n nnii4 2"); spy_term->term_type=TUPLE; spy_term->argument_array[0]->functor=agent_id; spy_term->argument_array[1]->functor=X_WINDOW; spy_term->argument_array[1]->argument_array[0]->functor=INSPECT; spy_term->argument_array[1]->argument_array[1]->functor=STATE; spy_term->argument_array[1]->argument_array[2]->functor=state; spy_term->argument_array[1]->argument_array[3]->functor=window_id; write_window_pipe(spy_term); free_term(spy_term); }