28213
|
1 |
theory Further
|
|
2 |
imports Setup
|
|
3 |
begin
|
|
4 |
|
28447
|
5 |
section {* Further issues \label{sec:further} *}
|
28419
|
6 |
|
|
7 |
subsection {* Further reading *}
|
|
8 |
|
|
9 |
text {*
|
34155
|
10 |
To dive deeper into the issue of code generation, you should visit
|
|
11 |
the Isabelle/Isar Reference Manual \cite{isabelle-isar-ref}, which
|
28593
|
12 |
contains exhaustive syntax diagrams.
|
28419
|
13 |
*}
|
|
14 |
|
37426
|
15 |
subsection {* Locales and interpretation *}
|
|
16 |
|
|
17 |
text {*
|
|
18 |
A technical issue comes to surface when generating code from
|
|
19 |
specifications stemming from locale interpretation.
|
|
20 |
|
|
21 |
Let us assume a locale specifying a power operation
|
|
22 |
on arbitrary types:
|
|
23 |
*}
|
|
24 |
|
|
25 |
locale %quote power =
|
|
26 |
fixes power :: "'a \<Rightarrow> 'b \<Rightarrow> 'b"
|
|
27 |
assumes power_commute: "power x \<circ> power y = power y \<circ> power x"
|
|
28 |
begin
|
|
29 |
|
|
30 |
text {*
|
|
31 |
\noindent Inside that locale we can lift @{text power} to exponent lists
|
|
32 |
by means of specification relative to that locale:
|
|
33 |
*}
|
|
34 |
|
|
35 |
primrec %quote powers :: "'a list \<Rightarrow> 'b \<Rightarrow> 'b" where
|
|
36 |
"powers [] = id"
|
|
37 |
| "powers (x # xs) = power x \<circ> powers xs"
|
|
38 |
|
|
39 |
lemma %quote powers_append:
|
|
40 |
"powers (xs @ ys) = powers xs \<circ> powers ys"
|
|
41 |
by (induct xs) simp_all
|
|
42 |
|
|
43 |
lemma %quote powers_power:
|
|
44 |
"powers xs \<circ> power x = power x \<circ> powers xs"
|
|
45 |
by (induct xs)
|
|
46 |
(simp_all del: o_apply id_apply add: o_assoc [symmetric],
|
|
47 |
simp del: o_apply add: o_assoc power_commute)
|
|
48 |
|
|
49 |
lemma %quote powers_rev:
|
|
50 |
"powers (rev xs) = powers xs"
|
|
51 |
by (induct xs) (simp_all add: powers_append powers_power)
|
|
52 |
|
|
53 |
end %quote
|
|
54 |
|
|
55 |
text {*
|
|
56 |
After an interpretation of this locale (say, @{command
|
|
57 |
interpretation} @{text "fun_power:"} @{term [source] "power (\<lambda>n (f ::
|
|
58 |
'a \<Rightarrow> 'a). f ^^ n)"}), one would expect to have a constant @{text
|
|
59 |
"fun_power.powers :: nat list \<Rightarrow> ('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a"} for which code
|
|
60 |
can be generated. But this not the case: internally, the term
|
|
61 |
@{text "fun_power.powers"} is an abbreviation for the foundational
|
|
62 |
term @{term [source] "power.powers (\<lambda>n (f :: 'a \<Rightarrow> 'a). f ^^ n)"}
|
|
63 |
(see \cite{isabelle-locale} for the details behind).
|
|
64 |
|
37836
|
65 |
Fortunately, with minor effort the desired behaviour can be achieved.
|
37426
|
66 |
First, a dedicated definition of the constant on which the local @{text "powers"}
|
|
67 |
after interpretation is supposed to be mapped on:
|
|
68 |
*}
|
|
69 |
|
|
70 |
definition %quote funpows :: "nat list \<Rightarrow> ('a \<Rightarrow> 'a) \<Rightarrow> 'a \<Rightarrow> 'a" where
|
|
71 |
[code del]: "funpows = power.powers (\<lambda>n f. f ^^ n)"
|
|
72 |
|
|
73 |
text {*
|
|
74 |
\noindent In general, the pattern is @{text "c = t"} where @{text c} is
|
|
75 |
the name of the future constant and @{text t} the foundational term
|
|
76 |
corresponding to the local constant after interpretation.
|
|
77 |
|
|
78 |
The interpretation itself is enriched with an equation @{text "t = c"}:
|
|
79 |
*}
|
|
80 |
|
|
81 |
interpretation %quote fun_power: power "\<lambda>n (f :: 'a \<Rightarrow> 'a). f ^^ n" where
|
|
82 |
"power.powers (\<lambda>n f. f ^^ n) = funpows"
|
|
83 |
by unfold_locales
|
37432
|
84 |
(simp_all add: expand_fun_eq funpow_mult mult_commute funpows_def)
|
37426
|
85 |
|
|
86 |
text {*
|
|
87 |
\noindent This additional equation is trivially proved by the definition
|
|
88 |
itself.
|
|
89 |
|
|
90 |
After this setup procedure, code generation can continue as usual:
|
|
91 |
*}
|
|
92 |
|
|
93 |
text %quote {*@{code_stmts funpows (consts) Nat.funpow funpows (Haskell)}*}
|
|
94 |
|
|
95 |
|
28419
|
96 |
subsection {* Modules *}
|
|
97 |
|
|
98 |
text {*
|
|
99 |
When invoking the @{command export_code} command it is possible to leave
|
|
100 |
out the @{keyword "module_name"} part; then code is distributed over
|
|
101 |
different modules, where the module name space roughly is induced
|
28635
|
102 |
by the @{text Isabelle} theory name space.
|
28213
|
103 |
|
28419
|
104 |
Then sometimes the awkward situation occurs that dependencies between
|
|
105 |
definitions introduce cyclic dependencies between modules, which in the
|
|
106 |
@{text Haskell} world leaves you to the mercy of the @{text Haskell} implementation
|
|
107 |
you are using, while for @{text SML}/@{text OCaml} code generation is not possible.
|
|
108 |
|
|
109 |
A solution is to declare module names explicitly.
|
|
110 |
Let use assume the three cyclically dependent
|
|
111 |
modules are named \emph{A}, \emph{B} and \emph{C}.
|
|
112 |
Then, by stating
|
|
113 |
*}
|
|
114 |
|
28593
|
115 |
code_modulename %quote SML
|
28419
|
116 |
A ABC
|
|
117 |
B ABC
|
|
118 |
C ABC
|
|
119 |
|
34155
|
120 |
text {*\noindent
|
28419
|
121 |
we explicitly map all those modules on \emph{ABC},
|
|
122 |
resulting in an ad-hoc merge of this three modules
|
|
123 |
at serialisation time.
|
|
124 |
*}
|
28213
|
125 |
|
|
126 |
subsection {* Evaluation oracle *}
|
|
127 |
|
28593
|
128 |
text {*
|
|
129 |
Code generation may also be used to \emph{evaluate} expressions
|
|
130 |
(using @{text SML} as target language of course).
|
34155
|
131 |
For instance, the @{command value} reduces an expression to a
|
28593
|
132 |
normal form with respect to the underlying code equations:
|
|
133 |
*}
|
|
134 |
|
|
135 |
value %quote "42 / (12 :: rat)"
|
|
136 |
|
|
137 |
text {*
|
|
138 |
\noindent will display @{term "7 / (2 :: rat)"}.
|
|
139 |
|
|
140 |
The @{method eval} method tries to reduce a goal by code generation to @{term True}
|
|
141 |
and solves it in that case, but fails otherwise:
|
|
142 |
*}
|
|
143 |
|
|
144 |
lemma %quote "42 / (12 :: rat) = 7 / 2"
|
|
145 |
by %quote eval
|
|
146 |
|
|
147 |
text {*
|
|
148 |
\noindent The soundness of the @{method eval} method depends crucially
|
|
149 |
on the correctness of the code generator; this is one of the reasons
|
31050
|
150 |
why you should not use adaptation (see \secref{sec:adaptation}) frivolously.
|
28593
|
151 |
*}
|
|
152 |
|
28213
|
153 |
subsection {* Code antiquotation *}
|
|
154 |
|
28593
|
155 |
text {*
|
|
156 |
In scenarios involving techniques like reflection it is quite common
|
|
157 |
that code generated from a theory forms the basis for implementing
|
|
158 |
a proof procedure in @{text SML}. To facilitate interfacing of generated code
|
|
159 |
with system code, the code generator provides a @{text code} antiquotation:
|
|
160 |
*}
|
|
161 |
|
30880
|
162 |
datatype %quote form = T | F | And form form | Or form form (*<*)
|
|
163 |
|
|
164 |
(*>*) ML %quotett {*
|
28593
|
165 |
fun eval_form @{code T} = true
|
|
166 |
| eval_form @{code F} = false
|
|
167 |
| eval_form (@{code And} (p, q)) =
|
|
168 |
eval_form p andalso eval_form q
|
|
169 |
| eval_form (@{code Or} (p, q)) =
|
|
170 |
eval_form p orelse eval_form q;
|
|
171 |
*}
|
|
172 |
|
|
173 |
text {*
|
|
174 |
\noindent @{text code} takes as argument the name of a constant; after the
|
|
175 |
whole @{text SML} is read, the necessary code is generated transparently
|
|
176 |
and the corresponding constant names are inserted. This technique also
|
|
177 |
allows to use pattern matching on constructors stemming from compiled
|
37210
|
178 |
@{text "datatypes"}.
|
28593
|
179 |
|
29796
|
180 |
For a less simplistic example, theory @{theory Ferrack} is
|
28593
|
181 |
a good reference.
|
|
182 |
*}
|
28213
|
183 |
|
28419
|
184 |
subsection {* Imperative data structures *}
|
|
185 |
|
28593
|
186 |
text {*
|
|
187 |
If you consider imperative data structures as inevitable for a specific
|
|
188 |
application, you should consider
|
|
189 |
\emph{Imperative Functional Programming with Isabelle/HOL}
|
34155
|
190 |
\cite{bulwahn-et-al:2008:imperative};
|
28593
|
191 |
the framework described there is available in theory @{theory Imperative_HOL}.
|
|
192 |
*}
|
|
193 |
|
28213
|
194 |
end
|