doc-src/isac/jrocnik/eJMT-paper/jrocnik_eJMT.tex
changeset 42505 47abd8fbf5a7
parent 42503 67921e3c60ff
child 42506 480aee713e3d
equal deleted inserted replaced
42503:67921e3c60ff 42505:47abd8fbf5a7
   703 The language for both axes is defined in the axis at the bottom, deductive
   703 The language for both axes is defined in the axis at the bottom, deductive
   704 knowledge, in {\sisac} represented by Isabelle's theories.
   704 knowledge, in {\sisac} represented by Isabelle's theories.
   705 
   705 
   706 \subsection{Preparation of Simplifiers for the Program}\label{simp}
   706 \subsection{Preparation of Simplifiers for the Program}\label{simp}
   707 
   707 
   708 If it is clear how the later calculation should look like
   708 All evaluation in the prototyp's Lucas-Interpreter is done by term rewriting on
   709 %WN3 ... Allgem.<-->Konkret ist gut: aber hier ist 'calculation'
   709 Isabelle's terms, see \S\ref{math} below; in this section some of respective
   710 %WN3 zu weit weg: der Satz geh"ort bestenfalls gleich an den
   710 preparations are described. In order to work reliably with term rewriting, the
   711 %WN3 Anfang von \sect.3
   711 respective rule-sets must be confluent and terminating~\cite{nipk:rew-all-that},
   712 %WN3 
   712 then they are called (canonical) simplifiers. These properties do not go without
   713 %WN3 Im Folgenden sind einige Ungenauigkeiten:
   713 saying, their establishment is a difficult task for the programmer; this task is
   714  and when
   714 not yet supported in the prototype.\par
   715 which mathematic rule 
   715 
   716 %WN3 rewrite-rule oder theorem ! Ein Paper enth"alt viele Begriffe
   716 % If it is clear how the later calculation should look like
   717 %WN3 und man versucht, die Anzahl so gering wie m"oglich zu halten
   717 % %WN3 ... Allgem.<-->Konkret ist gut: aber hier ist 'calculation'
   718 %WN3 und die verbleibenden so pr"azise zu definieren wie m"oglich;
   718 % %WN3 zu weit weg: der Satz geh"ort bestenfalls gleich an den
   719 %WN3 das Vermeiden von Wiederholungen muss mit anderen Mitteln erfolgen,
   719 % %WN3 Anfang von \sect.3
   720 %WN3 als dieselbe Sache mit verschiedenen Namen zu benennen;
   720 % %WN3 
   721 %WN3 das gilt insbesonders f"ur technische Begriffe wie oben
   721 % %WN3 Im Folgenden sind einige Ungenauigkeiten:
   722 should be applied, it can be started to find ways of
   722 %  and when
   723 simplifications. 
   723 % which mathematic rule 
   724 %WN3 ... zu allgemein. Das Folgende w"urde durch einen Verweis in
   724 % %WN3 rewrite-rule oder theorem ! Ein Paper enth"alt viele Begriffe
   725 %WN3 das Programm auf S.12 gewinnen.
   725 % %WN3 und man versucht, die Anzahl so gering wie m"oglich zu halten
   726 This includes in e.g. the simplification of reational 
   726 % %WN3 und die verbleibenden so pr"azise zu definieren wie m"oglich;
   727 expressions or also rewrites of an expession.
   727 % %WN3 das Vermeiden von Wiederholungen muss mit anderen Mitteln erfolgen,
   728 \par
   728 % %WN3 als dieselbe Sache mit verschiedenen Namen zu benennen;
   729 %WN3 das Folgende habe ich aus dem Beispielprogramm auf S.12
   729 % %WN3 das gilt insbesonders f"ur technische Begriffe wie oben
   730 %WN3 gestrichen, weil es aus prinzipiellen Gr"unden unsch"on ist.
   730 % should be applied, it can be started to find ways of
   731 %WN3 Und es ist so kompliziert dass es mehr Platz zum Erkl"aren
   731 % simplifications. 
   732 %WN3 braucht, als es wert ist ...
   732 % %WN3 ... zu allgemein. Das Folgende w"urde durch einen Verweis in
   733 Obligate is the use of the function \texttt{drop\_questionmarks} 
   733 % %WN3 das Programm auf S.12 gewinnen.
   734 which excludes irrelevant symbols out of the expression. (Irrelevant symbols may 
   734 % This includes in e.g. the simplification of reational 
   735 be result out of the system during the calculation. The function has to be
   735 % expressions or also rewrites of an expession.
   736 applied for two reasons. First two make every placeholder in a expression 
   736 % \par
   737 useable as a constant and second to provide a better view at the frontend.) 
   737 % %WN3 das Folgende habe ich aus dem Beispielprogramm auf S.12
   738 \par
   738 % %WN3 gestrichen, weil es aus prinzipiellen Gr"unden unsch"on ist.
   739 %WN3 Da kommt eine ganze Reihe von Ungenauigkeiten:
   739 % %WN3 Und es ist so kompliziert dass es mehr Platz zum Erkl"aren
   740 Most rewrites are represented through rulesets
   740 % %WN3 braucht, als es wert ist ...
   741 %WN3 ... das ist schlicht falsch:
   741 % Obligate is the use of the function \texttt{drop\_questionmarks} 
   742 %WN3 _alle_ rewrites werden durch rule-sets erzeugt (per definition
   742 % which excludes irrelevant symbols out of the expression. (Irrelevant symbols may 
   743 %WN3 dieser W"orter).
   743 % be result out of the system during the calculation. The function has to be
   744  this
   744 % applied for two reasons. First two make every placeholder in a expression 
   745 rulesets tell the machine which terms have to be rewritten into which
   745 % useable as a constant and second to provide a better view at the frontend.) 
   746 representation. 
   746 % \par
   747 %WN3 ... ist ein besonders "uberzeugendes Beispiel von Allgem.<-->Konkret:
   747 % %WN3 Da kommt eine ganze Reihe von Ungenauigkeiten:
   748 %WN3 so allgemein, wie es hier steht, ist es
   748 % Most rewrites are represented through rulesets
   749 %WN3 # f"ur einen Fachmann klar und nicht ganz fachgem"ass formuliert
   749 % %WN3 ... das ist schlicht falsch:
   750 %WN3   (a rule-set rewrites a certain term into another with certain properties)
   750 % %WN3 _alle_ rewrites werden durch rule-sets erzeugt (per definition
   751 %WN3 # f"ur einen Nicht-Fachmann trotz allem unverst"andlich.
   751 % %WN3 dieser W"orter).
   752 %WN3 
   752 %  this
   753 %WN3 Wenn schon allgemeine S"atze, dann unmittelbar auf das Beispiel
   753 % rulesets tell the machine which terms have to be rewritten into which
   754 %WN3 unten verweisen,
   754 % representation. 
   755 %WN3 oder besser: den Satz dorthin schreiben, wo er unmittelbar vom
   755 % %WN3 ... ist ein besonders "uberzeugendes Beispiel von Allgem.<-->Konkret:
   756 %WN3 Beispiel gefolgt wird.
   756 % %WN3 so allgemein, wie es hier steht, ist es
   757 In the upcoming programm a rewrite can be applied only in using
   757 % %WN3 # f"ur einen Fachmann klar und nicht ganz fachgem"ass formuliert
   758 such rulesets on existing terms.
   758 % %WN3   (a rule-set rewrites a certain term into another with certain properties)
   759 %WN3 Du willst wohl soetwas sagen wie ...
   759 % %WN3 # f"ur einen Nicht-Fachmann trotz allem unverst"andlich.
   760 %WN3 rewriting is the main concept to step-wise create and transform 
   760 % %WN3 
   761 %WN3 formulas in order to proceed towards a solution of a problem
   761 % %WN3 Wenn schon allgemeine S"atze, dann unmittelbar auf das Beispiel
   762 %WN3 ...?
   762 % %WN3 unten verweisen,
   763 \paragraph{The core} of our implemented problem is the Z-Transformation
   763 % %WN3 oder besser: den Satz dorthin schreiben, wo er unmittelbar vom
   764 %WN3 ^^^^^ ist nicht gut: was soll THE CORE vermitteln, wenn man die
   764 % %WN3 Beispiel gefolgt wird.
   765 %WN3 Seite "uberfliegt ? Dass hier das Zentrum Deiner Arbeit liegt ?
   765 % In the upcoming programm a rewrite can be applied only in using
   766 %WN3 
   766 % such rulesets on existing terms.
   767 %WN3 Das Folgende ist eine allgemeine Design-"Uberlegung, die entweder
   767 % %WN3 Du willst wohl soetwas sagen wie ...
   768 %WN3 vorne zur Einf"uhrung des Beispiels geh"ort,
   768 % %WN3 rewriting is the main concept to step-wise create and transform 
   769 %WN3 oder zur konkreten L"osung durch die Rechnung auf S.15/16.
   769 % %WN3 formulas in order to proceed towards a solution of a problem
   770 (remember the description of the running example, introduced by
   770 % %WN3 ...?
   771 Fig.\ref{fig-interactive} on p.\pageref{fig-interactive}) due the fact that the
   771 % \paragraph{The core} of our implemented problem is the Z-Transformation
   772 transformation itself would require higher math which isn't yet avaible in our system we decided to choose the way like it is applied in labratory and problem classes at our university - by applying transformation rules (collected in
   772 % %WN3 ^^^^^ ist nicht gut: was soll THE CORE vermitteln, wenn man die
   773 transformation tables).
   773 % %WN3 Seite "uberfliegt ? Dass hier das Zentrum Deiner Arbeit liegt ?
   774 \par
   774 % %WN3 
   775 %WN3 Zum Folgenden: 'axiomatization' ist schon in 3.1. angesprochen:
   775 % %WN3 Das Folgende ist eine allgemeine Design-"Uberlegung, die entweder
   776 %WN3 entweder dort erg"anzen, wenn's wichtig ist, oder weglassen.
   776 % %WN3 vorne zur Einf"uhrung des Beispiels geh"ort,
   777 Rules, in {\sisac{}}'s programming language can be designed by the use of
   777 % %WN3 oder zur konkreten L"osung durch die Rechnung auf S.15/16.
   778 axiomatization. In this axiomatization we declare how a term has to look like
   778 % (remember the description of the running example, introduced by
   779 (left side) to be rewritten into another form (right side). Every line of this 
   779 % Fig.\ref{fig-interactive} on p.\pageref{fig-interactive}) due the fact that the
   780 axiomatizations starts with the name of the rule.
   780 % transformation itself would require higher math which isn't yet avaible in our system we decided to choose the way like it is applied in labratory and problem classes at our university - by applying transformation rules (collected in
   781 %WN3 Die folgenden Zeilen nehmen Platz weg: von hier auf S.6 verweisen
   781 % transformation tables).
   782 %\begin{example}
   782 % \par
   783 {\footnotesize
   783 % %WN3 Zum Folgenden: 'axiomatization' ist schon in 3.1. angesprochen:
   784   \label{eg:ruledef}
   784 % %WN3 entweder dort erg"anzen, wenn's wichtig ist, oder weglassen.
   785 %  \hfill\\
   785 % Rules, in {\sisac{}}'s programming language can be designed by the use of
   786   \begin{verbatim}
   786 % axiomatization. In this axiomatization we declare how a term has to look like
   787   axiomatization where
   787 % (left side) to be rewritten into another form (right side). Every line of this 
   788     rule1: ``1 = $\delta$[n]'' and
   788 % axiomatizations starts with the name of the rule.
   789     rule2: ``|| z || > 1 ==> z / (z - 1) = u [n]'' and
   789 
   790     rule3: ``|| z || < 1 ==> z / (z - 1) = -u [-n - 1]''
   790 The prototype rewrites using theorems only. Axioms which are theorems as well 
   791 \end{verbatim}
   791 have been already shown in \S\ref{eg:neuper1} on p.\pageref{eg:neuper1} , we
   792 %\end{example}
   792 assemble them in a rule-set and apply them as follows:
   793 }
   793 
   794 
   794 % %WN3 Die folgenden Zeilen nehmen Platz weg: von hier auf S.6 verweisen
   795 Rules can be summarized in a ruleset (collection of rules) and afterwards tried to be applied to a given expression as puttet over in following code.
   795 % %\begin{example}
       
   796 % {\footnotesize
       
   797 %   \label{eg:ruledef}
       
   798 % %  \hfill\\
       
   799 %   \begin{verbatim}
       
   800 %   axiomatization where
       
   801 %     rule1: ``1 = $\delta$[n]'' and
       
   802 %     rule2: ``|| z || > 1 ==> z / (z - 1) = u [n]'' and
       
   803 %     rule3: ``|| z || < 1 ==> z / (z - 1) = -u [-n - 1]''
       
   804 % \end{verbatim}
       
   805 % %\end{example}
       
   806 % }
       
   807 
       
   808 % Rules can be summarized in a ruleset (collection of rules) and afterwards tried % to be applied to a given expression as puttet over in following code.
   796 %WN3 ... ist schon mehrmals gesagt worden. 1-mal pr"azise sagen gen"ugt.
   809 %WN3 ... ist schon mehrmals gesagt worden. 1-mal pr"azise sagen gen"ugt.
   797 %WN3 
   810 %WN3 
   798 %WN3 mit dem append_rls unten verbirgst Du die ganze Komplexit"at von
   811 %WN3 mit dem append_rls unten verbirgst Du die ganze Komplexit"at von
   799 %WN3 rule-sets --- ich w"urde diese hier ausbreiten, damit man die
   812 %WN3 rule-sets --- ich w"urde diese hier ausbreiten, damit man die
   800 %WN3 Schwierigkeit von TP-based programming ermessen kann.
   813 %WN3 Schwierigkeit von TP-based programming ermessen kann.
   805 %WN3 mache ein 'grep -r "and rls";
   818 %WN3 mache ein 'grep -r "and rls";
   806 %WN3 auch in Build_Inverse_Z_Transform.thy hast Du 'Rls'
   819 %WN3 auch in Build_Inverse_Z_Transform.thy hast Du 'Rls'
   807 
   820 
   808 %\begin{example}
   821 %\begin{example}
   809 %  \hfill\\
   822 %  \hfill\\
       
   823 
   810   \label{eg:ruleapp}
   824   \label{eg:ruleapp}
   811   \begin{enumerate}
   825   \begin{enumerate}
   812 
   826 
   813   \item Store rules in ruleset:
   827   \item Store rules in ruleset:
   814   {\footnotesize\begin{verbatim}
   828   {\footnotesize\begin{verbatim}
   815   val inverse_Z = append_rls "inverse_Z" e_rls
   829 01  val inverse_Z = append_rls "inverse_Z" e_rls
   816     [ Thm ("rule1",num_str @{thm rule1}),
   830 02    [ Thm ("rule1",num_str @{thm rule1}),
   817       Thm ("rule2",num_str @{thm rule2}),
   831 03      Thm ("rule2",num_str @{thm rule2}),
   818       Thm ("rule3",num_str @{thm rule3})
   832 04      Thm ("rule3",num_str @{thm rule3})
   819     ];\end{verbatim}}
   833 05    ];\end{verbatim}}
   820 
   834 
   821   \item Define exression:
   835   \item Define exression:
   822   {\footnotesize\begin{verbatim}
   836   {\footnotesize\begin{verbatim}
   823   val sample_term = str2term "z/(z-1)+z/(z-</delta>)+1";\end{verbatim}}
   837 06  val sample_term = str2term "z/(z-1)+z/(z-</delta>)+1";\end{verbatim}}
       
   838 
       
   839 
   824 %WN3 vergleiche bitte obige Zeile mit den letzten 3 Zeilen aus S.8,
   840 %WN3 vergleiche bitte obige Zeile mit den letzten 3 Zeilen aus S.8,
   825 %WN3 diese entsprechen dem g"angigen functional-programming Stil.
   841 %WN3 diese entsprechen dem g"angigen functional-programming Stil.
   826 %WN3 
   842 
       
   843 
       
   844 
       
   845 
   827 %WN3 Super w"ar's, wenn Du hier schon die interne Darstellung von
   846 %WN3 Super w"ar's, wenn Du hier schon die interne Darstellung von
   828 %WN3 Isabelle Termen zeigen k"onntest, dann w"urde ich den entsprechenden Teil
   847 %WN3 Isabelle Termen zeigen k"onntest, dann w"urde ich den entsprechenden Teil
   829 %WN3 am Ende von S.8 und Anfang S.9 (erste 2.1 Zeilen) l"oschen.
   848 %WN3 am Ende von S.8 und Anfang S.9 (erste 2.1 Zeilen) l"oschen.
   830 
   849 
       
   850 %JR ich habe einige male über seite acht gelesen, finde aber dass der teil über
       
   851 %JR die interne representation dorthin besser passt da diese in unserem 
       
   852 %JR gezeigten beispiel ja in direkter verbindung zur gezeigtem funktion besteht
       
   853 %JR und so der übergang exzellent ist.
       
   854 
   831   \item Apply ruleset:
   855   \item Apply ruleset:
   832   {\footnotesize\begin{verbatim}
   856   {\footnotesize\begin{verbatim}
   833   val SOME (sample_term', asm) = 
   857 07  val SOME (sample_term', asm) = 
   834     rewrite_set_ thy true inverse_Z sample_term;\end{verbatim}}
   858 08    rewrite_set_ thy true inverse_Z sample_term;\end{verbatim}}
   835 
   859 
   836   \end{enumerate}
   860   \end{enumerate}
   837 %\end{example}
   861 %\end{example}
   838  
   862  
   839 %WN3 Wie oben gesagt, die folgenden allgemeinen S"atze scheinen
   863 %WN3 Wie oben gesagt, die folgenden allgemeinen S"atze scheinen
   840 %WN3 weniger wert als eine konkrete Beschreibung der rls-Struktur.
   864 %WN3 weniger wert als eine konkrete Beschreibung der rls-Struktur.
   841 %WN3 
   865 %WN3 
   842 %WN3 Ich nehme an, wir l"oschen das Folgende
   866 %WN3 Ich nehme an, wir l"oschen das Folgende
   843 %WN3 und ich spare mir Kommentare (ausser Du hast noch Zeit/Energie
   867 %WN3 und ich spare mir Kommentare (ausser Du hast noch Zeit/Energie
   844 %WN3 daf"ur und fragst extra nach).
   868 %WN3 daf"ur und fragst extra nach).
   845 The use of rulesets makes it much easier to develop our designated applications,
   869 
   846 but the programmer has to be careful and patient. When applying rulesets
   870 % The use of rulesets makes it much easier to develop our designated applications,
   847 two important issues have to be mentionend:
   871 % but the programmer has to be careful and patient. When applying rulesets
   848 \begin{enumerate}
   872 % two important issues have to be mentionend:
   849 \item How often the rules have to be applied? In case of
   873 % \begin{enumerate}
   850 transformations it is quite clear that we use them once but other fields
   874 % \item How often the rules have to be applied? In case of
   851 reuqire to apply rules until a special condition is reached (e.g.
   875 % transformations it is quite clear that we use them once but other fields
   852 a simplification is finished when there is nothing to be done left).
   876 % reuqire to apply rules until a special condition is reached (e.g.
   853 \item The order in which rules are applied often takes a big effect
   877 % a simplification is finished when there is nothing to be done left).
   854 and has to be evaluated for each purpose once again.
   878 % \item The order in which rules are applied often takes a big effect
   855 \end{enumerate}
   879 % and has to be evaluated for each purpose once again.
   856 In the special case of Signal Processing the rules defined in the
   880 % \end{enumerate}
   857 Example upwards have to be applied in a dedicated order to transform all 
   881 % In the special case of Signal Processing the rules defined in the
   858 constants first of all. After this first transformation step has been done it no 
   882 % Example upwards have to be applied in a dedicated order to transform all 
   859 mather which rule fit's next.
   883 % constants first of all. After this first transformation step has been done it no 
       
   884 % mather which rule fit's next.
       
   885 
   860 %WN3 Beim Paper-Schreiben ist mir aufgefallen, dass eine Konstante ZZ_1
   886 %WN3 Beim Paper-Schreiben ist mir aufgefallen, dass eine Konstante ZZ_1
   861 %WN3 (f"ur ${\cal Z}^{-1}$) die eben beschriebenen Probleme gel"ost
   887 %WN3 (f"ur ${\cal Z}^{-1}$) die eben beschriebenen Probleme gel"ost
   862 %WN3 h"atte: auf S.6 in rule1, auf S.12 in line 10 und in der Rechnung S.16
   888 %WN3 h"atte: auf S.6 in rule1, auf S.12 in line 10 und in der Rechnung S.16
   863 %WN3 hab' ich die Konstante schon eingef"uhrt.
   889 %WN3 hab' ich die Konstante schon eingef"uhrt.
   864 %WN3 
   890 %WN3 
   865 %WN3 Bite bei der rewrite_set_ demo oben bitte schummeln !
   891 %WN3 Bite bei der rewrite_set_ demo oben bitte schummeln !
       
   892 
       
   893 %JR TODO es is klein z bitte auf S.6 in rule1, auf S.12 in line 10 ausbessern
       
   894 %JR  ${\cal z}^{-1}$
       
   895 
       
   896 
       
   897 In the first step of upper code we extend the method's own ruleset with
       
   898 the predefined rules.\par
       
   899 When adding rules to this set we already have to take care on the order the
       
   900 rules we be applied in later context, this can be an important point when it
       
   901 comes to a case where one rule has to be applied explicite before an other.
       
   902 \par Rules are added to the ruleset with an unique name and a reference to their
       
   903 defined theorem. After summerizing this rules we still have the posibility to
       
   904 pick out a single one.
       
   905 \par In upper example we define an expression, as it comes up in our running
       
   906 example, it can be useful to take a look at \S\ref{funs} on p.\pageref{funs} to
       
   907 get to know {\sisac}'s' internal representation of variables.
       
   908 \par Upper step three is the final use of a ruleset for rewriting expression.
       
   909 The inline declared \ttfamily sample\_term' \normalfont is the result of applying the upper
       
   910 rule set one time to the before defined \texttt{sample\_term'}.
       
   911 
   866 
   912 
   867 \subsection{Preparation of ML-Functions}\label{funs}
   913 \subsection{Preparation of ML-Functions}\label{funs}
   868 The prototype's Lucas-Interpreter uses the {\sisac}-rewrite-engine for
   914 The prototype's Lucas-Interpreter uses the {\sisac}-rewrite-engine for
   869 all kinds of evaluation. Some functionality required in programming,
   915 all kinds of evaluation. Some functionality required in programming,
   870 however, cannot be accomplished by rewriting. So the prototype has a
   916 however, cannot be accomplished by rewriting. So the prototype has a