On Mon, Dec 22, 2025, 4:21 PM David McClain <[email protected]> wrote:
I guess the specific example of my Actor-State does have an ordering relation, since the keys are all keyword symbols. Oh, an ordering relation can be defined for almost anything. FSet has a generic function 'compare' that can be easily extended for new types. Functional red-black trees are a fine choice. FSet has long used an older kind of balanced trees, called weight-balanced. More recently, I've added a relatively new hash-based data structure called CHAMP. On Mon, Dec 22, 2025, 4:25 PM David McClain <[email protected]> wrote: > I track 15 MHz carriers to <100 μHz precision. > Impressive! I did this implementation because a friend of mine involved in Actors > machines suggested the JavaScript JSON Dictionary - which I find to be > enormously redundant and noisy. Just a simple PList with keyword keys could > fully replace them and great simplification. And so my Actor-State was an > attempt to prove that out. > > I fear that Purely Functional Red-Black Trees would be even more costly, > but maybe not. I should look into it, or your FSet. > Haha, if you want small and simple, FSet might not be to your taste. My goal was to make it easy to use and featureful. It's pretty fast, though. -- Scott > > > On Dec 22, 2025, at 17:19, David McClain <[email protected]> > wrote: > > I guess the specific example of my Actor-State does have an ordering > relation, since the keys are all keyword symbols. So good point on that > O(log n). My simple implementation is just a copy / replace, which is O(n). > > > > On Dec 22, 2025, at 17:16, David McClain <[email protected]> > wrote: > > Yes, good points O(log n) cost. But that implies that elements have an > ordering relation, no? Partial or total order. I have such structures that > I use often, red-black trees that are purely functional implementations. So > I understand your points here. But many times my data does not have any > order relation, just an equality. > > > > On Dec 22, 2025, at 15:52, Scott L. Burson <[email protected]> wrote: > > On Mon, Dec 22, 2025, 12:20 PM David McClain <[email protected]> > wrote: > >> >> > BECOME takes a functional closure, which contains its state within the >> closure vars. But I have become frustrated with too many BOA args, and I >> also implemented a kind of dictionary to carry state with items labeled by >> a keyword. > > > Right. I saw your file 'actor-state.lisp' and thought "Ah! This is a > functional map. This man needs FSet." > > Yes, the state is in the closure vars, but that doesn't preclude it being > large and complex. With functional data structures, you can efficiently > prepare an updated version of a large structure without invalidating the > previous version. If something goes wrong before the BECOME takes effect, > no harm has been done; the tentative new version simply becomes garbage. > The trick is to use only O(log n) space each time, where n is the size of > the previous version. > > -- Scott > > > > > >
