GRAM: Some Papers of Tony Pritchett

The set of papers below were found in Tony Pritchett's archive. They were written between 1972 and 1976 so describe GRAM as it was at that time. So the descriptions of the GRAM system change over that period so they exhibit some of the changes made during the course of the project. The papers are believed to be approximately in date order.

P1: A Computer Graphics Facility for the Open University

Paper by Tony Pritchett written in 1972. Scanned by Kate January 2021 (GRAM 1972/73 Folder 14).

1. Introduction

The application so far for a computer graphics system at the OU divide roughly into three categories:

  1. Animated films.
  2. Static computer-aided design for producing course publications etc.
  3. Artificial Intelligence/Pattern Recognition research.

The primary aim of this project is to achieve something with the above applications rather than an exercise in the design and implementation of generalised graphic languages. Therefore if one or more systems exist which would fulfill the requirements, and which are accessible to the OU (either by remote access or by easy implementation on one of the OU's present or possible future computers), then there would be no need to design and implement a new system from scratch.

There are many systems in existence, both for computer animation and more generalised graphics, which could be made available to the OU without too much effort, but do they fulfill our particular requirements? As far as items (2) and (3) above are concerned this is difficult to answer due to lack of previous experience, so that almost any existing system at present employed successfully for similar applications is likely to be just as good and if not better than anything thought up from scratch. For animated film generation, however, on which there is considerable amount of personal experience, the answer is no.

Since, therefore, it is desirable to build a new system for doing animation, it ought to be sufficiently flexible to cope with the more general application as well.

2. Why Existing Available Computer-Animation Systems are Inadequate

Criticism of the Atlas systems, the only ones at present available to the OU can be summarised by saying that they are:

  1. too slow for OU production schedules;
  2. not cost/effort effective compared with other animation techniques for the majority of things they have been asked to do.

The main reasons are:

  1. Subroutine package type systems requiring unwieldy one-off programs for each film.
  2. Batch-type computer installation restricted to 2 or 3 runs per day, making development of these large programs very slow. This is further aggravated by all graphic output being off-line.
  3. Lack of real-time playback of movies before they are committed to film. There are a whole range of common errors, mainly of the continuity type which are hard to spot by a random sampling of still frames.
  4. Lack of any facilities to edit mistakes on a plotter tape without doing a complete continuous re-run of the whole film program on the computer.
  5. Difficult to make minor adjustments to sequencing and timing without wholesale and sometimes disastrous program alterations (in a better system quite a lot could be done at a post-editing stage, as with (4) above).

Some quite sophisticated interactive systems have been implemented in the USA which overcome some or all of these difficulties (in particular GENESYS). The snag is that all of them are highly machine- (and even configuration-) dependent. It is hard to program for interactive displays in a transportable manner, as they nearly all operate in totally different ways, and demand a large amount of assembly language programming.

Other systems which have been or could be transferred onto any of the computers available to the OU are non-interactive, implemented in a popular language (usually FORTRAN) and suffer from the same drawbacks as the Atlas systems. Implementing one of these on a remote time-shared installation would bring some benefits with conversational-mode debugging, but would no confer true interactivity.

The Atlas Laboratory at Chilton has a new system (SPROGS) under development which is supposed to eliminate the difficulties of previous ones, but since its final structure is still an open issue, it remains to be seen by how much. Also the degree of access to it by the OU is at present unknown. However, the possibility of designing an OU system so that it will interface easily with SPROGS should be considered.

Essential Features of a Visible Computer-Animation System

3.1 Data-Structure-Editor Concept

The Atlas system is based on the principle that a complete film sequence is generated (just once) by means of a single, monolithic program, which does everything in one run on the computer. The trouble is that such large, complicated programs need a very large number of test runs to eradicate errors, which appear to increase exponentially with the program size. It was found to be comparatively easy to get the various component processes to work in isolation from each other. Also, there was a desperate need to be able to make simple modifications to the final product without having to alter and re-run the whole program, which suggested the desirability of being able to edit the SC4020 plotter tapes themselves.

It is therefore maintained that a more sensible approach would be to construct a film sequence in a number of separate, simple steps, representing the different aspects of the process, and different streams of action, all being brought together by a powerful editing system. The thread joining these processes would be a common data base which would represent the state of the film sequence following the last process, and the user would be able to check its correctness by causing this data base to be displayed graphically. Thus each process merely manipulates the data base in some way so that the final state of the data base after the last process completely describes the film sequence, from which microfilm plotter orders can be generated automatically.

The processes could be pieces of user-defined program calling a common I/O system to handle the format of the data base, or sequence of commands in a standard editing program for doing the more common manipulations on the data base. An interesting implication of this is that the different processes need not necessarily be programmed in the same language, nor even executed on the same machine, provided they can all handle the same data base format via a common medium such as magnetic tape.

3.3 Interactivity

This is most important for the achievement of speed and ease of construction of a data base. One ought to be able to issue a command through a keyboard, and immediately see whether its effect on the data base is what was intended. The intention is to achieve the kind of dynamic man-machine involvement of a film editor in a cutting-room, but with much wider powers than just the ability to arrange the sequence and timing of shots.

One should also be able to digitize arbitrary line-drawings interactively through a tablet, and input Path Descriptions and Rhythm Descriptions as in GENESYS.

3.3 Real-Time Animation Playback

This is actually possible with a fast refresh display, but is limited by picture complexity. It is very much a desirable adjunct to achieving complete interactivity, and it is very difficult to spot some kinds of errors without real-time movement. It imposes certain constraints on the design of the data base, as it is necessary to interpret from that to display orders as fast as possible; (the playback program would most likely have to be in assembly code, or at least in an implementation language very close to machine level such as BCPL). It ma.y not be possible because of the time factor to get straight from data-base to display in real time in all circumstances without first compiling to an expanded form on disc. This could be made optional.

3.4 General Algorithmic Ability

It must be possible for the user to be able to write general mathematical and logical algorithms within the system, which communicate with the graphic part. This is difficult to achieve without having a built-in general-purpose language complete with expressions, etc, apart from the subroutine package approach which has other drawbacks. Within the philosophy of a range of independent programs operating serially on a common data base, however, it becomes simple, because any of the independent programs can be user-written in a high-level language.

3.5 Good for All Graphic Types

The data base should not be restricted to holding line drawings as strings of coordinate pairs. It should also be able to cope with coordinate triplets for 3D, scanned grey-scale areas, and anything else that might be required. In other words, the structure of the data base should not be designed around any particular way of representing graphics digitally.

3.6 History Independence

This is a concise but not very clear expression for the avoidance of a particular difficulty with interactive movie generation, when it is desired to view individual frames or sequences of a film at random. There is no problem when viewing a magnetic tape containing only plotter commands, as each frame is completely defined each time afresh. But if the data base is partly generative and what appears in a particular frame is dependent on what happened previously, it is necessary to go through all the processes in the film from the beginning in order to make sure that the state arrived at in the particular frame is correct, unless one is looking at frames in ascending sequence. In other words, to view frame 123 after viewing frame 124, one would have to go back to the beginning and work through all the processes from frame 1 up to frame 123, because programs do not work in reverse. This is clearly undesirable in terms of time.

A simple solution is to constrain the data base as follows: the data base must not contain active elements which when interpreted modify the data-base itself.

3.7 General Graphics Base

The lower levels of the system should form a basic graphics package with which one could construct further graphic systems for CAD and pattern-recognition work, for instance, without having to start from scratch. The data base could be designed to be easily made to form LISP-type list structures, or even ring-structures.

3.8 To Fit Small Machine

It is highly desirable that the system should be able to be implemented on a small 16-bit computer with perhaps 8K words of main store and a disc. A side effect of the philosophy of having a number of small programs operating on a data base is that this becomes feasible.

4. A Linked-List Structure for a Primary Data Base

Although list structures are essential in most CAD applications, where the digital representation of a three-dimensional object has to convey all the complex relationships between its different parts, this is not necessarily true for computer animation. However, lists do seem to have some advantages, particularly from the standpoint of editing; and something which can be expanded into a ring structure or used to implement LISP is probably worth the trouble.

The classical LISP type of list structure consists of linked elements, each of which contains two items of information, the car and the cdr in LISP jargon.

car cdr

The car is the main information field, and the cdr is the link to the next element in the list. The car can be an atom or a downward link to a sublist; a cdr may be a null link (end of list).

For example, a typical LISP structure:

A F G H B C D E

which can be written:

(A (B C (D E))F G H)

On a 16-bit machine the car and the cdr would have to occupy a whole word each. This is downright wasteful if, as in the case of an animation data base, a majority of it may be made up of linear lists of coordinate pairs which are not likely to be altered. For example:

(X1 Y1 X2 Y2 X3 Y3 ...XN YN) 
X1 Y1 X2 Y2 XN YN

It would be more economical to represent them as an array of consecutive words:

X1 Y1 X2 Y2 X3 Y3 XN YN

This is the same as saying that they have implied links (or cdrs) between them.

If one wanted them to modify this list, say insert some new elements between Y2 and X3, without having to move everything to the right of Y2, this would be possible by re-introducing links in some places and removing one of the previous elements to a new location:

X1 Y1 X2 X3 Y3 XN YN Y2 X21 Y21

This means that:

  1. one would have to distinguish between car's and cdr's by some means other than position, ie one bit in the 16-bit word,
  2. one would be in trouble if Y2 was already being pointed at from somewhere else, for if an element is actually moved to a different location, one would have to go through the whole store looking for references to it in order to change them.

The solution to problem (b) is to declare that no element, which is in the middle of a list and which is pointed at by a car in another list, can be joined to the previous element by an implied cdr, but only by an actual one. Thus any time a new link is set to point at a particular element, that element must be examined to check whether it is part of a contiguous list with implied cdr's (this is done by looking at the preceding word), and if it is, drop it out to a different location. For example, consider a list of elements with implied cdr's:

A B C D E F G H I J

It is at some stage decided to refer to element D from outside, in which case D must be dropped out into a new location, where it will remain fixed for the benefit of any more references to it:

A B C E F G H I J D Pointer from Outside

If another element K is then required to be inserted between C and D, this is no problem:

A B C E F G H I J K From Outside . D

and likewise if something is inserted between D and E.

There could be a secondary garbage collection process which would relocate everything so that all elements of a list which were not multiply referred to are assembled into consecutive locations with implied cdr's. This would give a space saving of between 30% and 50%. For a data base describing a movie sequence this is worth having, as the fast display program would not be permitted to modify the list structure, and it would speed up the transfer rate from backing store as well as permitting more to be in fast core at once.

Word Types

It is proposed to use the top two bits of a 16-bit word to distinguish between four different types, as follows:

   15 14 13
0)  0 0  14-bit integer      Literal integer (Atom), -8192≤i≤8191 
1)  0 1  Symbol ref no       Symbol (pointer to item in symbol table)
2)  1 0  Address             Link to sublist in car
3)  1 1  Address             cdr pointer/list terminator( if address = 0)

Numbers 0, 1 and 2 are all car's, and a cdr would be implied where a 0, 1, or 2 are juxtaposed without an intervening 3.

Ring Structure

A possible way of implementing a ring structure in the primary list system is shown below:

Conventional notation for a ring structure GRANDFATHER FATHER MOTHER SON 1 SON 2 SON 3 GRANDFATHER1 2 2 3 2 FATHER1 2 2 3 MOTHER1 2 2 3 2 2 SON 11 2 2 3 2 2 SON 21 2 2 3 2 2 SON 31 2 2 3

Implementation

(See paper by N.E. Wiseman: 'A ring structure processor for a small computer')

It would seem that either it would have to be composed of elements which carry their own cdr words (as explained above), or it would break the rule about not having pointed-at elements in consecutive locations with implied cdr's

Because of the amount of extra space it would occupy if one did not, it would be permissible to break this rule in this situation, provided the lists are added to only at their left-hand ends, with the right-hand 3 elements always remaining.

P2: A Computer Animation System for the Open University

Tony Pritchett (Faculty of Technology)

Paper produced by Tony Pritchett, date unknown. Scanned by Kate, September 2020

This is a system which has been implemented on the Nova Computer belonging to Technology Faculty. The Nova does the principle computation work, but the film is actually shot on either one of two film plotters, one at the Science Research Council's Atlas Computer Laboratory (ACL) and the other at the University Of London Computing Centre (ULCC).

NOVA Computer at Walton Hall Paper or magnetic tape SC4020 Film Plotter at ACL CALCOMP Film Plotter at ULCC Ready-processed Reversal B&W Film White-line drawings on Black background Kay's or Denham Film Processing Labs Solid filled-in areas in various shades on B&W film Technicolor Labs Solid filled-in areas in colour

Animation System

There are two separate advantages of using this system over previous ones, depending on which film plotter is used:

  1. Nova and ULCC Plotter: Short time scale Using the interactive animation program on the Nova and with a 24-hour turnround time on the ULCC plotter it is possible to produce simple animations of the moving graph or Wurmsers within four or five days.
  2. Nova and ACL plotter: Solid areas of grey or colour Using the ANTICS package at ACL, animated images generated in outline form on the Nova may be filled in with solid areas of black, white and grey, or by making use of the Technicolor 3-strip process, in a range of about 200 different colours. Due to the slow speed and heavy workload of the ACL plotter, a time-scale of less than four weeks for this stage of production cannot be guaranteed. Also, if colour is required, another two weeks should be added for Technicolor processing. Therefore, depending on the complexity of the design and compositional stage on the Nova, the total time scale to produce a sequence should be four to seven weeks for solid areas in black and white or six to nine weeks for colour.

It is intended to provide a solid-area filling program for the ULCC plotter as soon as possible, so as to be able to provide the advantages of speed and solid areas together. Colour can in fact be obtained at present from the ULCC plotter, but only in the form of coloured outlines.

The Nova Animation Program

Images of any arbitrary shape can be fed into this program ; one is not limited to mathematically-generated images. It can therefore be very conveniently used for providing all kinds of diagrammatic and even figurative animation.

All the standard rostrum camera operations can be accomplished with this program, e.g. PAN, ZOOM, ROTATE, MIX, FADE, but with the additional bonus that they can be done independently and simultaneously on any of the constituent sub-images making up the picture. In other words, one part of the picture can be made to rotate while other parts zoom or fade.

One can also inbetween two images, i.e. transform gradually from one to another over a number of frames: this is something which can normally only be achieved at great expense with large numbers of individually drawn cels.

Wurmser Animations mentioned above:

Alfred Wurmser was responsible for BBC simple animation and captions, such as drawing a graph, showing results of elections etc. Thus the naming of such animations as Wurmsers. They tended to be made up of layers of black and white card. The object to be animated tended to be in white and was revealed by sliding away the black card that covered it.

A photograph of Alfred Wurmser can be found at:

 http://tech-ops.co.uk/next/captions-animations-and-captain-pugwash/

An archived BBC clip Facts and Figures show several Wurmsers.

Patrick Moore's autobiography includes In pursuit of "props" we went to see Alfred Wurmser, a charming Viennese who lived in Goldhawk Road. He had a dog named Till, half-Alsatian and half-wolf, who weighed about a ton but was under the strange delusion that he was a lap-dog. Alfred made moving diagrams out of cardboard, and he soon became enthusiastic, so that we continued to use the "wurmsers" until he decided to return to his native Austria. The original title of our programme was to be Star Map, but we changed it to The Sky at Night almost at once - to make sure that the new title went into the Radio Times.

P3: GRAM: A Macrogenerator for Computer Graphics

Downloaded by Kate 07.05.20

A.G.M. PRITCHETT, Faculty of Technology, The Open University, Milton Keynes

Introduction

GRAphic Macrogenerator is an adaptation of C. Strachey's General Purpose Macrogenerator to provide an experimental interactive graphics facility on a small computer. The initial implementation is in ASA FORTRAN IV to provide portability.

This paper explains the principles of the macrogenerator and how it can be used for graphics.

GRAM is intended to be part of a software package for providing computer-generated graphics for the Open University's course material, including animated film sequences for television programmes. It can, however, also be used as a general purpose macrogenerator.

Basic Principles

GRAM is a macro-generator which has been designed primarily for interactive graphics although it is sufficiently general-purpose to be useful outside of graphics. Therefore it is possible to explain the basic operation 0f GRAM without specific reference to graphic input or output.

It has input and output streams of symbols which correspond to single computer words. The primitive concept of macro-generation is one in which a symbol in the input stream generates one or more symbols in the output stream which form some predefined correspondence with the input symbol. But it must be a little more sophisticated than that to be of any use.

With GRAM, until a special control symbol is met, every symbol in the input stream is merely copied across to the output stream. Therefore, (using lower case characters for the moment to represent symbols) the input stream "a b c d e f" would reappear at the output unchanged. This does not by itself seem to be very useful. However, the occurrence of the special symbol "(" in the input stream causes the symbol following it to be regarded as a macro-name and be replaced by a corresponding string of symbols (known as its macrodefinition) in the output stream. This is a macro-call, and must be terminated by the special symbol ")".

For example, if the macro-name "d" has as its macrodefinition the symbol string "x y z" then the input stream "a b c ( d ) e f" would be transformed on output into "a b c x y z e f".

But that is not all, for a macro-call can take arguments. Any symbols following a macro-name up to the closing bracket ")" are its arguments; ( b j k l ) represents the macro b called with arguments j, k and l. In a macro-definition, the special symbol # followed by an integer number n indicates that the nth argument in the macro-call should be inserted at that point when the macro is evaluated.

e.g. 
b is defined as p # 3 q r # 1 s # 2 t 
p ( b c h x) q  in the input stream becomes 
p p x q r c s h t q. 

Another vital point is that the macro-call delimiting brackets "(" and ")" can appear anywhere any other symbol can appear, which means that macro-calls can be nested to any depth inside argument lists or macro definitions. The rule is that the innermost calls are evaluated first, their results becoming part of the argument list of the next call out.

e.g.   
a is defined as   b # 1 c     
b is defined as   # 1 a  # 2 b  # 3   
Therefore       ( b ( a c ) )       
becomes first   ( b b c c )       
then             b a c b C       

Note also the effect of having a macro-call inside a macro-definition:

a is defined as # 2 ( b a ) # 1 
b is defined as # 1 c
Thus     ( a b c )
becomes  c ( b a) b 
then     c a c b. 

The stack

Each macro-call is actually evaluated only when its closing bracket is encountered, which takes care of the innermost calls first. This means that a macro name and its arguments must be stored prior to evaluation. The current argument list is assembled in a stack. When the first left bracket "(" is encountered, the destination of the incoming symbols is switched from the output stream to the stack. It is not switched back to the output stream until the last matching right bracket ")" has been encountered, whence the results of the outermost remaining macro call are delivered to the output stream. Each time a ")" which is not the outermost is encountered, the macro call contained between there and the last "(" is evaluated and replaced by its results.

e.g. 
A picture of the stack in course of evaluation: 
( v x j ( p z k e ( b i ) 
and evaluation of the last macro call according 
to the definition of b in the previous example gives 
( v x j ( p z k e i C ....... 

Likewise the source of symbols is switched from the input stream to a macro-definition when the first "(" is encountered, and is not returned to the input stream until the outermost macro-call has been evaluated.

External syntax of symbols

Single lower-case letters have been used for symbols in the above examples for the sake of clarity whilst introducing the concept. Since a single symbol in this macro-generator is a whole computer word (or at least 16 bits), a single character would clearly be inadequate for its representation on an external medium such as a teletype.

There are four classes of symbols:

(1) The special control symbols
such as ( ) and #.
(2)Macro-names
These are represented externally by a character string made up from the letters A-Z and the numerals 0-9, but always starting with a letter. e.g. ABC THING M45 X WIERDSHAPE34. A macro-name is terminated by a space, newline or one of the special symbols. Its maximum number of characters is only limited by the length of the input line.
Internally, the word representing the macro-name contains the address where its corresponding definition may be found.
Example of an input line: (DO AZ B2 THING)
Note that a macro is only evaluated when its name appears immediately after a "(". In any other position it is merely a symbol which happens to be a macro-name. A macro-name in an argument list may be subsequently evaluated by means of the following trick: Suppose DO is defined to be ( # 1 # 3 ) ( # 2 #= 3 ), the effect of the last example would be equivalent to (AZ THING) (B2 THING).
(3) Numbers
are just positive or negative integer literals internally which have no meaning other than themselves. Externally they are represented by a string of decimal digits optionally preceded by a minus sign, and terminated by a space, newline or special symbol. e.g. 101 4 -16 2048 0 -300. The symbol following a # must be a number.
(4) Alpha strings
are literals which represent strings of alphanumeric characters. They have no connection with macro names and are distinguished externally on the input side by being surrounded by quotes, e.g. "THIS IS AN ALPHA STRING".
They can also contain any of the special symbol characters without them being interpreted as such, e.g. "(ABC 23) WILL NOT BE EVALUATED, BUT WILL REMAIN AS PART OF THIS STRING, SO WILL # 2".
An alpha string may contain any number of characters and may occupy more than one word internally. The only exception to the one-to-one relationship between symbols and computer words is that an alpha string between quotes is treated as a single symbol, however many words it may occupy internally.

Output

Putting aside for the moment the question of graphic output, the appearance of the symbols in the output stream on a character printer is the same as for input, except that alpha strings are not surrounded by quotes. The reason for this is plain from the following example:

LONDON is defined as    "ENGLAND" 
PARIS  is defined as    "FRANCE"  
WHERES is defined as    #1 "IS IN" ( #1 )
therefore the input    
( WHERES LONDON ) will provide the output LONDON IS IN ENGLAND
( WHERES PARIS )  will provide the output PARIS IS IN FRANCE

Macro-definitions

Nothing has so far been said about how macros are defined. This is in fact done by calling the special macro DEF. DEF has the same calling syntax as any other macro, except that it is intrinsic, that is, it is not defined in terms of other symbols, but executes a special piece of program in the implementation language which transfers its arguments to the list of definitions. The first argument is the name of the macro being defined. Thus to define ABC as QB "N" (z3 2) H, one would input

(DEF ABC <QB "N" (z3 2) H>)

Diamond brackets

At this point it is necessary to introduce a new pair of control symbols, the diamond brackets < and >.

They have the effect of suppressing the action of any of the other control symbols lying between pairs of them. They can be nested to any depth, and the outermost layer of diamond brackets is removed each time the symbol item string is copied from source to destination. In the defining macro DEF they are necessary to prevent any macro calls in the definition from being evaluated while it is being loaded on to the stack as an argument of DEF.

Temporary definitions

Calling (DEF NAME .... ) again when NAME has already been defined, replaces its old definition with a new one. However, its old definition is not lost, since each entry in the table of definitions is organised as a push-down stack, the symbol-string on the top of the stack being used as the current definition. There is another intrinsic macro, OLD, which does the opposite of DEF. Calling (OLD NAME) deletes the current definition of NAME and restores the previous one. If NAME has only been defined once it causes it to become "undefined", and any subsequent calling of NAME will give a run-time error.

Graphic output

This is conceived merely as being an alternative interpretation of the output stream from that already described. On entry, GRAM is normally in ordinary output mode. After calling the intrinsic macro (GRAFOUT), all numbers in the output stream are henceforth interpreted as coordinates. Graphic output in GRAM is intended to be as independent as possible of the actual graphic hardware being used. The form of graphic output most commonly available is that of drawing straight lines between coordinate points on a grid, and GRAM is restricted to this form for the moment. Numbers arriving in the output stream are treated as x and y coordinates alternately in pairs. Each pair of numbers draws one line. It is assumed that the numbers correspond to the coordinate system of the device (most commonly 0 - 1023 on both axes) and the responsibility for scissoring off-the-screen lines must be taken by the output routine which obviously has to be written for a particular device.

Alpha strings in graphic output mode appear as alpha strings, the first character in the string being positioned by the previous coordinate pair.

There then remains the question of what effect the other two symbol classes, i.e. macro names and special symbols, have on graphic output. They would not normally reach the output stream, but it so happens that this particular form of graphic output needs something to indicate that a following coordinate pair represents a move to it without plotting a line, i.e. the start of a new series of connected lines. It is therefore expedient from the programming point of view to let any macro name or special symbol act as a move-without-plotting command. In practice, it is expedient to use a suitable undefined macro-name, such as $, for this purpose.

e.g.
$ xl y1 x2 y2 $ x3 y3 x4 y4 
would mean: 
move to x1 y1, plot a line to x2 Y2, 
move to x3 y3, plot a line to x4 y4

Graphic input

This presents problems with some kinds of input device. Something like the D-Mac digitizer is straightforward, as it merely provides number pairs for each point which can go straight into the input stream. It also has a character keyboard which enables one to insert macro names and special symbols.

The Tektronix storage tube display, on the other hand, uses the keying of a single keyboard character to return the graphic cursor coordinates. The actual character keyed is returned with the coordinates and is most conveniently used as a command code to signify the action to be taken with the coordinate pair. In these circumstances it is most convenient for the graphic input routine to present the input stream with five symbols representing a complete macro call, (C x y), where C is the character which keyed in the coordinate numbers x and y. C is then one of a range of macros with single-character names which do something appropriate with x and y.

It is obviously necessary to be able to switch between this special graphic input mode and normal mode otherwise the format of the input stream would he too limited. This requires the introduction of two intrinsic macros GRAFIN and E. GRAFIN switches to graphic input mode and (E x y) switches it out, x and y being ignored.

As an example, I will define two of the simplest Tektronix graphic input macros:

(DEF S <$ #1 # 2 > )             ... first point in chain of connected points 
(DEF L < (OUTPUT #l #2) #1 #2 >) ... line to x, y. 
Keying S gives the result $ x y. 

OUTPUT is an intrinsic macro which passes its arguments direct to the output stream whether or not the results of a macro call at that point would normally be destined for the output stream. Keying L therefore plots a line to x, y from the last point and passes the results x y.

Thus to digitize and store an image called PICTURE, one types in the following:

(DEF PICTURE (GRAFIN)   [RETURN]

GRAFIN is executed and the graphic cursor appears. Then one keys in coordinates with S or L, during which the stack looks something like this:

(DEF PICTURE $ x1 y1 x2 y2 x3 y3 $ x4 y4 x5 y5 ...

(GRAFIN) completely disappears, since it generates no results on to the stack. When the image is complete, key in E, and one is back to normal input mode.

Follow this by a closing bracket ) in order to execute DEF, and the coordinate string is defined under the name PICTURE. Note that in this case diamond brackets surrounding the coordinate string are unnecessary since it does not contain ( ) or #. Typing (PICTURE) will display the original image.

Grouping a number of subpictures under one name can be done as follows:

(DEF BODY < (HEAD) (TRUNK) (ARMS) (LEGS) > ) 
(BODY) will then display all of them. 

Graphic processes

So far it has been demonstrated how one can create graphic line-drawings, give them names, arrange them hierarchically in groups and re-display them. This by itself is rather limited unless one can also perform geometric operations such as translation, scaling and rotation. GRAM can readily be supplied with a set of intrinsic macros for performing simple diadic arithmetic operations such as (ADD a b), but they would be a very inefficient way of doing geometric operations on large numbers of coordinates. So intrinsic macros can be provided which perform certain complete geometric transformations on a whole string of coordinate pairs in one call.

Examples: 
(MOVE x0 y0 x1 y1 c2 y2 ...xn yn)
Result is the argument list, starting with  third argument, 
added to x0, y0 in pairs.  One would more commonly call 
a picture to be moved by name: 
(MOVE  x0 y0 (PICTURE) ) 
(SCALE sx sy (PICTURE) ) 
   Result is coordinates of PICTURE multiplied by sx sy in pairs. 
(ROTATE t x y (PICTURE) ) 
   Result is coordinates of PICTURE rotated t degrees about x, y. 

Any symbols other than numbers appearing in the string generated by (PICTURE) are copied without modification.

This highlights the fact that the system has to be able to distinguish between the different classes of symbols in their internal form.

Adding to the set of intrinsic macros

It is clear that the available set of intrinsic macros should be open-ended and variable, in order to serve different applications. In this way, programs written in the implementation language may be entered through a macro call. The only difficulty lies in establishing a hygienic method of linking new implementation-language segments into GRAM. In the present FORTRAN implementation, the intrinsic macros are accessed via a computed-GOTO (about the only way of doing it in FORTRAN). A new addition involves extending the computed-GOTO, adding a CALL to the new program segment followed by a jump back to the part of GRAM which handles the termination of a macro call, which is a bit messy. Also, the appropriate computed-GOTO number has to be entered against the macro name in the name-list. This is done by a special intrinsic-macro called DIN (for Define INtrinsic).

e.g. (DIN MULT 15), which defines the intrinsic macro MULT to be accessed via the 15th label in the computed GOTO. This is a convenient way of setting up the name-list for all intrinsic macros, apart of course from DIN itself, which must be built-in.

A better long-term approach to defining intrinsic macros would be to use the macrogenerator in its classical role of generating machine-language instructions. One could even employ the time-honoured technique of writing GRAM in itself.

Comparison with GPM

GRAM is basically an adaptation of Christopher Strachey's General Purpose Macrogenerator [1] to handle graphics more efficiently. It also bears a generic resemblance to some other stack-based languages.

GPM is a character-stream processor: its primitive symbol is a single alphanumeric character. Macro names are held internally as character strings, which necessitates a linear search down the list of names each time a macro is called. GPM therefore has a reputation of being extremely slow in execution, which was not a very important consideration in the application for which it was originally intended, i.e. implementing a CPL compiler.

There are three main ways in which GRAM differs from GPM, which were made primarily to improve efficiency for interactive graphics:

  1. A single-word binary integer as a primitive symbol. The basic data component in graphics is a numerical coordinate. In character form it would be very inefficient indeed both to process and to store.
  2. The linear search to match a macro-name occurs once only, on input. Thereafter it is replaced by the address of its definition. (This has been done at the expense of some useful tricks that can be performed with macro-names in GPM.)
  3. The whole of the working store, which includes the stack and the macro-definitions, is in the form of a linked list (with forward links only). Each symbol word has a corresponding link word, pointing to the next symbol. In GPM, on termination of a macro-call, all the results have to be copied back over the argument list. In GRAM, the argument list is merely unlinked and returned to free list, with savings in both time and program complexity.

Conclusions and general comments

Although various design measures have been taken to make it reasonably efficient in execution, GRAM is, by its very nature of being a stack-based interpretive language, likely to be a lot slower than an interactive system written in a completely ad hoc manner. But since it is primarily intended for use with a non time-shared stand-alone minicomputer + graphic display system such sluggishness is of no great importance when matched against the reaction and thinking speed of a single user. The bonus side is that the basic program is quite small, whereas a large number of interactive processes with multiple options may be constructed out of macro-definitions which are more compact than their FORTRAN or even assembly-language equivalents. Another useful feature is the ease with which one can test a new macro, simply by typing a call to it and getting the results straight back on the output stream without having to write an elaborate test program.

Because of its sluggishness, GRAM is not likely to be attractive for the production-run stage of animated movie-making, where efficiency is very important in face of large volumes of graphic output multiplied by 24 for each second's worth of animation. The most promising solution here is to separate the functions of composition and production; using GRAM's interactive talents to compose a graphic data-base [3] which is then handed over to be interpreted by a production program in a straight through manner without stacking operations.

Initial usage of GRAM has shown up certain weaknesses which suggest modifications and extensions. I will mention a few:

  1. The inability to treat a group of symbols as a single argument (as in GPM) is very limiting. It has become imperative, at the very least, to introduce an argument-replacement function in addition to #n which means copy all arguments from the nth to the end of the list. However, a more sophisticated argument-handling system is under consideration, involving a pointer which can be made to move along the argument list and stop when it has found certain symbols. This could be made to do a form of syntax analysis, and also, with the help of insertion and deletion functions, to perform editing operations on the stack (made possible by its linked list organisation).
  2. Because in GPM macro names are held as alpha strings rather than addresses, one can do some very clever operations making use of this fact. Strachey's paper [1] gives an example of how to achieve the effect of a conditional expression dependent on the equality of two symbol strings. To rectify this disability in GRAM would require intrinsic macros to convert between the different symbol classes. e.g. if (NAME "ABC") converts the string into the macro-name ABC, then
    ( (NAME a) (DEF (NAME a) RESULT1 ) (DEF (NAME b) RESULT 2 ) )
    
    gives the result RESULT1, if the string a is the same as string b, RESULT2. if a and b are different. It is a good test of understanding the system to be able to figure out why.
  3. In GPM, a definition which occurs in an argument list rather than the outer-most level is automatically deleted when the argument list is overwritten. This is generally desirable, but because of a difference in structure does not occur automatically with GRAM. Thus the above example should be terminated by (OLD (NAME a) ) (OLD (NAME b) ) to prevent the unlimited building up of redundant definitions. It would be possible to modify GRAM to do this automatically with a corresponding decrease in efficiency.
  4. The inclusion of an intrinsic macro to do conditional operations would be less cumbersome than the method described in (2), and the further inclusion of intrinsic macros to do arithmetic would greatly increase its general-purpose usefulness.

References

[1] "A General Purpose Macrogenerator" by C. Strachey, Computer Journal, Vol.8, pages 225-241.

[2] "TRAC, A Procedure-Describing Language for the Reactive Typewriter" by Calvin N. Mooers. Communications of the ACM, Vol.9, No.3, March 1966, pages 215-219.

[3] "A Computer Graphics Facility for the Open University" "A Data Base System for Computer Animation" (Open University internal reports, available from the author) .

P4: Definitions and GRAM Syntax

Kate scanned January 2021

The word item is used or the basic unit of stored information in the GRAM system. (In most implementations one item corresponds to one machine word, with a minimum length of 16-bits.

There are four types of items:

The types are uniquely distinguishable internally (This is done in the FORTRAN implementation by restricting each type to a particular numerical range).

INTEGER

Internal Meaning: integer constant restricted to the range -8191 to +8191 for distinguishability from other types.

External symbols: A string of digits 0-9 optionally preceded by a minus sign (123, -1, 2048, 0, -98, 2)

ALPHA PAIR

Internal meaning: A pair of alphanumeric characters.

External syntax: one or two ASCII graphic characters (control characters are not allowed) between string quotes ("AB" "C" "J*" "," "?" "3 ").

More than two " characters between a pair of string quotes is permissible, but will translate internally into more than one item.

Example:

"XYZ" = 2 items "XY" + "Z "

"ABCDEF" = 3 items "AB" +"CD"+ "E F"

NAME

Internal Meaning: a pointer to a macro definition or a primitive function.

External syntax: (1) Any string of letters a-Z or digits 0-9 beginning with a letter. The number of characters is only limited by the number which can be input on one line.

(2) One of the graphic symbols = ' + - * / $ @ % ? : & .

Example FR90 ABC $ B24 Z MK76AA @.

There is no syntactical distinction between a macro name and a primitive name; any name can be defined to represent either. However, all the graphic symbols except ? & and . are normally assigned to primitives.

All names can be redefined at any stage to be macros (by means of the primitives : or NEW) or primitives (by means of the primitive PRIM).

CONTROL SYMBOL

This is a type of item which has a primary control effect on the processor. It is built on to the system and cannot be redefined.

Internal Meaning         External Syntax
Macro Call delimiter     ( and )
Protecting brackets      < and >
Argument passer          #
Newline                  ^ or newline
Null                      !

DELIMITERS

The normal syntactic delimiter between items is a space or newline. But neither of these are necessary where the result is unambiguous, such as when one of the items is only permitted to be a single character.

Example
(:FILM<(:PRM 12AC##)(SRC FILM)>)
becomes
(  :  FILM  <  (  :  PRM  12  AC  #  #  )  (  SRC  FRM  )  >  )

Note that 12AC splits into 12 and AC since 12 is clearly an integer because it begins with a digit, and it is terminated by any non-digit. However, PRM12AC would be a valid name, so the space is needed between M and 1.

SPECIAL FEATURES OF INPUT SYNTAX

1 Implicit Call Brackets

When GRAM is used interactively from a keyboard, 99% of all input lines consist of simple macro calls, such as:

(EDIT FIG2)

In order to make life easier for the user, a pair of brackets are automatically inserted at the beginning and end of each input line, (they do not appear on the print out), so taking the above example one has only to type

EDIT FIG 2

in order to execute the macro EDIT.

However,inner nested calls must be bracketed,

EG typing
EDIT(CURRENTFIG)
is interpreted as
(EDIT(CURRENT FILE))

For the few occasions when one does not want the implicit brackets, they may be effectively cancelled by typing their opposite at the beginning and end of the line.

)123 456 789(

which is converted internally to 123 456 789.

Similarly, a long argument lst may be continued on the next line without primitive execution of the call:

Typing
NEW PIC 1000 1000 2400 3400 (
)1700 2300 45450 8450

would be treated internally as

(NEW PIC 1000 1000 2400 3400 1700 2300 4450 8450)

2 Comma

To facilitate the typing of several macro calls on one line, one may separate each one by a comma , which is translated internally into the two items )(. Thus typing SRC PIC,GET GREDIT, TEK, EDIT PIC means internally (SRC PIC)(GET GREDIT)(TEK)(EDIT PIC)

3. Square Brackets

The commonly occurring combinations of pairs of control symbols <( and )> may be represented externally as [ and ] respectively. The unwieldy item string (:ABC <(SRC PIC)(GET GREDIT)(TEK)(EDIT PIC)>) may therefore be written as :ABC[SRC PIC, GET GREDIT, TEK, EDIT PIC]

4.Comments

The character semicolon ; tells the input translator to ignore the rest of the current line. This enables macros stored on external files to be annotated with comments.

P5: Letter to BBC Open University Productions

Tony Pritchett 
32 Winchester Rd. 
London NW3 3NT 

01-586 1329 
John Richmond,Esq. 
BBC Open University Productions 
Alexandra Palace 
London N22. 
6 October 1976 

Dear John,

As promised, I am writing to tell you about the computer animation system I have recently got working on the Nova computer in Technology faculty. The system is called GRAM (for GRAphic Macroprocessor). I will list some of its features:

  1. It is interactive. One may sit down in front of a storage-tube v.d.u. and compose pictures using its graphic input facility like an "electronic drawing board". A script to animate the pictures may also be composed interactively, and putting the two together, one can view immediately any frame of the resulting sequences on the v.d.u. Unfortunately, it is not fast enough to display moving pictures.

    Such a system provides a considerable saving in time over existing batch methods of doing computer animation. It is possible to compose a very simple animated sequence inside a few minutes, but I would normally expect to take considerably more time and trouble over even the simplest sequence for the O-U.

  2. It can do 3D perspectives as easily as it can do 2D, either by supplying x, y, z coordinates for points in a 3D structure or by rotating flat 2D pictures about their x and y axes. GRAM displays the results as a "wire-frame" picture without hidden line removal. ANTICS MKII (at the Atlas Lab) can then take these pictures and convert them into a film with filled-in areas of colour, incidentally doing the hidden line removal at the same time, (see below).
  3. Complex mathematics (I don't mean in the real/imaginary sense) can be programmed into the system by writing subroutines in FORTRAN which are then plugged into GRAM. There is a built-in facility for doing this.

The GRAM system on the Nova at Milton Keynes cannot produce film directly, as it does not have the right hardware. This has to be done on the FR-80 microfilm recorder at the Atlas Lab, via tapes and the Atlas Lab's SMOG program.

The FR-80 can plot in colour direct1y on to colour film stock (negative or reversal, 16 or 35mm) without any registration problems.

There is also a system at the Atlas Lab which Colin Emmett and I have developed from the original ANTICS system which takes line images and scans them in to produce solid areas of colour ( and does hidden line removal at the same time). We haven't found a name for it yet, so we refer to it aa ANTICS MkII or SUPER ANTICS.

Time Scales

I am hoping for a turnround time of about a week for the simple moving graph type of sequence, using the Nova interactively and possibly handling more than one sequence at a time. However I would still have to allow much longer periods for the more sophisticated animations (one month or more).

The sequence of operations would be as follows:

  1. Initial briefing with producer (and/or graphic designer).
  2. Interactive composition on the Nova at Milton Keynes.
  3. Return to AP with polaroid shots of selected frames from v.d.u. for approval. If not approved repeat (2).
  4. Go to Atlas Lab with tape from Nova to transfer to FR-80.
  5. Send FR-80 output to film labs for processing.

Cost

This is very difficult to determine without any real-life operational experience with the system and without the following factors being known:

  1. How much the Atlas Lab are going to charge. It was £150 per hour computing plus £60 per hour FR-80 plotting for Barrie Whatley's job, but they may have put it up by now.
  2. Whether and how much Technology are going to charge for use of the Nova. There is a possibility that they might want to charge - it needs some careful politicking.

Having put forward these uncertainties, I am now going to stick my neck out and say that I would hope to do the simple moving graph stuff for under £100 per minute.

Colin and I have found that for the more sophisticated animation using Antics full colour shading, we have to quote £800 per minute minimum.

So there you have some ball-park extremes. Quoting "per minute" can also be misleading because the cost of computer animation is not nearly so dependent on footage than conventional animation, and more dependent on complexity. Thus a 30 sec sequence may cost £100, say, but extending it to 5 minutes doing the same thing will not put it up to £1000 but probably more like £300.

Type-faces for captions, etc

This is something you specially seemed concerned about. GRAM has no specific type-face permanently set up in it. They are digitised as and when they are needed - normally 3 or 4 hours work on the digitiser at the Atlas Lab.

Yours,

Tony

REFERENCES

1. A general purpose macrogenerator. C. Strachey, Computer Journal, Vol 8 No 3, 1965

2. Fortran IV: X3J3/90.4