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 |