author | oheimb |
Wed, 03 Apr 2002 10:21:13 +0200 | |
changeset 13076 | 70704dd48bd5 |
parent 12890 | 75b254b1c8ba |
child 13754 | 021cf00435a9 |
permissions | -rw-r--r-- |
12446 | 1 |
(* Title: HOL/datatype_codegen.ML |
12445 | 2 |
ID: $Id$ |
3 |
Author: Stefan Berghofer, TU Muenchen |
|
4 |
License: GPL (GNU GENERAL PUBLIC LICENSE) |
|
5 |
||
6 |
Code generator for inductive datatypes. |
|
7 |
*) |
|
8 |
||
9 |
signature DATATYPE_CODEGEN = |
|
10 |
sig |
|
11 |
val setup: (theory -> theory) list |
|
12 |
end; |
|
13 |
||
14 |
structure DatatypeCodegen : DATATYPE_CODEGEN = |
|
15 |
struct |
|
16 |
||
17 |
open Codegen; |
|
18 |
||
19 |
fun mk_tuple [p] = p |
|
20 |
| mk_tuple ps = Pretty.block (Pretty.str "(" :: |
|
21 |
flat (separate [Pretty.str ",", Pretty.brk 1] (map single ps)) @ |
|
22 |
[Pretty.str ")"]); |
|
23 |
||
24 |
||
25 |
(**** datatype definition ****) |
|
26 |
||
12890 | 27 |
fun add_dt_defs thy dep gr (descr: DatatypeAux.descr) = |
12445 | 28 |
let |
29 |
val sg = sign_of thy; |
|
30 |
val tab = DatatypePackage.get_datatypes thy; |
|
31 |
||
32 |
val descr' = filter (can (map DatatypeAux.dest_DtTFree o #2 o snd)) descr; |
|
33 |
||
34 |
val (_, (_, _, (cname, _) :: _)) :: _ = descr'; |
|
35 |
val dname = mk_const_id sg cname; |
|
36 |
||
37 |
fun mk_dtdef gr prfx [] = (gr, []) |
|
38 |
| mk_dtdef gr prfx ((_, (tname, dts, cs))::xs) = |
|
39 |
let |
|
40 |
val tvs = map DatatypeAux.dest_DtTFree dts; |
|
41 |
val sorts = map (rpair []) tvs; |
|
42 |
val cs' = map (apsnd (map (DatatypeAux.typ_of_dtyp descr sorts))) cs; |
|
43 |
val (gr', ps) = foldl_map (fn (gr, (cname, cargs)) => |
|
44 |
apsnd (pair cname) (foldl_map |
|
45 |
(invoke_tycodegen thy dname false) (gr, cargs))) (gr, cs'); |
|
46 |
val (gr'', rest) = mk_dtdef gr' "and " xs |
|
47 |
in |
|
48 |
(gr'', |
|
49 |
Pretty.block (Pretty.str prfx :: |
|
50 |
(if null tvs then [] else |
|
51 |
[mk_tuple (map Pretty.str tvs), Pretty.str " "]) @ |
|
52 |
[Pretty.str (mk_type_id sg tname ^ " ="), Pretty.brk 1] @ |
|
53 |
flat (separate [Pretty.brk 1, Pretty.str "| "] |
|
54 |
(map (fn (cname, ps') => [Pretty.block |
|
55 |
(Pretty.str (mk_const_id sg cname) :: |
|
56 |
(if null ps' then [] else |
|
57 |
flat ([Pretty.str " of", Pretty.brk 1] :: |
|
58 |
separate [Pretty.str " *", Pretty.brk 1] |
|
59 |
(map single ps'))))]) ps))) :: rest) |
|
60 |
end |
|
61 |
in |
|
62 |
((Graph.add_edge_acyclic (dname, dep) gr |
|
63 |
handle Graph.CYCLES _ => gr) handle Graph.UNDEF _ => |
|
64 |
let |
|
65 |
val gr1 = Graph.add_edge (dname, dep) |
|
66 |
(Graph.new_node (dname, (None, "")) gr); |
|
67 |
val (gr2, dtdef) = mk_dtdef gr1 "datatype " descr'; |
|
68 |
in |
|
69 |
Graph.map_node dname (K (None, |
|
70 |
Pretty.string_of (Pretty.blk (0, separate Pretty.fbrk dtdef @ |
|
71 |
[Pretty.str ";"])) ^ "\n\n")) gr2 |
|
72 |
end) |
|
73 |
end; |
|
74 |
||
75 |
||
76 |
(**** case expressions ****) |
|
77 |
||
78 |
fun pretty_case thy gr dep brack constrs (c as Const (_, T)) ts = |
|
79 |
let val i = length constrs |
|
80 |
in if length ts <= i then |
|
81 |
invoke_codegen thy dep brack (gr, eta_expand c ts (i+1)) |
|
82 |
else |
|
83 |
let |
|
84 |
val ts1 = take (i, ts); |
|
85 |
val t :: ts2 = drop (i, ts); |
|
86 |
val names = foldr add_term_names (ts1, |
|
87 |
map (fst o fst o dest_Var) (foldr add_term_vars (ts1, []))); |
|
88 |
val (Ts, dT) = split_last (take (i+1, fst (strip_type T))); |
|
89 |
||
90 |
fun pcase gr [] [] [] = ([], gr) |
|
91 |
| pcase gr ((cname, cargs)::cs) (t::ts) (U::Us) = |
|
92 |
let |
|
93 |
val j = length cargs; |
|
94 |
val xs = variantlist (replicate j "x", names); |
|
95 |
val Us' = take (j, fst (strip_type U)); |
|
96 |
val frees = map Free (xs ~~ Us'); |
|
97 |
val (gr0, cp) = invoke_codegen thy dep false |
|
98 |
(gr, list_comb (Const (cname, Us' ---> dT), frees)); |
|
99 |
val t' = Envir.beta_norm (list_comb (t, frees)); |
|
100 |
val (gr1, p) = invoke_codegen thy dep false (gr0, t'); |
|
101 |
val (ps, gr2) = pcase gr1 cs ts Us; |
|
102 |
in |
|
103 |
([Pretty.block [cp, Pretty.str " =>", Pretty.brk 1, p]] :: ps, gr2) |
|
104 |
end; |
|
105 |
||
106 |
val (ps1, gr1) = pcase gr constrs ts1 Ts; |
|
107 |
val ps = flat (separate [Pretty.brk 1, Pretty.str "| "] ps1); |
|
108 |
val (gr2, p) = invoke_codegen thy dep false (gr1, t); |
|
109 |
val (gr3, ps2) = foldl_map (invoke_codegen thy dep true) (gr2, ts2) |
|
110 |
in (gr3, (if not (null ts2) andalso brack then parens else I) |
|
111 |
(Pretty.block (separate (Pretty.brk 1) |
|
112 |
(Pretty.block ([Pretty.str "(case ", p, Pretty.str " of", |
|
113 |
Pretty.brk 1] @ ps @ [Pretty.str ")"]) :: ps2)))) |
|
114 |
end |
|
115 |
end; |
|
116 |
||
117 |
||
118 |
(**** constructors ****) |
|
119 |
||
120 |
fun pretty_constr thy gr dep brack args (c as Const (s, _)) ts = |
|
121 |
let val i = length args |
|
122 |
in if i > 1 andalso length ts < i then |
|
123 |
invoke_codegen thy dep brack (gr, eta_expand c ts i) |
|
124 |
else |
|
125 |
let |
|
126 |
val id = mk_const_id (sign_of thy) s; |
|
127 |
val (gr', ps) = foldl_map (invoke_codegen thy dep (i = 1)) (gr, ts); |
|
128 |
in (case args of |
|
129 |
_ :: _ :: _ => (gr', (if brack then parens else I) |
|
130 |
(Pretty.block [Pretty.str id, Pretty.brk 1, mk_tuple ps])) |
|
131 |
| _ => (gr', mk_app brack (Pretty.str id) ps)) |
|
132 |
end |
|
133 |
end; |
|
134 |
||
135 |
||
136 |
(**** code generators for terms and types ****) |
|
137 |
||
138 |
fun datatype_codegen thy gr dep brack t = (case strip_comb t of |
|
139 |
(c as Const (s, T), ts) => |
|
140 |
(case find_first (fn (_, {index, descr, case_name, ...}) => |
|
141 |
s = case_name orelse |
|
142 |
is_some (assoc (#3 (the (assoc (descr, index))), s))) |
|
143 |
(Symtab.dest (DatatypePackage.get_datatypes thy)) of |
|
144 |
None => None |
|
145 |
| Some (tname, {index, descr, ...}) => |
|
146 |
if is_some (get_assoc_code thy s T) then None else |
|
147 |
let val Some (_, _, constrs) = assoc (descr, index) |
|
12822
073116d65bb9
datatype_codegen now checks type of constructor.
berghofe
parents:
12446
diff
changeset
|
148 |
in (case (assoc (constrs, s), strip_type T) of |
073116d65bb9
datatype_codegen now checks type of constructor.
berghofe
parents:
12446
diff
changeset
|
149 |
(None, _) => Some (pretty_case thy gr dep brack |
12445 | 150 |
(#3 (the (assoc (descr, index)))) c ts) |
12822
073116d65bb9
datatype_codegen now checks type of constructor.
berghofe
parents:
12446
diff
changeset
|
151 |
| (Some args, (_, Type _)) => Some (pretty_constr thy |
12445 | 152 |
(fst (invoke_tycodegen thy dep false (gr, snd (strip_type T)))) |
12822
073116d65bb9
datatype_codegen now checks type of constructor.
berghofe
parents:
12446
diff
changeset
|
153 |
dep brack args c ts) |
073116d65bb9
datatype_codegen now checks type of constructor.
berghofe
parents:
12446
diff
changeset
|
154 |
| _ => None) |
12445 | 155 |
end) |
156 |
| _ => None); |
|
157 |
||
158 |
fun datatype_tycodegen thy gr dep brack (Type (s, Ts)) = |
|
159 |
(case Symtab.lookup (DatatypePackage.get_datatypes thy, s) of |
|
160 |
None => None |
|
161 |
| Some {descr, ...} => |
|
162 |
if is_some (get_assoc_type thy s) then None else |
|
163 |
let val (gr', ps) = foldl_map |
|
164 |
(invoke_tycodegen thy dep false) (gr, Ts) |
|
165 |
in Some (add_dt_defs thy dep gr' descr, |
|
166 |
Pretty.block ((if null Ts then [] else |
|
167 |
[mk_tuple ps, Pretty.str " "]) @ |
|
168 |
[Pretty.str (mk_type_id (sign_of thy) s)])) |
|
169 |
end) |
|
170 |
| datatype_tycodegen _ _ _ _ _ = None; |
|
171 |
||
172 |
||
173 |
val setup = |
|
174 |
[add_codegen "datatype" datatype_codegen, |
|
175 |
add_tycodegen "datatype" datatype_tycodegen]; |
|
176 |
||
177 |
end; |