Add labelled expressions.

Restructure project (again).

Convert `Cat` and `Alt` from binary to n+2-ary.

21 files changed, 1390 insertions, 1903 deletions

diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs
new file mode 100644
index 0000000..d2c49cd
--- /dev/null
+++ b/src/chomp/ast/error.rs
@@ -0,0 +1,27 @@
+use std::{error::Error, fmt::{self, Display}};
+
+use proc_macro2::Span;
+
+use crate::chomp::Name;
+
+use super::{Call, Parameter};
+
+#[derive(Debug)]
+pub enum SubstituteError {
+    FreeParameter { param: Parameter, span: Option<Span>, name: Option<Name> },
+    WrongArgCount { call: Call, expected: usize, span: Option<Span> },
+}
+
+impl From<SubstituteError> for syn::Error {
+    fn from(e: SubstituteError) -> Self {
+        todo!()
+    }
+}
+
+impl Display for SubstituteError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        todo!()
+    }
+}
+
+impl Error for SubstituteError {}
diff --git a/src/chomp/ast.rs b/src/chomp/ast/mod.rs
index 76d75ae..110e5c0 100644
--- a/src/chomp/ast.rs
+++ b/src/chomp/ast/mod.rs
@@ -1,127 +1,46 @@
-use std::{
-    fmt::{self, Display},
-    hash,
-};
+use std::fmt::{self, Display};
 
 use proc_macro2::Span;
-use syn::{Ident, LitStr, Token};
+use syn::Token;
 
 use super::Name;
 
-pub type Epsilon = Option<Token![_]>;
+pub mod error;
+pub mod substitute;
 
-#[derive(Clone, Debug)]
-pub enum Literal {
-    Spanned(LitStr),
-    Spanless(String),
-}
+#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
+pub struct Epsilon;
 
-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)
-    }
-}
+pub type Literal = String;
 
 #[derive(Clone, Debug)]
 pub struct Cat {
-    pub fst: Box<Expression>,
+    pub first: Box<NamedExpression>,
     pub punct: Option<Token![.]>,
-    pub snd: Box<Expression>,
-}
-
-impl Cat {
-    pub fn new(fst: Expression, punct: Option<Token![.]>, snd: Expression) -> Self {
-        Self {
-            fst: Box::new(fst),
-            punct,
-            snd: Box::new(snd),
-        }
-    }
-
-    pub fn first(&self) -> &Expression {
-        &self.fst
-    }
-
-    pub fn first_mut(&mut self) -> &mut Expression {
-        &mut self.fst
-    }
-
-    pub fn punct(&self) -> Option<Token![.]> {
-        self.punct
-    }
-
-    pub fn second(&self) -> &Expression {
-        &self.snd
-    }
-
-    pub fn second_mut(&mut self) -> &mut Expression {
-        &mut self.snd
-    }
+    pub second: Box<NamedExpression>,
+    pub rest: Vec<(Option<Token![.]>, NamedExpression)>,
 }
 
 impl Display for Cat {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "({}.{})", self.fst, self.snd)
+        write!(f, "({} . {}", self.first, self.second)?;
+        for (_, other) in &self.rest {
+            write!(f, " . {}", other)?;
+        }
+        write!(f, ")")
     }
 }
 
 impl PartialEq for Cat {
     fn eq(&self, other: &Self) -> bool {
-        self.first() == other.first() && self.second() == other.second()
+        self.first == other.first
+            && self.second == other.second
+            && self.rest.len() == other.rest.len()
+            && self
+                .rest
+                .iter()
+                .zip(other.rest.iter())
+                .all(|((_, me), (_, them))| me == them)
     }
 }
 
@@ -129,50 +48,32 @@ impl Eq for Cat {}
 
 #[derive(Clone, Debug)]
 pub struct Alt {
-    pub left: Box<Expression>,
+    pub first: Box<NamedExpression>,
     pub punct: Option<Token![|]>,
-    pub right: Box<Expression>,
-}
-
-impl Alt {
-    pub fn new(left: Expression, punct: Option<Token![|]>, right: Expression) -> Self {
-        Self {
-            left: Box::new(left),
-            punct,
-            right: Box::new(right),
-        }
-    }
-
-    pub fn left(&self) -> &Expression {
-        &self.left
-    }
-
-    pub fn left_mut(&mut self) -> &mut Expression {
-        &mut self.left
-    }
-
-    pub fn punct(&self) -> Option<Token![|]> {
-        self.punct
-    }
-
-    pub fn right(&self) -> &Expression {
-        &self.right
-    }
-
-    pub fn right_mut(&mut self) -> &mut Expression {
-        &mut self.right
-    }
+    pub second: Box<NamedExpression>,
+    pub rest: Vec<(Option<Token![|]>, NamedExpression)>
 }
 
 impl Display for Alt {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "({}|{})", self.left, self.right)
+        write!(f, "({} | {}", self.first, self.second)?;
+        for (_, other) in &self.rest {
+            write!(f, " | {}", other)?;
+        }
+        write!(f, ")")
     }
 }
 
 impl PartialEq for Alt {
     fn eq(&self, other: &Self) -> bool {
-        self.left() == other.left() && self.right() == other.right()
+        self.first == other.first
+            && self.second == other.second
+            && self.rest.len() == other.rest.len()
+            && self
+            .rest
+            .iter()
+            .zip(other.rest.iter())
+            .all(|((_, me), (_, them))| me == them)
     }
 }
 
@@ -180,46 +81,22 @@ impl Eq for Alt {}
 
 #[derive(Clone, Debug)]
 pub struct Fix {
-    pub arg: Name,
-    pub inner: Box<Expression>,
-    pub span: Option<Span>,
-}
-
-impl Fix {
-    pub fn new(arg: Name, inner: Expression, span: Option<Span>) -> Self {
-        Self {
-            arg,
-            inner: Box::new(inner),
-            span,
-        }
-    }
-
-    pub fn arg(&self) -> &Name {
-        &self.arg
-    }
-
-    pub fn inner(&self) -> &Expression {
-        &self.inner
-    }
-
-    pub fn inner_mut(&mut self) -> &mut Expression {
-        &mut self.inner
-    }
-
-    pub fn span(&self) -> Option<Span> {
-        self.span
-    }
+    pub arg: Option<Name>,
+    pub inner: Box<NamedExpression>,
 }
 
 impl Display for Fix {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "[{}]({})", self.arg, self.inner)
+        match &self.arg {
+            Some(arg) => write!(f, "[{}]({})", arg, self.inner),
+            None => write!(f, "[]({})", self.inner),
+        }
     }
 }
 
 impl PartialEq for Fix {
     fn eq(&self, other: &Self) -> bool {
-        self.inner() == other.inner()
+        self.inner == other.inner
     }
 }
 
@@ -227,92 +104,31 @@ impl Eq for Fix {}
 
 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
 pub struct Variable {
-    pub name: Name,
     pub index: usize,
 }
 
-impl Variable {
-    pub fn new(name: Name, index: usize) -> Self {
-        Self { name, index }
-    }
-
-    pub fn name(&self) -> &Name {
-        &self.name
-    }
-
-    pub fn index(&self) -> usize {
-        self.index
-    }
-
-    pub fn index_mut(&mut self) -> &mut usize {
-        &mut self.index
-    }
-}
-
 impl Display for Variable {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.name.fmt(f)
+        write!(f, "'{}", self.index)
     }
 }
 
 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
 pub struct Parameter {
-    pub name: Name,
     pub index: usize,
 }
 
-impl Parameter {
-    pub const fn new(name: Name, index: usize) -> Self {
-        Self { name, index }
-    }
-
-    pub fn name(&self) -> &Name {
-        &self.name
-    }
-
-    pub fn index(&self) -> usize {
-        self.index
-    }
-
-    pub fn index_mut(&mut self) -> &mut usize {
-        &mut self.index
-    }
-}
-
 impl Display for Parameter {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "{}", self.name)
+        write!(f, "<{}>", self.index)
     }
 }
 
 /// A macro invocation.
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, Eq, PartialEq)]
 pub struct Call {
     pub name: Name,
-    pub args: Vec<Expression>,
-    pub span: Option<Span>,
-}
-
-impl Call {
-    pub fn new(name: Name, args: Vec<Expression>, span: Option<Span>) -> Self {
-        Self { name, args, span }
-    }
-
-    pub fn name(&self) -> &Name {
-        &self.name
-    }
-
-    pub fn args(&self) -> &[Expression] {
-        &self.args
-    }
-
-    pub fn args_mut(&mut self) -> &mut [Expression] {
-        &mut self.args
-    }
-
-    pub fn span(&self) -> Option<Span> {
-        self.span
-    }
+    pub args: Vec<NamedExpression>,
 }
 
 impl Display for Call {
@@ -335,14 +151,6 @@ 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.
@@ -486,20 +294,33 @@ impl From<Call> for Expression {
 }
 
 #[derive(Clone, Debug)]
-pub struct Function {
-    pub name: Name,
-    pub params: usize,
+pub struct NamedExpression {
+    pub name: Option<Name>,
     pub expr: Expression,
     pub span: Option<Span>,
 }
 
-impl Function {
-    pub const fn new(name: Name, params: usize, expr: Expression, span: Option<Span>) -> Self {
-        Self {
-            name,
-            params,
-            expr,
-            span,
+impl Display for NamedExpression {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match &self.name {
+            Some(name) => write!(f, "({} : {})", self.expr, name),
+            None => self.expr.fmt(f),
         }
     }
 }
+
+impl PartialEq for NamedExpression {
+    fn eq(&self, other: &Self) -> bool {
+        self.expr == other.expr
+    }
+}
+
+impl Eq for NamedExpression {}
+
+#[derive(Clone, Debug)]
+pub struct Function {
+    pub name: Name,
+    pub params: Vec<Option<Name>>,
+    pub expr: NamedExpression,
+    pub span: Option<Span>,
+}
diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
new file mode 100644
index 0000000..1a622e1
--- /dev/null
+++ b/src/chomp/ast/substitute.rs
@@ -0,0 +1,439 @@
+use proc_macro2::Span;
+
+use crate::chomp::{
+    visit::{Folder, Mapper, Visitable},
+    Name,
+};
+
+use super::{
+    error::SubstituteError, Alt, Call, Cat, Epsilon, Fix, Function, Literal, NamedExpression,
+    Parameter, Variable,
+};
+
+#[derive(Clone, Copy, Debug, Default)]
+pub struct DeepenVars {
+    pub depth: usize,
+}
+
+impl Mapper for DeepenVars {
+    type Out = ();
+
+    fn map_epsilon(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        _eps: &mut Epsilon,
+    ) -> Self::Out {
+    }
+
+    fn map_literal(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        _lit: &mut Literal,
+    ) -> Self::Out {
+    }
+
+    fn map_cat(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        cat: &mut Cat,
+    ) -> Self::Out {
+        cat.first.map(self);
+        cat.second.map(self);
+
+        for (_, term) in &mut cat.rest {
+            term.map(self);
+        }
+    }
+
+    fn map_alt(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        alt: &mut Alt,
+    ) -> Self::Out {
+        alt.first.map(self);
+        alt.second.map(self);
+
+        for (_, term) in &mut alt.rest {
+            term.map(self);
+        }
+    }
+
+    fn map_fix(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        fix: &mut Fix,
+    ) -> Self::Out {
+        self.depth += 1;
+        fix.inner.map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        var: &mut Variable,
+    ) -> Self::Out {
+        if var.index >= self.depth {
+            var.index += 1;
+        }
+    }
+
+    fn map_parameter(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        _param: &mut Parameter,
+    ) -> Self::Out {
+    }
+
+    fn map_call(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        call: &mut Call,
+    ) -> Self::Out {
+        for arg in &mut call.args {
+            arg.map(self)
+        }
+    }
+}
+
+#[derive(Clone, Copy, Debug, Default)]
+pub struct ShallowVars {
+    pub depth: usize,
+}
+
+impl Mapper for ShallowVars {
+    type Out = ();
+
+    fn map_epsilon(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        _eps: &mut Epsilon,
+    ) -> Self::Out {
+    }
+
+    fn map_literal(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        _lit: &mut Literal,
+    ) -> Self::Out {
+    }
+
+    fn map_cat(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        cat: &mut Cat,
+    ) -> Self::Out {
+        cat.first.map(self);
+        cat.second.map(self);
+
+        for (_, term) in &mut cat.rest {
+            term.map(self);
+        }
+    }
+
+    fn map_alt(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        alt: &mut Alt,
+    ) -> Self::Out {
+        alt.first.map(self);
+        alt.second.map(self);
+
+        for (_, term) in &mut alt.rest {
+            term.map(self);
+        }
+    }
+
+    fn map_fix(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        fix: &mut Fix,
+    ) -> Self::Out {
+        self.depth += 1;
+        fix.inner.map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        var: &mut Variable,
+    ) -> Self::Out {
+        if var.index >= self.depth {
+            var.index -= 1;
+        }
+    }
+
+    fn map_parameter(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        _param: &mut Parameter,
+    ) -> Self::Out {
+    }
+
+    fn map_call(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Option<Span>,
+        call: &mut Call,
+    ) -> Self::Out {
+        for arg in &mut call.args {
+            arg.map(self)
+        }
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct SubstituteParams {
+    pub params: Vec<NamedExpression>,
+}
+
+impl Folder for SubstituteParams {
+    type Out = Result<NamedExpression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: eps.into(),
+            span,
+        })
+    }
+
+    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: lit.into(),
+            span,
+        })
+    }
+
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
+        cat.first = Box::new(cat.first.fold(self)?);
+        cat.second = Box::new(cat.second.fold(self)?);
+        cat.rest = cat
+            .rest
+            .into_iter()
+            .map(|(p, term)| Ok((p, term.fold(self)?)))
+            .collect::<Result<_, _>>()?;
+        Ok(NamedExpression {
+            name,
+            expr: cat.into(),
+            span,
+        })
+    }
+
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
+        alt.first = Box::new(alt.first.fold(self)?);
+        alt.second = Box::new(alt.second.fold(self)?);
+        alt.rest = alt
+            .rest
+            .into_iter()
+            .map(|(p, term)| Ok((p, term.fold(self)?)))
+            .collect::<Result<_, _>>()?;
+        Ok(NamedExpression {
+            name,
+            expr: alt.into(),
+            span,
+        })
+    }
+
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, 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(NamedExpression {
+            name,
+            expr: fix.into(),
+            span,
+        })
+    }
+
+    fn fold_variable(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        var: Variable,
+    ) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: var.into(),
+            span,
+        })
+    }
+
+    fn fold_parameter(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        param: Parameter,
+    ) -> Self::Out {
+        let mut expr = self
+            .params
+            .get(param.index)
+            .cloned()
+            .ok_or_else(|| SubstituteError::FreeParameter { param, span, name: name.clone() })?;
+        expr.name = expr.name.or(name);
+        expr.span = expr.span.or(span);
+        Ok(expr)
+    }
+
+    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+        Ok(NamedExpression {
+            name,
+            expr: call.into(),
+            span,
+        })
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct InlineCalls {
+    pub function: Function,
+}
+
+impl Folder for InlineCalls {
+    type Out = Result<NamedExpression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: eps.into(),
+            span,
+        })
+    }
+
+    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: lit.into(),
+            span,
+        })
+    }
+
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
+        cat.first = Box::new(cat.first.fold(self)?);
+        cat.second = Box::new(cat.second.fold(self)?);
+        cat.rest = cat
+            .rest
+            .into_iter()
+            .map(|(punct, term)| Ok((punct, term.fold(self)?)))
+            .collect::<Result<_, _>>()?;
+
+        Ok(NamedExpression {
+            name,
+            expr: cat.into(),
+            span,
+        })
+    }
+
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
+        alt.first = Box::new(alt.first.fold(self)?);
+        alt.second = Box::new(alt.second.fold(self)?);
+        alt.rest = alt
+            .rest
+            .into_iter()
+            .map(|(punct, term)| Ok((punct, term.fold(self)?)))
+            .collect::<Result<_, _>>()?;
+
+        Ok(NamedExpression {
+            name,
+            expr: alt.into(),
+            span,
+        })
+    }
+
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
+        fix.inner = Box::new(fix.inner.fold(self)?);
+
+        Ok(NamedExpression {
+            name,
+            expr: fix.into(),
+            span,
+        })
+    }
+
+    fn fold_variable(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        var: Variable,
+    ) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: var.into(),
+            span,
+        })
+    }
+
+    fn fold_parameter(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        param: Parameter,
+    ) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: param.into(),
+            span,
+        })
+    }
+
+    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, 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(NamedExpression {
+                name,
+                expr: call.into(),
+                span,
+            })
+        } else if call.args.len() != self.function.params.len() {
+            Err(SubstituteError::WrongArgCount {
+                call,
+                expected: self.function.params.len(),
+                span,
+            })
+        } else {
+            let mut expr = self
+                .function
+                .expr
+                .clone()
+                .fold(&mut SubstituteParams { params: call.args })?;
+            expr.name = Some(expr.name.or(name).unwrap_or(call.name));
+            expr.span = expr.span.or(span);
+
+            Ok(expr)
+        }
+    }
+}
diff --git a/src/chomp/check/check.rs b/src/chomp/check/check.rs
deleted file mode 100644
index 8729565..0000000
--- a/src/chomp/check/check.rs
+++ /dev/null
@@ -1,81 +0,0 @@
-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
deleted file mode 100644
index 07ef7ac..0000000
--- a/src/chomp/check/closed.rs
+++ /dev/null
@@ -1,50 +0,0 @@
-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
deleted file mode 100644
index b9f606d..0000000
--- a/src/chomp/check/deepen.rs
+++ /dev/null
@@ -1,47 +0,0 @@
-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
deleted file mode 100644
index 941ddba..0000000
--- a/src/chomp/check/infer.rs
+++ /dev/null
@@ -1,92 +0,0 @@
-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
deleted file mode 100644
index da501f1..0000000
--- a/src/chomp/check/inline.rs
+++ /dev/null
@@ -1,349 +0,0 @@
-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 crate::chomp::Name;
-
-    use super::*;
-
-    fn opt() -> Function {
-        Function::new(
-            Name::Spanless("opt".to_string()),
-            1,
-            Expression::Alt(Alt::new(
-                Expression::Epsilon(None),
-                None,
-                Parameter::new(Name::Spanless("x".to_string()), 0).into(),
-            )),
-            None,
-        )
-    }
-
-    #[test]
-    fn test_inline_absent() {
-        let expr = Epsilon::default();
-        let inlined = expr.fold(&mut InlineCalls::new(opt()));
-        assert_eq!(inlined, Ok(Epsilon::default().into()))
-    }
-
-    #[test]
-    fn test_inline_in_fix() {
-        let expr = Fix::new(
-            Name::Spanless("rec".to_string()),
-            Call::new(
-                Name::Spanless("opt".to_string()),
-                vec![Variable::new(Name::Spanless("rec".to_string()), 0).into()],
-                None,
-            )
-            .into(),
-            None,
-        );
-        let inlined = expr.fold(&mut InlineCalls::new(opt()));
-        assert_eq!(
-            inlined,
-            Ok(Fix::new(
-                Name::Spanless("rec".to_string()),
-                Alt::new(
-                    Epsilon::default().into(),
-                    None,
-                    Variable::new(Name::Spanless("rec".to_string()), 0).into()
-                )
-                .into(),
-                None
-            )
-            .into())
-        )
-    }
-
-    #[test]
-    fn test_inline_deepens_vars() {
-        let function = Function::new(
-            Name::Spanless("plus".into()),
-            1,
-            Fix::new(
-                Name::Spanless("rec".to_string()),
-                Cat::new(
-                    Parameter::new(Name::Spanless("x".to_string()), 0).into(),
-                    None,
-                    Variable::new(Name::Spanless("rec".to_string()), 0).into(),
-                )
-                .into(),
-                None,
-            )
-            .into(),
-            None,
-        );
-        let expr = Fix::new(
-            Name::Spanless("var".to_string()),
-            Call::new(
-                Name::Spanless("plus".into()),
-                vec![Variable::new(Name::Spanless("var".to_string()), 0).into()],
-                None,
-            )
-            .into(),
-            None,
-        );
-        let inlined = expr.fold(&mut InlineCalls::new(function));
-        assert_eq!(
-            inlined,
-            Ok(Fix::new(
-                Name::Spanless("var".to_string()),
-                Fix::new(
-                    Name::Spanless("rec".to_string()),
-                    Cat::new(
-                        Variable::new(Name::Spanless("var".to_string()), 1).into(),
-                        None,
-                        Variable::new(Name::Spanless("rec".to_string()), 0).into(),
-                    )
-                    .into(),
-                    None,
-                )
-                .into(),
-                None
-            )
-            .into())
-        )
-    }
-
-    #[test]
-    fn test_inline_resets_vars() {
-        let function = Function::new(
-            Name::Spanless("plus".into()),
-            1,
-            Cat::new(
-                Fix::new(
-                    Name::Spanless("rec".to_string()),
-                    Epsilon::default().into(),
-                    None,
-                )
-                .into(),
-                None,
-                Parameter::new(Name::Spanless("x".to_string()), 0).into(),
-            )
-            .into(),
-            None,
-        );
-        let expr = Fix::new(
-            Name::Spanless("var".to_string()),
-            Call::new(
-                Name::Spanless("plus".into()),
-                vec![Variable::new(Name::Spanless("var".to_string()), 0).into()],
-                None,
-            )
-            .into(),
-            None,
-        );
-        let inlined = expr.fold(&mut InlineCalls::new(function));
-        assert_eq!(
-            inlined,
-            Ok(Fix::new(
-                Name::Spanless("var".to_string()),
-                Cat::new(
-                    Fix::new(
-                        Name::Spanless("rec".to_string()),
-                        Epsilon::default().into(),
-                        None,
-                    )
-                    .into(),
-                    None,
-                    Variable::new(Name::Spanless("var".to_string()), 0).into(),
-                )
-                .into(),
-                None
-            )
-            .into())
-        )
-    }
-
-    #[test]
-    fn test_inline_double_subst() {
-        let expr = Call::new(
-            Name::Spanless("opt".to_string()),
-            vec![Call::new(
-                Name::Spanless("opt".to_string()),
-                vec![Literal::Spanless("x".to_string()).into()],
-                None,
-            )
-            .into()],
-            None,
-        );
-        let inlined = expr.fold(&mut InlineCalls::new(opt()));
-        assert_eq!(
-            inlined,
-            Ok(Alt::new(
-                Epsilon::default().into(),
-                None,
-                Alt::new(
-                    Epsilon::default().into(),
-                    None,
-                    Literal::Spanless("x".to_string()).into()
-                )
-                .into()
-            )
-            .into())
-        )
-    }
-
-    #[test]
-    fn test_inline_call_args() {
-        let expr = Fix::new(
-            Name::Spanless("rec".to_string()),
-            Cat::new(
-                Literal::Spanless("a".to_string()).into(),
-                None,
-                Call::new(
-                    Name::Spanless("opt".to_string()),
-                    vec![Cat::new(
-                        Cat::new(
-                            Literal::Spanless("a".to_string()).into(),
-                            None,
-                            Fix::new(
-                                Name::Spanless("star".to_string()),
-                                Call::new(
-                                    Name::Spanless("opt".to_string()),
-                                    vec![Cat::new(
-                                        Literal::Spanless(" ".to_string()).into(),
-                                        None,
-                                        Variable::new(Name::Spanless("star".to_string()), 0).into(),
-                                    )
-                                    .into()],
-                                    None,
-                                )
-                                .into(),
-                                None,
-                            )
-                            .into(),
-                        )
-                        .into(),
-                        None,
-                        Variable::new(Name::Spanless("rec".to_string()), 0).into(),
-                    )
-                    .into()],
-                    None,
-                )
-                .into(),
-            )
-            .into(),
-            None,
-        );
-        let inlined = expr.fold(&mut InlineCalls::new(opt()));
-        assert_eq!(inlined,
-        Ok(Fix::new(
-            Name::Spanless("rec".to_string()),
-            Cat::new(
-                Literal::Spanless("a".to_string()).into(),
-                None,
-                Alt::new(
-                    Epsilon::default().into(),
-                    None,
-                    Cat::new(
-                        Cat::new(
-                            Literal::Spanless("a".to_string()).into(),
-                            None,
-                            Fix::new(
-                                Name::Spanless("star".to_string()),
-                                Alt::new(
-                                    Epsilon::default().into(),
-                                    None,
-                                    Cat::new(
-                                        Literal::Spanless(" ".to_string()).into(),
-                                        None,
-                                        Variable::new(Name::Spanless("star".to_string()), 0).into(),
-                                    )
-                                        .into()
-                                )
-                                .into(),
-                                None,
-                            )
-                            .into(),
-                        )
-                        .into(),
-                        None,
-                        Variable::new(Name::Spanless("rec".to_string()), 0).into(),
-                    )
-                    .into(),
-                )
-                .into(),
-            )
-            .into(),
-            None,
-        ).into()))
-    }
-}
diff --git a/src/chomp/check/mod.rs b/src/chomp/check/mod.rs
deleted file mode 100644
index c9aeda4..0000000
--- a/src/chomp/check/mod.rs
+++ /dev/null
@@ -1,17 +0,0 @@
-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
deleted file mode 100644
index e5cc1a1..0000000
--- a/src/chomp/check/shallow.rs
+++ /dev/null
@@ -1,47 +0,0 @@
-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
deleted file mode 100644
index 59c3811..0000000
--- a/src/chomp/check/spanning.rs
+++ /dev/null
@@ -1,59 +0,0 @@
-use proc_macro2::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
deleted file mode 100644
index 32595b1..0000000
--- a/src/chomp/check/substitute.rs
+++ /dev/null
@@ -1,77 +0,0 @@
-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
deleted file mode 100644
index e7e4660..0000000
--- a/src/chomp/error.rs
+++ /dev/null
@@ -1,402 +0,0 @@
-use std::{
-    error::Error,
-    fmt::{self, Display},
-};
-
-use proc_macro2::Span;
-
-use super::{
-    ast::{Alt, Call, Cat, Fix, Parameter, Variable},
-    check::Spanning,
-    typed::Type,
-    visit::Visitable,
-};
-
-/// A type error when using a fix point variable.
-#[derive(Debug, Eq, PartialEq)]
-pub enum VariableError {
-    /// Usage of a free variable.
-    FreeVariable(Variable),
-    /// Usage of a guarded variable.
-    GuardedVariable(Variable),
-}
-
-impl From<VariableError> for syn::Error {
-    fn from(other: VariableError) -> Self {
-        match other {
-            VariableError::FreeVariable(_) => todo!(),
-            VariableError::GuardedVariable(_) => todo!(),
-        }
-    }
-}
-
-impl Display for VariableError {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Self::FreeVariable(var) => {
-                let start = var.name().span().unwrap_or_else(Span::call_site).start();
-                write!(
-                    f,
-                    "{}:{}: unbound variable '{}'",
-                    start.line,
-                    start.column,
-                    var.name()
-                )
-            }
-            Self::GuardedVariable(var) => {
-                let start = var.name().span().unwrap_or_else(Span::call_site).start();
-                write!(
-                    f,
-                    "{}:{}: variable '{}' is guarded",
-                    start.line,
-                    start.column,
-                    var.name()
-                )
-            }
-        }
-    }
-}
-
-impl Error for VariableError {}
-
-/// A type error when concatenating two terms.
-#[derive(Debug, Eq, PartialEq)]
-pub enum CatError {
-    /// The first term was unexpectedly nullable.
-    FirstNullable(Cat),
-    /// The flast set of the first term intersects the first set of the second.
-    FirstFlastOverlap(Cat),
-}
-
-impl From<CatError> for syn::Error {
-    fn from(other: CatError) -> Self {
-        match other {
-            CatError::FirstNullable(cat) => {
-                let mut err = Self::new(
-                    cat.punct().map_or_else(Span::call_site, |p| p.span),
-                    "first item in sequence cannot accept the empty string",
-                );
-                err.combine(Self::new(
-                    cat.first()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "this can accept empty string",
-                ));
-                err
-            }
-            CatError::FirstFlastOverlap(cat) => {
-                let mut err = Self::new(
-                    cat.punct().map_or_else(Span::call_site, |p| p.span),
-                    "cannot decide whether to repeat first or start accepting second",
-                );
-                err.combine(Self::new(
-                    cat.first()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "a repetition of this",
-                ));
-                err.combine(Self::new(
-                    cat.second()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "collides with the start of this",
-                ));
-                err
-            }
-        }
-    }
-}
-
-impl Display for CatError {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Self::FirstNullable(cat) => {
-                let start = cat.punct().map_or_else(Span::call_site, |p| p.span).start();
-                let fst_start = cat
-                    .first()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                write!(
-                    f,
-                    "{}:{}: term `{}' ({}:{}) accepts the empty string",
-                    start.line,
-                    start.column,
-                    cat.first(),
-                    fst_start.line,
-                    fst_start.column
-                )
-            }
-            Self::FirstFlastOverlap(cat) => {
-                let start = cat.punct().map_or_else(Span::call_site, |p| p.span).start();
-                let fst_start = cat
-                    .first()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                let snd_start = cat
-                    .second()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                write!(
-                    f,
-                    "{}:{}: cannot decide whether to repeat `{}' ({}:{}) or start accepting `{}' ({}:{}).",
-                    start.line,
-                    start.column,
-                    cat.first(),
-                    fst_start.line,
-                    fst_start.column,
-                    cat.second(),
-                    snd_start.line,
-                    snd_start.column
-                )
-            }
-        }
-    }
-}
-
-impl Error for CatError {}
-
-/// A type error when alternating two terms.
-#[derive(Debug, Eq, PartialEq)]
-pub enum AltError {
-    /// Both terms are nullable.
-    BothNullable(Alt),
-    /// The first sets of the two terms intersect.
-    FirstOverlap(Alt),
-}
-
-impl From<AltError> for syn::Error {
-    fn from(other: AltError) -> Self {
-        match other {
-            AltError::BothNullable(alt) => {
-                let mut err = Self::new(
-                    alt.punct().map_or_else(Span::call_site, |p| p.span),
-                    "both branches accept the empty string",
-                );
-                err.combine(Self::new(
-                    alt.left()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "left branch accepts the empty string",
-                ));
-                err.combine(Self::new(
-                    alt.right()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "right branch accepts the empty string",
-                ));
-                err
-            }
-            AltError::FirstOverlap(alt) => {
-                let mut err = Self::new(
-                    alt.punct().map_or_else(Span::call_site, |p| p.span),
-                    "cannot decide whether to accept the left or right branch",
-                );
-                err.combine(Self::new(
-                    alt.left()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "left branch starts with a character",
-                ));
-                err.combine(Self::new(
-                    alt.right()
-                        .visit(&mut Spanning)
-                        .unwrap_or_else(Span::call_site),
-                    "right branch starts with the same character",
-                ));
-                err
-            }
-        }
-    }
-}
-
-impl Display for AltError {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Self::BothNullable(alt) => {
-                let start = alt.punct().map_or_else(Span::call_site, |p| p.span).start();
-                let left_start = alt
-                    .left()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                let right_start = alt
-                    .right()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                write!(
-                    f,
-                    "{}:{}: both `{}' ({}:{}) and `{}' ({}:{}) accept the empty string.",
-                    start.line,
-                    start.column,
-                    alt.left(),
-                    left_start.line,
-                    left_start.column,
-                    alt.right(),
-                    right_start.line,
-                    right_start.column,
-                )
-            }
-            Self::FirstOverlap(alt) => {
-                let start = alt.punct().map_or_else(Span::call_site, |p| p.span).start();
-                let left_start = alt
-                    .left()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                let right_start = alt
-                    .right()
-                    .visit(&mut Spanning)
-                    .unwrap_or_else(Span::call_site)
-                    .start();
-                write!(
-                    f,
-                    "{}:{}: cannot decide whether to accept `{}' ({}:{}) or `{}' ({}:{}).",
-                    start.line,
-                    start.column,
-                    alt.left(),
-                    left_start.line,
-                    left_start.column,
-                    alt.right(),
-                    right_start.line,
-                    right_start.column,
-                )
-            }
-        }
-    }
-}
-
-impl Error for AltError {}
-
-#[derive(Debug, Eq, PartialEq)]
-pub struct FixError(pub Fix, pub Type, pub Box<TypeError>);
-
-impl From<FixError> for syn::Error {
-    fn from(e: FixError) -> Self {
-        let mut error = Self::from(*e.2);
-        error.combine(Self::new(
-            e.0.span().unwrap_or_else(Span::call_site),
-            format!("assuming `{}' has type {:?}.", e.0.arg(), e.1),
-        ));
-        error
-    }
-}
-
-impl Display for FixError {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.2.fmt(f)?;
-        let start = self.0.span().unwrap_or_else(Span::call_site).start();
-        write!(
-            f,
-            "\n{}:{}: assuming `{}' has type {:?}.",
-            start.line,
-            start.column,
-            self.0.arg(),
-            self.1
-        )
-    }
-}
-
-impl Error for FixError {}
-
-#[derive(Debug, Eq, PartialEq)]
-pub enum TypeError {
-    Cat(CatError),
-    Alt(AltError),
-    Variable(VariableError),
-    Fix(FixError),
-}
-
-impl From<CatError> for TypeError {
-    fn from(other: CatError) -> Self {
-        Self::Cat(other)
-    }
-}
-
-impl From<AltError> for TypeError {
-    fn from(other: AltError) -> Self {
-        Self::Alt(other)
-    }
-}
-
-impl From<VariableError> for TypeError {
-    fn from(other: VariableError) -> Self {
-        Self::Variable(other)
-    }
-}
-
-impl From<TypeError> for syn::Error {
-    fn from(other: TypeError) -> Self {
-        match other {
-            TypeError::Cat(e) => e.into(),
-            TypeError::Alt(e) => e.into(),
-            TypeError::Variable(e) => e.into(),
-            TypeError::Fix(e) => e.into(),
-        }
-    }
-}
-
-impl Display for TypeError {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Self::Cat(e) => e.fmt(f),
-            Self::Alt(e) => e.fmt(f),
-            Self::Variable(e) => e.fmt(f),
-            Self::Fix(e) => e.fmt(f),
-        }
-    }
-}
-
-impl Error for TypeError {}
-
-#[derive(Debug, Eq, PartialEq)]
-pub enum SubstituteError {
-    FreeParameter(Parameter),
-    WrongArgCount { call: Call, expected: usize },
-}
-
-impl From<SubstituteError> for syn::Error {
-    fn from(e: SubstituteError) -> Self {
-        match e {
-            SubstituteError::FreeParameter(param) => {
-                Self::new(param.name().span().unwrap_or_else(Span::call_site), format!("undeclared variable `{}'", param.name()))
-            }
-            SubstituteError::WrongArgCount { call, expected } => {
-                Self::new(call.span().unwrap_or_else(Span::call_site), format!("wrong number of arguments. Expected {}, got {}", expected, call.args().len()))
-            }
-        }
-    }
-}
-
-impl Display for SubstituteError {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Self::FreeParameter(param) => {
-                let start = param.name().span().unwrap_or_else(Span::call_site).start();
-                write!(
-                    f,
-                    "{}:{}: undeclared variable `{}'",
-                    start.line,
-                    start.column,
-                    param.name()
-                )
-            }
-            SubstituteError::WrongArgCount { call, expected } => {
-                let start = call.span().unwrap_or_else(Span::call_site).start();
-                write!(
-                    f,
-                    "{}:{}: wrong number of arguments. Expected {}, got {}",
-                    start.line,
-                    start.column,
-                    expected,
-                    call.args().len()
-                )
-            }
-        }
-    }
-}
-
-impl Error for SubstituteError {}
diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
index 1e30738..79b4fac 100644
--- a/src/chomp/mod.rs
+++ b/src/chomp/mod.rs
@@ -1,12 +1,10 @@
 use std::{fmt, hash};
 
+use heck::{CamelCase, SnakeCase};
 use proc_macro2::{Ident, Span};
 use syn::ext::IdentExt;
 
 pub mod ast;
-pub mod check;
-pub mod context;
-pub mod error;
 pub mod set;
 pub mod typed;
 pub mod visit;
@@ -25,7 +23,7 @@ impl Name {
         }
     }
 
-    pub fn as_ident(self, span: Span) -> Ident {
+    pub fn into_ident(self, span: Span) -> Ident {
         match self {
             Self::Spanned(i) => i,
             Self::Spanless(s) => Ident::new(&s, span),
@@ -33,6 +31,36 @@ impl Name {
     }
 }
 
+impl CamelCase for Name {
+    fn to_camel_case(&self) -> Self::Owned {
+        match self {
+            Self::Spanned(ident) => {
+                let span = ident.span();
+                let name = ident.unraw().to_string();
+                Ident::new(&name.to_camel_case(), span).into()
+            }
+            Name::Spanless(name) => {
+                name.to_camel_case().into()
+            }
+        }
+    }
+}
+
+impl SnakeCase for Name {
+    fn to_snake_case(&self) -> Self::Owned {
+        match self {
+            Self::Spanned(ident) => {
+                let span = ident.span();
+                let name = ident.unraw().to_string();
+                Ident::new(&name.to_snake_case(), span).into()
+            }
+            Name::Spanless(name) => {
+                name.to_snake_case().into()
+            }
+        }
+    }
+}
+
 impl PartialEq for Name {
     fn eq(&self, other: &Self) -> bool {
         match (self, other) {
diff --git a/src/chomp/typed.rs b/src/chomp/typed.rs
deleted file mode 100644
index db07552..0000000
--- a/src/chomp/typed.rs
+++ /dev/null
@@ -1,323 +0,0 @@
-use std::hash::{Hash, Hasher};
-
-use proc_macro2::Span;
-use syn::Token;
-
-use super::{
-    ast,
-    set::{FirstSet, FlastSet},
-    Name,
-};
-
-#[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
-pub struct Type {
-    nullable: bool,
-    first_set: FirstSet,
-    flast_set: FlastSet,
-}
-
-impl Type {
-    pub const fn new(nullable: bool, first_set: FirstSet, flast_set: FlastSet) -> Self {
-        Self {
-            nullable,
-            first_set,
-            flast_set,
-        }
-    }
-
-    pub fn of_str(s: &str) -> Self {
-        Self {
-            nullable: s.is_empty(),
-            first_set: FirstSet::of_str(s),
-            flast_set: FlastSet::default(),
-        }
-    }
-
-    pub fn nullable(&self) -> bool {
-        self.nullable
-    }
-
-    pub fn first_set(&self) -> &FirstSet {
-        &self.first_set
-    }
-
-    pub fn flast_set(&self) -> &FlastSet {
-        &self.flast_set
-    }
-
-    pub fn cat(self, other: Self) -> Self {
-        Self {
-            nullable: self.nullable && other.nullable,
-            first_set: self.first_set.union(if self.nullable {
-                other.first_set.clone()
-            } else {
-                FirstSet::default()
-            }),
-            flast_set: other.flast_set.union(if other.nullable {
-                self.flast_set.union_first(other.first_set)
-            } else {
-                FlastSet::default()
-            }),
-        }
-    }
-
-    pub fn alt(self, other: Self) -> Self {
-        Self {
-            nullable: self.nullable || other.nullable,
-            first_set: self.first_set.union(other.first_set),
-            flast_set: self.flast_set.union(other.flast_set),
-        }
-    }
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub struct Epsilon {
-    inner: Option<Token![_]>,
-    ty: Type,
-}
-
-impl From<ast::Epsilon> for Epsilon {
-    fn from(inner: ast::Epsilon) -> Self {
-        Self {
-            inner,
-            ty: Type::new(true, FirstSet::default(), FlastSet::default()),
-        }
-    }
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub struct Literal {
-    inner: ast::Literal,
-    ty: Type,
-}
-
-impl Literal {
-    pub fn inner(&self) -> &ast::Literal {
-        &self.inner
-    }
-
-    pub fn span(&self) -> Option<Span> {
-        self.inner.span()
-    }
-}
-
-impl From<ast::Literal> for Literal {
-    fn from(inner: ast::Literal) -> Self {
-        let ty = Type::of_str(&inner.value());
-        Self { inner, ty }
-    }
-}
-
-impl From<Literal> for ast::Literal {
-    fn from(lit: Literal) -> Self {
-        lit.inner
-    }
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub struct Cat {
-    fst: Box<TypedExpression>,
-    punct: Option<Token![.]>,
-    snd: Box<TypedExpression>,
-    ty: Type,
-}
-
-impl Cat {
-    pub(crate) fn new(
-        fst: TypedExpression,
-        punct: Option<Token![.]>,
-        snd: TypedExpression,
-        ty: Type,
-    ) -> Self {
-        Self {
-            fst: Box::new(fst),
-            punct,
-            snd: Box::new(snd),
-            ty,
-        }
-    }
-
-    pub fn unwrap(self) -> (TypedExpression, Option<Token![.]>, TypedExpression) {
-        (*self.fst, self.punct, *self.snd)
-    }
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub struct Alt {
-    left: Box<TypedExpression>,
-    punct: Option<Token![|]>,
-    right: Box<TypedExpression>,
-    ty: Type,
-}
-
-impl Alt {
-    pub(crate) fn new(
-        left: TypedExpression,
-        punct: Option<Token![|]>,
-        right: TypedExpression,
-        ty: Type,
-    ) -> Self {
-        Self {
-            left: Box::new(left),
-            punct,
-            right: Box::new(right),
-            ty,
-        }
-    }
-
-    pub fn unwrap(self) -> (TypedExpression, Option<Token![|]>, TypedExpression) {
-        (*self.left, self.punct, *self.right)
-    }
-}
-
-#[derive(Debug)]
-pub struct Fix {
-    arg: Name,
-    inner: Box<TypedExpression>,
-    span: Option<Span>,
-    ty: Type,
-}
-
-impl Fix {
-    pub(crate) fn new(arg: Name, inner: TypedExpression, span: Option<Span>, ty: Type) -> Self {
-        Self {
-            arg,
-            inner: Box::new(inner),
-            span,
-            ty,
-        }
-    }
-
-    pub fn unwrap(self) -> (Name, TypedExpression, Option<Span>) {
-        (self.arg, *self.inner, self.span)
-    }
-}
-
-impl PartialEq for Fix {
-    fn eq(&self, other: &Self) -> bool {
-        self.arg == other.arg && self.inner == other.inner && self.ty == other.ty
-    }
-}
-
-impl Eq for Fix {}
-
-impl Hash for Fix {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        self.arg.hash(state);
-        self.inner.hash(state);
-        self.ty.hash(state);
-    }
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub struct Variable {
-    inner: ast::Variable,
-    ty: Type,
-}
-
-impl Variable {
-    pub(crate) fn new(inner: ast::Variable, ty: Type) -> Self {
-        Self { inner, ty }
-    }
-
-    pub fn index(&self) -> usize {
-        self.inner.index
-    }
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub(crate) enum RawTypedExpression {
-    Epsilon(Epsilon),
-    Literal(Literal),
-    Cat(Cat),
-    Alt(Alt),
-    Fix(Fix),
-    Variable(Variable),
-}
-
-#[derive(Debug, Eq, Hash, PartialEq)]
-pub struct TypedExpression {
-    pub(crate) inner: RawTypedExpression,
-}
-
-impl From<Epsilon> for TypedExpression {
-    fn from(eps: Epsilon) -> Self {
-        Self {
-            inner: RawTypedExpression::Epsilon(eps),
-        }
-    }
-}
-
-impl From<Literal> for TypedExpression {
-    fn from(lit: Literal) -> Self {
-        Self {
-            inner: RawTypedExpression::Literal(lit),
-        }
-    }
-}
-
-impl From<Cat> for TypedExpression {
-    fn from(cat: Cat) -> Self {
-        Self {
-            inner: RawTypedExpression::Cat(cat),
-        }
-    }
-}
-
-impl From<Alt> for TypedExpression {
-    fn from(alt: Alt) -> Self {
-        Self {
-            inner: RawTypedExpression::Alt(alt),
-        }
-    }
-}
-
-impl From<Fix> for TypedExpression {
-    fn from(fix: Fix) -> Self {
-        Self {
-            inner: RawTypedExpression::Fix(fix),
-        }
-    }
-}
-
-impl From<Variable> for TypedExpression {
-    fn from(var: Variable) -> Self {
-        Self {
-            inner: RawTypedExpression::Variable(var),
-        }
-    }
-}
-
-pub trait Typed {
-    fn get_type(&self) -> &Type;
-}
-
-macro_rules! leaf_typed {
-    ($ty:ty, $field:ident) => {
-        impl Typed for $ty {
-            fn get_type(&self) -> &Type {
-                &self.$field
-            }
-        }
-    };
-}
-
-leaf_typed!(Epsilon, ty);
-leaf_typed!(Literal, ty);
-leaf_typed!(Cat, ty);
-leaf_typed!(Alt, ty);
-leaf_typed!(Fix, ty);
-leaf_typed!(Variable, ty);
-
-impl Typed for TypedExpression {
-    fn get_type(&self) -> &Type {
-        match &self.inner {
-            RawTypedExpression::Epsilon(e) => e.get_type(),
-            RawTypedExpression::Literal(l) => l.get_type(),
-            RawTypedExpression::Cat(c) => c.get_type(),
-            RawTypedExpression::Alt(a) => a.get_type(),
-            RawTypedExpression::Fix(f) => f.get_type(),
-            RawTypedExpression::Variable(v) => v.get_type(),
-        }
-    }
-}
diff --git a/src/chomp/context.rs b/src/chomp/typed/context.rs
index 392023f..5c8d398 100644
--- a/src/chomp/context.rs
+++ b/src/chomp/typed/context.rs
@@ -1,4 +1,6 @@
-use super::{ast::Variable, error::VariableError, typed::Type};
+use crate::chomp::ast::Variable;
+
+use super::Type;
 
 #[derive(Debug, Default)]
 pub struct Context {
@@ -16,14 +18,12 @@ impl Context {
     }
 
     pub fn is_unguarded(&self, var: &Variable) -> Option<bool> {
-        if self.vars.len() <= var.index() {
+        if self.vars.len() <= var.index {
             None
         } else if self.unguard_points.is_empty() {
             Some(false)
         } else {
-            Some(
-                self.unguard_points[self.unguard_points.len() - 1] + var.index() >= self.vars.len(),
-            )
+            Some(self.unguard_points[self.unguard_points.len() - 1] + var.index >= self.vars.len())
         }
     }
 
@@ -34,11 +34,11 @@ impl Context {
         res
     }
 
-    pub fn get_variable_type(&self, var: &Variable) -> Result<&Type, VariableError> {
+    pub fn get_variable_type(&self, var: &Variable) -> Result<&Type, GetVariableError> {
         match self.is_unguarded(var) {
-            None => Err(VariableError::FreeVariable(var.clone())),
-            Some(false) => Err(VariableError::GuardedVariable(var.clone())),
-            Some(true) => Ok(&self.vars[self.vars.len() - var.index() - 1]),
+            None => Err(GetVariableError::FreeVariable),
+            Some(false) => Err(GetVariableError::GuardedVariable),
+            Some(true) => Ok(&self.vars[self.vars.len() - var.index - 1]),
         }
     }
 
@@ -49,3 +49,9 @@ impl Context {
         res
     }
 }
+
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub enum GetVariableError {
+    FreeVariable,
+    GuardedVariable,
+}
diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs
new file mode 100644
index 0000000..bb807fc
--- /dev/null
+++ b/src/chomp/typed/error.rs
@@ -0,0 +1,150 @@
+use std::{
+    error::Error,
+    fmt::{self, Display},
+};
+
+use proc_macro2::Span;
+
+use crate::chomp::{ast::Variable, Name};
+
+use super::{context::GetVariableError, TypedExpression};
+
+/// A type error when using a fix point variable.
+#[derive(Debug)]
+pub struct VariableError {
+    pub inner: GetVariableError,
+    pub var: Variable,
+    pub span: Option<Span>,
+    pub name: Option<Name>,
+}
+
+impl PartialEq for VariableError {
+    fn eq(&self, other: &Self) -> bool {
+        todo!()
+    }
+}
+
+impl Eq for VariableError {}
+
+impl From<VariableError> for syn::Error {
+    fn from(other: VariableError) -> Self {
+        todo!()
+    }
+}
+
+impl Display for VariableError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        todo!()
+    }
+}
+
+impl Error for VariableError {}
+
+/// A type error when concatenating two terms.
+#[derive(Debug)]
+pub enum CatError {
+    /// The first term was unexpectedly nullable.
+    FirstNullable(TypedExpression, Option<Span>),
+    /// The flast set of the first term intersects the first set of the second.
+    FirstFlastOverlap(Vec<TypedExpression>, Option<Span>, TypedExpression),
+}
+
+impl PartialEq for CatError {
+    fn eq(&self, other: &Self) -> bool {
+        todo!()
+    }
+}
+
+impl Eq for CatError {}
+
+impl From<CatError> for syn::Error {
+    fn from(other: CatError) -> Self {
+        todo!()
+    }
+}
+
+impl Display for CatError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        todo!()
+    }
+}
+
+impl Error for CatError {}
+
+/// A type error when alternating two terms.
+#[derive(Debug)]
+pub enum AltError {
+    /// Both terms are nullable.
+    BothNullable(Vec<TypedExpression>, Option<Span>, TypedExpression),
+    /// The first sets of the two terms intersect.
+    FirstOverlap(Vec<TypedExpression>, Option<Span>, TypedExpression),
+}
+
+impl PartialEq for AltError {
+    fn eq(&self, other: &Self) -> bool {
+        todo!()
+    }
+}
+
+impl Eq for AltError {}
+
+impl From<AltError> for syn::Error {
+    fn from(other: AltError) -> Self {
+        todo!()
+    }
+}
+
+impl Display for AltError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        todo!()
+    }
+}
+
+impl Error for AltError {}
+
+#[derive(Debug, Eq, PartialEq)]
+pub enum TypeError {
+    Cat(CatError),
+    Alt(AltError),
+    Variable(VariableError),
+}
+
+impl From<CatError> for TypeError {
+    fn from(other: CatError) -> Self {
+        Self::Cat(other)
+    }
+}
+
+impl From<AltError> for TypeError {
+    fn from(other: AltError) -> Self {
+        Self::Alt(other)
+    }
+}
+
+impl From<VariableError> for TypeError {
+    fn from(other: VariableError) -> Self {
+        Self::Variable(other)
+    }
+}
+
+impl From<TypeError> for syn::Error {
+    fn from(other: TypeError) -> Self {
+        match other {
+            TypeError::Cat(e) => e.into(),
+            TypeError::Alt(e) => e.into(),
+            TypeError::Variable(e) => e.into(),
+        }
+    }
+}
+
+impl Display for TypeError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Cat(e) => e.fmt(f),
+            Self::Alt(e) => e.fmt(f),
+            Self::Variable(e) => e.fmt(f),
+        }
+    }
+}
+
+impl Error for TypeError {}
diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs
new file mode 100644
index 0000000..0161471
--- /dev/null
+++ b/src/chomp/typed/infer.rs
@@ -0,0 +1,145 @@
+use proc_macro2::Span;
+
+use crate::chomp::{
+    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    visit::{Folder, Visitable},
+    Name,
+};
+
+use super::{
+    context::Context,
+    error::{TypeError, VariableError},
+    Type, Typed, TypedExpression,
+};
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+    pub context: &'a mut Context,
+}
+
+impl Folder for TypeInfer<'_> {
+    type Out = Result<TypedExpression, TypeError>;
+
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+        Ok(TypedExpression {
+            inner: super::Epsilon::from(eps).into(),
+            name,
+            span,
+        })
+    }
+
+    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+        Ok(TypedExpression {
+            inner: super::Literal::from(lit).into(),
+            name,
+            span,
+        })
+    }
+
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+        let first = cat.first.fold(self)?;
+        let second = cat.second;
+        let rest = cat.rest;
+        let punct = cat.punct;
+        self.context
+            .with_unguard(|context| -> Result<TypedExpression, TypeError> {
+                let mut infer = TypeInfer { context };
+                let second = second.fold(&mut infer)?;
+                let rest = rest
+                    .into_iter()
+                    .map(|(punct, term)| -> Result<_, TypeError> {
+                        Ok((punct.map(|p| p.span), term.fold(&mut infer)?))
+                    })
+                    .collect::<Result<Vec<_>, _>>()?;
+                Ok(TypedExpression {
+                    inner: super::Cat::new(first, punct.map(|p| p.span), second, rest)?.into(),
+                    name,
+                    span,
+                })
+            })
+    }
+
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+        let first = alt.first.fold(self)?;
+        let second = alt.second;
+        let rest = alt.rest;
+        let punct = alt.punct;
+        self.context
+            .with_unguard(|context| -> Result<TypedExpression, TypeError> {
+                let mut infer = TypeInfer { context };
+                let second = second.fold(&mut infer)?;
+                let rest = rest
+                    .into_iter()
+                    .map(|(punct, term)| -> Result<_, TypeError> {
+                        Ok((punct.map(|p| p.span), term.fold(&mut infer)?))
+                    })
+                    .collect::<Result<Vec<_>, _>>()?;
+                Ok(TypedExpression {
+                    inner: super::Alt::new(first, punct.map(|p| p.span), second, rest)?.into(),
+                    name,
+                    span,
+                })
+            })
+    }
+
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+        let mut ty = Type::default();
+
+        loop {
+            let last = ty;
+            let res = self.context.with_variable_type(last.clone(), |context| {
+                fix.inner.clone().fold(&mut TypeInfer { context })
+            })?;
+            ty = res.get_type().clone();
+
+            if last == ty {
+                return Ok(TypedExpression {
+                    inner: super::Fix {
+                        inner: Box::new(res),
+                    }
+                    .into(),
+                    name,
+                    span,
+                });
+            }
+        }
+    }
+
+    fn fold_variable(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        var: Variable,
+    ) -> Self::Out {
+        let ty = match self.context.get_variable_type(&var) {
+            Ok(ty) => ty.clone(),
+            Err(inner) => {
+                return Err(VariableError {
+                    inner,
+                    var,
+                    span,
+                    name,
+                }
+                .into())
+            }
+        };
+        Ok(TypedExpression {
+            inner: super::Variable { inner: var, ty }.into(),
+            name,
+            span,
+        })
+    }
+
+    fn fold_parameter(
+        &mut self,
+        _name: Option<Name>,
+        _span: Option<Span>,
+        _param: Parameter,
+    ) -> Self::Out {
+        todo!()
+    }
+
+    fn fold_call(&mut self, _name: Option<Name>,_span: Option<Span>, _call: Call) -> Self::Out {
+        todo!()
+    }
+}
diff --git a/src/chomp/typed/lower.rs b/src/chomp/typed/lower.rs
new file mode 100644
index 0000000..37589a1
--- /dev/null
+++ b/src/chomp/typed/lower.rs
@@ -0,0 +1,41 @@
+use proc_macro2::Span;
+
+use crate::chomp::Name;
+
+use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable};
+
+pub trait Backend: Default {
+    type Id;
+    type Code;
+
+    fn gen_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Id;
+
+    fn gen_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Id;
+
+    fn gen_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Id;
+
+    fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id;
+
+    fn gen_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Id;
+
+    fn gen_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable) -> Self::Id;
+
+    fn emit_code(self, name: Option<Name>, span: Option<Span>, id: Self::Id) -> Self::Code;
+}
+
+pub trait GenerateCode {
+    fn gen<B: Backend>(self, backend: &mut B) -> B::Id;
+}
+
+impl GenerateCode for TypedExpression {
+    fn gen<B: Backend>(self, backend: &mut B) -> B::Id {
+        match self.inner {
+            RawTypedExpression::Epsilon(e) => backend.gen_epsilon(self.name, self.span, e),
+            RawTypedExpression::Literal(l) => backend.gen_literal(self.name, self.span, l),
+            RawTypedExpression::Cat(c) => backend.gen_cat(self.name, self.span, c),
+            RawTypedExpression::Alt(a) => backend.gen_alt(self.name, self.span, a),
+            RawTypedExpression::Fix(f) => backend.gen_fix(self.name, self.span, f),
+            RawTypedExpression::Variable(v) => backend.gen_variable(self.name, self.span, v),
+        }
+    }
+}
diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs
new file mode 100644
index 0000000..e9aed79
--- /dev/null
+++ b/src/chomp/typed/mod.rs
@@ -0,0 +1,343 @@
+use std::{hash, iter};
+
+use proc_macro2::Span;
+
+use super::{
+    ast,
+    set::{FirstSet, FlastSet},
+    Name,
+};
+
+pub mod context;
+pub mod error;
+pub mod lower;
+
+mod infer;
+
+pub use self::infer::TypeInfer;
+use self::error::{AltError, CatError};
+
+#[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
+pub struct Type {
+    nullable: bool,
+    first_set: FirstSet,
+    flast_set: FlastSet,
+}
+
+impl Type {
+    pub const fn new(nullable: bool, first_set: FirstSet, flast_set: FlastSet) -> Self {
+        Self {
+            nullable,
+            first_set,
+            flast_set,
+        }
+    }
+
+    pub fn of_str(s: &str) -> Self {
+        Self {
+            nullable: s.is_empty(),
+            first_set: FirstSet::of_str(s),
+            flast_set: FlastSet::default(),
+        }
+    }
+
+    pub fn nullable(&self) -> bool {
+        self.nullable
+    }
+
+    pub fn first_set(&self) -> &FirstSet {
+        &self.first_set
+    }
+
+    pub fn flast_set(&self) -> &FlastSet {
+        &self.flast_set
+    }
+
+    pub fn cat(self, other: Self) -> Self {
+        Self {
+            nullable: self.nullable && other.nullable,
+            first_set: self.first_set.union(if self.nullable {
+                other.first_set.clone()
+            } else {
+                FirstSet::default()
+            }),
+            flast_set: other.flast_set.union(if other.nullable {
+                self.flast_set.union_first(other.first_set)
+            } else {
+                FlastSet::default()
+            }),
+        }
+    }
+
+    pub fn alt(self, other: Self) -> Self {
+        Self {
+            nullable: self.nullable || other.nullable,
+            first_set: self.first_set.union(other.first_set),
+            flast_set: self.flast_set.union(other.flast_set),
+        }
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Epsilon {
+    ty: Type,
+}
+
+impl From<ast::Epsilon> for Epsilon {
+    fn from(_: ast::Epsilon) -> Self {
+        Self {
+            ty: Type::new(true, FirstSet::default(), FlastSet::default()),
+        }
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Literal {
+    inner: ast::Literal,
+    ty: Type,
+}
+
+impl Literal {
+    pub fn inner(&self) -> &ast::Literal {
+        &self.inner
+    }
+}
+
+impl From<ast::Literal> for Literal {
+    fn from(inner: ast::Literal) -> Self {
+        let ty = Type::of_str(&inner);
+        Self { inner, ty }
+    }
+}
+
+impl From<Literal> for ast::Literal {
+    fn from(lit: Literal) -> Self {
+        lit.inner
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Cat {
+    terms: Vec<TypedExpression>,
+    ty: Type,
+}
+
+impl Cat {
+    fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
+        first: TypedExpression,
+        punct: Option<Span>,
+        second: TypedExpression,
+        rest: I,
+    ) -> Result<Self, CatError> {
+        if first.get_type().nullable() {
+            return Err(CatError::FirstNullable(first, punct));
+        }
+
+        iter::once((punct, second))
+            .chain(rest)
+            .try_fold(
+                (first.get_type().clone(), vec![first]),
+                |(ty, mut terms), (punct, right)| {
+                    if !ty
+                        .flast_set()
+                        .intersect_first(right.get_type().first_set())
+                        .is_empty()
+                    {
+                        Err(CatError::FirstFlastOverlap(terms, punct, right))
+                    } else {
+                        let ty = ty.cat(right.get_type().clone());
+                        terms.push(right);
+                        Ok((ty, terms))
+                    }
+                },
+            )
+            .map(|(ty, terms)| Self { ty, terms })
+    }
+}
+
+impl IntoIterator for Cat {
+    type Item = TypedExpression;
+
+    type IntoIter = <Vec<TypedExpression> as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.terms.into_iter()
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Alt {
+    terms: Vec<TypedExpression>,
+    ty: Type,
+}
+
+impl Alt {
+    pub fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
+        first: TypedExpression,
+        punct: Option<Span>,
+        second: TypedExpression,
+        rest: I,
+    ) -> Result<Self, AltError> {
+        iter::once((punct, second))
+            .chain(rest)
+            .try_fold(
+                (first.get_type().clone(), vec![first]),
+                |(ty, mut terms), (punct, right)| {
+                    if ty.nullable() && right.get_type().nullable() {
+                        Err(AltError::BothNullable(terms, punct, right))
+                    } else if !ty
+                        .first_set()
+                        .intersect(right.get_type().first_set())
+                        .is_empty()
+                    {
+                        Err(AltError::FirstOverlap(terms, punct, right))
+                    } else {
+                        let ty = ty.alt(right.get_type().clone());
+                        terms.push(right);
+                        Ok((ty, terms))
+                    }
+                },
+            )
+            .map(|(ty, terms)| Self { ty, terms })
+    }
+}
+
+impl IntoIterator for Alt {
+    type Item = TypedExpression;
+
+    type IntoIter = <Vec<TypedExpression> as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.terms.into_iter()
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Fix {
+    inner: Box<TypedExpression>,
+}
+
+impl Fix {
+    pub fn unwrap(self) -> TypedExpression {
+        *self.inner
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Variable {
+    inner: ast::Variable,
+    ty: Type,
+}
+
+impl Variable {
+    pub fn index(&self) -> usize {
+        self.inner.index
+    }
+}
+
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+enum RawTypedExpression {
+    Epsilon(Epsilon),
+    Literal(Literal),
+    Cat(Cat),
+    Alt(Alt),
+    Fix(Fix),
+    Variable(Variable),
+}
+
+impl From<Epsilon> for RawTypedExpression {
+    fn from(eps: Epsilon) -> Self {
+        Self::Epsilon(eps)
+    }
+}
+
+impl From<Literal> for RawTypedExpression {
+    fn from(lit: Literal) -> Self {
+        Self::Literal(lit)
+    }
+}
+
+impl From<Cat> for RawTypedExpression {
+    fn from(cat: Cat) -> Self {
+        Self::Cat(cat)
+    }
+}
+
+impl From<Alt> for RawTypedExpression {
+    fn from(alt: Alt) -> Self {
+        Self::Alt(alt)
+    }
+}
+
+impl From<Fix> for RawTypedExpression {
+    fn from(fix: Fix) -> Self {
+        Self::Fix(fix)
+    }
+}
+
+impl From<Variable> for RawTypedExpression {
+    fn from(var: Variable) -> Self {
+        Self::Variable(var)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct TypedExpression {
+    inner: RawTypedExpression,
+    pub name: Option<Name>,
+    pub span: Option<Span>,
+}
+
+impl PartialEq for TypedExpression {
+    fn eq(&self, other: &Self) -> bool {
+        self.inner == other.inner && self.name == other.name
+    }
+}
+
+impl Eq for TypedExpression {}
+
+impl hash::Hash for TypedExpression {
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        self.inner.hash(state);
+        self.name.hash(state);
+    }
+}
+
+pub trait Typed {
+    fn get_type(&self) -> &Type;
+}
+
+macro_rules! leaf_typed {
+    ($ty:ty, $field:ident) => {
+        impl Typed for $ty {
+            fn get_type(&self) -> &Type {
+                &self.$field
+            }
+        }
+    };
+}
+
+leaf_typed!(Epsilon, ty);
+leaf_typed!(Literal, ty);
+leaf_typed!(Cat, ty);
+leaf_typed!(Alt, ty);
+leaf_typed!(Variable, ty);
+
+impl Typed for Fix {
+    fn get_type(&self) -> &Type {
+        self.inner.get_type()
+    }
+}
+
+impl Typed for TypedExpression {
+    fn get_type(&self) -> &Type {
+        match &self.inner {
+            RawTypedExpression::Epsilon(e) => e.get_type(),
+            RawTypedExpression::Literal(l) => l.get_type(),
+            RawTypedExpression::Cat(c) => c.get_type(),
+            RawTypedExpression::Alt(a) => a.get_type(),
+            RawTypedExpression::Fix(f) => f.get_type(),
+            RawTypedExpression::Variable(v) => v.get_type(),
+        }
+    }
+}
diff --git a/src/chomp/visit.rs b/src/chomp/visit.rs
index 4113b64..bdef30e 100644
--- a/src/chomp/visit.rs
+++ b/src/chomp/visit.rs
@@ -1,62 +1,120 @@
-use super::ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable};
+use proc_macro2::Span;
+
+use super::{
+    ast::{
+        Alt, Call, Cat, Epsilon, Expression, Fix, Literal, NamedExpression, Parameter, Variable,
+    },
+    Name,
+};
 
 pub trait Visitor {
     type Out;
-    fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out;
-
-    fn visit_literal(&mut self, lit: &Literal) -> Self::Out;
-
-    fn visit_cat(&mut self, cat: &Cat) -> Self::Out;
-
-    fn visit_alt(&mut self, alt: &Alt) -> Self::Out;
-
-    fn visit_fix(&mut self, fix: &Fix) -> Self::Out;
-
-    fn visit_variable(&mut self, var: &Variable) -> Self::Out;
-
-    fn visit_parameter(&mut self, param: &Parameter) -> Self::Out;
-
-    fn visit_call(&mut self, call: &Call) -> Self::Out;
+    fn visit_epsilon(
+        &mut self,
+        name: Option<&Name>,
+        span: Option<Span>,
+        eps: &Epsilon,
+    ) -> Self::Out;
+
+    fn visit_literal(
+        &mut self,
+        name: Option<&Name>,
+        span: Option<Span>,
+        lit: &Literal,
+    ) -> Self::Out;
+
+    fn visit_cat(&mut self, name: Option<&Name>, span: Option<Span>, cat: &Cat) -> Self::Out;
+
+    fn visit_alt(&mut self, name: Option<&Name>, span: Option<Span>, alt: &Alt) -> Self::Out;
+
+    fn visit_fix(&mut self, name: Option<&Name>, span: Option<Span>, fix: &Fix) -> Self::Out;
+
+    fn visit_variable(
+        &mut self,
+        name: Option<&Name>,
+        span: Option<Span>,
+        var: &Variable,
+    ) -> Self::Out;
+
+    fn visit_parameter(
+        &mut self,
+        name: Option<&Name>,
+        span: Option<Span>,
+        param: &Parameter,
+    ) -> Self::Out;
+
+    fn visit_call(&mut self, name: Option<&Name>, span: Option<Span>, call: &Call) -> Self::Out;
 }
 
 pub trait Mapper {
     type Out;
 
-    fn map_epsilon(&mut self, eps: &mut Epsilon) -> Self::Out;
-
-    fn map_literal(&mut self, lit: &mut Literal) -> Self::Out;
-
-    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out;
-
-    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out;
-
-    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out;
-
-    fn map_variable(&mut self, var: &mut Variable) -> Self::Out;
-
-    fn map_parameter(&mut self, param: &mut Parameter) -> Self::Out;
-
-    fn map_call(&mut self, call: &mut Call) -> Self::Out;
+    fn map_epsilon(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        eps: &mut Epsilon,
+    ) -> Self::Out;
+
+    fn map_literal(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        lit: &mut Literal,
+    ) -> Self::Out;
+
+    fn map_cat(&mut self, name: &mut Option<Name>, span: Option<Span>, cat: &mut Cat) -> Self::Out;
+
+    fn map_alt(&mut self, name: &mut Option<Name>, span: Option<Span>, alt: &mut Alt) -> Self::Out;
+
+    fn map_fix(&mut self, name: &mut Option<Name>, span: Option<Span>, fix: &mut Fix) -> Self::Out;
+
+    fn map_variable(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        var: &mut Variable,
+    ) -> Self::Out;
+
+    fn map_parameter(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        param: &mut Parameter,
+    ) -> Self::Out;
+
+    fn map_call(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        call: &mut Call,
+    ) -> Self::Out;
 }
 
 pub trait Folder {
     type Out;
 
-    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out;
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out;
 
-    fn fold_literal(&mut self, lit: Literal) -> Self::Out;
+    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out;
 
-    fn fold_cat(&mut self, cat: Cat) -> Self::Out;
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out;
 
-    fn fold_alt(&mut self, alt: Alt) -> Self::Out;
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out;
 
-    fn fold_fix(&mut self, fix: Fix) -> Self::Out;
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out;
 
-    fn fold_variable(&mut self, var: Variable) -> Self::Out;
+    fn fold_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable)
+        -> Self::Out;
 
-    fn fold_parameter(&mut self, param: Parameter) -> Self::Out;
+    fn fold_parameter(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        param: Parameter,
+    ) -> Self::Out;
 
-    fn fold_call(&mut self, call: Call) -> Self::Out;
+    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out;
 }
 
 pub trait Visitable {
@@ -67,70 +125,43 @@ pub trait Visitable {
     fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out;
 }
 
-macro_rules! visitable_leaf {
-    ($ty:ty, $visit:ident, $map:ident, $fold:ident) => {
-        impl Visitable for $ty {
-            fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
-                visitor.$visit(self)
-            }
-
-            fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
-                mapper.$map(self)
-            }
-
-            fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
-                folder.$fold(self)
-            }
-        }
-    };
-}
-
-visitable_leaf!(Epsilon, visit_epsilon, map_epsilon, fold_epsilon);
-visitable_leaf!(Literal, visit_literal, map_literal, fold_literal);
-visitable_leaf!(Cat, visit_cat, map_cat, fold_cat);
-visitable_leaf!(Alt, visit_alt, map_alt, fold_alt);
-visitable_leaf!(Fix, visit_fix, map_fix, fold_fix);
-visitable_leaf!(Variable, visit_variable, map_variable, fold_variable);
-visitable_leaf!(Parameter, visit_parameter, map_parameter, fold_parameter);
-visitable_leaf!(Call, visit_call, map_call, fold_call);
-
-impl Visitable for Expression {
+impl Visitable for NamedExpression {
     fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
-        match self {
-            Self::Epsilon(e) => visitor.visit_epsilon(e),
-            Self::Literal(l) => visitor.visit_literal(l),
-            Self::Cat(c) => visitor.visit_cat(c),
-            Self::Alt(a) => visitor.visit_alt(a),
-            Self::Fix(f) => visitor.visit_fix(f),
-            Self::Variable(v) => visitor.visit_variable(v),
-            Self::Parameter(p) => visitor.visit_parameter(p),
-            Self::Call(c) => visitor.visit_call(c),
+        match &self.expr {
+            Expression::Epsilon(e) => visitor.visit_epsilon(self.name.as_ref(), self.span, e),
+            Expression::Literal(l) => visitor.visit_literal(self.name.as_ref(), self.span, l),
+            Expression::Cat(c) => visitor.visit_cat(self.name.as_ref(), self.span, c),
+            Expression::Alt(a) => visitor.visit_alt(self.name.as_ref(), self.span, a),
+            Expression::Fix(f) => visitor.visit_fix(self.name.as_ref(), self.span, f),
+            Expression::Variable(v) => visitor.visit_variable(self.name.as_ref(), self.span, v),
+            Expression::Parameter(p) => visitor.visit_parameter(self.name.as_ref(), self.span, p),
+            Expression::Call(c) => visitor.visit_call(self.name.as_ref(), self.span, c),
         }
     }
 
     fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
-        match self {
-            Self::Epsilon(e) => mapper.map_epsilon(e),
-            Self::Literal(l) => mapper.map_literal(l),
-            Self::Cat(c) => mapper.map_cat(c),
-            Self::Alt(a) => mapper.map_alt(a),
-            Self::Fix(f) => mapper.map_fix(f),
-            Self::Variable(v) => mapper.map_variable(v),
-            Self::Parameter(p) => mapper.map_parameter(p),
-            Self::Call(c) => mapper.map_call(c),
+        match &mut self.expr {
+            Expression::Epsilon(e) => mapper.map_epsilon(&mut self.name, self.span, e),
+            Expression::Literal(l) => mapper.map_literal(&mut self.name, self.span, l),
+            Expression::Cat(c) => mapper.map_cat(&mut self.name, self.span, c),
+            Expression::Alt(a) => mapper.map_alt(&mut self.name, self.span, a),
+            Expression::Fix(f) => mapper.map_fix(&mut self.name, self.span, f),
+            Expression::Variable(v) => mapper.map_variable(&mut self.name, self.span, v),
+            Expression::Parameter(p) => mapper.map_parameter(&mut self.name, self.span, p),
+            Expression::Call(c) => mapper.map_call(&mut self.name, self.span, c),
         }
     }
 
     fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
-        match self {
-            Self::Epsilon(e) => folder.fold_epsilon(e),
-            Self::Literal(l) => folder.fold_literal(l),
-            Self::Cat(c) => folder.fold_cat(c),
-            Self::Alt(a) => folder.fold_alt(a),
-            Self::Fix(f) => folder.fold_fix(f),
-            Self::Variable(v) => folder.fold_variable(v),
-            Self::Parameter(p) => folder.fold_parameter(p),
-            Self::Call(c) => folder.fold_call(c),
+        match self.expr {
+            Expression::Epsilon(e) => folder.fold_epsilon(self.name, self.span, e),
+            Expression::Literal(l) => folder.fold_literal(self.name, self.span, l),
+            Expression::Cat(c) => folder.fold_cat(self.name, self.span, c),
+            Expression::Alt(a) => folder.fold_alt(self.name, self.span, a),
+            Expression::Fix(f) => folder.fold_fix(self.name, self.span, f),
+            Expression::Variable(v) => folder.fold_variable(self.name, self.span, v),
+            Expression::Parameter(p) => folder.fold_parameter(self.name, self.span, p),
+            Expression::Call(c) => folder.fold_call(self.name, self.span, c),
         }
     }
 }