15 datatype ('v,'f)"term" = Var 'v | App 'f "('v,'f)term list" |
15 datatype ('v,'f)"term" = Var 'v | App 'f "('v,'f)term list" |
16 |
16 |
17 text\<open>\noindent |
17 text\<open>\noindent |
18 Note that we need to quote \<open>term\<close> on the left to avoid confusion with |
18 Note that we need to quote \<open>term\<close> on the left to avoid confusion with |
19 the Isabelle command \isacommand{term}. |
19 the Isabelle command \isacommand{term}. |
20 Parameter @{typ"'v"} is the type of variables and @{typ"'f"} the type of |
20 Parameter \<^typ>\<open>'v\<close> is the type of variables and \<^typ>\<open>'f\<close> the type of |
21 function symbols. |
21 function symbols. |
22 A mathematical term like $f(x,g(y))$ becomes @{term"App f [Var x, App g |
22 A mathematical term like $f(x,g(y))$ becomes \<^term>\<open>App f [Var x, App g |
23 [Var y]]"}, where @{term f}, @{term g}, @{term x}, @{term y} are |
23 [Var y]]\<close>, where \<^term>\<open>f\<close>, \<^term>\<open>g\<close>, \<^term>\<open>x\<close>, \<^term>\<open>y\<close> are |
24 suitable values, e.g.\ numbers or strings. |
24 suitable values, e.g.\ numbers or strings. |
25 |
25 |
26 What complicates the definition of \<open>term\<close> is the nested occurrence of |
26 What complicates the definition of \<open>term\<close> is the nested occurrence of |
27 \<open>term\<close> inside \<open>list\<close> on the right-hand side. In principle, |
27 \<open>term\<close> inside \<open>list\<close> on the right-hand side. In principle, |
28 nested recursion can be eliminated in favour of mutual recursion by unfolding |
28 nested recursion can be eliminated in favour of mutual recursion by unfolding |
69 substs Var ts = (ts::('v,'f)term list)" |
69 substs Var ts = (ts::('v,'f)term list)" |
70 apply(induct_tac t and ts rule: subst.induct substs.induct, simp_all) |
70 apply(induct_tac t and ts rule: subst.induct substs.induct, simp_all) |
71 done |
71 done |
72 |
72 |
73 text\<open>\noindent |
73 text\<open>\noindent |
74 Note that @{term Var} is the identity substitution because by definition it |
74 Note that \<^term>\<open>Var\<close> is the identity substitution because by definition it |
75 leaves variables unchanged: @{prop"subst Var (Var x) = Var x"}. Note also |
75 leaves variables unchanged: \<^prop>\<open>subst Var (Var x) = Var x\<close>. Note also |
76 that the type annotations are necessary because otherwise there is nothing in |
76 that the type annotations are necessary because otherwise there is nothing in |
77 the goal to enforce that both halves of the goal talk about the same type |
77 the goal to enforce that both halves of the goal talk about the same type |
78 parameters \<open>('v,'f)\<close>. As a result, induction would fail |
78 parameters \<open>('v,'f)\<close>. As a result, induction would fail |
79 because the two halves of the goal would be unrelated. |
79 because the two halves of the goal would be unrelated. |
80 |
80 |
85 Correct this statement (you will find that it does not type-check), |
85 Correct this statement (you will find that it does not type-check), |
86 strengthen it, and prove it. (Note: \<open>\<circ>\<close> is function composition; |
86 strengthen it, and prove it. (Note: \<open>\<circ>\<close> is function composition; |
87 its definition is found in theorem @{thm[source]o_def}). |
87 its definition is found in theorem @{thm[source]o_def}). |
88 \end{exercise} |
88 \end{exercise} |
89 \begin{exercise}\label{ex:trev-trev} |
89 \begin{exercise}\label{ex:trev-trev} |
90 Define a function @{term trev} of type @{typ"('v,'f)term => ('v,'f)term"} |
90 Define a function \<^term>\<open>trev\<close> of type \<^typ>\<open>('v,'f)term => ('v,'f)term\<close> |
91 that recursively reverses the order of arguments of all function symbols in a |
91 that recursively reverses the order of arguments of all function symbols in a |
92 term. Prove that @{prop"trev(trev t) = t"}. |
92 term. Prove that \<^prop>\<open>trev(trev t) = t\<close>. |
93 \end{exercise} |
93 \end{exercise} |
94 |
94 |
95 The experienced functional programmer may feel that our definition of |
95 The experienced functional programmer may feel that our definition of |
96 @{term subst} is too complicated in that @{const substs} is |
96 \<^term>\<open>subst\<close> is too complicated in that \<^const>\<open>substs\<close> is |
97 unnecessary. The @{term App}-case can be defined directly as |
97 unnecessary. The \<^term>\<open>App\<close>-case can be defined directly as |
98 @{term[display]"subst s (App f ts) = App f (map (subst s) ts)"} |
98 @{term[display]"subst s (App f ts) = App f (map (subst s) ts)"} |
99 where @{term"map"} is the standard list function such that |
99 where \<^term>\<open>map\<close> is the standard list function such that |
100 \<open>map f [x1,...,xn] = [f x1,...,f xn]\<close>. This is true, but Isabelle |
100 \<open>map f [x1,...,xn] = [f x1,...,f xn]\<close>. This is true, but Isabelle |
101 insists on the conjunctive format. Fortunately, we can easily \emph{prove} |
101 insists on the conjunctive format. Fortunately, we can easily \emph{prove} |
102 that the suggested equation holds: |
102 that the suggested equation holds: |
103 \<close> |
103 \<close> |
104 (*<*) |
104 (*<*) |
138 simplification rule: |
138 simplification rule: |
139 \<close> |
139 \<close> |
140 |
140 |
141 declare subst_App [simp del] |
141 declare subst_App [simp del] |
142 |
142 |
143 text\<open>\noindent The advantage is that now we have replaced @{const |
143 text\<open>\noindent The advantage is that now we have replaced \<^const>\<open>substs\<close> by \<^const>\<open>map\<close>, we can profit from the large number of |
144 substs} by @{const map}, we can profit from the large number of |
144 pre-proved lemmas about \<^const>\<open>map\<close>. Unfortunately, inductive proofs |
145 pre-proved lemmas about @{const map}. Unfortunately, inductive proofs |
|
146 about type \<open>term\<close> are still awkward because they expect a |
145 about type \<open>term\<close> are still awkward because they expect a |
147 conjunction. One could derive a new induction principle as well (see |
146 conjunction. One could derive a new induction principle as well (see |
148 \S\ref{sec:derive-ind}), but simpler is to stop using |
147 \S\ref{sec:derive-ind}), but simpler is to stop using |
149 \isacommand{primrec} and to define functions with \isacommand{fun} |
148 \isacommand{primrec} and to define functions with \isacommand{fun} |
150 instead. Simple uses of \isacommand{fun} are described in |
149 instead. Simple uses of \isacommand{fun} are described in |