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} } + +@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 = {} +} + +@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