adamc@29: (* Copyright (c) 2008, Adam Chlipala
adamc@29:  * All rights reserved.
adamc@29:  *
adamc@29:  * Redistribution and use in source and binary forms, with or without
adamc@29:  * modification, are permitted provided that the following conditions are met:
adamc@29:  *
adamc@29:  * - Redistributions of source code must retain the above copyright notice,
adamc@29:  *   this list of conditions and the following disclaimer.
adamc@29:  * - Redistributions in binary form must reproduce the above copyright notice,
adamc@29:  *   this list of conditions and the following disclaimer in the documentation
adamc@29:  *   and/or other materials provided with the distribution.
adamc@29:  * - The names of contributors may not be used to endorse or promote products
adamc@29:  *   derived from this software without specific prior written permission.
adamc@29:  *
adamc@29:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@29:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@29:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@29:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@29:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
adamc@29:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@29:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@29:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@29:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@29:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@29:  * POSSIBILITY OF SUCH DAMAGE.
adamc@29:  *)
adamc@29: 
adamc@29: structure Cjrize :> CJRIZE = struct
adamc@29: 
adamc@109: structure L = Mono
adamc@29: structure L' = Cjr
adamc@29: 
adamc@196: structure IM = IntBinaryMap
adamc@196: 
adamc@29: structure Sm :> sig
adamc@29:     type t
adamc@29: 
adamc@29:     val empty : t
adamc@29:     val find : t * (string * L.typ) list * (string * L'.typ) list -> t * int
adamc@29: 
adamc@29:     val declares : t -> (int * (string * L'.typ) list) list
adamc@29: end = struct
adamc@29: 
adamc@29: structure FM = BinaryMapFn(struct
adamc@29:                            type ord_key = L.typ
adamc@109:                            val compare = MonoUtil.Typ.compare
adamc@29:                            end)
adamc@29: 
adamc@29: type t = int * int FM.map * (int * (string * L'.typ) list) list
adamc@29: 
adamc@102: val empty : t = (1, FM.insert (FM.empty, (L.TRecord [], ErrorMsg.dummySpan), 0), [])
adamc@29: 
adamc@29: fun find ((n, m, ds), xts, xts') =
adamc@29:     let
adamc@29:         val t = (L.TRecord xts, ErrorMsg.dummySpan)
adamc@29:     in
adamc@29:         case FM.find (m, t) of
adamc@29:             NONE => ((n+1, FM.insert (m, t, n), (n, xts') :: ds), n)
adamc@29:           | SOME i => ((n, m, ds), i)
adamc@29:     end
adamc@29: 
adamc@29: fun declares (_, _, ds) = ds
adamc@29: 
adamc@29: end
adamc@29: 
adamc@196: fun cifyTyp x =
adamc@196:     let
adamc@196:         fun cify dtmap ((t, loc), sm) =
adamc@196:             case t of
adamc@196:                 L.TFun (t1, t2) =>
adamc@196:                 let
adamc@196:                     val (t1, sm) = cify dtmap (t1, sm)
adamc@196:                     val (t2, sm) = cify dtmap (t2, sm)
adamc@196:                 in
adamc@196:                     ((L'.TFun (t1, t2), loc), sm)
adamc@196:                 end
adamc@196:               | L.TRecord xts =>
adamc@196:                 let
adamc@196:                     val old_xts = xts
adamc@196:                     val (xts, sm) = ListUtil.foldlMap (fn ((x, t), sm) =>
adamc@196:                                                           let
adamc@196:                                                               val (t, sm) = cify dtmap (t, sm)
adamc@196:                                                           in
adamc@196:                                                               ((x, t), sm)
adamc@196:                                                           end)
adamc@196:                                                       sm xts
adamc@196:                     val (sm, si) = Sm.find (sm, old_xts, xts)
adamc@196:                 in
adamc@196:                     ((L'.TRecord si, loc), sm)
adamc@196:                 end
adamc@196:               | L.TDatatype (n, ref (dk, xncs)) =>
adamc@196:                 (case IM.find (dtmap, n) of
adamc@196:                      SOME r => ((L'.TDatatype (dk, n, r), loc), sm)
adamc@196:                    | NONE =>
adamc@196:                      let
adamc@196:                          val r = ref []
adamc@196:                          val dtmap = IM.insert (dtmap, n, r)
adamc@196: 
adamc@196:                          val (xncs, sm) = ListUtil.foldlMap (fn ((x, n, to), sm) =>
adamc@196:                                                                 case to of
adamc@196:                                                                     NONE => ((x, n, NONE), sm)
adamc@196:                                                                   | SOME t =>
adamc@196:                                                                     let
adamc@196:                                                                         val (t, sm) = cify dtmap (t, sm)
adamc@196:                                                                     in
adamc@196:                                                                         ((x, n, SOME t), sm)
adamc@196:                                                                     end)
adamc@196:                                                             sm xncs
adamc@196:                      in
adamc@196:                          r := xncs;
adamc@196:                          ((L'.TDatatype (dk, n, r), loc), sm)
adamc@196:                      end)
adamc@196:               | L.TFfi mx => ((L'.TFfi mx, loc), sm)
adamc@196:     in
adamc@196:         cify IM.empty x
adamc@196:     end
adamc@29: 
adamc@109: val dummye = (L'.EPrim (Prim.Int 0), ErrorMsg.dummySpan)
adamc@109: 
adamc@186: fun cifyPatCon (pc, sm) =
adamc@181:     case pc of
adamc@186:         L.PConVar n => (L'.PConVar n, sm)
adamc@186:       | L.PConFfi {mod = m, datatyp, con, arg} =>
adamc@186:         let
adamc@186:             val (arg, sm) =
adamc@186:                 case arg of
adamc@186:                     NONE => (NONE, sm)
adamc@186:                   | SOME t =>
adamc@186:                     let
adamc@186:                         val (t, sm) = cifyTyp (t, sm)
adamc@186:                     in
adamc@186:                         (SOME t, sm)
adamc@186:                     end
adamc@186:         in
adamc@186:             (L'.PConFfi {mod = m, datatyp = datatyp, con = con, arg = arg}, sm)
adamc@186:         end
adamc@181: 
adamc@182: fun cifyPat ((p, loc), sm) =
adamc@181:     case p of
adamc@182:         L.PWild => ((L'.PWild, loc), sm)
adamc@182:       | L.PVar (x, t) =>
adamc@182:         let
adamc@182:             val (t, sm) = cifyTyp (t, sm)
adamc@182:         in
adamc@182:             ((L'.PVar (x, t), loc), sm)
adamc@182:         end
adamc@182:       | L.PPrim p => ((L'.PPrim p, loc), sm)
adamc@188:       | L.PCon (dk, pc, NONE) =>
adamc@186:         let
adamc@186:             val (pc, sm) = cifyPatCon (pc, sm)
adamc@186:         in
adamc@188:             ((L'.PCon (dk, pc, NONE), loc), sm)
adamc@186:         end
adamc@188:       | L.PCon (dk, pc, SOME p) =>
adamc@182:         let
adamc@186:             val (pc, sm) = cifyPatCon (pc, sm)
adamc@182:             val (p, sm) = cifyPat (p, sm)
adamc@182:         in
adamc@188:             ((L'.PCon (dk, pc, SOME p), loc), sm)
adamc@182:         end
adamc@182:       | L.PRecord xps =>
adamc@182:         let
adamc@182:             val (xps, sm) = ListUtil.foldlMap (fn ((x, p, t), sm) =>
adamc@182:                                                   let
adamc@182:                                                       val (p, sm) = cifyPat (p, sm)
adamc@182:                                                       val (t, sm) = cifyTyp (t, sm)
adamc@182:                                                   in
adamc@182:                                                       ((x, p, t), sm)
adamc@182:                                                   end) sm xps
adamc@182:         in
adamc@182:             ((L'.PRecord xps, loc), sm)
adamc@182:         end
adamc@181: 
adamc@29: fun cifyExp ((e, loc), sm) =
adamc@29:     case e of
adamc@29:         L.EPrim p => ((L'.EPrim p, loc), sm)
adamc@29:       | L.ERel n => ((L'.ERel n, loc), sm)
adamc@29:       | L.ENamed n => ((L'.ENamed n, loc), sm)
adamc@188:       | L.ECon (dk, pc, eo) =>
adamc@181:         let
adamc@181:             val (eo, sm) =
adamc@181:                 case eo of
adamc@181:                     NONE => (NONE, sm)
adamc@181:                   | SOME e =>
adamc@181:                     let
adamc@181:                         val (e, sm) = cifyExp (e, sm)
adamc@181:                     in
adamc@181:                         (SOME e, sm)
adamc@181:                     end
adamc@186:             val (pc, sm) = cifyPatCon (pc, sm)
adamc@181:         in
adamc@188:             ((L'.ECon (dk, pc, eo), loc), sm)
adamc@181:         end
adamc@53:       | L.EFfi mx => ((L'.EFfi mx, loc), sm)
adamc@53:       | L.EFfiApp (m, x, es) =>
adamc@53:         let
adamc@53:             val (es, sm) = ListUtil.foldlMap cifyExp sm es
adamc@53:         in
adamc@53:             ((L'.EFfiApp (m, x, es), loc), sm)
adamc@53:         end
adamc@29:       | L.EApp (e1, e2) =>
adamc@29:         let
adamc@29:             val (e1, sm) = cifyExp (e1, sm)
adamc@29:             val (e2, sm) = cifyExp (e2, sm)
adamc@29:         in
adamc@29:             ((L'.EApp (e1, e2), loc), sm)
adamc@29:         end
adamc@109:       | L.EAbs _ => (ErrorMsg.errorAt loc "Anonymous function remains at code generation";
adamc@109:                      (dummye, sm))
adamc@29: 
adamc@29:       | L.ERecord xes =>
adamc@29:         let
adamc@29:             val old_xts = map (fn (x, _, t) => (x, t)) xes
adamc@29: 
adamc@29:             val (xets, sm) = ListUtil.foldlMap (fn ((x, e, t), sm) =>
adamc@29:                                                   let
adamc@29:                                                       val (e, sm) = cifyExp (e, sm)
adamc@29:                                                       val (t, sm) = cifyTyp (t, sm)
adamc@29:                                                   in
adamc@29:                                                       ((x, e, t), sm)
adamc@29:                                                   end)
adamc@29:                             sm xes
adamc@29: 
adamc@29:             val (sm, si) = Sm.find (sm, old_xts, map (fn (x, _, t) => (x, t)) xets)
adamc@29: 
adamc@29:             val xes = map (fn (x, e, _) => (x, e)) xets
adamc@29:             val xes = ListMergeSort.sort (fn ((x1, _), (x2, _)) => String.compare (x1, x2) = GREATER) xes
adamc@29:         in
adamc@29:             ((L'.ERecord (si, xes), loc), sm)
adamc@29:         end
adamc@29:       | L.EField (e, x) =>
adamc@29:         let
adamc@29:             val (e, sm) = cifyExp (e, sm)
adamc@29:         in
adamc@29:             ((L'.EField (e, x), loc), sm)
adamc@29:         end
adamc@29: 
adamc@182:       | L.ECase (e, pes, {disc, result}) =>
adamc@181:         let
adamc@181:                 val (e, sm) = cifyExp (e, sm)
adamc@181:                 val (pes, sm) = ListUtil.foldlMap
adamc@181:                                     (fn ((p, e), sm) =>
adamc@181:                                         let
adamc@181:                                             val (e, sm) = cifyExp (e, sm)
adamc@182:                                             val (p, sm) = cifyPat (p, sm)
adamc@181:                                         in
adamc@182:                                             ((p, e), sm)
adamc@181:                                         end) sm pes
adamc@182:                 val (disc, sm) = cifyTyp (disc, sm)
adamc@182:                 val (result, sm) = cifyTyp (result, sm)
adamc@181:             in
adamc@182:                 ((L'.ECase (e, pes, {disc = disc, result = result}), loc), sm)
adamc@181:             end
adamc@178: 
adamc@180:       | L.EStrcat (e1, e2) =>
adamc@180:         let
adamc@180:             val (e1, sm) = cifyExp (e1, sm)
adamc@180:             val (e2, sm) = cifyExp (e2, sm)
adamc@180:         in
adamc@180:             ((L'.EFfiApp ("Basis", "strcat", [e1, e2]), loc), sm)
adamc@180:         end
adamc@102: 
adamc@102:       | L.EWrite e =>
adamc@102:         let
adamc@102:             val (e, sm) = cifyExp (e, sm)
adamc@102:         in
adamc@102:             ((L'.EWrite e, loc), sm)
adamc@102:         end
adamc@102: 
adamc@106:       | L.ESeq (e1, e2) =>
adamc@106:         let
adamc@106:             val (e1, sm) = cifyExp (e1, sm)
adamc@106:             val (e2, sm) = cifyExp (e2, sm)
adamc@106:         in
adamc@106:             ((L'.ESeq (e1, e2), loc), sm)
adamc@106:         end
adamc@106: 
adamc@269:       | L.ELet (x, t, e1, e2) =>
adamc@269:         let
adamc@269:             val (t, sm) = cifyTyp (t, sm)
adamc@269:             val (e1, sm) = cifyExp (e1, sm)
adamc@269:             val (e2, sm) = cifyExp (e2, sm)
adamc@269:         in
adamc@269:             ((L'.ELet (x, t, e1, e2), loc), sm)
adamc@269:         end
adamc@251: 
adamc@111:       | L.EClosure _ => (ErrorMsg.errorAt loc "Nested closure remains in code generation";
adamc@111:                          (dummye, sm))
adamc@111: 
adamc@269:       | L.EQuery {exps, tables, state, query, body, initial} =>
adamc@269:         let
adamc@269:             val (exps', sm) = ListUtil.foldlMap (fn ((x, t), sm) =>
adamc@269:                                                     let
adamc@269:                                                         val (t, sm) = cifyTyp (t, sm)
adamc@269:                                                     in
adamc@269:                                                         ((x, t), sm)
adamc@269:                                                     end) sm exps
adamc@269:             val (tables', sm) = ListUtil.foldlMap (fn ((x, xts), sm) =>
adamc@269:                                                       let
adamc@269:                                                           val (xts, sm) = ListUtil.foldlMap
adamc@269:                                                                               (fn ((x, t), sm) =>
adamc@269:                                                                                   let
adamc@269:                                                                                       val (t, sm) = cifyTyp (t, sm)
adamc@269:                                                                                   in
adamc@269:                                                                                       ((x, t), sm)
adamc@269:                                                                                   end) sm xts
adamc@269:                                                       in
adamc@269:                                                           ((x, xts), sm)
adamc@269:                                                       end) sm tables
adamc@269: 
adamc@269:             val row = exps @ map (fn (x, xts) => (x, (L.TRecord xts, loc))) tables
adamc@269:             val row = ListMergeSort.sort (fn ((x, _), (y, _)) => String.compare (x, y) = GREATER) row
adamc@269: 
adamc@269:             val (tableRows, sm) = ListUtil.foldlMap (fn (((x, xts), (_, xts')), sm) =>
adamc@269:                                                         let
adamc@269:                                                             val (sm, rnum) = Sm.find (sm, xts, xts')
adamc@269:                                                         in
adamc@269:                                                             ((x, rnum), sm)
adamc@269:                                                         end)
adamc@269:                                                     sm (ListPair.zip (tables, tables'))
adamc@269:             val row' = exps' @ map (fn (x, n) => (x, (L'.TRecord n, loc))) tableRows
adamc@269:             val row' = ListMergeSort.sort (fn ((x, _), (y, _)) => String.compare (x, y) = GREATER) row'
adamc@269: 
adamc@269:             val (sm, rnum) = Sm.find (sm, row, row')
adamc@269: 
adamc@269:             val (state, sm) = cifyTyp (state, sm)
adamc@269:             val (query, sm) = cifyExp (query, sm)
adamc@269:             val (body, sm) = cifyExp (body, sm)
adamc@269:             val (initial, sm) = cifyExp (initial, sm)
adamc@269:         in
adamc@269:             ((L'.EQuery {exps = exps', tables = tables', rnum = rnum, state = state,
adamc@269:                          query = query, body = body, initial = initial}, loc), sm)
adamc@269:         end
adamc@269: 
adamc@252: 
adamc@29: fun cifyDecl ((d, loc), sm) =
adamc@29:     case d of
adamc@165:         L.DDatatype (x, n, xncs) =>
adamc@165:         let
adamc@198:             val dk = ElabUtil.classifyDatatype xncs
adamc@165:             val (xncs, sm) = ListUtil.foldlMap (fn ((x, n, to), sm) =>
adamc@165:                                                    case to of
adamc@165:                                                        NONE => ((x, n, NONE), sm)
adamc@165:                                                      | SOME t =>
adamc@165:                                                        let
adamc@165:                                                            val (t, sm) = cifyTyp (t, sm)
adamc@165:                                                        in
adamc@165:                                                            ((x, n, SOME t), sm)
adamc@165:                                                        end) sm xncs
adamc@165:         in
adamc@188:             (SOME (L'.DDatatype (dk, x, n, xncs), loc), NONE, sm)
adamc@165:         end
adamc@164: 
adamc@164:       | L.DVal (x, n, t, e, _) =>
adamc@29:         let
adamc@29:             val (t, sm) = cifyTyp (t, sm)
adamc@109: 
adamc@109:             val (d, sm) = case #1 t of
adamc@121:                               L'.TFun _ =>
adamc@121:                               let
adamc@121:                                   fun unravel (tAll as (t, _), eAll as (e, _)) =
adamc@121:                                       case (t, e) of
adamc@121:                                           (L'.TFun (dom, ran), L.EAbs (ax, _, _, e)) =>
adamc@121:                                           let
adamc@121:                                               val (args, t, e) = unravel (ran, e)
adamc@121:                                           in
adamc@121:                                               ((ax, dom) :: args, t, e)
adamc@121:                                           end
adamc@121:                                         | (L'.TFun _, _) =>
adamc@121:                                           (ErrorMsg.errorAt loc "Function isn't explicit at code generation";
adamc@121:                                            ([], tAll, eAll))
adamc@121:                                         | _ => ([], tAll, eAll)
adamc@121: 
adamc@121:                                   val (args, ran, e) = unravel (t, e)
adamc@121:                                   val (e, sm) = cifyExp (e, sm)
adamc@121:                               in
adamc@121:                                   (L'.DFun (x, n, args, ran, e), sm)
adamc@121:                               end
adamc@121: 
adamc@109:                             | _ =>
adamc@109:                               let
adamc@109:                                   val (e, sm) = cifyExp (e, sm)
adamc@109:                               in
adamc@109:                                   (L'.DVal (x, n, t, e), sm)
adamc@109:                               end
adamc@29:         in
adamc@109:             (SOME (d, loc), NONE, sm)
adamc@29:         end
adamc@129:       | L.DValRec vis =>
adamc@129:         let
adamc@129:             val (vis, sm) = ListUtil.foldlMap
adamc@129:                             (fn ((x, n, t, e, _), sm) =>
adamc@129:                                 let                                    
adamc@129:                                     val (t, sm) = cifyTyp (t, sm)
adamc@129: 
adamc@129:                                     fun unravel (tAll as (t, _), eAll as (e, _)) =
adamc@129:                                         case (t, e) of
adamc@129:                                             (L'.TFun (dom, ran), L.EAbs (ax, _, _, e)) =>
adamc@129:                                             let
adamc@129:                                                 val (args, t, e) = unravel (ran, e)
adamc@129:                                             in
adamc@129:                                                 ((ax, dom) :: args, t, e)
adamc@129:                                             end
adamc@129:                                           | (L'.TFun _, _) =>
adamc@129:                                             (ErrorMsg.errorAt loc "Function isn't explicit at code generation";
adamc@129:                                              ([], tAll, eAll))
adamc@129:                                           | _ => ([], tAll, eAll)
adamc@129:                                                  
adamc@129:                                     val (args, ran, e) = unravel (t, e)
adamc@129:                                     val (e, sm) = cifyExp (e, sm)
adamc@129:                               in
adamc@129:                                   ((x, n, args, ran, e), sm)
adamc@129:                               end)
adamc@129:                             sm vis
adamc@129:         in
adamc@129:             (SOME (L'.DFunRec vis, loc), NONE, sm)
adamc@129:         end        
adamc@129: 
adamc@144:       | L.DExport (ek, s, n, ts) =>
adamc@120:         let
adamc@120:             val (ts, sm) = ListUtil.foldlMap cifyTyp sm ts
adamc@120:         in
adamc@144:             (NONE, SOME (ek, "/" ^ s, n, ts), sm)
adamc@120:         end
adamc@29: 
adamc@29: fun cjrize ds =
adamc@29:     let
adamc@196:         val (dsF, ds, ps, sm) = foldl (fn (d, (dsF, ds, ps, sm)) =>
adamc@196:                                           let
adamc@196:                                               val (dop, pop, sm) = cifyDecl (d, sm)
adamc@196:                                               val (dsF, ds) = case dop of
adamc@196:                                                                   NONE => (dsF, ds)
adamc@196:                                                                 | SOME (d as (L'.DDatatype (dk, x, n, _), loc)) =>
adamc@196:                                                                   ((L'.DDatatypeForward (dk, x, n), loc) :: dsF,
adamc@196:                                                                    d :: ds)
adamc@196:                                                                 | SOME d => (dsF, d :: ds)
adamc@196:                                               val ps = case pop of
adamc@196:                                                            NONE => ps
adamc@196:                                                          | SOME p => p :: ps
adamc@196:                                           in
adamc@196:                                               (dsF, ds, ps, sm)
adamc@196:                                           end)
adamc@196:                                       ([], [], [], Sm.empty) ds
adamc@29:     in
adamc@196:         (List.revAppend (dsF,
adamc@196:                          List.revAppend (map (fn v => (L'.DStruct v, ErrorMsg.dummySpan)) (Sm.declares sm),
adamc@196:                                          rev ds)),
adamc@101:          ps)
adamc@29:     end
adamc@29: 
adamc@29: end