/* This is a literate program.

Built-in Operators
==================
Some built-in operators evaluate their operands lazily, so they are dealt with on an ad hoc basis.  Note that, because all the user-defined relations have already been dealt with, we can safely use 'cut' once an operator has been recognised.  Presumably, this will speed things up a bit.

'X!R' denotes the application of relation 'R' to argument 'X'.  This is not just a syntactic variant of R(X), because R may be a complex expression.  (In theory, we should even be able to cope with 'X!(!)'.) 

 */ built_in(!,(X,R),Y) :- atom(R),!,tuple_to_list(X,L),simplify_compound(L,R,Y). /*
 */ built_in(!,(X,R),Z) :- !,simplify(X,Y),construct(Y,R,Z). /*

Functional application is like relational application, except that exactly one result is used.

 */ built_in(~,(X,R),Y) :- atom(R),!,tuple_to_list(X,L),simplify_compound(L,R,Y),!. /*
 */ built_in(~,(X,R),Z) :- !,simplify(X,Y),construct(Y,R,Z),!. /*

Generating the members of a set is done by 'generate'. 

 */ built_in(@,S,Y) :- !,generate(S,Y). /*

Generating a single member is similar. 

 */ built_in(i,S,Y) :- !,generate(S,Y),!. /*

Membership
==========
A membership test calls a set as a filter.  If the filter succeeds, the result is 'True'.  Otherwise the result is 'False'.  To evaluate sets lazily, in no case is the right operand simplified.

 */ built_in((?),(X,S),B) :- !,simplify(X,Y),test_filter(Y,S,B1),B=B1. /*

 */ built_in(\?,(X,S),B) :- !,simplify(X,Y),test_filter(Y,S,B1),complement(B1,B). /*

The 'test_filter' predicate is used to stop the 'cut' limiting the number of solutions to 'built_in'.

 */ test_filter(X,S,B) :- filter(X,S),!,B='True'. /*
 */ test_filter(_,_,'False') :- true. /*

Reduction Operators
===================
The expression 'S>>->Op' (set reduce) combines all values of S using operator Op.

 */ built_in(>>->,(S,Op),Z) :- !,findall(Y,simplify(S,Y),L),set_reduce(L,Op,Z). /*

 */ set_reduce([],_,_) :- !,fail. /*
 */ set_reduce([H|[]],_,Z) :- !,simplify(H,Z). /*
 */ set_reduce([H|T],Op,Z) :- set_reduce(T,Op,Y),construct((H,Y),Op,Z). /*

The expression 'E>>->' (set of) finds the set of values generated by E.

 */ built_in(>>->,E,Z) :- !,findall(Y,simplify(E,Y),L),sort(L,Z). /*

The expression 'S>>=>Op' (sequence reduce) operator combines all terms of a sequence S in left to right order, using operator Op.

 */ built_in(>>=>,(S,Op),Z) :- !,findall(Y,simplify(S,Y),L),sort(L,L1),seq_reduce(L1,Op,Z). /*

 */ seq_reduce([],_,_) :- !,fail. /*
 */ seq_reduce([(_,H)|[]],_,Z) :- !,simplify(H,Z). /*
 */ seq_reduce([(_,H)|T],Op,Z) :- seq_reduce(T,Op,Y),construct((H,Y),Op,Z). /*

The expression 'S image R' yields the image of S in R, i.e., the set of all Y such that there exists an X that is a member of S, and X R Y is true.

 */ built_in(image,(S,R),Z) :- simplify(S,S1),!,findall(Y,in_image(S1,R,Y),L),sort(L,Z). /*

 */ in_image(S,R,Y) :- generate(S,X),construct(X,R,Y). /*

The expression 'values Exp' is the set of values of Exp.

 */ built_in(values,X,Z) :- !,findall(Y,simplify(X,Y),L),sort(L,Z). /*


Arithmetic
==========
The following definitions make Prolog arithmetic possible.

 */ built_in(^,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),power(X1,Y1,Z). /*

 */ power(_,0,1) :- !. /*
 */ power(X,Y,Z) :- integer(X),integer(Y),Y>0,Y1 is Y-1,power(X,Y1,Z1),Z is X*Z1,!. /*
 */ power(X,Y,_) :- inapplicable(^,(X,Y)). /*

 */ built_in(mod,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),modulo(X1,Y1,Z). /*

 */ modulo(X,Y,Z) :- integer(X),integer(Y),Y>0,Z is X mod Y,!. /*
 */ modulo(X,Y,_) :- inapplicable(mod,(X,Y)). /*

 */ built_in(*,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),times(X1,Y1,Z). /*

 */ times(X,Y,Z) :- integer(X),integer(Y),Z is X*Y,!. /*
 */ times(X,Y,_) :- inapplicable(*,(X,Y)). /*

 */ built_in(/,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),divide(X1,Y1,Z). /*

 */ divide(X,Y,Z) :- integer(X),integer(Y),!,Y\=0,Z is X/Y. /*
 */ divide(X,Y,_) :- inapplicable(/,(X,Y)). /*

 */ built_in(<<,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),left_shift(X1,Y1,Z). /*

 */ left_shift(X,Y,Z) :- integer(X),integer(Y),Z is X<<Y,!. /*
 */ left_shift(X,Y,_) :- inapplicable(<<,(X,Y)). /*

 */ built_in(>>,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),right_shift(X1,Y1,Z). /*

 */ right_shift(X,Y,Z) :- integer(X),integer(Y),Z is X>>Y,!. /*
 */ right_shift(X,Y,_) :- inapplicable(>>,(X,Y)). /*

 */ built_in(+,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),add(X1,Y1,Z). /*

 */ add(X,Y,Z) :- integer(X),integer(Y),Z is X+Y,!. /*
 */ add(X,Y,_) :- inapplicable(+,(X,Y)). /*

 */ built_in(+,X,Z) :- !,simplify(X,X1),plus(X1,Z). /*
 */ plus(X,X) :- integer(X),!. /*
 */ plus(X,_) :- inapplicable(+,X). /*

 */ built_in(-,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),subtract(X1,Y1,Z). /*

 */ subtract(X,Y,Z) :- integer(X),integer(Y),Z is X-Y,!. /*
 */ subtract(X,Y,_) :- inapplicable(-,(X,Y)). /*

 */ built_in(-,X,Z) :- !,simplify(X,X1),minus(X1,Z). /*

 */ minus(X,Z) :- integer(X),Z is - X,!. /*
 */ minus(X,_) :- inapplicable(-,X). /*

 */ built_in(/\,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),bitwise_and(X1,Y1,Z). /*

 */ bitwise_and(X,Y,Z) :- integer(X),integer(Y),Z is X/\Y,!. /*
 */ bitwise_and(X,Y,_) :- inapplicable(/\,(X,Y)). /*

 */ built_in(\/,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),bitwise_or(X1,Y1,Z). /*
 */ bitwise_or(X,Y,Z) :- integer(X),integer(Y),Z is X\/Y,!. /*
 */ bitwise_or(X,Y,_) :- inapplicable(\/,(X,Y)). /*

 */ built_in(max,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),max(X1,Y1,Z). /*

 */ max(X,Y,X) :- integer(X),integer(Y),X>=Y,!. /*
 */ max(X,Y,Y) :- integer(X),integer(Y). /*
 */ max(X,Y,_) :- inapplicable(max,(X,Y)). /*

 */ built_in(min,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),min(X1,Y1,Z). /*

 */ min(X,Y,X) :- integer(X),integer(Y),X=<Y,!. /*
 */ min(X,Y,Y) :- integer(X),integer(Y). /*
 */ min(X,Y,_) :- inapplicable(min,(X,Y)). /*

 */ built_in(>,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),compare_int(>,X1,Y1,Z). /*
 */ built_in(>=,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),compare_int(>=,X1,Y1,Z). /*
 */ built_in(<,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),compare_int(<,X1,Y1,Z). /*
 */ built_in(=<,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),compare_int(=<,X1,Y1,Z). /*
 */ built_in(=,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),compare_int(=,X1,Y1,Z). /*
 */ built_in(\=,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),compare_int(\=,X1,Y1,Z). /*

The 'test' predicate returns 'True' if the specified predicate succeeds, and 'False' otherwise.

 */ compare_int(R,X,Y,Z) :- integer(X),integer(Y),!,F=..[R,X,Y],test(F,Z),!. /*
 */ compare_int(R,X,Y,Z) :- test_cmpd(R,X,Y,Z). /*

 */ test(Bool,'True') :- call(Bool),!. /*
 */ test(_,'False'). /*

The function 'random(M,N)' returns a random integer in the range M..N.

 */ built_in(random,(M,N),Z) :- !,simplify(M,M1),simplify(N,N1),integer(M1),integer(N1),M1<N1,
                                R is N1-M1+1,'system$random'(R,Y),Z is Y+M1. /*

The 'unary_prec' and 'binary_prec' operators have to be treated specially, as their operands are operators that mustn't be looked up and evaluated in the regular way.

The 'unary_prec' function returns the precedence of a unary operator, or 0 if the operator is undefined.

 */ built_in((unary_prec),Op,P) :- current_op(P,M,Op),M=fx,!. /*
 */ built_in((unary_prec),Op,P) :- current_op(P,M,Op),M=fy,!. /*
 */ built_in((unary_prec),Op,P) :- current_op(P,M,Op),M=yf,!. /*
 */ built_in((unary_prec),Op,P) :- current_op(P,M,Op),M=xf,!. /*
 */ built_in((unary_prec),_,_) :- look_up((unary_prec),_),!,fail. /*
 */ built_in((unary_prec),Op,0) :- write(''''),write(Op),write(''' is not a current unary operator.'), nl,!. /*

The 'binary_prec' function returns the precedence of a binary operator, or 0 if the operator is undefined.

 */ built_in((binary_prec),Op,P) :- current_op(P,M,Op),M=xfx,!. /*
 */ built_in((binary_prec),Op,P) :- current_op(P,M,Op),M=xfy,!. /*
 */ built_in((binary_prec),Op,P) :- current_op(P,M,Op),M=yfx,!. /*
 */ built_in((binary_prec),_,_) :- look_up((binary_prec),_),!,fail. /*
 */ built_in((binary_prec),Op,0) :- write(''''),write(Op),write(''' is not a current binary operator.'),nl,!. /*

Booleans
========
The boolean values are 'True' and 'False'.

 */ boolean('True'). /*
 */ boolean('False'). /*

'True' and 'False' are complements of one another.
        
 */ complement('True','False'). /*
 */ complement('False','True'). /*

'\X' denotes the complement of X; if X is 'True' \X is 'False' and vice versa.

 */ built_in(\,X,Z) :- !,simplify(X,Y),find_complement(Y,Z). /*

 */ find_complement(Y,Z) :- complement(Y,Z),!. /*
 */ find_complement(Y,_) :- inapplicable(\,Y). /*

'X v Y' is 'True' if either X or Y is 'True'.  Therefore if X is 'True', Y needn't be simplified.

 */ built_in(v,(X,Y),Z) :- !,simplify(X,X1),simplify_or(X1,Y,Z),!. /*
    
 */ simplify_or('True',_,'True') :- !. /*
 */ simplify_or('False',Y,Z) :- simplify(Y,Z),boolean(Z),!. /*
 */ simplify_or(X,Y,_) :- inapplicable(v,(X,Y)). /*

'X & Y' is 'False' if either X or Y is 'False'.  Therefore if X is 'False', Y needn't be simplified.

 */ built_in(&,(X,Y),Z) :- !,simplify(X,X1),simplify_and(X1,Y,Z),!. /*
    
 */ simplify_and('False',_,'False') :- !. /*
 */ simplify_and('True',Y,Z) :- simplify(Y,Z),boolean(Z). /*
 */ simplify_and(X,Y,_) :- inapplicable(&,(X,Y)). /*

'X=>Y' denotes 'X implies Y', which is 'False' only if X is 'True' and Y is 'False'.

 */ built_in(=>,(X,Y),Z) :- !,simplify(X,X1),implies(X1,Y,Z). /*

 */ implies('True',_,Z) :- !,Z='True'. /*
 */ implies('False',Y,Z) :- !,simplify(Y,Y1),complement(Y1,Y2),!,Z=Y2. /*
 */ implies(X,Y,_) :- inapplicable(=>,(X,Y)). /*

'X<=>Y' denotes 'X if and only if Y' which is true if and only if X and Y have the same value.

 */ built_in(<=>,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),boolean(X1),boolean(Y1),simplify_iff(X1,Y1,Z). /*

 */ simplify_iff(X,X,Z) :- boolean(X),!,Z='True'. /*
 */ simplify_iff(X,Y,Z) :- complement(X,Y),!,Z='False'. /*
 */ simplify_iff(X,Y,_) :- inapplicable(<=>,(X,Y)). /*

The succeeds function yields 'True' if it argument succeeds as a Prolog goal, otherwise it yields 'False'.
A Prolog goal can look just like a Libra expression, so X is not simplified.

 */ built_in(succeeds,X,Z) :- call(X),!,Z='True'. /*
 */ built_in(succeeds,_,'False') :- !. /*

Sets & Relations as Data
========================
The following uses of relational operators occur in contexts where the operator is NOT part of the 2nd operand of an application.  Therefore the operator can't be applied as lazily as when the relational expression is applied to an argument by 'construct'.  The basic strategy is to use 'generate' to enumerate the values of the expression, and 'findall' to collect them.  'Sort' gets rid of duplicates, and puts the set into standard form.  The exceptions are the closure operators, which work more intelligently than 'generate' would - and anything else where there is a fast easy method.
            
 */ built_in(^+,(R,N),Z) :- !,findall(W,generate(R^+N,W),U),sort(U,Z). /*
 */ built_in(^-,(R,N),Z) :- !,simplify(R,R1),build_inverse(R1,R2),sort(R2,R3),findall(W,generate(R3^+N,W),U),sort(U,Z). /*
 */ built_in(^+,R,Z) :- !,simplify(R,R1),construct_closure([],R1,Z). /*
 */ built_in(^*,R,Z) :- !,simplify(R,R1),construct_closure([],R1,C),findall((X,X),generate(C,(X,_)),D),sort(D,E),
                        findall((Y,Y),generate(C,(_,Y)),F),sort(F,G),simplify(C join E join G,Z). /*
 */ built_in(^^,R,Z) :- !,simplify(R,R1),simplify(R1^*,C),simplify(dom R1,D),findall(W,construct_limit(D,C,W),U),sort(U,Z). /*
 */ built_in(<-,S,Z) :- !,simplify(S,S1),build_reverse(S1,S2),sort(S2,Z). /*

 */ built_in(o,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),build_composition(X1,Y1,Z). /*
 */ built_in(join,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),build_join(X1,Y1,Z). /*

 */ built_in(meet,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),build_meet(X1,Y1,Z). /*
 */ built_in(omit,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),build_omit(X1,Y1,Z). /*
 */ built_in(else,(R1,R2),Z) :- !,simplify(R1,X),simplify(R2,Y),build_else(X,Y,Z). /*
 */ built_in(but,(R1,R2),Z) :- !,simplify(R1,X),simplify(R2,Y),build_else(Y,X,Z). /*

 */ built_in(<?,(S,R),Z) :- !,simplify(R,R1),build_left_rest(S,R1,Z). /*
 */ built_in(<\?,(S,R),Z) :- !,simplify(R,R1),build_left_anti_rest(S,R1,Z). /*
 */ built_in(?>,(R,S),Z) :- !,simplify(R,R1),build_right_rest(S,R1,Z). /*
 */ built_in(\?>,(R,S),Z) :- !,simplify(R,R1),build_right_anti_rest(S,R1,Z). /*

 */ built_in(x,(S,T),Z) :- !,findall(W,generate((S x T),W),L),sort(L,Z). /*
 */ built_in(sets_of,S,T) :- !,findall(X,generate(sets_of S,X),L),sort(L,T). /*
 */ built_in(seqs_of,S,T) :- !,findall(X,generate(seqs_of S,X),L),sort(L,T). /*

 */ built_in(&&,(X,Y),Z) :- !,simplify(X,X1),simplify(Y,Y1),append_seq(0,X1,Y1,Z). /*

 */ built_in(dom,R,Z) :- !,simplify(R,R1),build_dom(R1,Z). /*
 */ built_in(codom,R,Z) :- !,simplify(R,R1),findall(Y,generate(R1,(_,Y)),U),sort(U,Z). /*

 */ built_in(\\,((X,Y),Op),Z) :- !,findall(W,generate((X,Y)\\Op,W),L),sort(L,Z). /*

 */ construct_closure(Old,New,Old) :- test_subset(New,Old,'True'),!. /*
 */ construct_closure(Old,New,Z) :- build_join(Old,New,Both),build_composition(Both,Both,More),
                                    construct_closure(Both,More,Z). /*

 */ construct_limit(D,C,(X,Y)) :- generate(C,(X,Y)),filter_out(Y,D). /*

 */ build_composition(X,Y,Z) :- grounded(X),grounded(Y),!,build_inverse(X,X1),sort(X1,X2),compose(X2,Y,[],Z1),sort(Z1,Z). /*
 */ build_composition(X,Y,Z) :- !,findall(W,generate(X o Y,W),U),sort(U,Z). /*

 */ compose([],T2,W,W) :- !. /*
 */ compose(T1,[],W,W) :- !. /*
 */ compose([(Y,X)|T1],[(Y,Z)|T2],W,W2) :- !,compose_term((Y,X),[(Y,Z)|T2],W,W1),compose(T1,[(Y,Z)|T2],W1,W2). /*
 */ compose([(Y1,X)|T1],[(Y2,Z)|T2],W,W1) :- Y1@<Y2,!,compose(T1,[(Y2,Z)|T2],W,W1). /*
 */ compose([(Y1,X)|T1],[(Y2,Z)|T2],W,W1) :- !,compose([(Y1,X)|T1],T2,W,W1). /*
 */ compose(R1,R2,_,_) :- inapplicable(o,(R1,R2)). /*

 */ compose_term((Y,X),[(Y,Z)|T2],W,[(X,Z)|W1]) :- !,compose_term((Y,X),T2,W,W1). /*
 */ compose_term(_,_,W,W) :- true. /*

 */ build_join([],S2,S2) :- !. /*
 */ build_join(S1,[],S1) :- !. /*
 */ build_join([H1|T1],[H2|T2],[H1|T3]) :- isomorphic(H1,H2),!,build_join(T1,T2,T3). /*
 */ build_join([H1|T1],[H2|T2],[H1|T3]) :- H1@<H2,!,build_join(T1,[H2|T2],T3). /*
 */ build_join([H1|T1],[H2|T2],[H2|T3]) :- !,build_join([H1|T1],T2,T3). /*
 */ build_join(S1,S2,_) :- inapplicable(join,(S1,S2)). /*

 */ build_meet([],_,[]) :- !. /*
 */ build_meet(_,[],[]) :- !. /*
 */ build_meet(S1,S2,S3) :- grounded(S2),!,build_fast_meet(S1,S2,S3). /*
 */ build_meet([H1|T1],S2,[H1|T3]) :- filter(H1,S2),!,build_meet(T1,S2,T3). /*
 */ build_meet([_|T1],S2,S3) :- !,build_meet(T1,S2,S3). /*
 */ build_meet(S1,S2,_) :- inapplicable(meet,(S1,S2)). /*

 */ build_fast_meet([],_,[]) :- !. /*
 */ build_fast_meet(_,[],[]) :- !. /*
 */ build_fast_meet([H1|T1],[H2|T2],[H1|T3]) :- isomorphic(H1,H2),!,build_fast_meet(T1,T2,T3). /*
 */ build_fast_meet([H1|T1],[H2|T2],T3) :- H1@<H2,!,build_fast_meet(T1,[H2|T2],T3). /*
 */ build_fast_meet([H1|T1],[H2|T2],T3) :- !,build_fast_meet([H1|T1],T2,T3). /*
 */ build_fast_meet(S1,S2,_) :- inapplicable(meet,(S1,S2)). /*

 */ build_omit([],_,[]) :- !. /*
 */ build_omit(S1,[],S1) :- !. /*
 */ build_omit(S1,S2,S3) :- grounded(S2),!,build_fast_omit(S1,S2,S3). /*
 */ build_omit([H1|T1],S2,S3) :- filter(H1,S2),!,build_omit(T1,S2,S3). /*
 */ build_omit([H1|T1],S2,[H1|T3]) :- !,build_omit(T1,S2,T3). /*
 */ build_omit(S1,S2,_) :- inapplicable(omit,(S1,S2)). /*

 */ build_fast_omit([],_,[]) :- !. /*
 */ build_fast_omit(S1,[],S1) :- !. /*
 */ build_fast_omit([H1|T1],[H2|T2],T3) :- isomorphic(H1,H2),!,build_fast_omit(T1,T2,T3). /*
 */ build_fast_omit([H1|T1],[H2|T2],[H1|T3]) :- H1@<H2,!,build_fast_omit(T1,[H2|T2],T3). /*
 */ build_fast_omit([H1|T1],[H2|T2],T3) :- !,build_fast_omit([H1|T1],T2,T3). /*
 */ build_fast_omit(S1,S2,_) :- inapplicable(omit,(S1,S2)). /*

 */ build_else([],R2,R2) :- !. /*
 */ build_else([(X1,Y1)|T1],[(X2,_)|T2],S3) :- isomorphic(X1,X2),!,build_else([(X1,Y1)|T1],T2,S3). /*
 */ build_else([(X1,Y1)|T1],[(X2,Y2)|T2],[(X1,Y1)|T3]) :- X1@<X2,!,build_else(T1,[(X2,Y2)|T2],T3). /*
 */ build_else([(X1,Y1)|T1],[(X2,Y2)|T2],[(X2,Y2)|T3]) :- !,build_else([(X1,Y1)|T1],T2,T3). /*
 */ build_else(R1,R2,_) :- inapplicable(else,(R1,R2)). /*

 */ build_left_rest(_,[],[]) :- !. /*
 */ build_left_rest(S,[(X,Y)|T2],[(X,Y)|T3]) :- filter(X,S),!,build_left_rest(S,T2,T3). /*
 */ build_left_rest(S,[_|T2],T3) :- !,build_left_rest(S,T2,T3). /*
 */ build_left_rest(S,R,_) :- inapplicable(<?,(R,S)). /*

 */ build_left_anti_rest(_,[],[]) :- !. /*
 */ build_left_anti_rest(S,[(X,_)|T2],T3) :- filter(X,S),!,build_left_anti_rest(S,T2,T3). /*
 */ build_left_anti_rest(S,[(X,Y)|T2],[(X,Y)|T3]) :- !,build_left_anti_rest(S,T2,T3). /*
 */ build_left_anti_rest(S,R,_) :- inapplicable(<\?,(R,S)). /*

 */ build_right_rest(_,[],[]) :- !. /*
 */ build_right_rest(S,[(X,Y)|T2],[(X,Y)|T3]) :- filter(Y,S),!,build_right_rest(S,T2,T3). /*
 */ build_right_rest(S,[_|T2],T3) :- !,build_right_rest(S,T2,T3). /*
 */ build_right_rest(S,R,_) :- inapplicable(?>,(R,S)). /*

 */ build_right_anti_rest(_,[],[]) :- !. /*
 */ build_right_anti_rest(S,[(_,Y)|T2],T3) :- filter(Y,S),!,build_right_anti_rest(S,T2,T3). /*
 */ build_right_anti_rest(S,[(X,Y)|T2],[(X,Y)|T3]) :- !,build_right_anti_rest(S,T2,T3). /*
 */ build_right_anti_rest(S,R,_) :- inapplicable(/?>,(R,S)). /*

 */ build_dom([],[]) :- !. /*
 */ build_dom([(X1,_),(X2,Y2)|T1],S2) :- isomorphic(X1,X2),!,build_dom([(X2,Y2)|T1],S2). /*
 */ build_dom([(X1,_)|T1],[X1|T2]) :- !,build_dom(T1,T2). /*
 */ build_dom(S,_) :- inapplicable(dom,S). /*

 */ build_inverse([],[]) :- !. /*
 */ build_inverse([(X,Y)|T1],[(Y,X)|T2]) :- !,build_inverse(T1,T2). /*
 */ build_inverse(S,_) :- inapplicable(^-,S). /*

 */ build_reverse(S,S1) :- length(S,L),reverse_seq(L,1,S,S1),!. /*
 */ build_reverse(S,_) :- inapplicable(<-,S). /*

 */ reverse_seq(_,_,[],[]) :- !. /*
 */ reverse_seq(L,N1,[(N1,H)|T1],[(N2,H)|T2]) :- N2 is L+1-N1,N3 is N1+1,reverse_seq(L,N3,T1,T2). /*

 */ append_seq(N,[],S2,S3) :- !,shift(1,N,S2,S3). /*
 */ append_seq(N,[(N1,Y)|T1],S2,[(N1,Y)|T3]) :- N1 is N+1,!,append_seq(N1,T1,S2,T3). /*
 */ append_seq(_,_,_,_) :- look_up(&&,_),!,fail. /*
 */ append_seq(_,S1,_,_) :- write('''&&'' can''t be applied to '''),display_exp(S1),write('''.'),nl,fail. /*

The expression #S is the number of members (cardinality) of S.  The members of S are generated, collected and sorted, to deal with expressions that yield a set.
    
 */ built_in(#,S,N) :- !,simplify(S,S1),cardinality(S1,N). /*

 */ cardinality(S,N) :- length(S,N),!. /*
 */ cardinality(S,_) :- inapplicable(#,S). /*

The identity function of a set is a restriction of the universal identity function to the set.

 */ built_in(id,X,Z) :- grounded(X),!,findall((Y,Y),generate(X,Y),L),sort(L,Z). /*
 */ built_in(id,S,[((X,X):X?S)]) :- !. /*

The 'head' function returns the first term of a sequence.  This is done by applying the sequence to 1 as a relation.

 */ built_in(head,S,Y) :- !,simplify(S,S1),head(S1,Y). /*

 */ head([],_) :- !,fail. /*
 */ head([(1,Y)|_],Y) :- !. /*
 */ head(S,_) :- inapplicable(head,S). /*

The 'tail' function returns all terms but the first term of a sequence.  The sequence had better be a generator!

 */ built_in(tail,S,Y) :- !,simplify(S,S1),tail(S1,Y). /*

 */ tail([],_) :- fail,!. /*
 */ tail([(1,_)|T],Y) :- shift(2,-1,T,Y),!. /*
 */ tail(S,_) :- inapplicable(tail,S). /*

The predicate 'shift(M,N,X,Y)' shifts X, the tail of a sequence starting with the Mth term, N positions right, by adding N to all its arguments, leaving the values the same.

 */ shift(_,_,[],[]) :- !. /*
 */ shift(M,N,[(M,Y)|T],[(N1,Y)|T1]) :- !,N1 is M+N,M1 is M+1,shift(M1,N,T,T1). /*

The 'last' function returns the last term of a sequence.  This is done by finding its length, then applying the sequence to the length as a relation.

 */ built_in(last,S,Y) :- !,simplify(S,S1),last(S1,Y). /*

 */ last([],_) :- !,fail. /*
 */ last(S,Y) :- simplify(#S,N),construct(N,S,Y),!. /*
 */ last(S,_) :- inapplicable(last,S). /*
 
The 'front' function returns all but the last term of a sequence.  This is done by sorting it, then omiting its last term.

 */ built_in(front,S,Y) :- !,simplify(S,S1),front(1,S1,Y). /*
    
 */ front(_,[],_) :- !,fail. /*
 */ front(N,[(N,_)|[]],[]) :- !. /*
 */ front(N,[(N,H)|T],[(N,H)|T1]) :- !,N1 is N+1,front2(N1,T,T1). /*
 */ front(_,S,_) :- inapplicable(front,S). /*

The 'unique' relation constructs a unique name from a given prefix.

 */ built_in(unique,X,Z) :- simplify(X,X1),new_suffix(X1,Y),construct((X1,Y),&&,Z),!. /*

 */ new_suffix(X,Z) :- retract(unique(X,N)),!,N1 is N+1,assert(unique(X,N1)),name(N1,Y),list_to_seq(1,Y,Z). /*
 */ new_suffix(X,Z) :- assert(unique(X,1)),name(1,Y),list_to_seq(1,Y,Z). /*

The 'sort' relation converts a set into a sorted sequence.  Since sets are always stored in sorted order, they only need to be paired with numbers.

 */ built_in(sort,X,Z) :- !,simplify(X,Y),list_to_seq(1,Y,Z). /*

Set comparisons are done as lazily as possible, and terminated as soon as a result is known.  X is a subset of Y if every member of X is also a member of Y.  Conversely, if any member of X is not a member of Y, X is not a subset of Y:

 */ built_in(subset,(X,Y),Z) :- grounded(X),grounded(Y),!,test_subset(X,Y,Z). /*
 */ built_in(subset,(X,Y),'False') :- generate(X,Z),test_filter(Z,Y,'False'),!. /*
 */ built_in(subset,(_,_),'True') :- !. /*

 */ test_subset([],_,'True') :- !. /*
 */ test_subset([H|T1],[H|T2],Z) :- !,test_subset(T1,T2,Z). /*
 */ test_subset([H1|T1],[H2|T2],Z) :- H1@<H2,!,Z='False'. /*
 */ test_subset(X,[H2|T2],Z) :- !,test_subset(X,T2,Z). /*
 

Sets X and Y are equal if every member of X is a member of Y, and vice versa.

 */ built_in(equal,(X,Y),Z) :- !,built_in(=,(X,Y),Z). /*

Sets X and Y are unequal if they are not equal.

 */ built_in(unequal,(X,Y),Z) :- !,built_in(\=,(X,Y),Z). /*

X is a proper subset of Y ('X inside Y') if X is a subset of Y, but Y has some member that is not a member of X.

 */ built_in(inside,(X,Y),Z) :- built_in(subset,(X,Y),B1),built_in(subset,(Y,X),B2),complement(B2,B3),built_in(&,(B1,B3),Z). /*

X and Y are disjoint if no member of X is a member of Y, and vice versa.  Conversely, if any member of X is also a member of Y, the sets are not disjoint.

 */ built_in(disjoint,(X,Y),'False') :- generate(X,Z),test_filter(Z,Y,'True'),!. /*
 */ built_in(disjoint,(_,_),'True') :- !. /*

'X includes Y' is a syntactical variant of 'Y subset X'.

 */ built_in(includes,(X,Y),Z) :- !,built_in(subset,(Y,X),Z). /*

'X encloses Y' is a syntactical variant of 'Y inside X'.

 */ built_in(encloses,(X,Y),Z) :- !,built_in(inside,(Y,X),Z). /*

The ordinary comparison operators can be applied to sequences.  Since sequences can contain structured elements, we want this to work nicely, even to the extent that {X->X+1} and {Y->Y+1} are considered equal.  However, > and < don't always make sense because not every pair of structures is comparable.  Out of laziness, we check that both operands are structures, then use Prolog's standard order.  The predicate 'test_cmpd' is called from within 'compare_int', along with the arithmetic comparison logic.

 */ built_in(=,(X,Y),Z) :- !,test_cmpd(=,X,Y,Z). /*
 */ built_in(\=,(X,Y),Z) :- !,test_cmpd(\=,X,Y,Z). /*
 */ built_in(>,(X,Y),Z) :- !,test_cmpd(>,X,Y,Z). /*
 */ built_in(<,(X,Y),Z) :- !,test_cmpd(<,X,Y,Z). /*
 */ built_in(>=,(X,Y),Z) :- !,test_cmpd(>=,X,Y,Z). /*
 */ built_in(=,(X,Y),Z) :- !,test_cmpd(=<,X,Y,Z). /*

 */ test_cmpd(R,X,Y,Z) :- compound(X),compound(Y),!,test_rel(R,X,Y,Z). /*
 */ test_cmpd(R,X,Y,_) :- inapplicable(R,(X,Y)). /*

 */ test_rel(=,X,Y,Z) :- isomorphic(X,Y),!,Z='True'. /*
 */ test_rel(=,_,_,'False') :- true. /*
 */ test_rel(\=,X,Y,Z) :- test_rel(=,X,Y,B),complement(B,Z). /*
 */ test_rel(>=,X,Y,Z) :- isomorphic(X,Y),!,Z='True'. /*
 */ test_rel(>=,X,Y,Z) :- X@>Y,!,Z='True'. /*
 */ test_rel(>=,_,_,'False') :- true. /*
 */ test_rel(=<,X,Y,Z) :- isomorphic(X,Y),!,Z='True'. /*
 */ test_rel(=<,X,Y,Z) :- X@<Y,!,Z='True'. /*
 */ test_rel(=<,_,_,'False') :- true. /*
 */ test_rel(<,X,Y,Z) :- test_rel(>=,X,Y,B),complement(B,Z). /*
 */ test_rel(>,X,Y,Z) :- test_rel(=<,X,Y,B),complement(B,Z). /*

Input-Output
============
Because there can be many threads of control, which proceed in parallel at least in principle, an input-output file shared between different threads would be subjected to a random sequence of reads and writes.  This might be OK, if the order of output lines doesn't matter, or if input lines are processed as a set rather than as a sequence.  The solution adopted for the present is restrict input and output to one file at a time using 'see' and 'tell', much as in Prolog.  However, once a thread has grabbed the file using 'see' or 'tell', no other thread can grab it, until it has been released using 'seen' or 'told'.  The relations 'speak' and 'spoken' are shorthands for 'see("user") o tell("user")' and 'seen o told'.  Note that file-names are strings, not atoms.  'See' and 'tell' yield identity functions as output, so that they are transparent.

The 'see' relation expects a string specifying a file name.  If a file is already being seen (including the user), an error is reported.  'See(file-name)' yields an identity function.

 */ built_in(see,F,Z) :- !,simplify(F,F1),simplify_see(F1,Z). /*

 */ simplify_see(F,_) :- clause(input_file(F2,_),true),!,simplify_see_2(F,F2). /*
 */ simplify_see(F,[(X,X)]) :- is_seq(F,1),seq_to_list(F,L),name(N,L),see(N),!,assert(input_file(N,false)). /*
 */ simplify_see(_,_) :- look_up(see,_),!,fail. /*
 */ simplify_see(F,_) :- !,write('Can''t see '''),display_exp(F),write('''.  It isn''t a file.'),nl,fail. /*

 */ simplify_see_2(_,_) :- look_up(see,_),!. /*
 */ simplify_see_2(F,F2) :- telling(Old),tell(user),write('Cannot see '''),put_str(1,F),write('''; '''),
                            write(F2),write(''' is already in use.'),nl,told,tell(Old),!,fail. /*

The 'seen' predicate copies its argument, and disconnects the current input file.

 */ built_in(seen,X,Y) :- !,simplify(X,Y),built_in_seen. /*

 */ built_in_seen :- retract(input_file(_,_)),!,seen. /*
 */ built_in_seen :- look_up(seen,_),!,fail. /*
 */ built_in_seen :- !,write('Can''t release input file; nothing is being seen.'),nl,fail. /*

The 'read' relation ignores its argument and yields the next expression from the current input file.  It is inapplicable at the end-of-file.

 */ built_in(read,_,Z) :- clause(input_file(_,false),true),!,read(Y),process_term(Y,Z). /*
 */ built_in(read,_,_) :- clause(input_file(_,true),true),!,fail. /*
 */ built_in(read,_,_) :- look_up(read,_),!,fail. /*
 */ built_in(read,_,_) :- !,write('Can''t read.  No file is being seen.'),nl,fail. /*

 */ process_term(end_of_file,_) :- !,fail. /*
 */ process_term(X,Y) :- preprocess(X,Y,[[]],_,read). /*

The 'get' relation ignores its argument and yields the next line of input as a string.  It is inapplicable at end of file.  If the line is not terminated by end-of-line before end-of-file is reached, an end of line is imagined.

 */ built_in(get,_,Y) :- clause(input_file(_,false),true),!,get0(LA),get_line(LA,Y). /*
 */ built_in(get,_,_) :- clause(input_file(_,true),true),!,fail. /*
 */ built_in(get,_,_) :- look_up(get,_),!,fail. /*
 */ built_in(get,_,_) :- !,write('Can''t get.  No file is being seen.'),nl,fail. /*

 */ get_line(26,_) :- !,retract(input_file(F,false)),assert(input_file(F,true)),fail. /* 
 */ get_line(LA,Y) :- get_chars(LA,_,1,Y). /* 

 */ get_chars(26,26,_,[]) :- !,retract(input_file(F,false)),assert(input_file(F,true)). /*
 */ get_chars(31,31,_,[]) :- !. /*
 */ get_chars(LA,LC,N,[(N,LA)|T]) :- get0(Ch),N1 is N+1,get_chars(Ch,LC,N1,T). /*

The 'tell' relation expects a string specifying a file name.  If a file is already being told (including the user), an error is reported.  'Tell(file-name)' yields an identity function.

 */ built_in(tell,F,Z) :- !,simplify(F,F1),simplify_tell(F1,Z). /*

 */ simplify_tell(F,_) :- clause(output_file(F2),true),!,simplify_tell_2(F,F2). /*
 */ simplify_tell(F,[(X,X)]) :- is_seq(F,1),seq_to_list(F,L),name(N,L),tell(N),!,assert(output_file(N)). /*
 */ simplify_tell(_,_) :- look_up(tell,_),!,fail. /*
 */ simplify_tell(F,_) :- !,write('Can''t tell '''),display_exp(F),write('''.  It isn''t a file-name.'),nl,fail. /*

 */ simplify_tell_2(_,_) :- look_up(tell,_),!,fail. /*
 */ simplify_tell_2(F,F2) :- telling(Old),tell(user),write('Can''t tell '''),put_str(1,F),write('''; '''),
                             write(F2),write(''' is already in use .'),nl,told,tell(Old),!,fail. /*

The 'told' relation copies its argument, and disconnects the current output file.

 */ built_in(told,X,Y) :- !,simplify(X,Y),built_in_told. /*
 */ built_in_told :- retract(output_file(_)),!,told. /*
 */ built_in_told :- look_up(told,_),!,fail. /*
 */ built_in_told :- !,write('Can''t release output file; nothing is being told.'),nl,fail. /*

The 'speak' relation is equivalent to 'tell("user") o see("user")'.  It copies its arguments.  It is used to open a dialogue with the user.

 */ built_in(speak,X,Y) :- !,simplify(X,Y),list_to_seq(1,"user",U),simplify_tell(U,_),simplify_see(U,_). /*

The 'spoken' relation is equivalent to 'told o seen'.  It copies its arguments.

 */ built_in(spoken,X,Y) :- !,simplify(X,Y),built_in(told,Y,Y),built_in(seen,Y,Y). /*

The 'write' relation copies its arguments, pretty-printing them as a side-effect.

 */ built_in(write,X,Y) :- !,simplify(X,Y),built_in_write(Y). /*

 */ built_in_write(Y) :- clause(output_file(_),true),!,display_exp(Y). /*
 */ built_in_write(_) :- look_up(write,_),!,fail. /*
 */ built_in_write(_) :- !,write('Can''t write; no output file is being told.'),nl,fail. /*

The 'debug' relation copies its arguments, displaying them and a new-line to the user as a side effect.

 */ built_in(debug,X,Y) :- !,simplify(X,Y),telling(Old),tell(user),write('debug: '),display_exp(Y),nl,told,tell(Old). /*

The 'put' relation expects a string, which it displays as a side-effect. 'Put(str)' yields an identity function.

 */ built_in(put,X,[(Z,Z)]) :- !,simplify(X,Y),built_in_put(Y). /*

 */ built_in_put(X) :- clause(output_file(_),true),!,put_str(1,X). /*
 */ built_in_put(_) :- look_up(put,_),!,fail. /*
 */ built_in_put(_) :- !,write('Can''t put; no output file is being told.'),nl,fail. /*

 */ put_str(_,[]) :- !. /*
 */ put_str(N,[(N,H)|T]) :- character(H),!,put(H),N1 is N+1,put_str(N1,T). /*
 */ put_str(_,_) :- look_up(put,_),!,fail. /*
 */ put_str(_,S) :- write('Can''t put '''),display_exp(S),write('''.  It isn''t a character string.'),nl,fail. /*

The 'nl' function copies its arguments, writing a new line as a side-effect.

 */ built_in(nl,X,Y) :- !,simplify(X,Y),built_in_nl. /*
 */ built_in_nl :- clause(output_file(_),true),!,nl. /*
 */ built_in(nl,_,_) :- look_up(nl,_),!. /*
 */ built_in_nl :- !,write('Can''t start a new line; no output file is being told.'),nl,fail. /*

The 'null' relation generates the special token 'null', which suppresses normal output from 'find'.

 */ built_in(null,X,null) :- !,simplify(X,_). /*

The 'int_to_str' function converts an integer to the corresponding string.

 */ built_in(int_to_str,X,Z) :- !,simplify(X,Y),int_to_str(Y,Z). /*

 */ int_to_str(X,Z) :- integer(X),!,name(X,Y),list_to_seq(1,Y,Z). /*
 */ int_to_str(X,_) :- inapplicable(int_to_str,X). /*

The 'str_to_int' function converts a string to an integer, if it can.

 */ built_in(str_to_int,X,Z) :- !,simplify(X,Y),str_to_int(Y,Z). /*

 */ str_to_int(X,Z) :- seq_to_list(X,Y),list_to_integer(Y,Z),!. /*
 */ str_to_int(X,_) :- inapplicable(str_to_int,X). /*

 */ list_to_integer([43|X],Z) :- !,name(Z,X),integer(Z). /*
 */ list_to_integer([45|X],Z) :- !,name(Y,X),integer(Y),Z is -Y. /*
 */ list_to_integer(X,Z) :- name(Z,X),integer(Z). /*
 
Safety Net
==========
We want to be sure that all the predefined relations have been caught correctly.  Therefore if this point is reached, we should get excited.

 */ built_in(R,X,_) :- inapplicable(R,X). /*

 */ inapplicable(R,_) :- look_up(R,_),!,fail. /*
 */ inapplicable(R,X) :- write(''''),write(R),write(''' isn''t applicable to '''),display_exp(X),write('''.'),nl,!,fail. /*

End of literate program. */
