MUMBLE(ID:4125/mum002)Programming language appropriate for describing bitmap computations and manipulations Includes a Bitmap Calculus based on APL array manipulations Related languages
References: in [ACM SIGACT-SIGPLAN] Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages 1978 , Tucson, Arizona view details Extract: Introduction Introduction Many present-day graphical systems use raster devices, such as displays and printers, as output media. These media require that displayed pictures and text first be converted into bitmaps, (i.e., arrays of discrete intensity/color values). Some such systems, notably the new breed of personal computers initiated by the Xerox Alto, the M.I.T. Lisp machine, and others, have been able to provide a user interface superior to anything that has existed before through the use of specifically designed, powerful bitmap manipulation instructions. Up to now the study of such instructions has not received extensive treatment in the literature. It has been considered mostly the province of system architects and a few daring hackers. Furthermore, bitmaps have been treated as imperfect and mathematically uninteresting approximations to the ideal images of plane geometry. W.e feel that it is time to give bitmaps full citizenship in the world of computer science. Their practical importance alone would be enough to justify this attention, but it can also be argued that bitmaps are worthy mathematical objects on their own. In this paper we propose a bitmap calculus: a mathematical model and notation for describing operations on bitmaps. The model is machine-independent and takes full account of the discrete nature of bitmaps. It is quite general, allowing one to describe, for example, color and grey-scale computations, point and neighborhood operators, picture translation, rotation, and sampling. We show some obvious and not so obvious applications of this calculus. It is interesting that there are several examples of bitmap computations that ostensibly depend on global properties, and yet in fact can be done by applying purely local operations in a uniform manner. We decribe MUMBLE, an interactive language designed and implemented to allow experimentation within this bitmap calculus. It is hoped that such experimentation will help in the discovery and development of useful algorithms and "idioms" of the bitmap calculus; we mention some interesting examples that seem to justify this hope. Finally, we present some techniques that can be used to evaluate complex bitmap expressions efficiently. In particular, we show how to use "lazy evaluation," run-length encoding, and word-oriented Boolean operations to cut down on time and memory requirements. In the evaluation of complex bitmap expressions, for example, these techniques will avoid the creation of large temporary bitmaps. These ideas have been implemented in BOP, a flexible and general software package for bitmap manipulation, that forms the underpinning of our MUMBLE system. Section 1 of this paper discusses a justification for bitmaps and introduces the bitblt instruction; Section 2 presents our bitmap calculus; Section 3 describes MUMBLE; Section 4 contains a collection of MUMBLE programs that do various interesting graphic computations; Section 5 elaborates on BOP; and finally Section 6 contains some conclusions. Extract: The Traditional View of Bitmaps 1.1 The Traditional View of Bitmaps Traditionally, bitmaps have been viewed as imperfect approximations to the ideal images one would like to display. Such ideal images are assumed to be described by continuous variation in color, intensity, and so forth. The imperfection is brought about by the discrete nature of the imaging devices we possess, as well as the digital nature of the computers themselves, which forces us to quantize these continuous variables into a discrete (but possibly very large) set of values. A consequence of this view is that bitmaps are essentially an implementation artifact, and the graphics programmer should be spared the pain of being exposed to them as long as possible. For example, in designing a graphics package it has often been argued that the objects the programmer should be given access to are the ideal shapes of plane geometry plus continuous functions for describing color and intensity modulation. The operators available in such a package must always correspond to operations on these ideal objects. It is the responsibility of the package's implementor to discretize all these continuous functions internally and transform the ideal continuous operators into their discrete counterparts. Unfortunately, for a variety of reasons, no such package has ever been able to hide fully the discrete representation involved beneath the surface. Perhaps the most fundamental reason is that certain laws, which hold in the continuous domain, cannot be made to hold in the discrete domain, no matter how careful one is about the quantization process. (We will have more to say about this shortly.) Also, good quantized approximations to continuous tone images naturally involve very large bitmaps. Such large bitmaps are expensive to store and manipulate. Thus efficiency considerations often make it imperative that the graphics programmer be made aware of the implementation underneath. As anyone who has taken a course in numerical methods knows, floating-point numbers do not satisfy many of the identities that hold true for real (ideal) numbers. In large part, the science of numerical computing is devoted to compensating for these (fundamental) imperfections in floating-point arithmetic. Similarly, when images are discretized, certain errors are unavoidable. In general, different policies about how these errors are to be made can optimize different goals. Two philosophies commonly used for error distribution are what we shall term global faithfulness and local faithfulness. These are illustrated by considering the picket fence example shown in Figure 1. Suppose each picket is 1 pixel wide, but the pickets are spaced 2.5 pixels apart. Then the global faithfulness method would rasterize the picket spacing to an alternating thickness of 2 and 3 pixels respectively, so as to make the overall length of the fence as close to its real value as possible. The local faithfulness method would simply choose either 2 or 3 pixels and make all spacings that thickness. In the global method the overall length of the fence is preserved, but the local congruence of the spacings is lost. In the local method the converse is true: local congruence is preserved, but global dimensions can be way off. Which scheme is better clearly depends on the particular application. Another reason bitmaps seep through to higher levels of system design is efficiency. Dynamic raster graphics require very high-speed manipulations of the raster memory [17], where the image being displayed is stored. In every case, the contents of the raster memory can be computed by scan conversion algorithms from higher level shape, illumination, and color descriptions. Such algorithms are rarely, however, fast enough to cope with incremental updating of the display, as is often required in interactive applications. Although, as we remarked earlier, ideal image manipulations do not always have exact counterparts in discrete form, in many cases they often do. For instance, the common operation of copying or translating a subimage on the screen has an exact counterpart in the discretized form. There are immense speed advantages to be gained by doing these manipulations in the raster representations, rather than in the ideal ones and then repeating the scan conversion. It is the conclusion of this subsection that an attempt to ban bitmaps from anything other than a temporary low-level representation for computer images is bound to encounter difficulties. Extract: Introduction of Bitblt Introduction of Bitblt To facilitate raster manipulations, several novel computer systems have used specialized instructions dealing with the raster memory. Typically these systems have been personal computers, such as the Xerox Alto [18] or the M.I.T. Lisp Machine [21], where a premium is placed on interactive graphics facilities. Their raster instructions are powerful primitives, often implemented in a combination of hardware and microcode. For example, the operation of copying a rectangle of pixels from one part of the screen to another can be accomplished by invoking a single such instruction. Such an instruction is commonly known by the name bitblt (bit boundary block transfer), or RasterOp in the Newman-Sproull terminology [15]. (See also the discussion in [1].) The first instance of this instruction was coded by Dan Ingalls and Diana Merry at Xerox PARC in 1975. The most common form of this instruction is a bitwise Boolean operation between two comformable (i.e., having the same dimensions) and possibly overlapping rectangles of pixels. If we call one rectangle S for source and the other D for destination, then bitblt performs the operation d *-- d ® s for corresponding bits d and s in D and S. Here (D denotes some two-argument Boolean operation, which is a parameter to bitblt. Such an instruction can obviously be used to move rectangles of bits around the screen. There are many subtle issues regarding this instruction. How are the two rectangles to be specified? In whose coordinate system? What if they are not comformable? Useful stipple and grey-scale patterns can be obtained by giving an appropriate meaning to bitblt when mapping a small rectangle onto a large one. There are also several interesting issues about the implementation of the bitblt instruction, but we will not elaborate on these here. For us, the most important property of bitblt is that it has been found to have an amazing number of uses, far beyond the obvious ones discussed above. (This fact has been part of the raster graphics folklore for some time.) For example, it is possible to rotate or transpose an n × n bitmap with a number of bitblts which is a small constant times n. Bitblt can also be used to fill in areas, count connected components, and do several other interesting and useful bitmap computations in very ingenious ways. Part of the reason for this seems to be that many interesting bitmap computations can be done entirely through local operations, that is by uniformly replacing each pixel with a function of (the old values of) itself and its neighboring pixels. Such algorithms have been studied to a certain extent in the theory of iterative arrays [20] (though not especially in a graphics context) and correspond naturally to invocations of bitblt. We will see some examples later in this paper. Extract: A Bitmap Calculus A Bitmap Calculus The techniques mentioned in the previous section appear at first to have an ad hoc nature, to be just hacks or tricks. We believe instead that they are instances of general mathematical principles waiting to be discovered, if an appropriate setting is created. Such a setting would be a calculus of bitmap operations, so one can learn to use these operations just as naturally as arithmetic operations on numbers. A number of related calculi have already established their value. APL [9, 16] is a widely used programming language whose basic data structure is the multidimensional array. Much of the power of APL stems from the fact that it has a carefully chosen set of operators which compose well with each other. In fact APL was invented as a notation for array computations long before an interpreter for it was available. Many of the issues we will discuss concerning efficient implementation of bitmap computations have also been encountered earlier in the construction of optimized APL interpreters and compilers [6]. Boolean algebra is another calculus closely related to our bitmap computations, since very frequently our bitmaps are only a single bit deep. Although most of us have some experience with manipulating expressions involving ANDs and ORs, perhaps we do not all realize the usefulness of other Boolean functions, such as exclusive OR (XOR). The XOR operation also satisfies simple algebraic laws, for instance (x XOR y) XOR x = y, or (x XOR y) AND z = (x AND z) XOR (y AND z). This can often be used to advantage. Some of the most interesting uses of XOR are covered in [10]. Several applications of XOR in bitmap computations are discussed later in this paper. The most significant influences on the bitmap language we describe have been these two calculi, plus a hefty amount of intuition about the proper geometric shapes to use for creating primitive bitmaps (the atoms of this calculus). The concepts and a notation for the bitmap calculus are defined in what follows. This description should be considered a proposal of a formal mathematical notation for bitmaps and bitmap operations, rather than the definition of a programming language. However, the syntax and semantics proposed here were also incorporated in MUMBLE, as FORTRAN and ALGOL were patterned after the notation of common algebra. Extract: Pictures and the Image Plane Pictures and the Image Plane A (discrete) image, or picture, is defined to be an infinite two-dimensional array of bitstrings of uniform length called pixels (short for picture elements). Pictures are the central concept of the bitmap calculus and are a mathematical representation of the intuitive "bitmap" concept. The elements of a given picture all have the same length, which is called the depth of the picture. They are indexed by pairs [i, j], where i andj range over all (positive and negative) integers. We follow the array convention when drawing the coordinate axes, so the /-axis proceeds downward and the ]-axis to the right. This is just a 90 degree clockwise rotation of the normal x, y-coordinate system. It is convenient to think of a picture B in geometric terms, by considering its pixels to be located on a Cartesian plane (the image plane), with pixel B[i,j] centered at the point with coordinates [i + ½,j + ½].1 Also, the bits bn-]bn-2 " ' " b] b0 of each pixel are considered to be stacked in the direction perpendicular to the image plane, with b0 at the bottom. We can therefore speak of the kth layer of the image as the picture formed by considering bit bk of every pixel. Operations and algorithms involving pictures make frequent use of points, vectors, and other geometric entities of the image plane, particularly those with integer coordinates. An important example is that of a box: a rectangular region of the plane with sides parallel to the axes. We represent a box by a pair of points [l, h] with integer coordinates, the coordinates of the upper left and lower right corner, respectively. A pixel is said to be inside a box (or any other geometric figure) if the same is true of its center point. Extract: Elementwise Operations Elementwise Operations Most operations defined for finite bit strings naturally extend to pictures in an elementwise fashion. For example, pixels can be combined by using bitwise Boolean operations such as AND, OR, XOR, etc. Bitstrings can also be interpreted as representing numbers in binary notation, and thus the usual arithmetic and relational operations extend naturally to pictures. Signed (two's complement) and unsigned binary notations are both widely used in computer practice; each has its own advantages and a large set of applications for which it is almost mandatory. Both notations have been retained in the bitmap calculus. Relational operators (=, >, etc.) compare the numerical values of the operands, and return either 0 (= FALSE) or -1(= TRUE) in two's complement. Relational operators extended to pictures are very useful in building masks: one-bit images containing only TRUE and FALSE pixels. Masks can be used with Boolean operators to extract and combine selected parts of other pictures. For example, (X AND (A > B)) OR (Y AND (A _< B)) is an image that is equal to X[i,j] wherever A[i,j] > Blij], and equal to Y[~,j] everywhere else. Other bitstring operations that are particularly useful when extended to pictures are: b TOLEN n, which makes b into an n-bitstring by padding or truncating its high-order bits; b CHOP n, which returns the higher order n bits of b; and the lamination operation, a I b, which concatenates the bitstrings a and b. In addition, the depth and the kth layer of a picture P are denoted by DEPTH P and P LAYER k, respectively. Conditional bitmap expressions can be defined in terms of Boolean operators: IF A THEN B ELSE C FI is by convention equivalent to B AND (A ~ FALSE) OR C AND (A = FALSE), for any pictures A, B, and C. A related operation is P CUT b which produces a picture coinciding with P inside the box b, but zero everywhere else. When two bitstrings of unequal length are combined in a Boolean operation, we assume that the shorter is extended (preserving its numerical value) to match the longer. This means that TRUE and FALSE extend to the bitstrings 111... 1 and 000... 0, and therefore masks built by relational operators can be used with pictures of any depth. Extract: Geometric Operations Geometric Operations Let T be a geometric transformation, a function that maps the image plane into itself, and let P be a picture. The picture T(P) is defined by moving every pixel of P as specified by T. For example, consider the operation p SHIFT v, that displaces the point p = [pi, pj] by the vector v = [vi, vj], producing the point [pi -I- vi,pj -I- Vii. The result of P SHIFT [7, 3] is a picture O such that Q[i,j] -- P[i-7,j-3] for all [i, j]. Geometric operations can be extended to boxes and other geometric figures in exactly the same way. In order for this extension to have meaning, the function T must have a welldefined inverse, even though T itself may be undefined or multivalued at some points. The function T is assumed to apply to the centers of the pixels, rather than to their indices, so T-l(p) must map pixel centers to pixel centers. Three important functions that satisfy this requirement are p ROT c, that rotates point p by 90 degrees counterclockwise around the point c, and p I__ FLIP i0, p J__ FLIP j0, that mirror the point p around the lines i = i0 and j = j0, respectively, where c, io, and jo have integer or half-integer coordinates. Another operation that falls in this category is the sampling operation, defined by the identity (P SAMPLE [s, t])[is, jt] -- P[i,i] (s and t must be integers). Its effect is to collect every sth row and tth column of P and "compress" the resulting picture. A related operation is b REPEAT F, which denotes the bitmap obtained by replicating a rectangular patch of the picture F all over the image plane. The box b defines the portion of F to be replicated, and also determines the phase (placement of the first "tile") and the period of tesselation. Extract: The MUMBLE Language The MUMBLE Language MUMBLE is a language designed to perform computations on digital images or bitmaps. It implements the operations and primitives discussed in the previous section, so formulas of the bitmap calculus are generally valid MUMBLE expressions. As most programming languages, this one includes many features that have no counterpart in the language of mathematics, the most notable being the concepts of assignment and variable (in the sense of assignable identifier). In previous sections we used the term "bitmap" both as a loose synonym for "discrete image," and in the machine-related sense meaning "an area of the memory where a discrete image is stored." The distinction between the two concepts is quite important for understanding the semantics of MUMBLE; therefore, from now on we reserve the term "bitmap" for the machine-related concept only, and use the terms "image" or "picture" for the abstract concept. Pictures are always infinite in both dimensions, whereas bitmaps are necessarily restricted to a finite subset of the picture plane, which in the case of MUMBLE is a finite bounding box. It follows that when a picture is stored in a bitmap, only the portion that falls inside its bounding box will be preserved. If the content of the bitmap is to be used in subsequent computations, it is extended to an infinite picture by assuming the pixels outside the box to be zero. Thanks to these conventions, it has been possible for us to give a "natural" meaning to arbitrarily complex expressions, involving geometric figures and transformations, bitmaps of different sizes, and infinitely repeating patterns, without having to specify for each operation what happens at the points where some operand is undefined. We should also emphasize here that the definition of pixels as bitstrings, rather than as pure integers or real numbers, is an essential part of the bitmap calculus we propose, not a limitation imposed on MUMBLE by implementation issues. This assumption lends a different character to the picture computations we are concentrating on from those traditionally associated with image processing, where pixels are considered to be real-valued. MUMBLE is a block-structured, weakly typed interactive language. Besides bitstrings (which include numbers), bitmaps, and pictures, it handles a few other kinds of objects, such as characters and character strings, pointers, records, variables, and procedures that are necessary in a useful programming environment. Extract: Some Fundamental Pictures Some Fundamental Pictures In this section we define some fundamental pictures that either possess wide applicability or are relevant to some major application of raster-scan graphics. These pictures are the "atoms" of our bitmap calculus. The notation ALL v stands for a picture whose pixels are all equal to the bitstring v. The expressions I__IM n and J__IM n represent a signed picture of depth n where pixel [i,j] is the value of i or j, respectively, extended or truncated to n bits. These two primitives allow the description of pictures where pixel [i, j] is defined by an expression involving i and j. Note, however, that all pictures described in this way will be ultimately periodic, owing to the finite number of bits of i and j used according to the definition. An important class of pictures is that of geometric shapes, which in the bitmap calculus are defined as discrete approximations to the geometric figures of the Euclidean plane geometry, like rectangles, triangles, circles, and so forth. Such images are defined as masks which are TRUE inside the figure and FALSE outside it. A box can be considered a geometric shape and used as such in formulas. Additional geometric shapes one would like to have as primitives very much depend on the application, so their definition is better left to the user of the calculus. Two primitives that seem to be reasonably useful in graphics applications, however, are CIRCLE[c, r] (a circle centered at point c with radius r) and TRIANGLE[p1, p2, p3] (a triangle with the specified vertices). Also useful is LINE[p1, p2, w], a line segment from Pl to p2 with thickness w. However, the exact definition of this shape, particularly at the two endpoints, is again application- dependent. Extract: Values and Variables; Bitmaps Values and Variables; Bitmaps In general, a MUMBLE expression may evaluate to either a value or a variable. A value is a piece of data, or bit pattern (some examples are bitstrings, pictures, character strings, and pointers to other objects); a variable is an object in which values may be stored. Ordinary variables are similar to the simple variables of PASCAL or ALGOL, except that they are essentially typeless: they can be assigned any simple value, including bitstrings and pointers. Pixel variables can only be assigned bitstring values of a fixed size and type; moreover, they cannot be named or created in isolation, occurring only as elements of bitmaps. A bitmap B behaves in MUMBLE as a rectangular array of pixel variables; subscripting can be used to access each pixel individually. Ordinary variables can be directly named in MUMBLE, but bitmaps and individual pixel variables cannot. The usual way to refer to a bitmap in MUMBLE is to store its descriptor (essentially a pointer to its location in memory, plus some associated information) in an ordinary variable. To get hold of the bitmap itself, the descriptor must be dereferenced by the "!" operator. The ordinary assignment V : = e stores the value of the expression e into the ordinary variable Y, without any type conversions. Pixel variables cannot be assigned with ": =": they require the pixel assignment operator "*-", as for example in (!B)[i, j] *- (!B)[i, j] + 1. Unlike ": =", the "*-" operator extends or truncates the value on the right-hand side to conform to the variable on the left. The pixel assignment operator can also be used to assign a whole picture to an entire bitmap. The command (!B) *- (!B) + ALL 1 will add one to every pixel of the bitmap pointed to by B. Actually, MUMBLE automatically dereferences a bitmap descriptor when an indexing or pixel assignment operation is applied to it, so we could have written B[i, j] *- B[i, j] + 1 and B *- B + ALL 1 in the examples above. Note that B := A assigns to B the descriptor in A, while B *- A copies the contents of the bitmap pointed by A into the one pointed by B. The expression BOUNDS A returns the bounding box of bitmap A. Applying a geometric transformation (SHIFT, ROT, etc.) to a bitmap descriptor returns another descriptor, pointing to the same bitmap, with its parameters modified so as to simulate the specified transformation. That is, the pixel assignment (A SHIFT [-2, 3])[i, j] *- 1 has exactly the same effect as A[i + 2, j - 3]*-1. The meaning of an assignment like A := A SHIFT [-2, 3] should be carefully considered: the picture stored in the bitmap A stays fixed, but the names of its pixels and its bounding box are moved around. It is like sliding an egg carton (the bitmap) over a tiled floor (the image plane): the positions of the eggs (pixels) change, even though they do not move relative to the carton. In contrast, the assignment A *- A SHIFT [-2, 3] will actually move the contents of the bitmap by the specified amount, without disturbing its descriptor or bounding box; some pixel values around the margins will be lost, and some will be filled in with zeros. Continuing the above analogy, this corresponds to leaving the carton in the same place and moving each egg inside it by the specified amount. To determine the meaning of pixel assignments that refer to the same bitmap both on the left and on the right-hand side, as in the above example, we must take into account the order in which the pixels are assigned by MUMBLE. The right-hand side is evaluated, and the left-hand side is written, in the so-called ravel order: this is a double loop, the inner loop being from low j to high j, and the outer loop being from low i to high i. Of course, the new value of a pixel has to be computed before being written; but, apart from this, owing to internal buffering in the implementation, no implicit guarantee is made about the relative time ordering of the reads versus the writes. The effect of A (-- A SHIFT [2, 3] is therefore undefined, since the value of A[i-2,/-3] may already have been overwritten by the time the individual pixel assignment A[i,j](-- A[i-2,j-3] is executed. Note however that the assignments A (-- NOT A and A (-- (A SHIFT [0, - 1 ]) are perfectly safe. Only in some cases will dangerous assignments like the above be flagged by the interpreter. It should be noted that the bitblt instruction discussed in Section 1 usually chooses the order of evaluation in such a way that no pixel is overwritten before being read; this increases significantly both the conceptual simplicity and the usefulness of the bitblt instruction. It would be highly desirable to include the same mechanism in the bitmap assignment of MUMBLE; unfortunately, the generality of the expressions allowed in such assignments makes this technique much harder to implement. Indeed, some bitmap assignments cannot be correctly evaluated on a pixel-by-pixel basis, no matter what the scanning order is. Consider, for example, the statement A (-- A I__FLIP 5, where the bounding box of A is [[0, 0], [10, 10]]: no matter which of the two assignments A[0, 01 (-- A[9, o] and A[9, o] (-- A[o,o] is executed first, the other will produce the wrong result. This problem can be solved by the introduction of auxiliary bitmaps (e.g., by writing Aux (-- A I__FLIP 5; A (-- Aux in the example above). Considering, however, that bitmaps are typically quite large objects, and that the detection of such invalid assignments is by no means trivial, we decided against the automatic introduction of auxiliary bitmaps by MUMBLE, leaving to the user the primary responsibility of detecting and preventing such errors. Section 4.5 shows how one can code a common case of the bitblt instruction in the MUMBLE language. Extract: Why Bitmap Descriptors? Why Bitmap Descriptors? Bitmap descriptors and the existence of two flavors of assignment operator are among the main causes of complexity in the MUMBLE language. These two features were motivated by the desire to combine a natural way of expressing bitmap computations with enough structure to make a smart evaluator possible. For example, consider the following computation: A (-- B OR (((B SHIFT [0, 1] + (B SHIFT [0,-1]) + (B SHIFT [1,0]) + (B SHIFT [- 1,0])) > ALL 2) An important feature of MUMBLE is that complex picture expressions like the one above do not require temporary bitmaps for intermediate results. Since bitmaps are usually quite large objects, this is a feature of considerable value. However, this optimization is usually inhibited by the common programming practice of breaking complex expressions into a sequence of smaller ones and assigning their values to temporary variables. If we rewrite the statement above as BL *- B SHIFT [0, 1]; BR *- B SHIFT [0, -1]; BU *- B SHIFT [1,0]; BD ,- B SHIFT [- 1,0]; A*-BOR((BL+ BR + BU + BD)>ALL2); the computation will require the four temporary bitmaps BL, BR, BU, and BD, each containing a slightly displaced copy of the bitmap B. If we write instead BL := B SHIFT [0, 1]; BR := B SHIFT [0, -1]; BU := B SHIFT [1,0]; BD :-- B SHIFT [-1,0]; A,-BOR((BL+ BR + BU + BD)>ALL2); then BL, BR, BU, and BD will just be modified descriptors of the original bitmap B. Extract: Deferred Evaluation and Picture Formulas Deferred Evaluation and Picture Formulas An important aspect of MUMBLE is the mechanism by which such apparently infinite expressions like B + ALL 1 are evaluated in finite time. This is accomplished by evaluating picture expressions and subexpressions only when and where their values are actually needed. For example, in A *-- B AND (C OR D), the expression B AND (C OR D) will not be computed outside the bounding box of the bitmap A; furthermore, if B[i,/] is zero, it is possible that MUMBLE will skip the evaluation of (C OR D)[i,/]. A conditional picture expression like IF A THEN B (-- F ELSE C (--- F FI, where all variables evaluate to bitmap descriptors, means that the assignment B[i,j] *-- F[i,j] is to be performed for all pixels, and only those, for which A[i,j] is not FALSE. For the remaining pixels, and only those, the assignment C[i,j] (-- F[i,j] is to be performed. A conditional expression including bitmap assignments can be replaced by an equivalent one containing Boolean operations instead of the conditionals, but in that form its execution cost may be much higher. The operations in a picture expression like A (-- B AND (C OR D) are not evaluated in the "bottom-up" fashion characteristic of PASCAL or ALGOL. Rather, the whole expression is first encoded into a delayed picture formula, or form, that is a symbolic, unevaluated representation of those operations and their operands. The actual evaluation proceeds in a "top-down" fashion: the outermost operation ("(--" in the example) is examined first, and its operands are evaluated only for the pixels where their values are actually needed. Inner operations are treated in the same way. This process is called the scanning of the picture formula, and its details will be discussed in Section 5. It is possible to build and keep around a deferred formula in its "unscanned" state: the (ordinary) assignment F : = FORM (B AND (C OR D)} will store in F a pointer to the given deferred formula, without actually carrying out the indicated picture computations. The formula F can be used to build more complex expressions and statements, as for example A (-- (X AND F) OR (Y AND NOT F). Complex picture expressions can thus be built up little by little, but no actual evaluation happens until the programmer indicates that this should occur. A deferred formula may contain bitmap assignment operations, as in the case of E : = FORM {B (-- B + ALL 1 }. It is frequently the case that a formula like E has to be evaluated only for its side effects, and its value (if any) is to be discarded. This is accomplished in MUMBLE by the statement SCAN E. Deferred formulas are similar to picture-returning procedures in many ways, with F := FORM {...} corresponding to a procedure declaration, and A (-- F or SCAN F corresponding to its invocation. The two concepts differ in several aspects, however, the most notable being the way in which their bodies are evaluated. Extract: Other Syntactical Features Other Syntactical Features This section presents an overview of some unconventional features of MUMBLE syntax. Together with the previous sections, the paragraphs below should enable a reader with programming experience to follow the examples in Section 4. For a full presentation of the language, see [5]. Syntactically, a MUMBLE expression consists of closed subexpressions {identifiers, unary operators, literals, parenthesized expressions), applied to each other and/or combined by means of infix operators. For example, in B i + Foo [i, j] XOR (Func R) Fum X the identifier B is applied to i, Foo is applied to [i, j], and the result of applying Func to R is applied to the result of Furn applied to X; the symbols "+" and "XOR" are infix operators. The priorities of infix operators are for the most part similar to those of ALGOL. Most usual operation on numbers, strings, etc. are available in MUMBLE. The application construct has different meanings depending on the types of the operands. It is used to denote procedure invocation, unary operator application, bitmap, record, and string subscripting (with the subscript on the right, as in X i) and record field selection (with the selector on the left, as in irn X). Applications are evaluated from right to left, so Fee Fi Foo Fum means Fee (Fi (Foo Fum)). A single MUMBLE construct implements both the record concept of PASCAL and the block structure of ALGOL. The MUMBLE expression [L0: Eo, L1 :El, L2:E2 . . . . . Ln-~ :E,-1] constructs an n-field record, with selectors L0, L 1 , . . . , Ln-1 and whose values are the results of evaluating Eo, E~,..., En-] (some or all Li and/or Ei may be omitted). During the evaluation of Ei, the field selectors L0 to Ln-1 can be used as if they were ordinary variables. A pointer to the constructed record is returned as the value of the whole expression. The infix operator "; ", that evaluates both its arguments in sequence and returns the second, can be used with ordinary parentheses to build compound statements. Individual components of a record can also be accessed by subscripting, and can be modified by the ordinary assignment operator ":= ". Record fields are untyped: they may hold any simple value. Record constructors can be nested, and the usual ALGOL-like scope rules apply. Points and vectors of the bitmap calculus are represented in MUMBLE by records with two bitstring components, I and d. Only the numerical values of I and J, and not their lengths and types, are relevant for MUMBLE operations that require point and vector arguments. The language contains the usual collection of conditional and iterative commands, including IF-FI, DO-OD, WHILE, FOR, EXIT, and so forth. Procedures are declared by writing name: PROC {formal parameters I local declarations and commands }. If the type of a formal parameter is not specified, any simple value can be passed as argument. The result can be any simple value, and is given by the last expression appearing in the procedure body, or by the execution of RETURN e. in Computer Graphics, 16(3) July, 1982 Proceedings of the 9th annual conference on Computer graphics and interactive techniques, 1982 ((SIGGRAPH 82) view details in Computer Graphics, 16(3) July, 1982 Proceedings of the 9th annual conference on Computer graphics and interactive techniques, 1982 ((SIGGRAPH 82) view details |