Mercurial > urweb

annotate src/reduce.sml @ 417:e0e9e9eca1cb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix nasty de Bruijn substitution bug; TcSum demo
author Adam Chlipala <adamc@hcoop.net>
date Thu, 23 Oct 2008 12:58:35 -0400
parents 075b36dbb1a4
children bd9ee9aeca2f
rev   line source
adamc@20 1 (* Copyright (c) 2008, Adam Chlipala
adamc@20 2 * All rights reserved.
adamc@20 3 *
adamc@20 4 * Redistribution and use in source and binary forms, with or without
adamc@20 5 * modification, are permitted provided that the following conditions are met:
adamc@20 6 *
adamc@20 7 * - Redistributions of source code must retain the above copyright notice,
adamc@20 8 * this list of conditions and the following disclaimer.
adamc@20 9 * - Redistributions in binary form must reproduce the above copyright notice,
adamc@20 10 * this list of conditions and the following disclaimer in the documentation
adamc@20 11 * and/or other materials provided with the distribution.
adamc@20 12 * - The names of contributors may not be used to endorse or promote products
adamc@20 13 * derived from this software without specific prior written permission.
adamc@20 14 *
adamc@20 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@20 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@20 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@20 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@20 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
adamc@20 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@20 21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@20 22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@20 23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@20 24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@20 25 * POSSIBILITY OF SUCH DAMAGE.
adamc@20 26 *)
adamc@20 27
adamc@20 28 (* Simplify a Core program algebraically *)
adamc@20 29
adamc@20 30 structure Reduce :> REDUCE = struct
adamc@20 31
adamc@20 32 open Core
adamc@20 33
adamc@20 34 structure E = CoreEnv
adamc@20 35 structure U = CoreUtil
adamc@20 36
adamc@20 37 val liftConInCon = E.liftConInCon
adamc@193 38 val subConInCon = E.subConInCon
adamc@417 39 val liftConInExp = E.liftConInExp
adamc@20 40
adamc@21 41 val liftExpInExp =
adamc@21 42 U.Exp.mapB {kind = fn k => k,
adamc@21 43 con = fn _ => fn c => c,
adamc@21 44 exp = fn bound => fn e =>
adamc@21 45 case e of
adamc@21 46 ERel xn =>
adamc@21 47 if xn < bound then
adamc@21 48 e
adamc@21 49 else
adamc@21 50 ERel (xn + 1)
adamc@21 51 | _ => e,
adamc@21 52 bind = fn (bound, U.Exp.RelE _) => bound + 1
adamc@21 53 | (bound, _) => bound}
adamc@21 54
adamc@21 55 val subExpInExp =
adamc@21 56 U.Exp.mapB {kind = fn k => k,
adamc@21 57 con = fn _ => fn c => c,
adamc@21 58 exp = fn (xn, rep) => fn e =>
adamc@21 59 case e of
adamc@21 60 ERel xn' =>
adamc@74 61 (case Int.compare (xn', xn) of
adamc@74 62 EQUAL => #1 rep
adamc@74 63 | GREATER=> ERel (xn' - 1)
adamc@74 64 | LESS => e)
adamc@21 65 | _ => e,
adamc@21 66 bind = fn ((xn, rep), U.Exp.RelE _) => (xn+1, liftExpInExp 0 rep)
adamc@417 67 | ((xn, rep), U.Exp.RelC _) => (xn, liftConInExp 0 rep)
adamc@21 68 | (ctx, _) => ctx}
adamc@21 69
adamc@315 70 val liftConInExp = E.liftConInExp
adamc@315 71 val subConInExp = E.subConInExp
adamc@21 72
adamc@20 73 fun bindC (env, b) =
adamc@20 74 case b of
adamc@20 75 U.Con.Rel (x, k) => E.pushCRel env x k
adamc@20 76 | U.Con.Named (x, n, k, co) => E.pushCNamed env x n k co
adamc@20 77
adamc@20 78 fun bind (env, b) =
adamc@20 79 case b of
adamc@20 80 U.Decl.RelC (x, k) => E.pushCRel env x k
adamc@20 81 | U.Decl.NamedC (x, n, k, co) => E.pushCNamed env x n k co
adamc@20 82 | U.Decl.RelE (x, t) => E.pushERel env x t
adamc@109 83 | U.Decl.NamedE (x, n, t, eo, s) => E.pushENamed env x n t eo s
adamc@20 84
adamc@20 85 fun kind k = k
adamc@20 86
adamc@20 87 fun con env c =
adamc@20 88 case c of
adamc@70 89 CApp ((CApp ((CApp ((CFold ks, _), f), _), i), loc), (CRecord (k, xcs), _)) =>
adamc@70 90 (case xcs of
adamc@70 91 [] => #1 i
adamc@70 92 | (n, v) :: rest =>
adamc@70 93 #1 (reduceCon env (CApp ((CApp ((CApp (f, n), loc), v), loc),
adamc@70 94 (CApp ((CApp ((CApp ((CFold ks, loc), f), loc), i), loc),
adamc@70 95 (CRecord (k, rest), loc)), loc)), loc)))
adamc@70 96 | CApp ((CAbs (_, _, c1), loc), c2) =>
adamc@20 97 #1 (reduceCon env (subConInCon (0, c2) c1))
adamc@20 98 | CNamed n =>
adamc@20 99 (case E.lookupCNamed env n of
adamc@20 100 (_, _, SOME c') => #1 c'
adamc@20 101 | _ => c)
adamc@20 102 | CConcat ((CRecord (k, xcs1), loc), (CRecord (_, xcs2), _)) => CRecord (k, xcs1 @ xcs2)
adamc@215 103
adamc@215 104 | CProj ((CTuple cs, _), n) => #1 (List.nth (cs, n - 1))
adamc@215 105
adamc@20 106 | _ => c
adamc@20 107
adamc@20 108 and reduceCon env = U.Con.mapB {kind = kind, con = con, bind = bindC} env
adamc@20 109
adamc@21 110 fun exp env e =
adamc@417 111 let
adamc@417 112 (*val () = Print.prefaces "exp" [("e", CorePrint.p_exp env (e, ErrorMsg.dummySpan))]*)
adamc@21 113
adamc@417 114 val r = case e of
adamc@417 115 ENamed n =>
adamc@417 116 (case E.lookupENamed env n of
adamc@417 117 (_, _, SOME e', _) => #1 e'
adamc@417 118 | _ => e)
adamc@74 119
adamc@417 120 | ECApp ((EApp ((EApp ((ECApp ((EFold ks, _), ran), _), f), _), i), _), (CRecord (k, xcs), loc)) =>
adamc@417 121 (case xcs of
adamc@417 122 [] => #1 i
adamc@417 123 | (n, v) :: rest =>
adamc@417 124 #1 (reduceExp env (EApp ((ECApp ((ECApp ((ECApp (f, n), loc), v), loc), (CRecord (k, rest), loc)), loc),
adamc@417 125 (ECApp ((EApp ((EApp ((ECApp ((EFold ks, loc), ran), loc), f), loc), i), loc),
adamc@417 126 (CRecord (k, rest), loc)), loc)), loc)))
adamc@21 127
adamc@417 128 | EApp ((EAbs (_, _, _, e1), loc), e2) =>
adamc@417 129 #1 (reduceExp env (subExpInExp (0, e2) e1))
adamc@417 130 | ECApp ((ECAbs (_, _, e1), loc), c) =>
adamc@417 131 #1 (reduceExp env (subConInExp (0, c) e1))
adamc@22 132
adamc@417 133 | EField ((ERecord xes, _), (CName x, _), _) =>
adamc@417 134 (case List.find (fn ((CName x', _), _, _) => x' = x
adamc@417 135 | _ => false) xes of
adamc@417 136 SOME (_, e, _) => #1 e
adamc@417 137 | NONE => e)
adamc@417 138 | EWith (r as (_, loc), x, e, {rest = (CRecord (k, xts), _), field}) =>
adamc@417 139 let
adamc@417 140 fun fields (remaining, passed) =
adamc@417 141 case remaining of
adamc@417 142 [] => []
adamc@417 143 | (x, t) :: rest =>
adamc@417 144 (x,
adamc@417 145 (EField (r, x, {field = t,
adamc@417 146 rest = (CRecord (k, List.revAppend (passed, rest)), loc)}), loc),
adamc@417 147 t) :: fields (rest, (x, t) :: passed)
adamc@417 148 in
adamc@417 149 #1 (reduceExp env (ERecord ((x, e, field) :: fields (xts, [])), loc))
adamc@417 150 end
adamc@417 151 | ECut (r as (_, loc), _, {rest = (CRecord (k, xts), _), ...}) =>
adamc@417 152 let
adamc@417 153 fun fields (remaining, passed) =
adamc@417 154 case remaining of
adamc@417 155 [] => []
adamc@417 156 | (x, t) :: rest =>
adamc@417 157 (x,
adamc@417 158 (EField (r, x, {field = t,
adamc@417 159 rest = (CRecord (k, List.revAppend (passed, rest)), loc)}), loc),
adamc@417 160 t) :: fields (rest, (x, t) :: passed)
adamc@417 161 in
adamc@417 162 #1 (reduceExp env (ERecord (fields (xts, [])), loc))
adamc@417 163 end
adamc@417 164
adamc@417 165 | _ => e
adamc@417 166 in
adamc@417 167 (*Print.prefaces "exp'" [("e", CorePrint.p_exp env (e, ErrorMsg.dummySpan)),
adamc@417 168 ("r", CorePrint.p_exp env (r, ErrorMsg.dummySpan))];*)
adamc@417 169
adamc@417 170 r
adamc@417 171 end
adamc@21 172
adamc@21 173 and reduceExp env = U.Exp.mapB {kind = kind, con = con, exp = exp, bind = bind} env
adamc@20 174
adamc@330 175 fun decl env d =
adamc@330 176 case d of
adamc@330 177 DValRec [vi as (_, n, _, e, _)] =>
adamc@330 178 let
adamc@330 179 fun kind _ = false
adamc@330 180 fun con _ = false
adamc@330 181 fun exp e =
adamc@330 182 case e of
adamc@330 183 ENamed n' => n' = n
adamc@330 184 | _ => false
adamc@330 185 in
adamc@330 186 if U.Exp.exists {kind = kind, con = con, exp = exp} e then
adamc@330 187 d
adamc@330 188 else
adamc@330 189 DVal vi
adamc@330 190 end
adamc@330 191 | _ => d
adamc@20 192
adamc@133 193 val reduce = U.File.mapB {kind = kind, con = con, exp = exp, decl = decl, bind = bind} E.empty
adamc@20 194
adamc@20 195 end