Make some progress, I guesstypes

11 files changed, 454 insertions, 284 deletions

diff --git a/autochomp/src/main.rs b/autochomp/src/main.rs
index cbc0646..e1faafc 100644
--- a/autochomp/src/main.rs
+++ b/autochomp/src/main.rs
@@ -7,7 +7,7 @@ use std::{
 use chewed::{IterWrapper, Parser};
 use chomp::{
     chomp::{
-        ast::substitute::InlineCalls,
+        ast::substitute::InlineGlobal,
         typed::{
             context::Context,
             lower::{Backend, GenerateCode},
@@ -32,7 +32,7 @@ fn main() {
         .and_then(|(funs, goal)| {
             funs.into_iter()
                 .try_rfold(goal, |goal, function| {
-                    goal.fold(&mut InlineCalls { function })
+                    goal.fold(&mut InlineGlobal { function })
                 })
                 .map_err(|e| Box::new(e) as Box<dyn Error>)
         })
diff --git a/chomp-macro/src/lib.rs b/chomp-macro/src/lib.rs
index 91e1527..864a491 100644
--- a/chomp-macro/src/lib.rs
+++ b/chomp-macro/src/lib.rs
@@ -1,6 +1,6 @@
 use chomp::{
     chomp::{
-        ast::substitute::InlineCalls,
+        ast::substitute::InlineGlobal,
         typed::{
             context::Context,
             lower::{Backend, GenerateCode},
@@ -21,7 +21,7 @@ pub fn nibble(item: TokenStream) -> TokenStream {
         .and_then(|(funs, goal)| {
             funs.into_iter()
                 .try_rfold(goal, |goal, function| {
-                    goal.fold(&mut InlineCalls { function })
+                    goal.fold(&mut InlineGlobal { function })
                 })
                 .map_err(Error::from)
         })
diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs
index e4ed2fc..4a202e0 100644
--- a/src/chomp/ast/mod.rs
+++ b/src/chomp/ast/mod.rs
@@ -102,55 +102,74 @@ impl PartialEq for Fix {
 impl Eq for Fix {}
 
 #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
-pub struct Variable {
+pub struct Parameter {
     pub index: usize,
 }
 
-impl Display for Variable {
+impl Display for Parameter {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "'{}", self.index)
+        write!(f, "<{}>", self.index)
     }
 }
 
-#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
-pub struct Parameter {
-    pub index: usize,
+#[derive(Clone, Debug, Eq, Hash, PartialEq)]
+pub struct Global {
+    pub name: Name,
 }
 
-impl Display for Parameter {
+impl Display for Global {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "<{}>", self.index)
+        write!(f, "'{}", self.name)
     }
 }
 
 /// A macro invocation.
 #[derive(Clone, Debug, Eq, PartialEq)]
 pub struct Call {
-    pub name: Name,
+    pub fun: Box<NamedExpression>,
     pub args: Vec<NamedExpression>,
 }
 
 impl Display for Call {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "{}", self.name)?;
+        write!(f, "({})(", self.fun)?;
 
         let mut iter = self.args.iter();
 
         if let Some(arg) = iter.next() {
-            write!(f, "({}", arg)?;
+            write!(f, "{}", arg)?;
 
             for arg in iter {
                 write!(f, ", {}", arg)?;
             }
+        }
+
+        write!(f, ")")
+    }
+}
 
-            write!(f, ")")
-        } else {
-            Ok(())
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Function {
+    pub args: Vec<Name>,
+    pub expr: Box<NamedExpression>,
+}
+
+impl Display for Function {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "[")?;
+        let mut iter = self.args.iter();
+        if let Some(arg) = iter.next() {
+            write!(f, "{}", arg)?;
+            for arg in iter {
+                write!(f, ", {}", arg)?;
+            }
         }
+
+        write!(f, "]")
     }
 }
 
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, PartialEq, Eq)]
 pub enum Expression {
     /// Matches the empty string.
     Epsilon(Epsilon),
@@ -162,12 +181,14 @@ pub enum Expression {
     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.
+    /// A global variable.
+    Global(Global),
+    /// A function invocation.
     Call(Call),
+    /// A function definition.
+    Function(Function)
 }
 
 impl Display for Expression {
@@ -178,72 +199,14 @@ impl Display for Expression {
             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::Global(g) => g.fmt(f),
             Self::Parameter(p) => p.fmt(f),
             Self::Call(c) => c.fmt(f),
+            Self::Function(n) => n.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::Parameter(p) => {
-                if let Self::Parameter(them) = other {
-                    p == them
-                } else {
-                    false
-                }
-            }
-            Self::Call(c) => {
-                if let Self::Call(them) = other {
-                    c == them
-                } else {
-                    false
-                }
-            }
-        }
-    }
-}
-
-impl Eq for Expression {}
-
 impl From<Epsilon> for Expression {
     fn from(eps: Epsilon) -> Self {
         Self::Epsilon(eps)
@@ -274,24 +237,30 @@ impl From<Fix> for Expression {
     }
 }
 
-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<Global> for Expression {
+    fn from(global: Global) -> Self {
+        Self::Global(global)
+    }
+}
+
 impl From<Call> for Expression {
     fn from(call: Call) -> Self {
         Self::Call(call)
     }
 }
 
+impl From<Function> for Expression {
+    fn from(fun: Function) -> Self {
+        Self::Function(fun)
+    }
+}
+
 #[derive(Clone, Debug)]
 pub struct NamedExpression {
     pub name: Option<Name>,
@@ -315,11 +284,3 @@ impl PartialEq for NamedExpression {
 }
 
 impl Eq for NamedExpression {}
-
-#[derive(Clone, Debug)]
-pub struct Function {
-    pub name: Name,
-    pub params: Vec<Option<Name>>,
-    pub expr: NamedExpression,
-    pub span: Option<Span>,
-}
diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
index 2008a15..5f5d576 100644
--- a/src/chomp/ast/substitute.rs
+++ b/src/chomp/ast/substitute.rs
@@ -6,8 +6,8 @@ use crate::chomp::{
 };
 
 use super::{
-    error::SubstituteError, Alt, Call, Cat, Epsilon, Fix, Function, Literal, NamedExpression,
-    Parameter, Variable,
+    error::SubstituteError, Alt, Call, Cat, Epsilon, Expression, Fix, Function, Global, Literal,
+    NamedExpression, Parameter,
 };
 
 #[derive(Clone, Copy, Debug, Default)]
@@ -73,22 +73,20 @@ impl Mapper for DeepenVars {
         self.depth -= 1;
     }
 
-    fn map_variable(
+    fn map_parameter(
         &mut self,
         _name: &mut Option<Name>,
         _span: Option<Span>,
-        var: &mut Variable,
+        _param: &mut Parameter,
     ) -> Self::Out {
-        if var.index >= self.depth {
-            var.index += 1;
-        }
+        todo!()
     }
 
-    fn map_parameter(
+    fn map_global(
         &mut self,
-        _name: &mut Option<Name>,
-        _span: Option<Span>,
-        _param: &mut Parameter,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        global: &mut Global,
     ) -> Self::Out {
     }
 
@@ -102,6 +100,15 @@ impl Mapper for DeepenVars {
             arg.map(self)
         }
     }
+
+    fn map_function(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        fun: &mut Function,
+    ) -> Self::Out {
+        todo!()
+    }
 }
 
 #[derive(Clone, Copy, Debug, Default)]
@@ -167,22 +174,20 @@ impl Mapper for ShallowVars {
         self.depth -= 1;
     }
 
-    fn map_variable(
+    fn map_parameter(
         &mut self,
         _name: &mut Option<Name>,
         _span: Option<Span>,
-        var: &mut Variable,
+        _param: &mut Parameter,
     ) -> Self::Out {
-        if var.index >= self.depth {
-            var.index -= 1;
-        }
+        todo!()
     }
 
-    fn map_parameter(
+    fn map_global(
         &mut self,
-        _name: &mut Option<Name>,
-        _span: Option<Span>,
-        _param: &mut Parameter,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        global: &mut Global,
     ) -> Self::Out {
     }
 
@@ -196,6 +201,15 @@ impl Mapper for ShallowVars {
             arg.map(self)
         }
     }
+
+    fn map_function(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        fun: &mut Function,
+    ) -> Self::Out {
+        todo!()
+    }
 }
 
 #[derive(Clone, Debug)]
@@ -270,35 +284,32 @@ impl Folder for SubstituteParams {
         })
     }
 
-    fn fold_variable(
-        &mut self,
-        name: Option<Name>,
-        span: Option<Span>,
-        var: Variable,
-    ) -> Self::Out {
-        Ok(NamedExpression {
-            name,
-            expr: var.into(),
-            span,
-        })
-    }
-
     fn fold_parameter(
         &mut self,
         name: Option<Name>,
         span: Option<Span>,
         param: Parameter,
     ) -> Self::Out {
-        let mut expr = self
-            .params
-            .get(param.index)
-            .cloned()
-            .ok_or_else(|| SubstituteError::FreeParameter { param, span, name: name.clone() })?;
+        let mut expr = self.params.get(param.index).cloned().ok_or_else(|| {
+            SubstituteError::FreeParameter {
+                param,
+                span,
+                name: name.clone(),
+            }
+        })?;
         expr.name = expr.name.or(name);
         expr.span = expr.span.or(span);
         Ok(expr)
     }
 
+    fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out {
+        Ok(NamedExpression {
+            name,
+            expr: global.into(),
+            span,
+        })
+    }
+
     fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
         call.args = call
             .args
@@ -311,14 +322,161 @@ impl Folder for SubstituteParams {
             span,
         })
     }
+
+    fn fold_function(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        fun: Function,
+    ) -> Self::Out {
+        todo!()
+    }
 }
 
 #[derive(Clone, Debug)]
-pub struct InlineCalls {
-    pub function: Function,
+pub struct InlineGlobal {
+    pub expr: Expression,
+    pub name: Name,
+    pub span: Option<Span>,
 }
 
-impl Folder for InlineCalls {
+impl Folder for InlineGlobal {
+    type Out = NamedExpression;
+
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+        NamedExpression {
+            name,
+            expr: eps.into(),
+            span,
+        }
+    }
+
+    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+        NamedExpression {
+            name,
+            expr: lit.into(),
+            span,
+        }
+    }
+
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
+        cat.first = Box::new(cat.first.fold(self));
+        cat.second = Box::new(cat.second.fold(self));
+        cat.rest = cat
+            .rest
+            .into_iter()
+            .map(|(punct, term)| (punct, term.fold(self)))
+            .collect();
+
+        NamedExpression {
+            name,
+            expr: cat.into(),
+            span,
+        }
+    }
+
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
+        alt.first = Box::new(alt.first.fold(self));
+        alt.second = Box::new(alt.second.fold(self));
+        alt.rest = alt
+            .rest
+            .into_iter()
+            .map(|(punct, term)| (punct, term.fold(self)))
+            .collect();
+
+        NamedExpression {
+            name,
+            expr: alt.into(),
+            span,
+        }
+    }
+
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
+        fix.inner = Box::new(fix.inner.fold(self));
+
+        NamedExpression {
+            name,
+            expr: fix.into(),
+            span,
+        }
+    }
+
+    fn fold_parameter(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        param: Parameter,
+    ) -> Self::Out {
+        NamedExpression {
+            name,
+            expr: param.into(),
+            span,
+        }
+    }
+
+    fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out {
+        if global.name == self.name {
+            NamedExpression {
+                name: Some(name.unwrap_or(self.name.clone())),
+                expr: self.expr.clone(),
+                span: span.or(self.span),
+            }
+        } else {
+            NamedExpression {
+                name,
+                expr: global.into(),
+                span,
+            }
+        }
+    }
+
+    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
+        call.fun = Box::new(call.fun.fold(self));
+        call.args = call.args.into_iter().map(|arg| arg.fold(self)).collect();
+
+        NamedExpression {
+            name,
+            expr: call.into(),
+            span,
+        }
+    }
+
+    fn fold_function(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        fun: Function,
+    ) -> Self::Out {
+        fun.expr = Box::new(fun.expr.fold(self));
+        NamedExpression {
+            name,
+            expr: fun.into(),
+            span,
+        }
+    }
+}
+
+pub struct ExpandCalls {
+    pub changed: bool,
+}
+
+impl ExpandCalls {
+    fn fold_until_done(
+        &mut self,
+        mut term: NamedExpression,
+    ) -> Result<NamedExpression, SubstituteError> {
+        let last = self.changed;
+        self.changed = true;
+        while self.changed {
+            self.changed = false;
+            term = term.fold(self)?
+        }
+        self.changed = last;
+        Ok(term)
+    }
+}
+
+impl Folder for ExpandCalls {
     type Out = Result<NamedExpression, SubstituteError>;
 
     fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
@@ -337,13 +495,13 @@ impl Folder for InlineCalls {
         })
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
-        cat.first = Box::new(cat.first.fold(self)?);
-        cat.second = Box::new(cat.second.fold(self)?);
+    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+        cat.first = Box::new(self.fold_until_done(*cat.first)?);
+        cat.second = Box::new(self.fold_until_done(*cat.second)?);
         cat.rest = cat
             .rest
             .into_iter()
-            .map(|(punct, term)| Ok((punct, term.fold(self)?)))
+            .map(|(punct, term)| Ok((punct, self.fold_until_done(term)?)))
             .collect::<Result<_, _>>()?;
 
         Ok(NamedExpression {
@@ -353,13 +511,13 @@ impl Folder for InlineCalls {
         })
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
-        alt.first = Box::new(alt.first.fold(self)?);
-        alt.second = Box::new(alt.second.fold(self)?);
+    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+        alt.first = Box::new(self.fold_until_done(*alt.first)?);
+        alt.second = Box::new(self.fold_until_done(*alt.second)?);
         alt.rest = alt
             .rest
             .into_iter()
-            .map(|(punct, term)| Ok((punct, term.fold(self)?)))
+            .map(|(punct, term)| Ok((punct, self.fold_until_done(term)?)))
             .collect::<Result<_, _>>()?;
 
         Ok(NamedExpression {
@@ -369,9 +527,8 @@ impl Folder for InlineCalls {
         })
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
-        fix.inner = Box::new(fix.inner.fold(self)?);
-
+    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+        fix.inner = Box::new(self.fold_until_done(*fix.inner)?);
         Ok(NamedExpression {
             name,
             expr: fix.into(),
@@ -379,61 +536,76 @@ impl Folder for InlineCalls {
         })
     }
 
-    fn fold_variable(
+    fn fold_parameter(
         &mut self,
         name: Option<Name>,
         span: Option<Span>,
-        var: Variable,
+        param: Parameter,
     ) -> Self::Out {
         Ok(NamedExpression {
             name,
-            expr: var.into(),
+            expr: param.into(),
             span,
         })
     }
 
-    fn fold_parameter(
-        &mut self,
-        name: Option<Name>,
-        span: Option<Span>,
-        param: Parameter,
-    ) -> Self::Out {
+    fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out {
         Ok(NamedExpression {
             name,
-            expr: param.into(),
+            expr: global.into(),
             span,
         })
     }
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
-        call.args = call
+    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out {
+        let fun = self.fold_until_done(*call.fun)?;
+        let args = call
             .args
             .into_iter()
-            .map(|arg| arg.fold(self))
-            .collect::<Result<_, _>>()?;
-
-        if call.name != self.function.name {
+            .map(|arg| self.fold_until_done(arg))
+            .collect::<Result<Vec<_>, _>>()?;
+
+        if let Expression::Function(f) = fun.expr {
+            if f.args.len() == args.len() {
+                let mut out = f.expr.fold(&mut SubstituteParams { params: args })?;
+                self.changed = true;
+                out.name = name.or(out.name);
+                out.span = span.or(out.span);
+                Ok(out)
+            } else {
+                Err(SubstituteError::WrongArgCount {
+                    call: Call {
+                        fun: Box::new(fun),
+                        args,
+                    },
+                    expected: f.args.len(),
+                    span,
+                })
+            }
+        } else {
             Ok(NamedExpression {
                 name,
-                expr: call.into(),
-                span,
-            })
-        } else if call.args.len() == self.function.params.len() {
-            let mut expr = self
-                .function
-                .expr
-                .clone()
-                .fold(&mut SubstituteParams { params: call.args })?;
-            expr.name = Some(name.or(expr.name).unwrap_or(call.name));
-            expr.span = span.or(expr.span);
-
-            Ok(expr)
-        } else {
-            Err(SubstituteError::WrongArgCount {
-                call,
-                expected: self.function.params.len(),
+                expr: Call {
+                    fun: Box::new(fun),
+                    args,
+                }
+                .into(),
                 span,
             })
         }
     }
+
+    fn fold_function(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        fun: Function,
+    ) -> Self::Out {
+        fun.expr = Box::new(self.fold_until_done(*fun.expr)?);
+        Ok(NamedExpression {
+            name,
+            expr: fun.into(),
+            span,
+        })
+    }
 }
diff --git a/src/chomp/typed/context.rs b/src/chomp/typed/context.rs
index aaf01a7..3656da1 100644
--- a/src/chomp/typed/context.rs
+++ b/src/chomp/typed/context.rs
@@ -1,10 +1,13 @@
-use crate::chomp::ast::Variable;
+use std::collections::HashMap;
+
+use crate::chomp::ast::Parameter;
 
 use super::{GroundType, Type};
 
 #[derive(Default)]
 pub struct Context {
-    vars: Vec<Type>,
+    vars: Vec<(Type, bool)>,
+    globals: HashMap<String, Type>,
     unguard_points: Vec<usize>,
 }
 
@@ -24,27 +27,38 @@ impl Context {
         res
     }
 
-    pub fn get_variable_type(&self, var: Variable) -> Result<&Type, GetVariableError> {
+    pub fn get_param_type(&self, param: Parameter) -> Result<&Type, GetParameterError> {
         self.vars
             .iter()
-            .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)
+            .nth_back(param.index)
+            .ok_or(GetParameterError::FreeParameter)
+            .and_then(|(ty, unguard)| {
+                if *unguard {
+                    Ok(ty)
+                } else {
+                    self.unguard_points
+                        .last()
+                        .and_then(|point| {
+                            if point + param.index >= self.vars.len() {
+                                Some(ty)
+                            } else {
+                                None
+                            }
+                        })
+                        .ok_or(GetParameterError::GuardedParameter)
+                }
             })
     }
 
-    pub fn with_variable_type<F: FnOnce(&mut Self) -> R, R>(&mut self, ty: Type, f: F) -> R {
-        self.vars.push(ty);
+    pub fn with_fixed_point_type<F: FnOnce(&mut Self) -> R, R>(&mut self, ty: Type, f: F) -> R {
+        self.vars.push((ty, false));
+        let res = f(self);
+        self.vars.pop();
+        res
+    }
+
+    pub fn with_parameter_type<F: FnOnce(&mut Self) -> R, R>(&mut self, ty: Type, f: F) -> R {
+        self.vars.push((ty, true));
         let res = f(self);
         self.vars.pop();
         res
@@ -52,7 +66,7 @@ impl Context {
 }
 
 #[derive(Clone, Copy, Debug, Eq, PartialEq)]
-pub enum GetVariableError {
-    FreeVariable,
-    GuardedVariable,
+pub enum GetParameterError {
+    FreeParameter,
+    GuardedParameter,
 }
diff --git a/src/chomp/typed/error.rs b/src/chomp/typed/error.rs
index 405568b..4cc55b9 100644
--- a/src/chomp/typed/error.rs
+++ b/src/chomp/typed/error.rs
@@ -7,12 +7,12 @@ use proc_macro2::Span;
 
 use crate::chomp::{ast::Variable, Name};
 
-use super::{context::GetVariableError, TypedExpression};
+use super::{context::GetParameterError, TypedExpression};
 
 /// A type error when using a fix point variable.
 #[derive(Debug)]
 pub struct VariableError {
-    pub inner: GetVariableError,
+    pub inner: GetParameterError,
     pub var: Variable,
     pub span: Option<Span>,
     pub name: Option<Name>,
@@ -29,8 +29,8 @@ impl From<VariableError> for syn::Error {
 impl Display for VariableError {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match &self.inner {
-            GetVariableError::FreeVariable => write!(f, "unbound variable: "),
-            GetVariableError::GuardedVariable => write!(f, "usage of guarded variable: "),
+            GetParameterError::FreeParameter => write!(f, "unbound variable: "),
+            GetParameterError::GuardedParameter => write!(f, "usage of guarded variable: "),
         }?;
 
         if let Some(name) = &self.name {
diff --git a/src/chomp/typed/infer.rs b/src/chomp/typed/infer.rs
index 01fe9c8..03deb8d 100644
--- a/src/chomp/typed/infer.rs
+++ b/src/chomp/typed/infer.rs
@@ -1,7 +1,7 @@
 use proc_macro2::Span;
 
 use crate::chomp::{
-    ast::{Alt, Call, Cat, Epsilon, Fix, Literal, Parameter, Variable},
+    ast::{Alt, Call, Cat, Epsilon, Fix, Function, Global, Literal, Parameter},
     visit::{Folder, Visitable},
     Name,
 };
@@ -79,9 +79,11 @@ impl Folder for TypeInfer<'_> {
 
         loop {
             let last = ty;
-            let res = self.context.with_variable_type(last.clone().into(), |context| {
-                fix.inner.clone().fold(&mut TypeInfer { context })
-            })?;
+            let res = self
+                .context
+                .with_variable_type(last.clone().into(), |context| {
+                    fix.inner.clone().fold(&mut TypeInfer { context })
+                })?;
 
             ty = res.get_type().as_ground(span)?.clone();
 
@@ -98,31 +100,6 @@ impl Folder for TypeInfer<'_> {
         }
     }
 
-    fn fold_variable(
-        &mut self,
-        name: Option<Name>,
-        span: Option<Span>,
-        var: Variable,
-    ) -> Self::Out {
-        let ty = match self.context.get_variable_type(var) {
-            Ok(ty) => ty.clone(),
-            Err(inner) => {
-                return Err(VariableError {
-                    inner,
-                    var,
-                    span,
-                    name,
-                }
-                .into())
-            }
-        };
-        Ok(TypedExpression {
-            inner: super::Variable { inner: var, ty }.into(),
-            name,
-            span,
-        })
-    }
-
     fn fold_parameter(
         &mut self,
         _name: Option<Name>,
@@ -132,7 +109,20 @@ impl Folder for TypeInfer<'_> {
         unimplemented!()
     }
 
+    fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out {
+        todo!()
+    }
+
     fn fold_call(&mut self, _name: Option<Name>, _span: Option<Span>, _call: Call) -> Self::Out {
         unimplemented!()
     }
+
+    fn fold_function(
+        &mut self,
+        name: Option<Name>,
+        span: Option<Span>,
+        fun: Function,
+    ) -> Self::Out {
+        todo!()
+    }
 }
diff --git a/src/chomp/typed/mod.rs b/src/chomp/typed/mod.rs
index 10514f0..1a171c1 100644
--- a/src/chomp/typed/mod.rs
+++ b/src/chomp/typed/mod.rs
@@ -291,15 +291,16 @@ impl Fix {
 }
 
 #[derive(Clone, Debug)]
-pub struct Variable {
-    inner: ast::Variable,
+pub struct Call {
+    fun: Box<TypedExpression>,
+    args: Vec<TypedExpression>,
     ty: Type,
 }
 
-impl Variable {
-    pub fn index(&self) -> usize {
-        self.inner.index
-    }
+#[derive(Clone, Debug)]
+pub struct Function {
+    args: Vec<Option<Name>>,
+    expr: Box<TypedExpression>,
 }
 
 #[derive(Clone, Debug)]
@@ -309,7 +310,8 @@ enum RawTypedExpression {
     Cat(Cat),
     Alt(Alt),
     Fix(Fix),
-    Variable(Variable),
+    Call(Call),
+    Function(Function),
 }
 
 impl From<Epsilon> for RawTypedExpression {
@@ -342,9 +344,15 @@ impl From<Fix> for RawTypedExpression {
     }
 }
 
-impl From<Variable> for RawTypedExpression {
-    fn from(var: Variable) -> Self {
-        Self::Variable(var)
+impl From<Call> for RawTypedExpression {
+    fn from(call: Call) -> Self {
+        Self::Call(call)
+    }
+}
+
+impl From<Function> for RawTypedExpression {
+    fn from(fun: Function) -> Self {
+        Self::Function(fun)
     }
 }
 
diff --git a/src/chomp/visit.rs b/src/chomp/visit.rs
index bdef30e..5a81f4f 100644
--- a/src/chomp/visit.rs
+++ b/src/chomp/visit.rs
@@ -2,7 +2,8 @@ use proc_macro2::Span;
 
 use super::{
     ast::{
-        Alt, Call, Cat, Epsilon, Expression, Fix, Literal, NamedExpression, Parameter, Variable,
+        Alt, Call, Cat, Epsilon, Expression, Fix, Function, Global, Literal, NamedExpression,
+        Parameter,
     },
     Name,
 };
@@ -29,21 +30,28 @@ pub trait Visitor {
 
     fn visit_fix(&mut self, name: Option<&Name>, span: Option<Span>, fix: &Fix) -> Self::Out;
 
-    fn visit_variable(
+    fn visit_parameter(
         &mut self,
         name: Option<&Name>,
         span: Option<Span>,
-        var: &Variable,
+        param: &Parameter,
     ) -> Self::Out;
 
-    fn visit_parameter(
+    fn visit_global(
         &mut self,
         name: Option<&Name>,
         span: Option<Span>,
-        param: &Parameter,
+        global: &Global,
     ) -> Self::Out;
 
     fn visit_call(&mut self, name: Option<&Name>, span: Option<Span>, call: &Call) -> Self::Out;
+
+    fn visit_function(
+        &mut self,
+        name: Option<&Name>,
+        span: Option<Span>,
+        fun: &Function,
+    ) -> Self::Out;
 }
 
 pub trait Mapper {
@@ -69,18 +77,18 @@ pub trait Mapper {
 
     fn map_fix(&mut self, name: &mut Option<Name>, span: Option<Span>, fix: &mut Fix) -> Self::Out;
 
-    fn map_variable(
+    fn map_parameter(
         &mut self,
         name: &mut Option<Name>,
         span: Option<Span>,
-        var: &mut Variable,
+        param: &mut Parameter,
     ) -> Self::Out;
 
-    fn map_parameter(
+    fn map_global(
         &mut self,
         name: &mut Option<Name>,
         span: Option<Span>,
-        param: &mut Parameter,
+        global: &mut Global,
     ) -> Self::Out;
 
     fn map_call(
@@ -89,6 +97,13 @@ pub trait Mapper {
         span: Option<Span>,
         call: &mut Call,
     ) -> Self::Out;
+
+    fn map_function(
+        &mut self,
+        name: &mut Option<Name>,
+        span: Option<Span>,
+        fun: &mut Function,
+    ) -> Self::Out;
 }
 
 pub trait Folder {
@@ -104,9 +119,6 @@ pub trait Folder {
 
     fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out;
 
-    fn fold_variable(&mut self, name: Option<Name>, span: Option<Span>, var: Variable)
-        -> Self::Out;
-
     fn fold_parameter(
         &mut self,
         name: Option<Name>,
@@ -114,7 +126,12 @@ pub trait Folder {
         param: Parameter,
     ) -> Self::Out;
 
+    fn fold_global(&mut self, name: Option<Name>, span: Option<Span>, global: Global) -> Self::Out;
+
     fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, call: Call) -> Self::Out;
+
+    fn fold_function(&mut self, name: Option<Name>, span: Option<Span>, fun: Function)
+        -> Self::Out;
 }
 
 pub trait Visitable {
@@ -127,41 +144,50 @@ pub trait Visitable {
 
 impl Visitable for NamedExpression {
     fn visit<V: Visitor>(&self, visitor: &mut V) -> <V as Visitor>::Out {
+        let name = self.name.as_ref();
+        let span = self.span;
         match &self.expr {
-            Expression::Epsilon(e) => visitor.visit_epsilon(self.name.as_ref(), self.span, e),
-            Expression::Literal(l) => visitor.visit_literal(self.name.as_ref(), self.span, l),
-            Expression::Cat(c) => visitor.visit_cat(self.name.as_ref(), self.span, c),
-            Expression::Alt(a) => visitor.visit_alt(self.name.as_ref(), self.span, a),
-            Expression::Fix(f) => visitor.visit_fix(self.name.as_ref(), self.span, f),
-            Expression::Variable(v) => visitor.visit_variable(self.name.as_ref(), self.span, v),
-            Expression::Parameter(p) => visitor.visit_parameter(self.name.as_ref(), self.span, p),
-            Expression::Call(c) => visitor.visit_call(self.name.as_ref(), self.span, c),
+            Expression::Epsilon(e) => visitor.visit_epsilon(name, span, e),
+            Expression::Literal(l) => visitor.visit_literal(name, span, l),
+            Expression::Cat(c) => visitor.visit_cat(name, span, c),
+            Expression::Alt(a) => visitor.visit_alt(name, span, a),
+            Expression::Fix(f) => visitor.visit_fix(name, span, f),
+            Expression::Parameter(p) => visitor.visit_parameter(name, span, p),
+            Expression::Global(g) => visitor.visit_global(name, span, g),
+            Expression::Call(c) => visitor.visit_call(name, span, c),
+            Expression::Function(f) => visitor.visit_function(name, span, f),
         }
     }
 
     fn map<M: Mapper>(&mut self, mapper: &mut M) -> <M as Mapper>::Out {
+        let name = &mut self.name;
+        let span = self.span;
         match &mut self.expr {
-            Expression::Epsilon(e) => mapper.map_epsilon(&mut self.name, self.span, e),
-            Expression::Literal(l) => mapper.map_literal(&mut self.name, self.span, l),
-            Expression::Cat(c) => mapper.map_cat(&mut self.name, self.span, c),
-            Expression::Alt(a) => mapper.map_alt(&mut self.name, self.span, a),
-            Expression::Fix(f) => mapper.map_fix(&mut self.name, self.span, f),
-            Expression::Variable(v) => mapper.map_variable(&mut self.name, self.span, v),
-            Expression::Parameter(p) => mapper.map_parameter(&mut self.name, self.span, p),
-            Expression::Call(c) => mapper.map_call(&mut self.name, self.span, c),
+            Expression::Epsilon(e) => mapper.map_epsilon(name, span, e),
+            Expression::Literal(l) => mapper.map_literal(name, span, l),
+            Expression::Cat(c) => mapper.map_cat(name, span, c),
+            Expression::Alt(a) => mapper.map_alt(name, span, a),
+            Expression::Fix(f) => mapper.map_fix(name, span, f),
+            Expression::Parameter(p) => mapper.map_parameter(name, span, p),
+            Expression::Global(g) => mapper.map_global(name, span, g),
+            Expression::Call(c) => mapper.map_call(name, span, c),
+            Expression::Function(f) => mapper.map_function(name, span, f),
         }
     }
 
     fn fold<F: Folder>(self, folder: &mut F) -> <F as Folder>::Out {
+        let name = self.name;
+        let span = self.span;
         match self.expr {
-            Expression::Epsilon(e) => folder.fold_epsilon(self.name, self.span, e),
-            Expression::Literal(l) => folder.fold_literal(self.name, self.span, l),
-            Expression::Cat(c) => folder.fold_cat(self.name, self.span, c),
-            Expression::Alt(a) => folder.fold_alt(self.name, self.span, a),
-            Expression::Fix(f) => folder.fold_fix(self.name, self.span, f),
-            Expression::Variable(v) => folder.fold_variable(self.name, self.span, v),
-            Expression::Parameter(p) => folder.fold_parameter(self.name, self.span, p),
-            Expression::Call(c) => folder.fold_call(self.name, self.span, c),
+            Expression::Epsilon(e) => folder.fold_epsilon(name, span, e),
+            Expression::Literal(l) => folder.fold_literal(name, span, l),
+            Expression::Cat(c) => folder.fold_cat(name, span, c),
+            Expression::Alt(a) => folder.fold_alt(name, span, a),
+            Expression::Fix(f) => folder.fold_fix(name, span, f),
+            Expression::Parameter(p) => folder.fold_parameter(name, span, p),
+            Expression::Global(g) => folder.fold_global(name, span, g),
+            Expression::Call(c) => folder.fold_call(name, span, c),
+            Expression::Function(f) => folder.fold_function(name, span, f),
         }
     }
 }
diff --git a/src/lib.rs b/src/lib.rs
index a94e08c..8ea6543 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -11,7 +11,6 @@
 #![warn(non_ascii_idents)]
 #![warn(private_doc_tests)]
 #![warn(single_use_lifetimes)]
-#![warn(trivial_casts)]
 #![warn(trivial_numeric_casts)]
 #![warn(unaligned_references)]
 #![warn(unreachable_pub)]
diff --git a/src/main.rs b/src/main.rs
index 10156e6..13b0630 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -6,7 +6,7 @@ use std::{
 
 use chomp::{
     chomp::{
-        ast::substitute::InlineCalls,
+        ast::substitute::InlineGlobal,
         typed::{
             context::Context,
             lower::{Backend, GenerateCode},
@@ -28,7 +28,7 @@ fn main() {
         .and_then(|(funs, goal)| {
             funs.into_iter()
                 .try_rfold(goal, |goal, function| {
-                    goal.fold(&mut InlineCalls { function })
+                    goal.fold(&mut InlineGlobal { function })
                 })
                 .map_err(|e| Box::new(e) as Box<dyn Error>)
         })