/* This is a literate program.

Applying Relations and Sets
===========================
There are three ways a relation may be used: it may be applied to an argument to give some results, it may enumerate its members, or pairs of values may be tested to see if they are members of it.  These modes of use are called generate, construct, and filter.  The generate and filter modes are also applicable to any set, and any set operator can  be applied to a relation.  This makes it attractive to place all the rules for handling sets and relations in one section.  This led to some soul searching at the design, but the solution finally adopted has been to state the rules three times, grouping them together for ease of maintenance.  A built-in operation is included in this file if and only if its definition depends on the mode.  This is almost the same as saying that it can appear in an expression to the right of '@', '?' or '!'.  (An exception might be something like 'head(S)', which is not in this file, but which might simplify to a set or relation.)  All other built-ins are defined within the 'simplify' file.

The predicate 'generate(S,X)' is used with S bound to a set, and binds X to each element of the set in turn.  (The order is unspecified.)  The predicate 'construct(X,R,Y)' is used with X bound to an argument and R bound to a set, binding Y in turn to each value that satisfies the relation 'X R Y'.  The predicate 'filter(X,S)' is used with X bound to an element and S bound to a set, succeeding if and only if X is a member of S.

There are two important points to bear in mind in evaluating relations and relational operators.  First, evaluation is lazy: finding the Y values corresponding to a given X should not involve completely expanding R, but only the pairs of R that are applicable to X.  This is the chief means by which a programmer saves storage space, but perhaps at the cost of repeated computation.  Second, evaluation should allow for the three different kinds of relations: generators, constructors, and filters, aiming to allow the weaker forms to be used wherever possible.  For example, to apply 'R1 meet R2' to X, it is enough if R1 is a constructor and R2 is a filter, because, after allowing R1 to construct a value of Y, it is possible simply to test if (X,Y) satisfies R2.  This module incorporates the knowledge of how to evaluate weak relations lazily.

It is best to begin by considering how things work at the bottom level, i.e., considering each term of a relation.

To generate a term, it is merely necessary to simplify it.  There may be several ways.

 */ generate_term(T,X)  :- copy_term(T,T1),simplify(T1,X),legal_member(T1,X). /*

If the result is symbolic, but is not a set or relation, this looks like a programming error.  

 */ legal_member(T,X) :- var(X),!,illegal_member(T,X). /*
 */ legal_member(_,[_]) :- !. /*
 */ legal_member(T,(X,Y)) :- legal_member(T,X),legal_member(T,Y),!. /*
 */ legal_member(_,X) :- grounded(X),!. /*
 */ legal_member(T,X) :- illegal_member(T,X). /*

 */ illegal_member(T,X) :- write('The set element '''),display_exp(X),write(''' generated by '''),
                           display_exp(T),write(''' has no enclosing {..}''s.'),nl,fail. /*

There is a problem in applying a term to an argument, in that the term becomes bound to the argument.  This wouldn't matter if it were not for recursion and composition, which may apply the same term again to a different argument after binding it the first time.  We therefore use copy_term, but we don't want it to succeed all the time, so we only make copies of matching terms.  The program runs faster if we test if the copied term will match before trying copy_term.  The predicate 'no_match' succeeds if its arguments won't match.  Matching isn't unification.  A pattern of {X,Y} should accept {X,X}, but a pattern of {X,X} shouldn't accept {X,Y}.  Using 'numbervars' fixes this.

 */ no_match(Pattern,Arg) :- numbervars(Arg,0,_),Arg=Pattern,!,fail. /*
 */ no_match(_,_) :- true. /*

Where a relation is to be applied to an argument, X is certainly bound.  Y should be unbound.  The 1st case is a constructor with a condition.  Since Y is an expression based on X, B can be evaluated before Y is evaluated, because it can only depend on terms in X.

 */ construct_term(X2,((X1,_):_),_) :- no_match(X1,X2),!,fail. /*
 */ construct_term(X2,((X1,Y1):B1),Z) :- !,copy_term(((X1,Y1):B1),((X2,Y2):B2)),
                                         simplify(B2,B3),B3='True',simplify(Y2,Z),legal_value(X2,((X2,Y2):B2),Z). /*

The second case deals with a generator or an unconditional constructor.

 */ construct_term(X2,(X1,_),_) :- no_match(X1,X2),!,fail. /*
 */ construct_term(X2,(X1,Y1),Z) :- !,copy_term((X1,Y1),(X2,Y2)),simplify(Y2,Z),legal_value(X2,(X2,Y2),Z). /*

If the result is symbolic, but is not a set, this looks like a programming error.  

 */ legal_value(X,R,Y) :- var(Y),!,illegal_value(X,R,Y). /*
 */ legal_value(_,_,[_]) :- !. /*
 */ legal_value(_,R,(X,Y)) :- legal_value(_,R,X),legal_value(_,R,Y),!. /*
 */ legal_value(_,_,Y) :- grounded(Y),!. /*
 */ legal_value(X,R,Y) :- illegal_value(X,R,Y). /*

 */ illegal_value(X,R,Y) :- write('The result '''),display_exp(Y),write(''' of '''),display_exp(R),
                            write(''' applied to '''),display_exp(X),write(''' has no enclosing {..}''s.'),nl,fail. /*

To filter a term, it is necessary to consider four cases.  The first two rules consider a term with a condition.  If the term is a pair, either Y may include new variables, or Y may be an expression in X.  Since a compound expression cannot match a grounded argument, the pattern match is tested first.

 */ filter_term(X2,(X1:_)) :- no_match(X1,X2),!,fail. /*
 */ filter_term(X2,(X1:B1)) :- !,copy_term((X1:B1),(X2:B2)),simplify(B2,B3),B3='True'. /*
 */ filter_term((X2,_),((X1,_):_)) :- no_match(X1,X2),!,fail. /*
 */ filter_term((X2,Z),((X1,Y1):B1)) :- !,copy_term(((X1,Y1):B1),((X2,Y2):B2)),simplify(B2,B3),B3='True',simplify(Y2,Z). /*

If there is no condition, the term can be a constructor or a filter.  Again, the simple pattern match is considered first.

 */ filter_term(X2,X1) :- no_match(X1,X2),!,fail. /*
 */ filter_term(X2,X1) :- !,copy_term(X1,X2). /*
 */ filter_term((X2,_),(X1,_)) :- no_match(X1,X2),!,fail. /*
 */ filter_term((X2,Z),(X1,Y1)) :- !,copy_term((X1,Y1),(X2,Y2)),simplify(Y2,Z). /*

Before considering the realistic uses of sets and relations, we have to exclude the possibility of a set or relation being an unbound variable.  This is a clear case of an error.

 */ generate(N,_) :- var(N),!,write('Can''t generate members of a variable.'),nl,fail. /*

 */ filter(X,N) :- var(N),!,write(''''),display_exp(X),write(''' can''t be a member of a variable.'),nl,fail. /*

 */ construct(X,N,X!N) :- var(N),!,write('Can''t apply a variable to '''),display_exp(X),write('''.'),nl,fail. /*

Another problem is that the programmer might write something like '(R1,R2)!else' instead of 'R1 else R2', so we change this back to 'else(R1,R2)', which is indistinguishable from 'R1 else R2'.

 */ generate(Args!Op,X) :- atom(Op),!,tuple_to_list(Args,L),F=..[Op|L],generate(F,X). /*

 */ filter(X,Args!Op) :- atom(Op),!,tuple_to_list(Args,L),F=..[Op|L],filter(X,F). /*

 */ construct(X,Args!Op,Y) :- atom(Op),!,tuple_to_list(Args,L),F=..[Op|L],construct(X,F,Y). /*

Before considering sets (which are represented as lists in this implementation), it is necessary to exclude the specific pattern for a shift sequence.  We do ranges here too because they look similar.

The notation {M..N} denotes the set of all integers from M to N inclusive.  It is merely a shorthand, but for efficiency, it is defined differently for use as a generator and a filter.  Care has to be taken that when M>N that nothing gets generated.  It cannot be treated as a simple built-in, because its (efficient) use depends on context.

 */ filter(X,{M..N}) :- !,simplify(M,M1),simplify(N,N1),filter_range(M1,N1,X). /*

 */ filter_range(M1,N1,X) :- integer(M1),integer(N1),integer(X),!,X>=M1,X=<N1. /*
 */ filter_range(M1,N1,X) :- inapplicable('{..}',((M1,N1),X)). /*

 */ generate({M..N},Y) :- !,simplify(M,M1),simplify(N,N1),generate_range(M1,N1,Y). /*

 */ generate_range(M1,N1,Y) :- integer(M1),integer(N1),!,range(M1,N1,Y). /*
 */ generate_range(M1,N1,_) :- inapplicable('{..}',(M1,N1)). /*

 */ range(M,N,_) :- M>N,!,fail. /*
 */ range(M,_,M) :- true. /*
 */ range(M,N,Y) :- M1 is M+1,range(M1,N,Y). /*

The notation [M..N] denotes a sequence whose members range from M to N.  Again, it is defined differently in different modes.

 */ filter((X,Y),[M..N]) :- !,simplify(M,M1),simplify(N,N1),!,filter_shifter(M1,N1,X,Y). /*

 */ filter_shifter(M1,N1,X,Y) :- integer(M1),integer(N1),integer(X),integer(Y),!,M1=<X,X=<N1,Y-M1=X-1. /*
 */ filter_shifter(M1,N1,X,Y) :- inapplicable('[..]',((X,Y),(M1,N1))). /*

 */ construct(X,[M..N],Y) :- !,simplify(M,M1),simplify(N,N1),construct_shifter(M1,N1,X,Y). /*

 */ construct_shifter(M1,N1,X,Y) :- integer(M1),integer(N1),integer(X),!,Y is M1+X-1,Y>=M1,Y=<N1. /*
 */ construct_shifter(M1,N1,X,_) :- inapplicable('[..]',((M1,N1),X)). /*

 */ generate([M..N],Y) :- !,simplify(M,M1),simplify(N,N1),!,generate_shifter(M1,N1,Y). /*

 */ generate_shifter(M1,N1,Y) :- integer(M1),integer(N1),!,shifter(M1,N1,1,Y). /*
 */ generate_shifter(M1,N1,_) :- inapplicable('[..]',(M1,N1)). /*

 */ shifter(M,N,_,_) :- M>N,!,fail. /*
 */ shifter(M,_,X,(X,M)) :- true. /*
 */ shifter(M,N,X,Y) :- M1 is M+1,X1 is X+1,shifter(M1,N,X1,Y). /*

Continuing the bottom-up description, we consider a relation that is written as a set of pairs.  In this case, we use 'generate_term', 'filter_term' or 'construct_term' for each pair in the set.  Notice that, as each pattern is recognised, a cut is taken, to prevent the pattern being picked up again by a more general rule later - especially the error handler.
      
 */ generate([],_) :- !,fail. /*
 */ generate([X|_],Z) :- generate_term(X,Z). /*
 */ generate([_|T],Z) :- !,generate(T,Z). /*

 */ filter(_,[]) :- !,fail. /*
 */ filter(X,[Y|_]) :- filter_term(X,Y),!. /*
 */ filter(X,[_|T]) :- filter(X,T),!. /*
 */ filter(_,[_|_]) :- !,fail. /*

 */ construct(_,[],_) :- !,fail. /*
 */ construct(X,[Y|_],Z) :- construct_term(X,Y,Z). /*
 */ construct(X,[_|T],Y) :- !,construct(X,T,Y). /*

Relations as Programs
=====================
The next level enforces the lazy evaluation of relational operators, which are the basic program structures.  This is where the language incorporates some expert knowledge of problem solving.  One of the objectives is to reduce the rank of relations needed to evaluate an expression, e.g., to allow filters instead of insisting on generators everywhere.

The set R1 o R2 comprises all pairs (X,Z) for which there exists a Y such that (X,Y) is in R1 and (Y,Z) is in R2.
                                
 */ generate(R1 o R2,(X,Z)) :- !,generate(R1,(X,Y)),construct(Y,R2,Z). /*

Filtering (R1 o R2) means applying R1 to X to give Y, then checking (Y,Z) is in R2.

 */ filter((X,Z),(R1 o R2)) :- construct(X,R1,Y),filter((Y,Z),R2),!. /*
 */ filter((_,_),(_ o _)) :- !,fail. /*

Applying (R1 o R2) to X is to apply R1 to X then apply R2 to the result(s).

 */ construct(X,(R1 o R2),Z) :- !,construct(X,R1,Y),construct(Y,R2,Z). /*

The domain of a relation (dom R) is the set of arguments it can be applied to.  A problem of context arises with 'dom R', which can be generated as a set, or tested for membership.

 */ generate(dom R,X) :- !,generate(R,(X,_)). /*

 */ filter(X,dom R) :- !,filter((X,_),R),!. /*

The codomain of a relation (codom R) is the set of values it can construct.  Although 'codom R' seems similar to 'dom R', membership can only be tested by generating (X,Y) pairs.

 */ generate(codom R,Y) :- !,generate(R,(_,Y)). /*

 */ filter(Y,codom R) :- !,generate(R,(_,Y1)),Y=Y1,!. /*

Applying R^* to X is equivalent to applying R to X any number of times. 

 */ construct(X,_^*,X) :- true. /*
 */ construct(X,R^*,Z) :- !,construct(X,R,Y),construct(Y,R^*,Z). /*

Filtering has to work in the same way, but can stop at the first solution.

 */ filter((X,Y),R^*)   :- construct(X,R^*,Y),!. /*
 */ filter((_,_),_^*)   :- !,fail. /*

Generating is harder, because no X value is given to start the process.  The base values are chosen from the domain of the relation.  If X is base value, Y can be constructed from X, and Z can be constructed from Y, then (Y,Z) is in the closure of R.

 */ generate(R^*,(Y,Z)) :- generate(R,(X,_)),construct(X,R^*,Y),construct(Y,R^*,Z). /*
 */ generate(_^*,(_,_)) :- fail,!. /*

The notation R^+ is similar to R^*, but always applies R at least once.

 */ construct(X,R^+,Z)  :- !,construct(X,R,Y),construct(Y,R^*,Z). /*

 */ filter((X,Y),R^+)   :- !,construct(X,R^+,Y),!. /*

 */ generate(R^+,(Y,Z)) :- generate(R,(X,_)),construct(X,R^*,Y),construct(Y,R^+,Z). /*
 */ generate(_^+,(_,_)) :- fail,!. /*

The notation R^^ (the limit of R) is similar to R^*, but always applies R until it can't be applied further.  For notes on how 'new_counter', 'increment_counter', 'read_counter' and 'trash_counter' work, see the explanation of the 'else' operator.

 */ construct(X,R^^,Z) :- !,new_counter(C),construct_limit(C,X,R,Z),trash_counter(C). /*

 */ construct_limit(C,X,R,Z) :- construct(X,R,Y),increment_counter(C),construct(Y,R^^,Z),!. /*
 */ construct_limit(C,X,_,Z) :- read_counter(C,N),!,N=0,Z=X. /*

 */ filter((X,Y),R^^) :- !,construct(X,R^^,Y),!. /*

 */ generate(R^^,(Y,Z)) :- generate(R,(X,_)),construct(X,R^*,Y),construct(Y,R^^,Z). /*
 */ generate(_^^,(_,_)) :- fail,!. /*

The notation R^+N means R applied N times.  R^+0 is the identity function on the domain of R.

 */ construct(X,R^+N,Z) :- !,simplify(N,N1),construct_paths(X,R,N1,Z). /*

 */ construct_paths(X,R,0,X) :- !,filter(X,dom R). /*
 */ construct_paths(X,R,1,Z) :- !,construct(X,R,Z). /*
 */ construct_paths(X,R,N,Z) :- integer(N),N>0,!,construct(X,R,Y),N1 is N-1,construct_paths(Y,R,N1,Z). /*
 */ construct_paths(_,R,N,_) :- inapplicable(^+,(R,N)). /*

Filtering has to work in the same way, but can stop at the first solution.

 */ filter(X,R^+N) :- !,simplify(N,N1),filter_paths(X,R^+N1). /*

 */ filter_paths((X,X),R,0)   :- !,filter(X,dom R). /*
 */ filter_paths((X,Y),R,1)   :- !,filter((X,Y),R). /*
 */ filter_paths((X,Z),R,N)   :- integer(N),N>0,!,construct_paths(X,R,N,Z),!. /*
 */ filter_paths(_,R,N) :- inapplicable(^+,(R,N)). /*

Generating is a little harder, because no X value is given to start the process.

 */ generate(R^+N,Y) :- !,simplify(N,N1),generate_paths(R,N1,Y). /*

 */ generate_paths(R,0,(X,X)) :- !,generate(R,(X,_)). /*
 */ generate_paths(R,1,(X,Y)) :- !,generate(R,(X,Y)). /*
 */ generate_paths(R,N,(X,Y)) :- integer(N),N>0,!,generate(R,(X,_)),construct_paths(X,R,N,Y). /*
 */ generate_paths(R,N,_) :- inapplicable(^+,(R,N)). /*

The notation R^-N means the inverse of R applied N times, i.e, if X R^+N Y, then Y R^-N X.  R^-0 is the identity function on the codomain of R.  The ^- operator only works on generators.

 */ construct(X,R^-N,Y) :- !,simplify(N,N1),construct_inverse(X,R,N1,Y). /*

 */ construct_inverse(X,R,0,X) :- !,filter(X,codom R). /*
 */ construct_inverse(X,R,1,Y) :- !,generate(R,(Y,X)). /*
 */ construct_inverse(X,R,N,Z) :- integer(N),N>0,!,generate(R,(Y,X)),N1 is N-1,construct_inverse(Y,R,N1,Z). /*
 */ construct_inverse(_,R,N,_) :- inapplicable(^-,(R,N)). /*

Filtering has to work in the same way, but can stop at the first solution.

 */ filter((X,Y),R^-N)   :- !,simplify(N,N1),construct_inverse(X,R,N1,Y),!. /*

Generating is a little harder, because no X value is given to start the process.

 */ generate(R^-N,Z) :- !,simplify(N,N1),generate_inverse(R,N1,Z). /*

 */ generate_inverse(R,0,(X,X)) :- !,generate(R,(X,_)). /*
 */ generate_inverse(R,1,(X,Y)) :- !,generate(R,(Y,X)). /*
 */ generate_inverse(R,N,(X,Y)) :- integer(N),N>0,!,generate(R,(X,_)),construct_inverse(X,R,N,Y). /*
 */ generate_inverse(R,N,_) :- inapplicable(^-,(R,N)). /*

The notation S<- denotes the reverse of sequence S.

 */ construct(X,S<-,Z) :- !,simplify(S,S1),construct_reverse(X,S1,Z). /*

 */ construct_reverse(X,S,Z) :- length(S,L),!,Y is L+1-X,construct(Y,S,Z). /*
 */ construct_reverse(_,S,_) :- inapplicable(<-,S). /*

 */ filter(X,S<-) :- !,simplify(S,S1),filter_reverse(X,S1). /*

 */ filter_reverse((X,Z),S) :- length(S,L),!,Y is L+1-X,filter((Y,Z),S). /*
 */ filter_reverse(_,S) :- inapplicable(<-,S). /*

 */ generate(S<-,Z) :- !,simplify(S,S1),generate_reverse(S1,Z). /*

 */ generate_reverse(S,(Y,Z)) :- length(S,L),!,generate(S,(X,Z)),Y is L+1-X. /*
 */ generate_reverse(S,_) :- inapplicable(<-,S). /*

An element is in the 'join' of two sets if it is a member of either of them.  The results of applying (R1 join R2) to X are the union of the results of applying R1 to X and of applying R2 to X.  Both relations must be at least constructors.  Similar rules find the members of the join of two sets, when both sets must be generators.  When membership of a join is tested, both sets may be filters.

 */ generate(S1 join _,X) :- generate(S1,X). /*
 */ generate(_ join S2,X) :- !,generate(S2,X). /*

 */ filter(X,(S1 join _)) :- filter(X,S1). /*
 */ filter(X,(_ join S2)) :- !,filter(X,S2). /*

 */ construct(X,(R1 join _),Y) :- construct(X,R1,Y). /*
 */ construct(X,(_ join R2),Y) :- !,construct(X,R2,Y). /*

An element is in the 'meet' of two sets if it is an element of both.  The results of applying (R1 meet R2) to X are the intersection of the results of applying R1 to X and of applying R2 to X.  The first relation must be a generator or constructor, and the second may be a filter.  Similar rules find the members of the meet of sets.  The first set must be a generator, but the second may be a filter, because Y is already bound.  When membership of a meet is tested, both sets may be filters.

 */ construct(X,(R1 meet R2),Y) :- construct(X,R1,Y),filter((X,Y),R2). /*
 */ construct(_,_ meet _,_) :- !,fail. /*

 */ generate(S1 meet S2,X) :- generate(S1,X),filter(X,S2). /*
 */ generate(_ meet _,_) :- !,fail. /*

 */ filter(X,S1 meet S2) :- filter(X,S1),filter(X,S2),!. /*
 */ filter(_,_ meet _,_) :- !,fail. /*

(R1 omit R2) to X are the results of applying R1 to X except those that also result from applying R2 to X.  The first relation must be a generator or constructor, and the second may be a filter.  The same rules also find the members of the difference of two sets.  The first set must be a generator, but the second may be a filter, because Y is already bound.  When membership of a difference is tested, both sets may be filters.

 */ generate(S1 omit S2,X) :- generate(S1,X),filter_out(X,S2). /*
 */ generate(_ omit _,_) :- !,fail. /*

 */ filter(X,S1 omit S2) :- filter(X,S1),filter_out(X,S2),!. /*
 */ filter(_,_ omit _) :- !,fail. /*

 */ construct(X,(R1 omit R2),Y) :- !,construct(X,R1,Y),filter_out((X,Y),R2). /*

An element is in 'S1 omit S2' if it is a member of S1 but not a member of S2.  The results of applying The predicate 'filter_out(X,S)' fails if set S contains element X, and succeeds if it doesn't. 

 */ filter_out(X,S) :- filter(X,S),!,fail. /*
 */ filter_out(_,_) :- true. /*
        
The expression (R1 else R2) denotes R1 extended by R2, i.e., if R1 is applicable, the results are determined by R1, but when R1 is inapplicable, the results are determined by R2.  Like composition, 'else' needs special treatment for sets, otherwise the definition would be non-standard.

 */ generate((R1 else R2),Z) :- !,new_counter(C),generate_else(C,R1,R2,Z),trash_counter(C). /*

 */ generate_else(C,R1,_,(X,Y)) :- generate(R1,(X,Y)),increment_counter(C). /*
 */ generate_else(C,_,R2,(X,Y)) :- read_counter(C,N),!,N=0,generate(R2,(X,Y)). /*

 */ filter(X,(R1 else R2)) :- !,new_counter(C),filter_else(C,X,R1,R2),trash_counter(C). /*

 */ filter_else(C,(X,Y),R1,_) :- filter((X,Y),R1),increment_counter(C). /*
 */ filter_else(C,(X,Y),_,R2) :- read_counter(C,N),!,N=0,filter((X,Y),R2). /*

 */ construct(X,(R1 else R2),Y) :- !,new_counter(C),construct_else(C,X,R1,R2,Y),trash_counter(C). /*

 */ construct_else(C,X,R1,_,Y) :- construct(X,R1,Y),increment_counter(C). /*
 */ construct_else(C,X,_,R2,Y) :- read_counter(C,N),!,N=0,construct(X,R2,Y). /*

The following four predicates keep track of how many times R1 has been applied in a fact of the form 'counter(C,N)'.  Because R1 might contain nested 'else' operators, the 'counter' fact has to be identified by a unique number.  The 'new_counter(C)' predicate asserts 'counter(C,0)' where C is an index unique to the occurrence of the expression.  The 'increment_counter(C)' predicate adds 1 to counter(C) each time R1 succeeds.  After trying to apply R1, the counter is read by 'read_counter' and if it is still zero, R1 wasn't applicable, so R2 is applied.  After both R1 and R2 have been tried, the counter is trashed.

 */ new_counter(C) :- retract(unique(N)),!,C is N+1,assert(unique(C)),assert(counter(C,0)),!. /*
 */ new_counter(1) :- assert(unique(1)),assert(counter(1,0)),!. /*

 */ increment_counter(C) :- retract(counter(C,N)),N1 is N+1,assert(counter(C,N1)),!. /*

 */ read_counter(C,N) :- clause(counter(C,N),true). /*

 */ trash_counter(C) :- retract(counter(C,_)). /*

The expression 'R1 but R2' denotes R1 'over-ridden' by R2.  It is a syntactical variant of (R2 else R1).

 */ generate((R1 but R2),X) :- !,generate((R2 else R1),X). /*
 */ construct(X,(R1 but R2),Y) :- !,construct(X,(R2 else R1),Y). /*
 */ filter(X,(R1 but R2)) :- !,filter(X,(R2 else R1)). /*

There are four 'restriction' operators: 'S <? R' means R restricted to the input set S, 'R ?> S' means R restricted to the output set S, 'S <\? R' means R restricted to exclude the input set S, and 'R \?> S' means R restricted to exclude the output set S.  These are merely shorthands.

 */ generate(S <? R,(X,Y)) :- !,generate(S,X),construct(X,R,Y). /*
 */ generate(S <\? R,(X,Y)) :- !,generate(R,(X,Y)),filter_out(X,S). /*
 */ generate(R ?> S,(X,Y)) :- !,generate(R,(X,Y)),filter(Y,S). /*
 */ generate(R \?> S,(X,Y)) :- !,generate(R,(X,Y)),filter_out(Y,S). /*

 */ construct(X,S <? R,Y) :- !,filter(X,S),construct(X,R,Y). /*
 */ construct(X,S <\? R,Y) :- !,filter_out(X,S),construct(X,R,Y). /*
 */ construct(X,R ?> S,Y) :- !,construct(X,R,Y),filter(Y,S). /*
 */ construct(X,R \?> S,Y) :- !,construct(X,R,Y),filter_out(Y,S). /*

 */ filter(X,S <? R,Y) :- !,filter(X,S),filter(X,R,Y). /*
 */ filter(X,S <\? R,Y) :- !,filter_out(X,S),filter(X,R,Y). /*
 */ filter(X,R ?> S,Y) :- !,filter(X,R,Y),filter(Y,S). /*
 */ filter(X,R \?> S,Y) :- !,filter(X,R,Y),filter_out(Y,S). /*

The expression 'S x T' denotes the cartesian product of sets S and T, the relation formed from every possible pairing (X,Y), where X is a member of S and Y is a member of T.

 */ generate((S x T),(X,Y)) :- !,generate(S,X),generate(T,Y). /*

 */ construct(X,(S x T),Y) :- !,filter(X,S),!,generate(T,Y). /*

 */ filter((X,Y),(S x T)) :- !,filter(X,S),!,filter(Y,T),!. /*
 */ filter(_,(_ x _)) :- !,fail. /*

The expression 'sets_of S' denotes all sets with members drawn from set S.

 */ filter(T,(sets_of S)) :- generate(T,X),filter_out(X,S),!,fail. /*
 */ filter(_,(sets_of _)) :- !. /*

 */ generate(sets_of S,T) :- !,findall(X,generate(S,X),L),sort(L,L1),generate_subsets(L1,T). /*

 */ generate_subsets([],[]) :- true. /*
 */ generate_subsets([H|T],[H|T1]) :- generate_subsets(T,T1). /*
 */ generate_subsets([_|T],T1) :- generate_subsets(T,T1). /*

A sequence is a function from the integers 1-N to a series of terms.  The expression 'seqs_of S' denotes all sequences whose terms are drawn from set S.

 */ filter(L,(seqs_of S)) :- !,is_seq_of(L,1,S). /*

The predicate 'is_seq_of(L,N,S)' succeeds if L is the tail of a sequence of members of S, starting from the Nth term.

 */ is_seq_of([],_,_). /*
 */ is_seq_of([(X,Y)|T],N,S) :- !,integer(X),X=N,filter(Y,S),N1 is N+1,is_seq_of(T,N1,S). /*

Sequences of S can be generated, provided there is a generator for S.

 */ generate(seqs_of S, Y) :- !,generate_seqs(S,[],Y,1,_). /*

 */ generate_seqs(_,L,L,N,N) :- true. /*
 */ generate_seqs(S,L,L2,N,N2) :- generate_seqs(S,L,L1,N,N1),generate(S,X),sort([(N1,X)|L1],L2),N2 is N1+1. /*

The concatenation of two sequences may be applied to an argument lazily, in the sense that if the argument selects a term of the first sequence, the second need not be examined.

 */ generate(R1&&R2,Z) :- !,simplify(R1,S1),simplify(R2,S2),length(S1,N),generate_concat(N,S1,S2,Z). /*

 */ generate_concat(_,R1,_,(X,Y)) :- generate(R1,(X,Y)). /*
 */ generate_concat(N,_,R2,(X,Y)) :- generate(R2,(X1,Y)),X is X1+N. /*

 */ filter((X,Y),R1&&_) :- filter((X,Y),R1),!. /*
 */ filter((X,Y),R1&&R2) :- !,simplify(#,R1,N),X1 is X-N,filter((X1,Y),R2),!. /*

 */ construct(X,R1&&_,Y) :- construct(X,R1,Y),!. /*
 */ construct(X,R1&&R2,Y) :- !,simplify(#,R1,N),X1 is X-N,!,construct(X1,R2,Y). /*

Given sequences R and S, the expression '(R,S)\\(Op)' (parallel application) constructs a new sequence by applying 'op' to each pair of corresponding terms from R and S.  This also works with relations other than sequences, operating on all pairs of values with a common argument.  If an argument maps to multiple values, every combination of pairs from R and S is used.

 */ generate((R,S)\\Op,(X,Y)) :- !,generate(R,(X,Y1)),construct(X,S,Y2),construct((Y1,Y2),Op,Y). /*

 */ construct(X,(R,S)\\Op,Y) :- !,construct(X,R,Y1),construct(X,S,Y2),construct((Y1,Y2),Op,Y). /*

 */ filter((X,Y),(R,S)\\Op) :- !,construct(X,R,Y1),construct(X,S,Y2),construct((Y1,Y2),Op,Y). /*

Type Checking
=============
Types can be checked dynamically to limit the applicability of relations to their intended arguments.  Types are all specified as filters.  Apart from the types specified directly, composite types can be built up using operators, e.g., sets_of(integer x character) defines the set of all relations from integers to characters.

Integer, natural and positive numbers have obvious definitions:

 */ filter(X,integers) :- !,integer(X). /*
 */ generate(integers,X) :- !,generate_integers(0,X). /*

 */ generate_integers(N,N) :- true. /*
 */ generate_integers(N,X) :- N>0,!,N1 is -N,generate_integers(N1,X). /*
 */ generate_integers(N,X) :- N1 is 1-N,generate_integers(N1,X). /*

 */ filter(X,naturals) :- !,integer(X),X>=0. /*

 */ generate(naturals,X) :- !,generate_naturals(0,X). /*

 */ generate_naturals(N,N) :- true. /*
 */ generate_naturals(N,X) :- N1 is N+1,generate_naturals(N1,X). /*

 */ filter(X,positives) :- !,integer(X),X>0. /*

 */ generate(positives,X) :- !,generate_naturals(1,X). /*

What counts as a character is somewhat debatable, and depends on the implementation:

 */ filter(X,characters) :- !,character(X). /*

 */ character(X) :- integer(X),X>=0,X=<255. /*

 */ generate(characters,X) :- !,range(0,255,X). /*

Atoms that begin with capital letters stand for themselves, and are called literals.

 */ filter(X,literals) :- !,literal(X). /*

The set of atoms is the same as in Prolog.

 */ filter(X,atoms) :- !,atom(X). /*

The set of compounds is the same as in Prolog.

 */ filter(X,compounds) :- !,compound(X). /*

The booleans are 'True' and 'False'.

 */ filter(X,booleans) :- !,boolean(X). /*
 */ generate(booleans,X) :- !,boolean(X). /*

'Any' is just a place holder, so that, e.g., 'any x any' can be used to define any pair.

 */ filter(_,any) :- !. /*

Sets are usually represented as lists:

 */ filter({_.._},sets) :- !. /* 
 */ filter([],sets) :- !. /* 
 */ filter([_],sets) :- !. /* 

A relation is a set of pairs. It could be described as 'sets_of(any x any)'.

 */ filter(X,relations) :- !,is_rel(X). /* 

 */ is_rel([]). /*
 */ is_rel([(_,_)|T]) :- !,is_rel(T). /*

A sequence is identified by consisting of a list of pairs.  The first members of the pairs are the integers 1,2,3, and so on.  The predicate 'is_seq(L,N)' succeeds if L is the tail of a sequence, starting from the Nth term.

 */ filter([_.._],sequences) :- !. /*
 */ filter(X,sequences) :- !,is_seq(X,1). /*

 */ is_seq([],_). /*
 */ is_seq([(H,_)|T],N) :- !,integer(H),H=N,N1 is N+1,is_seq(T,N1). /*

A 'string' is a sequence whose values are characters:

 */ filter(X,strings) :- !,is_str(X,1). /* 

 */ is_str([],_). /*
 */ is_str([(H,C)|T],N) :- !,integer(H),character(C),H=N,N1 is N+1,is_str(T,N1). /*

More complex structures can be tested using 'seqs_of', 'sets_of', 'x', and pattern matching.

Finally, it should be possible to test if an argument contains variables, as it might if it represents a constructor or filter.  The set 'grounded' consists of all variable-free structures, and the set 'symbolic' consists of all structures containing at least one variable.

 */ filter(X,grounded) :- !,grounded(X). /*
 */ filter(X,symbolic) :- !,symbolic(X). /*

Some Problem Cases
==================
If the relation is a literal it is a clear case of an error.

 */ generate(N,_) :- literal(N),!,generate_error(N). /*

 */ filter(_,N) :- literal(N),!,filter_error(N). /*

 */ construct(X,N,_) :- literal(N),!,construct_error(X,N). /*

The same problem arises if the supposed relation is an integer.

 */ generate(N,_) :- integer(N),!,generate_error(N). /*

 */ filter(_,N) :- integer(N),!,filter_error(N). /*

 */ construct(X,N,_) :- integer(N),!,construct_error(X,N). /*

Of course, any relation can be replaced by a name, which must then be looked up and replaced by its definition(s).  Multiple definitions are all applied.  If no definition exists, the relation is ignored.  There is no cut in these rules, because the same pattern may also match a built-in operator.  Note that in the present implementation there is no trap for undefined names, which simply fail.

 */ generate(N,Z) :- look_up(N,Def),generate(Def,Z). /*

 */ filter(X,N) :- look_up(N,Def),filter(X,Def). /*

The second operand of 'construct' might be a built-in operator, e.g., the programmer may write '(X,Y)!(+)', which eventually got turned into 'construct((X,Y),+,Z)'.  There are no 'construct' rules with built-in operators as their second arguments; these cases are handled by 'built_in'.

 */ construct(Args,Op,Z) :- look_up(Op,Def),construct(Args,Def,Z). /*
 */ construct(Args,Op,Z) :- predefined(Op),built_in(Op,Args,Z). /*

Finally, we allow that the relation or set has none of the above forms: i.e., it is an expression.  So we evaluate the expression and apply the result.  Unfortunately, if the expression is already fully evaluated, no progress will be made. So a loop must be tested for.

 */ generate(Exp,X) :- compound(Exp),!,simplify(Exp,S),generate_loop(Exp,S,X). /*

 */ generate_loop(S,S,_) :- !,generate_error(S). /*
 */ generate_loop(_,S,X) :- generate(S,X). /*

 */ filter(X,Exp) :- compound(Exp),!,simplify(Exp,S),filter_loop(X,Exp,S). /*

 */ filter_loop(_,S,S) :- !,filter_error(S). /*
 */ filter_loop(X,_,S) :- filter(X,S). /*

 */ construct(X,Exp,Y) :- compound(Exp),!,simplify(Exp,R),construct_loop(X,Exp,R,Y). /*
 
 */ construct_loop(X,R,R,_) :- !,construct_error(X,R). /*
 */ construct_loop(X,_,R,Y) :- construct(X,R,Y). /*

 */ generate_error(N) :- write('Can''t generate members of '''),write(N),write('''.  It isn''t a set.'),nl,fail. /*

 */ filter_error(N) :- write('Can''t test membership of '''),write(N), write('''.  It isn''t a set.'),nl,fail. /*

 */ construct_error(X,R) :- write('Can''t apply '''),write(R),write(''' to '''),display_exp(X),
                            write('''.  It isn''t a relation.'),nl,fail. /*

Safety Net
==========
In theory, the only times control should reach this point are when a named set or relation is used.  The name look-up can't include a cut in case the name is also a built-in operator.  Built-in operators are always atoms.  Therefore, if control reaches here with a non-atom, there has been an error.  The only non-atoms are integers, variables and compounds, all of which have been excluded.  Assuming the treatment of variables and integers are reliable enough, the following rules defend against errors in the compound definitions above:

 */ generate(S,_) :- compound(S),!,write('Bug: '),write(S),write(' wasn''t caught by ''generate''.'),nl,fail. /*

 */ filter(_,S) :- compound(S),!,write('Bug: '),write(S),write(' wasn''t caught by ''filter''.'),nl,fail. /*

 */ construct(_,R,_) :- compound(R),!,write('Bug: '),write(R),write(' wasn''t caught by ''construct''.'),nl,fail. /*

End of literate program. */
