1 \documentclass{article} |
1 \documentclass[12pt]{article} |
2 \usepackage{a4} |
2 \usepackage{a4} |
3 \usepackage{times} |
3 \usepackage{times} |
4 \usepackage{latexsym} |
4 \usepackage{latexsym} |
5 %\bibliographystyle{alpha} |
5 \bibliographystyle{alpha} |
6 \bibliographystyle{abbrv} |
6 %\bibliographystyle{abbrv} |
7 \usepackage{graphicx} |
7 \usepackage{graphicx} |
8 |
8 |
9 \def\isac{${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$} |
9 \def\isac{${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$} |
10 \def\sisac{{\footnotesize${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$}} |
10 \def\sisac{{\footnotesize${\cal I}\mkern-2mu{\cal S}\mkern-5mu{\cal AC}$}} |
11 |
11 |
12 \title{Tentative Title:\\ |
12 \title{Tentative Title:\\ |
13 Theory of Functional Programming\\ |
13 Theory of Functional Programming\\ |
14 Introduced by Isabelle and \isac} |
14 Introduced by Isabelle and \isac} |
15 \author{n.n.\\ |
15 \author{n.n\\ |
16 {\tt TODO@xxx.at}} |
16 {\tt TODO@xxx.at}} |
17 |
17 |
18 \begin{document} |
18 \begin{document} |
19 \maketitle |
19 \maketitle |
20 \abstract{ |
20 %\abstract{ |
21 TODO |
21 %TODO |
22 } |
22 %} |
23 |
23 |
24 \section{Background} |
24 \section{Background} |
25 |
25 |
26 ``Functional programing'' (FP) is one of the leading paradigms in programming besides ``object oriented programming'' \cite{?} and ``logic / constraint programming'' \cite{}. One advantage of FP are general and elegant approaches to the mathematical theory of programming. |
26 ``Functional programing'' (FP) is one of the leading paradigms in programming besides ``object oriented programming'' %\cite{?} |
|
27 and ``logic (or constraint) programming'' \cite{?}. One advantage of FP are general and elegant approaches to the mathematical theory of programming \cite{?}. |
27 |
28 |
28 Presently FP gains importance in face of the ``multi-core crisis'' \cite{}: functional programs are ready to exploit many cores in parallel. |
29 Presently FP gains importance in face of the ``multi-core crisis'' \cite{?}: functional programs are ready to exploit many cores in parallel. In spite of this fact, at Graz University of Technology (TUG) FP has vanished during recent years, and it is of actual importance to include FP again in education. |
29 |
30 |
30 In spite of this fact, at Graz University of Technology (TUG) FP has vanished during recent years, and it is of actual importance to include FP again in education. |
31 In order to support such education this thesis will compile a course based on advanced tools developed in the intersection between computer science and mathematics: The computer theorem prover Isabelle \cite{Nipkow-Paulson-Wenzel:2002} and the educational math assistant \sisac. |
31 |
|
32 In order to support such education this thesis will employ advanced tools developed in the intersection between computer science and mathematics: The computer theorem prover Isabelle \cite{} and the educational math assistant \sisac. |
|
33 |
32 |
34 \section{Goal} |
33 \section{Goal} |
35 |
34 |
36 The goal of this thesis is generation of interactive course material on the topic, implemented in Isabelle and \sisac. |
35 The goal of this thesis is generation of interactive course material on FP and respective theory of programming, implemented in Isabelle and \sisac. |
37 |
36 |
38 In Isabelle the material shall exploit the recently implemented ``function package'' \cite{}. This package is the most advanced in comparison to other provers and supports all what is needed for programming and proving properties of programs. |
37 The material shall use most recent developments, for instance the ``function package'' \cite{krauss:funs} recently implemented in Isabelle. This package supports all what is needed for programming and proving properties of programs. |
39 |
38 |
40 Experience shows, that in early phases of programming (as well as of doing mathematics \cite{?}) proceeding step by step in a program is important for learning. This will be done by implementing selected programs into \sisac. |
39 Although addressing most recent developments and theory at the state of the art, the material also shall serve in early phases of programming. Experience shows, that in early phases (in analogy to doing mathematics \cite{?}) proceeding step by step in a program is important for learning. This will be done by implementing selected programs into \sisac. |
41 |
40 |
42 The interactive course material shall serve in certain courses at TUG and in the recently established ``entry and orientation phase'' (Studien-Eingangs und -Oreintierungs Phase, STEOP). |
41 The interactive course material shall serve in certain courses at TUG and in the recently established ``entry and orientation phase'' (Studien-Eingangs und -Orientierungs Phase, STEOP). |
43 |
42 |
44 \section{State of the Art} |
43 \section{State of the Art} |
|
44 The thesis cover a wide range of topics some of which will be presented in more detail to be agreed on. |
45 |
45 |
|
46 \paragraph{Theory of functional programming ?} |
46 TODO |
47 TODO |
47 |
48 |
48 %supports different kinds of function definitions (providing more or less automated support by the prover), mutual, nested and higher-order recursion, partiality |
49 \paragraph{Proof tools for FP} |
|
50 Isabelle's function package \cite{krauss:funs} is the most advanced in comparison to other provers. It supports two different way of function definitions, one providing full automation (applicable in simple cases) and another featuring interactive proofs of termination. |
49 |
51 |
50 %Coq \cite{} |
52 The function package covers the full range of FP: mutual, nested and higher-order recursion, partiality |
|
53 |
|
54 The other European computer theorem prover, Coq \cite{}, has less powerful support for FP (TODO) |
|
55 |
|
56 \paragraph{Didactics of FP} is concern of very different opinions: At some universities FP is addressed in introductory courses, while at other universities FP is considered an abstract topic addressed in higher semesters. The choice between these extreme alternatives seems to be related to principcal considerations on software construction \cite{aichernig:ingenieur}. |
|
57 |
|
58 The planned course might provide a bridge between the alternatives, addressing novices as well as advanced students by employing computer theorem provers. |
|
59 |
|
60 \paragraph{Educational math assistants,} if based on computer theorem proving, are appropriate to serve introduction to FP in a specific way: If considering evaluation of functional programs as rewriting, there is an obstacle. Empirical data show that students do not learn to apply rules at high-school --- for instance, the cannot apply the law of distributivity in algebra consciously, they do algebra in the same way they they use their mother language. |
|
61 |
|
62 The experimental system \sisac{}\footnote{http://www.ist.tugraz.at/projects/isac/} developed at TU Graz seems appropriate to provide experience in rigorous application of rewrite rules as a prerequisite to understand evaluation in FP. |
51 |
63 |
52 |
64 |
53 \section{Thesis Structure} |
65 \section{Thesis Structure} |
54 |
66 |
55 The main point of this thesis is the interactive course material, and the thesis serves this point in several ways: |
67 The main result of this thesis is the interactive course material, accompanied by a thesis. |
56 |
68 |
57 general survey on FP |
69 \paragraph{The interactive course material} will be implemented as Isabelle theories. Isabelle provides a document preparation system for theories which shall lead for a twofold presentation of the course: as (a) pdf-file(s) and as theories supporting interactive learning. |
58 |
70 |
59 description of the state of the art in proof tools specialized on FP |
71 For stepwise exercises in \sisac{} an additional Isabelle theory is required, which contains the specifications and programs for the respective exercises in ML-sections. |
60 |
72 |
61 didactic consideration about the course (what has been omitted, ...) |
73 \paragraph{The thesis} completes the work as required for a bakkalaureate. |
62 |
74 |
63 future work, probably extending the course to more advanced topics |
75 %general survey on FP |
64 |
76 % |
65 future work, extending the course to more elementary topics, probably usable at high school |
77 %description of the state of the art in proof tools specialized on FP |
66 |
78 % |
67 ... |
79 %didactic consideration about the course (what has been omitted, ...) |
68 |
80 % |
69 ... |
81 %future work, probably extending the course to more advanced topics |
|
82 % |
|
83 %future work, extending the course to more elementary topics, probably usable at high school |
|
84 % |
|
85 %... |
|
86 % |
|
87 %... |
70 |
88 |
71 |
89 |
72 \section{Timeline} |
90 \section{Timeline} |
73 |
91 |
74 The main work shall be done during this summer as much as possible. |
92 The main work shall be done during this summer as much as possible. |
75 |
93 |
76 Milestones |
94 %Milestones |
77 \subsection{TODO} |
95 %\subsection{TODO} |
78 study introductory material for Isabelle; contact Alexander Kraus and others for similar course material |
96 %study introductory material for Isabelle; contact Alexander Kraus and others for similar course material |
|
97 % |
|
98 %\subsection{TODO} |
|
99 %\sisac =''= |
79 |
100 |
80 \subsection{TODO} |
101 \bibliography{references} |
81 \sisac =''= |
|
82 |
|
83 %\bibliography{bib/TODO} |
|
84 \end{document} |
102 \end{document} |