Mercurial > urweb

annotate src/cjrize.sml @ 252:7e9bd70ad3ce

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Monoized and optimized initial query test
author Adam Chlipala <adamc@hcoop.net>
date Sun, 31 Aug 2008 13:58:47 -0400
parents 326fb4686f60
children fac9fae654e2
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@196 33 structure IM = IntBinaryMap
adamc@196 34
adamc@29 35 structure Sm :> sig
adamc@29 36 type t
adamc@29 37
adamc@29 38 val empty : t
adamc@29 39 val find : t * (string * L.typ) list * (string * L'.typ) list -> t * int
adamc@29 40
adamc@29 41 val declares : t -> (int * (string * L'.typ) list) list
adamc@29 42 end = struct
adamc@29 43
adamc@29 44 structure FM = BinaryMapFn(struct
adamc@29 45 type ord_key = L.typ
adamc@109 46 val compare = MonoUtil.Typ.compare
adamc@29 47 end)
adamc@29 48
adamc@29 49 type t = int * int FM.map * (int * (string * L'.typ) list) list
adamc@29 50
adamc@102 51 val empty : t = (1, FM.insert (FM.empty, (L.TRecord [], ErrorMsg.dummySpan), 0), [])
adamc@29 52
adamc@29 53 fun find ((n, m, ds), xts, xts') =
adamc@29 54 let
adamc@29 55 val t = (L.TRecord xts, ErrorMsg.dummySpan)
adamc@29 56 in
adamc@29 57 case FM.find (m, t) of
adamc@29 58 NONE => ((n+1, FM.insert (m, t, n), (n, xts') :: ds), n)
adamc@29 59 | SOME i => ((n, m, ds), i)
adamc@29 60 end
adamc@29 61
adamc@29 62 fun declares (_, _, ds) = ds
adamc@29 63
adamc@29 64 end
adamc@29 65
adamc@196 66 fun cifyTyp x =
adamc@196 67 let
adamc@196 68 fun cify dtmap ((t, loc), sm) =
adamc@196 69 case t of
adamc@196 70 L.TFun (t1, t2) =>
adamc@196 71 let
adamc@196 72 val (t1, sm) = cify dtmap (t1, sm)
adamc@196 73 val (t2, sm) = cify dtmap (t2, sm)
adamc@196 74 in
adamc@196 75 ((L'.TFun (t1, t2), loc), sm)
adamc@196 76 end
adamc@196 77 | L.TRecord xts =>
adamc@196 78 let
adamc@196 79 val old_xts = xts
adamc@196 80 val (xts, sm) = ListUtil.foldlMap (fn ((x, t), sm) =>
adamc@196 81 let
adamc@196 82 val (t, sm) = cify dtmap (t, sm)
adamc@196 83 in
adamc@196 84 ((x, t), sm)
adamc@196 85 end)
adamc@196 86 sm xts
adamc@196 87 val (sm, si) = Sm.find (sm, old_xts, xts)
adamc@196 88 in
adamc@196 89 ((L'.TRecord si, loc), sm)
adamc@196 90 end
adamc@196 91 | L.TDatatype (n, ref (dk, xncs)) =>
adamc@196 92 (case IM.find (dtmap, n) of
adamc@196 93 SOME r => ((L'.TDatatype (dk, n, r), loc), sm)
adamc@196 94 | NONE =>
adamc@196 95 let
adamc@196 96 val r = ref []
adamc@196 97 val dtmap = IM.insert (dtmap, n, r)
adamc@196 98
adamc@196 99 val (xncs, sm) = ListUtil.foldlMap (fn ((x, n, to), sm) =>
adamc@196 100 case to of
adamc@196 101 NONE => ((x, n, NONE), sm)
adamc@196 102 | SOME t =>
adamc@196 103 let
adamc@196 104 val (t, sm) = cify dtmap (t, sm)
adamc@196 105 in
adamc@196 106 ((x, n, SOME t), sm)
adamc@196 107 end)
adamc@196 108 sm xncs
adamc@196 109 in
adamc@196 110 r := xncs;
adamc@196 111 ((L'.TDatatype (dk, n, r), loc), sm)
adamc@196 112 end)
adamc@196 113 | L.TFfi mx => ((L'.TFfi mx, loc), sm)
adamc@196 114 in
adamc@196 115 cify IM.empty x
adamc@196 116 end
adamc@29 117
adamc@109 118 val dummye = (L'.EPrim (Prim.Int 0), ErrorMsg.dummySpan)
adamc@109 119
adamc@186 120 fun cifyPatCon (pc, sm) =
adamc@181 121 case pc of
adamc@186 122 L.PConVar n => (L'.PConVar n, sm)
adamc@186 123 | L.PConFfi {mod = m, datatyp, con, arg} =>
adamc@186 124 let
adamc@186 125 val (arg, sm) =
adamc@186 126 case arg of
adamc@186 127 NONE => (NONE, sm)
adamc@186 128 | SOME t =>
adamc@186 129 let
adamc@186 130 val (t, sm) = cifyTyp (t, sm)
adamc@186 131 in
adamc@186 132 (SOME t, sm)
adamc@186 133 end
adamc@186 134 in
adamc@186 135 (L'.PConFfi {mod = m, datatyp = datatyp, con = con, arg = arg}, sm)
adamc@186 136 end
adamc@181 137
adamc@182 138 fun cifyPat ((p, loc), sm) =
adamc@181 139 case p of
adamc@182 140 L.PWild => ((L'.PWild, loc), sm)
adamc@182 141 | L.PVar (x, t) =>
adamc@182 142 let
adamc@182 143 val (t, sm) = cifyTyp (t, sm)
adamc@182 144 in
adamc@182 145 ((L'.PVar (x, t), loc), sm)
adamc@182 146 end
adamc@182 147 | L.PPrim p => ((L'.PPrim p, loc), sm)
adamc@188 148 | L.PCon (dk, pc, NONE) =>
adamc@186 149 let
adamc@186 150 val (pc, sm) = cifyPatCon (pc, sm)
adamc@186 151 in
adamc@188 152 ((L'.PCon (dk, pc, NONE), loc), sm)
adamc@186 153 end
adamc@188 154 | L.PCon (dk, pc, SOME p) =>
adamc@182 155 let
adamc@186 156 val (pc, sm) = cifyPatCon (pc, sm)
adamc@182 157 val (p, sm) = cifyPat (p, sm)
adamc@182 158 in
adamc@188 159 ((L'.PCon (dk, pc, SOME p), loc), sm)
adamc@182 160 end
adamc@182 161 | L.PRecord xps =>
adamc@182 162 let
adamc@182 163 val (xps, sm) = ListUtil.foldlMap (fn ((x, p, t), sm) =>
adamc@182 164 let
adamc@182 165 val (p, sm) = cifyPat (p, sm)
adamc@182 166 val (t, sm) = cifyTyp (t, sm)
adamc@182 167 in
adamc@182 168 ((x, p, t), sm)
adamc@182 169 end) sm xps
adamc@182 170 in
adamc@182 171 ((L'.PRecord xps, loc), sm)
adamc@182 172 end
adamc@181 173
adamc@29 174 fun cifyExp ((e, loc), sm) =
adamc@29 175 case e of
adamc@29 176 L.EPrim p => ((L'.EPrim p, loc), sm)
adamc@29 177 | L.ERel n => ((L'.ERel n, loc), sm)
adamc@29 178 | L.ENamed n => ((L'.ENamed n, loc), sm)
adamc@188 179 | L.ECon (dk, pc, eo) =>
adamc@181 180 let
adamc@181 181 val (eo, sm) =
adamc@181 182 case eo of
adamc@181 183 NONE => (NONE, sm)
adamc@181 184 | SOME e =>
adamc@181 185 let
adamc@181 186 val (e, sm) = cifyExp (e, sm)
adamc@181 187 in
adamc@181 188 (SOME e, sm)
adamc@181 189 end
adamc@186 190 val (pc, sm) = cifyPatCon (pc, sm)
adamc@181 191 in
adamc@188 192 ((L'.ECon (dk, pc, eo), loc), sm)
adamc@181 193 end
adamc@53 194 | L.EFfi mx => ((L'.EFfi mx, loc), sm)
adamc@53 195 | L.EFfiApp (m, x, es) =>
adamc@53 196 let
adamc@53 197 val (es, sm) = ListUtil.foldlMap cifyExp sm es
adamc@53 198 in
adamc@53 199 ((L'.EFfiApp (m, x, es), loc), sm)
adamc@53 200 end
adamc@29 201 | L.EApp (e1, e2) =>
adamc@29 202 let
adamc@29 203 val (e1, sm) = cifyExp (e1, sm)
adamc@29 204 val (e2, sm) = cifyExp (e2, sm)
adamc@29 205 in
adamc@29 206 ((L'.EApp (e1, e2), loc), sm)
adamc@29 207 end
adamc@109 208 | L.EAbs _ => (ErrorMsg.errorAt loc "Anonymous function remains at code generation";
adamc@109 209 (dummye, sm))
adamc@29 210
adamc@29 211 | L.ERecord xes =>
adamc@29 212 let
adamc@29 213 val old_xts = map (fn (x, _, t) => (x, t)) xes
adamc@29 214
adamc@29 215 val (xets, sm) = ListUtil.foldlMap (fn ((x, e, t), sm) =>
adamc@29 216 let
adamc@29 217 val (e, sm) = cifyExp (e, sm)
adamc@29 218 val (t, sm) = cifyTyp (t, sm)
adamc@29 219 in
adamc@29 220 ((x, e, t), sm)
adamc@29 221 end)
adamc@29 222 sm xes
adamc@29 223
adamc@29 224 val (sm, si) = Sm.find (sm, old_xts, map (fn (x, _, t) => (x, t)) xets)
adamc@29 225
adamc@29 226 val xes = map (fn (x, e, _) => (x, e)) xets
adamc@29 227 val xes = ListMergeSort.sort (fn ((x1, _), (x2, _)) => String.compare (x1, x2) = GREATER) xes
adamc@29 228 in
adamc@29 229 ((L'.ERecord (si, xes), loc), sm)
adamc@29 230 end
adamc@29 231 | L.EField (e, x) =>
adamc@29 232 let
adamc@29 233 val (e, sm) = cifyExp (e, sm)
adamc@29 234 in
adamc@29 235 ((L'.EField (e, x), loc), sm)
adamc@29 236 end
adamc@29 237
adamc@182 238 | L.ECase (e, pes, {disc, result}) =>
adamc@181 239 let
adamc@181 240 val (e, sm) = cifyExp (e, sm)
adamc@181 241 val (pes, sm) = ListUtil.foldlMap
adamc@181 242 (fn ((p, e), sm) =>
adamc@181 243 let
adamc@181 244 val (e, sm) = cifyExp (e, sm)
adamc@182 245 val (p, sm) = cifyPat (p, sm)
adamc@181 246 in
adamc@182 247 ((p, e), sm)
adamc@181 248 end) sm pes
adamc@182 249 val (disc, sm) = cifyTyp (disc, sm)
adamc@182 250 val (result, sm) = cifyTyp (result, sm)
adamc@181 251 in
adamc@182 252 ((L'.ECase (e, pes, {disc = disc, result = result}), loc), sm)
adamc@181 253 end
adamc@178 254
adamc@180 255 | L.EStrcat (e1, e2) =>
adamc@180 256 let
adamc@180 257 val (e1, sm) = cifyExp (e1, sm)
adamc@180 258 val (e2, sm) = cifyExp (e2, sm)
adamc@180 259 in
adamc@180 260 ((L'.EFfiApp ("Basis", "strcat", [e1, e2]), loc), sm)
adamc@180 261 end
adamc@102 262
adamc@102 263 | L.EWrite e =>
adamc@102 264 let
adamc@102 265 val (e, sm) = cifyExp (e, sm)
adamc@102 266 in
adamc@102 267 ((L'.EWrite e, loc), sm)
adamc@102 268 end
adamc@102 269
adamc@106 270 | L.ESeq (e1, e2) =>
adamc@106 271 let
adamc@106 272 val (e1, sm) = cifyExp (e1, sm)
adamc@106 273 val (e2, sm) = cifyExp (e2, sm)
adamc@106 274 in
adamc@106 275 ((L'.ESeq (e1, e2), loc), sm)
adamc@106 276 end
adamc@106 277
adamc@251 278 | L.ELet _ => raise Fail "Cjrize ELet"
adamc@251 279
adamc@111 280 | L.EClosure _ => (ErrorMsg.errorAt loc "Nested closure remains in code generation";
adamc@111 281 (dummye, sm))
adamc@111 282
adamc@252 283 | L.EQuery _ => raise Fail "Cjrize EQuery"
adamc@252 284
adamc@29 285 fun cifyDecl ((d, loc), sm) =
adamc@29 286 case d of
adamc@165 287 L.DDatatype (x, n, xncs) =>
adamc@165 288 let
adamc@198 289 val dk = ElabUtil.classifyDatatype xncs
adamc@165 290 val (xncs, sm) = ListUtil.foldlMap (fn ((x, n, to), sm) =>
adamc@165 291 case to of
adamc@165 292 NONE => ((x, n, NONE), sm)
adamc@165 293 | SOME t =>
adamc@165 294 let
adamc@165 295 val (t, sm) = cifyTyp (t, sm)
adamc@165 296 in
adamc@165 297 ((x, n, SOME t), sm)
adamc@165 298 end) sm xncs
adamc@165 299 in
adamc@188 300 (SOME (L'.DDatatype (dk, x, n, xncs), loc), NONE, sm)
adamc@165 301 end
adamc@164 302
adamc@164 303 | L.DVal (x, n, t, e, _) =>
adamc@29 304 let
adamc@29 305 val (t, sm) = cifyTyp (t, sm)
adamc@109 306
adamc@109 307 val (d, sm) = case #1 t of
adamc@121 308 L'.TFun _ =>
adamc@121 309 let
adamc@121 310 fun unravel (tAll as (t, _), eAll as (e, _)) =
adamc@121 311 case (t, e) of
adamc@121 312 (L'.TFun (dom, ran), L.EAbs (ax, _, _, e)) =>
adamc@121 313 let
adamc@121 314 val (args, t, e) = unravel (ran, e)
adamc@121 315 in
adamc@121 316 ((ax, dom) :: args, t, e)
adamc@121 317 end
adamc@121 318 | (L'.TFun _, _) =>
adamc@121 319 (ErrorMsg.errorAt loc "Function isn't explicit at code generation";
adamc@121 320 ([], tAll, eAll))
adamc@121 321 | _ => ([], tAll, eAll)
adamc@121 322
adamc@121 323 val (args, ran, e) = unravel (t, e)
adamc@121 324 val (e, sm) = cifyExp (e, sm)
adamc@121 325 in
adamc@121 326 (L'.DFun (x, n, args, ran, e), sm)
adamc@121 327 end
adamc@121 328
adamc@109 329 | _ =>
adamc@109 330 let
adamc@109 331 val (e, sm) = cifyExp (e, sm)
adamc@109 332 in
adamc@109 333 (L'.DVal (x, n, t, e), sm)
adamc@109 334 end
adamc@29 335 in
adamc@109 336 (SOME (d, loc), NONE, sm)
adamc@29 337 end
adamc@129 338 | L.DValRec vis =>
adamc@129 339 let
adamc@129 340 val (vis, sm) = ListUtil.foldlMap
adamc@129 341 (fn ((x, n, t, e, _), sm) =>
adamc@129 342 let
adamc@129 343 val (t, sm) = cifyTyp (t, sm)
adamc@129 344
adamc@129 345 fun unravel (tAll as (t, _), eAll as (e, _)) =
adamc@129 346 case (t, e) of
adamc@129 347 (L'.TFun (dom, ran), L.EAbs (ax, _, _, e)) =>
adamc@129 348 let
adamc@129 349 val (args, t, e) = unravel (ran, e)
adamc@129 350 in
adamc@129 351 ((ax, dom) :: args, t, e)
adamc@129 352 end
adamc@129 353 | (L'.TFun _, _) =>
adamc@129 354 (ErrorMsg.errorAt loc "Function isn't explicit at code generation";
adamc@129 355 ([], tAll, eAll))
adamc@129 356 | _ => ([], tAll, eAll)
adamc@129 357
adamc@129 358 val (args, ran, e) = unravel (t, e)
adamc@129 359 val (e, sm) = cifyExp (e, sm)
adamc@129 360 in
adamc@129 361 ((x, n, args, ran, e), sm)
adamc@129 362 end)
adamc@129 363 sm vis
adamc@129 364 in
adamc@129 365 (SOME (L'.DFunRec vis, loc), NONE, sm)
adamc@129 366 end
adamc@129 367
adamc@144 368 | L.DExport (ek, s, n, ts) =>
adamc@120 369 let
adamc@120 370 val (ts, sm) = ListUtil.foldlMap cifyTyp sm ts
adamc@120 371 in
adamc@144 372 (NONE, SOME (ek, "/" ^ s, n, ts), sm)
adamc@120 373 end
adamc@29 374
adamc@29 375 fun cjrize ds =
adamc@29 376 let
adamc@196 377 val (dsF, ds, ps, sm) = foldl (fn (d, (dsF, ds, ps, sm)) =>
adamc@196 378 let
adamc@196 379 val (dop, pop, sm) = cifyDecl (d, sm)
adamc@196 380 val (dsF, ds) = case dop of
adamc@196 381 NONE => (dsF, ds)
adamc@196 382 | SOME (d as (L'.DDatatype (dk, x, n, _), loc)) =>
adamc@196 383 ((L'.DDatatypeForward (dk, x, n), loc) :: dsF,
adamc@196 384 d :: ds)
adamc@196 385 | SOME d => (dsF, d :: ds)
adamc@196 386 val ps = case pop of
adamc@196 387 NONE => ps
adamc@196 388 | SOME p => p :: ps
adamc@196 389 in
adamc@196 390 (dsF, ds, ps, sm)
adamc@196 391 end)
adamc@196 392 ([], [], [], Sm.empty) ds
adamc@29 393 in
adamc@196 394 (List.revAppend (dsF,
adamc@196 395 List.revAppend (map (fn v => (L'.DStruct v, ErrorMsg.dummySpan)) (Sm.declares sm),
adamc@196 396 rev ds)),
adamc@101 397 ps)
adamc@29 398 end
adamc@29 399
adamc@29 400 end