reduce-historical/r38/packages/redlog/dvfsf.red

% ----------------------------------------------------------------------
% $Id: dvfsf.red,v 1.16 2002/05/28 13:21:56 sturm Exp $
% ----------------------------------------------------------------------
% Copyright (c) 1995-1999 Andreas Dolzmann and Thomas Sturm
% ----------------------------------------------------------------------
% $Log: dvfsf.red,v $
% Revision 1.16  2002/05/28 13:21:56  sturm
% Added black box rl_fbqe() and corresponding switch rlqefb.
% That is, for ofsf, rlqe uses rlcad in case of failure now.
%
% Revision 1.15  1999/05/06 12:18:37  sturm
% Updated comments for exported procedures.
%
% Revision 1.14  1999/03/23 15:10:45  dolzmann
% Fixed a bug in dvfsf_enter.
%
% Revision 1.13  1999/03/23 08:44:16  dolzmann
% Changed copyright information.
% Added list of exported procedures.
%
% Revision 1.12  1999/03/22 12:37:51  dolzmann
% Adapted procedure dvfsf_enter to the protocol required from the new rl_set.
%
% Revision 1.11  1999/03/21 13:35:40  dolzmann
% Corrected comments.
% Added black box implementation dvfsf_subsumption.
% Use property number!-of!-args instead of num!-of!-args.
% Use new procedure dvfsf_chsimpat instead of dvfsf_chsimpat. The AM
% interface allows now the input of relation chains.
% Fixed a bug in dvfsf_simpat: The AM interface now handles rationals
% correct.
% Added procedure dvfsf_opp.
% Added package dvfsfsism.
% Register dvfsf-code instead of cl-code for smart simplification.
% Added switch rlsusi.
%
% Revision 1.10  1999/03/19 18:34:42  dolzmann
% Added services rl_varl, rl_fvarl, and rl_bvarl.
%
% Revision 1.9  1999/03/19 15:50:31  dolzmann
% Added service rlifacml.
%
% Revision 1.8  1999/03/19 15:20:51  dolzmann
% Added service rl_subfof.
%
% Revision 1.7  1999/03/19 12:17:47  dolzmann
% Added service rlmkcanonic.
%
% Revision 1.6  1999/01/17 16:21:42  dolzmann
% Added services rl_explats, rl_termml, rl_terml, rl_struct, and
% rl_ifstruct.
% Added black boxes rl_termmlat, rl_structat, and rl_ifstructat.
% Added procedure dvfsf_simpterm.
% Removed unused properties simptermfn, mktermfn, and preptermfn from
% context tag.
% Added properties rl_prepterm, and rl_simpterm.
% Added fluid binding for switches rlsiexpl, rlsiexpla, and rlsifac.
% Changed copyright notice.
%
% Revision 1.5  1999/01/10 11:13:03  sturm
% Added black box rl_specelim (cl_specelim).
% Added service rlqea.
%
% Revision 1.4  1997/11/03 15:11:21  sturm
% Added BB implementation dvfsf_a2cdl and services rl_tab, rlitab,
% and rl_atab.
% Turned on BFS for QE by default.
%
% Revision 1.3  1996/09/30 12:38:12  sturm
% Fixed some comments for automatic processing.
%
% Revision 1.2  1996/07/13 11:51:34  dolzmann
% Pakage dvfsf now uses context independent smart simplification facilities
% of cl.
% Removed control of switch rlsism.
% Set servives rl_dnf and rl_cnf to dvfsf_dnf and dvfsf_cnf respectively.
% Package dvfsf now uses cl black box implementations for black boxes
% rl_sacatlp and rl_sacat.
%
% Revision 1.1  1996/07/08 12:15:19  sturm
% Initial check-in.
%
% ----------------------------------------------------------------------
lisp <<
   fluid '(dvfsf_rcsid!* dvfsf_copyright!*);
   dvfsf_rcsid!* := "$Id: dvfsf.red,v 1.16 2002/05/28 13:21:56 sturm Exp $";
   dvfsf_copyright!* := "Copyright (c) 1995-1999 by A. Dolzmann and T. Sturm"
>>;

module dvfsf;
% Discretely valued field standard form. Main module. Algorithms on
% first-order formulas over the language of fields together with a
% constant [p] and binary relations [equal], [neq], [div], [sdiv],
% [assoc], and [nassoc]. The terms are SF's.

create!-package('(dvfsf dvfsfsiat dvfsfsism dvfsfqe dvfsfmisc),nil);

load!-package 'cl;
load!-package 'rltools;

exports dvfsf_enter,dvfsf_exit,dvfsf_simpterm,dvfsf_prepat,dvfsf_resimpat,
   dvfsf_lengthat,dvfsf_chsimpat,dvfsf_simpat,dvfsf_op,dvfsf_arg2l,dvfsf_arg2r,
   dvfsf_argn,dvfsf_mk2,dvfsf_0mk2,dvfsf_mkn,dvfsf_opp,dvfsf_simplat1,
   dvfsf_smupdknowl,dvfsf_smrmknowl,dvfsf_smcpknowl,dvfsf_smmkatl,
   dvfsf_susirmknowl,dvfsf_varsel,dvfsf_translat,dvfsf_elimset,dvfsf_qesubcq,
   dvfsf_qesubq,dvfsf_transform,dvfsf_trygauss,dvfsf_qemkans,
   dvfsf_ordatp,dvfsf_varlat,dvfsf_varsubstat,dvfsf_negateat,dvfsf_fctrat,
   dvfsf_dnf,dvfsf_cnf,dvfsf_subsumption,dvfsf_a2cdl,dvfsf_subat,dvfsf_subalchk,
   dvfsf_eqnrhskernels,dvfsf_structat,dvfsf_ifstructat,dvfsf_termmlat,
   dvfsf_explats,dvfsf_mkcanonic;

imports rltools,cl;

fluid '(!*rlverbose dvfsf_p!* !*rlsiexpl !*rlsiexpla !*rlsifac !*rlsusi);

flag('(dvfsf),'rl_package);

% Parameters
put('dvfsf,'rl_params,'(
   (rl_smupdknowl!* . dvfsf_smupdknowl)
   (rl_smrmknowl!* . dvfsf_smrmknowl)
   (rl_smcpknowl!* . dvfsf_smcpknowl)
   (rl_smmkatl!* . dvfsf_smmkatl)
   (rl_smsimpl!-impl!* . cl_smsimpl!-impl)
   (rl_smsimpl!-equiv1!* . cl_smsimpl!-equiv1)
   (rl_sacatlp!* . cl_sacatlp)
   (rl_sacat!* . cl_sacat)
   (rl_ordatp!* . dvfsf_ordatp)
   (rl_tordp!* . ordp)
   (rl_simplat1!* . dvfsf_simplat1)
   (rl_negateat!* . dvfsf_negateat)
   (rl_varlat!* . dvfsf_varlat)
   (rl_varsubstat!* . dvfsf_varsubstat)
   (rl_translat!* . dvfsf_translat)
   (rl_transform!* . dvfsf_transform)
   (rl_elimset!*. dvfsf_elimset)
   (rl_trygauss!* . dvfsf_trygauss)
   (rl_subsumption!* . dvfsf_subsumption)
   (rl_bnfsimpl!* . cl_bnfsimpl)
   (rl_fctrat!* . dvfsf_fctrat)
   (rl_varsel!* . dvfsf_varsel)
   (rl_a2cdl!* . dvfsf_a2cdl)
   (rl_qemkans!* . dvfsf_qemkans)
   (rl_termmlat!* . dvfsf_termmlat)
   (rl_structat!* . dvfsf_structat)
   (rl_ifstructat!* . dvfsf_ifstructat)
   (rl_subat!* . dvfsf_subat)
   (rl_subalchk!* . dvfsf_subalchk)
   (rl_eqnrhskernels!* . dvfsf_eqnrhskernels)
   (rl_susipost!* . dvfsf_susipost)
   (rl_susitf!* . dvfsf_susitf)
   (rl_susibin!* . dvfsf_susibin)
   (rl_specelim!* . cl_specelim)
   (rl_fbqe!* . cl_fbqe)));

% Switches
put('dvfsf,'rl_cswitches,'(
   (rlqeheu . nil)
   (rlqedfs . nil)
   (rlsusi . T)
));

% Services
put('dvfsf,'rl_services,'(
   (rl_subfof!* . cl_subfof)
   (rl_identifyonoff!* . cl_identifyonoff)
   (rl_simpl!* . cl_simpl)
   (rl_nnf!* . cl_nnf)
   (rl_nnfnot!* . cl_nnfnot)
   (rl_pnf!* . cl_pnf)
   (rl_cnf!* . dvfsf_cnf)
   (rl_dnf!* . dvfsf_dnf)
   (rl_all!* . cl_all)
   (rl_ex!* . cl_ex)
   (rl_atnum!* . cl_atnum)
   (rl_ifacl!* . cl_ifacl)
   (rl_ifacml!* . cl_ifacml)
   (rl_matrix!* . cl_matrix)
   (rl_apnf!* . cl_apnf)
   (rl_atml!* . cl_atml)
   (rl_atl!* . cl_atl)
   (rl_qe!* . cl_qe)
   (rl_qeipo!* . cl_qeipo)
   (rl_qews!* . cl_qews)
   (rl_qea!* . cl_qea)
   (rl_tab!* . cl_tab)
   (rl_atab!* . cl_atab)
   (rl_termml!* . cl_termml)
   (rl_terml!* . cl_terml)
   (rl_varl!* . cl_varl)
   (rl_fvarl!* . cl_fvarl)
   (rl_bvarl!* . cl_bvarl)
   (rl_struct!* . cl_struct)
   (rl_ifstruct!* . cl_ifstruct)
   (rl_explats!* . dvfsf_explats)
   (rl_mkcanonic!* . dvfsf_mkcanonic)
   (rl_itab!* . cl_itab)));

% Admin
put('dvfsf,'rl_enter,'dvfsf_enter);
put('dvfsf,'rl_exit,'dvfsf_exit);

put('dvfsf,'simpfnname,'dvfsf_simpfn);

put('dvfsf,'rl_prepat,'dvfsf_prepat);
put('dvfsf,'rl_resimpat,'dvfsf_resimpat);
put('dvfsf,'rl_lengthat,'dvfsf_lengthat);

put('dvfsf,'rl_prepterm,'prepf);
put('dvfsf,'rl_simpterm,'dvfsf_simpterm);

algebraic infix equal;
put('equal,'dvfsf_simpfn,'dvfsf_chsimpat);
put('equal,'number!-of!-args,2);

algebraic infix neq;
put('neq,'dvfsf_simpfn,'dvfsf_chsimpat);
put('neq,'number!-of!-args,2);
put('neq,'rtypefn,'quotelog);
newtok '((!< !>) neq);

algebraic infix sdiv;
put('sdiv,'dvfsf_simpfn,'dvfsf_chsimpat);
put('sdiv,'number!-of!-args,2);
put('sdiv,'rtypefn,'quotelog);
precedence sdiv,neq;
newtok '((| |) sdiv);

algebraic infix div;
put('div,'dvfsf_simpfn,'dvfsf_chsimpat);
put('div,'number!-of!-args,2);
put('div,'rtypefn,'quotelog);
precedence div,sdiv;
newtok '((|) div);

algebraic infix assoc;
put('assoc,'dvfsf_simpfn,'dvfsf_chsimpat);
put('assoc,'number!-of!-args,2);
put('assoc,'rtypefn,'quotelog);
precedence assoc,div;
newtok '((~) assoc);

algebraic infix nassoc;
put('nassoc,'dvfsf_simpfn,'dvfsf_chsimpat);
put('nassoc,'number!-of!-args,2);
put('nassoc,'rtypefn,'quotelog);
precedence nassoc,assoc;
newtok '((/ ~) nassoc);

flag('(equal neq sdiv div assoc nassoc),'spaced);

flag('(dvfsf_chsimpat),'full);

procedure dvfsf_enter(argl);
   % Discretely valued field enter context. [argl] is either [nil] or
   % it evaluates to a list containing an integer $n$ such that $n=0$
   % or $|n|$ prime. Returns a pair $(f . l)$; if $f$ is [nil], then
   % $l$ contains an error message; if $f$ is non-[nil], then $l$ is
   % the new value for the fluid [rl_argl!*]. Modifies the algebraic
   % variable [p] and the fluid [dvfsf_p!*]. The argument $n$
   % describes the range of considered $p$-adic valuations for
   % elimination and simplification. With $n=0$ these functions are
   % uniformly correct for all $p$-adic valuations; with $n<0$ they
   % are correct for all $p$-adic valuations with $p \leq |n|$. For
   % $n>0$ the $n$-adic valuation is selected, and both the algebraic
   % variable [p] and the fluid [dvfsf_p!*] are set to $n$; then
   % simplification and quantifier elimination are correct only for
   % this $n$-adic valuation.
   begin scalar n;
      n := if argl then reval car argl else 0;
      if argl and cdr argl then <<
	 lprim {"extra",ioto_cplu("argument",cddr argl),"ignored"};
	 argl := {car argl}
      >>;
      if not (n=0 or primep n) then
 	 return nil . "dvfsf extra argument must be 0 or prime";
      if n <= 0 then <<
	 lprim "p is being cleared";
      	 clear 'p;
      >> else <<
	 lprim {"p is set to",n};
      	 algebraic(p := n);
      >>;
      flag('(p),'reserved);
      dvfsf_p!* := n;
      return T . argl
   end;

procedure dvfsf_exit();
   % Discretely valued field exit context. No arguments. The return
   % value is unspecified. Modified the algebraic variable [p].
   <<
      remflag('(p),'share);
      remflag('(p),'reserved)
   >>;

procedure dvfsf_simpterm(u);
   % Discretely valued field simp term. [u] is Lisp Prefix. Returns
   % the [u] as a DVFSF term.
   numr simp u;

procedure dvfsf_prepat(f);
   % Discretely valued field prep atomic formula. [f] is a DVFSF
   % atomic formula. Returns [f] in Lisp prefix form.
   {dvfsf_op f,prepf dvfsf_arg2l f,prepf dvfsf_arg2r f};

procedure dvfsf_resimpat(f);
   % Discretely valued field resimp atomic formula. [f] is an DVFSF
   % atomic formula. Returns the atomic formula [f] with resimplified
   % terms.
   dvfsf_mk2(dvfsf_op f,
      numr resimp !*f2q dvfsf_arg2l f,numr resimp !*f2q dvfsf_arg2r f);

procedure dvfsf_lengthat(f);
   % Discretely valued field length of atomic formula. [f] is an
   % atomic formula. Returns a number, the length of [f].
   2;

procedure dvfsf_chsimpat(u);
   % Discretely valued field chain simp atomic formula. [u] is the
   % Lisp prefix representation of a chain of atomic formulas, i.e.,
   % the operators are nested right associatively. Returns a formula,
   % which is the corresponding conjunction.
   rl_smkn('and,for each x in dvfsf_chsimpat1 u collect dvfsf_simpat x);

procedure dvfsf_chsimpat1(u);
   % Discretely valued field chain simp atomic formula subroutine. [u]
   % is the Lisp prefix representation of a chain of atomic formulas,
   % i.e., the operators are nested right associatively.
   begin scalar leftl,rightl,lhs,rhs;
      lhs := cadr u;
      if pairp lhs and dvfsf_opp car lhs then <<
	 leftl := dvfsf_chsimpat1 lhs;
	 lhs := caddr lastcar leftl
      >>;
      rhs := caddr u;
      if pairp rhs and dvfsf_opp car rhs then <<
	 rightl := dvfsf_chsimpat1 rhs;
	 rhs := cadr car rightl
      >>;
      return nconc(leftl,{car u,lhs,rhs} . rightl)
   end;

procedure dvfsf_simpat(u);
   % Discretely valued field simp atomic formula. [u] is Lisp prefix.
   % Returns [u] as an atomic formula.
   begin scalar op,lhs,rhs,w;
      op := car u;
      lhs := simp cadr u;
      if not (numberp denr lhs) then
 	 typerr(u,"atomic formula");
      rhs := simp caddr u;
      if not (numberp denr rhs) then
 	 typerr(u,"atomic formula");
      if op memq '(equal neq) then
      	 return dvfsf_0mk2(op,numr subtrsq(lhs,rhs));
      w := lcm(denr lhs,denr rhs);
      return dvfsf_mk2(op,numr multsq(lhs,!*f2q w),numr multsq(rhs,!*f2q w))
   end;

procedure dvfsf_op(atf);
   % Discretely valued field operator. [atf] is an atomic formula
   % $R(t_1,t_2)$. Returns $R$.
   car atf;

procedure dvfsf_arg2l(atf);
   % Discretely valued field binary operator left hand side argument.
   % [atf] is an atomic formula $R(t_1,t_2)$. Returns $t_1$.
   cadr atf;

procedure dvfsf_arg2r(atf);
   % Discretely valued field binary operator right hand side argument.
   % [atf] is an atomic formula $R(t_1,t_2)$. Returns $t_2$.
   caddr atf;

procedure dvfsf_argn(atf);
   % Discretely valued field n-ary operator argument list. [atf] is an
   % atomic formula $R(t_1,...,t_n)$. Returns the list
   % $(t_1,...,t_n)$.
   {cadr atf,caddr atf};

procedure dvfsf_mk2(op,lhs,rhs);
   % Discretely valued field make atomic formula for binary operator.
   % [op] is one of the operators [equal], [neq], [div], [sdiv],
   % [assoc], and [nassoc]; [lhs] and [rhs] are terms. Returns the
   % atomic formula $[op]([lhs],[rhs])$.
   {op,lhs,rhs};

procedure dvfsf_0mk2(op,lhs);
   % Discretely valued field make zero right hand atomic formula for
   % binary operator. [op] is one of the operators [equal], [neq],
   % [div], [sdiv], [assoc], and [nassoc]; [lhs] is a term. Returns
   % the atomic formula $[op]([lhs],0)$.
   {op,lhs,nil};

procedure dvfsf_mkn(op,argl);
   % Discretely valued field make atomic formula for n-ary operator.
   % [op] is one of the operators [equal], [neq], [div], [sdiv],
   % [assoc], and [nassoc]; [argl] is a list $(t_1,t_2)$ of terms.
   % Returns the atomic formula $[op](t_1,t_2)$.
   {op,car argl,cadr argl};

procedure dvfsf_opp(op);
   % Discretely valued field operator predicate. [op] is an
   % S-expression. Returns non-[nil] iff op is a relation.
   op memq '(equal neq div sdiv assoc nassoc);

endmodule;  % [dvfsf]

end;  % of file