pereira@sri-unix.UUCP (08/15/83)
/* TIDY.PL : Lawrence's go fast, hacked up, version of Tidy
Lawrence
Updated: 9 August 82
This code implements a simple tidy/evaluator which tries to
maximise evaluation. It is supposed to be efficient so that there
is not much expense involved in using it as a first step to something
else. It traverses the input term in a single pass and does not
build any significant intermediate structures. It performs two
kinds of function:
1) Simple normalisation
All occurences of the operators / and - are removed in
favour of * and +.
Bags are formed for * and +. These bags are left recursive
trees built with the functors *(_,_) and +(_,_). All numbers
in the bag are evaluated and the result, if any, will always
be the top rightmost element of the bag. This will not be present
if it would be the unit element of the bag. Nested exponentiations
(of the form ((A^B)^C)^D etc) are collapsed into their base
to the power of a multiplication bag (ie A^(B*C*D)).
egs: * bags:
* *
/ \ / \
* c * 19
/ \ / \
a b * c
/ \
a b
(This form gives the advantages of bags, ie traversing, selecting
elements is easy and you know when you've finished, while leaving
the expression as a standard algebraic term. However this may not
be optimal for all purposes)
2) Evaluation
Numerical evaluation is performed where possible. Advantage is
taken of the associative properties of * and + (as the bags are
formed). Some simplifying rules are applied concerning zero and
unit elements of these bags. A small amount of distribution of
one operator over another is done where this will aid evaluation.
The total set of functions that tidy actually tidies are as follows:
*(_,_) /(_,_) +(_,_) -(_,_) -(_) ^(_,_) &(_,_) #(_,_)
Expressions involving other functions are handed to eval if all their
arguments have been evaluated (to numbers). This may result in these
simple expressions being reduced to numbers (which may then be involved
in further evaluations).
NB Tidy should be used as the expression evaluator instead of eval
(from LONG.PL) whenever the expressions are (or may be) partly
symbolic. It will call eval for all the numeric subexpressions
(using its normalisation tricks to try and maximise the the amount
of numeric evaluation). Over purely numeric expressions tidy will
be equivalent to eval.
** TODO
There is undoubtably scope for improvement. I can think of:
b) Improve the evaluation. Only self generated numbers
(such as *-1, ^-1) are distributed at the moment.
tidy does not handle such things already occuring
in the input. Eg (a*b^-1)^-1 is left as it is.
But it is arguable how much of this should go on.
(Try to produce bag with the minimum number of
recipricals/negatives?)
c) Various people seem to want sin/arcsin (etc) cancelling
added for good measure.
** SIGNIFICANT BUG
There is a logical bug in the current code. I have assumed
that when bag sweepers bottom out, the tidied version of
the bit at the bottom will not be the sort of thing that could
have been incorporated into the bag, otherwise we would
have spotted it and kept going. However, this is not true!
For example: a*b*( (c*d)+0 )
When the c*d comes back it is a mulbag and should be merged
with the upper a*b mulbag. The current code doesn't do this
because it I didn't realise that the lower bag could be hidden
as shown in the example. When I find time I intend to rewrite
the affected bits so that a proper bag merge is defined and
applied. The interesting bit is how to do this without
rebuilding one of the bags completely - ie by using partial
structures a la difference lists. But I am not sure how much
I care about such efficiency/complexity hacks any more. Trying
to be clever in the current code taught me what an effort it
is and how it makes things much more complicated. What I really
need is a practical program transformation system to
Unfold/Fold a multipass specification into a single pass hack
(Cf Burstall & Darlington, Feather etc). Please tell me when
you have such a thing ready for use.
** RECENT FIXES
[ 1981 ]
(4 March) Code for & and # added by Leon. This code leaves the
structure of these functions as it was (ie no bagging
is done), however simplifications are applied. Note
that this includes some identical element merging (but
this does not use associativity).
(10 March) Put some cuts in the code for & and #. Also renamed
the predicates and flattened out the structures into
separate arguments (These little things!).
Fixed problem stemming from assumption that arithmetic
always succeed. This was not true (power sometimes fails)
and resulted in tidy failing when an arithmetic operation
failed. The fix involved moving the cuts in the ...build
and ...fin routines which call arithmetic routines. No
assumption is now made about their success, even for
add and multiply which should always succeed.
Reordered the file a little and added some more
documentation.
(18 March) Added tidy clauses for logs.
Also normalize clause for sqrt (Leon)
(1 April) When given nested variables tidy produces mode errors
as these are not expected. Fixed this by adding checks
to appropriate places and a top level error message
if tidy fails.
(2 August) Added the BUG note above and a couple of other comments.
[ 1982 ]
(13 May 82) Tidied up the use of simplification a bit.
simplify_axiom's moved elsewhere.
(9 August 82) Added tidy_withvars for those seldom occasions where
the structure to be tidied is allowed to contain
variables (required by Bernard).
*/
/* EXPORT */
:- public tidy/2,
tidy_withvars/2,
simple/1.
/* IMPORT */
% This version designed for use with rational package (LONG)
% In particular it uses:
% number/1
% eval/2
% add/3
% multiply/3
% power/3
%
% Other imports (existence optional):
%
% simplify_axiom/2
/* MODES */
:- mode tidy(+,?),
tidy_withvars(?,?),
t_wvhack(+,+,-,-),
dotidy(+,-),
simple(?),
tidyall(+,+,+,+,-),
chknum(+,+,-),
try_eval(+,+,-),
apply_simplification(+,-),
mulbag(+),
plusbag(+),
expbag(+),
multidy(+,+,+,+,-,-),
m2tidy(+,+,-),
mulbuild(+,+,+,-,-),
plustidy(+,+,+,+,-,-),
p2tidy(+,+,-),
plusbuild(+,+,+,-,-),
exptidy(+,+,+,-,-,-),
distr_inverse(+,-),
andfin(+,+,-),
orfin(+,+,-),
mulfin(+,+,-),
plusfin(+,+,-),
expfin(+,+,+,-),
n_expfin(+,+,-),
tidy_varerr.
/* Implementation - some hints.
The top level is pretty straight forward, note that the invarient
that all solution arguments should be initially uninstantiated is
guaranteed by unifying the tidied expression with the output variable
right at the end of the tidy operation (tidy/2). This is to avoid any
bugs with output arg unification failures causing clauses with cuts
to be missed. [You should know what this means - if not then think
about it. Eg ?- foo(a,b). foo(a,c) :- !. foo(_,b). ]
The bag sweeping routines sweep across the term (left to right
for multiplication and division bags but right to left down
exponentiation chains) with a pair of accumulators being passed
across. Thus for multidy, Left and Ltag are the two incoming
accumulators and Right and Rtag are the resultant accumulators
after this bit of the tree has been looked at. (For exptidy the
names are the other way round). One accumulator is the bag of
symbolic structures (eg Left), the other is the bag of numeric
structures (eg Ltag). The numeric bag will always be just a number
since the arithmetic operations are done immediately whenever a number
is found. The symbolic bag may be empty, which is represented by the
Prolog atom 'empty'. Simultaneously with this accumulation there is a
process of pushing down a distibuted term (Distr). This is one of {1,-1}.
For multidy this is the power that each final element should be raised
to, and for plustidy this is the multiplier that each final element
should be multiplied by. This value is flipped back and forth as the
top down descent passes through divisions (multidy) and subtractions
(plustidy).
The bag sweepers bottom out when they hit the top of an expression
which they won't be able to incorporate. m2tidy and p2tidy see that
this expression gets (recursively) tidied, and then they incorporate
this with the distributed term (simplifying this away when it is 1).
There is a special case here when the expression bottomed out on involves
the same operation as will be used with the distributed term. In this case
the distibuted term can be shoved down into the bag below (by making it
the initial value of the numeric bag). Mulbuild and plusbuild add whatever
comes back from this to the accumulators. There is a decision here
concerning which bag (symbolic or numeric) it goes in. If evaluation works
on the incoming numeric bag (Ltag) and the element then this gives a new
value for this bag (Rtag). Otherwise it will be put into the symbolic bag.
There is a special case here for constructing with (previously) empty
bags. (Not wanting explicit tail markers, like [] in lists, makes things
slightly harder here).
Exptidy is simpler in that it only recursively sweeps one side. Note that
it uses multidy so that all the possible multiplication bags on the
right hand side of the exp chain will get packed into one. Since this a
right to left sweep down the chain there will be some reordering of
elements from the original. (However, they are changing from exp chains
to mul bags as well - so it's not important). The bottom left term in the
chain comes out as the base of course. Thus exptidy has this extra result.
The various ...fin routines take the final (accumulator) symbolic and
numeric bags and produce a final term. There are various things going
om here: Simplification rules get applied, empty symbolic bags disappear
and so forth. Mulfin and plusfin check to see if the symbolic bag is a
number, because I also want to be able to use them to glue arbitrary bits
together (current example: the use of mulfin in p2tidy). Expfin combines
bits of exponential stuff with bits of multiplication stuff (since the
base is to be raised to a mul bag). This makes it a bit more complicated.
In general one can make use of the zero element reduction to completely
elininate the need to look at certain bits of the tree. In this
implementation we would spot that the numeric bag (eg Ltag) had become
the zero element, and we could then return a result without looking any
further. This further optimisation is left as an exercise for the reader.
*/
% @@@ (Marker - Ie, easy to find string)
%% Top Level %%
% Tidy top level
tidy(X,Ans) :- dotidy(X,Y), !, Ans = Y.
tidy(X,X)
:- ttynl, display('** TIDY error: '), ttyprint(X),
ttynl, display(' (trace and continuing...)'), ttynl,
trace.
% New Thingy for when variables are allowed.
% Implemented very badly at the moment - should
% be improved (v slow, O(n^2)).
tidy_withvars(X,Ans) :-
variables(X,Vlist),
t_wvhack(Vlist,1,Subst1,Subst2),
subst(Subst1,X,X0),
tidy(X0,Ans0),
subst(Subst2,Ans0,Ans).
t_wvhack([],_,true,true).
t_wvhack([V],N,(V='$tidyv'(N)),('$tidyv'(N)=V)) :- !.
t_wvhack([V|Vrest],N,(V='$tidyv'(N))&SRest1,('$tidyv'(N)=V)&SRest2) :-
N1 is N+1,
t_wvhack(Vrest,N1,SRest1,SRest2).
% The general tidy routine
% Dispatches on special bag types (or logical ops)
% otherwise just tidies arguments recursively
% and then attempts evaluation.
dotidy(V,V) :- var(V), !, tidy_varerr.
dotidy(X,X) :- simple(X), !.
dotidy(Expr,Ans) :- % Top down application of simplification
apply_simplification(Expr,NewExpr),
!,
dotidy(NewExpr,Ans).
dotidy(A&B,Ans)
:- !,
dotidy(A,Ans1),
dotidy(B,Ans2),
andfin(Ans1,Ans2,Ans).
dotidy(A#B,Ans)
:- !,
dotidy(A,Ans1),
dotidy(B,Ans2),
orfin(Ans1,Ans2,Ans).
dotidy(X,Ans)
:- mulbag(X),
!,
multidy(X,1,empty,1,Right,Rtag),
mulfin(Rtag,Right,Ans).
dotidy(X,Ans)
:- plusbag(X),
!,
plustidy(X,1,empty,0,Right,Rtag),
plusfin(Rtag,Right,Ans).
dotidy(X,Ans)
:- expbag(X),
!,
exptidy(X,empty,1,Mult,Mtag,Base),
expfin(Mult,Mtag,Base,Ans).
dotidy(X,Newans)
:- functor(X,Fn,Arity),
functor(Ans,Fn,Arity),
tidyall(Arity,X,Ans,win,Flag),
try_eval(Flag,Ans,Newans).
% Simple things are always tidiest
simple(X) :- (atomic(X) ; number(X)), !.
% Tidy all the arguments of a term to
% give some new term. Keep track of whether
% or not all the tidied arguments are
% numbers.
tidyall(0,_,_,Flag,Flag) :- !.
tidyall(N,X,Ans,Flag,FinalFlag)
:- arg(N,X,Arg),
arg(N,Ans,Narg),
N1 is N-1,
dotidy(Arg,Narg),
chknum(Flag,Narg,Flag2),
tidyall(N1,X,Ans,Flag2,FinalFlag).
% Maintain number checking flag
chknum(lose,_,lose).
chknum(win,X,win) :- number(X), !.
chknum(win,_,lose).
% Try to evaluate non bag function
% Eval should just return the structure if it
% can't do the arithmetic
% We also try to simplify the result - this is the
% bottom up application of the simplify axioms. Note
% that this bottom up application is only being
% applied to non-bag functors (This should be fixed).
try_eval(lose,X,Y) :- apply_simplification(X,Y),!.
try_eval(lose,X,X).
try_eval(win,X,Y) :- eval(X,Y).
%% Simplification %%
% Just use the axioms if they exist.
apply_simplification(X,Y) :- simplify_axiom(X,Y), !.
%% Bag Sweeping %%
% Types of operation to which bag collecting
% is applicable.
mulbag(A*B).
mulbag(A/B).
plusbag(A+B).
plusbag(A-B).
plusbag(-(A)).
expbag(A^B).
% Collecting a multiplication bag together
multidy(V,_,_,_,_,_) :- var(V), !, tidy_varerr.
multidy(A*B,Distr,Left,Ltag,Right,Rtag)
:- !,
multidy(A,Distr,Left,Ltag,Q,Qtag),
multidy(B,Distr,Q,Qtag,Right,Rtag).
multidy(A/B,Distr,Left,Ltag,Right,Rtag)
:- !,
multidy(A,Distr,Left,Ltag,Q,Qtag),
distr_inverse(Distr,Idistr),
multidy(B,Idistr,Q,Qtag,Right,Rtag).
multidy(X,Distr,Left,Ltag,Right,Rtag)
:- m2tidy(X,Distr,Q),
mulbuild(Q,Left,Ltag,Right,Rtag).
m2tidy(E,Distr,Ans)
:- expbag(E),
!,
exptidy(E,empty,Distr,Result,Tag,Base),
expfin(Result,Tag,Base,Ans).
m2tidy(X,1,Ans)
:- !,
dotidy(X,Ans).
m2tidy(X,Distr,Ans)
:- dotidy(X,Result),
expfin(empty,Distr,Result,Ans).
% Build mul bags with various special cases
% handled.
mulbuild(N,Left,Ltag,Left,Rtag)
:- number(N),
multiply(N,Ltag,Rtag),
!.
mulbuild(X,empty,Ltag,X,Ltag) :- !.
mulbuild(X,Left,Ltag,Left*X,Ltag).
% Collecting a plus bag together
plustidy(V,_,_,_,_,_) :- var(V), !, tidy_varerr.
plustidy(A+B,Distr,Left,Ltag,Right,Rtag)
:- !,
plustidy(A,Distr,Left,Ltag,Q,Qtag),
plustidy(B,Distr,Q,Qtag,Right,Rtag).
plustidy(A-B,Distr,Left,Ltag,Right,Rtag)
:- !,
plustidy(A,Distr,Left,Ltag,Q,Qtag),
distr_inverse(Distr,Idistr),
plustidy(B,Idistr,Q,Qtag,Right,Rtag).
plustidy(-(A),Distr,Left,Ltag,Right,Rtag)
:- !,
distr_inverse(Distr,Idistr),
plustidy(A,Idistr,Left,Ltag,Right,Rtag).
plustidy(X,Distr,Left,Ltag,Right,Rtag)
:- p2tidy(X,Distr,Q),
plusbuild(Q,Left,Ltag,Right,Rtag).
p2tidy(M,Distr,Ans)
:- mulbag(M),
!,
multidy(M,1,empty,Distr,Result,Tag),
mulfin(Tag,Result,Ans).
p2tidy(X,1,Ans)
:- !,
dotidy(X,Ans).
p2tidy(X,Distr,Ans)
:- dotidy(X,Result),
mulfin(Distr,Result,Ans).
% Build plus bags with various special cases
% handled.
plusbuild(N,Left,Ltag,Left,Rtag)
:- number(N),
add(N,Ltag,Rtag),
!.
plusbuild(X,empty,Ltag,X,Ltag) :- !.
plusbuild(X,Left,Ltag,Left+X,Ltag).
% Collecting together exp bags
exptidy(V,_,_,_,_,_) :- var(V), !, tidy_varerr.
exptidy(A^B,Right,Rtag,Left,Ltag,Base)
:- !,
multidy(B,1,Right,Rtag,Q,Qtag),
exptidy(A,Q,Qtag,Left,Ltag,Base).
exptidy(X,Right,Rtag,Right,Rtag,Base)
:- dotidy(X,Base).
% Inverting factors being distributed
distr_inverse(1,-1).
distr_inverse(-1,1).
%% Finalising Structures %%
% Final AND building
andfin(false,X,false) :- !. % Zero element
andfin(true,X,X) :- !. % Unit element
andfin(X,false,false) :- !. % Zero element
andfin(X,true,X) :- !. % Unit element
andfin(X,X,X) :- !. % Merging of identical elements
andfin(X,Y,X&Y). % General case
% Final OR building
orfin(true,X,true) :- !. % Zero element
orfin(false,X,X) :- !. % Unit element
orfin(X,true,true) :- !. % Zero element
orfin(X,false,X) :- !. % Unit element
orfin(X,X,X) :- !. % Merging of identical elements
orfin(X,Y,X#Y). % General case
% Final multiplication building
mulfin(0,_,0) :- !. % Zero element
mulfin(N,empty,N) :- !. % Completely evaluated
mulfin(1,X,X) :- !. % Unit element
mulfin(N,N2,Ans) % Further evaluation possible
:- number(N2),
multiply(N,N2,Ans),
!.
mulfin(N,Bag*N2,Ans) % Caught a nested mult bag
:- number(N2),
multiply(N,N2,N3),
mulfin(N3,Bag,Ans),
!.
mulfin(N,X,X*N). % General case
% Final plus building
plusfin(N,empty,N) :- !. % Completely evaluated
plusfin(0,X,X) :- !. % Unit element
plusfin(N,N2,Ans) % Further evaluation possible
:- number(N2),
add(N,N2,Ans),
!.
plusfin(N,Bag+N2,Ans) % Caught a nested plus bag!
:- number(N2),
add(N,N2,N3),
plusfin(N3,Bag,Ans),
!.
plusfin(N,X,X+N). % General case
% Final exp building
expfin(_,0,_,1) :- !. % E^0 -> 1
expfin(_,_,0,0) :- !. % 0^X -> 0
expfin(empty,N,E,Ans) % special empty bag cases
:- !,
n_expfin(N,E,Ans).
expfin(Bag,1,E,E^Bag) :- !. % case with bag unit element
expfin(Bag,N,E,Z^Bag) % E^(Bag*N) -> (E^N)^Bag
:- number(E), % providing E^N will evaluate
power(E,N,Z),
!.
expfin(Bag,N,E,E^(Bag*N)). % General case
% special exp cases for when the symbolic
% bag is empty
n_expfin(1,E,E) :- !. % E^1 -> E
n_expfin(N,E,Ans) % E^N evaluates
:- number(E),
power(E,N,Ans),
!.
n_expfin(N,E,E^N). % General case for empty bag
%% Junk %%
% Produce an error message and fail (when
% variables are found).
% The failure will trip the Tidy top level
% error message (who throws a nl for us).
tidy_varerr :- ttynl, display('** Prolog variable in expression'), fail.