adamc@2: (* Copyright (c) 2008, Adam Chlipala adamc@2: * All rights reserved. adamc@2: * adamc@2: * Redistribution and use in source and binary forms, with or without adamc@2: * modification, are permitted provided that the following conditions are met: adamc@2: * adamc@2: * - Redistributions of source code must retain the above copyright notice, adamc@2: * this list of conditions and the following disclaimer. adamc@2: * - Redistributions in binary form must reproduce the above copyright notice, adamc@2: * this list of conditions and the following disclaimer in the documentation adamc@2: * and/or other materials provided with the distribution. adamc@2: * - The names of contributors may not be used to endorse or promote products adamc@2: * derived from this software without specific prior written permission. adamc@2: * adamc@2: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" adamc@2: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE adamc@2: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE adamc@2: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE adamc@2: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR adamc@2: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF adamc@2: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS adamc@2: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN adamc@2: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) adamc@2: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE adamc@2: * POSSIBILITY OF SUCH DAMAGE. adamc@2: *) adamc@2: adamc@2: structure Elaborate :> ELABORATE = struct adamc@2: adamc@14: structure P = Prim adamc@4: structure L = Source adamc@2: structure L' = Elab adamc@2: structure E = ElabEnv adamc@2: structure U = ElabUtil adamc@2: adamc@3: open Print adamc@3: open ElabPrint adamc@3: adamc@2: fun elabExplicitness e = adamc@2: case e of adamc@2: L.Explicit => L'.Explicit adamc@2: | L.Implicit => L'.Implicit adamc@2: adamc@2: fun occursKind r = adamc@2: U.Kind.exists (fn L'.KUnif (_, r') => r = r' adamc@2: | _ => false) adamc@2: adamc@3: datatype kunify_error = adamc@2: KOccursCheckFailed of L'.kind * L'.kind adamc@2: | KIncompatible of L'.kind * L'.kind adamc@2: adamc@3: exception KUnify' of kunify_error adamc@3: adamc@3: fun kunifyError err = adamc@2: case err of adamc@2: KOccursCheckFailed (k1, k2) => adamc@3: eprefaces "Kind occurs check failed" adamc@3: [("Kind 1", p_kind k1), adamc@3: ("Kind 2", p_kind k2)] adamc@2: | KIncompatible (k1, k2) => adamc@3: eprefaces "Incompatible kinds" adamc@3: [("Kind 1", p_kind k1), adamc@3: ("Kind 2", p_kind k2)] adamc@2: adamc@3: fun unifyKinds' (k1All as (k1, _)) (k2All as (k2, _)) = adamc@2: let adamc@3: fun err f = raise KUnify' (f (k1All, k2All)) adamc@2: in adamc@2: case (k1, k2) of adamc@2: (L'.KType, L'.KType) => () adamc@2: | (L'.KArrow (d1, r1), L'.KArrow (d2, r2)) => adamc@3: (unifyKinds' d1 d2; adamc@3: unifyKinds' r1 r2) adamc@2: | (L'.KName, L'.KName) => () adamc@3: | (L'.KRecord k1, L'.KRecord k2) => unifyKinds' k1 k2 adamc@2: adamc@2: | (L'.KError, _) => () adamc@2: | (_, L'.KError) => () adamc@2: adamc@3: | (L'.KUnif (_, ref (SOME k1All)), _) => unifyKinds' k1All k2All adamc@3: | (_, L'.KUnif (_, ref (SOME k2All))) => unifyKinds' k1All k2All adamc@2: adamc@2: | (L'.KUnif (_, r1), L'.KUnif (_, r2)) => adamc@2: if r1 = r2 then adamc@2: () adamc@2: else adamc@2: r1 := SOME k2All adamc@2: adamc@2: | (L'.KUnif (_, r), _) => adamc@2: if occursKind r k2All then adamc@2: err KOccursCheckFailed adamc@2: else adamc@2: r := SOME k2All adamc@2: | (_, L'.KUnif (_, r)) => adamc@2: if occursKind r k1All then adamc@2: err KOccursCheckFailed adamc@2: else adamc@2: r := SOME k1All adamc@2: adamc@2: | _ => err KIncompatible adamc@2: end adamc@2: adamc@3: exception KUnify of L'.kind * L'.kind * kunify_error adamc@3: adamc@3: fun unifyKinds k1 k2 = adamc@3: unifyKinds' k1 k2 adamc@3: handle KUnify' err => raise KUnify (k1, k2, err) adamc@3: adamc@3: datatype con_error = adamc@3: UnboundCon of ErrorMsg.span * string adamc@34: | UnboundStrInCon of ErrorMsg.span * string adamc@3: | WrongKind of L'.con * L'.kind * L'.kind * kunify_error adamc@3: adamc@5: fun conError env err = adamc@3: case err of adamc@3: UnboundCon (loc, s) => adamc@3: ErrorMsg.errorAt loc ("Unbound constructor variable " ^ s) adamc@34: | UnboundStrInCon (loc, s) => adamc@34: ErrorMsg.errorAt loc ("Unbound structure " ^ s) adamc@3: | WrongKind (c, k1, k2, kerr) => adamc@3: (ErrorMsg.errorAt (#2 c) "Wrong kind"; adamc@5: eprefaces' [("Constructor", p_con env c), adamc@5: ("Have kind", p_kind k1), adamc@5: ("Need kind", p_kind k2)]; adamc@3: kunifyError kerr) adamc@3: adamc@5: fun checkKind env c k1 k2 = adamc@3: unifyKinds k1 k2 adamc@3: handle KUnify (k1, k2, err) => adamc@5: conError env (WrongKind (c, k1, k2, err)) adamc@3: adamc@3: val dummy = ErrorMsg.dummySpan adamc@3: adamc@3: val ktype = (L'.KType, dummy) adamc@3: val kname = (L'.KName, dummy) adamc@12: val ktype_record = (L'.KRecord ktype, dummy) adamc@3: adamc@3: val cerror = (L'.CError, dummy) adamc@3: val kerror = (L'.KError, dummy) adamc@10: val eerror = (L'.EError, dummy) adamc@31: val sgnerror = (L'.SgnError, dummy) adamc@31: val strerror = (L'.StrError, dummy) adamc@3: adamc@56: val int = ref cerror adamc@56: val float = ref cerror adamc@56: val string = ref cerror adamc@56: adamc@3: local adamc@3: val count = ref 0 adamc@3: in adamc@3: adamc@3: fun resetKunif () = count := 0 adamc@3: adamc@3: fun kunif () = adamc@3: let adamc@3: val n = !count adamc@3: val s = if n <= 26 then adamc@3: str (chr (ord #"A" + n)) adamc@3: else adamc@3: "U" ^ Int.toString (n - 26) adamc@3: in adamc@3: count := n + 1; adamc@3: (L'.KUnif (s, ref NONE), dummy) adamc@3: end adamc@3: adamc@3: end adamc@3: adamc@10: local adamc@10: val count = ref 0 adamc@10: in adamc@10: adamc@10: fun resetCunif () = count := 0 adamc@10: adamc@10: fun cunif k = adamc@10: let adamc@10: val n = !count adamc@10: val s = if n <= 26 then adamc@10: str (chr (ord #"A" + n)) adamc@10: else adamc@10: "U" ^ Int.toString (n - 26) adamc@10: in adamc@10: count := n + 1; adamc@10: (L'.CUnif (k, s, ref NONE), dummy) adamc@10: end adamc@10: adamc@10: end adamc@10: adamc@18: fun elabKind (k, loc) = adamc@18: case k of adamc@18: L.KType => (L'.KType, loc) adamc@18: | L.KArrow (k1, k2) => (L'.KArrow (elabKind k1, elabKind k2), loc) adamc@18: | L.KName => (L'.KName, loc) adamc@18: | L.KRecord k => (L'.KRecord (elabKind k), loc) adamc@18: | L.KWild => kunif () adamc@18: adamc@3: fun elabCon env (c, loc) = adamc@3: case c of adamc@3: L.CAnnot (c, k) => adamc@3: let adamc@3: val k' = elabKind k adamc@3: val (c', ck) = elabCon env c adamc@3: in adamc@5: checkKind env c' ck k'; adamc@3: (c', k') adamc@3: end adamc@3: adamc@3: | L.TFun (t1, t2) => adamc@3: let adamc@3: val (t1', k1) = elabCon env t1 adamc@3: val (t2', k2) = elabCon env t2 adamc@3: in adamc@5: checkKind env t1' k1 ktype; adamc@5: checkKind env t2' k2 ktype; adamc@3: ((L'.TFun (t1', t2'), loc), ktype) adamc@3: end adamc@3: | L.TCFun (e, x, k, t) => adamc@3: let adamc@3: val e' = elabExplicitness e adamc@3: val k' = elabKind k adamc@3: val env' = E.pushCRel env x k' adamc@3: val (t', tk) = elabCon env' t adamc@3: in adamc@5: checkKind env t' tk ktype; adamc@3: ((L'.TCFun (e', x, k', t'), loc), ktype) adamc@3: end adamc@3: | L.TRecord c => adamc@3: let adamc@3: val (c', ck) = elabCon env c adamc@3: val k = (L'.KRecord ktype, loc) adamc@3: in adamc@5: checkKind env c' ck k; adamc@3: ((L'.TRecord c', loc), ktype) adamc@3: end adamc@3: adamc@34: | L.CVar ([], s) => adamc@3: (case E.lookupC env s of adamc@9: E.NotBound => adamc@5: (conError env (UnboundCon (loc, s)); adamc@3: (cerror, kerror)) adamc@9: | E.Rel (n, k) => adamc@3: ((L'.CRel n, loc), k) adamc@9: | E.Named (n, k) => adamc@3: ((L'.CNamed n, loc), k)) adamc@34: | L.CVar (m1 :: ms, s) => adamc@34: (case E.lookupStr env m1 of adamc@42: NONE => (conError env (UnboundStrInCon (loc, m1)); adamc@34: (cerror, kerror)) adamc@34: | SOME (n, sgn) => adamc@34: let adamc@34: val (str, sgn) = foldl (fn (m, (str, sgn)) => adamc@34: case E.projectStr env {sgn = sgn, str = str, field = m} of adamc@34: NONE => (conError env (UnboundStrInCon (loc, m)); adamc@34: (strerror, sgnerror)) adamc@34: | SOME sgn => ((L'.StrProj (str, m), loc), sgn)) adamc@34: ((L'.StrVar n, loc), sgn) ms adamc@34: adamc@34: val k = case E.projectCon env {sgn = sgn, str = str, field = s} of adamc@34: NONE => (conError env (UnboundCon (loc, s)); adamc@34: kerror) adamc@34: | SOME (k, _) => k adamc@34: in adamc@34: ((L'.CModProj (n, ms, s), loc), k) adamc@34: end) adamc@34: adamc@3: | L.CApp (c1, c2) => adamc@3: let adamc@3: val (c1', k1) = elabCon env c1 adamc@3: val (c2', k2) = elabCon env c2 adamc@3: val dom = kunif () adamc@3: val ran = kunif () adamc@3: in adamc@5: checkKind env c1' k1 (L'.KArrow (dom, ran), loc); adamc@5: checkKind env c2' k2 dom; adamc@3: ((L'.CApp (c1', c2'), loc), ran) adamc@3: end adamc@8: | L.CAbs (x, k, t) => adamc@3: let adamc@3: val k' = elabKind k adamc@3: val env' = E.pushCRel env x k' adamc@3: val (t', tk) = elabCon env' t adamc@3: in adamc@8: ((L'.CAbs (x, k', t'), loc), adamc@3: (L'.KArrow (k', tk), loc)) adamc@3: end adamc@3: adamc@3: | L.CName s => adamc@3: ((L'.CName s, loc), kname) adamc@3: adamc@3: | L.CRecord xcs => adamc@3: let adamc@3: val k = kunif () adamc@3: adamc@3: val xcs' = map (fn (x, c) => adamc@3: let adamc@3: val (x', xk) = elabCon env x adamc@3: val (c', ck) = elabCon env c adamc@3: in adamc@5: checkKind env x' xk kname; adamc@5: checkKind env c' ck k; adamc@3: (x', c') adamc@3: end) xcs adamc@3: in adamc@5: ((L'.CRecord (k, xcs'), loc), (L'.KRecord k, loc)) adamc@3: end adamc@3: | L.CConcat (c1, c2) => adamc@3: let adamc@3: val (c1', k1) = elabCon env c1 adamc@3: val (c2', k2) = elabCon env c2 adamc@3: val ku = kunif () adamc@3: val k = (L'.KRecord ku, loc) adamc@3: in adamc@5: checkKind env c1' k1 k; adamc@5: checkKind env c2' k2 k; adamc@3: ((L'.CConcat (c1', c2'), loc), k) adamc@3: end adamc@3: adamc@18: | L.CWild k => adamc@18: let adamc@18: val k' = elabKind k adamc@18: in adamc@18: (cunif k', k') adamc@18: end adamc@18: adamc@6: fun kunifsRemain k = adamc@6: case k of adamc@6: L'.KUnif (_, ref NONE) => true adamc@6: | _ => false adamc@10: fun cunifsRemain c = adamc@10: case c of adamc@10: L'.CUnif (_, _, ref NONE) => true adamc@10: | _ => false adamc@6: adamc@6: val kunifsInKind = U.Kind.exists kunifsRemain adamc@6: val kunifsInCon = U.Con.exists {kind = kunifsRemain, adamc@6: con = fn _ => false} adamc@10: val kunifsInExp = U.Exp.exists {kind = kunifsRemain, adamc@10: con = fn _ => false, adamc@10: exp = fn _ => false} adamc@10: adamc@10: val cunifsInCon = U.Con.exists {kind = fn _ => false, adamc@10: con = cunifsRemain} adamc@10: val cunifsInExp = U.Exp.exists {kind = fn _ => false, adamc@10: con = cunifsRemain, adamc@10: exp = fn _ => false} adamc@10: adamc@10: fun occursCon r = adamc@10: U.Con.exists {kind = fn _ => false, adamc@10: con = fn L'.CUnif (_, _, r') => r = r' adamc@10: | _ => false} adamc@10: adamc@10: datatype cunify_error = adamc@10: CKind of L'.kind * L'.kind * kunify_error adamc@10: | COccursCheckFailed of L'.con * L'.con adamc@10: | CIncompatible of L'.con * L'.con adamc@10: | CExplicitness of L'.con * L'.con adamc@12: | CKindof of L'.con adamc@12: | CRecordFailure adamc@10: adamc@10: exception CUnify' of cunify_error adamc@10: adamc@10: fun cunifyError env err = adamc@10: case err of adamc@10: CKind (k1, k2, kerr) => adamc@10: (eprefaces "Kind unification failure" adamc@10: [("Kind 1", p_kind k1), adamc@10: ("Kind 2", p_kind k2)]; adamc@10: kunifyError kerr) adamc@10: | COccursCheckFailed (c1, c2) => adamc@10: eprefaces "Constructor occurs check failed" adamc@10: [("Con 1", p_con env c1), adamc@10: ("Con 2", p_con env c2)] adamc@10: | CIncompatible (c1, c2) => adamc@10: eprefaces "Incompatible constructors" adamc@10: [("Con 1", p_con env c1), adamc@10: ("Con 2", p_con env c2)] adamc@10: | CExplicitness (c1, c2) => adamc@10: eprefaces "Differing constructor function explicitness" adamc@10: [("Con 1", p_con env c1), adamc@10: ("Con 2", p_con env c2)] adamc@12: | CKindof c => adamc@12: eprefaces "Kind unification variable blocks kindof calculation" adamc@12: [("Con", p_con env c)] adamc@12: | CRecordFailure => adamc@12: eprefaces "Can't unify record constructors" [] adamc@10: adamc@13: exception SynUnif = E.SynUnif adamc@13: val liftConInCon = E.liftConInCon adamc@12: adamc@12: val subConInCon = adamc@12: U.Con.mapB {kind = fn k => k, adamc@12: con = fn (xn, rep) => fn c => adamc@12: case c of adamc@12: L'.CRel xn' => adamc@12: if xn = xn' then adamc@12: #1 rep adamc@12: else adamc@12: c adamc@17: (*| L'.CUnif _ => raise SynUnif*) adamc@12: | _ => c, adamc@12: bind = fn ((xn, rep), U.Con.Rel _) => (xn+1, liftConInCon 0 rep) adamc@12: | (ctx, _) => ctx} adamc@12: adamc@43: fun subStrInSgn (m1, m2) = adamc@43: U.Sgn.map {kind = fn k => k, adamc@43: con = fn c as L'.CModProj (m1', ms, x) => adamc@43: if m1 = m1' then adamc@43: L'.CModProj (m2, ms, x) adamc@43: else adamc@43: c adamc@43: | c => c, adamc@43: sgn_item = fn sgi => sgi, adamc@43: sgn = fn sgn => sgn} adamc@43: adamc@12: type record_summary = { adamc@12: fields : (L'.con * L'.con) list, adamc@12: unifs : (L'.con * L'.con option ref) list, adamc@12: others : L'.con list adamc@12: } adamc@12: adamc@12: fun summaryToCon {fields, unifs, others} = adamc@12: let adamc@12: val c = (L'.CRecord (ktype, []), dummy) adamc@12: val c = List.foldr (fn (c', c) => (L'.CConcat (c', c), dummy)) c others adamc@12: val c = List.foldr (fn ((c', _), c) => (L'.CConcat (c', c), dummy)) c unifs adamc@12: in adamc@12: (L'.CConcat ((L'.CRecord (ktype, fields), dummy), c), dummy) adamc@12: end adamc@12: adamc@12: fun p_summary env s = p_con env (summaryToCon s) adamc@12: adamc@12: exception CUnify of L'.con * L'.con * cunify_error adamc@12: adamc@12: fun hnormKind (kAll as (k, _)) = adamc@12: case k of adamc@12: L'.KUnif (_, ref (SOME k)) => hnormKind k adamc@12: | _ => kAll adamc@12: adamc@12: fun kindof env (c, loc) = adamc@12: case c of adamc@12: L'.TFun _ => ktype adamc@12: | L'.TCFun _ => ktype adamc@12: | L'.TRecord _ => ktype adamc@12: adamc@12: | L'.CRel xn => #2 (E.lookupCRel env xn) adamc@12: | L'.CNamed xn => #2 (E.lookupCNamed env xn) adamc@34: | L'.CModProj (n, ms, x) => adamc@34: let adamc@34: val (_, sgn) = E.lookupStrNamed env n adamc@34: val (str, sgn) = foldl (fn (m, (str, sgn)) => adamc@34: case E.projectStr env {sgn = sgn, str = str, field = m} of adamc@34: NONE => raise Fail "kindof: Unknown substructure" adamc@34: | SOME sgn => ((L'.StrProj (str, m), loc), sgn)) adamc@34: ((L'.StrVar n, loc), sgn) ms adamc@34: in adamc@34: case E.projectCon env {sgn = sgn, str = str, field = x} of adamc@34: NONE => raise Fail "kindof: Unknown con in structure" adamc@34: | SOME (k, _) => k adamc@34: end adamc@34: adamc@12: | L'.CApp (c, _) => adamc@12: (case #1 (hnormKind (kindof env c)) of adamc@12: L'.KArrow (_, k) => k adamc@12: | L'.KError => kerror adamc@12: | _ => raise CUnify' (CKindof c)) adamc@12: | L'.CAbs (x, k, c) => (L'.KArrow (k, kindof (E.pushCRel env x k) c), loc) adamc@12: adamc@12: | L'.CName _ => kname adamc@12: adamc@12: | L'.CRecord (k, _) => (L'.KRecord k, loc) adamc@12: | L'.CConcat (c, _) => kindof env c adamc@12: adamc@12: | L'.CError => kerror adamc@12: | L'.CUnif (k, _, _) => k adamc@12: adamc@12: fun unifyRecordCons env (c1, c2) = adamc@12: let adamc@12: val k1 = kindof env c1 adamc@12: val k2 = kindof env c2 adamc@12: in adamc@12: unifyKinds k1 k2; adamc@12: unifySummaries env (k1, recordSummary env c1, recordSummary env c2) adamc@12: end adamc@12: adamc@12: and recordSummary env c : record_summary = adamc@12: case hnormCon env c of adamc@12: (L'.CRecord (_, xcs), _) => {fields = xcs, unifs = [], others = []} adamc@12: | (L'.CConcat (c1, c2), _) => adamc@12: let adamc@12: val s1 = recordSummary env c1 adamc@12: val s2 = recordSummary env c2 adamc@12: in adamc@12: {fields = #fields s1 @ #fields s2, adamc@12: unifs = #unifs s1 @ #unifs s2, adamc@12: others = #others s1 @ #others s2} adamc@12: end adamc@12: | (L'.CUnif (_, _, ref (SOME c)), _) => recordSummary env c adamc@12: | c' as (L'.CUnif (_, _, r), _) => {fields = [], unifs = [(c', r)], others = []} adamc@12: | c' => {fields = [], unifs = [], others = [c']} adamc@12: adamc@12: and consEq env (c1, c2) = adamc@12: (unifyCons env c1 c2; adamc@12: true) adamc@12: handle CUnify _ => false adamc@12: adamc@12: and unifySummaries env (k, s1 : record_summary, s2 : record_summary) = adamc@12: let adamc@14: (*val () = eprefaces "Summaries" [("#1", p_summary env s1), adamc@14: ("#2", p_summary env s2)]*) adamc@12: adamc@12: fun eatMatching p (ls1, ls2) = adamc@12: let adamc@12: fun em (ls1, ls2, passed1) = adamc@12: case ls1 of adamc@12: [] => (rev passed1, ls2) adamc@12: | h1 :: t1 => adamc@12: let adamc@12: fun search (ls2', passed2) = adamc@12: case ls2' of adamc@12: [] => em (t1, ls2, h1 :: passed1) adamc@12: | h2 :: t2 => adamc@12: if p (h1, h2) then adamc@12: em (t1, List.revAppend (passed2, t2), passed1) adamc@12: else adamc@12: search (t2, h2 :: passed2) adamc@12: in adamc@12: search (ls2, []) adamc@12: end adamc@12: in adamc@12: em (ls1, ls2, []) adamc@12: end adamc@12: adamc@12: val (fs1, fs2) = eatMatching (fn ((x1, c1), (x2, c2)) => adamc@12: if consEq env (x1, x2) then adamc@12: (unifyCons env c1 c2; adamc@12: true) adamc@12: else adamc@12: false) (#fields s1, #fields s2) adamc@14: (*val () = eprefaces "Summaries2" [("#1", p_summary env {fields = fs1, unifs = #unifs s1, others = #others s1}), adamc@14: ("#2", p_summary env {fields = fs2, unifs = #unifs s2, others = #others s2})]*) adamc@12: val (unifs1, unifs2) = eatMatching (fn ((_, r1), (_, r2)) => r1 = r2) (#unifs s1, #unifs s2) adamc@12: val (others1, others2) = eatMatching (consEq env) (#others s1, #others s2) adamc@12: adamc@12: fun unifFields (fs, others, unifs) = adamc@12: case (fs, others, unifs) of adamc@12: ([], [], _) => ([], [], unifs) adamc@12: | (_, _, []) => (fs, others, []) adamc@12: | (_, _, (_, r) :: rest) => adamc@12: let adamc@12: val r' = ref NONE adamc@12: val cr' = (L'.CUnif (k, "recd", r'), dummy) adamc@12: adamc@12: val prefix = case (fs, others) of adamc@12: ([], other :: others) => adamc@12: List.foldl (fn (other, c) => adamc@12: (L'.CConcat (c, other), dummy)) adamc@12: other others adamc@12: | (fs, []) => adamc@12: (L'.CRecord (k, fs), dummy) adamc@12: | (fs, others) => adamc@12: List.foldl (fn (other, c) => adamc@12: (L'.CConcat (c, other), dummy)) adamc@12: (L'.CRecord (k, fs), dummy) others adamc@12: in adamc@12: r := SOME (L'.CConcat (prefix, cr'), dummy); adamc@12: ([], [], (cr', r') :: rest) adamc@12: end adamc@12: adamc@12: val (fs1, others1, unifs2) = unifFields (fs1, others1, unifs2) adamc@12: val (fs2, others2, unifs1) = unifFields (fs2, others2, unifs1) adamc@12: adamc@12: val clear1 = case (fs1, others1) of adamc@12: ([], []) => true adamc@12: | _ => false adamc@12: val clear2 = case (fs2, others2) of adamc@12: ([], []) => true adamc@12: | _ => false adamc@12: val empty = (L'.CRecord (k, []), dummy) adamc@12: fun pairOffUnifs (unifs1, unifs2) = adamc@12: case (unifs1, unifs2) of adamc@12: ([], _) => adamc@12: if clear1 then adamc@12: List.app (fn (_, r) => r := SOME empty) unifs2 adamc@12: else adamc@12: raise CUnify' CRecordFailure adamc@12: | (_, []) => adamc@12: if clear2 then adamc@12: List.app (fn (_, r) => r := SOME empty) unifs1 adamc@12: else adamc@12: raise CUnify' CRecordFailure adamc@12: | ((c1, _) :: rest1, (_, r2) :: rest2) => adamc@12: (r2 := SOME c1; adamc@12: pairOffUnifs (rest1, rest2)) adamc@12: in adamc@12: pairOffUnifs (unifs1, unifs2) adamc@12: end adamc@12: adamc@34: and hnormCon env (cAll as (c, loc)) = adamc@11: case c of adamc@11: L'.CUnif (_, _, ref (SOME c)) => hnormCon env c adamc@11: adamc@11: | L'.CNamed xn => adamc@11: (case E.lookupCNamed env xn of adamc@11: (_, _, SOME c') => hnormCon env c' adamc@11: | _ => cAll) adamc@11: adamc@34: | L'.CModProj (n, ms, x) => adamc@34: let adamc@34: val (_, sgn) = E.lookupStrNamed env n adamc@34: val (str, sgn) = foldl (fn (m, (str, sgn)) => adamc@34: case E.projectStr env {sgn = sgn, str = str, field = m} of adamc@34: NONE => raise Fail "hnormCon: Unknown substructure" adamc@34: | SOME sgn => ((L'.StrProj (str, m), loc), sgn)) adamc@34: ((L'.StrVar n, loc), sgn) ms adamc@34: in adamc@34: case E.projectCon env {sgn = sgn, str = str, field = x} of adamc@34: NONE => raise Fail "kindof: Unknown con in structure" adamc@34: | SOME (_, NONE) => cAll adamc@34: | SOME (_, SOME c) => hnormCon env c adamc@34: end adamc@34: adamc@12: | L'.CApp (c1, c2) => adamc@12: (case hnormCon env c1 of adamc@12: (L'.CAbs (_, _, cb), _) => adamc@12: ((hnormCon env (subConInCon (0, c2) cb)) adamc@12: handle SynUnif => cAll) adamc@12: | _ => cAll) adamc@12: adamc@12: | L'.CConcat (c1, c2) => adamc@12: (case (hnormCon env c1, hnormCon env c2) of adamc@12: ((L'.CRecord (k, xcs1), loc), (L'.CRecord (_, xcs2), _)) => adamc@12: (L'.CRecord (k, xcs1 @ xcs2), loc) adamc@12: | _ => cAll) adamc@12: adamc@11: | _ => cAll adamc@11: adamc@12: and unifyCons' env c1 c2 = adamc@11: unifyCons'' env (hnormCon env c1) (hnormCon env c2) adamc@11: adamc@11: and unifyCons'' env (c1All as (c1, _)) (c2All as (c2, _)) = adamc@10: let adamc@10: fun err f = raise CUnify' (f (c1All, c2All)) adamc@12: adamc@12: fun isRecord () = unifyRecordCons env (c1All, c2All) adamc@10: in adamc@10: case (c1, c2) of adamc@10: (L'.TFun (d1, r1), L'.TFun (d2, r2)) => adamc@10: (unifyCons' env d1 d2; adamc@10: unifyCons' env r1 r2) adamc@10: | (L'.TCFun (expl1, x1, d1, r1), L'.TCFun (expl2, _, d2, r2)) => adamc@10: if expl1 <> expl2 then adamc@10: err CExplicitness adamc@10: else adamc@10: (unifyKinds d1 d2; adamc@10: unifyCons' (E.pushCRel env x1 d1) r1 r2) adamc@10: | (L'.TRecord r1, L'.TRecord r2) => unifyCons' env r1 r2 adamc@10: adamc@10: | (L'.CRel n1, L'.CRel n2) => adamc@10: if n1 = n2 then adamc@10: () adamc@10: else adamc@10: err CIncompatible adamc@10: | (L'.CNamed n1, L'.CNamed n2) => adamc@10: if n1 = n2 then adamc@10: () adamc@10: else adamc@10: err CIncompatible adamc@10: adamc@10: | (L'.CApp (d1, r1), L'.CApp (d2, r2)) => adamc@10: (unifyCons' env d1 d2; adamc@10: unifyCons' env r1 r2) adamc@10: | (L'.CAbs (x1, k1, c1), L'.CAbs (_, k2, c2)) => adamc@10: (unifyKinds k1 k2; adamc@10: unifyCons' (E.pushCRel env x1 k1) c1 c2) adamc@10: adamc@10: | (L'.CName n1, L'.CName n2) => adamc@10: if n1 = n2 then adamc@10: () adamc@10: else adamc@10: err CIncompatible adamc@10: adamc@34: | (L'.CModProj (n1, ms1, x1), L'.CModProj (n2, ms2, x2)) => adamc@34: if n1 = n2 andalso ms1 = ms2 andalso x1 = x2 then adamc@34: () adamc@34: else adamc@34: err CIncompatible adamc@34: adamc@10: | (L'.CError, _) => () adamc@10: | (_, L'.CError) => () adamc@10: adamc@10: | (L'.CUnif (_, _, ref (SOME c1All)), _) => unifyCons' env c1All c2All adamc@10: | (_, L'.CUnif (_, _, ref (SOME c2All))) => unifyCons' env c1All c2All adamc@10: adamc@10: | (L'.CUnif (k1, _, r1), L'.CUnif (k2, _, r2)) => adamc@10: if r1 = r2 then adamc@10: () adamc@10: else adamc@10: (unifyKinds k1 k2; adamc@10: r1 := SOME c2All) adamc@10: adamc@10: | (L'.CUnif (_, _, r), _) => adamc@10: if occursCon r c2All then adamc@10: err COccursCheckFailed adamc@10: else adamc@10: r := SOME c2All adamc@10: | (_, L'.CUnif (_, _, r)) => adamc@10: if occursCon r c1All then adamc@10: err COccursCheckFailed adamc@10: else adamc@10: r := SOME c1All adamc@10: adamc@12: | (L'.CRecord _, _) => isRecord () adamc@12: | (_, L'.CRecord _) => isRecord () adamc@12: | (L'.CConcat _, _) => isRecord () adamc@12: | (_, L'.CConcat _) => isRecord () adamc@12: adamc@10: | _ => err CIncompatible adamc@10: end adamc@10: adamc@12: and unifyCons env c1 c2 = adamc@10: unifyCons' env c1 c2 adamc@10: handle CUnify' err => raise CUnify (c1, c2, err) adamc@10: | KUnify args => raise CUnify (c1, c2, CKind args) adamc@10: adamc@10: datatype exp_error = adamc@10: UnboundExp of ErrorMsg.span * string adamc@34: | UnboundStrInExp of ErrorMsg.span * string adamc@10: | Unify of L'.exp * L'.con * L'.con * cunify_error adamc@11: | Unif of string * L'.con adamc@11: | WrongForm of string * L'.exp * L'.con adamc@10: adamc@10: fun expError env err = adamc@10: case err of adamc@10: UnboundExp (loc, s) => adamc@10: ErrorMsg.errorAt loc ("Unbound expression variable " ^ s) adamc@34: | UnboundStrInExp (loc, s) => adamc@34: ErrorMsg.errorAt loc ("Unbound structure " ^ s) adamc@10: | Unify (e, c1, c2, uerr) => adamc@10: (ErrorMsg.errorAt (#2 e) "Unification failure"; adamc@10: eprefaces' [("Expression", p_exp env e), adamc@10: ("Have con", p_con env c1), adamc@10: ("Need con", p_con env c2)]; adamc@10: cunifyError env uerr) adamc@11: | Unif (action, c) => adamc@11: (ErrorMsg.errorAt (#2 c) ("Unification variable blocks " ^ action); adamc@11: eprefaces' [("Con", p_con env c)]) adamc@11: | WrongForm (variety, e, t) => adamc@11: (ErrorMsg.errorAt (#2 e) ("Expression is not a " ^ variety); adamc@11: eprefaces' [("Expression", p_exp env e), adamc@11: ("Type", p_con env t)]) adamc@10: adamc@10: fun checkCon env e c1 c2 = adamc@10: unifyCons env c1 c2 adamc@10: handle CUnify (c1, c2, err) => adamc@10: expError env (Unify (e, c1, c2, err)) adamc@10: adamc@14: fun primType env p = adamc@56: case p of adamc@56: P.Int _ => !int adamc@56: | P.Float _ => !float adamc@56: | P.String _ => !string adamc@14: adamc@15: fun typeof env (e, loc) = adamc@15: case e of adamc@56: L'.EPrim p => primType env p adamc@15: | L'.ERel n => #2 (E.lookupERel env n) adamc@15: | L'.ENamed n => #2 (E.lookupENamed env n) adamc@34: | L'.EModProj (n, ms, x) => adamc@34: let adamc@34: val (_, sgn) = E.lookupStrNamed env n adamc@34: val (str, sgn) = foldl (fn (m, (str, sgn)) => adamc@34: case E.projectStr env {sgn = sgn, str = str, field = m} of adamc@34: NONE => raise Fail "kindof: Unknown substructure" adamc@34: | SOME sgn => ((L'.StrProj (str, m), loc), sgn)) adamc@34: ((L'.StrVar n, loc), sgn) ms adamc@34: in adamc@34: case E.projectVal env {sgn = sgn, str = str, field = x} of adamc@34: NONE => raise Fail "typeof: Unknown val in structure" adamc@34: | SOME t => t adamc@34: end adamc@34: adamc@15: | L'.EApp (e1, _) => adamc@15: (case #1 (typeof env e1) of adamc@15: L'.TFun (_, c) => c adamc@15: | _ => raise Fail "typeof: Bad EApp") adamc@26: | L'.EAbs (_, _, ran, _) => ran adamc@15: | L'.ECApp (e1, c) => adamc@15: (case #1 (typeof env e1) of adamc@15: L'.TCFun (_, _, _, c1) => subConInCon (0, c) c1 adamc@15: | _ => raise Fail "typeof: Bad ECApp") adamc@15: | L'.ECAbs (expl, x, k, e1) => (L'.TCFun (expl, x, k, typeof (E.pushCRel env x k) e1), loc) adamc@15: adamc@29: | L'.ERecord xes => (L'.TRecord (L'.CRecord (ktype, map (fn (x, _, t) => (x, t)) xes), loc), loc) adamc@15: | L'.EField (_, _, {field, ...}) => field adamc@15: adamc@15: | L'.EError => cerror adamc@15: adamc@15: fun elabHead env (e as (_, loc)) t = adamc@15: let adamc@15: fun unravel (t, e) = adamc@15: case hnormCon env t of adamc@15: (L'.TCFun (L'.Implicit, x, k, t'), _) => adamc@15: let adamc@15: val u = cunif k adamc@15: in adamc@15: unravel (subConInCon (0, u) t', adamc@15: (L'.ECApp (e, u), loc)) adamc@15: end adamc@15: | _ => (e, t) adamc@15: in adamc@15: unravel (t, e) adamc@15: end adamc@15: adamc@10: fun elabExp env (e, loc) = adamc@10: case e of adamc@10: L.EAnnot (e, t) => adamc@10: let adamc@10: val (e', et) = elabExp env e adamc@10: val (t', _) = elabCon env t adamc@10: in adamc@10: checkCon env e' et t'; adamc@10: (e', t') adamc@10: end adamc@10: adamc@56: | L.EPrim p => ((L'.EPrim p, loc), primType env p) adamc@34: | L.EVar ([], s) => adamc@10: (case E.lookupE env s of adamc@10: E.NotBound => adamc@10: (expError env (UnboundExp (loc, s)); adamc@10: (eerror, cerror)) adamc@10: | E.Rel (n, t) => ((L'.ERel n, loc), t) adamc@10: | E.Named (n, t) => ((L'.ENamed n, loc), t)) adamc@34: | L.EVar (m1 :: ms, s) => adamc@34: (case E.lookupStr env m1 of adamc@42: NONE => (expError env (UnboundStrInExp (loc, m1)); adamc@34: (eerror, cerror)) adamc@34: | SOME (n, sgn) => adamc@34: let adamc@34: val (str, sgn) = foldl (fn (m, (str, sgn)) => adamc@34: case E.projectStr env {sgn = sgn, str = str, field = m} of adamc@34: NONE => (conError env (UnboundStrInCon (loc, m)); adamc@34: (strerror, sgnerror)) adamc@34: | SOME sgn => ((L'.StrProj (str, m), loc), sgn)) adamc@34: ((L'.StrVar n, loc), sgn) ms adamc@34: adamc@34: val t = case E.projectVal env {sgn = sgn, str = str, field = s} of adamc@34: NONE => (expError env (UnboundExp (loc, s)); adamc@34: cerror) adamc@34: | SOME t => t adamc@34: in adamc@34: ((L'.EModProj (n, ms, s), loc), t) adamc@34: end) adamc@34: adamc@10: | L.EApp (e1, e2) => adamc@10: let adamc@10: val (e1', t1) = elabExp env e1 adamc@15: val (e1', t1) = elabHead env e1' t1 adamc@10: val (e2', t2) = elabExp env e2 adamc@10: adamc@10: val dom = cunif ktype adamc@10: val ran = cunif ktype adamc@10: val t = (L'.TFun (dom, ran), dummy) adamc@10: in adamc@10: checkCon env e1' t1 t; adamc@10: checkCon env e2' t2 dom; adamc@10: ((L'.EApp (e1', e2'), loc), ran) adamc@10: end adamc@10: | L.EAbs (x, to, e) => adamc@10: let adamc@10: val t' = case to of adamc@10: NONE => cunif ktype adamc@10: | SOME t => adamc@10: let adamc@10: val (t', tk) = elabCon env t adamc@10: in adamc@10: checkKind env t' tk ktype; adamc@10: t' adamc@10: end adamc@10: val (e', et) = elabExp (E.pushERel env x t') e adamc@10: in adamc@26: ((L'.EAbs (x, t', et, e'), loc), adamc@10: (L'.TFun (t', et), loc)) adamc@10: end adamc@10: | L.ECApp (e, c) => adamc@10: let adamc@10: val (e', et) = elabExp env e adamc@15: val (e', et) = elabHead env e' et adamc@10: val (c', ck) = elabCon env c adamc@10: in adamc@11: case #1 (hnormCon env et) of adamc@11: L'.CError => (eerror, cerror) adamc@11: | L'.TCFun (_, _, k, eb) => adamc@11: let adamc@11: val () = checkKind env c' ck k adamc@11: val eb' = subConInCon (0, c') eb adamc@11: handle SynUnif => (expError env (Unif ("substitution", eb)); adamc@11: cerror) adamc@11: in adamc@11: ((L'.ECApp (e', c'), loc), eb') adamc@11: end adamc@11: adamc@11: | L'.CUnif _ => adamc@11: (expError env (Unif ("application", et)); adamc@11: (eerror, cerror)) adamc@11: adamc@11: | _ => adamc@11: (expError env (WrongForm ("constructor function", e', et)); adamc@11: (eerror, cerror)) adamc@10: end adamc@11: | L.ECAbs (expl, x, k, e) => adamc@11: let adamc@11: val expl' = elabExplicitness expl adamc@11: val k' = elabKind k adamc@11: val (e', et) = elabExp (E.pushCRel env x k') e adamc@11: in adamc@11: ((L'.ECAbs (expl', x, k', e'), loc), adamc@11: (L'.TCFun (expl', x, k', et), loc)) adamc@11: end adamc@6: adamc@12: | L.ERecord xes => adamc@12: let adamc@12: val xes' = map (fn (x, e) => adamc@12: let adamc@12: val (x', xk) = elabCon env x adamc@12: val (e', et) = elabExp env e adamc@12: in adamc@12: checkKind env x' xk kname; adamc@12: (x', e', et) adamc@12: end) xes adamc@12: in adamc@29: ((L'.ERecord xes', loc), adamc@12: (L'.TRecord (L'.CRecord (ktype, map (fn (x', _, et) => (x', et)) xes'), loc), loc)) adamc@12: end adamc@12: adamc@12: | L.EField (e, c) => adamc@12: let adamc@12: val (e', et) = elabExp env e adamc@12: val (c', ck) = elabCon env c adamc@12: adamc@12: val ft = cunif ktype adamc@12: val rest = cunif ktype_record adamc@12: in adamc@12: checkKind env c' ck kname; adamc@12: checkCon env e' et (L'.TRecord (L'.CConcat ((L'.CRecord (ktype, [(c', ft)]), loc), rest), loc), loc); adamc@12: ((L'.EField (e', c', {field = ft, rest = rest}), loc), ft) adamc@12: end adamc@12: adamc@12: adamc@6: datatype decl_error = adamc@6: KunifsRemainKind of ErrorMsg.span * L'.kind adamc@6: | KunifsRemainCon of ErrorMsg.span * L'.con adamc@10: | KunifsRemainExp of ErrorMsg.span * L'.exp adamc@10: | CunifsRemainCon of ErrorMsg.span * L'.con adamc@10: | CunifsRemainExp of ErrorMsg.span * L'.exp adamc@6: adamc@6: fun declError env err = adamc@6: case err of adamc@6: KunifsRemainKind (loc, k) => adamc@6: (ErrorMsg.errorAt loc "Some kind unification variables are undetermined in kind"; adamc@6: eprefaces' [("Kind", p_kind k)]) adamc@6: | KunifsRemainCon (loc, c) => adamc@6: (ErrorMsg.errorAt loc "Some kind unification variables are undetermined in constructor"; adamc@6: eprefaces' [("Constructor", p_con env c)]) adamc@10: | KunifsRemainExp (loc, e) => adamc@10: (ErrorMsg.errorAt loc "Some kind unification variables are undetermined in expression"; adamc@10: eprefaces' [("Expression", p_exp env e)]) adamc@10: | CunifsRemainCon (loc, c) => adamc@10: (ErrorMsg.errorAt loc "Some constructor unification variables are undetermined in constructor"; adamc@10: eprefaces' [("Constructor", p_con env c)]) adamc@10: | CunifsRemainExp (loc, e) => adamc@10: (ErrorMsg.errorAt loc "Some constructor unification variables are undetermined in expression"; adamc@10: eprefaces' [("Expression", p_exp env e)]) adamc@6: adamc@31: datatype sgn_error = adamc@31: UnboundSgn of ErrorMsg.span * string adamc@31: | UnmatchedSgi of L'.sgn_item adamc@31: | SgiWrongKind of L'.sgn_item * L'.kind * L'.sgn_item * L'.kind * kunify_error adamc@31: | SgiWrongCon of L'.sgn_item * L'.con * L'.sgn_item * L'.con * cunify_error adamc@41: | SgnWrongForm of L'.sgn * L'.sgn adamc@42: | UnWhereable of L'.sgn * string adamc@31: adamc@31: fun sgnError env err = adamc@31: case err of adamc@31: UnboundSgn (loc, s) => adamc@31: ErrorMsg.errorAt loc ("Unbound signature variable " ^ s) adamc@31: | UnmatchedSgi (sgi as (_, loc)) => adamc@31: (ErrorMsg.errorAt loc "Unmatched signature item"; adamc@31: eprefaces' [("Item", p_sgn_item env sgi)]) adamc@31: | SgiWrongKind (sgi1, k1, sgi2, k2, kerr) => adamc@31: (ErrorMsg.errorAt (#2 sgi1) "Kind unification failure in signature matching:"; adamc@31: eprefaces' [("Item 1", p_sgn_item env sgi1), adamc@31: ("Item 2", p_sgn_item env sgi2), adamc@31: ("Kind 1", p_kind k1), adamc@31: ("Kind 2", p_kind k2)]; adamc@31: kunifyError kerr) adamc@31: | SgiWrongCon (sgi1, c1, sgi2, c2, cerr) => adamc@31: (ErrorMsg.errorAt (#2 sgi1) "Constructor unification failure in signature matching:"; adamc@31: eprefaces' [("Item 1", p_sgn_item env sgi1), adamc@31: ("Item 2", p_sgn_item env sgi2), adamc@31: ("Con 1", p_con env c1), adamc@31: ("Con 2", p_con env c2)]; adamc@31: cunifyError env cerr) adamc@41: | SgnWrongForm (sgn1, sgn2) => adamc@41: (ErrorMsg.errorAt (#2 sgn1) "Incompatible signatures:"; adamc@41: eprefaces' [("Sig 1", p_sgn env sgn1), adamc@41: ("Sig 2", p_sgn env sgn2)]) adamc@42: | UnWhereable (sgn, x) => adamc@42: (ErrorMsg.errorAt (#2 sgn) "Unavailable field for 'where'"; adamc@42: eprefaces' [("Signature", p_sgn env sgn), adamc@42: ("Field", PD.string x)]) adamc@31: adamc@31: datatype str_error = adamc@31: UnboundStr of ErrorMsg.span * string adamc@44: | NotFunctor of L'.sgn adamc@46: | FunctorRebind of ErrorMsg.span adamc@31: adamc@31: fun strError env err = adamc@31: case err of adamc@31: UnboundStr (loc, s) => adamc@31: ErrorMsg.errorAt loc ("Unbound structure variable " ^ s) adamc@44: | NotFunctor sgn => adamc@44: (ErrorMsg.errorAt (#2 sgn) "Application of non-functor"; adamc@44: eprefaces' [("Signature", p_sgn env sgn)]) adamc@46: | FunctorRebind loc => adamc@46: ErrorMsg.errorAt loc "Attempt to rebind functor" adamc@31: adamc@42: val hnormSgn = E.hnormSgn adamc@31: adamc@31: fun elabSgn_item ((sgi, loc), env) = adamc@31: let adamc@31: adamc@31: in adamc@31: resetKunif (); adamc@31: resetCunif (); adamc@31: case sgi of adamc@31: L.SgiConAbs (x, k) => adamc@31: let adamc@31: val k' = elabKind k adamc@31: adamc@31: val (env', n) = E.pushCNamed env x k' NONE adamc@31: in adamc@31: if ErrorMsg.anyErrors () then adamc@31: () adamc@31: else ( adamc@31: if kunifsInKind k' then adamc@31: declError env (KunifsRemainKind (loc, k')) adamc@31: else adamc@31: () adamc@31: ); adamc@31: adamc@31: ((L'.SgiConAbs (x, n, k'), loc), env') adamc@31: end adamc@31: adamc@31: | L.SgiCon (x, ko, c) => adamc@31: let adamc@31: val k' = case ko of adamc@31: NONE => kunif () adamc@31: | SOME k => elabKind k adamc@31: adamc@31: val (c', ck) = elabCon env c adamc@31: val (env', n) = E.pushCNamed env x k' (SOME c') adamc@31: in adamc@31: checkKind env c' ck k'; adamc@31: adamc@31: if ErrorMsg.anyErrors () then adamc@31: () adamc@31: else ( adamc@31: if kunifsInKind k' then adamc@31: declError env (KunifsRemainKind (loc, k')) adamc@31: else adamc@31: (); adamc@31: adamc@31: if kunifsInCon c' then adamc@31: declError env (KunifsRemainCon (loc, c')) adamc@31: else adamc@31: () adamc@31: ); adamc@31: adamc@31: ((L'.SgiCon (x, n, k', c'), loc), env') adamc@31: end adamc@31: adamc@31: | L.SgiVal (x, c) => adamc@31: let adamc@31: val (c', ck) = elabCon env c adamc@31: adamc@31: val (env', n) = E.pushENamed env x c' adamc@31: in adamc@31: unifyKinds ck ktype; adamc@31: adamc@31: if ErrorMsg.anyErrors () then adamc@31: () adamc@31: else ( adamc@31: if kunifsInCon c' then adamc@31: declError env (KunifsRemainCon (loc, c')) adamc@31: else adamc@31: () adamc@31: ); adamc@31: adamc@31: ((L'.SgiVal (x, n, c'), loc), env') adamc@31: end adamc@31: adamc@31: | L.SgiStr (x, sgn) => adamc@31: let adamc@31: val sgn' = elabSgn env sgn adamc@31: val (env', n) = E.pushStrNamed env x sgn' adamc@31: in adamc@31: ((L'.SgiStr (x, n, sgn'), loc), env') adamc@31: end adamc@31: adamc@31: end adamc@31: adamc@31: and elabSgn env (sgn, loc) = adamc@31: case sgn of adamc@31: L.SgnConst sgis => adamc@31: let adamc@31: val (sgis', _) = ListUtil.foldlMap elabSgn_item env sgis adamc@31: in adamc@31: (L'.SgnConst sgis', loc) adamc@31: end adamc@31: | L.SgnVar x => adamc@31: (case E.lookupSgn env x of adamc@31: NONE => adamc@31: (sgnError env (UnboundSgn (loc, x)); adamc@31: (L'.SgnError, loc)) adamc@31: | SOME (n, sgis) => (L'.SgnVar n, loc)) adamc@41: | L.SgnFun (m, dom, ran) => adamc@41: let adamc@41: val dom' = elabSgn env dom adamc@41: val (env', n) = E.pushStrNamed env m dom' adamc@41: val ran' = elabSgn env' ran adamc@41: in adamc@41: (L'.SgnFun (m, n, dom', ran'), loc) adamc@41: end adamc@42: | L.SgnWhere (sgn, x, c) => adamc@42: let adamc@42: val sgn' = elabSgn env sgn adamc@42: val (c', ck) = elabCon env c adamc@42: in adamc@42: case #1 (hnormSgn env sgn') of adamc@42: L'.SgnError => sgnerror adamc@42: | L'.SgnConst sgis => adamc@42: if List.exists (fn (L'.SgiConAbs (x, _, k), _) => adamc@42: (unifyKinds k ck; adamc@42: true) adamc@42: | _ => false) sgis then adamc@42: (L'.SgnWhere (sgn', x, c'), loc) adamc@42: else adamc@42: (sgnError env (UnWhereable (sgn', x)); adamc@42: sgnerror) adamc@42: | _ => (sgnError env (UnWhereable (sgn', x)); adamc@42: sgnerror) adamc@42: end adamc@31: adamc@31: fun sgiOfDecl (d, loc) = adamc@31: case d of adamc@31: L'.DCon (x, n, k, c) => SOME (L'.SgiCon (x, n, k, c), loc) adamc@31: | L'.DVal (x, n, t, _) => SOME (L'.SgiVal (x, n, t), loc) adamc@31: | L'.DSgn _ => NONE adamc@31: | L'.DStr (x, n, sgn, _) => SOME (L'.SgiStr (x, n, sgn), loc) adamc@48: | L'.DFfiStr (x, n, sgn) => SOME (L'.SgiStr (x, n, sgn), loc) adamc@31: adamc@35: fun subSgn env sgn1 (sgn2 as (_, loc2)) = adamc@35: case (#1 (hnormSgn env sgn1), #1 (hnormSgn env sgn2)) of adamc@31: (L'.SgnError, _) => () adamc@31: | (_, L'.SgnError) => () adamc@31: adamc@31: | (L'.SgnConst sgis1, L'.SgnConst sgis2) => adamc@31: let adamc@31: fun folder (sgi2All as (sgi, _), env) = adamc@31: let adamc@31: fun seek p = adamc@31: let adamc@31: fun seek env ls = adamc@31: case ls of adamc@31: [] => (sgnError env (UnmatchedSgi sgi2All); adamc@31: env) adamc@31: | h :: t => adamc@31: case p h of adamc@31: NONE => seek (E.sgiBinds env h) t adamc@31: | SOME env => env adamc@31: in adamc@31: seek env sgis1 adamc@31: end adamc@31: in adamc@31: case sgi of adamc@31: L'.SgiConAbs (x, n2, k2) => adamc@31: seek (fn sgi1All as (sgi1, _) => adamc@31: let adamc@41: fun found (x', n1, k1, co1) = adamc@41: if x = x' then adamc@41: let adamc@41: val () = unifyKinds k1 k2 adamc@41: handle KUnify (k1, k2, err) => adamc@41: sgnError env (SgiWrongKind (sgi1All, k1, sgi2All, k2, err)) adamc@41: val env = E.pushCNamedAs env x n1 k1 co1 adamc@41: in adamc@41: SOME (if n1 = n2 then adamc@41: env adamc@41: else adamc@41: E.pushCNamedAs env x n2 k2 (SOME (L'.CNamed n1, loc2))) adamc@41: end adamc@41: else adamc@41: NONE adamc@31: in adamc@31: case sgi1 of adamc@41: L'.SgiConAbs (x', n1, k1) => found (x', n1, k1, NONE) adamc@41: | L'.SgiCon (x', n1, k1, c1) => found (x', n1, k1, SOME c1) adamc@31: | _ => NONE adamc@31: end) adamc@31: adamc@31: | L'.SgiCon (x, n2, k2, c2) => adamc@31: seek (fn sgi1All as (sgi1, _) => adamc@31: case sgi1 of adamc@41: L'.SgiCon (x', n1, k1, c1) => adamc@41: if x = x' then adamc@41: let adamc@41: val () = unifyCons env c1 c2 adamc@41: handle CUnify (c1, c2, err) => adamc@41: sgnError env (SgiWrongCon (sgi1All, c1, sgi2All, c2, err)) adamc@41: in adamc@41: SOME (E.pushCNamedAs env x n2 k2 (SOME c2)) adamc@41: end adamc@41: else adamc@41: NONE adamc@31: | _ => NONE) adamc@31: adamc@32: | L'.SgiVal (x, n2, c2) => adamc@32: seek (fn sgi1All as (sgi1, _) => adamc@32: case sgi1 of adamc@41: L'.SgiVal (x', n1, c1) => adamc@41: if x = x' then adamc@41: let adamc@41: val () = unifyCons env c1 c2 adamc@41: handle CUnify (c1, c2, err) => adamc@41: sgnError env (SgiWrongCon (sgi1All, c1, sgi2All, c2, err)) adamc@41: in adamc@41: SOME env adamc@41: end adamc@41: else adamc@41: NONE adamc@32: | _ => NONE) adamc@32: adamc@33: | L'.SgiStr (x, n2, sgn2) => adamc@33: seek (fn sgi1All as (sgi1, _) => adamc@33: case sgi1 of adamc@41: L'.SgiStr (x', n1, sgn1) => adamc@41: if x = x' then adamc@41: (subSgn env sgn1 sgn2; adamc@41: SOME env) adamc@41: else adamc@41: NONE adamc@33: | _ => NONE) adamc@33: (* Add type equations between structures here some day. *) adamc@31: end adamc@31: in adamc@31: ignore (foldl folder env sgis2) adamc@31: end adamc@31: adamc@41: | (L'.SgnFun (m1, n1, dom1, ran1), L'.SgnFun (m2, n2, dom2, ran2)) => adamc@43: let adamc@43: val ran1 = adamc@43: if n1 = n2 then adamc@43: ran1 adamc@43: else adamc@43: subStrInSgn (n1, n2) ran1 adamc@43: in adamc@43: subSgn env dom2 dom1; adamc@43: subSgn (E.pushStrNamedAs env m2 n2 dom2) ran1 ran2 adamc@43: end adamc@41: adamc@41: | _ => sgnError env (SgnWrongForm (sgn1, sgn2)) adamc@41: adamc@35: fun selfify env {str, strs, sgn} = adamc@35: case #1 (hnormSgn env sgn) of adamc@35: L'.SgnError => sgn adamc@35: | L'.SgnVar _ => sgn adamc@35: adamc@35: | L'.SgnConst sgis => adamc@35: (L'.SgnConst (map (fn (L'.SgiConAbs (x, n, k), loc) => adamc@35: (L'.SgiCon (x, n, k, (L'.CModProj (str, strs, x), loc)), loc) adamc@35: | (L'.SgiStr (x, n, sgn), loc) => adamc@35: (L'.SgiStr (x, n, selfify env {str = str, strs = strs @ [x], sgn = sgn}), loc) adamc@35: | x => x) sgis), #2 sgn) adamc@41: | L'.SgnFun _ => sgn adamc@42: | L'.SgnWhere _ => sgn adamc@35: adamc@44: fun selfifyAt env {str, sgn} = adamc@44: let adamc@44: fun self (str, _) = adamc@44: case str of adamc@44: L'.StrVar x => SOME (x, []) adamc@44: | L'.StrProj (str, x) => adamc@44: (case self str of adamc@44: NONE => NONE adamc@44: | SOME (m, ms) => SOME (m, ms @ [x])) adamc@44: | _ => NONE adamc@44: in adamc@44: case self str of adamc@44: NONE => sgn adamc@44: | SOME (str, strs) => selfify env {sgn = sgn, str = str, strs = strs} adamc@44: end adamc@44: adamc@31: fun elabDecl ((d, loc), env) = adamc@30: let adamc@30: adamc@30: in adamc@30: resetKunif (); adamc@30: resetCunif (); adamc@30: case d of adamc@30: L.DCon (x, ko, c) => adamc@30: let adamc@30: val k' = case ko of adamc@30: NONE => kunif () adamc@30: | SOME k => elabKind k adamc@3: adamc@30: val (c', ck) = elabCon env c adamc@30: val (env', n) = E.pushCNamed env x k' (SOME c') adamc@30: in adamc@30: checkKind env c' ck k'; adamc@6: adamc@30: if ErrorMsg.anyErrors () then adamc@30: () adamc@30: else ( adamc@30: if kunifsInKind k' then adamc@30: declError env (KunifsRemainKind (loc, k')) adamc@30: else adamc@30: (); adamc@6: adamc@30: if kunifsInCon c' then adamc@30: declError env (KunifsRemainCon (loc, c')) adamc@30: else adamc@30: () adamc@30: ); adamc@6: adamc@31: ((L'.DCon (x, n, k', c'), loc), env') adamc@30: end adamc@30: | L.DVal (x, co, e) => adamc@30: let adamc@30: val (c', ck) = case co of adamc@30: NONE => (cunif ktype, ktype) adamc@30: | SOME c => elabCon env c adamc@10: adamc@30: val (e', et) = elabExp env e adamc@30: val (env', n) = E.pushENamed env x c' adamc@30: in adamc@30: checkCon env e' et c'; adamc@10: adamc@30: if ErrorMsg.anyErrors () then adamc@30: () adamc@30: else ( adamc@30: if kunifsInCon c' then adamc@30: declError env (KunifsRemainCon (loc, c')) adamc@30: else adamc@30: (); adamc@10: adamc@30: if cunifsInCon c' then adamc@30: declError env (CunifsRemainCon (loc, c')) adamc@30: else adamc@30: (); adamc@10: adamc@30: if kunifsInExp e' then adamc@30: declError env (KunifsRemainExp (loc, e')) adamc@30: else adamc@30: (); adamc@10: adamc@30: if cunifsInExp e' then adamc@30: declError env (CunifsRemainExp (loc, e')) adamc@30: else adamc@30: ()); adamc@10: adamc@31: ((L'.DVal (x, n, c', e'), loc), env') adamc@30: end adamc@30: adamc@31: | L.DSgn (x, sgn) => adamc@31: let adamc@31: val sgn' = elabSgn env sgn adamc@31: val (env', n) = E.pushSgnNamed env x sgn' adamc@31: in adamc@31: ((L'.DSgn (x, n, sgn'), loc), env') adamc@31: end adamc@31: adamc@31: | L.DStr (x, sgno, str) => adamc@31: let adamc@31: val formal = Option.map (elabSgn env) sgno adamc@31: val (str', actual) = elabStr env str adamc@31: adamc@31: val sgn' = case formal of adamc@44: NONE => selfifyAt env {str = str', sgn = actual} adamc@31: | SOME formal => adamc@31: (subSgn env actual formal; adamc@31: formal) adamc@31: adamc@31: val (env', n) = E.pushStrNamed env x sgn' adamc@31: in adamc@46: case #1 (hnormSgn env sgn') of adamc@46: L'.SgnFun _ => adamc@46: (case #1 str' of adamc@46: L'.StrFun _ => () adamc@46: | _ => strError env (FunctorRebind loc)) adamc@46: | _ => (); adamc@46: adamc@31: ((L'.DStr (x, n, sgn', str'), loc), env') adamc@31: end adamc@48: adamc@48: | L.DFfiStr (x, sgn) => adamc@48: let adamc@48: val sgn' = elabSgn env sgn adamc@48: adamc@48: val (env', n) = E.pushStrNamed env x sgn' adamc@48: in adamc@48: ((L'.DFfiStr (x, n, sgn'), loc), env') adamc@48: end adamc@30: end adamc@3: adamc@31: and elabStr env (str, loc) = adamc@31: case str of adamc@31: L.StrConst ds => adamc@31: let adamc@31: val (ds', env') = ListUtil.foldlMap elabDecl env ds adamc@31: val sgis = List.mapPartial sgiOfDecl ds' adamc@31: in adamc@31: ((L'.StrConst ds', loc), (L'.SgnConst sgis, loc)) adamc@31: end adamc@31: | L.StrVar x => adamc@31: (case E.lookupStr env x of adamc@31: NONE => adamc@31: (strError env (UnboundStr (loc, x)); adamc@31: (strerror, sgnerror)) adamc@31: | SOME (n, sgn) => ((L'.StrVar n, loc), sgn)) adamc@34: | L.StrProj (str, x) => adamc@34: let adamc@34: val (str', sgn) = elabStr env str adamc@34: in adamc@34: case E.projectStr env {str = str', sgn = sgn, field = x} of adamc@34: NONE => (strError env (UnboundStr (loc, x)); adamc@34: (strerror, sgnerror)) adamc@34: | SOME sgn => ((L'.StrProj (str', x), loc), sgn) adamc@34: end adamc@41: | L.StrFun (m, dom, ranO, str) => adamc@41: let adamc@41: val dom' = elabSgn env dom adamc@41: val (env', n) = E.pushStrNamed env m dom' adamc@41: val (str', actual) = elabStr env' str adamc@41: adamc@41: val formal = adamc@41: case ranO of adamc@41: NONE => actual adamc@41: | SOME ran => adamc@41: let adamc@42: val ran' = elabSgn env' ran adamc@41: in adamc@41: subSgn env' actual ran'; adamc@41: ran' adamc@41: end adamc@41: in adamc@41: ((L'.StrFun (m, n, dom', formal, str'), loc), adamc@41: (L'.SgnFun (m, n, dom', formal), loc)) adamc@41: end adamc@44: | L.StrApp (str1, str2) => adamc@44: let adamc@44: val (str1', sgn1) = elabStr env str1 adamc@44: val (str2', sgn2) = elabStr env str2 adamc@44: in adamc@44: case #1 (hnormSgn env sgn1) of adamc@44: L'.SgnError => (strerror, sgnerror) adamc@44: | L'.SgnFun (m, n, dom, ran) => adamc@44: (subSgn env sgn2 dom; adamc@44: case #1 (hnormSgn env ran) of adamc@44: L'.SgnError => (strerror, sgnerror) adamc@44: | L'.SgnConst sgis => adamc@44: ((L'.StrApp (str1', str2'), loc), adamc@44: (L'.SgnConst ((L'.SgiStr (m, n, selfifyAt env {str = str2', sgn = sgn2}), loc) :: sgis), loc)) adamc@44: | _ => raise Fail "Unable to hnormSgn in functor application") adamc@44: | _ => (strError env (NotFunctor sgn1); adamc@44: (strerror, sgnerror)) adamc@44: end adamc@31: adamc@56: fun elabFile basis env file = adamc@56: let adamc@56: val sgn = elabSgn env (L.SgnConst basis, ErrorMsg.dummySpan) adamc@56: val (env', basis_n) = E.pushStrNamed env "Basis" sgn adamc@56: adamc@56: val (ds, env') = adamc@56: case #1 (hnormSgn env' sgn) of adamc@56: L'.SgnConst sgis => adamc@56: ListUtil.foldlMap (fn ((sgi, loc), env') => adamc@56: case sgi of adamc@56: L'.SgiConAbs (x, n, k) => adamc@56: ((L'.DCon (x, n, k, (L'.CModProj (basis_n, [], x), loc)), loc), adamc@56: E.pushCNamedAs env' x n k NONE) adamc@56: | L'.SgiCon (x, n, k, c) => adamc@56: ((L'.DCon (x, n, k, (L'.CModProj (basis_n, [], x), loc)), loc), adamc@56: E.pushCNamedAs env' x n k (SOME c)) adamc@56: | L'.SgiVal (x, n, t) => adamc@56: ((L'.DVal (x, n, t, (L'.EModProj (basis_n, [], x), loc)), loc), adamc@56: E.pushENamedAs env' x n t) adamc@56: | L'.SgiStr (x, n, sgn) => adamc@56: ((L'.DStr (x, n, sgn, (L'.StrProj ((L'.StrVar basis_n, loc), x), loc)), loc), adamc@56: E.pushStrNamedAs env' x n sgn)) adamc@56: env' sgis adamc@56: | _ => raise Fail "Non-constant Basis signature" adamc@56: adamc@56: fun discoverC r x = adamc@56: case E.lookupC env' x of adamc@56: E.NotBound => raise Fail ("Constructor " ^ x ^ " unbound in Basis") adamc@56: | E.Rel _ => raise Fail ("Constructor " ^ x ^ " bound relatively in Basis") adamc@56: | E.Named (n, (_, loc)) => r := (L'.CNamed n, loc) adamc@56: adamc@56: val () = discoverC int "int" adamc@56: val () = discoverC float "float" adamc@56: val () = discoverC string "string" adamc@56: adamc@56: val (file, _) = ListUtil.foldlMap elabDecl env' file adamc@56: in adamc@56: (L'.DFfiStr ("Basis", basis_n, sgn), ErrorMsg.dummySpan) :: ds @ file adamc@56: end adamc@2: adamc@2: end