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@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@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@3: 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@3: | 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@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@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@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@12: and hnormCon env (cAll as (c, _)) = 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@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@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@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@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@14: let adamc@14: val s = case p of adamc@14: P.Int _ => "int" adamc@14: | P.Float _ => "float" adamc@14: | P.String _ => "string" adamc@14: in adamc@14: case E.lookupC env s of adamc@14: E.NotBound => raise Fail ("Primitive type " ^ s ^ " unbound") adamc@14: | E.Rel _ => raise Fail ("Primitive type " ^ s ^ " bound as relative") adamc@14: | E.Named (n, (L'.KType, _)) => L'.CNamed n adamc@14: | E.Named _ => raise Fail ("Primitive type " ^ s ^ " bound at non-Type kind") adamc@14: end adamc@14: adamc@15: fun typeof env (e, loc) = adamc@15: case e of adamc@15: L'.EPrim p => (primType env p, loc) adamc@15: | L'.ERel n => #2 (E.lookupERel env n) adamc@15: | L'.ENamed n => #2 (E.lookupENamed env n) 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@15: | L'.EAbs (x, t, e1) => (L'.TFun (t, typeof (E.pushERel env x t) e1), loc) 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@15: | L'.ERecord xes => (L'.TRecord (L'.CRecord (ktype, map (fn (x, e) => (x, typeof env e)) 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@14: | L.EPrim p => ((L'.EPrim p, loc), (primType env p, loc)) adamc@10: | 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@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@10: ((L'.EAbs (x, t', 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@12: ((L'.ERecord (map (fn (x', e', _) => (x', e')) 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@3: fun elabDecl env (d, loc) = adamc@5: (resetKunif (); adamc@12: resetCunif (); adamc@5: case d of adamc@5: L.DCon (x, ko, c) => adamc@5: let adamc@5: val k' = case ko of adamc@5: NONE => kunif () adamc@5: | SOME k => elabKind k adamc@3: adamc@5: val (c', ck) = elabCon env c adamc@11: val (env', n) = E.pushCNamed env x k' (SOME c') adamc@5: in adamc@5: checkKind env c' ck k'; adamc@6: adamc@15: if ErrorMsg.anyErrors () then adamc@15: () adamc@15: else ( adamc@15: if kunifsInKind k' then adamc@15: declError env (KunifsRemainKind (loc, k')) adamc@15: else adamc@15: (); adamc@6: adamc@15: if kunifsInCon c' then adamc@15: declError env (KunifsRemainCon (loc, c')) adamc@15: else adamc@15: () adamc@15: ); adamc@6: adamc@5: (env', adamc@5: (L'.DCon (x, n, k', c'), loc)) adamc@10: end adamc@10: | L.DVal (x, co, e) => adamc@10: let adamc@10: val (c', ck) = case co of adamc@10: NONE => (cunif ktype, ktype) adamc@10: | SOME c => elabCon env c adamc@10: adamc@10: val (e', et) = elabExp env e adamc@10: val (env', n) = E.pushENamed env x c' adamc@10: in adamc@10: checkCon env e' et c'; adamc@10: adamc@15: if ErrorMsg.anyErrors () then adamc@15: () adamc@15: else ( adamc@15: if kunifsInCon c' then adamc@15: declError env (KunifsRemainCon (loc, c')) adamc@15: else adamc@15: (); adamc@10: adamc@15: if cunifsInCon c' then adamc@15: declError env (CunifsRemainCon (loc, c')) adamc@15: else adamc@15: (); adamc@10: adamc@15: if kunifsInExp e' then adamc@15: declError env (KunifsRemainExp (loc, e')) adamc@15: else adamc@15: (); adamc@10: adamc@15: if cunifsInExp e' then adamc@15: declError env (CunifsRemainExp (loc, e')) adamc@15: else adamc@15: ()); adamc@10: adamc@10: (env', adamc@10: (L'.DVal (x, n, c', e'), loc)) adamc@5: end) adamc@3: adamc@5: fun elabFile env ds = adamc@5: ListUtil.mapfoldl (fn (d, env) => elabDecl env d) env ds adamc@2: adamc@2: end