Automatically derive variable binding and alpha equivalence for abstract syntax trees.

Example

Here is an example of how you might use moniker to define the AST for the simply typed lambda calculus:

#[macro_use]
extern crate moniker;

use std::rc::Rc;
use moniker::{Embed, Nest, Binder, Scope, Var};

# #[cfg(feature = "moniker-derive")]
#[derive(Debug, Clone, BoundTerm)]
pub enum Type {
    Base,
    Arrow(Rc<Type>, Rc<Type>),
}

# #[cfg(feature = "moniker-derive")]
#[derive(Debug, Clone, BoundTerm)]
pub enum Expr {
    Var(Var<String>),
    Lam(Scope<(Binder<String>, Embed<Rc<Type>>), Rc<Expr>>),
    Let(Scope<Nest<(Binder<String>, Embed<(Rc<Type>, Rc<Expr>)>)>, Rc<Expr>>),
    App(Rc<Expr>, Rc<Expr>),
}
# fn main() {}

Overview of traits and data types

We separate data types into terms and patterns:

Terms

Terms are data types that implement the BoundTerm trait.

• Var<N>: A variable that is either free or bound
• Scope<P: BoundPattern<N>, T: BoundTerm<N>>: bind the term T using the pattern P

Implementations for tuples, strings, numbers, slices, vectors, and mart pointers are also provided for convenience.

Patterns

Patterns are data types that implement the BoundPattern trait.

• Binder<N>: Captures a free variables within a term, but is ignored for alpha equality
• Ignore<T>: Ignores T when comparing for alpha equality
• Embed<T: BoundTerm<N>>: Embed a term T in a pattern
• Nest<P: BoundPattern<N>>: Multiple nested binding patterns
• Rec<P: BoundPattern<N>>: Recursively bind a pattern in itself

Implementations for tuples, strings, numbers, slices, vectors, and mart pointers are also provided for convenience.