[lisp-interface-library-devel] Curating libraries

[Dan Lentz]

>
> > In fact DrewC may appreciate I'd been using his CSTM as a means of
> > implementing the "box" of the root container in my "stateful" type.
> >
> I have no idea what you mean, but it sounds cool :-)


Drew seems to have a number of fascinating libraries...  He redid pascal
costanza's contextl based STM library a while back -- I've been calling it
CSTM but maybe I have the name incorrect.

My "box" was implemented as a CSTM transactional-class with one slot:
VALUE.  I used this as a container for the root node of a pure functional
tree to effect a transactionally mutable variant of that structure.  A
transaction would be to replace the root node in this box with the root
node of the updated tree on commit.

I forked LIL and placed some sources taken from my wb and rb trees into
contrib if you're interested to take a look at where I'm starting from.
 It's the majority of the core treeish stuff but pruned to the basic
routines.   Naturally it is just for reference and doesn't compile in this
state.

The implementation is mostly based on Adams purely functional data
structures, plus a couple other papers mentioned in the weight balanced
file.  One good thing is that it seems like it should be straightforward to
translate my use of layers into interfaces, at least at the moment.

I see the AVL trees do "post-balanced" where balancing occurs in the
stateful interface-- is that correct and is that technique something I
should try to replicate?  It would be nice if my binary trees conformed
with your AVL as much as possible I think but on the other hand maybe there
is some value in the Adams approach?  OTOH your way results in a truly
mutable structure in stateful, where my approach was just to have a mutable
"box" containing the current root node.


> BTW,
> 1- your file ctrie-lambda scares me!


yeah, just a plaything.


> 2- the cas thing should definitely be moved to its own system.
>
>
Noted.  I am not sure if Clozure has comparable CAS routines and don't have
a Lispworks license but the original thought was to have some manner of CAS
compatibility layer there.  Actually none of it is used at all in master
branch, and the only part currently used (in the persistence branch) is
CAS-WORD-SAP.


> > Ctries are very different from binary trees of course but also very easy
> to
> > implement pure and stateful by virtue of the capability for O(1) "Atomic
> > Fork" operation which produces a (still mutable) structure that is
> > independently readable and writable at a small cost to the next few
> > subsequent lookup operations in both the original and clone Ctries.
> >
> I can't imagine how that would work, but I suppose I could read the
> articles, first.
>
> I probably did a poor job of describing it, but yes the articles go into
more detail.  As you said though the binary trees are an easier place to
start and get my feet wet with IPS and after that I should be in a better
position to tackle the ctries.

> No doubt the ctrie is kind of an "odd duck" but also present some
> > opportunity for harnessing different types of behaviors more difficult
> with
> > other structures
> >
> Every structure is an "odd duck", different from all others.
> That's the point in having so many of them.
>
> Indeed.  Probably the red-black trees are a little bit redundant with AVL
(except for some small benefits for insert dominant workload) but as they
are so similar to the existing height balanced interface they seem like the
easiest place for me to start. So there is value in that sense.

> Very happy to be participating in this effort,
> > Dan
> >
> Yay! Let's happily hack this thing together.
>
>
Do you have suggestions on workflow?  I forked LIL for now -- should I be
instead (or also) in a branch?  I'm a little bit of a boob when it comes to
git.  Currently your AVL specifics are in the tree, tree-interface files,
but it seems problematic if I were to also include the others into them.
 Just looking for your preference on this type of thing.

BTW I meant to type "noob when it comes to git" above, but on consideration
I'll let the typo stand. :)

—♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics•
> http://fare.tunes.org
> There is no such thing as philosophy-free science; there is only science
> whose philosophical baggage is taken on board without examination.
>         — Daniel C. Dennett, Darwin's Dangerous Idea
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/lisp-interface-library-devel/attachments/20121030/f330cacf/attachment.html>