Thesis
University of Southampton

Structure and Hypertext

by

Leslie Alan Carr

A thesis submitted for the degree of

Doctor of Philosophy

in the

Faculty of Engineering and Applied Science

Department of Electronics and Computer Science

November, 1994

UNIVERSITY OF SOUTHAMPTON

ABSTRACT

FACULTY OF ENGINEERING AND APPLIED SCIENCE

DEPARTMENT OF ELECTRONICS AND COMPUTER SCIENCE

Doctor of Philosophy

Structure and Hypertext

by L. A. Carr

Hypertext techniques are now beginning to be used in the ways that early researchers anticipated, from personal note taking to online help for ubiquitous computing environments and universal literature resources, yet despite this, hypertext models have remained substantially unchanged. This thesis investigates the nature of text, how it may best be modelled on a computer and how the connections between related texts may be expressed in a flexible and efficient way.

First we look at the development of hypertext systems and then compare that with the complex structured nature of texts themselves. LACE, a small-scale hypertext system based on structured texts is introduced and compared with other hypertext systems. Approaches to large-scale distributed hypertexts are discussed, and LACE-92, a system used to produce hypertexts from distributed information services is presented. Finally LACE-93, a new document architecture for global hypertext environments is proposed.

TABLE OF CONTENTS

LIST OF FIGURES

LIST OF TABLES

ACKNOWLEDGEMENTS

I would like first to thank Prof. David Barron, my supervisor throughout the period of this PhD, who convinced me as an undergraduate that documents were of crucial importance in the study of Computer Science. Much gratitude is due to Sebastian Rahtz who named LACE, touted LACE at conferences and transcribed a conversation between his two cats which defined the term `third generation hypertext' in terms of LACE. Thanks also to Gerard Hutchings for sharing an untidy office and on many occasions straightening out an untidy mind; to Wendy Hall for provoking me into thinking and writing and to Hugh Davis for helping to bounce ideas around and generally keeping me from panicking.

But most of all, many thanks and much appreciation to my wife Jan who has at last received a straight answer to the question "How long until you finish the last chapter?".

1. OVERVIEW OF HYPERTEXT MODELS

The concept of hypertext is commonly attributed to Vanevar Bush [31] in the 1940s and Doug Engelbart [53] and Ted Nelson [108] in the 1960s, however the systems which they pioneered have, at first sight, little in common. This chapter examines the various models which have been proposed and implemented for hypertexts, and discusses the effects of these models on the end users (both producers or consumers) of the hypertext.

1.1 Introduction

The classic definition of hypertext made by Nelson in [108] is ``forms of writing which branch or perform on request'' or more simply ``non-sequential writing''. Various other terms were claimed in the same work, notably hypergrams for diagrams which performed similarly and stretchtext for literature which expanded and contracted to greater and lesser degrees of detail upon request. Neither of these names have become well-known, although the concept of hypergrams has been subsumed by hypermedia--performing non-sequential drawings, images, sound and video, and the concept of stretchtext has been most effectively demonstrated (under the more prosaic alias of `inline replacement') by the Guide system (see section A1.9).

Conklin's famous introduction to the subject [42] classifies the various hypertext systems into four broad application areas. Two of these were macro literary systems for large-scale literatures and problem exploration tools for highly flexible personal use on a much smaller amount of information (the third was a derivative of the former category and the fourth a miscellaneous category). However, it is important to realise that the two applications are not somehow separable: a scholar who needs to study and `inwardly digest' a topic needs not only to express his or her own thoughts, but also to draw on the information capacity of a huge library with the musings and conclusions of other researchers. These two application areas are then simply complementary functions that the same hypertext system should be able to provide. Van Dam [147] emphasises the ability of the computer to enhance connectivity, and that must be provided both in the large (in the sense of a newly published book being added to a library by connecting its key words and concepts to the huge web of pre-existing information links) and in the small (by connecting and re-connecting the hypertext structures which represent an author's initial ideas according to a changing and evolving personal understanding of the subject).

A review of the hypertext literature of the last twenty years shows that hypertexts have been implemented variously as:

* indivisible information nodes connected by links: Memex [31], NoteCards [63,64], KMS (a commercial version of the ZOG research project [98]), HyperCard [5]

* structured nodes connected by links: Augment [53], Dynatext [46]

* documents and modular sets of connecting links: Intermedia [148], Microcosm [55]

* a knowledge-based framework of texts: Aquanet [92], gIBIS [10], Much [117]

* non-linear `unfolding' text : Guide [27]

* everything incestuously connected to everything else: Xanadu [109]

* a word-processed document with added links: Word for Windows [101]

The above systems mainly share a common general model of hypertext: `nodes' of information which are `linked' to each other and so can be characterised by the linking mechanism, by the nodes that are linked and by the user interface which determines the way that the user encounters and manipulates these node and link objects.

1.2 Nodes

Nodes are the most obvious features of hypertext systems as they contain the system's complete information store and display it to the user. Characteristics of a node which are important to the users (readers or authors) of a hypertext system are the kind of information that can be stored (text, diagrams, exotic data types or media) and the capacity of each node.

1.2.1 Node Contents

Some hypertext systems can only hold text (for example, NLS and ZOG), some also allow diagrams and bitmapped pictures to be displayed (HyperTIES, HyperCard and Guide) while others gave extensible mechanisms for interpreting many different kinds of information (e.g. timelines or video) inside the hypertext network (Intermedia, Notecards, Word and Acrobat).

It is important to realise that simply displaying a new information type is not sufficient for true multi-media hypertext (or hypermedia). HyperCard may easily enough be persuaded to display sequences from a videodisk, but unless the methods for creating links between video sequences or between video stills and text are in place then the system is simply acting as an expensive remote control device. It is imperative that each new information type be completely integrated into the system's hypertext network. Both Intermedia and NoteCards are successful in this area because they themselves are built on extensible environments (Object-Oriented C and Lisp respectively) so that modules defining hypertext functionality for new information sources may be slotted into the existing application's framework.

A compromise often adopted is to graft a `dumb' medium (like videodisk) onto a true hypertext network by associating each frame/sequence on the video with one `place holding' node in the network. Hypertext operations on the new medium are then mapped onto existing operations on a normal node. For example, node A will always activate the showing of video frame A', and node B will cause video sequence B' to be played. A link from frame A' to sequence B' can then be effected by placing a button on node A which links it to node B. The nodes would commonly display a brief textual description of the video sequences that they shadow. HyperCard is an example of such a hybrid hypermedia system, since HyperTalk extension commands are widely available which interact with external devices (such as a video player) via the host computer's communications port, although no information can be received from the remote device.

Even text-only systems may be classified according to the kinds of text which can be displayed. Some allow only fixed-font text (early systems such as NLS, HyperTIES and original versions of HyperCard), some allow multiple text fonts, sizes and styles (later versions of HyperCard, Guide), and some provide full composition facilities, including horizontal and vertical spacing (Word).

1.2.2 Node Capacity

A second significant issue relating to nodes is their size. Systems such as ZOG and HyperCard have rigidly fixed-sized nodes, whereas others are more flexible. The size of a node is not just a function of the size of its host system's display since both ZOG and HyperTIES use a standard `terminal-sized' display, though the latter allows a node to be constructed from several screensful of information. Neither is it solely to do with the sophistication of the display hardware: HyperCard (fixed, screen-sized nodes) and Guide (unlimited scrolling nodes) both run on (small) bitmapped displays which make heavy use of windows and pointer devices, whereas ZOG (fixed screen-sized nodes) and NLS (flexible node length) both run on dumb terminals.

The size of the display is an important factor in any information system since it is desirable to present an uncluttered, easy-to-read screen to the user. Narrow newspaper columns are difficult to read because the eye has to keep rescanning to find the start of the line; small screens force the reader to keep flipping between pages of information.

If display-size is a problem for the reader, node-size is a problem for the author. Each node in a hypertext network typically requires a unique name and occupies a unique space in the information `hierarchy'. If the size of the node is fixed, then the author is faced with two choices, either to edit the material to fit within the node or to split the node into two new ones. The former choice may be effective during the initial construction of the network, but extra material that is to be added during a process of revision may force the latter to occur. If so, the split can be undertaken in two ways, either by re-partitioning the information into several logical chunks, each with its own node, or by creating a linear sequence of continuation nodes. Both of these courses of action may have the knock-on effect of invalidating some of the links to the existing node, requiring further revision work.

1.3 Links

The way in which links are implemented is key to any hypertext system as they provide the `non-sequential branching' which is at the heart of hypertext functionality. If a hypertext system is really about enhancing connectivity, as has been claimed above, then how are the connections made? Can they be adequately visualised? And how accurately can they target the information that they link?

1.3.1 Link Representation

Systems either give links the status of first-class objects and allow the user (reader or author) to manipulate them directly, or support `insubstantial' links which are hidden in the system (possibly even part of the text) and only have an observable existence when the user in some way `actions' them.

Intermedia is a prime example of a system with first-class links. There the links are stored separately from the documents to which they refer. These links also have the capacity for holding information in the form of attribute-value pairs that can be used as part of a reader's query.

It is the first-class nature of links that allow systems to provide a graphical browser. Without explicit storage of the links between the nodes it is impossible to tell the overall structure of the network without actually traversing it. Hence only systems such as NoteCards, Intermedia and derivatives of HAM provide such a function.

Insubstantial links are merely specifications for the address of a jump and as such only have any existence when they are invoked. HyperCard links, for example, are generally buttons containing the instruction ``go to card id 42106'' (or similar). However, buttons need not contain jump instructions, and, in fact, such a jump is not constrained to be attached to a button: it can instead be a part of a more general handler that is invoked when a particular key is pressed or invoked on some arbitrary event. It may also be the result of a more general computation, such as ``look up the id of the card which matches the text that the user has selected and go to it''. Because there is no clear correspondence between any particular object and the set of links in a hypertext network, HyperCard has no means of manipulating the network as a whole. Although it does maintain a graphically displayed list of the last 42 cards visited, no information is kept of alternative routes that may be followed.

NLS links are simply stored as part of the text of each node. Selecting the link reference causes a hypertext jump to be activated, but once again it cannot be easily distinguished as a link except by the user who understands the context. HyperTIES and ZOG also make use of links embedded in but displayed differently from the nodes' content. HyperTIES highlights the embedded link by displaying its name in a contrasting font, ZOG uses spatial highlighting, separating the links from the text. In both cases `address' of the destination node is the same as the name of the link.

Guide is more perverse in that it has a clear idea of the existence of links and indeed cannot display the document without a knowledge of the state of each link, but it has a less-well defined concept of nodes. As has been explained, each Guide document is considered a continuous scroll of material with links `folding' and unfolding spans of material. However, the reference links to other documents are of the insubstantial kind.

Insubstantial links are by nature unidirectional (HyperCard has no ``come from'' command), which make it difficult to model a naturally symmetric relationship between nodes but instead give rise to a directed walk-through of a document. It also leads to the ``you can't get there from here'' phenomenon, where many links may lead into a node, but none out, so leaving the reader stranded.

1.3.2 Link Granularity

The granularity of a link is an important consideration. In many systems the destination of a link is a node and no targeting of the information contained therein is possible. As has been mentioned before, this can cause problems when editing a node requires splitting its contents amongst several new nodes. Another shortcoming is that traversing a link does not necessarily take the reader's attention straight to relevant information, but requires them to search for it on the new node. Under such circumstances the reader must be completely clear about why the link is there and what is supposed to be taking them to. Intermedia solves these problems by having any span of text within the node as the destination of the link. A link anchor is placed next to the text to draw attention to it.

The granularity of the link source is also important. By limiting the positioning of links to an empty space at the bottom of the frame, the Memex forced the whole frame to act as the link's source. This of course makes it very difficult to know what is being linked from, i.e. what is the key phrase on this frame. Since there can be many links present on each frame, it makes the job even more difficult, especially compounded by having complete frames as link destinations. Intermedia is much more flexible since it allows any span of text within a node to act as the link source. NLS, ZOG, HyperTIES and Guide all have specific words and phrases within the text that are bound to the link, whereas NoteCards, HyperCard and Acrobat anchor a link at a single position on a card. As has been mentioned before, HyperCard's buttons are fixed at a geographical position on the card rather than a logical position within the text, making it very cumbersome to edit a node.

1.4 User Interface

Although nodes and links provide the basic facilities of a hypertext system, the user interface is of paramount importance since it determines the ease of use of each of the facilities. A library, after all, has many sophisticated indexing and cross-referencing facilities but the manual procedure required to follow them through is time-consuming enough to deter casual browsing.

All systems make it easy to follow the natural progression of a document whether it involves scrolling through a linear document (Intermedia, Guide) or tree-walking through a hierarchical structure of nodes using next-sibling and return-to-parent operations (ZOG, HyperCard). Of more interest is how cross-reference links are encountered--here there are several considerations for a reader to be aware of--how can a link be recognised (what is its visual representation), and once the link opportunity has been recognised how can the link be invoked?

1.4.1 Link Display

The Memex relied on marginalia facilities in which the information about a link was stored on a blank space on the node. This allowed no `inline cueing' but simply alerted the reader to a link from something on this page to further information. All other systems provide facilities for marking the parts of a nodes information which are the subjects of links. Some (ZOG, HyperTIES and Guide) by highlighting the appropriate key words or key phrases, others (HyperCard, Intermedia, NoteCards) by providing link anchors or buttons which act like a footnote marker, alerting the reader to the presence of auxilliary information related to the information which appears here. NLS stands alone as it provides no visual cueing of links, but a semantic cueing akin to writing ``see statement 4b''.

1.4.2 Link Triggering

With the Memex and ZOG this was achieved by a mapping between each available link option and a key on the keyboard (exactly like choosing from a menu). For Intermedia, NoteCards, HyperCard and Guide this is done instead by pointing at the link and clicking on it with the mouse button, in line with the direct manipulation model. HyperTIES has a slightly different (keyboard-based) model: one link-point remains highlighted but this hot-spot is moved from link-point to link-point under control of the cursor keys. When the correct link has been selected the user activates the link with a different key. NLS also has an explicitly two-part operation (select and activate) by making the reader select the link text with a mouse before the "follow-this-link" action is taken. This type of approach is highly extensible as it allows the user to control both the selection and the action to be taken, allowing dynamic data lookup rather than just the normal ``jump to another card which also makes reference to this'' consequence. This issue is elaborated in [55] with a description of a system which works on the basis of selections and actions.

1.4.3 Hypertext Jumps

Once recognised and selected the system in all cases performs an immediate hypertext jump to the linked information. It is interesting to question why this should always be so: if someone comes across a citation in a library journal they do not stop what they are doing to follow up the reference. Rather they take a note of the reference (perhaps looking to the bibliography at the end of the article to evaluate the true relevance of this item) and follow it up after they have finished reading the journal. The instantaneous jump phenomenon is more suited to a computer than a human since it leads to a depth first traversal of the network with a growing stack of outstanding articles to be finished (exactly mimicking the operation of a computer following a program through nested levels of subroutines). Hypertext systems which implement delayed jumps may well act to cut down the disorientating effects of navigation.

A common side-effect of making a hypertext jump is losing the context of the original information since many systems can only display one node at a time on the screen. This adds to the disorientation of the user who is navigating through an unknown network of unfamiliar information. NLS contrives (under certain circumstances) to lock part of a node onto the display, keeping some familiar reference for the user despite being limited to a terminal-sized display. NoteCards and Intermedia allow many nodes to be displayed at a time and so avoid the dangers of losing the reader but at the risk of swamping him or her with too many pieces of concurrent information. Although the display can handle many windows some are bound to become partially concealed. This is made worse by the hoarding instincts of the reader who is frightened to put away any window `just in case' it is needed again. Guide has a novel approach to these problems as it performs an inline replacement of the link cue by the information stored at the link's destination. Hence clicking on a highlighted key-phrase in Guide may cause it to be replaced by a paragraph giving a fuller explanation of the phrase. In this way both the source and destination contexts are still visible to the reader and hyperspace disorientation is minimised.

1.5 Summary

In this chapter we have seen hypertext as blocks or streams of text (or other forms of information) linked to each other (according to some set of rules). While adding functionality to a static print format, some of the basic features of these systems (fixed nodes, coarse links) make the hypertext cumbersome to write or difficult to comprehend.

The `hyper-' prefix in the word `hypertext' indicates `more than', thus hypertext is literally `more than' text. The advantages of nonlinearity, cross-reference jumps and multimedia information have to be balanced against some of the disadvantages mentioned above or the resulting system will implement hypotext, text which is less useful or less accessible than its print-bound counterpart.

In the following chapters we will examine the nature of text and how it can be adequately modelled by a computer. Then we will look again at hypertext, in particular a system developed by the author in 1988 which is based on these ideas of text. We then examine the use of computer environments which aid reading or writing both electronic documents and electronic non-linear hypertexts and then return to re-examine the models of hypertext beyond the `nodes and links' seen here.

2. TEXTS

It is important to consider for any hypertext system, such as the ones described in the previous chapter, not only the technology and user-interface of linking texts, but also what it means to make a link between two texts, and the meaning of a linked network of texts. The impact of these considerations on the usability of the resultant hypertexts can be understood when it is considered that a single text is itself a complex network of related components.

In this chapter we look at the way in which texts themselves are constructed, how texts can be adequately represented on a computer and compare the way in which hypertext systems model a network of linked texts.

2.1 Text as Structures

In a study of hypertexts and their features, it is instructive to consider the nature of `ordinary' or `traditional' texts. We can ask the questions: what is a text? How is a text composed by writers, and how is it understood by readers?

In a computing environment, `text' is usually thought of as a simple sequence of characters as defined by the ASCII encoding. In fact, even to the present day, the most prevalent type of document or file is the text file: a sequence of ASCII characters whose record ends define the line breaks for display purposes. However a text in its fullest sense consists of more than just its encoding and layout information. It principally contains high-level cognitive information which is communicated in a natural language expressed by the character coding and layout. It is the expression of this embedded information which is the crucial purpose of the text, and the responsibility of the writer to construct the text in such a way as to accurately present the information to the reader and in a fashion which can be easily assimilated by the reader. In this way the intent or purpose of a text is not to produce a suitably formatted piece of paper, but to inform a reader.

Human cognition is often described in terms of a semantic network into which new facts are added through the learning process (see for example [54]). This gives rise to a close correspondence between texts and computer programs. A program specifies a set of actions which, when elaborated by a computing processor, produce a certain change of state in that system. Similarly, a text, when elaborated by a suitable cognitive processor, produces a change of state in that system, with an increased understanding achieved by an incrementally updated knowledge network.

2.1.1 A Text is more than a Linear Sequence

Nelson defined hypertext as any form of writing which cannot be simply expressed as a linear sequence, but it is not only the new technologies of hypertext which have extended writing beyond the linear sequence. Various techniques have evolved within conventional text that allow richer forms to be expressed than a simple one-dimensional elabortaion of facts. Hierarchical structures are a case in point: the sub- and super-ordination of concepts achieved by the various levels of the tree structure is mapped onto a conventional linear text sequence by a pre-order tree expansion. Hierarchies are seen particularly in technical and legal writing through an extensive range of different `levels': parts, chapters, sections, subsections, subsubsections, paragraphs and subparagraphs. Other literary forms have shallow hierarchies: plays have Acts and Scenes, novels have parts and chapters, newspapers have sections and articles.

Hierarchies bring structure to a text, but even sequence itself is a simple structuring tool, allowing a directed development of an argument or the build-up of context. A narrative text often makes use of parallel threads (sequences) which are interleaved throughout the text. Cross-reference is frequently seen in technical writing, allowing the author a means of emulating a network of ideas rather than a fixed hierarchy.

2.1.2 A Text as a Hierarchical Structures of Ideas

We are familiar with the use of structure to decompose complex ideas within a text, since technical documentation, such as manuals and reports, is made up of chapters, sections and subsections in which ideas are developed in successively greater detail as the reader descends through the hierarchy of sections. However, this familar (and often explicit) hierarchy is not the only type of structure which is present in a text. The study of discourse theory [142] identifies large-scale super-structures which organise complex semantic information within the text. The text is not just a sum of the component parts; the function of superstructures is to add meaning to the text by defining its global coherence. Superstructures contain two other kinds of structure: micro-structures which relate ideas at the level of words and phrases in a fashion analogous to semantic networks and macro-structures which summarise and encapsulate the meaning of statements and paragraphs. Whereas macro-structures are distilled content, superstructures are independent of content.

According to [141], the functions of superstructures become conventionalised in a given culture, leading to fixed schemas for the global content of a text. The following five superstructures are identified as being common to many text types:

Introduction: presuppositions and background

Problem: a twist on the state of affairs

Solution: resolution of the above

Evaluation: discussion of consequences

Conclusion: closing/summary

Stories, scientific papers, dramas and arguments are all identified as containing the above superstructures. Despite the variety of texts, the author is leading the reader towards a particular conclusion via a particular interpretation of the facts--a directed presentation. In each type of text, the structure acts both to direct and constrain the content--no introductory material is allowed to appear within a concluding section, nor is the conclusion allowed to precede the material which supports it.

2.1.3 A Text as a Hierarchical Structure of Presentation

Superstructures are not related to content, but at a meta-level in which the author is making decisions about the presentation of the semantic content. This `presentation structure' is the form of written or spoken communication used to present ideas in the form of narratives, technical documents, arguments or dramas. The model for conventional `texts' is that of a lecture in which an author actively educates an audience. The structure of the text (or presentation) is key in the audience's understanding of the content because it assigns a role to each piece of information, showing some facts to be subordinate to or of equal importance to others. The relationships made explicit in a cognitive structure are similar, but deal with the `plain facts of the matter' rather than the directed interpretation of an authored text.

2.2 Representing Structured Texts

Having briefly explored the complexity of a text, with its concurrent internal structures (semantic microstructures, organising macrostructures, presentational superstructures), let us consider how this this complex information can be represented on a computer. There have been various schemes for representing texts as computer data: originally the purpose of a text was to produce a printed document, and so the first structures which were explicitly coded were those of physical rendering for display. We first look at these methods, and how they have developed to allow coding of the abstract structures of the content and rhetoric of text.

2.2.1 Physical Representations

Markup was the process of marking a manuscript with instructions to the human compositor for rendering the manuscript in print. When the manuscript became a computer file and the compositor a computer program, markup instead comprised the codes inserted into the text to control the composition program. These codes may be explicitly inserted by the author (in the case of typesetting systems like LATEX [85] or troff [8]) or added `behind the scenes' as a consequence of the author choosing a particular style from a menu (in word processor systems like Microsoft Word [101] or WordPerfect). These codes control printed (physical) attributes of the document, such as the fonts and spaces used to render the text (Figure 2.1a), and mimic the pre-existing technology used by printers, so the models which both the above kinds of programs manipulate is that of a book, magazine, memo, or letter--i.e. any printed item.

.ce 1

.ft B

A title, a title, my kingdom for a title

.ft R

.sp 0.5i

In this chapter we look at the possible

Figure 2.1a: Nroff physical markup for a section heading

.H 1 "A title, a title, my kingdom for a title"

In this chapter we look at the possible

Figure 2.1b: Nroff mm logical markup for a section heading

Because of the tedious and repetitive nature of this `physically oriented' low-level typographic manipulation, markup languages adopt procedural abstractions (Figure 2.1b) which mirror higher-level physical document constructs like display paragraphs, hanging indents, bulleted lists and headings, and reflect a document's logical or abstract composition, such as its construction from chapters, sections and subsections, figures and tables. Emphasised text is no longer marked up with prescriptive physical commands to "change the font to italic", but with an abstract declaration that "the following text is emphasised". It is now the responsibility of the composition program to know how to suitably render emphasised text--in other words its role has expanded from dealing with page imaging semantics to dealing with document semantics. The advantage of this style of markup is that the author can concentrate on expressing ideas within an appropriate logical framework without worrying about issues of presentation that the compositor should deal with.

Markup systems which adhere to this philosophy (troff+mm, LATEX, GML) emphasise the logical nature of their markup, especially the facilities for expressing the document's overall hierarchical structure. However a closer inspection reveals that such markup is still implicitly tied to describing the physical layout of a printed document. In fact mm and LATEX markup for a `section' or `chapter' is defined in terms of lower-level primitives for changing fonts and leaving vertical space, and so is still a physically-oriented markup, rather than a truly logical one. Document structures like `sections' are catered for in name only; in fact one is really marking up the section heading alone. Another apparently separate component of the logical document structure, the footnote, only has any meaning in a paginated environment and may need to be re-interpreted as a marginal paragraph or an endnote in an on-line text presentation system.

2.2.2 Logical Representations

Logical markup has been taken to its (logical) extreme by SGML, the Standard Generalized Markup Language [7, 76], which defines a regime for document markup without any predefined processing operations or any built-in document structure semantics. This lack of built-in semantics is both SGML's greatest strength and greatest weakness. The strength is that SGML forces abstraction from the eventual document delivery medium and allows a content-based approach, imposing a cognitive discipline that brings benefits beyond any immediate publishing requirements. However, SGML can be used to code all the different categories of logical structure: semantic structure vs presentational structure, microstructure vs macrostructure.

SGML specifies each document architecture with a DTD (Document Type Definition) defining the hierarchy of structures which may compose the document. This architecture may be used by an interactive document editor to check the structure of the document being created, or by a document formatter to process the entire document. There is a strict syntax associated with the architecture which may be understood and verified by any SGML-compliant application, but each application is responsible for interpreting the meaning of the document structure, according to its requirements.

For example, figure 2.2 shows how a biographical dictionary may be marked up. To produce a printed document it may only be necessary to specially highlight the start of the entry, the name and dates of birth and death of the individual. The other tags may be completely ignored during formatting, with the text set as if they were not there. However, when forming a biographical database from the same document it may be deemed important to identify all the information marked above so that the database can be used to determine everyone who was educated at a particular university. Without the extra markup it would be impossible to pick out these details that make the data useful for many purposes apart from printing. The markup makes explicit the information that is embedded within the text, and this information can subsequently be reused in different ways.

<entry>

<biographand><name>John Smith</></>

<dob><day>12<month>June<year>194</dob>

<dod><day>1<month>Feb<year>1987b></dob>

John was born in <birthplace><place>Edinburgh</birthplace> and studied <subject>English</> at <education><place>Southampton</> University</>, graduating in <graduation><date><yr>1956</graduation>. He married <spouse><name>Emma Jones</name></spouse> in 1962 and became <profession>MP</> for Southampton in 1975 until his death.

</entry>

Figure 2.2: SGML markup for an entry in a biographical dictionary

According to [58] any document can be considered to have 3 parallel structures associated with it. These are the abstract representation which is concerned with the logical structure of the information contained in a document and made explicit by some form of high-level markup, the physical representation which is determined by a formatting process and the page representation which is defined by a viewing process. The physical representation corresponds to the document formatted for output on an infinitely long scroll, whereas the page representation is concerned with how the formatted representation can be mapped onto discrete pages. We have already seen that there are in fact a number of different structures which comprise the abstract document. The bibliographic dictionary example in figure 2.2 has a very fixed database-type micro-structure. The dictionary simply consists of an order list of entries, with no combining of data between entries into any higher level structure. In a report document, conversely, the superstructure would be combined with content-based macro-structures but probably without the detailed exposition of the microstructure.

In a text-processing environment, the technical author usually manipulates the abstract document (which is a union of the content of the document and the distinguishable markup interleaved with the content) via a text editor. This is normally done by treating the markup as text and providing a standard set of text manipulation functions which apply to both the content and the markup. Alternatively the editing process may provide the author with the same set of text manipulations but treat the markup separately by graphically interpreting it through the use of indentation, whitespace and highlighting (as found in IBM's LEXX editor). In a WYSIWYG environment the author is usually directly manipulating the physical representation (the-document-as-a-scroll) with all `markup' inserted invisibly and interpreted faithfully on the screen. There is little concept of the abstract structure, although `style sheets' give the illusion that such a structure exists by allowing logical names to be associated with groups of physical formatting specifications that are applied to specific paragraphs. Some WYSIWYG systems (e.g. Microsoft WORD) give the author access to the page representation, or the option of swapping between both representations as required.

2.2.3 Representing Multimedia Documents

Click here for Picture

Figure 2.3: A multimedia document

In a modern multimedia document environment, the models manipulated by the computer programs are no longer those of traditional printing technology, with common interfaces and operational semantics. A document may consist of a collection of video sequences, audio clips and computer animations as well as text. Abstract but physically-based markup can no longer be used to define `how to' present each piece of information because there is (as yet) no standard practice to follow for presenting non-textual information. In any case instructions such as `leave 2 seconds of space and then show this video clip in the top-left corner of the screen with that text next to it' leave little room for true hypermedia which necessitates user-directed interaction.

Although physically-oriented markup has a limited role in a truly multimedia environment, it has a crucial role to play in describing each different component of the document, describing its representation and its purpose (especially for non-textual information). The markup can therefore be used in two ways

i) To encode or represent the various document objects themselves

ii) To describe meta-information about the objects or their intended use.

For example, figure 2.3 demonstrates a document which consists of some text, a diagram and a video sequence. Figure 2.4 shows how it might be coded according to an SGML DTD, with the document structure used as a container to hold the various encodings of the document media (text, picture and video). The contents of the text objects are also coded according to the DTD, although the diagram object is coded according to some external scheme and the video object as a mixture of SGML markup and external scheme. All the document objects (text, diagram and video) are coded using SGML markup and also have special tags which give information about the objects.

<mmdoc>

<element type=text>Welcome to the Department of Electronics and Computer Science. <p>Click on the map below.</>

<element type=diag size=7x8 rendering=winmetafile>

AA145367382A5...</>

<element type=text>The Department was formed in 1990 as a merger between the Departments of Electronics (Faculty of Engineering) and Computer Science (Maths). This has resulted in a successful partnership of hardware and software expertise.</>

<element type=video size=3x3 rendering=frames>

<frame num=1 timecode=002701>AA145367382A5...

<frame num=2 timecode=002702>AA145367382A5...

<frame num=3 timecode=002703>AA145367382A5...

</>

</mmdoc>

Figure 2.4: Representing the document with SGML

2.2.4 Mapping Between Representations

The advantage a logical style of markup is that the author can concentrate on expressing ideas within an appropriate logical framework without worrying about issues of formatting that the compositor should properly deal with. However, if the purpose of logical markup is to make explicit the author's intent, the structure of the information contained in the document or the structure of the argument being presented, then there has to be some kind of relationship defined to bridge the gap with the formatting commands which were used to render the document in print in the first place.

Some of the issues that a document composition system must deal with in converting between logical and physical structures (legibility, readability, hyphenation, typographic design) can be seen in [126], but the nature of that relationship between these structures varies between the different systems of logical markup. For LATEX and ms/mm, which are high-level macro packages built on top of specific text formatters (TEX and troff respectively), the high level markup is simply a disguise for a sequence of physical formatting operations. Each piece of `logical markup' is actually a set of font changes and spacing commands in disguise. ODA maintains separate physical and abstract structures for a document in parallel, and provides an explicit mapping between the two structures. SGML, by contrast, deals with no concept of a physical structure, and devolves all formatting issues to separate application programs. (In fact the SGML LINK facility [29] can be used to provide stylesheet-like formatting capabilities, and the forthcoming DSSSL standard [2] defines an ODA-like mechanism for mapping SGML structure onto a physical structure.)

2.3 Hypertexts as Structured Networks

Bush's view of hypertext [31] was of an associative network in which nodes (peers of equal status) were connected by undifferentiated links. Many modern systems such as HyperCard and HyperTIES are based on this model, providing unstructured hypertext that can become very difficult to navigate around. One of the main reasons for this is the lack of information associated with each link which would otherwise enable judgements to be made about the applicability of the associated material.

Extending the hypertext model to include typed links allows a structure to be imposed on the information content. The most frequently used model for this structure is that of human memory. Bush's paper held the view that human memory worked in the same fundamentally unstructured way as the associative links provided by the Memex, however modern theories of human cognition favour the semantic network [78], which as a network of nodes joined by typed links is congruent to a hypertext network with typed links. Various authors have tried to identify sets of link types sufficient for structuring a hypertext--[52] advocates the use of seven link types: being (subset relationship), showing, causing, using, having, including, and similarity. Nelson [109] provisionally suggests a large number of link types for Xanadu including correction, comment, translation, quote, expansion, suggested pathway and citation. Xanadu link types are entirely arbitrary, but in general the set of link types should be both small enough to maintain a rigid structure and large enough to be generally applicable in all situations.

Whereas the links model the relationships in a semantic network, the nodes of the hypertext are the information content proper. For a semantic network, each node has a fine information granularity, dealing in individual concepts or propositions, i.e. textual micro-structures where each node is a self-contained entity and does not rely on a global context for its meaning. Even at this level the hypertext network may be constructed to model one of two alternative semantic structures. It may either plot the relationship between facts and concepts in the knowledge domain or depict the cognitive structure of the expert's understanding of the field. The latter choice is seen as a powerful tool since the goal of education is to transfer the expert's cognitive structure to the novice [132].

Although the cognitive structure approach to hypertext provides a sound model of knowledge and concept, and is a popular model for implementing hypertext systems [77, 81, 84], it has no model of the text itself. Begeman & Conklin document the difficulty of comprehension for readers in such a hypertext environment, since however clear the concepts in each individual node are it becomes impossible to track the thread of these concepts through many linked nodes [10]. The author is limited to expressing ideas in fine-grained, distinct units which obscure the overall development of any larger ideas, i.e. there are no macro- or super-structures. Traditional text with its linear form allows for the development of ideas and arguments building on the successive disclosure of individual points and concepts. In such a medium there is an evolving context that can be built on: in a hypertext medium there is no such context as there is no `correct' path through the network, and no guarantee that the reader will have encountered a particular piece of information.

Hence, in a cognitive structure there can be no larger theme or overall point of view which directs the authoring process as the semantic network deals only with atomic facts or propositions and their interrelationships. One of the first rules of writing taught at school, is that a text should have a beginning, a middle and an end. This is not the case in a cognitively structured hypertext since there is no ordering or natural sequencing imposed upon the information.

2.3.1 Implementation Requirements for Structure

Systems such as HyperCard do not implement links as first class objects and allow them to be visualised or directly manipulated. Instead, they are embedded in the document as a part of a sequence of instructions to be triggered by some action of the reader. As a consequence, only nodes have any concrete representation--the links (and the network they specify) have only an abstract existence as a `flow of control' of the computational process which embodies the hypertext browser program.

Since links (as opposed to buttons which anchor the links to a position on the computer screen) have no independent existence, no extra information can be attached to them in the form of names, types or attributes. It is also not possible to provide a graphical browser to aid navigation through the network (this statement refers to the `plain' package--since HyperCard contains a powerful programming language it is possible to emulate more sophisticated hypertext features).

Other systems (such as Intermedia) do implement links as first-class objects, and allow direct manipulation of nodes, links and the network as a whole. These implementations also provide for extra information (in the form of tables of attributes) to be attached to nodes and links for use in the navigation process, allowing the reader (or the system) to filter links according to some criterion of relevancy.

As an example, the gIBIS system [10] has a small number of node and link types that allow the reader to differentiate between the kinds of information that are connected to any particular node. When viewing a node the reader may choose to follow up other information which supports, contradicts or in some other way relates to the current issue. All this information is deducible from the type of the individual links, and allows the reader to make decisions about the linked material without traversing the link. A similar phenomenon is demonstrated by McAleese's [51] method of qualifying citations for traditional texts. By providing extra information about the type of the citation readers can judge whether the reference is relevant to them.

Structure in a hypertext network is the organising principle that determines how the individual nodes are arranged and related to each other through the links. Typed links provide a useful means of structuring the hypertext network by placing some organising criteria on the information accessible from each node in the network. Such an organisation of the relationship between nodes in the network may, according to the choice of link types, reflect the relationship between the propositions in the knowledge domain, the organizational structure of the author's understanding, or a higher level text-oriented structure.

The choice between various kinds of structure as a basis for a hypertext model has consequences for the users of the hypertext. We have seen that the primitive associative-semantic structure provides no context and provides certain difficulties for effective use by readers. In the next chapter we look at other structuring mechanisms which provide better navigation facilities.

3. HYPERTEXT IN THE SMALL

From texts we turn to consider hypertext systems. "Hypertext in the small" is hypertext concerned with a local context--usually a single text or group of intimately related texts. It has been shown in the previous chapter that texts are themselves complex structures of related components. This chapter introduces a hypertext system, LACE, which is based on a model of structured texts and creates hypertexts from existing structured documents. It then goes on to examine the use of structure both as a reader's navigation tool and an author's construction tool, and introduces a system called LACE'92 which is used to help author structured documents. The chapter closes by looking at intentional authored structure versus non-intentional evolutionary structures.

3.1 LACE

The previous chapter has examined the nature of `text' and the various structures associated with it. It also demonstrated the difficulties of hypertext which are structured too closely to the atomic facts of the knowedge domain. In fact, most authors are producing not hypertexts, but documents in printed or electronic form as reports, letters, or books. Modern document composition systems deal with structured documents whose contents can be rendered in different styles (LATEX, SGML, ODA, Word). This chapter describes a system which allows hypertexts to be built from these existing documents.

In [40] Cole & Brown, remarking upon the similarities between paper documents and hypertexts, state

"it also seems sensible to make provision for readers to have the advantage of hypertext navigation when viewing a document on screen, even if the document is eventually intended to be read from paper. These aims could best be achieved by having a common underlying representation for the structures of both types of document, together with well-defined ways of mapping these structures into different forms of representation... it is not suggested, of course, that a document designed for paper would necessarily make a good hypertext or vice versa, only that a usable representation should be readily available by applying different presentation styles."

Here we describe LACE [38, 118], a hypertext presentation environment built on the LATEX document production system. LACE turns each document into a database of components which can be individually addressed. A document can be viewed as a contiguous whole or have isolated components extracted. The logical structure of the document is important because it provides both coherence to the document as a whole and a mechanism for deconstructing the document.

LACE addresses the goal of automatic hypertext generation by producing a hypertext from the original sources used to create a paper document. LACE's hypertext viewer uses a document's explicit structural information (chapters, sections, floats, marginalia) and existing navigation structures (table of contents, index, citations).

The advantage that the Memex had was a huge increase in speed and convenience for the user--no more walking through miles of bookshelves or flicking through hundreds of pages to locate a single piece of information. Instead, everything was to be available through the motion of a lever. One of the appealing characteristics of the Memex was that it gave the reader just what they were used to: complete pages of text (lots of information available at a glance) which were designed especially to make the reading process easier. Use was made of both horizontal and vertical white space to set off important information and to help divide the text into units of paragraphs, sections and chapters. Different styles of letter-shape were used to further highlight and draw attention to important information. All this was available because the Memex gave a photographic reproduction of the original texts at their original size.

Limitations of size and layout hinder many hypertext systems from fulfilling the fundamental goal of hypertext. Small fixed node sizes force the author to break material into unnatural chunks thus hiding information from the reader, and the lack of typographic devices means that the reader finds it harder to locate information. Typically the author is forced to use excessive spacing in the layout to force items to stand out which in turn exacerbates the problem of size.

A further limitation is the insular nature of these systems--documents have to be explicitly authored within the system and can only be read using it. There is a need for open standards of access when building up a network database of literature so that one system may act as a hypertext viewer to a set of documents, while another can perform textual criticisms of the documents' contents and yet another may perform automatic content analysis. A great deal of effort must be put into creating an online literature database; it is imperative that the result is easily extensible and reusable.

Centuries of use of paper-based books and journals have led to many developments in their presentation which have enhanced the way in which we extract information from the page. The techniques of typography and layout to which we have already alluded, footnotes, indexes, tables of contents, citations and bibliographies all help us to navigate through printed material. Even physical attributes of the document (such as the relative thickness of the document) provide navigational clues when we read [11]. It is important that problems associated with readability and the convenience of the user-interface are solved, otherwise that which we call hypertext indicating facilities in excess of a normal text actually becomes hypotext or substandard literature which is no longer as useful as its original paper form.

LACE was conceived as a solution to some of these limitations. Instead of a fixed array of characters, LACE supports typeset pages, with different font styles and sizes used as they would be in a printed document. A page allows more information to be presented to the user, so reducing the problem of information fragmentation. LACE avoids insularity by using documents that conform to various common generic markup schemes (LATEX, WEB and troff's man macros) allowing them to be viewed in a hypertext environment or formatted for printing without modification.

In the following sections Lace will be explained according to the various concerns of a hypertext system: how to represent, store and retrieve documents (back end issues); what facilities to provide for browsing published documents and navigating through the body of published works (reader's front end); and what facilities to give provide for creating documents and for linking them into the existing body of literature (author's front end).

3.1.1 Document Representation

LACE deals with documents which are expressed in some form of logical markup (commonly LATEX). This section discusses the reasons behind choosing explicit markup over a direct-manipulation WYSIWYG model and the choice of a particular markup system. Although users of other hypertext systems (such as Intermedia) directly manipulate a document's physical representation, logical markup and an abstract document model were chosen for the following reasons:

logical markup allows authors to make their intentions explicit

logical markup allows a document to be `ported' easily between diverse applications and systems

logical markup is very commonly used within the academic community

It is the first reason which is in fact the touchstone of LACE's approach to documents. An academic document often takes the form of a reasoned argument, and an argument involves a sequential development of points and a hierarchy of ideas and information which support and contribute to the main thesis. In a similar fashion a technical document frequently follows the structure of lexical taxonomy, in which the discourse proceeds from a general class to the subclasses and their particulars. The structure of such documents allows the reader to understand the contribution that a particular statement makes to the overall argument or theme and to make relationships between ideas that are being developed and ideas that have been previously established. If the structure is not stated clearly enough then readers are left to their own devices to make decisions about the function of a new piece of information, whether it is a subsidiary point of a previous topic or whether it stands alone as a major item in its own right, leading to ambiguity and confusion. Tyler [140] argues that the understanding of a document presupposes that the text as a whole is composed of a hierarchy of parts, and that comprehension of the text comes from construing those parts. The structure with which logical markup systems usually deal is a mixture of the macro-structures and superstructures of discourse analysis--the sections, subsections and sub-subsections are often used to dissect the subject-specific content, while their agglomeration into chapters and complete documents is controlled by the genre's (implicit) superstructure.

The use of logical markup which mirrors the logical structure of a document (structural markup) reinforces the semantics of the text that is being created. This is often helpful to the author as it coincides with the process of creating an outline of the document which both directs and constrains the authoring process. It is also helpful to the reader because the formatting process may use the structural semantics to provide visual clues to aid comprehension of the flow of the text (for example, the titles of key points may be emphasised by representing them in a bold font while subordinate information may be separated from a major points by extra vertical and horizontal space). It is also useful in a hypertext environment, because it makes explicit both the division of information amongst separate nodes and an initial set of links that can be established between those nodes--in effect providing method of automating the production of a hypertext network from a `flat' document.

SGML would seem to be the natural markup scheme for use with LACE, but LATEX [85] and troff's man package were chosen instead because of their widespread use within the academic community. In both cases the markup is actually implemented by programming language embedded in a lower-level formatting engine (see [8] and [85] for full descriptions). Of the two, LATEX is more widely used as it has been ported to all major computers and is compatible with all major printer types, whereas troff is mainly available on UNIX systems. LATEX is also the more flexible since it defines a one-to-many mapping between the abstract and physical structures by use of different document styles. Support has been provided for both troff's man macros and LATEX, although the description of LACE that follows will assume the latter.

As well as reinforcing the semantics of the text, structural markup frees the author from making decisions about the visual design of the document. This is especially important when the physical representation of the information may change radically for each different publication medium (computer screen, low fidelity computer printout or book). One of the goals of the LACE project is the reusability of literature. It is important that documents authored for one system are capable of being used in another, making the use of a text-based interchange format appropriate. LATEX allows the author to `plug in' different document styles to radically alter the physical representation of the document. LACE extends this capability by defining a hypertext style that formats the elements of the document's structure for display as nodes in a hypertext network.

3.1.2 Document Storage and Retrieval

In the `real world', literature is composed of published `works' in the form of novels, plays, manuals, reports and the like. LACE deals with these works, or `documents', which have to go through a publishing process before they are available to anyone other than the author. Both in the real world and in LACE, each document is in some sense complete in itself, containing all the information required for a particular purpose: a novel is published as a single entity, not as a separate set of chapters, although hypertext systems with fixed-sized nodes often force this sort of behaviour.

The publishing process which makes a document accessible to the world at large involves entering it into a host-wide database of documents presided over by the document librarian, also known as the lace dæmon. The database holds information about the document such as its title, keywords that sum up its contents, its access permissions, its type (video, LATEX, WEB or man) and its location in the filestore.

In LACE the structural elements of the document are the nodes of the network--each element of the document may be individually addressed by naming its position within the structure and the title or number associated with it (e.g. `abstract', `chapter 1', `section Troubleshooting and Diagnostics' or `table 3.5'). As well as this, each document is published by entering its details into a site-wide database. A librarian process listens for requests for individual elements from particular documents, and displays them in an appropriate fashion on the console.

Each individual document is itself a database--a database of logical elements (in the logical markup sense) and the relationships between them. The document librarian is a process that listens over the network for requests of the form Far From The Madding Crowd:chapter 4. The librarian then looks in its database to find the document whose title is Far From the Madding Crowd, checks that it has public access, and works out where it is stored. The document is then inspected, and chapter 4 is extracted from it and sent over the network to the user who requested it. Each document also has a short nick-name stored in the database along with the title, so that requests don't become cumbersome to type!

The structure-based addressing scheme acts to unify various document types. Videodisks are published divided into chapters which can be logically subdivided into different video sequences or `sections'. This allows links to be made to various media: the librarian process is responsible for displaying the various data types in an appropriate fashion (a window on the console, a sequence on a separate video display monitor or an audio sequence from a CD player). In this sense, LACE is a hybrid hypermedia system, as explained in section 1.2.1, as it allows simple access to information in different media.

3.1.3 Creating LACE Documents

Authoring a document is straight-forward since there is (or should be) no difference between creating a document for paper and creating a document for hypertext browsing. The document librarian provides LACE's low-level machinery, but the access to that machinery is largely hidden from the author. This is necessarily a part of the LACE philosophy, since its aim is to automatically convert existing literature into a hypertext format. In fact, just a LATEX aims to provide different document styles to automatically change a document's printed representation between that of a journal article, report, thesis and book, so LACE aims to provide a new document style that will change the document's representation into a hypertext network.

LACE uses all the facilities provided by the markup scheme to present the document to the reader in a useful way. For example, the author's use of chapters, section and subsections will not only allow the hypertext machinery to request that particular element, but also provides a table of contents with buttons to call up the sections automatically. This information is also provided as a menu and in pictorial form as a tree.

To publish a paper, it must first of all be converted into a form that the LACE librarian will accept. For LATEX documents this involves adding the lace documentstyle option at the head of the document and running latex as normal followed by hyperdvi. WEB documents (from TEX's structured programming language [82]) should first be processed by tex, (but should \input hyperwebmac instead of the standard webmac), and then by hyperdvi. Troff manual page are processed by hypertroff -man. All these processes create a .ps file that will be used by the librarian, and a .ps.map file that indexes the PostScript file by the original document's logical structure.

Publishing consists of making an entry in the librarian's database. This is accomplished by running the command lace -n foo, replacing foo with the name of the file that holds the document. The author is then prompted for a number of pieces of information (such as keywords describing the content of the document), and the database is updated.

3.1.4 Reading LACE Documents

LACE documents are displayed using the NEWS windowing system [61], a PostScript-based window system that is proprietary to Sun Microsystems. (NEWS was later incorporated with X11 into SunOS's OpenWindows, but has now been dropped in favour of Display PostScript extensions to X11.) The command startLACE fires up the server with the extensions needed to display all the documents (since NEWS was a class-based PostScript environment, the startLACE command defines new document classes for TEX and troff documents). Typing lace help in the console window brings up a document that gives guidance for running lace and also provides buttons to reference all the documents available on this host.

At a casual glance, LACE provides a LATEX previewing facility, and allows the page to pass as part of the logical structure. This is convenient in allowing reader to make use of the familiar book metaphor. When a request is made for a document without specifying any substructure the librarian process returns `page 1'. The LACE menu has the usual TEX previewer functions of moving between pages as well as the hypertext capability of stepping backwards through the list of nodes seen so far. The Table of Contents, List of Tables and Lists of Figures, usually seen in the document's front matter are also turned into submenus which bring up a new window containing only the appropriate document element. As well as the menu these table structures have buttons placed over each line, so that clicking on the line in the Table of Contents which refers to section 3.3 also brings up a new window containing that node.

LACE buttons are transparent `patches' which respond to a mouseclick by sending a request for a document part to the librarian process. Visual cueing is left to the document style or author to decide, though it is anticipated that the author will never have to explicitly request a hypertext link. Instead, LACE attempts to infer as many links as possible from the structural markup. This is done not only for navigation structures like the contents list and lists of tables structures, but also for cross references and citations.

Some of the document's physical representation has been changed for more suitable behaviour in a hypertext environment. Document formatters make every effort to move some structures (table, figures and footnotes) out of the main body of text as they interfere with the flow of the discourse. Usually they are `floated' to the top of a new page or a page by themselves to minimise their interaction with the surrounding text. In a hypertext network they can be taken out of the containing node entirely. Tables, figures and footnotes are displayed by clicking on cross-references to them.

Click here for Picture

Figure 3.1: The title page of a LACE document

Figure 3.1 shows the title page of a LACE document. The window is surrounded by a frame with the title of the document, and an indication of the number of pages through the document (here on page 0 out of 26). In the top left-hand corner is the close button that shrinks the window to an icon when it is pressed with the left mouse button. In the bottom right-hand corner is the adjust button that shrinks or expands the window by clicking on it with the left mouse button and dragging the window until it has the required size. The bottom left-hand corner houses the zoom button which magnifies the size of the page by clicking on it with the left button (zoom in) or shrinks it with the right mouse button (zoom out). The upward, downward, left and right facing arrow-heads are scroll buttons that are activated by the left mouse button. To move the window, click anywhere in the frame and drag with the middle mouse button.

The menu is brought up with the right mouse button. The menu items Next Page and Previous Page advance through the document and back, one page at a time. Goto Page brings up a submenu with the page numbers that can be chosen directly, and Back returns the reader one at a time backwards through the list of pages that they have visited.

The Contents submenu lists the major document structures (exactly like a table of contents) and brings up the appropriate part in an independent window. It helps the reader to navigate quickly to the information wanted, as long as its position is known. There are also submenus for Figures and Tables which will only appear if the document had any figures or tables in it. A new window with the appropriate figure or table will be displayed when the reader makes a choice from one of these submenus. Since the object has been `floated out of the document' and away from the main flow of text the user will only see the object by using these menus, or by clicking on an explicit reference to that object.

The Add to Trail menu item puts a reference to the current element on display in the reader's trail. A trail is simply a document which is composed of list of references to other documents, with the effect that list of interesting references can be saved and replayed later. An automatic trail is also kept which consists of every document element seen, whether interesting or not! The Gotos and ComeFroms items give submenus detailing the other document parts (or nodes) that are referenced by this node or that reference this node, respectively. This enables the reader to jump to any piece of information that has been marked as being relevant to this node. The last item, Zap, destroys the window.

Figure 3.2 shows the the end of a (somewhat hectic) session which demonstrates many of LACE's features. The title page of a document similar to that shown in figure 3.1 is in the top left corner, as are further pages. Page 1 is shown slightly to the right, displayed in the same fashion as a printed page, but with a number of hypertext effects added, all implemented as buttons on the page. A button is an invisible patch placed over a significant word or phrase on the window. Since it is invisible, it is left to the typesetting software to mark the phrase as `active', generally by using a different font. Each document style will choose its own convention for displaying important material. When the mouse pointer is moved over a button the cursor is changed to a cross to indicate that a hypertext jump is available.

Click here for Picture

Figure 3.2: A LACE session

Buttons have been placed over each entry in the table of contents, list of tables and list of figures. Clicking on any line in the table of contents or list of tables performs a jump to that part of the document--a button has been placed around each line of the table of contents that sends a request to the LACE librarian for the specified node. Footnotes are treated similarly. Each footnote marker (usually a superscripted number or asterisk) has a button placed over it. When the button is clicked, the text of the footnote is displayed in a new window. References to other parts of the document are also given buttons: clicking on a piece of text that looks like for further details, see section 4.5 will bring up a new window with section 4.5 in it. Citations of other works are treated similarly: the citation markers (like `[8]' or `Rahtz85') are given buttons that bring up the full reference from the document's bibliography. There is currently no method for bringing up that document, even if it is held in the system.

To the right and overlapping with the first page in figure 3.2 is a window containing the Introduction section from the same document. It contains some of the text which is on the first page, but is not finished by the page boundary, containing all the text from section 1 and any enclosed subsections. The long window over the top, slightly obscured by the menu is a footnote window, brought up by clicking the (obscured) footnote marker. Below the title page is an experimental table of contents, produced by the LATEX typesetting software as part of the LACE document style, intended to give an alternative form of graphical navigation. The other windows are section 1, a table and a figure from another document. Appendix 2.1 contains further information on the use of LACE along with details of its implementation.

3.1.5 A Comparison of LACE with other systems

LACE bears some similarities to NLS in its treatment of nodes, since it models a document as an hierarchical structure, any subtree of which is taken as a whole node. Other systems only allow an individual leaf from the tree to act as the node. For example, choosing section 3 from a LACE document will result in the entire contents of that section including any subsections, whereas the same operation in ZOG displays only the node which represents that section, the subsection nodes being addressed by further hypertext jumps.

LACE allows a large degree of access to multiple information types by virtue of its unified data addressing scheme. Many of these types of information are provided by the typesetting software (diagrams, tables, complex mathematical equations, graphs) and are really part of a fundamentally textual document. Video information truly is a different medium, although it is not currently fully integrated into the environment since it is not currently possible to have a video node (or a subpart of a video node) as the source of a link. However, the generality of the addressing scheme allows computational information types (such as dynamic references to tables in a relational database) to be intermixed with text and video.

The large screen which LACE uses to display its windows allow a large body of information to be shown to the reader at once. This allows the reader to work in the familiar book paradigm, using its familiar navigation and browsing techniques (tables of contents, indexes, cross references).

Links are not currently first-class objects, but are simply references to the destination address invisibly embedded in the text. However, much can be done at the time of publication, including building a list of the links into and out of each node. The role often played by a graphical browser is adequately given by the table of contents. Changing the publication process so that links are included in the document's map file is sufficient to make links into first-class objects, allowing the creation of a true graphical browser.

An advantage of LACE is that it allows reusability of each document. The same version that was produced as a paper report can be stored as part of a hypertext network because of the generic nature of the markup that is used to describe it. If hypertext is to succeed as a medium it is just this sort of integration which is necessary, otherwise a prohibitive expense will be incurred in redocumentation. Practical experience shows, however, that authors tend to write for a particular medium, and even for a particular house style, especially if they are not anticipating the reuse of their efforts. Often this involves abandoning logical markup and mixing text formatting commands with the logical markup to gain a specific layout effect. Unfortunately, this meant that it was frequently necessary to alter (although one might say "improve") the document source to produce a suitable hypertext conversion.

A disadvantage of LACE is that is based on a non-WYSIWYG process, i.e. there are two versions of the document: the one that the author wrote (the LATEX document) and the POSTSCRIPT version that the typesetting software created. Because of this it is difficult to make any changes to a document, including adding new links, without resorting to a `recompilation' process. Since the typesetting software also destroys the sense of the document (turning it into a list of characters and white spaces) it is difficult to provide a dynamic querying of the document. LACE makes up for this deficiency by searching the source of the document and returning the appropriate node from the compiled version.

Acrobat, a more recent document environment than LACE, turns each document into a database of objects which can be individually addressed. Unlike LACE, the document is structured not according to its logical content, but its physical formatting characteristics. Acrobat does not attempt to automatically generate hypertext from an existing document, instead it `normalises' the document's formatted representation and provides a viewer which can add hypertext links and annotations to the document. Both Dynatext [46] and Grif [116] (also more recent systems) are similar in concept to LACE, but use SGML style markup instead of LATEX. DynaText directly interprets the SGML markup to produce a formatted physical structure, and so does not suffer from the disadvantages of LACE`s compilation process. DynaText also provides full-text indexing of its documents, whereas LACE only deals with a document's gross structural elements.

3.2 Document Structure as a User's Tool

LACE takes advantage of the internal structure of a document as a navigation facility for readers, but beyond that structure can also be treated as a construction tool for authors. In this section we will further consider systems that take advantage of a document's structure.

3.2.1 Structure as a Tool for Navigation

Cole and Brown [40] are not alone in commenting on the similarities between paper documents and hypertexts. Furuta, Plaisant and Schneiderman [59] describe the conversion of several kinds of documents into hypertexts. Raymond & Tompa [119] describe the production of book and hypertext versions of the Oxford English Dictionary from a single (SGML) source. Others have argued that hypertexts should conform to the same user-interface and navigation paradigms as books [11, 74].

The end result of the authoring process for a paper document is not a database of facts but a discourse or directed presentation whose structure is a part of the meaning of the discourse [135]. LACE exploits this explicit structure of presentation as a navigation tool for browsing the hypertext. Grif [116] and DynaText [46] also perform a similar function for the structure of documents expressed in SGML.

Narnard and Narnard [106] also work with a model of structured documents, but extend it with parallel structures representing knowledge domain concepts and task domain concepts. Explicit relationships (or links) are set up by the author between the various layers of structure (from the document to the knowledge base or from the knowledge base to the task descriptions), so that the system can use these different information sources to improve the reader's navigation around the document layer. In this system, document structure is augmented by a content-based knowledge structure as a navigational utility, and can be used to generate new views of the original documents (synthesised documents). See section 3.2.4 for a description of a system which provides this kind of layering of structures to aid authoring.

Others have also seen structure as a means of navigating a hypertext, even when structure is not explicitly present in the network. Such post-hoc structuring techniques are explored in [18], where graph-theoretical algorithms are used to identify abstractions such as aggregate concepts within a network. Another post-hoc method of imposing structure on an existing hypertext to aid readers is given in [94], where implicit structures are derived from the spatial relationships of a displayed hypertext network. Salton uses textual comparisons to identify similarities between groups of texts, and thus creates a linked text structure to allow navigation [127].

3.2.2 Structure as a Tool for Authoring

A lesson that Brown distils from the development of Guide is that it is important not to set out to build a hypertext system, rather to set out to build a system to help authors and readers of online documents [26]. This section describes the development of a prototype system (LACE-92) which is intended to extend the focus of LACE into the authoring stage of a document's life-cycle, and then describes the authoring support provided by other systems.

Hypertext studies have looked at the mechanisms of joining and intertwining information units, of the mechanics of hypertext jumps, the technology which supports reading and analyses of comprehension. What is frequently lacking is the context of a complete document life-cycle in which to fit the finished hypertext: how is information presented for reading, and how is a document composed from the raw information.

Structure can be used not only to present pre-existing material but also to direct and constrain the authoring process. This section describes an extension to LACE to encompass the authoring stage of the document life-cycle by providing a simple model of the authoring process.

The previous description of LACE has shown how a document's logical structure is useful for imposing a hypertext presentation upon it and why that should be so: a document is created and shaped according to the rules governed by its superstructure. This section covers a model for authoring new material in a hypertext environment. LACE utilised "off-the-peg" literature, while other systems have assumed that pre-written (or pre-planned) material is to be imported chunk-by-chunk [72] in an author-unfriendly fashion. Hutchings describes in chapter 8 of [72] the necessity for a complete storyboarding process to take place away from the hypertext system in order to establish the required structure and contents without confusion. Most realistic writing assignments, however, involve an author starting from scratch without the benefit of a file containing the contents of the finished assignment.

Lace '92 is a prototype system which implements a simple model of authorship in which an author first of all researches (i.e. searches for relevant ideas and information), then chooses the information appropriate to the task, then organises the information within an informal structure. This structure develops iteratively into the logical structure of the authored document, and is used to create a new LATEX or SGML document containing the references and quotations chosen in the earlier stage.

3.2.2.1 The Author as a Reader

When presented with an assignment the author starts work as a reader, searching the literature for all relevant work. This may not just occur as the initial phase of an individual project but may also continue through all following phases of the authoring process. In a hypertext environment this means that all previous works must be easily available, with good browsing facilities and sophisticated information retrieval facilities to be able to deliver a reasonably comprehensive list of relevant material. The phrase "previous works" should include not only carefully edited, published online works, but also more haphazard sources such as personal notes, E-mail conversations and bulletin board messages.

3.2.2.2 The Author as a Censor

Having obtained a body of material (documents or raw facts and statistics), the author must decide which items are truly relevant, which are relevant but uninteresting, and even those which are relevant but "wrong". This process is driven by the nature of the final work and its identified macrostructure (anthology, report, summary, experimental report), the desired conclusion, and the intended audience.

This model assumes that the author is provided with more than enough source material (or information) to produce the finished work, and places the author in the role of a sculptor, chiselling away unwanted material to reveal a work of art beneath.

3.2.2.3 The Author as an Organiser

Having obtained a pertinent set of source documentation, the author must choose how to present this information to the audience. This process consists of two activities: partitioning, in which the common themes are identified and sources grouped according to this thematic classification and sorting, in which items of a particular theme have a partial ordering imposed on them. This ordering is due to the constraints of the document (whatever the medium a reader can only follow one trail at a time) and the constraints of the document's superstructure. For example, if several points are to be presented, it may be necessary to present one before the points which support or refute it. These two processes are iterative, since each theme may be divided into subthemes requiring more partitioning and sorting.

3.2.2.4 Overview of LACE-92

LACE, as has been mentioned previously, used pre-authored literature and presented it in a hypertext environment using information on its internal structure to produce a degree of automated link generation. The authoring had to be done (unsupported) using a text editor, but the goal of LACE-92 is to provide as much support to the author as possible, and to ease structured hypertext authoring.

LACE-92 uses WAIS information retrieval techniques (see section 4.2 for a full discussion of WAIS) to provide the author's set of source documents from network-based information servers. Much of the material would be from pre-published works, and may be in a structured, hypertext format, allowing the chosen sources to act as transclusions or links back to their native hypertext networks. In this way, a new document will automatically be linked into the existing literature from the very start.

The partitioning and sorting described above proceeds on a network diagram, where the overall structure of the network is constrained by the document's chosen superstructure. When these processes have run to completion, the author has produced a skeleton of the finished document. It contains a framework consisting of the points and themes which are to be presented, with the sources placed appropriately. The framework is fully linked with the source literature, and, by virtue of the chosen document structure is also internally linked. The network browser could also facilitate the production of high level summaries, automated tables of contents, citations, references, footnotes, glossaries and other physical document structures.

What goes into the network is mainly "information" and "quotations" which are linked back to the original sources. However the final stage of production is a written document, not a handful of transcluded texts and citations, so it is necessary to do some real writing! This may be achieved in the browser, but the whole framework can instead be exported as an SGML or LATEX document for editing in a conventional environment.

3.2.2.5 Using LACE-92

Click here for Picture

Figure 3.3: The WAIS information-gatherer component of Lace'92.

LACE-92 exists as a prototype implemented in HyperCard, and is based around two HyperCard stacks. One (see figure 3.3) is for information retrieval using the WAIS protocols and a WAIS-like interface and the other (see figure 3.4) for manipulating the relevant retrieved information.

According to the simple authoring model of Lace '92, the author starts with a writing task which involves selecting relevant material from a library of information. This is done by choosing from among a menu of information servers, each typically concerned with a single topic. The field at the top left of the WAIS window in figure 3.3 shows that the user has chosen the database of CACM articles at the Internet site quake.think.com (these are a set of articles on the subject of hypertext which were originally published in [1]). The field at the top right of the window shows that the user has asked for articles about "hypertext" and the scrolling field in the middle of the screen shows the list of articles returned by this query. The user clicks on one of the lines to retrieve the full article which is then displayed in the bottom field.

Click here for Picture

Figure 3.4: The information-organiser component of Lace'92.

The user may select any text which is relevant to the task in hand, and by dragging it offscreen can have it placed in a new field in the organising window (figure 3.4). Along with the selected text, the system stores the details of the chosen article's remote storage address, the server it was obtained from and the offset of the selection from the start of the article. As the user builds up more and more of these selections they can be easily moved around the screen to reflect some form of incremental organisation. Each text selection can have its enclosing field moved, resized or deleted, and the text can be reformatted with single keypresses.

Once a collection of document fragments has been retrieved it is partitioned and sorted by laying the information out as an (informal) network. The network structure of the information is expressed by its position on the screen, with similarly relevant pieces of information being clustered together (this use of spatial layout is also described as a way of creating structure in [92]). To alleviate clutter on small screens, it is possible to select the nodes in a cluster and have them replaced by a named aggregate node which expands to a new (subordinate) network diagram by choosing New Partition from the Lace '92 menu. The network of document fragments should be created according to the required document superstructure, although this is not enforced. The collection, sorting and partitioning phases may go on in parallel and may be iterated many times, but once the user is ready to proceed with the writing phase of the task (combining the collected quotations and evidence into an original work) then the current state of the document can be dumped (in SGML or LATEX format) to a text file by choosing Export Structure from the Lace '92 menu. Not only is the partitioning reflected in the heading structure of the file, but also each quotation is recorded with its reference from the WAIS retrieval, so that this new piece of writing is created with `links' back into a wider body of literature.

3.2.3 Related Authoring Support Work

This section describes a number of systems that have been designed from scratch to provide authoring support and some existing systems which have been retrospectively enhanced to provide better support for authors.

Marshall & Shipman [94] point out that although unconstrained hypertexts are the norm, embedded constraints can aid the coherence and consistency of a network. Many systems which allow unconstrained hypertext, support the author by making it more easy to create consistent structures which are constrained according to some chosen type or model. These constraints may take the form of standard structural components which can be `plugged' together to produce the overall network. Both Notecards and Intermedia developers have recognised the need for this kind of author support. The NoteCards approach is the Instructional Design Environment [79] which provides structure accelerators, in the form of template cards (containing prototype text and links for various styles of card), automatic links (which create a new anchor, link and card of the appropriate type in one operation) and a structure library (which is a global store of named, contentless hypertext structures taken from specific instantiations of networks of cards). Intermedia provides Hypermedia Templates [39] which are a combination of IDE's template cards and structure library, containing both node prototype contents and inter-node links.

Both the Instructional Design Environment and the Hypermedia Templates provide "fill-in-the-blanks" support for authors to be able to rapidly create larger hypertext networks, but provide no support for the cognitive disciplines involved in writing (creating the node content). The cognitive overhead required for producing the hypertext form is lessened, but support is given not for what to say or how to say it but only where to say it.

Various authors have proposed hypertext models containing composite nodes, i.e. nodes which `contain' subnetworks of linked nodes [49, 91, 130]. These models help authors to compose large complex artefacts from smaller subgraphs, also resulting in improved human comprehension of the network structure. The HyDesign model [91] also helps the author to structure the network by providing aggregate links for sequence, hierarchy and group abstractions. De Bra et al [49] introduce other network abstractions: the tower (for representing multiple levels of description of a concept) and the city (for multiple views and perspectives of a concept).

A number of other hypertext systems have been designed to allow explicit representation of structure. Nanard & Nanard describe in [105] their use of MacWeb to allow the description and capture of knowledge-domain information. The MacWeb hypertext kernel provides weakly typed nodes and links; the application built upon it makes use of a separate hypertext network to define relationships between the different link and node types which are to be used in the main hypertext. It is this augmented type structure which is used as a basis of building the hypertext according to a specific pattern of knowledge elicitation.

Kaindl and Snaprud [80] make it explicit that there are two quite separate structures which the author needs to attend to: the structure of the text and the structure of the underlying knowledge. Whereas IDE, HyperMedia Templates and Narnard's systems attempt to structure the text according to (gross) relationships in the knowledge domain, Kaindl presents a mechanism for unifying the two structures in which the hypertext is implemented by a system of frames inside a knowledge representation tool. The rules of the system ensure a close match between the structure of the hypertext and knowledge domains, with appropriate links automatically managed between the corresponding nodes.

Aquanet was designed to allow authors to express structured relationships between hypertext nodes, but experiences from its use [93] show that authors do not rely on a predefined library of network structures. Instead they try to define their own schemas for hypertext structures, often without a full understanding of those structures, and were consequently frustrated by a system unable to support flexible schema modification. Similar problems of premature commitment were also seen by users of Notecards [93] and even users of non-hypertext structured document editors [22]. Aquanet users circumvented this problem by using the main display space as a drawing board, and expressing developing relationships between objects as similar spatial relationships between the object icons (e.g. similar objects may be placed in a messy pile; a `uses' relationship may be expressed by placing the `user' on the left-hand side of the `used'). Marshall & Rogers [93] describe the Aquanet users' various manipulations of representational structure as crucial to the author's interpretive process, and a basis for subsequent writing activity even if the hypertext network and content are not reused.

One of the aims of the SEPIA system [137, 138] is to help avoid problems of premature organisation of unfinished or poorly understood ideas by offering authors more assistance than organising linked nodes of text. It makes a similar but more extensive separation of domains than are seen in Kaindl's system. SEPIA provides an authoring environment based on the ideas of micro-, macro- and super-structures expanded in chapter 2. It provides a number of writing spaces in which different types of writing activity are performed, including a content space for building up semantic networks representing the domain knowledge (as well as notes, excerpts and whole authored texts), an argumentation space for generating, ordering and relating arguments about the knowledge and a rhetorical space for organising and re-organising the global outline, issues, arguments and coherent sentences. SEPIA is more complete than LACE-92 in that it provides a separate activity for the authoring processes associated with each `level' of structure composing the text. LACE-92 only allows the author to manipulate the final `rhetorically and argumentatively complete' text, even while trying to manipulate the basic relationships between the knowledge of the knowledge domain.

3.3 Authored Structure vs Evolutionary Structure

According to Moulthrop, hypertexts must have local coherence within a grain [104]. These grains, or lexias are reading units which can stand in isolation and are the atoms of a hypertext network [87]. In a hypertext environment such as Notecards or HyperTIES, the lexias are the individual cards or screens of information which are linked together to form the larger network. In a document-base