DRAFT -- DRAFT -- DRAFT -- DRAFT
XEROX
PALO ALTO RESEARCH CENTER
System Sciences Laboratory -- Computer Sciences Laboratory
December 16, 1975
Xerox Internal Use Only
To:File
From:Bob Sproull, William Newman
Subject:Press Overview
Things go in through SLITS and come out through SLOTS. What you’re talking about is everything in between. -- Lee Sproull
Abstract
Press is a set of conventions used to define, in computer-readable form, a wide variety of documents. The most important part of Press is a specification of a file format that allows images, line drawings and text data to be intermixed freely in a document. The file is designed so that (a) documents can be acquired with document scanners such as SLIT devices and represented in the file; (b) text editing or composition programs may easily create documents or make modifications to documents represented by such files; and (c) output to printers or display devices can be generated easily.
Press was initially designed in January 1975; the conventions described here have been in use at PARC since then. Experience with scanning in, editing and printing such documents is growing. The Cypress project, currently underway, will combine into one interactive document creation system a powerful text editor, illustrator and composer based on the Press conventions.
Table of contents
Introduction
Design considerations
The Press design
Design critique
History
Present uses of Press
Plans
References
Introduction
The need for adequate means of encoding documents for digital processing has existed for some time. We can see how serious this need is by considering just the narrow field of word-processing. Most word-processing systems attempt to encode documents in ASCII or EBCDIC; these encoding schemes were never designed for document encoding, and include no facilities for accurate text positioning or changes in character font. Attempts to extend ASCII or EBCDIC for these purposes have generally been extremely awkward and of limited capability.
We would now like to extend the notion of a document to include forms of information other than text. Many of the documents and office forms in use at PARC contain line-drawings. There is also a considerable need to include solid-tone or half-tone images, particularly in certain classes of high-quality, large-circulation documents. Finally, we would like to experiment with documents that include voice messages or annotations. Documents will often contain several different forms of information on one page, so the encoding technique should allow the mixing of forms of information in an arbitrary fashion.
The Press Format has been designed to provide a complete and consistent method of encoding documents. It provides full capability for multiple-font, arbitrarily positioned text, together with image and line-drawing capability. There is at present no provision for voice information, but the Press format is designed for easy extension to other such forms of information. We have designed Press to meet a number of important criteria. The full list of criteria, of which the first two have been mentioned, is as follows:
Versatility: The format should accommodate all kinds of text, line drawing and image information. This objective permits Press to become a standard format for encoding documents. [[Footnote: In this discussion we use different terminology from the OIS Architecture Report [1], where the terms used are Orthographic for text, Ideographic for line drawings, and Imaginal for images.]]
Extensibility: The format should be extended easily to handle other forms of information.
Compactness: Documents represented in the format should be compact, for efficient storage or transmission.
Ease of output: It should be easy to print and display documents.
Device independence: To the extent possible, the appearance of displayed and printed documents should be unaffected by the output device used.
Ease of generation: It should be easy to generate documents in the format.
Ease of editing: It should be easy to create or modify documents interactively with a variety of editing and formatting programs.
Editor independence: Methods used to permit interactive editing of documents should not cater for a particular document creation system, but should be generally applicable.
Robustness: The format should not be fragile. A small error should not be allowed to propagate and prevent the entire document from being read or printed.
The following discussion first addresses the approach used by Press to define documents and outlines the considerations that guide the design. Then the design is presented in more detail, including encoding techniques used for text, line-drawings and images. Finally, we present a critique of the design that presents reasons for various design decisions and illustrates shortcomings of the design. A complete description of the Press format is given in Reference [2].
Design considerations
A design problem of the magnitude indicated by the Press objectives is perhaps best attacked by trying to meet each requirement independently and then to deal with interactions. This section takes up the issues in the design of the various aspects of Press: the graphical representation of the document, the information included for the benefit of editor programs, etc. As we shall see, the interactions have had a substantial influence on the final design.
The overall design problem is similar to that of designing a graphical data structure [3]. This technique, used occasionally in interactive computer graphics systems, tries to combine in one data structure both the information required by a hardware display processor to generate a picture and the information required by the application program in order to carry out its calculations. It is inevitable that the choice of objects contained in such structures is a compromise between convenience of representation for the application program and convenience of representation for the display processor. Experience designing such structures has shown this to be a difficult compromise to resolve.
In the Press design, we are freed from the need to design a graphical representation for a particular display or printing device, and can instead choose a representation that does not impair choices of application-oriented structures. On the other hand, Press strives to accommodate different, unanticipated, application programs (editors, formatters, printers, etc.) and requires an application data structure that is generally applicable to these uses.
Pages
Because a document is normally composed of a sequence of pages, Press views the problem of representing a document as that of representing each page individually. Of course, some information is naturally associated with the entire document (e.g., the typefaces used for printing characters), and Press indeed collects this information into a Document Directory and a Font Directory.
This view has some disadvantages. For example, it often happens that a paragraph of text is split between two pages; the Press representation will require that the first part of the paragraph be included with information for one page and the second part with the successor page. This strategy is somewhat inconvenient for document editing programs: a modification to the first part of the paragraph may require that the second part be modified as well, and thus that the Press description of the next page be modified. [[Footnote: The passages in small type are technical asides that are perhaps best ignored on first reading.]]
Cypress, a document editing system designed to edit documents described by Press files, is exploring various solutions to this problem. It appears that this problem can be solved without incurring noticable delays in the interactive editors.
Graphical Representation
Choosing a graphical representation for a document seems deceptively straightforward: we must simply specify what black marks are to appear on each page of the document. Closer examination reveals an extremely wide range of alternative representations.
A conceptually simple approach is to represent the entire page as a single dot-matrix image, using one of the many facsimile encoding techniques available. Text characters in the document are replaced by appropriately shaped patterns of dots. A page defined as a dot image is easily printed on a matrix printer such as SLOT, since the intensity of each dot on the page is uniquely defined. There are overwhelming disadvantages to this approach, however: the method is extremely device-dependent, requiring matrix-oriented printers and displays of fixed, closely coordinated resolutions; text in the document is extremely difficult to edit; and the representation is far from compact.
A more subtle problem prevents this method from working. Although the sampling theorem shows how resolution conversion can be achieved, such methods are inferior for generating low-resolution displays. For example, a low-resolution 1 bit-per-point display (such as the Alto) can display quite legible text characters, provided they are carefully designed for the particular display device being used. A key part of the design is distorting character shapes so that legibility is achieved (i.e., the designer can cope knowledgeably with quantization effects). Resolution conversion will not perform the distortion (i.e., produces random quantization effects), and characters are substantially less legible.
Press adopts a different approach: a page is defined as a collection of graphical objects. Objects are chosen to correspond to the natural forms of information that appear in documents: text is represented by strings of character codes; line drawings are described by their geometric properties; images alone are represented by sample arrays of the sort mentioned above. This approach conserves storage space and offers substantial convenience to editing programs that operate on the objects.
The position of each object on the page is specified as an (x,y) coordinate in a standard Cartesian coordinate system: the point (0,0) lies at the lower left-hand corner of the page; values of x increase to the right, values of y increase toward the top of the page. The unit of distance on the page is a mica, equal to 10 microns. Recording positions in this way is thus independent of the addressing mechanisms chosen by output or display devices.
Each object representation has two parts: a description of its color, and a description of its shape. In order to achieve compact files, the storage of the information varies among objects:
Geometric objects. The shape of a geometric object, exemplified by a line drawing, is described mathematically by its boundaries. The boundaries are made up of line segments or of parametric cubic spline curves [7]. Thus a rectangle is described by 4 line segments that comprise its outline; the standard coordinate system is used. The color of such an object is assumed to be uniform throughout, and is described by a set of numbers.
Text objects. Although text characters could be represented as geometric objects, they occur so frequently in a document that a more compact representation is required. We have chosen to represent a character by a font code and a character code (usually ASCII). The Press file includes, in a Font Directory, a table that associates font codes with type faces, using terminology borrowed from the printing industry. Again, characters are assumed to have uniform color.
Image objects. The shape of an image is a simple rectangle, but the color varies within the region. Colors (often simply black and white) are sampled and encoded, using one of a variety of schemes. In simplest form, the images are analogous to facsimile data.
The job of a program that prints Press files is to reproduce each object as faithfully as possible. Adequate device independence is achieved by representing the shapes mathematically in a standard coordinate system, and by expecting the printing or displaying program to perform whatever calculations are necessary in order to generate an acceptable likeness. A necessary consequence of the goal of device independence is that computation is required to generate output for a particular device.
Computation and buffering are often required because the Press file does not order the objects for printing. Some printing devices (e.g., SLOT scanners) require that the objects be sorted first, so that they can be presented to the output device when the appropriate part of the page lies under the output head. In order to achieve device independence, Press does not order objects for printing because some printing devices have random access to the page (e.g., the Alto display), and because different printing devices may require different kinds of ordering (e.g., portrait or landscape SLOT printers).
Unfortunately, encoding the page as a collection of graphical objects introduces a complication, that of overlap. It may happen that a black object and a gray object overlap on the page, causing part of one object to obscure part of the other. Which obscures which? The Press file must leave nothing to chance: it must unambiguously describe the appearance of the page. To resolve the ambiguity, Press introduces an overlay concept analogous to painting: the Press file is viewed as an ordered list of commands to "paint" various objects onto an initially blank page. This technique insures that objects that appear late in the list will over-write objects that appeared earlier.
One might be tempted simply to rule out the possibility of overlap, and require objects specified for a given page to be either all the same color (in which case overlap ambiguities will not change the visible effect) or to be free of overlap. The second requirement would make certain simple illustrations extremely difficult to represent: consider a legend of black text that appears on a gray background, perhaps in a segment of a pie chart.
This approach to resolving overlap ambiguities has also found application in generating hidden-surface renderings of three-dimensional objects [4,5,6].
To summarize, we have chosen a graphical representation that considers a page to be a set of graphical objects, each described by position, shape and color. Positions and shapes are described mathematically in a standard coordinate system; character codes are simply references to standard sets of shapes. Images are represented by reflectivity samples, and are conceptually rectangular objects of non-uniform color.
Printing and Generation Considerations
A key requirement of the Press design is that pages should be printed easily on a wide variety of devices. This "printing" process may be performed in order to generate "hard" or "soft" copy. A program capable of printing a Press file on a SLOT/3100 is an example of the first; an editing program that "prints" a page of a Press file on the user’s display console is an example of the second.
Although we cannot anticipate the consequences of all possible designs of printing devices, several general considerations influence the Press design:
1. Effective and reasonably efficient algorithms must exist for transforming the graphical objects in a Press file into a form that is suitable for the printing device. Of course, some devices may be unable to generate even crude likenesses of some objects (e.g. an image object displayed on a character-only printer). Press conventions expect a printing program to use its best efforts to generate a faithful rendition of the Press description.
2. Because we have chosen to represent text characters by a font code and a character code, each program for printing Press files requires a substantial library of font shapes on file. No attempt is normally made to include these shape descriptions in the Press file, principally because the shapes are best stored in a form that is particularly convenient for the printing device.
3. Insofar as possible, the contents of a Press file should be arranged in an order that is convenient for most printing processing. It would clearly be disastrous if several passes over a Press file were required in order to print on even the simplest of devices! For a simple, random-access printing device such as the Alto display screen, we might wish a page to be printed "on the fly," i.e., by a simple linear pass over the description of the page.
A typical hard-copy Press printing facility might be a high-speed digital processor attached to a communications network, a large disk and a SLOT device. A Press file would be transmitted to the printing station via the communications device. The printing system might be able to print a copy of the document as the Press file arrives, page for page. Alternatively, it might perform some "pre-processing" as the file arrives, buffering the intermediate form on the disk, and only start printing after the entire file has arrived (a printer that prints the last page first, such as a SLOT/7000, must clearly wait for the last page to arrive before printing can start). Or it might choose different approaches for different pages because the pages have differing complexities.
The ability to generate Press files with straightforward processes is also desirable. Simple formatting programs may wish to input a file of standard ASCII text and to create a Press document with appropriate formatting of lines, pages, etc. (This process is similar to computer systems capable of generating pleasing listings of text files on an output device.) Again, a convenient convention for ordering information in the Press file might permit this process to be performed rapidly, without buffering the entire output file.
The concern for avoiding buffering arises in this case because we envision a simple formatter being able to pass the Press file into a communications network as it is being created. If the Press format required information available only after the formatter is finished (e.g., the number of pages in the document) to appear near the beginning of the Press file, the file must be buffered before it can be transmitted.
Given only the requirements of graphical representation and of printing and generation convenience, a very simple design of the Press file would suffice. Very few conflicting requirements have arisen. As we shall see, it is the editing requirements that introduce complexity.
The requirements already mentioned can be met with a straightforward design; indeed our first design for Press demonstrates the simplicity: The file has a document header, followed by a table of correspondances between font codes and typeface names, followed by the page encodings. Each page has a header to mark its beginning. Objects on the page can be grouped together for good encoding: a text group might have a header specifying position, color and font code; the data in the text group would be characters in a single font to be placed at the given position and subsequent positions along the text line. Similar encodings could be used for geometric objects and image objects.
This encoding certainly meets the graphical requirements, and can be generated on-the-fly (with the proviso that a simple formatter must anticipate what typefaces are required). It could be printed on-the-fly on a random-access output device: the typeface information arrives before any font codes that require it, and the pages arrive in order. A SLOT output device might have to sort objects into an order that corresponds to the order of appearance under the output head of various parts of the page.
Editing Considerations
Making a Press file easy to edit is partly a matter of arranging the file data structure so that modifications are easy, and partly a matter of providing, in the data, the sorts of information required by an editor to decide what changes to make. We have already mentioned the most fundamental requirement, that the graphical constructs used by Press correspond to the units that are often rearranged by editing (characters, geometric objects, images).
Editing programs will, however, wish to structure these objects in various ways. Typical formatting text editors do not view a document as simply a collection of characters, but rather as a hierarchy of objects:
Pages
Paragraphs
Lines
Words
Characters
A representation for such a hierarchy must state the inclusion relationships as well as additional information. Paragraphs, for example, may need margin and justification information used to re-format the paragraph when a line, word or character within it is altered. This is a simple example of the sort of non-graphical information that accompanies the abstract objects in editors.
Press must permit structural and ancillary information to be saved with the graphical objects for a page. However, it cannot choose a representation that would force a particular hierarchy on an editing program.
Further requirements for editing can be determined by considering the sorts of operations that an editor performs frequently:
1. Displaying portions of the document. In many respects, this activity is identical to that of printing a Press document. It differs in one crucial respect: the editor may wish to display only that portion of the document which falls within a rectangular window, a process referred to as "windowing" the document. If Press is designed correctly, the display can be created without testing all objects on the page to see if they lie within the window.
A simple technique for speeding this checking is the bounding box. With each object or set of objects in the hierarchy we associate a description of a rectangular "bounding box" which surrounds all the graphical objects. Given the area of the page we wish to display, we can compare it with the bounding boxes of all paragraphs on the page. Some paragraphs may lie entirely outside the area, and do not need to be considered further. This "bounding box check" is extremely rapid.
2. Identifying a displayed object by pointing to it with a mouse or other coordinate input device. This method of selecting objects for arguments to editing operations is common practice on display-oriented editors (e.g., Bravo, Gypsy). The operation is somewhat similar to the windowing operation: we must discover the nearest object to a given (x,y) coordinate. The bounding box technique permits the identification to be made without examining all objects on the page.
3. Updating a document incrementally. It is possible to design the Press data structure to permit small modifications to be made very easily. Such is the case when, for example, correcting typographical errors in a document. It is essential that random access to distant portions of a document be efficient.
4. Merging documents or copying parts of one document into another. If these sorts of operations are performed frequently, Press can be designed to minimize the computation required. If the file is heavily structured, such copy and merge operations may be difficult, because a lot of structural information may have to be altered.
5. Rearranging large numbers of objects on the page. A page layout or composition system will probably focus on functions for moving substantial chunks of text or drawings on the page. Press can be designed to ease such reorganizations.
6. Letting different editor programs work on one document. Press should permit the structural information for several different document editors to be recorded in the same file. Any editing program will of course be able to display the graphical objects created by others, because the object encoding is standardized to permit printing programs to print the document. However, the program need not understand the structural information associated with objects created by other editors.
This requirement is a key to the flexiblity of Press. Specialized editors or information processors may operate freely on the same document. A fresh idea for editing images can be applied immediately to documents that have been created with other editors, without having to program all sorts of operations for dealing with text. And, significantly, this facility helps provide backward compatibility among versions of editors.
7. Performing all the above operations quickly. The most exacting spped requirement is that of providing adequate feedback to the user, for example to indicate the sections of text or illustrations selected for an editing operation. Speed considerations often influence the placement of information in the file: data required for a particular operation can be accessed most efficiently if it is all in one place. The price for such placement may be to decrease the efficiency of other operations or to add redundant data.
8. Scavenging the file. Any data structure that is incrementally updated runs a risk of being permanently destroyed by a hardware or software error. If the data structure is designed correctly, it is possible to scavenge the file, rebuilding most mutilated data structures. This consideration arises only when we consider using the Press document format for storage of information critical to a user. (If Press files were designed with only graphical output in mind, and were not intended to be edited, this problem would be insignificant.)
The objectives listed above are by no means easily assimilated into a design that offers optimal solutions to all of the problems. All the requirements can be met, but the cost in efficiency is presently unclear. Only experience and measurement will expose the imbalances in the design.
The Press design
[[[This section, which will describe the Press file design in a tutorial fashion, is yet to be written. See [2].
Font design for Press:
What a character is (little diagram)
Notation
Mimic printing industry
Device independence
Scalable fonts -- like current photo-typesetter practice
Coordinated fonts -- the two algorithms
Common understanding -- widths, shapes
]]]
Design critique
In view of the general considerations governing the Press design, the detailed design presented above may seem somewhat arbitrary. This section explores the various design decisions and comments on their justice. Some of the considerations presented below will bear on any attempt at such a design; others are less important, but serve to explain our decisions.
Trailers. Perhaps the most controversial Press convention is that all descriptive information trails the data to which it refers. This technique, introduced by the EARS printing format, eases the generation of a file on the fly. Thus a simple program to "list" a text file could generate and transmit the Press file without first buffering it on a disk.
We overestimated the importance of the listing function and underestimated the inconvenience of the trailer convention for other sorts of processing. An editor program must read the document directory first (the last record), then the part directory (usually the last record but one) and the font directory (usually the record before the part directory), all near the end of the file. If the file is allocated on a disk in such a way that reading forward is fast (i.e., successive pages of the file occur at consecutively numbered sectors around the disk), this "reading backwards" operation is extremely slow because an entire disk revolution is required in order to read each record. Similarly, the entities must be read backwards, starting with the last one on each page, in search of the first one.
We also failed to recognize that the trailer convention would preclude any preprocessing by a printing program as it receives a file over a communications device. It appears that on-the-fly encoding and on-the-fly decoding are mutually exclusive. The possibility of high performance printing far outweighs a small convenience for "listing" functions.
Since Press was designed, added experience with the EARS format has further questioned the wisdom of the trailer philosophy. Although Bravo currently sends files to EARS on-the-fly, it is becoming apparent that two passes over the text file would ease certain sticky formatting problems. Additionally, Bravo generates its output so slowly that it needlessly ties up EARS during the transmission. If the file were first composed on the disk, the transmission would then be substantially faster and could furthermore be carried out as a background to other editing tasks, being completed when the printing facility was next free.
The key to rectifying this problem is to note that the unit of encoding and decoding need not be the entire document, but can be the page. Thus we can require a "listing" program to buffer each page, so that the "printing" program may decode the page on the fly.
The serious inconvenience of trailers is one of the primary motivations for redesigning the Press format.
The Data List and the Entity List. We chose initially to separate "data" and "formatting information." This choice was supported by several arguments:
1. The design followed experience with formatting in Bravo and Gypsy, which recorded all formatting information for a paragraph at its end (an alternative is to use escape sequences mixed in with the text to record format changes). The separation left the text of the paragraph unencumbered by extraneous characters which would have to be skipped when search or substitute functions were invoked. It also simplifies skipping over formatting information when only the text is of interest (e.g., when compiling a program).
The "run-coding" of format in the EL commands was also borrowed from Gypsy. The intent is that the EL contains all the formatting information that the user has provided (i.e., the "looks" applied to the text).
2. We anticipated that simple formatting programs could copy their ASCII input verbatim into the DL as they generated the EL in core. This is not a great advantage, as each input character must be examined in any case.
3. Some kinds of global re-formatting (such as making a two-up version of a document) would not require changing information in the DL. [This is not presently true, because objects and dots do not have this property.]
4. We anticipated that some editors might want to keep virtually all of the formatting information in core, but page the data because it might be large. Markup found this to be a very effective technique. A similar consideration applies to generating displays of only part of a page: by keeping the entity control information compact, a quick scan can be made to find those entities whose bounding boxes indicate they must be displayed.
5. Separation generally improves the robustness of the file. If the formatting information (which we view as rather fragile) should become damaged, the text, objects and dots are still likely to be intact. [The DL cannot at present be scavenged because objects and dots are not preceded by an identifiable code.]
However, there are problems with the DL/EL distinction:
1. As the design progressed, we had trouble deciding whether certain information should be included in the DL or in the EL. This problem is exemplified most clearly by <show-rectangle>: its arguments all lie in the EL because its anticipated use was for solving a formatting problem (underlines). However, the exact same effect is achievable with a <show-object> and some DL data that describe a rectangle.
2. For certain applications, the separation of format and data is simply a nuisance. A program that needs to make only one pass over the Press file (e.g., a printing program) derives no benefit from the separation, but is required to manage two separate pointers into the file being read.
3. If a program wishes to check exhaustively the consistency of pointers into the DL and the EL commands, there are a large number of checks to make. This is a consequence of the separation.
Entities. Entities (and to a far lesser extent, pages) are the only structural concepts in Press. Although other structural information can be recorded as "control information," it cannot be shared reasonably among several editing programs.
What user concepts are analogous to entities? Is a paragraph an entity? What about an illustration, which may contain text passages and graphical information? It might seem natural to consider an entity very similar to a paragraph. It cannot be exactly a paragraph, because paragraphs are sometimes split across pages; an entity appears on a single page.
This problem is not restricted to paragraphs. Words are occasionally broken at line boundaries. The trouble is that two sets of concepts are at work: a formatting set, which speaks of pages, lines and characters; and a content set, which speaks of paragraphs, sentences, words and characters.
The choice of the entity as the single structural component on a page was influenced by experience with display file designs in computer graphics. The entity corresponds to a segment in a segmented display file [3]. This sort of design is generally accepted as the simplest that is adequate for interactive applications that require rapid updates to a display.
Using only one structural component simplifies other parts of the design. The entity type, for example, serves to identify the editing program that has created the entity and can correctly interpret the control information and make modifications to it. If an entity could "point" to other structural objects, we might have to identify those as well, and to worry about how conflicts are resolved (e.g., a line owned by A and one by B contained in a paragraph owned by C).
At least one level of structure is required to aid moving collections of objects. Because all coordinates recorded in an entity command list are relative to Xe and Ye, an entire entity can be moved by changing these two numbers (and the bounding box).
Coordinate system. The choice of micas as the unit of measure has worked well. However, Press cannot describe really big documents, because 215 micas is only 32 cm. An alternative is to represent coordinates with 16 bits of precision, but to have an additional scale factor that relates these numbers to physical coordinates or to provide extended precision (e.g., 32 bits) for Xe and Ye. The price of such a scheme might be quite high.
Objects. The <show-object> directive points to only one object, largely so that color information can be changed from object to object. We chose not to include color changes in both the DL and EL for this purpose. [Of course, certain kinds of images effectively contain color change information in the DL!]
Rectangles. We added rectangles as a special case of objects because (1) we thought they would be very common, and deserved a simple encoding, and (2) we envisioned printing devices capable of generating vertical and horizontal rules although incapable of generating arbitrary objects. Without the separate encoding, a program must examine an object carefully to discover whether it really is a rectangle.
Rectangles were also intended for underlining words. However, they are not quite correct: there is no easy way to tell which words are actually underlined (one must calculate widths of characters in words and compare to the rectangle dimensions). Thus, unlike font change information, the appearance of a character or word is not clearly encoded in the EL.
Images. Although our experience with images in Press files is somewhat limited, it is clear that the present design cannot accommodate the subtleties of images. For example, in order to reproduce an image correctly, we need to associate with its encoding some information about the sampling technique used to generate the data. As a crude example, a scan on 1 mil centers with a 1 mil spot is currently indistinguishable from a scan on 1 mil centers with a 2 mil spot.
Characters. The view of a character code as shorthand for a geometric object has generally worked well. A key contribution to device independence is offered by naming fonts, and letting the particular devices decide how best to display each request. Printing devices may therefore need a substantial file of fonts.
The file is not large compared to the amount of data needed to represent scanned documents. One way to think about font storage is to envision a "font book" which has a single example of every character, printed closely spaced on several pages. The amount of file storage required to save these characters is then roughly the same amount required to scan in the font book and to store it as a scanned document. (This way of thinking about the problem automatically includes effects of resolution or compression differences among printing devices.)
Breaking the address space for characters into three parts (font set, font, character) is advantageous. We can merge (or append) two Press documents simply by re-assigning font sets to the second document so that they do not conflict with font sets used in the first document. It is thus unnecessary to parse the EL commands and change individual <set-font> commands. The price for this flexibility is that duplicate entries in the font directory are common, and the printing or reading program must detect sharing of common fonts in order to avoid inefficiencies in its processing. Neither is very hard.
The design of the font directory is too general. Originally, we anticipated that best compaction of the Press file would be achieved by "filling up" fonts with all 256 codes so that very few <set-font> commands would be required and so that all 8 bits of a character code were used effectively. However, achieving this compaction was enough trouble that it was overshadowed by other considerations:
- The fonts and associated <set-font> EL commands were seen as a way of directly recording the "looks" applied to the text. Thus the EL reveals the format changes in the text. If a user italicizes a word, the editor need only add some <set-font>s to the EL; if characters were packed in, we might have to map each character code of the word separately, and then perhaps introduce <set-fonts>s in strange places if we run over the 256 code limit.
- Packing characters into the 256 code space makes certain "parsing" operations very hard. Examples are: search, substitute, spelling correction, compilation, etc.
The generality of the font directory (especially the source field and the ability to have several entries apply to a single font) makes detecting exact sharing very difficult.
The ability to specify the shapes of characters in the font directory is, however, essential. It allows individual users to design and print their own special characters. It also allows a Press file to be transmitted to a site that does not have a certain font on file.
"Formatting" characters. Press specifically excludes interpreting any "formatting" characters in the ASCII character set. Tab, carriage return and line feed have no special meaning, partly because they violate the concept of the character code as shorthand for a graphical object, and partly because their interpretation is nearly impossible when combined with rotation. How does one deal with tabs or carriage returns when the "font" they are in has a rotation of 32 degrees? [Of course, we could devise an interpretation, but it would be very complex.]
Widths. It should be evident from the encoding of the EL that an understanding of character widths that is common to all readers and writers of Press files is essential. Presently, this information is distributed in a common "widths data base." Unfortunately, this technique offers substantial occasion for trouble: if a new version of a font with altered widths is created, how are Press files written with old widths to be interpreted? (Note that small modifications to the shape of characters are far less critical, as they do not alter the appearance of the page except where they appear. Width errors, however, can accumulate along a line.)
- One possibility is to include, in the font directory, a list of the font widths actually used, so that any reader will have the same understanding.
- We could include a "version number" that tells what version of the widths was used for each font. This would require a printer to save several old versions.
Overlap. Although we have had very little experience with Press editors that make active use of the overlap resolution, it appears that the Press design goes to greater lengths to solve this problem than is necessary. Most pages have no overlap problem at all because either (1) all objects are one color (black), in which case overlap ambiguities do not change the appearance of the page, or (2) no two objects on the page overlap.
Press should probably flag only those pages and/or entities where overlap ambiguities occur. Although the present SLOT/3100 printing software is very simple using the present arrangement, some high performance printing systems may be able to process more efficiently pages without overlap ambiguities.
Compaction. The current design of Press does not emphasize compaction, but rather convenience in the construction of editing programs. This is a reflection of our belief that Press be simple enough to encourage programmers to adopt it.
Even should compaction become a major goal, it should be pursued carefully. For example, one might be tempted to permit "graphical subroutines" to be defined: once a collection of objects (say, for displaying the "private data" stamp at the top of each page) is specified, further uses of the same collection can simply refer to the original and say: do that! Unfortunately, this technique has broad and troubling implications:
- Is the subroutine a literal constant, or can it have "arguments," such as the position on the page, or...
- When a human chooses to edit an image created by the subroutine, is he editing the subroutine or the instance?
Things we missed. Several objectives that we felt important were not adequately met by the Press design:
1. References to other files are clumsy and weak. A more generally applicable mechanism is required, which can refer to all sort of objects (not just dots) and to various pages of the external Press file. Thus a customer could have a Press file that is the current set of forms in use in the organization. Press files that represent filled out forms need only refer to pages in the forms file to find descriptions of how to print the form itself.
2. Lexical "parsing" of Press files. It would be nice if Press files could be read as a text stream by, say, a compiler. This facility is clearly required of any standard, and would have certain side benefits (illustrating programs). At present, there are no conventions about the ordering of characters in the DL or of entities on the page.
3. Press cannot "label" a particular object in the file. Labels are useful for establishing cross-references between files. A special case is the cross-reference to a standard name: one could label the "author" or "abstract" of a document (or the "net pay" field of a form), so that programs that wished to extract such things from the document could do so.
4. Press cannot represent texture. Although the "intensity" setting may cause a spatial half-tone pattern to be generated, the file cannot express other repetitious patterns. This omission could be remedied with a "texture directory," similar in philosophy to the font directory, that establishes correspondances between known texture types and internal texture numbers. These numbers can then be used to specify textures much the way the intensity numbers are used to specify gray tones.
History
Press is a result of research on Illustrators, programs designed to permit users to add illustrations to documents. Early in 1974, the graphics interests of the Systems Sciences Laboratory and of the Computer Sciences Laboratory were merged into a single "graphics group" to work on this problem.
The group first designed PICO, a graphics subroutine package capable of generating displays on video terminals. This design explored problems involved in scan conversion of objects specified by outlines, in ways of specifying how to handle overlapping objects, etc. This effort supported our first illustrator, TAPE, constructed in Fall, 1974. TAPE uncovered the lack of adequate facilities for printing graphical information on hard copies, and for representing illustrations in files.
Several interim solutions were devised, various file formats proliferated, and valiant attempts were made to print illustrations using printing devices and software systems totally unsuited to the task.
Plans to acquire several SLOT/3100 devices provided a cue to the graphics group: we volunteered to provide software for operating these devices that would, for the first time, accomodate graphical information in a reasonable way. Press began as an effort to encode the textual, graphical and imaginal content of a document in a file for printing. We soon realized that clever design would also permit the file to be edited; it could thus be the representation of the document.
The first Press design, completed in February 1975, prompted a number of activities designed to test out our ideas. In order the provide an interim facility for printing Press files, the EPRESS program was written for transforming Press files into a form suitable for printing on the SLOT/7000. Although this program did not correctly print all sorts of objects that could appear in a document, it was an invaluable tool for testing Press and for fostering its use. The first dramatic impact connected with Press was the development of the Markup program. This program, which creates and modifies illustrations using a very simple but powerful command language, was in part inspired by the Press format: at last, storing an illustration with its accompanying text was straightforward!
The Press design reflects experience extracted from previous hard-copy systems. The EARS system (a SLOT/7000 driven by an Alto attached to the Ethernet) greatly influenced the design: the "trailer" organization is a direct result of considerations thought important when EARS was designed. EARS was itself designed to cure problems with a previous hard copy facility, XPRINT. XPRINT printed files on an XGP from ASCII text input files, formatting the file in a pleasing manner. As ambitions grew, special character sequences were used to specify more precise formatting. Unfortunately, not all formatting decisions made by XPRINT could be controlled from the input file. This led to endless requests for special formatting features in XPRINT. Both EARS and Press therefore, do no automatic formatting.
Other key ingredients of the Press design originated in the field of interactive computer graphics. Experience with software for creating display files for computer displays, and more recently with design of device-independent drivers, is a source of many of the techniques. Emergence of raster-scan displays has prompted work on scan conversion and on hidden-surface elimination, also sources of ideas for Press.
Xerox launched a project to develop a standard for electronic representation of documents, the XIP code, based largely upon techniques for encoding imaginal information. PARC’s concern for editing and manipulating documents, rather than for copying them, makes much of the XIP code philosophy invalid. We believe that Press offers more promise as a standard document representation, even though a good deal of computation is required in order to produce hard copies.
Present uses of Press
The impact of Press is perhaps best assessed by studying some of the uses to which it has been put. The following list simply refers to other documentation:
1. Cypress [9]. A group at PARC is currently constructing an Alto user program to aid the design and layout of pages for publishing. This sytem is in part an extension of the Gypsy system in use by Ginn, and in part an effort to integrate into one system the various text editing, formatting and illustrating techniques currently available.
2. Markup [8]. This program is an illustrator that operates on Press files. It explores the use of the Alto screen as the only representation of an illustration: the illustration is simply a collection of black bits. The user makes illustrations with "brushes" controlled by the mouse: the brushes follow either free-form or straight-line paths. To experiment with images, a halftone technique was applied to images digitized from a television camera.
3. Press printing software for the SLOT/3100 [10]. This software, constructed but not yet fully operational, is a complete implementation of a Press printing facility. The equipment that comprises the facility is a Xerox 3100 copier fitted with a SLOT head constructed by EOS capable of scanning at resolutions up to 500 dots/inch., an Alto copmputer and a large Trident T80 disk (capacity 80 Mbytes). Although the software currently does not include the best known algorithms for certain operations (e.g., resolution conversion of images), the program is designed so that new techniques can be tried out easily.
Plans
At the time of writing, Press is being redesigned to correct certain flaws uncovered during the design of Cypress.
When both Cypress and the SLOT/3100 facilities are fully operational, we shall be concerned with measuring various apsects of the Press design. In addition to improving the performance of the software for editing and printing Press files, we would like to gather information that might suggest ways Press could be improved.
A great deal of experience with the design is needed before Press can be adopted as a serious standard.
References
[1] "The OIS Architectural Concepts," April 15, 1975. (Release 1; revision 0; H. Lazar, supervisor).
[2] R.F. Sproull and W.M. Newman, "Press file format for SLOT/3100," Xerox PARC Internal Memo, 15 June 1975 (CSL archive no. 5GR-015) [Detailed description of the Press file format.]
[3] W.M. Newman and R.F. Sproull, Principles of Interactive Computer Graphics, McGraw-Hill Book Co., New York, 1973. [A general text dealing with computer graphics.]
[4] I.E. Sutherland, R.F. Sproull and R.A. Schumacker, "A Characterization of Ten Hidden-Surface Algorithms," ACM Computing Surveys, 6, 1, pp. 1-55 (March 1974). [A tutorial description of several hidden-surface algorithms.]
[5] R.F. Sproull and W.M. Newman, "The design of gray-scale graphics software," Proceedings, Computer Graphics, Pattern Recognition and Data Structures Conference, May 1975. [This public paper describes PICO.]
[6] W.M. Newman and R.F. Sproull, "PICO Manual," Xerox PARC Internal Memo, July 1974 (CSL archive no. 4GR-015) [Programming manual for PICO, a graphics package for generating color and/or gray-scale video displays.]
[7] P. Baudelaire, R.M. Flegal, and R.F. Sproull, "Spline Curve Technologies," forthcoming Xerox PARC Internal Memo.
[8] W.M. Newman, "Markup," Xerox PARC Internal Memo, June 17,1975.
[9] W.M. Newman, "A Command Language," Xerox PARC Internal Memo, October 10, 1975.
[10] R.F. Sproull, "Press Printing Internals," forthcoming Xerox PARC Internal Memo.