lambda-throw-cat 0.1.0

//! Abstract syntax and source-position newtypes.
//!
//! Spike 4 extends the spike-3 grammar with two non-local control-flow forms:
//! [`Expr::Throw`] raises an exception carrying any runtime value, and
//! [`Expr::TryCatch`] catches a thrown value into a let-style binder around
//! the handler.  Every other reduction form is unchanged; the propagation of
//! a thrown value is purely a property of the evaluator's `Outcome` return
//! type, not of the syntax tree.

/// 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 or property identifier.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, 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 {
        /// 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 or property pointed to by `target`.
    /// When `target` is a [`Expr::Field`] the assignment is to an own
    /// property of the referenced object; otherwise it is to a cell.
    Assign {
        /// The expression denoting the location to be written.
        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>,
    },
    /// Object literal with optional prototype.  Evaluating an [`Expr::Object`]
    /// allocates a fresh object on the heap and returns a reference to it.
    Object {
        /// Property entries, in source order.  Duplicates resolve by the
        /// last write.
        entries: Vec<(VarName, Expr)>,
        /// Optional prototype expression.  When `Some`, the value must
        /// evaluate to a reference to another object at run time.
        prototype: Option<Box<Expr>>,
    },
    /// Field access on an object.  Walks the prototype chain on miss.
    Field {
        /// The object expression.
        object: Box<Expr>,
        /// The property name to look up.
        name: VarName,
    },
    /// Throw an exception carrying the value of `inner`.  Unwinds the
    /// current evaluation until caught by an enclosing [`Expr::TryCatch`].
    Throw {
        /// The value to throw.
        inner: Box<Expr>,
    },
    /// Catch an exception thrown by `body`, binding the thrown value to
    /// `catch_param` while evaluating `handler`.
    TryCatch {
        /// The expression evaluated under exception protection.
        body: Box<Expr>,
        /// The name to which a caught thrown value is bound.
        catch_param: VarName,
        /// The handler expression evaluated when `body` throws.
        handler: 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.
    #[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),
        }
    }

    /// Build an object literal with no prototype.
    #[must_use]
    pub fn object(entries: Vec<(VarName, Self)>) -> Self {
        Self::Object {
            entries,
            prototype: None,
        }
    }

    /// Build an object literal with a prototype expression.
    #[must_use]
    pub fn object_with_proto(entries: Vec<(VarName, Self)>, prototype: Self) -> Self {
        Self::Object {
            entries,
            prototype: Some(Box::new(prototype)),
        }
    }

    /// Build a field access node.
    #[must_use]
    pub fn field(object: Self, name: impl Into<VarName>) -> Self {
        Self::Field {
            object: Box::new(object),
            name: name.into(),
        }
    }

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

    /// Build a try-catch node.
    #[must_use]
    pub fn try_catch(body: Self, catch_param: impl Into<VarName>, handler: Self) -> Self {
        Self::TryCatch {
            body: Box::new(body),
            catch_param: catch_param.into(),
            handler: Box::new(handler),
        }
    }
}

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})"),
            Self::Object { entries, prototype } => write_object(f, entries, prototype.as_deref()),
            Self::Field { object, name } => write!(f, "({object}.{name})"),
            Self::Throw { inner } => write!(f, "(throw {inner})"),
            Self::TryCatch {
                body,
                catch_param,
                handler,
            } => write!(f, "(try {body} catch {catch_param}. {handler})"),
        }
    }
}

fn write_object(
    f: &mut std::fmt::Formatter<'_>,
    entries: &[(VarName, Expr)],
    prototype: Option<&Expr>,
) -> std::fmt::Result {
    let body = entries
        .iter()
        .map(|(k, v)| format!("{k} = {v}"))
        .collect::<Vec<_>>()
        .join(", ");
    let formatted = prototype.map_or_else(
        || format!("{{{body}}}"),
        |proto| format!("(extend {proto} {{{body}}})"),
    );
    f.write_str(&formatted)
}