[climacs-devel] a paragraph on persistent buffers

[Aleksandar Bakic]

Hi,

Below is a paragraph explaining the essence of the persistent buffer
implementations, together with a couple of references (which need be put in the
bibtex format). Please let me know if you'd like to see more.

Regards,
Alex

There are three purely functional (aka fully persistent) buffer
implementations, all based on work in progress by Robert Will in
Haskell~[1], which builds upon work by Stephen Adams~[2]. The
underlying data structure is a balanced binary tree with an
abstracted-away rebalancing scheme, supporting sequence operations
needed by the Climacs buffer protocol at reasonable speed
($O(\log~N$)). The first implementation, {\tt binseq-buffer}, uses one
tree whose leaf nodes (buffer elements) can be arbitrary objects. An
optimized implementation, {\tt obinseq-buffer}, uses less space but
buffer elements must be non-nil atoms. Finally, {\tt binseq2-buffer}
combines the previous two implementations, by using a tree whose leaf
nodes contain the optimized trees representing lines; the benefit of
this implementation are faster ($O(\log~N)$) operations dealing with
lines and columns. All the three implementations enable simple and
inexpensive undo/redo operations because older buffer versions are
kept as a whole in memory. The space cost of these implementations is
not negligent, however, significant portions of older buffer versions
are simply shared with newer buffer versions. Also, it is not
necessary separately to remember editing operations in undo records,
in order to preserve precise buffer history. Besides the undo
operation simplification, the persistent buffer implementations
facilitate further purely functional operations on Climacs buffers.

[1] Robert Will. Algebraic Collections: A Standard for Functional Data
Structures. http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/

[2] Stephen Adams. Functional pearls: Efficient sets -- a balancing
act. Journal of Functional Programming, 3(4):553-561, October
1993. http://swiss.csail.mit.edu/~adams/BB/


		
Yahoo! Mail
Stay connected, organized, and protected. Take the tour:
http://tour.mail.yahoo.com/mailtour.html