Restructure code base to separate compilation phases.

9 files changed, 2296 insertions, 0 deletions

diff --git a/src/chomp/' b/src/chomp/'
new file mode 100644
index 0000000..f2f6588
--- /dev/null
+++ b/src/chomp/'
@@ -0,0 +1,475 @@
+use proc_macro2::{Ident, Span};
+
+use super::{ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable}, context::Context, error::{AltError, CatError, FixError, SubstituteError, TypeError}, set::{FirstSet, FlastSet}, typed::{self, Type, TypedExpression}, visit::{Folder, Mapper, Visitable, Visitor}};
+
+/// Test if term is closed for a context with `depth` variables.
+#[derive(Debug, Default)]
+struct Closed {
+    depth: usize,
+}
+
+impl Visitor for Closed {
+    type Out = bool;
+
+    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+        true
+    }
+
+    fn visit_literal(&mut self, _lit: &Literal) -> Self::Out {
+        true
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        cat.first().visit(self) && cat.second().visit(self)
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        alt.left().visit(self) && alt.right().visit(self)
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        self.depth += 1;
+        let res = fix.inner().visit(self);
+        self.depth -= 1;
+        res
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        var.index() < self.depth
+    }
+
+    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+        true
+    }
+
+    fn visit_call(&mut self, call: &Call) -> Self::Out {
+        call.args().iter().all(|arg| arg.visit(self))
+    }
+}
+
+#[derive(Clone, Copy, Debug)]
+pub struct Spanning;
+
+impl Visitor for Spanning {
+    type Out = Option<Span>;
+
+    fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out {
+        Some(eps.span)
+    }
+
+    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+        Some(lit.span())
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        let fst = cat.first().visit(self);
+        let snd = cat.second().visit(self);
+
+        match (fst, snd) {
+            (None, snd) => snd,
+            (Some(fst), None) => Some(fst),
+            (Some(fst), Some(snd)) => fst.join(snd),
+        }
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        let left = alt.left().visit(self);
+        let right = alt.right().visit(self);
+
+        match (left, right) {
+            (None, right) => right,
+            (Some(left), None) => Some(left),
+            (Some(left), Some(right)) => left.join(right),
+        }
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        fix.span()
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        Some(var.name().span())
+    }
+
+    fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
+        Some(param.name().span())
+    }
+
+    fn visit_call(&mut self, call: &Call) -> Self::Out {
+        call.span()
+    }
+}
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+    context: &'a mut Context,
+}
+
+impl Visitor for TypeInfer<'_> {
+    type Out = Result<Type, TypeError>;
+
+    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+        Ok(Type::new(true, FirstSet::default(), FlastSet::default()))
+    }
+
+    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+        Ok(Type::of_str(&lit.value()))
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        let first = cat.first().visit(self)?;
+        let second = self
+            .context
+            .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?;
+
+        if first.nullable() {
+            Err(TypeError::Cat(CatError::FirstNullable(cat.clone())))
+        } else if !first
+            .flast_set()
+            .intersect_first(second.first_set())
+            .is_empty()
+        {
+            Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone())))
+        } else {
+            Ok(first.cat(second))
+        }
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        let left = alt.left().visit(self)?;
+        let right = alt.right().visit(self)?;
+
+        if left.nullable() && right.nullable() {
+            Err(TypeError::Alt(AltError::BothNullable(alt.clone())))
+        } else if !left.first_set().intersect(right.first_set()).is_empty() {
+            Err(TypeError::Alt(AltError::FirstOverlap(alt.clone())))
+        } else {
+            Ok(left.alt(right))
+        }
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        let mut res = Type::default();
+        let mut last = None;
+
+        while last.map(|r| r != res).unwrap_or(true) {
+            last = Some(res);
+            res = self
+                .context
+                .with_variable_type(last.as_ref().cloned().unwrap(), |context| {
+                    fix.inner().visit(&mut TypeInfer { context })
+                })
+                .map_err(|e| {
+                    TypeError::Fix(FixError(
+                        fix.clone(),
+                        last.as_ref().cloned().unwrap(),
+                        Box::new(e),
+                    ))
+                })?;
+        }
+
+        Ok(res)
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        Ok(self.context.get_variable_type(&var)?.clone())
+    }
+
+    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+        todo!()
+    }
+
+    fn visit_call(&mut self, _call: &Call) -> Self::Out {
+        todo!()
+    }
+}
+
+#[derive(Debug)]
+pub struct TypeCheck<'a> {
+    pub context: &'a mut Context,
+}
+
+impl Folder for TypeCheck<'_> {
+    type Out = Result<TypedExpression, TypeError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(typed::Epsilon::from(eps).into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(typed::Literal::from(lit).into())
+    }
+
+    fn fold_cat(&mut self, cat: Cat) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_cat(&cat)?;
+        let fst = cat.fst.fold(self)?;
+        let snd = cat.snd;
+        let snd = self
+            .context
+            .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?;
+
+        Ok(typed::Cat::new(fst, cat.punct, snd, ty).into())
+    }
+
+    fn fold_alt(&mut self, alt: Alt) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_alt(&alt)?;
+        let left = alt.left.fold(self)?;
+        let right = alt.right.fold(self)?;
+
+        Ok(typed::Alt::new(left, alt.punct, right, ty).into())
+    }
+
+    fn fold_fix(&mut self, fix: Fix) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_fix(&fix)?;
+        let inner = fix.inner;
+        let inner = self
+            .context
+            .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?;
+
+        Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_variable(&var)?;
+        Ok(typed::Variable::new(var, ty).into())
+    }
+
+    fn fold_parameter(&mut self, _param: Parameter) -> Self::Out {
+        todo!()
+    }
+
+    fn fold_call(&mut self, _call: Call) -> Self::Out {
+        todo!()
+    }
+}
+
+#[derive(Debug, Default)]
+struct DeepenVars {
+    depth: usize,
+}
+
+impl Mapper for DeepenVars {
+    type Out = ();
+
+    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+        cat.first_mut().map(self);
+        cat.second_mut().map(self);
+    }
+
+    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+        alt.left_mut().map(self);
+        alt.right_mut().map(self);
+    }
+
+    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+        self.depth += 1;
+        fix.inner_mut().map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+        if bind.index() >= self.depth {
+            *bind.index_mut() += 1;
+        }
+    }
+
+    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+    fn map_call(&mut self, call: &mut Call) -> Self::Out {
+        for arg in call.args_mut() {
+            arg.map(self);
+        }
+    }
+}
+
+#[derive(Debug, Default)]
+struct ShallowVars {
+    depth: usize,
+}
+
+impl Mapper for ShallowVars {
+    type Out = ();
+
+    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+        cat.first_mut().map(self);
+        cat.second_mut().map(self);
+    }
+
+    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+        alt.left_mut().map(self);
+        alt.right_mut().map(self);
+    }
+
+    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+        self.depth += 1;
+        fix.inner_mut().map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+        if bind.index() > self.depth {
+            *bind.index_mut() -= 1;
+        }
+    }
+
+    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+    fn map_call(&mut self, call: &mut Call) -> Self::Out {
+        for arg in call.args_mut() {
+            arg.map(self);
+        }
+    }
+}
+
+struct Substitute {
+    params: Vec<Expression>,
+}
+
+impl Folder for Substitute {
+    type Out = Result<Expression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(eps.into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(lit.into())
+    }
+
+    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+        cat.fst = Box::new(cat.fst.fold(self)?);
+        cat.snd = Box::new(cat.snd.fold(self)?);
+        Ok(cat.into())
+    }
+
+    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+        alt.left = Box::new(alt.left.fold(self)?);
+        alt.right = Box::new(alt.right.fold(self)?);
+        Ok(alt.into())
+    }
+
+    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+        for param in &mut self.params {
+            param.map(&mut DeepenVars::default());
+        }
+
+        fix.inner = Box::new(fix.inner.fold(self)?);
+
+        for param in &mut self.params {
+            param.map(&mut ShallowVars::default());
+        }
+
+        Ok(fix.into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        Ok(Expression::Variable(var))
+    }
+
+    fn fold_call(&mut self, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+        Ok(call.into())
+    }
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+        self.params
+            .get(param.index())
+            .cloned()
+            .ok_or(SubstituteError::FreeParameter(param))
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct InlineCall {
+    function: Function,
+}
+
+impl InlineCall {
+    pub fn new(function: Function) -> Self {
+        Self {
+            function
+        }
+    }
+}
+
+impl Folder for InlineCall {
+    type Out = Result<Expression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(eps.into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(lit.into())
+    }
+
+    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+        cat.fst = Box::new(cat.fst.fold(self)?);
+        cat.snd = Box::new(cat.snd.fold(self)?);
+        Ok(cat.into())
+    }
+
+    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+        alt.left = Box::new(alt.left.fold(self)?);
+        alt.right = Box::new(alt.right.fold(self)?);
+        Ok(alt.into())
+    }
+
+    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+        fix.inner = Box::new(fix.inner.fold(self)?);
+        Ok(fix.into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        Ok(var.into())
+    }
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+        Ok(param.into())
+    }
+
+    fn fold_call(&mut self, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+
+        if call.name != self.function.name {
+            Ok(call.into())
+        } else if call.args.len() != self.function.params {
+            Err(SubstituteError::WrongArgCount {
+                call,
+                expected: self.args,
+            })
+        } else {
+            self.term
+                .clone()
+                .fold(&mut Substitute { params: call.args })
+        }
+    }
+}
diff --git a/src/chomp/ast.rs b/src/chomp/ast.rs
new file mode 100644
index 0000000..e8e3309
--- /dev/null
+++ b/src/chomp/ast.rs
@@ -0,0 +1,345 @@
+use std::fmt::{self, Display};
+
+use proc_macro2::Span;
+use syn::{Ident, LitStr, Token};
+
+pub type Epsilon = Token![_];
+
+pub type Literal = LitStr;
+
+#[derive(Clone, Debug)]
+pub struct Cat {
+    pub fst: Box<Expression>,
+    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
+    }
+}
+
+impl Display for Cat {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "({}.{})", self.fst, self.snd)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct Alt {
+    pub left: Box<Expression>,
+    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
+    }
+}
+
+impl Display for Alt {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "({}|{})", self.left, self.right)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct Fix {
+    pub arg: Ident,
+    pub inner: Box<Expression>,
+    pub span: Option<Span>,
+}
+
+impl Fix {
+    pub fn new(arg: Ident, inner: Expression, span: Option<Span>) -> Self {
+        Self {
+            arg,
+            inner: Box::new(inner),
+            span,
+        }
+    }
+
+    pub fn arg(&self) -> &Ident {
+        &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
+    }
+}
+
+impl Display for Fix {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "[{}]({})", self.arg, self.inner)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct Variable {
+    pub name: Ident,
+    pub index: usize,
+}
+
+impl Variable {
+    pub fn new(name: Ident, index: usize) -> Self {
+        Self { name, index }
+    }
+
+    pub fn name(&self) -> &Ident {
+        &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)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct Parameter {
+    pub name: Ident,
+    pub index: usize,
+}
+
+impl Parameter {
+    pub fn new(name: Ident, index: usize) -> Self {
+        Self { name, index }
+    }
+
+    pub fn name(&self) -> &Ident {
+        &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 {
+        self.name.fmt(f)
+    }
+}
+
+/// A macro invocation.
+#[derive(Clone, Debug)]
+pub struct Call {
+    pub name: Ident,
+    pub args: Vec<Expression>,
+    pub span: Option<Span>,
+}
+
+impl Call {
+    pub fn new(name: Ident, args: Vec<Expression>, span: Option<Span>) -> Self {
+        Self { name, args, span }
+    }
+
+    pub fn name(&self) -> &Ident {
+        &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
+    }
+}
+
+impl Display for Call {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{}", self.name)?;
+
+        let mut iter = self.args.iter();
+
+        if let Some(arg) = iter.next() {
+            write!(f, "({}", arg)?;
+
+            for arg in iter {
+                write!(f, ", {}", arg)?;
+            }
+
+            write!(f, ")")
+        } else {
+            Ok(())
+        }
+    }
+}
+
+#[derive(Clone, Debug)]
+pub enum Expression {
+    /// Matches the empty string.
+    Epsilon(Epsilon),
+    /// Matches the literal string.
+    Literal(Literal),
+    /// Matches one term followed by another.
+    Cat(Cat),
+    /// Matches either one term or another.
+    Alt(Alt),
+    /// The least fix point of a term.
+    Fix(Fix),
+    /// A fixed point variable.
+    Variable(Variable),
+    /// A formal parameter.
+    Parameter(Parameter),
+    /// A macro invocation.
+    Call(Call),
+}
+
+impl Display for Expression {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Epsilon(_) => write!(f, "_"),
+            Self::Literal(l) => write!(f, "{:?}", l.value()),
+            Self::Cat(c) => c.fmt(f),
+            Self::Alt(a) => a.fmt(f),
+            Self::Fix(x) => x.fmt(f),
+            Self::Variable(v) => v.fmt(f),
+            Self::Parameter(p) => p.fmt(f),
+            Self::Call(c) => c.fmt(f),
+        }
+    }
+}
+
+impl From<Epsilon> for Expression {
+    fn from(eps: Epsilon) -> Self {
+        Self::Epsilon(eps)
+    }
+}
+
+impl From<Literal> for Expression {
+    fn from(lit: Literal) -> Self {
+        Self::Literal(lit)
+    }
+}
+
+impl From<Cat> for Expression {
+    fn from(cat: Cat) -> Self {
+        Self::Cat(cat)
+    }
+}
+
+impl From<Alt> for Expression {
+    fn from(alt: Alt) -> Self {
+        Self::Alt(alt)
+    }
+}
+
+impl From<Fix> for Expression {
+    fn from(fix: Fix) -> Self {
+        Self::Fix(fix)
+    }
+}
+
+impl From<Variable> for Expression {
+    fn from(var: Variable) -> Self {
+        Self::Variable(var)
+    }
+}
+
+impl From<Parameter> for Expression {
+    fn from(param: Parameter) -> Self {
+        Self::Parameter(param)
+    }
+}
+
+impl From<Call> for Expression {
+    fn from(call: Call) -> Self {
+        Self::Call(call)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct Function {
+    pub name: Ident,
+    pub params: usize,
+    pub expr: Expression,
+    pub span: Option<Span>,
+}
+
+impl Function {
+    pub fn new(name: Ident, params: usize, expr: Expression, span: Option<Span>) -> Self {
+        Self {
+            name,
+            params,
+            expr,
+            span,
+        }
+    }
+}
diff --git a/src/chomp/check.rs b/src/chomp/check.rs
new file mode 100644
index 0000000..cb4798c
--- /dev/null
+++ b/src/chomp/check.rs
@@ -0,0 +1,481 @@
+use proc_macro2::Span;
+
+use super::{
+    ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Function, Literal, Parameter, Variable},
+    context::Context,
+    error::{AltError, CatError, FixError, SubstituteError, TypeError},
+    set::{FirstSet, FlastSet},
+    typed::{self, Type, TypedExpression},
+    visit::{Folder, Mapper, Visitable, Visitor},
+};
+
+/// Test if term is closed for a context with `depth` variables.
+#[derive(Debug, Default)]
+struct Closed {
+    depth: usize,
+}
+
+impl Visitor for Closed {
+    type Out = bool;
+
+    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+        true
+    }
+
+    fn visit_literal(&mut self, _lit: &Literal) -> Self::Out {
+        true
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        cat.first().visit(self) && cat.second().visit(self)
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        alt.left().visit(self) && alt.right().visit(self)
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        self.depth += 1;
+        let res = fix.inner().visit(self);
+        self.depth -= 1;
+        res
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        var.index() < self.depth
+    }
+
+    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+        true
+    }
+
+    fn visit_call(&mut self, call: &Call) -> Self::Out {
+        call.args().iter().all(|arg| arg.visit(self))
+    }
+}
+
+#[derive(Clone, Copy, Debug)]
+pub struct Spanning;
+
+impl Visitor for Spanning {
+    type Out = Option<Span>;
+
+    fn visit_epsilon(&mut self, eps: &Epsilon) -> Self::Out {
+        Some(eps.span)
+    }
+
+    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+        Some(lit.span())
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        let fst = cat.first().visit(self);
+        let snd = cat.second().visit(self);
+
+        match (fst, snd) {
+            (None, snd) => snd,
+            (Some(fst), None) => Some(fst),
+            (Some(fst), Some(snd)) => fst.join(snd),
+        }
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        let left = alt.left().visit(self);
+        let right = alt.right().visit(self);
+
+        match (left, right) {
+            (None, right) => right,
+            (Some(left), None) => Some(left),
+            (Some(left), Some(right)) => left.join(right),
+        }
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        fix.span()
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        Some(var.name().span())
+    }
+
+    fn visit_parameter(&mut self, param: &Parameter) -> Self::Out {
+        Some(param.name().span())
+    }
+
+    fn visit_call(&mut self, call: &Call) -> Self::Out {
+        call.span()
+    }
+}
+
+#[derive(Debug)]
+pub struct TypeInfer<'a> {
+    context: &'a mut Context,
+}
+
+impl Visitor for TypeInfer<'_> {
+    type Out = Result<Type, TypeError>;
+
+    fn visit_epsilon(&mut self, _eps: &Epsilon) -> Self::Out {
+        Ok(Type::new(true, FirstSet::default(), FlastSet::default()))
+    }
+
+    fn visit_literal(&mut self, lit: &Literal) -> Self::Out {
+        Ok(Type::of_str(&lit.value()))
+    }
+
+    fn visit_cat(&mut self, cat: &Cat) -> Self::Out {
+        let first = cat.first().visit(self)?;
+        let second = self
+            .context
+            .with_unguard(|context| cat.second().visit(&mut TypeInfer { context }))?;
+
+        if first.nullable() {
+            Err(TypeError::Cat(CatError::FirstNullable(cat.clone())))
+        } else if !first
+            .flast_set()
+            .intersect_first(second.first_set())
+            .is_empty()
+        {
+            Err(TypeError::Cat(CatError::FirstFlastOverlap(cat.clone())))
+        } else {
+            Ok(first.cat(second))
+        }
+    }
+
+    fn visit_alt(&mut self, alt: &Alt) -> Self::Out {
+        let left = alt.left().visit(self)?;
+        let right = alt.right().visit(self)?;
+
+        if left.nullable() && right.nullable() {
+            Err(TypeError::Alt(AltError::BothNullable(alt.clone())))
+        } else if !left.first_set().intersect(right.first_set()).is_empty() {
+            Err(TypeError::Alt(AltError::FirstOverlap(alt.clone())))
+        } else {
+            Ok(left.alt(right))
+        }
+    }
+
+    fn visit_fix(&mut self, fix: &Fix) -> Self::Out {
+        let mut res = Type::default();
+        let mut last = None;
+
+        while last.map(|r| r != res).unwrap_or(true) {
+            last = Some(res);
+            res = self
+                .context
+                .with_variable_type(last.as_ref().cloned().unwrap(), |context| {
+                    fix.inner().visit(&mut TypeInfer { context })
+                })
+                .map_err(|e| {
+                    TypeError::Fix(FixError(
+                        fix.clone(),
+                        last.as_ref().cloned().unwrap(),
+                        Box::new(e),
+                    ))
+                })?;
+        }
+
+        Ok(res)
+    }
+
+    fn visit_variable(&mut self, var: &Variable) -> Self::Out {
+        Ok(self.context.get_variable_type(&var)?.clone())
+    }
+
+    fn visit_parameter(&mut self, _param: &Parameter) -> Self::Out {
+        todo!()
+    }
+
+    fn visit_call(&mut self, _call: &Call) -> Self::Out {
+        todo!()
+    }
+}
+
+#[derive(Debug)]
+pub struct TypeCheck<'a> {
+    pub context: &'a mut Context,
+}
+
+impl Folder for TypeCheck<'_> {
+    type Out = Result<TypedExpression, TypeError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(typed::Epsilon::from(eps).into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(typed::Literal::from(lit).into())
+    }
+
+    fn fold_cat(&mut self, cat: Cat) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_cat(&cat)?;
+        let fst = cat.fst.fold(self)?;
+        let snd = cat.snd;
+        let snd = self
+            .context
+            .with_unguard(|context| snd.fold(&mut TypeCheck { context }))?;
+
+        Ok(typed::Cat::new(fst, cat.punct, snd, ty).into())
+    }
+
+    fn fold_alt(&mut self, alt: Alt) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_alt(&alt)?;
+        let left = alt.left.fold(self)?;
+        let right = alt.right.fold(self)?;
+
+        Ok(typed::Alt::new(left, alt.punct, right, ty).into())
+    }
+
+    fn fold_fix(&mut self, fix: Fix) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_fix(&fix)?;
+        let inner = fix.inner;
+        let inner = self
+            .context
+            .with_variable_type(ty.clone(), |context| inner.fold(&mut TypeCheck { context }))?;
+
+        Ok(typed::Fix::new(fix.arg, inner, fix.span, ty).into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        let ty = TypeInfer {
+            context: self.context,
+        }
+        .visit_variable(&var)?;
+        Ok(typed::Variable::new(var, ty).into())
+    }
+
+    fn fold_parameter(&mut self, _param: Parameter) -> Self::Out {
+        todo!()
+    }
+
+    fn fold_call(&mut self, _call: Call) -> Self::Out {
+        todo!()
+    }
+}
+
+#[derive(Debug, Default)]
+struct DeepenVars {
+    depth: usize,
+}
+
+impl Mapper for DeepenVars {
+    type Out = ();
+
+    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+        cat.first_mut().map(self);
+        cat.second_mut().map(self);
+    }
+
+    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+        alt.left_mut().map(self);
+        alt.right_mut().map(self);
+    }
+
+    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+        self.depth += 1;
+        fix.inner_mut().map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+        if bind.index() >= self.depth {
+            *bind.index_mut() += 1;
+        }
+    }
+
+    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+    fn map_call(&mut self, call: &mut Call) -> Self::Out {
+        for arg in call.args_mut() {
+            arg.map(self);
+        }
+    }
+}
+
+#[derive(Debug, Default)]
+struct ShallowVars {
+    depth: usize,
+}
+
+impl Mapper for ShallowVars {
+    type Out = ();
+
+    fn map_epsilon(&mut self, _: &mut Epsilon) -> Self::Out {}
+
+    fn map_literal(&mut self, _: &mut Literal) -> Self::Out {}
+
+    fn map_cat(&mut self, cat: &mut Cat) -> Self::Out {
+        cat.first_mut().map(self);
+        cat.second_mut().map(self);
+    }
+
+    fn map_alt(&mut self, alt: &mut Alt) -> Self::Out {
+        alt.left_mut().map(self);
+        alt.right_mut().map(self);
+    }
+
+    fn map_fix(&mut self, fix: &mut Fix) -> Self::Out {
+        self.depth += 1;
+        fix.inner_mut().map(self);
+        self.depth -= 1;
+    }
+
+    fn map_variable(&mut self, bind: &mut Variable) -> Self::Out {
+        if bind.index() > self.depth {
+            *bind.index_mut() -= 1;
+        }
+    }
+
+    fn map_parameter(&mut self, _param: &mut Parameter) -> Self::Out {}
+
+    fn map_call(&mut self, call: &mut Call) -> Self::Out {
+        for arg in call.args_mut() {
+            arg.map(self);
+        }
+    }
+}
+
+struct Substitute {
+    params: Vec<Expression>,
+}
+
+impl Folder for Substitute {
+    type Out = Result<Expression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(eps.into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(lit.into())
+    }
+
+    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+        cat.fst = Box::new(cat.fst.fold(self)?);
+        cat.snd = Box::new(cat.snd.fold(self)?);
+        Ok(cat.into())
+    }
+
+    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+        alt.left = Box::new(alt.left.fold(self)?);
+        alt.right = Box::new(alt.right.fold(self)?);
+        Ok(alt.into())
+    }
+
+    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+        for param in &mut self.params {
+            param.map(&mut DeepenVars::default());
+        }
+
+        fix.inner = Box::new(fix.inner.fold(self)?);
+
+        for param in &mut self.params {
+            param.map(&mut ShallowVars::default());
+        }
+
+        Ok(fix.into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        Ok(Expression::Variable(var))
+    }
+
+    fn fold_call(&mut self, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+        Ok(call.into())
+    }
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+        self.params
+            .get(param.index())
+            .cloned()
+            .ok_or(SubstituteError::FreeParameter(param))
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct InlineCall {
+    function: Function,
+}
+
+impl InlineCall {
+    pub fn new(function: Function) -> Self {
+        Self { function }
+    }
+}
+
+impl Folder for InlineCall {
+    type Out = Result<Expression, SubstituteError>;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out {
+        Ok(eps.into())
+    }
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out {
+        Ok(lit.into())
+    }
+
+    fn fold_cat(&mut self, mut cat: Cat) -> Self::Out {
+        cat.fst = Box::new(cat.fst.fold(self)?);
+        cat.snd = Box::new(cat.snd.fold(self)?);
+        Ok(cat.into())
+    }
+
+    fn fold_alt(&mut self, mut alt: Alt) -> Self::Out {
+        alt.left = Box::new(alt.left.fold(self)?);
+        alt.right = Box::new(alt.right.fold(self)?);
+        Ok(alt.into())
+    }
+
+    fn fold_fix(&mut self, mut fix: Fix) -> Self::Out {
+        fix.inner = Box::new(fix.inner.fold(self)?);
+        Ok(fix.into())
+    }
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out {
+        Ok(var.into())
+    }
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out {
+        Ok(param.into())
+    }
+
+    fn fold_call(&mut self, mut call: Call) -> Self::Out {
+        call.args = call
+            .args
+            .into_iter()
+            .map(|arg| arg.fold(self))
+            .collect::<Result<_, _>>()?;
+
+        if call.name != self.function.name {
+            Ok(call.into())
+        } else if call.args.len() != self.function.params {
+            Err(SubstituteError::WrongArgCount {
+                call,
+                expected: self.function.params,
+            })
+        } else {
+            self.function
+                .expr
+                .clone()
+                .fold(&mut Substitute { params: call.args })
+        }
+    }
+}
diff --git a/src/chomp/context.rs b/src/chomp/context.rs
new file mode 100644
index 0000000..392023f
--- /dev/null
+++ b/src/chomp/context.rs
@@ -0,0 +1,51 @@
+use super::{ast::Variable, error::VariableError, typed::Type};
+
+#[derive(Debug, Default)]
+pub struct Context {
+    vars: Vec<Type>,
+    unguard_points: Vec<usize>,
+}
+
+impl Context {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    pub fn depth(&self) -> usize {
+        self.vars.len()
+    }
+
+    pub fn is_unguarded(&self, var: &Variable) -> Option<bool> {
+        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(),
+            )
+        }
+    }
+
+    pub fn with_unguard<F: FnOnce(&mut Self) -> R, R>(&mut self, f: F) -> R {
+        self.unguard_points.push(self.vars.len());
+        let res = f(self);
+        self.unguard_points.pop();
+        res
+    }
+
+    pub fn get_variable_type(&self, var: &Variable) -> Result<&Type, VariableError> {
+        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]),
+        }
+    }
+
+    pub fn with_variable_type<F: FnOnce(&mut Self) -> R, R>(&mut self, ty: Type, f: F) -> R {
+        self.vars.push(ty);
+        let res = f(self);
+        self.vars.pop();
+        res
+    }
+}
diff --git a/src/chomp/error.rs b/src/chomp/error.rs
new file mode 100644
index 0000000..6733d06
--- /dev/null
+++ b/src/chomp/error.rs
@@ -0,0 +1,389 @@
+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)]
+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().start();
+                write!(
+                    f,
+                    "{}:{}: unbound variable '{}'",
+                    start.line,
+                    start.column,
+                    var.name()
+                )
+            }
+            Self::GuardedVariable(var) => {
+                let start = var.name().span().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)]
+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)]
+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)]
+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)]
+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)]
+pub enum SubstituteError {
+    FreeParameter(Parameter),
+    WrongArgCount { call: Call, expected: usize },
+}
+
+impl Display for SubstituteError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::FreeParameter(param) => {
+                let start = param.name().span().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,
+                    call.args().len(),
+                    expected
+                )
+            }
+        }
+    }
+}
+
+impl Error for SubstituteError {}
diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
new file mode 100644
index 0000000..bb31b6f
--- /dev/null
+++ b/src/chomp/mod.rs
@@ -0,0 +1,7 @@
+pub mod ast;
+pub mod check;
+pub mod context;
+pub mod error;
+pub mod set;
+pub mod typed;
+pub mod visit;
diff --git a/src/chomp/set.rs b/src/chomp/set.rs
new file mode 100644
index 0000000..0661ab6
--- /dev/null
+++ b/src/chomp/set.rs
@@ -0,0 +1,91 @@
+use std::collections::BTreeSet;
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
+pub struct FirstSet {
+    inner: BTreeSet<char>,
+}
+
+impl FirstSet {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    pub fn of_str(s: &str) -> Self {
+        let mut inner = BTreeSet::new();
+        s.chars().next().map(|c| inner.insert(c));
+
+        Self { inner }
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    pub fn union(mut self, mut other: Self) -> Self {
+        self.inner.append(&mut other.inner);
+        self
+    }
+
+    pub fn intersect(&self, other: &Self) -> Self {
+        Self {
+            inner: self.inner.intersection(&other.inner).copied().collect(),
+        }
+    }
+}
+
+impl IntoIterator for FirstSet {
+    type Item = char;
+
+    type IntoIter = <BTreeSet<char> as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.inner.into_iter()
+    }
+}
+
+#[derive(Clone, Debug, Default, Eq, PartialEq, Hash)]
+pub struct FlastSet {
+    inner: BTreeSet<char>,
+}
+
+impl FlastSet {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    pub fn union_first(mut self, mut other: FirstSet) -> Self {
+        self.inner.append(&mut other.inner);
+        self
+    }
+
+    pub fn union(mut self, mut other: Self) -> Self {
+        self.inner.append(&mut other.inner);
+        self
+    }
+
+    pub fn intersect_first(&self, other: &FirstSet) -> Self {
+        Self {
+            inner: self.inner.intersection(&other.inner).copied().collect(),
+        }
+    }
+
+    pub fn intersect(&self, other: &Self) -> Self {
+        Self {
+            inner: self.inner.intersection(&other.inner).copied().collect(),
+        }
+    }
+}
+
+impl IntoIterator for FlastSet {
+    type Item = char;
+
+    type IntoIter = <BTreeSet<char> as IntoIterator>::IntoIter;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.inner.into_iter()
+    }
+}
diff --git a/src/chomp/typed.rs b/src/chomp/typed.rs
new file mode 100644
index 0000000..69108ae
--- /dev/null
+++ b/src/chomp/typed.rs
@@ -0,0 +1,321 @@
+use std::hash::{Hash, Hasher};
+
+use proc_macro2::Span;
+use syn::{Ident, LitStr, Token};
+
+use super::{
+    ast,
+    set::{FirstSet, FlastSet},
+};
+
+#[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: 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: LitStr,
+    ty: Type,
+}
+
+impl Literal {
+    pub fn inner(&self) -> &LitStr {
+        &self.inner
+    }
+
+    pub fn span(&self) -> 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 }
+    }
+}
+
+#[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: Ident,
+    inner: Box<TypedExpression>,
+    span: Option<Span>,
+    ty: Type,
+}
+
+impl Fix {
+    pub(crate) fn new(arg: Ident, inner: TypedExpression, span: Option<Span>, ty: Type) -> Self {
+        Self {
+            arg,
+            inner: Box::new(inner),
+            span,
+            ty,
+        }
+    }
+
+    pub fn unwrap(self) -> (Ident, 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 {
+    ident: Ident,
+    index: usize,
+    ty: Type,
+}
+
+impl Variable {
+    pub(crate) fn new(var: ast::Variable, ty: Type) -> Self {
+        Self {
+            ident: var.name,
+            index: var.index,
+            ty,
+        }
+    }
+
+    pub fn index(&self) -> usize {
+        self.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/visit.rs b/src/chomp/visit.rs
new file mode 100644
index 0000000..4113b64
--- /dev/null
+++ b/src/chomp/visit.rs
@@ -0,0 +1,136 @@
+use super::ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Literal, Parameter, Variable};
+
+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;
+}
+
+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;
+}
+
+pub trait Folder {
+    type Out;
+
+    fn fold_epsilon(&mut self, eps: Epsilon) -> Self::Out;
+
+    fn fold_literal(&mut self, lit: Literal) -> Self::Out;
+
+    fn fold_cat(&mut self, cat: Cat) -> Self::Out;
+
+    fn fold_alt(&mut self, alt: Alt) -> Self::Out;
+
+    fn fold_fix(&mut self, fix: Fix) -> Self::Out;
+
+    fn fold_variable(&mut self, var: Variable) -> Self::Out;
+
+    fn fold_parameter(&mut self, param: Parameter) -> Self::Out;
+
+    fn fold_call(&mut self, call: Call) -> Self::Out;
+}
+
+pub trait Visitable {
+    fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out;
+
+    fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out;
+
+    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 {
+    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),
+        }
+    }
+
+    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),
+        }
+    }
+
+    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),
+        }
+    }
+}