9722
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
9924
|
3 |
\def\isabellecontext{Nested}%
|
8749
|
4 |
%
|
|
5 |
\begin{isamarkuptext}%
|
|
6 |
So far, all datatypes had the property that on the right-hand side of their
|
|
7 |
definition they occurred only at the top-level, i.e.\ directly below a
|
|
8 |
constructor. This is not the case any longer for the following model of terms
|
|
9 |
where function symbols can be applied to a list of arguments:%
|
|
10 |
\end{isamarkuptext}%
|
9698
|
11 |
\isacommand{datatype}\ {\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}{\isachardoublequote}term{\isachardoublequote}\ {\isacharequal}\ Var\ {\isacharprime}a\ {\isacharbar}\ App\ {\isacharprime}b\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term\ list{\isachardoublequote}%
|
8749
|
12 |
\begin{isamarkuptext}%
|
|
13 |
\noindent
|
|
14 |
Note that we need to quote \isa{term} on the left to avoid confusion with
|
10171
|
15 |
the Isabelle command \isacommand{term}.
|
9792
|
16 |
Parameter \isa{{\isacharprime}a} is the type of variables and \isa{{\isacharprime}b} the type of
|
8749
|
17 |
function symbols.
|
9933
|
18 |
A mathematical term like $f(x,g(y))$ becomes \isa{App\ f\ {\isacharbrackleft}Var\ x{\isacharcomma}\ App\ g\ {\isacharbrackleft}Var\ y{\isacharbrackright}{\isacharbrackright}}, where \isa{f}, \isa{g}, \isa{x}, \isa{y} are
|
8749
|
19 |
suitable values, e.g.\ numbers or strings.
|
|
20 |
|
|
21 |
What complicates the definition of \isa{term} is the nested occurrence of
|
|
22 |
\isa{term} inside \isa{list} on the right-hand side. In principle,
|
|
23 |
nested recursion can be eliminated in favour of mutual recursion by unfolding
|
|
24 |
the offending datatypes, here \isa{list}. The result for \isa{term}
|
|
25 |
would be something like
|
8751
|
26 |
\medskip
|
|
27 |
|
|
28 |
\input{Datatype/document/unfoldnested.tex}
|
|
29 |
\medskip
|
|
30 |
|
|
31 |
\noindent
|
8749
|
32 |
Although we do not recommend this unfolding to the user, it shows how to
|
|
33 |
simulate nested recursion by mutual recursion.
|
|
34 |
Now we return to the initial definition of \isa{term} using
|
|
35 |
nested recursion.
|
|
36 |
|
|
37 |
Let us define a substitution function on terms. Because terms involve term
|
|
38 |
lists, we need to define two substitution functions simultaneously:%
|
|
39 |
\end{isamarkuptext}%
|
|
40 |
\isacommand{consts}\isanewline
|
9698
|
41 |
subst\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isasymRightarrow}{\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term{\isacharparenright}\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term\ \ \ \ \ \ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term{\isachardoublequote}\isanewline
|
|
42 |
substs{\isacharcolon}{\isacharcolon}\ {\isachardoublequote}{\isacharparenleft}{\isacharprime}a{\isasymRightarrow}{\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term{\isacharparenright}\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term\ list\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term\ list{\isachardoublequote}\isanewline
|
8749
|
43 |
\isanewline
|
|
44 |
\isacommand{primrec}\isanewline
|
9698
|
45 |
\ \ {\isachardoublequote}subst\ s\ {\isacharparenleft}Var\ x{\isacharparenright}\ {\isacharequal}\ s\ x{\isachardoublequote}\isanewline
|
|
46 |
\ \ subst{\isacharunderscore}App{\isacharcolon}\isanewline
|
|
47 |
\ \ {\isachardoublequote}subst\ s\ {\isacharparenleft}App\ f\ ts{\isacharparenright}\ {\isacharequal}\ App\ f\ {\isacharparenleft}substs\ s\ ts{\isacharparenright}{\isachardoublequote}\isanewline
|
8749
|
48 |
\isanewline
|
9698
|
49 |
\ \ {\isachardoublequote}substs\ s\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequote}\isanewline
|
|
50 |
\ \ {\isachardoublequote}substs\ s\ {\isacharparenleft}t\ {\isacharhash}\ ts{\isacharparenright}\ {\isacharequal}\ subst\ s\ t\ {\isacharhash}\ substs\ s\ ts{\isachardoublequote}%
|
8749
|
51 |
\begin{isamarkuptext}%
|
|
52 |
\noindent
|
10171
|
53 |
Individual equations in a primrec definition may be named as shown for \isa{subst{\isacharunderscore}App}.
|
|
54 |
The significance of this device will become apparent below.
|
9644
|
55 |
|
8749
|
56 |
Similarly, when proving a statement about terms inductively, we need
|
|
57 |
to prove a related statement about term lists simultaneously. For example,
|
|
58 |
the fact that the identity substitution does not change a term needs to be
|
|
59 |
strengthened and proved as follows:%
|
|
60 |
\end{isamarkuptext}%
|
9698
|
61 |
\isacommand{lemma}\ {\isachardoublequote}subst\ \ Var\ t\ \ {\isacharequal}\ {\isacharparenleft}t\ {\isacharcolon}{\isacharcolon}{\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term{\isacharparenright}\ \ {\isasymand}\isanewline
|
|
62 |
\ \ \ \ \ \ \ \ substs\ Var\ ts\ {\isacharequal}\ {\isacharparenleft}ts{\isacharcolon}{\isacharcolon}{\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}term\ list{\isacharparenright}{\isachardoublequote}\isanewline
|
10171
|
63 |
\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ t\ \isakeyword{and}\ ts{\isacharcomma}\ simp{\isacharunderscore}all{\isacharparenright}\isanewline
|
|
64 |
\isacommand{done}%
|
8749
|
65 |
\begin{isamarkuptext}%
|
|
66 |
\noindent
|
9933
|
67 |
Note that \isa{Var} is the identity substitution because by definition it
|
|
68 |
leaves variables unchanged: \isa{subst\ Var\ {\isacharparenleft}Var\ x{\isacharparenright}\ {\isacharequal}\ Var\ x}. Note also
|
8749
|
69 |
that the type annotations are necessary because otherwise there is nothing in
|
|
70 |
the goal to enforce that both halves of the goal talk about the same type
|
9792
|
71 |
parameters \isa{{\isacharparenleft}{\isacharprime}a{\isacharcomma}{\isacharprime}b{\isacharparenright}}. As a result, induction would fail
|
8749
|
72 |
because the two halves of the goal would be unrelated.
|
|
73 |
|
|
74 |
\begin{exercise}
|
|
75 |
The fact that substitution distributes over composition can be expressed
|
|
76 |
roughly as follows:
|
9792
|
77 |
\begin{isabelle}%
|
10178
|
78 |
\ \ \ \ \ subst\ {\isacharparenleft}f\ {\isasymcirc}\ g{\isacharparenright}\ t\ {\isacharequal}\ subst\ f\ {\isacharparenleft}subst\ g\ t{\isacharparenright}%
|
9924
|
79 |
\end{isabelle}
|
8749
|
80 |
Correct this statement (you will find that it does not type-check),
|
10178
|
81 |
strengthen it, and prove it. (Note: \isa{{\isasymcirc}} is function composition;
|
9792
|
82 |
its definition is found in theorem \isa{o{\isacharunderscore}def}).
|
8749
|
83 |
\end{exercise}
|
9644
|
84 |
\begin{exercise}\label{ex:trev-trev}
|
9792
|
85 |
Define a function \isa{trev} of type \isa{{\isacharparenleft}{\isacharprime}a{\isacharcomma}\ {\isacharprime}b{\isacharparenright}\ term\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a{\isacharcomma}\ {\isacharprime}b{\isacharparenright}\ term}
|
|
86 |
that recursively reverses the order of arguments of all function symbols in a
|
|
87 |
term. Prove that \isa{trev\ {\isacharparenleft}trev\ t{\isacharparenright}\ {\isacharequal}\ t}.
|
9644
|
88 |
\end{exercise}
|
|
89 |
|
|
90 |
The experienced functional programmer may feel that our above definition of
|
9792
|
91 |
\isa{subst} is unnecessarily complicated in that \isa{substs} is
|
|
92 |
completely unnecessary. The \isa{App}-case can be defined directly as
|
9644
|
93 |
\begin{isabelle}%
|
9834
|
94 |
\ \ \ \ \ subst\ s\ {\isacharparenleft}App\ f\ ts{\isacharparenright}\ {\isacharequal}\ App\ f\ {\isacharparenleft}map\ {\isacharparenleft}subst\ s{\isacharparenright}\ ts{\isacharparenright}%
|
9924
|
95 |
\end{isabelle}
|
9644
|
96 |
where \isa{map} is the standard list function such that
|
9792
|
97 |
\isa{map\ f\ {\isacharbrackleft}x\isadigit{1}{\isacharcomma}{\isachardot}{\isachardot}{\isachardot}{\isacharcomma}xn{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}f\ x\isadigit{1}{\isacharcomma}{\isachardot}{\isachardot}{\isachardot}{\isacharcomma}f\ xn{\isacharbrackright}}. This is true, but Isabelle
|
|
98 |
insists on the above fixed format. Fortunately, we can easily \emph{prove}
|
|
99 |
that the suggested equation holds:%
|
9644
|
100 |
\end{isamarkuptext}%
|
9698
|
101 |
\isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\ {\isachardoublequote}subst\ s\ {\isacharparenleft}App\ f\ ts{\isacharparenright}\ {\isacharequal}\ App\ f\ {\isacharparenleft}map\ {\isacharparenleft}subst\ s{\isacharparenright}\ ts{\isacharparenright}{\isachardoublequote}\isanewline
|
10171
|
102 |
\isacommand{apply}{\isacharparenleft}induct{\isacharunderscore}tac\ ts{\isacharcomma}\ simp{\isacharunderscore}all{\isacharparenright}\isanewline
|
|
103 |
\isacommand{done}%
|
9644
|
104 |
\begin{isamarkuptext}%
|
9689
|
105 |
\noindent
|
9644
|
106 |
What is more, we can now disable the old defining equation as a
|
|
107 |
simplification rule:%
|
|
108 |
\end{isamarkuptext}%
|
9933
|
109 |
\isacommand{declare}\ subst{\isacharunderscore}App\ {\isacharbrackleft}simp\ del{\isacharbrackright}%
|
9644
|
110 |
\begin{isamarkuptext}%
|
|
111 |
\noindent
|
9689
|
112 |
The advantage is that now we have replaced \isa{substs} by
|
|
113 |
\isa{map}, we can profit from the large number of pre-proved lemmas
|
|
114 |
about \isa{map}. Unfortunately inductive proofs about type
|
|
115 |
\isa{term} are still awkward because they expect a conjunction. One
|
|
116 |
could derive a new induction principle as well (see
|
|
117 |
\S\ref{sec:derive-ind}), but turns out to be simpler to define
|
|
118 |
functions by \isacommand{recdef} instead of \isacommand{primrec}.
|
10186
|
119 |
The details are explained in \S\ref{sec:nested-recdef} below.
|
8749
|
120 |
|
|
121 |
Of course, you may also combine mutual and nested recursion. For example,
|
|
122 |
constructor \isa{Sum} in \S\ref{sec:datatype-mut-rec} could take a list of
|
9792
|
123 |
expressions as its argument: \isa{Sum}~\isa{{\isachardoublequote}{\isacharprime}a\ aexp\ list{\isachardoublequote}}.%
|
8749
|
124 |
\end{isamarkuptext}%
|
9722
|
125 |
\end{isabellebody}%
|
9145
|
126 |
%%% Local Variables:
|
|
127 |
%%% mode: latex
|
|
128 |
%%% TeX-master: "root"
|
|
129 |
%%% End:
|