The Design of a User Interface for Computer Algebra Systems

Neil Morrell Soiffer

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-91-626

, 1991

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/CSD-91-626.pdf

This thesis discusses the design and implementation of natural user interfaces for Computer Algebra Systems. Such an interface must not only display expressions generated by the Computer Algebra System in standard mathematical notation, but must also allow easy manipulation and entry of expressions in that notation. The user interface should also assist in the understanding of large expressions that are generated by Computer Algebra Systems and should be able to accommodate new notational forms. 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.

Advisors: Richard J. Fateman

BibTeX citation:

@phdthesis{Soiffer:CSD-91-626,
Author= {Soiffer, Neil Morrell},
Title= {The Design of a User Interface for Computer Algebra Systems},
School= {EECS Department, University of California, Berkeley},
Year= {1991},
Month= {Apr},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6400.html},
Number= {UCB/CSD-91-626},
Abstract= {This thesis discusses the design and implementation of natural user interfaces for Computer Algebra Systems. Such an interface must not only display expressions generated by the Computer Algebra System in standard mathematical notation, but must also allow easy manipulation and entry of expressions in that notation. The user interface should also assist in the understanding of large expressions that are generated by Computer Algebra Systems and should be able to accommodate new notational forms. 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.},
}

EndNote citation:

%0 Thesis
%A Soiffer, Neil Morrell 
%T The Design of a User Interface for Computer Algebra Systems
%I EECS Department, University of California, Berkeley
%D 1991
%@ UCB/CSD-91-626
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6400.html
%F Soiffer:CSD-91-626