I am still digesting everything you said in your previous message, but on an unrelated topic... <div><br></div><div dir="ltr">Why did you use association-pair as a base class rather than some type of box?   (re: your note in interface/tree)  The reason I ask is that in my code I currently also have both key and value slots hard wired and I think I preferred my previous approach which amounted to a single "payload" slot in the node which would contain (the equivalent of) a single-value-box for sets, an association-pair box for maps, and a specialized kind of association pair box for seqs.  One  reason this seems to be a better way is that when implementing persistence (as in on disk) the key and or value tend to be serialized lisp objects ie octet vectors of some length.  Keeping them together in a single object makes it much simpler when manually allocating storage.  Thus nodes will be of a fixed allocation size (containing essentially 4 pointers :  payload left right height -- typically each being a fixnum offset into a file stream,  mmap index, or heap address)  Also when creating new nodes in the pure interface, one does not have to duplicate the long serialized key/value data (if it were to be physically stored in the node) or, more likely, deal with separate allocation and pointers to the serialized data of key and value slots.   <span style>In the non persistent case things work as normal of course.</span><div>
 </div><div>Another benefit, possibly less (or not) important under IPS was that</div><div>This leaves the underlying tree node as the same class regardless of the type of collection, set map or seq, and one can distinguish the type of collection by simple examination of any tree node just by looking at the class of its payload box.  <br>
<br>I can work either way of course, and like I said wb and rb currently also use quintuple nodes (kvlrh) but I've thought once or twice that given the opportunity I'd change back to my previous approach using quad nodes (plrh). <span></span></div>
<div><br></div><div><span style>Thoughts?  </span><br dir="ltr"></div><div><span style><br></span></div><div><span style><br></span></div><div><br>On Wednesday, October 31, 2012, Faré  wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
> My "box" was implemented as a CSTM transactional-class with one slot: VALUE.<br>
> I used this as a container for the root node of a pure functional tree to<br>
> effect a transactionally mutable variant of that structure.  A transaction<br>
> would be to replace the root node in this box with the root node of the<br>
> updated tree on commit.<br>
><br>
That would be a nice thing to add to interface/box.lisp<br>
and to use with the define-mutating-interface macro<br>
to automatically deduce shared-mutable objects<br>
from pure interfaces.<br>
<br>
> I forked LIL and placed some sources taken from my wb and rb trees into<br>
> contrib if you're interested to take a look at where I'm starting from.<br>
> It's the majority of the core treeish stuff but pruned to the basic<br>
> routines.   Naturally it is just for reference and doesn't compile in this<br>
> state.<br>
><br>
Forking is fine. I'd rather the work be committed to master<br>
in steps that don't involve breaking the workingness of the system<br>
(i.e. compiles and passes tests) or importing non-working files<br>
(there are a few in funds/ already).<br>
<br>
But I prefer working code to non-working code,<br>
even if there is some ugly commit history.<br>
<br>
> The implementation is mostly based on Adams purely functional data<br>
> structures, plus a couple other papers mentioned in the weight balanced<br>
> file.  One good thing is that it seems like it should be straightforward to<br>
> translate my use of layers into interfaces, at least at the moment.<br>
><br>
Any link to Adams?<br>
We should probably maintain a bibliography somewhere.<br>
<br>
> I see the AVL trees do "post-balanced" where balancing occurs in the<br>
> stateful interface-- is that correct and is that technique something I<br>
> should try to replicate?<br>
><br>
For stateful trees, I believe this works great.<br>
For pure trees, I have so far overridden the node method.<br>
I'm wondering if state-passing :post and :pre method combinators<br>
wouldn't be better instead.<br>
And of course I eventually want both pure & stateful<br>
from a single linear logic specification.<br>
<br>
> It would be nice if my binary trees conformed with<br>
> your AVL as much as possible I think but on the other hand maybe there is<br>
> some value in the Adams approach?<br>
<br>
> OTOH your way results in a truly mutable<br>
> structure in stateful, where my approach was just to have a mutable "box"<br>
> containing the current root node.<br>
><br>
IIUC, that approach is what my "mutating" macro gives you automatically<br>
from a pure interface.<br>
<br>
—♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• <a href="http://fare.tunes.org" target="_blank">http://fare.tunes.org</a><br>
To most Christians, the Bible is like a software license. Nobody<br>
actually reads it. They just scroll to the bottom and click "I agree."<br>
</blockquote></div></div>