Reorganize dhall_core a bit

3 files changed, 539 insertions, 1079 deletions

diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index e7c9f2a..68e781d 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -1,11 +1,17 @@
 #![allow(non_snake_case)]
+use crate::*;
 use std::collections::BTreeMap;
-use std::fmt::{self, Display};
-use std::iter::FromIterator;
-use std::ops::Add;
-use std::path::PathBuf;
 use std::rc::Rc;
 
+pub type Double = f64;
+pub type Int = isize;
+pub type Integer = isize;
+pub type Natural = usize;
+
+/// An empty type
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+pub enum X {}
+
 /// Constants for a pure type system
 ///
 /// The only axiom is:
@@ -33,82 +39,9 @@ pub enum Const {
     Kind,
 }
 
-/// The beginning of a file path which anchors subsequent path components
-#[derive(Debug, Clone, PartialEq, Eq)]
-pub enum FilePrefix {
-    /// Absolute path
-    Absolute,
-    /// Path relative to .
-    Here,
-    /// Path relative to ..
-    Parent,
-    /// Path relative to ~
-    Home,
-}
-
-/// The location of import (i.e. local vs. remote vs. environment)
-#[derive(Debug, Clone, PartialEq, Eq)]
-pub enum ImportLocation {
-    Local(FilePrefix, PathBuf),
-    // TODO: other import types
-}
-
-/// How to interpret the import's contents (i.e. as Dhall code or raw text)
-#[derive(Debug, Clone, PartialEq, Eq)]
-pub enum ImportMode {
-    Code,
-    // TODO
-    // RawText,
-}
-
-/// Reference to an external resource
-#[derive(Debug, Clone, PartialEq, Eq)]
-pub struct Import {
-    pub mode: ImportMode,
-    pub location: ImportLocation,
-    // TODO
-    pub hash: Option<()>,
-}
-
-// The type for labels throughout the AST
-// It owns the data because otherwise lifetimes would make recursive imports impossible
-#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
-pub struct Label(Rc<str>);
-
-impl From<String> for Label {
-    fn from(s: String) -> Self {
-        let s: &str = &s;
-        Label(s.into())
-    }
-}
-
-impl<'a> From<&'a str> for Label {
-    fn from(s: &'a str) -> Self {
-        Label(Rc::from(s))
-    }
-}
-
-impl From<Label> for String {
-    fn from(x: Label) -> String {
-        x.0.as_ref().to_owned()
-    }
-}
-
-impl Display for Label {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        self.0.as_ref().fmt(f)
-    }
-}
-
-impl Label {
-    pub fn from_str(s: &str) -> Label {
-        Label(s.into())
-    }
-}
-
-/// Label for a bound variable
+/// Bound variable
 ///
-/// The `String` field is the variable's name (i.e. \"`x`\").
+/// The `Label` field is the variable's name (i.e. \"`x`\").
 ///
 /// The `Int` field disambiguates variables with the same name if there are
 /// multiple bound variables of the same name in scope.  Zero refers to the
@@ -173,93 +106,43 @@ pub enum BinOp {
     ListAppend,
 }
 
-#[derive(Debug, Clone, PartialEq)]
-pub struct InterpolatedText<Note, Embed> {
-    head: String,
-    tail: Vec<(Rc<Expr<Note, Embed>>, String)>,
-}
-
-impl<N, E> From<(String, Vec<(Rc<Expr<N, E>>, String)>)>
-    for InterpolatedText<N, E>
-{
-    fn from(x: (String, Vec<(Rc<Expr<N, E>>, String)>)) -> Self {
-        InterpolatedText {
-            head: x.0,
-            tail: x.1,
-        }
-    }
-}
-
-impl<N, E> From<String> for InterpolatedText<N, E> {
-    fn from(s: String) -> Self {
-        InterpolatedText {
-            head: s,
-            tail: vec![],
-        }
-    }
-}
-
-#[derive(Debug, Clone)]
-pub enum InterpolatedTextContents<'a, Note, Embed> {
-    Text(&'a str),
-    Expr(SubExpr<Note, Embed>),
-}
-
-impl<N, E> InterpolatedText<N, E> {
-    pub fn map<N2, E2, F>(&self, mut f: F) -> InterpolatedText<N2, E2>
-    where
-        F: FnMut(&Rc<Expr<N, E>>) -> Rc<Expr<N2, E2>>,
-    {
-        InterpolatedText {
-            head: self.head.clone(),
-            tail: self.tail.iter().map(|(e, s)| (f(e), s.clone())).collect(),
-        }
-    }
-
-    pub fn iter(&self) -> impl Iterator<Item = InterpolatedTextContents<N, E>> {
-        use std::iter::once;
-        once(InterpolatedTextContents::Text(self.head.as_ref())).chain(
-            self.tail.iter().flat_map(|(e, s)| {
-                once(InterpolatedTextContents::Expr(Rc::clone(e)))
-                    .chain(once(InterpolatedTextContents::Text(s)))
-            }),
-        )
-    }
-}
-
-impl<'a, N: 'a, E: 'a> FromIterator<InterpolatedTextContents<'a, N, E>>
-    for InterpolatedText<N, E>
-{
-    fn from_iter<T>(iter: T) -> Self
-    where
-        T: IntoIterator<Item = InterpolatedTextContents<'a, N, E>>,
-    {
-        let mut res = InterpolatedText {
-            head: "".to_owned(),
-            tail: vec![],
-        };
-        // let mut empty_string = "".to_owned();
-        let mut crnt_str = &mut res.head;
-        for x in iter.into_iter() {
-            match x {
-                InterpolatedTextContents::Text(s) => crnt_str.push_str(s),
-                InterpolatedTextContents::Expr(e) => {
-                    // crnt_str = &mut empty_string;
-                    res.tail.push((e.clone(), "".to_owned()));
-                    crnt_str = &mut res.tail.last_mut().unwrap().1;
-                }
-            }
-        }
-        res
-    }
+/// Built-ins
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+pub enum Builtin {
+    Bool,
+    Natural,
+    Integer,
+    Double,
+    Text,
+    List,
+    Optional,
+    OptionalSome,
+    OptionalNone,
+    NaturalBuild,
+    NaturalFold,
+    NaturalIsZero,
+    NaturalEven,
+    NaturalOdd,
+    NaturalToInteger,
+    NaturalShow,
+    IntegerToDouble,
+    IntegerShow,
+    DoubleShow,
+    ListBuild,
+    ListFold,
+    ListLength,
+    ListHead,
+    ListLast,
+    ListIndexed,
+    ListReverse,
+    OptionalFold,
+    OptionalBuild,
+    TextShow,
 }
 
-impl<N, E> Add for &InterpolatedText<N, E> {
-    type Output = InterpolatedText<N, E>;
-    fn add(self, rhs: &InterpolatedText<N, E>) -> Self::Output {
-        self.iter().chain(rhs.iter()).collect()
-    }
-}
+pub type ParsedExpr<S> = SubExpr<S, Import>;
+pub type ResolvedExpr<S> = SubExpr<S, X>;
+pub type DhallExpr = ResolvedExpr<X>;
 
 pub type SubExpr<Note, Embed> = Rc<Expr<Note, Embed>>;
 
@@ -341,64 +224,6 @@ pub enum Expr<Note, Embed> {
     Embed(Embed),
 }
 
-/// Built-ins
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
-pub enum Builtin {
-    Bool,
-    Natural,
-    Integer,
-    Double,
-    Text,
-    List,
-    Optional,
-    OptionalSome,
-    OptionalNone,
-    NaturalBuild,
-    NaturalFold,
-    NaturalIsZero,
-    NaturalEven,
-    NaturalOdd,
-    NaturalToInteger,
-    NaturalShow,
-    IntegerToDouble,
-    IntegerShow,
-    DoubleShow,
-    ListBuild,
-    ListFold,
-    ListLength,
-    ListHead,
-    ListLast,
-    ListIndexed,
-    ListReverse,
-    OptionalFold,
-    OptionalBuild,
-    TextShow,
-}
-
-impl From<Label> for V {
-    fn from(s: Label) -> Self {
-        V(s, 0)
-    }
-}
-
-impl From<&'static str> for V {
-    fn from(s: &'static str) -> Self {
-        V(s.into(), 0)
-    }
-}
-
-impl<S, A> From<&'static str> for Expr<S, A> {
-    fn from(s: &'static str) -> Self {
-        Expr::Var(V(s.into(), 0))
-    }
-}
-
-impl<S, A> From<Builtin> for Expr<S, A> {
-    fn from(t: Builtin) -> Self {
-        Expr::Builtin(t)
-    }
-}
-
 impl<S, A> Expr<S, A> {
     pub fn map_shallow<T, B, F1, F2, F3, F4>(
         &self,
@@ -445,20 +270,6 @@ 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)
     }
-
-    pub fn bool_lit(&self) -> Option<bool> {
-        match *self {
-            Expr::BoolLit(v) => Some(v),
-            _ => None,
-        }
-    }
-
-    pub fn natural_lit(&self) -> Option<usize> {
-        match *self {
-            Expr::NaturalLit(v) => Some(v),
-            _ => None,
-        }
-    }
 }
 
 impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
@@ -475,406 +286,11 @@ impl<S: Clone, A: Clone> Expr<S, Expr<S, A>> {
     }
 }
 
-//  There is a one-to-one correspondence between the formatters in this section
-//  and the grammar in grammar.lalrpop.  Each formatter is named after the
-//  corresponding grammar rule and the relationship between formatters exactly matches
-//  the relationship between grammar rules.  This leads to the nice emergent property
-//  of automatically getting all the parentheses and precedences right.
-//
-//  This approach has one major disadvantage: you can get an infinite loop if
-//  you add a new constructor to the syntax tree without adding a matching
-//  case the corresponding builder.
-
-impl<S, A: Display> Display for Expr<S, A> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        // buildExprA
-        use crate::Expr::*;
-        match self {
-            &Annot(ref a, ref b) => {
-                a.fmt_b(f)?;
-                write!(f, " : ")?;
-                b.fmt(f)
-            }
-            &Note(_, ref b) => b.fmt(f),
-            a => a.fmt_b(f),
-        }
-    }
-}
-
-// WARNING: this may cause stack overflows when adding new variants
-impl<S, A: Display> Expr<S, A> {
-    fn fmt_b(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use crate::Expr::*;
-        match self {
-            &Lam(ref a, ref b, ref c) => {
-                write!(f, "λ({} : ", a)?;
-                b.fmt(f)?;
-                write!(f, ") → ")?;
-                c.fmt_b(f)
-            }
-            &BoolIf(ref a, ref b, ref c) => {
-                write!(f, "if ")?;
-                a.fmt(f)?;
-                write!(f, " then ")?;
-                b.fmt_b(f)?;
-                write!(f, " else ")?;
-                c.fmt_c(f)
-            }
-            // TODO: wait for decision on label types
-            // &Pi("_", ref b, ref c) => {
-            //     b.fmt_c(f)?;
-            //     write!(f, " → ")?;
-            //     c.fmt_b(f)
-            // }
-            &Pi(ref a, ref b, ref c) => {
-                write!(f, "∀({} : ", a)?;
-                b.fmt(f)?;
-                write!(f, ") → ")?;
-                c.fmt_b(f)
-            }
-            &Let(ref a, None, ref c, ref d) => {
-                write!(f, "let {} = ", a)?;
-                c.fmt(f)?;
-                write!(f, " in ")?;
-                d.fmt_b(f)
-            }
-            &Let(ref a, Some(ref b), ref c, ref d) => {
-                write!(f, "let {} : ", a)?;
-                b.fmt(f)?;
-                write!(f, " = ")?;
-                c.fmt(f)?;
-                write!(f, " in ")?;
-                d.fmt_b(f)
-            }
-            &EmptyListLit(ref t) => {
-                write!(f, "[] : List ")?;
-                t.fmt_e(f)
-            }
-            &NEListLit(ref es) => {
-                fmt_list("[", ", ", "]", es, f, |e, f| e.fmt(f))
-            }
-            &OptionalLit(ref t, ref es) => {
-                match es {
-                    None => {
-                        // TODO: use None when parsing fixed
-                        write!(f, "[] : Optional ")?;
-                        t.as_ref().unwrap().fmt_e(f)?;
-                    }
-                    Some(e) => {
-                        // TODO: use Some when parsing fixed
-                        write!(f, "[ ")?;
-                        e.fmt_e(f)?;
-                        write!(f, " ]")?;
-                        if let Some(t) = t {
-                            write!(f, " : Optional ")?;
-                            t.fmt_e(f)?;
-                        }
-                    }
-                }
-                Ok(())
-            }
-            &Merge(ref a, ref b, ref c) => {
-                write!(f, "merge ")?;
-                a.fmt_e(f)?;
-                write!(f, " ")?;
-                b.fmt_e(f)?;
-                match c {
-                    Some(c) => {
-                        write!(f, " : ")?;
-                        c.fmt_d(f)?
-                    }
-                    None => {}
-                }
-                Ok(())
-            }
-            &Note(_, ref b) => b.fmt_b(f),
-            a => a.fmt_c(f),
-        }
-    }
-
-    fn fmt_c(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use crate::BinOp::*;
-        use crate::Expr::*;
-        match self {
-            // FIXME precedence
-            &BinOp(op, ref a, ref b) => {
-                write!(f, "(")?;
-                a.fmt_d(f)?;
-                write!(
-                    f,
-                    " {} ",
-                    match op {
-                        BoolOr => "||",
-                        TextAppend => "++",
-                        NaturalPlus => "+",
-                        BoolAnd => "&&",
-                        Combine => "/\\",
-                        NaturalTimes => "*",
-                        BoolEQ => "==",
-                        BoolNE => "!=",
-                        CombineTypes => "//\\\\",
-                        ImportAlt => "?",
-                        Prefer => "//",
-                        ListAppend => "#",
-                    }
-                )?;
-                b.fmt_c(f)?;
-                write!(f, ")")
-            }
-            &Note(_, ref b) => b.fmt_c(f),
-            a => a.fmt_d(f),
-        }
-    }
-
-    fn fmt_d(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use crate::Expr::*;
-        match self {
-            &App(ref a, ref args) => {
-                a.fmt_d(f)?;
-                for x in args {
-                    f.write_str(" ")?;
-                    x.fmt_e(f)?;
-                }
-                Ok(())
-            }
-            &Note(_, ref b) => b.fmt_d(f),
-            a => a.fmt_e(f),
-        }
-    }
-
-    fn fmt_e(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use crate::Expr::*;
-        match self {
-            &Field(ref a, ref b) => {
-                a.fmt_e(f)?;
-                write!(f, ".{}", b)
-            }
-            &Note(_, ref b) => b.fmt_e(f),
-            a => a.fmt_f(f),
-        }
-    }
-
-    fn fmt_f(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use crate::Expr::*;
-        match &self {
-            &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),
-            &TextLit(ref a) => {
-                f.write_str("\"")?;
-                for x in a.iter() {
-                    match x {
-                        InterpolatedTextContents::Text(a) => {
-                            // TODO Format all escapes properly
-                            f.write_str(
-                                &a.replace("\n", "\\n")
-                                    .replace("\t", "\\t")
-                                    .replace("\r", "\\r")
-                                    .replace("\"", "\\\""),
-                            )?;
-                        }
-                        InterpolatedTextContents::Expr(e) => {
-                            f.write_str("${ ")?;
-                            e.fmt(f)?;
-                            f.write_str(" }")?;
-                        }
-                    }
-                }
-                f.write_str("\"")?;
-                Ok(())
-            }
-            &Record(ref a) if a.is_empty() => f.write_str("{}"),
-            &Record(ref a) => fmt_list("{ ", ", ", " }", a, f, |(k, t), f| {
-                write!(f, "{} : {}", k, t)
-            }),
-            &RecordLit(ref a) if a.is_empty() => f.write_str("{=}"),
-            &RecordLit(ref a) => {
-                fmt_list("{ ", ", ", " }", a, f, |(k, v), f| {
-                    write!(f, "{} = {}", k, v)
-                })
-            }
-            &Union(ref a) => fmt_list("< ", " | ", " >", a, f, |(k, v), f| {
-                write!(f, "{} : {}", k, v)
-            }),
-            &UnionLit(ref a, ref b, ref c) => {
-                f.write_str("< ")?;
-                write!(f, "{} = {}", a, b)?;
-                for (k, v) in c {
-                    f.write_str(" | ")?;
-                    write!(f, "{} : {}", k, v)?;
-                }
-                f.write_str(" >")
-            }
-            &Embed(ref a) => a.fmt(f),
-            &Note(_, ref b) => b.fmt_f(f),
-            a => write!(f, "({})", a),
-        }
-    }
-}
-
-fn fmt_list<T, I, F>(
-    open: &str,
-    sep: &str,
-    close: &str,
-    it: I,
-    f: &mut fmt::Formatter,
-    func: F,
-) -> Result<(), fmt::Error>
-where
-    I: IntoIterator<Item = T>,
-    F: Fn(T, &mut fmt::Formatter) -> Result<(), fmt::Error>,
-{
-    f.write_str(open)?;
-    for (i, x) in it.into_iter().enumerate() {
-        if i > 0 {
-            f.write_str(sep)?;
-        }
-        func(x, f)?;
-    }
-    f.write_str(close)
-}
-
-impl Display for Const {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        <Self as fmt::Debug>::fmt(self, f)
-    }
-}
-
-impl Display for Import {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        <Self as fmt::Debug>::fmt(self, f)
-    }
-}
-
-impl Display for Builtin {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        use crate::Builtin::*;
-        f.write_str(match *self {
-            Bool => "Bool",
-            Natural => "Natural",
-            Integer => "Integer",
-            Double => "Double",
-            Text => "Text",
-            List => "List",
-            Optional => "Optional",
-            OptionalSome => "Some",
-            OptionalNone => "None",
-            NaturalBuild => "Natural/build",
-            NaturalFold => "Natural/fold",
-            NaturalIsZero => "Natural/isZero",
-            NaturalEven => "Natural/even",
-            NaturalOdd => "Natural/odd",
-            NaturalToInteger => "Natural/toInteger",
-            NaturalShow => "Natural/show",
-            IntegerToDouble => "Integer/toDouble",
-            IntegerShow => "Integer/show",
-            DoubleShow => "Double/show",
-            ListBuild => "List/build",
-            ListFold => "List/fold",
-            ListLength => "List/length",
-            ListHead => "List/head",
-            ListLast => "List/last",
-            ListIndexed => "List/indexed",
-            ListReverse => "List/reverse",
-            OptionalFold => "Optional/fold",
-            OptionalBuild => "Optional/build",
-            TextShow => "Text/show",
-        })
-    }
-}
-
-impl Builtin {
-    pub fn parse(s: &str) -> Option<Self> {
-        use self::Builtin::*;
-        match s {
-            "Bool" => Some(Bool),
-            "Natural" => Some(Natural),
-            "Integer" => Some(Integer),
-            "Double" => Some(Double),
-            "Text" => Some(Text),
-            "List" => Some(List),
-            "Optional" => Some(Optional),
-            "Some" => Some(OptionalSome),
-            "None" => Some(OptionalNone),
-            "Natural/build" => Some(NaturalBuild),
-            "Natural/fold" => Some(NaturalFold),
-            "Natural/isZero" => Some(NaturalIsZero),
-            "Natural/even" => Some(NaturalEven),
-            "Natural/odd" => Some(NaturalOdd),
-            "Natural/toInteger" => Some(NaturalToInteger),
-            "Natural/show" => Some(NaturalShow),
-            "Integer/toDouble" => Some(IntegerToDouble),
-            "Integer/show" => Some(IntegerShow),
-            "Double/show" => Some(DoubleShow),
-            "List/build" => Some(ListBuild),
-            "List/fold" => Some(ListFold),
-            "List/length" => Some(ListLength),
-            "List/head" => Some(ListHead),
-            "List/last" => Some(ListLast),
-            "List/indexed" => Some(ListIndexed),
-            "List/reverse" => Some(ListReverse),
-            "Optional/fold" => Some(OptionalFold),
-            "Optional/build" => Some(OptionalBuild),
-            "Text/show" => Some(TextShow),
-            _ => None,
-        }
-    }
-}
-
-impl Display for V {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        let V(ref x, ref n) = *self;
-        x.fmt(f)?;
-        if *n != 0 {
-            write!(f, "@{}", n)?;
-        }
-        Ok(())
-    }
-}
-
-pub fn pi<S, A, Name, Et, Ev>(var: Name, ty: Et, value: Ev) -> Expr<S, A>
-where
-    Name: Into<Label>,
-    Et: Into<Expr<S, A>>,
-    Ev: Into<Expr<S, A>>,
-{
-    Expr::Pi(var.into(), bx(ty.into()), bx(value.into()))
-}
-
-pub fn app<S, A, Ef>(f: Ef, x: Vec<Rc<Expr<S, A>>>) -> Expr<S, A>
-where
-    Ef: Into<Expr<S, A>>,
-{
-    Expr::App(bx(f.into()), x)
-}
-
-pub type Double = f64;
-pub type Int = isize;
-pub type Integer = isize;
-pub type Natural = usize;
-
-/// A void type
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
-pub enum X {}
-
-impl Display for X {
-    fn fmt(&self, _: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        match *self {}
-    }
-}
-
+// Remains of a previous life, where everything was in Boxes
 pub fn bx<T>(x: T) -> Rc<T> {
     Rc::new(x)
 }
+
 pub fn rc<T>(x: T) -> Rc<T> {
     Rc::new(x)
 }
diff --git a/dhall_core/src/lib.rs b/dhall_core/src/lib.rs
index 6215456..0874b09 100644
--- a/dhall_core/src/lib.rs
+++ b/dhall_core/src/lib.rs
@@ -6,7 +6,16 @@
     clippy::new_without_default
 )]
 
-pub mod core;
+mod core;
 pub use crate::core::*;
+mod import;
+pub use crate::import::*;
+mod label;
+pub use crate::label::*;
+mod text;
+pub use crate::text::*;
+mod printer;
+pub use crate::printer::*;
+mod parser;
+pub use crate::parser::*;
 pub mod context;
-pub mod parser;
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index 66581a3..896a93f 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -2,27 +2,62 @@ use pest::iterators::Pair;
 use pest::Parser;
 use std::collections::BTreeMap;
 use std::path::PathBuf;
-use std::rc::Rc;
 
 use dhall_parser::{DhallParser, Rule};
 
-use crate::core;
-use crate::core::*;
+use crate::*;
 
 // 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.
 
-pub type ParsedExpr = Expr<X, Import>;
-pub type ParsedText = InterpolatedText<X, Import>;
-pub type ParsedTextContents<'a> = InterpolatedTextContents<'a, X, Import>;
-pub type RcExpr = Rc<ParsedExpr>;
+type ParsedExpr = crate::ParsedExpr<X>;
+type ParsedText = InterpolatedText<X, Import>;
+type ParsedTextContents<'a> = InterpolatedTextContents<'a, X, Import>;
 
 pub type ParseError = pest::error::Error<Rule>;
 
 pub type ParseResult<T> = Result<T, ParseError>;
 
+impl Builtin {
+    pub fn parse(s: &str) -> Option<Self> {
+        use self::Builtin::*;
+        match s {
+            "Bool" => Some(Bool),
+            "Natural" => Some(Natural),
+            "Integer" => Some(Integer),
+            "Double" => Some(Double),
+            "Text" => Some(Text),
+            "List" => Some(List),
+            "Optional" => Some(Optional),
+            "Some" => Some(OptionalSome),
+            "None" => Some(OptionalNone),
+            "Natural/build" => Some(NaturalBuild),
+            "Natural/fold" => Some(NaturalFold),
+            "Natural/isZero" => Some(NaturalIsZero),
+            "Natural/even" => Some(NaturalEven),
+            "Natural/odd" => Some(NaturalOdd),
+            "Natural/toInteger" => Some(NaturalToInteger),
+            "Natural/show" => Some(NaturalShow),
+            "Integer/toDouble" => Some(IntegerToDouble),
+            "Integer/show" => Some(IntegerShow),
+            "Double/show" => Some(DoubleShow),
+            "List/build" => Some(ListBuild),
+            "List/fold" => Some(ListFold),
+            "List/length" => Some(ListLength),
+            "List/head" => Some(ListHead),
+            "List/last" => Some(ListLast),
+            "List/indexed" => Some(ListIndexed),
+            "List/reverse" => Some(ListReverse),
+            "Optional/fold" => Some(OptionalFold),
+            "Optional/build" => Some(OptionalBuild),
+            "Text/show" => Some(TextShow),
+            _ => None,
+        }
+    }
+}
+
 pub fn custom_parse_error(pair: &Pair<Rule>, msg: String) -> ParseError {
     let msg =
         format!("{} while matching on:\n{}", msg, debug_pair(pair.clone()));
@@ -221,466 +256,466 @@ fn can_be_shortcutted(rule: Rule) -> bool {
 }
 
 make_parser! {
-rule!(EOI<()>; raw_pair!(_) => ());
+    rule!(EOI<()>; raw_pair!(_) => ());
 
-rule!(label_raw<Label>; captured_str!(s) => Label::from(s.trim().to_owned()));
+    rule!(label_raw<Label>; captured_str!(s) => Label::from(s.trim().to_owned()));
 
-rule!(double_quote_literal<ParsedText>; children!(
-    [double_quote_chunk(chunks..)] => {
-        chunks.collect()
-    }
-));
-
-rule!(double_quote_chunk<ParsedTextContents<'a>>; children!(
-    [interpolation(e)] => {
-        InterpolatedTextContents::Expr(e)
-    },
-    [double_quote_escaped(s)] => {
-        InterpolatedTextContents::Text(s)
-    },
-    [double_quote_char(s)] => {
-        InterpolatedTextContents::Text(s)
-    },
-));
-rule!(double_quote_escaped<&'a str>;
-    // TODO: parse all escapes
-    captured_str!(s) => {
-        match s {
-            "\"" => "\"",
-            "$" => "$",
-            "\\" => "\\",
-            "/" => "/",
-            // "b" => "\b",
-            // "f" => "\f",
-            "n" => "\n",
-            "r" => "\r",
-            "t" => "\t",
-            // "uXXXX"
-            _ => unimplemented!(),
+    rule!(double_quote_literal<ParsedText>; children!(
+        [double_quote_chunk(chunks..)] => {
+            chunks.collect()
         }
-    }
-);
-rule!(double_quote_char<&'a str>;
-    captured_str!(s) => s
-);
+    ));
+
+    rule!(double_quote_chunk<ParsedTextContents<'a>>; children!(
+        [interpolation(e)] => {
+            InterpolatedTextContents::Expr(e)
+        },
+        [double_quote_escaped(s)] => {
+            InterpolatedTextContents::Text(s)
+        },
+        [double_quote_char(s)] => {
+            InterpolatedTextContents::Text(s)
+        },
+    ));
+    rule!(double_quote_escaped<&'a str>;
+        // TODO: parse all escapes
+        captured_str!(s) => {
+            match s {
+                "\"" => "\"",
+                "$" => "$",
+                "\\" => "\\",
+                "/" => "/",
+                // "b" => "\b",
+                // "f" => "\f",
+                "n" => "\n",
+                "r" => "\r",
+                "t" => "\t",
+                // "uXXXX"
+                _ => unimplemented!(),
+            }
+        }
+    );
+    rule!(double_quote_char<&'a str>;
+        captured_str!(s) => s
+    );
 
-rule!(end_of_line<()>; raw_pair!(_) => ());
+    rule!(end_of_line<()>; raw_pair!(_) => ());
 
-rule!(single_quote_literal<ParsedText>; children!(
-    [end_of_line(eol), single_quote_continue(contents)] => {
-        contents.into_iter().rev().collect::<ParsedText>()
-    }
-));
-rule!(single_quote_char<&'a str>;
-    captured_str!(s) => s
-);
-rule!(escaped_quote_pair<&'a str>;
-    raw_pair!(_) => "''"
-);
-rule!(escaped_interpolation<&'a str>;
-    raw_pair!(_) => "${"
-);
-rule!(interpolation<RcExpr>; children!(
-    [expression(e)] => e
-));
-
-rule!(single_quote_continue<Vec<ParsedTextContents<'a>>>; children!(
-    [interpolation(c), single_quote_continue(rest)] => {
-        let mut rest = rest;
-        rest.push(InterpolatedTextContents::Expr(c)); rest
-    },
-    [escaped_quote_pair(c), single_quote_continue(rest)] => {
-        let mut rest = rest;
-        rest.push(InterpolatedTextContents::Text(c)); rest
-    },
-    [escaped_interpolation(c), single_quote_continue(rest)] => {
-        let mut rest = rest;
-        rest.push(InterpolatedTextContents::Text(c)); rest
-    },
-    [single_quote_char(c), single_quote_continue(rest)] => {
-        let mut rest = rest;
-        rest.push(InterpolatedTextContents::Text(c)); rest
-    },
-    [] => {
-        vec![]
-    },
-));
-
-rule!(NaN_raw<()>; raw_pair!(_) => ());
-rule!(minus_infinity_literal<()>; raw_pair!(_) => ());
-rule!(plus_infinity_literal<()>; raw_pair!(_) => ());
-
-rule!(double_literal_raw<core::Double>;
-    raw_pair!(pair) => {
-        pair.as_str().trim()
-            .parse()
-            .map_err(|e: std::num::ParseFloatError| custom_parse_error(&pair, format!("{}", e)))?
-    }
-);
+    rule!(single_quote_literal<ParsedText>; children!(
+        [end_of_line(eol), single_quote_continue(contents)] => {
+            contents.into_iter().rev().collect::<ParsedText>()
+        }
+    ));
+    rule!(single_quote_char<&'a str>;
+        captured_str!(s) => s
+    );
+    rule!(escaped_quote_pair<&'a str>;
+        raw_pair!(_) => "''"
+    );
+    rule!(escaped_interpolation<&'a str>;
+        raw_pair!(_) => "${"
+    );
+    rule!(interpolation<ParsedExpr>; children!(
+        [expression(e)] => e
+    ));
+
+    rule!(single_quote_continue<Vec<ParsedTextContents<'a>>>; children!(
+        [interpolation(c), single_quote_continue(rest)] => {
+            let mut rest = rest;
+            rest.push(InterpolatedTextContents::Expr(c)); rest
+        },
+        [escaped_quote_pair(c), single_quote_continue(rest)] => {
+            let mut rest = rest;
+            rest.push(InterpolatedTextContents::Text(c)); rest
+        },
+        [escaped_interpolation(c), single_quote_continue(rest)] => {
+            let mut rest = rest;
+            rest.push(InterpolatedTextContents::Text(c)); rest
+        },
+        [single_quote_char(c), single_quote_continue(rest)] => {
+            let mut rest = rest;
+            rest.push(InterpolatedTextContents::Text(c)); rest
+        },
+        [] => {
+            vec![]
+        },
+    ));
+
+    rule!(NaN_raw<()>; raw_pair!(_) => ());
+    rule!(minus_infinity_literal<()>; raw_pair!(_) => ());
+    rule!(plus_infinity_literal<()>; raw_pair!(_) => ());
+
+    rule!(double_literal_raw<core::Double>;
+        raw_pair!(pair) => {
+            pair.as_str().trim()
+                .parse()
+                .map_err(|e: std::num::ParseFloatError| custom_parse_error(&pair, format!("{}", e)))?
+        }
+    );
 
-rule!(natural_literal_raw<core::Natural>;
-    raw_pair!(pair) => {
-        pair.as_str().trim()
-            .parse()
-            .map_err(|e: std::num::ParseIntError| custom_parse_error(&pair, format!("{}", e)))?
-    }
-);
+    rule!(natural_literal_raw<core::Natural>;
+        raw_pair!(pair) => {
+            pair.as_str().trim()
+                .parse()
+                .map_err(|e: std::num::ParseIntError| custom_parse_error(&pair, format!("{}", e)))?
+        }
+    );
 
-rule!(integer_literal_raw<core::Integer>;
-    raw_pair!(pair) => {
-        pair.as_str().trim()
-            .parse()
-            .map_err(|e: std::num::ParseIntError| custom_parse_error(&pair, format!("{}", e)))?
-    }
-);
-
-rule!(path<PathBuf>;
-    captured_str!(s) => (".".to_owned() + s).into()
-);
-
-rule_group!(local_raw<(FilePrefix, PathBuf)>);
-
-rule!(parent_path<(FilePrefix, PathBuf)> as local_raw; children!(
-    [path(p)] => (FilePrefix::Parent, p)
-));
-
-rule!(here_path<(FilePrefix, PathBuf)> as local_raw; children!(
-    [path(p)] => (FilePrefix::Here, p)
-));
-
-rule!(home_path<(FilePrefix, PathBuf)> as local_raw; children!(
-    [path(p)] => (FilePrefix::Home, p)
-));
-
-rule!(absolute_path<(FilePrefix, PathBuf)> as local_raw; children!(
-    [path(p)] => (FilePrefix::Absolute, p)
-));
-
-// TODO: other import types
-rule!(import_type_raw<ImportLocation>; children!(
-    // [missing_raw(_e)] => {
-    //     ImportLocation::Missing
-    // }
-    // [env_raw(e)] => {
-    //     ImportLocation::Env(e)
-    // }
-    // [http(url)] => {
-    //     ImportLocation::Remote(url)
-    // }
-    [local_raw((prefix, path))] => {
-        ImportLocation::Local(prefix, path)
-    }
-));
-
-rule!(import_hashed_raw<(ImportLocation, Option<()>)>; children!(
-    // TODO: handle hash
-    [import_type_raw(import)] => (import, None)
-));
-
-rule_group!(expression<RcExpr>);
-
-rule!(import_raw<RcExpr> as expression; children!(
-    // TODO: handle "as Text"
-    [import_hashed_raw((location, hash))] => {
-        bx(Expr::Embed(Import {
-            mode: ImportMode::Code,
-            hash,
-            location,
-        }))
-    }
-));
+    rule!(integer_literal_raw<core::Integer>;
+        raw_pair!(pair) => {
+            pair.as_str().trim()
+                .parse()
+                .map_err(|e: std::num::ParseIntError| custom_parse_error(&pair, format!("{}", e)))?
+        }
+    );
 
-rule!(lambda_expression<RcExpr> as expression; children!(
-    [label_raw(l), expression(typ), expression(body)] => {
-        bx(Expr::Lam(l, typ, body))
-    }
-));
+    rule!(path<PathBuf>;
+        captured_str!(s) => (".".to_owned() + s).into()
+    );
 
-rule!(ifthenelse_expression<RcExpr> as expression; children!(
-    [expression(cond), expression(left), expression(right)] => {
-        bx(Expr::BoolIf(cond, left, right))
-    }
-));
+    rule_group!(local_raw<(FilePrefix, PathBuf)>);
+
+    rule!(parent_path<(FilePrefix, PathBuf)> as local_raw; children!(
+        [path(p)] => (FilePrefix::Parent, p)
+    ));
+
+    rule!(here_path<(FilePrefix, PathBuf)> as local_raw; children!(
+        [path(p)] => (FilePrefix::Here, p)
+    ));
+
+    rule!(home_path<(FilePrefix, PathBuf)> as local_raw; children!(
+        [path(p)] => (FilePrefix::Home, p)
+    ));
+
+    rule!(absolute_path<(FilePrefix, PathBuf)> as local_raw; children!(
+        [path(p)] => (FilePrefix::Absolute, p)
+    ));
+
+    // TODO: other import types
+    rule!(import_type_raw<ImportLocation>; children!(
+        // [missing_raw(_e)] => {
+        //     ImportLocation::Missing
+        // }
+        // [env_raw(e)] => {
+        //     ImportLocation::Env(e)
+        // }
+        // [http(url)] => {
+        //     ImportLocation::Remote(url)
+        // }
+        [local_raw((prefix, path))] => {
+            ImportLocation::Local(prefix, path)
+        }
+    ));
+
+    rule!(import_hashed_raw<(ImportLocation, Option<()>)>; children!(
+        // TODO: handle hash
+        [import_type_raw(import)] => (import, None)
+    ));
+
+    rule_group!(expression<ParsedExpr>);
+
+    rule!(import_raw<ParsedExpr> as expression; children!(
+        // TODO: handle "as Text"
+        [import_hashed_raw((location, hash))] => {
+            bx(Expr::Embed(Import {
+                mode: ImportMode::Code,
+                hash,
+                location,
+            }))
+        }
+    ));
 
-rule!(let_expression<RcExpr> as expression; children!(
-    [let_binding(bindings..), expression(final_expr)] => {
-        bindings.fold(final_expr, |acc, x| bx(Expr::Let(x.0, x.1, x.2, acc)))
-    }
-));
+    rule!(lambda_expression<ParsedExpr> as expression; children!(
+        [label_raw(l), expression(typ), expression(body)] => {
+            bx(Expr::Lam(l, typ, body))
+        }
+    ));
 
-rule!(let_binding<(Label, Option<RcExpr>, RcExpr)>; children!(
-    [label_raw(name), expression(annot), expression(expr)] => (name, Some(annot), expr),
-    [label_raw(name), expression(expr)] => (name, None, expr),
-));
+    rule!(ifthenelse_expression<ParsedExpr> as expression; children!(
+        [expression(cond), expression(left), expression(right)] => {
+            bx(Expr::BoolIf(cond, left, right))
+        }
+    ));
 
-rule!(forall_expression<RcExpr> as expression; children!(
-    [label_raw(l), expression(typ), expression(body)] => {
-        bx(Expr::Pi(l, typ, body))
-    }
-));
+    rule!(let_expression<ParsedExpr> as expression; children!(
+        [let_binding(bindings..), expression(final_expr)] => {
+            bindings.fold(final_expr, |acc, x| bx(Expr::Let(x.0, x.1, x.2, acc)))
+        }
+    ));
 
-rule!(arrow_expression<RcExpr> as expression; children!(
-    [expression(typ), expression(body)] => {
-        bx(Expr::Pi("_".into(), typ, body))
-    }
-));
-
-rule!(merge_expression<RcExpr> as expression; children!(
-    [expression(x), expression(y), expression(z)] => bx(Expr::Merge(x, y, Some(z))),
-    [expression(x), expression(y)] => bx(Expr::Merge(x, y, None)),
-));
-
-rule!(List<()>; raw_pair!(_) => ());
-rule!(Optional<()>; raw_pair!(_) => ());
-
-rule!(empty_collection<RcExpr> as expression; children!(
-    [List(_), expression(y)] => {
-        bx(Expr::EmptyListLit(y))
-    },
-    [Optional(_), expression(y)] => {
-        bx(Expr::OptionalLit(Some(y), None))
-    },
-));
-
-rule!(non_empty_optional<RcExpr> as expression; children!(
-    [expression(x), Optional(_), expression(z)] => {
-        bx(Expr::OptionalLit(Some(z), Some(x)))
-    }
-));
-
-rule!(import_alt_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::ImportAlt, acc, e)))
-    },
-));
-rule!(or_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolOr, acc, e)))
-    },
-));
-rule!(plus_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::NaturalPlus, acc, e)))
-    },
-));
-rule!(text_append_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::TextAppend, acc, e)))
-    },
-));
-rule!(list_append_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::ListAppend, acc, e)))
-    },
-));
-rule!(and_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolAnd, acc, e)))
-    },
-));
-rule!(combine_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::Combine, acc, e)))
-    },
-));
-rule!(prefer_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::Prefer, acc, e)))
-    },
-));
-rule!(combine_types_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::CombineTypes, acc, e)))
-    },
-));
-rule!(times_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::NaturalTimes, acc, e)))
-    },
-));
-rule!(equal_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolEQ, acc, e)))
-    },
-));
-rule!(not_equal_expression<RcExpr> as expression; children!(
-    [expression(e)] => e,
-    [expression(first), expression(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolNE, acc, e)))
-    },
-));
-
-rule!(annotated_expression<RcExpr> as expression; children!(
-    [expression(e), expression(annot)] => {
-        bx(Expr::Annot(e, annot))
-    },
-    [expression(e)] => e,
-));
-
-rule!(application_expression<RcExpr> as expression; children!(
-    [expression(first), expression(rest..)] => {
-        let rest: Vec<_> = rest.collect();
-        if rest.is_empty() {
-            first
-        } else {
-            bx(Expr::App(first, rest))
+    rule!(let_binding<(Label, Option<ParsedExpr>, ParsedExpr)>; children!(
+        [label_raw(name), expression(annot), expression(expr)] => (name, Some(annot), expr),
+        [label_raw(name), expression(expr)] => (name, None, expr),
+    ));
+
+    rule!(forall_expression<ParsedExpr> as expression; children!(
+        [label_raw(l), expression(typ), expression(body)] => {
+            bx(Expr::Pi(l, typ, body))
         }
-    }
-));
+    ));
 
-rule!(selector_expression_raw<RcExpr> as expression; children!(
-    [expression(first), selector_raw(rest..)] => {
-        rest.fold(first, |acc, e| bx(Expr::Field(acc, e)))
-    }
-));
-
-// TODO: handle record projection
-rule!(selector_raw<Label>; children!(
-    [label_raw(l)] => l
-));
-
-rule!(literal_expression_raw<RcExpr> as expression; children!(
-    [double_literal_raw(n)] => bx(Expr::DoubleLit(n)),
-    [minus_infinity_literal(n)] => bx(Expr::DoubleLit(std::f64::NEG_INFINITY)),
-    [plus_infinity_literal(n)] => bx(Expr::DoubleLit(std::f64::INFINITY)),
-    [NaN_raw(n)] => bx(Expr::DoubleLit(std::f64::NAN)),
-    [natural_literal_raw(n)] => bx(Expr::NaturalLit(n)),
-    [integer_literal_raw(n)] => bx(Expr::IntegerLit(n)),
-    [double_quote_literal(s)] => bx(Expr::TextLit(s)),
-    [single_quote_literal(s)] => bx(Expr::TextLit(s)),
-    [expression(e)] => e,
-));
-
-rule!(identifier_raw<RcExpr> as expression; children!(
-    [label_raw(l), natural_literal_raw(idx)] => {
-        let name = String::from(l.clone());
-        match Builtin::parse(name.as_str()) {
-            Some(b) => bx(Expr::Builtin(b)),
-            None => match name.as_str() {
-                "True" => bx(Expr::BoolLit(true)),
-                "False" => bx(Expr::BoolLit(false)),
-                "Type" => bx(Expr::Const(Const::Type)),
-                "Kind" => bx(Expr::Const(Const::Kind)),
-                _ => bx(Expr::Var(V(l, idx))),
+    rule!(arrow_expression<ParsedExpr> as expression; children!(
+        [expression(typ), expression(body)] => {
+            bx(Expr::Pi("_".into(), typ, body))
+        }
+    ));
+
+    rule!(merge_expression<ParsedExpr> as expression; children!(
+        [expression(x), expression(y), expression(z)] => bx(Expr::Merge(x, y, Some(z))),
+        [expression(x), expression(y)] => bx(Expr::Merge(x, y, None)),
+    ));
+
+    rule!(List<()>; raw_pair!(_) => ());
+    rule!(Optional<()>; raw_pair!(_) => ());
+
+    rule!(empty_collection<ParsedExpr> as expression; children!(
+        [List(_), expression(y)] => {
+            bx(Expr::EmptyListLit(y))
+        },
+        [Optional(_), expression(y)] => {
+            bx(Expr::OptionalLit(Some(y), None))
+        },
+    ));
+
+    rule!(non_empty_optional<ParsedExpr> as expression; children!(
+        [expression(x), Optional(_), expression(z)] => {
+            bx(Expr::OptionalLit(Some(z), Some(x)))
+        }
+    ));
+
+    rule!(import_alt_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::ImportAlt, acc, e)))
+        },
+    ));
+    rule!(or_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolOr, acc, e)))
+        },
+    ));
+    rule!(plus_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::NaturalPlus, acc, e)))
+        },
+    ));
+    rule!(text_append_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::TextAppend, acc, e)))
+        },
+    ));
+    rule!(list_append_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::ListAppend, acc, e)))
+        },
+    ));
+    rule!(and_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolAnd, acc, e)))
+        },
+    ));
+    rule!(combine_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::Combine, acc, e)))
+        },
+    ));
+    rule!(prefer_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::Prefer, acc, e)))
+        },
+    ));
+    rule!(combine_types_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::CombineTypes, acc, e)))
+        },
+    ));
+    rule!(times_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::NaturalTimes, acc, e)))
+        },
+    ));
+    rule!(equal_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolEQ, acc, e)))
+        },
+    ));
+    rule!(not_equal_expression<ParsedExpr> as expression; children!(
+        [expression(e)] => e,
+        [expression(first), expression(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::BinOp(BinOp::BoolNE, acc, e)))
+        },
+    ));
+
+    rule!(annotated_expression<ParsedExpr> as expression; children!(
+        [expression(e), expression(annot)] => {
+            bx(Expr::Annot(e, annot))
+        },
+        [expression(e)] => e,
+    ));
+
+    rule!(application_expression<ParsedExpr> as expression; children!(
+        [expression(first), expression(rest..)] => {
+            let rest: Vec<_> = rest.collect();
+            if rest.is_empty() {
+                first
+            } else {
+                bx(Expr::App(first, rest))
             }
         }
-    },
-    [label_raw(l)] => {
-        let name = String::from(l.clone());
-        match Builtin::parse(name.as_str()) {
-            Some(b) => bx(Expr::Builtin(b)),
-            None => match name.as_str() {
-                "True" => bx(Expr::BoolLit(true)),
-                "False" => bx(Expr::BoolLit(false)),
-                "Type" => bx(Expr::Const(Const::Type)),
-                "Kind" => bx(Expr::Const(Const::Kind)),
-                _ => bx(Expr::Var(V(l, 0))),
+    ));
+
+    rule!(selector_expression_raw<ParsedExpr> as expression; children!(
+        [expression(first), selector_raw(rest..)] => {
+            rest.fold(first, |acc, e| bx(Expr::Field(acc, e)))
+        }
+    ));
+
+    // TODO: handle record projection
+    rule!(selector_raw<Label>; children!(
+        [label_raw(l)] => l
+    ));
+
+    rule!(literal_expression_raw<ParsedExpr> as expression; children!(
+        [double_literal_raw(n)] => bx(Expr::DoubleLit(n)),
+        [minus_infinity_literal(n)] => bx(Expr::DoubleLit(std::f64::NEG_INFINITY)),
+        [plus_infinity_literal(n)] => bx(Expr::DoubleLit(std::f64::INFINITY)),
+        [NaN_raw(n)] => bx(Expr::DoubleLit(std::f64::NAN)),
+        [natural_literal_raw(n)] => bx(Expr::NaturalLit(n)),
+        [integer_literal_raw(n)] => bx(Expr::IntegerLit(n)),
+        [double_quote_literal(s)] => bx(Expr::TextLit(s)),
+        [single_quote_literal(s)] => bx(Expr::TextLit(s)),
+        [expression(e)] => e,
+    ));
+
+    rule!(identifier_raw<ParsedExpr> as expression; children!(
+        [label_raw(l), natural_literal_raw(idx)] => {
+            let name = String::from(l.clone());
+            match Builtin::parse(name.as_str()) {
+                Some(b) => bx(Expr::Builtin(b)),
+                None => match name.as_str() {
+                    "True" => bx(Expr::BoolLit(true)),
+                    "False" => bx(Expr::BoolLit(false)),
+                    "Type" => bx(Expr::Const(Const::Type)),
+                    "Kind" => bx(Expr::Const(Const::Kind)),
+                    _ => bx(Expr::Var(V(l, idx))),
+                }
             }
+        },
+        [label_raw(l)] => {
+            let name = String::from(l.clone());
+            match Builtin::parse(name.as_str()) {
+                Some(b) => bx(Expr::Builtin(b)),
+                None => match name.as_str() {
+                    "True" => bx(Expr::BoolLit(true)),
+                    "False" => bx(Expr::BoolLit(false)),
+                    "Type" => bx(Expr::Const(Const::Type)),
+                    "Kind" => bx(Expr::Const(Const::Kind)),
+                    _ => bx(Expr::Var(V(l, 0))),
+                }
+            }
+        },
+    ));
+
+    rule!(empty_record_literal<ParsedExpr> as expression;
+        raw_pair!(_) => bx(Expr::RecordLit(BTreeMap::new()))
+    );
+
+    rule!(empty_record_type<ParsedExpr> as expression;
+        raw_pair!(_) => bx(Expr::Record(BTreeMap::new()))
+    );
+
+    rule!(non_empty_record_type_or_literal<ParsedExpr> as expression; children!(
+        [label_raw(first_label), non_empty_record_type(rest)] => {
+            let (first_expr, mut map) = rest;
+            map.insert(first_label, first_expr);
+            bx(Expr::Record(map))
+        },
+        [label_raw(first_label), non_empty_record_literal(rest)] => {
+            let (first_expr, mut map) = rest;
+            map.insert(first_label, first_expr);
+            bx(Expr::RecordLit(map))
+        },
+    ));
+
+    rule!(non_empty_record_type<(ParsedExpr, BTreeMap<Label, ParsedExpr>)>; children!(
+        [expression(expr), record_type_entry(entries..)] => {
+            (expr, entries.collect())
         }
-    },
-));
-
-rule!(empty_record_literal<RcExpr> as expression;
-    raw_pair!(_) => bx(Expr::RecordLit(BTreeMap::new()))
-);
-
-rule!(empty_record_type<RcExpr> as expression;
-    raw_pair!(_) => bx(Expr::Record(BTreeMap::new()))
-);
-
-rule!(non_empty_record_type_or_literal<RcExpr> as expression; children!(
-    [label_raw(first_label), non_empty_record_type(rest)] => {
-        let (first_expr, mut map) = rest;
-        map.insert(first_label, first_expr);
-        bx(Expr::Record(map))
-    },
-    [label_raw(first_label), non_empty_record_literal(rest)] => {
-        let (first_expr, mut map) = rest;
-        map.insert(first_label, first_expr);
-        bx(Expr::RecordLit(map))
-    },
-));
-
-rule!(non_empty_record_type<(RcExpr, BTreeMap<Label, RcExpr>)>; children!(
-    [expression(expr), record_type_entry(entries..)] => {
-        (expr, entries.collect())
-    }
-));
+    ));
 
-rule!(record_type_entry<(Label, RcExpr)>; children!(
-    [label_raw(name), expression(expr)] => (name, expr)
-));
+    rule!(record_type_entry<(Label, ParsedExpr)>; children!(
+        [label_raw(name), expression(expr)] => (name, expr)
+    ));
 
-rule!(non_empty_record_literal<(RcExpr, BTreeMap<Label, RcExpr>)>; children!(
-    [expression(expr), record_literal_entry(entries..)] => {
-        (expr, entries.collect())
-    }
-));
-
-rule!(record_literal_entry<(Label, RcExpr)>; children!(
-    [label_raw(name), expression(expr)] => (name, expr)
-));
-
-rule!(union_type_or_literal<RcExpr> as expression; children!(
-    [empty_union_type(_)] => {
-        bx(Expr::Union(BTreeMap::new()))
-    },
-    [non_empty_union_type_or_literal((Some((l, e)), entries))] => {
-        bx(Expr::UnionLit(l, e, entries))
-    },
-    [non_empty_union_type_or_literal((None, entries))] => {
-        bx(Expr::Union(entries))
-    },
-));
-
-rule!(empty_union_type<()>; raw_pair!(_) => ());
-
-rule!(non_empty_union_type_or_literal
-      <(Option<(Label, RcExpr)>, BTreeMap<Label, RcExpr>)>; children!(
-    [label_raw(l), expression(e), union_type_entries(entries)] => {
-        (Some((l, e)), entries)
-    },
-    [label_raw(l), expression(e), non_empty_union_type_or_literal(rest)] => {
-        let (x, mut entries) = rest;
-        entries.insert(l, e);
-        (x, entries)
-    },
-    [label_raw(l), expression(e)] => {
-        let mut entries = BTreeMap::new();
-        entries.insert(l, e);
-        (None, entries)
-    },
-));
-
-rule!(union_type_entries<BTreeMap<Label, RcExpr>>; children!(
-    [union_type_entry(entries..)] => entries.collect()
-));
-
-rule!(union_type_entry<(Label, RcExpr)>; children!(
-    [label_raw(name), expression(expr)] => (name, expr)
-));
-
-rule!(non_empty_list_literal_raw<RcExpr> as expression; children!(
-    [expression(items..)] => bx(Expr::NEListLit(items.collect()))
-));
-
-rule!(final_expression<RcExpr> as expression; children!(
-    [expression(e), EOI(_eoi)] => e
-));
+    rule!(non_empty_record_literal<(ParsedExpr, BTreeMap<Label, ParsedExpr>)>; children!(
+        [expression(expr), record_literal_entry(entries..)] => {
+            (expr, entries.collect())
+        }
+    ));
+
+    rule!(record_literal_entry<(Label, ParsedExpr)>; children!(
+        [label_raw(name), expression(expr)] => (name, expr)
+    ));
+
+    rule!(union_type_or_literal<ParsedExpr> as expression; children!(
+        [empty_union_type(_)] => {
+            bx(Expr::Union(BTreeMap::new()))
+        },
+        [non_empty_union_type_or_literal((Some((l, e)), entries))] => {
+            bx(Expr::UnionLit(l, e, entries))
+        },
+        [non_empty_union_type_or_literal((None, entries))] => {
+            bx(Expr::Union(entries))
+        },
+    ));
+
+    rule!(empty_union_type<()>; raw_pair!(_) => ());
+
+    rule!(non_empty_union_type_or_literal
+          <(Option<(Label, ParsedExpr)>, BTreeMap<Label, ParsedExpr>)>; children!(
+        [label_raw(l), expression(e), union_type_entries(entries)] => {
+            (Some((l, e)), entries)
+        },
+        [label_raw(l), expression(e), non_empty_union_type_or_literal(rest)] => {
+            let (x, mut entries) = rest;
+            entries.insert(l, e);
+            (x, entries)
+        },
+        [label_raw(l), expression(e)] => {
+            let mut entries = BTreeMap::new();
+            entries.insert(l, e);
+            (None, entries)
+        },
+    ));
+
+    rule!(union_type_entries<BTreeMap<Label, ParsedExpr>>; children!(
+        [union_type_entry(entries..)] => entries.collect()
+    ));
+
+    rule!(union_type_entry<(Label, ParsedExpr)>; children!(
+        [label_raw(name), expression(expr)] => (name, expr)
+    ));
+
+    rule!(non_empty_list_literal_raw<ParsedExpr> as expression; children!(
+        [expression(items..)] => bx(Expr::NEListLit(items.collect()))
+    ));
+
+    rule!(final_expression<ParsedExpr> as expression; children!(
+        [expression(e), EOI(_eoi)] => e
+    ));
 }
 
-pub fn parse_expr(s: &str) -> ParseResult<RcExpr> {
+pub fn parse_expr(s: &str) -> ParseResult<crate::ParsedExpr<X>> {
     let mut pairs = DhallParser::parse(Rule::final_expression, s)?;
     let expr = parse_any(pairs.next().unwrap())?;
     assert_eq!(pairs.next(), None);