KULSRUD(ID:5083/kul001)


Unnamed graphical language for pictorial manipulation, RCA 1967, Yale 1968

Stood as a general purpose translator to MAD, FORTRAN or ALGOL 60, depending on computer system. Had a Cartesian data structure, ass opposed to Ring or Matrix


Related languages
FSL => KULSRUD   Written using
MAD => KULSRUD   Target language for
KULSRUD => VIP   Influence

Samples:
References:
  • Kulsrud, H.E. "A programming system for electron optical simulation" RCA Rev. 28 (June 1967), pp351-365. view details
  • H. E. Kulsrud "A General Purpose Graphic Language" view details Abstract: This allows the languages to be compiled by standard
    techniques, thereby reducing the time required to imple-
    ment the language. Although the syntax of one-dimen-
    sional languages is not a natural medium for two-di-
    mensional problems, it is at present the only practical
    technique for making progress with graphic languages. Abstract: Interactive use of computers with graphic terminals will permit many new problems to be solved using machines. In order to handle a variety of applications, it is expedient to develop a general purpose graphic language that is useful on a number of graphic devices. A system has been designed to produce such a language quickly and cheaply. A model graphic language which has been developed with the system is presented.
    Extract: Introduction
    Introduction
    In order to utilize graphic equipment effectively, a number of graphic languages have been developed. Usually these languages are used for the generation and display of pictures [1, 2], although some applications have led to the development of languages for the analysis or interpretation of pictures [3, 4]. Clearly, what is needed is a single language that can handle both these aspects while containing features desirable in a general purpose language.
    Narasimhan [4] and others have shown that graphic languages can be successfully specified by their syntax.
    This allows the languages to be compiled by standard techniques, thereby reducing the time required to implement the language. Although the syntax of one-dimensional languages is not a natural medium for two-dimensional problems, it is at present the only practical technique for making progress with graphic languages. (Kirsch [5] has indicated how a two-dimensional syntax might operate for a simple problem.) Furthermore, it is convenient to first specify the syntax for an English-like or typewritten version of the graphic language. Then a translation can be made to suit the graphic equipment using light pen and control button sequences. Actual use of a graphic console usually requires both graphic and typewritten commands.
    In this paper the requirements for a general purpose graphic language are discussed and some of the inherent problems are indicated. A system for constructing and testing graphic languages is described, and finally, a model lang~mge which fits a large number of the requirements is presented. The model language is described for the typewritten form to facilitate understanding.
    Extract: Attributes of a Graphic Language
    Attributes of a Graphic Language
    Description and Manipulation. A primary requirement for a general purpose graphic language is the ability to describe, generate, and manipulate pictures. Several languages, for example Cad~t [1] and Pencm [2], have adequately met these requirements. Many graphic applications merely prepare pictures for output, for example, design layout. To describe a picture the language must have commands for the placement and intensity of points, line segments, and text within a picture. What is meant by "line segment" depends on the hardware and on the time available to the designer for software development. A complete language should allow for straight line segments,
    segments generated by conic sections, and segments produced by an arbitrary function.
    Manipulation provides for such operations as rotation, rearrangement, merging, and deletion of subelements of the picture. Some of these functions can be carried out on the hardware level [6]. Completeness and convenience require the retention of several pictures, though only one picture can be processed at a time. One of the major difficulties in the design of the manipulation language is the selection of all effective scheme for labeling subclements of the picture.
    Analysis. A graphic language should also allow for the analysis of pictures. Pictures may be generated either through the graphic language or through some hardware device such as a digital photograph scanner [7]. Analysis requires commands that Call examine and locate special features in the picture. Also, analysis may be concerned with the relation of one subelement of the picture to another.
    How the analysis is actually carried out (i.e. implemented) depends very much on the internal data structure. Although the problem of data structure is a central one for graphics, it should not affect the graphic language design directly. Several very interesting schemes, such as Sutherland's ring structure [6] and Freeman's rectangular array encoding [8], have been invented for graphic data storage. However, there are applications (e.g. the solution of partial differential equations by relaxation techniques [9]) for which a cartesian grid structure is most useful. Probably a complete graphic system would contain two or more data structures with appropriate translation routines.
    Checking Validity. Another major requirement on a graphic language is that it incorporate a method for checking the validity of pictures. This aspect is especially important when the graphic data serve as input for another program or for a remote computer. Such validation should take place prior to execution, but it might be specified at art earlier time. There is some overlap in the analysis and validity functions, though the aim of each is different. Both functions require commands to deal with topological and geometric properties.
    General Aspects. It is especially important to provide a method for associating the data list or description list with points or subelements of a picture, particularly if such a list is required by the application program.
    A number of other features are also desirable in a graphic language. First, much dynamic flexibility should be provided. This will exist if algorithmic-type statements are introduced into the lm~guage, especially in the description part of the language. Of course, this feature will be more valuable for the typewritten version of the language.
    Procedures or subroutine capabilities are essential. These will allow introducing into the picture new and unusual figures which are to be reproduced at various locations with varying scales and orientation. Naturally the language should be interactive to reduce time delays and to give immediate response to trivial errors. Finally,
    the language should be incremental, that is open-ended, to permit additions to programs without recompilation. Extract: Conclusion
    Conclusion
    The model of a general purpose graphic language presented above is actually a first approximation to a complete language. With the techniques of Section 3, more features can be added to this language as needed. Limited use of the model language has indicated the need for some additional commands. More commands, or perhaps built-in subroutines, for locating particular features and for comparing subelements are needed. .Am iteration command (such as an Algol (for statement}) would reduce code as in the case of the subroutine SCAN of Example 2. The data structure should also allow for arrays.
    A great deal of knowledge nevertheless would be gained by the use of the model language on various graphic devices and different applications. As yet our experience with graphics is limited because of the high cost of the equipment and the complications in implementation. The system described here permits access to graphic equipment with a small investment in programming. When the results of more complete experience become available, the implementation can be optimized.
    Some aspects of the model language may be considered difficulties. A reserved first word structure is employed to incorporate algorithmic commands and gain access to programs coded in other languages. Though this approach saves scanning time (using a jump table for the first operation in the syntax analysis), it has the disadvantage that the user must remember many special words. The reserved words can be used for variable names provided they do not appear on the left-hand side of assignment statements. This difficulty may be reduced by introducing abbreviations, such as PT for POINT, as is done in some languages (Mad [15] and PL/I [16]).
    Much of the command interpretation is carried out through subroutine calls. Though these subroutines can be written in any language for which a compiler is available, efficient code will not necessarily be produced. Also, these routines have been written for a data structure that is optimal for the command coding rather than for the system as a whole. It may prove costly to have to eonvert back and forth from one data structure to another to make command action efficient. Greater experience with various applications will be necessary to resolve this problem.
    The need for a general approach to graphics has been pointed out by L. G. Roberts [17] who advocates a generalized translator which handles languages for a variety of descriptive applications. We would like to go one step further in the plea for generality by suggesting that an even more general purpose language than the one described
    in this paper be developed. The use of an incremental-interactive metacompiler system provides a cheap and efficient way to produce such a language. Extract: A System for Language Design
    A System for Language Design
    In designing a language it is important to be able to make changes and deletions without reassembling the entire compiler. Trivial errors should be eliminated immediately. Interactive computer systems that treat programs as files have these advantages. Furthermore, if compilation occurs on a line-by-line basis (incrementally) rather than on a program basis, typographical errors will be reduced, and immediate testing of language syntax will be possible. A design system should have many error diagnostics and self-explanatory error comments. The design system should be easily accessible so that as many users as possible can participate in the testing of the language.
    A metacompiler, or a compiler-compiler [10], provides the basis for a system of this type. The system consists of two passes: The first pass, phase 1, accepts the language syntax and produces compiler code as its output; the second pass, phase 2, compiles and executes programs in the new language. These two phases can be linked together in a single machine run of an interactive system. Incremental compilation by the metacompiler and the output compiler produces open-ended programs which can run at M1 points in time. Thus in a single machine run (or session) the syntax and test programs for a language addition can be processed. Figure 1 depicts the action of phase 1;

    Figure 2 that of phase 2.

    The system described above consists of the following elements:
    (1)  A metacompiler which accepts syntax for graphic-type  languages.  This  metacompiler is  interactive  and incremental. It accepts input statements which combine syntax and semantics on a line-by-line basis, and it produces parts of a new compiler [11]. The output code for the compiler is either added to the old version of the graphic compiler or substituted for parts of the compiler. Naturally the metacompiler is a one-pass system. An example of combined syntax-semantic specifications can be found in Table I.

    (2)  A growing library of semantic routines which are part of the new graphic compiler.
    (3)  A  graphic compiler which is  composed  of three parts. (See Figure 3 and contrast it with [10].)

    First, there is the executive part of the compiler, which is a copy of the executive part of the metaeompiler; next are the pieces of scanning code and semantic routine calls produced by the metacompiler; and third, there is the library of semantic routines, which are partly produced by the metacompiler and partly hand-coded.
    (4)  An operational executive which controls computation in phase 2. This executive decides when compilation is to occur, when execution is possible, and when debugging information is to be issued2 Use of the executive permits debugging on the graphic language level.
    (5)  A library of programs in any language which has previously been compiled into a form compatible with the graphic output language. These routines are accessed at execution time in phase 2. Some of these library programs are the actual implementation of the graphic commands; others are the routines pertinent to the application.
    This system has been written and run on an IBM 360 computer. Some of the routines have also been run on the RCA 70/45. The metacompiler (1), semantic routines (2), graphic compiler (3), and operational executive (4) have been coded in 360 assembly language. The library of programs (5) is in various languages. Output from the graphic compiler is in Mad, a dialect of Fortaan, or the 360 machine language. When the algorithmic languages are used, the output code is fed into a second compiler before execution. This method has been useful for testing syntax, but it is too slow for applications. When machine language is used the algorithmic syntax is incorporated into the graphic compiler.
    In using a true graphic device, such as a cathode-ray tube with a light pen, it is necessary only to change the symbols of the syntax input to the metacompiler. Thus, for example, the word "LINE" might be replaced by the machine symbol or order for unblanked beam movement. Extract: A Model Language
    A Model Language
    In this section a graphic language which has been developed with the system is described. This language embodies the ideas discussed in Section 2 and is described as a model; for though complete in itself, its use has indicated directions of extension.
    A graphic language will process the following data types:
    Variable                Statement label
    Point                     Subroutine label
    Line segment                Procedure
    Subelement                   Function
    Region                          Graphic from library
    Frame                          Application routine from
    library
    All statements in the language consist of a label field followed by the command. Graphic commands begin with a special word. If no special word is recognized the statement will be scanned for an equal sign. The presence of an equal sign will indicate that the statement is an assignment statement; the absence will indicate that a subroutine call is to be generated. Many fields will have default conditions.
    Throughout this section amending lists of parameters or text are not illustrated. Using the notation STEXT$ and #Data# will permit introduction of these at proper points in the program.
    Extract: A Model Language (A) Commands for Description
    Commands for Description
    LABEL     SCALE       X = el,e2,e;~ ; Y = e4,es,e6
    The purpose of this statement is to set the ranges of the two dimensions. The "X =" and "Y =" are not required and any w~riable names (e.g. "TEMP =") may be substituted. However, the first expressions will refer to the X-direction in the picture and the second set to the Y-direction. All e's are the usual type of algorithmic expression and correspond to those allowed by the given algorithmic syntax (e.g. Algol [12]). e~ and e4 are the minimum values of the parameters; e2 and e5 are the maximum values; and e3 and e6 are the distances between grid lines (for the display). If e3 or e6 is omitted, a value of one will be assumed. This statement also clears the current memory picture.
    LABEL     POINT       NAMEP = ebe2;e~,e~;...;en,e,~.l
    This statement evaluates e~ and e2 , declares NAMEP as a point, assigns NAMEP these values, and plots the point NAMEP in the picture. Then the point e~, e4 is evaluated and plotted, etc. If "NAMEP = " is omitted, there is no declaration and assignment. Text or additional data may be amended to NAMEP by the method described above, for example:
    POINT       NAMEP = el,e2$Corner$
    FinMly, if el, e2 is replaced by a single variable, this right-hand side is understood to be the name of a point. Henceforth in this paper we adopt the notation p~ to stand for either the name of a previously assigned point or a pair of expressions separated by a comma.
    LABEL     LINE        NAMEL  = p,;p2;p3;...;p~
    This statement evaluates p~ and p2, declares NAMEL as a line segment, assigns NAMEL these values and plots a straight line from p~ to p2 in the memory. Then Pi is evaluated and a line drawn from p2 to p3, etc. Omission of "NAMEL =" again eliminates the assignment and declaration. If p~ is omitted (statement begins with a ;) a line is drawn from the last plotted point (or end point of a line) to p2 . It is also possible to put only a line name on the right-hand side. This variable will be declared a line if it has not been so previously. However,
    the line on the right-hand side must be assigned a value before the statement is  executed.
    LABEL     ARC         NAMEA ~ pl;p2;pa;l
    This statement declares NAME A as an arc line segment, assigns it the calculated values of pl, p2 and pa, and draws a circular arc clockwise from pl to p2 whose center is at p3. If ";l" is included, the arc is drawn in the counter-clockwise direction.
    FNAME   FUNCT      X = f~(Y); Y = f2(X)
    This statement defines a function of X and a function of Y, which are called FNAME. The functions do not need to be related. The fl and f2 are standard algorithmic statements. One may be omitted, but the name of the parameter for use by the other must be included. For example, a function for generating the conehoid of Nicomedes where A and B are parameters would be:
    CONCH   FUNCT   X; Y= ~QR.TF(((B • X)/(X - A))
    ,2 - X**2) LABEL     CURVE      FNAME; X = el,e~,e3;Y = e4,e~,e~
    This statement causes the function named FNAME to be evaluated and the points plotted in the picture for X equal to el through e2 in steps of e3 and for Y equal to e4 through e5 in steps of e6 . If e3 or e6 is omitted a step size of one is assumed. Either group may be omitted, but the semicolon must remain. "X = " and "Y = " may also be eliminated as the first group will serve as parameters for the second function in FNAME, and vice versa.
    Extract: A Model Language (B) Commands for Manipulation
    B) Commands for Manipulation
    LABEL     PRINT       a,b,...,c
    PRINT without a list is a command which produces an output version of the picture being generated. In some graphic devices plotting of points will ea ase them to appear automatically on the output device, and the PRINT command without a list will not be used. The names in the list can specify entities to be superimposed on the output picture but not kept in the memory. Some of the possible names in the list are:
    AXIS         Prints the lines of X = 0 and Y = 0.
    BOUNDS    Prints the boundary lines for the picture (useful
    on photographic recordings). GRID         Causes a cartesian grid to appear on the output,
    device. LOGGRID   Causes a log (or semilog) grid to appear on the
    output device.
    LABEL     STORE       PICT
    This statement causes the picture currently being worked on to be stored in the stack of pictures under the name PICT. PICT is declared as a frame.
    LABEL     GET          P[CT
    This statement replaces the picture in memory with the picture previously stored under the name PICT.
    LABEL     NAME        SUBE;NAMEP,N AMEL,...,N AMER
    This statement provides for the labeling of subelements in the picture currently in the memory. The entities listed, for example, points, lines, curves, or calls to graphic subroutines, will be linked together and fetched when the name SUBE is used. SUBE is declared a subelement.
    LABEL     COPY         PICTl;PICTi,SUBEu...,p1;...;PICTn
    This statement provides for the merging of elements in other frames into the memory held picture. Elements in the list may be a frame name followed by a semicolon which causes that entire frame to be copied into the current picture. Frame names followed by. a list of subelements will cause only those subelements of the frame to be copied.
    LABEL     ROTATE   SUBEi,   THETA1,'pi;...;SUBEn,
    THETAn , Pn
    This command rotates the subelement named SUBE^ THETAi degrees about the point px, etc.
    LABEL     ERASE       SUBE, PICT.NAUEP,...,N AMEL*
    This command provides for the deletion of entire frames and subelements in the current picture. If an element such as a line is specified, only that line will be eliminated from the picture. If an asterisk is appended to the name, all references to that line, including its subelements (in the case of a line, all points along it), and its presence in any subelements will be eliminated. If no list is appended the current memory picture will be cleared.
    Extract: A Model Language (C) Commands for Program Control
    C) Commands for Program Control
    LABEL     BEGIN       N AMEPR(J,J,...,K)
    This if the first statement of the procedure called NAMEPR which has the parameters I,J,---,K.
    LABEL     END
    This statement signifies the end of the procedure.
    LABEL     GO TO       LABEL!
    This statement transfers control to the statement labeled LABELI.
    LABEL     GO TO       LABELI, WHEN g
    This statement transfers control to the statement labeled LABELI when the Boolean statement g is true; otherwise control is passed to the next statement. Boolean statements have the form allowed by the algorithmic syntax for instance, (^L LE. B), indicates A less than or equal to B.
    LABEL     STOP
    This statement terminates execution and returns control to the user.
    START  LABELI, STOP LABELJ
    This statement indicates execution should be started at the statement labeled LABELI and ended after the statement labeled LABELJ has been executed. Omission of LABELI will cause the program to start at the first compiled statement. The stopping point may also be omitted. This statement has no LABEL as it is not part of the compiled program.
    Extract: A Model Language (D) Commands for Regional Analysis
    D) Commands for Regional Analysis
    Some analysis functions can be carried out using the concept and data type of a region. A region is defined to be a set of connected points all of which have, or all of which have not, a certain property. A point is connected to another if a chain of nearest neighbor moves can be constructed between them. Each point in the picture will be assigned to a region by means of a region snap. The snap, a piece of software, creates an auxiliary frame in which each point is assigned a region name. A method for assigning the names is presented by Rosenfeld and Pfaltz [14]. A region snap can be printed by listing REGION after a PRINT command. LABEL     REGION    NAMER = px (or h) #PROP#
    This statement causes the region containing the point pi (or the line k) to be named NAMER. On execution of this statement a check first will be made to see if there is a valid region frame for the property PROP. If new data have been entered into the picture since the snap, or if no frame exists, a new snap will be made. The regions will be assigned names composed of the first four characters of NAMER followed by two digits. The region containing pi will then be assigned the name NAMER. If "NAMER =" is omitted from the statement the regions will be named with an internally generated label. If the property is omitted, the property of "plottedness" (black spot in the picture) will be assumed. If the right-hand side is omitted, only the region snap will be executed.
    LABEL     CONECT   pupy, I; FNAME
    This command is used to check whether two points are in the same region and if the FNAME curve connecting the points is in the region. On execution, the need for a region snap will first be ascertained. If it is necessary to make a snap, the last used value of PROP will be assumed. When ";FNAME" is omitted the variable / is set to zero if pi and pi are in the same region; otherwise I is set to one. If FNAME has the value LINE, a check is made to see if every point on the straight line joining p^ and pz is a member of the same region. If the value of FNAME is that of a function statement, all points on the curve from T>x to pi generated by FNAME are checked for presence in the region. Again, I is set to zero for success, to one for failure.
    LABEL     ADJAC       kr, fc2; I
    This statement provides a means for checking the adjacency of the entities kt and k2. k may be a point, line, arc, or region. Upon execution the status of the region snap is first checked, and a new one is made if necessary. If k\ and k2 are in the same region the variable I is assigned
    the value zero. If the entities are in adjoining regions, I is set to one; otherwise I is set to the number of regions plus one intervening between the region containing k~ and the region containing k: .
    LABEL     INTERX    11; 12; pl
    This statement is used to determine where the lines h and 12 intersect. If they intersect within the picture, pl will receive the intersection value; otherwise p~ will be set to some special value.
    LABEL     DIST        pl; p2; I
    This statement is used to determine the number of steps from p~ and p2. A step is made by a move to a nearest neighbor. I is assigned the minimum value for the number of steps necessary to get from p~ tq.p2 while staying in the same region. If p~ and p2 are not in the same region, it is not possible to calculate the distance.
    Extract: A Model Language (E) Commands for Topological Analysis
    E) Commands for Topological Analysis
    The following commands will generally be used to check the validity of prepared pictures.
    LABEL     WITHIN    SUBE1; SUBEe; I
    This statement is used to check whether the subelement SUBE~ lies within the subelement SUBE2. A zero is stored in I if it does; a one is stored in I if it does not.
    LABEL     SEPAR       SUBE~; SUBE2; I
    This statement is used to verify whether the two subele-meats are separate. If there are no intersections of lines or points and the one figure does not lie within the other, then I is assigned a zero; otherwise it is assigned a one.
    LABEL     SIMPLY    SUBEb I; SUBE2, J; ,..;SUBE,, K
    This statement is used to verify whether a frame or a subelement is a simply connected region. If no list is specified, the entire current picture is scanned. If a subelement is specified, then only that subelement is scanned. A scheme for checking for simply connected curves has been developed for problems using a relaxation solution of partial differential equations [14]. I is assigned a zero if the entity is simply connected; otherwise it is assigned a one.
    Extract: A Model Language (E) Commands for Topological Analysis
    Table II contains a list of all the available commands.

    A graphic compiler for the model language has been generated as discussed in Section 4. This compiler, in 360 language, translates graphic statements into Mad statements. These statements are then translated into machine language by a Mad compiler. Though this scheme has the effect of increasing the compilation time and removing the advantages of incremental compilation, it permits concentration on the graphic aspects of the language. Routines for carrying out the graphic functions are written in FoRtRan or Mad, translated into machine language, and kept as a library. A cathode-ray tube with programmed camera is used for implementation of the PRINT command.
    Extract: Conclusion
    Conclusion
    The model of a general purpose graphic language presented above is actually a first approximation to a complete language. With the techniques of Section 3, more features can be added to this language as needed. Limited use of the model language has indicated the need for some additional commands. More commands, or perhaps built-in subroutines, for locating particular features and for comparing subelements are needed. .Am iteration command (such as an Algol (for statement}) would reduce code as in the case of the subroutine SCAN of Example 2. The data structure should also allow for arrays.
    A great deal of knowledge nevertheless would be gained by the use of the model language on various graphic devices and different applications. As yet our experience with graphics is limited because of the high cost of the equipment and the complications in implementation. The system described here permits access to graphic equipment with a small investment in programming. When the results of more complete experience become available, the implementation can be optimized.
    Some aspects of the model language may be considered difficulties. A reserved first word structure is employed to incorporate algorithmic commands and gain access to programs coded in other languages. Though this approach saves scanning time (using a jump table for the first operation in the syntax analysis), it has the disadvantage that the user must remember many special words. The reserved words can be used for variable names provided they do not appear on the left-hand side of assignment statements. This difficulty may be reduced by introducing abbreviations, such as PT for POINT, as is done in some languages (Mad [15] and PL/I [16]).
    Much of the command interpretation is carried out through subroutine calls. Though these subroutines can be written in any language for which a compiler is available, efficient code will not necessarily be produced. Also, these routines have been written for a data structure that is optimal for the command coding rather than for the system as a whole. It may prove costly to have to eonvert back and forth from one data structure to another to make command action efficient. Greater experience with various applications will be necessary to resolve this problem.
    The need for a general approach to graphics has been pointed out by L. G. Roberts [17] who advocates a generalized translator which handles languages for a variety of descriptive applications. We would like to go one step further in the plea for generality by suggesting that an even more general purpose language than the one described
    in this paper be developed. The use of an incremental-interactive metacompiler system provides a cheap and efficient way to produce such a language.

          in [ACM] CACM 11(04) (April 1968) view details
  • Smith, Lyle B. "A Survey of Interactive Graphical Systems for Mathematics" view details Extract: Kulsrud
    Kulsrud (1968)--describes a general purpose graphic language to handle generation and display, as well as analysis of pictures. The language was developed at Yale University, New Haven, pen," a novel, high-speed, input/output device for CRT display systems, developed at the Electronic Systems Laboratory, MIT;

          in [ACM] ACM Computing Surveys 2(4) Dec1970 view details