`Ever discovered after weeks of working on a software problem
`that yourcolleague down the hall solved it months ago?
`What you probably needed was a system likethis.
`
`
`A Browsing Approach
`
`to Documentation
`
`Yvan Leclerc, Steven W. Zucker, and Denis Leclerc, McGill University
`
`There are those who would argue that the OS/360six-foot
`shelf of manuals represents verbal diarrhea, that the very
`voluminosity of manualsrepresents a new kind of incompre-
`hensibility. And there is sometruth in that.
`
`Frederick P. Brooks, Jr.!
`
`AsBrooks implies above, the sheer volumeof informa-
`tion requiredfor researchfacilities to function makesthat
`self-same information both difficult to retrieve and dif-
`ficult to comprehend. His responseto this Catch-22situa-
`tion (in the case of the IBM 360) was to compilea carefully
`organizedset of manuals through whichspecific informa-
`tion suchasthedetails of a programminglanguageorthe
`parameters of a subroutine could beeasily found.
`While the time-honored technique of manually search-
`ing through extensive indexes does adequately allow for
`the retrieval of such information, it does notlenditself to
`the simple andleisurely discovery of that information. In
`other words, itis difficult to browse through the informa-
`tion in order to discover just whatis or is not available.
`Computerized documentation systems such as the VAX/
`VMS HELPfacility? offer more flexibility in their infor-
`mationretrieval capabilities than hard-copy manuals,but
`they are not particularly well-suited to browsingeither.
`The purposeofthis article is to describe one experimentin
`the design of adocumentation system that provides mech-
`anismsfor both needs—retrieval and comprehension.
`Thedecision to design and implement a documentation
`system with browsing capabilities was made when we
`noticed that many membersof our laboratory” tended to
`“‘reinventthe wheel’’ by needlessly duplicating the efforts
`of others in the laboratory. Even though these previous
`efforts were documented in various ways, most people
`were unawarethat a particular topic (e.g., fast Fourier
`transformsor pseudocoloring of images) had even been
`explored by another memberof the laboratory. Even
`
`“The McGill University Computer Vision and Graphics Laboratory.
`
`fewer knew precisely what that other memberhad done.
`Also, wheneverit was knownthat a particular topic had
`beeninvestigated by a particular person, the originalin-
`vestigator spent considerable time explaining exactly
`where the documentation for the topic was to be found
`andin furnishing general information aboutthe topic.
`We hoped that providing a documentation system that
`allowed people to both discover and quickly retrieve in-
`formation about
`the resources of the laboratory (re-
`sources such as software and hardware documentation,
`technical reports, etc.) would alleviate the above prob-
`lems. (It is also our experience that these informationdis-
`semination problemsare not unique to our laboratory. In
`fact, they are moreoften the rule than the exception.)
`
`System design
`
`the primary goal of our browsing
`As stated above,
`system was to provide a means for browsing through
`and/or quickly retrieving information about the labor-
`atory’s resources. Our needs, however, dictated that the
`implementation, and especially the maintenance,of the
`system require a minimum of manpower and on-line
`storage.
`
`Accessibility. Since executable programsare an impor-
`tant part of the resources of the laboratory, wefelt that,
`ideally, the documentation system should be accessible
`from within other programs and that other programs
`should be accessible from within the documentation
`system. For example, the former might be useful when
`editing a program (e.g., to find the parameters of an ex-
`ternal subroutine) and thelatter would allow a person to
`discover what programsare available without leaving the
`environmentof the documentation system. Both capabil-
`ities are provided in our current implementation.
`
`0018-9162/82/0600-0046$00.75 © 1982 IEEE
`
`COMPUTER
`
`46
`
`(cid:20)
`
`ELASTIC - EXHIBIT 1012
`ELASTIC - EXHIBIT 1012
`
`

`

`Humaninterface. One constraint on ourdesign of the
`humaninterface to the browsing system wasthe require-
`mentthat it be usable from a standardvideo terminal with
`minimal graphic capabilities. Inspired by the standard
`Lisp pretty-printed form of displaying lists, we chose the
`indented form of displaying a hierarchy illustrated in
`Figure 1. The desire for quick traversal of the graph led to
`single keystroke commands, whicharelisted at the bot-
`tom of the screen as a reminderto the user.
`Figure 2 illustrates the initial display of the browsing
`system. The design of the human interface wasalso in-
`spired, in part, by an application of the Zog system?to
`browsing through books andtechnicalreports.> In fact, a
`version of the browsing system could have been im-
`plemented in Zog, but
`this conflicted with our re-
`quirementsfor simplicity of implementation andefficien-
`cy of computation. Interested readers can find further
`details of the issues of a documentretrieval language in
`Gebhartand Stellmacher.® Note that only onelevel of the
`hierarchyisinitially visible in Figure 2, althoughellipses
`indicate that further levels exist. This is to simplify the
`user’s initial view of the system, but the display can be
`changed to view up to four levels of the hierarchy
`simultaneously. If the displayed hierarchy does notfit
`
`$1.1
`
`$1.2
`
`S1.4.1
`
`$1.1.2
`
`$1.21
`
`$1.2.2
`
`$1.2.3
`
`Figure 1. (a) A small hierarchy. (b) The same hierarchy
`displayed in the indented form used in the browsing
`system.
`
`(a)
`locate next page run sons top
`
`Press ‘‘i’’ for information.
`
`t L
`
`ATEST ENTRIES...
`AREAS OF RESEARCH...
`SUPPORTED SOFTWARE. . .
`AVAILABLE HARDWARE. . .
`REPORTS & THESES...
`DEMONSTRATION PROGRAMS... .
`PEOPLE POINTERS. . .
`SUGGESTION BOX...
`
`back exit father generations help information
`
`Figure 2. Theinitial display of the browsing system. The
`ellipses following the keywordsindicatethat the keyword
`has sons. Attached to each of these keywordsis anar-
`bitrary text file, which can be retrieved by moving the
`pointer(currently pointing to the topmost keyword) to the
`appropriate keyword and then pressing “i.” The set of
`available commandsare listed at the bottom of the
`screen.
`
`47
`
`(cid:21)
`
`Information organization. A capability for browsing
`requires both an appropriate presentation of individual
`items of information and an organizational context to
`facilitate the browsing. Thefirst need was met by naming
`each item of information explicitly so that it could be
`retrieved immediately once its name waslocated. In other
`words, each item of information, be it an executable pro-
`gram or some form of text, was assigned one or more
`keywords. The second need was met by making each entry
`short—short enoughto allow a large numberof them to
`fit on one page of a normaldisplay terminal—andthese
`keywords were then embeddedin a structure whosecate-
`gory nameswere also keywords.
`is, a
`We chose a multiple-parent hierarchy (that
`directed acyclic graph with a single root node) as the
`structural organization of the keywords. We did this
`because of the simplicity and flexibility of this type of
`organization. A strict hierarchy was considered too in-
`flexible because it forces each keywordentryto be placed
`in a specific category. This often leadsto difficulties both
`in searching andin categorizing information. At the same
`time, an arbitrary network of keywords, although quite
`flexible, is difficult for a person to grasp and follow. The
`compromise ofa hierarchy with multiple parents allows
`itemsof information to be found through multiple paths,
`yet it
`is simple enough that traversal of the graph is
`natural.
`Thus, for example, a general-purpose image-displaying
`program can becategorized under both IMAGE PRO-
`CESSING and GRAPHICSusing a multiple-parent
`hierarchy, rather than under just one or the other as
`would be necessarywith a strict hierarchy. As a result, the
`program can be found moreeasily, especially if the person
`searching for the program is not really sure where it
`belongs.
`‘
`
`Separation of organization and information. The
`hierarchy of keywords described above is kept
`in a
`separate network file, with the information associated
`with each keywordpointedto byfile names. The network
`file basically contains a doubly linked list of variable
`length records containing the keyword name,theassoci-
`ated file name, and pointersto the fathers and sonsof the
`keyword. The simplicity of this structure is possible
`primarily because the text information is kept separate
`from the organization.
`There are other important advantagesin storing the in-
`formation separately from the hierarchy:
`
`(1) Once a keyword hasbeen entered for a particular
`item of information, the information can be updated by
`the person responsible without
`the intervention of a
`“‘librarian.”’
`(2) Information need not be modified in any way to be
`incorporated into the browsing system.
`(3) The information can be created independently of
`the system without the need forspecial editors, thereby
`reducing the implementation cost.
`(4) Since informationis not stored explicitly, the struc-
`ture is relatively small and can be quickly andefficiently
`traversed by the system, allowing quick traversal of the
`graphbytheuser.
`
`June 1982
`
`

`

`n=
`SUPPORTED SOFTWARE
`1
`CHARACTER STRING MANIPULATION
`DISCARDING TRAILING BLANKS. .
`FILE NAME MANIPULATION...
`FREE FORMAT DECODING...
`KEYWORD MATCHING...
`TRANSLATING CASES...
`CVAGL UTILITY PROGRAMS
`DISPLAY
`PRETTY__PRINT
`SCANNER
`TEST PATTERN GENERATOR
`TYPE__VIDEO...
`GRAPHICS
`PROGRAMS...
`SUBROUTINES...
`HUMAN ENGINEERING AIDS
`KEYWORD MATCHING INPUT STREAM...
`VIDEO TERMINAL OUTPUT...
`IMAGE PROCESSING
`PROGRAMS...
`SUBROUTINES...
`SYSTEM UTILITIES
`back exit father generations help information
`
`Figure 3. Two levels of the keyword “SUPPORTED SOFT-
`WARE.” The “MORE...” indicates that the two levels
`could not fit completely on the screen. This display was
`obtainedby using the “generations” command preceded
`by the number“2.” (Optional numeric arguments,as for
`the ‘‘generations” command, appear after the “‘n =”of
`the top line of the display.)
`
`completely on thescreen, the user can scroll the display up
`or down.
`
`Figure 3 illustrates a case in which twolevels of a hier-
`archyare displayed simultaneously, while Figure 4 shows
`the displayed hierarchy scrolled down several
`lines.
`(Figure 4 also illustrates the multiple-parent hierarchy
`
`locate next page run sons top
`
`
`Add
`- Add the Input node to the network as the son of the ‘‘—"’ node.
`Back
`- Move the ‘‘—"’ back one page (22 lines) when possible.
`- Create a new node (call this the Input node).
`Create
`- Delete the ‘*—"’ node and all nodesisolated bythis deletion.
`Delete
`‘‘downarrow"’ * Movethe **—'' downwards (whennotavailable, use linefeed).
`Exit
`- Exit from the program, saving all modifications in a newfile.
`Father
`- Go to the father (super-category) of the current node.
`Generations
`* Specifies depth of subcategories seen simultaneously. Max (4).
`Help
`- Print this message.
`Information
` - Print the information associated with the ‘‘—"' node.
`Kill link
`- Kill (delete) the link from the Input node to the ‘‘—"' node.
`Locate
`- Search for the first match of the specified String in the net.
`Modify
`- Modify the ‘‘—** node and makeit the new Input node.
`Next
`- Search for the next match of the string in the net.
`Page
`- Move the ‘’—"’ forward one page (22 lines) when possible.
`Quit
`- Exit from the program without creating a newfile.
`Run
`- Run the program associated with the ‘‘—'’ node.
`Sons
`- List the sons (subcategories) of the ‘‘—’’ node.
`Top
`- Go to the top of the tree.
`“‘uparrow’’
`* Move the **—'' upwards (when not available, use backspace).
`Update
`- Update the network file.
`?
`- Print the namesofthefiles associated with the ‘‘~"’ node.
`
`“These commands have anoptional numeric argument enteredprior to the command.
`
`Figure 5. Asummaryof the commandsavailablein the browsingeditor.
`Notethat all of the commandsof the browsing systemare also com-
`mands of the browsing editor.
`
`48
`
`(cid:22)
`
`locate next page run sons top
`
`SUPPORTED SOFTWARE
`TRANSLATING CASES...
`CVAGL UTILITY PROGRAMS
`DISPLAY
`PRETTY__PRINT
`SCANNER
`TEST PATTERN GENERATOR
`TYPE__VIDEO...
`GRAPHICS
`PROGRAMS...
`SUBROUTINES...
`HUMANENGINEERING AIDS
`KEYWORD MATCHING INPUT STREAM... .
`VIDEO TERMINAL OUTPUT...
`IMAGE PROCESSING
`PROGRAMS...
`SUBROUTINES...
`SYSTEM UTILITIES
`COMMAND LANGUAGE INTERPRETER
`VIDEO TERMINAL OUTPUT
`MCG__TERM__TYPE
`NEW__PAGE
`PRINT__HELP. . .
`-
`back exit father generations help information
`
`Figure 4. Twolevels of the keyword “SUPPORTED SOFT-
`WARE?”scrolled downseverallines. Notice that the arrow
`now points to the keyword “PRINT__HELP”andthat the
`system is indicating that more of the hierarchy can be
`displayed by the two symbols “MORE...”
`
`the keyword ‘“‘VIDEO TERMINAL
`concept;
`OUTPUT” is a son of both ‘““SSUPPORTED SOFT-
`WARE” and ‘‘HUMAN ENGINEERINGAIDS.’’)
`The user moves downthe hierarchy by moving the
`pointer (in the top left-hand corner of Figure 2) up or
`downonthe screen to the desired keyword, typing ‘‘s’’ to
`view its sons. The user can move upthehierarchyonelevel
`at a time (retracing his or her steps down thehierarchy), or
`can movedirectly back to the top. The user canalso locate
`a specific keywordby entering either a full keywordorits
`abbreviation. The browsing system then searches for the
`first matching keyword from thetopof the hierarchy (us-
`ing a depth-first search). If the matched keywordis not
`the one the user wanted, he or she can force the system to
`go on to the next match.
`Once theuser has placed the pointerat an appropriate
`keyword, the associated information can bedisplayed on
`the screen or the associated program run. The user can
`always return to the browsing system via a control
`character, giving him or her the freedom to experiment.
`
`Creating and modifying a network. Anyuser can create
`and modify a personal browsing network, although a
`passwordis required to modify the (default) system net-
`work. A different program is used for this, one thatis a
`superset of the normal browsing system. In other words,
`every commandin the browsing systemis also available in
`the browsing editor, along with extra commandsto
`create, insert, delete, and modify keywordentries.
`There are two requiredsteps for creating a new entry.
`First, anew nodeis created, specifying the keyword name
`and the associated text and/or executable file name(s).
`
`COMPUTER
`
`

`

`2.
`
`Second, the new nodeis added to the networkas the son
`References
`of one or more other nodes. Onceanodehasbeen entered,
`its keyword name and/orfile name can be modified andit
`1. F. P. Brooks, Jr., The Mythical Man-Month—Essays on
`Software Engineering, Addison-Wesley, Reading, Mass.,
`can be moved aboutthe networkat will by removing and
`1975, p. 134.
`adding links from it to other nodes. Figure 5 lists the com-
`‘‘VAX/VMS Command Language User’s Guide,’’
`mandsavailable for doing this in the browsing editor.
`AA—D023B-TE, Digital Equipment Corporation,
`The approach weusedin building the system network
`Maynard, Mass., 1980.
`wasto proceed from the abstract to the concrete. The top
`3. G. Robertson, A. Newell, and K. Ramakrishna, ‘‘ZOG: A
`level of the hierarchy is the most abstract, representing
`Man-Machine Communication Philosophy,’’ Carnegie-
`various points of view that a user might have whenenter-
`Mellon University Technical Report, Carnegie-Mellon
`ing the system. For example, a personinterested in seeing
`University, Pittsburgh, Pa., Aug. 5, 1977.
`the type of research carried on in the laboratory might
`4. G. Robertson, D. McCracken, and A. Newell, ‘‘The ZOG
`start searching through the ‘‘AREAS OF RESEARCH”’
`Approach to Man-Machine Communication,’’ Carnegie-
`Mellon University Technical Report, Carnegie-Mellon
`keyword; a visitor to the laboratory might first search
`University, Pittsburgh, Pa., Oct. 23, 1979.
`through the
`‘‘DEMONSTRATION PROGRAMS”
`5. M.S. FoxandA. J. Palay, ‘“The BROWSESystem, PartI:
`keyword to get a glimpse of the current work; while a
`An Introduction,’? Computer Science Department,
`veteran user might be more inclined to start with the
`Carnegie-Mellon University Technical Report, Carnegie-
`‘““LATEST ENTRIES” keyword to see whathasrecently
`Mellon University, Pittsburgh, Pa., 1979.
`been added to the network.
`6. F. Gebhart and I. Stellmacher,
`‘‘Design Criteria for
`Documentation Retrieval Languages,’’ J. Am. Soc. Infor-
`mation Science, Vol. 29, No. 4, July 1978, pp. 191-199.
`
`As a user moves down the hierarchy, the keywords
`becomeincreasingly more specific, with the lowest-level
`keywords typically pointing to programs, subroutine
`sources,
`technical
`reports, etc. The multiple-parent
`feature of the system was used extensively to allow
`keywordsto be found througha variety of paths, easing
`the discovery of information by the user.
`
`Conclusions
`
`Yvan G. Leclere is currently working
`toward a PhD inthefield of computervi-
`sion at McGill University. His research in-
`terests include computervision, the char-
`acterization of local vs. global computa-
`tions, and cooperative processing. Other
`academic interests include the general
`study of humanintelligence (from both the
`_ psychological and artificial
`intelligence
`points of view), and the humanengineer-
`inggot computer systems.
`Leclerc received the M. Eng. and B. Eng. degreesin electrical
`engineering from McGill University in 1980 and 1977, respec-
`tively. He is currently a student memberof the IEEE and ACM.
`
`
`
`
`
`
`The browsing system has been implemented as de-
`scribedin this article. To date, it has been used primarily,
`though notexclusively, to document software developed
`in ourlaboratory. This has been done in conjunction with
`a prior commitmentto the use of a standard header page
`preceding every piece of software created in ourlabratory.
`Thus, for the mostpart, the browsing system is pointing to
`files starting with a standard header page, which makesfor
`a consistent view ofthe available software.
`Steven W. Zuckeris currently an associate
`The system hasbeenvery helpfulin alleviating needless
`professor in the Departmentof Electrical
`duplication of effort by providing a meansfor discover-
`Engineering, McGill University, Mon-
`ing, in a simple manner, what other people have done.
`treal, P.Q., Canada and is codirector of
`the Computer Vision and Graphics Lab-
`And, perhaps more importantly, the development and
`oratory there. His research interests in-
`maintenance costs were quite reasonable (two to three
`clude computer vision, humanperception,
`man-monthsfor designing and implementing the system,
`andartificial intelligence. He received the
`with another man-monthfor organizing the information
`BS degree in electrical engineering from
`in the network), demonstrating the feasibility of im-
`Carnegie-Mellon University in 1969, and
`the MS and PhD dearetysin biomedical engineering from Drexel
`plementing useful documentation systemsat a reasonable
`University, Philadelphia, in 1972 and 1975, respectively.
`cost. When these costs are compared with the time that
`From 1974 to 1976 he wasaresearch associateat the Picture
`our expert users no longer have to expend to simply
`Processing Laboratory, Computer Science Center, University of
`disseminate information, the investment seems eminently
`Maryland, College Park.
`Zucker is a member of Sigma Xi, ACM,and the IEEE.
`worthwhile. In short, the system is working as planned.
`
`Acknowledgments
`
`The authorsare grateful to John Mohammed, David
`Kashtan, Harold Hubschman, and Peter Sanderfortheir
`help in designing the browsing system, and for their
`critical comments and helpful suggestions concerningthis
`article.
`This research was supported in part by NSERC grant
`number A4470 andin part by the Quebec Department of
`Education.
`
`
`
`Denis Leclerc is currently in the master’s
`degree program in computer science at
`McGill University, working in the program-
`ming languages area. Heis also working
`part-time at Bell Northern Research on a
`text-to-speech conversion system. His re-
`search interests
`are programming lan-
`guages, compiler optimization, and natural
`language understanding. He received the
`BSc degree in mathematics and computer
`science from McGill University in 1980.
`
`June 1982
`
`49
`
`(cid:23)
`
`