;;;-*- Mode: Lisp; Package: XLE -*-

(in-package :XLE)

#||
/* (c) 1996-2001 by the Xerox Corporation.  All rights reserved */
#ifndef RELATIONS_H
#define RELATIONS_H

#include "values.h"

extern TypedValue null_arg;

/* ------------------------------------------------------------------------ */
/* DU uses Relations to extend the unifier to relations other than          */
/* equality.  For instance, the REL_HAS_ELEMENT relation is used to         */
/* indicate that something has an element.  In particular, when             */
/* assert_relation gets called with rel equal to REL_HAS_ELEMENT and arg1   */
/* an AVPair, then REL_HAS_ELEMENT gets added to arg1's rels in an RVPair   */
/* with arg2 as its value to indicate that arg1 has arg2 as an element.  It */
/* makes a difference which argument REL_HAS_ELEMENT gets added to, since   */
/* deductions on pairs of relations can only occur between relations that   */
/* are added to the same AVPair. If deductions are possible on more than    */
/* one argument, then it may be necessary to have two different relations   */
/* which are correlated (such as REL_SUBSUME and REL_SUBSUME_INV.)          */
/* ------------------------------------------------------------------------ */
||#
;; enum RelID {
(defconstant  +REL_DUMMY+ 0)		;        /* This is a dummy relation with no deductions. */

;;  /* ------------------------------------------------- */
;;  /* Relations related to attribute-value unification. */
;;  /* ------------------------------------------------- */
(defconstant  +REL_EQUALS+ 1)		;       /* This is built into AVPair's equals, but is included */
					; /* here for completeness. */
(defconstant  +REL_COPY+ 2)		;         /* This is built into AVPair's copies, but is included */
					; /* here for completeness. */
(defconstant  +REL_EXISTS+ 3)		;       /* The existence relation. */
(defconstant  +REL_ATTR+ 4)		;         /* dummy relation for printing purposes. */
(defconstant  +REL_ATTR_INV+ 5)		;     /* inverse attribute used for inside-out fu. */
(defconstant  +REL_ATTR_CONTEXT+ 6)	; /* used for queued deductions */
(defconstant  +REL_ATTR_DEFINED+ 7)	; /* used for queued deductions */
(defconstant  +REL_INV_DEFINED+ 8)	;  /* used for (^ FOO) = (! FOO) constriants. */
(defconstant  +REL_UNKNOWN_ATTR+ 9)	; /* used for (^ (! PCASE)) (rename to UKS ?) */
(defconstant  +REL_UNKNOWN_ATTR2+ 10)	;/* used for (^ (! PCASE)) (rename to UKS ?) */
(defconstant  +REL_PHI_INVERSE+ 11)	;  /* used for the phi inverse map */
(defconstant  +REL_CAT+ 12)		;          /* used for the CAT predicate */
(defconstant  +REL_CAT_INVERSE+ 13)	;  /* used for the CAT predicate */
(defconstant  +REL_FID+ 14)		;          /* used for labeling an F-structure with an ID */
(defconstant  +REL_PROLOG_ID+ 15)	;    /* used for recording the Prolog ID of an f-structure */
(defconstant  +REL_COPY_PATH+ 16)	;    /* used to cache copy_path */
(defconstant  +REL_CONCAT+ 17)	;       /* used for concatenating symbols. */

;;  /* ------------------------------------ */
;;  /* Relations related to semantic forms. */
;;  /* ------------------------------------ */
(defconstant  +REL_ARGLIST+ 18)		;      /* used for predicate coherence */
(defconstant  +REL_PUSHED_HEAD+ 19)	;  /* used for pushing uncertainties */
(defconstant  +REL_HAS_HEAD+ 20)	;     /* has an instantiated head (PRED or set id + ELT_PRED) */
(defconstant  +REL_SLASH_HAS_HEAD+ 21)	; /* used for threading uncertainties */
(defconstant  +REL_HAS_PRED2+ 22)	;    /* used for predicate uniqueness. This should precede */
					; /* REL_HAS_PRED+ ) ; since it produces more nogoods.  */
(defconstant  +REL_HAS_PRED+ 23)	;     /* used for predicate completeness */
(defconstant  +REL_SEMFORM+ 24)		;      /* Is the value a SEMFORM? */
(defconstant  +REL_SEMANTIC+ 25)	;     /* used for semantic completeness */

;;  /* -------------------------- */
;;  /* Relations related to sets. */
;;  /* -------------------------- */
(defconstant  +REL_SET+ 26)		;          /* AVPair is a set */
(defconstant  +REL_SET_ID+ 27)		;       /* The id of the set's instantiated symbol */
(defconstant  +REL_HAS_ELEMENT+ 28)	;  /* used for set membership */
(defconstant  +REL_IS_MEMBER_OF+ 29)	; /* used for set membership */
(defconstant  +REL_ELT_PRED+ 30)	;     /* used for early nogoods and head precedence. */
(defconstant  +REL_ELT_ARGLIST+ 31)	;  /* used for predicate coherence. */
(defconstant  +REL_EQUATIVE+ 32)	;     /* use equality instead of subsumption for set
					; distribution (experimental) */
(defconstant  +REL_ORIGINAL+ 33)	 ;     /* stores uncollapsed subsumees for debugging */

;;  /* --------------------------------------------------------- */
;;  /* Relations related to closed sets and closed f-structures. */
;;  /* --------------------------------------------------------- */
(defconstant  +REL_CLOSED_FS+ 34)	;    /* This f-structure cannot get new attributes. */
(defconstant  +REL_CLOSED_SET+ 35)	;   /* used to indicate that a set is closed */
(defconstant  +REL_DISTRIBUTION+ 36)	; /* tests whether a variable is distributed (used for
					; closed sets) */
(defconstant  +REL_DISTRIBUTE_VALUES+ 37)	; 
					; /* A set of values from a closed set that needs to */
					; /* to be distributed across set elements and unified. */ 

;;  /* --------------------------------- */
;;  /* Relations related to subsumption. */
;;  /* --------------------------------- */
(defconstant  +REL_SUBSUME+ 38)		;      /* used for distribution of attributes across sets */
(defconstant  +REL_SUBSUME2+ 39)	;     /* keeps track of interactions between REL_SUBSUMEs */
(defconstant  +REL_SUBSUME_INV+ 40)	;  /* The inverse of REL_SUBSUME */
(defconstant  +REL_SUBSUME_DISCHARGED+ 41) ; /* cancels a lazy subsumption link. */
(defconstant  +REL_SUBSUMPTION_REQUEST+ 42) ;  /* Used for pending subsumptions. */

;;  /* -------------------------------------------- */
;;  /* Relations related to functional uncertainty. */
;;  /* -------------------------------------------- */
(defconstant  +REL_UNCERTAINTY+ 43)	;  /* used for functional uncertainty */
(defconstant  +REL_FILLER+ 44)		;       /* An uncertainty with PRED can fill one slot. */
(defconstant  +REL_FU_PATH+ 45)		;      /* used for keeping track of which path an uncertainty
					; took. */
(defconstant  +REL_FU_ATTR+ 46)		;      /* used for keeping track of whether or not an fu
					; attribute has been defined. */
(defconstant  +REL_FU_ATTR1+ 47)	;      /* used for keeping track of whether or not a singleton
					; fu attribute has been defined. */
(defconstant  +REL_FU_DISCHARGED+ 48)	;/* used for keeping track of which uncertainty arms
					; have been discharged. */
(defconstant  +REL_INSIDE_OUT_FU+ 49)	; /* inside out functional uncertainty */
(defconstant  +REL_INSIDE_OUT_PATH+ 50)	; /* inside out functional uncertainty */
(defconstant  +REL_SUBC_MATCH1+ 51)	;        /* used for sub-c uncertainties */
(defconstant  +REL_SUBC_MATCH2+ 52)	;        /* used for sub-c uncertainties */

;;  /* -------------------------------------- */
;;  /* Relations related to local completion. */
;;  /* -------------------------------------- */
(defconstant  +REL_COMPLETE+ 53)	;     /* This AVPair is declared complete. */
(defconstant  +REL_INCOMPLETE+ 54)	;   /* All the contexts in which the AVPair is incomplete. */

;;  /* ----------------------------------------------- */
;;  /* Relations related to head precedence and scope. */
;;  /* ----------------------------------------------- */
(defconstant  +REL_HEAD_PRECEDES+ 55)	;    /* tests head precedence order */
(defconstant  +REL_HEAD_PRECEDES2+ 56)	;   /* helps test head precedence order */
(defconstant  +REL_IN_SCOPE_OF+ 57)	;    /* asserts scope order */
(defconstant  +REL_OUT_SCOPES+ 58)	;   /* inverse of REL_IN_SCOPE_OF */
(defconstant  +REL_LEFT_SCOPE+ 59)	;   /* elements to the left outscope those to the right */
(defconstant  +REL_LEFT_SCOPE2+ 60)	;  /* helps test REL_LEFT_SCOPE */
(defconstant  +REL_LEFT_SCOPE3+ 61)	;  /* helps test REL_LEFT_SCOPE */
(defconstant  +REL_RIGHT_SCOPE+ 62)	;  /* elements to the right outscope those to the left */
(defconstant  +REL_RIGHT_SCOPE2+ 63)	; /* helps test REL_RIGHT_SCOPE */
(defconstant  +REL_RIGHT_SCOPE3+ 64)	; /* helps test REL_RIGHT_SCOPE */
#||  
;;  /* --------------------------------- */
;;  /* Relations related to restriction. */
;;  /* --------------------------------- */
(defconstant  +REL_RESTRICTED_EQUALS+ ) ; /* Restricted version of equality. */

;;  /* -------------------------------- */
;;  /* Relations related to generation. */
;;  /* -------------------------------- */
(defconstant  +REL_GOAL+ ) ;         /* used as the goal in generation */
(defconstant  +REL_GOAL_SET+ ) ;     /* used as the goal with uncertainties */
(defconstant  +REL_UNC_GOAL+ ) ;     /* used as possible goal in gen for goal prediction */
(defconstant  +REL_SUBSUMED_GOAL+ ) ; /* used for goal prediction */
(defconstant  +REL_PREDLESS_GOAL+ ) ; /* used for storing predless versions */
(defconstant  +REL_HAS_GOAL_ELEMENT+ ) ; /* used for set membership testing in generator */
(defconstant  +REL_IN_SCOPE_OF_GOAL+ ) ; /* helps the generator detect scope conflicts. */
  REL_ADDED_ATTR,       /* Used for grammar debugging. */
  REL_MISSING_ATTR,     /* Used for grammar debugging. */
  REL_MISSING_VALUE,    /* Used for grammar debugging. */

  /* ---------------------------------------------------------- */
  /* Relations related to abstraction over sets (experimental). */
  /* ---------------------------------------------------------- */
(defconstant  +REL_ABSTRACT+ ) ;     /* instead of distributing, we are abstracting. */
(defconstant  +REL_ABSTRACT_ATTRS+ ) ; /* There are attributes in what we are
					; abstracting. */
(defconstant  +REL_ABSTRACT_FU+ ) ;  /* There is a functional uncertainty in what we are
					; abstracting. */
(defconstant  +REL_ABSTRACT_FU_ATTRS+ ) ; /* There are attributes that could be part of a
					; functional uncertainty in what we are
					; abstracting. */
(defconstant  +REL_ABSTRACT_OTHER+ ) ; /* There are other relations in what we are
					; abstracting. */
(defconstant  +REL_MISSING+ ) ;      /* Used for indicating that a relation is missing. */
(defconstant  +REL_ABSTRACTABLE+ ) ; /* This AVPair can be abstracted. */
(defconstant  +REL_EQUALS_ABS+ ) ;   /* The abstraction of REL_EQUALS. */

  /* ------------------------------------------------------- */
  /* Relations related to pushing facts down (experimental). */
  /* ------------------------------------------------------- */
(defconstant  +REL_PUSHER+ ) ;       /* used by push-facts.c. */

  /* ----------------------- */
  /* Relations over numbers. */
  /* ----------------------- */
(defconstant  +REL_LESS_THAN+ ) ;
(defconstant  +REL_GREATER_THAN+ ) ;

  /* -------------------------------------- */
  /* Relations used for transfer induction. */
  /* -------------------------------------- */
  REL_CORR1,
  REL_CORR2,
  REL_VAR_ALIGNMENT,
  REL_TRANSFER,
  REL_PIVOT,
  REL_HEAD_SWITCH,
  /* -------------------------------- */
  /* Relations reserved for the user. */
  /* -------------------------------- */
(defconstant  +REL_USER1+ ) ;        /* reserved for user relations.  Use */
                    /* get_next_rel_user_id to get the next unused */
                    /* relation id. */
(defconstant  +REL_USER2+ ) ;
(defconstant  +REL_USER3+ ) ;
(defconstant  +REL_MAX_ID+ ) ;       /* the maximum number of relations */
};

#define HAS_ELEMENT_TYPE VT_2_TUPLE
/* the data type for REL_HAS_ELEMENT. */

/*------------------------------------------------------------------------- */
/* Each Relation can have an assertion function, a deduction function, and  */
/* a completion function.  Relations are accessed through the 'relation'    */
/* array and installed by install_relations.  See relations.c and           */
/* semantic-forms.c for examples of how relations are implemented.          */
/*------------------------------------------------------------------------- */

typedef struct Relation Relation;

typedef void (*AssertionFN)(Graph *graph, TypedValue arg1, TypedValue arg2,
			   Clause *context, CVProps props);
/* If a relation has an assertion function, then it gets called by */
/* assert_relation whenever the relation is asserted.  Otherwise, */
/* add_relation gets called.  This is a convenient place for adding other */
/* relations that are correlated with this one (such as REL_SUBSUME and */
/* REL_SUBSUMED). */

typedef void (*DeductionFN)(Graph *graph, AVPair *avp, CVPair *values);
/* If a relation has a deduction function, then it gets called by */
/* process_new_facts whenever new facts get added to an AVPair that has */
/* this relation in its rels field.  The 'values' parameter contains the */
/* values in the relation's RVPair.  The deduction function should look in */
/* avp for other relations or attributes that this relation interacts with */
/* and call conjoin_oldnew on the context arrays to determine whether */
/* there are any new deductions.  If you have a deduction that involves */
/* three relations on the same AVPair (e.g. A & B & C --> D), then you */
/* might consider breaking it up into two deductions (e.g. A & B --> AB, AB */
/* & C --> D).  Otherwise, the code to determine when you have a new */
/* deduction may be a little complex. */

typedef void (*AbsDeductionFN)(Graph *graph, AVPair *avp, 
			       AVPair *set, CVPair *values);
/* A deduction function on an abstract relations. */

typedef void (*CompletionFN)(Graph *graph, AVPair *avp, CVPair *values, 
			     Clause *context);
/* If a deduction has a completion function, then it gets called by */
/* complete_avpair.  Otherwise, complete_values gets called.  The 'values' */
/* parameter contains the values in the relation's RVPair.  The 'context' */
/* parameter is the context in which completion should be checked.  It */
/* corresponds to the context left when the equalities have been subtracted */
/* out.  When you detect that a relation is incomplete, then you should */
/* call distribute_incomplete to distribute the incomplete across the */
/* graphs where it is incomplete. */

typedef Clause *(*IsCompletedFN)(Graph *graph, AVPair *avp, RelID rel,
				 TypedValue tv);
/* Determines the contexts in which the given subc constraint is completed
   (e.g. is not incomplete). */

enum RelType {
  InternalRel = 0, /* This relation is internal (the default). */
  DefiningRel,     /* This is a defining relation. It should be included
		      in any output.  */
  ConstrainingRel, /* This is a constraining relation.  It should be
		      included whenever the "constraints" button is
		      enabled.  */
};

struct Relation {
  RelID id;
  AssertionFN assert_func;    /* Called by assert_relation. */
  DeductionFN deduce_func;    /* Called by process_new_facts. */
  AbsDeductionFN deduce_abs_func;    /* Called by process_new_facts. */
  CompletionFN complete_func; /* Called by complete_avpair. */
  IsCompletedFN is_completed_func;
  RelType type;               /* See the definition for RelType. */
  int distributive;           /* Whether this relation is distributed
				 across sets. */
  int multipotent;            /* Whether this relation is not
				 idempotent. */
  int subc;                   /* Whether this relation ever has a
				 SUBC constraint. */
};

extern Relation relation[REL_MAX_ID];

/* -------------------------------------------------------------------------*/
/* The macros below are just for convenience in declaring and defining      */
/* functions.                                                               */
/* -------------------------------------------------------------------------*/

#define ASSERT_REL(rel) \
        void assert_##rel(Graph *graph, TypedValue arg1, TypedValue arg2, \
			  Clause *context, CVProps props)
#define DEDUCE_REL(rel) \
        void deduce_##rel(Graph *graph, AVPair *avp, CVPair *cvp)
#define DEDUCE_ABS_REL(rel) \
        void deduce_abs_##rel(Graph *graph, AVPair *avp, \
			      AVPair *set, CVPair *cvp)
#define COMPLETE_REL(rel) \
        void complete_##rel(Graph *graph, AVPair *avp, CVPair *cvp, \
			  Clause *context)

/* -------------------------------------------------------------------------*/
/* Relations are added to an AVPair by adding an RVPair to the AVPair's     */
/* rels field.  There can only be one RVPair per relation per AVPair, but   */
/* the RVPair can have multiple contexted values that represent different   */
/* relation arguments in different contexts.  NEGATED, SUBC, and LAZY       */
/* relations are all stored under the same RVPair along with ordinary       */
/* relations.  They are distinguished by the props field of their CVPair.   */
/* A particular combination of props and value can only appear once per     */
/* relation per AVPair.  If the same combination was going to be added      */
/* twice, then add_value would disjoin their contexts.  (This is also true  */
/* of AVPair->equals and AVPair->copies.)                             */
/* ------------------------------------------------------------------------ */

struct RVPair {
  RelID rel;			/* relation designator */
  
  CVPair *cvalues;		/* list of its contexted values */

  RVPair *next;                 /* the next relation in AVPair->rels */
};

#ifdef notdef
/* ------------------------------------------------------------------------ */
/* Each data type (except tuples) should have a deduction function and a    */
/* comparison function. The deduction function is of the same type as the   */
/* relation's function.  It works on only one cvpair at a time. The         */
/* comparison function is used to compare types.                            */
/* ------------------------------------------------------------------------ */

typedef int (*CompareValuesFN)(TypedValue value1, TypedValue value2);

extern DeductionFN deduce_value_func[VT_USER_MAX];
extern CompareValuesFN compare_values_func[VT_USER_MAX];
#endif

#endif
||#

:EOF