Mercurial > urweb

annotate src/especialize.sml @ 455:d4a81273d4b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Nested demo
author Adam Chlipala <adamc@hcoop.net>
date Tue, 04 Nov 2008 09:33:35 -0500
parents 787d4931fb07
children b393c2fc80f8
rev   line source
adamc@443 1 (* Copyright (c) 2008, Adam Chlipala
adamc@443 2 * All rights reserved.
adamc@443 3 *
adamc@443 4 * Redistribution and use in source and binary forms, with or without
adamc@443 5 * modification, are permitted provided that the following conditions are met:
adamc@443 6 *
adamc@443 7 * - Redistributions of source code must retain the above copyright notice,
adamc@443 8 * this list of conditions and the following disclaimer.
adamc@443 9 * - Redistributions in binary form must reproduce the above copyright notice,
adamc@443 10 * this list of conditions and the following disclaimer in the documentation
adamc@443 11 * and/or other materials provided with the distribution.
adamc@443 12 * - The names of contributors may not be used to endorse or promote products
adamc@443 13 * derived from this software without specific prior written permission.
adamc@443 14 *
adamc@443 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@443 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@443 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@443 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@443 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
adamc@443 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@443 21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@443 22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@443 23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@443 24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@443 25 * POSSIBILITY OF SUCH DAMAGE.
adamc@443 26 *)
adamc@443 27
adamc@443 28 structure ESpecialize :> ESPECIALIZE = struct
adamc@443 29
adamc@443 30 open Core
adamc@443 31
adamc@443 32 structure E = CoreEnv
adamc@443 33 structure U = CoreUtil
adamc@443 34
adamc@453 35 datatype skey =
adamc@453 36 Named of int
adamc@453 37 | App of skey * skey
adamc@453 38
adamc@453 39 structure K = struct
adamc@453 40 type ord_key = skey list
adamc@453 41 fun compare' (k1, k2) =
adamc@453 42 case (k1, k2) of
adamc@453 43 (Named n1, Named n2) => Int.compare (n1, n2)
adamc@453 44 | (Named _, _) => LESS
adamc@453 45 | (_, Named _) => GREATER
adamc@453 46
adamc@453 47 | (App (x1, y1), App (x2, y2)) => Order.join (compare' (x1, x2), fn () => compare' (y1, y2))
adamc@453 48
adamc@453 49 val compare = Order.joinL compare'
adamc@443 50 end
adamc@443 51
adamc@453 52 structure KM = BinaryMapFn(K)
adamc@443 53 structure IM = IntBinaryMap
adamc@443 54
adamc@453 55 fun skeyIn (e, _) =
adamc@453 56 case e of
adamc@453 57 ENamed n => SOME (Named n)
adamc@453 58 | EApp (e1, e2) =>
adamc@453 59 (case (skeyIn e1, skeyIn e2) of
adamc@453 60 (SOME k1, SOME k2) => SOME (App (k1, k2))
adamc@453 61 | _ => NONE)
adamc@453 62 | _ => NONE
adamc@453 63
adamc@453 64 fun skeyOut (k, loc) =
adamc@453 65 case k of
adamc@453 66 Named n => (ENamed n, loc)
adamc@453 67 | App (k1, k2) => (EApp (skeyOut (k1, loc), skeyOut (k2, loc)), loc)
adamc@453 68
adamc@443 69 type func = {
adamc@443 70 name : string,
adamc@453 71 args : int KM.map,
adamc@443 72 body : exp,
adamc@443 73 typ : con,
adamc@443 74 tag : string
adamc@443 75 }
adamc@443 76
adamc@443 77 type state = {
adamc@443 78 maxName : int,
adamc@443 79 funcs : func IM.map,
adamc@443 80 decls : (string * int * con * exp * string) list
adamc@443 81 }
adamc@443 82
adamc@443 83 fun kind (k, st) = (k, st)
adamc@443 84 fun con (c, st) = (c, st)
adamc@443 85
adamc@443 86 fun exp (e, st : state) =
adamc@443 87 let
adamc@443 88 fun getApp e =
adamc@443 89 case e of
adamc@443 90 ENamed f => SOME (f, [], [])
adamc@443 91 | EApp (e1, e2) =>
adamc@443 92 (case getApp (#1 e1) of
adamc@443 93 NONE => NONE
adamc@453 94 | SOME (f, xs, xs') =>
adamc@453 95 let
adamc@453 96 val k =
adamc@453 97 if List.null xs' then
adamc@453 98 skeyIn e2
adamc@453 99 else
adamc@453 100 NONE
adamc@453 101 in
adamc@453 102 case k of
adamc@453 103 NONE => SOME (f, xs, xs' @ [e2])
adamc@453 104 | SOME k => SOME (f, xs @ [k], xs')
adamc@453 105 end)
adamc@443 106 | _ => NONE
adamc@443 107 in
adamc@443 108 case getApp e of
adamc@443 109 NONE => (e, st)
adamc@443 110 | SOME (_, [], _) => (e, st)
adamc@443 111 | SOME (f, xs, xs') =>
adamc@443 112 case IM.find (#funcs st, f) of
adamc@453 113 NONE => ((*print "SHOT DOWN!\n";*) (e, st))
adamc@443 114 | SOME {name, args, body, typ, tag} =>
adamc@453 115 case KM.find (args, xs) of
adamc@453 116 SOME f' => ((*Print.prefaces "Pre-existing" [("e", CorePrint.p_exp CoreEnv.empty (e, ErrorMsg.dummySpan))];*)
adamc@453 117 (#1 (foldl (fn (e, arg) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@453 118 (ENamed f', ErrorMsg.dummySpan) xs'),
adamc@453 119 st))
adamc@443 120 | NONE =>
adamc@443 121 let
adamc@453 122 (*val () = Print.prefaces "New" [("e", CorePrint.p_exp CoreEnv.empty (e, ErrorMsg.dummySpan))]*)
adamc@453 123
adamc@443 124 fun subBody (body, typ, xs) =
adamc@443 125 case (#1 body, #1 typ, xs) of
adamc@443 126 (_, _, []) => SOME (body, typ)
adamc@443 127 | (EAbs (_, _, _, body'), TFun (_, typ'), x :: xs) =>
adamc@453 128 let
adamc@453 129 val body'' = E.subExpInExp (0, skeyOut (x, #2 body)) body'
adamc@453 130 in
adamc@453 131 (*Print.prefaces "espec" [("body'", CorePrint.p_exp CoreEnv.empty body'),
adamc@453 132 ("body''", CorePrint.p_exp CoreEnv.empty body'')];*)
adamc@453 133 subBody (body'',
adamc@453 134 typ',
adamc@453 135 xs)
adamc@453 136 end
adamc@443 137 | _ => NONE
adamc@443 138 in
adamc@443 139 case subBody (body, typ, xs) of
adamc@443 140 NONE => (e, st)
adamc@443 141 | SOME (body', typ') =>
adamc@443 142 let
adamc@443 143 val f' = #maxName st
adamc@453 144 (*val () = print ("f' = " ^ Int.toString f' ^ "\n")*)
adamc@443 145 val funcs = IM.insert (#funcs st, f, {name = name,
adamc@453 146 args = KM.insert (args, xs, f'),
adamc@443 147 body = body,
adamc@443 148 typ = typ,
adamc@443 149 tag = tag})
adamc@443 150 val st = {
adamc@443 151 maxName = f' + 1,
adamc@443 152 funcs = funcs,
adamc@443 153 decls = #decls st
adamc@443 154 }
adamc@443 155
adamc@443 156 val (body', st) = specExp st body'
adamc@443 157 val e' = foldl (fn (e, arg) => (EApp (e, arg), ErrorMsg.dummySpan))
adamc@443 158 (ENamed f', ErrorMsg.dummySpan) xs'
adamc@443 159 in
adamc@443 160 (#1 e',
adamc@443 161 {maxName = #maxName st,
adamc@443 162 funcs = #funcs st,
adamc@444 163 decls = (name, f', typ', body', tag) :: #decls st})
adamc@443 164 end
adamc@443 165 end
adamc@443 166 end
adamc@443 167
adamc@443 168 and specExp st = U.Exp.foldMap {kind = kind, con = con, exp = exp} st
adamc@443 169
adamc@443 170 fun decl (d, st) = (d, st)
adamc@443 171
adamc@443 172 val specDecl = U.Decl.foldMap {kind = kind, con = con, exp = exp, decl = decl}
adamc@443 173
adamc@453 174 fun specialize' file =
adamc@443 175 let
adamc@453 176 fun doDecl (d, (st : state, changed)) =
adamc@443 177 let
adamc@453 178 val funcs = #funcs st
adamc@453 179 val funcs =
adamc@453 180 case #1 d of
adamc@453 181 DValRec vis =>
adamc@453 182 foldl (fn ((x, n, c, e, tag), funcs) =>
adamc@453 183 IM.insert (funcs, n, {name = x,
adamc@453 184 args = KM.empty,
adamc@453 185 body = e,
adamc@453 186 typ = c,
adamc@453 187 tag = tag}))
adamc@453 188 funcs vis
adamc@453 189 | _ => funcs
adamc@453 190
adamc@453 191 val st = {maxName = #maxName st,
adamc@453 192 funcs = funcs,
adamc@453 193 decls = []}
adamc@453 194
adamc@443 195 val (d', st) = specDecl st d
adamc@443 196
adamc@443 197 val funcs = #funcs st
adamc@443 198 val funcs =
adamc@443 199 case #1 d of
adamc@443 200 DVal (x, n, c, e as (EAbs _, _), tag) =>
adamc@443 201 IM.insert (funcs, n, {name = x,
adamc@453 202 args = KM.empty,
adamc@443 203 body = e,
adamc@443 204 typ = c,
adamc@443 205 tag = tag})
adamc@443 206 | _ => funcs
adamc@443 207
adamc@453 208 val (changed, ds) =
adamc@443 209 case #decls st of
adamc@453 210 [] => (changed, [d'])
adamc@453 211 | vis =>
adamc@453 212 (true, case d' of
adamc@453 213 (DValRec vis', _) => [(DValRec (vis @ vis'), ErrorMsg.dummySpan)]
adamc@453 214 | _ => [(DValRec vis, ErrorMsg.dummySpan), d'])
adamc@443 215 in
adamc@453 216 (ds, ({maxName = #maxName st,
adamc@453 217 funcs = funcs,
adamc@453 218 decls = []}, changed))
adamc@443 219 end
adamc@443 220
adamc@453 221 val (ds, (_, changed)) = ListUtil.foldlMapConcat doDecl
adamc@453 222 ({maxName = U.File.maxName file + 1,
adamc@453 223 funcs = IM.empty,
adamc@453 224 decls = []}, false)
adamc@453 225 file
adamc@443 226 in
adamc@453 227 (changed, ds)
adamc@443 228 end
adamc@443 229
adamc@453 230 fun specialize file =
adamc@453 231 let
adamc@453 232 val (changed, file) = specialize' file
adamc@453 233 in
adamc@453 234 if changed then
adamc@453 235 specialize file
adamc@453 236 else
adamc@453 237 file
adamc@453 238 end
adamc@453 239
adamc@443 240
adamc@443 241 end