%WN051006 dropped in code, but interesting for case study 'order a list'

 %EqSystem.thy

 %---------------------------------------------------------------------------

 %

 % order'_system      :: "bool list => bool list " ("order'_system _")

 %

 %EqSystem.ML

 %---------------------------------------------------------------------------

 %(*("order_system", ("EqSystem.order'_system", 

 %                   eval_order_system "#eval_order_system_"))*)

 %fun eval_order_system _ "EqSystem.order'_system"

 %                         (p as (Const ("EqSystem.order'_system",_) $ ts)) _ =

 %    let val ts' = sort (ord_simplify_Integral_ false (assoc_thy"Isac.thy") [])

 %                (isalist2list ts)

 %       val ts'' = list2isalist HOLogic.boolT ts'

 %    in if ts <> ts''

 %       then Some (term2str p ^ " = " ^ term2str ts'',

 %              Trueprop $ (mk_equality (p,ts'')))

 %       else None

 %    end

 %  | eval_order_system _ _ _ _ = None;

 %

 %

 %"Script Norm2SystemScript (es_::bool list) (vs_::real list) = \

 %\  (let es__ = Try (Rewrite_Set simplify_Integral_parenthesized False) es_; \

 %\       es__ = (Try (Calculate order_system_) (order_system es__))\

 %\in (SubProblem (Biegelinie_,[linear,system],[no_met])\

 %\                  [bool_list_ es__, real_list_ vs_]))"

 %              ));

 %

 %eqsystem.sml

 %---------------------------------------------------------------------------

 %"----------- eval_sort -------------------------------------------";

 %"----------- eval_sort -------------------------------------------";

 %"----------- eval_sort -------------------------------------------";

 %val ts = TermC.parse_test @{context} "[c_2 = 0, -1 * (q_0 * L ^^^ 2) / 2 + (L * c + c_2) = 0]";

 %val ts' = sort (ord_simplify_Integral_ false (assoc_thy"Isac.thy") [])

 %              (isalist2list ts);

 %terms2str ts';

 %val ts'' = list2isalist HOLogic.boolT ts';

 %if term2str ts'' = "[-1 * (q_0 * L ^^^ 2) / 2 + (L * c + c_2) = 0, c_2 = 0]"

 %then () else raise error "eqsystem.sml eval_sort 1";

 %

 %val t = TermC.parse_test @{context} "order_system [c_2 = 0,\

 %                \-1 * (q_0 * L ^^^ 2) / 2 + (L * c + c_2) = 0]";

 %val Some (str,_) = eval_order_system "" "EqSystem.order'_system" t "";

 %if str = "order_system [c_2 = 0, -1 * (q_0 * L ^^^ 2) / 2 + (L * c + c_2) = 0] = [-1 * (q_0 * L ^^^ 2) / 2 + (L * c + c_2) = 0, c_2 = 0]" then ()

 %else raise error "eqsystem.sml eval_sort 2";

 %

 %

 %

 %  calculate_ thy ("EqSystem.order'_system", 

 %                 eval_order_system "#eval_order_system_") t;

 %

 %---------------------------------------------------------------------------

 %---------------------------------------------------------------------------

 %---------------------------------------------------------------------------

 %In the following this text is not compatible with isac-code:

 %* move termorder to knowledge: FIXXXmat0201a

 %

 %

 \documentclass[11pt,a4paper,headline,headcount,towside,nocenter]{report}

 \usepackage{latexsym}           % recommended by Ch.Schinagl 10.98

 \bibliographystyle{alpha}

 \def\isac{${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$}

 \title{\isac --- Interface for\\

   Developers of Math Knowledge\\[1.0ex]

   and\\[1.0ex]

   Tools for Experiments in\\

   Symbolic Computation\\[1.0ex]}

 \author{The \isac-Team\\

   \tt isac-users@ist.tugraz.at\\[1.0ex]}

 \date{\today}

 \begin{document}

 \maketitle

 \newpage

 \tableofcontents

 \newpage

 \listoftables

 \newpage

 \chapter{Introduction}

 \section{The scope of this document}

 \paragraph{As a manual:} This document describes the interface to \isac's kernel (KE), the interface to the mathematics engine (ME) included in the KE, and to the various tools like rewriting, matching etc.

 \isac's KE is written in SML, the language developed in conjunction with predecessors of the theorem prover Isabelle. Thus, in this document we use the plain ASCII representation of SML code. The reader may note that the \isac-user is presented a completely different view on a graphical user interface.

 The document is selfcontained; basic knowledge about SML (as an introduction \cite{Paulson:91} is recommended), terms and rewriting is assumed.

 %The interfaces will be moderately exended during the first phase of development of the mathematics knowledge. The work on the subprojects defined should {\em not} create interfaces of any interest to a user or another author of knowledge except identifiers (of type string) for theorems, rulesets etc.

 Notation: SML code, directories, file names are {\tt written in 'tt'}; in particular {\tt ML>} is the KE prompt.

 \paragraph{Give it a try !} Another aim of this text is to give the reader hints for experiments with the tools introduced.

 \section{Related documents}\label{related-docs}

 Isabelle reference manual \cite{Isa-ref}, also contained in the Isabelle distribution under $\sim${\tt /doc/}.

 {\bf The actual locations of files is being recorded in \\{\tt /software/services/isac/README}

 \footnote{The KEs current version is {\tt isac.020120-math/} which is based on the version Isabelle99 at {\tt http://isabelle.in.tum.de}.\\

 The current locations at IST are\\

 {\tt [isabelle]\hspace{3em}      /software/sol26/Isabelle99/}\\

 {\tt [isac-src]\hspace{3em}      /software/services/isac/src/ke/}\\ 

 {\tt [isac-bin]\hspace{3em}      /software/services/isac/bin/ke/}

 } 

 and rigorously updated.} In this document we refer to the following directories

 \begin{tabbing}

 xxx\=Isabelle sources1234 \=\kill

 \>Isabelle sources \> {\tt [isabelle]/}\\

 \>KE sources       \> {\tt [isac-src]/\dots{version}\dots/}\\

 \>KE binary        \> {\tt [isac-bin]/\dots{version}\dots/}

 \end{tabbing}

 where {\tt\dots version\dots} stands for a directory-name containing information on the version.

 \section{Getting started}

 Change to the directory {\tt [isac-bin]} where \isac's binary is located and type to the unix-prompt '$>$' (ask your system administrator where the directory {\tt [isac-bin]} is on your system):

 \begin{verbatim}

    > [isac-bin]/sml @SMLload=isac.020120-math

    val it = false : bool

    ML>

 \end{verbatim}

 yielding the message {\tt val it = false : bool} followed by the prompt of the KE. Having been successful so far, just type in the input presented below -- all of it belongs to {\em one} session~!

 \part{Experimental approach}

 \chapter{Basics, terms and parsing}

 Isabelle implements terms of the {\it simply typed lambda calculus} \cite{typed-lambda} defined in $\sim${\tt/src/Pure.ML}. 

 \section{The definition of terms}

 There are two kinds of terms in Isabelle, 'raw terms' and 'certified terms'. \isac{} works on raw terms, which are efficient but hard to comprehend. 

 {\footnotesize\begin{verbatim}

    datatype term = 

        Const of string * typ

      | Free  of string * typ 

      | Var   of indexname * typ

      | Bound of int

      | Abs   of string * typ * term

      | op $  of term * term;

    datatype typ = Type  of string * typ list

                 | TFree of string * sort

                 | TVar  of indexname * sort;

 \end{verbatim}}%size % $

 where the definitions of sort and indexname is not relevant in this context. The {\tt typ}e is being inferred during parsing. Parsing creates the other kind of terms, {\tt cterm}. These {\tt cterm}s are encapsulated records, which cannot be composed without the respective Isabelle functions (checking for type correctness), but which then are conveniently displayed as strings (using SML compiler internals -- see below).

 \section{Theories and parsing}

 Parsing uses information contained in Isabelles theories $\sim${\tt /src/HOL}. The currently active theory is held in a global variable {\tt thy}; theories can be accessed individually;

 {\footnotesize\begin{verbatim}

    ML> thy;

    val it =

      {ProtoPure, CPure, HOL, Ord, Set, subset, equalities, mono, Vimage, Fun,

        Prod, Lfp, Relation, Trancl, WF, NatDef, Gfp, Sum, Inductive, Nat, Arith,

        Divides, Power, Finite, Equiv, IntDef, Int, Univ, Datatype, Numeral, Bin,

        IntArith, WF_Rel, Recdef, IntDiv, NatBin, List, Option, Map, Record,

        RelPow, Sexp, String, Calculation, SVC_Oracle, Main, Zorn, Filter, PNat,

        PRat, PReal, RealDef, RealOrd, RealInt, RealBin, HyperDef, Descript, ListG,

        Tools, Script, Typefix, Atools, RatArith, SqRoot, Differentiate, DiffAppl,

        InsSort, Isac} : theory                                                    ML>

    ML> HOL.thy;

    val it = {ProtoPure, CPure, HOL} : theory 

    ML>

    ML> parse;

    val it = fn : theory -> string -> cterm option

    ML> parse thy "a + b * #3";

    val it = Some "a + b * #3" : cterm option

    ML>

    ML> val t = (term_of o the) it;

    val t = Const (#,#) $ Free (#,#) $ (Const # $ Free # $ Free (#,#)) : term

 \end{verbatim}}%size

 where {\tt term\_of} and {\tt the} are explained below. The syntax of the list of characters can be read out of Isabelles theories \cite{Isa-obj} {\tt [isabelle]/src/HOL/}\footnote{Or you may use your internetbrowser to look at the files in {\tt [isabelle]/browser\_info}.} 

 and from theories developed with in \isac{} at {\tt [isac-src]/knowledge/}. Note that the syntax of the terms is different from those displayed at \isac's frontend after conversion to MathML.

 \section{Displaying terms}

 The print depth on the SML top-level can be set in order to produce output in the amount of detail desired:

 {\footnotesize\begin{verbatim}

    ML> Compiler.Control.Print.printDepth;

    val it = ref 4 : int ref

    ML>

    ML> Compiler.Control.Print.printDepth:= 2;

    val it = () : unit

    ML> t;

    val it = # $ # $ (# $ #) : term

    ML>

    ML> Compiler.Control.Print.printDepth:= 6;

    val it = () : unit

    ML> t;

    val it =

      Const ("op +","[RealDef.real, RealDef.real] => RealDef.real") $

      Free ("a","RealDef.real") $

      (Const ("op *","[RealDef.real, RealDef.real] => RealDef.real") $

       Free ("b","RealDef.real") $ Free ("#3","RealDef.real")) : term

 \end{verbatim}}%size % $

 A closer look to the latter output shows that {\tt typ} is output as a string like {\tt cterm}. Other useful settings for the output are:

 {\footnotesize\begin{verbatim}

    ML> Compiler.Control.Print.printLength;

    val it = ref 8 : int ref

    ML> Compiler.Control.Print.stringDepth;

    val it = ref 250 : int ref

 \end{verbatim}}%size

 Anyway, the SML output of terms is not very readable; there are functions in the KE to display them:

 {\footnotesize\begin{verbatim}

    ML> atomt;

    val it = fn : term -> unit

    ML> atomt t; 

    *** -------------

    *** Const ( op +)

    *** . Free ( a, )

    *** . Const ( op *)

    *** . . Free ( b, )

    *** . . Free ( #3, )

    val it = () : unit

    ML>

    ML> TermC.atom_trace_detail \@\{context\};

    val it = fn : theory -> term -> unit

    ML> TermC.atom_trace_detail \@\{context\} t;

    *** -------------

    *** Const ( op +, [real, real] => real)

    *** . Free ( a, real)

    *** . Const ( op *, [real, real] => real)

    *** . . Free ( b, real)

    *** . . Free ( #3, real)

    val it = () : unit

 \end{verbatim}}%size

 where again the {\tt typ}s are rendered as strings, but more elegantly by use of the information contained in {\tt thy}..

 \paragraph{Give it a try !} {\bf The mathematics knowledge grows} as it is defined in Isabelle theory by theory. Have a look by your internet browser to the hierarchy of those theories at {\tt [isabelle]/src/HOL/HOL.thy} and its children available on your system. Or you may use your internetbrowser to look at the files in {\tt [isabelle]/browser\_info}.

 {\footnotesize\begin{verbatim}

    ML> (*-1-*) parse HOL.thy "#2^^^#3";

    *** Inner lexical error at: "^^^#3"

    val it = None : cterm option

    ML>

    ML> (*-2-*) parse HOL.thy "d_d x (a + x)";

    val it = None : cterm option

    ML>

    ML>

    ML> (*-3-*) parse RatArith.thy "#2^^^#3";

    val it = Some "#2 ^^^ #3" : cterm option

    ML>

    ML> (*-4-*) parse RatArith.thy "d_d x (a + x)";

    val it = Some "d_d x (a + x)" : cterm option

    ML>

    ML>

    ML> (*-5-*) parse Differentiate.thy "d_d x (a + x)";

    val it = Some "d_d x (a + x)" : cterm option

    ML>

    ML> (*-6-*) parse Differentiate.thy "#2^^^#3";

    val it = Some "#2 ^^^ #3" : cterm option

 \end{verbatim}}%size

 Don't trust the string representation: if we convert {\tt(*-4-*)} and {\tt(*-6-*)} to terms \dots

 {\footnotesize\begin{verbatim}

    ML> (*-4-*) val thy = RatArith.thy;

    ML> ((TermC.atom_trace_detail \@\{context\}) o term_of o the o (parse thy)) "d_d x (a + x)";

    *** -------------

    *** Free ( d_d, [real, real] => real)

    *** . Free ( x, real)

    *** . Const ( op +, [real, real] => real)

    *** . . Free ( a, real)

    *** . . Free ( x, real)

    val it = () : unit

    ML>

    ML> (*-6-*) val thy = Differentiate.thy;

    ML> ((TermC.atom_trace_detail \@\{context\}) o term_of o the o (parse thy)) "d_d x (a + x)";

    *** -------------

    *** Const ( Differentiate.d_d, [real, real] => real)

    *** . Free ( x, real)

    *** . Const ( op +, [real, real] => real)

    *** . . Free ( a, real)

    *** . . Free ( x, real)

    val it = () : unit

 \end{verbatim}}%size

 \dots we see: in {\tt(*-4-*)} we have an arbitrary function {\tt Free ( d\_d, \_)} and in {\tt(*-6-*)} we have the special function constant {\tt Const ( Differentiate.d\_d, \_)} for differentiation, which is defined in {\tt Differentiate.thy} and presumerably is meant.

 \section{Converting terms}

 The conversion from {\tt cterm} to {\tt term} has been shown above:

 {\footnotesize\begin{verbatim}

    ML> term_of;

    val it = fn : cterm -> term

    ML>

    ML> the;

    val it = fn : 'a option -> 'a

    ML>

    ML> val t = (term_of o the o (parse thy)) "a + b * #3";

    val t = Const (#,#) $ Free (#,#) $ (Const # $ Free # $ Free (#,#)) : term

 \end{verbatim}}%size

 where {\tt the} unwraps the {\tt term option} --- an auxiliary function from Larry Paulsons basic library at {\tt [isabelle]/src/Pure/library.ML}, which is really worthwile to study for any SML programmer.

 The other conversions are the following, some of which use the {\it signature} {\tt sign} of a theory:

 {\footnotesize\begin{verbatim}

    ML> sign_of;

    val it = fn : theory -> Sign.sg

    ML>

    ML> cterm_of;

    val it = fn : Sign.sg -> term -> cterm

    ML> val ct = cterm_of (sign_of thy) t;

    val ct = "a + b * #3" : cterm

    ML>

    ML> Sign.string_of_term;

    val it = fn : Sign.sg -> term -> string

    ML> Sign.string_of_term (sign_of thy) t;

    val it = "a + b * #3" : ctem'

    ML>

    ML> string_of_cterm;

    val it = fn : cterm -> string

    ML> string_of_cterm ct;

    val it = "a + b * #3" : ctem'

 \end{verbatim}}%size

 \section{Theorems}

 Theorems are a type, {\tt thm}, even more protected than {\tt cterms}: they are defined as axioms or proven in Isabelle. These definitions and proofs are contained in theories in the directory {\tt[isac-src]/knowledge/}, e.g. the theorem {\tt diff\_sum} in the theory {\tt[isac-src]/knowledge/Differentiate.thy}. Additionally, each theorem has to be recorded for \isac{} in the respective {\tt *.ML}, e.g. {\tt diff\_sum} in {\tt[isac-src]/knowledge/Differentiate.ML} as follows:

 {\footnotesize\begin{verbatim}

    ML> theorem' := overwritel (!theorem',

    [("diff_const",num_str diff_const)

    ]);

 \end{verbatim}}%size

 The additional recording of theorems and other values will disappear in later versions of \isac.

 \chapter{Rewriting}

 \section{The arguments for rewriting}

 The type identifiers of the arguments and values of the rewrite-functions in \ref{rewrite} differ only in an apostroph: the apostrohped types are re-named strings in order to maintain readability.

 {\footnotesize\begin{verbatim}

    ML> HOL.thy;

    val it = {ProtoPure, CPure, HOL} : theory

    ML> "HOL.thy" : theory';

    val it = "HOL.thy" : theory'

    ML>

    ML> sqrt_right;

    val it = fn : rew_ord (* term * term -> bool *)

    ML> "sqrt_right" : rew_ord;

    val it = "sqrt_right" : rew_ord

    ML>

    ML> eval_rls;

    val it =

      Rls

        {preconds=[],rew_ord=("sqrt_right",fn),

         rules=[Thm #,Thm #,Thm #,Thm #,Thm #,Thm #,Thm #,Thm #,

                Thm #,Thm #,Thm #,Thm #,Thm #,Calc #,Calc #,...],

         program=Script (Free #)} : rls

    ML> "eval_rls" : rls';

    val it = "eval_rls" : rls'

    ML>

    ML> diff_sum;

    val it = "d_d ?bdv (?u + ?v) = d_d ?bdv ?u + d_d ?bdv ?v" : thm

    ML> ("diff_sum", "") : thm';

    val it = ("diff_sum","") : thm'

 \end{verbatim}}%size

 where a {\tt thm'} is a pair, eventually with the string-representation of the respective theorem.

 \section{The functions for rewriting}\label{rewrite}

 Rewriting comes along with two equivalent functions, where the first is being actually used within the KE, and the second one is useful for tests: 

 {\footnotesize\begin{verbatim}

    ML> rewrite_;

    val it = fn

      : theory

        -> rew_ord

           -> rls -> bool -> thm -> term -> (term * term list) option

    ML>

    ML> rewrite;

    val it = fn

      : theory'

        -> rew_ord

           -> rls' -> bool -> thm' -> cterm' -> (cterm' * cterm' list) option

 \end{verbatim}}%size

 The arguments are the following:\\

 \tabcolsep=4mm

 \def\arraystretch{1.5}

 \begin{tabular}{lp{11.0cm}}

   {\tt theory}  & the Isabelle theory containing the definitions necessary for parsing the {\tt term} \\

   {\tt rew\_ord}& the rewrite order \cite{nipk:rew-all-that} for ordered rewriting -- see the section \ref{term-order} below. For {\em no} ordered rewriting take {\tt tless\_true}, a dummy order yielding true for all arguments \\

   {\tt rls}     & the rule set for evaluating the condition within {\tt thm} in case {\tt thm} is a conditional rule \\

   {\tt bool}    & a flag which triggers the evaluation of the eventual condition in {\tt thm}: if {\tt false} then evaluate the condition and according to the result of the evaluation apply {\tt thm} or not (conditional rewriting \cite{nipk:rew-all-that}), if {\tt true} then don't evaluate the condition, but put it into the set of assumptions \\

   {\tt thm}     & the theorem used to try to rewrite {\tt term} \\

   {\tt term}    & the term eventually rewritten by {\tt thm} \\

 \end{tabular}\\

 \noindent The respective values of {\tt rewrite\_} and {\tt rewrite} are an {\tt option} of a pair, i.e. {\tt Some(\_,\_)} in case the {\tt term} can be rewritten by {\tt thm} w.r.t. {\tt rew\_ord} and/or {\tt rls}, or {\tt None} if no rewrite is found:\\

 \begin{tabular}{lp{10.4cm}}

   {\tt term}     & the term rewritten \\

   {\tt term list}& the assumptions eventually generated if the {\tt bool} flag is set to {\tt true} and {\tt thm} is applicable. \\

 \end{tabular}\\

 \paragraph{Give it a try !} {\bf\dots rewriting is fun~!} many examples can be found in {\tt [isac-src]/tests/\dots}. In {\tt [isac-src]/tests/differentiate.sml} the following can be found:

 {\footnotesize\begin{verbatim}

    ML> val thy' = "Differentiate.thy";

    val thy' = "Differentiate.thy" : string

    ML> val ct = "d_d x (x ^^^ #2 + #3 * x + #4)";

    val ct = "d_d x (x ^^^ #2 + #3 * x + #4)" : cterm'

    ML>

    ML> val thm = ("diff_sum","");

    val thm = ("diff_sum","") : thm'

    ML> val Some (ct,_) = rewrite_inst thy' "tless_true" "eval_rls" true

                      [("bdv","x::real")] thm ct;

    val ct = "d_d x (x ^^^ #2 + #3 * x) + d_d x #4" : cterm'

    ML>

    ML> val Some (ct,_) = rewrite_inst thy' "tless_true" "eval_rls" true

                      [("bdv","x::real")] thm ct;

    val ct = "d_d x (x ^^^ #2) + d_d x (#3 * x) + d_d x #4" : cterm'

    ML>

    ML> val thm = ("diff_prod_const","");

    val thm = ("diff_prod_const","") : thm'

    ML> val Some (ct,_) = rewrite_inst thy' "tless_true" "eval_rls" true

                      [("bdv","x::real")] thm ct;

    val ct = "d_d x (x ^^^ #2) + #3 * d_d x x + d_d x #4" : cterm'

 \end{verbatim}}%size

 You can look up the theorems in {\tt [isac-src]/knowledge/Differentiate.thy} and try to apply them until you get the result you would expect if calculating by hand.

 \footnote{Hint: At the end you will need {\tt val (ct,\_) = the (rewrite\_set thy' "eval\_rls" false "SqRoot\_simplify" ct);}}

 \paragraph{Give it a try !}\label{cond-rew} {\bf Conditional rewriting} is a more powerful technique then ordinary rewriting, and is closer to the power of programming languages (see the subsequent 'try it out'~!). The following example expands a term to poynomial form:

 {\footnotesize\begin{verbatim}

    ML> val thy' = "Isac.thy";

    val thy' = "Isac.thy" : string

    ML> val ct' = "#3 * a + #2 * (a + #1)";

    val ct' = "#3 * a + #2 * (a + #1)" : cterm'

    ML>

    ML> val thm' = ("radd_mult_distrib2","?k * (?m + ?n) = ?k * ?m + ?k * ?n");

    val thm' = ("radd_mult_distrib2","?k * (?m + ?n) = ?k * ?m + ?k * ?n")

      : thm'

    ML> (*1*) val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "#3 * a + (#2 * a + #2 * #1)" : cterm'

    ML>

    ML> val thm' = ("radd_assoc_RS_sym","?m1 + (?n1 + ?k1) = ?m1 + ?n1 + ?k1");

    val thm' = ("radd_assoc_RS_sym","?m1 + (?n1 + ?k1) = ?m1 + ?n1 + ?k1")

      : thm'

    ML> (*2*) val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "#3 * a + #2 * a + #2 * #1" : cterm'

    ML>

    ML> val thm' = ("rcollect_right",

      "[| ?l is_const; ?m is_const |] ==> ?l * ?n + ?m * ?n = (?l + ?m) * ?n");

    val thm' =

      ("rcollect_right",

       "[| ?l is_const; ?m is_const |] ==> ?l * ?n + ?m * ?n = (?l + ?m) * ?n")

      : thm'

    ML> (*3*) val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "(#3 + #2) * a + #2 * #1" : cterm'

    ML>

    ML> (*4*) val Some (ct',_) = calculate' thy' "plus" ct';

    val ct' = "#5 * a + #2 * #1" : cterm'

    ML>

    ML> (*5*) val Some (ct',_) = calculate' thy' "times" ct';

    val ct' = "#5 * a + #2" : cterm'

 \end{verbatim}}%size

 Note, that the two rules, {\tt radd\_mult\_distrib2} in {\tt(*1*)} and {\tt rcollect\_right} in {\tt(*3*)} would neutralize each other (i.e. a rule set would not terminate), if there would not be the condition {\tt is\_const}.

 \paragraph{Give it a try !} {\bf Functional programming} can, within a certain range, modeled by rewriting. In {\tt [isac-src]/\dots/tests/InsSort.thy} the following rules can be found, which are able to sort a list ('insertion sort'):

 {\footnotesize\begin{verbatim}

    sort_def   "sort ls = foldr ins ls []"

    ins_base   "ins [] a = [a]"

    ins_rec    "ins (x#xs) a = (if x < a then x#(ins xs a) else a#(x#xs))"  

    foldr_base "foldr f [] a = a"

    foldr_rec  "foldr f (x#xs) a = foldr f xs (f a x)"

    if_True    "(if True then ?x else ?y) = ?x"

    if_False   "(if False then ?x else ?y) = ?y"

 \end{verbatim}}%size

 where {\tt\#} is the list-constructor, {\tt foldr} is the well-known standard function of functional programming, and {\tt if\_True, if\_False} are auxiliary rules. Then the sort may be done by the following rewrites:

 {\footnotesize\begin{verbatim}

    ML>  val thy' = "InsSort.thy";

    val thy' = "InsSort.thy" : theory'

    ML>  val ct = "sort [#1,#3,#2]" : cterm';

    val ct = "sort [#1,#3,#2]" : cterm'

    ML>

    ML>  val thm = ("sort_def","");

    ML>  val (ct,_) = the (rewrite thy' "tless_true" "eval_rls" false thm ct);

    val ct = "foldr ins [#1, #3, #2] []" : cterm'

    ML>

    ML>  val thm = ("foldr_rec","");

    ML>  val (ct,_) = the (rewrite thy' "tless_true" "eval_rls" false thm ct);

    val ct = "foldr ins [#3, #2] (ins [] #1)" : cterm'

    ML>

    ML>  val thm = ("ins_base","");

    ML>  val (ct,_) = the (rewrite thy' "tless_true" "eval_rls" false thm ct);

    val ct = "foldr ins [#3, #2] [#1]" : cterm'

    ML>

    ML>  val thm = ("foldr_rec","");

    ML>  val (ct,_) = the (rewrite thy' "tless_true" "eval_rls" false thm ct);

    val ct = "foldr ins [#2] (ins [#1] #3)" : cterm'

    ML>

    ML>  val thm = ("ins_rec","");

    ML>  val (ct,_) = the (rewrite thy' "tless_true" "eval_rls" false thm ct);

    val ct = "foldr ins [#2] (if #1 < #3 then #1 # ins [] #3 else [#3, #1])"

      : cterm'

    ML>

    ML>  val (ct,_) = the (calculate' thy' "le" ct);

    val ct = "foldr ins [#2] (if True then #1 # ins [] #3 else [#3, #1])" : cterm'

    ML>

    ML>  val thm = ("if_True","(if True then ?x else ?y) = ?x");

    ML>  val (ct,_) = the (rewrite thy' "tless_true" "eval_rls" false thm ct);

    val ct = "foldr ins [#2] (#1 # ins [] #3)" : cterm'

    ML> 

    ...

    val ct = "sort [#1,#3,#2]" : cterm'

 \end{verbatim}}%size

 \section{Variants of rewriting}

 Some of the above examples already used variants of {\tt rewrite} all of which have the same value, and very similar arguments:

 {\footnotesize\begin{verbatim}

    ML> rewrite_inst_;

    val it = fn

      : theory

        -> rew_ord

           -> rls

              -> bool

              -> (cterm' * cterm') list

                    -> thm -> term -> (term * term list) option

    ML> rewrite_inst;

    val it = fn

      : theory'

        -> rew_ord

           -> rls'

              -> bool

                 -> (cterm' * cterm') list

                    -> thm' -> cterm' -> (cterm' * cterm' list) option

    ML>

    ML> rewrite_set_;

    val it = fn 

      : theory -> rls -> bool -> rls -> term -> (term * term list) option

    ML> rewrite_set;

    val it = fn

      : theory' -> rls' -> bool -> rls' -> cterm' -> (cterm' * cterm' list) option

    ML>

    ML> rewrite_set_inst_;

    val it = fn

      : theory

        -> rls

           -> bool

              -> (cterm' * cterm') list

                 -> rls -> term -> (term * term list) option

    ML> rewrite_set_inst;

    val it = fn

      : theory'

        -> rls'

           -> bool

              -> (cterm' * cterm') list

                 -> rls' -> cterm' -> (cterm' * cterm' list) option

 \end{verbatim}}%size

 \noindent The variant {\tt rewrite\_inst} substitutes {\tt (term * term) list} in {\tt thm} before rewriting,\\

 the variant {\tt rewrite\_set} rewrites with a whole rule set {\tt rls} (instead with a {\tt thm} only),\\

 the variant {\tt rewrite\_set\_inst} is a combination of the latter two variants. In order to watch how a term is rewritten theorem by theorem, there is a switch {\tt trace\_rewrite}:

 {\footnotesize\begin{verbatim}

    ML> toggle;

    val it = fn : bool ref -> bool

    ML>

    ML> toggle trace_rewrite;

    val it = true : bool

    ML> toggle trace_rewrite;

    val it = false : bool

 \end{verbatim}}%size

 \section{Rule sets}

 Some of the variants of {\tt rewrite} above do not only apply one theorem, but a whole set of theorems, called a 'rule set'. Such a rule set is applied as long one of its elements can be used for a rewrite (which can go forever, i.e. the rule set eventually does not 'terminate').

 A simple example of a rule set is {\tt rearrange\_assoc} which is defined in {\tt knowledge/RatArith.ML} as:

 {\footnotesize\begin{verbatim}

    val rearrange_assoc = 

      Rls{preconds = [], rew_ord = ("tless_true",tless_true), 

          rules = 

          [Thm ("radd_assoc_RS_sym",num_str (radd_assoc RS sym)),

           Thm ("rmult_assoc_RS_sym",num_str (rmult_assoc RS sym))],

          program = Script ((term_of o the o (parse thy)) 

          "empty_script")

          }:rls;

 \end{verbatim}}%size

 where 

 \begin{description}

 \item [\tt preconds] are conditions which must be true in order to make the rule set applicable (the empty list evaluates to {\tt true})

 \item [\tt rew\_ord] concerns term orders introduced below in \ref{term-order}

 \item [\tt rules] are the theorems to be applied -- in priciple applied in arbitrary order, because all these rule sets should be 'complete' \cite{nipk:rew-all-that} (and actually the theorems are applied in the sequence they appear in this list). The function {\tt num\_str} must be applied to theorems containing numeral constants (and thus is obsolete in this example). {\tt RS} is an infix function applying the theorem {\tt sym} to {\tt radd\_assoc} before storage (the effect see below)

 \item [\tt program] is the script applying the ruleset; it will disappear in later versions of \isac.

 \end{description}

 These variables evaluate to

 {\footnotesize\begin{verbatim}

    ML> sym;

    val it = "?s = ?t ==> ?t = ?s" : thm 

    ML> rearrange_assoc;

    val it =

      Rls

        {preconds=[],rew_ord=("tless_true",fn),

         rules=[Thm ("radd_assoc_RS_sym","?m1 + (?n1 + ?k1) = ?m1 + ?n1 + ?k1"),

                Thm ("rmult_assoc_RS_sym","?m1 * (?n1 * ?k1) = ?m1 * ?n1 * ?k1")],

         program=Script (Free ("empty_script","RealDef.real"))} : rls 

 \end{verbatim}}%size

 \paragraph{Give it a try !} The above rule set makes an arbitrary number of parentheses disappear which are not necessary due to associativity of {\tt +} and 

 {\footnotesize\begin{verbatim}

    ML> val ct = (string_of_cterm o the o (parse RatArith.thy))

                 "a + (b * (c * d) + e)";

    val ct = "a + ((b * (c * d) + e) + f)" : cterm'

    ML> rewrite_set "RatArith.thy" "eval_rls" false "rearrange_assoc" ct;

    val it = Some ("a + b * c * d + e + f",[]) : (string * string list) option

 \end{verbatim}}%size

 For acchieving this result the rule set has to be surprisingly busy:

 {\footnotesize\begin{verbatim}

    ML> toggle trace_rewrite;

    val it = true : bool

    ML> rewrite_set "RatArith.thy" "eval_rls" false "rearrange_assoc" ct;

    ### trying thm 'radd_assoc_RS_sym'

    ### rewrite_set_: a + b * (c * d) + e

    ### trying thm 'radd_assoc_RS_sym'

    ### trying thm 'rmult_assoc_RS_sym'

    ### rewrite_set_: a + b * c * d + e

    ### trying thm 'rmult_assoc_RS_sym'

    ### trying thm 'radd_assoc_RS_sym'

    ### trying thm 'rmult_assoc_RS_sym'

    val it = Some ("a + b * c * d + e",[]) : (string * string list) option

 \end{verbatim}}%size

 \section{Calculate numeric constants}

 As soon as numeric constants are in adjacent subterms (see the example on p.\pageref{cond-rew}), they can be calculated by the function

 {\footnotesize\begin{verbatim}

    ML> calculate;

    val it = fn : theory' -> string -> cterm' -> (cterm' * thm') option

    ML> calculate_;

    val it = fn : theory -> string -> term -> (term * (string * thm)) option

 \end{verbatim}}%size

 where the {\tt string} in the arguments defines the algebraic operation to be calculated. The function returns the result of the calculation, and as second element in the pair the theorem applied. The following algebraic operations are available:

 {\footnotesize\begin{verbatim}

    ML> calc_list;

    val it =

      ref

        [("plus",("op +",fn)),

         ("times",("op *",fn)),

         ("cancel_",("cancel",fn)),

         ("power",("pow",fn)),

         ("sqrt",("sqrt",fn)),

         ("Var",("Var",fn)),

         ("Length",("Length",fn)),

         ("Nth",("Nth",fn)),

         ("power",("pow",fn)),

         ("le",("op <",fn)),

         ("leq",("op <=",fn)),

         ("is_const",("is'_const",fn)),

         ("is_root_free",("is'_root'_free",fn)),

         ("contains_root",("contains'_root",fn)),

         ("ident",("ident",fn))]

      : (string * (string * (string -> term -> theory -> 

         (string * term) option))) list ref

 \end{verbatim}}%size

 These operations can be used in the following way.

 {\footnotesize\begin{verbatim}

    ML> calculate' "Isac.thy" "plus" "#1 + #2";

    val it = Some ("#3",("#add_#1_#2","\"#1 + #2 = #3\"")) : (string * thm') option

    ML>

    ML> calculate' "Isac.thy" "times" "#2 * #3";

    val it = Some ("#6",("#mult_#2_#3","\"#2 * #3 = #6\""))

      : (string * thm') option

    ML>

    ML> calculate' "Isac.thy" "power" "#2 ^^^ #3";

    val it = Some ("#8",("#power_#2_#3","\"#2 ^^^ #3 = #8\""))

      : (string * thm') option

    ML>

    ML> calculate' "Isac.thy" "cancel_" "#9 // #12";

    val it = Some ("#3 // #4",("#cancel_#9_#12","\"#9 // #12 = #3 // #4\""))

      : (string * thm') option

    ML>

    ML> ...

 \end{verbatim}}%size

 \chapter{Term orders}\label{term-order}

 Orders on terms are indispensable for the purpose of rewriting to normal forms in associative - commutative domains \cite{nipk:rew-all-that}, and for rewriting to normal forms necessary for matching models to problems, see sect.\ref{pbt}.

 \section{Examples for term orders}

 It is not trivial to construct a relation $<$ on terms such that it is really an order, i.e. a transitive and antisymmetric relation. These orders are 'recursive path orders' \cite{nipk:rew-all-that}. Some orders implemented in the knowledgebase at {\tt [isac-src]/knowledge/\dots}, %FIXXXmat0201a

 e.g.

 {\footnotesize\begin{verbatim}

    ML> sqrt_right;

    val it = fn : bool -> theory -> term * term -> bool

    ML> tless_true;

    val it = fn : 'a -> bool 

 \end{verbatim}}%size

 where the bool argument is a switch for tracing the checks on the respective subterms (and theory is necessary for displyinging the (sub-)terms as strings in the case of 'true'). The order {\tt tless\_true} is a dummy always yielding {\tt true}, and {\tt sqrt\_right} prefers a square root shifted to the right within a term:

 {\footnotesize\begin{verbatim}

    ML> val t1 = (term_of o the o (parse thy)) "(sqrt a) + b";

    val t1 = Const # $ (# $ #) $ Free (#,#) : term

    ML>

    ML> val t2 = (term_of o the o (parse thy)) "b + (sqrt a)";

    val t2 = Const # $ Free # $ (Const # $ Free #) : term

    ML>

    ML> sqrt_right false SqRoot.thy (t1, t2);

    val it = false : bool

    ML> sqrt_right false SqRoot.thy (t2, t1);

    val it = true : bool

 \end{verbatim}}%size

 The many checks performed recursively through all subterms can be traced throughout the algorithm in {\tt [isac-src]/knowledge/SqRoot.ML} by setting the flag to true:

 {\footnotesize\begin{verbatim}

    ML> val t1 = (term_of o the o (parse thy)) "a + b*(sqrt c) + d";

    val t1 = Const (#,#) $ (# $ # $ (# $ #)) $ Free ("d","RealDef.real") : term

    ML>

    ML> val t2 = (term_of o the o (parse thy)) "a + (sqrt b)*c + d";

    val t2 = Const (#,#) $ (# $ # $ (# $ #)) $ Free ("d","RealDef.real") : term

    ML>

    ML> sqrt_right true SqRoot.thy (t1, t2);

    t= f@ts= "op +" @ "[a + b * sqrt c,d]"

    u= g@us= "op +" @ "[a + sqrt b * c,d]"

    size_of_term(t,u)= (8, 8)

    hd_ord(f,g)      = EQUAL

    terms_ord(ts,us) = LESS

    -------

    t= f@ts= "op +" @ "[a,b * sqrt c]"

    u= g@us= "op +" @ "[a,sqrt b * c]"

    size_of_term(t,u)= (6, 6)

    hd_ord(f,g)      = EQUAL

    terms_ord(ts,us) = LESS

    -------

    t= f@ts= "a" @ "[]"

    u= g@us= "a" @ "[]"

    size_of_term(t,u)= (1, 1)

    hd_ord(f,g)      = EQUAL

    terms_ord(ts,us) = EQUAL

    -------

    t= f@ts= "op *" @ "[b,sqrt c]"

    u= g@us= "op *" @ "[sqrt b,c]"

    size_of_term(t,u)= (4, 4)

    hd_ord(f,g)      = EQUAL

    terms_ord(ts,us) = LESS

    -------

    t= f@ts= "b" @ "[]"

    u= g@us= "sqrt" @ "[b]"

    size_of_term(t,u)= (1, 2)

    hd_ord(f,g)      = LESS

    terms_ord(ts,us) = LESS

    -------

    val it = true : bool 

 \end{verbatim}}%size

 \section{Ordered rewriting}

 Rewriting faces problems in just the most elementary domains, which are all associative and commutative w.r.t. {\tt +} and {\tt *} --- the law of commutativity applied within a rule set causes this set not to terminate~! One method to cope with this difficulty is ordered rewriting, where a rewrite is only done if the resulting term is smaller w.r.t. a term order (with some additional properties called 'rewrite orders' \cite{nipk:rew-all-that}).

 Such a rule set {\tt ac\_plus\_times}, called an AC-rewrite system, can be found in {\tt[isac-src]/knowledge/RathArith.ML}:

 {\footnotesize\begin{verbatim}

    val ac_plus_times =

      Rls{preconds = [], rew_ord = ("term_order",term_order),

          rules =

          [Thm ("radd_commute",radd_commute),

           Thm ("radd_left_commute",radd_left_commute),

           Thm ("radd_assoc",radd_assoc),

           Thm ("rmult_commute",rmult_commute),

           Thm ("rmult_left_commute",rmult_left_commute),

           Thm ("rmult_assoc",rmult_assoc)],

          program = Script ((term_of o the o (parse thy))

          "empty_script")

          }:rls;

    val ac_plus_times =

      Rls

        {preconds=[],rew_ord=("term_order",fn),

         rules=[Thm ("radd_commute","?m + ?n = ?n + ?m"),

                Thm ("radd_left_commute","?x + (?y + ?z) = ?y + (?x + ?z)"),

                Thm ("radd_assoc","?m + ?n + ?k = ?m + (?n + ?k)"),

                Thm ("rmult_commute","?m * ?n = ?n * ?m"),

                Thm ("rmult_left_commute","?x * (?y * ?z) = ?y * (?x * ?z)"),

                Thm ("rmult_assoc","?m * ?n * ?k = ?m * (?n * ?k)")],

         program=Script (Free ("empty_script","RealDef.real"))} : rls 

 \end{verbatim}}%size

 Note that the theorems {\tt radd\_left\_commute} and {\tt rmult\_left\_commute} are really necessary in order to make the rule set 'confluent'~!

 \paragraph{Give it a try !} Ordered rewriting is one technique to produce polynomial normal from from arbitrary integer terms:

 {\footnotesize\begin{verbatim}

    ML> val ct' = "#3 * a + b + #2 * a";

    val ct' = "#3 * a + b + #2 * a" : cterm'

    ML>

    ML> (*-1-*) radd_commute; val thm' = ("radd_commute","") : thm';

    val it = "?m + ?n = ?n + ?m" : thm

    val thm' = ("radd_commute","") : thm'

    ML> val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "#2 * a + (#3 * a + b)" : cterm'

    ML>

    ML> (*-2-*) rdistr_right_assoc_p; val thm' = ("rdistr_right_assoc_p","") : thm';

    val it = "?l * ?n + (?m * ?n + ?k) = (?l + ?m) * ?n + ?k" : thm

    val thm' = ("rdistr_right_assoc_p","") : thm'

    ML> val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "(#2 + #3) * a + b" : cterm'

    ML>

    ML> (*-3-*)

    ML> val Some (ct',_) = calculate thy' "plus" ct';

    val ct' = "#5 * a + b" : cterm'

 \end{verbatim}}%size %FIXXXmat0201b ... calculate !

 This looks nice, but if {\tt radd\_commute} is applied automatically in {\tt (*-1-*)} without checking the resulting term to be 'smaller' w.r.t. a term order, then rewritin goes on forever (i.e. it does not 'terminate') \dots

 {\footnotesize\begin{verbatim}

    ML> val ct' = "#3 * a + b + #2 * a" : cterm';

    val ct' = "#3 * a + b + #2 * a" : cterm'

    ML> val thm' = ("radd_commute","") : thm';

    val thm' = ("radd_commute","") : thm'

    ML>

    ML> val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "#2 * a + (#3 * a + b)" : cterm'

    ML> val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "#3 * a + b + #2 * a" : cterm'

    ML> val Some (ct',_) = rewrite thy' "tless_true" "eval_rls" true thm' ct';

    val ct' = "#2 * a + (#3 * a + b)" : cterm'

               ..........

 \end{verbatim}}%size

 Ordered rewriting with the above AC-rewrite system {\tt ac\_plus\_times} performs a kind of bubble sort which can be traced:

 {\footnotesize\begin{verbatim}

    ML> toggle trace_rewrite;

    val it = true : bool

    ML>

    ML> rewrite_set "RatArith.thy" "eval_rls" false "ac_plus_times" ct;

    ### trying thm 'radd_commute'

    ### not: "a + (b * (c * d) + e)" > "b * (c * d) + e + a"

    ### rewrite_set_: a + (e + b * (c * d))

    ### trying thm 'radd_commute'

    ### not: "a + (e + b * (c * d))" > "e + b * (c * d) + a"

    ### not: "e + b * (c * d)" > "b * (c * d) + e"

    ### trying thm 'radd_left_commute'

    ### not: "a + (e + b * (c * d))" > "e + (a + b * (c * d))"

    ### trying thm 'radd_assoc'

    ### trying thm 'rmult_commute'

    ### not: "b * (c * d)" > "c * d * b"

    ### not: "c * d" > "d * c"

    ### trying thm 'rmult_left_commute'

    ### not: "b * (c * d)" > "c * (b * d)"

    ### trying thm 'rmult_assoc'

    ### trying thm 'radd_commute'

    ### not: "a + (e + b * (c * d))" > "e + b * (c * d) + a"

    ### not: "e + b * (c * d)" > "b * (c * d) + e"

    ### trying thm 'radd_left_commute'

    ### not: "a + (e + b * (c * d))" > "e + (a + b * (c * d))"

    ### trying thm 'radd_assoc'

    ### trying thm 'rmult_commute'

    ### not: "b * (c * d)" > "c * d * b"

    ### not: "c * d" > "d * c"

    ### trying thm 'rmult_left_commute'

    ### not: "b * (c * d)" > "c * (b * d)"

    ### trying thm 'rmult_assoc'

    val it = Some ("a + (e + b * (c * d))",[]) : (string * string list) option     \end{verbatim}}%size

 Notice that {\tt +} is left-associative where the parentheses are omitted for {\tt (a + b) + c = a + b + c}, but not for {\tt a + (b + c)}. Ordered rewriting necessarily terminates with parentheses which could be omitted due to associativity.

 \chapter{The hierarchy of problem types}\label{pbt}

 \section{The standard-function for 'matching'}

 Matching \cite{nipk:rew-all-that} is a technique used within rewriting, and used by \isac{} also for (a generalized) 'matching' a problem with a problem type. The function which tests for matching has the following signature:

 {\footnotesize\begin{verbatim}

    ML> matches;

    val it = fn : theory -> term -> term -> bool

 \end{verbatim}}%size

 where the first of the two {\tt term} arguments is the particular term to be tested, and the second one is the pattern:

 {\footnotesize\begin{verbatim}

    ML> val t = (term_of o the o (parse thy)) "#3 * x^^^#2 = #1";

    val t = Const (#,#) $ (# $ # $ (# $ #)) $ Free ("#1","RealDef.real") : term

    ML>

    ML> val p = (term_of o the o (parse thy)) "a * b^^^#2 = c";

    val p = Const (#,#) $ (# $ # $ (# $ #)) $ Free ("c","RealDef.real") : term

    ML> atomt p;

    *** -------------

    *** Const ( op =)

    *** . Const ( op *)

    *** . . Free ( a, )

    *** . . Const ( RatArith.pow)

    *** . . . Free ( b, )

    *** . . . Free ( #2, )

    *** . Free ( c, )

    val it = () : unit

    ML>

    ML> mk_Var;

    val it = fn : term -> term

    ML>

    ML> val pat = mk_Var p;

    val pat = Const (#,#) $ (# $ # $ (# $ #)) $ Var ((#,#),"RealDef.real") : term

    ML> Sign.string_of_term (sign_of thy) pat;

    val it = "?a * ?b ^^^ #2 = ?c" : cterm' 

    ML> atomt pat;

    *** -------------

    *** Const ( op =)

    *** . Const ( op *)

    *** . . Var ((a, 0), )

    *** . . Const ( RatArith.pow)

    *** . . . Var ((b, 0), )

    *** . . . Free ( #2, )

    *** . Var ((c, 0), )

    val it = () : unit

 \end{verbatim}}%size % $ 

 Note that the pattern {\tt pat} contains so-called {\it scheme variables} decorated with a {\tt ?} (analoguous to theorems). The pattern is generated by the function {\tt mk_Var}. This format of the pattern is necessary in order to obtain results like these:

 {\footnotesize\begin{verbatim}

    ML> matches thy t pat;

    val it = true : bool

    ML>

    ML> val t2 = (term_of o the o (parse thy)) "x^^^#2 = #1";

    val t2 = Const (#,#) $ (# $ # $ Free #) $ Free ("#1","RealDef.real") : term

    ML> matches thy t2 pat;

    val it = false : bool    

    ML>

    ML> val pat2 = (term_of o the o (parse thy)) "?u^^^#2 = ?v";

    val pat2 = Const (#,#) $ (# $ # $ Free #) $ Var ((#,#),"RealDef.real") : term

    ML> matches thy t2 pat2;

    val it = true : bool 

 \end{verbatim}}%size % $

 \section{Accessing the hierarchy}

 The hierarchy of problem types is encapsulated; it can be accessed by the following functions. {\tt show\_ptyps} retrieves all leaves of the hierarchy (here in an early version for testing):

 {\footnotesize\begin{verbatim}

    ML> show_ptyps;

    val it = fn : unit -> unit

    ML> show_ptyps();

    [

     ["e_pblID"],

     ["equation", "univariate", "linear"],

     ["equation", "univariate", "plain_square"],

     ["equation", "univariate", "polynomial", "degree_two", "pq_formula"],

     ["equation", "univariate", "polynomial", "degree_two", "abc_formula"],

     ["equation", "univariate", "squareroot"],

     ["equation", "univariate", "normalize"],

     ["equation", "univariate", "sqroot-test"],

     ["function", "derivative_of"],

     ["function", "maximum_of", "on_interval"],

     ["function", "make"],

     ["tool", "find_values"],

     ["functional", "inssort"]

    ]

    val it = () : unit

 \end{verbatim}}%size

 The retrieve function for individual problem types is {\tt get\_pbt}

 \footnote{A function providing better readable output is in preparation}. Note that its argument, the 'problem identifier' {\tt pblID}, has the strings listed in reverse order w.r.t. the hierarchy, i.e. from the leave to the root. This order makes the {\tt pblID} closer to a natural description:

 {\footnotesize\begin{verbatim}

    ML> get_pbt;

    val it = fn : pblID -> pbt

    ML> get_pbt ["squareroot", "univariate", "equation"];

    val it =

      {met=[("SqRoot.thy","square_equation")],

       model=[("#Given",(Const (#,#),Free (#,#))),

            ("#Given",(Const (#,#),Free (#,#))),

            ("#Given",(Const (#,#),Free (#,#))),

            ("#Find",(Const (#,#),Free (#,#)))],

       thy={ProtoPure, CPure, HOL, Ord, Set, subset, equalities, mono, Vimage, Fun,

             Prod, Lfp, Relation, Trancl, WF, NatDef, Gfp, Sum, Inductive, Nat,

             Arith, Divides, Power, Finite, Equiv, IntDef, Int, Univ, Datatype,

             Numeral, Bin, IntArith, WF_Rel, Recdef, IntDiv, NatBin, List, Option,

             Map, Record, RelPow, Sexp, String, Calculation, SVC_Oracle, Main,

             Zorn, Filter, PNat, PRat, PReal, RealDef, RealOrd, RealInt, RealBin,

             HyperDef, Descript, ListG, Tools, Script, Typefix, Atools, RatArith,

             SqRoot},

       where_=[Const ("SqRoot.contains'_root","bool => bool") $

               Free ("e_","bool")]} : pbt

 \end{verbatim}}%size %$

 where the records fields hold the following data:

 \begin{description}

 \item [\tt thy]: the theory necessary for parsing the formulas

 \item [\tt model]: the items of the problem type, divided into those {\tt Given}, the precondition {\tt Where} and the output item(s) {\tt Find}. The items of {\tt Given} and {\tt Find} are all headed by so-called descriptions, which determine the type. These descriptions are defined in {\tt [isac-src]/Isa99/Descript.thy}.

 \item [\tt met]: the list of methods solving this problem type.\\

 \end{description}

 The following function adds or replaces a problem type (after having it prepared using {\tt prep\_pbt})

 {\footnotesize\begin{verbatim}

    ML> store_pbt;

    val it = fn : pbt * pblID -> unit

    ML> store_pbt

     (prep_pbt SqRoot.thy

     (["newtype","univariate","equation"],

      [("#Given" ,["equality e_","solveFor v_","errorBound err_"]),

       ("#Where" ,["contains_root (e_::bool)"]),

       ("#Find"  ,["solutions v_i_"])

      ],

      [("SqRoot.thy","square_equation")]));

    val it = () : unit

 \end{verbatim}}%size

 When adding a new type with argument {\tt pblID}, an immediate parent must already exist in the hierarchy (this is the one with the tail of {\tt pblID}).

 \section{Internals of the datastructure}

 This subsection only serves for the implementation of the hierarchy browser and can be skipped by the authors of math knowledge.

 A problem type is described by the following record type (in the file {\tt [isac-src]/globals.sml}, the respective functions are in {\tt [isac-src]/ME/ptyps.sml}), and held in a global reference variable:

 {\footnotesize\begin{verbatim}

    type pbt = 

         {thy   : theory,       (* the nearest to the root,

                                   which allows to compile that pbt  *)

          where_: term list,    (* where - predicates                *)

          model   : ((string *    (* fields "#Given","#Find"           *)

                    (term *     (* description                       *)

                     term))     (* id                                *)

                       list),                                        

          met   : metID list};  (* methods solving the pbt           *)

    datatype ptyp = 

             Ptyp of string *   (* key within pblID                  *)

                     pbt list * (* several pbts with different domIDs*)

                     ptyp list;

    val e_Ptyp = Ptyp ("empty",[],[]);

    type ptyps = ptyp list;

    val ptyps = ref ([e_Ptyp]:ptyps);

 \end{verbatim}}%size

 The predicates in {\tt where\_} (i.e. the preconditions) usually are defined in the respective theory in {\tt[isac-src]/knowledge}. Most of the predicates are not defined by rewriting, but by SML-code contained in the respective {\tt *.ML} file.

 Each item is headed by a so-called description which provides some guidance for interactive input. The descriptions are defined in {\tt[isac-src]/Isa99/Descript.thy}.

 \section{Match a formalization with a problem type}\label{pbl}

 A formalization is {\it match}ed with a problem type which yields a problem. A formal description of this kind of {\it match}ing can be found in \\{\tt ftp://ft.ist.tugraz.at/projects/isac/publ/calculemus01.ps.gz}. A formalization of an equation is e.g.

 {\footnotesize\begin{verbatim}

    ML> val fmz = ["equality (#1 + #2 * x = #0)",

                   "solveFor x",

                   "solutions L"] : fmz;

    val fmz = ["equality (#1 + #2 * x = #0)","solveFor x","solutions L"] : fmz

 \end{verbatim}}%size

 Given a formalization (and a specification of the problem, i.e. a theory, a problemtype, and a method) \isac{} can solve the respective problem automatically. The formalization must match the problem type for this purpose:

 {\footnotesize\begin{verbatim}

    ML> by_formalise;

    val it = fn : fmz -> pbt -> match'

    ML>

    ML> by_formalise fmz (get_pbt ["univariate","equation"]);

    val it =

      Matches'

        {Find=[Correct "solutions L"],

         Given=[Correct "equality (#1 + #2 * x = #0)",Correct "solveFor x"],

         Relate=[],Where=[Correct "matches (?a = ?b) (#1 + #2 * x = #0)"],With=[]}

      : match'

    ML>

    ML> by_formalise fmz (get_pbt ["linear","univariate","equation"]);

    val it =

      Matches'

        {Find=[Correct "solutions L"],

         Given=[Correct "equality (#1 + #2 * x = #0)",Correct "solveFor x"],

         Relate=[],

         Where=[Correct

                  "matches (          x = #0) (#1 + #2 * x = #0) |

                   matches (     ?b * x = #0) (#1 + #2 * x = #0) |

                   matches (?a      + x = #0) (#1 + #2 * x = #0) |

                   matches (?a + ?b * x = #0) (#1 + #2 * x = #0)"],

         With=[]} : match'

    ML>

    ML> by_formalise fmz (get_pbt ["squareroot","univariate","equation"]);

    val it =

      NoMatch'

        {Find=[Correct "solutions L"],

         Given=[Correct "equality (#1 + #2 * x = #0)",Correct "solveFor x",

                Missing "errorBound err_"],Relate=[],

         Where=[False "contains_root #1 + #2 * x = #0 "],With=[]} : match'

 \end{verbatim}}%size

 The above formalization does not match the problem type \\{\tt["squareroot","univariate","equation"]} which is explained by the tags:

 \begin{tabbing}

 123\=\kill

 \> {\tt Missing:} the item is missing in the formalization as required by the problem type\\

 \> {\tt Superfl:} the item is not required by the problem type\\

 \> {\tt Correct:} the item is correct, or the precondition ({\tt Where}) is true\\

 \> {\tt False:} the precondition ({\tt Where}) is false\\

 \> {\tt Incompl:} the item is incomlete, or not yet input.\\

 \end{tabbing}

 \section{Refine a problem specification}

 The challenge in constructing the problem hierarchy is, to design the branches in such a way, that problem refinement can be done automatically (as it is done in algebra system e.g. by a internal hierarchy of equations).

 For this purpose the hierarchy must be built using the following rules: Let $F$ be a formalization and $P$ and $P_i,\:i=1\cdots n$ problem types, where the $P_i$ are specialized problem types w.r.t. $P$ (i.e. $P$ is a parent node of $P_i$), then

 {\small

 \begin{enumerate}

 \item for all $F$ matching some $P_i$ must follow, that $F$ matches $P$

 \item an $F$ matching $P$ should not have more than {\em one} $P_i,\:i=1\cdots n-1$ with $F$ matching $P_i$ (if there are more than one $P_i$, the first one will be taken)

 \item for all $F$ matching some $P$ must follow, that $F$ matches $P_n$\\

 \end{enumerate}}%small

 \noindent Let us give an example for the point (1.) and (2.) first:

 {\footnotesize\begin{verbatim}

    ML> refine;

    val it = fn : fmz -> pblID -> match list

    ML>

    ML> val fmz = ["equality (sqrt(#9+#4*x)=sqrt x + sqrt(#5+x))",

               "solveFor x","errorBound (eps=#0)",

               "solutions L"];

    ML>

    ML> refine fmz ["univariate","equation"];

    *** pass ["equation","univariate"]

    *** pass ["equation","univariate","linear"]

    *** pass ["equation","univariate","plain_square"]

    *** pass ["equation","univariate","polynomial"]

    *** pass ["equation","univariate","squareroot"]

    val it =

      [Matches

         (["univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x))",

                  Correct "solveFor x",Superfl "errorBound (eps = #0)"],Relate=[],

           Where=[Correct

                    "matches (?a = ?b) (sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x))"],

           With=[]}),

       NoMatch

         (["linear","univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x))",

                  Correct "solveFor x",Superfl "errorBound (eps = #0)"],Relate=[],

           Where=[False "(?a + ?b * x = #0) (sqrt (#9 + #4 * x#"],

           With=[]}),

       NoMatch

         (["plain_square","univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x))",

                  Correct "solveFor x",Superfl "errorBound (eps = #0)"],Relate=[],

           Where=[False

                    "matches (?a + ?b * x ^^^ #2 = #0)"],

           With=[]}),

       NoMatch

         (["polynomial","univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x))",

                  Correct "solveFor x",Superfl "errorBound (eps = #0)"],Relate=[],

           Where=[False 

                  "is_polynomial_in sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x) x"],

           With=[]}),

       Matches

         (["squareroot","univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x))",

                  Correct "solveFor x",Correct "errorBound (eps = #0)"],Relate=[],

           Where=[Correct

                    "contains_root sqrt (#9 + #4 * x) = sqrt x + sqrt (#5 + x) "],

           With=[]})] : match list

 \end{verbatim}}%size}%footnotesize\label{refine}

 This example shows, that in order to refine an {\tt["univariate","equation"]}, the formalization must match respective respective problem type (rule (1.)) and one of the descendants which should match selectively (rule (2.)).

 If no one of the descendants of {\tt["univariate","equation"]} match, rule (3.) comes into play: The {\em last} problem type on this level ($P_n$) provides for a special 'problem type' {\tt["normalize"]}. This node calls a method transforming the equation to a (or another) normal form, which then may match. Look at this example:

 {\footnotesize\begin{verbatim}

    ML>  val fmz = ["equality (x+#1=#2)",

                "solveFor x","errorBound (eps=#0)",

                "solutions L"];

    [...]

    ML>

    ML>  refine fmz ["univariate","equation"];

    *** pass ["equation","univariate"]

    *** pass ["equation","univariate","linear"]

    *** pass ["equation","univariate","plain_square"]

    *** pass ["equation","univariate","polynomial"]

    *** pass ["equation","univariate","squareroot"]

    *** pass ["equation","univariate","normalize"]

    val it =

      [Matches

         (["univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (x + #1 = #2)",Correct "solveFor x",

                  Superfl "errorBound (eps = #0)"],Relate=[],

           Where=[Correct "matches (?a = ?b) (x + #1 = #2)"],With=[]}),

       NoMatch

         (["linear","univariate","equation"],

    [...]

           With=[]}),

       NoMatch

         (["squareroot","univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (x + #1 = #2)",Correct "solveFor x",

                  Correct "errorBound (eps = #0)"],Relate=[],

           Where=[False "contains_root x + #1 = #2 "],With=[]}),

       Matches

         (["normalize","univariate","equation"],

          {Find=[Correct "solutions L"],

           Given=[Correct "equality (x + #1 = #2)",Correct "solveFor x",

                  Superfl "errorBound (eps = #0)"],Relate=[],Where=[],With=[]})]

      : match list

 \end{verbatim}}%size

 The problem type $P_n$, {\tt["normalize","univariate","equation"]}, will transform the equation {\tt x + \#1 = \#2} to the normal form {\tt \#-1 + x = \#0}, which then will match {\tt["linear","univariate","equation"]}.

 This recursive search on the problem hierarchy can be  done within a proof state. This leads to the next section.

 \chapter{Methods}

 A problem type can have one ore more methods solving a respective problem. A method is described by means of another new program language. The language itself looks like a simple functional language, but constructs an imperative proof-state behind the scenes (thus liberating the programer from dealing with technical details and also prohibiting incorrect construction of the proof tree). The interpreter of 'scripts' written in this language evaluates the scriptexpressions, and also delivers certain parts of the script itself for discussion with the user.

 \section{The scripts' syntax}

 The syntax of scripts follows the definition given in Backus-normal-form:

 {\it

 \begin{tabbing}

 123\=123\=expr ::=\=$|\;\;$\=\kill

 \>script ::= {\tt Script} id arg$\,^*$ = body\\

 \>\>arg ::= id $\;|\;\;($ ( id :: type ) $)$\\

 \>\>body ::= expr\\

 \>\>expr ::= \>\>{\tt let} id = expr $($ ; id = expr$)^*$ {\tt in} expr\\

 \>\>\>$|\;$\>{\tt if} prop {\tt then} expr {\tt else} expr\\

 \>\>\>$|\;$\>listexpr\\

 \>\>\>$|\;$\>id\\

 \>\>\>$|\;$\>seqex id\\

 \>\>seqex ::= \>\>{\tt While} prop {\tt Do} seqex\\

 \>\>\>$|\;$\>{\tt Repeat} seqex\\

 \>\>\>$|\;$\>{\tt Try} seqex\\

 \>\>\>$|\;$\>seqex {\tt Or} seqex\\

 \>\>\>$|\;$\>seqex {\tt @@} seqex\\

 \>\>\>$|\;$\>tac $($ id $|$ listexpr $)^*$\\

 \>\>type ::= id\\

 \>\>tac ::= id

 \end{tabbing}}

 where {\it id} is an identifier with the usual syntax, {\it prop} is a proposition constructed by Isabelles logical operators (see \cite{Isa-obj} {\tt [isabelle]/src/HOL/HOL.thy}), {\it listexpr} (called {\bf list-expression}) is constructed by Isabelles list functions like {\tt hd, tl, nth} described in {\tt [isabelle]/src/HOL/List.thy}, and {\it type} are (virtually) all types declared in Isabelles version 99.

 Expressions containing some of the keywords {\tt let}, {\tt if} etc. are called {\bf script-expressions}.

 Tactics {\it tac} are (curried) functions. For clarity and simplicity reasons, {\it listexpr} must not contain a {\it tac}, and {\it tac}s must not be nested,

 \section{Control the flow of evaluation}

 The flow of control is managed by the following script-expressions called {\it tacticals}.

 \begin{description}

 \item{{\tt while} prop {\tt Do} expr id} 

 \item{{\tt if} prop {\tt then} expr {\tt else} expr}

 \end{description}

 While the the above script-expressions trigger the flow of control by evaluating the current formula, the other expressions depend on the applicability of the tactics within their respective subexpressions (which in turn depends on the proofstate)

 \begin{description}

 \item{{\tt Repeat} expr id}

 \item{{\tt Try} expr id}

 \item{expr {\tt Or} expr id}

 \item{expr {\tt @@} expr id}

 \end{description}

 \begin{description}

 \item xxx

 \end{description}

 \chapter{Do a calculational proof}

 First we list all the tactics available so far (this list may be extended during further development of \isac).

 \section{Tactics for doing steps in calculations}

 \input{tactics}

 \section{The functionality of the math engine}

 A proof is being started in the math engine {\tt me} by the tactic

 \footnote{In the present version a tactic is of type {\tt mstep}.}

  {\tt Init\_Proof}, and interactively promoted by other tactics. On input of each tactic the {\tt me} returns the resulting formula and the next tactic applicable. The proof is finished, when the {\tt me} proposes {\tt End\_Proof} as the next tactic.

 We show a calculation (calculational proof) concerning equation solving, where the type of equation is refined automatically: The equation is given by the respective formalization ...

 {\footnotesize\begin{verbatim}

    ML> val fmz = ["equality ((x+#1)*(x+#2)=x^^^#2+#8)","solveFor x",

                   "errorBound (eps=#0)","solutions L"];

    val fmz =

      ["equality ((x+#1)*(x+#2)=x^^^#2+#8)","solveFor x","errorBound (eps=#0)",

       "solutions L"] : string list

    ML>

    ML> val spec as (dom, pbt, met) = ("SqRoot.thy",["univariate","equation"],

                                  ("SqRoot.thy","no_met"));

    val dom = "SqRoot.thy" : string

    val pbt = ["univariate","equation"] : string list

    val met = ("SqRoot.thy","no_met") : string * string

 \end{verbatim}}%size

 ... and the specification {\tt spec} of a domain {\tt dom}, a problem type {\tt pbt} and a method {\tt met}. Note that the equation is such, that it is not immediatly clear, what type it is in particular (it could be a polynomial of degree 2; but, for sure, the type is some specialized type of a univariate equation). Thus, no method ({\tt no\_met}) can be specified for solving the problem.

 Nevertheless this specification is sufficient for automatically solving the equation --- the appropriate method will be found by refinement within the hierarchy of problem types.

 \section{Initialize the calculation}

 The start of a new proof requires the following initializations: The proof state is given by a proof tree {\tt ctree} and a position {\tt pos'}; both are empty at the beginning. The tactic {\tt Init\_Proof} is, like all other tactics, paired with an identifier of type {\tt string} for technical reasons.

 {\footnotesize\begin{verbatim}

    ML>  val (mID,m) = ("Init_Proof",Init_Proof (fmz, (dom,pbt,met)));

    val mID = "Init_Proof" : string

    val m =

      Init_Proof

        (["equality ((x+#1)*(x+#2)=x^^^#2+#8)","solveFor x","errorBound (eps=#0)",

          "solutions L"],("SqRoot.thy",[#,#],(#,#))) : mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me (mID,m) e_pos' c EmptyPtree;

    val p = ([],Pbl) : pos'

    val f = Form' (PpcKF (0,EdUndef,0,Nundef,(#,#))) : mout

    val nxt = ("Refine_Tacitly",Refine_Tacitly ["univariate","equation"])

      : string * mstep

    val pt =

      Nd

        (PblObj

           {branch=#,cell=#,env=#,loc=#,meth=#,model=#,origin=#,ostate=#,probl=#,

            result=#,spec=#},[]) : ctree

    \end{verbatim}}%size

 The mathematics engine {\tt me} returns the resulting formula {\tt f} of type {\tt mout} (which in this case is a problem), the next tactic {\tt nxt}, and a new proof state ({\tt ctree}, {\tt pos'}).

 We can convince ourselves, that the problem is still empty, by increasing {\tt Compiler.Control.Print.printDepth}:

 {\footnotesize\begin{verbatim}

    ML> Compiler.Control.Print.printDepth:=8; (*4 default*)

    val it = () : unit

    ML>

    ML> f;

    val it =

      Form'

        (PpcKF

           (0,EdUndef,0,Nundef,

            (Problem [],

             {Find=[Incompl "solutions []"],

              Given=[Incompl "equality",Incompl "solveFor"],Relate=[],

              Where=[False "matches (?a = ?b) e_"],With=[]}))) : mout

 \end{verbatim}}%size

 Recall, please, the format of a problem as presented in sect.\ref{pbl} on p.\pageref{pbl}; such an 'empty' problem can be found above encapsulated by several constructors containing additional data (necessary for the dialog guide, not relevant here).\\

 {\it In the sequel we will omit output of the {\tt me} if it is not important for the respective context}.\\

 In general, the dialog guide will hide the following two tactics {\tt Refine\_Tacitly} and {\tt Model\_Problem} from the user.

 {\footnotesize\begin{verbatim}

    ML>  nxt;

    val it = ("Refine_Tacitly",Refine_Tacitly ["univariate","equation"])

      : string * mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val nxt = ("Model_Problem",Model_Problem ["normalize","univariate","equation"])

      : string * mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

 \end{verbatim}}%size

 \section{The phase of modeling} 

 comprises the input of the items of the problem; the {\tt me} can help by use of the formalization tacitly transferred by {\tt Init\_Proof}. In particular, the {\tt me} in general 'knows' the next promising tactic; the first one has been returned by the (hidden) tactic {\tt Model\_Problem}.

 {\footnotesize\begin{verbatim}

    ML>  nxt;

    val it =

      ("Add_Given",Add_Given "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)")

      : string * mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val nxt = ("Add_Given",Add_Given "solveFor x") : string * mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val nxt = ("Add_Find",Add_Find "solutions L") : string * mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt; 

    val f = Form' (PpcKF (0,EdUndef,0,Nundef,(#,#))) : mout

 \end{verbatim}}%size

 \noindent Now the problem is 'modeled', all items are input. We convince ourselves by increasing {\tt Compiler.Control.Print.printDepth} once more.

 {\footnotesize\begin{verbatim}

    ML>  Compiler.Control.Print.printDepth:=8;

    ML>  f;

    val it =

      Form'

        (PpcKF

           (0,EdUndef,0,Nundef,

            (Problem [],

             {Find=[Correct "solutions L"],

              Given=[Correct "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)",

                     Correct "solveFor x"],Relate=[],Where=[],With=[]}))) : mout

 \end{verbatim}}%size

 %One of the input items is considered {\tt Superfluous} by the {\tt me} consulting the problem type {\tt ["univariate","equation"]}. The {\tt ErrorBound}, however, could become important in case the equation only could be solved by some iteration method.

 \section{The phase of specification} 

 This phase provides for explicit determination of the domain, the problem type, and the method to be used. In particular, the search for the appropriate problem type is being supported. There are two tactics for this purpose: {\tt Specify\_Problem} generates feedback on how a candidate of a problem type matches the current problem, and {\tt Refine\_Problem} provides help by the system, if the user gets lost.

 {\footnotesize\begin{verbatim}

 ML> nxt;

    val it = ("Specify_Domain",Specify_Domain "SqRoot.thy") : string * mstep

    ML>

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val nxt =

      ("Specify_Problem",Specify_Problem ["normalize","univariate","equation"])

      : string * mstep

    val pt =

      Nd

        (PblObj

           {branch=#,cell=#,env=#,loc=#,meth=#,model=#,origin=#,ostate=#,probl=#,

               result=#,spec=#},[]) : ctree

 \end{verbatim}}%size

 The {\tt me} is smart enough to know the appropriate problem type (transferred tacitly with {\tt Init\_Proof}). In order to challenge the student, the dialog guide may hide this information; then the {\tt me} works as follows.

 {\footnotesize\begin{verbatim}

    ML> val nxt = ("Specify_Problem",

                Specify_Problem ["polynomial","univariate","equation"]);

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f = Form' (PpcKF (0,EdUndef,0,Nundef,(#,#))) : mout

    val nxt =

      ("Refine_Problem",Refine_Problem ["normalize","univariate","equation"])

      : string * mstep

    ML>

    ML> val nxt = ("Specify_Problem",

                Specify_Problem ["linear","univariate","equation"]);

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f =

      Form'

        (PpcKF

           (0,EdUndef,0,Nundef,

            (Problem ["linear","univariate","equation"],

             {Find=[Correct "solutions L"],

              Given=[Correct "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)",

                     Correct "solveFor x"],Relate=[],

              Where=[False

                     "matches (?a + ?b * x = #0) ((x + #1) * (x + #2) = x ^^^ #2 + #8)"],

              With=[]}))) : mout 

 \end{verbatim}}%size

 Again assuming that the dialog guide hide the next tactic proposed by the {\tt me}, and the student gets lost, {\tt Refine\_Problem} always 'knows' the way out, if applied to the problem type {\tt["univariate","equation"]}.

 {\footnotesize\begin{verbatim}

    ML> val nxt = ("Refine_Problem",

                   Refine_Problem ["linear","univariate","equation

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f = Problems (RefinedKF [NoMatch #]) : mout

    ML>

    ML>  Compiler.Control.Print.printDepth:=9;f;Compiler.Control.Print.printDepth:=4;

    val f =

      Problems

        (RefinedKF

           [NoMatch

              (["linear","univariate","equation"],

               {Find=[Correct "solutions L"],

                Given=[Correct "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)",

                       Correct "solveFor x"],Relate=[],

                Where=[False

                      "matches (?a + ?b * x = #0) ((x + #1) * (x + #2) = x ^^^ #2 + #8)"],

                With=[]})]) : mout

    ML>

    ML> val nxt = ("Refine_Problem",Refine_Problem ["univariate","equation"]);

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f =

      Problems

        (RefinedKF [Matches #,NoMatch #,NoMatch #,NoMatch #,NoMatch #,Matches #])

      : mout

    ML>

    ML>

    ML>  Compiler.Control.Print.printDepth:=9;f;Compiler.Control.Print.printDepth:=4;

    val f =

      Problems

        (RefinedKF

           [Matches

              (["univariate","equation"],

               {Find=[Correct "solutions L"],

                Given=[Correct "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)",

                       Correct "solveFor x"],Relate=[],

                Where=[Correct

                With=[]}),

            NoMatch

              (["linear","univariate","equation"],

               {Find=[Correct "solutions L"],

                Given=[Correct "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)",

                       Correct "solveFor x"],Relate=[],

                Where=[False

                       "matches (?a + ?b * x = #0) ((x + #1) * (x + #2) = x ^^^ #2 + #8)"],

                   With=[]}),

            NoMatch

              ...

              ...   

            Matches

              (["normalize","univariate","equation"],

               {Find=[Correct "solutions L"],

                Given=[Correct "equality ((x + #1) * (x + #2) = x ^^^ #2 + #8)",

                       Correct "solveFor x"],Relate=[],Where=[],With=[]})]) : mout

 \end{verbatim}}%size

 The tactic {\tt Refine\_Problem} returns all matches to problem types along the path traced in the problem hierarchy (anlogously to the authoring tool for refinement in sect.\ref{refine} on p.\pageref{refine}) --- a lot of information to be displayed appropriately in the hiearchy browser~!

 \section{The phase of solving} 

 This phase starts by invoking a method, which acchieves the normal form within two tactics, {\tt Rewrite rnorm\_equation\_add} and {\tt Rewrite\_Set SqRoot\_simplify}:

 {\footnotesize\begin{verbatim} 

    ML> nxt;

    val it = ("Apply_Method",Apply_Method ("SqRoot.thy","norm_univar_equation"))

      : string * mstep

    ML>

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f =

      Form' (FormKF (~1,EdUndef,1,Nundef,"(x + #1) * (x + #2) = x ^^^ #2 + #8"))

    val nxt =

      ("Rewrite", Rewrite

         ("rnorm_equation_add","~ ?b =!= #0 ==> (?a = ?b) = (?a + #-1 * ?b = #0)"))

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f =

      Form' (FormKF (~1,EdUndef,1,Nundef,

            "(x + #1) * (x + #2) + #-1 * (x ^^^ #2 + #8) = #0")) : mout

    val nxt = ("Rewrite_Set",Rewrite_Set "SqRoot_simplify") : string * mstep

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f = Form' (FormKF (~1,EdUndef,1,Nundef,"#-6 + #3 * x = #0")) : mout

    val nxt = ("Subproblem",Subproblem ("SqRoot.thy",[#,#])) : string * mstep

 \end{verbatim}}%size

 Now the normal form {\tt \#-6 + \#3 * x = \#0} is the input to a subproblem, which again allows for specification of the type of equation, and the respective method:

 {\footnotesize\begin{verbatim}

    ML> nxt;

    val it = ("Subproblem",Subproblem ("SqRoot.thy",["univariate","equation"]))

    ML>   

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f =

      Form' (FormKF

           (~1,EdUndef,1,Nundef,"Subproblem (SqRoot.thy, [univariate, equation])"))

      : mout

    val nxt = ("Refine_Tacitly",Refine_Tacitly ["univariate","equation"])

    ML>

    ML> val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val nxt = ("Model_Problem",Model_Problem ["linear","univariate","equation"])

 \end{verbatim}}%size

 As required, the tactic {\tt Refine ["univariate","equation"]} selects the appropriate type of equation from the problem hierarchy, which can be seen by the tactic {\tt Model\_Problem ["linear","univariate","equation"]} prosed by the system.

 Again the whole phase of modeling and specification follows; we skip it here, and \isac's dialog guide may decide to do so as well.

 \section{The final phase: check the post-condition}

 The type of problems solved by \isac{} are so-called 'example construction problems' as shown above. The most characteristic point of such a problem is the post-condition. The handling of the post-condition in the given context is an open research question.

 Thus the post-condition is just mentioned, in our example for both, the problem and the subproblem:

 {\footnotesize\begin{verbatim}

    ML> nxt;

    val it = ("Check_Postcond",Check_Postcond ["linear","univariate","equation"])

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f = Form' (FormKF (~1,EdUndef,1,Nundef,"[x = #2]")) : mout

    val nxt =

      ("Check_Postcond",Check_Postcond ["normalize","univariate","equation"])

    ML>

    ML>  val (p,_,f,nxt,_,pt) = me nxt p [1] pt;

    val f = Form' (FormKF (~1,EdUndef,0,Nundef,"[x = #2]")) : mout

    val nxt = ("End_Proof'",End_Proof') : string * mstep

 \end{verbatim}}%size

 The next tactic proposed by the system, {\tt End\_Proof'} indicates that the proof has finished successfully.\\

 {\it The tactics proposed by the system need {\em not} be followed by the user; the user is free to choose other tactics, and the system will report, if this is applicable at the respective proof state, or not~! The reader may try out~!}

 \part{Systematic description}

 \chapter{The structure of the knowledge base}

 \section{Tactics and data}

 First we view the ME from outside, i.e. we regard tactics and relate them to the knowledge base (KB). W.r.t. the KB we address the atomic items which have to be implemented in detail by the authors of the KB

 \footnote{Some of these items are fetched by the tactics from intermediate storage within the ME, and not directly from the KB.}

 . The items are listed in alphabetical order in Tab.\ref{kb-items} on p.\pageref{kb-items}.

 {\begin{table}[h]

 \caption{Atomic items of the KB} \label{kb-items}

 %\tabcolsep=0.3mm

 \begin{center}

 \def\arraystretch{1.0}

 \begin{tabular}{lp{9.0cm}}

 abbrevation & description \\

 \hline

 &\\

 {\it calc\_list}

 & associationlist of the evaluation-functions {\it eval\_fn}\\

 {\it eval\_fn}

 & evaluation-function for numerals and for predicates coded in SML\\

 {\it eval\_rls   }

 & ruleset {\it rls} for simplifying expressions with {\it eval\_fn}s\\

 {\it fmz}

 & formalization, i.e. a minimal formula representation of an example \\

 {\it met}

 & a method, i.e. a datastructure holding all informations for the solving phase ({\it rew\_ord}, {\it program}, etc.)\\

 {\it metID}

 & reference to a {\it met}\\

 {\it op}

 & operator as key to an {\it eval\_fn} in a {\it calc\_list}\\

 {\it pbl}

 & problem, i.e. a node in the problem-hierarchy\\

 {\it pblID}

 & reference to a {\it pbl}\\

 {\it rew\_ord}

 & rewrite-order\\

 {\it rls}

 & ruleset, i.e. a datastructure holding theorems {\it thm} and operators {\it op} for simplification (with a {\it rew\_ord})\\

 {\it Rrls}

 & ruleset for 'reverse rewriting' (an \isac-technique generating stepwise rewriting, e.g. for cancelling fractions)\\

 {\it program}

 & script describing algorithms by tactics, part of a {\it met} \\

 {\it norm\_rls}

 & special ruleset calculating a normalform, associated with a {\it thy}\\

 {\it spec}

 & specification, i.e. a tripel ({\it thyID, pblID, metID})\\

 {\it subs}

 & substitution, i.e. a list of variable-value-pairs\\

 {\it term}

 & Isabelle term, i.e. a formula\\

 {\it thm}

 & theorem\\     

 {\it thy}

 & theory\\

 {\it thyID}

 & reference to a {\it thy} \\

 \end{tabular}\end{center}\end{table}

 }

 The relations between tactics and data items are shown in Tab.\ref{tac-kb}on p.\pageref{tac-kb}.

 {\def\arraystretch{1.2}

 \begin{table}[h]

 \caption{Which tactic uses which KB's item~?} \label{tac-kb}

 \tabcolsep=0.3mm

 \begin{center}

 \begin{tabular}{|ll||cccc|ccc|cccc|} \hline

 tactic  &input &    &    &    &norm\_&   &rew\_&rls &eval\_&eval\_&calc\_&   \\

         &      &thy &program &Rrls&rls  &thm &ord  &Rrls&fn    &rls   &list  &dsc\\

 \hline\hline

 Init\_Proof

         &fmz   & x  &    &    & x   &    &     &    &      &      &      & x \\

         &spec  &    &    &    &     &    &     &    &      &      &      &   \\

 \hline

 \multicolumn{13}{|l|}{model phase}\\

 \hline

 Add\_*  &term  & x  &    &    & x   &    &     &    &      &      &      & x \\

 FormFK  &model & x  &    &    & x   &    &     &    &      &      &      & x \\

 \hline

 \multicolumn{13}{|l|}{specify phase}\\

 \hline

 Specify\_Theory 

         &thyID & x  &    &    & x   &    &     &    & x    & x    &      & x \\

 Specify\_Problem 

         &pblID & x  &    &    & x   &    &     &    & x    & x    &      & x \\

 Refine\_Problem 

            &pblID & x  &    &    & x   &    &     &    & x    & x    &      & x \\

 Specify\_Method 

         &metID & x  &    &    & x   &    &     &    & x    & x    &      & x \\

 Apply\_Method 

         &metID & x  & x  &    & x   &    &     &    & x    & x    &      & x \\

 \hline

 \multicolumn{13}{|l|}{solve phase}\\

 \hline

 Rewrite,\_Inst 

         &thm   & x  & x  &    &     & x  &met  &    & x    &met   &      &   \\

 Rewrite, Detail

         &thm   & x  & x  &    &     & x  &rls  &    & x    &rls   &      &   \\

 Rewrite, Detail

         &thm   & x  & x  &    &     & x  &Rrls &    & x    &Rrls  &      &   \\

 Rewrite\_Set,\_Inst

         &rls   & x  & x  &    &     &    &     & x  & x    & x    &      &   \\

 Calculate  

         &op    & x  & x  &    &     &    &     &    &      &      & x    &   \\

 Substitute 

         &subs  & x  &    &    & x   &    &     &    &      &      &      &   \\

         &      &    &    &    &     &    &     &    &      &      &      &   \\

 SubProblem 

         &spec  & x  & x  &    & x   &    &     &    & x    & x    &      & x \\

         &fmz   &    &    &    &     &    &     &    &      &      &      &   \\

 \hline

 \end{tabular}\end{center}\end{table}

 }

 \section{\isac's theories}

 \isac's theories build upon Isabelles theories for high-order-logic (HOL) up to the respective development of real numbers ({\tt HOL/Real}). Theories have a special format defined in \cite{Isa-ref} and the suffix {\tt *.thy}; usually theories are paired with SML-files having the same filename and the suffix {\tt *.ML}.

 \isac's theories represent the deductive part of \isac's knowledge base, the hierarchy of theories is structured accordingly. The {\tt *.ML}-files, however, contain {\em all} data of the other two axes of the knowledge base, the problems and the methods (without presenting their respective structure, which is done by the problem browser and the method browser, see \ref{pbt}).

 Tab.\ref{theories} on p.\pageref{theories} lists the basic theories planned to be implemented in version \isac.1. We expext the list to be expanded in the near future, actually, have a look to the theory browser~!

 The first three theories in the list do {\em not} belong to \isac's knowledge base; they are concerned with \isac's script-language for methods and listed here for completeness.

 {\begin{table}[h]

 \caption{Theories in \isac-version I} \label{theories}

 %\tabcolsep=0.3mm

 \begin{center}

 \def\arraystretch{1.0}

 \begin{tabular}{lp{9.0cm}}

 theory & description \\

 \hline

 &\\

 ListI.thy

 & assigns identifiers to the functions defined in {\tt Isabelle2002/src/HOL/List.thy} and (intermediatly~?) defines some more list functions\\

 ListI.ML

 & {\tt eval\_fn} for the additional list functions\\

 Tools.thy

 & functions required for the evaluation of scripts\\

 Tools.ML

 & the respective {\tt eval\_fn}s\\

 Script.thy

 & prerequisites for scripts: types, tactics, tacticals,\\

 Script.ML

 & sets of tactics and functions for internal use\\

 & \\

 \hline

 & \\

 Typefix.thy

 & an intermediate hack for escaping type errors\\

 Descript.thy

 & {\it description}s for the formulas in {\it model}s and {\it problem}s\\

 Atools

 & (re-)definition of operators; general predicates and functions for preconditions; theorems for the {\tt eval\_rls}\\

 Float

 & floating point numerals\\

 Equation

 & basic notions for equations and equational systems\\

 Poly

 & polynomials\\

 PolyEq

 & polynomial equations and equational systems \\

 Rational.thy

 & additional theorems for rationals\\

 Rational.ML

 & cancel, add and simplify rationals using (a generalization of) Euclids algorithm; respective reverse rulesets\\

 RatEq

 & equations on rationals\\

 Root

 & radicals; calculate normalform; respective reverse rulesets\\

 RootEq

 & equations on roots\\

 RatRootEq

 & equations on rationals and roots (i.e. on terms containing both operations)\\

 Vect

 & vector analysis\\

 Trig

 & trigonometriy\\

 LogExp

 & logarithms and exponential functions\\

 Calculus

 & nonstandard analysis\\

 Diff

 & differentiation\\

 DiffApp

 & applications of differentiaten (maxima-minima-problems)\\

 Test

 & (old) data for the test suite\\

 Isac

 & collects all \isac-theoris.\\

 \end{tabular}\end{center}\end{table}

 }

 \section{Data in {\tt *.thy}- and {\tt *.ML}-files}

 As already mentioned, theories come in pairs of {\tt *.thy}- and {\tt *.ML}-files with the same respective filename. How data are distributed between the two files is shown in Tab.\ref{thy-ML} on p.\pageref{thy-ML}.

 {\begin{table}[h]

 \caption{Data in {\tt *.thy}- and {\tt *.ML}-files} \label{thy-ML}

 \tabcolsep=2.0mm

 \begin{center}

 \def\arraystretch{1.0}

 \begin{tabular}{llp{7.7cm}}

 file & data & description \\

 \hline

 & &\\

 {\tt *.thy}

 & consts 

 & operators, predicates, functions, script-names ('{\tt Script} name \dots{\tt arguments}')

 \\

 & rules  

 & theorems: \isac{} uses Isabelles theorems if possible; additional theorems analoguous to such existing in Isabelle get the Isabelle-identifier attached an {\it I}

 \\& &\\

 {\tt *.ML}

 & {\tt theory' :=} 

 & the theory defined by the actual {\tt *.thy}-file is made accessible to \isac

 \\

 & {\tt eval\_fn}

 & evaluation function for operators and predicates, coded on the meta-level (SML); the identifier of such a function is a combination of the keyword {\tt eval\_} with the identifier of the function as defined in {\tt *.thy}

 \\

 & {\tt *\_simplify} 

 & the canonical simplifier for the actual theory, i.e. the identifier for this ruleset is a combination of the theories identifier and the keyword {\tt *\_simplify}

 \\

 & {\tt norm\_rls :=}

 & the canonical simplifier {\tt *\_simplify} is stored such that it is accessible for \isac

 \\

 & {\tt rew\_ord' :=}

 & the same for rewrite orders, if needed outside of one particular ruleset

 \\

 & {\tt ruleset' :=}

 & the same for rulesets (ordinary rulesets, reverse rulesets and {\tt eval\_rls})

 \\

 & {\tt calc\_list :=}

 & the same for {\tt eval\_fn}s, if needed outside of one particular ruleset (e.g. for a tactic {\tt Calculate} in a script)

 \\

 & {\tt store\_pbl}

 & problems defined within this {\tt *.ML}-file are made accessible for \isac

 \\

 & {\tt methods :=}

 & methods defined within this {\tt *.ML}-file are made accessible for \isac

 \\

 \end{tabular}\end{center}\end{table}

 }

 The order of the data-items within the theories should adhere to the order given in this list.

 \section{Formal description of the problem-hierarchy}

 %for Richard Lang

 \section{Script tactics}

 The tactics actually promote the calculation: they construct the prooftree behind the scenes, and they are the points during evaluation where the script-interpreter transfers control to the user. Here we only describe the sytax of the tactics; the semantics is described on p.\pageref{user-tactics} below in context with the tactics the student uses ('user-tactics'): there is a 1-to-1 correspondence between user-tactics and script-tactics.

 \part{Authoring on the knowledge}

 \section{Add a theorem}

 \section{Define and add a problem}

 \section{Define and add a predicate}

 \section{Define and add a method}

 \section{}

 \section{}

 \section{}

 \section{}

 \newpage

 \bibliography{bib/isac,bib/from-theses}

 \end{document}