lambda_ref_cat/
heap.rs

1//! Persistent heap of mutable cells.
2//!
3//! The heap is a [`BTreeMap`] from monotonically-allocated [`Address`]es to
4//! [`Value`]s.  Every operation that conceptually mutates the heap (`alloc`,
5//! `store`, `retain`) instead returns a new [`Heap`] value; the receiver is
6//! left untouched.  No `Rc`, `Arc`, `RefCell`, `Cell`, or `Mutex` is used to
7//! provide shared mutability.
8//!
9//! The trade-off is performance: each non-read operation clones the existing
10//! cell map.  This is acceptable for a falsification spike and an explicit
11//! mirror of the persistent-data-structure pattern that the user's no-
12//! interior-mutability rule pushes the design toward.
13
14use std::collections::{BTreeMap, BTreeSet};
15
16use crate::value::Value;
17
18/// An address of a cell on the heap.
19///
20/// Addresses are allocated monotonically and never reused, including across
21/// garbage collections.  This keeps every previously-issued address either
22/// resolvable to its surviving cell or detectable as dangling.
23#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
24pub struct Address(usize);
25
26impl Address {
27    /// The underlying numeric address.
28    #[must_use]
29    pub fn value(&self) -> usize {
30        self.0
31    }
32}
33
34impl From<usize> for Address {
35    fn from(value: usize) -> Self {
36        Self(value)
37    }
38}
39
40impl std::fmt::Display for Address {
41    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42        write!(f, "#{}", self.0)
43    }
44}
45
46/// A persistent map of addresses to cell values.
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct Heap {
49    cells: BTreeMap<Address, Value>,
50    next: usize,
51}
52
53impl Heap {
54    /// An empty heap with the address counter at zero.
55    #[must_use]
56    pub fn empty() -> Self {
57        Self {
58            cells: BTreeMap::new(),
59            next: 0,
60        }
61    }
62
63    /// The number of cells currently live in the heap.
64    #[must_use]
65    pub fn len(&self) -> usize {
66        self.cells.len()
67    }
68
69    /// Whether the heap holds no cells.
70    #[must_use]
71    pub fn is_empty(&self) -> bool {
72        self.cells.is_empty()
73    }
74
75    /// Whether the heap has a cell at `address`.
76    #[must_use]
77    pub fn contains(&self, address: Address) -> bool {
78        self.cells.contains_key(&address)
79    }
80
81    /// All addresses currently live in the heap, in ascending order.
82    pub fn addresses(&self) -> impl Iterator<Item = Address> + '_ {
83        self.cells.keys().copied()
84    }
85
86    /// Allocate a fresh cell holding `value`, returning the resulting heap
87    /// and the new cell's address.
88    #[must_use]
89    pub fn alloc(&self, value: Value) -> (Self, Address) {
90        let addr = Address(self.next);
91        let cells: BTreeMap<Address, Value> = self
92            .cells
93            .iter()
94            .map(|(k, v)| (*k, v.clone()))
95            .chain(std::iter::once((addr, value)))
96            .collect();
97        (
98            Self {
99                cells,
100                next: self.next + 1,
101            },
102            addr,
103        )
104    }
105
106    /// Read the value held at `address`, or `None` if the address is dangling.
107    #[must_use]
108    pub fn load(&self, address: Address) -> Option<&Value> {
109        self.cells.get(&address)
110    }
111
112    /// Return a heap with the cell at `address` set to `value`, or `None` if
113    /// the address is dangling.  Address counter is preserved.
114    #[must_use]
115    pub fn store(&self, address: Address, value: Value) -> Option<Self> {
116        self.cells.contains_key(&address).then(|| {
117            let cells: BTreeMap<Address, Value> = self
118                .cells
119                .iter()
120                .filter(|(k, _)| **k != address)
121                .map(|(k, v)| (*k, v.clone()))
122                .chain(std::iter::once((address, value)))
123                .collect();
124            Self {
125                cells,
126                next: self.next,
127            }
128        })
129    }
130
131    /// Return a heap containing only cells whose addresses are in `live`.
132    /// The next-address counter is preserved so the surviving addresses
133    /// stay stable and no future address ever collides with a freed one.
134    #[must_use]
135    pub fn retain(&self, live: &BTreeSet<Address>) -> Self {
136        let cells: BTreeMap<Address, Value> = self
137            .cells
138            .iter()
139            .filter(|(k, _)| live.contains(k))
140            .map(|(k, v)| (*k, v.clone()))
141            .collect();
142        Self {
143            cells,
144            next: self.next,
145        }
146    }
147}
148
149impl Default for Heap {
150    fn default() -> Self {
151        Self::empty()
152    }
153}
154
155impl std::fmt::Display for Heap {
156    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
157        let entries = self
158            .cells
159            .iter()
160            .map(|(k, v)| format!("{k} = {v}"))
161            .collect::<Vec<_>>()
162            .join(", ");
163        write!(f, "[{entries}]")
164    }
165}
lambda_ref_cat/heap.rs

lambda_ref_cat/
heap.rs
