Logical Optimization (1)

% reduce.pl % things we can run at load time. % unification can happen right now. reduce(X = X, true). % if we have enough info to do % a calculation, do it now reduce(X is Y,true) :- ground(Y), X is Y. % lists can be appended if % the lists are defined enoug % at runtime reduce(append(L1,L2,L3),true) :- proper_list(L1), proper_list(L2), append(L1,L2,L3). % univs can be called at % runtime, if the list is % well-defined and the head is % bound reduce(Term =.. [H|T],true) :- proper_list(T), ground(H), Term =.. [H|T]. % if there is only one fact % for X, we can call it at % compile time reduce(X,true) :- singleton(X), clause(X,true). % if there is only one rule % that defines X, we can ust % swap the head for the rule % body. reduce(X,Y) :- singleton(X), clause(X,Y). singleton(X) :- \+ predicate_property(X,built_in), findall(Y,clause(X,Y),[_]).

tidyTrue.pl=

% tidy.pl % author= lindsay mason & timm % "reduce"drops in all these bogus "true" % sub-goals. tidy removes these "true"s. tidy(A,B) :- once(tidy1(A,B)). tidy1(A, A) :- var(A). tidy1((A :- true), A). tidy1((A :- B), Out) :- tidy(B,TB), (TB=true -> Out = A; Out=(A :- TB)). tidy1((A,B), (A,TB)) :- var(A), tidy(B,TB). tidy1((A,B), (TA,B)) :- var(B), tidy(A,TA). tidy1(((A,B),C), R) :- tidy((A,B,C), R). tidy1((true,A), R) :- tidy(A,R). tidy1((A,true), R) :- tidy(A,R). tidy1((A,B), Out) :- tidy(A,TA), tidy(B,TB), (TB=true -> Out=TA ; Out=(TA,TB)). tidy1((A;B), (TA;TB)) :- tidy(A,TA), tidy(B,TB). tidy1((A->B), (TA->TB)) :- tidy(A,TA), tidy(B,TB). tidy1((\+ A), (\+ TA)) :- tidy(A,TA). tidy1(A, A).

fastereg1.pl=

% fastereg1.pl `twoPi(TwoPi) :- TwoPi is 2*pi. `area(R,A) :- twoPi(X), A is R * X. `volume(H,R,V) :- area(R,A), V is H * A. `myVolume(V) :- volume(10,1,V). `combine(F,A,Val1,Val2,Term) :- append([F,A],[Val1,Val2],L), % this is a great predicate to % to optimize away Term =.. L. `myCombine(L) :- combine(ff,aa,10,10,L).

faster1.out=

% output from faster1.pl twoPi(6.28319). area(A, B) :- B is A*6.28319. volume(A, B, C) :- D is B*6.28319, C is A*D. myVolume(62.8319). combine(A, B, C, D, E) :- E=..[A, B, C, D]. myCombine(ff(aa, 10, 10)).

faster1.pl=

% faster.pl % an optimizer using a meta-interpreter. % things that can be reduced, are % reduced. :- [lib], -[demos,reduce,tidyTrue]. :- op(999,xfx,`), op(998,fx,`). demof :- demos(faster1). demo1 :- listing([twoPi, area, volume, myVolume,combine, myCombine ]). % potentinal of prolog- write the interpreter % and AUTOMATICALLY generate the compiler % PE= partial evaluation: perform as much of % the calculation as allowed by the inputs. % residual = pe(program, inputs) % where residual is a new program specialized % by the inputs from the old program. % general computation is just a special case % of pe where the residual is (e.g.) a single % number. % logical optimization = hook term_expansion % into a partial evaluator term_expansion((`X:-Y),Z) :- faster(X,Y,Z). faster(X,Y0,Z) :- pe(Y0,Y1), tidy((X :- Y1),Z). % standard top-down parser. % once(X) :- X,!. % only have 1 solution. pe(X,Y) :- once(pe1(X,Y)). % standard base cases % 1) don't let vars fall into the % rest of stuff pe1(X, X) :- var(X). % 2) true- just end. pe1(true, true). % pe on all parts of an "or" pe1((A0;B0),(A;B)) :- pe(A0,A), pe(B0,B). % pe on all parts of an "and" pe1((A0,B0),(A,B)) :- pe(A0,A), pe(B0,B). % if not inside an "and" or an "or", % try reducing it pe1(X, Y) :- % if reduce works, pe the % reduced stuff. note: % these means that our pe % chase multiple nested % definitions. reduce(X,Z), pe(Z,Y). % if none of the above- do nothing pe1(X, X). :- [fastereg1].

demos.pl=

% demos.pl % handle the generic demo stuff % run the demo predicate, saving output demos(F) :- sformat(Out,'~w.out',F), write(Out),nl, tell(Out), format('% output from ~w.pl\n',F), % never fail ignore(demo), told. % run through all the demo1's demo :- demo1,fail. demo.

Not © Tim Menzies, 2001 Share and enjoy- information wants to be free. But if you take anything from this site, please credit tim@menzies.com.