climacs-cvs May 2005

climacs-cvs@common-lisp.net

4 participants
64 discussions

[climacs-cvs] CVS update: papers/ilc2005/syntax/boardfig.eps papers/ilc2005/syntax/boardfig.pdf papers/ilc2005/syntax/climacssyntax.bib papers/ilc2005/syntax/climacssyntax.tex
by crhodes＠common-lisp.net 23 May '05

23 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv6888 Modified Files: climacssyntax.bib climacssyntax.tex Added Files: boardfig.eps boardfig.pdf Log Message: Initial stab at describing interesting bits of the tabeditor Date: Mon May 23 13:34:58 2005 Author: crhodes Index: papers/ilc2005/syntax/climacssyntax.bib diff -u papers/ilc2005/syntax/climacssyntax.bib:1.7 papers/ilc2005/syntax/climacssyntax.bib:1.8 --- papers/ilc2005/syntax/climacssyntax.bib:1.7 Mon May 23 12:21:41 2005 +++ papers/ilc2005/syntax/climacssyntax.bib Mon May 23 13:34:58 2005 @@ -149,14 +149,14 @@ @book{FinsethCraft, author = {Craig A. Finseth}, - title = {The Craft of Text Editing}, + title = "{The Craft of Text Editing}", publisher = {Springer-Verlag}, year = {1991, 1999--}, note = {http://www.finseth.com/craft} } @Manual{ISOProlog, - title = "{Information technology -- Programming languages -- Prolog -- Part 1: General core}", + title = "{Prolog -- Part 1: General core}", key = {ISO/IEC 13211-1:1995}, OPTauthor = {}, organization = {ISO}, @@ -165,6 +165,16 @@ OPTmonth = {}, year = {1995}, OPTnote = {}, + OPTannote = {} +} + +@Unpublished{tabxml, + author = {Frans Wiering and Tim Crawford and David Lewis}, + title = "{Creating an XML vocabulary for encoding lute music}", + note = {In preparation}, + OPTkey = {}, + OPTmonth = {}, + OPTyear = {}, OPTannote = {} } Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.16 papers/ilc2005/syntax/climacssyntax.tex:1.17 --- papers/ilc2005/syntax/climacssyntax.tex:1.16 Mon May 23 12:21:41 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Mon May 23 13:34:58 2005 @@ -432,36 +432,72 @@ computer-based musicological studies (as in \cite{ecolm-graz} for example). -\TabCode\ has a rather ad-hoc cobbled together grammar. Tokenising is -easy; determining which elements of the notation are best captured is -not so easy. Chords, obviously; beams, comments... Should we try to -capture a BNF or something? I suppose it depends how we're doing for -space. - -Ornaments are simple to model, as they are merely modifiers to note -objects; higher-level grouping things (beams, connecting lines) have -their own semi-independent identity, despite not being notated as such -in the textual \TabCode. Beams and connecting lines can overlap -(thinking linearly, not on the manuscript!) in non-trivial ways: - -\begin{verbatim} - [ beamed section ] - word word word word word - ^____ line ____^ -\end{verbatim} - -Need whole-buffer function to present an alternative whole-system view -on the data. - -Editor is in use for cataloguing European lute music, and supports -research into more advanced notations (for e.g. editorial comment, or -manuscript markup) - -Efficiency concerns assuaged by typical locality of edit, CLIM -incremental redisplay on the tablature buffer. - -MIDI feedback. At present, based on Apple's extremely badly -documented CoreMIDI framework; a port to alsalib is on the cards. +The \TabCode\ language itself has developed to provide a terse and +intuitive encoding of tablature, rather than a well-formed grammar for +parsing. Simple \TabCode, as in figure \ref{fig:besfantlach}, +presents no problems: each chord is an optional rhythm sign (a capital +letter), followed by zero or more notes as fret--string pairs +(letter--number combinations). Adding ornaments and fingering marks +to this structure is simple, as they are merely optional modifiers to +each note, and can be parsed as such. + +\begin{figure} + \begin{center} + \includegraphics{boardfig} + \caption{Extract from 'An Almand by mr Jo Dowland Bacheler of + musique', \textit{The Board Lute Book} (GB:Lam MS 603), f.13. + Note in particular the connecting lines in this bar, joining + chords within beams to an unbeamed chord.} + \label{fig:board} + \end{center} +\end{figure} + +More complex to model are beams and connecting lines, which have their +own semi-independent identity, despite being encoded in \TabCode\ as +modifiers to individual tokens. In particular, the existence of beams +and connecting lines means that we cannot parse a buffer into a +sequence of tabwords and thence into hypothetical higher-level +structures such as \texttt{beamed-group} and \texttt{connected-pair}, +because these higher-level structures can overlap in non-trivial ways, +as in figure \ref{fig:board}. Instead, we deal with these modifiers by +invoking a parser on the sequence of parsed buffer elements to +generate parallel sequences of beams, connecting lines and other such +tablature elements. + +The tablature editor that has been developed in parallel with Climacs +is in use for a project to catalogue European lute music, and +additionally supports research \cite{tabxml} into more advanced +notations and extensions of \TabCode\ (to provide a means to encode +editorial comments or alterations, or markup of distinguishing +features of a specific source ma\-nu\-script). + +When the tablature editor is in use, the user has in addition to the +usual editor window a scrollable graphical display of the tablature +encoded within the buffer. Individual tablature elements are +presented to this CLIM pane, allowing the graphical display to provide +mouse-activated commands, such as one which moves the buffer cursor to +the beginning of the tabword encoding a particular element. + +Since we are presenting an alternative view of the whole buffer's +contents, we analyse the entire buffer's contents on every edit, +rather than bounding our analysis by the extent of the visible textual +area. To mitigate the efficiency concerns that this might suggest, it +should first be noted that the typical length of a \TabCode\ file is +of the order of 200--300 words, which requires only little time to +parse on modern hardware. However, such a parsing scheme would stress +the display engine if a complete redraw were forced on every edit, so +we have implemented the obvious optimizations: the extent of the edit, +along with its typical locality of effect, are used to limit the +damaged region as before, so preserving the identity of unaffected +tabwords; this identity can then be used in a cache informing CLIM's +incremental redisplay mechanism. + +To assist the editorial process, we have also implemented MIDI audio +feedback: in addition to a command to render the entire tablature, we +provide several gestures to play individual chords: one intended for +use during the initial entry of the encoding, to act as a rapid +error-detection aid, and a motion command and mouse gesture to assist +revision and navigation. \section{Future Work and Conclusions} \label{sec:conclusions}

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.bib papers/ilc2005/syntax/climacssyntax.tex
by crhodes＠common-lisp.net 23 May '05

23 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv2490 Modified Files: climacssyntax.bib climacssyntax.tex Log Message: Mostly describe Prolog syntax. One or two fixups Date: Mon May 23 12:21:41 2005 Author: crhodes Index: papers/ilc2005/syntax/climacssyntax.bib diff -u papers/ilc2005/syntax/climacssyntax.bib:1.6 papers/ilc2005/syntax/climacssyntax.bib:1.7 --- papers/ilc2005/syntax/climacssyntax.bib:1.6 Sat May 21 18:32:16 2005 +++ papers/ilc2005/syntax/climacssyntax.bib Mon May 23 12:21:41 2005 @@ -153,4 +153,18 @@ publisher = {Springer-Verlag}, year = {1991, 1999--}, note = {http://www.finseth.com/craft} -} \ No newline at end of file +} + +@Manual{ISOProlog, + title = "{Information technology -- Programming languages -- Prolog -- Part 1: General core}", + key = {ISO/IEC 13211-1:1995}, + OPTauthor = {}, + organization = {ISO}, + OPTaddress = {}, + OPTedition = {}, + OPTmonth = {}, + year = {1995}, + OPTnote = {}, + OPTannote = {} +} + Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.15 papers/ilc2005/syntax/climacssyntax.tex:1.16 --- papers/ilc2005/syntax/climacssyntax.tex:1.15 Mon May 23 06:06:39 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Mon May 23 12:21:41 2005 @@ -61,10 +61,13 @@ history and an apparent ability to cause passionate argument. Climacs is philosophically part of the Emacs editor tradition, which has spawned many variants with many different approaches to buffer -management, incremental redisplay, and syntax analysis. Emacs itself +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}. +a set of TECO macros. Climacs is compared to several interesting +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{center} @@ -107,17 +110,17 @@ 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 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. +representation and parsing, loosely coupled with a CLIM-based +\cite{mckayacm} display engine. It includes the Flexichain library +\cite{flexichain}, which provides an editable sequence representation +and mark (cursor) 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 @@ -182,8 +185,8 @@ point of edit before an edit operation is allowed. When the buffer is large and edit operations occur frequently at multiple locations in the buffer, this requires a substantial amount of copying between -edits. In this situation single-gap-buffer editors like Emacs will -noticably pause between edits to move the gap. A structure which +edits. In this situation single-gap-buffer editors such as GNU Emacs +will noticably pause between edits to move the gap. A structure which contains a sequence of lines and keeps the most recently used lines open as gap buffers can operate as a multi-gap buffer with automatic gap placement, while not providing pessimistic performance when @@ -193,14 +196,14 @@ implementation of the buffer protocol that is used. Space efficiency will also depend on the implementation of Common Lisp which is used to run Climacs. In Steel Bank Common Lisp, the type character is -represented with the full 22 bits used by the Unicode character -space. External character encodings other than Unicode are converted -to Unicode when a file is read in to memory. If the characters are -stored in a specialized array, this will net a worst case space -efficiency of four bytes of every byte in the file. However, the time -advantages of this representation outweigh the space -inefficiency. Searching for an individual character in a sequence of -characters encoded in UTF-8 is $O(n)$, because each individual +represented with the full 21 bits used by the Unicode character space. +External character encodings other than Unicode are converted to +UTF-32 when a file is read in to memory. If the characters are stored +in a specialized array, this will net a worst case space efficiency of +four bytes of every byte in the file. However, the time advantages of +this representation outweigh the space inefficiency. Searching for an +individual character in a sequence of characters encoded in UTF-8 (or +other variable-length encoding) is $O(n)$, because each individual character must be examined to determine the number of octets which are stored to represent that character. @@ -208,7 +211,7 @@ which uses one machine word per element, either as an immediate value or as a pointer to a larger element. Climacs buffers can contain any object, so in a suitably complex syntax and buffer protocol -implementation an object in a buffer may +implementation an object in a buffer may ... may what? FIXME \section{Syntax Protocol} \label{sec:syntax} @@ -243,13 +246,6 @@ \ref{fig:syntaxclasses} shows the organization of classes in the TTCN3 grammar. -Climacs provides an Earley parser \cite{earley} which is sufficient to -parse most context-free grammars. Earley parser: discussion of -generality and asymptotic efficiency (in general and for usual cases). -Possibility of replacement in case of complicated grammars? (What was -that parsing algorithm that someone mentioned on \verb+#lisp+? -\textit{I have no idea.}) - The syntax analysis can be applied either in a per-window or per-buffer function. The per-window approach is best suited to analysis of text where the parse tree will be used only for display @@ -286,18 +282,19 @@ 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. +generality than LR, but which is nearly as fast in most cases. \section{Syntaxes} \label{sec:syntaxes} We describe two different approaches to syntax analysis in the Climacs editor. Per-window parsing is used by the provided modes for HTML, -Common Lisp, Prolog, and TTCN3. Each of these syntaxes is implemented -with the provided Earley parser \cite{earley}. The lute tablature -editor uses a per-buffer function for its syntax analysis and -implements a simple recursive-descent parsing algorithm. (FIXME: is -this true? I don't know enough about parsing) +Common Lisp, Prolog, and a Testing Control Notation (TTCN3). Each of +these syntaxes is implemented with the provided Earley parser +\cite{earley}. The lute tablature editor uses a per-buffer function +for its syntax analysis and implements a simple recursive-descent +parsing algorithm. (FIXME: is this true? I don't know enough about +parsing) \subsection{Per-Window Syntaxes} @@ -312,25 +309,35 @@ rules to accommodate the level of analysis to parse the language's grammar. -Christophe might want to describe the Prolog syntax a bit here. In -particular any details having to do with the implementation of -operator precedence as specified in the ISO Prolog standard might be -interesting. - -[ Maybe just the \textit{priority} stuff? I think that's -the only interesting bit of non-context-freeness; user-defined -operators is OK because you can't actually define and use a new -operator in the same directive. ] - -Float tokenizer (not interesting, but not yet done) - -Need for inheritable grammars / tokenizers: most Prologs deviate from -ISO slightly, mostly in surface syntax rather than in the engine. -Examples: \verb+"ab\x011\"+, \texttt{0'''}, \texttt{[H|T]} when -\texttt{|} is an operator. - -Possibility (probably ``Future Work'') to make nice integrated Prolog -environment. +Implementing the Prolog syntax proved a good test of the established +framework. Firstly, and most importantly, ISO Prolog \cite{ISOProlog} +is not a context-free grammar: \textit{terms} have an implicit +priority affecting their parse.\footnote{Formally, the grammar could + be made context-free by introducing 1200 new production rules.} The +implementation of Earley's algorithm, however, was able to address +this additional complexity with no difficulty. + +Another area of difficulty is the fact that parsing a Prolog text can +change the grammar itself through the use of the \texttt{op/3} +directive: including +\begin{verbatim} + :- op(100,xfy,<>). +\end{verbatim} +in a Prolog text means that, after parsing this directive, the token +\texttt{<>} must be recognized as an right-associative operator with +priority 100 in the grammar. This is achievable by keeping a cache of +parsed \texttt{op/3} directives, and maintaining and invalidating it +in parallel with the parse of the buffer itself. + +While the Prolog syntax included with Climacs is a demonstration of +the potential of strongly syntax-aware editors, it is not yet a +practical tool for Prolog programmers, as most implementations of +Prolog deviate from strict ISO compliance. On the level of surface +syntax, interpretation of quoting rules and escape sequences in +strings are very variable, while additionally treatment of operators +in currently-available Prologs can differ markedly from the standard +requirements. Nevertheless, work is underway to use Climacs' syntax +analysis to provide a front-end for a Prolog development environment. At present, one parse error implies the invalidation of the rest of the file. This adds a burden on the mode implementor that the syntax @@ -410,20 +417,20 @@ \end{center} \end{figure*} -\TabCode\ is a textual format for description of lute tablature. In -its simplest form, it is a sequence of whitespace-delimited -independent words, where each word represents either a set of frets to -depress and strings to be sounded, or alternatively some element of -musical notation (such as a barline); figure \ref{fig:besfantlach} -demonstrates a fragment of manuscript, and its \TabCode\ encoding. It -is also possible to encode more complex elements of lute tablature -notation in \TabCode: ornaments, fingering marks, beaming, connecting -lines and other complex elements can all be accommodated (see figure -\ref{fig:barley} for examples of more these more complex elements). - -\TabCode\ has been used to produce scholarly editions of lute works -\cite{Weiss} and to computer-based musicological studies (as in -\cite{ecolm-graz} for example). +\TabCode\ \cite{tabcode} is a textual format for description of lute +tablature. In its simplest form, it is a sequence of +whitespace-delimited independent words, where each word represents +either a set of frets to depress and strings to be sounded, or +alternatively some element of musical notation (such as a barline); +figure \ref{fig:besfantlach} demonstrates a fragment of manuscript, +and its \TabCode\ encoding. It is also possible to encode more +complex elements of lute tablature notation in \TabCode: ornaments, +fingering marks, beaming, connecting lines and other complex elements +can all be accommodated (see figure \ref{fig:barley} for examples of +some of these more complex elements). \TabCode\ has been used to +produce scholarly editions of lute works \cite{Weiss} and to assist in +computer-based musicological studies (as in \cite{ecolm-graz} for +example). \TabCode\ has a rather ad-hoc cobbled together grammar. Tokenising is easy; determining which elements of the notation are best captured is @@ -462,13 +469,14 @@ 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. +\cite{ilc2002-moore} implementation) as the display engine has allowed +the project to progress much more rapidly than would otherwise have +been possible. However, Climacs development has also revealed some +serious limitations and performance problems of the McCLIM library. +Nevertheless, we maintain that using CLIM and McCLIM was the best +choice, and in fact advantageous to other McCLIM users as well, as the +deficiencies in McCLIM implementation are being addressed and other +improvements made 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 @@ -483,7 +491,7 @@ us to improve those protocols as well as their corresponding implementations. -Another future direction high up on the list of priorites is the +Another future direction high up on the list of priorities 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 @@ -491,7 +499,14 @@ 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 +One disadvantage of the current parsing scheme is that a single parse +error prevents analysis of the rest of the buffer, which is +potentially disturbing to a user's workflow. For relatively simple +grammars such as \TabCode, it is simple enough to resynchronize at the +next token, whereas for more complex grammars the resolution is less +clear. + +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 @@ -502,19 +517,20 @@ 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 currently 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{*} +%\nocite{*} \section*{Acknowledgments} -C.R. is supported by EPSRC grant GR/\-S84750/\-01. B.M. acknowledges -Motorola's generous support. +The authors wish to thank Aleksandr Bakic for fruitful discussions. +B.M.\ acknowledges Motorola's generous support. C.R.\ is supported by +EPSRC grant GR/\-S84750/\-01. \bibliographystyle{acm} \bibliography{climacssyntax}

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.tex
by rstrandh＠common-lisp.net 23 May '05

23 May '05

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{*}

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/parserclasses.eps papers/ilc2005/syntax/parserclasses.pdf papers/ilc2005/syntax/ttcn3msc.eps papers/ilc2005/syntax/ttcn3msc.pdf papers/ilc2005/syntax/climacssyntax.tex
by bmastenbrook＠common-lisp.net 23 May '05

23 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv1803 Modified Files: climacssyntax.tex Added Files: parserclasses.eps parserclasses.pdf ttcn3msc.eps ttcn3msc.pdf Log Message: Buffer protocol description; some syntax Date: Mon May 23 03:05:55 2005 Author: bmastenbrook Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.13 papers/ilc2005/syntax/climacssyntax.tex:1.14 --- papers/ilc2005/syntax/climacssyntax.tex:1.13 Sun May 22 13:47:26 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Mon May 23 03:05:55 2005 @@ -58,42 +58,65 @@ \section{Introduction} The field of advanced text editors is a crowded one, with a long -history and an apparent ability to cause passionate argument. Climacs is philosophically part of the Emacs editor tradition, which has spawned many variants with many different approaches to buffer 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}. +history and an apparent ability to cause passionate argument. Climacs +is philosophically part of the Emacs editor tradition, which has +spawned many variants with many different approaches to buffer +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}. -\begin{figure*} \begin{center} +\begin{figure*} +\begin{center} \begin{tabular}{|c|c|c|c|c|} \hline \textbf{Editor} & \textbf{Buffer Implementation} & \textbf{Syntax Analysis} & \textbf{Language} \\ -\hline TECO & Gap Buffer & Unknown & Assembly + TECO Macros +\hline TECO & Gap buffer & Unknown & Assembly + TECO Macros \\ \hline Zmacs & Probably doubly-linked list of lines & None & MacLisp \\ -\hline GNU Emacs & Gap Buffer & Regular Expressions & C + Emacs Lisp +\hline GNU Emacs & Gap buffer & Regular Expressions & C + Emacs Lisp \\ \hline Hemlock & Doubly-linked list of lines & None & Common Lisp \\ -\hline FRED & Gap Buffer & None & PPC Assembly + Common Lisp +\hline FRED & Gap buffer & None & PPC Assembly + Common Lisp \\ \hline Deuce & Doubly-linked lists of lines & Unknown & Dylan \\ \hline Climacs & Multiple & Multiple & Common Lisp \\\hline \end{tabular} -\caption{Implementation strategies of multiple Emacs variants} \end{center} \label{table:editorcompare} \end{figure*} - -Climacs' syntax analysis is a flexible protocol which can be implemented with a full language lexer and parser. GNU Emacs, the most commonly used Emacs-like editor, uses regular expressions for its syntax analysis. Because these regular expressions are applied lazily and not on the whole buffer, constructs such as Common Lisp's nestable \verb+#| |#+ block comments will often confuse the regular expressions. If the parser starts after the opening \verb+#|+ then the closing \verb+|#+ will be treated as the start of an escaped symbol name. Even if the regular expression parses the whole block comment 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' font-lock deficiencies. +\caption{Implementation strategies of multiple Emacs variants} +\end{center} +\label{table:editorcompare} +\end{figure*} + +Climacs' syntax analysis is a flexible protocol which can be +implemented with a full language lexer and parser. GNU Emacs, the most +commonly used Emacs-like editor, uses regular expressions for its +syntax analysis. Because these regular expressions are applied lazily +and not on the whole buffer, constructs such as Common Lisp's nestable +\verb+#| |#+ block comments will often confuse the regular +expressions. If the parser starts after the opening \verb+#|+ then the +closing \verb+|#+ will be treated as the start of an escaped symbol +name. Even if the regular expression parses the whole block comment +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' +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. +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. The Climacs buffer protocol, which provides a standard interface to common text editor buffer operations, uses the Flexichain library; we @@ -112,39 +135,119 @@ \section{Buffer Protocol} \label{sec:buffer} -The buffer protocol provides a set of methods for modifying and -reading the contents of a buffer which can contain arbitrary objects. -Typically these objects are characters, but the buffer can contain any -object that the syntax protocol can display in the Climacs window. The -buffer protocol is independent of any implementation of the protocol, -which allows flexible representations of buffers. - -The aim is for Climacs to provide several implementations of the -buffer protocol, one of which will use a sequence of lines organized -into a tree for quick access. In this implementation, a line can be -considered opened or closed. Editing operations are performed on -opened lines, which are represented as a cursorchain (a Flexichain -with an arbitrary number of cursors). A fixed number of lines are kept -opened according to a LRU scheme. When a line is closed it is -converted to a vector. If the line contains only base-char objects -this vector is a base-string; otherwise, it is unspecialized. -Currently, however, Climacs uses a single cursorchain for the entire -buffer, in effect making it a simple gap-buffer implementation. - -``Protocol'' is not just an empty claim, as there are already multiple -buffer implementations: Aleksandar Bakic's persistent buffer -implementations, providing a cheap implementation of the undo protocol. -(FIXME: a citation, either to something ``in preparation'' or to some -previous description of the ideas?) +Climacs abstracts the implementation of editable sequences as editor +buffers using the buffer protocol. The buffer protocol provides a set +of methods for modifying and reading the contents of a buffer, and +setting and retrieving marks in the buffer. Buffers can contain +arbitrary objects. Typically these objects are characters, but the +buffer can contain any object that the syntax protocol can display in +the Climacs window. The buffer protocol is independent of any +implementation of the protocol, which allows flexible representations +of buffers. + +Currently Climacs uses a single Flexichain ``cursorchain'' as the +editable sequence representation for standard buffers. A cursorchain +is a circular gap buffer with an arbitrary number of cursors in the +buffer. Climacs uses these cursors as the implementation of marks in +the buffer. The single gap-buffer implementation is used by many other +editors, including GNU Emacs. Flexichain improves on this by making +the gap buffer circular in its underlying representation; the start of +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 is intended to provide other buffer implementations, one of +which will use a sequence of lines organized into a tree for quick +access. In this structure, a line can be considered opened or +closed. When a line is opened, it is represented as a Flexichain +cursorchain. All editing operations are performed on open lines. A +fixed number of lines are kept opened according to a +least-recently-used scheme. When a line is closed it is converted to a +vector for efficient storage and access. If the line contains only +base-char objects this vector is a base-string; otherwise, it is +unspecialized. + +This structure has the advantage of efficient line-based access in the +buffer. It also provides much less pessimistic behavior than that of a +single gap buffer when a user is editing two disparate sections in a +large file. With a single gap buffer, the gap must be moved to the +point of edit before an edit operation is allowed. When the buffer is +large and edit operations occur frequently at multiple locations in +the buffer, this requires a substantial amount of copying between +edits. In this situation single-gap-buffer editors like Emacs will +noticably pause between edits to move the gap. A structure which +contains a sequence of lines and keeps the most recently used lines +open as gap buffers can operate as a multi-gap buffer with automatic +gap placement, while not providing pessimistic performance when +accessing a specific line in the buffer. + +The efficiency of Climacs buffers depends greatly on the +implementation of the buffer protocol that is used. Space efficiency +will also depend on the implementation of Common Lisp which is used to +run Climacs. In Steel Bank Common Lisp, the type character is +represented with the full 22 bits used by the Unicode character +space. External character encodings other than Unicode are converted +to Unicode when a file is read in to memory. If the characters are +stored in a specialized array, this will net a worst case space +efficiency of four bytes of every byte in the file. However, the time +advantages of this representation outweigh the space +inefficiency. Searching for an individual character in a sequence of +characters encoded in UTF-8 is $O(n)$, because each individual +character must be examined to determine the number of octets which are +stored to represent that character. + +The Flexichain library uses an unspecialized vector for its storage, +which uses one machine word per element, either as an immediate value +or as a pointer to a larger element. Climacs buffers can contain any +object, so in a suitably complex syntax and buffer protocol +implementation an object in a buffer may \section{Syntax Protocol} \label{sec:syntax} -A syntax in Climacs is an incremental parser which creates and updates -a parse tree of a buffer's contents, and provides a mechanism for -drawing these parsed objects in a window. The parser accepts lexemes -produced by an incremental lexical analyzer associated with the -syntax. +\begin{figure*} + \begin{center} + \includegraphics{parserclasses} + \caption{Organization of classes used by a typical syntax} + \label{fig:syntaxclasses} + \end{center} +\end{figure*} + +Climacs is designed to allow multiple implementation strategies for +buffer parsers and syntax-aware display mechanisms. The set of hooks +that Climacs provides to allow this is the syntax protocol. A syntax +in Climacs is a class and set of methods which provide a lexical +analyzer, parser, and display methods for a buffer. The incremental +parser associated with a syntax creates and updates a parse tree of a +buffer's contents, and provides a mechanism for drawing these parsed +objects in a window. The parser accepts lexemes produced by an +incremental lexical analyzer. Display is handled by drawing methods +implemented using the CLIM high-level display toolkit. + +Though a syntax is free to choose its own implementation strategy, +lexical analysis and parsing of the buffer is typically done in an +object-oriented fashion. The lexer operates on objects in the buffer, +usually characters, and returns objects of various classes. Each +parser production is represented by a class. In complex syntaxes, the +parser rules can be quite complicated and involve arbitrary code, but +for a simple grammar the parsing rules can be entirely represented by +matching on the classes returned by the tokenizer and parser. Figure +\ref{fig:syntaxclasses} shows the organization of classes in the TTCN3 +grammar. + +Climacs provides an Earley parser \cite{earley} which is sufficient to +parse most context-free grammars. Earley parser: discussion of +generality and asymptotic efficiency (in general and for usual cases). +Possibility of replacement in case of complicated grammars? (What was +that parsing algorithm that someone mentioned on \verb+#lisp+? +\textit{I have no idea.}) The syntax analysis can be applied either in a per-window or per-buffer function. The per-window approach is best suited to @@ -154,11 +257,6 @@ approach is appropriate when the parse tree will also be used for some other display or analysis of the text in the buffer. -Earley parser: discussion of generality and asymptotic efficiency (in -general and for usual cases). Possibility of replacement in case of -complicated grammars? (What was that parsing algorithm that someone -mentioned on \verb+#lisp+?) - \section{Syntaxes} \label{sec:syntaxes} @@ -186,7 +284,7 @@ Christophe might want to describe the Prolog syntax a bit here. In particular any details having to do with the implementation of operator precedence as specified in the ISO Prolog standard might be -interesting. +interesting. [ Maybe just the \textit{priority} stuff? I think that's the only interesting bit of non-context-freeness; user-defined @@ -209,6 +307,12 @@ slightly-buggy or incomplete syntax mode will render the whole thing useless. Violation of WiB? +The Testing and Test Control Notation 3 (TTCN3) language is a language +which captures detailed test specifications. TTCN provides both a +textual ``core'' grammar and a graphical presentation format similar +to Message Sequence Charts (see figure \ref{fig:ttcn3gr}). Climacs +currently provides an editor for a subset of the TTCN3 core language. + The TTCN3 syntax is implemented with a high-level macro which defines classes and adds syntax rules using the syntax protocol for each terminal and non-terminal in the grammar. The syntax of this macro @@ -218,6 +322,20 @@ receive their own non-terminal entry in the grammar. In addition, this macro defines basic display functions for the syntax objects produced by the parser, with language keywords appearing in a separate color. + +\begin{figure*} + \begin{center} + \parbox{0.45\linewidth}{\includegraphics{ttcn3msc}} + \parbox{0.25\linewidth}{\texttt{\\ [1cm]\noindent + testcase MyTestCase (inout integer MyPar)\\ + runs on MyMTCtype system SystemType \{\\ + var integer MyVar := 1;\\ + MyMTCPort.send(MyTemplate);\\ + \}}} + \caption{A fragment of TTCN3 and its corresponding Graphical Representation (GR)} + \label{fig:ttcn3gr} + \end{center} +\end{figure*} \subsection{Per-Buffer Syntax: a tablature editor} \label{sec:tabeditor}

1 0

[climacs-cvs] CVS update: climacs/ttcn3-syntax.lisp climacs/climacs.asd
by bmastenbrook＠common-lisp.net 23 May '05

23 May '05

Update of /project/climacs/cvsroot/climacs In directory common-lisp.net:/tmp/cvs-serv1250 Modified Files: climacs.asd Added Files: ttcn3-syntax.lisp Log Message: Add the TTCN3 syntax Date: Mon May 23 03:00:24 2005 Author: bmastenbrook Index: climacs/climacs.asd diff -u climacs/climacs.asd:1.28 climacs/climacs.asd:1.29 --- climacs/climacs.asd:1.28 Fri Apr 22 10:18:26 2005 +++ climacs/climacs.asd Mon May 23 03:00:24 2005 @@ -64,6 +64,7 @@ "cl-syntax" "html-syntax" "prolog-syntax" + "ttcn3-syntax" "gui" ;;---- optional ---- "testing/rt"

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.tex
by abakic＠common-lisp.net 22 May '05

22 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv19050 Modified Files: climacssyntax.tex Log Message: Minor fixes. I'll try to add some background/references soon. Date: Sun May 22 13:47:26 2005 Author: abakic Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.12 papers/ilc2005/syntax/climacssyntax.tex:1.13 --- papers/ilc2005/syntax/climacssyntax.tex:1.12 Sun May 22 12:53:59 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Sun May 22 13:47:26 2005 @@ -132,8 +132,8 @@ buffer, in effect making it a simple gap-buffer implementation. ``Protocol'' is not just an empty claim, as there are already multiple -buffer implementations: Aleksandr Bakic's persistent buffer -implementation, providing a cheap implementation of the undo protocol. +buffer implementations: Aleksandar Bakic's persistent buffer +implementations, providing a cheap implementation of the undo protocol. (FIXME: a citation, either to something ``in preparation'' or to some previous description of the ideas?)

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.tex
by rstrandh＠common-lisp.net 22 May '05

22 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv15544 Modified Files: climacssyntax.tex Log Message: Made the description of the current buffer protocol implementation more accurate. Date: Sun May 22 12:53:59 2005 Author: rstrandh Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.11 papers/ilc2005/syntax/climacssyntax.tex:1.12 --- papers/ilc2005/syntax/climacssyntax.tex:1.11 Sat May 21 22:14:00 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Sun May 22 12:53:59 2005 @@ -23,8 +23,8 @@ \affaddr{London SE14 6NW, UK}\\ \email{c.rhodes(a)gold.ac.uk} \alignauthor Robert Strandh\\ - \affaddr{Equipe Image et son, LaBRI}\\ - \affaddr{Domaine Universitaire}\\ + \affaddr{LaBRI}\\ + \affaddr{Universit\'{e} Bordeaux 1}\\ \affaddr{351, cours de la Lib\'{e}ration}\\ \affaddr{33405 Talence Cedex} \affaddr{FRANCE}\\ @@ -84,12 +84,16 @@ Climacs' syntax analysis is a flexible protocol which can be implemented with a full language lexer and parser. GNU Emacs, the most commonly used Emacs-like editor, uses regular expressions for its syntax analysis. Because these regular expressions are applied lazily and not on the whole buffer, constructs such as Common Lisp's nestable \verb+#| |#+ block comments will often confuse the regular expressions. If the parser starts after the opening \verb+#|+ then the closing \verb+|#+ will be treated as the start of an escaped symbol name. Even if the regular expression parses the whole block comment 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' font-lock deficiencies. The Climacs text editor is a combination of frameworks for buffer -representation and parsing 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 based on a linked lists of lines, some of which are represented as a circular gap buffer; and an implementation of a +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. +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. The Climacs buffer protocol, which provides a standard interface to common text editor buffer operations, uses the Flexichain library; we @@ -115,13 +119,17 @@ buffer protocol is independent of any implementation of the protocol, which allows flexible representations of buffers. -Climacs provides an implementation of buffers as a 2-3-tree of lines. -A line can be considered opened or closed. Editing operations are -performed on opened lines, which are represented as a cursorchain. A -fixed number of lines are kept opened according to a LRU scheme. When -a line is closed it is converted to a vector. If the line contains -only base-char objects this vector is a base-string; otherwise, it is -unspecialized. +The aim is for Climacs to provide several implementations of the +buffer protocol, one of which will use a sequence of lines organized +into a tree for quick access. In this implementation, a line can be +considered opened or closed. Editing operations are performed on +opened lines, which are represented as a cursorchain (a Flexichain +with an arbitrary number of cursors). A fixed number of lines are kept +opened according to a LRU scheme. When a line is closed it is +converted to a vector. If the line contains only base-char objects +this vector is a base-string; otherwise, it is unspecialized. +Currently, however, Climacs uses a single cursorchain for the entire +buffer, in effect making it a simple gap-buffer implementation. ``Protocol'' is not just an empty claim, as there are already multiple buffer implementations: Aleksandr Bakic's persistent buffer

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.tex
by bmastenbrook＠common-lisp.net 21 May '05

21 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv28137 Modified Files: climacssyntax.tex Log Message: MORE SYNTAX Date: Sat May 21 22:14:00 2005 Author: bmastenbrook Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.10 papers/ilc2005/syntax/climacssyntax.tex:1.11 --- papers/ilc2005/syntax/climacssyntax.tex:1.10 Sat May 21 18:32:16 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Sat May 21 22:14:00 2005 @@ -58,33 +58,38 @@ \section{Introduction} The field of advanced text editors is a crowded one, with a long -history and an apparent ability to cause passionate argument. Climacs is philosophically part of the Emacs editor tradition, which has spawned many variants with many different approaches to buffer management, incremental redisplay, and syntax analysis. +history and an apparent ability to cause passionate argument. Climacs is philosophically part of the Emacs editor tradition, which has spawned many variants with many different approaches to buffer 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}. -\begin{itemize} -\item TECO -\item emacs (Zmacs) (emacs time line) \cite{greenberg} -\item some kind of interlispy/smalltalky structure editor? -\item Z -- the 95\% text editor \cite{woodZ}. Note that WiB didn't - win! -\item Plan9 / Acme (mouse-oriented) \cite{Pike94} -\end{itemize} +\begin{figure*} \begin{center} +\begin{tabular}{|c|c|c|c|c|} +\hline \textbf{Editor} & \textbf{Buffer Implementation} & \textbf{Syntax Analysis} & \textbf{Language} +\\ +\hline TECO & Gap Buffer & Unknown & Assembly + TECO Macros +\\ +\hline Zmacs & Probably doubly-linked list of lines & None & MacLisp +\\ +\hline GNU Emacs & Gap Buffer & Regular Expressions & C + Emacs Lisp +\\ +\hline Hemlock & Doubly-linked list of lines & None & Common Lisp +\\ +\hline FRED & Gap Buffer & None & PPC Assembly + Common Lisp +\\ +\hline Deuce & Doubly-linked lists of lines & Unknown & Dylan +\\ +\hline Climacs & Multiple & Multiple & Common Lisp +\\\hline +\end{tabular} +\caption{Implementation strategies of multiple Emacs variants} \end{center} \label{table:editorcompare} \end{figure*} -Discuss lameness of emacs-like regexoid analysis in e.g. CL mode; -maybe mention how it falls over dramatically in perl mode (where -context starts really mattering) -\begin{itemize} -\item non-locality leading to confusion in \verb+#| |#+ -\item paren-in-column-1 hack (and its workaround in docstrings: - \verb+\(+) -\end{itemize} +Climacs' syntax analysis is a flexible protocol which can be implemented with a full language lexer and parser. GNU Emacs, the most commonly used Emacs-like editor, uses regular expressions for its syntax analysis. Because these regular expressions are applied lazily and not on the whole buffer, constructs such as Common Lisp's nestable \verb+#| |#+ block comments will often confuse the regular expressions. If the parser starts after the opening \verb+#|+ then the closing \verb+|#+ will be treated as the start of an escaped symbol name. Even if the regular expression parses the whole block comment 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' font-lock deficiencies. The Climacs text editor is a combination of frameworks for buffer representation and parsing 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 based on a circular gap buffer; and an implementation of a +management based on a linked lists of lines, some of which are represented as a circular gap buffer; and an implementation of a slight modification of the Earley parsing algorithm \cite{earley}, to -assist in the creation of syntax-aware editing modes. +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. The Climacs buffer protocol, which provides a standard interface to common text editor buffer operations, uses the Flexichain library; we

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.bib papers/ilc2005/syntax/climacssyntax.tex
by bmastenbrook＠common-lisp.net 21 May '05

21 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv15600 Modified Files: climacssyntax.bib climacssyntax.tex Log Message: Date: Sat May 21 18:32:16 2005 Author: bmastenbrook Index: papers/ilc2005/syntax/climacssyntax.bib diff -u papers/ilc2005/syntax/climacssyntax.bib:1.5 papers/ilc2005/syntax/climacssyntax.bib:1.6 --- papers/ilc2005/syntax/climacssyntax.bib:1.5 Fri May 20 16:44:55 2005 +++ papers/ilc2005/syntax/climacssyntax.bib Sat May 21 18:32:16 2005 @@ -145,4 +145,12 @@ year = {1994}, pages = {223-234}, bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@book{FinsethCraft, + author = {Craig A. Finseth}, + title = {The Craft of Text Editing}, + publisher = {Springer-Verlag}, + year = {1991, 1999--}, + note = {http://www.finseth.com/craft} } Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.9 papers/ilc2005/syntax/climacssyntax.tex:1.10 --- papers/ilc2005/syntax/climacssyntax.tex:1.9 Fri May 20 16:44:55 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Sat May 21 18:32:16 2005 @@ -33,7 +33,7 @@ \affaddr{Motorola}\\ \affaddr{1303 E. Algonquin Road}\\ \affaddr{Schaumburg, IL, USA 60196}\\ - \email{Brian.Mastenbrook(a)motorola.com} + \email{brian(a)mastenbrook.net} } \maketitle @@ -58,13 +58,10 @@ \section{Introduction} The field of advanced text editors is a crowded one, with a long -history and an apparent ability to cause passionate argument. - -[ Does anyone know enough about the history of editors? ] +history and an apparent ability to cause passionate argument. Climacs is philosophically part of the Emacs editor tradition, which has spawned many variants with many different approaches to buffer management, incremental redisplay, and syntax analysis. \begin{itemize} -\item ed -\item vi (vim) +\item TECO \item emacs (Zmacs) (emacs time line) \cite{greenberg} \item some kind of interlispy/smalltalky structure editor? \item Z -- the 95\% text editor \cite{woodZ}. Note that WiB didn't

1 0

[climacs-cvs] CVS update: papers/ilc2005/syntax/climacssyntax.bib papers/ilc2005/syntax/climacssyntax.tex
by crhodes＠common-lisp.net 20 May '05

20 May '05

Update of /project/climacs/cvsroot/papers/ilc2005/syntax In directory common-lisp.net:/tmp/cvs-serv17307 Modified Files: climacssyntax.bib climacssyntax.tex Log Message: One more prehistoric editor reference Date: Fri May 20 16:44:55 2005 Author: crhodes Index: papers/ilc2005/syntax/climacssyntax.bib diff -u papers/ilc2005/syntax/climacssyntax.bib:1.4 papers/ilc2005/syntax/climacssyntax.bib:1.5 --- papers/ilc2005/syntax/climacssyntax.bib:1.4 Fri May 20 15:35:22 2005 +++ papers/ilc2005/syntax/climacssyntax.bib Fri May 20 16:44:55 2005 @@ -136,4 +136,13 @@ isbn = {0-89791-050-8}, pages = {1--7}, location = {Portland, Oregon, United States}}, - } \ No newline at end of file + } + +@inproceedings{Pike94, + author = {Rob Pike}, + title = "{Acme: A User Interface for Programmers}", + booktitle = {USENIX Winter}, + year = {1994}, + pages = {223-234}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} \ No newline at end of file Index: papers/ilc2005/syntax/climacssyntax.tex diff -u papers/ilc2005/syntax/climacssyntax.tex:1.8 papers/ilc2005/syntax/climacssyntax.tex:1.9 --- papers/ilc2005/syntax/climacssyntax.tex:1.8 Fri May 20 15:35:22 2005 +++ papers/ilc2005/syntax/climacssyntax.tex Fri May 20 16:44:55 2005 @@ -69,6 +69,7 @@ \item some kind of interlispy/smalltalky structure editor? \item Z -- the 95\% text editor \cite{woodZ}. Note that WiB didn't win! +\item Plan9 / Acme (mouse-oriented) \cite{Pike94} \end{itemize} Discuss lameness of emacs-like regexoid analysis in e.g. CL mode; @@ -81,9 +82,9 @@ \end{itemize} The Climacs text editor is a combination of frameworks for buffer -representation and buffer contents parsing with a CLIM-based display -engine. It includes the Flexichain library \cite{flexichain}, which -provides an editable sequence representation and mark (cursor) +representation and parsing 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 based on a circular gap buffer; and an implementation of a slight modification of the Earley parsing algorithm \cite{earley}, to assist in the creation of syntax-aware editing modes. @@ -120,6 +121,12 @@ only base-char objects this vector is a base-string; otherwise, it is unspecialized. +``Protocol'' is not just an empty claim, as there are already multiple +buffer implementations: Aleksandr Bakic's persistent buffer +implementation, providing a cheap implementation of the undo protocol. +(FIXME: a citation, either to something ``in preparation'' or to some +previous description of the ideas?) + \section{Syntax Protocol} \label{sec:syntax} @@ -268,7 +275,14 @@ Ornaments are simple to model, as they are merely modifiers to note objects; higher-level grouping things (beams, connecting lines) have their own semi-independent identity, despite not being notated as such -in the textual \TabCode. +in the textual \TabCode. Beams and connecting lines can overlap +(thinking linearly, not on the manuscript!) in non-trivial ways: + +\begin{verbatim} + [ beamed section ] + word word word word word + ^____ line ____^ +\end{verbatim} Need whole-buffer function to present an alternative whole-system view on the data.

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

climacs-cvs May 2005