Introduce lambda expressions.

12 files changed, 755 insertions, 562 deletions

diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs
index 9057ec3..ea145a7 100644
--- a/src/chomp/ast/error.rs
+++ b/src/chomp/ast/error.rs
@@ -6,31 +6,31 @@ use std::{
 };
 
 #[derive(Debug)]
-pub enum TranslateError {
+pub enum ReductionError {
     CallNotAFunction {
         on: Expression,
-        span: Option<Span>,
+        span: Span,
     },
     WrongArgCount {
         lambda: Lambda,
         args: Vec<NamedExpression>,
-        span: Option<Span>,
+        span: Span,
     },
 }
 
-impl From<TranslateError> for syn::Error {
-    fn from(e: TranslateError) -> Self {
+impl From<ReductionError> for syn::Error {
+    fn from(e: ReductionError) -> Self {
         let msg = e.to_string();
         let span = match e {
-            TranslateError::CallNotAFunction { span, .. }
-            | TranslateError::WrongArgCount { span, .. } => span,
+            ReductionError::CallNotAFunction { span, .. }
+            | ReductionError::WrongArgCount { span, .. } => span,
         };
 
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
+        Self::new(span, msg)
     }
 }
 
-impl Display for TranslateError {
+impl Display for ReductionError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             Self::CallNotAFunction { .. } => {
@@ -38,7 +38,7 @@ impl Display for TranslateError {
             }
             Self::WrongArgCount { lambda, args, .. } => match (lambda.args.len(), args.len()) {
                 (1, n) => write!(f, "this function takes 1 argument but {} were supplied", n),
-                (m, _) => write!(f, "this function takes {} arguments but 1 was supplied", m),
+                (m, 1) => write!(f, "this function takes {} arguments but 1 was supplied", m),
                 (m, n) => write!(
                     f,
                     "this function takes {} arguments but {} were supplied",
@@ -49,4 +49,4 @@ impl Display for TranslateError {
     }
 }
 
-impl Error for TranslateError {}
+impl Error for ReductionError {}
diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs
index 232381a..7b3ea16 100644
--- a/src/chomp/ast/mod.rs
+++ b/src/chomp/ast/mod.rs
@@ -2,7 +2,7 @@ use std::fmt::{self, Display};
 
 use proc_macro2::Span;
 
-use super::Name;
+use super::name::Name;
 
 pub mod error;
 pub mod substitute;
@@ -15,7 +15,7 @@ pub type Literal = String;
 #[derive(Clone, Debug)]
 pub struct Cat {
     pub first: Box<NamedExpression>,
-    pub rest: Vec<(Option<Span>, NamedExpression)>,
+    pub rest: Vec<(Span, NamedExpression)>,
 }
 
 impl Display for Cat {
@@ -45,7 +45,7 @@ impl Eq for Cat {}
 #[derive(Clone, Debug)]
 pub struct Alt {
     pub first: Box<NamedExpression>,
-    pub rest: Vec<(Option<Span>, NamedExpression)>
+    pub rest: Vec<(Span, NamedExpression)>
 }
 
 impl Display for Alt {
@@ -105,7 +105,7 @@ impl Display for Call {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "({}", self.on)?;
 
-        for arg in self.args {
+        for arg in &self.args {
             write!(f, " {}", arg)?;
         }
 
@@ -135,7 +135,21 @@ impl Display for Lambda {
     }
 }
 
-#[derive(Clone, Debug)]
+/// A let statement.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Let {
+    pub name: Name,
+    pub bound: Box<NamedExpression>,
+    pub body: Box<NamedExpression>,
+}
+
+impl Display for Let {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "let {} = {}; {}", self.name, self.bound, self.body)
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
 pub enum Expression {
     /// Matches the empty string.
     Epsilon(Epsilon),
@@ -153,6 +167,8 @@ pub enum Expression {
     Call(Call),
     /// A function abstraction.
     Lambda(Lambda),
+    /// A let statement
+    Let(Let),
 }
 
 impl Expression {
@@ -176,69 +192,11 @@ impl Display for Expression {
             Self::Variable(v) => v.fmt(f),
             Self::Lambda(p) => p.fmt(f),
             Self::Call(c) => c.fmt(f),
+            Self::Let(l) => l.fmt(f),
         }
     }
 }
 
-impl PartialEq for Expression {
-    fn eq(&self, other: &Self) -> bool {
-        match self {
-            Self::Epsilon(_) => matches!(other, Self::Epsilon(_)),
-            Self::Literal(l) => {
-                if let Self::Literal(them) = other {
-                    l == them
-                } else {
-                    false
-                }
-            }
-            Self::Cat(c) => {
-                if let Self::Cat(them) = other {
-                    c == them
-                } else {
-                    false
-                }
-            }
-            Self::Alt(a) => {
-                if let Self::Alt(them) = other {
-                    a == them
-                } else {
-                    false
-                }
-            }
-            Self::Fix(f) => {
-                if let Self::Fix(them) = other {
-                    f == them
-                } else {
-                    false
-                }
-            }
-            Self::Variable(v) => {
-                if let Self::Variable(them) = other {
-                    v == them
-                } else {
-                    false
-                }
-            }
-            Self::Lambda(p) => {
-                if let Self::Lambda(them) = other {
-                    p == them
-                } else {
-                    false
-                }
-            }
-            Self::Call(c) => {
-                if let Self::Call(them) = other {
-                    c == them
-                } else {
-                    false
-                }
-            }
-        }
-    }
-}
-
-impl Eq for Expression {}
-
 impl From<Epsilon> for Expression {
     fn from(eps: Epsilon) -> Self {
         Self::Epsilon(eps)
@@ -287,17 +245,29 @@ impl From<Call> for Expression {
     }
 }
 
+impl From<Let> for Expression {
+    fn from(stmt: Let) -> Self {
+        Self::Let(stmt)
+    }
+}
+
 #[derive(Clone, Debug)]
 pub struct NamedExpression {
     pub name: Option<Name>,
+    pub span: Span,
     pub expr: Expression,
-    pub span: Option<Span>,
 }
 
 impl Display for NamedExpression {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match &self.name {
-            Some(name) => write!(f, "({} : {})", self.expr, name),
+            Some(name) => {
+                if let Expression::Variable(_) = self.expr {
+                    write!(f, "{}", name)
+                } else {
+                    write!(f, "({} : {})", self.expr, name)
+                }
+            },
             None => self.expr.fmt(f),
         }
     }
@@ -310,16 +280,3 @@ impl PartialEq for NamedExpression {
 }
 
 impl Eq for NamedExpression {}
-
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub struct Let {
-    pub name: Name,
-    pub val: NamedExpression,
-    pub inner: Box<TopLevel>,
-}
-
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub enum TopLevel {
-    Let(Let),
-    Goal(NamedExpression),
-}
diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
index 80df588..c6d3ef6 100644
--- a/src/chomp/ast/substitute.rs
+++ b/src/chomp/ast/substitute.rs
@@ -1,24 +1,32 @@
+use std::array;
+
 use super::{
-    error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable,
+    error::ReductionError, Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal,
+    NamedExpression, Variable,
 };
 use crate::chomp::{
+    name::Name,
     visit::{Folder, Mapper, Visitable},
-    Name,
 };
 use proc_macro2::Span;
 
-struct Deepen {
-    pub depth: usize,
-    pub by: usize,
+enum Direction {
+    Deepen,
+    Shallow,
+}
+struct RenameVars {
+    depth: usize,
+    by: usize,
+    direction: Direction,
 }
 
-impl Mapper for Deepen {
+impl Mapper for RenameVars {
     type Out = ();
 
     fn map_epsilon(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         _eps: &mut Epsilon,
     ) -> Self::Out {
     }
@@ -26,7 +34,7 @@ impl Mapper for Deepen {
     fn map_literal(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         _lit: &mut Literal,
     ) -> Self::Out {
     }
@@ -34,7 +42,7 @@ impl Mapper for Deepen {
     fn map_cat(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         cat: &mut Cat,
     ) -> Self::Out {
         cat.first.map(self);
@@ -46,7 +54,7 @@ impl Mapper for Deepen {
     fn map_alt(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         alt: &mut Alt,
     ) -> Self::Out {
         alt.first.map(self);
@@ -58,7 +66,7 @@ impl Mapper for Deepen {
     fn map_fix(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         fix: &mut Fix,
     ) -> Self::Out {
         fix.inner.map(self);
@@ -67,18 +75,21 @@ impl Mapper for Deepen {
     fn map_variable(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         var: &mut Variable,
     ) -> Self::Out {
         if var.index >= self.depth {
-            var.index += self.by;
+            match self.direction {
+                Direction::Deepen => var.index += self.by,
+                Direction::Shallow => var.index -= self.by,
+            }
         }
     }
 
     fn map_call(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         call: &mut Call,
     ) -> Self::Out {
         call.on.map(self);
@@ -90,24 +101,56 @@ impl Mapper for Deepen {
     fn map_lambda(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         lambda: &mut Lambda,
     ) -> Self::Out {
         self.depth += lambda.args.len();
         lambda.inner.map(self);
         self.depth -= lambda.args.len();
     }
+
+    fn map_let(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Span,
+        stmt: &mut Let,
+    ) -> Self::Out {
+        stmt.bound.map(self);
+        self.depth += 1;
+        stmt.body.map(self);
+        self.depth -= 1;
+    }
 }
 
+#[derive(Debug)]
 pub struct Substitute {
     pub index: usize,
     pub expr: NamedExpression,
 }
 
+impl Substitute {
+    fn with_args<V: Visitable>(&mut self, args: usize, visitable: V) -> <Self as Folder>::Out {
+        self.index += args;
+        self.expr.map(&mut RenameVars {
+            depth: 0,
+            by: args,
+            direction: Direction::Deepen,
+        });
+        let out = visitable.fold(self);
+        self.expr.map(&mut RenameVars {
+            depth: 0,
+            by: args,
+            direction: Direction::Shallow,
+        });
+        self.index -= args;
+        out
+    }
+}
+
 impl Folder for Substitute {
     type Out = NamedExpression;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
         NamedExpression {
             name,
             expr: eps.into(),
@@ -115,7 +158,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
         NamedExpression {
             name,
             expr: lit.into(),
@@ -123,7 +166,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, mut cat: Cat) -> Self::Out {
         cat.first = Box::new(cat.first.fold(self));
         cat.rest = cat
             .rest
@@ -137,7 +180,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, mut alt: Alt) -> Self::Out {
         alt.first = Box::new(alt.first.fold(self));
         alt.rest = alt
             .rest
@@ -151,7 +194,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, mut fix: Fix) -> Self::Out {
         fix.inner = Box::new(fix.inner.fold(self));
         NamedExpression {
             name,
@@ -163,11 +206,13 @@ impl Folder for Substitute {
     fn fold_variable(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: Variable,
     ) -> Self::Out {
         if var.index == self.index {
-            self.expr.clone()
+            let mut out = self.expr.clone();
+            out.name = Name::merge(out.name, name);
+            out
         } else {
             NamedExpression {
                 name,
@@ -184,7 +229,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
+    fn fold_call(&mut self, name: Option<Name>, span: Span, mut call: Call) -> Self::Out {
         call.on = Box::new(call.on.fold(self));
         call.args = call.args.into_iter().map(|e| e.fold(self)).collect();
         NamedExpression {
@@ -197,40 +242,36 @@ impl Folder for Substitute {
     fn fold_lambda(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         mut lambda: Lambda,
     ) -> Self::Out {
-        self.index += lambda.args.len();
-        lambda.inner = Box::new(lambda.inner.fold(self));
-        self.index -= lambda.args.len();
+        let depth = lambda.args.len();
+        lambda.inner = Box::new(self.with_args(depth, lambda.inner));
         NamedExpression {
             name,
             expr: lambda.into(),
             span,
         }
     }
-}
 
-pub struct Translate {
-    changed: bool,
-}
-
-impl Translate {
-    pub fn new() -> Self {
-        Self { changed: false }
+    fn fold_let(&mut self, name: Option<Name>, span: Span, mut stmt: Let) -> Self::Out {
+        stmt.bound = Box::new(stmt.bound.fold(self));
+        stmt.body = Box::new(self.with_args(1, stmt.body));
+        NamedExpression {
+            name,
+            expr: stmt.into(),
+            span,
+        }
     }
 }
 
-impl Default for Translate {
-    fn default() -> Self {
-        Self::new()
-    }
-}
+#[derive(Copy, Clone, Debug)]
+pub struct Reduce;
 
-impl Folder for Translate {
-    type Out = Result<NamedExpression, TranslateError>;
+impl Folder for Reduce {
+    type Out = Result<NamedExpression, ReductionError>;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
         Ok(NamedExpression {
             name,
             expr: eps.into(),
@@ -238,7 +279,7 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
         Ok(NamedExpression {
             name,
             expr: lit.into(),
@@ -246,7 +287,13 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, mut cat: Cat) -> Self::Out {
+        cat.first = Box::new(cat.first.fold(self)?);
+        cat.rest = cat
+            .rest
+            .into_iter()
+            .map(|(p, e)| Ok((p, e.fold(self)?)))
+            .collect::<Result<_, _>>()?;
         Ok(NamedExpression {
             name,
             expr: cat.into(),
@@ -254,7 +301,13 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, mut alt: Alt) -> Self::Out {
+        alt.first = Box::new(alt.first.fold(self)?);
+        alt.rest = alt
+            .rest
+            .into_iter()
+            .map(|(p, e)| Ok((p, e.fold(self)?)))
+            .collect::<Result<_, _>>()?;
         Ok(NamedExpression {
             name,
             expr: alt.into(),
@@ -262,7 +315,13 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, mut fix: Fix) -> Self::Out {
+        let mut inner = fix.inner.fold(self)?;
+        if let Expression::Lambda(mut l) = inner.expr {
+            l.inner = Box::new(l.inner.fold(self)?);
+            inner.expr = Expression::Lambda(l);
+        }
+        fix.inner = Box::new(inner);
         Ok(NamedExpression {
             name,
             expr: fix.into(),
@@ -273,7 +332,7 @@ impl Folder for Translate {
     fn fold_variable(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: Variable,
     ) -> Self::Out {
         Ok(NamedExpression {
@@ -283,21 +342,16 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out {
-        let mut on = *call.on;
-        self.changed = true;
-        while self.changed {
-            self.changed = false;
-            on = on.fold(self)?;
-        }
+    fn fold_call(&mut self, name: Option<Name>, span: Span, call: Call) -> Self::Out {
+        let on = call.on.fold(self)?;
 
         let lambda = on
             .expr
             .try_into_lambda()
-            .map_err(|on| TranslateError::CallNotAFunction { on, span })?;
+            .map_err(|on| ReductionError::CallNotAFunction { on, span })?;
 
         if lambda.args.len() != call.args.len() {
-            return Err(TranslateError::WrongArgCount {
+            return Err(ReductionError::WrongArgCount {
                 lambda,
                 args: call.args,
                 span,
@@ -307,33 +361,44 @@ impl Folder for Translate {
         let mut out = *lambda.inner;
 
         for ((i, mut arg), name) in call.args.into_iter().enumerate().zip(lambda.args).rev() {
-            arg.name = arg.name.or(Some(name));
-            arg.map(&mut Deepen { depth: 0, by: i });
+            arg.name = Name::merge(arg.name, Some(name));
+            arg.map(&mut RenameVars {
+                depth: 0,
+                by: i,
+                direction: Direction::Deepen,
+            });
             out = out.fold(&mut Substitute {
                 index: 0,
                 expr: arg,
             });
         }
 
-        self.changed = true;
-        while self.changed {
-            self.changed = false;
-            out = out.fold(self)?;
-        }
-
-        self.changed = true;
-        out.name = name.or(out.name);
-        out.span = span.or(out.span);
+        out = out.fold(self)?;
+        out.name = Name::merge_all(array::IntoIter::new([name, on.name, out.name]));
+        out.span = span;
         Ok(out)
     }
 
-    fn fold_lambda(&mut self, name: Option<Name>, span: Option<Span>, lambda: Lambda) -> Self::Out {
+    fn fold_lambda(&mut self, name: Option<Name>, span: Span, lambda: Lambda) -> Self::Out {
         Ok(NamedExpression {
             name,
             expr: lambda.into(),
             span,
         })
     }
+
+    fn fold_let(&mut self, name: Option<Name>, span: Span, stmt: Let) -> Self::Out {
+        let mut out = stmt
+            .body
+            .fold(&mut Substitute {
+                index: 0,
+                expr: *stmt.bound,
+            })
+            .fold(self)?;
+        out.name = Name::merge(out.name, name);
+        out.span = span;
+        Ok(out)
+    }
 }
 
 #[cfg(test)]
@@ -345,23 +410,23 @@ mod tests {
         let var = NamedExpression {
             name: None,
             expr: Variable { index: 0 }.into(),
-            span: None,
+            span: Span::call_site(),
         };
 
         let lambda = NamedExpression {
             name: None,
             expr: Lambda {
-                args: vec!["x".to_owned().into()],
+                args: vec![Name::new_variable("x".to_owned())],
                 inner: Box::new(var),
             }
             .into(),
-            span: None,
+            span: Span::call_site(),
         };
 
         let var = NamedExpression {
             name: None,
             expr: Variable { index }.into(),
-            span: None,
+            span: Span::call_site(),
         };
 
         NamedExpression {
@@ -371,14 +436,18 @@ mod tests {
                 args: vec![var],
             }
             .into(),
-            span: None,
+            span: Span::call_site(),
         }
     }
 
     #[test]
     fn deepen_lambda() {
         let mut expr = make_expr(0);
-        expr.map(&mut Deepen { depth: 0, by: 1 });
+        expr.map(&mut RenameVars {
+            depth: 0,
+            by: 1,
+            direction: Direction::Deepen,
+        });
         assert_eq!(expr, make_expr(1))
     }
 
@@ -390,22 +459,22 @@ mod tests {
             expr: NamedExpression {
                 name: None,
                 expr: Epsilon.into(),
-                span: None,
+                span: Span::call_site(),
             },
         });
         assert_eq!(expr, make_expr(0))
     }
 
     #[test]
-    fn translate_lambda() {
+    fn reduce_lambda() {
         let expr = make_expr(1);
-        let expr = expr.fold(&mut Translate::new()).unwrap();
+        let expr = expr.fold(&mut Reduce).unwrap();
         assert_eq!(
             expr,
             NamedExpression {
-                name: Some("x".to_owned().into()),
+                name: Some(Name::new_variable("x".to_owned())),
                 expr: Variable { index: 1 }.into(),
-                span: None
+                span: Span::call_site(),
             }
         )
     }
diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
index 79b4fac..029c10f 100644
--- a/src/chomp/mod.rs
+++ b/src/chomp/mod.rs
@@ -1,114 +1,7 @@
-use std::{fmt, hash};
-
-use heck::{CamelCase, SnakeCase};
-use proc_macro2::{Ident, Span};
-use syn::ext::IdentExt;
+use proc_macro2::Span;
 
 pub mod ast;
+pub mod name;
 pub mod set;
 pub mod typed;
 pub mod visit;
-
-#[derive(Clone, Debug)]
-pub enum Name {
-    Spanned(Ident),
-    Spanless(String),
-}
-
-impl Name {
-    pub fn span(&self) -> Option<Span> {
-        match self {
-            Self::Spanned(i) => Some(i.span()),
-            Self::Spanless(_) => None,
-        }
-    }
-
-    pub fn into_ident(self, span: Span) -> Ident {
-        match self {
-            Self::Spanned(i) => i,
-            Self::Spanless(s) => Ident::new(&s, span),
-        }
-    }
-}
-
-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) {
-            (Self::Spanned(me), Self::Spanned(them)) => me == them,
-            (Self::Spanned(me), Self::Spanless(them)) => me.unraw() == them,
-            (Self::Spanless(me), Self::Spanned(them)) => them.unraw() == me,
-            (Self::Spanless(me), Self::Spanless(them)) => me == them,
-        }
-    }
-}
-
-impl<T: AsRef<str>> PartialEq<T> for Name {
-    fn eq(&self, other: &T) -> bool {
-        match self {
-            Name::Spanned(me) => me.unraw() == other,
-            Name::Spanless(me) => me == other.as_ref(),
-        }
-    }
-}
-
-impl Eq for Name {}
-
-impl hash::Hash for Name {
-    fn hash<H: hash::Hasher>(&self, state: &mut H) {
-        match self {
-            Self::Spanned(i) => i.unraw().to_string().hash(state),
-            Self::Spanless(s) => s.hash(state),
-        }
-    }
-}
-
-impl fmt::Display for Name {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Name::Spanned(i) => i.fmt(f),
-            Name::Spanless(s) => s.fmt(f),
-        }
-    }
-}
-
-impl From<Ident> for Name {
-    fn from(ident: Ident) -> Self {
-        Self::Spanned(ident)
-    }
-}
-
-impl From<String> for Name {
-    fn from(string: String) -> Self {
-        Self::Spanless(string)
-    }
-}
diff --git a/src/chomp/name.rs b/src/chomp/name.rs
new file mode 100644
index 0000000..450b6e9
--- /dev/null
+++ b/src/chomp/name.rs
@@ -0,0 +1,217 @@
+use std::{
+    array::IntoIter,
+    cmp::{self, Ordering},
+    fmt, hash,
+};
+
+use heck::{CamelCase, SnakeCase};
+use proc_macro2::{Ident, Span};
+use syn::{ext::IdentExt, spanned::Spanned};
+
+#[derive(Clone, Debug)]
+pub enum Content {
+    Spanned(Ident),
+    Spanless(String),
+}
+
+impl Spanned for Content {
+    fn span(&self) -> Span {
+        match self {
+            Content::Spanned(i) => i.span(),
+            Content::Spanless(_) => Span::call_site(),
+        }
+    }
+}
+
+impl From<Content> for Ident {
+    fn from(content: Content) -> Self {
+        match content {
+            Content::Spanned(i) => i,
+            Content::Spanless(s) => Ident::new(&s, Span::call_site()),
+        }
+    }
+}
+
+impl CamelCase for Content {
+    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()
+            }
+            Self::Spanless(name) => name.to_camel_case().into(),
+        }
+    }
+}
+
+impl SnakeCase for Content {
+    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()
+            }
+            Self::Spanless(name) => name.to_snake_case().into(),
+        }
+    }
+}
+
+impl PartialEq for Content {
+    fn eq(&self, other: &Self) -> bool {
+        match (self, other) {
+            (Self::Spanned(me), Self::Spanned(them)) => me == them,
+            (Self::Spanned(me), Self::Spanless(them)) => me.unraw() == them,
+            (Self::Spanless(me), Self::Spanned(them)) => them.unraw() == me,
+            (Self::Spanless(me), Self::Spanless(them)) => me == them,
+        }
+    }
+}
+
+impl<T: AsRef<str>> PartialEq<T> for Content {
+    fn eq(&self, other: &T) -> bool {
+        match self {
+            Self::Spanned(me) => me.unraw() == other,
+            Self::Spanless(me) => me == other.as_ref(),
+        }
+    }
+}
+
+impl Eq for Content {}
+
+impl hash::Hash for Content {
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        match self {
+            Self::Spanned(i) => i.unraw().to_string().hash(state),
+            Self::Spanless(s) => s.hash(state),
+        }
+    }
+}
+
+impl fmt::Display for Content {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Spanned(i) => i.fmt(f),
+            Self::Spanless(s) => s.fmt(f),
+        }
+    }
+}
+
+impl From<Ident> for Content {
+    fn from(ident: Ident) -> Self {
+        Self::Spanned(ident)
+    }
+}
+
+impl From<String> for Content {
+    fn from(string: String) -> Self {
+        Self::Spanless(string)
+    }
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+pub enum Kind {
+    Label,
+    Let,
+    Variable,
+}
+
+impl PartialOrd for Kind {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(match (self, other) {
+            (Kind::Label, Kind::Label)
+            | (Kind::Let, Kind::Let)
+            | (Kind::Variable, Kind::Variable) => Ordering::Equal,
+            (Kind::Label, Kind::Let)
+            | (Kind::Label, Kind::Variable)
+            | (Kind::Let, Kind::Variable) => Ordering::Greater,
+            (Kind::Let, Kind::Label)
+            | (Kind::Variable, Kind::Label)
+            | (Kind::Variable, Kind::Let) => Ordering::Less,
+        })
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct Name {
+    pub content: Content,
+    kind: Kind,
+}
+
+impl Name {
+    pub fn new_variable<T: Into<Content>>(content: T) -> Self {
+        Self {
+            content: content.into(),
+            kind: Kind::Variable,
+        }
+    }
+
+    pub fn new_let<T: Into<Content>>(content: T) -> Self {
+        Self {
+            content: content.into(),
+            kind: Kind::Let,
+        }
+    }
+
+    pub fn new_label<T: Into<Content>>(content: T) -> Self {
+        Self {
+            content: content.into(),
+            kind: Kind::Label,
+        }
+    }
+
+    pub fn merge(this: Option<Self>, that: Option<Self>) -> Option<Self> {
+        match (this, that) {
+            (None, that) => that,
+            (Some(this), None) => Some(this),
+            (Some(this), Some(that)) => {
+                if this.kind >= that.kind {
+                    Some(this)
+                } else {
+                    Some(that)
+                }
+            }
+        }
+    }
+
+    pub fn merge_all<I: IntoIterator<Item = Option<Self>>>(iter: I) -> Option<Self> {
+        iter.into_iter().fold(None, Self::merge)
+    }
+}
+
+impl Spanned for Name {
+    fn span(&self) -> Span {
+        self.content.span()
+    }
+}
+
+impl From<Name> for Ident {
+    fn from(name: Name) -> Self {
+        name.content.into()
+    }
+}
+
+impl CamelCase for Name {
+    fn to_camel_case(&self) -> Self::Owned {
+        Self {
+            content: self.content.to_camel_case(),
+            kind: self.kind,
+        }
+    }
+}
+
+impl SnakeCase for Name {
+    fn to_snake_case(&self) -> Self::Owned {
+        Self {
+            content: self.content.to_snake_case(),
+            kind: self.kind,
+        }
+    }
+}
+
+impl fmt::Display for Name {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.content.fmt(f)
+    }
+}
diff --git a/src/chomp/set.rs b/src/chomp/set.rs
index 0661ab6..db533da 100644
--- a/src/chomp/set.rs
+++ b/src/chomp/set.rs
@@ -21,15 +21,12 @@ impl FirstSet {
         self.inner.is_empty()
     }
 
-    pub fn union(mut self, mut other: Self) -> Self {
+    pub fn union(&mut self, mut other: Self) {
         self.inner.append(&mut other.inner);
-        self
     }
 
-    pub fn intersect(&self, other: &Self) -> Self {
-        Self {
-            inner: self.inner.intersection(&other.inner).copied().collect(),
-        }
+    pub fn disjoint(&self, other: &Self) -> bool {
+        self.inner.intersection(&other.inner).next().is_none()
     }
 }
 
@@ -57,26 +54,16 @@ impl FlastSet {
         self.inner.is_empty()
     }
 
-    pub fn union_first(mut self, mut other: FirstSet) -> Self {
+    pub fn union_first(&mut self, mut other: FirstSet) {
         self.inner.append(&mut other.inner);
-        self
     }
 
-    pub fn union(mut self, mut other: Self) -> Self {
+    pub fn union(&mut self, mut other: 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(),
-        }
+    pub fn disjoint(&self, other: &FirstSet) -> bool {
+        self.inner.intersection(&other.inner).next().is_none()
     }
 }
 
diff --git a/src/chomp/typed/context.rs b/src/chomp/typed/context.rs
index f3263ce..7ac4ae0 100644
--- a/src/chomp/typed/context.rs
+++ b/src/chomp/typed/context.rs
@@ -30,16 +30,11 @@ impl Context {
             .nth_back(var.index)
             .ok_or(GetVariableError::FreeVariable)
             .and_then(|ty| {
-                self.unguard_points
-                    .last()
-                    .and_then(|point| {
-                        if point + var.index >= self.vars.len() {
-                            Some(ty)
-                        } else {
-                            None
-                        }
-                    })
-                    .ok_or(GetVariableError::GuardedVariable)
+                if self.unguard_points.last().unwrap_or(&0) + var.index >= self.vars.len() {
+                    Ok(ty)
+                } else {
+                    Err(GetVariableError::GuardedVariable)
+                }
             })
     }
 
diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs
index 5c1e21e..48bfa25 100644
--- a/src/chomp/typed/error.rs
+++ b/src/chomp/typed/error.rs
@@ -5,27 +5,19 @@ use std::{
 
 use proc_macro2::Span;
 
-use crate::chomp::{ast::Variable, Name};
+use crate::chomp::{name::Name, ast::{Call, Fix, Lambda, Let, Variable}};
 
-use super::{context::GetVariableError, TypedExpression};
+use super::{Type, TypedExpression, context::GetVariableError};
 
 /// 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 span: Span,
     pub name: Option<Name>,
 }
 
-impl From<VariableError> for syn::Error {
-    fn from(other: VariableError) -> Self {
-        let msg = other.to_string();
-        let span = other.span;
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
-    }
-}
-
 impl Display for VariableError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match &self.inner {
@@ -47,24 +39,20 @@ impl Error for VariableError {}
 pub enum CatError {
     FirstNullable {
         expr: TypedExpression,
-        punct: Option<Span>,
+        punct: Span,
     },
     FirstFlastOverlap {
-        first: Vec<TypedExpression>,
-        punct: Option<Span>,
+        front_ty: Type,
+        punct: Span,
         next: TypedExpression,
     },
 }
 
-impl From<CatError> for syn::Error {
-    fn from(other: CatError) -> Self {
-        let msg = other.to_string();
-        let span = match other {
-            CatError::FirstNullable { punct, .. } | CatError::FirstFlastOverlap { punct, .. } => {
-                punct
-            }
-        };
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
+impl CatError {
+    pub fn span(&self) -> Span {
+        match self {
+            Self::FirstNullable { punct, .. } | Self::FirstFlastOverlap { punct, .. } => *punct,
+        }
     }
 }
 
@@ -84,24 +72,22 @@ impl Error for CatError {}
 #[derive(Debug)]
 pub enum AltError {
     BothNullable {
-        left: Vec<TypedExpression>,
-        punct: Option<Span>,
+        left_ty: Type,
+        punct: Span,
         right: TypedExpression,
     },
     FirstOverlap {
-        left: Vec<TypedExpression>,
-        punct: Option<Span>,
+        left_ty: Type,
+        punct: Span,
         right: TypedExpression,
     },
 }
 
-impl From<AltError> for syn::Error {
-    fn from(other: AltError) -> Self {
-        let msg = other.to_string();
-        let span = match other {
-            AltError::BothNullable { punct, .. } | AltError::FirstOverlap { punct, .. } => punct,
-        };
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
+impl AltError {
+    pub fn span(&self) -> Span {
+        match self {
+            Self::BothNullable { punct, .. } | Self::FirstOverlap { punct, .. } => *punct,
+        }
     }
 }
 
@@ -121,6 +107,24 @@ pub enum TypeError {
     Cat(CatError),
     Alt(AltError),
     Variable(VariableError),
+    UnexpectedCall { span: Span, call: Call },
+    UnexpectedLambda { span: Span, lambda: Lambda },
+    UnexpectedLet { span: Span, stmt: Let },
+    ExpectedLambda {span: Span, fix: Fix },
+}
+
+impl TypeError {
+    pub fn span(&self) -> Span {
+        match self {
+            TypeError::Cat(c) => c.span(),
+            TypeError::Alt(a) => a.span(),
+            TypeError::Variable(v) => v.span,
+            TypeError::UnexpectedCall { span, .. }
+            | TypeError::UnexpectedLambda { span, .. }
+            | TypeError::UnexpectedLet { span, .. }
+            | TypeError::ExpectedLambda { span, .. } => *span,
+        }
+    }
 }
 
 impl From<CatError> for TypeError {
@@ -143,11 +147,9 @@ impl From<VariableError> for TypeError {
 
 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(),
-        }
+        let span = other.span();
+        let msg = format!("{}", other);
+        Self::new(span, msg)
     }
 }
 
@@ -157,6 +159,19 @@ impl Display for TypeError {
             Self::Cat(e) => e.fmt(f),
             Self::Alt(e) => e.fmt(f),
             Self::Variable(e) => e.fmt(f),
+
+            Self::UnexpectedCall { .. } => {
+                write!(f, "unexpected call")
+            }
+            Self::UnexpectedLambda { .. } => {
+                write!(f, "unexpected lambda")
+            }
+            Self::UnexpectedLet { .. } => {
+                write!(f, "unexpected let")
+            }
+            Self::ExpectedLambda { .. } => {
+                write!(f, "expected a lambda expression")
+            }
         }
     }
 }
diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs
index e2c2198..bc2baea 100644
--- a/src/chomp/typed/infer.rs
+++ b/src/chomp/typed/infer.rs
@@ -1,8 +1,18 @@
+use std::{array, iter};
+
 use proc_macro2::Span;
 
-use crate::chomp::{Name, ast::{Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, substitute::Translate}, visit::{Folder, Visitable}};
+use crate::chomp::{
+    ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal, Variable},
+    name::Name,
+    visit::{Folder, Visitable},
+};
 
-use super::{Type, Typed, TypedExpression, context::Context, error::{TypeError, VariableError}};
+use super::{
+    context::Context,
+    error::{AltError, CatError, TypeError, VariableError},
+    Type, Typed, TypedExpression,
+};
 
 #[derive(Debug)]
 pub struct TypeInfer<'a> {
@@ -12,7 +22,7 @@ pub struct TypeInfer<'a> {
 impl Folder for TypeInfer<'_> {
     type Out = Result<TypedExpression, TypeError>;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
         Ok(TypedExpression {
             inner: super::Epsilon::from(eps).into(),
             name,
@@ -20,7 +30,7 @@ impl Folder for TypeInfer<'_> {
         })
     }
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
         Ok(TypedExpression {
             inner: super::Literal::from(lit).into(),
             name,
@@ -28,47 +38,99 @@ impl Folder for TypeInfer<'_> {
         })
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Out {
         let first = cat.first.fold(self)?;
+
+        if first.get_type().nullable() {
+            let punct = cat.rest.into_iter().next().map(|(p, _)| p).unwrap_or_else(Span::call_site);
+            return Err(CatError::FirstNullable { expr: first, punct }.into());
+        }
+
         let rest = cat.rest;
-        self.context
-            .with_unguard(|context| -> Result<TypedExpression, TypeError> {
-                let mut infer = TypeInfer { context };
-                let rest = rest
-                    .into_iter()
-                    .map(|(punct, term)| -> Result<_, TypeError> {
-                        Ok((punct, term.fold(&mut infer)?))
-                    })
-                    .collect::<Result<Vec<_>, _>>()?;
-                Ok(TypedExpression {
-                    inner: super::Cat::new(first, rest)?.into(),
-                    name,
-                    span,
+        let mut ty = first.get_type().clone();
+        let terms = self.context.with_unguard(|context| {
+            let mut infer = TypeInfer { context };
+            rest.into_iter()
+                .map(|(punct, right)| {
+                    let right = right.fold(&mut infer)?;
+                    if ty.flast_set().disjoint(right.get_type().first_set()) {
+                        ty.cat(right.get_type().clone());
+                        Ok(right)
+                    } else {
+                        Err(CatError::FirstFlastOverlap {
+                            front_ty: ty.clone(),
+                            punct,
+                            next: right,
+                        }
+                        .into())
+                    }
                 })
-            })
+                .collect::<Result<Vec<_>, TypeError>>()
+        })?;
+        Ok(TypedExpression {
+            inner: super::Cat {
+                terms: iter::once(first).chain(terms).collect(),
+                ty,
+            }
+            .into(),
+            name,
+            span,
+        })
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Out {
         let first = alt.first.fold(self)?;
-        let rest = alt
+        let mut ty = first.get_type().clone();
+        let terms = alt
             .rest
             .into_iter()
-            .map(|(punct, term)| -> Result<_, TypeError> { Ok((punct, term.fold(self)?)) })
-            .collect::<Result<Vec<_>, _>>()?;
+            .map(|(punct, right)| {
+                let right = right.fold(self)?;
+                if ty.nullable() && right.get_type().nullable() {
+                    Err(AltError::BothNullable {
+                        left_ty: ty.clone(),
+                        punct,
+                        right,
+                    }
+                    .into())
+                } else if ty.first_set().disjoint(right.get_type().first_set()) {
+                    ty.alt(right.get_type().clone());
+                    Ok(right)
+                } else {
+                    Err(AltError::FirstOverlap {
+                        left_ty: ty.clone(),
+                        punct,
+                        right,
+                    }
+                    .into())
+                }
+            })
+            .collect::<Result<Vec<_>, TypeError>>()?;
         Ok(TypedExpression {
-            inner: super::Alt::new(first, rest)?.into(),
+            inner: super::Alt {
+                terms: iter::once(first).chain(terms).collect(),
+                ty,
+            }
+            .into(),
             name,
             span,
         })
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Out {
         let mut ty = Type::default();
+        let body = if let Expression::Lambda(l) = fix.inner.expr {
+            let mut body = *l.inner;
+            body.name = Name::merge_all(array::IntoIter::new([fix.inner.name, body.name, name.clone()]));
+            body
+        } else {
+            return Err(TypeError::ExpectedLambda { span, fix });
+        };
 
         loop {
             let last = ty;
             let res = self.context.with_variable_type(last.clone(), |context| {
-                fix.inner.clone().fold(&mut TypeInfer { context })
+                body.clone().fold(&mut TypeInfer { context })
             })?;
             ty = res.get_type().clone();
 
@@ -88,7 +150,7 @@ impl Folder for TypeInfer<'_> {
     fn fold_variable(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: Variable,
     ) -> Self::Out {
         let ty = match self.context.get_variable_type(var) {
@@ -110,18 +172,101 @@ impl Folder for TypeInfer<'_> {
         })
     }
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out {
-        let translated = NamedExpression { name, expr: call.into(), span}.fold(&mut Translate::new())?;
-        let inner = translated.fold(self)?;
-        todo!()
+    fn fold_call(&mut self, _name: Option<Name>, span: Span, call: Call) -> Self::Out {
+        Err(TypeError::UnexpectedCall { span, call })
     }
 
     fn fold_lambda(
         &mut self,
         _name: Option<Name>,
-        _span: Option<Span>,
-        _lambda: Lambda,
+        span: Span,
+        lambda: Lambda,
     ) -> Self::Out {
-        unimplemented!()
+        Err(TypeError::UnexpectedLambda { span, lambda })
+    }
+
+    fn fold_let(&mut self, _name: Option<Name>, span: Span, stmt: Let) -> Self::Out {
+        Err(TypeError::UnexpectedLet { span, stmt })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::chomp::{ast::NamedExpression, typed::RawTypedExpression};
+
+    use super::*;
+
+    #[test]
+    fn cat_uses_all() {
+        let ast = Cat {
+            first: Box::new(NamedExpression {
+                name: None,
+                expr: "a".to_owned().into(),
+                span: Span::call_site(),
+            }),
+            rest: vec![(
+                Span::call_site(),
+                NamedExpression {
+                    name: None,
+                    expr: "b".to_owned().into(),
+                    span: Span::call_site(),
+                },
+            )],
+        };
+
+        let typed = NamedExpression {
+            name: None,
+            expr: ast.into(),
+            span: Span::call_site(),
+        }
+        .fold(&mut TypeInfer {
+            context: &mut Context::default(),
+        })
+        .unwrap();
+        match typed.inner {
+            RawTypedExpression::Cat(super::super::Cat { terms, .. }) => assert_eq!(terms.len(), 2),
+            RawTypedExpression::Epsilon(_)
+            | RawTypedExpression::Literal(_)
+            | RawTypedExpression::Alt(_)
+            | RawTypedExpression::Fix(_)
+            | RawTypedExpression::Variable(_) => panic!("Cat should type check to Cat"),
+        };
+    }
+
+    #[test]
+    fn alt_uses_all() {
+        let ast = Alt {
+            first: Box::new(NamedExpression {
+                name: None,
+                expr: "a".to_owned().into(),
+                span: Span::call_site(),
+            }),
+            rest: vec![(
+                Span::call_site(),
+                NamedExpression {
+                    name: None,
+                    expr: "b".to_owned().into(),
+                    span: Span::call_site(),
+                },
+            )],
+        };
+
+        let typed = NamedExpression {
+            name: None,
+            expr: ast.into(),
+            span: Span::call_site(),
+        }
+        .fold(&mut TypeInfer {
+            context: &mut Context::default(),
+        })
+        .unwrap();
+        match typed.inner {
+            RawTypedExpression::Alt(super::super::Alt { terms, .. }) => assert_eq!(terms.len(), 2),
+            RawTypedExpression::Epsilon(_)
+            | RawTypedExpression::Literal(_)
+            | RawTypedExpression::Cat(_)
+            | RawTypedExpression::Fix(_)
+            | RawTypedExpression::Variable(_) => panic!("Alt should type check to Alt"),
+        };
     }
 }
diff --git a/src/chomp/typed/lower.rs b/src/chomp/typed/lower.rs
index 37589a1..03237de 100644
--- a/src/chomp/typed/lower.rs
+++ b/src/chomp/typed/lower.rs
@@ -1,6 +1,6 @@
 use proc_macro2::Span;
 
-use crate::chomp::Name;
+use crate::chomp::name::Name;
 
 use super::{Alt, Cat, Epsilon, Fix, Literal, RawTypedExpression, TypedExpression, Variable};
 
@@ -8,19 +8,19 @@ 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_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Id;
 
-    fn gen_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Id;
+    fn gen_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Id;
 
-    fn gen_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Id;
+    fn gen_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Id;
 
-    fn gen_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Id;
+    fn gen_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Id;
 
-    fn gen_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Id;
+    fn gen_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Id;
 
-    fn gen_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable) -> Self::Id;
+    fn gen_variable(&mut self, name: Option<Name>, span: Span, var: Variable) -> Self::Id;
 
-    fn emit_code(self, name: Option<Name>, span: Option<Span>, id: Self::Id) -> Self::Code;
+    fn emit_code(self, name: Option<Name>, span: Span, id: Self::Id) -> Self::Code;
 }
 
 pub trait GenerateCode {
diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs
index cddb05a..f1f6967 100644
--- a/src/chomp/typed/mod.rs
+++ b/src/chomp/typed/mod.rs
@@ -5,7 +5,7 @@ use proc_macro2::Span;
 use super::{
     ast,
     set::{FirstSet, FlastSet},
-    Name,
+    name::Name,
 };
 
 pub mod context;
@@ -14,7 +14,6 @@ pub mod lower;
 
 mod infer;
 
-use self::error::{AltError, CatError};
 pub use self::infer::TypeInfer;
 
 #[derive(Debug, Default, Clone, Eq, Hash, PartialEq)]
@@ -53,28 +52,25 @@ impl Type {
         &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 cat(&mut self, other: Self) {
+        if self.nullable {
+            self.first_set.union(other.first_set.clone())
         }
-    }
 
-    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),
+        if other.nullable {
+            self.flast_set.union_first(other.first_set);
+            self.flast_set.union(other.flast_set);
+        } else {
+            self.flast_set = other.flast_set;
         }
+
+        self.nullable &= other.nullable;
+    }
+
+    pub fn alt(&mut self, other: Self) {
+        self.nullable |= other.nullable;
+        self.first_set.union(other.first_set);
+        self.flast_set.union(other.flast_set);
     }
 }
 
@@ -122,43 +118,6 @@ pub struct Cat {
     ty: Type,
 }
 
-impl Cat {
-    fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
-        first: TypedExpression,
-        rest: I,
-    ) -> Result<Self, CatError> {
-        if first.get_type().nullable() {
-            return Err(CatError::FirstNullable {
-                expr: first,
-                punct: todo!(),
-            });
-        }
-
-        rest.into_iter()
-            .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()
-                    {
-                        let ty = ty.cat(right.get_type().clone());
-                        terms.push(right);
-                        Ok((ty, terms))
-                    } else {
-                        Err(CatError::FirstFlastOverlap {
-                            first: terms,
-                            punct,
-                            next: right,
-                        })
-                    }
-                },
-            )
-            .map(|(ty, terms)| Self { ty, terms })
-    }
-}
-
 impl IntoIterator for Cat {
     type Item = TypedExpression;
 
@@ -175,42 +134,6 @@ pub struct Alt {
     ty: Type,
 }
 
-impl Alt {
-    pub fn new<I: IntoIterator<Item = (Option<Span>, TypedExpression)>>(
-        first: TypedExpression,
-        rest: I,
-    ) -> Result<Self, AltError> {
-        rest.into_iter()
-            .try_fold(
-                (first.get_type().clone(), vec![first]),
-                |(ty, mut terms), (punct, right)| {
-                    if ty.nullable() && right.get_type().nullable() {
-                        Err(AltError::BothNullable {
-                            left: terms,
-                            punct,
-                            right,
-                        })
-                    } else if ty
-                        .first_set()
-                        .intersect(right.get_type().first_set())
-                        .is_empty()
-                    {
-                        let ty = ty.alt(right.get_type().clone());
-                        terms.push(right);
-                        Ok((ty, terms))
-                    } else {
-                        Err(AltError::FirstOverlap {
-                            left: terms,
-                            punct,
-                            right,
-                        })
-                    }
-                },
-            )
-            .map(|(ty, terms)| Self { ty, terms })
-    }
-}
-
 impl IntoIterator for Alt {
     type Item = TypedExpression;
 
@@ -245,14 +168,6 @@ impl Variable {
 }
 
 #[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Call {
-    ty: Type,
-}
-
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
-pub struct Lambda {}
-
-#[derive(Clone, Debug, Eq, Hash, PartialEq)]
 enum RawTypedExpression {
     Epsilon(Epsilon),
     Literal(Literal),
@@ -260,8 +175,6 @@ enum RawTypedExpression {
     Alt(Alt),
     Fix(Fix),
     Variable(Variable),
-    Call(Call),
-    Lambda(Lambda),
 }
 
 impl From<Epsilon> for RawTypedExpression {
@@ -304,7 +217,7 @@ impl From<Variable> for RawTypedExpression {
 pub struct TypedExpression {
     inner: RawTypedExpression,
     pub name: Option<Name>,
-    pub span: Option<Span>,
+    pub span: Span,
 }
 
 impl PartialEq for TypedExpression {
@@ -360,3 +273,20 @@ impl Typed for TypedExpression {
         }
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn cat_right() {
+        let epsilon = Type { nullable: true, ..Type::default()};
+        let mut x = Type::of_str("a");
+        x.cat(Type::of_str("b"));
+        assert_eq!(x, Type::of_str("a"));
+        x.cat(Type::default());
+        assert_eq!(x, Type::of_str("a"));
+        x.cat(epsilon);
+        assert_eq!(x, Type::of_str("a"));
+    }
+}
diff --git a/src/chomp/visit.rs b/src/chomp/visit.rs
index 7e716d3..b37909d 100644
--- a/src/chomp/visit.rs
+++ b/src/chomp/visit.rs
@@ -1,113 +1,81 @@
 use proc_macro2::Span;
 
 use super::{
-    ast::{Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Literal, NamedExpression, Variable},
-    Name,
+    ast::{
+        Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal, NamedExpression, Variable,
+    },
+    name::Name,
 };
 
 pub trait Visitor {
     type Out;
-    fn visit_epsilon(
-        &mut self,
-        name: Option<&Name>,
-        span: Option<Span>,
-        eps: &Epsilon,
-    ) -> Self::Out;
+    fn visit_epsilon(&mut self, name: Option<&Name>, span: Span, eps: &Epsilon) -> Self::Out;
 
-    fn visit_literal(
-        &mut self,
-        name: Option<&Name>,
-        span: Option<Span>,
-        lit: &Literal,
-    ) -> Self::Out;
+    fn visit_literal(&mut self, name: Option<&Name>, span: Span, lit: &Literal) -> Self::Out;
 
-    fn visit_cat(&mut self, name: Option<&Name>, span: Option<Span>, cat: &Cat) -> Self::Out;
+    fn visit_cat(&mut self, name: Option<&Name>, span: Span, cat: &Cat) -> Self::Out;
 
-    fn visit_alt(&mut self, name: Option<&Name>, span: Option<Span>, alt: &Alt) -> Self::Out;
+    fn visit_alt(&mut self, name: Option<&Name>, span: Span, alt: &Alt) -> Self::Out;
 
-    fn visit_fix(&mut self, name: Option<&Name>, span: Option<Span>, fix: &Fix) -> Self::Out;
+    fn visit_fix(&mut self, name: Option<&Name>, span: Span, fix: &Fix) -> Self::Out;
 
-    fn visit_variable(
-        &mut self,
-        name: Option<&Name>,
-        span: Option<Span>,
-        var: &Variable,
-    ) -> Self::Out;
+    fn visit_variable(&mut self, name: Option<&Name>, span: Span, var: &Variable) -> Self::Out;
 
-    fn visit_call(&mut self, name: Option<&Name>, span: Option<Span>, call: &Call) -> Self::Out;
+    fn visit_call(&mut self, name: Option<&Name>, span: Span, call: &Call) -> Self::Out;
 
-    fn visit_lambda(
-        &mut self,
-        name: Option<&Name>,
-        span: Option<Span>,
-        lambda: &Lambda,
-    ) -> Self::Out;
+    fn visit_lambda(&mut self, name: Option<&Name>, span: Span, lambda: &Lambda) -> Self::Out;
+
+    fn visit_let(&mut self, name: Option<&Name>, span: Span, stmt: &Let) -> Self::Out;
 }
 
 pub trait Mapper {
     type Out;
 
-    fn map_epsilon(
-        &mut self,
-        name: &mut Option<Name>,
-        span: Option<Span>,
-        eps: &mut Epsilon,
-    ) -> Self::Out;
+    fn map_epsilon(&mut self, name: &mut Option<Name>, span: 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_literal(&mut self, name: &mut Option<Name>, span: 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_cat(&mut self, name: &mut Option<Name>, span: 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_alt(&mut self, name: &mut Option<Name>, span: 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_fix(&mut self, name: &mut Option<Name>, span: Span, fix: &mut Fix) -> Self::Out;
 
     fn map_variable(
         &mut self,
         name: &mut Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: &mut Variable,
     ) -> Self::Out;
 
-    fn map_call(
-        &mut self,
-        name: &mut Option<Name>,
-        span: Option<Span>,
-        call: &mut Call,
-    ) -> Self::Out;
+    fn map_call(&mut self, name: &mut Option<Name>, span: Span, call: &mut Call) -> Self::Out;
 
-    fn map_lambda(
-        &mut self,
-        name: &mut Option<Name>,
-        span: Option<Span>,
-        lambda: &mut Lambda,
-    ) -> Self::Out;
+    fn map_lambda(&mut self, name: &mut Option<Name>, span: Span, lambda: &mut Lambda)
+        -> Self::Out;
+
+    fn map_let(&mut self, name: &mut Option<Name>, span: Span, stmt: &mut Let) -> Self::Out;
 }
 
 pub trait Folder {
     type Out;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out;
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out;
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out;
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out;
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out;
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, cat: Cat) -> Self::Out;
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out;
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, alt: Alt) -> Self::Out;
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out;
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, fix: Fix) -> Self::Out;
 
-    fn fold_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable)
-        -> Self::Out;
+    fn fold_variable(&mut self, name: Option<Name>, span: Span, var: Variable) -> Self::Out;
+
+    fn fold_call(&mut self, name: Option<Name>, span: Span, call: Call) -> Self::Out;
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out;
+    fn fold_lambda(&mut self, name: Option<Name>, span: Span, lambda: Lambda) -> Self::Out;
 
-    fn fold_lambda(&mut self, name: Option<Name>, span: Option<Span>, lambda: Lambda) -> Self::Out;
+    fn fold_let(&mut self, name: Option<Name>, span: Span, stmt: Let) -> Self::Out;
 }
 
 pub trait Visitable {
@@ -118,6 +86,20 @@ pub trait Visitable {
     fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out;
 }
 
+impl<T: Visitable> Visitable for Box<T> {
+    fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
+        self.as_ref().visit(visitor)
+    }
+
+    fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
+        self.as_mut().map(mapper)
+    }
+
+    fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
+        (*self).fold(folder)
+    }
+}
+
 impl Visitable for NamedExpression {
     fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
         match &self.expr {
@@ -129,6 +111,7 @@ impl Visitable for NamedExpression {
             Expression::Variable(v) => visitor.visit_variable(self.name.as_ref(), self.span, v),
             Expression::Call(c) => visitor.visit_call(self.name.as_ref(), self.span, c),
             Expression::Lambda(l) => visitor.visit_lambda(self.name.as_ref(), self.span, l),
+            Expression::Let(l) => visitor.visit_let(self.name.as_ref(), self.span, l),
         }
     }
 
@@ -142,6 +125,7 @@ impl Visitable for NamedExpression {
             Expression::Variable(v) => mapper.map_variable(&mut self.name, self.span, v),
             Expression::Call(c) => mapper.map_call(&mut self.name, self.span, c),
             Expression::Lambda(l) => mapper.map_lambda(&mut self.name, self.span, l),
+            Expression::Let(l) => mapper.map_let(&mut self.name, self.span, l),
         }
     }
 
@@ -155,6 +139,7 @@ impl Visitable for NamedExpression {
             Expression::Variable(v) => folder.fold_variable(self.name, self.span, v),
             Expression::Call(c) => folder.fold_call(self.name, self.span, c),
             Expression::Lambda(l) => folder.fold_lambda(self.name, self.span, l),
+            Expression::Let(l) => folder.fold_let(self.name, self.span, l),
         }
     }
 }