adamc@26: (* Copyright (c) 2008, Adam Chlipala adamc@26: * All rights reserved. adamc@26: * adamc@26: * Redistribution and use in source and binary forms, with or without adamc@26: * modification, are permitted provided that the following conditions are met: adamc@26: * adamc@26: * - Redistributions of source code must retain the above copyright notice, adamc@26: * this list of conditions and the following disclaimer. adamc@26: * - Redistributions in binary form must reproduce the above copyright notice, adamc@26: * this list of conditions and the following disclaimer in the documentation adamc@26: * and/or other materials provided with the distribution. adamc@26: * - The names of contributors may not be used to endorse or promote products adamc@26: * derived from this software without specific prior written permission. adamc@26: * adamc@26: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" adamc@26: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE adamc@26: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE adamc@26: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE adamc@26: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR adamc@26: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF adamc@26: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS adamc@26: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN adamc@26: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) adamc@26: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE adamc@26: * POSSIBILITY OF SUCH DAMAGE. adamc@26: *) adamc@26: adamc@26: structure Cloconv :> CLOCONV = struct adamc@26: adamc@26: structure L = Mono adamc@26: structure L' = Flat adamc@26: adamc@26: structure IS = IntBinarySet adamc@26: adamc@26: structure U = FlatUtil adamc@26: structure E = FlatEnv adamc@26: adamc@26: open Print.PD adamc@26: open Print adamc@26: adamc@26: val liftExpInExp = adamc@26: U.Exp.mapB {typ = fn t => t, adamc@26: exp = fn bound => fn e => adamc@26: case e of adamc@26: L'.ERel xn => adamc@26: if xn < bound then adamc@26: e adamc@26: else adamc@26: L'.ERel (xn + 1) adamc@26: | _ => e, adamc@26: bind = fn (bound, U.Exp.RelE _) => bound + 1 adamc@26: | (bound, _) => bound} adamc@26: val subExpInExp = adamc@26: U.Exp.mapB {typ = fn t => t, adamc@26: exp = fn (xn, rep) => fn e => adamc@26: case e of adamc@26: L'.ERel xn' => adamc@74: (case Int.compare (xn', xn) of adamc@74: EQUAL => #1 rep adamc@74: | GREATER => L'.ERel (xn' - 1) adamc@74: | _ => e) adamc@26: | _ => e, adamc@26: bind = fn ((xn, rep), U.Exp.RelE _) => (xn+1, liftExpInExp 0 rep) adamc@26: | (ctx, _) => ctx} adamc@26: adamc@26: adamc@26: fun ccTyp (t, loc) = adamc@26: case t of adamc@26: L.TFun (t1, t2) => (L'.TFun (ccTyp t1, ccTyp t2), loc) adamc@26: | L.TRecord xts => (L'.TRecord (map (fn (x, t) => (x, ccTyp t)) xts), loc) adamc@26: | L.TNamed n => (L'.TNamed n, loc) adamc@52: | L.TFfi mx => (L'.TFfi mx, loc) adamc@26: adamc@26: structure Ds :> sig adamc@26: type t adamc@26: adamc@26: val empty : t adamc@26: adamc@26: val exp : t -> string * int * L'.typ * L'.exp -> t adamc@26: val func : t -> string * L'.typ * L'.typ * L'.exp -> t * int adamc@101: val page : t -> (string * L'.typ) list * L'.exp -> t adamc@26: val decls : t -> L'.decl list adamc@26: adamc@26: val enter : t -> t adamc@26: val used : t * int -> t adamc@26: val leave : t -> t adamc@26: val listUsed : t -> int list adamc@26: end = struct adamc@26: adamc@26: type t = int * L'.decl list * IS.set adamc@26: adamc@26: val empty = (0, [], IS.empty) adamc@26: adamc@26: fun exp (fc, ds, vm) (v as (_, _, _, (_, loc))) = (fc, (L'.DVal v, loc) :: ds, vm) adamc@26: adamc@26: fun func (fc, ds, vm) (x, dom, ran, e as (_, loc)) = adamc@26: ((fc+1, (L'.DFun (fc, x, dom, ran, e), loc) :: ds, vm), fc) adamc@26: adamc@101: fun page (fc, ds, vm) (xts, e as (_, loc)) = (fc, (L'.DPage (xts, e), loc) :: ds, vm) adamc@101: adamc@26: fun decls (_, ds, _) = rev ds adamc@26: adamc@26: fun enter (fc, ds, vm) = (fc, ds, IS.map (fn n => n + 1) vm) adamc@26: fun used ((fc, ds, vm), n) = (fc, ds, IS.add (vm, n)) adamc@26: fun leave (fc, ds, vm) = (fc, ds, IS.map (fn n => n - 1) (IS.delete (vm, 0) handle NotFound => vm)) adamc@26: adamc@26: fun listUsed (_, _, vm) = IS.listItems vm adamc@26: adamc@26: end adamc@26: adamc@26: adamc@26: fun ccExp env ((e, loc), D) = adamc@26: case e of adamc@26: L.EPrim p => ((L'.EPrim p, loc), D) adamc@26: | L.ERel n => ((L'.ERel n, loc), Ds.used (D, n)) adamc@26: | L.ENamed n => ((L'.ENamed n, loc), D) adamc@52: | L.EFfi mx => ((L'.EFfi mx, loc), D) adamc@52: | L.EFfiApp (m, x, es) => adamc@52: let adamc@52: val (es, D) = ListUtil.foldlMap (ccExp env) D es adamc@52: in adamc@52: ((L'.EFfiApp (m, x, es), loc), D) adamc@52: end adamc@26: | L.EApp (e1, e2) => adamc@26: let adamc@26: val (e1, D) = ccExp env (e1, D) adamc@26: val (e2, D) = ccExp env (e2, D) adamc@26: in adamc@29: ((L'.ELet ([("closure", (L'.TTop, loc), e1), adamc@29: ("arg", (L'.TTop, loc), liftExpInExp 0 e2), adamc@29: ("code", (L'.TTop, loc), (L'.EField ((L'.ERel 1, loc), "func"), loc)), adamc@29: ("env", (L'.TTop, loc), (L'.EField ((L'.ERel 2, loc), "env"), loc))], adamc@26: (L'.EApp ((L'.ERel 1, loc), adamc@29: (L'.ERecord [("env", (L'.ERel 0, loc), (L'.TTop, loc)), adamc@29: ("arg", (L'.ERel 2, loc), (L'.TTop, loc))], loc)), loc)), loc), D) adamc@26: end adamc@26: | L.EAbs (x, dom, ran, e) => adamc@26: let adamc@26: val dom = ccTyp dom adamc@26: val ran = ccTyp ran adamc@26: val (e, D) = ccExp (E.pushERel env x dom) (e, Ds.enter D) adamc@26: val ns = Ds.listUsed D adamc@26: val ns = List.filter (fn n => n <> 0) ns adamc@26: val D = Ds.leave D adamc@26: adamc@98: val envT = (L'.TRecord (map (fn n => ("fv" ^ Int.toString n, #2 (E.lookupERel env (n-1)))) ns), loc) adamc@98: adamc@26: (*val () = Print.preface ("Before", FlatPrint.p_exp FlatEnv.basis e) adamc@26: val () = List.app (fn (x, t) => preface ("Bound", box [string x, adamc@26: space, adamc@26: string ":", adamc@26: space, adamc@26: FlatPrint.p_typ env t])) adamc@26: (E.listERels env) adamc@26: val () = List.app (fn n => preface ("Free", FlatPrint.p_exp (E.pushERel env x dom) adamc@26: (L'.ERel n, loc))) ns*) adamc@26: val body = foldl (fn (n, e) => adamc@26: subExpInExp (n, (L'.EField ((L'.ERel 1, loc), "fv" ^ Int.toString n), loc)) e) adamc@26: e ns adamc@26: (*val () = Print.preface (" After", FlatPrint.p_exp FlatEnv.basis body)*) adamc@98: val body = (L'.ELet ([("env", envT, (L'.EField ((L'.ERel 0, loc), "env"), loc)), adamc@98: ("arg", dom, (L'.EField ((L'.ERel 1, loc), "arg"), loc))], adamc@26: body), loc) adamc@98: adamc@26: val (D, fi) = Ds.func D (x, (L'.TRecord [("env", envT), ("arg", dom)], loc), ran, body) adamc@26: in adamc@29: ((L'.ERecord [("code", (L'.ECode fi, loc), (L'.TTop, loc)), adamc@26: ("env", (L'.ERecord (map (fn n => ("fv" ^ Int.toString n, adamc@29: (L'.ERel (n-1), loc), adamc@29: #2 (E.lookupERel env (n-1)))) ns), loc), adamc@29: envT)], loc), D) adamc@26: end adamc@26: adamc@26: | L.ERecord xes => adamc@26: let adamc@29: val (xes, D) = ListUtil.foldlMap (fn ((x, e, t), D) => adamc@26: let adamc@26: val (e, D) = ccExp env (e, D) adamc@26: in adamc@29: ((x, e, ccTyp t), D) adamc@26: end) D xes adamc@26: in adamc@26: ((L'.ERecord xes, loc), D) adamc@26: end adamc@26: | L.EField (e1, x) => adamc@26: let adamc@26: val (e1, D) = ccExp env (e1, D) adamc@26: in adamc@26: ((L'.EField (e1, x), loc), D) adamc@26: end adamc@26: adamc@102: | L.EStrcat (e1, e2) => adamc@102: let adamc@102: val (e1, D) = ccExp env (e1, D) adamc@102: val (e2, D) = ccExp env (e2, D) adamc@102: in adamc@102: ((L'.EStrcat (e1, e2), loc), D) adamc@102: end adamc@102: adamc@102: | L.EWrite e => adamc@102: let adamc@102: val (e, D) = ccExp env (e, D) adamc@102: in adamc@102: ((L'.EWrite e, loc), D) adamc@102: end adamc@94: adamc@106: | L.ESeq (e1, e2) => adamc@106: let adamc@106: val (e1, D) = ccExp env (e1, D) adamc@106: val (e2, D) = ccExp env (e2, D) adamc@106: in adamc@106: ((L'.ESeq (e1, e2), loc), D) adamc@106: end adamc@106: adamc@26: fun ccDecl ((d, loc), D) = adamc@26: case d of adamc@26: L.DVal (x, n, t, e) => adamc@26: let adamc@26: val t = ccTyp t adamc@56: val (e, D) = ccExp E.empty (e, D) adamc@26: in adamc@26: Ds.exp D (x, n, t, e) adamc@26: end adamc@101: | L.DPage (xts, e) => adamc@101: let adamc@101: val xts = map (fn (x, t) => (x, ccTyp t)) xts adamc@101: val (e, D) = ccExp E.empty (e, D) adamc@101: in adamc@101: Ds.page D (xts, e) adamc@101: end adamc@26: adamc@26: fun cloconv ds = adamc@26: let adamc@26: val D = foldl ccDecl Ds.empty ds adamc@26: in adamc@26: Ds.decls D adamc@26: end adamc@26: adamc@26: end