lambda_ref_cat/

syntax.rs

//! Abstract syntax and source-position newtypes.
//!
//! Extends the spike-1 grammar (variable, lambda, application, `let`, `fix`)
//! with four stateful forms: cell allocation (`ref e`), dereference (`!e`),
//! assignment (`r := v`), and sequencing (`e1 ; e2`).

/// 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.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
    /// Variable reference.
    Var(VarName),
    /// Lambda abstraction.
    Lam {
        /// Bound parameter name.
        param: VarName,
        /// Function body.
        body: Box<Expr>,
    },
    /// Function application (left-associative at the surface).
    App {
        /// The function being applied.
        func: Box<Expr>,
        /// The argument.
        arg: Box<Expr>,
    },
    /// Let-binding.
    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`.
    Fix {
        /// The name bound to the fixed point inside `body`.
        name: VarName,
        /// The expression being closed over its own name.
        body: Box<Expr>,
    },
    /// Allocate a fresh cell initialised with the value of `inner`.
    Ref {
        /// The expression whose value will populate the new cell.
        inner: Box<Expr>,
    },
    /// Dereference the cell pointed to by `inner`.
    Deref {
        /// The expression that must evaluate to a [`Value::Ref`].
        ///
        /// [`Value::Ref`]: crate::value::Value::Ref
        inner: Box<Expr>,
    },
    /// Assign `value` into the cell pointed to by `target`.
    Assign {
        /// The expression that must evaluate to a [`Value::Ref`].
        ///
        /// [`Value::Ref`]: crate::value::Value::Ref
        target: Box<Expr>,
        /// The value to store.
        value: Box<Expr>,
    },
    /// Sequence: evaluate `first` (discarding its value), then evaluate
    /// `second` and return its value.
    Seq {
        /// The expression evaluated for effect only.
        first: Box<Expr>,
        /// The expression whose value is the result of the sequence.
        second: 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),
        }
    }

    /// Build a `ref` allocation node.  Named `alloc` to avoid the `ref`
    /// keyword.
    #[must_use]
    pub fn alloc(inner: Self) -> Self {
        Self::Ref {
            inner: Box::new(inner),
        }
    }

    /// Build a dereference node.
    #[must_use]
    pub fn deref(inner: Self) -> Self {
        Self::Deref {
            inner: Box::new(inner),
        }
    }

    /// Build an assignment node.
    #[must_use]
    pub fn assign(target: Self, value: Self) -> Self {
        Self::Assign {
            target: Box::new(target),
            value: Box::new(value),
        }
    }

    /// Build a sequence node.
    #[must_use]
    pub fn seq(first: Self, second: Self) -> Self {
        Self::Seq {
            first: Box::new(first),
            second: Box::new(second),
        }
    }
}

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})"),
            Self::Ref { inner } => write!(f, "(ref {inner})"),
            Self::Deref { inner } => write!(f, "(!{inner})"),
            Self::Assign { target, value } => write!(f, "({target} := {value})"),
            Self::Seq { first, second } => write!(f, "({first} ; {second})"),
        }
    }
}