[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.tex

[Robert Strandh]

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

Modified Files:
	climacssyntax.tex 
Log Message:
Corrected some statements about the current implementation that were
incorrect.  Added conclusions and future work. 


Date: Mon May 23 06:06:40 2005
Author: rstrandh

Index: papers/ilc2005/syntax/climacssyntax.tex
diff -u papers/ilc2005/syntax/climacssyntax.tex:1.14 papers/ilc2005/syntax/climacssyntax.tex:1.15
--- papers/ilc2005/syntax/climacssyntax.tex:1.14	Mon May 23 03:05:55 2005
+++ papers/ilc2005/syntax/climacssyntax.tex	Mon May 23 06:06:39 2005
@@ -42,7 +42,7 @@
   The Climacs text editor is a CLIM implementation of a text editor in
   the Emacs tradition.  Climacs was designed to allow for incremental
   parsing of the buffer contents, so that a sophisticated analysis of
-  the buffer contents can be performed without impacting performance.
+  the contents can be performed without impacting performance.
   We describe two different syntax modules: a module for a
   sequentially-defined syntax of a typical programming language, doing
   the bulk of its parsing in a per-window function; and an interactive
@@ -103,20 +103,21 @@
 correctly, other expressions can still match on the contents of the
 comment, leading to issues when the first character in a column in the
 block comment is the start of a definition. Emacs users quickly learn
-to insert a space before the open paren to work around Emacs'
+to insert a space before the open parenthesis to work around Emacs'
 font-lock deficiencies.
 
 The Climacs text editor is a combination of frameworks for buffer
 representation and parsing, loosely coupled with a CLIM-based display
 engine.  It includes the Flexichain library \cite{flexichain}, which
 provides an editable sequence representation and mark (cursor)
-management using a simple linked lists used for implementing the
-buffer protocol; and an implementation of a slight modification of the
-Earley parsing algorithm \cite{earley}, to assist in the creation of
-syntax-aware editing modes. An application can combine a particular
-implementation of the buffer protocol, the syntax protocol, and its
-own display methods to produce a sophisticated editor for a particular
-language.
+management using a simple linked list for implementing the buffer
+protocol.  Climacs also includes an implementation of a slight
+modification of the Earley parsing algorithm \cite{earley}, to assist
+in the creation of syntax-aware editing modes, though such modes can
+use any appropriate parsing algorithm.  An application can combine a
+particular implementation of the buffer protocol, the syntax protocol,
+and its own display methods to produce a sophisticated editor for a
+particular language.
 
 The Climacs buffer protocol, which provides a standard interface to
 common text editor buffer operations, uses the Flexichain library; we
@@ -125,7 +126,7 @@
 provides a method for interfacing a lexical analyzer and parser with
 the text editor, and provides for defining methods to draw syntax
 objects in the Climacs window.  In section \ref{sec:syntaxes} we
-discuss the implementation of syntactic analysis for various
+discuss the implementation of syntactic analyses for various
 programming languages, including Common Lisp; in section
 \ref{sec:tabeditor}, we discuss an application with Climacs at its
 core to support editing a textual representation of lute tablature.
@@ -257,6 +258,36 @@
 approach is appropriate when the parse tree will also be used for some
 other display or analysis of the text in the buffer.
 
+Climacs includes a parser that uses the Earley \cite{earley} parsing
+algorithm.  There are many advantages of this algorithm in the context
+of text editing.  Perhaps most importantly, it does not require any
+preprocessing of the grammar, which makes it necessary for the entire
+grammar to be known ahead of time.  This means that the user can
+load Lisp files containing additional syntax rules to complete the
+existing ones without having to apply any costly grammar analysis.
+Other advantages include the possibility of using ambiguous grammars,
+since the Earley parsing algorithm accepts the full class of
+context-free grammars.  This feature is crucial in certain
+applications, for instance in a grammar checker for natural
+languages.  The Climacs syntax protocol can, but is not required
+to, use the provided Earley parser.  It can use any algorithm with an
+explicit representation of the parser state, which is a necessary, but
+not sufficient, requirement for making the parsing algorithm
+incremental. 
+
+However, the Earley parsing algorithm is relatively slow compared to
+table-based algorithms such as the LR shift/reduce algorithm.
+Worst-case complexity is $O(n^3)$ where $n$ is the size of the input.
+It drops to $O(n^2)$ for unambiguous grammars and to $O(n)$ for a
+large class of grammars suitable for parsing programming langauges.
+Even so, the complexity is often proportional to the size of the
+grammar (which is considered a constant by Earley), which can be
+problematic in a text editor.  We have yet to determine whether the
+implementation of the Earley algorithm that we provide will turn out
+to be sufficiently fast for most Climacs syntax modules.  Other
+possibilities include the Tomita parsing algorithm which provides more
+generality than LR, but which is nearly as fast in most cases. 
+
 \section{Syntaxes}
 \label{sec:syntaxes}
 
@@ -428,8 +459,55 @@
 \section{Future Work and Conclusions}
 \label{sec:conclusions}
 
-I like Jello.  Jello is good.  We should enable people to make better
-Jello.
+Given the relatively small amount of work (only a few person-months)
+that has been put into Climacs so far, it is already a very competent
+and stable editor.  Using CLIM (and in particular the McCLIM
+implementation) as the display engine has allowed the project to
+progress much more rapidly than what would have been possible
+otherwise.  However, Climacs has also revealed some serious
+limitations and performance problems of the McCLIM library.  We
+maintain that using CLIM and McCLIM was the best choice, and in fact
+advantageous to other McCLIM users as well, since work is being done
+to correct and improve it for use with Climacs. 
+
+Due to its reliance on fairly well-defined protocols, the Climacs text
+editor framework is flexible enough to allow for different future
+directions.  Turning the Common Lisp syntax module into an excellent
+programming tool for Lisp programmers is high on the list of
+priorities, for many reasons.  First, it will encourage further work
+on Climacs.  Second, the Common Lisp syntax module is likely to become
+one of the more advanced ones to exist for Climacs, given that Climacs
+has unique and direct access to the features of the underlying Common
+Lisp implementation.  Thus, the Common Lisp syntax module is likely to
+exercise the Climacs protocols to a very high degree.  This will allow
+us to improve those protocols as well as their corresponding
+implementations. 
+
+Another future direction high up on the list of priorites is the
+planned implementation of the buffer protocol.  Representing a line
+being editied as a flexichain can greatly improve the performance of
+some crucial operations that currently require looping over each
+buffer object until a newline character is found.  Other operations
+that are currently prohibitive include knowing the line- and column
+number of a given mark. 
+
+However, our plans for Climacs go further than creating an improved
+implementation of Emacs.  We intend to make Climacs a fully-integrated
+CLIM application.  This implies among other things using the
+presentation-type system of CLIM to exchange objects between Climacs
+and other CLIM appliations such as an inspector application, a
+debugger pane, etc.  We also hope that implementors of other CLIM
+applications such as mail readers, news readers, etc, will consider
+using Climacs for creating messages.
+
+We are often asked whether applications such as VM and Gnus for GNU
+Emacs will be available for Climacs.  Our opinion is that such
+applications currenltly run as GNU Emacs subsystems, simply because
+GNU Emacs does not have an independent substrate such as CLIM for
+creating user interfaces.  Climacs is itself a CLIM application, and
+applications such as mail readers and news readers that do not require
+editable buffers should instead be implemented directly as CLIM
+applications, perhaps calling Climacs to write messages.
 
 \nocite{*}