Mercurial > urweb

annotate src/cjrize.sml @ 188:8e9f97508f0d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Datatype representation optimization
author Adam Chlipala <adamc@hcoop.net>
date Sun, 03 Aug 2008 19:49:21 -0400
parents 88d46972de53
children 890a61991263
rev   line source
adamc@29 1 (* Copyright (c) 2008, Adam Chlipala
adamc@29 2 * All rights reserved.
adamc@29 3 *
adamc@29 4 * Redistribution and use in source and binary forms, with or without
adamc@29 5 * modification, are permitted provided that the following conditions are met:
adamc@29 6 *
adamc@29 7 * - Redistributions of source code must retain the above copyright notice,
adamc@29 8 * this list of conditions and the following disclaimer.
adamc@29 9 * - Redistributions in binary form must reproduce the above copyright notice,
adamc@29 10 * this list of conditions and the following disclaimer in the documentation
adamc@29 11 * and/or other materials provided with the distribution.
adamc@29 12 * - The names of contributors may not be used to endorse or promote products
adamc@29 13 * derived from this software without specific prior written permission.
adamc@29 14 *
adamc@29 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@29 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@29 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@29 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@29 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
adamc@29 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@29 21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@29 22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@29 23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@29 24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@29 25 * POSSIBILITY OF SUCH DAMAGE.
adamc@29 26 *)
adamc@29 27
adamc@29 28 structure Cjrize :> CJRIZE = struct
adamc@29 29
adamc@109 30 structure L = Mono
adamc@29 31 structure L' = Cjr
adamc@29 32
adamc@29 33 structure Sm :> sig
adamc@29 34 type t
adamc@29 35
adamc@29 36 val empty : t
adamc@29 37 val find : t * (string * L.typ) list * (string * L'.typ) list -> t * int
adamc@29 38
adamc@29 39 val declares : t -> (int * (string * L'.typ) list) list
adamc@29 40 end = struct
adamc@29 41
adamc@29 42 structure FM = BinaryMapFn(struct
adamc@29 43 type ord_key = L.typ
adamc@109 44 val compare = MonoUtil.Typ.compare
adamc@29 45 end)
adamc@29 46
adamc@29 47 type t = int * int FM.map * (int * (string * L'.typ) list) list
adamc@29 48
adamc@102 49 val empty : t = (1, FM.insert (FM.empty, (L.TRecord [], ErrorMsg.dummySpan), 0), [])
adamc@29 50
adamc@29 51 fun find ((n, m, ds), xts, xts') =
adamc@29 52 let
adamc@29 53 val t = (L.TRecord xts, ErrorMsg.dummySpan)
adamc@29 54 in
adamc@29 55 case FM.find (m, t) of
adamc@29 56 NONE => ((n+1, FM.insert (m, t, n), (n, xts') :: ds), n)
adamc@29 57 | SOME i => ((n, m, ds), i)
adamc@29 58 end
adamc@29 59
adamc@29 60 fun declares (_, _, ds) = ds
adamc@29 61
adamc@29 62 end
adamc@29 63
adamc@29 64 fun cifyTyp ((t, loc), sm) =
adamc@29 65 case t of
adamc@109 66 L.TFun (t1, t2) =>
adamc@29 67 let
adamc@29 68 val (t1, sm) = cifyTyp (t1, sm)
adamc@29 69 val (t2, sm) = cifyTyp (t2, sm)
adamc@29 70 in
adamc@109 71 ((L'.TFun (t1, t2), loc), sm)
adamc@29 72 end
adamc@29 73 | L.TRecord xts =>
adamc@29 74 let
adamc@29 75 val old_xts = xts
adamc@29 76 val (xts, sm) = ListUtil.foldlMap (fn ((x, t), sm) =>
adamc@29 77 let
adamc@29 78 val (t, sm) = cifyTyp (t, sm)
adamc@29 79 in
adamc@29 80 ((x, t), sm)
adamc@29 81 end)
adamc@29 82 sm xts
adamc@29 83 val (sm, si) = Sm.find (sm, old_xts, xts)
adamc@29 84 in
adamc@29 85 ((L'.TRecord si, loc), sm)
adamc@29 86 end
adamc@188 87 | L.TDatatype (dk, n, xncs) =>
adamc@168 88 let
adamc@168 89 val (xncs, sm) = ListUtil.foldlMap (fn ((x, n, to), sm) =>
adamc@168 90 case to of
adamc@168 91 NONE => ((x, n, NONE), sm)
adamc@168 92 | SOME t =>
adamc@168 93 let
adamc@168 94 val (t, sm) = cifyTyp (t, sm)
adamc@168 95 in
adamc@168 96 ((x, n, SOME t), sm)
adamc@168 97 end)
adamc@168 98 sm xncs
adamc@168 99 in
adamc@188 100 ((L'.TDatatype (dk, n, xncs), loc), sm)
adamc@168 101 end
adamc@53 102 | L.TFfi mx => ((L'.TFfi mx, loc), sm)
adamc@29 103
adamc@109 104 val dummye = (L'.EPrim (Prim.Int 0), ErrorMsg.dummySpan)
adamc@109 105
adamc@186 106 fun cifyPatCon (pc, sm) =
adamc@181 107 case pc of
adamc@186 108 L.PConVar n => (L'.PConVar n, sm)
adamc@186 109 | L.PConFfi {mod = m, datatyp, con, arg} =>
adamc@186 110 let
adamc@186 111 val (arg, sm) =
adamc@186 112 case arg of
adamc@186 113 NONE => (NONE, sm)
adamc@186 114 | SOME t =>
adamc@186 115 let
adamc@186 116 val (t, sm) = cifyTyp (t, sm)
adamc@186 117 in
adamc@186 118 (SOME t, sm)
adamc@186 119 end
adamc@186 120 in
adamc@186 121 (L'.PConFfi {mod = m, datatyp = datatyp, con = con, arg = arg}, sm)
adamc@186 122 end
adamc@181 123
adamc@182 124 fun cifyPat ((p, loc), sm) =
adamc@181 125 case p of
adamc@182 126 L.PWild => ((L'.PWild, loc), sm)
adamc@182 127 | L.PVar (x, t) =>
adamc@182 128 let
adamc@182 129 val (t, sm) = cifyTyp (t, sm)
adamc@182 130 in
adamc@182 131 ((L'.PVar (x, t), loc), sm)
adamc@182 132 end
adamc@182 133 | L.PPrim p => ((L'.PPrim p, loc), sm)
adamc@188 134 | L.PCon (dk, pc, NONE) =>
adamc@186 135 let
adamc@186 136 val (pc, sm) = cifyPatCon (pc, sm)
adamc@186 137 in
adamc@188 138 ((L'.PCon (dk, pc, NONE), loc), sm)
adamc@186 139 end
adamc@188 140 | L.PCon (dk, pc, SOME p) =>
adamc@182 141 let
adamc@186 142 val (pc, sm) = cifyPatCon (pc, sm)
adamc@182 143 val (p, sm) = cifyPat (p, sm)
adamc@182 144 in
adamc@188 145 ((L'.PCon (dk, pc, SOME p), loc), sm)
adamc@182 146 end
adamc@182 147 | L.PRecord xps =>
adamc@182 148 let
adamc@182 149 val (xps, sm) = ListUtil.foldlMap (fn ((x, p, t), sm) =>
adamc@182 150 let
adamc@182 151 val (p, sm) = cifyPat (p, sm)
adamc@182 152 val (t, sm) = cifyTyp (t, sm)
adamc@182 153 in
adamc@182 154 ((x, p, t), sm)
adamc@182 155 end) sm xps
adamc@182 156 in
adamc@182 157 ((L'.PRecord xps, loc), sm)
adamc@182 158 end
adamc@181 159
adamc@29 160 fun cifyExp ((e, loc), sm) =
adamc@29 161 case e of
adamc@29 162 L.EPrim p => ((L'.EPrim p, loc), sm)
adamc@29 163 | L.ERel n => ((L'.ERel n, loc), sm)
adamc@29 164 | L.ENamed n => ((L'.ENamed n, loc), sm)
adamc@188 165 | L.ECon (dk, pc, eo) =>
adamc@181 166 let
adamc@181 167 val (eo, sm) =
adamc@181 168 case eo of
adamc@181 169 NONE => (NONE, sm)
adamc@181 170 | SOME e =>
adamc@181 171 let
adamc@181 172 val (e, sm) = cifyExp (e, sm)
adamc@181 173 in
adamc@181 174 (SOME e, sm)
adamc@181 175 end
adamc@186 176 val (pc, sm) = cifyPatCon (pc, sm)
adamc@181 177 in
adamc@188 178 ((L'.ECon (dk, pc, eo), loc), sm)
adamc@181 179 end
adamc@53 180 | L.EFfi mx => ((L'.EFfi mx, loc), sm)
adamc@53 181 | L.EFfiApp (m, x, es) =>
adamc@53 182 let
adamc@53 183 val (es, sm) = ListUtil.foldlMap cifyExp sm es
adamc@53 184 in
adamc@53 185 ((L'.EFfiApp (m, x, es), loc), sm)
adamc@53 186 end
adamc@29 187 | L.EApp (e1, e2) =>
adamc@29 188 let
adamc@29 189 val (e1, sm) = cifyExp (e1, sm)
adamc@29 190 val (e2, sm) = cifyExp (e2, sm)
adamc@29 191 in
adamc@29 192 ((L'.EApp (e1, e2), loc), sm)
adamc@29 193 end
adamc@109 194 | L.EAbs _ => (ErrorMsg.errorAt loc "Anonymous function remains at code generation";
adamc@109 195 (dummye, sm))
adamc@29 196
adamc@29 197 | L.ERecord xes =>
adamc@29 198 let
adamc@29 199 val old_xts = map (fn (x, _, t) => (x, t)) xes
adamc@29 200
adamc@29 201 val (xets, sm) = ListUtil.foldlMap (fn ((x, e, t), sm) =>
adamc@29 202 let
adamc@29 203 val (e, sm) = cifyExp (e, sm)
adamc@29 204 val (t, sm) = cifyTyp (t, sm)
adamc@29 205 in
adamc@29 206 ((x, e, t), sm)
adamc@29 207 end)
adamc@29 208 sm xes
adamc@29 209
adamc@29 210 val (sm, si) = Sm.find (sm, old_xts, map (fn (x, _, t) => (x, t)) xets)
adamc@29 211
adamc@29 212 val xes = map (fn (x, e, _) => (x, e)) xets
adamc@29 213 val xes = ListMergeSort.sort (fn ((x1, _), (x2, _)) => String.compare (x1, x2) = GREATER) xes
adamc@29 214 in
adamc@29 215 ((L'.ERecord (si, xes), loc), sm)
adamc@29 216 end
adamc@29 217 | L.EField (e, x) =>
adamc@29 218 let
adamc@29 219 val (e, sm) = cifyExp (e, sm)
adamc@29 220 in
adamc@29 221 ((L'.EField (e, x), loc), sm)
adamc@29 222 end
adamc@29 223
adamc@182 224 | L.ECase (e, pes, {disc, result}) =>
adamc@181 225 let
adamc@181 226 val (e, sm) = cifyExp (e, sm)
adamc@181 227 val (pes, sm) = ListUtil.foldlMap
adamc@181 228 (fn ((p, e), sm) =>
adamc@181 229 let
adamc@181 230 val (e, sm) = cifyExp (e, sm)
adamc@182 231 val (p, sm) = cifyPat (p, sm)
adamc@181 232 in
adamc@182 233 ((p, e), sm)
adamc@181 234 end) sm pes
adamc@182 235 val (disc, sm) = cifyTyp (disc, sm)
adamc@182 236 val (result, sm) = cifyTyp (result, sm)
adamc@181 237 in
adamc@182 238 ((L'.ECase (e, pes, {disc = disc, result = result}), loc), sm)
adamc@181 239 end
adamc@178 240
adamc@180 241 | L.EStrcat (e1, e2) =>
adamc@180 242 let
adamc@180 243 val (e1, sm) = cifyExp (e1, sm)
adamc@180 244 val (e2, sm) = cifyExp (e2, sm)
adamc@180 245 in
adamc@180 246 ((L'.EFfiApp ("Basis", "strcat", [e1, e2]), loc), sm)
adamc@180 247 end
adamc@102 248
adamc@102 249 | L.EWrite e =>
adamc@102 250 let
adamc@102 251 val (e, sm) = cifyExp (e, sm)
adamc@102 252 in
adamc@102 253 ((L'.EWrite e, loc), sm)
adamc@102 254 end
adamc@102 255
adamc@106 256 | L.ESeq (e1, e2) =>
adamc@106 257 let
adamc@106 258 val (e1, sm) = cifyExp (e1, sm)
adamc@106 259 val (e2, sm) = cifyExp (e2, sm)
adamc@106 260 in
adamc@106 261 ((L'.ESeq (e1, e2), loc), sm)
adamc@106 262 end
adamc@106 263
adamc@111 264 | L.EClosure _ => (ErrorMsg.errorAt loc "Nested closure remains in code generation";
adamc@111 265 (dummye, sm))
adamc@111 266
adamc@29 267 fun cifyDecl ((d, loc), sm) =
adamc@29 268 case d of
adamc@165 269 L.DDatatype (x, n, xncs) =>
adamc@165 270 let
adamc@188 271 val dk = MonoUtil.classifyDatatype xncs
adamc@165 272 val (xncs, sm) = ListUtil.foldlMap (fn ((x, n, to), sm) =>
adamc@165 273 case to of
adamc@165 274 NONE => ((x, n, NONE), sm)
adamc@165 275 | SOME t =>
adamc@165 276 let
adamc@165 277 val (t, sm) = cifyTyp (t, sm)
adamc@165 278 in
adamc@165 279 ((x, n, SOME t), sm)
adamc@165 280 end) sm xncs
adamc@165 281 in
adamc@188 282 (SOME (L'.DDatatype (dk, x, n, xncs), loc), NONE, sm)
adamc@165 283 end
adamc@164 284
adamc@164 285 | L.DVal (x, n, t, e, _) =>
adamc@29 286 let
adamc@29 287 val (t, sm) = cifyTyp (t, sm)
adamc@109 288
adamc@109 289 val (d, sm) = case #1 t of
adamc@121 290 L'.TFun _ =>
adamc@121 291 let
adamc@121 292 fun unravel (tAll as (t, _), eAll as (e, _)) =
adamc@121 293 case (t, e) of
adamc@121 294 (L'.TFun (dom, ran), L.EAbs (ax, _, _, e)) =>
adamc@121 295 let
adamc@121 296 val (args, t, e) = unravel (ran, e)
adamc@121 297 in
adamc@121 298 ((ax, dom) :: args, t, e)
adamc@121 299 end
adamc@121 300 | (L'.TFun _, _) =>
adamc@121 301 (ErrorMsg.errorAt loc "Function isn't explicit at code generation";
adamc@121 302 ([], tAll, eAll))
adamc@121 303 | _ => ([], tAll, eAll)
adamc@121 304
adamc@121 305 val (args, ran, e) = unravel (t, e)
adamc@121 306 val (e, sm) = cifyExp (e, sm)
adamc@121 307 in
adamc@121 308 (L'.DFun (x, n, args, ran, e), sm)
adamc@121 309 end
adamc@121 310
adamc@109 311 | _ =>
adamc@109 312 let
adamc@109 313 val (e, sm) = cifyExp (e, sm)
adamc@109 314 in
adamc@109 315 (L'.DVal (x, n, t, e), sm)
adamc@109 316 end
adamc@29 317 in
adamc@109 318 (SOME (d, loc), NONE, sm)
adamc@29 319 end
adamc@129 320 | L.DValRec vis =>
adamc@129 321 let
adamc@129 322 val (vis, sm) = ListUtil.foldlMap
adamc@129 323 (fn ((x, n, t, e, _), sm) =>
adamc@129 324 let
adamc@129 325 val (t, sm) = cifyTyp (t, sm)
adamc@129 326
adamc@129 327 fun unravel (tAll as (t, _), eAll as (e, _)) =
adamc@129 328 case (t, e) of
adamc@129 329 (L'.TFun (dom, ran), L.EAbs (ax, _, _, e)) =>
adamc@129 330 let
adamc@129 331 val (args, t, e) = unravel (ran, e)
adamc@129 332 in
adamc@129 333 ((ax, dom) :: args, t, e)
adamc@129 334 end
adamc@129 335 | (L'.TFun _, _) =>
adamc@129 336 (ErrorMsg.errorAt loc "Function isn't explicit at code generation";
adamc@129 337 ([], tAll, eAll))
adamc@129 338 | _ => ([], tAll, eAll)
adamc@129 339
adamc@129 340 val (args, ran, e) = unravel (t, e)
adamc@129 341 val (e, sm) = cifyExp (e, sm)
adamc@129 342 in
adamc@129 343 ((x, n, args, ran, e), sm)
adamc@129 344 end)
adamc@129 345 sm vis
adamc@129 346 in
adamc@129 347 (SOME (L'.DFunRec vis, loc), NONE, sm)
adamc@129 348 end
adamc@129 349
adamc@144 350 | L.DExport (ek, s, n, ts) =>
adamc@120 351 let
adamc@120 352 val (ts, sm) = ListUtil.foldlMap cifyTyp sm ts
adamc@120 353 in
adamc@144 354 (NONE, SOME (ek, "/" ^ s, n, ts), sm)
adamc@120 355 end
adamc@29 356
adamc@29 357 fun cjrize ds =
adamc@29 358 let
adamc@101 359 val (ds, ps, sm) = foldl (fn (d, (ds, ps, sm)) =>
adamc@101 360 let
adamc@101 361 val (dop, pop, sm) = cifyDecl (d, sm)
adamc@101 362 val ds = case dop of
adamc@101 363 NONE => ds
adamc@101 364 | SOME d => d :: ds
adamc@101 365 val ps = case pop of
adamc@101 366 NONE => ps
adamc@101 367 | SOME p => p :: ps
adamc@101 368 in
adamc@101 369 (ds, ps, sm)
adamc@101 370 end)
adamc@101 371 ([], [], Sm.empty) ds
adamc@29 372 in
adamc@101 373 (List.revAppend (map (fn v => (L'.DStruct v, ErrorMsg.dummySpan)) (Sm.declares sm),
adamc@101 374 rev ds),
adamc@101 375 ps)
adamc@29 376 end
adamc@29 377
adamc@29 378 end