lambda-cat 0.1.0

//! Persistent lexical environments.
//!
//! An [`Env`] is a cons-list of name-value bindings.  Lookup walks the list
//! head-first so an inner binding shadows an outer one with the same name.
//! [`Env::extend`] returns a fresh `Env` rather than mutating the receiver;
//! the underlying tail is cloned to satisfy the no-`Rc`/`Arc` constraint.

use crate::syntax::VarName;
use crate::value::Value;

/// A persistent lexical environment.
///
/// Variants are public so tests and downstream tools can pattern match on
/// the structure, but construction normally goes through [`Env::empty`] and
/// [`Env::extend`] and lookup goes through [`Env::lookup`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Env {
    /// The empty environment.
    Empty,
    /// A binding of `name` to `value`, atop the rest of the environment.
    Cons {
        /// The bound name.
        name: VarName,
        /// The bound value.
        value: Box<Value>,
        /// The environment without this binding.
        rest: Box<Env>,
    },
}

impl Env {
    /// The environment with no bindings.
    #[must_use]
    pub fn empty() -> Self {
        Self::Empty
    }

    /// Return a new environment with `name` bound to `value` shadowing any
    /// prior binding of `name`.  The receiver is unchanged.
    #[must_use]
    pub fn extend(&self, name: VarName, value: Value) -> Self {
        Self::Cons {
            name,
            value: Box::new(value),
            rest: Box::new(self.clone()),
        }
    }

    /// Look up the most recent binding of `name`, or `None` if unbound.
    #[must_use]
    pub fn lookup(&self, name: &VarName) -> Option<&Value> {
        match self {
            Self::Empty => None,
            Self::Cons {
                name: bound,
                value,
                rest,
            } => {
                if bound == name {
                    Some(value)
                } else {
                    rest.lookup(name)
                }
            }
        }
    }
}

impl std::fmt::Display for Env {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Empty => f.write_str("{}"),
            Self::Cons { name, value, rest } => {
                write!(f, "{{{name} = {value}}} :: {rest}")
            }
        }
    }
}