Description
Building a good user interface requires many tradeoffs. As such, there may be no "best" solution for any individual subtask. This thesis discusses many of the tradeoffs involved and develops algorithms for displaying, entering, and selecting from expressions. Two new algorithms for incremental parsing of input are presented. Either algorithm can be coupled with the incremental reformatting and screen update algorithm developed in this thesis to produce an interface capable of correctly updating and displaying changes to relatively large expressions in real-time. Moreover, algorithms that exploit locality for the selection of subexpressions are also given. These selection algorithms are also capable of providing real-time feedback as to what is being selected.
Because Computer Algebra Systems generate large expressions, efficiency in both time and space are important. Data is presented that shows that using directed acyclic graphs as the fundamental underlying data structure instead of trees significantly decreases time and space usage. The ability to display large expressions efficiently must be coupled with the ability to manipulate them into understandable forms. This thesis discusses three such techniques: elision, renaming of subexpressions, and line breaking. Two new algorithms are given for incrementally reformatting expressions in the presence of line breaks.
This thesis introduces the idea of translations. Translations convert between the form used by a Computer Algebra System and the mathematical notation displayed on the screen. Translations increase the portability of the interface and allow it to communicate with different Computer Algebra Systems during a single session. Translations can be grouped together to form notation libraries which can be used to eliminate some of the ambiguity inherent in mathematical notation.