Internal Memo

XEROX
	From
	Michael Plass <Plass.pa>
	Ken Pier <Pier.pa>
	PARC/CSL





Subject	Date
Research Interpress Architecture	December 18, 1985


Filed as ResearchInterpressArchitecture.tioga
Last edited by Michael Plass, December 18, 1985 9:19:27 am PST
Abstract: Research Interpress [8] is a version of Interpress that is intended to be a testbed for new concepts and facilities before they are incorporated into the corporate Xerox Interpress Standard.  This document is an overview of the architecture of the PARC/CSL implementation of Research Interpress.
Attributes: draft, technical, Cedar, Interpress, imaging
Introduction
Interpress began as a research effort within the Computing Sciences Laboratory at PARC.  Interpress finds its roots in a number of earlier systems developed at PARC.  One of these is Press [7].  Another source of the ideas came from the combination of JaM (a simple interpreted postfix language) [1] together with a graphics package (initially JaMGraphics, later CedarGraphics) that utilized essentially the same imaging model as Interpress [9].  The experience gained in implementing these prototypes was applied to the development of a specification for printable documents.  The result of these research efforts has come to be called Research Interpress, from which portions have been selected and established as a Xerox Standard.  The first such corporate standard was Interpress 82, followed by Interpress 2.0 and Interpress 2.1, and recently Interpress 3.0.  In parallel with these standardization activities and implementations of the standard by product organizations, a small group within PARC/CSL has been developing and refining an implementation of Research Interpress in the Cedar programming environment.
There are several reasons for doing this implementation.  One is to check out the soundness of the new ideas in Research Interpress before they are incorporated into a standard.  Another is to explore techniques for structuring the resulting somewhat large system.  As a running system, it provides a useful service within Xerox wherever the appropriate environment can be installed.  And finally, it is a prime candidate for technology transfer into product organizations, either in its entirety with suitable modifications to allow for the differing environments, or in part where it contains pieces that can be profitably incorporated into product implementations.
The version of Interpress associated with the current Cedar release (Cedar6.0) is complete in all of the imaging aspects and most of the base language aspects of Interpress.  We have recently installed our implementation as a prototype Interpress 3.0 server as well.  This document deals with the Cedar 6.0 version.
Although the CSL Interpress implementation is written in Cedar, it has been written with an eye towards the possibility of porting it into Mesa.  Some of the issues involved are discussed in the appendix.
The Interpress/Imager relationship
The imaging operations detailed in Chapter 4 of the Interpress standard are useful in a wider context than Interpress.  To capitalize on this, we have built the implementation of these operations as a separate graphics package, called the Imager.  Although the Imager is in some ways a descendant of CedarGraphics, an earlier graphics package for Cedar, it was built from scratch and has a significantly different internal structure.  In Cedar6.0, the Imager is the basic graphics package, through which all display screen refresh takes place.  The same interface can be used to draw on gray-scale or color displays, or to produce Interpress masters or PD files (a printer-dependent format file similar to bandlists) for a variety of different printers.  The Interpress interpreter uses the Imager to perform all of its imaging operations; consequently an Interpress master may be displayed on any of the devices supported by the Imager with equal ease.  Similarly, programs that use the Imager can produce output directly on the screen or into an Interpress master, using the same composition code.  Programs may also call on the interpreter to render a fragment of Interpress into an Imager context; this is useful for displaying Interpress fragments embedded in editable document, for example.
The Interpress Interpreter
The Interpreter's job is to accept an Interpress master, and to make the appropriate calls on the Imager to render the pages described in the master.  The Interpreter is built to deal directly with the Xerox encoding of Interpress; separate utilities may be used to translate to and from the written encoding.  (This is in contrast with our earlier implementations, which had a level of abstraction that allowed the Interpreter to work directly from either representation; it seemed this extra layer was not worth the added runtime overhead.)  
Following is a catalog of Cedar interfaces which comprise the programmed capabilities of the Interpreter package.  The code for these interfaces may be accessed via the package descriptor file on /Cedar/CedarChest6.0/Top/Interpress.df.  Public interfaces are the only ones that a client (i.e. application program) needs; private interfaces are internal to the implementation of the Interpreter.
Public interfaces
IPMaster
Contains type definitions for the various data structures that occur in an Interpress master, plus operations for reading and writing Xerox-encoded masters at the token level.  At this level, the readers and writers consist of simply a STREAM, with no additional state information.
Interpress
This small interface contains the definition of a handle on an Interpress master open for reading, plus operations for rendering a given page into an Imager context.  This small set should serve quite nicely for many applications, but this is a logical place to add public access to such things as printing instructions, etc.
ImagerInterpress
This small interface contains the definition of a handle on an Interpress master open for writing, plus operations for rendering a given page into an Imager context and thence to the open Master.  Included are procedures to put fonts, colors, and pixel arrays into the Master preamble.
ImagerInterpressBackdoor
This interface provides a procedure for getting an Imager context that corresponds to an Interpress master open for writing.  Clients can then cause new pages to be started and objects to be rendered into the Master using Imager operations on that context.
Private interfaces
IPInterpreter
Types and operations for the Interpress interpreter, including the top level object which represents a particular instance of Interpress state.  Interpress Values are represented using Cedar's REF ANY construct (see appendix); the Interpreter uses runtime discrimination to determine the type of a given Value.  This interface contains the type definitions for all the valid referents, as well as the type for the state record of the Interpress machine.  It also contains procedures for creating, converting, and operating on Values, and access to the facilities of the Interpress machine, such as the stack and current frame.
Particularly interesting is the definition of the Vector type; this is defined in the object style, so that different implementations can be underneath various flavors of Vector; for instance, the vector of operators constituting a font, the result of MAKEVEC, and all of the various compact encodings used in a Master may be represented in this fashion.  There is also a type field provided in the class, so various operators can implement accelerators for the most common cases.  This same object style is used for operators, as well as in other places in the Interpreter and the Imager.
IPBase, IPImage
The procedure calls for causing the Interpress machine to apply primitive operators to an Interpress state.  The implementations of these procedures are quite simple, for example:
ApplyADD: PUBLIC PROC[self: IPInterpreter.Ref] = {
b: REAL ~ IPInterpreter.PopReal[self];
a: REAL ~ IPInterpreter.PopReal[self];
IPInterpreter.PushReal[self, a+b];
};
(They are not all quite this simple, but there is nothing too complicated going on.)  The Apply* procedures for the base language are in IPBase , and those that deal with the imaging operators are in IPImage.
IPImager
Procedures for converting between Imager representations of fonts, colors, color operators, and pixel arrays to corresponding Interpress Vectors and Operators.  Also contains the Interpress text operators Show and ShowAndXRel.
IPReal
Some basic real arithmetic operations.
The Imager
Public interfaces are the only ones that a client (i.e. application program) needs; private interfaces are internal to the implementation of the Interpreter.
Public interfaces
Vector2
Two-dimensional vector type (VEC: TYPE ~ RECORD[x, y: REAL]) and operations on VECs.  Vector2 is used by many Imager interfaces.
FunctionCache
A utility module which implements a general caching mechanism.  The module provides a facility for writing cached implementations of REF-valued functions. The caches are managed with a move-to-front discipline, and trimmed according to the client supplied limits on the total number of entries or the total number of words consumed.
ImagerTransformation
The Transformation type and operations.  This module contains procedures for creating, copying, combining, and modifying transformations.  Transformations are two-dimensional affine transformations represented as a 3 by 3 matrix:
		[ a  d  0 ]
		[ b  e  0 ]
		[ c  f  1 ]
As far as the Interpreter is concerned, Transformations are considered to be immutable, as are all Interpress Values.  However, the Imager allows clients to treat Transformations as mutable when this is desirable to avoid excessive storage allocations.  The representation of Transformations contains some extra information to speed recognition of special cases; the 3 by 3 matrix is always the truth.
ImagerPath
Deals with the representation of outlines and trajectories.  The Imager interface uses a callback mechanism as the basic means of communicating these entities between parts of the system, and the relevant procedure types are defined here.  A callback mechanism simply means that the client program calls procedures in the Imager which take as a parameter a second client procedure to be "called back" when the Imager is prepared.  The Imager sets up the environment in which the callback procedure will be executed. Also provided are some explicit representations, primarily for use by the Interpress interpreter and for other clients where the callback mechanism is not the most natural.
ImagerFont
The definition of the Font type and operations on it.  The operations are largely just for accessing the metric information, since the public Show procedures are provided in the Imager interface (see below).  A font is object-oriented, so that new kinds of font definitions can be added at will.  The mechanism for doing this is not exposed in the public interface.  The font implementation record contains tables for the metrics, corresponding to those in ImagerFont, plus one procedure, MaskChar, to apply the mask of a given character to a given Imager context.  The simplest kind of Imager device implementation might implement Show just by drawing each character through this mechanism, but in most cases the device implementation is expected to call MaskChar just once per character, and cache the results in a format appropriate to the device, usually a bitmap at device resolution.  This is also where any device-specific font tuning may take place; we'll examine this some more later on.  Note that the context passed to MaskChar is generally not the same one the client passed to the call to Show, but is a special one designed to capture the image in memory so that it can be cached.
The Font record, like most of the Imager data types, contains a property list.  This is so new fields and operations may be added without having to change the interface.
The font interface is designed to use 16-bit character codes.  It is desirable to decouple the particular string representation from the rest of the Imager; for example a composition system might have its own internal representation for a string of 16-bit characters, different from the string-body encoding standard, which is, after all, designed for interchange purposes.  In all the operations that require a string of characters (StringWidth or StringBoundingBox, for example), a two-level callback mechanism is used; the client calls the package, supplying a StringProc; the package calls the client-supplied StringProc, passing it a charAction procedure, which the client, in turn, calls once for each character.  This mechanism is a little confusing at first, but works out to be a very handy way to hook a system together, without having to use a common format or allocate extra memory just for changing representations.  The same style is used to pass other complicated entities to the Imager, such as outlines for MaskFill.  In all of these cases, convenience procedures are also supplied for what are expected to be the most common representations, so most clients will not need to worry about the general mechanism.
ImagerPixelArrayDefs and ImagerPixelArray
Defines the type corresponding with the Interpress PixelArray type, and procedures for creating and accessing pixel arrays.  This, again, is object-oriented, so many different implementations can hide behind this interface.  The public interface just provides procedures for creating PixelArrays from a variety of sources, plus the Extract and Join operations.  Refer to Sampling and Halftoning, below, for a description of how the Imager uses PixelArrays.
ImagerColorDefs and ImagerColor
Defines the type corresponding to the Interpress Color type.  There are two basic kinds of color: constant and sampled.  Sampled colors follow the pattern described in the Interpress standard quite literally, consisting of a PixelArray, a Transformation, and a ColorOperator.  Constant colors are more complicated than they appear at first thought, the complication arising largely from the desire to support full color, not just shades of gray.  Since no real device to date can render the full color gamut, it is important to try to capture the client's intent, not just the ideal color.  Just what this specification should look like is still a matter for research.
In addition, there is the desire to be able to specify colors in a somewhat device-dependent way; for example, to generate check-plots for VLSI on a full-color plotter it is handy to be able to use colors that mix where they overlap, just by putting toners down on top of each other.  For this type of application it seems sufficient to supply a collection of named colors, e.g. Xerox/.../VLSI/Metal-1, which will make it feasible to provide alternative schemes for other devices, for example stipple patterns on black-and-white printers.
Another type of special constant color is ImagerBackdoor.invert, which is handy for interaction on displays, but which is not supported on all devices.
Imager
This is the main client interface.  Aside from the procedures for access to the imager variables, the operations in this interface are all "one-way," that is, the information flow is strictly from the client to the Imager package.  This makes it possible to provide a "stateless" implementation, that is, one that does not need to maintain the values of the imager variables.  Such an implementation may merely translate the Imager calls into an Interpress master, written as a stream.  To make this possible, while still preserving the full power of the imaging model, there are some procedures supplied that will generate some state-accessing Interpress code when used for creating a master.  In this category are SetSampledColor and SetSampledBlack, which set a sampled color relative to the current transformation.  The other one is DontCorrect, which is useful in contexts where it is necessary to save and restore the correctPass imager variable.
For operations that, in Interpress, take a body, the Imager uses a simple callback mechanism.  The procedures that do this are DoSave, DoSaveAll, Correct, and DontCorrect.  The callback procedures are parameterless, and, in the case of Correct, may be called more than once.  Because they are parameterless, callback procedures will be defined as local to a client's procedure, so they can access the variables of that procedure; in particular, they will need access to the context itself in order to be able to draw anything!  This does not restrict the power of the construct, since it is possible for the client to have its own DoSave that uses an action procedure with parameters, written using just the parameterless mechanism provided.  In most circumstances, though, using a local callback procedure is most straightforward.
The remainder of the Imager interface simply provides the imaging operations described in chapter 4 of the Interpress standard, as supplemented by the extension strategy.  Procedures include translation, rotation, and scaling of imaging contexts, showing characters and strings, all the mask and clipping operations, and setting colors and stroke parameters.
ImagerSample
Defines the notion of a sample buffer and provides procedures for creating, reading, and writing samples.  Samples represent a set of values which correpsond to pixel values for a raster device.  For example, a sample for a color display would likely consist of a triple of values named red, green, blue.
Also provides the Sampler type, which contains the state needed to sample an array of samples trhough an arbitrary transformation, as well as the sampling primitives GetPointSamples, and GetInterpolatedSamples.  GetPointSamples uses undersampling, for use when speed is more important than high image quality, or where the image is not known to contain high spatial-frequency images that might lead to aliasing.  GetInterpolatedSamples interpolates a value from neightboring pixels, and is appropriate when the output resolution is higher than the input resolution and the sample values can be combined linearly in a meaningful way.
ImagerColorOperator
Provides operations on ColorOperators and mapping back and forth among samples, pixels, and colors as a function of a ColorOperator.  Six color model operators are defined: black, gray linear, gray density, gray visual, RGB linear, and color mapping.
ImagerBackdoor
Low level interface for clients to read and write context state.  Not all devices implement Backdoor, and to be strictly device independent clients should not use Backdoor.  Also includes MakeStipple, for converting small stipple patterns to Colors.
ImagerTerminal
A low level interface for supplying clients with Imager contexts corresponding to the current black and white or color terminals.
ImagerColorMap and ImagerDitherContext
Two mid-level interfaces for maintaining the color map on the color display device.  Its purpose is primarily to provide synchonization between the various clients that modify and use the color map, and to hold extra information about the color map.  Provides for setting up standard color maps, client color maps, and gamma correction.
ImagerOps
A miscellaneous low-level interface for manipulating PixelMaps and creating PixelMaps from other kinds of pixel storage such as contexts and frame buffers.
Private interfaces
Following is a list and very brief comment on each of the Imager private interfaces.  Private interfaces are internal to the implementation of the Imager and should not be needed by clients.
ImagerTypeface and ImagerTypefaceExtras
Defines a private typeface object for use in implementing ImagerFont operations.
ImagerFontPrivate
Private specification of font object representation.
ImagerPixelArrayPrivate
Private specification of pixel array object representation.
ImagerColorPrivate
Private specification of color object representations.
ImagerColorOperatorPrivate
Private specification of color operator object representations.
ImagerPrivate
Private specification of imager state object representation.
ImagerState
Private specification of imager state operators.
ImmutablePropList
Utility interface that implements immutable, sharable property lists.
AISFileFormat
Definitions of record types needed to parse AIS files.
StrikeFontFormat
Definitions of record types needed to parse strike format fonts.
PrePressFontFormat
Definitions of record types and procedures needed to parse PrePress format fonts.
ImagerPixelMap
A PixelMap describes a window into a buffer, and the buffer itself may be positioned anywhere in a global device space.  The windowing information is stored in the PixelMap record, so that it may be easily changed to accomplish translation and clipping by rectangles.  The translation feature may be used for destination maps to conveniently implement band buffers.  This interface provides most of the functionality of BitBlt, without the attendant risks of smashing the world.  This is one private interface that could be exported for client use.
ImagerManhattan and ImagerManhattanExtras
A Manhattan polygon which may be described as a collection of non-overlapping rectangles.  ImagerManhattan provides objects and procedures for creating and operating on Manhattan polygons, including creation, copy, union, intersection, difference of polygons.  This package can be useful in creating complex clipping boundaries for Imager contexts.
ImagerScanConverter and ImagerScanConverterPrivate
The basic module for scan converting from paths to pixels or runs of pixels.
ImagerStroke
Basic routines for producing the outline of a stroke given a path for the stroke centerline.
ImagerDevice
Defines the class and instance types for representing Imager logical devices.
ImagerRaster
Procedures for creating new Imager devices from client definition.  Predefines devices for the black and white terminal and color terminal in color map and full color modes.
ImagerRasterPrivate
Private definitions for use in implementing raster devices.
ImagerDither, ImagerDitheredDevice, ImagerDitheredDevicePrivate
Definitions and procedures for implementing a dithering type display device.
ImagerBitmapDevicePrivate
Definition of the object record for a Bitmap Device.
ImagerColor24DevicePrivate
Definition of the object record for a full color Device.
ImagerFastShow
Optimization for displaying a pixel map via an Imager context.
ImagerMask
Procedures to convert masks, bitmaps, and rectangles to run groups
ImagerCache
A simple caching mechanism for caching font bitmaps.
ImagerBox
A utility for dealing with bounding and intersecting boxes
ImagerBrick
Types and procedures for defining halftone "bricks", based on the work of Thomas Holladay [2].  Bricks are used for halftoning by the Imager devices.
Imager device implementations
The Imager interface is object-oriented, and so may have any number of different implementations behind it.  For example, the implementation that knows how to write Interpress masters shares very little with other device implementations, and has its own set of procedures in the device class record.  This is also the case for other devices that merely record the sequence of calls, for subsequent screen refresh, for example.  Most other device implementations will want to share the mechanism for maintaining the imager variables.  The raster devices, including the PD file writer, share even more in common.  This sharing is accomplished in two ways: one way is to make the common parts into modules that the various devices can call on as appropriate; this collection of modules may be called the implementor's Toolkit, and pieces of this may well be useful for other clients as well.  The other way to accomplish the sharing is again to use a classing mechanism.  This is done for the raster devices (displays, sampled-image creators, and PD files).  This class turns out to need relatively few operations in it.  Note that any particular Imager device still has the option of intercepting calls through the Imager class record, making it easy to put in accelerators for frequent cases without doing serious harm to the overall structure.
Imager Implementor's Toolkit
This section describes the various modules in the "toolkit."  These modules are provided for the convenience of the device implementations, although the implementations are not obligated in any way to make use of them.
Pixel Maps
The best way to think about this package is as a safe interface to BITBLT.  The PixelMap type describes a rectangular portion of a two-dimensional array of pixels, upon which various operations may be performed.  In addition to exposing the capability of BITBLT without the dangers of smashing memory, the interface provides some other useful operations, such as tiling with a brick of arbitrary size and phase shift, and rotations by multiples of ninety degrees.  Interface: ImagerPixelMap.
Filled-area Scan Conversion
The scan converter takes a description of an outline (already transformed to device coordinates), and turns it into a mask at device resolution.  The outline in the current version consists of straight edges and cubic Bezier pieces; conics are reduced to this form before they reach the scan converter, although the scan converter could just as well treat conic pieces directly.  The scan converter works by generating the intersection points of the various pieces with the scan lines, doing a bucket-sort of the points by s (the coordinate in the slow direction) as they are generated.  Then for each scan line, the points are sorted by f and the wrap-number calculations are done.  Where the storage for the buckets would be too large, the problem is subdivided into appropriately-sized swaths and solved one swath at a time.
The intersections with Bezier pieces are found by using the Bezier subdivision rule until the polygon is very flat, and using linear interpolation after that.  This is done separately for each intersection, but since the subdivisions are done in fixed-point, this is not very expensive.  In addition, a conservative number of iterations is predicted in advance, so there is no flatness test in the loop.  A fair amount of logic is devoted to preliminary subdivision of the pieces to assure that they each cross a given scan line at most once, are within the appropriate range for fixed-point arithmetic, and are clipped to the bounds of the device-space properly.  This latter operation must be done carefully, to allow, for instance, a boundary that encloses the whole device space.  The Interpress specifications impose some limits on what needs to be handled, but this scan converter allows input across the full range of floating-point arithmetic.  All of this pre-processing, by the way, doesn't cost much in terms of execution time.
The straight-line edges are handled similarly to the Bezier pieces, except that they don't need to be preprocessed as much, and the intersections are found using Bresenham's algorithm.
The output of the scan-converter can be in one of three forms: it can fill a constant directly into a PixelMap, or it can provide runs using a callback procedure, or it can produce a Manhattan polygon (described below).
There are, of course, many ways to implement a scan converter.  The simplest approach, which has a lot to say for it, is to write a scan converter for polygons, and then reduce everything to polygons at the appropriate resolution.  This was the approach taken in CedarGraphics, for example. The polygons could be rendered using a simplified version of the Imager's scan converter, or by other means.
In CedarGraphics the polygons were reduced to trapezoids with their bases aligned with the fast scan direction.  This was done by a rather subtle plane-sweep algorithm.  It is hard to make this algorithm work correctly in the face of degenerate cases and floating-point roundoff, and the CedarGraphics implementation still had bugs in it.  That is not to say it can't be done, and it is certainly a good approach to take where there is hardware available for rendering trapezoids.  However, care should be taken with the way the trapezoids are represented; if the trapezoids are represented by their corners, and integer coordinates are used, then straight edges of polygons can get turned into edges that wobble a bit, and there may be a gap between abutting polygons.  For laser printers this may not be too serious, since single-bit gaps are often lost in the xerography.  Interface: ImagerScanConverter.
Sampling
This module is used for sampling a SampleBuffer through an arbitrary transformation, and for combining these buffers in various ways.  The strategy for sampled images is to pre-process the sampled color, reducing the amount of data, if required, by averaging adjacent pixels together, to get a version that can comfortably fit into memory.  Note that the color model must be applied first, to put the image into a representation where local averaging makes sense.  It might be argued that this approach throws away too much information, but actually the image should be filtered anyway to remove spatial frequencies near the frequency of the halftone screen, so the low-pass filter is actually quite reasonable for continuous-tone images.  For bi-level images, no halftoning is done, and this scheme will need to be modified.  Two ways of sampling are provided: point sampling for maximum speed, and interpolated sampling, to minimize aliasing. Interface: ImagerSample.
Manhattan Polygons
These are a representation of masks at device resolution as a list of non-overlapping rectangles that satisfy certain invariants.  The module provides boolean operations on these masks, plus some other useful operations.  Manhattan polygons are useful for fancy clipping regions. Interface: ImagerManhattan.
PD Files
A PD file is a file that describes a document in Printer Dependent format [5].  Such files are used for transmitting a document from the Interpreter to the print server, which may be running on  different machines.  The format is general enough to support most raster printers, by varying the appropriate parameters.  The toolkit contains an interface for writing PD files (and, for completeness, a reader as well).  Currently there are two types of PD printers available, one running in the Alto world (which can share a Press server) [6], and the other using a PD interpreter written in Mesa 11 and running on Dicentras (or, in one case, on a Dandelion) [4].
The Cedar package called ImagerPD contains the necessary code for dealing with PD files.  However, except in unusual circumstances, clients should not write PD files, but should write Interpress files instead.
ImagerPD Public interfaces
PDFileFormat
Definitions of record types needed to parse PD files.
PDFileWriter
Procedures for creating a new PD file, starting new images within the file,  and causing images to be rendered into the file.
PDFileReader
Data types and procedures for reading PD files, including opening and closing files and sequentially fetching the elements out of a PD file.
ImagerPD Private interfaces
ImagerPD and ImagerPDPrivate
Definitions of internal PD objects. 
Font Cache
The font cache provides a mechanism for saving frequently-used masks in a device-coordinate representation.  The font cache, in its current implementation, has a working copy in VM, which is checkpointed to disk from time to time.  Experience with PD files seems to indicate that it is reasonable to use VM for the cache, but the interface is designed so this can be changed if necessary.  The device implementations are responsible for creating the masks from the font, and for deciding when to insert a given mask into the cache.  The cache mechanism includes statistics-gathering to keep track of the frequency that each mask is used, and the ability to reorganize the cache to eliminate the least frequently used masks and to put the most-frequently used masks together, to reduce the number of page faults.
The font cache can store masks in one of two forms: one is just as a bitmap, and the other is a simple run-encoding.
Appendix: Cedar vs. Mesa
As mentioned in the introduction, our Interpress implementation is written in Cedar.  Since Cedar is a derivative of Mesa, it is natural to consider the possibility of porting the implementation into Mesa; this section is concerned with some of the issues involved.
The primary feature of Cedar that is not in Mesa is reference-counted, garbage-collected storage.  This is used throughout Interpress and the Imager.  The Cedar type REF is a special long pointer to such collectable storage.  In many cases explicit FREEs could be put in without a great deal of trouble, but where structures are shared, this becomes difficult to do correctly.  A better approach (assuming that Interpress printing is the interesting case) is to take advantage of the limited scope of documents and pages: it is fairly easy to predict, when a given unit of storage is allocated, whether it should persist to the end of the current page, to the end of the current document, or indefinitely.  Thus zones can be used for the management of storage, provided that it is possible to release a whole zone at once.
Another Cedar facility is run-time type discrimination: a REF ANY may be used in a Cedar program to point to an object of any type; before the object can be accessed, it is necessary to NARROW the REF ANY into a REF to the particular type of object.  There are two different styles of using REF ANY; one use, in object-style programming, is simply to point at the class-specific data.  This use is easy to translate, since (barring disaster) the class procedures always know what particular type they are expecting; thus the REF ANY can become a LONG POINTER, and the NARROW can become a LOOPHOLE.  The other use is where the particular type is not known in advance.  The major use of this kind of REF ANY is for the implementation of Interpress Values.  But since the set of types of Interpress Values is static, it is reasonable to define a variant record structure that contains all the possibilities.
A third issue, relating to runtime support rather than the languages, is the use of floating-point arithmetic.  Floating-point is microcoded in all existing Cedar environments, whereas it is done in software in most Mesa environments.  The Imager uses floating-point pervasively, although fixed-point is used in many of the critical loops.  The provision of floating-point hardware or microcode is clearly desirable, but it would be interesting to know how much the use of software support would slow things down.
References
[1] Leo Guibas and Rick Beach, JaM manual
CSL Notebook Entry 85CSLN-0001
[Indigo]<CSL-Notebook>Entries>85CSLN-0001.Press

[2] Thomasi M. Holladay,
An Optimum Algorithm for Halftone Generation for Displays and Hard Copies
Proceedings of the Society for Information Display, Vol. 21 No. 2, 1980.  pages 185-192.

[3] William M. Newman and Robert F. Sproull,
Principles of Interactive Computer Graphics  Second Edition
McGraw-Hill, 1973

[4] Michael F. Plass, Peach PD printers and how to use them.
[indigo]<Peach>Documentation>PeachDoc.press

[5] Ken Pier and Bob Sproull, Printing Device Format.
[Indigo]<PD>Docs>PDFormat.press

[6] Bob Sproull, PD Printer Operation.
(Alto BCPL version) [Indigo]<PD>Docs>PDPrintOps.press

[7] Bob Sproull, William Newman, and Joe Maleson, Press File Format
[Indigo]<PrintingDocs>PressFormat.press

[8] Bob Sproull and Butler Lampson, Full Interpress (Interpress Extension Strategy)
[Indigo]<Interpress>FIP>FIP.press

[9] John Warnock and Douglas K. Wyatt,
A Device Independent Graphics Imaging Model For Use with Raster Devices.
Computer Graphics Vol 16, No. 3  July 1982
[SIGGRAPH 82 proceedings]





FCopyright (C) 1985 by Xerox Corporation.  All rights reserved.
Κv•StyleDef­BeginStyle

(Cedar) AttachStyle

(firstHeadersAfterPage) {0} .cvx .def

(root) "format for root nodes" {
  docStandard
  36 pt topMargin
  36 pt headerMargin
  .5 in footerMargin
  .5 in bottomMargin
  1.75 in leftMargin
  1.5 in rightMargin
  5.25 in lineLength
  24 pt topIndent
  24 pt topLeading
  0 leftIndent
  10 pt rightIndent
  } StyleRule
  
(positionInternalMemoLogo) "Xerox logo: screen" {
  docStandard
  1 pt leading
  1 pt topLeading
  1 pt bottomLeading
  } ScreenRule

(positionInternalMemoLogo) "for Xerox logo" {
  docStandard
  1 pt leading
  1 pt topLeading
  -28 pt bottomLeading
  -1.5 in leftIndent
  } PrintRule

(internalMemoLogo) "Xerox logo: screen" {
  "Logo" family
  18 bp size
  20 pt topLeading
  20 pt bottomLeading
  } ScreenRule

(internalMemoLogo) "for Xerox logo" {
  "Logo" family
  18 pt size
  12 pt leading
  -28 pt topLeading
  36 pt bottomLeading
  -1.5 in leftIndent
  } PrintRule

(memoHead) "for the To, From, Subject nodes at front of memos" {
  docStandard
  AlternateFontFamily
  240 pt tabStops
  } StyleRule

EndStyle˜
blockš
Ρbox
˜
Icodeš
œ>™>—Ipositioninternalmemologo˜Iinternalmemologoš
œ˜
memoheadšœ
Οs˜OšΟt
œ˜Oš
œ˜Oš
œ	˜	O˜O˜O˜O˜O˜—šžœ
ž˜Oš
œ2˜2O˜O˜—Iabstractšžœ
ž0œ
žœ/˜lPš	ž	Ÿ
œΠrt
œβ
Οkœ
‘œ'˜±Pšžœ-˜8
head˜KšœΎ
 
œjŸ
œ
Ÿ
œ£˜ήIbodyš
œ›˜›R˜»Rš
œΜ
˜Μ
—	˜"K˜
—	˜K˜ K˜Š	˜	š
œ˜Kšœμ
‘œ'˜™—	š
œ
˜
Kš
œΕ˜Ε—	š
œ˜Kš
œ˜—	š
œ˜Kš
œ€˜€——	˜	š
œ
˜
KšœΑ
‘œ
‘œͺ˜ςRš
œΝ˜Ν—	š
œ˜˜³

unitšΟnœ‘œ
‘œ˜2Lšœ‘œ˜&Lšœ‘œ˜&Lš
œ"˜"L˜——Kš
œΠ
˜Π
—	š
œ˜K˜β
—	š
œ˜K˜&———	˜
R˜
	˜	š
œ˜Kšœ‘œ‘œ‘œ‘œ‘œ-˜€
—	š
œ
˜
K˜Μ—	š
œ˜Kš
œε
˜ε
Jš
Οf
˜
Jš
£
˜
Jš
£
˜
Kš
œ‘˜‘—	š
œ
˜
Kš
œ°˜°—	š
œ
˜
Kšœι’œΉ˜ͺ	R˜©
Ršœ²’œ’œω˜Λ	—	š
œ)˜)K˜Θ—	š
œ˜Kš
œœ˜œRšœϋΟiœ‰
˜šRš
œ—
˜—
—	š
œ˜KšœΜ’œ’œV’œh˜ΈRšœ’œ’	œ’œ’œB’œΜ˜ΏR˜ζ—	š
œ˜Kš
œ°˜°Kš	œ¦
’œ’œ’œΊ
’œΕ
˜ψ—	š
œ˜K˜ϊ
—	š
œ˜K˜ω
—	š
œ˜K˜
—	š
œ&˜&Kš
œΠ˜Π—	˜	K˜›
——Q˜˜Ύ
	š
œ'˜'Q˜P—	š
œ˜Q˜4—	š
œ˜Qš
œ;˜;—	š
œ˜Qš
œ6˜6—	š
œ˜Qš
œ?˜?—	š
œ
˜
Qš
œ<˜<—	š
œ˜Qš
œ0˜0—	š
œ˜Q˜E—	š
œ
˜
Q˜6—	š
œ˜Qš
œ@˜@—	š
œ˜Qš
œQ˜Q—	š
œ˜Qš
œ€˜€—	š
œ)˜)Q˜ά—	š
œ2˜2Q˜L—	˜Q˜\—	š
œ˜Q˜M—	š
œ˜Q˜­
—	š
œ˜Q˜;—	š
œ?˜?Q˜L—	š
œ˜Q˜4—	š
œ˜Qš
œ8˜8—	š
œ˜Q˜>—	š
œ
˜
Q˜B—	š
œ˜Q˜4—	š
œ	˜	Q˜:—	š
œ˜Q˜•
——	˜Kš
œΏ
˜Ώ
——	š
œ˜Kš
œΪ
˜Ϊ
	˜
Kšœά€˜λ—	˜Kšœ‹€
œr€
œΌ
˜»R˜ŽRš
œΈ
˜Έ
Rš
œΫ
˜Ϋ
R˜Ršœχ€˜‹—	˜KšœΌ€
˜Ι—	˜Kšœ£€œ
˜³—	˜KšœK 
œΝ 
œw 
œ˜”Rš
œΡ
˜Ρ
—	˜	š
œ˜Kš
œ5˜5—	š
œ˜K˜}—	š
œ˜K˜Œ
——	˜	š
œ˜K˜$——	˜
K˜«R˜t——	˜K˜‰Ršœ¦
‘œP‘œΉ˜ΆRš!œ:‘œ
‘œy‘œ‘œ
‘œ‘œL‘œ
‘œγ
‘œ
‘œ‘œ
‘œ
‘œ‘œf‘œ
‘œΗ
˜ˆR˜—	˜

refrenceš œ€˜)Tš
œ˜Tš
œ/˜/T˜—š œ˜Tš
€I˜IT˜XT˜—š œ(˜,Tš
€;˜;T˜T˜—š œ€'˜<Tš
œ+˜+T˜—š œ€œ
˜5š
œ˜T˜——š œ
€œ
˜&Tš
œ5˜5T˜—š œ-€˜CTš
œ'˜'T˜—š œ€0˜STš
œ!˜!T˜—š œ"˜&Tš€Gœ
˜HT˜*T˜T˜—T˜T˜T˜—J˜—…—ŒN˜