From 2b69638e128d6c8f2f308a3a46d9ed1a28412820 Mon Sep 17 00:00:00 2001 From: NanoTech Date: Fri, 9 Dec 2016 00:31:07 -0600 Subject: normalize: Take the input Expr by reference --- src/core.rs | 75 +++++++++++++++++++++++++++++++------------------------- src/main.rs | 2 +- src/typecheck.rs | 34 ++++++++++++------------- 3 files changed, 60 insertions(+), 51 deletions(-) (limited to 'src') diff --git a/src/core.rs b/src/core.rs index 2a0ae1f..5a521b5 100644 --- a/src/core.rs +++ b/src/core.rs @@ -513,6 +513,15 @@ fn add_ui(u: usize, i: isize) -> usize { } } +fn map_record_value<'a, I, K, V, U, F>(it: I, f: F) -> HashMap + where I: IntoIterator, + K: Eq + ::std::hash::Hash + Copy + 'a, + V: 'a, + F: Fn(&V) -> U +{ + it.into_iter().map(|(&k, v)| (k, f(v))).collect() +} + /// `shift` is used by both normalization and type-checking to avoid variable /// capture by shifting variable indices /// @@ -670,11 +679,11 @@ shift d v (OptionalLit a b) = OptionalLit a' b' b' = fmap (shift d v) b */ &Record(ref a) => - Record(a.iter().map(|(&k, val)| (k, shift(d, v, val))).collect()), + Record(map_record_value(a, |val| shift(d, v, val))), &RecordLit(ref a) => - RecordLit(a.iter().map(|(&k, val)| (k, shift(d, v, val))).collect()), + RecordLit(map_record_value(a, |val| shift(d, v, val))), &Union(ref a) => - Union(a.iter().map(|(&k, val)| (k, shift(d, v, val))).collect()), + Union(map_record_value(a, |val| shift(d, v, val))), /* shift d v (UnionLit a b c) = UnionLit a b' c' where @@ -753,8 +762,8 @@ pub fn subst<'i, S, T, A>(v: V<'i>, e: &Expr<'i, S, A>, b: &Expr<'i, T, A>) -> E let b2 = b.iter().map(|be| subst(v, e, be)).collect(); ListLit(bx(a2), b2) } - &Record(ref kts) => Record(kts.iter().map(|(&k, t)| (k, subst(v, e, t))).collect()), - &RecordLit(ref kvs) => Record(kvs.iter().map(|(&k, val)| (k, subst(v, e, val))).collect()), + &Record(ref kts) => Record(map_record_value(kts, |t| subst(v, e, t))), + &RecordLit(ref kvs) => Record(map_record_value(kvs, |val| subst(v, e, val))), &Field(ref a, b) => Field(bx(subst(v, e, a)), b), &Note(_, ref b) => subst(v, e, b), b => panic!("Unimplemented subst case: {:?}", b), @@ -770,7 +779,7 @@ pub fn subst<'i, S, T, A>(v: V<'i>, e: &Expr<'i, S, A>, b: &Expr<'i, T, A>) -> E /// However, `normalize` will not fail if the expression is ill-typed and will /// leave ill-typed sub-expressions unevaluated. /// -pub fn normalize(e: Expr) -> Expr +pub fn normalize<'i, S, T, A>(e: &Expr<'i, S, A>) -> Expr<'i, T, A> where S: Clone + fmt::Debug, T: Clone + fmt::Debug, A: Clone + fmt::Debug, @@ -778,27 +787,27 @@ pub fn normalize(e: Expr) -> Expr use BuiltinValue::*; use Expr::*; match e { - Const(k) => Const(k), - Var(v) => Var(v), - Lam(x, tA, b) => { - let tA2 = normalize(*tA); - let b2 = normalize(*b); + &Const(k) => Const(k), + &Var(v) => Var(v), + &Lam(x, ref tA, ref b) => { + let tA2 = normalize(tA); + let b2 = normalize(b); Lam(x, bx(tA2), bx(b2)) } - Pi(x, tA, tB) => { - let tA2 = normalize(*tA); - let tB2 = normalize(*tB); + &Pi(x, ref tA, ref tB) => { + let tA2 = normalize(tA); + let tB2 = normalize(tB); pi(x, tA2, tB2) } - App(f, a) => match normalize::(*f) { + &App(ref f, ref a) => match normalize::(f) { Lam(x, _A, b) => { // Beta reduce let vx0 = V(x, 0); - let a2 = shift::( 1, vx0, &a); + let a2 = shift::( 1, vx0, a); let b2 = subst::(vx0, &a2, &b); let b3 = shift::(-1, vx0, &b2); - normalize(b3) + normalize(&b3) } - f2 => match (f2, normalize::(*a)) { + f2 => match (f2, normalize::(a)) { /* -- fold/build fusion for `List` App (App ListBuild _) (App (App ListFold _) e') -> normalize e' @@ -890,31 +899,31 @@ pub fn normalize(e: Expr) -> Expr (f2, a2) => app(f2, a2), } }, - Let(f, _, ref r, ref b) => { + &Let(f, _, ref r, ref b) => { let r2 = shift::<_, S, _>( 1, V(f, 0), r); let b2 = subst(V(f, 0), &r2, b); let b3 = shift::<_, T, _>(-1, V(f, 0), &b2); - normalize(b3) + normalize(&b3) } - NaturalLit(n) => NaturalLit(n), - NaturalPlus(x, y) => match (normalize(*x), normalize(*y)) { + &NaturalLit(n) => NaturalLit(n), + &NaturalPlus(ref x, ref y) => match (normalize(x), normalize(y)) { (NaturalLit(xn), NaturalLit(yn)) => NaturalLit(xn + yn), (x2, y2) => NaturalPlus(bx(x2), bx(y2)), }, - IntegerLit(n) => IntegerLit(n), - ListLit(t, es) => { - let t2 = normalize(*t); - let es2 = es.into_iter().map(normalize).collect(); + &IntegerLit(n) => IntegerLit(n), + &ListLit(ref t, ref es) => { + let t2 = normalize(t); + let es2 = es.iter().map(normalize).collect(); ListLit(bx(t2), es2) } - Record(kts) => Record(kts.into_iter().map(|(k, t)| (k, normalize(t))).collect()), - RecordLit(kvs) => Record(kvs.into_iter().map(|(k, v)| (k, normalize(v))).collect()), - BuiltinType(t) => BuiltinType(t), - BuiltinValue(v) => BuiltinValue(v), - Field(r, x) => match normalize(*r) { - RecordLit(kvs) => match kvs.get(x).cloned() { + &Record(ref kts) => Record(map_record_value(kts, normalize)), + &RecordLit(ref kvs) => Record(map_record_value(kvs, normalize)), + &BuiltinType(t) => BuiltinType(t), + &BuiltinValue(v) => BuiltinValue(v), + &Field(ref r, x) => match normalize(r) { + RecordLit(kvs) => match kvs.get(x) { Some(r2) => normalize(r2), - None => Field(bx(RecordLit(kvs.into_iter().map(|(k, v)| (k, normalize(v))).collect())), x), + None => Field(bx(RecordLit(map_record_value(&kvs, normalize))), x), }, r2 => Field(bx(r2), x), }, diff --git a/src/main.rs b/src/main.rs index a4b5408..52a7d9e 100644 --- a/src/main.rs +++ b/src/main.rs @@ -98,7 +98,7 @@ fn main() { }; println!("{}", type_expr); println!(""); - println!("{}", normalize::<_, X, _>(*expr)); + println!("{}", normalize::<_, X, _>(&expr)); /* typeExpr <- case Dhall.TypeCheck.typeOf expr' of Left err -> Control.Exception.throwIO err diff --git a/src/typecheck.rs b/src/typecheck.rs index 6fa9747..ac7e30e 100644 --- a/src/typecheck.rs +++ b/src/typecheck.rs @@ -123,7 +123,7 @@ fn prop_equal(eL0: &Expr, eR0: &Expr) -> bool } } let mut ctx = vec![]; - go::(&mut ctx, &normalize(eL0.clone()), &normalize(eR0.clone())) + go::(&mut ctx, &normalize(eL0), &normalize(eR0)) } @@ -155,14 +155,14 @@ pub fn type_with<'i, S>(ctx: &Context<'i, Expr<'i, S, X>>, Ok(p) } &Pi(ref x, ref tA, ref tB) => { - let tA2 = normalize::(type_with(ctx, tA)?); + let tA2 = normalize::(&type_with(ctx, tA)?); let kA = match tA2 { Const(k) => k, _ => return Err(TypeError::new(ctx, e, InvalidInputType((**tA).clone()))), }; let ctx2 = ctx.insert(x, (**tA).clone()).map(|e| core::shift(1, V(x, 0), e)); - let tB = normalize(type_with(&ctx2, tB)?); + let tB = normalize(&type_with(&ctx2, tB)?); let kB = match tB { Const(k) => k, _ => return Err(TypeError::new(&ctx2, e, InvalidOutputType(tB))), @@ -174,7 +174,7 @@ pub fn type_with<'i, S>(ctx: &Context<'i, Expr<'i, S, X>>, } } &App(ref f, ref a) => { - let tf = normalize(type_with(ctx, f)?); + let tf = normalize(&type_with(ctx, f)?); let (x, tA, tB) = match tf { Pi(x, tA, tB) => (x, tA, tB), _ => return Err(TypeError::new(ctx, e, NotAFunction((**f).clone(), tf))), @@ -187,14 +187,14 @@ pub fn type_with<'i, S>(ctx: &Context<'i, Expr<'i, S, X>>, let tB3 = shift::(-1, vx0, &tB2); Ok(tB3) } else { - let nf_A = normalize(*tA); - let nf_A2 = normalize(tA2); + let nf_A = normalize(&tA); + let nf_A2 = normalize(&tA2); Err(TypeError::new(ctx, e, TypeMismatch((**f).clone(), nf_A, (**a).clone(), nf_A2))) } } &Let(ref f, ref mt, ref r, ref b) => { let tR = type_with(ctx, r)?; - let ttR = normalize::(type_with(ctx, &tR)?); + let ttR = normalize::(&type_with(ctx, &tR)?); let kR = match ttR { Const(k) => k, // Don't bother to provide a `let`-specific version of this error @@ -204,7 +204,7 @@ pub fn type_with<'i, S>(ctx: &Context<'i, Expr<'i, S, X>>, let ctx2 = ctx.insert(f, tR.clone()); let tB = type_with(&ctx2, b)?; - let ttB = normalize::(type_with(ctx, &tB)?); + let ttB = normalize::(&type_with(ctx, &tB)?); let kB = match ttB { Const(k) => k, // Don't bother to provide a `let`-specific version of this error @@ -217,8 +217,8 @@ pub fn type_with<'i, S>(ctx: &Context<'i, Expr<'i, S, X>>, } if let &Some(ref t) = mt { - let nf_t = normalize((**t).clone()); - let nf_tR = normalize(tR.clone()); + let nf_t = normalize(t); + let nf_tR = normalize(&tR); if !prop_equal(&nf_tR, &nf_t) { return Err(TypeError::new(ctx, &e, AnnotMismatch((**r).clone(), nf_t, nf_tR))); } @@ -246,13 +246,13 @@ type_with ctx e@(Annot x t ) = do }), &BoolLit(_) => Ok(BuiltinType(Bool)), &BoolAnd(ref l, ref r) => { - let tl = normalize(type_with(ctx, l)?); + let tl = normalize(&type_with(ctx, l)?); match tl { BuiltinType(Bool) => {} _ => return Err(TypeError::new(ctx, e, CantAnd((**l).clone(), tl))), } - let tr = normalize(type_with(ctx, r)?); + let tr = normalize(&type_with(ctx, r)?); match tr { BuiltinType(Bool) => {} _ => return Err(TypeError::new(ctx, e, CantAnd((**r).clone(), tr))), @@ -339,13 +339,13 @@ type_with _ NaturalBuild = do &BuiltinValue(NaturalEven) => Ok(pi("_", Natural, Bool)), &BuiltinValue(NaturalOdd) => Ok(pi("_", Natural, Bool)), &NaturalPlus(ref l, ref r) => { - let tl = normalize(type_with(ctx, l)?); + let tl = normalize(&type_with(ctx, l)?); match tl { BuiltinType(Natural) => {} _ => return Err(TypeError::new(ctx, e, CantAdd((**l).clone(), tl))), } - let tr = normalize(type_with(ctx, r)?); + let tr = normalize(&type_with(ctx, r)?); match tr { BuiltinType(Natural) => {} _ => return Err(TypeError::new(ctx, e, CantAdd((**r).clone(), tr))), @@ -455,7 +455,7 @@ type_with _ OptionalFold = do */ &Record(ref kts) => { for (k, t) in kts { - let s = normalize::(type_with(ctx, t)?); + let s = normalize::(&type_with(ctx, t)?); match s { Const(Type) => {} _ => return Err(TypeError::new(ctx, e, InvalidFieldType((*k).to_owned(), (*t).clone()))), @@ -466,7 +466,7 @@ type_with _ OptionalFold = do &RecordLit(ref kvs) => { let kts = kvs.iter().map(|(&k, v)| { let t = type_with(ctx, v)?; - let s = normalize::(type_with(ctx, &t)?); + let s = normalize::(&type_with(ctx, &t)?); match s { Const(Type) => {} _ => return Err(TypeError::new(ctx, e, InvalidField((*k).to_owned(), (*v).clone()))), @@ -557,7 +557,7 @@ type_with ctx e@(Merge kvsX kvsY t) = do return t */ &Field(ref r, x) => { - let t = normalize(type_with(ctx, r)?); + let t = normalize(&type_with(ctx, r)?); match &t { &Record(ref kts) => kts.get(x).cloned().ok_or_else(|| TypeError::new(ctx, e, MissingField(x.to_owned(), t.clone()))), -- cgit v1.2.3