1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 % Electronic Journal of Mathematics and Technology (eJMT) %
3 % style sheet for LaTeX. Please do not modify sections %
4 % or commands marked 'eJMT'. %
6 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
10 \documentclass[12pt,a4paper]{article}% %
12 \usepackage{amsfonts,amsmath,amssymb} %
13 \usepackage[a4paper]{geometry} %
14 \usepackage{fancyhdr} %
16 \usepackage[pdftex]{hyperref} % see note below %
17 \usepackage{graphicx}% %
23 \newtheorem{theorem}{Theorem} %
24 \newtheorem{acknowledgement}[theorem]{Acknowledgement} %
25 \newtheorem{algorithm}[theorem]{Algorithm} %
26 \newtheorem{axiom}[theorem]{Axiom} %
27 \newtheorem{case}[theorem]{Case} %
28 \newtheorem{claim}[theorem]{Claim} %
29 \newtheorem{conclusion}[theorem]{Conclusion} %
30 \newtheorem{condition}[theorem]{Condition} %
31 \newtheorem{conjecture}[theorem]{Conjecture} %
32 \newtheorem{corollary}[theorem]{Corollary} %
33 \newtheorem{criterion}[theorem]{Criterion} %
34 \newtheorem{definition}[theorem]{Definition} %
35 \newtheorem{example}[theorem]{Example} %
36 \newtheorem{exercise}[theorem]{Exercise} %
37 \newtheorem{lemma}[theorem]{Lemma} %
38 \newtheorem{notation}[theorem]{Notation} %
39 \newtheorem{problem}[theorem]{Problem} %
40 \newtheorem{proposition}[theorem]{Proposition} %
41 \newtheorem{remark}[theorem]{Remark} %
42 \newtheorem{solution}[theorem]{Solution} %
43 \newtheorem{summary}[theorem]{Summary} %
44 \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} } %
45 {\ \rule{0.5em}{0.5em}} %
47 % eJMT page dimensions %
49 \geometry{left=2cm,right=2cm,top=3.2cm,bottom=4cm} %
51 % eJMT header & footer %
53 \newcounter{ejmtFirstpage} %
54 \setcounter{ejmtFirstpage}{1} %
56 \setlength{\headheight}{14pt} %
57 \geometry{left=2cm,right=2cm,top=3.2cm,bottom=4cm} %
58 \pagestyle{fancyplain} %
60 \fancyhead[c]{\small The Electronic Journal of Mathematics%
61 \ and Technology, Volume 1, Number 1, ISSN 1933-2823} %
63 \ifnum\value{ejmtFirstpage}=0% %
64 {\vtop to\hsize{\hrule\vskip .2cm\thepage}}% %
65 \else\setcounter{ejmtFirstpage}{0}\fi% %
68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70 % Please place your own definitions here
72 \def\isac{${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$}
73 \def\sisac{\footnotesize${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$}
76 \definecolor{lgray}{RGB}{238,238,238}
79 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
81 % How to use hyperref %
82 % ------------------- %
84 % Probably the only way you will need to use the hyperref %
85 % package is as follows. To make some text, say %
86 % "My Text Link", into a link to the URL %
87 % http://something.somewhere.com/mystuff, use %
89 % \href{http://something.somewhere.com/mystuff}{My Text Link}
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
97 \title{Trials with TP-based Programming
99 for Interactive Course Material}%
101 % Single author. Please supply at least your name,
102 % email address, and affiliation here.
104 \author{\begin{tabular}{c}
105 \textit{Jan Ro\v{c}nik} \\
106 jan.rocnik@student.tugraz.at \\
108 Graz University of Technologie\\
112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
114 % eJMT commands - do not change these %
119 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
125 Traditional course material in engineering disciplines lacks an
126 important component, interactive support for step-wise problem
127 solving. Theorem-Proving (TP) technology is appropriate for one part
128 of such support, in checking user-input. For the other part of such
129 support, guiding the learner towards a solution, another kind of
130 technology is required. %TODO ... connect to prototype ...
132 Both kinds of support can be acchieved by so-called
133 Lucas-Interpretation which combines deduction and computation and, for
134 the latter, uses a novel kind of programming language. This language
135 is based on (Computer) Theorem Proving (TP), thus called a ``TP-based
136 programming language''.
138 This paper is the experience report of the first ``application
139 programmer'' using this language for creating exercises in step-wise
140 problem solving for an advanced lab in Signal Processing. The tasks
141 involved in TP-based programming are described together with the
142 experience gained from a prototype of the programming language and of
145 The report concludes with a positive proof of concept, states
146 insuggicient usability of the prototype and captures the requirements
147 for further development of both, the programming language and the
152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
156 \thispagestyle{fancy} %
158 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
160 % Please use the following to indicate sections, subsections,
161 % etc. Please also use \subsubsection{...}, \paragraph{...}
162 % and \subparagraph{...} as necessary.
165 \section{Introduction}\label{intro}
167 % \paragraph{Didactics of mathematics}
168 %WN: wenn man in einem high-quality paper von 'didactics' spricht,
169 %WN muss man am state-of-the-art ankn"upfen -- siehe
170 %WN W.Neuper, On the Emergence of TP-based Educational Math Assistants
171 % faces a specific issue, a gap
172 % between (1) introduction of math concepts and skills and (2)
173 % application of these concepts and skills, which usually are separated
174 % into different units in curricula (for good reasons). For instance,
175 % (1) teaching partial fraction decomposition is separated from (2)
176 % application for inverse Z-transform in signal processing.
178 % \par This gap is an obstacle for applying math as an fundamental
179 % thinking technology in engineering: In (1) motivation is lacking
180 % because the question ``What is this stuff good for?'' cannot be
181 % treated sufficiently, and in (2) the ``stuff'' is not available to
182 % students in higher semesters as widespread experience shows.
184 % \paragraph{Motivation} taken by this didactic issue on the one hand,
185 % and ongoing research and development on a novel kind of educational
186 % mathematics assistant at Graz University of
187 % Technology~\footnote{http://www.ist.tugraz.at/isac/} promising to
188 % scope with this issue on the other hand, several institutes are
189 % planning to join their expertise: the Institute for Information
190 % Systems and Computer Media (IICM), the Institute for Software
191 % Technology (IST), the Institutes for Mathematics, the Institute for
192 % Signal Processing and Speech Communication (SPSC), the Institute for
193 % Structural Analysis and the Institute of Electrical Measurement and
194 % Measurement Signal Processing.
195 %WN diese Information ist f"ur das Paper zu spezielle, zu aktuell
196 %WN und damit zu verg"anglich.
197 % \par This thesis is the first attempt to tackle the above mentioned
198 % issue, it focuses on Telematics, because these specific studies focus
199 % on mathematics in \emph{STEOP}, the introductory orientation phase in
200 % Austria. \emph{STEOP} is considered an opportunity to investigate the
201 % impact of {\sisac}'s prototype on the issue and others.
204 Traditional course material in engineering disciplines lacks an
205 important component, interactive support for step-wise problem
206 solving. Theorem-Proving (TP) technology can provide such support by
207 specific services. An important part of such services is called
208 ``next-step-guidance'', generated by a specific kind of ``TP-based
209 programming language''. In the
210 {\sisac}-project~\footnote{http://www.ist.tugraz.at/projects/isac/} such
211 a language is prototyped in line with~\cite{plmms10} and built upon
213 Isabelle~\cite{Nipkow-Paulson-Wenzel:2002}\footnote{http://isabelle.in.tum.de/}.
214 The TP services are coordinated by a specific interpreter for the
215 programming language, called
216 Lucas-Interpreter~\cite{wn:lucas-interp-12}. The language and the
217 interpreter will be briefly re-introduced in order to make the paper
220 The main part of the paper is an account of first experiences
221 with programming in this TP-based language. The experience was gained
222 in a case study by the author. The author was considered an ideal
223 candidate for this study for the following reasons: as a student in
224 Telematics (computer science with focus on Signal Processing) he had
225 general knowledge in programming as well as specific domain knowledge
226 in Signal Processing; and he was {\em not} involved in the development of
227 {\sisac}'s programming language and interpeter, thus a novice to the
230 The goal of the case study was (1) some TP-based programs for
231 interactive course material for a specific ``Adavanced Signal
232 Processing Lab'' in a higher semester, (2) respective program
233 development with as little advice from the {\sisac}-team and (3) records
234 and comments for the main steps of development in an Isabelle theory;
235 this theory should provide guidelines for future programmers. An
236 excerpt from this theory is the main part of this paper.
238 The paper will use the problem in Fig.\ref{fig-interactive} as a
242 \includegraphics[width=140mm]{fig/isac-Ztrans-math-3}
243 %\includegraphics[width=140mm]{fig/isac-Ztrans-math}
244 \caption{Step-wise problem solving guided by the TP-based program}
245 \label{fig-interactive}
249 The problem is from the domain of Signal Processing and requests to
250 determine the inverse ${\cal Z}$-transform for a given term. Fig.\ref{fig-interactive}
251 also shows the beginning of the interactive construction of a solution
252 for the problem. This construction is done in the right window named
255 User-interaction on the Worksheet is {\em checked} and {\em guided} by
258 \item Formulas input by the user are {\em checked} by TP: such a
259 formula establishes a proof situation --- the prover has to derive the
260 formula from the logical context. The context is built up from the
261 formal specification of the problem (here hidden from the user) by the
263 \item If the user gets stuck, the program developed below in this
264 paper ``knows the next step'' and Lucas-Interpretation provides services
265 featuring so-called ``next-step-guidance''; this is out of scope of this
266 paper and can be studied in~\cite{gdaroczy-EP-13}.
267 \end{enumerate} It should be noted that the programmer using the
268 TP-based language is not concerned with interaction at all; we will
269 see that the program contains neither input-statements nor
270 output-statements. Rather, interaction is handled by the interpreter
273 So there is a clear separation of concerns: Dialogues are adapted by
274 dialogue authors (in Java-based tools), using TP services provided by
275 Lucas-Interpretation. The latter acts on programs developed by
276 mathematics-authors (in Isabelle/ML); their task is concern of this
279 \paragraph{The paper is structed} as follows: The introduction
280 \S\ref{intro} is followed by a brief re-introduction of the TP-based
281 programming language in \S\ref{PL}, which extends the executable
282 fragment of Isabelle's language (\S\ref{PL-isab}) by tactics which
283 play a specific role in Lucas-Interpretation and in providing the TP
284 services (\S\ref{PL-tacs}). The main part \S\ref{trial} describes
285 the main steps in developing the program for the running example:
286 prepare domain knowledge, implement the formal specification of the
287 problem, prepare the environment for the interpreter, implement the
288 program in \S\ref{isabisac} to \S\ref{progr} respectively.
289 The workflow of programming, debugging and testing is
290 described in \S\ref{workflow}. The conclusion \S\ref{conclusion} will
291 give directions identified for future development.
294 \section{\isac's Prototype for a Programming Language}\label{PL}
295 The prototype of the language and of the Lucas-Interpreter are briefly
296 described from the point of view of a programmer. The language extends
297 the executable fragment in the language of the theorem prover
298 Isabelle~\cite{Nipkow-Paulson-Wenzel:2002}\footnote{http://isabelle.in.tum.de/}.
300 \subsection{The Executable Fragment of Isabelle's Language}\label{PL-isab}
301 The executable fragment consists of data-type and function
302 definitions. It's usability even suggests that fragment for
303 introductory courses \cite{nipkow-prog-prove}. HOL is a typed logic
304 whose type system resembles that of functional programming
305 languages. Thus there are
307 \item[base types,] in particular \textit{bool}, the type of truth
308 values, \textit{nat}, \textit{int}, \textit{complex}, and the types of
309 natural, integer and complex numbers respectively in mathematics.
310 \item[type constructors] allow to define arbitrary types, from
311 \textit{set}, \textit{list} to advanced data-structures like
312 \textit{trees}, red-black-trees etc.
313 \item[function types,] denoted by $\Rightarrow$.
314 \item[type variables,] denoted by $^\prime a, ^\prime b$ etc, provide
315 type polymorphism. Isabelle automatically computes the type of each
316 variable in a term by use of Hindley-Milner type inference
317 \cite{pl:hind97,Milner-78}.
320 \textbf{Terms} are formed as in functional programming by applying
321 functions to arguments. If $f$ is a function of type
322 $\tau_1\Rightarrow \tau_2$ and $t$ is a term of type $\tau_1$ then
323 $f\;t$ is a term of type~$\tau_2$. $t\;::\;\tau$ means that term $t$
324 has type $\tau$. There are many predefined infix symbols like $+$ and
325 $\leq$ most of which are overloaded for various types.
327 HOL also supports some basic constructs from functional programming:
328 {\it\label{isabelle-stmts}
329 \begin{tabbing} 123\=\kill
330 \>$( \; {\tt if} \; b \; {\tt then} \; t_1 \; {\tt else} \; t_2 \;)$\\
331 \>$( \; {\tt let} \; x=t \; {\tt in} \; u \; )$\\
332 \>$( \; {\tt case} \; t \; {\tt of} \; {\it pat}_1
333 \Rightarrow t_1 \; |\dots| \; {\it pat}_n\Rightarrow t_n \; )$
335 \noindent The running example's program uses some of these elements
336 (marked by {\tt tt-font} on p.\pageref{s:impl}): for instance {\tt
337 let}\dots{\tt in} in lines {\rm 02} \dots {\rm 13}. In fact, the whole program
338 is an Isabelle term with specific function constants like {\tt
339 program}, {\tt Take}, {\tt Rewrite}, {\tt Subproblem} and {\tt
340 Rewrite\_Set} in lines {\rm 01, 03. 04, 07, 10} and {\rm 11, 12}
343 % Terms may also contain $\lambda$-abstractions. For example, $\lambda
344 % x. \; x$ is the identity function.
346 %JR warum auskommentiert? WN2...
347 %WN2 weil ein Punkt wie dieser in weiteren Zusammenh"angen innerhalb
348 %WN2 des Papers auftauchen m"usste; nachdem ich einen solchen
349 %WN2 Zusammenhang _noch_ nicht sehe, habe ich den Punkt _noch_ nicht
351 %WN2 Wenn der Punkt nicht weiter gebraucht wird, nimmt er nur wertvollen
352 %WN2 Platz f"ur Anderes weg.
354 \textbf{Formulae} are terms of type \textit{bool}. There are the basic
355 constants \textit{True} and \textit{False} and the usual logical
356 connectives (in decreasing order of precedence): $\neg, \land, \lor,
359 \textbf{Equality} is available in the form of the infix function $=$
360 of type $a \Rightarrow a \Rightarrow {\it bool}$. It also works for
361 formulas, where it means ``if and only if''.
363 \textbf{Quantifiers} are written $\forall x. \; P$ and $\exists x. \;
364 P$. Quantifiers lead to non-executable functions, so functions do not
365 always correspond to programs, for instance, if comprising \\$(
366 \;{\it if} \; \exists x.\;P \; {\it then} \; e_1 \; {\it else} \; e_2
369 \subsection{\isac's Tactics for Lucas-Interpretation}\label{PL-tacs}
370 The prototype extends Isabelle's language by specific statements
371 called tactics~\footnote{{\sisac}'s tactics are different from
372 Isabelle's tactics: the former concern steps in a calculation, the
373 latter concern proofs.} and tacticals. For the programmer these
374 statements are functions with the following signatures:
377 \item[Rewrite:] ${\it theorem}\Rightarrow{\it term}\Rightarrow{\it
378 term} * {\it term}\;{\it list}$:
379 this tactic appplies {\it theorem} to a {\it term} yielding a {\it
380 term} and a {\it term list}, the list are assumptions generated by
381 conditional rewriting. For instance, the {\it theorem}
382 $b\not=0\land c\not=0\Rightarrow\frac{a\cdot c}{b\cdot c}=\frac{a}{b}$
383 applied to the {\it term} $\frac{2\cdot x}{3\cdot x}$ yields
384 $(\frac{2}{3}, [x\not=0])$.
386 \item[Rewrite\_Set:] ${\it ruleset}\Rightarrow{\it
387 term}\Rightarrow{\it term} * {\it term}\;{\it list}$:
388 this tactic appplies {\it ruleset} to a {\it term}; {\it ruleset} is
389 a confluent and terminating term rewrite system, in general. If
390 none of the rules ({\it theorem}s) is applicable on interpretation
391 of this tactic, an exception is thrown.
393 % \item[Rewrite\_Inst:] ${\it substitution}\Rightarrow{\it
394 % theorem}\Rightarrow{\it term}\Rightarrow{\it term} * {\it term}\;{\it
397 % \item[Rewrite\_Set\_Inst:] ${\it substitution}\Rightarrow{\it
398 % ruleset}\Rightarrow{\it term}\Rightarrow{\it term} * {\it term}\;{\it
402 \item[Substitute:] ${\it substitution}\Rightarrow{\it
403 term}\Rightarrow{\it term}$: allows to access sub-terms.
406 \item[Take:] ${\it term}\Rightarrow{\it term}$:
407 this tactic has no effect in the program; but it creates a side-effect
408 by Lucas-Interpretation (see below) and writes {\it term} to the
411 \item[Subproblem:] ${\it theory} * {\it specification} * {\it
412 method}\Rightarrow{\it argument}\;{\it list}\Rightarrow{\it term}$:
413 this tactic is a generalisation of a function call: it takes an
414 \textit{argument list} as usual, and additionally a triple consisting
415 of an Isabelle \textit{theory}, an implicit \textit{specification} of the
416 program and a \textit{method} containing data for Lucas-Interpretation,
417 last not least a program (as an explicit specification)~\footnote{In
418 interactive tutoring these three items can be determined explicitly
421 The tactics play a specific role in
422 Lucas-Interpretation~\cite{wn:lucas-interp-12}: they are treated as
423 break-points where, as a side-effect, a line is added to a calculation
424 as a protocol for proceeding towards a solution in step-wise problem
425 solving. At the same points Lucas-Interpretation serves interactive
426 tutoring and hands over control to the user. The user is free to
427 investigate underlying knowledge, applicable theorems, etc. And the
428 user can proceed constructing a solution by input of a tactic to be
429 applied or by input of a formula; in the latter case the
430 Lucas-Interpreter has built up a logical context (initialised with the
431 precondition of the formal specification) such that Isabelle can
432 derive the formula from this context --- or give feedback, that no
433 derivation can be found.
435 \subsection{Tacticals as Control Flow Statements}
436 The flow of control in a program can be determined by {\tt if then else}
437 and {\tt case of} as mentioned on p.\pageref{isabelle-stmts} and also
438 by additional tacticals:
440 \item[Repeat:] ${\it tactic}\Rightarrow{\it term}\Rightarrow{\it
441 term}$: iterates over tactics which take a {\it term} as argument as
442 long as a tactic is applicable (for instance, {\tt Rewrite\_Set} might
445 \item[Try:] ${\it tactic}\Rightarrow{\it term}\Rightarrow{\it term}$:
446 if {\it tactic} is applicable, then it is applied to {\it term},
447 otherwise {\it term} is passed on without changes.
449 \item[Or:] ${\it tactic}\Rightarrow{\it tactic}\Rightarrow{\it
450 term}\Rightarrow{\it term}$: If the first {\it tactic} is applicable,
451 it is applied to the first {\it term} yielding another {\it term},
452 otherwise the second {\it tactic} is applied; if none is applicable an
455 \item[@@:] ${\it tactic}\Rightarrow{\it tactic}\Rightarrow{\it
456 term}\Rightarrow{\it term}$: applies the first {\it tactic} to the
457 first {\it term} yielding an intermediate term (not appearing in the
458 signature) to which the second {\it tactic} is applied.
460 \item[While:] ${\it term::bool}\Rightarrow{\it tactic}\Rightarrow{\it
461 term}\Rightarrow{\it term}$: if the first {\it term} is true, then the
462 {\it tactic} is applied to the first {\it term} yielding an
463 intermediate term (not appearing in the signature); the intermediate
464 term is added to the environment the first {\it term} is evaluated in
465 etc as long as the first {\it term} is true.
467 The tacticals are not treated as break-points by Lucas-Interpretation
468 and thus do neither contribute to the calculation nor to interaction.
470 \section{Concepts and Tasks in TP-based Programming}\label{trial}
471 %\section{Development of a Program on Trial}
473 This section presents all the concepts involved in TP-based
474 programming and all the tasks to be accomplished by programmers. The
475 presentation uses the running example from
476 Fig.\ref{fig-interactive} on p.\pageref{fig-interactive}.
478 \subsection{Mechanization of Math --- Domain Engineering}\label{isabisac}
480 %WN was Fachleute unter obigem Titel interessiert findet sich
481 %WN unterhalb des auskommentierten Textes.
483 %WN der Text unten spricht Benutzer-Aspekte anund ist nicht speziell
484 %WN auf Computer-Mathematiker fokussiert.
485 % \paragraph{As mentioned in the introduction,} a prototype of an
486 % educational math assistant called
487 % {{\sisac}}\footnote{{{\sisac}}=\textbf{Isa}belle for
488 % \textbf{C}alculations, see http://www.ist.tugraz.at/isac/.} bridges
489 % the gap between (1) introducation and (2) application of mathematics:
490 % {{\sisac}} is based on Computer Theorem Proving (TP), a technology which
491 % requires each fact and each action justified by formal logic, so
492 % {{{\sisac}{}}} makes justifications transparent to students in
493 % interactive step-wise problem solving. By that way {{\sisac}} already
496 % \item Introduction of math stuff (in e.g. partial fraction
497 % decomposition) by stepwise explaining and exercising respective
498 % symbolic calculations with ``next step guidance (NSG)'' and rigorously
499 % checking steps freely input by students --- this also in context with
500 % advanced applications (where the stuff to be taught in higher
501 % semesters can be skimmed through by NSG), and
502 % \item Application of math stuff in advanced engineering courses
503 % (e.g. problems to be solved by inverse Z-transform in a Signal
504 % Processing Lab) and now without much ado about basic math techniques
505 % (like partial fraction decomposition): ``next step guidance'' supports
506 % students in independently (re-)adopting such techniques.
508 % Before the question is answers, how {{\sisac}}
509 % accomplishes this task from a technical point of view, some remarks on
510 % the state-of-the-art is given, therefor follow up Section~\ref{emas}.
512 % \subsection{Educational Mathematics Assistants (EMAs)}\label{emas}
514 % \paragraph{Educational software in mathematics} is, if at all, based
515 % on Computer Algebra Systems (CAS, for instance), Dynamic Geometry
516 % Systems (DGS, for instance \footnote{GeoGebra http://www.geogebra.org}
517 % \footnote{Cinderella http://www.cinderella.de/}\footnote{GCLC
518 % http://poincare.matf.bg.ac.rs/~janicic/gclc/}) or spread-sheets. These
519 % base technologies are used to program math lessons and sometimes even
520 % exercises. The latter are cumbersome: the steps towards a solution of
521 % such an interactive exercise need to be provided with feedback, where
522 % at each step a wide variety of possible input has to be foreseen by
523 % the programmer - so such interactive exercises either require high
524 % development efforts or the exercises constrain possible inputs.
526 % \subparagraph{A new generation} of educational math assistants (EMAs)
527 % is emerging presently, which is based on Theorem Proving (TP). TP, for
528 % instance Isabelle and Coq, is a technology which requires each fact
529 % and each action justified by formal logic. Pushed by demands for
530 % \textit{proven} correctness of safety-critical software TP advances
531 % into software engineering; from these advancements computer
532 % mathematics benefits in general, and math education in particular. Two
533 % features of TP are immediately beneficial for learning:
535 % \paragraph{TP have knowledge in human readable format,} that is in
536 % standard predicate calculus. TP following the LCF-tradition have that
537 % knowledge down to the basic definitions of set, equality,
538 % etc~\footnote{http://isabelle.in.tum.de/dist/library/HOL/HOL.html};
539 % following the typical deductive development of math, natural numbers
540 % are defined and their properties
541 % proven~\footnote{http://isabelle.in.tum.de/dist/library/HOL/Number\_Theory/Primes.html},
542 % etc. Present knowledge mechanized in TP exceeds high-school
543 % mathematics by far, however by knowledge required in software
544 % technology, and not in other engineering sciences.
546 % \paragraph{TP can model the whole problem solving process} in
547 % mathematical problem solving {\em within} a coherent logical
548 % framework. This is already being done by three projects, by
549 % Ralph-Johan Back, by ActiveMath and by Carnegie Mellon Tutor.
551 % Having the whole problem solving process within a logical coherent
552 % system, such a design guarantees correctness of intermediate steps and
553 % of the result (which seems essential for math software); and the
554 % second advantage is that TP provides a wealth of theories which can be
555 % exploited for mechanizing other features essential for educational
558 % \subsubsection{Generation of User Guidance in EMAs}\label{user-guid}
560 % One essential feature for educational software is feedback to user
561 % input and assistance in coming to a solution.
563 % \paragraph{Checking user input} by ATP during stepwise problem solving
564 % is being accomplished by the three projects mentioned above
565 % exclusively. They model the whole problem solving process as mentioned
566 % above, so all what happens between formalized assumptions (or formal
567 % specification) and goal (or fulfilled postcondition) can be
568 % mechanized. Such mechanization promises to greatly extend the scope of
569 % educational software in stepwise problem solving.
571 % \paragraph{NSG (Next step guidance)} comprises the system's ability to
572 % propose a next step; this is a challenge for TP: either a radical
573 % restriction of the search space by restriction to very specific
574 % problem classes is required, or much care and effort is required in
575 % designing possible variants in the process of problem solving
576 % \cite{proof-strategies-11}.
578 % Another approach is restricted to problem solving in engineering
579 % domains, where a problem is specified by input, precondition, output
580 % and postcondition, and where the postcondition is proven by ATP behind
581 % the scenes: Here the possible variants in the process of problem
582 % solving are provided with feedback {\em automatically}, if the problem
583 % is described in a TP-based programing language: \cite{plmms10} the
584 % programmer only describes the math algorithm without caring about
585 % interaction (the respective program is functional and even has no
586 % input or output statements!); interaction is generated as a
587 % side-effect by the interpreter --- an efficient separation of concern
588 % between math programmers and dialog designers promising application
589 % all over engineering disciplines.
592 % \subsubsection{Math Authoring in Isabelle/ISAC\label{math-auth}}
593 % Authoring new mathematics knowledge in {{\sisac}} can be compared with
594 % ``application programing'' of engineering problems; most of such
595 % programing uses CAS-based programing languages (CAS = Computer Algebra
596 % Systems; e.g. Mathematica's or Maple's programing language).
598 % \paragraph{A novel type of TP-based language} is used by {{\sisac}{}}
599 % \cite{plmms10} for describing how to construct a solution to an
600 % engineering problem and for calling equation solvers, integration,
601 % etc~\footnote{Implementation of CAS-like functionality in TP is not
602 % primarily concerned with efficiency, but with a didactic question:
603 % What to decide for: for high-brow algorithms at the state-of-the-art
604 % or for elementary algorithms comprehensible for students?} within TP;
605 % TP can ensure ``systems that never make a mistake'' \cite{casproto} -
606 % are impossible for CAS which have no logics underlying.
608 % \subparagraph{Authoring is perfect} by writing such TP based programs;
609 % the application programmer is not concerned with interaction or with
610 % user guidance: this is concern of a novel kind of program interpreter
611 % called Lucas-Interpreter. This interpreter hands over control to a
612 % dialog component at each step of calculation (like a debugger at
613 % breakpoints) and calls automated TP to check user input following
614 % personalized strategies according to a feedback module.
616 % However ``application programing with TP'' is not done with writing a
617 % program: according to the principles of TP, each step must be
618 % justified. Such justifications are given by theorems. So all steps
619 % must be related to some theorem, if there is no such theorem it must
620 % be added to the existing knowledge, which is organized in so-called
621 % \textbf{theories} in Isabelle. A theorem must be proven; fortunately
622 % Isabelle comprises a mechanism (called ``axiomatization''), which
623 % allows to omit proofs. Such a theorem is shown in
624 % Example~\ref{eg:neuper1}.
626 The running example requires to determine the inverse $\cal
627 Z$-transform for a class of functions. The domain of Signal Processing
628 is accustomed to specific notation for the resulting functions, which
629 are absolutely summable and are called step-response: $u[n]$, where $u$ is the
630 function, $n$ is the argument and the brackets indicate that the
631 arguments are discrete. Surprisingly, Isabelle accepts the rules for
632 ${\cal Z}^{-1}$ in this traditional notation~\footnote{Isabelle
633 experts might be particularly surprised, that the brackets do not
634 cause errors in typing (as lists).}:
638 {\footnotesize\begin{tabbing}
639 123\=123\=123\=123\=\kill
641 \>axiomatization where \\
642 \>\> rule1: ``${\cal Z}^{-1}\;1 = \delta [n]$'' and\\
643 \>\> rule2: ``$\vert\vert z \vert\vert > 1 \Rightarrow {\cal Z}^{-1}\;z / (z - 1) = u [n]$'' and\\
644 \>\> rule3: ``$\vert\vert$ z $\vert\vert$ < 1 ==> z / (z - 1) = -u [-n - 1]'' and \\
646 \>\> rule4: ``$\vert\vert$ z $\vert\vert$ > $\vert\vert$ $\alpha$ $\vert\vert$ ==> z / (z - $\alpha$) = $\alpha^n$ $\cdot$ u [n]'' and\\
648 \>\> rule5: ``$\vert\vert$ z $\vert\vert$ < $\vert\vert$ $\alpha$ $\vert\vert$ ==> z / (z - $\alpha$) = -($\alpha^n$) $\cdot$ u [-n - 1]'' and\\
650 \>\> rule6: ``$\vert\vert$ z $\vert\vert$ > 1 ==> z/(z - 1)$^2$ = n $\cdot$ u [n]''
655 These 6 rules can be used as conditional rewrite rules, depending on
656 the respective convergence radius. Satisfaction from accordance with traditional notation
657 contrasts with the above word {\em axiomatization}: As TP-based, the
658 programming language expects these rules as {\em proved} theorems, and
659 not as axioms implemented in the above brute force manner; otherwise
660 all the verification efforts envisaged (like proof of the
661 post-condition, see below) would be meaningless.
663 Isabelle provides a large body of knowledge, rigorously proven from
664 the basic axioms of mathematics~\footnote{This way of rigorously
665 deriving all knowledge from first principles is called the
666 LCF-paradigm in TP.}. In the case of the ${\cal Z}$-Transform the most advanced
667 knowledge can be found in the theoris on Multivariate
668 Analysis~\footnote{http://isabelle.in.tum.de/dist/library/HOL/HOL-Multivariate\_Analysis}. However,
669 building up knowledge such that a proof for the above rules would be
670 reasonably short and easily comprehensible, still requires lots of
671 work (and is definitely out of scope of our case study).
673 At the state-of-the-art in mechanization of knowledge in engineering
674 sciences, the process does not stop with the mechanization of
675 mathematics traditionally used in these sciences. Rather, ``Formal
676 Methods''~\cite{ fm-03} are expected to proceed to formal and explicit
677 description of physical items. Signal Processing, for instance is
678 concerned with physical devices for signal acquisition and
679 reconstruction, which involve measuring a physical signal, storing it,
680 and possibly later rebuilding the original signal or an approximation
681 thereof. For digital systems, this typically includes sampling and
682 quantization; devices for signal compression, including audio
683 compression, image compression, and video compression, etc. ``Domain
684 engineering''\cite{db:dom-eng} is concerned with {\em specification}
685 of these devices' components and features; this part in the process of
686 mechanization is only at the beginning in domains like Signal
689 TP-based programming, concern of this paper, is determined to
690 add ``algorithmic knowledge'' to the mechanised body of knowledge.
691 % in Fig.\ref{fig:mathuni} on
692 % p.\pageref{fig:mathuni}. As we shall see below, TP-based programming
693 % starts with a formal {\em specification} of the problem to be solved.
696 % \includegraphics[width=110mm]{../../fig/jrocnik/math-universe-small}
697 % \caption{The three-dimensional universe of mathematics knowledge}
698 % \label{fig:mathuni}
701 % The language for both axes is defined in the axis at the bottom, deductive
702 % knowledge, in {\sisac} represented by Isabelle's theories.
704 \subsection{Preparation of Simplifiers for the Program}\label{simp}
706 All evaluation in the prototyp's Lucas-Interpreter is done by term rewriting on
707 Isabelle's terms, see \S\ref{meth} below; in this section some of respective
708 preparations are described. In order to work reliably with term rewriting, the
709 respective rule-sets must be confluent and terminating~\cite{nipk:rew-all-that},
710 then they are called (canonical) simplifiers. These properties do not go without
711 saying, their establishment is a difficult task for the programmer; this task is
712 not yet supported in the prototype.\par
714 % If it is clear how the later calculation should look like
715 % %WN3 ... Allgem.<-->Konkret ist gut: aber hier ist 'calculation'
716 % %WN3 zu weit weg: der Satz geh"ort bestenfalls gleich an den
717 % %WN3 Anfang von \sect.3
719 % %WN3 Im Folgenden sind einige Ungenauigkeiten:
721 % which mathematic rule
722 % %WN3 rewrite-rule oder theorem ! Ein Paper enth"alt viele Begriffe
723 % %WN3 und man versucht, die Anzahl so gering wie m"oglich zu halten
724 % %WN3 und die verbleibenden so pr"azise zu definieren wie m"oglich;
725 % %WN3 das Vermeiden von Wiederholungen muss mit anderen Mitteln erfolgen,
726 % %WN3 als dieselbe Sache mit verschiedenen Namen zu benennen;
727 % %WN3 das gilt insbesonders f"ur technische Begriffe wie oben
728 % should be applied, it can be started to find ways of
730 % %WN3 ... zu allgemein. Das Folgende w"urde durch einen Verweis in
731 % %WN3 das Programm auf S.12 gewinnen.
732 % This includes in e.g. the simplification of reational
733 % expressions or also rewrites of an expession.
735 % %WN3 das Folgende habe ich aus dem Beispielprogramm auf S.12
736 % %WN3 gestrichen, weil es aus prinzipiellen Gr"unden unsch"on ist.
737 % %WN3 Und es ist so kompliziert dass es mehr Platz zum Erkl"aren
738 % %WN3 braucht, als es wert ist ...
739 % Obligate is the use of the function \texttt{drop\_questionmarks}
740 % which excludes irrelevant symbols out of the expression. (Irrelevant symbols may
741 % be result out of the system during the calculation. The function has to be
742 % applied for two reasons. First two make every placeholder in a expression
743 % useable as a constant and second to provide a better view at the frontend.)
745 % %WN3 Da kommt eine ganze Reihe von Ungenauigkeiten:
746 % Most rewrites are represented through rulesets
747 % %WN3 ... das ist schlicht falsch:
748 % %WN3 _alle_ rewrites werden durch rule-sets erzeugt (per definition
749 % %WN3 dieser W"orter).
751 % rulesets tell the machine which terms have to be rewritten into which
753 % %WN3 ... ist ein besonders "uberzeugendes Beispiel von Allgem.<-->Konkret:
754 % %WN3 so allgemein, wie es hier steht, ist es
755 % %WN3 # f"ur einen Fachmann klar und nicht ganz fachgem"ass formuliert
756 % %WN3 (a rule-set rewrites a certain term into another with certain properties)
757 % %WN3 # f"ur einen Nicht-Fachmann trotz allem unverst"andlich.
759 % %WN3 Wenn schon allgemeine S"atze, dann unmittelbar auf das Beispiel
760 % %WN3 unten verweisen,
761 % %WN3 oder besser: den Satz dorthin schreiben, wo er unmittelbar vom
762 % %WN3 Beispiel gefolgt wird.
763 % In the upcoming programm a rewrite can be applied only in using
764 % such rulesets on existing terms.
765 % %WN3 Du willst wohl soetwas sagen wie ...
766 % %WN3 rewriting is the main concept to step-wise create and transform
767 % %WN3 formulas in order to proceed towards a solution of a problem
769 % \paragraph{The core} of our implemented problem is the Z-Transformation
770 % %WN3 ^^^^^ ist nicht gut: was soll THE CORE vermitteln, wenn man die
771 % %WN3 Seite "uberfliegt ? Dass hier das Zentrum Deiner Arbeit liegt ?
773 % %WN3 Das Folgende ist eine allgemeine Design-"Uberlegung, die entweder
774 % %WN3 vorne zur Einf"uhrung des Beispiels geh"ort,
775 % %WN3 oder zur konkreten L"osung durch die Rechnung auf S.15/16.
776 % (remember the description of the running example, introduced by
777 % Fig.\ref{fig-interactive} on p.\pageref{fig-interactive}) due the fact that the
778 % 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
779 % transformation tables).
781 % %WN3 Zum Folgenden: 'axiomatization' ist schon in 3.1. angesprochen:
782 % %WN3 entweder dort erg"anzen, wenn's wichtig ist, oder weglassen.
783 % Rules, in {\sisac{}}'s programming language can be designed by the use of
784 % axiomatization. In this axiomatization we declare how a term has to look like
785 % (left side) to be rewritten into another form (right side). Every line of this
786 % axiomatizations starts with the name of the rule.
788 The prototype rewrites using theorems only. Axioms which are theorems as well
789 have been already shown in \S\ref{eg:neuper1} on p.\pageref{eg:neuper1} , we
790 assemble them in a rule-set and apply them as follows:
792 % %WN3 Die folgenden Zeilen nehmen Platz weg: von hier auf S.6 verweisen
798 % axiomatization where
799 % rule1: ``1 = $\delta$[n]'' and
800 % rule2: ``|| z || > 1 ==> z / (z - 1) = u [n]'' and
801 % rule3: ``|| z || < 1 ==> z / (z - 1) = -u [-n - 1]''
806 % 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.
807 %WN3 ... ist schon mehrmals gesagt worden. 1-mal pr"azise sagen gen"ugt.
809 %WN3 mit dem append_rls unten verbirgst Du die ganze Komplexit"at von
810 %WN3 rule-sets --- ich w"urde diese hier ausbreiten, damit man die
811 %WN3 Schwierigkeit von TP-based programming ermessen kann.
812 %WN3 Eine Erkl"arung wie in 3.4 und 3.5 braucht viel Platz, der sich
813 %WN3 meines Erachtens mehr auszahlt als die allgemeinen S"atze
814 %WN3 am Ende von 3.2 auf S.8.
816 %WN3 mache ein 'grep -r "and rls";
817 %WN3 auch in Build_Inverse_Z_Transform.thy hast Du 'Rls'
825 \item Store rules in ruleset:
826 {\footnotesize\begin{verbatim}
827 01 val inverse_Z = append_rls "inverse_Z" e_rls
828 02 [ Thm ("rule1",num_str @{thm rule1}),
829 03 Thm ("rule2",num_str @{thm rule2}),
830 04 Thm ("rule3",num_str @{thm rule3})
833 \item Define exression:
834 {\footnotesize\begin{verbatim}
835 06 val sample_term = str2term "z/(z-1)+z/(z-</delta>)+1";\end{verbatim}}
838 %WN3 vergleiche bitte obige Zeile mit den letzten 3 Zeilen aus S.8,
839 %WN3 diese entsprechen dem g"angigen functional-programming Stil.
844 %WN3 Super w"ar's, wenn Du hier schon die interne Darstellung von
845 %WN3 Isabelle Termen zeigen k"onntest, dann w"urde ich den entsprechenden Teil
846 %WN3 am Ende von S.8 und Anfang S.9 (erste 2.1 Zeilen) l"oschen.
848 %JR ich habe einige male über seite acht gelesen, finde aber dass der teil über
849 %JR die interne representation dorthin besser passt da diese in unserem
850 %JR gezeigten beispiel ja in direkter verbindung zur gezeigtem funktion besteht
851 %JR und so der übergang exzellent ist.
854 {\footnotesize\begin{verbatim}
855 07 val SOME (sample_term', asm) =
856 08 rewrite_set_ thy true inverse_Z sample_term;\end{verbatim}}
861 %WN3 Wie oben gesagt, die folgenden allgemeinen S"atze scheinen
862 %WN3 weniger wert als eine konkrete Beschreibung der rls-Struktur.
864 %WN3 Ich nehme an, wir l"oschen das Folgende
865 %WN3 und ich spare mir Kommentare (ausser Du hast noch Zeit/Energie
866 %WN3 daf"ur und fragst extra nach).
868 % The use of rulesets makes it much easier to develop our designated applications,
869 % but the programmer has to be careful and patient. When applying rulesets
870 % two important issues have to be mentionend:
872 % \item How often the rules have to be applied? In case of
873 % transformations it is quite clear that we use them once but other fields
874 % reuqire to apply rules until a special condition is reached (e.g.
875 % a simplification is finished when there is nothing to be done left).
876 % \item The order in which rules are applied often takes a big effect
877 % and has to be evaluated for each purpose once again.
879 % In the special case of Signal Processing the rules defined in the
880 % Example upwards have to be applied in a dedicated order to transform all
881 % constants first of all. After this first transformation step has been done it no
882 % mather which rule fit's next.
884 %WN3 Beim Paper-Schreiben ist mir aufgefallen, dass eine Konstante ZZ_1
885 %WN3 (f"ur ${\cal Z}^{-1}$) die eben beschriebenen Probleme gel"ost
886 %WN3 h"atte: auf S.6 in rule1, auf S.12 in line 10 und in der Rechnung S.16
887 %WN3 hab' ich die Konstante schon eingef"uhrt.
889 %WN3 Bite bei der rewrite_set_ demo oben bitte schummeln !
891 %JR TODO es is klein z bitte auf S.6 in rule1, auf S.12 in line 10 ausbessern
895 In the first step of upper code we extend the method's own ruleset with
896 the predefined rules.\par
897 When adding rules to this set we already have to take care on the order the
898 rules we be applied in later context, this can be an important point when it
899 comes to a case where one rule has to be applied explicite before an other.
900 \par Rules are added to the ruleset with an unique name and a reference to their
901 defined theorem. After summerizing this rules we still have the posibility to
902 pick out a single one.
903 \par In upper example we define an expression, as it comes up in our running
904 example, it can be useful to take a look at \S\ref{funs} on p.\pageref{funs} to
905 get to know {\sisac}'s' internal representation of variables.
906 \par Upper step three is the final use of a ruleset for rewriting expression.
907 The inline declared \ttfamily sample\_term' \normalfont is the result of applying the upper
908 rule set one time to the before defined \texttt{sample\_term'}.
911 \subsection{Preparation of ML-Functions}\label{funs}
912 Some functionality required in programming, cannot be accomplished by
913 rewriting. So the prototype has a mechanism to call functions within
914 the rewrite-engine: certain redexes in Isabelle terms call these
915 functions written in SML~\cite{pl:milner97}, the implementation {\em
916 and} meta-language of Isabelle. The programmer has to use this
919 In the running example's program on p.\pageref{s:impl} the lines {\rm
920 05} and {\rm 06} contain such functions; we go into the details with
921 \textit{argument\_in X\_z;}. This function fetches the argument from a
922 function application: Line {\rm 03} in the example calculation on
923 p.\pageref{exp-calc} is created by line {\rm 06} of the example
924 program on p.\pageref{s:impl} where the program's environment assigns
925 the value \textit{X z} to the variable \textit{X\_z}; so the function
926 shall extract the argument \textit{z}.
928 \medskip In order to be recognised as a function constant in the
929 program source the constant needs to be declared in a theory, here in
930 \textit{Build\_Inverse\_Z\_Transform.thy}; then it can be parsed in
931 the context \textit{ctxt} of that theory:
936 argument'_in :: "real => real" ("argument'_in _" 10)
939 %^3.2^ ML {* val SOME t = parse ctxt "argument_in (X z)"; *}
940 %^3.2^ val t = Const ("Build_Inverse_Z_Transform.argument'_in", "RealDef.real ⇒ RealDef.real")
941 %^3.2^ $ (Free ("X", "RealDef.real ⇒ RealDef.real") $ Free ("z", "RealDef.real")): term
942 %^3.2^ \end{verbatim}}
944 %^3.2^ \noindent Parsing produces a term \texttt{t} in internal
945 %^3.2^ representation~\footnote{The attentive reader realizes the
946 %^3.2^ differences between interal and extermal representation even in the
947 %^3.2^ strings, i.e \texttt{'\_}}, consisting of \texttt{Const
948 %^3.2^ ("argument'\_in", type)} and the two variables \texttt{Free ("X",
949 %^3.2^ type)} and \texttt{Free ("z", type)}, \texttt{\$} is the term
951 The function body below is implemented directly in SML,
952 i.e in an \texttt{ML \{* *\}} block; the function definition provides
953 a unique prefix \texttt{eval\_} to the function name:
958 fun eval_argument_in _
959 "Build_Inverse_Z_Transform.argument'_in"
960 (t as (Const ("Build_Inverse_Z_Transform.argument'_in", _) $ (f $ arg))) _ =
961 if is_Free arg (*could be something to be simplified before*)
962 then SOME (term2str t ^ " = " ^ term2str arg, Trueprop $ (mk_equality (t, arg)))
964 | eval_argument_in _ _ _ _ = NONE;
968 \noindent The function body creates either creates \texttt{NONE}
969 telling the rewrite-engine to search for the next redex, or creates an
970 ad-hoc theorem for rewriting, thus the programmer needs to adopt many
971 technicalities of Isabelle, for instance, the \textit{Trueprop}
974 \bigskip This sub-task particularly sheds light on basic issues in the
975 design of a programming language, the integration of diffent language
976 layers, the layer of Isabelle/Isar and Isabelle/ML.
978 Another point of improvement for the prototype is the rewrite-engine: The
979 program on p.\pageref{s:impl} would not allow to contract the two lines {\rm 05}
982 {\small\it\label{s:impl}
984 123l\=123\=123\=123\=123\=123\=123\=((x\=123\=(x \=123\=123\=\kill
985 \>{\rm 05/6}\>\>\> (z::real) = argument\_in (lhs X\_eq) ;
988 \noindent because nested function calls would require creating redexes
989 inside-out; however, the prototype's rewrite-engine only works top down
990 from the root of a term down to the leaves.
992 How all these technicalities are to be checked in the prototype is
993 shown in \S\ref{flow-prep} below.
995 % \paragraph{Explicit Problems} require explicit methods to solve them, and within
996 % this methods we have some explicit steps to do. This steps can be unique for
997 % a special problem or refindable in other problems. No mather what case, such
998 % steps often require some technical functions behind. For the solving process
999 % of the Inverse Z Transformation and the corresponding partial fraction it was
1000 % neccessary to build helping functions like \texttt{get\_denominator},
1001 % \texttt{get\_numerator} or \texttt{argument\_in}. First two functions help us
1002 % to filter the denominator or numerator out of a fraction, last one helps us to
1003 % get to know the bound variable in a equation.
1005 % By taking \texttt{get\_denominator} as an example, we want to explain how to
1006 % implement new functions into the existing system and how we can later use them
1009 % \subsubsection{Find a place to Store the Function}
1011 % The whole system builds up on a well defined structure of Knowledge. This
1012 % Knowledge sets up at the Path:
1013 % \begin{center}\ttfamily src/Tools/isac/Knowledge\normalfont\end{center}
1014 % For implementing the Function \texttt{get\_denominator} (which let us extract
1015 % the denominator out of a fraction) we have choosen the Theory (file)
1016 % \texttt{Rational.thy}.
1018 % \subsubsection{Write down the new Function}
1020 % In upper Theory we now define the new function and its purpose:
1022 % get_denominator :: "real => real"
1024 % This command tells the machine that a function with the name
1025 % \texttt{get\_denominator} exists which gets a real expression as argument and
1026 % returns once again a real expression. Now we are able to implement the function
1027 % itself, upcoming example now shows the implementation of
1028 % \texttt{get\_denominator}.
1031 % \label{eg:getdenom}
1035 % 02 *("get_denominator",
1036 % 03 * ("Rational.get_denominator", eval_get_denominator ""))
1038 % 05 fun eval_get_denominator (thmid:string) _
1039 % 06 (t as Const ("Rational.get_denominator", _) $
1040 % 07 (Const ("Rings.inverse_class.divide", _) $num
1042 % 09 SOME (mk_thmid thmid ""
1043 % 10 (Print_Mode.setmp []
1044 % 11 (Syntax.string_of_term (thy2ctxt thy)) denom) "",
1045 % 12 Trueprop $ (mk_equality (t, denom)))
1046 % 13 | eval_get_denominator _ _ _ _ = NONE;\end{verbatim}
1049 % Line \texttt{07} and \texttt{08} are describing the mode of operation the best -
1050 % there is a fraction\\ (\ttfamily Rings.inverse\_class.divide\normalfont)
1052 % into its two parts (\texttt{\$num \$denom}). The lines before are additionals
1053 % commands for declaring the function and the lines after are modeling and
1054 % returning a real variable out of \texttt{\$denom}.
1056 % \subsubsection{Add a test for the new Function}
1058 % \paragraph{Everytime when adding} a new function it is essential also to add
1059 % a test for it. Tests for all functions are sorted in the same structure as the
1060 % knowledge it self and can be found up from the path:
1061 % \begin{center}\ttfamily test/Tools/isac/Knowledge\normalfont\end{center}
1062 % This tests are nothing very special, as a first prototype the functionallity
1063 % of a function can be checked by evaluating the result of a simple expression
1064 % passed to the function. Example~\ref{eg:getdenomtest} shows the test for our
1065 % \textit{just} created function \texttt{get\_denominator}.
1068 % \label{eg:getdenomtest}
1071 % 01 val thy = @{theory Isac};
1072 % 02 val t = term_of (the (parse thy "get_denominator ((a +x)/b)"));
1073 % 03 val SOME (_, t') = eval_get_denominator "" 0 t thy;
1074 % 04 if term2str t' = "get_denominator ((a + x) / b) = b" then ()
1075 % 05 else error "get_denominator ((a + x) / b) = b" \end{verbatim}
1078 % \begin{description}
1079 % \item[01] checks if the proofer set up on our {\sisac{}} System.
1080 % \item[02] passes a simple expression (fraction) to our suddenly created
1082 % \item[04] checks if the resulting variable is the correct one (in this case
1083 % ``b'' the denominator) and returns.
1084 % \item[05] handels the error case and reports that the function is not able to
1085 % solve the given problem.
1088 \subsection{Specification of the Problem}\label{spec}
1089 %WN <--> \chapter 7 der Thesis
1090 %WN die Argumentation unten sollte sich NUR auf Verifikation beziehen..
1092 Mechanical treatment requires to translate a textual problem
1093 description like in Fig.\ref{fig-interactive} on
1094 p.\pageref{fig-interactive} into a {\em formal} specification. The
1095 formal specification of the running example could look like is this:
1097 %WN Hier brauchen wir die Spezifikation des 'running example' ...
1098 %JR Habe input, output und precond vom Beispiel eingefügt brauche aber Hilfe bei
1099 %JR der post condition - die existiert für uns ja eigentlich nicht aka
1100 %JR haben sie bis jetzt nicht beachtet WN...
1101 %WN2 Mein Vorschlag ist, das TODO zu lassen und deutlich zu kommentieren.
1105 {\small\begin{tabbing}
1106 123\=123\=postcond \=: \= $\forall \,A^\prime\, u^\prime \,v^\prime.\,$\=\kill
1109 \> \>input \>: ${\it filterExpression} \;\;X\;z=\frac{3}{z-\frac{1}{4}+-\frac{1}{8}*\frac{1}{z}}, \;{\it domain}\;\mathbb{R}-\{\frac{1}{2}, \frac{-1}{4}\}$\\
1110 \>\>precond \>: $\frac{3}{z-\frac{1}{4}+-\frac{1}{8}*\frac{1}{z}}\;\; {\it continuous\_on}\; \mathbb{R}-\{\frac{1}{2}, \frac{-1}{4}\}$ \\
1111 \>\>output \>: stepResponse $x[n]$ \\
1112 \>\>postcond \>: TODO
1115 %JR wie besprochen, kein remark, keine begründung, nur simples "nicht behandelt"
1118 % Defining the postcondition requires a high amount mathematical
1119 % knowledge, the difficult part in our case is not to set up this condition
1120 % nor it is more to define it in a way the interpreter is able to handle it.
1121 % Due the fact that implementing that mechanisms is quite the same amount as
1122 % creating the programm itself, it is not avaible in our prototype.
1123 % \label{rm:postcond}
1126 The implementation of the formal specification in the present
1127 prototype, still bar-bones without support for authoring, is done
1129 %WN Kopie von Inverse_Z_Transform.thy, leicht versch"onert:
1131 {\footnotesize\label{exp-spec}
1134 01 store_specification
1135 02 (prepare_specification
1136 03 "pbl_SP_Ztrans_inv"
1139 06 ( ["Inverse", "Z_Transform", "SignalProcessing"],
1140 07 [ ("#Given", ["filterExpression X_eq", "domain D"]),
1141 08 ("#Pre" , ["(rhs X_eq) is_continuous_in D"]),
1142 09 ("#Find" , ["stepResponse n_eq"]),
1143 10 ("#Post" , [" TODO "])])
1146 13 [["SignalProcessing","Z_Transform","Inverse"]]);
1150 Although the above details are partly very technical, we explain them
1151 in order to document some intricacies of TP-based programming in the
1152 present state of the {\sisac} prototype:
1154 \item[01..02]\textit{store\_specification:} stores the result of the
1155 function \textit{prep\_specification} in a global reference
1156 \textit{Unsynchronized.ref}, which causes principal conflicts with
1157 Isabelle's asyncronous document model~\cite{Wenzel-11:doc-orient} and
1158 parallel execution~\cite{Makarius-09:parall-proof} and is under
1159 reconstruction already.
1161 \textit{prep\_specification:} translates the specification to an internal format
1162 which allows efficient processing; see for instance line {\rm 07}
1164 \item[03..04] are a unique identifier for the specification within {\sisac}
1165 and the ``mathematics author'' holding the copy-rights.
1166 \item[05] is the Isabelle \textit{theory} required to parse the
1167 specification in lines {\rm 07..10}.
1168 \item[06] is a key into the tree of all specifications as presented to
1169 the user (where some branches might be hidden by the dialog
1171 \item[07..10] are the specification with input, pre-condition, output
1172 and post-condition respectively; note that the specification contains
1173 variables to be instantiated with concrete values for a concrete problem ---
1174 thus the specification actually captures a class of problems. The post-condition is not handled in
1175 the prototype presently.
1176 \item[11] is a rule-set (defined elsewhere) for evaluation of the pre-condition: \textit{(rhs X\_eq) is\_continuous\_in D}, instantiated with the values of a concrete problem, evaluates to true or false --- and all evaluation is done by
1177 rewriting determined by rule-sets.
1178 \item[12]\textit{NONE:} could be \textit{SOME ``solve ...''} for a
1179 problem associated to a function from Computer Algebra (like an
1180 equation solver) which is not the case here.
1181 \item[13] is a list of methods solving the specified problem (here
1182 only one list item) represented analogously to {\rm 06}.
1186 %WN die folgenden Erkl"arungen finden sich durch "grep -r 'datatype pbt' *"
1189 % {guh : guh, (*unique within this isac-knowledge*)
1190 % mathauthors: string list, (*copyright*)
1191 % init : pblID, (*to start refinement with*)
1192 % thy : theory, (* which allows to compile that pbt
1193 % TODO: search generalized for subthy (ref.p.69*)
1194 % (*^^^ WN050912 NOT used during application of the problem,
1195 % because applied terms may be from 'subthy' as well as from super;
1196 % thus we take 'maxthy'; see match_ags !*)
1197 % cas : term option,(*'CAS-command'*)
1198 % prls : rls, (* for preds in where_*)
1199 % where_: term list, (* where - predicates*)
1201 % (*this is the model-pattern;
1202 % it contains "#Given","#Where","#Find","#Relate"-patterns
1203 % for constraints on identifiers see "fun cpy_nam"*)
1204 % met : metID list}; (* methods solving the pbt*)
1206 %WN weil dieser Code sehr unaufger"aumt ist, habe ich die Erkl"arungen
1207 %WN oben selbst geschrieben.
1212 %WN das w"urde ich in \sec\label{progr} verschieben und
1213 %WN das SubProblem partial fractions zum Erkl"aren verwenden.
1214 % Such a specification is checked before the execution of a program is
1215 % started, the same applies for sub-programs. In the following example
1216 % (Example~\ref{eg:subprob}) shows the call of such a subproblem:
1220 % \label{eg:subprob}
1222 % {\ttfamily \begin{tabbing}
1223 % ``(L\_L::bool list) = (\=SubProblem (\=Test','' \\
1224 % ``\>\>[linear,univariate,equation,test],'' \\
1225 % ``\>\>[Test,solve\_linear])'' \\
1226 % ``\>[BOOL equ, REAL z])'' \\
1230 % \noindent If a program requires a result which has to be
1231 % calculated first we can use a subproblem to do so. In our specific
1232 % case we wanted to calculate the zeros of a fraction and used a
1233 % subproblem to calculate the zeros of the denominator polynom.
1238 \subsection{Implementation of the Method}\label{meth}
1239 A method collects all data required to interpret a certain program by
1240 Lucas-Interpretation. The \texttt{program} from p.\pageref{s:impl} of
1241 the running example is embedded on the last line in the following method:
1242 %The methods represent the different ways a problem can be solved. This can
1243 %include mathematical tactics as well as tactics taught in different courses.
1244 %Declaring the Method itself gives us the possibilities to describe the way of
1245 %calculation in deep, as well we get the oppertunities to build in different
1253 03 "SP_InverseZTransformation_classic"
1256 06 ( ["SignalProcessing", "Z_Transform", "Inverse"],
1257 07 [ ("#Given", ["filterExpression X_eq", "domain D"]),
1258 08 ("#Pre" , ["(rhs X_eq) is_continuous_in D"]),
1259 09 ("#Find" , ["stepResponse n_eq"]),
1267 \noindent The above code stores the whole structure analogously to a
1268 specification as described above:
1270 \item[01..06] are identical to those for the example specification on
1271 p.\pageref{exp-spec}.
1273 \item[07..09] show something looking like the specification; this is a
1274 {\em guard}: as long as not all \textit{Given} items are present and
1275 the \textit{Pre}-conditions is not true, interpretation of the program
1278 \item[10..11] all concern rewriting (the respective data are defined elsewhere): \textit{rew\_ord} is the rewrite order~\cite{nipk:rew-all-that} in case
1279 \textit{program} contains a \textit{Rewrite} tactic; and in case the respective rule is a conditional rewrite-rule, \textit{erls} features evaluating the conditions. The rule-sets
1280 \textit{srls, prls, nrls} feature evaluating (a) the ML-functions in the program (e.g.
1281 \textit{lhs, argument\_in, rhs} in the program on p.\pageref{s:impl}, (b) the pre-condition analoguous to the specification in line 11 on p.\pageref{exp-spec}
1282 and (c) is required for the derivation-machinery checking user-input formulas.
1284 \item[12..13] \textit{errpats} are error-patterns~\cite{gdaroczy-EP-13} for this method and \textit{program} is the variable holding the example from p.\pageref {s:impl}.
1286 The many rule-sets above cause considerable efforts for the
1287 programmers, in particular, because there are no tools for checking
1288 essential features of rule-sets.
1290 % is again very technical and goes hard in detail. Unfortunataly
1291 % most declerations are not essential for a basic programm but leads us to a huge
1292 % range of powerful possibilities.
1294 % \begin{description}
1295 % \item[01..02] stores the method with the given name into the system under a global
1297 % \item[03] specifies the topic within which context the method can be found.
1298 % \item[04..05] as the requirements for different methods can be deviant we
1299 % declare what is \emph{given} and and what to \emph{find} for this specific method.
1300 % The code again helds on the topic of the case studie, where the inverse
1301 % z-transformation does a switch between a term describing a electrical filter into
1302 % its step response. Also the datatype has to be declared (bool - due the fact that
1303 % we handle equations).
1304 % \item[06] \emph{rewrite order} is the order of this rls (ruleset), where one
1305 % theorem of it is used for rewriting one single step.
1306 % \item[07] \texttt{rls} is the currently used ruleset for this method. This set
1307 % has already been defined before.
1308 % \item[08] we would have the possiblitiy to add this method to a predefined tree of
1309 % calculations, i.eg. if it would be a sub of a bigger problem, here we leave it
1311 % \item[09] The \emph{source ruleset}, can be used to evaluate list expressions in
1313 % \item[10] \emph{predicates ruleset} can be used to indicates predicates within
1315 % \item[11] The \emph{check ruleset} summarizes rules for checking formulas
1317 % \item[12] \emph{error patterns} which are expected in this kind of method can be
1318 % pre-specified to recognize them during the method.
1319 % \item[13] finally the \emph{canonical ruleset}, declares the canonical simplifier
1320 % of the specific method.
1321 % \item[14] for this code snipset we don't specify the programm itself and keep it
1322 % empty. Follow up \S\ref{progr} for informations on how to implement this
1323 % \textit{main} part.
1326 \subsection{Implementation of the TP-based Program}\label{progr}
1327 So finally all the prerequisites are described and the final task can
1328 be addressed. The program below comes back to the running example: it
1329 computes a solution for the problem from Fig.\ref{fig-interactive} on
1330 p.\pageref{fig-interactive}. The reader is reminded of
1331 \S\ref{PL-isab}, the introduction of the programming language:
1333 {\footnotesize\it\label{s:impl}
1335 123l\=123\=123\=123\=123\=123\=123\=((x\=123\=(x \=123\=123\=\kill
1336 \>{\rm 00}\>ML \{*\\
1337 \>{\rm 00}\>val program =\\
1338 \>{\rm 01}\> "{\tt Program} InverseZTransform (X\_eq::bool) = \\
1339 \>{\rm 02}\>\> {\tt let} \\
1340 \>{\rm 03}\>\>\> X\_eq = {\tt Take} X\_eq ; \\
1341 \>{\rm 04}\>\>\> X\_eq = {\tt Rewrite} prep\_for\_part\_frac X\_eq ; \\
1342 \>{\rm 05}\>\>\> (X\_z::real) = lhs X\_eq ; \\ %no inside-out evaluation
1343 \>{\rm 06}\>\>\> (z::real) = argument\_in X\_z; \\
1344 \>{\rm 07}\>\>\> (part\_frac::real) = {\tt SubProblem} \\
1345 \>{\rm 08}\>\>\>\>\>\>\>\> ( Isac, [partial\_fraction, rational, simplification], [] )\\
1346 %\>{\rm 10}\>\>\>\>\>\>\>\>\> [simplification, of\_rationals, to\_partial\_fraction] ) \\
1347 \>{\rm 09}\>\>\>\>\>\>\>\> [ (rhs X\_eq)::real, z::real ]; \\
1348 \>{\rm 10}\>\>\> (X'\_eq::bool) = {\tt Take} ((X'::real =$>$ bool) z = ZZ\_1 part\_frac) ; \\
1349 \>{\rm 11}\>\>\> X'\_eq = (({\tt Rewrite\_Set} prep\_for\_inverse\_z) @@ \\
1350 \>{\rm 12}\>\>\>\>\> $\;\;$ ({\tt Rewrite\_Set} inverse\_z)) X'\_eq \\
1351 \>{\rm 13}\>\> {\tt in } \\
1352 \>{\rm 14}\>\>\> X'\_eq"\\
1355 % ORIGINAL FROM Inverse_Z_Transform.thy
1356 % "Script InverseZTransform (X_eq::bool) = "^(*([], Frm), Problem (Isac, [Inverse, Z_Transform, SignalProcessing])*)
1357 % "(let X = Take X_eq; "^(*([1], Frm), X z = 3 / (z - 1 / 4 + -1 / 8 * (1 / z))*)
1358 % " X' = Rewrite ruleZY False X; "^(*([1], Res), ?X' z = 3 / (z * (z - 1 / 4 + -1 / 8 * (1 / z)))*)
1359 % " (X'_z::real) = lhs X'; "^(* ?X' z*)
1360 % " (zzz::real) = argument_in X'_z; "^(* z *)
1361 % " (funterm::real) = rhs X'; "^(* 3 / (z * (z - 1 / 4 + -1 / 8 * (1 / z)))*)
1363 % " (pbz::real) = (SubProblem (Isac', "^(**)
1364 % " [partial_fraction,rational,simplification], "^
1365 % " [simplification,of_rationals,to_partial_fraction]) "^
1366 % " [REAL funterm, REAL zzz]); "^(*([2], Res), 4 / (z - 1 / 2) + -4 / (z - -1 / 4)*)
1368 % " (pbz_eq::bool) = Take (X'_z = pbz); "^(*([3], Frm), ?X' z = 4 / (z - 1 / 2) + -4 / (z - -1 / 4)*)
1369 % " pbz_eq = Rewrite ruleYZ False pbz_eq; "^(*([3], Res), ?X' z = 4 * (?z / (z - 1 / 2)) + -4 * (?z / (z - -1 / 4))*)
1370 % " pbz_eq = drop_questionmarks pbz_eq; "^(* 4 * (z / (z - 1 / 2)) + -4 * (z / (z - -1 / 4))*)
1371 % " (X_zeq::bool) = Take (X_z = rhs pbz_eq); "^(*([4], Frm), X_z = 4 * (z / (z - 1 / 2)) + -4 * (z / (z - -1 / 4))*)
1372 % " n_eq = (Rewrite_Set inverse_z False) X_zeq; "^(*([4], Res), X_z = 4 * (1 / 2) ^^^ ?n * ?u [?n] + -4 * (-1 / 4) ^^^ ?n * ?u [?n]*)
1373 % " n_eq = drop_questionmarks n_eq "^(* X_z = 4 * (1 / 2) ^^^ n * u [n] + -4 * (-1 / 4) ^^^ n * u [n]*)
1374 % "in n_eq)" (*([], Res), X_z = 4 * (1 / 2) ^^^ n * u [n] + -4 * (-1 / 4) ^^^ n * u [n]*)
1375 The program is represented as a string and part of the method in
1376 \S\ref{meth}. As mentioned in \S\ref{PL} the program is purely
1377 functional and lacks any input statements and output statements. So
1378 the steps of calculation towards a solution (and interactive tutoring
1379 in step-wise problem solving) are created as a side-effect by
1380 Lucas-Interpretation. The side-effects are triggered by the tactics
1381 \texttt{Take}, \texttt{Rewrite}, \texttt{SubProblem} and
1382 \texttt{Rewrite\_Set} in the above lines {\rm 03, 04, 07, 10, 11} and
1383 {\rm 12} respectively. These tactics produce the respective lines in the
1384 calculation on p.\pageref{flow-impl}.
1386 The above lines {\rm 05, 06} do not contain a tactics, so they do not
1387 immediately contribute to the calculation on p.\pageref{flow-impl};
1388 rather, they compute actual arguments for the \texttt{SubProblem} in
1389 line {\rm 09}~\footnote{The tactics also are break-points for the
1390 interpreter, where control is handed over to the user in interactive
1391 tutoring.}. Line {\rm 11} contains tactical \textit{@@}.
1393 \medskip The above program also indicates the dominant role of interactive
1394 selection of knowledge in the three-dimensional universe of
1395 mathematics as depicted in Fig.\ref{fig:mathuni} on
1396 p.\pageref{fig:mathuni}, The \texttt{SubProblem} in the above lines
1397 {\rm 07..09} is more than a function call with the actual arguments
1398 \textit{[ (rhs X\_eq)::real, z::real ]}. The programmer has to determine
1402 \item the theory, in the example \textit{Isac} because different
1403 methods can be selected in Pt.3 below, which are defined in different
1404 theories with \textit{Isac} collecting them.
1405 \item the specification identified by \textit{[partial\_fraction,
1406 rational, simplification]} in the tree of specifications; this
1407 specification is analogous to the specification of the main program
1408 described in \S\ref{spec}; the problem is to find a ``partial fraction
1409 decomposition'' for a univariate rational polynomial.
1410 \item the method in the above example is \textit{[ ]}, i.e. empty,
1411 which supposes the interpreter to select one of the methods predefined
1412 in the specification, for instance in line {\rm 13} in the running
1413 example's specification on p.\pageref{exp-spec}~\footnote{The freedom
1414 (or obligation) for selection carries over to the student in
1415 interactive tutoring.}.
1418 The program code, above presented as a string, is parsed by Isabelle's
1419 parser --- the program is an Isabelle term. This fact is expected to
1420 simplify verification tasks in the future; on the other hand, this
1421 fact causes troubles in error detectetion which are discussed as part
1422 of the workflow in the subsequent section.
1424 \section{Workflow of Programming in the Prototype}\label{workflow}
1425 The new prover IDE Isabelle/jEdit~\cite{makar-jedit-12} is a great
1426 step forward for interactive theory and proof development. The
1427 {\sisac}-prototype re-uses this IDE as a programming environment. The
1428 experiences from this re-use show, that the essential components are
1429 available from Isabelle/jEdit. However, additional tools and features
1430 are required to acchieve acceptable usability.
1432 So notable experiences are reported here, also as a requirement
1433 capture for further development of TP-based languages and respective
1436 \subsection{Preparations and Trials}\label{flow-prep}
1437 The many sub-tasks to be accomplished {\em before} the first line of
1438 program code can be written and tested suggest an approach which
1439 step-wise establishes the prerequisites. The case study underlying
1440 this paper~\cite{jrocnik-bakk} documents the approach in a separate
1442 \textit{Build\_Inverse\_Z\_Transform.thy}~\footnote{http://www.ist.tugraz.at/projects/isac/publ/Build\_Inverse\_Z\_Transform.thy}. Part
1443 II in the study comprises this theory, \LaTeX ed from the theory by
1444 use of Isabelle's document preparation system. This paper resembles
1445 the approach in \S\ref{isabisac} to \S\ref{meth}, which in actual
1446 implementation work involves several iterations.
1448 \bigskip For instance, only the last step, implementing the program
1449 described in \S\ref{meth}, reveals details required. Let us assume,
1450 this is the ML-function \textit{argument\_in} required in line {\rm 06}
1451 of the example program on p.\pageref{s:impl}; how this function needs
1452 to be implemented in the prototype has been discussed in \S\ref{funs}
1455 Now let us assume, that calling this function from the program code
1456 does not work; so testing this function is required in order to find out
1457 the reason: type errors, a missing entry of the function somewhere or
1458 even more nasty technicalities \dots
1463 val SOME t = parseNEW ctxt "argument_in (X (z::real))";
1464 val SOME (str, t') = eval_argument_in ""
1465 "Build_Inverse_Z_Transform.argument'_in" t 0;
1470 val it = "(argument_in X z) = z": string
1473 \noindent So, this works: we get an ad-hoc theorem, which used in
1474 rewriting would reduce \texttt{argument\_in X z} to \texttt{z}. Now we check this
1475 reduction and create a rule-set \texttt{rls} for that purpose:
1480 val rls = append_rls "test" e_rls
1481 [Calc ("Build_Inverse_Z_Transform.argument'_in", eval_argument_in "")]
1484 val SOME (t', asm) = rewrite_set_ @{theory} rls t;
1486 val t' = Free ("z", "RealDef.real"): term
1487 val asm = []: term list
1490 \noindent The resulting term \texttt{t'} is \texttt{Free ("z",
1491 "RealDef.real")}, i.e the variable \texttt{z}, so all is
1492 perfect. Probably we have forgotten to store this function correctly~?
1493 We review the respective \texttt{calclist} (again an
1494 \textit{Unsynchronized.ref} to be removed in order to adjust to
1495 IsabelleIsar's asyncronous document model):
1499 calclist:= overwritel (! calclist,
1500 [("argument_in",("Build_Inverse_Z_Transform.argument'_in", eval_argument_in "")),
1505 \noindent The entry is perfect. So what is the reason~? Ah, probably there
1506 is something messed up with the many rule-sets in the method, see \S\ref{meth} ---
1507 right, the function \texttt{argument\_in} is not contained in the respective
1508 rule-set \textit{srls} \dots this just as an example of the intricacies in
1509 debugging a program in the present state of the prototype.
1511 \subsection{Implementation in Isabelle/{\isac}}\label{flow-impl}
1512 Given all the prerequisites from \S\ref{isabisac} to \S\ref{meth},
1513 usually developed within several iterations, the program can be
1514 assembled; on p.\pageref{s:impl} there is the complete program of the
1517 The completion of this program required efforts for several weeks
1518 (after some months of familiarisation with {\sisac}), caused by the
1519 abundance of intricacies indicated above. Also writing the program is
1520 not pleasant, given Isabelle/Isar/ without add-ons for
1521 programming. Already writing and parsing a few lines of program code
1522 is a challenge: the program is an Isabelle term; Isabelle's parser,
1523 however, is not meant for huge terms like the program of the running
1524 example. So reading out the specific error (usually type errors) from
1525 Isabelle's message is difficult.
1527 \medskip Testing the evaluation of the program has to rely on very
1528 simple tools. Step-wise execution is modelled by a function
1529 \texttt{me}, short for mathematics-engine~\footnote{The interface used
1530 by the fron-end which created the calculation on
1531 p.\pageref{fig-interactive} is different from this function}:
1532 %the following is a simplification of the actual function
1537 val it = tac -> ctree * pos -> mout * tac * ctree * pos
1540 \noindent This function takes as arguments a tactic \texttt{tac} which
1541 determines the next step, the step applied to the interpreter-state
1542 \texttt{ctree * pos} as last argument taken. The interpreter-state is
1543 a pair of a tree \texttt{ctree} representing the calculation created
1544 (see the example below) and a position \texttt{pos} in the
1545 calculation. The function delivers a quadrupel, beginning with the new
1546 formula \texttt{mout} and the next tactic followed by the new
1549 This function allows to stepwise check the program:
1555 ["filterExpression (X z = 3 / ((z::real) + 1/10 - 1/50*(1/z)))",
1556 "stepResponse (x[n::real]::bool)"];
1559 ["Inverse", "Z_Transform", "SignalProcessing"],
1560 ["SignalProcessing","Z_Transform","Inverse"]);
1562 val (mout, tac, ctree, pos) = CalcTreeTEST [(fmz, (dI, pI, mI))];
1563 val (mout, tac, ctree, pos) = me tac (ctree, pos);
1564 val (mout, tac, ctree, pos) = me tac (ctree, pos);
1565 val (mout, tac, ctree, pos) = me tac (ctree, pos);
1569 \noindent Several douzens of calls for \texttt{me} are required to
1570 create the lines in the calculation below (including the sub-problems
1571 not shown). When an error occurs, the reason might be located
1572 many steps before: if evaluation by rewriting, as done by the prototype,
1573 fails, then first nothing happens --- the effects come later and
1574 cause unpleasant checks.
1576 The checks comprise watching the rewrite-engine for many different
1577 kinds of rule-sets (see \S\ref{meth}), the interpreter-state, in
1578 particular the environment and the context at the states position ---
1579 all checks have to rely on simple functions accessing the
1580 \texttt{ctree}. So getting the calculation below (which resembles the
1581 calculation in Fig.\ref{fig-interactive} on p.\pageref{fig-interactive})
1582 is the result of several weeks of development:
1584 {\small\it\label{exp-calc}
1586 123l\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=123\=\kill
1587 \>{\rm 01}\> $\bullet$ \> {\tt Problem } (Inverse\_Z\_Transform, [Inverse, Z\_Transform, SignalProcessing]) \`\\
1588 \>{\rm 02}\>\> $\vdash\;\;X z = \frac{3}{z - \frac{1}{4} - \frac{1}{8} \cdot z^{-1}}$ \`{\footnotesize {\tt Take} X\_eq}\\
1589 \>{\rm 03}\>\> $X z = \frac{3}{z + \frac{-1}{4} + \frac{-1}{8} \cdot \frac{1}{z}}$ \`{\footnotesize {\tt Rewrite} prep\_for\_part\_frac X\_eq}\\
1590 \>{\rm 04}\>\> $\bullet$\> {\tt Problem } [partial\_fraction,rational,simplification] \`{\footnotesize {\tt SubProblem} \dots}\\
1591 \>{\rm 05}\>\>\> $\vdash\;\;\frac{3}{z + \frac{-1}{4} + \frac{-1}{8} \cdot \frac{1}{z}}=$ \`- - -\\
1592 \>{\rm 06}\>\>\> $\frac{24}{-1 + -2 \cdot z + 8 \cdot z^2}$ \`- - -\\
1593 \>{\rm 07}\>\>\> $\bullet$\> solve ($-1 + -2 \cdot z + 8 \cdot z^2,\;z$ ) \`- - -\\
1594 \>{\rm 08}\>\>\>\> $\vdash$ \> $\frac{3}{z + \frac{-1}{4} + \frac{-1}{8} \cdot \frac{1}{z}}=0$ \`- - -\\
1595 \>{\rm 09}\>\>\>\> $z = \frac{2+\sqrt{-4+8}}{16}\;\lor\;z = \frac{2-\sqrt{-4+8}}{16}$ \`- - -\\
1596 \>{\rm 10}\>\>\>\> $z = \frac{1}{2}\;\lor\;z =$ \_\_\_ \`- - -\\
1597 \> \>\>\>\> \_\_\_ \`- - -\\
1598 \>{\rm 11}\>\> \dots\> $\frac{4}{z - \frac{1}{2}} + \frac{-4}{z - \frac{-1}{4}}$ \`\\
1599 \>{\rm 12}\>\> $X^\prime z = {\cal Z}^{-1} (\frac{4}{z - \frac{1}{2}} + \frac{-4}{z - \frac{-1}{4}})$ \`{\footnotesize {\tt Take} ((X'::real =$>$ bool) z = ZZ\_1 part\_frac)}\\
1600 \>{\rm 13}\>\> $X^\prime z = {\cal Z}^{-1} (4\cdot\frac{z}{z - \frac{1}{2}} + -4\cdot\frac{z}{z - \frac{-1}{4}})$ \`{\footnotesize{\tt Rewrite\_Set} prep\_for\_inverse\_z X'\_eq }\\
1601 \>{\rm 14}\>\> $X^\prime z = 4\cdot(\frac{1}{2})^n \cdot u [n] + -4\cdot(\frac{-1}{4})^n \cdot u [n]$ \`{\footnotesize {\tt Rewrite\_Set} inverse\_z X'\_eq}\\
1602 \>{\rm 15}\> \dots\> $X^\prime z = 4\cdot(\frac{1}{2})^n \cdot u [n] + -4\cdot(\frac{-1}{4})^n \cdot u [n]$ \`{\footnotesize {\tt Check\_Postcond}}
1604 The tactics on the right margin of the above calculation are those in
1605 the program on p.\pageref{s:impl} which create the respective formulas
1607 % ORIGINAL FROM Inverse_Z_Transform.thy
1608 % "Script InverseZTransform (X_eq::bool) = "^(*([], Frm), Problem (Isac, [Inverse, Z_Transform, SignalProcessing])*)
1609 % "(let X = Take X_eq; "^(*([1], Frm), X z = 3 / (z - 1 / 4 + -1 / 8 * (1 / z))*)
1610 % " X' = Rewrite ruleZY False X; "^(*([1], Res), ?X' z = 3 / (z * (z - 1 / 4 + -1 / 8 * (1 / z)))*)
1611 % " (X'_z::real) = lhs X'; "^(* ?X' z*)
1612 % " (zzz::real) = argument_in X'_z; "^(* z *)
1613 % " (funterm::real) = rhs X'; "^(* 3 / (z * (z - 1 / 4 + -1 / 8 * (1 / z)))*)
1615 % " (pbz::real) = (SubProblem (Isac', "^(**)
1616 % " [partial_fraction,rational,simplification], "^
1617 % " [simplification,of_rationals,to_partial_fraction]) "^
1618 % " [REAL funterm, REAL zzz]); "^(*([2], Res), 4 / (z - 1 / 2) + -4 / (z - -1 / 4)*)
1620 % " (pbz_eq::bool) = Take (X'_z = pbz); "^(*([3], Frm), ?X' z = 4 / (z - 1 / 2) + -4 / (z - -1 / 4)*)
1621 % " pbz_eq = Rewrite ruleYZ False pbz_eq; "^(*([3], Res), ?X' z = 4 * (?z / (z - 1 / 2)) + -4 * (?z / (z - -1 / 4))*)
1622 % " pbz_eq = drop_questionmarks pbz_eq; "^(* 4 * (z / (z - 1 / 2)) + -4 * (z / (z - -1 / 4))*)
1623 % " (X_zeq::bool) = Take (X_z = rhs pbz_eq); "^(*([4], Frm), X_z = 4 * (z / (z - 1 / 2)) + -4 * (z / (z - -1 / 4))*)
1624 % " n_eq = (Rewrite_Set inverse_z False) X_zeq; "^(*([4], Res), X_z = 4 * (1 / 2) ^^^ ?n * ?u [?n] + -4 * (-1 / 4) ^^^ ?n * ?u [?n]*)
1625 % " n_eq = drop_questionmarks n_eq "^(* X_z = 4 * (1 / 2) ^^^ n * u [n] + -4 * (-1 / 4) ^^^ n * u [n]*)
1626 % "in n_eq)" (*([], Res), X_z = 4 * (1 / 2) ^^^ n * u [n] + -4 * (-1 / 4) ^^^ n * u [n]*)
1628 \subsection{Transfer into the Isabelle/{\isac} Knowledge}\label{flow-trans}
1629 Finally \textit{Build\_Inverse\_Z\_Transform.thy} has got the job done
1630 and the knowledge accumulated in it can be distributed to appropriate
1631 theories: the program to \textit{Inverse\_Z\_Transform.thy}, the
1632 sub-problem accomplishing the partial fraction decomposition to
1633 \textit{Partial\_Fractions.thy}. Since there are hacks into Isabelle's
1634 internals, this kind of distribution is not trivial. For instance, the
1635 function \texttt{argument\_in} in \S\ref{funs} explicitly contains a
1636 string with the theory it has been defined in, so this string needs to
1637 be updated from \texttt{Build\_Inverse\_Z\_Transform} to
1638 \texttt{Atools} if that function is transferred to theory
1639 \textit{Atools.thy}.
1641 In order to obtain the functionality presented in Fig.\ref{fig-interactive} on p.\pageref{fig-interactive} data must be exported from SML-structures to XML.
1642 This process is also rather bare-bones without authoring tools and is
1643 described in detail in the {\sisac} wiki~\footnote{http://www.ist.tugraz.at/isac/index.php/Generate\_representations\_for\_ISAC\_Knowledge}.
1646 % -------------------------------------------------------------------
1648 % Material, falls noch Platz bleibt ...
1650 % -------------------------------------------------------------------
1653 % \subsubsection{Trials on Notation and Termination}
1655 % \paragraph{Technical notations} are a big problem for our piece of software,
1656 % but the reason for that isn't a fault of the software itself, one of the
1657 % troubles comes out of the fact that different technical subtopics use different
1658 % symbols and notations for a different purpose. The most famous example for such
1659 % a symbol is the complex number $i$ (in cassique math) or $j$ (in technical
1660 % math). In the specific part of signal processing one of this notation issues is
1661 % the use of brackets --- we use round brackets for analoge signals and squared
1662 % brackets for digital samples. Also if there is no problem for us to handle this
1663 % fact, we have to tell the machine what notation leads to wich meaning and that
1664 % this purpose seperation is only valid for this special topic - signal
1666 % \subparagraph{In the programming language} itself it is not possible to declare
1667 % fractions, exponents, absolutes and other operators or remarks in a way to make
1668 % them pretty to read; our only posssiblilty were ASCII characters and a handfull
1669 % greek symbols like: $\alpha, \beta, \gamma, \phi,\ldots$.
1671 % With the upper collected knowledge it is possible to check if we were able to
1672 % donate all required terms and expressions.
1674 % \subsubsection{Definition and Usage of Rules}
1676 % \paragraph{The core} of our implemented problem is the Z-Transformation, due
1677 % the fact that the transformation itself would require higher math which isn't
1678 % yet avaible in our system we decided to choose the way like it is applied in
1679 % labratory and problem classes at our university - by applying transformation
1680 % rules (collected in transformation tables).
1681 % \paragraph{Rules,} in {\sisac{}}'s programming language can be designed by the
1682 % use of axiomatizations like shown in Example~\ref{eg:ruledef}
1685 % \label{eg:ruledef}
1688 % axiomatization where
1689 % rule1: ``1 = $\delta$[n]'' and
1690 % rule2: ``|| z || > 1 ==> z / (z - 1) = u [n]'' and
1691 % rule3: ``|| z || < 1 ==> z / (z - 1) = -u [-n - 1]''
1695 % This rules can be collected in a ruleset and applied to a given expression as
1696 % follows in Example~\ref{eg:ruleapp}.
1700 % \label{eg:ruleapp}
1702 % \item Store rules in ruleset:
1704 % val inverse_Z = append_rls "inverse_Z" e_rls
1705 % [ Thm ("rule1",num_str @{thm rule1}),
1706 % Thm ("rule2",num_str @{thm rule2}),
1707 % Thm ("rule3",num_str @{thm rule3})
1709 % \item Define exression:
1711 % val sample_term = str2term "z/(z-1)+z/(z-</delta>)+1";\end{verbatim}
1712 % \item Apply ruleset:
1714 % val SOME (sample_term', asm) =
1715 % rewrite_set_ thy true inverse_Z sample_term;\end{verbatim}
1719 % The use of rulesets makes it much easier to develop our designated applications,
1720 % but the programmer has to be careful and patient. When applying rulesets
1721 % two important issues have to be mentionend:
1722 % \subparagraph{How often} the rules have to be applied? In case of
1723 % transformations it is quite clear that we use them once but other fields
1724 % reuqire to apply rules until a special condition is reached (e.g.
1725 % a simplification is finished when there is nothing to be done left).
1726 % \subparagraph{The order} in which rules are applied often takes a big effect
1727 % and has to be evaluated for each purpose once again.
1729 % In our special case of Signal Processing and the rules defined in
1730 % Example~\ref{eg:ruledef} we have to apply rule~1 first of all to transform all
1731 % constants. After this step has been done it no mather which rule fit's next.
1733 % \subsubsection{Helping Functions}
1735 % \paragraph{New Programms require,} often new ways to get through. This new ways
1736 % means that we handle functions that have not been in use yet, they can be
1737 % something special and unique for a programm or something famous but unneeded in
1738 % the system yet. In our dedicated example it was for example neccessary to split
1739 % a fraction into numerator and denominator; the creation of such function and
1740 % even others is described in upper Sections~\ref{simp} and \ref{funs}.
1742 % \subsubsection{Trials on equation solving}
1743 % %simple eq and problem with double fractions/negative exponents
1744 % \paragraph{The Inverse Z-Transformation} makes it neccessary to solve
1745 % equations degree one and two. Solving equations in the first degree is no
1746 % problem, wether for a student nor for our machine; but even second degree
1747 % equations can lead to big troubles. The origin of this troubles leads from
1748 % the build up process of our equation solving functions; they have been
1749 % implemented some time ago and of course they are not as good as we want them to
1750 % be. Wether or not following we only want to show how cruel it is to build up new
1751 % work on not well fundamentials.
1752 % \subparagraph{A simple equation solving,} can be set up as shown in the next
1759 % ["equality (-1 + -2 * z + 8 * z ^^^ 2 = (0::real))",
1763 % val (dI',pI',mI') =
1765 % ["abcFormula","degree_2","polynomial","univariate","equation"],
1766 % ["no_met"]);\end{verbatim}
1769 % Here we want to solve the equation: $-1+-2\cdot z+8\cdot z^{2}=0$. (To give
1770 % a short overview on the commands; at first we set up the equation and tell the
1771 % machine what's the bound variable and where to store the solution. Second step
1772 % is to define the equation type and determine if we want to use a special method
1773 % to solve this type.) Simple checks tell us that the we will get two results for
1774 % this equation and this results will be real.
1775 % So far it is easy for us and for our machine to solve, but
1776 % mentioned that a unvariate equation second order can have three different types
1777 % of solutions it is getting worth.
1778 % \subparagraph{The solving of} all this types of solutions is not yet supported.
1779 % Luckily it was needed for us; but something which has been needed in this
1780 % context, would have been the solving of an euation looking like:
1781 % $-z^{-2}+-2\cdot z^{-1}+8=0$ which is basically the same equation as mentioned
1782 % before (remember that befor it was no problem to handle for the machine) but
1783 % now, after a simple equivalent transformation, we are not able to solve
1785 % \subparagraph{Error messages} we get when we try to solve something like upside
1786 % were very confusing and also leads us to no special hint about a problem.
1787 % \par The fault behind is, that we have no well error handling on one side and
1788 % no sufficient formed equation solving on the other side. This two facts are
1789 % making the implemention of new material very difficult.
1791 % \subsection{Formalization of missing knowledge in Isabelle}
1793 % \paragraph{A problem} behind is the mechanization of mathematic
1794 % theories in TP-bases languages. There is still a huge gap between
1795 % these algorithms and this what we want as a solution - in Example
1796 % Signal Processing.
1802 % X\cdot(a+b)+Y\cdot(c+d)=aX+bX+cY+dY
1805 % \noindent A very simple example on this what we call gap is the
1806 % simplification above. It is needles to say that it is correct and also
1807 % Isabelle for fills it correct - \emph{always}. But sometimes we don't
1808 % want expand such terms, sometimes we want another structure of
1809 % them. Think of a problem were we now would need only the coefficients
1810 % of $X$ and $Y$. This is what we call the gap between mechanical
1811 % simplification and the solution.
1816 % \paragraph{We are not able to fill this gap,} until we have to live
1817 % with it but first have a look on the meaning of this statement:
1818 % Mechanized math starts from mathematical models and \emph{hopefully}
1819 % proceeds to match physics. Academic engineering starts from physics
1820 % (experimentation, measurement) and then proceeds to mathematical
1821 % modeling and formalization. The process from a physical observance to
1822 % a mathematical theory is unavoidable bound of setting up a big
1823 % collection of standards, rules, definition but also exceptions. These
1824 % are the things making mechanization that difficult.
1833 % \noindent Think about some units like that one's above. Behind
1834 % each unit there is a discerning and very accurate definition: One
1835 % Meter is the distance the light travels, in a vacuum, through the time
1836 % of 1 / 299.792.458 second; one kilogram is the weight of a
1837 % platinum-iridium cylinder in paris; and so on. But are these
1838 % definitions usable in a computer mechanized world?!
1843 % \paragraph{A computer} or a TP-System builds on programs with
1844 % predefined logical rules and does not know any mathematical trick
1845 % (follow up example \ref{eg:trick}) or recipe to walk around difficult
1851 % \[ \frac{1}{j\omega}\cdot\left(e^{-j\omega}-e^{j3\omega}\right)= \]
1852 % \[ \frac{1}{j\omega}\cdot e^{-j2\omega}\cdot\left(e^{j\omega}-e^{-j\omega}\right)=
1853 % \frac{1}{\omega}\, e^{-j2\omega}\cdot\colorbox{lgray}{$\frac{1}{j}\,\left(e^{j\omega}-e^{-j\omega}\right)$}= \]
1854 % \[ \frac{1}{\omega}\, e^{-j2\omega}\cdot\colorbox{lgray}{$2\, sin(\omega)$} \]
1856 % \noindent Sometimes it is also useful to be able to apply some
1857 % \emph{tricks} to get a beautiful and particularly meaningful result,
1858 % which we are able to interpret. But as seen in this example it can be
1859 % hard to find out what operations have to be done to transform a result
1860 % into a meaningful one.
1865 % \paragraph{The only possibility,} for such a system, is to work
1866 % through its known definitions and stops if none of these
1867 % fits. Specified on Signal Processing or any other application it is
1868 % often possible to walk through by doing simple creases. This creases
1869 % are in general based on simple math operational but the challenge is
1870 % to teach the machine \emph{all}\footnote{Its pride to call it
1871 % \emph{all}.} of them. Unfortunately the goal of TP Isabelle is to
1872 % reach a high level of \emph{all} but it in real it will still be a
1873 % survey of knowledge which links to other knowledge and {{\sisac}{}} a
1874 % trainer and helper but no human compensating calculator.
1876 % {{{\sisac}{}}} itself aims to adds \emph{Algorithmic Knowledge} (formal
1877 % specifications of problems out of topics from Signal Processing, etc.)
1878 % and \emph{Application-oriented Knowledge} to the \emph{deductive} axis of
1879 % physical knowledge. The result is a three-dimensional universe of
1880 % mathematics seen in Figure~\ref{fig:mathuni}.
1884 % \includegraphics{fig/universe}
1885 % \caption{Didactic ``Math-Universe'': Algorithmic Knowledge (Programs) is
1886 % combined with Application-oriented Knowledge (Specifications) and Deductive Knowledge (Axioms, Definitions, Theorems). The Result
1887 % leads to a three dimensional math universe.\label{fig:mathuni}}
1891 % %WN Deine aktuelle Benennung oben wird Dir kein Fachmann abnehmen;
1892 % %WN bitte folgende Bezeichnungen nehmen:
1894 % %WN axis 1: Algorithmic Knowledge (Programs)
1895 % %WN axis 2: Application-oriented Knowledge (Specifications)
1896 % %WN axis 3: Deductive Knowledge (Axioms, Definitions, Theorems)
1898 % %WN und bitte die R"ander von der Grafik wegschneiden (was ich f"ur *.pdf
1899 % %WN nicht hinkriege --- weshalb ich auch die eJMT-Forderung nicht ganz
1900 % %WN verstehe, separierte PDFs zu schicken; ich w"urde *.png schicken)
1902 % %JR Ränder und beschriftung geändert. Keine Ahnung warum eJMT sich pdf's
1903 % %JR wünschen, würde ebenfalls png oder ähnliches verwenden, aber wenn pdf's
1904 % %JR gefordert werden WN2...
1905 % %WN2 meiner Meinung nach hat sich eJMT unklar ausgedr"uckt (z.B. kann
1906 % %WN2 man meines Wissens pdf-figures nicht auf eine bestimmte Gr"osse
1907 % %WN2 zusammenschneiden um die R"ander weg zu bekommen)
1908 % %WN2 Mein Vorschlag ist, in umserem tex-file bei *.png zu bleiben und
1909 % %WN2 png + pdf figures mitzuschicken.
1911 % \subsection{Notes on Problems with Traditional Notation}
1913 % \paragraph{During research} on these topic severely problems on
1914 % traditional notations have been discovered. Some of them have been
1915 % known in computer science for many years now and are still unsolved,
1916 % one of them aggregates with the so called \emph{Lambda Calculus},
1917 % Example~\ref{eg:lamda} provides a look on the problem that embarrassed
1924 % \[ f(x)=\ldots\; \quad R \rightarrow \quad R \]
1927 % \[ f(p)=\ldots\; p \in \quad R \]
1930 % \noindent Above we see two equations. The first equation aims to
1931 % be a mapping of an function from the reel range to the reel one, but
1932 % when we change only one letter we get the second equation which
1933 % usually aims to insert a reel point $p$ into the reel function. In
1934 % computer science now we have the problem to tell the machine (TP) the
1935 % difference between this two notations. This Problem is called
1936 % \emph{Lambda Calculus}.
1941 % \paragraph{An other problem} is that terms are not full simplified in
1942 % traditional notations, in {{\sisac}} we have to simplify them complete
1943 % to check weather results are compatible or not. in e.g. the solutions
1944 % of an second order linear equation is an rational in {{\sisac}} but in
1945 % tradition we keep fractions as long as possible and as long as they
1946 % aim to be \textit{beautiful} (1/8, 5/16,...).
1947 % \subparagraph{The math} which should be mechanized in Computer Theorem
1948 % Provers (\emph{TP}) has (almost) a problem with traditional notations
1949 % (predicate calculus) for axioms, definitions, lemmas, theorems as a
1950 % computer program or script is not able to interpret every Greek or
1951 % Latin letter and every Greek, Latin or whatever calculations
1952 % symbol. Also if we would be able to handle these symbols we still have
1953 % a problem to interpret them at all. (Follow up \hbox{Example
1954 % \ref{eg:symbint1}})
1958 % \label{eg:symbint1}
1960 % u\left[n\right] \ \ldots \ unitstep
1963 % \noindent The unitstep is something we need to solve Signal
1964 % Processing problem classes. But in {{{\sisac}{}}} the rectangular
1965 % brackets have a different meaning. So we abuse them for our
1966 % requirements. We get something which is not defined, but usable. The
1967 % Result is syntax only without semantic.
1972 % In different problems, symbols and letters have different meanings and
1973 % ask for different ways to get through. (Follow up \hbox{Example
1974 % \ref{eg:symbint2}})
1978 % \label{eg:symbint2}
1980 % \widehat{\ }\ \widehat{\ }\ \widehat{\ } \ \ldots \ exponent
1983 % \noindent For using exponents the three \texttt{widehat} symbols
1984 % are required. The reason for that is due the development of
1985 % {{{\sisac}{}}} the single \texttt{widehat} and also the double were
1986 % already in use for different operations.
1991 % \paragraph{Also the output} can be a problem. We are familiar with a
1992 % specified notations and style taught in university but a computer
1993 % program has no knowledge of the form proved by a professor and the
1994 % machines themselves also have not yet the possibilities to print every
1995 % symbol (correct) Recent developments provide proofs in a human
1996 % readable format but according to the fact that there is no money for
1997 % good working formal editors yet, the style is one thing we have to
2000 % \section{Problems rising out of the Development Environment}
2002 % fehlermeldungen! TODO
2004 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\end{verbatim}
2006 \section{Conclusion}\label{conclusion}
2007 This paper gives a first experience report about programming with a
2008 TP-based programming language.
2010 \medskip A brief re-introduction of the novel kind of programming
2011 language by example of the {\sisac}-prototype makes the paper
2012 self-contained. The main section describes all the main concepts
2013 involved in TP-based programming and all the sub-tasks concerning
2014 respective implementation: mechanisation of mathematics and domain
2015 modelling, implementation of term rewriting systems for the
2016 rewriting-engine, formal (implicit) specification of the problem to be
2017 (explicitly) described by the program, implementation of the many components
2018 required for Lucas-Interpretation and finally implementation of the
2021 The many concepts and sub-tasks involved in programming require a
2022 comprehensive workflow; first experiences with the workflow as
2023 supported by the present prototype are described as well: Isabelle +
2024 Isar + jEdit provide appropriate components for establishing an
2025 efficient development environment integrating computation and
2026 deduction. However, the present state of the prototype is far off a
2027 state appropriate for wide-spread use: the prototype of the program
2028 language lacks expressiveness and elegance, the prototype of the
2029 development environment is hardly usable: error messages still address
2030 the developer of the prototype's interpreter rather than the
2031 application programmer, implementation of the many settings for the
2032 Lucas-Interpreter is cumbersome.
2034 From these experiences a successful proof of concept can be concluded:
2035 programming arbitrary problems from engineering sciences is possible,
2036 in principle even in the prototype. Furthermore the experiences allow
2037 to conclude detailed requirements for further development:
2039 \item Clarify underlying logics such that programming is smoothly
2040 integrated with verification of the program; the post-condition should
2041 be proved more or less automatically, otherwise working engineers
2042 would not encounter such programming.
2043 \item Combine the prototype's programming language with Isabelle's
2044 powerful function package and probably with more of SML's
2045 pattern-matching features; include parallel execution on multi-core
2046 machines into the language desing.
2047 \item Extend the prototype's Lucas-Interpreter such that it also
2048 handles functions defined by use of Isabelle's functions package; and
2049 generalize Isabelle's code generator such that efficient code for the
2050 whole definition of the programming language can be generated (for
2051 multi-core machines).
2052 \item Develop an efficient development environment with
2053 integration of programming and proving, with management not only of
2054 Isabelle theories, but also of large collections of specifications and
2057 Provided successful accomplishment, these points provide distinguished
2058 components for virtual workbenches appealing to practictioner of
2059 engineering in the near future.
2061 \medskip Interactive couse material, as addressed by the title, then
2062 can comprise step-wise problem solving created as a side-effect of a
2063 TP-based program: Lucas-Interpretation not only provides an
2064 interactive programming environment, Lucas-Interpretation also can
2065 provide TP-based services for a flexible dialog component with
2066 adaptive user guidance for independent and inquiry-based learning.
2069 \bibliographystyle{alpha}
2070 {\small\bibliography{references}}