lambda_cat/
syntax.rs

1//! Abstract syntax and source-position newtypes.
2//!
3//! The interpreter pipeline produces and consumes [`Expr`] trees built from
4//! [`VarName`] identifiers and [`Position`] source offsets.  These newtypes
5//! make each domain primitive distinct at the type level so a byte offset
6//! cannot be confused with any other `usize`, and a variable name cannot be
7//! confused with any other string.
8
9/// A byte offset into the source string.
10#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
11pub struct Position(usize);
12
13impl Position {
14    /// The underlying byte offset.
15    #[must_use]
16    pub fn value(&self) -> usize {
17        self.0
18    }
19}
20
21impl From<usize> for Position {
22    fn from(value: usize) -> Self {
23        Self(value)
24    }
25}
26
27impl std::fmt::Display for Position {
28    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
29        write!(f, "{}", self.0)
30    }
31}
32
33/// A variable identifier.
34#[derive(Debug, Clone, PartialEq, Eq, Hash)]
35pub struct VarName(String);
36
37impl VarName {
38    /// View the name as a string slice.
39    #[must_use]
40    pub fn as_str(&self) -> &str {
41        &self.0
42    }
43}
44
45impl From<String> for VarName {
46    fn from(value: String) -> Self {
47        Self(value)
48    }
49}
50
51impl From<&str> for VarName {
52    fn from(value: &str) -> Self {
53        Self(value.to_owned())
54    }
55}
56
57impl std::fmt::Display for VarName {
58    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59        f.write_str(&self.0)
60    }
61}
62
63/// The abstract syntax tree for the lambda calculus dialect.
64///
65/// Variant fields are exposed for direct pattern matching; the AST is
66/// purely a data shape and carries no internal invariants beyond well-
67/// formedness produced by the parser.
68#[derive(Debug, Clone, PartialEq, Eq)]
69pub enum Expr {
70    /// Variable reference.
71    Var(VarName),
72    /// Lambda abstraction: `\param. body`.
73    Lam {
74        /// Bound parameter name.
75        param: VarName,
76        /// Function body.
77        body: Box<Expr>,
78    },
79    /// Function application: `func arg` (left-associative at the surface).
80    App {
81        /// The function being applied.
82        func: Box<Expr>,
83        /// The argument supplied to the function.
84        arg: Box<Expr>,
85    },
86    /// Let-binding: `let name = value in body`.
87    Let {
88        /// The bound name.
89        name: VarName,
90        /// The value being bound.
91        value: Box<Expr>,
92        /// The body in which the binding is in scope.
93        body: Box<Expr>,
94    },
95    /// Fixed-point binding: `fix name. body`, where `name` may refer to the
96    /// whole expression inside `body`.  Models recursion without mutation.
97    Fix {
98        /// The name bound to the fixed point inside `body`.
99        name: VarName,
100        /// The expression being closed over its own name.
101        body: Box<Expr>,
102    },
103}
104
105impl Expr {
106    /// Build a variable reference.
107    #[must_use]
108    pub fn var(name: impl Into<VarName>) -> Self {
109        Self::Var(name.into())
110    }
111
112    /// Build a lambda abstraction.
113    #[must_use]
114    pub fn lam(param: impl Into<VarName>, body: Self) -> Self {
115        Self::Lam {
116            param: param.into(),
117            body: Box::new(body),
118        }
119    }
120
121    /// Build an application node.
122    #[must_use]
123    pub fn app(func: Self, arg: Self) -> Self {
124        Self::App {
125            func: Box::new(func),
126            arg: Box::new(arg),
127        }
128    }
129
130    /// Build a let-binding.  Named `bind` because `let` is a keyword.
131    #[must_use]
132    pub fn bind(name: impl Into<VarName>, value: Self, body: Self) -> Self {
133        Self::Let {
134            name: name.into(),
135            value: Box::new(value),
136            body: Box::new(body),
137        }
138    }
139
140    /// Build a fixed-point binding.
141    #[must_use]
142    pub fn fix(name: impl Into<VarName>, body: Self) -> Self {
143        Self::Fix {
144            name: name.into(),
145            body: Box::new(body),
146        }
147    }
148}
149
150impl std::fmt::Display for Expr {
151    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
152        match self {
153            Self::Var(name) => write!(f, "{name}"),
154            Self::Lam { param, body } => write!(f, "(\\{param}. {body})"),
155            Self::App { func, arg } => write!(f, "({func} {arg})"),
156            Self::Let { name, value, body } => {
157                write!(f, "(let {name} = {value} in {body})")
158            }
159            Self::Fix { name, body } => write!(f, "(fix {name}. {body})"),
160        }
161    }
162}
lambda_cat/syntax.rs

lambda_cat/
syntax.rs
