lambda-cat 0.1.0

//! Abstract syntax and source-position newtypes.
//!
//! The interpreter pipeline produces and consumes [`Expr`] trees built from
//! [`VarName`] identifiers and [`Position`] source offsets.  These newtypes
//! make each domain primitive distinct at the type level so a byte offset
//! cannot be confused with any other `usize`, and a variable name cannot be
//! confused with any other string.

/// A byte offset into the source string.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Position(usize);

impl Position {
    /// The underlying byte offset.
    #[must_use]
    pub fn value(&self) -> usize {
        self.0
    }
}

impl From<usize> for Position {
    fn from(value: usize) -> Self {
        Self(value)
    }
}

impl std::fmt::Display for Position {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

/// A variable identifier.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct VarName(String);

impl VarName {
    /// View the name as a string slice.
    #[must_use]
    pub fn as_str(&self) -> &str {
        &self.0
    }
}

impl From<String> for VarName {
    fn from(value: String) -> Self {
        Self(value)
    }
}

impl From<&str> for VarName {
    fn from(value: &str) -> Self {
        Self(value.to_owned())
    }
}

impl std::fmt::Display for VarName {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(&self.0)
    }
}

/// The abstract syntax tree for the lambda calculus dialect.
///
/// Variant fields are exposed for direct pattern matching; the AST is
/// purely a data shape and carries no internal invariants beyond well-
/// formedness produced by the parser.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
    /// Variable reference.
    Var(VarName),
    /// Lambda abstraction: `\param. body`.
    Lam {
        /// Bound parameter name.
        param: VarName,
        /// Function body.
        body: Box<Expr>,
    },
    /// Function application: `func arg` (left-associative at the surface).
    App {
        /// The function being applied.
        func: Box<Expr>,
        /// The argument supplied to the function.
        arg: Box<Expr>,
    },
    /// Let-binding: `let name = value in body`.
    Let {
        /// The bound name.
        name: VarName,
        /// The value being bound.
        value: Box<Expr>,
        /// The body in which the binding is in scope.
        body: Box<Expr>,
    },
    /// Fixed-point binding: `fix name. body`, where `name` may refer to the
    /// whole expression inside `body`.  Models recursion without mutation.
    Fix {
        /// The name bound to the fixed point inside `body`.
        name: VarName,
        /// The expression being closed over its own name.
        body: Box<Expr>,
    },
}

impl Expr {
    /// Build a variable reference.
    #[must_use]
    pub fn var(name: impl Into<VarName>) -> Self {
        Self::Var(name.into())
    }

    /// Build a lambda abstraction.
    #[must_use]
    pub fn lam(param: impl Into<VarName>, body: Self) -> Self {
        Self::Lam {
            param: param.into(),
            body: Box::new(body),
        }
    }

    /// Build an application node.
    #[must_use]
    pub fn app(func: Self, arg: Self) -> Self {
        Self::App {
            func: Box::new(func),
            arg: Box::new(arg),
        }
    }

    /// Build a let-binding.  Named `bind` because `let` is a keyword.
    #[must_use]
    pub fn bind(name: impl Into<VarName>, value: Self, body: Self) -> Self {
        Self::Let {
            name: name.into(),
            value: Box::new(value),
            body: Box::new(body),
        }
    }

    /// Build a fixed-point binding.
    #[must_use]
    pub fn fix(name: impl Into<VarName>, body: Self) -> Self {
        Self::Fix {
            name: name.into(),
            body: Box::new(body),
        }
    }
}

impl std::fmt::Display for Expr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Var(name) => write!(f, "{name}"),
            Self::Lam { param, body } => write!(f, "(\\{param}. {body})"),
            Self::App { func, arg } => write!(f, "({func} {arg})"),
            Self::Let { name, value, body } => {
                write!(f, "(let {name} = {value} in {body})")
            }
            Self::Fix { name, body } => write!(f, "(fix {name}. {body})"),
        }
    }
}