Merge pull request #131 from Nadrieril/hir

Decouple main expression types

7 files changed, 194 insertions, 508 deletions

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index b493fdb..a479b53 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,5 +1,6 @@
+use crate::semantics::Universe;
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
-use crate::syntax::visitor::{self, ExprKindMutVisitor, ExprKindVisitor};
+use crate::syntax::visitor;
 use crate::syntax::*;
 
 pub type Integer = isize;
@@ -18,6 +19,12 @@ pub enum Const {
     Sort,
 }
 
+impl Const {
+    pub(crate) fn to_universe(self) -> Universe {
+        Universe::from_const(self)
+    }
+}
+
 /// Bound variable
 ///
 /// The `Label` field is the variable's name (i.e. \"`x`\").
@@ -96,20 +103,34 @@ pub enum Builtin {
 
 // Each node carries an annotation.
 #[derive(Debug, Clone)]
-pub struct Expr<Embed> {
-    kind: Box<ExprKind<Expr<Embed>, Embed>>,
+pub struct Expr {
+    kind: Box<ExprKind<Expr>>,
     span: Span,
 }
 
-pub type UnspannedExpr<Embed> = ExprKind<Expr<Embed>, Embed>;
+pub type UnspannedExpr = ExprKind<Expr>;
+
+/// Simple literals
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum LitKind {
+    ///  `True`
+    Bool(bool),
+    ///  `1`
+    Natural(Natural),
+    ///  `+2`
+    Integer(Integer),
+    ///  `3.24`
+    Double(Double),
+}
 
 /// 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, Hash)]
-pub enum ExprKind<SubExpr, Embed> {
+pub enum ExprKind<SubExpr> {
     Const(Const),
+    Lit(LitKind),
     ///  `x`
     ///  `x@n`
     Var(V),
@@ -131,16 +152,8 @@ pub enum ExprKind<SubExpr, Embed> {
     Builtin(Builtin),
     // Binary operations
     BinOp(BinOp, SubExpr, SubExpr),
-    ///  `True`
-    BoolLit(bool),
     ///  `if x then y else z`
     BoolIf(SubExpr, SubExpr, SubExpr),
-    ///  `1`
-    NaturalLit(Natural),
-    ///  `+2`
-    IntegerLit(Integer),
-    ///  `3.24`
-    DoubleLit(Double),
     ///  `"Some ${interpolated} text"`
     TextLit(InterpolatedText<SubExpr>),
     ///  `[] : t`
@@ -169,29 +182,21 @@ pub enum ExprKind<SubExpr, Embed> {
     Completion(SubExpr, SubExpr),
     /// `./some/path`
     Import(Import<SubExpr>),
-    /// Embeds the result of resolving an import
-    Embed(Embed),
 }
 
-impl<SE, E> ExprKind<SE, E> {
+impl<SE> ExprKind<SE> {
     pub fn traverse_ref_maybe_binder<'a, SE2, Err>(
         &'a self,
         visit: impl FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprKind<SE2, E>, Err>
-    where
-        E: Clone,
-    {
-        visitor::TraverseRefMaybeBinderVisitor(visit).visit(self)
+    ) -> Result<ExprKind<SE2>, Err> {
+        visitor::visit_ref(self, visit)
     }
 
     pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
         mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
         mut visit_under_binder: impl FnMut(&'a Label, &'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprKind<SE2, E>, Err>
-    where
-        E: Clone,
-    {
+    ) -> Result<ExprKind<SE2>, Err> {
         self.traverse_ref_maybe_binder(|l, x| match l {
             None => visit_subexpr(x),
             Some(l) => visit_under_binder(l, x),
@@ -201,27 +206,14 @@ impl<SE, E> ExprKind<SE, E> {
     pub(crate) fn traverse_ref<'a, SE2, Err>(
         &'a self,
         mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprKind<SE2, E>, Err>
-    where
-        E: Clone,
-    {
+    ) -> Result<ExprKind<SE2>, Err> {
         self.traverse_ref_maybe_binder(|_, e| visit_subexpr(e))
     }
 
-    fn traverse_mut<'a, Err>(
-        &'a mut self,
-        visit_subexpr: impl FnMut(&'a mut SE) -> Result<(), Err>,
-    ) -> Result<(), Err> {
-        visitor::TraverseMutVisitor { visit_subexpr }.visit(self)
-    }
-
     pub fn map_ref_maybe_binder<'a, SE2>(
         &'a self,
         mut map: impl FnMut(Option<&'a Label>, &'a SE) -> SE2,
-    ) -> ExprKind<SE2, E>
-    where
-        E: Clone,
-    {
+    ) -> ExprKind<SE2> {
         trivial_result(self.traverse_ref_maybe_binder(|l, x| Ok(map(l, x))))
     }
 
@@ -229,10 +221,7 @@ impl<SE, E> ExprKind<SE, E> {
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
         mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2,
-    ) -> ExprKind<SE2, E>
-    where
-        E: Clone,
-    {
+    ) -> ExprKind<SE2> {
         self.map_ref_maybe_binder(|l, x| match l {
             None => map_subexpr(x),
             Some(l) => map_under_binder(l, x),
@@ -242,34 +231,30 @@ impl<SE, E> ExprKind<SE, E> {
     pub fn map_ref<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
-    ) -> ExprKind<SE2, E>
-    where
-        E: Clone,
-    {
+    ) -> ExprKind<SE2> {
         self.map_ref_maybe_binder(|_, e| map_subexpr(e))
     }
-
-    pub fn map_mut<'a>(&'a mut self, mut map_subexpr: impl FnMut(&'a mut SE)) {
-        trivial_result(self.traverse_mut(|x| Ok(map_subexpr(x))))
-    }
 }
 
-impl<E> Expr<E> {
-    pub fn as_ref(&self) -> &UnspannedExpr<E> {
+impl Expr {
+    pub fn as_ref(&self) -> &UnspannedExpr {
+        &self.kind
+    }
+    pub fn kind(&self) -> &UnspannedExpr {
         &self.kind
     }
     pub fn span(&self) -> Span {
         self.span.clone()
     }
 
-    pub fn new(kind: UnspannedExpr<E>, span: Span) -> Self {
+    pub fn new(kind: UnspannedExpr, span: Span) -> Self {
         Expr {
             kind: Box::new(kind),
             span,
         }
     }
 
-    pub fn rewrap<E2>(&self, kind: UnspannedExpr<E2>) -> Expr<E2> {
+    pub fn rewrap(&self, kind: UnspannedExpr) -> Expr {
         Expr {
             kind: Box::new(kind),
             span: self.span.clone(),
@@ -281,43 +266,6 @@ impl<E> Expr<E> {
             span,
         }
     }
-
-    pub fn traverse_resolve_mut<Err, F1>(
-        &mut self,
-        f: &mut F1,
-    ) -> Result<(), Err>
-    where
-        E: Clone,
-        F1: FnMut(Import<Expr<E>>) -> Result<E, Err>,
-    {
-        match self.kind.as_mut() {
-            ExprKind::BinOp(BinOp::ImportAlt, l, r) => {
-                let garbage_expr = ExprKind::BoolLit(false);
-                let new_self = if l.traverse_resolve_mut(f).is_ok() {
-                    l
-                } else {
-                    r.traverse_resolve_mut(f)?;
-                    r
-                };
-                *self.kind =
-                    std::mem::replace(new_self.kind.as_mut(), garbage_expr);
-            }
-            _ => {
-                self.kind.traverse_mut(|e| e.traverse_resolve_mut(f))?;
-                if let ExprKind::Import(import) = self.kind.as_mut() {
-                    let garbage_import = Import {
-                        mode: ImportMode::Code,
-                        location: ImportLocation::Missing,
-                        hash: None,
-                    };
-                    // Move out of &mut import
-                    let import = std::mem::replace(import, garbage_import);
-                    *self.kind = ExprKind::Embed(f(import)?);
-                }
-            }
-        }
-        Ok(())
-    }
 }
 
 pub fn trivial_result<T>(x: Result<T, !>) -> T {
@@ -362,15 +310,15 @@ impl From<Label> for V {
     }
 }
 
-impl<Embed: PartialEq> std::cmp::PartialEq for Expr<Embed> {
+impl std::cmp::PartialEq for Expr {
     fn eq(&self, other: &Self) -> bool {
         self.kind == other.kind
     }
 }
 
-impl<Embed: Eq> std::cmp::Eq for Expr<Embed> {}
+impl std::cmp::Eq for Expr {}
 
-impl<Embed: std::hash::Hash> std::hash::Hash for Expr<Embed> {
+impl std::hash::Hash for Expr {
     fn hash<H>(&self, state: &mut H)
     where
         H: std::hash::Hasher,
diff --git a/dhall/src/syntax/ast/import.rs b/dhall/src/syntax/ast/import.rs
index da3e99b..7bde6e0 100644
--- a/dhall/src/syntax/ast/import.rs
+++ b/dhall/src/syntax/ast/import.rs
@@ -75,15 +75,6 @@ impl<SE> URL<SE> {
             headers,
         })
     }
-    pub fn traverse_mut<'a, Err>(
-        &'a mut self,
-        f: impl FnOnce(&'a mut SE) -> Result<(), Err>,
-    ) -> Result<(), Err> {
-        if let Some(header) = &mut self.headers {
-            f(header)?;
-        }
-        Ok(())
-    }
 }
 
 impl<SE> ImportLocation<SE> {
@@ -99,15 +90,6 @@ impl<SE> ImportLocation<SE> {
             Missing => Missing,
         })
     }
-    pub fn traverse_mut<'a, Err>(
-        &'a mut self,
-        f: impl FnOnce(&'a mut SE) -> Result<(), Err>,
-    ) -> Result<(), Err> {
-        if let ImportLocation::Remote(url) = self {
-            url.traverse_mut(f)?;
-        }
-        Ok(())
-    }
 }
 
 impl<SE> Import<SE> {
@@ -121,10 +103,4 @@ impl<SE> Import<SE> {
             hash: self.hash.clone(),
         })
     }
-    pub fn traverse_mut<'a, Err>(
-        &'a mut self,
-        f: impl FnOnce(&'a mut SE) -> Result<(), Err>,
-    ) -> Result<(), Err> {
-        self.location.traverse_mut(f)
-    }
 }
diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs
index 6a1ce7d..c361bc1 100644
--- a/dhall/src/syntax/ast/visitor.rs
+++ b/dhall/src/syntax/ast/visitor.rs
@@ -2,343 +2,112 @@ use std::iter::FromIterator;
 
 use crate::syntax::*;
 
-/// A visitor trait that can be used to traverse `ExprKind`s. We need this pattern so that Rust lets
-/// us have as much mutability as we can.
-/// For example, `traverse_ref_with_special_handling_of_binders` cannot be made using only
-/// `traverse_ref`, because `traverse_ref` takes a `FnMut` so we would need to pass multiple
-/// mutable reverences to this argument to `traverse_ref`. But Rust's ownership system is all about
-/// preventing exactly this ! So we have to be more clever. The visitor pattern allows us to have
-/// only one mutable thing the whole time: the visitor itself. The visitor can then carry around
-/// multiple closures or just one, and Rust is ok with either. See for example TraverseRefVisitor.
-pub trait ExprKindVisitor<'a, SE1, SE2, E1, E2>: Sized {
-    type Error;
-
-    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error>;
-    fn visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error>;
-
-    fn visit_subexpr_under_binder(
-        mut self,
-        _label: &'a Label,
-        subexpr: &'a SE1,
-    ) -> Result<SE2, Self::Error> {
-        self.visit_subexpr(subexpr)
-    }
-
-    fn visit(
-        self,
-        input: &'a ExprKind<SE1, E1>,
-    ) -> Result<ExprKind<SE2, E2>, Self::Error> {
-        visit_ref(self, input)
-    }
+fn vec<'a, T, U, Err>(
+    x: &'a [T],
+    f: impl FnMut(&'a T) -> Result<U, Err>,
+) -> Result<Vec<U>, Err> {
+    x.iter().map(f).collect()
 }
 
-/// Like `ExprKindVisitor`, but by mutable reference
-pub trait ExprKindMutVisitor<'a, SE, E>: Sized {
-    type Error;
-
-    fn visit_subexpr(&mut self, subexpr: &'a mut SE)
-        -> Result<(), Self::Error>;
-    fn visit_embed(self, _embed: &'a mut E) -> Result<(), Self::Error> {
-        Ok(())
-    }
-
-    fn visit_subexpr_under_binder(
-        mut self,
-        _label: &'a mut Label,
-        subexpr: &'a mut SE,
-    ) -> Result<(), Self::Error> {
-        self.visit_subexpr(subexpr)
-    }
+fn opt<'a, T, U, Err>(
+    x: &'a Option<T>,
+    f: impl FnOnce(&'a T) -> Result<U, Err>,
+) -> Result<Option<U>, Err> {
+    Ok(match x {
+        Some(x) => Some(f(x)?),
+        None => None,
+    })
+}
 
-    fn visit(self, input: &'a mut ExprKind<SE, E>) -> Result<(), Self::Error> {
-        visit_mut(self, input)
-    }
+fn dupmap<'a, SE1, SE2, T, Err>(
+    x: impl IntoIterator<Item = (&'a Label, &'a SE1)>,
+    mut f: impl FnMut(&'a SE1) -> Result<SE2, Err>,
+) -> Result<T, Err>
+where
+    SE1: 'a,
+    T: FromIterator<(Label, SE2)>,
+{
+    x.into_iter().map(|(k, x)| Ok((k.clone(), f(x)?))).collect()
 }
 
-fn visit_ref<'a, V, SE1, SE2, E1, E2>(
-    mut v: V,
-    input: &'a ExprKind<SE1, E1>,
-) -> Result<ExprKind<SE2, E2>, V::Error>
+fn optdupmap<'a, SE1, SE2, T, Err>(
+    x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>,
+    mut f: impl FnMut(&'a SE1) -> Result<SE2, Err>,
+) -> Result<T, Err>
 where
-    V: ExprKindVisitor<'a, SE1, SE2, E1, E2>,
+    SE1: 'a,
+    T: FromIterator<(Label, Option<SE2>)>,
 {
-    fn vec<'a, T, U, Err, F: FnMut(&'a T) -> Result<U, Err>>(
-        x: &'a [T],
-        f: F,
-    ) -> Result<Vec<U>, Err> {
-        x.iter().map(f).collect()
-    }
-    fn opt<'a, T, U, Err, F: FnOnce(&'a T) -> Result<U, Err>>(
-        x: &'a Option<T>,
-        f: F,
-    ) -> Result<Option<U>, Err> {
-        Ok(match x {
-            Some(x) => Some(f(x)?),
-            None => None,
+    x.into_iter()
+        .map(|(k, x)| {
+            Ok((
+                k.clone(),
+                match x {
+                    Some(x) => Some(f(x)?),
+                    None => None,
+                },
+            ))
         })
-    }
-    fn dupmap<'a, V, SE1, SE2, E1, E2, T>(
-        x: impl IntoIterator<Item = (&'a Label, &'a SE1)>,
-        mut v: V,
-    ) -> Result<T, V::Error>
-    where
-        SE1: 'a,
-        T: FromIterator<(Label, SE2)>,
-        V: ExprKindVisitor<'a, SE1, SE2, E1, E2>,
-    {
-        x.into_iter()
-            .map(|(k, x)| Ok((k.clone(), v.visit_subexpr(x)?)))
-            .collect()
-    }
-    fn optdupmap<'a, V, SE1, SE2, E1, E2, T>(
-        x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>,
-        mut v: V,
-    ) -> Result<T, V::Error>
-    where
-        SE1: 'a,
-        T: FromIterator<(Label, Option<SE2>)>,
-        V: ExprKindVisitor<'a, SE1, SE2, E1, E2>,
-    {
-        x.into_iter()
-            .map(|(k, x)| {
-                Ok((
-                    k.clone(),
-                    match x {
-                        Some(x) => Some(v.visit_subexpr(x)?),
-                        None => None,
-                    },
-                ))
-            })
-            .collect()
+        .collect()
+}
+
+pub(crate) fn visit_ref<'a, F, SE1, SE2, Err>(
+    input: &'a ExprKind<SE1>,
+    mut f: F,
+) -> Result<ExprKind<SE2>, Err>
+where
+    F: FnMut(Option<&'a Label>, &'a SE1) -> Result<SE2, Err>,
+{
+    // Can't use closures because of borrowing rules
+    macro_rules! expr {
+        ($e:expr) => {
+            f(None, $e)
+        };
+        ($l:expr, $e:expr) => {
+            f(Some($l), $e)
+        };
     }
 
     use crate::syntax::ExprKind::*;
     Ok(match input {
         Var(v) => Var(v.clone()),
         Lam(l, t, e) => {
-            let t = v.visit_subexpr(t)?;
-            let e = v.visit_subexpr_under_binder(l, e)?;
+            let t = expr!(t)?;
+            let e = expr!(l, e)?;
             Lam(l.clone(), t, e)
         }
         Pi(l, t, e) => {
-            let t = v.visit_subexpr(t)?;
-            let e = v.visit_subexpr_under_binder(l, e)?;
+            let t = expr!(t)?;
+            let e = expr!(l, e)?;
             Pi(l.clone(), t, e)
         }
         Let(l, t, a, e) => {
-            let t = opt(t, &mut |e| v.visit_subexpr(e))?;
-            let a = v.visit_subexpr(a)?;
-            let e = v.visit_subexpr_under_binder(l, e)?;
+            let t = opt(t, &mut |e| expr!(e))?;
+            let a = expr!(a)?;
+            let e = expr!(l, e)?;
             Let(l.clone(), t, a, e)
         }
-        App(f, a) => App(v.visit_subexpr(f)?, v.visit_subexpr(a)?),
-        Annot(x, t) => Annot(v.visit_subexpr(x)?, v.visit_subexpr(t)?),
+        App(f, a) => App(expr!(f)?, expr!(a)?),
+        Annot(x, t) => Annot(expr!(x)?, expr!(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.traverse_ref(|e| v.visit_subexpr(e))?),
-        BinOp(o, x, y) => BinOp(*o, v.visit_subexpr(x)?, v.visit_subexpr(y)?),
-        BoolIf(b, t, f) => BoolIf(
-            v.visit_subexpr(b)?,
-            v.visit_subexpr(t)?,
-            v.visit_subexpr(f)?,
-        ),
-        EmptyListLit(t) => EmptyListLit(v.visit_subexpr(t)?),
-        NEListLit(es) => NEListLit(vec(es, |e| v.visit_subexpr(e))?),
-        SomeLit(e) => SomeLit(v.visit_subexpr(e)?),
-        RecordType(kts) => RecordType(dupmap(kts, v)?),
-        RecordLit(kvs) => RecordLit(dupmap(kvs, v)?),
-        UnionType(kts) => UnionType(optdupmap(kts, v)?),
-        Merge(x, y, t) => Merge(
-            v.visit_subexpr(x)?,
-            v.visit_subexpr(y)?,
-            opt(t, |e| v.visit_subexpr(e))?,
-        ),
-        ToMap(x, t) => {
-            ToMap(v.visit_subexpr(x)?, opt(t, |e| v.visit_subexpr(e))?)
-        }
-        Field(e, l) => Field(v.visit_subexpr(e)?, l.clone()),
-        Projection(e, ls) => Projection(v.visit_subexpr(e)?, ls.clone()),
-        ProjectionByExpr(e, x) => {
-            ProjectionByExpr(v.visit_subexpr(e)?, v.visit_subexpr(x)?)
-        }
-        Completion(e, x) => {
-            Completion(v.visit_subexpr(e)?, v.visit_subexpr(x)?)
-        }
-        Assert(e) => Assert(v.visit_subexpr(e)?),
-        Import(i) => Import(i.traverse_ref(|e| v.visit_subexpr(e))?),
-        Embed(a) => Embed(v.visit_embed(a)?),
+        Lit(l) => Lit(l.clone()),
+        TextLit(t) => TextLit(t.traverse_ref(|e| expr!(e))?),
+        BinOp(o, x, y) => BinOp(*o, expr!(x)?, expr!(y)?),
+        BoolIf(b, t, f) => BoolIf(expr!(b)?, expr!(t)?, expr!(f)?),
+        EmptyListLit(t) => EmptyListLit(expr!(t)?),
+        NEListLit(es) => NEListLit(vec(es, |e| expr!(e))?),
+        SomeLit(e) => SomeLit(expr!(e)?),
+        RecordType(kts) => RecordType(dupmap(kts, |e| expr!(e))?),
+        RecordLit(kvs) => RecordLit(dupmap(kvs, |e| expr!(e))?),
+        UnionType(kts) => UnionType(optdupmap(kts, |e| expr!(e))?),
+        Merge(x, y, t) => Merge(expr!(x)?, expr!(y)?, opt(t, |e| expr!(e))?),
+        ToMap(x, t) => ToMap(expr!(x)?, opt(t, |e| expr!(e))?),
+        Field(e, l) => Field(expr!(e)?, l.clone()),
+        Projection(e, ls) => Projection(expr!(e)?, ls.clone()),
+        ProjectionByExpr(e, x) => ProjectionByExpr(expr!(e)?, expr!(x)?),
+        Completion(e, x) => Completion(expr!(e)?, expr!(x)?),
+        Assert(e) => Assert(expr!(e)?),
+        Import(i) => Import(i.traverse_ref(|e| expr!(e))?),
     })
 }
-
-fn visit_mut<'a, V, SE, E>(
-    mut v: V,
-    input: &'a mut ExprKind<SE, E>,
-) -> Result<(), V::Error>
-where
-    V: ExprKindMutVisitor<'a, SE, E>,
-{
-    fn vec<'a, V, SE, E>(v: &mut V, x: &'a mut Vec<SE>) -> Result<(), V::Error>
-    where
-        V: ExprKindMutVisitor<'a, SE, E>,
-    {
-        for x in x {
-            v.visit_subexpr(x)?;
-        }
-        Ok(())
-    }
-    fn opt<'a, V, SE, E>(
-        v: &mut V,
-        x: &'a mut Option<SE>,
-    ) -> Result<(), V::Error>
-    where
-        V: ExprKindMutVisitor<'a, SE, E>,
-    {
-        if let Some(x) = x {
-            v.visit_subexpr(x)?;
-        }
-        Ok(())
-    }
-    fn dupmap<'a, V, SE, E>(
-        mut v: V,
-        x: impl IntoIterator<Item = (&'a Label, &'a mut SE)>,
-    ) -> Result<(), V::Error>
-    where
-        SE: 'a,
-        V: ExprKindMutVisitor<'a, SE, E>,
-    {
-        for (_, x) in x {
-            v.visit_subexpr(x)?;
-        }
-        Ok(())
-    }
-    fn optdupmap<'a, V, SE, E>(
-        mut v: V,
-        x: impl IntoIterator<Item = (&'a Label, &'a mut Option<SE>)>,
-    ) -> Result<(), V::Error>
-    where
-        SE: 'a,
-        V: ExprKindMutVisitor<'a, SE, E>,
-    {
-        for (_, x) in x {
-            opt(&mut v, x)?;
-        }
-        Ok(())
-    }
-
-    use crate::syntax::ExprKind::*;
-    match input {
-        Var(_) | Const(_) | Builtin(_) | BoolLit(_) | NaturalLit(_)
-        | IntegerLit(_) | DoubleLit(_) => {}
-        Lam(l, t, e) => {
-            v.visit_subexpr(t)?;
-            v.visit_subexpr_under_binder(l, e)?;
-        }
-        Pi(l, t, e) => {
-            v.visit_subexpr(t)?;
-            v.visit_subexpr_under_binder(l, e)?;
-        }
-        Let(l, t, a, e) => {
-            opt(&mut v, t)?;
-            v.visit_subexpr(a)?;
-            v.visit_subexpr_under_binder(l, e)?;
-        }
-        App(f, a) => {
-            v.visit_subexpr(f)?;
-            v.visit_subexpr(a)?;
-        }
-        Annot(x, t) => {
-            v.visit_subexpr(x)?;
-            v.visit_subexpr(t)?;
-        }
-        TextLit(t) => t.traverse_mut(|e| v.visit_subexpr(e))?,
-        BinOp(_, x, y) => {
-            v.visit_subexpr(x)?;
-            v.visit_subexpr(y)?;
-        }
-        BoolIf(b, t, f) => {
-            v.visit_subexpr(b)?;
-            v.visit_subexpr(t)?;
-            v.visit_subexpr(f)?;
-        }
-        EmptyListLit(t) => v.visit_subexpr(t)?,
-        NEListLit(es) => vec(&mut v, es)?,
-        SomeLit(e) => v.visit_subexpr(e)?,
-        RecordType(kts) => dupmap(v, kts)?,
-        RecordLit(kvs) => dupmap(v, kvs)?,
-        UnionType(kts) => optdupmap(v, kts)?,
-        Merge(x, y, t) => {
-            v.visit_subexpr(x)?;
-            v.visit_subexpr(y)?;
-            opt(&mut v, t)?;
-        }
-        ToMap(x, t) => {
-            v.visit_subexpr(x)?;
-            opt(&mut v, t)?;
-        }
-        Field(e, _) => v.visit_subexpr(e)?,
-        Projection(e, _) => v.visit_subexpr(e)?,
-        ProjectionByExpr(e, x) => {
-            v.visit_subexpr(e)?;
-            v.visit_subexpr(x)?;
-        }
-        Completion(x, y) => {
-            v.visit_subexpr(x)?;
-            v.visit_subexpr(y)?;
-        }
-        Assert(e) => v.visit_subexpr(e)?,
-        Import(i) => i.traverse_mut(|e| v.visit_subexpr(e))?,
-        Embed(a) => v.visit_embed(a)?,
-    }
-    Ok(())
-}
-
-pub struct TraverseRefMaybeBinderVisitor<F>(pub F);
-
-impl<'a, SE, E, SE2, Err, F> ExprKindVisitor<'a, SE, SE2, E, E>
-    for TraverseRefMaybeBinderVisitor<F>
-where
-    SE: 'a,
-    E: 'a + Clone,
-    F: FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
-{
-    type Error = Err;
-
-    fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
-        (self.0)(None, subexpr)
-    }
-    fn visit_subexpr_under_binder(
-        mut self,
-        label: &'a Label,
-        subexpr: &'a SE,
-    ) -> Result<SE2, Self::Error> {
-        (self.0)(Some(label), subexpr)
-    }
-    fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
-        Ok(embed.clone())
-    }
-}
-
-pub struct TraverseMutVisitor<F1> {
-    pub visit_subexpr: F1,
-}
-
-impl<'a, SE, E, Err, F1> ExprKindMutVisitor<'a, SE, E>
-    for TraverseMutVisitor<F1>
-where
-    SE: 'a,
-    E: 'a,
-    F1: FnMut(&'a mut SE) -> Result<(), Err>,
-{
-    type Error = Err;
-
-    fn visit_subexpr(
-        &mut self,
-        subexpr: &'a mut SE,
-    ) -> Result<(), Self::Error> {
-        (self.visit_subexpr)(subexpr)
-    }
-}
diff --git a/dhall/src/syntax/binary/decode.rs b/dhall/src/syntax/binary/decode.rs
index 52b699c..2e50d61 100644
--- a/dhall/src/syntax/binary/decode.rs
+++ b/dhall/src/syntax/binary/decode.rs
@@ -6,8 +6,8 @@ use crate::error::DecodeError;
 use crate::syntax;
 use crate::syntax::{
     Expr, ExprKind, FilePath, FilePrefix, Hash, ImportLocation, ImportMode,
-    Integer, InterpolatedText, Label, Natural, Scheme, Span, UnspannedExpr,
-    URL, V,
+    Integer, InterpolatedText, Label, LitKind, Natural, Scheme, Span,
+    UnspannedExpr, URL, V,
 };
 use crate::DecodedExpr;
 
@@ -19,7 +19,7 @@ pub(crate) fn decode(data: &[u8]) -> Result<DecodedExpr, DecodeError> {
 }
 
 // Should probably rename this
-fn rc<E>(x: UnspannedExpr<E>) -> Expr<E> {
+fn rc(x: UnspannedExpr) -> Expr {
     Expr::new(x, Span::Decoded)
 }
 
@@ -31,8 +31,8 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
         String(s) => match Builtin::parse(s) {
             Some(b) => ExprKind::Builtin(b),
             None => match s.as_str() {
-                "True" => BoolLit(true),
-                "False" => BoolLit(false),
+                "True" => Lit(LitKind::Bool(true)),
+                "False" => Lit(LitKind::Bool(false)),
                 "Type" => Const(Const::Type),
                 "Kind" => Const(Const::Kind),
                 "Sort" => Const(Const::Sort),
@@ -40,8 +40,8 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
             },
         },
         U64(n) => Var(V(Label::from("_"), *n as usize)),
-        F64(x) => DoubleLit((*x).into()),
-        Bool(b) => BoolLit(*b),
+        F64(x) => Lit(LitKind::Double((*x).into())),
+        Bool(b) => Lit(LitKind::Bool(*b)),
         Array(vec) => match vec.as_slice() {
             [String(l), U64(n)] => {
                 if l.as_str() == "_" {
@@ -216,9 +216,9 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<DecodedExpr, DecodeError> {
                 let z = cbor_value_to_dhall(&z)?;
                 BoolIf(x, y, z)
             }
-            [U64(15), U64(x)] => NaturalLit(*x as Natural),
-            [U64(16), U64(x)] => IntegerLit(*x as Integer),
-            [U64(16), I64(x)] => IntegerLit(*x as Integer),
+            [U64(15), U64(x)] => Lit(LitKind::Natural(*x as Natural)),
+            [U64(16), U64(x)] => Lit(LitKind::Integer(*x as Integer)),
+            [U64(16), I64(x)] => Lit(LitKind::Integer(*x as Integer)),
             [U64(18), String(first), rest @ ..] => {
                 TextLit(InterpolatedText::from((
                     first.clone(),
diff --git a/dhall/src/syntax/binary/encode.rs b/dhall/src/syntax/binary/encode.rs
index 5e79f2d..291ac4a 100644
--- a/dhall/src/syntax/binary/encode.rs
+++ b/dhall/src/syntax/binary/encode.rs
@@ -9,17 +9,16 @@ use crate::syntax::{
     Label, Scheme, V,
 };
 
-/// Warning: will fail if `expr` contains an `Embed` node.
-pub(crate) fn encode<E>(expr: &Expr<E>) -> Result<Vec<u8>, EncodeError> {
+pub(crate) fn encode(expr: &Expr) -> Result<Vec<u8>, EncodeError> {
     serde_cbor::ser::to_vec(&Serialize::Expr(expr))
         .map_err(|e| EncodeError::CBORError(e))
 }
 
-enum Serialize<'a, E> {
-    Expr(&'a Expr<E>),
+enum Serialize<'a> {
+    Expr(&'a Expr),
     CBOR(cbor::Value),
-    RecordMap(&'a DupTreeMap<Label, Expr<E>>),
-    UnionMap(&'a DupTreeMap<Label, Option<Expr<E>>>),
+    RecordMap(&'a DupTreeMap<Label, Expr>),
+    UnionMap(&'a DupTreeMap<Label, Option<Expr>>),
 }
 
 macro_rules! count {
@@ -39,7 +38,7 @@ macro_rules! ser_seq {
     }};
 }
 
-fn serialize_subexpr<S, E>(ser: S, e: &Expr<E>) -> Result<S::Ok, S::Error>
+fn serialize_subexpr<S>(ser: S, e: &Expr) -> Result<S::Ok, S::Error>
 where
     S: serde::ser::Serializer,
 {
@@ -47,13 +46,14 @@ where
     use std::iter::once;
     use syntax::Builtin;
     use syntax::ExprKind::*;
+    use syntax::LitKind::*;
 
     use self::Serialize::{RecordMap, UnionMap};
-    fn expr<E>(x: &Expr<E>) -> self::Serialize<'_, E> {
+    fn expr(x: &Expr) -> self::Serialize<'_> {
         self::Serialize::Expr(x)
     }
     let cbor =
-        |v: cbor::Value| -> self::Serialize<'_, E> { self::Serialize::CBOR(v) };
+        |v: cbor::Value| -> self::Serialize<'_> { self::Serialize::CBOR(v) };
     let tag = |x: u64| cbor(U64(x));
     let null = || cbor(cbor::Value::Null);
     let label = |l: &Label| cbor(cbor::Value::String(l.into()));
@@ -61,10 +61,10 @@ where
     match e.as_ref() {
         Const(c) => ser.serialize_str(&c.to_string()),
         Builtin(b) => ser.serialize_str(&b.to_string()),
-        BoolLit(b) => ser.serialize_bool(*b),
-        NaturalLit(n) => ser_seq!(ser; tag(15), U64(*n as u64)),
-        IntegerLit(n) => ser_seq!(ser; tag(16), I64(*n as i64)),
-        DoubleLit(n) => {
+        Lit(Bool(b)) => ser.serialize_bool(*b),
+        Lit(Natural(n)) => ser_seq!(ser; tag(15), U64(*n as u64)),
+        Lit(Integer(n)) => ser_seq!(ser; tag(16), I64(*n as i64)),
+        Lit(Double(n)) => {
             let n: f64 = (*n).into();
             ser.serialize_f64(n)
         }
@@ -166,16 +166,10 @@ where
         }
         Completion(x, y) => ser_seq!(ser; tag(3), tag(13), expr(x), expr(y)),
         Import(import) => serialize_import(ser, import),
-        Embed(_) => unimplemented!(
-            "An expression with resolved imports cannot be binary-encoded"
-        ),
     }
 }
 
-fn serialize_import<S, E>(
-    ser: S,
-    import: &Import<Expr<E>>,
-) -> Result<S::Ok, S::Error>
+fn serialize_import<S>(ser: S, import: &Import<Expr>) -> Result<S::Ok, S::Error>
 where
     S: serde::ser::Serializer,
 {
@@ -256,7 +250,7 @@ where
     ser_seq.end()
 }
 
-impl<'a, E> serde::ser::Serialize for Serialize<'a, E> {
+impl<'a> serde::ser::Serialize for Serialize<'a> {
     fn serialize<S>(&self, ser: S) -> Result<S::Ok, S::Error>
     where
         S: serde::ser::Serializer,
@@ -282,10 +276,8 @@ impl<'a, E> serde::ser::Serialize for Serialize<'a, E> {
     }
 }
 
-fn collect_nested_applications<'a, E>(
-    e: &'a Expr<E>,
-) -> (&'a Expr<E>, Vec<&'a Expr<E>>) {
-    fn go<'a, E>(e: &'a Expr<E>, vec: &mut Vec<&'a Expr<E>>) -> &'a Expr<E> {
+fn collect_nested_applications<'a>(e: &'a Expr) -> (&'a Expr, Vec<&'a Expr>) {
+    fn go<'a>(e: &'a Expr, vec: &mut Vec<&'a Expr>) -> &'a Expr {
         match e.as_ref() {
             ExprKind::App(f, a) => {
                 vec.push(a);
@@ -299,15 +291,10 @@ fn collect_nested_applications<'a, E>(
     (e, vec)
 }
 
-type LetBinding<'a, E> = (&'a Label, &'a Option<Expr<E>>, &'a Expr<E>);
+type LetBinding<'a> = (&'a Label, &'a Option<Expr>, &'a Expr);
 
-fn collect_nested_lets<'a, E>(
-    e: &'a Expr<E>,
-) -> (&'a Expr<E>, Vec<LetBinding<'a, E>>) {
-    fn go<'a, E>(
-        e: &'a Expr<E>,
-        vec: &mut Vec<LetBinding<'a, E>>,
-    ) -> &'a Expr<E> {
+fn collect_nested_lets<'a>(e: &'a Expr) -> (&'a Expr, Vec<LetBinding<'a>>) {
+    fn go<'a>(e: &'a Expr, vec: &mut Vec<LetBinding<'a>>) -> &'a Expr {
         match e.as_ref() {
             ExprKind::Let(l, t, v, e) => {
                 vec.push((l, t, v));
diff --git a/dhall/src/syntax/text/parser.rs b/dhall/src/syntax/text/parser.rs
index 8d571c0..f3ebd2b 100644
--- a/dhall/src/syntax/text/parser.rs
+++ b/dhall/src/syntax/text/parser.rs
@@ -5,23 +5,20 @@ use std::rc::Rc;
 
 use pest_consume::{match_nodes, Parser};
 
-use crate::syntax;
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::ExprKind::*;
+use crate::syntax::LitKind::*;
 use crate::syntax::{
-    Double, FilePath, FilePrefix, Hash, ImportLocation, ImportMode, Integer,
-    InterpolatedText, InterpolatedTextContents, Label, NaiveDouble, Natural,
-    Scheme, Span, URL, V,
+    Double, Expr, FilePath, FilePrefix, Hash, ImportLocation, ImportMode,
+    Integer, InterpolatedText, InterpolatedTextContents, Label, NaiveDouble,
+    Natural, Scheme, Span, UnspannedExpr, URL, V,
 };
-use crate::Normalized;
 
 // This file consumes the parse tree generated by pest and turns it into
 // our own AST. All those custom macros should eventually moved into
 // their own crate because they are quite general and useful. For now they
 // are here and hopefully you can figure out how they work.
 
-type Expr = syntax::Expr<Normalized>;
-type UnspannedExpr = syntax::UnspannedExpr<Normalized>;
 type ParsedText = InterpolatedText<Expr>;
 type ParsedTextContents = InterpolatedTextContents<Expr>;
 type ParseInput<'input> = pest_consume::Node<'input, Rule, Rc<str>>;
@@ -348,8 +345,8 @@ impl DhallParser {
         let e = match crate::syntax::Builtin::parse(s) {
             Some(b) => Builtin(b),
             None => match s {
-                "True" => BoolLit(true),
-                "False" => BoolLit(false),
+                "True" => Lit(Bool(true)),
+                "False" => Lit(Bool(false)),
                 "Type" => Const(crate::syntax::Const::Type),
                 "Kind" => Const(crate::syntax::Const::Kind),
                 "Sort" => Const(crate::syntax::Const::Sort),
@@ -837,9 +834,9 @@ impl DhallParser {
     #[alias(expression, shortcut = true)]
     fn primitive_expression(input: ParseInput) -> ParseResult<Expr> {
         Ok(match_nodes!(input.children();
-            [double_literal(n)] => spanned(input, DoubleLit(n)),
-            [natural_literal(n)] => spanned(input, NaturalLit(n)),
-            [integer_literal(n)] => spanned(input, IntegerLit(n)),
+            [double_literal(n)] => spanned(input, Lit(Double(n))),
+            [natural_literal(n)] => spanned(input, Lit(Natural(n))),
+            [integer_literal(n)] => spanned(input, Lit(Integer(n))),
             [double_quote_literal(s)] => spanned(input, TextLit(s)),
             [single_quote_literal(s)] => spanned(input, TextLit(s)),
             [record_type_or_literal(e)] => spanned(input, e),
diff --git a/dhall/src/syntax/text/printer.rs b/dhall/src/syntax/text/printer.rs
index 06dd70f..8891d41 100644
--- a/dhall/src/syntax/text/printer.rs
+++ b/dhall/src/syntax/text/printer.rs
@@ -19,17 +19,17 @@ enum PrintPhase {
 // Wraps an Expr with a phase, so that phase selection can be done separate from the actual
 // printing.
 #[derive(Clone)]
-struct PhasedExpr<'a, E>(&'a Expr<E>, PrintPhase);
+struct PhasedExpr<'a>(&'a Expr, PrintPhase);
 
-impl<'a, E: Display + Clone> PhasedExpr<'a, E> {
-    fn phase(self, phase: PrintPhase) -> PhasedExpr<'a, E> {
+impl<'a> PhasedExpr<'a> {
+    fn phase(self, phase: PrintPhase) -> PhasedExpr<'a> {
         PhasedExpr(self.0, phase)
     }
 }
 
-impl<E: Display + Clone> UnspannedExpr<E> {
+impl UnspannedExpr {
     // Annotate subexpressions with the appropriate phase, defaulting to Base
-    fn annotate_with_phases<'a>(&'a self) -> ExprKind<PhasedExpr<'a, E>, E> {
+    fn annotate_with_phases<'a>(&'a self) -> ExprKind<PhasedExpr<'a>> {
         use crate::syntax::ExprKind::*;
         use PrintPhase::*;
         let with_base = self.map_ref(|e| PhasedExpr(e, Base));
@@ -134,7 +134,7 @@ where
 }
 
 /// Generic instance that delegates to subexpressions
-impl<SE: Display + Clone, E: Display> Display for ExprKind<SE, E> {
+impl<SE: Display + Clone> Display for ExprKind<SE> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         use crate::syntax::ExprKind::*;
         match self {
@@ -196,15 +196,7 @@ impl<SE: Display + Clone, E: Display> Display for ExprKind<SE, E> {
             Var(a) => a.fmt(f)?,
             Const(k) => k.fmt(f)?,
             Builtin(v) => v.fmt(f)?,
-            BoolLit(true) => f.write_str("True")?,
-            BoolLit(false) => f.write_str("False")?,
-            NaturalLit(a) => a.fmt(f)?,
-            IntegerLit(a) if *a >= 0 => {
-                f.write_str("+")?;
-                a.fmt(f)?;
-            }
-            IntegerLit(a) => a.fmt(f)?,
-            DoubleLit(a) => a.fmt(f)?,
+            Lit(a) => a.fmt(f)?,
             TextLit(a) => a.fmt(f)?,
             RecordType(a) if a.is_empty() => f.write_str("{}")?,
             RecordType(a) => fmt_list("{ ", ", ", " }", a, f, |(k, t), f| {
@@ -232,19 +224,36 @@ impl<SE: Display + Clone, E: Display> Display for ExprKind<SE, E> {
                 write!(f, "{}::{}", a, b)?;
             }
             Import(a) => a.fmt(f)?,
-            Embed(a) => a.fmt(f)?,
         }
         Ok(())
     }
 }
 
-impl<E: Display + Clone> Display for Expr<E> {
+impl Display for Expr {
+    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+        self.kind().fmt_phase(f, PrintPhase::Base)
+    }
+}
+
+impl Display for LitKind {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        self.as_ref().fmt_phase(f, PrintPhase::Base)
+        use LitKind::*;
+        match self {
+            Bool(true) => f.write_str("True")?,
+            Bool(false) => f.write_str("False")?,
+            Natural(a) => a.fmt(f)?,
+            Integer(a) if *a >= 0 => {
+                f.write_str("+")?;
+                a.fmt(f)?;
+            }
+            Integer(a) => a.fmt(f)?,
+            Double(a) => a.fmt(f)?,
+        }
+        Ok(())
     }
 }
 
-impl<'a, E: Display + Clone> Display for PhasedExpr<'a, E> {
+impl<'a> Display for PhasedExpr<'a> {
     fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
         self.0.as_ref().fmt_phase(f, self.1)
     }