Do more restructuring.

17 files changed, 875 insertions, 536 deletions

diff --git a/src/chomp/ast.rs b/src/chomp/ast.rs
index e8e3309..58d76c9 100644
--- a/src/chomp/ast.rs
+++ b/src/chomp/ast.rs
@@ -1,11 +1,80 @@
-use std::fmt::{self, Display};
+use std::{
+    fmt::{self, Display},
+    hash,
+};
 
 use proc_macro2::Span;
 use syn::{Ident, LitStr, Token};
 
-pub type Epsilon = Token![_];
+use super::Name;
 
-pub type Literal = LitStr;
+pub type Epsilon = Option<Token![_]>;
+
+#[derive(Clone, Debug)]
+pub enum Literal {
+    Spanned(LitStr),
+    Spanless(String),
+}
+
+impl Literal {
+    pub fn value(&self) -> String {
+        match self {
+            Self::Spanned(l) => l.value(),
+            Self::Spanless(s) => s.clone(),
+        }
+    }
+
+    pub fn span(&self) -> Option<Span> {
+        match self {
+            Self::Spanned(l) => Some(l.span()),
+            Self::Spanless(_) => None,
+        }
+    }
+
+    pub fn as_litstr(self, span: Span) -> LitStr {
+        match self {
+            Self::Spanned(l) => l,
+            Self::Spanless(s) => LitStr::new(&s, span),
+        }
+    }
+}
+
+impl PartialEq for Literal {
+    fn eq(&self, other: &Self) -> bool {
+        match (self, other) {
+            (Self::Spanned(me), Self::Spanned(them)) => me == them,
+            (Self::Spanned(me), Self::Spanless(them)) => &me.value() == them,
+            (Self::Spanless(me), Self::Spanned(them)) => me == &them.value(),
+            (Self::Spanless(me), Self::Spanless(them)) => me == them,
+        }
+    }
+}
+
+impl Eq for Literal {}
+
+impl hash::Hash for Literal {
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        self.value().hash(state)
+    }
+}
+
+impl Display for Literal {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{:?}", self.value())
+    }
+}
+
+impl From<LitStr> for Literal {
+    fn from(l: LitStr) -> Self {
+        Self::Spanned(l)
+    }
+}
+
+impl From<String> for Literal {
+    fn from(s: String) -> Self {
+        Self::Spanless(s)
+    }
+}
 
 #[derive(Clone, Debug)]
 pub struct Cat {
@@ -50,6 +119,14 @@ impl Display for Cat {
     }
 }
 
+impl PartialEq for Cat {
+    fn eq(&self, other: &Self) -> bool {
+        self.first() == other.first() && self.second() == other.second()
+    }
+}
+
+impl Eq for Cat {}
+
 #[derive(Clone, Debug)]
 pub struct Alt {
     pub left: Box<Expression>,
@@ -93,15 +170,23 @@ impl Display for Alt {
     }
 }
 
+impl PartialEq for Alt {
+    fn eq(&self, other: &Self) -> bool {
+        self.left() == other.left() && self.right() == other.right()
+    }
+}
+
+impl Eq for Alt {}
+
 #[derive(Clone, Debug)]
 pub struct Fix {
-    pub arg: Ident,
+    pub arg: Name,
     pub inner: Box<Expression>,
     pub span: Option<Span>,
 }
 
 impl Fix {
-    pub fn new(arg: Ident, inner: Expression, span: Option<Span>) -> Self {
+    pub fn new(arg: Name, inner: Expression, span: Option<Span>) -> Self {
         Self {
             arg,
             inner: Box::new(inner),
@@ -109,7 +194,7 @@ impl Fix {
         }
     }
 
-    pub fn arg(&self) -> &Ident {
+    pub fn arg(&self) -> &Name {
         &self.arg
     }
 
@@ -132,18 +217,26 @@ impl Display for Fix {
     }
 }
 
-#[derive(Clone, Debug)]
+impl PartialEq for Fix {
+    fn eq(&self, other: &Self) -> bool {
+        self.inner() == other.inner()
+    }
+}
+
+impl Eq for Fix {}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
 pub struct Variable {
-    pub name: Ident,
+    pub name: Name,
     pub index: usize,
 }
 
 impl Variable {
-    pub fn new(name: Ident, index: usize) -> Self {
+    pub fn new(name: Name, index: usize) -> Self {
         Self { name, index }
     }
 
-    pub fn name(&self) -> &Ident {
+    pub fn name(&self) -> &Name {
         &self.name
     }
 
@@ -162,18 +255,18 @@ impl Display for Variable {
     }
 }
 
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
 pub struct Parameter {
-    pub name: Ident,
+    pub name: Name,
     pub index: usize,
 }
 
 impl Parameter {
-    pub fn new(name: Ident, index: usize) -> Self {
+    pub fn new(name: Name, index: usize) -> Self {
         Self { name, index }
     }
 
-    pub fn name(&self) -> &Ident {
+    pub fn name(&self) -> &Name {
         &self.name
     }
 
@@ -188,7 +281,7 @@ impl Parameter {
 
 impl Display for Parameter {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.name.fmt(f)
+        write!(f, "{}", self.name)
     }
 }
 
@@ -242,6 +335,14 @@ impl Display for Call {
     }
 }
 
+impl PartialEq for Call {
+    fn eq(&self, other: &Self) -> bool {
+        self.name() == other.name() && self.args() == other.args()
+    }
+}
+
+impl Eq for Call {}
+
 #[derive(Clone, Debug)]
 pub enum Expression {
     /// Matches the empty string.
@@ -266,7 +367,7 @@ impl Display for Expression {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             Self::Epsilon(_) => write!(f, "_"),
-            Self::Literal(l) => write!(f, "{:?}", l.value()),
+            Self::Literal(l) => l.fmt(f),
             Self::Cat(c) => c.fmt(f),
             Self::Alt(a) => a.fmt(f),
             Self::Fix(x) => x.fmt(f),
@@ -277,6 +378,65 @@ impl Display for Expression {
     }
 }
 
+impl PartialEq for Expression {
+    fn eq(&self, other: &Self) -> bool {
+        match self {
+            Self::Epsilon(_) => matches!(other, Self::Epsilon(_)),
+            Self::Literal(l) => {
+                if let Self::Literal(them) = other {
+                    l == them
+                } else {
+                    false
+                }
+            }
+            Self::Cat(c) => {
+                if let Self::Cat(them) = other {
+                    c == them
+                } else {
+                    false
+                }
+            }
+            Self::Alt(a) => {
+                if let Self::Alt(them) = other {
+                    a == them
+                } else {
+                    false
+                }
+            }
+            Self::Fix(f) => {
+                if let Self::Fix(them) = other {
+                    f == them
+                } else {
+                    false
+                }
+            }
+            Self::Variable(v) => {
+                if let Self::Variable(them) = other {
+                    v == them
+                } else {
+                    false
+                }
+            }
+            Self::Parameter(p) => {
+                if let Self::Parameter(them) = other {
+                    p == them
+                } else {
+                    false
+                }
+            }
+            Self::Call(c) => {
+                if let Self::Call(them) = other {
+                    c == them
+                } else {
+                    false
+                }
+            }
+        }
+    }
+}
+
+impl Eq for Expression {}
+
 impl From<Epsilon> for Expression {
     fn from(eps: Epsilon) -> Self {
         Self::Epsilon(eps)
@@ -334,7 +494,7 @@ pub struct Function {
 }
 
 impl Function {
-    pub fn new(name: Ident, params: usize, expr: Expression, span: Option<Span>) -> Self {
+    pub const fn new(name: Ident, params: usize, expr: Expression, span: Option<Span>) -> Self {
         Self {
             name,
             params,
diff --git a/src/chomp/check.rs b/src/chomp/check.rs
deleted file mode 100644
index cb4798c..0000000
--- a/src/chomp/check.rs
+++ /dev/null
@@ -1,481 +0,0 @@
-use proc_macro2::Span;
-
-use super::{
-    ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable},
-    context::Context,
-    error::{AltError, CatError, FixError, SubstituteError, TypeError},
-    set::{FirstSet, FlastSet},
-    typed::{self, Type, TypedExpression},
-    visit::{Folder, Mapper, Visitable, Visitor},
-};
-
-/// Test if term is closed for a context with `depth` variables.
-#[derive(Debug, Default)]
-struct Closed {
-    depth: usize,
-}
-
-impl Visitor for Closed {
-    type Out = bool;
-
-    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
-        true
-    }
-
-    fn visit_literal(&mut self, _lit: &Literal) -> Self::Out {
-        true
-    }
-
-    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
-        cat.first().visit(self) && cat.second().visit(self)
-    }
-
-    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
-        alt.left().visit(self) && alt.right().visit(self)
-    }
-
-    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
-        self.depth += 1;
-        let res = fix.inner().visit(self);
-        self.depth -= 1;
-        res
-    }
-
-    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
-        var.index() < self.depth
-    }
-
-    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
-        true
-    }
-
-    fn visit_call(&mut self, call: &Call) -> Self::Out {
-        call.args().iter().all(|arg| arg.visit(self))
-    }
-}
-
-#[derive(Clone, Copy, Debug)]
-pub struct Spanning;
-
-impl Visitor for Spanning {
-    type Out = Option<Span>;
-
-    fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out {
-        Some(eps.span)
-    }
-
-    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
-        Some(lit.span())
-    }
-
-    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
-        let fst = cat.first().visit(self);
-        let snd = cat.second().visit(self);
-
-        match (fst, snd) {
-            (None, snd) => snd,
-            (Some(fst), None) => Some(fst),
-            (Some(fst), Some(snd)) => fst.join(snd),
-        }
-    }
-
-    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
-        let left = alt.left().visit(self);
-        let right = alt.right().visit(self);
-
-        match (left, right) {
-            (None, right) => right,
-            (Some(left), None) => Some(left),
-            (Some(left), Some(right)) => left.join(right),
-        }
-    }
-
-    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
-        fix.span()
-    }
-
-    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
-        Some(var.name().span())
-    }
-
-    fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
-        Some(param.name().span())
-    }
-
-    fn visit_call(&mut self, call: &Call) -> Self::Out {
-        call.span()
-    }
-}
-
-#[derive(Debug)]
-pub struct TypeInfer<'a> {
-    context: &'a mut Context,
-}
-
-impl Visitor for TypeInfer<'_> {
-    type Out = Result<Type, TypeError>;
-
-    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
-        Ok(Type::new(true, FirstSet::default(), FlastSet::default()))
-    }
-
-    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
-        Ok(Type::of_str(&lit.value()))
-    }
-
-    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
-        let first = cat.first().visit(self)?;
-        let second = self
-            .context
-            .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?;
-
-        if first.nullable() {
-            Err(TypeError::Cat(CatError::FirstNullable(cat.clone())))
-        } else if !first
-            .flast_set()
-            .intersect_first(second.first_set())
-            .is_empty()
-        {
-            Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone())))
-        } else {
-            Ok(first.cat(second))
-        }
-    }
-
-    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
-        let left = alt.left().visit(self)?;
-        let right = alt.right().visit(self)?;
-
-        if left.nullable() && right.nullable() {
-            Err(TypeError::Alt(AltError::BothNullable(alt.clone())))
-        } else if !left.first_set().intersect(right.first_set()).is_empty() {
-            Err(TypeError::Alt(AltError::FirstOverlap(alt.clone())))
-        } else {
-            Ok(left.alt(right))
-        }
-    }
-
-    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
-        let mut res = Type::default();
-        let mut last = None;
-
-        while last.map(|r| r != res).unwrap_or(true) {
-            last = Some(res);
-            res = self
-                .context
-                .with_variable_type(last.as_ref().cloned().unwrap(), |context| {
-                    fix.inner().visit(&mut TypeInfer { context })
-                })
-                .map_err(|e| {
-                    TypeError::Fix(FixError(
-                        fix.clone(),
-                        last.as_ref().cloned().unwrap(),
-                        Box::new(e),
-                    ))
-                })?;
-        }
-
-        Ok(res)
-    }
-
-    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
-        Ok(self.context.get_variable_type(&var)?.clone())
-    }
-
-    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
-        todo!()
-    }
-
-    fn visit_call(&mut self, _call: &Call) -> Self::Out {
-        todo!()
-    }
-}
-
-#[derive(Debug)]
-pub struct TypeCheck<'a> {
-    pub context: &'a mut Context,
-}
-
-impl Folder for TypeCheck<'_> {
-    type Out = Result<TypedExpression, TypeError>;
-
-    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
-        Ok(typed::Epsilon::from(eps).into())
-    }
-
-    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
-        Ok(typed::Literal::from(lit).into())
-    }
-
-    fn fold_cat(&mut self, cat: Cat) -> Self::Out {
-        let ty = TypeInfer {
-            context: self.context,
-        }
-        .visit_cat(&cat)?;
-        let fst = cat.fst.fold(self)?;
-        let snd = cat.snd;
-        let snd = self
-            .context
-            .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?;
-
-        Ok(typed::Cat::new(fst, cat.punct, snd, ty).into())
-    }
-
-    fn fold_alt(&mut self, alt: Alt) -> Self::Out {
-        let ty = TypeInfer {
-            context: self.context,
-        }
-        .visit_alt(&alt)?;
-        let left = alt.left.fold(self)?;
-        let right = alt.right.fold(self)?;
-
-        Ok(typed::Alt::new(left, alt.punct, right, ty).into())
-    }
-
-    fn fold_fix(&mut self, fix: Fix) -> Self::Out {
-        let ty = TypeInfer {
-            context: self.context,
-        }
-        .visit_fix(&fix)?;
-        let inner = fix.inner;
-        let inner = self
-            .context
-            .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?;
-
-        Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into())
-    }
-
-    fn fold_variable(&mut self, var: Variable) -> Self::Out {
-        let ty = TypeInfer {
-            context: self.context,
-        }
-        .visit_variable(&var)?;
-        Ok(typed::Variable::new(var, ty).into())
-    }
-
-    fn fold_parameter(&mut self, _param: Parameter) -> Self::Out {
-        todo!()
-    }
-
-    fn fold_call(&mut self, _call: Call) -> Self::Out {
-        todo!()
-    }
-}
-
-#[derive(Debug, Default)]
-struct DeepenVars {
-    depth: usize,
-}
-
-impl Mapper for DeepenVars {
-    type Out = ();
-
-    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
-
-    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
-
-    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
-        cat.first_mut().map(self);
-        cat.second_mut().map(self);
-    }
-
-    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
-        alt.left_mut().map(self);
-        alt.right_mut().map(self);
-    }
-
-    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
-        self.depth += 1;
-        fix.inner_mut().map(self);
-        self.depth -= 1;
-    }
-
-    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
-        if bind.index() >= self.depth {
-            *bind.index_mut() += 1;
-        }
-    }
-
-    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
-
-    fn map_call(&mut self, call: &mut Call) -> Self::Out {
-        for arg in call.args_mut() {
-            arg.map(self);
-        }
-    }
-}
-
-#[derive(Debug, Default)]
-struct ShallowVars {
-    depth: usize,
-}
-
-impl Mapper for ShallowVars {
-    type Out = ();
-
-    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
-
-    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
-
-    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
-        cat.first_mut().map(self);
-        cat.second_mut().map(self);
-    }
-
-    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
-        alt.left_mut().map(self);
-        alt.right_mut().map(self);
-    }
-
-    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
-        self.depth += 1;
-        fix.inner_mut().map(self);
-        self.depth -= 1;
-    }
-
-    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
-        if bind.index() > self.depth {
-            *bind.index_mut() -= 1;
-        }
-    }
-
-    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
-
-    fn map_call(&mut self, call: &mut Call) -> Self::Out {
-        for arg in call.args_mut() {
-            arg.map(self);
-        }
-    }
-}
-
-struct Substitute {
-    params: Vec<Expression>,
-}
-
-impl Folder for Substitute {
-    type Out = Result<Expression, SubstituteError>;
-
-    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
-        Ok(eps.into())
-    }
-
-    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
-        Ok(lit.into())
-    }
-
-    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
-        cat.fst = Box::new(cat.fst.fold(self)?);
-        cat.snd = Box::new(cat.snd.fold(self)?);
-        Ok(cat.into())
-    }
-
-    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
-        alt.left = Box::new(alt.left.fold(self)?);
-        alt.right = Box::new(alt.right.fold(self)?);
-        Ok(alt.into())
-    }
-
-    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
-        for param in &mut self.params {
-            param.map(&mut DeepenVars::default());
-        }
-
-        fix.inner = Box::new(fix.inner.fold(self)?);
-
-        for param in &mut self.params {
-            param.map(&mut ShallowVars::default());
-        }
-
-        Ok(fix.into())
-    }
-
-    fn fold_variable(&mut self, var: Variable) -> Self::Out {
-        Ok(Expression::Variable(var))
-    }
-
-    fn fold_call(&mut self, mut call: Call) -> Self::Out {
-        call.args = call
-            .args
-            .into_iter()
-            .map(|arg| arg.fold(self))
-            .collect::<Result<_, _>>()?;
-        Ok(call.into())
-    }
-
-    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
-        self.params
-            .get(param.index())
-            .cloned()
-            .ok_or(SubstituteError::FreeParameter(param))
-    }
-}
-
-#[derive(Clone, Debug)]
-pub struct InlineCall {
-    function: Function,
-}
-
-impl InlineCall {
-    pub fn new(function: Function) -> Self {
-        Self { function }
-    }
-}
-
-impl Folder for InlineCall {
-    type Out = Result<Expression, SubstituteError>;
-
-    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
-        Ok(eps.into())
-    }
-
-    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
-        Ok(lit.into())
-    }
-
-    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
-        cat.fst = Box::new(cat.fst.fold(self)?);
-        cat.snd = Box::new(cat.snd.fold(self)?);
-        Ok(cat.into())
-    }
-
-    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
-        alt.left = Box::new(alt.left.fold(self)?);
-        alt.right = Box::new(alt.right.fold(self)?);
-        Ok(alt.into())
-    }
-
-    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
-        fix.inner = Box::new(fix.inner.fold(self)?);
-        Ok(fix.into())
-    }
-
-    fn fold_variable(&mut self, var: Variable) -> Self::Out {
-        Ok(var.into())
-    }
-
-    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
-        Ok(param.into())
-    }
-
-    fn fold_call(&mut self, mut call: Call) -> Self::Out {
-        call.args = call
-            .args
-            .into_iter()
-            .map(|arg| arg.fold(self))
-            .collect::<Result<_, _>>()?;
-
-        if call.name != self.function.name {
-            Ok(call.into())
-        } else if call.args.len() != self.function.params {
-            Err(SubstituteError::WrongArgCount {
-                call,
-                expected: self.function.params,
-            })
-        } else {
-            self.function
-                .expr
-                .clone()
-                .fold(&mut Substitute { params: call.args })
-        }
-    }
-}
diff --git a/src/chomp/check/check.rs b/src/chomp/check/check.rs
new file mode 100644
index 0000000..8729565
--- /dev/null
+++ b/src/chomp/check/check.rs
@@ -0,0 +1,81 @@
+use super::{
+    super::{
+        ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+        context::Context,
+        error::TypeError,
+        typed::{self, TypedExpression},
+        visit::{Folder, Visitable, Visitor},
+    },
+    TypeInfer,
+};
+
+#[derive(Debug)]
+pub struct TypeCheck<'a> {
+    pub context: &'a mut Context,
+}
+
+impl Folder for TypeCheck<'_> {
+    type Out = Result<TypedExpression, TypeError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(typed::Epsilon::from(eps).into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(typed::Literal::from(lit).into())
+    }
+
+    fn fold_cat(&mut self, cat: Cat) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_cat(&cat)?;
+        let fst = cat.fst.fold(self)?;
+        let snd = cat.snd;
+        let snd = self
+            .context
+            .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?;
+
+        Ok(typed::Cat::new(fst, cat.punct, snd, ty).into())
+    }
+
+    fn fold_alt(&mut self, alt: Alt) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_alt(&alt)?;
+        let left = alt.left.fold(self)?;
+        let right = alt.right.fold(self)?;
+
+        Ok(typed::Alt::new(left, alt.punct, right, ty).into())
+    }
+
+    fn fold_fix(&mut self, fix: Fix) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_fix(&fix)?;
+        let inner = fix.inner;
+        let inner = self
+            .context
+            .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?;
+
+        Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_variable(&var)?;
+        Ok(typed::Variable::new(var, ty).into())
+    }
+
+    fn fold_parameter(&mut self, _param: Parameter) -> Self::Out {
+        todo!()
+    }
+
+    fn fold_call(&mut self, _call: Call) -> Self::Out {
+        todo!()
+    }
+}
diff --git a/src/chomp/check/closed.rs b/src/chomp/check/closed.rs
new file mode 100644
index 0000000..07ef7ac
--- /dev/null
+++ b/src/chomp/check/closed.rs
@@ -0,0 +1,50 @@
+use super::super::{
+    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    visit::{Visitable, Visitor},
+};
+
+/// Test if term is closed for a context with `depth` variables.
+#[derive(Copy, Clone, Debug, Default)]
+pub struct Closed {
+    depth: usize,
+    params: usize,
+}
+
+impl Visitor for Closed {
+    type Out = bool;
+
+    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+        true
+    }
+
+    fn visit_literal(&mut self, _lit: &Literal) -> Self::Out {
+        true
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        cat.first().visit(self) && cat.second().visit(self)
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        alt.left().visit(self) && alt.right().visit(self)
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        self.depth += 1;
+        let res = fix.inner().visit(self);
+        self.depth -= 1;
+        res
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        var.index() < self.depth
+    }
+
+    fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
+        param.index() < self.params
+    }
+
+    fn visit_call(&mut self, call: &Call) -> Self::Out {
+        call.args().iter().all(|arg| arg.visit(self))
+    }
+}
diff --git a/src/chomp/check/deepen.rs b/src/chomp/check/deepen.rs
new file mode 100644
index 0000000..b9f606d
--- /dev/null
+++ b/src/chomp/check/deepen.rs
@@ -0,0 +1,47 @@
+use super::super::{
+    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    visit::{Mapper, Visitable},
+};
+
+#[derive(Clone, Copy, Debug, Default)]
+pub struct DeepenVars {
+    depth: usize,
+}
+
+impl Mapper for DeepenVars {
+    type Out = ();
+
+    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+        cat.first_mut().map(self);
+        cat.second_mut().map(self);
+    }
+
+    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+        alt.left_mut().map(self);
+        alt.right_mut().map(self);
+    }
+
+    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+        self.depth += 1;
+        fix.inner_mut().map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+        if bind.index() >= self.depth {
+            *bind.index_mut() += 1;
+        }
+    }
+
+    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+    fn map_call(&mut self, call: &mut Call) -> Self::Out {
+        for arg in call.args_mut() {
+            arg.map(self);
+        }
+    }
+}
diff --git a/src/chomp/check/infer.rs b/src/chomp/check/infer.rs
new file mode 100644
index 0000000..941ddba
--- /dev/null
+++ b/src/chomp/check/infer.rs
@@ -0,0 +1,92 @@
+use super::super::{
+    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    context::Context,
+    error::{AltError, CatError, FixError, TypeError},
+    set::{FirstSet, FlastSet},
+    typed::Type,
+    visit::{Visitable, Visitor},
+};
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+    pub context: &'a mut Context,
+}
+
+impl Visitor for TypeInfer<'_> {
+    type Out = Result<Type, TypeError>;
+
+    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+        Ok(Type::new(true, FirstSet::default(), FlastSet::default()))
+    }
+
+    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+        Ok(Type::of_str(&lit.value()))
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        let first = cat.first().visit(self)?;
+        let second = self
+            .context
+            .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?;
+
+        if first.nullable() {
+            Err(TypeError::Cat(CatError::FirstNullable(cat.clone())))
+        } else if !first
+            .flast_set()
+            .intersect_first(second.first_set())
+            .is_empty()
+        {
+            Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone())))
+        } else {
+            Ok(first.cat(second))
+        }
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        let left = alt.left().visit(self)?;
+        let right = alt.right().visit(self)?;
+
+        if left.nullable() && right.nullable() {
+            Err(TypeError::Alt(AltError::BothNullable(alt.clone())))
+        } else if !left.first_set().intersect(right.first_set()).is_empty() {
+            Err(TypeError::Alt(AltError::FirstOverlap(alt.clone())))
+        } else {
+            Ok(left.alt(right))
+        }
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        let mut res = Type::default();
+        let mut last = None;
+
+        while last.map(|r| r != res).unwrap_or(true) {
+            last = Some(res);
+            res = self
+                .context
+                .with_variable_type(last.as_ref().cloned().unwrap(), |context| {
+                    fix.inner().visit(&mut TypeInfer { context })
+                })
+                .map_err(|e| {
+                    TypeError::Fix(FixError(
+                        fix.clone(),
+                        last.as_ref().cloned().unwrap(),
+                        Box::new(e),
+                    ))
+                })?;
+        }
+
+        Ok(res)
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        Ok(self.context.get_variable_type(&var)?.clone())
+    }
+
+    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+        todo!()
+    }
+
+    fn visit_call(&mut self, _call: &Call) -> Self::Out {
+        todo!()
+    }
+}
diff --git a/src/chomp/check/inline.rs b/src/chomp/check/inline.rs
new file mode 100644
index 0000000..a6a831c
--- /dev/null
+++ b/src/chomp/check/inline.rs
@@ -0,0 +1,105 @@
+use super::{
+    super::{
+        ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable},
+        error::SubstituteError,
+        visit::{Folder, Visitable},
+    },
+    SubstituteParams,
+};
+
+#[derive(Clone, Debug)]
+pub struct InlineCalls {
+    function: Function,
+}
+
+impl InlineCalls {
+    pub fn new(function: Function) -> Self {
+        Self { function }
+    }
+}
+
+impl Folder for InlineCalls {
+    type Out = Result<Expression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(eps.into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(lit.into())
+    }
+
+    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+        cat.fst = Box::new(cat.fst.fold(self)?);
+        cat.snd = Box::new(cat.snd.fold(self)?);
+        Ok(cat.into())
+    }
+
+    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+        alt.left = Box::new(alt.left.fold(self)?);
+        alt.right = Box::new(alt.right.fold(self)?);
+        Ok(alt.into())
+    }
+
+    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+        fix.inner = Box::new(fix.inner.fold(self)?);
+        Ok(fix.into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        Ok(var.into())
+    }
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+        Ok(param.into())
+    }
+
+    fn fold_call(&mut self, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+
+        if call.name != self.function.name {
+            Ok(call.into())
+        } else if call.args.len() != self.function.params {
+            Err(SubstituteError::WrongArgCount {
+                call,
+                expected: self.function.params,
+            })
+        } else {
+            self.function
+                .expr
+                .clone()
+                .fold(&mut SubstituteParams::new(call.args))
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use proc_macro2::Span;
+    use syn::Ident;
+
+    use super::*;
+
+    const OPT_NAME: &str = "opt";
+    const OPT: Function = Function::new(
+        Ident::new(OPT_NAME, Span::call_site()),
+        1,
+        Expression::Alt(Alt::new(
+            Epsilon::default().into(),
+            None,
+            Parameter::new(None, 0).into(),
+        )),
+        None,
+    );
+
+    #[test]
+    fn test_inline_absent() {
+        let expr = Epsilon::default();
+        let inlined = expr.fold(&mut InlineCalls::new(OPT));
+        assert_eq!(inlined, Ok(Expression::from(Epsilon::default())))
+    }
+}
diff --git a/src/chomp/check/mod.rs b/src/chomp/check/mod.rs
new file mode 100644
index 0000000..c9aeda4
--- /dev/null
+++ b/src/chomp/check/mod.rs
@@ -0,0 +1,17 @@
+mod check;
+mod closed;
+mod deepen;
+mod infer;
+mod inline;
+mod shallow;
+mod spanning;
+mod substitute;
+
+pub use check::TypeCheck;
+pub use closed::Closed;
+pub use deepen::DeepenVars;
+pub use infer::TypeInfer;
+pub use inline::InlineCalls;
+pub use shallow::ShallowVars;
+pub use spanning::Spanning;
+pub use substitute::SubstituteParams;
diff --git a/src/chomp/check/shallow.rs b/src/chomp/check/shallow.rs
new file mode 100644
index 0000000..e5cc1a1
--- /dev/null
+++ b/src/chomp/check/shallow.rs
@@ -0,0 +1,47 @@
+use super::super::{
+    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    visit::{Mapper, Visitable},
+};
+
+#[derive(Clone, Copy, Debug, Default)]
+pub struct ShallowVars {
+    depth: usize,
+}
+
+impl Mapper for ShallowVars {
+    type Out = ();
+
+    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+        cat.first_mut().map(self);
+        cat.second_mut().map(self);
+    }
+
+    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+        alt.left_mut().map(self);
+        alt.right_mut().map(self);
+    }
+
+    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+        self.depth += 1;
+        fix.inner_mut().map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+        if bind.index() > self.depth {
+            *bind.index_mut() -= 1;
+        }
+    }
+
+    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+    fn map_call(&mut self, call: &mut Call) -> Self::Out {
+        for arg in call.args_mut() {
+            arg.map(self);
+        }
+    }
+}
diff --git a/src/chomp/check/spanning.rs b/src/chomp/check/spanning.rs
new file mode 100644
index 0000000..91e593b
--- /dev/null
+++ b/src/chomp/check/spanning.rs
@@ -0,0 +1,59 @@
+use proc_macro2::{Ident, Span};
+
+use super::super::{
+    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    visit::{Visitable, Visitor},
+};
+
+#[derive(Clone, Copy, Debug)]
+pub struct Spanning;
+
+impl Visitor for Spanning {
+    type Out = Option<Span>;
+
+    fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out {
+        eps.map(|e| e.span)
+    }
+
+    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+        lit.span()
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        let fst = cat.first().visit(self);
+        let snd = cat.second().visit(self);
+
+        match (fst, snd) {
+            (None, snd) => snd,
+            (Some(fst), None) => Some(fst),
+            (Some(fst), Some(snd)) => fst.join(snd),
+        }
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        let left = alt.left().visit(self);
+        let right = alt.right().visit(self);
+
+        match (left, right) {
+            (None, right) => right,
+            (Some(left), None) => Some(left),
+            (Some(left), Some(right)) => left.join(right),
+        }
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        fix.span()
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        var.name().span()
+    }
+
+    fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
+        param.name().span()
+    }
+
+    fn visit_call(&mut self, call: &Call) -> Self::Out {
+        call.span()
+    }
+}
diff --git a/src/chomp/check/substitute.rs b/src/chomp/check/substitute.rs
new file mode 100644
index 0000000..32595b1
--- /dev/null
+++ b/src/chomp/check/substitute.rs
@@ -0,0 +1,77 @@
+use super::{
+    super::{
+        ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable},
+        error::SubstituteError,
+        visit::{Folder, Visitable},
+    },
+    DeepenVars, ShallowVars,
+};
+
+#[derive(Clone, Debug)]
+pub struct SubstituteParams {
+    params: Vec<Expression>,
+}
+
+impl SubstituteParams {
+    pub fn new(params: Vec<Expression>) -> Self {
+        Self { params }
+    }
+}
+
+impl Folder for SubstituteParams {
+    type Out = Result<Expression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(eps.into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(lit.into())
+    }
+
+    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+        cat.fst = Box::new(cat.fst.fold(self)?);
+        cat.snd = Box::new(cat.snd.fold(self)?);
+        Ok(cat.into())
+    }
+
+    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+        alt.left = Box::new(alt.left.fold(self)?);
+        alt.right = Box::new(alt.right.fold(self)?);
+        Ok(alt.into())
+    }
+
+    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+        for param in &mut self.params {
+            param.map(&mut DeepenVars::default());
+        }
+
+        fix.inner = Box::new(fix.inner.fold(self)?);
+
+        for param in &mut self.params {
+            param.map(&mut ShallowVars::default());
+        }
+
+        Ok(fix.into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        Ok(Expression::Variable(var))
+    }
+
+    fn fold_call(&mut self, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+        Ok(call.into())
+    }
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+        self.params
+            .get(param.index())
+            .cloned()
+            .ok_or(SubstituteError::FreeParameter(param))
+    }
+}
diff --git a/src/chomp/error.rs b/src/chomp/error.rs
index d0a3cc8..ffcbdd0 100644
--- a/src/chomp/error.rs
+++ b/src/chomp/error.rs
@@ -13,7 +13,7 @@ use super::{
 };
 
 /// A type error when using a fix point variable.
-#[derive(Debug)]
+#[derive(Debug, Eq, PartialEq)]
 pub enum VariableError {
     /// Usage of a free variable.
     FreeVariable(Variable),
@@ -34,7 +34,7 @@ impl Display for VariableError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             Self::FreeVariable(var) => {
-                let start = var.name().span().start();
+                let start = var.name().span().unwrap_or_else(Span::call_site).start();
                 write!(
                     f,
                     "{}:{}: unbound variable '{}'",
@@ -44,7 +44,7 @@ impl Display for VariableError {
                 )
             }
             Self::GuardedVariable(var) => {
-                let start = var.name().span().start();
+                let start = var.name().span().unwrap_or_else(Span::call_site).start();
                 write!(
                     f,
                     "{}:{}: variable '{}' is guarded",
@@ -60,7 +60,7 @@ impl Display for VariableError {
 impl Error for VariableError {}
 
 /// A type error when concatenating two terms.
-#[derive(Debug)]
+#[derive(Debug, Eq, PartialEq)]
 pub enum CatError {
     /// The first term was unexpectedly nullable.
     FirstNullable(Cat),
@@ -159,7 +159,7 @@ impl Display for CatError {
 impl Error for CatError {}
 
 /// A type error when alternating two terms.
-#[derive(Debug)]
+#[derive(Debug, Eq, PartialEq)]
 pub enum AltError {
     /// Both terms are nullable.
     BothNullable(Alt),
@@ -271,7 +271,7 @@ impl Display for AltError {
 
 impl Error for AltError {}
 
-#[derive(Debug)]
+#[derive(Debug, Eq, PartialEq)]
 pub struct FixError(pub Fix, pub Type, pub Box<TypeError>);
 
 impl From<FixError> for syn::Error {
@@ -302,7 +302,7 @@ impl Display for FixError {
 
 impl Error for FixError {}
 
-#[derive(Debug)]
+#[derive(Debug, Eq, PartialEq)]
 pub enum TypeError {
     Cat(CatError),
     Alt(AltError),
@@ -352,7 +352,7 @@ impl Display for TypeError {
 
 impl Error for TypeError {}
 
-#[derive(Debug)]
+#[derive(Debug, Eq, PartialEq)]
 pub enum SubstituteError {
     FreeParameter(Parameter),
     WrongArgCount { call: Call, expected: usize },
@@ -362,7 +362,7 @@ impl Display for SubstituteError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             Self::FreeParameter(param) => {
-                let start = param.name().span().start();
+                let start = param.name().span().unwrap_or_else(Span::call_site).start();
                 write!(
                     f,
                     "{}:{}: undeclared variable `{}'",
diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
index bb31b6f..1e30738 100644
--- a/src/chomp/mod.rs
+++ b/src/chomp/mod.rs
@@ -1,3 +1,8 @@
+use std::{fmt, hash};
+
+use proc_macro2::{Ident, Span};
+use syn::ext::IdentExt;
+
 pub mod ast;
 pub mod check;
 pub mod context;
@@ -5,3 +10,77 @@ pub mod error;
 pub mod set;
 pub mod typed;
 pub mod visit;
+
+#[derive(Clone, Debug)]
+pub enum Name {
+    Spanned(Ident),
+    Spanless(String),
+}
+
+impl Name {
+    pub fn span(&self) -> Option<Span> {
+        match self {
+            Self::Spanned(i) => Some(i.span()),
+            Self::Spanless(_) => None,
+        }
+    }
+
+    pub fn as_ident(self, span: Span) -> Ident {
+        match self {
+            Self::Spanned(i) => i,
+            Self::Spanless(s) => Ident::new(&s, span),
+        }
+    }
+}
+
+impl PartialEq for Name {
+    fn eq(&self, other: &Self) -> bool {
+        match (self, other) {
+            (Self::Spanned(me), Self::Spanned(them)) => me == them,
+            (Self::Spanned(me), Self::Spanless(them)) => me.unraw() == them,
+            (Self::Spanless(me), Self::Spanned(them)) => them.unraw() == me,
+            (Self::Spanless(me), Self::Spanless(them)) => me == them,
+        }
+    }
+}
+
+impl<T: AsRef<str>> PartialEq<T> for Name {
+    fn eq(&self, other: &T) -> bool {
+        match self {
+            Name::Spanned(me) => me.unraw() == other,
+            Name::Spanless(me) => me == other.as_ref(),
+        }
+    }
+}
+
+impl Eq for Name {}
+
+impl hash::Hash for Name {
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        match self {
+            Self::Spanned(i) => i.unraw().to_string().hash(state),
+            Self::Spanless(s) => s.hash(state),
+        }
+    }
+}
+
+impl fmt::Display for Name {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Name::Spanned(i) => i.fmt(f),
+            Name::Spanless(s) => s.fmt(f),
+        }
+    }
+}
+
+impl From<Ident> for Name {
+    fn from(ident: Ident) -> Self {
+        Self::Spanned(ident)
+    }
+}
+
+impl From<String> for Name {
+    fn from(string: String) -> Self {
+        Self::Spanless(string)
+    }
+}
diff --git a/src/chomp/typed.rs b/src/chomp/typed.rs
index 69108ae..ab6cbc8 100644
--- a/src/chomp/typed.rs
+++ b/src/chomp/typed.rs
@@ -1,11 +1,12 @@
 use std::hash::{Hash, Hasher};
 
 use proc_macro2::Span;
-use syn::{Ident, LitStr, Token};
+use syn::{Ident, Token};
 
 use super::{
     ast,
     set::{FirstSet, FlastSet},
+    Name,
 };
 
 #[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
@@ -71,7 +72,7 @@ impl Type {
 
 #[derive(Debug, Eq, Hash, PartialEq)]
 pub struct Epsilon {
-    inner: Token![_],
+    inner: Option<Token![_]>,
     ty: Type,
 }
 
@@ -86,16 +87,16 @@ impl From<ast::Epsilon> for Epsilon {
 
 #[derive(Debug, Eq, Hash, PartialEq)]
 pub struct Literal {
-    inner: LitStr,
+    inner: ast::Literal,
     ty: Type,
 }
 
 impl Literal {
-    pub fn inner(&self) -> &LitStr {
+    pub fn inner(&self) -> &ast::Literal {
         &self.inner
     }
 
-    pub fn span(&self) -> Span {
+    pub fn span(&self) -> Option<Span> {
         self.inner.span()
     }
 }
@@ -107,6 +108,12 @@ impl From<ast::Literal> for Literal {
     }
 }
 
+impl From<Literal> for ast::Literal {
+    fn from(lit: Literal) -> Self {
+        lit.inner
+    }
+}
+
 #[derive(Debug, Eq, Hash, PartialEq)]
 pub struct Cat {
     fst: Box<TypedExpression>,
@@ -165,14 +172,14 @@ impl Alt {
 
 #[derive(Debug)]
 pub struct Fix {
-    arg: Ident,
+    arg: Name,
     inner: Box<TypedExpression>,
     span: Option<Span>,
     ty: Type,
 }
 
 impl Fix {
-    pub(crate) fn new(arg: Ident, inner: TypedExpression, span: Option<Span>, ty: Type) -> Self {
+    pub(crate) fn new(arg: Name, inner: TypedExpression, span: Option<Span>, ty: Type) -> Self {
         Self {
             arg,
             inner: Box::new(inner),
@@ -181,7 +188,7 @@ impl Fix {
         }
     }
 
-    pub fn unwrap(self) -> (Ident, TypedExpression, Option<Span>) {
+    pub fn unwrap(self) -> (Name, TypedExpression, Option<Span>) {
         (self.arg, *self.inner, self.span)
     }
 }
@@ -204,22 +211,17 @@ impl Hash for Fix {
 
 #[derive(Debug, Eq, Hash, PartialEq)]
 pub struct Variable {
-    ident: Ident,
-    index: usize,
+    inner: ast::Variable,
     ty: Type,
 }
 
 impl Variable {
-    pub(crate) fn new(var: ast::Variable, ty: Type) -> Self {
-        Self {
-            ident: var.name,
-            index: var.index,
-            ty,
-        }
+    pub(crate) fn new(inner: ast::Variable, ty: Type) -> Self {
+        Self { inner, ty }
     }
 
     pub fn index(&self) -> usize {
-        self.index
+        self.inner.index
     }
 }
 
diff --git a/src/lower/rust.rs b/src/lower/rust.rs
index fab040b..74deb73 100644
--- a/src/lower/rust.rs
+++ b/src/lower/rust.rs
@@ -1,9 +1,12 @@
 use std::collections::{BTreeSet, HashMap};
 
-use proc_macro2::{TokenStream, TokenTree};
+use proc_macro2::{Span, TokenStream, TokenTree};
 use quote::{format_ident, quote};
 
-use crate::chomp::typed::{Alt, Cat, Epsilon, Fix, Literal, Typed, TypedExpression, Variable};
+use crate::chomp::{
+    ast,
+    typed::{Alt, Cat, Epsilon, Fix, Literal, Typed, TypedExpression, Variable},
+};
 
 use super::{Backend, GenerateCode};
 
@@ -54,7 +57,7 @@ impl Backend for RustBackend {
     }
 
     fn gen_literal(&mut self, lit: Literal) -> Self::Id {
-        let lit = lit.inner();
+        let lit: ast::Literal = lit.into();
         if let Some(&id) = self.lit_map.get(&lit.value()) {
             id
         } else {
@@ -64,6 +67,7 @@ impl Backend for RustBackend {
                 r#"The literal string `"{}"`."#,
                 lit.value().escape_debug().collect::<String>()
             );
+            let lit = lit.as_litstr(Span::call_site());
             let tokens = quote! {
                 #[doc=#doc_name]
                 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
@@ -169,10 +173,10 @@ impl Backend for RustBackend {
                 quote! {
                     impl Parse for #name {
                         fn take<P: Parser + ?Sized>(input: &mut P) -> Result<Self, TakeError> {
-                            match input.peek().ok_or(TakeError::EndOfStream)? {
+                            match input.peek().ok_or_else(|| TakeError::EndOfStream(input.pos()))? {
                                 #(#iter_left)|* => input.take().map(Self::Left),
                                 #(#iter_right)|* => input.take().map(Self::Right),
-                                c => Err(TakeError::BadBranch(c, &[#(#iter_first),*]))
+                                c => Err(TakeError::BadBranch(input.pos(), c, &[#(#iter_first),*]))
                             }
                         }
                     }
diff --git a/src/main.rs b/src/main.rs
index 418f99f..a255590 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -7,7 +7,7 @@ use std::{
 
 use chomp::{
     chomp::{
-        check::{InlineCall, TypeCheck},
+        check::{InlineCalls, TypeCheck},
         context::Context,
         visit::Visitable,
     },
@@ -35,7 +35,7 @@ fn main() {
         .and_then(|(funs, goal)| {
             funs.into_iter()
                 .try_rfold(goal, |goal, function| {
-                    goal.fold(&mut InlineCall::new(function))
+                    goal.fold(&mut InlineCalls::new(function))
                 })
                 .map_err(|e| Box::new(e) as Box<dyn Error>)
         })
diff --git a/src/nibble/convert.rs b/src/nibble/convert.rs
index 3e47208..1a175a0 100644
--- a/src/nibble/convert.rs
+++ b/src/nibble/convert.rs
@@ -71,8 +71,8 @@ impl Convert for Ident {
         let span = self.span();
 
         match context.lookup(&self)? {
-            Binding::Variable(index) => Some(ast::Variable::new(self, index).into()),
-            Binding::Parameter(index) => Some(ast::Parameter::new(self, index).into()),
+            Binding::Variable(index) => Some(ast::Variable::new(self.into(), index).into()),
+            Binding::Parameter(index) => Some(ast::Parameter::new(self.into(), index).into()),
             Binding::Global => Some(ast::Call::new(self, Vec::new(), Some(span)).into()),
         }
     }
@@ -95,7 +95,7 @@ impl Convert for Fix {
         let span = self.span();
         let expr = self.expr;
         let inner = context.with_variable(&self.arg, |context| expr.convert(context))?;
-        Some(ast::Fix::new(self.arg, inner, span).into())
+        Some(ast::Fix::new(self.arg.into(), inner, span).into())
     }
 }
 
@@ -108,9 +108,9 @@ impl Convert for ParenExpression {
 impl Convert for Term {
     fn convert(self, context: &mut Context) -> Option<ast::Expression> {
         match self {
-            Self::Epsilon(e) => Some(e.into()),
+            Self::Epsilon(e) => Some(Some(e).into()),
             Self::Ident(i) => i.convert(context),
-            Self::Literal(l) => Some(l.into()),
+            Self::Literal(l) => Some(ast::Literal::from(l).into()),
             Self::Call(c) => c.convert(context),
             Self::Fix(f) => f.convert(context),
             Self::Parens(p) => p.convert(context),