[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.bib papers/ilc2005/syntax/climacssyntax.tex papers/ilc2005/syntax/acm_proc_article-sp.cls

[Christophe Rhodes]

Update of /project/climacs/cvsroot/papers/ilc2005/syntax
In directory common-lisp.net:/tmp/cvs-serv21552

Modified Files:
	climacssyntax.bib climacssyntax.tex 
Removed Files:
	acm_proc_article-sp.cls 
Log Message:
Remove acm_proc_article-sp.cls

Add discussion from amb about persistent buffer implementations

Date: Tue May 24 11:20:19 2005
Author: crhodes

Index: papers/ilc2005/syntax/climacssyntax.bib
diff -u papers/ilc2005/syntax/climacssyntax.bib:1.9 papers/ilc2005/syntax/climacssyntax.bib:1.10
--- papers/ilc2005/syntax/climacssyntax.bib:1.9	Mon May 23 15:57:22 2005
+++ papers/ilc2005/syntax/climacssyntax.bib	Tue May 24 11:20:19 2005
@@ -152,7 +152,7 @@
   title = "{The Craft of Text Editing}",
   publisher = {Springer-Verlag},
   year = {1991, 1999--},
-  note = {http://www.finseth.com/craft}
+  note = {\url{http://www.finseth.com/craft}}
 }
 
 @Manual{ISOProlog,
@@ -191,3 +191,28 @@
   organization = {International Telecommunication Union},
   year = {1999}
 }
+
+ at Unpublished{dessy,
+  author = 	 {Robert Will},
+  title = 	 "{Algebraic Collections: A Standard for Functional Data Structures}",
+  note = 	 {\url{http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/}},
+  OPTkey = 	 {},
+  OPTmonth = 	 {},
+  OPTyear = 	 {},
+  OPTannote = 	 {}
+}
+
+ at Article{adams,
+  author = 	 {Stephen Adams},
+  title = 	 "{Functional pearls: Efficient sets -- a balancing act}",
+  journal = 	 {Journal of Functional Programming},
+  year = 	 {1993},
+  OPTkey = 	 {},
+  volume = 	 {3},
+  number = 	 {4},
+  OPTpages = 	 {553--561},
+  OPTmonth = 	 {},
+  OPTnote = 	 {},
+  OPTannote = 	 {}
+}
+


Index: papers/ilc2005/syntax/climacssyntax.tex
diff -u papers/ilc2005/syntax/climacssyntax.tex:1.25 papers/ilc2005/syntax/climacssyntax.tex:1.26
--- papers/ilc2005/syntax/climacssyntax.tex:1.25	Tue May 24 11:08:43 2005
+++ papers/ilc2005/syntax/climacssyntax.tex	Tue May 24 11:20:19 2005
@@ -6,6 +6,7 @@
 
 \usepackage[a4paper,textwidth=6.7in,textheight=8.7in]{geometry}
 \usepackage{graphics}
+\usepackage{url}
 \usepackage{times}
 
 \pagestyle{empty}
@@ -76,12 +77,12 @@
 management, incremental redisplay, and syntax analysis.  Emacs itself
 traces its lineage to TECO, where Emacs was originally implemented as
 a set of TECO macros.  Climacs is compared to several interesting
-variants of Emacs in Table \ref{table:editorcompare}; more information
+variants of Emacs in table \ref{table:editorcompare}; more information
 about text editing in general, and some editors we shall not discuss
 further, can be found in \cite{FinsethCraft,greenberg,Pike94,woodZ}
 and references therein.
 
-\begin{figure*}
+\begin{table}
 \begin{center}
 {\small
 \begin{tabular}{|c|c|c|c|c|}
@@ -107,7 +108,7 @@
 \caption{Implementation strategies of multiple Emacs variants}
 \end{center}
 \label{table:editorcompare}
-\end{figure*}
+\end{table}
 
 Climacs' syntax analysis is a flexible protocol which can be
 implemented with a full language lexer and parser. GNU Emacs, the most
@@ -174,13 +175,28 @@
 the sequence is stored in a separate slot, along with the beginning of
 the gap.
 
-Climacs also provides a buffer implementation utilizing functional
-data structures as the editable sequence representation. This buffer
-implementation provides a low-cost implementation of undo along
-multiple edit histories. (FIXME: a citation, either to something ``in
-preparation'' or to some previous description of the ideas? It would
-help if someone with more understanding than I of this buffer
-implementation would sketch this out.)
+Climacs also provides three purely functional (aka fully persistent)
+buffer implementations, all based on work in progress \cite{dessy} by
+Robert Will in Haskell, which builds upon older work by Stephen Adams
+\cite{adams}.  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 negligible, 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.
 
 Climacs is intended to provide other buffer implementations, one of
 which will use a sequence of lines organized into a tree for quick