pddl.c

intel ipp4.1性能库的一些例子。

/*********************************************************************
 * File: pddl.c
 * Description: Functions for the pddl dependend part of
 *              the parser and the preprocessing.
 *
 * Authors: Frank Rittinger, Andreas Schoen 1998
 *
 *********************************************************************/ 
/*********************************************************************
 * (C) Copyright 1998 Albert Ludwigs University Freiburg
 *     Institute of Computer Science
 *
 * All rights reserved. Use of this software is permitted for 
 * non-commercial research purposes, and it may be copied only 
 * for that use.  All copies must include this copyright message.
 * This software is made available AS IS, and neither the authors
 * nor the  Albert Ludwigs University Freiburg make any warranty
 * about the software or its performance. 
 *********************************************************************/
/*********************************************************************
 * INTRODUCTION TO THIS FILE
 *
 * All(?) functions are programmed recursively and not dynamically 
 * but this should not affect the efficiency, as these functions are called
 * only once in the beginning, and in most domains the recusion 
 * depth is not high.
 * Exceptions are dnf and their dependent(?help/sub-) functions
 * distribute_and_ors and append_following. They might be called often
 * during the instantiation
 * 
 * All function, that have pl-nodes as both input and output 
 * keep the input node fixed!  (for convenience in the calling function)
 *
 * All functions assume they are allowed to free nodes the plnode tree doesn't 
 *   need anymore. 
 *   
 *
 * i_pl,j_pl,k_pl,l_pl always are Laufvars(?l)
 *********************************************************************/
/*********************************************************************
 *
 * Dependencies of functions:
 * (1)
 * pddl(16)-+----->rename_all_quantifiers*(13)----->rename_quantifier*(14)
 * (2)      |
 *          +----->axioms_to_operators->...
 * (3)      |                                                         
 *          +-->ands_to_top*(3)--->combine_whens*(2)-->contains_when*(1)
 *          |      |                     |   ^            ^                 
 *          |      |                     v   |            |
 *          |      |         distribute_whens,2nd branch--+
 *          |      v    
 *          | distribute_whens,1st branch ;distribute_unary;combine_ands
 *          |                                                         
 * (4)      |                                                         
 *          |                                                         
 *          |                                                         
 *          +-------+->nots_down_qunatifiers_up*(11)<----+
 *          |       |                            |             
 *          |       +-->nots_down(10)------------+
 *          |       |       v                    |             
 *          |       |     distibute_unary        |             
 *          |       |                            |             
 *          |       +->all_the quantifiers_up(9)-+
 *          |                                    |            
 *                                               v            
 *                                    move_quantifier(8)
 * (5) ,trafo (6)                                                
 * pddl_inner(16)----->dnf*(6)<->distribute_and_ors(5)
 *                         |      |               |           
 *                         |      v               v  
 *                         +-combine_ands     append_following(5)          
 * (7)
 *
 * fn_name*(position in file) ,* means function calls itself
 *
 *
 *
 * Used basic functions:
 *
 * distribute_unary(6)
 * combine_ands(12)
 * 
 *********************************************************************/

#include "ipp.h"
#include "pddl.h"
#include "memory.h"
#include "utilities.h"
#include "output.h"

#define LOG_Q_NUMBER 8  /* so there can be 10^(6-3)=1000 quantifiers */
		

/* #include "/home/keim/pur4.1/purify-4.1-solaris2/purify.h" */

/* Laufv?l for number of quantifiers, needed for quantifier renaming */
static int snr_quantifiers;

int dep=0;

/*  void copy_contents_of_CodeNode( CodeNode **dest, CodeNode *source ); */
/* in instantiate.c */


void 
begin_of_function_pl ( char * name , PlNode * plnode)
{
  if (0 && gcmd_line.display_info>=20)
    { 
      dep++;
      /* if (purify_new_leaks()) */
/* 	    { */
/* 	      printf("New leaks\n"); */
/* 	    }  */
/*       else  */
/* 	{ */
/* 	  printf("No New leaks\n"); */
/* 	} */
      printf("\n%u%s\n",dep,name);
      print_plnode( plnode ,0);
    }
}
void 
end_of_function_pl ( char * name , PlNode * plnode)
{
  if (0 && gcmd_line.display_info>=20)
    { 
      /* if (purify_new_leaks()) */
/* 	    { */
/* 	      printf("New leaks\n"); */
/* 	    }  */
/*       else  */
/* 	{ */
/* 	  printf("No New leaks\n"); */
/* 	} */
      printf("\n%uEnd %s\n",dep,name);
      print_plnode( plnode ,0);
      dep--;
    }
}
void 
begin_of_function_code ( char * name , CodeNode * codenode)
{
  if (0 && gcmd_line.display_info>=20)
    { 
      dep++;
      /* if (purify_new_leaks()) */
/* 	    { */
/* 	      printf("New leaks\n"); */
/* 	    }  */
/*       else  */
/* 	{ */
/* 	  printf("No New leaks\n"); */
/* 	} */
      printf("\n%u%s\n",dep,name);
      print_CodeNode( codenode ,0);
    }
}
void 
end_of_function_code ( char * name , CodeNode * codenode)
{
  if (0 && gcmd_line.display_info>=20)
    { 
      /* if (purify_new_leaks()) */
/* 	    { */
/* 	      printf("New leaks\n"); */
/* 	    }  */
/*       else  */
/* 	{ */
/* 	  printf("No New leaks\n"); */
/* 	} */
      printf("\n%uEnd %s\n",dep,name);
      print_CodeNode( codenode ,0);
      dep--;
    }
}

/******************** quantifiers_renaming  ***************************/
/*********************************************************************
 * INPUT  plnode: any pl-tree
 * OUTPUT plnode: equivalent tree with all the quantified variables renamed 
 * to ??x , x being a counter
 * USING  
 *********************************************************************/
void
rename_all_quantifiers(PlNode * plnode)
{
  Bool contained;
  PlNode * i_pl;
  begin_of_function_pl("Rename_all_quantifiers",plnode);
  switch (plnode->connective)
    {    
    case EX:
    case ALL:
      rename_all_quantifiers(plnode->sons);
      contained=
	rename_quantifier(plnode,plnode->atom->item,FALSE);
      snr_quantifiers++;
      if (!contained)
	{
	  printf("Quantor wegschmeissen noch nicht implementiert.");
	}
      break;
    case AND:
    case OR:
    case WHEN:
      {
	i_pl=plnode->sons;    
	while (i_pl!=NULL)
	  {
	    rename_all_quantifiers(i_pl);
	    i_pl=i_pl->next;
	  }
      }
      break;
    case NOT:
      rename_all_quantifiers(plnode->sons);
    case ATOM:
    case TRU:
      break;
    default:
      spec_error("Rename_all_quantifiers");
    }
  end_of_function_pl("Rename_all_quantifiers",plnode);
}

/*********************************************************************
 * This function renames all occurences of the variable token to
 *  ??x, where x is the current value of the static counter snr_quantifiers
 * INPUT  plnode: pl-tree
 *        token: the name of the variable to be renamed
 *        cont:TRUE if the variable occurred so far 
 *                 (just for stupid domain definitions)
 * OUTPUT Bool: TRUE if the variable occurred so far or now
 * USING  
 *********************************************************************/
Bool
rename_quantifier(PlNode * plnode,char * token,Bool cont)
{
  PlNode * i_pl;
  TokenList * i_tl;
  char * i_token;
  begin_of_function_pl("Rename_quantifier",plnode);
  i_token=new_token(strlen(token)+1);
  strcpy(i_token,token);
  switch (plnode->connective)
    {
    case ALL:
    case EX:
      if (SAME==strcmp(plnode->atom->item,i_token))
	{
	  free(plnode->atom->item);
	  plnode->atom->item = new_token(LOG_Q_NUMBER);
	  sprintf(plnode->atom->item,"??%d",snr_quantifiers);

	  cont=TRUE;
	}
      cont=rename_quantifier(plnode->sons,i_token,cont);
      break;
    case NOT:
      cont=rename_quantifier(plnode->sons,i_token,cont);
      break;
    case AND:
    case OR:
    case WHEN:
      i_pl=plnode->sons;    
      while (i_pl!=NULL)
	{
	  cont|=rename_quantifier(i_pl,i_token,cont);
	  i_pl=i_pl->next;
	}
      break;
    case TRU:
      break;
    case ATOM:
      i_tl=plnode->atom;
      while (i_tl!=NULL)
	{
	  if (SAME==strcmp(i_tl->item,i_token))
	    {
	      free(i_tl->item);
	      i_tl->item = new_token(LOG_Q_NUMBER);
	      sprintf(i_tl->item,"??%d",snr_quantifiers);
	      cont=TRUE;
	    }
	  i_tl=i_tl->next;
	}
      break;
    default:
      spec_error("Rename_quantifier");
    }
  free(i_token);
  end_of_function_pl("Rename_quantifier",plnode);
  return cont;
}

/******************** pddl_outer ***************************/

/*********************************************************************
 * INPUT  plnode: AND or OR node 
 * OUTPUT plnode: (same) AND/OR node with all nodes with the same connective 
 *   directly below combined to one single AND node
 * USING  
 *********************************************************************/
void
combine_ands_pl ( PlNode * plnode )
{
  PlNode * i_pl,*j_pl,*this_pl;
  Connective con=plnode->connective;
  
  begin_of_function_pl("Combine ands",plnode);
  if (plnode->connective!=AND && plnode->connective!=OR) 
    {
      spec_error("Combine ands");
    }
  i_pl=new_pl_node(DUMMY);
  this_pl=plnode->sons;
  i_pl->next=this_pl;
  plnode->sons=i_pl;
  while (this_pl !=NULL)
    {
      if (this_pl->connective==con)
	{
	  combine_ands_pl(this_pl);
	  i_pl->next=this_pl->sons;
	  j_pl=this_pl->next;
	  free(this_pl);
	  this_pl=j_pl;
	  while (NULL!=i_pl->next)
	    {
	      i_pl=i_pl->next;
	    }
	}
      else /*  !=AND  while  */
	{
	  i_pl->next=this_pl;
	  i_pl=this_pl;
	  this_pl=this_pl->next;
	}
    } /*  while  */
  i_pl=plnode->sons->next;
  free(plnode->sons);/* DUMMY */
  plnode->sons=i_pl;
  end_of_function_pl("Combine ands",plnode);
} 

/*********************************************************************
 * INPUT  plnode: pl-tree
 * OUTPUT Bool: true iff the tree below (including plnode) contains a when node
 * USING  
 *********************************************************************/
Bool 
contains_when ( PlNode * plnode )
{
  PlNode * i_pl;
  
  switch (plnode->connective)
    {
    case AND:
      for (i_pl=plnode->sons;i_pl!=NULL;i_pl=i_pl->next)
	{
	  if (contains_when(i_pl))
	    {
	      return TRUE;
	    }
	}
      return FALSE;
    case ALL:
      return contains_when(plnode->sons);
    case WHEN:
      return TRUE;
    case NOT:
      return FALSE;
    case ATOM:
      return FALSE;
    default:
      spec_error("Contains_when");
      return TRUE;
    }
  
}

/*********************************************************************
 * INPUT  plnode: WHEN node with another when node below
 * OUTPUT plnode: a logically equivalent tree without exactly one WHEN node
 * USING  
 *********************************************************************/
void
combine_whens ( PlNode * plnode )
{
  PlNode * new_pl;
  PlNode * son=plnode->sons->next; /* effect */

  begin_of_function_pl("Combine_whens",plnode);
  switch (son->connective)
    {
    case AND:
      distribute_when(plnode,FALSE);
      break;
    case ALL:
      /* puts quantifier above when node */
      plnode->sons->next=son->sons;
      plnode->atom=son->atom;
      son->atom=NULL;
      son->sons=plnode->sons;
      son->connective=WHEN;
      plnode->connective=ALL;
      plnode->sons=son;
      combine_whens(son);
      break;
    case WHEN:
      if (contains_when(son->sons->next))
	{
	  combine_whens(son);
	}
      if (WHEN==son->connective)  /* melts directly following whens */
	{
	  if (TRU==son->sons->connective)
	    {
	      plnode->sons->next=son->sons->next;
	      free(son->sons);
	      free(son);
	    }
	  else
	    {
	      new_pl=new_pl_node(AND);
	      new_pl->sons=plnode->sons;
	      new_pl->sons->next=son->sons;
	      new_pl->next=son ->sons->next;
	      free(son);
	      plnode->sons=new_pl;
	      new_pl->sons->next->next=NULL;
	    }
	}
      else
	{