COMPUTING
`PRACTICES
`
`Controlling the Complexity of Menu
`Networks
`
`James W. Brown
`Jet Propulsion Laboratory
`
`1. Introduction
`There are many techniques com-
`monly used for communication be-
`tween humans and computer sys-
`tems. They vary widely in their ease
`of learning and use, and their general
`applicability. One technique for hu-
`man-computer interaction is menu
`selection. It makes the most of the
`computer's ability to find and display
`large quantities of information rap-
`idly and the human's ability to make
`decisions in the context of a specific
`problem. It also recognizes the slow-
`ness of the input channel, i.e., fingers
`typing (or hunt and pecking) on a
`keyboard.
`2. Menu Networks
`The menu selection technique
`presents the user with a sequence of
`"frames" or "pages," each contain-
`ing some text and a list of options.
`The text offers information to the
`user, and the options allow the user
`to choose what to do or where to go
`
`CR Categories and Subject Descriptors: H. 1.2
`[Models and Principles]: User/Machine Sys-
`tems_human factors; H.3.3 [Information Stor-
`age and Retrieval[: Information Search and
`Retrieval-query formulation; H.3.5 [Informa-
`tion Storage and Retrieval]: On-Line Infor-
`mation Services.
`General Terms: Design, Human Factors.
`Additional Key Words and Phrases: Menu
`systems, graphs, networks, structured design
`tools.
`This paper presents the results of one phase
`of research conducted at the Jet Propulsion
`Laboratory, California Institute of Technol-
`ogy, under Contract NAS7-100, sponsored by
`the Information Systems Office of the Na-
`tional Aeronautics and Space Administration,
`Office of Space Science and Applications.
`Author's present address: J.W. Brown, Jet
`Propulsion Laboratory, California Institute of
`Technology, 4800 Oak Grove Drive, Pasa-
`dena, CA 91109.
`© 1982 ACM 0001-0782/82/0700-0412 75¢.
`412
`
`SUMMARY: A common approach to the design of user inter-
`faces for computer systems is the menu selection technique.
`Each menu frame can be considered a node in an information/
`action network. The set of nodes and the permissible transi-
`tions between them (menu selections) form a directed graph
`which,
`in a system of substantial size, can be large and
`enormously complex. The solution to this problem of unman-
`ageable complexity is the same for menu networks as for
`programs: the disciplined use of a set of well-defined one-in-
`one-out structures. This paper defines a set of such structures
`and offers some guidelines for their use.
`
`next, from a limited set of possibili-
`ties. The user indicates a choice by
`typing a single character, pointing,
`or other techniques [4]. The selection
`made determines which frame will
`be displayed next.
`Since each frame has several op-
`tions linking it to other frames, a
`frame can be thought of as a node in
`a network or graph, and the option
`links then correspond to "arcs" or
`"edges." Moreover, since the option
`selection represents a one-way tran-
`sition from one node to the next, the
`menu
`system
`(the collection of
`frames and option links) forms a di-
`rected graph.
`Menu
`systems are commonly
`used for two purposes: controlling
`the actions of computer applications
`systems and presenting information.
`
`In the illustrations we have taken some
`liberties with the graph-theoretic notion of an
`arc, several arcs having been combined into
`one with the joining dot notation.
`Communications
`of
`the ACM
`
`Systems of the former type typically
`contain tens or hundreds of frames,
`with the latter possibly containing
`tens of thousands [7, 8]. If the links
`between frames allow for great rich-
`ness of interconnection, the resulting
`graph can become so complex that
`understanding or modification be-
`comes virtually impossible.
`Such a situation is analogous to
`the unmanageable complexity which
`can occur with a large computer pro-
`gram containing many multiway
`branches; e.g., a program whose con-
`trol flow consists of a hundred to ten
`thousand computed ~OTOS, each
`with six to eight destinations, all in-
`terconnected, apparently at random.
`This kind of disaster has been
`averted by several modern
`tech-
`niques, especially top-down struc-
`tured programming.
`In fact,
`that
`technique suggests a useful approach
`to the design of menu networks,
`which can be called "structured
`subgraphs."
`July 1982
`Volume 25
`Number 7
`
`SKYHAWKE Ex. 1023, page 1
`
`

`

`-~.j
`-
`,,,.J
`CONCATENATION (SEQUENCE)
`
`SELECTION (IF - THEN - ELSE)
`
`third form, iteration, is the strangest.
`It is hard to imagine many uses for
`such a structure in a menu system.
`Soon we shall see that the value of
`the basic structures lies in using them
`as
`templates for combining more
`complex structures.
`4. Extended Structures
`As in structured programming,
`the basic structures are rather confin-
`ing, and so we look for useful ways
`to generalize them. Figure 2 illus-
`trates three generalizations which are
`very useful in real applications. The
`
`proach can be observed throughout
`a network which provides shortcuts
`for experienced users. It is also useful
`for implementing other kinds of op-
`tional side paths.
`The second extended structure,
`the "one-of-N," is the most common
`in most systems. It is the basis for the
`term "menu selection" and, as we
`shall see, generalizes into a tree struc-
`ture, which is a very common form
`of a menu network.
`The
`third extended
`structure,
`"M-of-N," is less commonly seen but
`is very useful. It permits the user to
`pick any number of entries (includ-
`ing zero) from a list, in any order.
`This is very important in applica-
`tions with no obvious, natural order
`for presenting things. In such cases
`each user needs the freedom to make
`decisions in the order that seems ap-
`propriate at the time, given the user's
`specific knowledge, background, and
`orientation with respect to the prob-
`lem at hand.
`5. HELP Facilities
`Menu systems are typically used
`in applications with little or no user
`training involved. A very well-de-
`signed menu network would be com-
`pletely self-teaching, unambiguous,
`
`OPTION (IF- THEN)
`
`1 OF N (CASE)
`
`ITERATION (DO - WHILE)
`Fig. 1. Basic Structured Subgraphs.
`
`3. Basic Structures
`Following the example of struc-
`tured programming, we define a
`basic set of one-in-one-out elemen-
`tary graphs, which can be used as
`building blocks to form arbitrarily
`large networks. Like the control-flow
`graph of a structured program, any
`network constructed by appropriate
`concatenation or nesting of these
`structures will be representable as a
`planar graph. In yet another analogy
`to structured programming, we find
`that three basic structures, equivalent
`to sequence, selection, and iteration,
`are sufficient to deal with a wide
`variety of applications, but some or-
`derly extensions
`to
`these provide
`much greater convenience and clar-
`ity.
`Figure l presents the three basic
`structures. The terms in parentheses
`relate the structures to commonly
`used programming constructs. We
`see that these do not represent very
`interesting or useful cases in the con-
`text of menu systems. The first, con-
`catenation, simply
`leads
`the user
`from one frame to the next without
`the necessity or opportunity of mak-
`ing any decision. The two frames
`could have been combined into one.
`The second structure, selection, al-
`lows the user a choice between two
`options. This is useful in some in-
`stances, but rather restrictive. The
`413
`
`M OF N
`(o_<M_< N)
`Fig. 2. Extended Structured Subgraphs.
`
`(CASE + WI.flLE)
`
`HELP (CALL- RETUI~I)
`
`first is a modification of IF-THEN-
`ELSE having a null ELSE-branch. This
`is commonly the entry point to any
`kind of menu network. The first
`frame asks, "Do you know how to
`use
`the system, or do you need
`help?"
`The second frame (the THEN-
`branch) provides an explanation of
`how to use the system and proceeds
`back (without the need for user ac-
`tion) to the "main-line." This ap-
`Communications
`of
`the ACM
`
`PREVIEW HELP
`Fig. 3. HELP Structures.
`
`July 1982
`Volume 25
`Number 7
`
`SKYHAWKE Ex. 1023, page 2
`
`

`

`COMPUTING
`PRACTICES
`
`and surprise-free. It may be possible
`to approach this ideal in application
`areas whose underlying subject mat-
`ter has a well-defined and well-
`known structure, and the wording of
`the menu frames and options is care-
`fully polished by incorporating feed-
`back from many users over a long
`period of time. However, this degree
`of refinement cannot be achieved in
`many cases, and so it is necessary to
`provide HELP facilities which can be
`invoked when a user becomes con-
`fused.
`Figure 3 illustrates one approach
`to providing such a facility. The help
`option is not explicitly included in
`the main frame's option list, but is
`invoked instead by some special,
`global mechanism. This mechanism
`may involve keying in "HELP", a "?",
`or simply "H", or pressing a special
`HELP key on terminals so equipped.
`This simple mechanism can only in-
`voke a single help frame from any
`given main frame, although the help
`frame itself may generalize to a help
`network.
`An extension of this technique is
`"preview help." This associates a dif-
`ferent help frame with each option
`on the main frame. If an option is
`selected by entering a corresponding
`digit or letter, the help frame for that
`option can be selected by preceding
`or following the selection character
`with a question mark. Preview help
`is useful when a user does not un-
`derstand the implications of making
`a particular selection and is afraid to
`"leap" before looking. The user can
`ask for clarification about any or all
`options before selecting one.
`What is important to note about
`these help structures is that they are
`analogous to subroutine calls. They
`always return
`to the place from
`which they were called. No special
`action from the user, beyond perhaps
`indicating "ready," should be re-
`quired to cause the return.
`414
`
`In order to keep drawings of the
`graphs uncluttered, help
`frames
`should not normally be included ex-
`plicitly in the drawings. In practice,
`a well-designed network would in-
`clude both types of help structures at
`every decision node where confusion
`might possibly arise. Single frames
`for each help node are usually best.
`Expanding a help node into a more
`complex subnetwork runs the risk of
`causing the user to forget why help
`was requested in the first place or
`that the current context is a help
`network rather
`than
`the "main"
`one.
`
`6. Building Composite
`Structures
`As in top-down structured pro-
`gramming, large networks can be
`constructed by combining the basic
`structures in two ways: nesting and
`
`concatenation. These are illustrated
`in Figure 4. Nesting is performed by
`replacing any single-exit node with a
`one-in-one-out structure. Concate-
`nation simply connects the outgoing
`"half-arc" of one structure with the
`incoming half-arc of another. Where
`arcs join at joining dots, they can be
`redrawn to terminate properly on
`frame nodes. This appears to destroy
`the one-in-one-out property, but it
`actually does not. An alternative
`would be to define the joining dots
`as null nodes and keep them in the
`graph. This is simply a matter of the
`convenience of external representa-
`tion versus mathematical rigor. The
`representation can be chosen to suit
`the purpose.
`If the concatenation is done with-
`out crossing any lines, the graph al-
`ways remains planar and well-struc-
`tured. How important this is remains
`to be determined.
`
`Fig. 4. Building Composite Structures.
`Communications
`of
`the ACM
`
`July 1982
`Volume 25
`Number 7
`
`SKYHAWKE Ex. 1023, page 3
`
`

`

`Figure 5. However, it is greatly dif-
`ferent, both topologically and psy-
`chologically. It extends uniformly to
`any N, without becoming nonplanar.
`It is used to allow the user to choose
`many or all of the N selections with-
`out returning to the precedent node.
`Its successful use necessitates that the
`list of selections be either short and
`simple enough for the user to keep
`in short-term memory (since it will
`not be seen again) or sufficiently reg-
`ular so individual items do not have
`to be remembered (e.g., the months
`of the year). It also requires that the
`user know
`in advance something
`about the local topology, and that
`each of the N selectable nodes be
`simple and nonconfusing.
`The "next" option appears to be
`appropriate only with the
`l-of-N
`structure. It can be generalized to the
`"circular next" at the cost of intro-
`ducing a minor local nonplanarity.
`This does not appear to be too trou-
`blesome as long as the user is able to
`cope with the "next" concept in the
`first place.
`8.
`Is the GOTO Harmful?
`In considering the GOTO state-
`ment, we perhaps come to a place
`where the analogy between menu
`networks and computer programs
`weakens. A branch implies a deci-
`sion, and in a menu network the
`decision-maker is a human being.
`The human user is present precisely
`because the decisions required can-
`not be preprogrammed. On the other
`hand, the user has a very limited
`ability
`to comprehend
`the static
`structure of an entire large network,
`whereas the computer can do so with
`ease. None of this tells us whether it
`is safe or desirable to use GOTO, only
`that the lessons learned in program-
`ming [2] may need to be modified.
`We should note that there are
`two types of GOTO in a menu system:
`a static or preprogrammed path in
`the network which violates the basic
`structuring rules, and a dynamic
`jump which a user may wish to con-
`struct from any node to any other.
`The first may be likened to an ex-
`press highway allowing a large vol-
`ume of traffic to bypass the local
`Communications
`of
`the ACM
`
`Fig. 5. A Nonstruetured Planar Subgraph.
`
`7. Noncanonical Forms
`At this point one might well ask
`whether the structures and opera-
`tions described above are sufficient
`for all interesting applications. In the
`case of programming,
`the answer
`would be a fairly emphatic yes (al-
`though with certain applications one
`must add provisions for dealing with
`interrupts and concurrent processes).
`In the case of menu systems, the
`answer might be no. There is at least
`one type of commonly encountered
`network, which is known to be useful
`although highly nonplanar. This is
`the cross-linked, multiple-tree struc-
`ture often seen in multiply-indexed
`library databases, organization/per-
`son/task networks, and elsewhere.
`An important question is whether
`organizing information into network
`structures which seem "natural," al-
`though not "structured" in the sense
`defined above, leads to problems of
`unmanageable complexity when the
`networks become large. Our initial
`experience, discussed below, indi-
`cates that it may.
`What are some other possibly
`useful forms? The subgraph in Fig-
`ure 5 is simple-looking, planar, one-
`in-one-out, but note that it cannot be
`extended to more (or less) than three
`selection nodes without destroying
`some of its properties. (Observe that
`the 1-of-N and M-of-N
`structures
`extend uniformly for any N greater
`than zero.) A fourth selection node,
`with an arc leading from the existing
`center node, cannot be added with-
`out making
`the result nonplanar.
`Would such a structure be useful in
`a real menu system? Perhaps, but it
`might also be a warning signal that
`some redesign is in order.
`Figure 6 presents a structure that,
`at first glance, seems the same as
`415
`
`road network, or to a direct trunk
`group bypassing the basic hierarchy
`of a telephone network. The second
`type is more akin to teleportation,
`allowing the user to arrive instantly
`at any desired destination without
`having to pass the places between the
`jump-off point and the destination.
`Direct
`paths
`are
`commonly
`found in the kinds of networks men-
`tioned above, and they seem to be
`useful and manageable. Both the
`highway network and the telephone
`network are larger than any menu
`network we are soon likely to see, yet
`users can navigate them with ease.
`Maintaining and modifying them re-
`quire massive efforts, but these ef-
`forts do not grow disproportionately
`with the size of the networks.
`Conversely, the phenomenon of
`users becoming lost or disoriented in
`menu systems is common enough
`[7], except perhaps
`in networks
`which are simple trees. Without a
`great deal of difficult experimenta-
`tion 2, it is impossible to relate the
`likelihood of getting lost with any
`measure of network complexity :~.
`
`[5] outlines some directions such exper-
`imentation might take.
`:~ [1] discusses the relative merits of sev-
`eral complexity measures.
`
`I OF N WITH NEXT
`
`1 OF N WITH CIRCULAIt NEXT
`Fig. 6. The "Next" Option.
`
`July 1982
`Volume 25
`Number 7
`
`SKYHAWKE Ex. 1023, page 4
`
`

`

`COMPUTING
`PRACTICES
`
`9. Implementation Experience
`The ideas described above were
`developed in the course of designing
`the menu-driven user interface for
`the NASA Oceanic Pilot System.
`This system is a pilot project in-
`tended to demonstrate techniques for
`providing convenient, rapid access to
`large volumes of satellite-derived
`data for the oceanographic research
`community. One of the requirements
`for the system is that infrequent,
`nonexpert users be able to easily use
`it. For this reason the menu selection
`technique was chosen as the primary
`user interface. Command language
`and OBMS query language interfaces
`supplement the menu interface for
`expert users.
`The menu interface allows access
`to the following basic system capa-
`bilities:
`(1) A bibliography of ocean remote
`sensing literature;
`(2) A directory of available data
`sets, consisting of high-level
`"abstracts" and availability in-
`formation;
`(3) A detailed inventory of avail-
`able data, including temporal
`and spatial location and access
`information;
`(4) Extraction
`of user-specified
`subsets of the archival data sets;
`(5) Formatting of extracted data
`into a variety of output prod-
`ucts, such as tabulations, plots,
`maps, magnetic tapes, and disk
`files;
`(6) Support functions such as sav-
`ing and retrieving request spec-
`ifications and files, status mon-
`itoring, accounting, etc.
`In addition,
`the menu system in-
`cludes a self-teaching option for new
`users. This feature guides the user
`through the various capabilities of
`the menu processor itself and pro-
`vides brief overviews of the various
`system capabilities.
`416
`
`A prototype menu network was
`initially designed and implemented
`with the designers' view of a typical
`use scenario in mind. The prototype
`network consisted of about 50 nodes,
`organized without
`regard
`to
`the
`structuring ideas described above.
`When the prototype was exposed to
`trial users, who were in fact more
`knowledgeable about
`the system
`than real users were expected to be,
`several important points quickly be-
`came evident. First, users can easily
`get lost in even a relatively small
`network. Second, users demand
`more flexibility in the order in which
`they specify or receive information
`than designers are likely to think
`necessary. Third, modifying an un-
`structured network, even if small, is
`unacceptably difficult.
`These observations
`led
`to the
`conclusion that a more disciplined
`methodology would be needed for
`the real network. The author's ex-
`perience with top-down structured
`programming led naturally to the
`ideas discussed in this paper. A re-
`view of the literature on human fac-
`tors in computer systems, starting
`with [6], indicated
`that no other
`work had been done in this area.
`Therefore, the concepts presented
`here may be considered tentative
`first steps in this direction.
`Although our prototype menu
`network proved imperfect, the results
`of our application were encouraging.
`The version of the network delivered
`for initial operational use is nearly
`an order of magnitude larger than
`the prototype, as illustrated in Table
`
`I. It has undergone several modifi-
`cations as features were added or
`relocated, but all changes have been
`made smoothly. Users still get lost
`occasionally, but not as frequently as
`in
`the prototype. It is not clear,
`though, that the structuring was re-
`sponsible for the latter effect, since
`considerable effort also went into
`polishing the wording of those menu
`frames which caused confusion.
`One area of the implementation
`which remains unsatisfactory is the
`bibliography. The initial version pro-
`vides access only by subject and is
`organized as a basic tree with limited
`cross-indexing added. The effort re-
`quired to organize the references into
`a hierarchy of subject categories and
`then implement the access frames
`was substantial. In addition, users
`sometimes want access by author,
`institution, title, report type, project,
`sensor, and key word. Creating ac-
`cess trees for each of these categories
`is a formidable task and still would
`not always provide the kinds of mul-
`tiple selectors which users desire.
`As a result, we plan to redesign
`the bibliography as a relational data-
`base, using the menu system to help
`users build queries. This is expected
`to yield much more flexible and se-
`lective access for users, while sub-
`stantially reducing the effort of add-
`ing new entries to the database.
`10. Design Aids
`The initial version of the frame
`network was developed manually,
`assisted by a single program which
`analyzes the network and produces
`
`I
`Table I. Oceanic Pilot System Menu Network~lnitial Version.
`Category
`Number of
`non-HELP Frames
`
`Bibliography
`access paths
`citations
`Data set directory
`access paths
`citations
`Data inventory and extraction
`Output product specification
`Support (request manipulation, file saving, etc.)
`Tutorial
`Total
`72 frames invoke 67 programs as subprocesses.
`
`50
`203
`17
`10
`37
`34
`21
`20
`392
`
`Communications
`of
`the ACM
`
`July 1982
`Volume 25
`Number 7
`
`Number of
`HELP Frames
`1
`
`1
`
`13
`12
`21
`3
`51
`
`SKYHAWKE Ex. 1023, page 5
`
`

`

`Oceanic P i l o t S~stem Menu Network
`
`DO S P e c i f ~ _ P l a t f o r m _ s e n s o r _ P a r a m e t e r s _ o f _ i n t e r e s t . . . . . . . . . . .
`
`95 SECTION C o n s t r u c t _ a _ r e a u e s t
`96
`LOOP u n t i l case 6 o r 7 i s s e l e c t e d
`97
`'You w i l l g e t a chance t o r e v i e w and modif~ ~our r e e u e s t '
`You can r e t u r n t o t h i s P a g e a s '
`98
`' b e f o r e e x e c u t i n g i t .
`99
`" o f t e n as necessar~ t o complete i t . '
`100
`SELECT menu o p t i o n :
`101
`CASE 1:
`102
`DO S P e c i f , _ r e g i o n _ o f _ i n t e r e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`103
`CASE 2t
`104
`DO S P e c i f , _ t i m e _ s P a n _ o f _ i n t e r e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`105
`CASE 3:
`106
`
`107
`CASE 4:
`108
`DO S P e c i f ~ _ P r o c e s s i n g _ l e v e l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`109
`CASE 5:
`110
`DO Check_comPleteness_of_reeuest . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`111
`CASE 6¢
`112
`DO C o n s t r u c t _ o u t p u t _ P r o d u c t _ r e Q u e s t . . . . . . . . . . . . . . . . . . . . . . . . .
`113
`CASE 7~
`114
`GOTO M o d i f y _ o r _ P r o c e s s _ r e q u e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`115
`ENDSELECT
`116
`REPEAT u n t i l case 6 or 7 i s s e l e c t e d
`117 END
`118 SECTION M o d i f ~ - o r _ P r o c e s s _ r e a u e s t
`119
`LOOP u n t i l case 7 i s s e l e c t e d
`120
`CALL Check~request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`121
`PAUSE
`122
`SELECT menu o p t i o n :
`123
`CASE 1:
`124
`DO D i s p l a y _ r e Q u e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`125
`CASE 2:
`126
`DO M o d i f y _ r e Q u e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`127
`CASE 3:
`128
`DO S a v e _ r e e u e s t _ f o r _ f u t u r e _ u s e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`129
`CASE 4:
`130
`DO E x e c u t e _ s a m P l e _ o f _ r e e u e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`131
`CASE 5:
`132
`DO E s t i m a t e - c o s t _ f o r _ f u l l _ r e a u e s t . . . . . . . . . . . . . . . . . . . . . . . . . . .
`133
`CASE 6:
`134
`DO E x e c u t e _ f u l l _ r e Q u e s t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`135
`CASE 7:
`t o B e g i n _ r e Q u e s t _ s P e c i f i c a t i o n (Erase and r e s t a r t )
`136
`E×i t
`137
`ENDSELECT
`138
`REPEAT u n t i l case 7 i s s e l e c t e d
`139 END
`
`>( 4)
`
`>(
`
`5)
`
`>( 5)
`
`>( 5)
`
`>( 10)
`
`>( 10)
`
`>( 3)
`
`> ( 2 9 )
`
`>( 19)
`
`>( 19)
`
`> ( 2 1 )
`
`> ( 2 2 )
`
`> ( 2 2 )
`
`> ( 2 2 )
`
`Fig. 7. SDDL Printout of Two Menu Subnetworks.
`
`8 - - C o n s t r u c t a r e e u e s t
`PAGE
`You w i l l get a chance t o r e v i e w and m o d i f y your r e e u e s t b e f o r e e×e c u t i n ~
`i t .
`You can r e t u r n t o t h i s Page as o f t e n as necessar~ t o complete i t .
`1 - S P e c i f ~ r e g i o n o f i n t e r e s t
`2 - S P e c i f ~ time span o f i n t e r e s t
`3 - S P e c i f ~ P l a t f o r m / s e n s o r / P a r a m e t e r ( s ) o f i n t e r e s t
`4 - S P e c i f ~ P r o c e s s i n g l e v e l
`5-Check completeness o f r e q u e s t
`6 - C o n s t r u c t o u t p u t Product r e o u e s t
`7 - M o d i f ~ o r Process r e a u e s t
`(?HELP -BACK +NEXT ~TOP :REFRESH !GRIPE ~TUTOR #GOTO >CMD $LOGOFF)
`SELECT > 7
`
`(Do above s t e p s f i r s t )
`
`100 - - M o d i f ~ or Process r e q u e s t
`PAGE
`NOW CHECKING COMPLETENESS OF YOUR REQUEST...
`REQUEST IS COMPLETE. READY TO PROCEED.
`PRESS <RETURN> TO CONTINUE
`1 - D i s P l a ~ r e a u e s t
`2 - M o d i f ~ r e e u e s t
`3-Save r e e u e s t f o r f u t u r e use
`( r e s u l t s
`4-E>:ecute sample o f r e e u e s t
`5 - E s t i m a t e c o s t f o r f u l l
`r e e u e s t
`6-E×ecute f u l l
`r e a u e s t
`7-Begin r e e u e s t s p e c i f i c a t i o n
`
`( e r a s e and r e s t a r t )
`
`t o t e r m i n a l )
`
`(?HELP -BACK +NEXT ~TOP :REFRESH !GRIPE ~TUTOR fGOTO >CMD SLOGOFF)
`SELECT >
`Fig. 8. Menu Processor Output of Frames Defined in Figure 7.
`
`417
`
`Communications
`of
`the ACM
`
`July 1982
`Volume 25
`Number 7
`
`SKYHAWKE Ex. 1023, page 6
`
`

`

`COMPUTING
`PRACTICES
`
`lists of: frames which invoke subpro-
`cesses, frame titles, frame pointers,
`pointer mismatches,
`spare
`frame
`numbers, and syntactical errors in
`the control information embedded in
`the frames. This sort of tool is essen-
`tial to weed out errors in manually
`created frame networks. Fortunately,
`it is easy to build--ours is less than
`300 lines of code, including com-
`ments.
`Because the network is expected
`to grow substantially, it has become
`necessary to look for more auto-
`mated support for the design and
`introduction of new subnetworks.
`One existing tool that has been used
`for this application is the Software
`Design and Documentation Lan-
`guage
`(SDDL) [3]. This
`is
`a
`"structured
`English"
`processor
`which is usually used for designing
`and describing program code, but
`which lends itself easily to a great
`variety of novel applications. Sample
`frame definitions using SDDL are
`shown in Figure 7, with the corre-
`sponding frames displayed to the
`user depicted in Figure 8. At this
`time, no tool is available to translate
`the SDDL representation into the for-
`mat actually used to drive the menu
`processor. The translation continues
`to be done manually. However, the
`SDDL processor provides enough sup-
`port, in the form of "call trees,"
`cross-references, and diagnostics, to
`eliminate all "topological" errors,
`such as mismatched or hanging
`pointers. The translation required is
`straightforward and can, for exam-
`ple, be automated by the modifica-
`tion of an existing structured Fortran
`preprocessor. Since errors
`intro-
`duced by manual translation are eas-
`ily found and corrected, this addi-
`tional automation does not appear to
`be warranted at this time.
`1 1. Measurement
`Because the system has not, at
`least as of this writing, been released
`to operational users, we have not
`
`418
`
`collected use-related statistics. How-
`ever, the menu processor does pro-
`duce a detailed log of all user inputs,
`with each entry time-stamped to ten
`millisecond resolution. In addition,
`there is an easy-to-use facility which
`allows users to enter comments into
`the log. Such comments are also
`time-stamped and can be analyzed
`in the context of the session history.
`From this log we intend to extract
`such information as: frequency of
`use for each frame and link, distri-
`bution of residence times at each
`frame, use of the dynamic GOTO and
`related commands, use of the HELP
`facility, requests for help when none
`is available (not all frames have HELP
`frames), and use of the user comment
`facility. In addition, we will monitor
`the use of the command language
`interface to determine to what extent
`users migrate from the menu mode
`to the command mode.
`
`12. Conclusions
`Although data is still lacking, the
`following principles for the design of
`menu networks seem reasonable:
`(1)
`If the underlying informa-
`tion has a stable, well-understood,
`and well-known structure, allow the
`network to reflect that structure.
`(2) Lacking such a structure,
`use the principles of top-down struc-
`tured network design described
`above.
`(3)
`If a demand for highly trav-
`elled shortcuts arises (measure it!),
`install direct routes (static GOTOS)
`where
`they are needed. Remove
`those
`that are
`infrequently used.
`Keep track of which links violate the
`structuring canons and always be
`alert to opportunities for eliminating
`some.
`(4) Provide a dynamic GOTO
`mechanism which users can either
`use or ignore. Monitor its use. Install
`static GOTOS for frequently used
`paths.
`(5) Look
`for software
`tools
`(analogous to structured design and
`structured programming languages)
`to aid in the construction, analysis,
`and maintenance of structured net-
`works.
`Communications
`of
`the ACM
`
`Acknowledgments
`A great deal of insight into the
`problems of users "getting lost" in a
`menu network resulted from discus-
`sions with the staff of the ZOG proj-
`ect at Carnegie-Mellon University.
`Also, the highway analogy and the
`"next" operation were inspired by
`ZOG.
`
`References
`1. Baker, A.L., and Zweben, S.H. A com-
`parison of measures of control flow complex-
`ity. Proc. IEEE Third lnternat. Comptr.
`Software and Applications Conf., Chicago,
`Ill., Nov. 6-8, 1979, pp. 695-701. Discusses
`the advantages and limitations of several
`complexity measures for program flow
`graphs.
`2. Dijkstra, E.W. Go to statement consid-
`ered harmful. Comm. ACM 11, 3 (March
`1968), 147-148.
`3. Kleine, H. Software Design and Docu-
`mentation Language. Pub. 77-24, Revision 1,
`NASA, Jet Propulsion Lab., Calif. Inst.
`Tech., Pasadena, Calif., Aug. 1977. Lan-
`guage reference with examples of use. This
`design language processor has been success-
`fully used for a wide variety of design and
`documentation tasks, from high-level func-
`tional design through detailed code design.
`4. Martin, J. Design of Man-Computer Dial-
`ogs. Prentice-Hall, Englewood Cliffs, N. J.,
`1973. A survey and discussion of interactive
`man-machine interface techniques.
`5. Newell, A. Notes for a model of human
`performance in ZOG. Tech. Rep., Dept.
`Comptr. Sci., Carnegie-Mellon Univ., Pitts-
`burgh, Pa., Aug. 1977. An outline and moti-
`vation for an experiment for measuring some
`human performance parameters in the con-
`text of a large-network, rapid-response menu
`system.
`6. Ramsey, H.R., Atwood, M.E., and
`Kirshbaum, P.J. A critically annotated bibli-
`ography of the literature on human factors in
`computer systems. Tech. Rep. SA1-78-070-
`DEN, Sci. Applications, Inc., Englewood,
`Co. (available from Defense Tech. Inform.
`Ctr., Alexandria, Va.). Abstracts and
`critiques of 564 papers selected from an
`initial set of 20,000 citations.
`7. Robertson, G., McCracken, D., and
`Newell, A. The ZOG approach to man-ma-
`chine communication. Tech. Rep. CMU-
`CS-79-148, Carnegie-Mellon Univ., Pitts-
`burgh, Pa., Oct. 1979. Describes a system
`designed for research into the characteristics
`of menu-driven man-machine communica-
`tions. Discusses the importance of large net-
`works and some general issues concerning
`menu se