Merge pull request #48 from Nadrieril/exprf

Move recursion out of Expr for enhanced genericity

14 files changed, 830 insertions, 705 deletions

diff --git a/dhall/compare.fish b/dhall/compare.fish
deleted file mode 100755
index 154f06a..0000000
--- a/dhall/compare.fish
+++ /dev/null
@@ -1,9 +0,0 @@
-#!/usr/bin/env fish
-
-set dhall_hs_path ../dhall
-set dhall_hs $dhall_hs_path/.stack-work/install/**/bin/dhall
-set dhall_rs target/debug/dhall
-set input_file $argv[1]
-diff -u \
-    --label "dhall-hs < $input_file" (eval $dhall_hs < $input_file ^&1 | psub) \
-    --label "dhall-rs < $input_file" (eval $dhall_rs < $input_file ^&1 | psub)
diff --git a/dhall/src/binary.rs b/dhall/src/binary.rs
index 235a55b..1ba1873 100644
--- a/dhall/src/binary.rs
+++ b/dhall/src/binary.rs
@@ -1,9 +1,8 @@
 use dhall_core::*;
 use itertools::*;
 use serde_cbor::value::value as cbor;
-use std::rc::Rc;
 
-type ParsedExpr = Rc<Expr<X, Import>>;
+type ParsedExpr = SubExpr<X, Import>;
 
 #[derive(Debug)]
 pub enum DecodeError {
@@ -21,10 +20,10 @@ pub fn decode(data: &[u8]) -> Result<ParsedExpr, DecodeError> {
 fn cbor_value_to_dhall(data: &cbor::Value) -> Result<ParsedExpr, DecodeError> {
     use cbor::Value::*;
     use dhall_core::{BinOp, Builtin, Const};
-    use Expr::*;
+    use ExprF::*;
     Ok(rc(match data {
         String(s) => match Builtin::parse(s) {
-            Some(b) => Expr::Builtin(b),
+            Some(b) => ExprF::Builtin(b),
             None => match s.as_str() {
                 "True" => BoolLit(true),
                 "False" => BoolLit(false),
diff --git a/dhall/src/imports.rs b/dhall/src/imports.rs
index 8df4e97..96268ca 100644
--- a/dhall/src/imports.rs
+++ b/dhall/src/imports.rs
@@ -79,9 +79,9 @@ pub fn load_dhall_file(
         let resolve = |import: &Import| -> Expr<X, X> {
             resolve_import(import, &root).unwrap()
         };
-        expr.map_embed(&resolve).squash_embed()
+        expr.as_ref().map_embed(&resolve).squash_embed()
     } else {
-        panic_imports(&expr)
+        panic_imports(expr.as_ref())
     };
     Ok(expr)
 }
diff --git a/dhall/src/main.rs b/dhall/src/main.rs
index 1a2e309..77f558c 100644
--- a/dhall/src/main.rs
+++ b/dhall/src/main.rs
@@ -1,6 +1,5 @@
 use std::error::Error;
 use std::io::{self, Read};
-use std::rc::Rc;
 use term_painter::ToStyle;
 
 use dhall::*;
@@ -66,7 +65,7 @@ fn main() {
         }
     };
 
-    let expr: Rc<Expr<_, _>> = rc(imports::panic_imports(&expr));
+    let expr: SubExpr<_, _> = rc(imports::panic_imports(expr.as_ref()));
 
     let type_expr = match typecheck::type_of(expr.clone()) {
         Err(e) => {
diff --git a/dhall/src/normalize.rs b/dhall/src/normalize.rs
index d9bd08a..7574c2f 100644
--- a/dhall/src/normalize.rs
+++ b/dhall/src/normalize.rs
@@ -2,84 +2,61 @@
 use dhall_core::*;
 use dhall_generator::dhall_expr;
 use std::fmt;
-use std::rc::Rc;
 
-fn apply_builtin<S, A>(
-    b: Builtin,
-    mut args: Vec<SubExpr<S, A>>,
-) -> SubExpr<S, A>
+fn apply_builtin<S, A>(b: Builtin, args: &Vec<Expr<S, A>>) -> WhatNext<S, A>
 where
-    S: fmt::Debug,
-    A: fmt::Debug,
+    S: fmt::Debug + Clone,
+    A: fmt::Debug + Clone,
 {
     use dhall_core::Builtin::*;
-    use dhall_core::Expr::*;
-    let f = rc(Builtin(b));
-    // How many arguments a builtin needs, and which argument
-    // should be normalized and pattern-matched
-    let (len_consumption, arg_to_eval) = match b {
-        OptionalSome => (1, None),
-        OptionalNone => (1, None),
-        NaturalIsZero => (1, Some(0)),
-        NaturalEven => (1, Some(0)),
-        NaturalOdd => (1, Some(0)),
-        NaturalToInteger => (1, Some(0)),
-        NaturalShow => (1, Some(0)),
-        ListLength => (2, Some(1)),
-        ListHead => (2, Some(1)),
-        ListLast => (2, Some(1)),
-        ListReverse => (2, Some(1)),
-        ListIndexed => (2, Some(1)),
-        ListBuild => (2, Some(1)),
-        OptionalBuild => (2, Some(1)),
-        ListFold => (5, Some(1)),
-        OptionalFold => (5, Some(1)),
-        NaturalBuild => (1, Some(0)),
-        NaturalFold => (4, Some(0)),
-        _ => (0, None),
-    };
-    // Abort if not enough arguments present
-    if len_consumption > args.len() {
-        return rc(App(f, args));
-    }
-    // Normalize the important argument
-    if let Some(i) = arg_to_eval {
-        args[i] = Rc::clone(&normalize_whnf(&args[i]));
-    }
-    let evaled_arg = arg_to_eval.map(|i| args[i].as_ref());
-
-    let ret = match (b, evaled_arg, args.as_slice()) {
-        (OptionalSome, _, [x, ..]) => rc(NEOptionalLit(Rc::clone(x))),
-        (OptionalNone, _, [t, ..]) => rc(EmptyOptionalLit(Rc::clone(t))),
-        (NaturalIsZero, Some(NaturalLit(n)), _) => rc(BoolLit(*n == 0)),
-        (NaturalEven, Some(NaturalLit(n)), _) => rc(BoolLit(*n % 2 == 0)),
-        (NaturalOdd, Some(NaturalLit(n)), _) => rc(BoolLit(*n % 2 != 0)),
-        (NaturalToInteger, Some(NaturalLit(n)), _) => {
-            rc(IntegerLit(*n as isize))
+    use dhall_core::ExprF::*;
+    use WhatNext::*;
+    let (ret, rest) = match (b, args.as_slice()) {
+        (OptionalSome, [x, rest..]) => (rc(NEOptionalLit(x.roll())), rest),
+        (OptionalNone, [t, rest..]) => (rc(EmptyOptionalLit(t.roll())), rest),
+        (NaturalIsZero, [NaturalLit(n), rest..]) => {
+            (rc(BoolLit(*n == 0)), rest)
         }
-        (NaturalShow, Some(NaturalLit(n)), _) => {
-            rc(TextLit(n.to_string().into()))
+        (NaturalEven, [NaturalLit(n), rest..]) => {
+            (rc(BoolLit(*n % 2 == 0)), rest)
         }
-        (ListLength, Some(EmptyListLit(_)), _) => rc(NaturalLit(0)),
-        (ListLength, Some(NEListLit(ys)), _) => rc(NaturalLit(ys.len())),
-        (ListHead, Some(EmptyListLit(t)), _) => rc(EmptyOptionalLit(t.clone())),
-        (ListHead, Some(NEListLit(ys)), _) => {
-            rc(NEOptionalLit(ys.first().unwrap().clone()))
+        (NaturalOdd, [NaturalLit(n), rest..]) => {
+            (rc(BoolLit(*n % 2 != 0)), rest)
         }
-        (ListLast, Some(EmptyListLit(t)), _) => rc(EmptyOptionalLit(t.clone())),
-        (ListLast, Some(NEListLit(ys)), _) => {
-            rc(NEOptionalLit(ys.last().unwrap().clone()))
+        (NaturalToInteger, [NaturalLit(n), rest..]) => {
+            (rc(IntegerLit(*n as isize)), rest)
         }
-        (ListReverse, Some(EmptyListLit(t)), _) => rc(EmptyListLit(t.clone())),
-        (ListReverse, Some(NEListLit(ys)), _) => {
-            let ys = ys.iter().rev().cloned().collect();
-            rc(NEListLit(ys))
+        (NaturalShow, [NaturalLit(n), rest..]) => {
+            (rc(TextLit(n.to_string().into())), rest)
+        }
+        (ListLength, [_, EmptyListLit(_), rest..]) => (rc(NaturalLit(0)), rest),
+        (ListLength, [_, NEListLit(ys), rest..]) => {
+            (rc(NaturalLit(ys.len())), rest)
+        }
+        (ListHead, [_, EmptyListLit(t), rest..]) => {
+            (rc(EmptyOptionalLit(t.clone())), rest)
+        }
+        (ListHead, [_, NEListLit(ys), rest..]) => {
+            (rc(NEOptionalLit(ys.first().unwrap().clone())), rest)
         }
-        (ListIndexed, Some(EmptyListLit(t)), _) => {
-            let t = Rc::clone(t);
-            dhall_expr!([] : List ({ index : Natural, value : t }))
+        (ListLast, [_, EmptyListLit(t), rest..]) => {
+            (rc(EmptyOptionalLit(t.clone())), rest)
         }
-        (ListIndexed, Some(NEListLit(xs)), _) => {
+        (ListLast, [_, NEListLit(ys), rest..]) => {
+            (rc(NEOptionalLit(ys.last().unwrap().clone())), rest)
+        }
+        (ListReverse, [_, EmptyListLit(t), rest..]) => {
+            (rc(EmptyListLit(t.clone())), rest)
+        }
+        (ListReverse, [_, NEListLit(ys), rest..]) => {
+            let ys = ys.iter().rev().cloned().collect();
+            (rc(NEListLit(ys)), rest)
+        }
+        (ListIndexed, [_, EmptyListLit(t), rest..]) => (
+            dhall_expr!([] : List ({ index : Natural, value : t })),
+            rest,
+        ),
+        (ListIndexed, [_, NEListLit(xs), rest..]) => {
             let xs = xs
                 .iter()
                 .cloned()
@@ -89,100 +66,110 @@ where
                     dhall_expr!({ index = i, value = e })
                 })
                 .collect();
-            rc(NEListLit(xs))
+            (rc(NEListLit(xs)), rest)
         }
-        (ListBuild, _, [a0, g, ..]) => {
+        (ListBuild, [a0, g, rest..]) => {
             loop {
-                if let App(f2, args2) = g.as_ref() {
-                    if let (Builtin(ListFold), [_, x, rest..]) =
+                if let App(f2, args2) = g {
+                    if let (Builtin(ListFold), [_, x, rest_inner..]) =
                         (f2.as_ref(), args2.as_slice())
                     {
                         // fold/build fusion
-                        break rc(App(x.clone(), rest.to_vec()));
+                        break (rc(App(x.clone(), rest_inner.to_vec())), rest);
                     }
                 };
-                let a0 = Rc::clone(a0);
+                let a0 = a0.roll();
                 let a1 = shift(1, &V("a".into(), 0), &a0);
-                // TODO: use Embed to avoid reevaluating g
-                break dhall_expr!(
-                    g
-                    (List a0)
-                    (λ(x : a0) -> λ(xs : List a1) -> [ x ] # xs)
-                    ([] : List a0)
+                let g = g.roll();
+                break (
+                    dhall_expr!(
+                        g
+                        (List a0)
+                        (λ(x : a0) -> λ(xs : List a1) -> [ x ] # xs)
+                        ([] : List a0)
+                    ),
+                    rest,
                 );
             }
         }
-        (OptionalBuild, _, [a0, g, ..]) => {
+        (OptionalBuild, [a0, g, rest..]) => {
             loop {
-                if let App(f2, args2) = g.as_ref() {
-                    if let (Builtin(OptionalFold), [_, x, rest..]) =
+                if let App(f2, args2) = g {
+                    if let (Builtin(OptionalFold), [_, x, rest_inner..]) =
                         (f2.as_ref(), args2.as_slice())
                     {
                         // fold/build fusion
-                        break rc(App(x.clone(), rest.to_vec()));
+                        break (rc(App(x.clone(), rest_inner.to_vec())), rest);
                     }
                 };
-                let a0 = Rc::clone(a0);
-                // TODO: use Embed to avoid reevaluating g
-                break dhall_expr!(
-                    g
-                    (Optional a0)
-                    (λ(x: a0) -> Some x)
-                    (None a0)
+                let a0 = a0.roll();
+                let g = g.roll();
+                break (
+                    dhall_expr!(
+                        g
+                        (Optional a0)
+                        (λ(x: a0) -> Some x)
+                        (None a0)
+                    ),
+                    rest,
                 );
             }
         }
-        (ListFold, Some(EmptyListLit(_)), [_, _, _, _, nil, ..]) => {
-            Rc::clone(nil)
+        (ListFold, [_, EmptyListLit(_), _, _, nil, rest..]) => {
+            (nil.roll(), rest)
         }
-        (ListFold, Some(NEListLit(xs)), [_, _, _, cons, nil, ..]) => {
-            xs.iter().rev().fold(Rc::clone(nil), |acc, x| {
+        (ListFold, [_, NEListLit(xs), _, cons, nil, rest..]) => (
+            xs.iter().rev().fold(nil.roll(), |acc, x| {
                 let x = x.clone();
                 let acc = acc.clone();
-                let cons = Rc::clone(cons);
+                let cons = cons.roll();
                 dhall_expr!(cons x acc)
-            })
-        }
+            }),
+            rest,
+        ),
         // // fold/build fusion
         // (ListFold, [_, App(box Builtin(ListBuild), [_, x, rest..]), rest..]) => {
-        //     normalize_whnf(&App(bx(x.clone()), rest.to_vec()))
+        //     normalize_ref(&App(bx(x.clone()), rest.to_vec()))
         // }
-        (OptionalFold, Some(NEOptionalLit(x)), [_, _, _, just, _, ..]) => {
+        (OptionalFold, [_, NEOptionalLit(x), _, just, _, rest..]) => {
             let x = x.clone();
-            let just = Rc::clone(just);
-            dhall_expr!(just x)
+            let just = just.roll();
+            (dhall_expr!(just x), rest)
+        }
+        (OptionalFold, [_, EmptyOptionalLit(_), _, _, nothing, rest..]) => {
+            (nothing.roll(), rest)
         }
-        (
-            OptionalFold,
-            Some(EmptyOptionalLit(_)),
-            [_, _, _, _, nothing, ..],
-        ) => Rc::clone(nothing),
         // // fold/build fusion
         // (OptionalFold, [_, App(box Builtin(OptionalBuild), [_, x, rest..]), rest..]) => {
-        //     normalize_whnf(&App(bx(x.clone()), rest.to_vec()))
+        //     normalize_ref(&App(bx(x.clone()), rest.to_vec()))
         // }
-        (NaturalBuild, _, [g, ..]) => {
+        (NaturalBuild, [g, rest..]) => {
             loop {
-                if let App(f2, args2) = g.as_ref() {
-                    if let (Builtin(NaturalFold), [x, rest..]) =
+                if let App(f2, args2) = g {
+                    if let (Builtin(NaturalFold), [x, rest_inner..]) =
                         (f2.as_ref(), args2.as_slice())
                     {
                         // fold/build fusion
-                        break rc(App(x.clone(), rest.to_vec()));
+                        break (rc(App(x.clone(), rest_inner.to_vec())), rest);
                     }
                 };
-                // TODO: use Embed to avoid reevaluating g
-                break dhall_expr!(g Natural (λ(x : Natural) -> x + 1) 0);
+                let g = g.roll();
+                break (
+                    dhall_expr!(g Natural (λ(x : Natural) -> x + 1) 0),
+                    rest,
+                );
             }
         }
-        (NaturalFold, Some(NaturalLit(0)), [_, _, _, zero]) => Rc::clone(zero),
-        (NaturalFold, Some(NaturalLit(n)), [_, t, succ, zero]) => {
+        (NaturalFold, [NaturalLit(0), _, _, zero, rest..]) => {
+            (zero.roll(), rest)
+        }
+        (NaturalFold, [NaturalLit(n), t, succ, zero, rest..]) => {
             let fold = rc(Builtin(NaturalFold));
             let n = rc(NaturalLit(n - 1));
-            let t = Rc::clone(t);
-            let succ = Rc::clone(succ);
-            let zero = Rc::clone(zero);
-            dhall_expr!(succ (fold n t succ zero))
+            let t = t.roll();
+            let succ = succ.roll();
+            let zero = zero.roll();
+            (dhall_expr!(succ (fold n t succ zero)), rest)
         }
         // (NaturalFold, Some(App(f2, args2)), _) => {
         //     match (f2.as_ref(), args2.as_slice()) {
@@ -193,140 +180,127 @@ where
         //         _ => return rc(App(f, args)),
         //     }
         // }
-        _ => return rc(App(f, args)),
+        _ => return DoneAsIs,
     };
     // Put the remaining arguments back and eval again. In most cases
     // ret will not be of a form that can be applied, so this won't go very deep.
     // In lots of cases, there are no remaining args so this cann will just return ret.
-    normalize_whnf(&rc(Expr::App(ret, args.split_off(len_consumption))))
+    let rest: Vec<SubExpr<S, A>> = rest.iter().map(ExprF::roll).collect();
+    Continue(ExprF::App(ret, rest))
 }
 
-/// Reduce an expression to its weak head normal form, i.e. normalize
-/// just enough to get the first constructor of the final expression
-/// Is identical to normalize on primitive types, but not on more complex
-/// types like functions and records.
-/// This allows normalization to be lazy.
-pub fn normalize_whnf<S, A>(e: &SubExpr<S, A>) -> SubExpr<S, A>
+// Small enum to help with being DRY
+enum WhatNext<'a, S, A> {
+    // Recurse on this expression
+    Continue(Expr<S, A>),
+    ContinueSub(SubExpr<S, A>),
+    // The following expression is the normal form
+    Done(Expr<S, A>),
+    DoneRef(&'a Expr<S, A>),
+    DoneRefSub(&'a SubExpr<S, A>),
+    // The current expression is already in normal form
+    DoneAsIs,
+}
+
+pub fn normalize_ref<S, A>(expr: &Expr<S, A>) -> Expr<S, A>
 where
-    S: fmt::Debug,
-    A: fmt::Debug,
+    S: fmt::Debug + Clone,
+    A: fmt::Debug + Clone,
 {
     use dhall_core::BinOp::*;
-    use dhall_core::Expr::*;
-    match e.as_ref() {
+    use dhall_core::ExprF::*;
+    // Recursively normalize all subexpressions
+    let expr: ExprF<Expr<S, A>, Label, S, A> =
+        expr.map_ref_simple(|e| normalize_ref(e.as_ref()));
+
+    use WhatNext::*;
+    let what_next = match &expr {
         Let(f, _, r, b) => {
             let vf0 = &V(f.clone(), 0);
-            let r2 = shift(1, vf0, r);
+            let r2 = shift(1, vf0, &r.roll());
             // TODO: use a context
-            let b2 = subst(vf0, &r2, b);
+            let b2 = subst(vf0, &r2, &b.roll());
             // TODO: add tests sensitive to shift errors before
             // trying anything
             let b3 = shift(-1, vf0, &b2);
-            normalize_whnf(&b3)
-        }
-        Annot(x, _) => normalize_whnf(x),
-        Note(_, e) => normalize_whnf(e),
-        App(f, args) => {
-            let f = normalize_whnf(f);
-            match (f.as_ref(), args.as_slice()) {
-                (_, []) => f,
-                // TODO: use Embed to avoid reevaluating f
-                (App(f, args1), args2) => normalize_whnf(&rc(App(
-                    f.clone(),
-                    args1.iter().chain(args2.iter()).cloned().collect(),
-                ))),
-                (Lam(ref x, _, ref b), [a, rest..]) => {
-                    // Beta reduce
-                    let vx0 = &V(x.clone(), 0);
-                    let a2 = shift(1, vx0, a);
-                    let b2 = subst(vx0, &a2, &b);
-                    let b3 = shift(-1, vx0, &b2);
-                    normalize_whnf(&rc(App(b3, rest.to_vec())))
-                }
-                (Builtin(b), _) => apply_builtin(*b, args.to_vec()),
-                _ => rc(App(f, args.to_vec())),
-            }
+            ContinueSub(b3)
         }
-        BoolIf(b, t, f) => {
-            let b = normalize_whnf(b);
-            match b.as_ref() {
-                BoolLit(true) => normalize_whnf(t),
-                BoolLit(false) => normalize_whnf(f),
-                _ => rc(BoolIf(b, t.clone(), f.clone())),
-            }
+        Annot(x, _) => DoneRef(x),
+        Note(_, e) => DoneRef(e),
+        App(f, args) if args.is_empty() => DoneRef(f),
+        App(App(f, args1), args2) => Continue(App(
+            f.clone(),
+            args1
+                .iter()
+                .cloned()
+                .chain(args2.iter().map(ExprF::roll))
+                .collect(),
+        )),
+        App(Builtin(b), args) => apply_builtin(*b, args),
+        App(Lam(x, _, b), args) => {
+            let mut iter = args.iter();
+            // We know args is nonempty
+            let a = iter.next().unwrap();
+            // Beta reduce
+            let vx0 = &V(x.clone(), 0);
+            let a2 = shift(1, vx0, &a.roll());
+            let b2 = subst(vx0, &a2, &b);
+            let b3 = shift(-1, vx0, &b2);
+            Continue(App(b3, iter.map(ExprF::roll).collect()))
         }
+        BoolIf(BoolLit(true), t, _) => DoneRef(t),
+        BoolIf(BoolLit(false), _, f) => DoneRef(f),
         // TODO: interpolation
         // TextLit(t) =>
-        BinOp(o, x, y) => {
-            let x = normalize_whnf(x);
-            let y = normalize_whnf(y);
-            rc(match (o, x.as_ref(), y.as_ref()) {
-                (BoolAnd, BoolLit(x), BoolLit(y)) => BoolLit(*x && *y),
-                (BoolOr, BoolLit(x), BoolLit(y)) => BoolLit(*x || *y),
-                (BoolEQ, BoolLit(x), BoolLit(y)) => BoolLit(x == y),
-                (BoolNE, BoolLit(x), BoolLit(y)) => BoolLit(x != y),
-                (NaturalPlus, NaturalLit(x), NaturalLit(y)) => {
-                    NaturalLit(x + y)
-                }
-                (NaturalTimes, NaturalLit(x), NaturalLit(y)) => {
-                    NaturalLit(x * y)
-                }
-                (TextAppend, TextLit(x), TextLit(y)) => TextLit(x + y),
-                (ListAppend, EmptyListLit(t), EmptyListLit(_)) => {
-                    EmptyListLit(Rc::clone(t))
-                }
-                (ListAppend, EmptyListLit(_), _) => return y,
-                (ListAppend, _, EmptyListLit(_)) => return x,
-                (ListAppend, NEListLit(xs), NEListLit(ys)) => {
-                    let xs = xs.into_iter().cloned();
-                    let ys = ys.into_iter().cloned();
-                    NEListLit(xs.chain(ys).collect())
-                }
-                (o, _, _) => BinOp(*o, x, y),
-            })
+        BinOp(BoolAnd, BoolLit(x), BoolLit(y)) => Done(BoolLit(*x && *y)),
+        BinOp(BoolOr, BoolLit(x), BoolLit(y)) => Done(BoolLit(*x || *y)),
+        BinOp(BoolEQ, BoolLit(x), BoolLit(y)) => Done(BoolLit(x == y)),
+        BinOp(BoolNE, BoolLit(x), BoolLit(y)) => Done(BoolLit(x != y)),
+        BinOp(NaturalPlus, NaturalLit(x), NaturalLit(y)) => {
+            Done(NaturalLit(x + y))
         }
-        Merge(x, y, t) => {
-            let x = normalize_whnf(x);
-            let y = normalize_whnf(y);
-            match (x.as_ref(), y.as_ref()) {
-                (RecordLit(handlers), UnionLit(k, v, _)) => {
-                    match handlers.get(&k) {
-                        Some(h) => {
-                            normalize_whnf(&rc(App(h.clone(), vec![v.clone()])))
-                        }
-                        None => rc(Merge(x, y, t.clone())),
-                    }
-                }
-                _ => rc(Merge(x, y, t.clone())),
-            }
+        BinOp(NaturalTimes, NaturalLit(x), NaturalLit(y)) => {
+            Done(NaturalLit(x * y))
         }
-        Field(e, l) => {
-            let e = normalize_whnf(e);
-            match e.as_ref() {
-                RecordLit(kvs) => match kvs.get(&l) {
-                    Some(r) => normalize_whnf(r),
-                    None => rc(Field(e, l.clone())),
-                },
-                _ => rc(Field(e, l.clone())),
-            }
+        BinOp(TextAppend, TextLit(x), TextLit(y)) => Done(TextLit(x + y)),
+        BinOp(ListAppend, EmptyListLit(t), EmptyListLit(_)) => {
+            Done(EmptyListLit(SubExpr::clone(t)))
         }
-        Projection(_, ls) if ls.is_empty() => {
-            rc(RecordLit(std::collections::BTreeMap::new()))
+        BinOp(ListAppend, EmptyListLit(_), y) => DoneRef(y),
+        BinOp(ListAppend, x, EmptyListLit(_)) => DoneRef(x),
+        BinOp(ListAppend, NEListLit(xs), NEListLit(ys)) => {
+            let xs = xs.into_iter().cloned();
+            let ys = ys.into_iter().cloned();
+            Done(NEListLit(xs.chain(ys).collect()))
         }
-        Projection(e, ls) => {
-            let e = normalize_whnf(e);
-            match e.as_ref() {
-                RecordLit(kvs) => rc(RecordLit(
-                    ls.iter()
-                        .filter_map(|l| {
-                            kvs.get(l).map(|x| (l.clone(), x.clone()))
-                        })
-                        .collect(),
-                )),
-                _ => rc(Projection(e, ls.clone())),
+        Merge(RecordLit(handlers), UnionLit(k, v, _), _) => {
+            match handlers.get(&k) {
+                Some(h) => Continue(App(h.clone(), vec![v.clone()])),
+                None => DoneAsIs,
             }
         }
-        _ => Rc::clone(e),
+        Field(RecordLit(kvs), l) => match kvs.get(&l) {
+            Some(r) => DoneRefSub(r),
+            None => DoneAsIs,
+        },
+        Projection(_, ls) if ls.is_empty() => {
+            Done(RecordLit(std::collections::BTreeMap::new()))
+        }
+        Projection(RecordLit(kvs), ls) => Done(RecordLit(
+            ls.iter()
+                .filter_map(|l| kvs.get(l).map(|x| (l.clone(), x.clone())))
+                .collect(),
+        )),
+        _ => DoneAsIs,
+    };
+
+    match what_next {
+        Continue(e) => normalize_ref(&e),
+        ContinueSub(e) => normalize_ref(e.as_ref()),
+        Done(e) => e,
+        DoneRef(e) => e.clone(),
+        DoneRefSub(e) => e.unroll(),
+        DoneAsIs => expr.map_ref_simple(ExprF::roll),
     }
 }
 
@@ -341,8 +315,8 @@ where
 ///
 pub fn normalize<S, A>(e: SubExpr<S, A>) -> SubExpr<S, A>
 where
-    S: fmt::Debug,
-    A: fmt::Debug,
+    S: fmt::Debug + Clone,
+    A: fmt::Debug + Clone,
 {
-    map_subexpr_rc(&normalize_whnf(&e), |x| normalize(Rc::clone(x)))
+    normalize_ref(e.as_ref()).roll()
 }
diff --git a/dhall/src/typecheck.rs b/dhall/src/typecheck.rs
index f21721d..75e6e1d 100644
--- a/dhall/src/typecheck.rs
+++ b/dhall/src/typecheck.rs
@@ -1,7 +1,6 @@
 #![allow(non_snake_case)]
 use std::collections::HashSet;
 use std::fmt;
-use std::rc::Rc;
 
 use crate::normalize::normalize;
 use dhall_core;
@@ -13,7 +12,7 @@ use self::TypeMessage::*;
 
 fn axiom<S>(c: Const) -> Result<Const, TypeError<S>> {
     use dhall_core::Const::*;
-    use dhall_core::Expr::*;
+    use dhall_core::ExprF::*;
     match c {
         Type => Ok(Kind),
         Kind => Err(TypeError::new(&Context::new(), rc(Const(Kind)), Untyped)),
@@ -29,7 +28,7 @@ fn rule(a: Const, b: Const) -> Result<Const, ()> {
     }
 }
 
-fn match_vars(vl: &V, vr: &V, ctx: &[(Label, Label)]) -> bool {
+fn match_vars(vl: &V<Label>, vr: &V<Label>, ctx: &[(Label, Label)]) -> bool {
     let mut vl = vl.clone();
     let mut vr = vr.clone();
     let mut ctx = ctx.to_vec();
@@ -54,7 +53,7 @@ where
     S: ::std::fmt::Debug,
     T: ::std::fmt::Debug,
 {
-    use dhall_core::Expr::*;
+    use dhall_core::ExprF::*;
     fn go<S, T>(
         ctx: &mut Vec<(Label, Label)>,
         el: &Expr<S, X>,
@@ -113,7 +112,7 @@ where
     go::<S, T>(&mut ctx, eL0, eR0)
 }
 
-fn type_of_builtin<S>(b: Builtin) -> Rc<Expr<S, X>> {
+fn type_of_builtin<S>(b: Builtin) -> SubExpr<S, X> {
     use dhall_core::Builtin::*;
     match b {
         Bool | Natural | Integer | Double | Text => dhall_expr!(Type),
@@ -184,17 +183,16 @@ fn type_of_builtin<S>(b: Builtin) -> Rc<Expr<S, X>> {
 /// is not necessary for just type-checking.  If you actually care about the
 /// returned type then you may want to `normalize` it afterwards.
 pub fn type_with<S>(
-    ctx: &Context<Label, Rc<Expr<S, X>>>,
-    e: Rc<Expr<S, X>>,
-) -> Result<Rc<Expr<S, X>>, TypeError<S>>
+    ctx: &Context<Label, SubExpr<S, X>>,
+    e: SubExpr<S, X>,
+) -> Result<SubExpr<S, X>, TypeError<S>>
 where
-    S: ::std::fmt::Debug,
+    S: ::std::fmt::Debug + Clone,
 {
     use dhall_core::BinOp::*;
     use dhall_core::Builtin::*;
     use dhall_core::Const::*;
-    use dhall_core::Expr;
-    use dhall_core::Expr::*;
+    use dhall_core::ExprF::*;
     let mkerr = |msg: TypeMessage<_>| TypeError::new(ctx, e.clone(), msg);
     let ensure_const = |x: &SubExpr<_, _>, msg: TypeMessage<_>| match x.as_ref()
     {
@@ -266,7 +264,7 @@ where
                     return Err(mkerr(NotAFunction(f.clone(), tf)));
                 }
             };
-            let tA = normalize(Rc::clone(tA));
+            let tA = normalize(SubExpr::clone(tA));
             let tA2 = normalized_type_with(ctx, a.clone())?;
             if prop_equal(tA.as_ref(), tA2.as_ref()) {
                 let vx0 = &V(x.clone(), 0);
@@ -280,9 +278,9 @@ where
         }
         Let(f, mt, r, b) => {
             let r = if let Some(t) = mt {
-                rc(Annot(Rc::clone(r), Rc::clone(t)))
+                rc(Annot(SubExpr::clone(r), SubExpr::clone(t)))
             } else {
-                Rc::clone(r)
+                SubExpr::clone(r)
             };
 
             let tR = type_with(ctx, r)?;
@@ -351,7 +349,7 @@ where
         EmptyListLit(t) => {
             let s = normalized_type_with(ctx, t.clone())?;
             ensure_is_type(s, InvalidListType(t.clone()))?;
-            let t = normalize(Rc::clone(t));
+            let t = normalize(SubExpr::clone(t));
             return Ok(dhall_expr!(List t));
         }
         NEListLit(xs) => {
@@ -377,7 +375,7 @@ where
             return Ok(dhall_expr!(Optional t));
         }
         NEOptionalLit(x) => {
-            let t: Rc<Expr<_, _>> = type_with(ctx, x.clone())?;
+            let t: SubExpr<_, _> = type_with(ctx, x.clone())?;
             let s = normalized_type_with(ctx, t.clone())?;
             ensure_is_type(s, InvalidOptionalType(t.clone()))?;
             let t = normalize(t);
@@ -451,11 +449,11 @@ where
 }
 
 pub fn normalized_type_with<S>(
-    ctx: &Context<Label, Rc<Expr<S, X>>>,
-    e: Rc<Expr<S, X>>,
-) -> Result<Rc<Expr<S, X>>, TypeError<S>>
+    ctx: &Context<Label, SubExpr<S, X>>,
+    e: SubExpr<S, X>,
+) -> Result<SubExpr<S, X>, TypeError<S>>
 where
-    S: ::std::fmt::Debug,
+    S: ::std::fmt::Debug + Clone,
 {
     Ok(normalize(type_with(ctx, e)?))
 }
@@ -463,9 +461,9 @@ where
 /// `typeOf` is the same as `type_with` with an empty context, meaning that the
 /// expression must be closed (i.e. no free variables), otherwise type-checking
 /// will fail.
-pub fn type_of<S: ::std::fmt::Debug>(
-    e: Rc<Expr<S, X>>,
-) -> Result<Rc<Expr<S, X>>, TypeError<S>> {
+pub fn type_of<S: ::std::fmt::Debug + Clone>(
+    e: SubExpr<S, X>,
+) -> Result<SubExpr<S, X>, TypeError<S>> {
     let ctx = Context::new();
     type_with(&ctx, e) //.map(|e| e.into_owned())
 }
@@ -474,63 +472,58 @@ pub fn type_of<S: ::std::fmt::Debug>(
 #[derive(Debug)]
 pub enum TypeMessage<S> {
     UnboundVariable,
-    InvalidInputType(Rc<Expr<S, X>>),
-    InvalidOutputType(Rc<Expr<S, X>>),
-    NotAFunction(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    TypeMismatch(
-        Rc<Expr<S, X>>,
-        Rc<Expr<S, X>>,
-        Rc<Expr<S, X>>,
-        Rc<Expr<S, X>>,
-    ),
-    AnnotMismatch(Rc<Expr<S, X>>, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
+    InvalidInputType(SubExpr<S, X>),
+    InvalidOutputType(SubExpr<S, X>),
+    NotAFunction(SubExpr<S, X>, SubExpr<S, X>),
+    TypeMismatch(SubExpr<S, X>, SubExpr<S, X>, SubExpr<S, X>, SubExpr<S, X>),
+    AnnotMismatch(SubExpr<S, X>, SubExpr<S, X>, SubExpr<S, X>),
     Untyped,
-    InvalidListElement(usize, Rc<Expr<S, X>>, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    InvalidListType(Rc<Expr<S, X>>),
-    InvalidOptionalElement(Rc<Expr<S, X>>, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
+    InvalidListElement(usize, SubExpr<S, X>, SubExpr<S, X>, SubExpr<S, X>),
+    InvalidListType(SubExpr<S, X>),
+    InvalidOptionalElement(SubExpr<S, X>, SubExpr<S, X>, SubExpr<S, X>),
     InvalidOptionalLiteral(usize),
-    InvalidOptionalType(Rc<Expr<S, X>>),
-    InvalidPredicate(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
+    InvalidOptionalType(SubExpr<S, X>),
+    InvalidPredicate(SubExpr<S, X>, SubExpr<S, X>),
     IfBranchMismatch(
-        Rc<Expr<S, X>>,
-        Rc<Expr<S, X>>,
-        Rc<Expr<S, X>>,
-        Rc<Expr<S, X>>,
+        SubExpr<S, X>,
+        SubExpr<S, X>,
+        SubExpr<S, X>,
+        SubExpr<S, X>,
     ),
-    IfBranchMustBeTerm(bool, Rc<Expr<S, X>>, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    InvalidField(Label, Rc<Expr<S, X>>),
-    InvalidFieldType(Label, Rc<Expr<S, X>>),
-    InvalidAlternative(Label, Rc<Expr<S, X>>),
-    InvalidAlternativeType(Label, Rc<Expr<S, X>>),
+    IfBranchMustBeTerm(bool, SubExpr<S, X>, SubExpr<S, X>, SubExpr<S, X>),
+    InvalidField(Label, SubExpr<S, X>),
+    InvalidFieldType(Label, SubExpr<S, X>),
+    InvalidAlternative(Label, SubExpr<S, X>),
+    InvalidAlternativeType(Label, SubExpr<S, X>),
     DuplicateAlternative(Label),
-    MustCombineARecord(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
+    MustCombineARecord(SubExpr<S, X>, SubExpr<S, X>),
     FieldCollision(Label),
-    MustMergeARecord(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    MustMergeUnion(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
+    MustMergeARecord(SubExpr<S, X>, SubExpr<S, X>),
+    MustMergeUnion(SubExpr<S, X>, SubExpr<S, X>),
     UnusedHandler(HashSet<Label>),
     MissingHandler(HashSet<Label>),
-    HandlerInputTypeMismatch(Label, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    HandlerOutputTypeMismatch(Label, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    HandlerNotAFunction(Label, Rc<Expr<S, X>>),
-    NotARecord(Label, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    MissingField(Label, Rc<Expr<S, X>>),
-    BinOpTypeMismatch(BinOp, Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    NoDependentLet(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
-    NoDependentTypes(Rc<Expr<S, X>>, Rc<Expr<S, X>>),
+    HandlerInputTypeMismatch(Label, SubExpr<S, X>, SubExpr<S, X>),
+    HandlerOutputTypeMismatch(Label, SubExpr<S, X>, SubExpr<S, X>),
+    HandlerNotAFunction(Label, SubExpr<S, X>),
+    NotARecord(Label, SubExpr<S, X>, SubExpr<S, X>),
+    MissingField(Label, SubExpr<S, X>),
+    BinOpTypeMismatch(BinOp, SubExpr<S, X>, SubExpr<S, X>),
+    NoDependentLet(SubExpr<S, X>, SubExpr<S, X>),
+    NoDependentTypes(SubExpr<S, X>, SubExpr<S, X>),
 }
 
 /// A structured type error that includes context
 #[derive(Debug)]
 pub struct TypeError<S> {
-    pub context: Context<Label, Rc<Expr<S, X>>>,
-    pub current: Rc<Expr<S, X>>,
+    pub context: Context<Label, SubExpr<S, X>>,
+    pub current: SubExpr<S, X>,
     pub type_message: TypeMessage<S>,
 }
 
 impl<S> TypeError<S> {
     pub fn new(
-        context: &Context<Label, Rc<Expr<S, X>>>,
-        current: Rc<Expr<S, X>>,
+        context: &Context<Label, SubExpr<S, X>>,
+        current: SubExpr<S, X>,
         type_message: TypeMessage<S>,
     ) -> Self {
         TypeError {
diff --git a/dhall/tests/common/mod.rs b/dhall/tests/common/mod.rs
index 6b893e0..325b80f 100644
--- a/dhall/tests/common/mod.rs
+++ b/dhall/tests/common/mod.rs
@@ -111,7 +111,7 @@ pub fn run_test(base_path: &str, feature: Feature) {
             let expected_file_path = base_path + "B.dhall";
             let expr = rc(read_dhall_file(&expr_file_path).unwrap());
             let expected = rc(read_dhall_file(&expected_file_path).unwrap());
-            typecheck::type_of(rc(Expr::Annot(expr, expected))).unwrap();
+            typecheck::type_of(rc(ExprF::Annot(expr, expected))).unwrap();
         }
     }
 }
diff --git a/dhall/tests/dhall_type.rs b/dhall/tests/dhall_type.rs
index faece20..941e3a4 100644
--- a/dhall/tests/dhall_type.rs
+++ b/dhall/tests/dhall_type.rs
@@ -33,10 +33,7 @@ fn test_dhall_type() {
     #[derive(Type)]
     #[allow(dead_code)]
     struct C<T>(T, Option<String>);
-    assert_eq!(
-        <C<bool>>::get_type(),
-        <(bool, Option<String>)>::get_type()
-    );
+    assert_eq!(<C<bool>>::get_type(), <(bool, Option<String>)>::get_type());
 
     #[derive(Type)]
     #[allow(dead_code)]
diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index afa3d3f..3d1b9f3 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -100,7 +100,7 @@ pub enum Const {
 /// appear as a numeric suffix.
 ///
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub struct V(pub Label, pub usize);
+pub struct V<Label>(pub Label, pub usize);
 
 // Definition order must match precedence order for
 // pretty-printing to work correctly
@@ -170,45 +170,42 @@ pub type ParsedExpr = SubExpr<X, Import>;
 pub type ResolvedExpr = SubExpr<X, X>;
 pub type DhallExpr = ResolvedExpr;
 
-pub type SubExpr<Note, Embed> = Rc<Expr<Note, Embed>>;
+#[derive(Debug, PartialEq, Eq)]
+pub struct SubExpr<Note, Embed>(pub Rc<Expr<Note, Embed>>);
+
+pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Label, Note, Embed>;
 
 /// Syntax tree for expressions
+// Having the recursion out of the enum definition enables writing
+// much more generic code and improves pattern-matching behind
+// smart pointers.
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum Expr<Note, Embed> {
+pub enum ExprF<SubExpr, Label, Note, Embed> {
     ///  `Const c                                  ~  c`
     Const(Const),
     ///  `Var (V x 0)                              ~  x`<br>
     ///  `Var (V x n)                              ~  x@n`
-    Var(V),
+    Var(V<Label>),
     ///  `Lam x     A b                            ~  λ(x : A) -> b`
-    Lam(Label, SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    Lam(Label, SubExpr, SubExpr),
     ///  `Pi "_" A B                               ~        A  -> B`
     ///  `Pi x   A B                               ~  ∀(x : A) -> B`
-    Pi(Label, SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    Pi(Label, SubExpr, SubExpr),
     ///  `App f A                                  ~  f A`
-    App(SubExpr<Note, Embed>, Vec<SubExpr<Note, Embed>>),
+    App(SubExpr, Vec<SubExpr>),
     ///  `Let x Nothing  r e  ~  let x     = r in e`
     ///  `Let x (Just t) r e  ~  let x : t = r in e`
-    Let(
-        Label,
-        Option<SubExpr<Note, Embed>>,
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-    ),
+    Let(Label, Option<SubExpr>, SubExpr, SubExpr),
     ///  `Annot x t                                ~  x : t`
-    Annot(SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    Annot(SubExpr, SubExpr),
     /// Built-in values
     Builtin(Builtin),
     // Binary operations
-    BinOp(BinOp, SubExpr<Note, Embed>, SubExpr<Note, Embed>),
+    BinOp(BinOp, SubExpr, SubExpr),
     ///  `BoolLit b                                ~  b`
     BoolLit(bool),
     ///  `BoolIf x y z                             ~  if x then y else z`
-    BoolIf(
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-    ),
+    BoolIf(SubExpr, SubExpr, SubExpr),
     ///  `NaturalLit n                             ~  +n`
     NaturalLit(Natural),
     ///  `IntegerLit n                             ~  n`
@@ -216,39 +213,31 @@ pub enum Expr<Note, Embed> {
     ///  `DoubleLit n                              ~  n`
     DoubleLit(Double),
     ///  `TextLit t                                ~  t`
-    TextLit(InterpolatedText<Note, Embed>),
+    TextLit(InterpolatedText<SubExpr>),
     ///  [] : List t`
-    EmptyListLit(SubExpr<Note, Embed>),
+    EmptyListLit(SubExpr),
     ///  [x, y, z]
-    NEListLit(Vec<SubExpr<Note, Embed>>),
+    NEListLit(Vec<SubExpr>),
     ///  None t
-    EmptyOptionalLit(SubExpr<Note, Embed>),
+    EmptyOptionalLit(SubExpr),
     ///  Some e
-    NEOptionalLit(SubExpr<Note, Embed>),
+    NEOptionalLit(SubExpr),
     ///  `Record            [(k1, t1), (k2, t2)]   ~  { k1 : t1, k2 : t1 }`
-    RecordType(BTreeMap<Label, SubExpr<Note, Embed>>),
+    RecordType(BTreeMap<Label, SubExpr>),
     ///  `RecordLit         [(k1, v1), (k2, v2)]   ~  { k1 = v1, k2 = v2 }`
-    RecordLit(BTreeMap<Label, SubExpr<Note, Embed>>),
+    RecordLit(BTreeMap<Label, SubExpr>),
     ///  `Union             [(k1, t1), (k2, t2)]   ~  < k1 : t1, k2 : t2 >`
-    UnionType(BTreeMap<Label, SubExpr<Note, Embed>>),
+    UnionType(BTreeMap<Label, SubExpr>),
     ///  `UnionLit (k1, v1) [(k2, t2), (k3, t3)]   ~  < k1 = t1, k2 : t2, k3 : t3 >`
-    UnionLit(
-        Label,
-        SubExpr<Note, Embed>,
-        BTreeMap<Label, SubExpr<Note, Embed>>,
-    ),
+    UnionLit(Label, SubExpr, BTreeMap<Label, SubExpr>),
     ///  `Merge x y t                              ~  merge x y : t`
-    Merge(
-        SubExpr<Note, Embed>,
-        SubExpr<Note, Embed>,
-        Option<SubExpr<Note, Embed>>,
-    ),
+    Merge(SubExpr, SubExpr, Option<SubExpr>),
     ///  e.x
-    Field(SubExpr<Note, Embed>, Label),
+    Field(SubExpr, Label),
     ///  e.{ x, y, z }
-    Projection(SubExpr<Note, Embed>, Vec<Label>),
+    Projection(SubExpr, Vec<Label>),
     /// Annotation on the AST. Unused for now but could hold e.g. file location information
-    Note(Note, SubExpr<Note, Embed>),
+    Note(Note, SubExpr),
     /// Embeds an import or the result of resolving the import
     Embed(Embed),
 }
@@ -270,13 +259,12 @@ impl<S, A> Expr<S, A> {
         F3: FnOnce(&A) -> B,
         F4: Fn(&Label) -> Label,
     {
-        map_subexpr(
-            self,
+        self.map_ref(
             |x| rc(map_expr(x.as_ref())),
+            |_, x| rc(map_expr(x.as_ref())),
             map_note,
             map_embed,
             map_label,
-            |_, x| rc(map_expr(x.as_ref())),
         )
     }
 
@@ -299,12 +287,21 @@ impl<S, A> Expr<S, A> {
         let recurse = |e: &Self| -> Self { e.map_label(map_label) };
         self.map_shallow(recurse, |x| x.clone(), |x| x.clone(), map_label)
     }
+
+    #[inline(always)]
+    pub fn roll(&self) -> SubExpr<S, A>
+    where
+        S: Clone,
+        A: Clone,
+    {
+        rc(ExprF::clone(self))
+    }
 }
 
 impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
     pub fn squash_embed(&self) -> Expr<S, A> {
         match self {
-            Expr::Embed(e) => e.clone(),
+            ExprF::Embed(e) => e.clone(),
             e => e.map_shallow(
                 |e| e.squash_embed(),
                 |x| x.clone(),
@@ -315,20 +312,297 @@ impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
     }
 }
 
+impl<SE, L, N, E> ExprF<SE, L, N, E> {
+    #[inline(always)]
+    pub fn as_ref(&self) -> ExprF<&SE, &L, &N, &E>
+    where
+        L: Ord,
+    {
+        fn opt<T>(x: &Option<T>) -> Option<&T> {
+            x.as_ref()
+        }
+        fn vec<T>(x: &Vec<T>) -> Vec<&T> {
+            x.iter().collect()
+        }
+        fn btmap<L: Ord, SE>(x: &BTreeMap<L, SE>) -> BTreeMap<&L, &SE> {
+            x.iter().collect()
+        }
+
+        use crate::ExprF::*;
+        match self {
+            Var(V(l, n)) => Var(V(l, *n)),
+            Lam(l, t, b) => Lam(l, t, b),
+            Pi(l, t, b) => Pi(l, t, b),
+            Let(l, t, a, b) => Let(l, opt(t), a, b),
+            App(f, args) => App(f, vec(args)),
+            Annot(x, t) => Annot(x, t),
+            Const(k) => Const(*k),
+            Builtin(v) => Builtin(*v),
+            BoolLit(b) => BoolLit(*b),
+            NaturalLit(n) => NaturalLit(*n),
+            IntegerLit(n) => IntegerLit(*n),
+            DoubleLit(n) => DoubleLit(*n),
+            TextLit(t) => TextLit(t.as_ref()),
+            BinOp(o, x, y) => BinOp(*o, x, y),
+            BoolIf(b, t, f) => BoolIf(b, t, f),
+            EmptyListLit(t) => EmptyListLit(t),
+            NEListLit(es) => NEListLit(vec(es)),
+            EmptyOptionalLit(t) => EmptyOptionalLit(t),
+            NEOptionalLit(e) => NEOptionalLit(e),
+            RecordType(kts) => RecordType(btmap(kts)),
+            RecordLit(kvs) => RecordLit(btmap(kvs)),
+            UnionType(kts) => UnionType(btmap(kts)),
+            UnionLit(k, v, kvs) => UnionLit(k, v, btmap(kvs)),
+            Merge(x, y, t) => Merge(x, y, opt(t)),
+            Field(e, l) => Field(e, l),
+            Projection(e, ls) => Projection(e, vec(ls)),
+            Note(n, e) => Note(n, e),
+            Embed(a) => Embed(a),
+        }
+    }
+
+    #[inline(always)]
+    pub fn map<SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
+        self,
+        map_subexpr: F1,
+        map_under_binder: F2,
+        map_note: F3,
+        map_embed: F4,
+        mut map_label: F5,
+    ) -> ExprF<SE2, L2, N2, E2>
+    where
+        L: Ord,
+        L2: Ord,
+        F1: FnMut(SE) -> SE2,
+        F2: FnOnce(&L, SE) -> SE2,
+        F3: FnOnce(N) -> N2,
+        F4: FnOnce(E) -> E2,
+        F5: FnMut(L) -> L2,
+    {
+        let mut map = map_subexpr;
+        fn vec<T, U, F: FnMut(T) -> U>(x: Vec<T>, f: F) -> Vec<U> {
+            x.into_iter().map(f).collect()
+        }
+        fn btmap<K, L, T, U, FK, FV>(
+            x: BTreeMap<K, T>,
+            mut fk: FK,
+            mut fv: FV,
+        ) -> BTreeMap<L, U>
+        where
+            K: Ord,
+            L: Ord,
+            FK: FnMut(K) -> L,
+            FV: FnMut(T) -> U,
+        {
+            x.into_iter().map(|(k, v)| (fk(k), fv(v))).collect()
+        }
+
+        use crate::ExprF::*;
+        match self {
+            Var(V(l, n)) => Var(V(map_label(l), n)),
+            Lam(l, t, b) => {
+                let b = map_under_binder(&l, b);
+                Lam(map_label(l), map(t), b)
+            }
+            Pi(l, t, b) => {
+                let b = map_under_binder(&l, b);
+                Pi(map_label(l), map(t), b)
+            }
+            Let(l, t, a, b) => {
+                let b = map_under_binder(&l, b);
+                Let(map_label(l), t.map(&mut map), map(a), b)
+            }
+            App(f, args) => App(map(f), vec(args, map)),
+            Annot(x, t) => Annot(map(x), map(t)),
+            Const(k) => Const(k),
+            Builtin(v) => Builtin(v),
+            BoolLit(b) => BoolLit(b),
+            NaturalLit(n) => NaturalLit(n),
+            IntegerLit(n) => IntegerLit(n),
+            DoubleLit(n) => DoubleLit(n),
+            TextLit(t) => TextLit(t.map(map)),
+            BinOp(o, x, y) => BinOp(o, map(x), map(y)),
+            BoolIf(b, t, f) => BoolIf(map(b), map(t), map(f)),
+            EmptyListLit(t) => EmptyListLit(map(t)),
+            NEListLit(es) => NEListLit(vec(es, map)),
+            EmptyOptionalLit(t) => EmptyOptionalLit(map(t)),
+            NEOptionalLit(e) => NEOptionalLit(map(e)),
+            RecordType(kts) => RecordType(btmap(kts, map_label, map)),
+            RecordLit(kvs) => RecordLit(btmap(kvs, map_label, map)),
+            UnionType(kts) => UnionType(btmap(kts, map_label, map)),
+            UnionLit(k, v, kvs) => {
+                UnionLit(map_label(k), map(v), btmap(kvs, map_label, map))
+            }
+            Merge(x, y, t) => Merge(map(x), map(y), t.map(map)),
+            Field(e, l) => Field(map(e), map_label(l)),
+            Projection(e, ls) => Projection(map(e), vec(ls, map_label)),
+            Note(n, e) => Note(map_note(n), map(e)),
+            Embed(a) => Embed(map_embed(a)),
+        }
+    }
+
+    #[inline(always)]
+    pub fn map_ref<'a, SE2, L2, N2, E2, F1, F2, F3, F4, F5>(
+        &'a self,
+        map_subexpr: F1,
+        map_under_binder: F2,
+        map_note: F3,
+        map_embed: F4,
+        map_label: F5,
+    ) -> ExprF<SE2, L2, N2, E2>
+    where
+        L: Ord,
+        L2: Ord,
+        F1: FnMut(&'a SE) -> SE2,
+        F2: FnOnce(&'a L, &'a SE) -> SE2,
+        F3: FnOnce(&'a N) -> N2,
+        F4: FnOnce(&'a E) -> E2,
+        F5: FnMut(&'a L) -> L2,
+    {
+        // Not optimal: reallocates all the Vecs and BTreeMaps for nothing.
+        self.as_ref().map(
+            map_subexpr,
+            |l, e| map_under_binder(*l, e),
+            map_note,
+            map_embed,
+            map_label,
+        )
+    }
+
+    #[inline(always)]
+    pub fn map_ref_simple<'a, SE2, F1>(
+        &'a self,
+        map_subexpr: F1,
+    ) -> ExprF<SE2, L, N, E>
+    where
+        L: Ord,
+        L: Clone,
+        N: Clone,
+        E: Clone,
+        F1: Fn(&'a SE) -> SE2,
+    {
+        self.map_ref(
+            &map_subexpr,
+            |_, e| map_subexpr(e),
+            N::clone,
+            E::clone,
+            L::clone,
+        )
+    }
+
+    // #[inline(always)]
+    // pub fn zip<SE2, L2, N2, E2>(
+    //     self,
+    //     other: ExprF<SE2, L2, N2, E2>
+    // ) -> Option<ExprF<(SE, SE2), (L, L2), (N, N2), (E, E2)>>
+    // where
+    //     L: Ord,
+    //     L2: Ord,
+    // {
+    //     // What to do with Var ?
+    //     use crate::ExprF::*;
+    //     match (self, other) {
+    //         // Var(V(l, n)) => Var(V(map_label(l), n)),
+    //         // Lam(l, t, b) => {
+    //         // Pi(l, t, b) => {
+    //         // Let(l, t, a, b) => {
+    //         // App(f, args) => App(map(f), vec(args, map)),
+    //         // Annot(x, t) => Annot(map(x), map(t)),
+    //         (Const(x), Const(y)) if x == y => Some(Const(x)),
+    //         (Builtin(x), Builtin(y)) if x == y => Some(Builtin(x)),
+    //         (BoolLit(x), BoolLit(y)) if x == y => Some(BoolLit(x)),
+    //         (NaturalLit(x), NaturalLit(y)) if x == y => Some(NaturalLit(x)),
+    //         (IntegerLit(x), IntegerLit(y)) if x == y => Some(IntegerLit(x)),
+    //         (DoubleLit(x), DoubleLit(y)) if x == y => Some(DoubleLit(x)),
+    //         // TextLit(t) => TextLit(t.map(map)),
+    //         // BinOp(o, x, y) => BinOp(o, map(x), map(y)),
+    //         // BoolIf(b, t, f) => BoolIf(map(b), map(t), map(f)),
+    //         // EmptyListLit(t) => EmptyListLit(map(t)),
+    //         // NEListLit(es) => NEListLit(vec(es, map)),
+    //         // EmptyOptionalLit(t) => EmptyOptionalLit(map(t)),
+    //         // NEOptionalLit(e) => NEOptionalLit(map(e)),
+    //         // RecordType(kts) => RecordType(btmap(kts, map_label, map)),
+    //         // RecordLit(kvs) => RecordLit(btmap(kvs, map_label, map)),
+    //         // UnionType(kts) => UnionType(btmap(kts, map_label, map)),
+    //         // UnionLit(k, v, kvs) => {
+    //         // Merge(x, y, t) => Merge(map(x), map(y), t.map(map)),
+    //         // Field(e, l) => Field(map(e), map_label(l)),
+    //         // Projection(e, ls) => Projection(map(e), vec(ls, map_label)),
+    //         // Note(n, e) => Note(map_note(n), map(e)),
+    //         // Embed(a) => Embed(map_embed(a)),
+    //     }
+    // }
+}
+
+impl<N, E> SubExpr<N, E> {
+    #[inline(always)]
+    pub fn as_ref(&self) -> &Expr<N, E> {
+        self.0.as_ref()
+    }
+
+    pub fn map_ref<'a, F1, F2>(
+        &'a self,
+        map_expr: F1,
+        map_under_binder: F2,
+    ) -> Self
+    where
+        F1: FnMut(&'a Self) -> Self,
+        F2: FnOnce(&'a Label, &'a Self) -> Self,
+    {
+        match self.as_ref() {
+            ExprF::Embed(_) => SubExpr::clone(self),
+            // Recursive call
+            ExprF::Note(_, e) => e.map_ref(map_expr, map_under_binder),
+            // Call ExprF::map_ref
+            e => rc(e.map_ref(
+                map_expr,
+                map_under_binder,
+                |_| unreachable!(),
+                |_| unreachable!(),
+                Label::clone,
+            )),
+        }
+    }
+
+    pub fn map_ref_simple<F1>(&self, map_expr: F1) -> Self
+    where
+        F1: Fn(&Self) -> Self,
+    {
+        self.map_ref(&map_expr, |_, e| map_expr(e))
+    }
+
+    #[inline(always)]
+    pub fn unroll(&self) -> Expr<N, E>
+    where
+        N: Clone,
+        E: Clone,
+    {
+        ExprF::clone(self.as_ref())
+    }
+}
+
+impl<N, E> Clone for SubExpr<N, E> {
+    #[inline(always)]
+    fn clone(&self) -> Self {
+        SubExpr(Rc::clone(&self.0))
+    }
+}
+
 // Remains of a previous life, where everything was in Boxes
-pub fn bx<T>(x: T) -> Rc<T> {
-    Rc::new(x)
+pub fn bx<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
+    SubExpr(Rc::new(x))
 }
 
-pub fn rc<T>(x: T) -> Rc<T> {
-    Rc::new(x)
+// Should probably rename this too
+pub fn rc<N, E>(x: Expr<N, E>) -> SubExpr<N, E> {
+    SubExpr(Rc::new(x))
 }
 
 pub fn app<N, E>(f: Expr<N, E>, args: Vec<SubExpr<N, E>>) -> Expr<N, E> {
     if args.is_empty() {
         f
     } else {
-        Expr::App(rc(f), args)
+        ExprF::App(rc(f), args)
     }
 }
 
@@ -339,7 +613,7 @@ pub fn app_rc<N, E>(
     if args.is_empty() {
         f
     } else {
-        rc(Expr::App(f, args))
+        rc(ExprF::App(f, args))
     }
 }
 
@@ -351,100 +625,6 @@ fn add_ui(u: usize, i: isize) -> usize {
     }
 }
 
-/// Map over the immediate children of the passed Expr
-pub fn map_subexpr<S, T, A, B, F1, F2, F3, F4, F5>(
-    e: &Expr<S, A>,
-    map: F1,
-    map_note: F2,
-    map_embed: F3,
-    map_label: F4,
-    map_under_binder: F5,
-) -> Expr<T, B>
-where
-    F1: Fn(&SubExpr<S, A>) -> SubExpr<T, B>,
-    F2: FnOnce(&S) -> T,
-    F3: FnOnce(&A) -> B,
-    F4: Fn(&Label) -> Label,
-    F5: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<T, B>,
-{
-    use crate::Expr::*;
-    let map = &map;
-    let opt = |x: &Option<_>| x.as_ref().map(&map);
-    let vec = |x: &Vec<_>| x.iter().map(&map).collect();
-    let btmap = |x: &BTreeMap<_, _>| {
-        x.into_iter().map(|(k, v)| (map_label(k), map(v))).collect()
-    };
-    match e {
-        Const(k) => Const(*k),
-        Var(V(l, n)) => Var(V(map_label(l), *n)),
-        Lam(l, t, b) => Lam(map_label(l), map(t), map_under_binder(l, b)),
-        Pi(l, t, b) => Pi(map_label(l), map(t), map_under_binder(l, b)),
-        App(f, args) => App(map(f), vec(args)),
-        Let(l, t, a, b) => {
-            Let(map_label(l), opt(t), map(a), map_under_binder(l, b))
-        }
-        Annot(x, t) => Annot(map(x), map(t)),
-        Builtin(v) => Builtin(*v),
-        BoolLit(b) => BoolLit(*b),
-        BoolIf(b, t, f) => BoolIf(map(b), map(t), map(f)),
-        NaturalLit(n) => NaturalLit(*n),
-        IntegerLit(n) => IntegerLit(*n),
-        DoubleLit(n) => DoubleLit(*n),
-        TextLit(t) => TextLit(t.map(&map)),
-        BinOp(o, x, y) => BinOp(*o, map(x), map(y)),
-        EmptyListLit(t) => EmptyListLit(map(t)),
-        NEListLit(es) => NEListLit(vec(es)),
-        EmptyOptionalLit(t) => EmptyOptionalLit(map(t)),
-        NEOptionalLit(e) => NEOptionalLit(map(e)),
-        RecordType(kts) => RecordType(btmap(kts)),
-        RecordLit(kvs) => RecordLit(btmap(kvs)),
-        UnionType(kts) => UnionType(btmap(kts)),
-        UnionLit(k, v, kvs) => UnionLit(map_label(k), map(v), btmap(kvs)),
-        Merge(x, y, t) => Merge(map(x), map(y), opt(t)),
-        Field(e, l) => Field(map(e), map_label(l)),
-        Projection(e, ls) => {
-            Projection(map(e), ls.iter().map(&map_label).collect())
-        }
-        Note(n, e) => Note(map_note(n), map(e)),
-        Embed(a) => Embed(map_embed(a)),
-    }
-}
-
-pub fn map_subexpr_rc_binder<S, A, F1, F2>(
-    e: &SubExpr<S, A>,
-    map_expr: F1,
-    map_under_binder: F2,
-) -> SubExpr<S, A>
-where
-    F1: Fn(&SubExpr<S, A>) -> SubExpr<S, A>,
-    F2: FnOnce(&Label, &SubExpr<S, A>) -> SubExpr<S, A>,
-{
-    match e.as_ref() {
-        Expr::Embed(_) => Rc::clone(e),
-        Expr::Note(_, e) => {
-            map_subexpr_rc_binder(e, map_expr, map_under_binder)
-        }
-        _ => rc(map_subexpr(
-            e,
-            map_expr,
-            |_| unreachable!(),
-            |_| unreachable!(),
-            Label::clone,
-            map_under_binder,
-        )),
-    }
-}
-
-pub fn map_subexpr_rc<S, A, F1>(
-    e: &SubExpr<S, A>,
-    map_expr: F1,
-) -> SubExpr<S, A>
-where
-    F1: Fn(&SubExpr<S, A>) -> SubExpr<S, A>,
-{
-    map_subexpr_rc_binder(e, &map_expr, |_, e| map_expr(e))
-}
-
 /// `shift` is used by both normalization and type-checking to avoid variable
 /// capture by shifting variable indices
 ///
@@ -518,10 +698,10 @@ where
 ///
 pub fn shift<S, A>(
     delta: isize,
-    var: &V,
-    in_expr: &Rc<Expr<S, A>>,
-) -> Rc<Expr<S, A>> {
-    use crate::Expr::*;
+    var: &V<Label>,
+    in_expr: &SubExpr<S, A>,
+) -> SubExpr<S, A> {
+    use crate::ExprF::*;
     let V(x, n) = var;
     let under_binder = |y: &Label, e: &SubExpr<_, _>| {
         let n = if x == y { n + 1 } else { *n };
@@ -532,11 +712,7 @@ pub fn shift<S, A>(
         Var(V(y, m)) if x == y && n <= m => {
             rc(Var(V(y.clone(), add_ui(*m, delta))))
         }
-        _ => map_subexpr_rc_binder(
-            in_expr,
-            |e| shift(delta, var, e),
-            under_binder,
-        ),
+        _ => in_expr.map_ref(|e| shift(delta, var, e), under_binder),
     }
 }
 
@@ -547,11 +723,11 @@ pub fn shift<S, A>(
 /// ```
 ///
 pub fn subst<S, A>(
-    var: &V,
-    value: &Rc<Expr<S, A>>,
-    in_expr: &Rc<Expr<S, A>>,
-) -> Rc<Expr<S, A>> {
-    use crate::Expr::*;
+    var: &V<Label>,
+    value: &SubExpr<S, A>,
+    in_expr: &SubExpr<S, A>,
+) -> SubExpr<S, A> {
+    use crate::ExprF::*;
     let under_binder = |y: &Label, e: &SubExpr<_, _>| {
         let V(x, n) = var;
         let n = if x == y { n + 1 } else { *n };
@@ -559,11 +735,7 @@ pub fn subst<S, A>(
         subst(newvar, &shift(1, &V(y.clone(), 0), value), e)
     };
     match in_expr.as_ref() {
-        Var(v) if var == v => Rc::clone(value),
-        _ => map_subexpr_rc_binder(
-            in_expr,
-            |e| subst(var, value, e),
-            under_binder,
-        ),
+        Var(v) if var == v => SubExpr::clone(value),
+        _ => in_expr.map_ref(|e| subst(var, value, e), under_binder),
     }
 }
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index b0d80c0..e18a709 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -13,10 +13,12 @@ use crate::*;
 // their own crate because they are quite general and useful. For now they
 // are here and hopefully you can figure out how they work.
 
+use crate::ExprF::*;
+
 type ParsedExpr = Expr<X, Import>;
 type ParsedSubExpr = SubExpr<X, Import>;
-type ParsedText = InterpolatedText<X, Import>;
-type ParsedTextContents = InterpolatedTextContents<X, Import>;
+type ParsedText = InterpolatedText<SubExpr<X, Import>>;
+type ParsedTextContents = InterpolatedTextContents<SubExpr<X, Import>>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
@@ -28,9 +30,9 @@ enum Either<A, B> {
     Right(B),
 }
 
-impl Builtin {
+impl crate::Builtin {
     pub fn parse(s: &str) -> Option<Self> {
-        use self::Builtin::*;
+        use crate::Builtin::*;
         match s {
             "Bool" => Some(Bool),
             "Natural" => Some(Natural),
@@ -279,7 +281,7 @@ make_parser! {
     ));
     rule!(nonreserved_label<Label>; children!(
         [label(l)] => {
-            if Builtin::parse(&String::from(&l)).is_some() {
+            if crate::Builtin::parse(&String::from(&l)).is_some() {
                 Err(
                     format!("Builtin names are not allowed as bound variables")
                 )?
@@ -541,13 +543,13 @@ make_parser! {
 
     rule!(import<ParsedExpr> as expression; children!(
         [import_hashed(location_hashed)] => {
-            Expr::Embed(Import {
+            Embed(Import {
                 mode: ImportMode::Code,
                 location_hashed
             })
         },
         [import_hashed(location_hashed), Text(_)] => {
-            Expr::Embed(Import {
+            Embed(Import {
                 mode: ImportMode::RawText,
                 location_hashed
             })
@@ -563,28 +565,28 @@ make_parser! {
 
     rule!(expression<ParsedExpr> as expression; children!(
         [lambda(()), nonreserved_label(l), expression(typ), arrow(()), expression(body)] => {
-            Expr::Lam(l, rc(typ), rc(body))
+            Lam(l, rc(typ), rc(body))
         },
         [if_(()), expression(cond), expression(left), expression(right)] => {
-            Expr::BoolIf(rc(cond), rc(left), rc(right))
+            BoolIf(rc(cond), rc(left), rc(right))
         },
         [let_binding(bindings).., in_(()), expression(final_expr)] => {
             bindings.fold(
                 final_expr,
-                |acc, x| Expr::Let(x.0, x.1, x.2, rc(acc))
+                |acc, x| Let(x.0, x.1, x.2, rc(acc))
             )
         },
         [forall(()), nonreserved_label(l), expression(typ), arrow(()), expression(body)] => {
-            Expr::Pi(l, rc(typ), rc(body))
+            Pi(l, rc(typ), rc(body))
         },
         [expression(typ), arrow(()), expression(body)] => {
-            Expr::Pi("_".into(), rc(typ), rc(body))
+            Pi("_".into(), rc(typ), rc(body))
         },
         [merge(()), expression(x), expression(y), expression(z)] => {
-            Expr::Merge(rc(x), rc(y), Option::Some(rc(z)))
+            Merge(rc(x), rc(y), Option::Some(rc(z)))
         },
         [merge(()), expression(x), expression(y)] => {
-            Expr::Merge(rc(x), rc(y), Option::None)
+            Merge(rc(x), rc(y), Option::None)
         },
         [expression(e)] => e,
     ));
@@ -601,108 +603,108 @@ make_parser! {
 
     rule!(empty_collection<ParsedExpr> as expression; children!(
         [List(_), expression(t)] => {
-            Expr::EmptyListLit(rc(t))
+            EmptyListLit(rc(t))
         },
         [Optional(_), expression(t)] => {
-            Expr::EmptyOptionalLit(rc(t))
+            EmptyOptionalLit(rc(t))
         },
     ));
 
     rule!(non_empty_optional<ParsedExpr> as expression; children!(
         [expression(x), Optional(_), expression(t)] => {
-            Expr::Annot(rc(Expr::NEOptionalLit(rc(x))), rc(t))
+            Annot(rc(NEOptionalLit(rc(x))), rc(t))
         }
     ));
 
     rule!(import_alt_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::ImportAlt;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::ImportAlt;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(or_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolOr;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::BoolOr;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(plus_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::NaturalPlus;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::NaturalPlus;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(text_append_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::TextAppend;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::TextAppend;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(list_append_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::ListAppend;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::ListAppend;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(and_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolAnd;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::BoolAnd;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(combine_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::Combine;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::Combine;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(prefer_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::Prefer;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::Prefer;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(combine_types_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::CombineTypes;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::CombineTypes;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(times_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::NaturalTimes;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::NaturalTimes;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(equal_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolEQ;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::BoolEQ;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
     rule!(not_equal_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(first), expression(rest)..] => {
-            let o = BinOp::BoolNE;
-            rest.fold(first, |acc, e| Expr::BinOp(o, rc(acc), rc(e)))
+            let o = crate::BinOp::BoolNE;
+            rest.fold(first, |acc, e| BinOp(o, rc(acc), rc(e)))
         },
     ));
 
     rule!(annotated_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
         [expression(e), expression(annot)] => {
-            Expr::Annot(rc(e), rc(annot))
+            Annot(rc(e), rc(annot))
         },
     ));
 
@@ -710,12 +712,12 @@ make_parser! {
 
     rule!(application_expression<ParsedExpr> as expression; children!(
         [expression(e)] => e,
-        [expression(Expr::Builtin(Builtin::OptionalNone)),
+        [expression(Builtin(crate::Builtin::OptionalNone)),
                 expression(e), expression(rest)..] => {
-            app(Expr::EmptyOptionalLit(rc(e)), rest.map(rc).collect())
+            app(EmptyOptionalLit(rc(e)), rest.map(rc).collect())
         },
         [Some(()), expression(e), expression(rest)..] => {
-            app(Expr::NEOptionalLit(rc(e)), rest.map(rc).collect())
+            app(NEOptionalLit(rc(e)), rest.map(rc).collect())
         },
         [expression(first), expression(rest)..] => {
             app(first, rest.map(rc).collect())
@@ -726,8 +728,8 @@ make_parser! {
         [expression(e)] => e,
         [expression(first), selector(rest)..] => {
             rest.fold(first, |acc, e| match e {
-                Either::Left(l) => Expr::Field(rc(acc), l),
-                Either::Right(ls) => Expr::Projection(rc(acc), ls),
+                Either::Left(l) => Field(rc(acc), l),
+                Either::Right(ls) => Projection(rc(acc), ls),
             })
         }
     ));
@@ -742,61 +744,61 @@ make_parser! {
     ));
 
     rule!(primitive_expression<ParsedExpr> as expression; children!(
-        [double_literal(n)] => Expr::DoubleLit(n),
-        [natural_literal(n)] => Expr::NaturalLit(n),
-        [integer_literal(n)] => Expr::IntegerLit(n),
-        [double_quote_literal(s)] => Expr::TextLit(s),
-        [single_quote_literal(s)] => Expr::TextLit(s),
+        [double_literal(n)] => DoubleLit(n),
+        [natural_literal(n)] => NaturalLit(n),
+        [integer_literal(n)] => IntegerLit(n),
+        [double_quote_literal(s)] => TextLit(s),
+        [single_quote_literal(s)] => TextLit(s),
         [expression(e)] => e,
     ));
 
     rule!(identifier<ParsedExpr> as expression; children!(
         [label(l), natural_literal(idx)] => {
             let name = String::from(&l);
-            match Builtin::parse(name.as_str()) {
-                Option::Some(b) => Expr::Builtin(b),
+            match crate::Builtin::parse(name.as_str()) {
+                Option::Some(b) => Builtin(b),
                 Option::None => match name.as_str() {
-                    "True" => Expr::BoolLit(true),
-                    "False" => Expr::BoolLit(false),
-                    "Type" => Expr::Const(Const::Type),
-                    "Kind" => Expr::Const(Const::Kind),
-                    _ => Expr::Var(V(l, idx)),
+                    "True" => BoolLit(true),
+                    "False" => BoolLit(false),
+                    "Type" => Const(crate::Const::Type),
+                    "Kind" => Const(crate::Const::Kind),
+                    _ => Var(V(l, idx)),
                 }
             }
         },
         [label(l)] => {
             let name = String::from(&l);
-            match Builtin::parse(name.as_str()) {
-                Option::Some(b) => Expr::Builtin(b),
+            match crate::Builtin::parse(name.as_str()) {
+                Option::Some(b) => Builtin(b),
                 Option::None => match name.as_str() {
-                    "True" => Expr::BoolLit(true),
-                    "False" => Expr::BoolLit(false),
-                    "Type" => Expr::Const(Const::Type),
-                    "Kind" => Expr::Const(Const::Kind),
-                    _ => Expr::Var(V(l, 0)),
+                    "True" => BoolLit(true),
+                    "False" => BoolLit(false),
+                    "Type" => Const(crate::Const::Type),
+                    "Kind" => Const(crate::Const::Kind),
+                    _ => Var(V(l, 0)),
                 }
             }
         },
     ));
 
     rule!(empty_record_literal<ParsedExpr> as expression;
-        captured_str!(_) => Expr::RecordLit(BTreeMap::new())
+        captured_str!(_) => RecordLit(BTreeMap::new())
     );
 
     rule!(empty_record_type<ParsedExpr> as expression;
-        captured_str!(_) => Expr::RecordType(BTreeMap::new())
+        captured_str!(_) => RecordType(BTreeMap::new())
     );
 
     rule!(non_empty_record_type_or_literal<ParsedExpr> as expression; children!(
         [label(first_label), non_empty_record_type(rest)] => {
             let (first_expr, mut map) = rest;
             map.insert(first_label, rc(first_expr));
-            Expr::RecordType(map)
+            RecordType(map)
         },
         [label(first_label), non_empty_record_literal(rest)] => {
             let (first_expr, mut map) = rest;
             map.insert(first_label, rc(first_expr));
-            Expr::RecordLit(map)
+            RecordLit(map)
         },
     ));
 
@@ -824,13 +826,13 @@ make_parser! {
 
     rule!(union_type_or_literal<ParsedExpr> as expression; children!(
         [empty_union_type(_)] => {
-            Expr::UnionType(BTreeMap::new())
+            UnionType(BTreeMap::new())
         },
         [non_empty_union_type_or_literal((Option::Some((l, e)), entries))] => {
-            Expr::UnionLit(l, e, entries)
+            UnionLit(l, e, entries)
         },
         [non_empty_union_type_or_literal((Option::None, entries))] => {
-            Expr::UnionType(entries)
+            UnionType(entries)
         },
     ));
 
@@ -875,7 +877,7 @@ make_parser! {
     ));
 
     rule!(non_empty_list_literal<ParsedExpr> as expression; children!(
-        [expression(items)..] => Expr::NEListLit(items.map(rc).collect())
+        [expression(items)..] => NEListLit(items.map(rc).collect())
     ));
 
     rule!(final_expression<ParsedExpr> as expression; children!(
@@ -891,7 +893,7 @@ pub fn parse_expr(s: &str) -> ParseResult<ParsedSubExpr> {
         ParsedValue::expression(e) => Ok(rc(e)),
         _ => unreachable!(),
     }
-    // Ok(rc(Expr::BoolLit(false)))
+    // Ok(rc(BoolLit(false)))
 }
 
 #[test]
diff --git a/dhall_core/src/printer.rs b/dhall_core/src/printer.rs
index 1d1b063..746b863 100644
--- a/dhall_core/src/printer.rs
+++ b/dhall_core/src/printer.rs
@@ -8,6 +8,12 @@ impl<S, A: Display> Display for Expr<S, A> {
     }
 }
 
+impl<S, A: Display> Display for SubExpr<S, A> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+        self.as_ref().fmt(f)
+    }
+}
+
 //  There is a one-to-one correspondence between the formatter and the grammar. Each phase is
 //  named after a corresponding grammar group, and the structure of the formatter reflects
 //  the relationship between the corresponding grammar rules. This leads to the nice property
@@ -29,7 +35,7 @@ impl<S, A: Display> Expr<S, A> {
         f: &mut fmt::Formatter,
         phase: PrintPhase,
     ) -> Result<(), fmt::Error> {
-        use crate::Expr::*;
+        use crate::ExprF::*;
         use PrintPhase::*;
         match self {
             _ if phase == Paren => {
@@ -137,7 +143,7 @@ impl<S, A: Display> Expr<S, A> {
                 write!(f, " : ")?;
                 b.fmt(f)?;
             }
-            Expr::BinOp(op, a, b) => {
+            ExprF::BinOp(op, a, b) => {
                 // Precedence is magically handled by the ordering of BinOps.
                 if phase > PrintPhase::BinOp(*op) {
                     return self.fmt_phase(f, Paren);
@@ -146,7 +152,7 @@ impl<S, A: Display> Expr<S, A> {
                 write!(f, " {} ", op)?;
                 b.fmt_phase(f, PrintPhase::BinOp(*op))?;
             }
-            Expr::App(a, args) => {
+            ExprF::App(a, args) => {
                 if phase > PrintPhase::App {
                     return self.fmt_phase(f, Paren);
                 }
@@ -211,6 +217,16 @@ impl<S, A: Display> Expr<S, A> {
     }
 }
 
+impl<S, A: Display> SubExpr<S, A> {
+    fn fmt_phase(
+        &self,
+        f: &mut fmt::Formatter,
+        phase: PrintPhase,
+    ) -> Result<(), fmt::Error> {
+        self.0.as_ref().fmt_phase(f, phase)
+    }
+}
+
 fn fmt_list<T, I, F>(
     open: &str,
     sep: &str,
@@ -233,7 +249,7 @@ where
     f.write_str(close)
 }
 
-impl<S, A: Display> Display for InterpolatedText<S, A> {
+impl<SubExpr: Display + Clone> Display for InterpolatedText<SubExpr> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         f.write_str("\"")?;
         for x in self.iter() {
@@ -446,7 +462,7 @@ impl Display for Scheme {
     }
 }
 
-impl Display for V {
+impl<Label: Display> Display for V<Label> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         let V(x, n) = self;
         x.fmt(f)?;
diff --git a/dhall_core/src/text.rs b/dhall_core/src/text.rs
index d377877..9500f32 100644
--- a/dhall_core/src/text.rs
+++ b/dhall_core/src/text.rs
@@ -1,18 +1,16 @@
-use crate::*;
 use std::iter::FromIterator;
 use std::ops::Add;
-use std::rc::Rc;
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub struct InterpolatedText<Note, Embed> {
+pub struct InterpolatedText<SubExpr> {
     head: String,
-    tail: Vec<(Rc<Expr<Note, Embed>>, String)>,
+    tail: Vec<(SubExpr, String)>,
 }
 
-impl<N, E> From<(String, Vec<(Rc<Expr<N, E>>, String)>)>
-    for InterpolatedText<N, E>
+impl<SubExpr> From<(String, Vec<(SubExpr, String)>)>
+    for InterpolatedText<SubExpr>
 {
-    fn from(x: (String, Vec<(Rc<Expr<N, E>>, String)>)) -> Self {
+    fn from(x: (String, Vec<(SubExpr, String)>)) -> Self {
         InterpolatedText {
             head: x.0,
             tail: x.1,
@@ -20,7 +18,7 @@ impl<N, E> From<(String, Vec<(Rc<Expr<N, E>>, String)>)>
     }
 }
 
-impl<N, E> From<String> for InterpolatedText<N, E> {
+impl<SubExpr> From<String> for InterpolatedText<SubExpr> {
     fn from(s: String) -> Self {
         InterpolatedText {
             head: s,
@@ -30,41 +28,55 @@ impl<N, E> From<String> for InterpolatedText<N, E> {
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum InterpolatedTextContents<Note, Embed> {
+pub enum InterpolatedTextContents<SubExpr> {
     Text(String),
-    Expr(SubExpr<Note, Embed>),
+    Expr(SubExpr),
 }
 
-impl<N, E> InterpolatedText<N, E> {
-    pub fn map<N2, E2, F>(&self, mut f: F) -> InterpolatedText<N2, E2>
+impl<SubExpr> InterpolatedText<SubExpr> {
+    pub fn map<SubExpr2, F>(self, mut f: F) -> InterpolatedText<SubExpr2>
     where
-        F: FnMut(&Rc<Expr<N, E>>) -> Rc<Expr<N2, E2>>,
+        F: FnMut(SubExpr) -> SubExpr2,
     {
         InterpolatedText {
             head: self.head.clone(),
-            tail: self.tail.iter().map(|(e, s)| (f(e), s.clone())).collect(),
+            tail: self
+                .tail
+                .into_iter()
+                .map(|(e, s)| (f(e), s.clone()))
+                .collect(),
+        }
+    }
+
+    pub fn as_ref(&self) -> InterpolatedText<&SubExpr> {
+        InterpolatedText {
+            head: self.head.clone(),
+            tail: self.tail.iter().map(|(e, s)| (e, s.clone())).collect(),
         }
     }
 
     pub fn iter<'a>(
         &'a self,
-    ) -> impl Iterator<Item = InterpolatedTextContents<N, E>> + 'a {
+    ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a
+    where
+        SubExpr: Clone,
+    {
         use std::iter::once;
         once(InterpolatedTextContents::Text(self.head.clone())).chain(
             self.tail.iter().flat_map(|(e, s)| {
-                once(InterpolatedTextContents::Expr(Rc::clone(e)))
+                once(InterpolatedTextContents::Expr(SubExpr::clone(e)))
                     .chain(once(InterpolatedTextContents::Text(s.clone())))
             }),
         )
     }
 }
 
-impl<'a, N: 'a, E: 'a> FromIterator<InterpolatedTextContents<N, E>>
-    for InterpolatedText<N, E>
+impl<'a, SubExpr: Clone + 'a> FromIterator<InterpolatedTextContents<SubExpr>>
+    for InterpolatedText<SubExpr>
 {
     fn from_iter<T>(iter: T) -> Self
     where
-        T: IntoIterator<Item = InterpolatedTextContents<N, E>>,
+        T: IntoIterator<Item = InterpolatedTextContents<SubExpr>>,
     {
         let mut res = InterpolatedText {
             head: "".to_owned(),
@@ -84,9 +96,9 @@ impl<'a, N: 'a, E: 'a> FromIterator<InterpolatedTextContents<N, E>>
     }
 }
 
-impl<N, E> Add for &InterpolatedText<N, E> {
-    type Output = InterpolatedText<N, E>;
-    fn add(self, rhs: &InterpolatedText<N, E>) -> Self::Output {
+impl<SubExpr: Clone> Add for &InterpolatedText<SubExpr> {
+    type Output = InterpolatedText<SubExpr>;
+    fn add(self, rhs: &InterpolatedText<SubExpr>) -> Self::Output {
         self.iter().chain(rhs.iter()).collect()
     }
 }
diff --git a/dhall_generator/src/dhall_expr.rs b/dhall_generator/src/dhall_expr.rs
index 41e558b..9da23b6 100644
--- a/dhall_generator/src/dhall_expr.rs
+++ b/dhall_generator/src/dhall_expr.rs
@@ -4,113 +4,123 @@ use dhall_core::*;
 use proc_macro2::TokenStream;
 use quote::quote;
 use std::collections::BTreeMap;
-use std::rc::Rc;
 
 pub fn dhall_expr(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
     let input_str = input.to_string();
     let expr: SubExpr<X, Import> = parse_expr(&input_str).unwrap();
     let no_import =
         |_: &Import| -> X { panic!("Don't use import in dhall!()") };
-    let expr = rc(expr.map_embed(&no_import));
-    let output = dhall_to_tokenstream_bx(&expr, &Context::new());
+    let expr = rc(expr.as_ref().map_embed(&no_import));
+    let output = quote_subexpr(&expr, &Context::new());
     output.into()
 }
 
-// Returns an expression of type Expr<_, _>. Expects interpolated variables
-// to be of type Rc<Expr<_, _>>.
-fn dhall_to_tokenstream(
-    expr: &DhallExpr,
-    ctx: &Context<Label, ()>,
-) -> TokenStream {
-    use dhall_core::Expr::*;
-    match expr.as_ref() {
-        Var(_) => {
-            let v = dhall_to_tokenstream_bx(expr, ctx);
-            quote! { *#v }
-        }
+// Returns an expression of type ExprF<T, _, _>, where T is the
+// type of the subexpressions after interpolation.
+pub fn quote_expr<TS>(expr: ExprF<TS, Label, X, X>) -> TokenStream
+where
+    TS: quote::ToTokens + std::fmt::Debug,
+{
+    let quote_map = |m: BTreeMap<Label, TS>| -> TokenStream {
+        let entries = m.into_iter().map(|(k, v)| {
+            let k = quote_label(&k);
+            quote!(m.insert(#k, #v);)
+        });
+        quote! { {
+            use std::collections::BTreeMap;
+            let mut m = BTreeMap::new();
+            #( #entries )*
+            m
+        } }
+    };
+
+    let quote_vec = |e: Vec<TS>| -> TokenStream {
+        quote! { vec![ #(#e),* ] }
+    };
+
+    use dhall_core::ExprF::*;
+    match expr {
+        Var(_) => unreachable!(),
         Pi(x, t, b) => {
-            let t = dhall_to_tokenstream_bx(t, ctx);
-            let b = dhall_to_tokenstream_bx(b, &ctx.insert(x.clone(), ()));
-            let x = label_to_tokenstream(x);
-            quote! { dhall_core::Expr::Pi(#x, #t, #b) }
+            let x = quote_label(&x);
+            quote! { dhall_core::ExprF::Pi(#x, #t, #b) }
         }
         Lam(x, t, b) => {
-            let t = dhall_to_tokenstream_bx(t, ctx);
-            let b = dhall_to_tokenstream_bx(b, &ctx.insert(x.clone(), ()));
-            let x = label_to_tokenstream(x);
-            quote! { dhall_core::Expr::Lam(#x, #t, #b) }
+            let x = quote_label(&x);
+            quote! { dhall_core::ExprF::Lam(#x, #t, #b) }
         }
         App(f, a) => {
-            let f = dhall_to_tokenstream_bx(f, ctx);
-            let a = vec_to_tokenstream(a, ctx);
-            quote! { dhall_core::Expr::App(#f, #a) }
+            let a = quote_vec(a);
+            quote! { dhall_core::ExprF::App(#f, #a) }
         }
         Const(c) => {
-            let c = const_to_tokenstream(*c);
-            quote! { dhall_core::Expr::Const(#c) }
+            let c = quote_const(c);
+            quote! { dhall_core::ExprF::Const(#c) }
         }
         Builtin(b) => {
-            let b = builtin_to_tokenstream(*b);
-            quote! { dhall_core::Expr::Builtin(#b) }
+            let b = quote_builtin(b);
+            quote! { dhall_core::ExprF::Builtin(#b) }
         }
         BinOp(o, a, b) => {
-            let o = binop_to_tokenstream(*o);
-            let a = dhall_to_tokenstream_bx(a, ctx);
-            let b = dhall_to_tokenstream_bx(b, ctx);
-            quote! { dhall_core::Expr::BinOp(#o, #a, #b) }
+            let o = quote_binop(o);
+            quote! { dhall_core::ExprF::BinOp(#o, #a, #b) }
         }
         NaturalLit(n) => {
-            quote! { dhall_core::Expr::NaturalLit(#n) }
+            quote! { dhall_core::ExprF::NaturalLit(#n) }
         }
         BoolLit(b) => {
-            quote! { dhall_core::Expr::BoolLit(#b) }
+            quote! { dhall_core::ExprF::BoolLit(#b) }
         }
         EmptyOptionalLit(x) => {
-            let x = dhall_to_tokenstream_bx(x, ctx);
-            quote! { dhall_core::Expr::EmptyOptionalLit(#x) }
+            quote! { dhall_core::ExprF::EmptyOptionalLit(#x) }
         }
         NEOptionalLit(x) => {
-            let x = dhall_to_tokenstream_bx(x, ctx);
-            quote! { dhall_core::Expr::NEOptionalLit(#x) }
+            quote! { dhall_core::ExprF::NEOptionalLit(#x) }
         }
         EmptyListLit(t) => {
-            let t = dhall_to_tokenstream_bx(t, ctx);
-            quote! { dhall_core::Expr::EmptyListLit(#t) }
+            quote! { dhall_core::ExprF::EmptyListLit(#t) }
         }
         NEListLit(es) => {
-            let es = vec_to_tokenstream(es, ctx);
-            quote! { dhall_core::Expr::NEListLit(#es) }
+            let es = quote_vec(es);
+            quote! { dhall_core::ExprF::NEListLit(#es) }
         }
         RecordType(m) => {
-            let m = map_to_tokenstream(m, ctx);
-            quote! { dhall_core::Expr::RecordType(#m) }
+            let m = quote_map(m);
+            quote! { dhall_core::ExprF::RecordType(#m) }
         }
         RecordLit(m) => {
-            let m = map_to_tokenstream(m, ctx);
-            quote! { dhall_core::Expr::RecordLit(#m) }
+            let m = quote_map(m);
+            quote! { dhall_core::ExprF::RecordLit(#m) }
         }
         UnionType(m) => {
-            let m = map_to_tokenstream(m, ctx);
-            quote! { dhall_core::Expr::UnionType(#m) }
+            let m = quote_map(m);
+            quote! { dhall_core::ExprF::UnionType(#m) }
         }
         e => unimplemented!("{:?}", e),
     }
 }
 
-// Returns an expression of type Rc<Expr<_, _>>
-fn dhall_to_tokenstream_bx(
-    expr: &DhallExpr,
+// Returns an expression of type SubExpr<_, _>. Expects interpolated variables
+// to be of type SubExpr<_, _>.
+fn quote_subexpr(
+    expr: &SubExpr<X, X>,
     ctx: &Context<Label, ()>,
 ) -> TokenStream {
-    use dhall_core::Expr::*;
-    match expr.as_ref() {
-        Var(V(s, n)) => {
-            match ctx.lookup(&s, *n) {
+    use dhall_core::ExprF::*;
+    match expr.as_ref().map_ref(
+        |e| quote_subexpr(e, ctx),
+        |l, e| quote_subexpr(e, &ctx.insert(l.clone(), ())),
+        |_| unreachable!(),
+        |_| unreachable!(),
+        |l| l.clone(),
+    ) {
+        Var(V(ref s, n)) => {
+            match ctx.lookup(s, n) {
                 // Non-free variable; interpolates as itself
                 Some(()) => {
                     let s: String = s.into();
                     let var = quote! { dhall_core::V(#s.into(), #n) };
-                    bx(quote! { dhall_core::Expr::Var(#var) })
+                    bx(quote! { dhall_core::ExprF::Var(#var) })
                 }
                 // Free variable; interpolates as a rust variable
                 None => {
@@ -124,51 +134,25 @@ fn dhall_to_tokenstream_bx(
                 }
             }
         }
-        _ => bx(dhall_to_tokenstream(expr, ctx)),
+        e => bx(quote_expr(e)),
     }
 }
 
-fn builtin_to_tokenstream(b: Builtin) -> TokenStream {
+fn quote_builtin(b: Builtin) -> TokenStream {
     format!("dhall_core::Builtin::{:?}", b).parse().unwrap()
 }
 
-fn const_to_tokenstream(c: Const) -> TokenStream {
+fn quote_const(c: Const) -> TokenStream {
     format!("dhall_core::Const::{:?}", c).parse().unwrap()
 }
 
-fn binop_to_tokenstream(b: BinOp) -> TokenStream {
+fn quote_binop(b: BinOp) -> TokenStream {
     format!("dhall_core::BinOp::{:?}", b).parse().unwrap()
 }
 
-fn label_to_tokenstream(l: &Label) -> TokenStream {
+fn quote_label(l: &Label) -> TokenStream {
     let l = String::from(l);
-    quote! { #l.into() }
-}
-
-fn map_to_tokenstream(
-    m: &BTreeMap<Label, Rc<Expr<X, X>>>,
-    ctx: &Context<Label, ()>,
-) -> TokenStream {
-    let (keys, values): (Vec<TokenStream>, Vec<TokenStream>) = m
-        .iter()
-        .map(|(k, v)| {
-            (label_to_tokenstream(k), dhall_to_tokenstream_bx(&*v, ctx))
-        })
-        .unzip();
-    quote! { {
-        use std::collections::BTreeMap;
-        let mut m = BTreeMap::new();
-        #( m.insert(#keys, #values); )*
-        m
-    } }
-}
-
-fn vec_to_tokenstream(
-    e: &Vec<DhallExpr>,
-    ctx: &Context<Label, ()>,
-) -> TokenStream {
-    let e = e.iter().map(|x| dhall_to_tokenstream_bx(x, ctx));
-    quote! { vec![ #(#e),* ] }
+    quote! { dhall_core::Label::from(#l) }
 }
 
 fn bx(x: TokenStream) -> TokenStream {
diff --git a/dhall_generator/src/dhall_type.rs b/dhall_generator/src/dhall_type.rs
index ac8eb4e..ec023bc 100644
--- a/dhall_generator/src/dhall_type.rs
+++ b/dhall_generator/src/dhall_type.rs
@@ -39,21 +39,17 @@ pub fn derive_for_struct(
             .collect(),
         syn::Fields::Unit => vec![],
     };
-    let fields = fields.into_iter().map(|(name, ty)| {
-        constraints.push(ty.clone());
-        quote! {
-            m.insert(
-                dhall_core::Label::from(#name),
-                <#ty as dhall::Type>::get_type()
-            );
-        }
-    });
-    Ok(quote! { dhall_core::rc(dhall_core::Expr::RecordType({
-        use std::collections::BTreeMap;
-        let mut m = BTreeMap::new();
-        #(#fields)*
-        m
-    })) })
+    let fields = fields
+        .into_iter()
+        .map(|(name, ty)| {
+            let name = dhall_core::Label::from(name);
+            constraints.push(ty.clone());
+            (name, quote!(<#ty as dhall::Type>::get_type()))
+        })
+        .collect();
+    let record =
+        crate::dhall_expr::quote_expr(dhall_core::ExprF::RecordType(fields));
+    Ok(quote! { dhall_core::rc(#record) })
 }
 
 pub fn derive_for_enum(
@@ -64,7 +60,7 @@ pub fn derive_for_enum(
         .variants
         .iter()
         .map(|v| {
-            let name = v.ident.to_string();
+            let name = dhall_core::Label::from(v.ident.to_string());
             let ty = match &v.fields {
                 syn::Fields::Unnamed(fields) if fields.unnamed.is_empty() => {
                     Err(Error::new(
@@ -92,21 +88,13 @@ pub fn derive_for_enum(
             };
             let ty = ty?;
             constraints.push(ty.clone());
-            Ok(quote! {
-                m.insert(
-                    dhall_core::Label::from(#name),
-                    <#ty as dhall::Type>::get_type()
-                );
-            })
+            Ok((name, quote!(<#ty as dhall::Type>::get_type())))
         })
-        .collect::<Result<Vec<_>, Error>>()?;
+        .collect::<Result<_, Error>>()?;
 
-    Ok(quote! { dhall_core::rc(dhall_core::Expr::UnionType({
-        use std::collections::BTreeMap;
-        let mut m = BTreeMap::new();
-        #(#variants)*
-        m
-    })) })
+    let union =
+        crate::dhall_expr::quote_expr(dhall_core::ExprF::UnionType(variants));
+    Ok(quote! { dhall_core::rc(#union) })
 }
 
 pub fn derive_type_inner(
@@ -168,9 +156,7 @@ pub fn derive_type_inner(
     // Ensure that all the fields have a Type impl
     let mut where_clause = orig_where_clause.clone();
     for ty in constraints.iter() {
-        where_clause
-            .predicates
-            .push(parse_quote!(#ty: dhall::Type));
+        where_clause.predicates.push(parse_quote!(#ty: dhall::Type));
     }
 
     let ident = &input.ident;