Tree-based list processing language 

List processing language, influenced by EOL.

Jurg Nievergelt, Computer Science, Univ. Illinois and L. Lukaszewicz, Institute of Mathematics, Polish Academy of Science, Warsaw, Poland. 1968-69

"Bounce-and-skip is based on two principles: first, to allow a programmer to delay using the outcome of a test indefinitely, and second, to make the entry and the exit of begin-end blocks conditional upon the last test performed."

Had ternary boolena values - true false and neutral

Related languages
EOL => NUCLEOL   Evolution of

  • Nievergelt, J., et al., NUCLEOL -- A Minimal List Processor, Report No. 324, Dept. of Computer Science, Univ. Illinois, Urbana, Ill. April 1969 view details
  • Nievergelt, J., Fischer, F., Irland, M. I., and Sidlo, J. R. "NUCLEOL - A Minimal List Proceqsor" Proc. Purdue Centennial Year Symposium on Information Processing, 1969 pp. 92-103. view details
  • Nievergelt, J. and Irland, M "Bounce-and-skip. A technique for directing the flow of control in programs" view details Abstract: A new technique for directing the flow of control in block structured programs is described. It
    allows a programmer to delay using the outcome of a test indefinitely, and to make the entry and
    exit of begin-end blocks conditional upon the last test performed. It was designed as a low-level
    technique in terms of which all the block structure control statements common in high-level
    programming languages can be implemented easily and efficiently. This technique is the main
    tool for directing the flow of control in the programming language NUCLEOL, and is considered
    to be particularly useful for program debugging. Extract: Bounce and skip
    Providing alternatives to the go to statement is one of the distinguishing features of high-level programming languages. Whether one considers such alternatives to be merely a convenience to the user, or whether one takes the attitude that they should replace go to statements entirely (see Dijkstra, 1968), it makes sense to investigate new techniques for directing the flow of control in programs, to supplement such well-known constructions as the do-loop and the if-then-else statement. We present here such a technique, called 'bounce-and-skip', which is incorporated in the programming language NUCLEOL (Nievergelt et al., 1969). In fact, because of the special purpose nature of the language, NUCLEOL has no labels and go to statements in the conventional sense. Bounce-and-skip is the main tool for directing the flow of control in NUCLEOL programs, and we have come to regard it as a very versatile technique for block-structured programming languages.
    Bounce-and-skip is based on two principles: first, to allow a programmer to delay using the outcome of a test indefinitely, and second, to make the entry and the exit of begin-end blocks conditional upon the last test performed. The first of these principles has long been used in computer hardware in the form of a 'condition register', while the second one is new. The simple device of letting a condition register or 'test-variable' control the block structure of a program provides an easy and efficient way to implement all of the common control statements of high-level languages, such as if-then-else and for statements, conditional expressions, or case statements.
    Bounce-and-skip works as follows. The outcome of all tests is automatically recorded in a variable T, which may assume (at least) three values :
    N, for 'neutral', is the initial value, and in general indicates that the outcome of the last test performed has already been used;
    S indicates that the last test performed was successful ;
    F indicates that the last test performed failed.
    Each BEGIN and each END has a 'protection attribute', which is a list of the values of T under which control can enter or leave the corresponding block. If control enters through a BEGIN or leaves a block through its END, then the variable T is reset to N (neutral). If control cannot enter through a BEGIN, then it skips the block, while if it cannot exit through an END, then it bounces and positions itself just after the matching BEGIN. In the case of both skipping and bouncing, the test variable T retains its value.
    The following examples illustrate the rules which govern bounce-and-skip :
    Esample 1 : 1 TEST condition
    2 BEGIN (S)
    3 END (N)
    4 BEGIN (F)
    5 END (N)
    6 -
    This bounce-and-skip block structure corresponds to the statement 'IF condition THEN P1 ELSE P2'. If the TEST on line 1 is successful then control enters the block PI through the BEGIN on line 2. Thereafter the test variable T is reset to N, and assuming it is still (or again) neutral at the end of PI, control will exit through the END on line 3. It will then skip block P2 (which is 'protected' by the absence of N and S in its attribute list) and continue on line 6. Analogously, if the TEST on line 1 had failed, block PI would have been skipped and block P2 executed. In either case, execution continues on line 6 with a neutral test variable.
    Example 2 : 1 BEGIN (N, S, F)
    2 P
    3 TEST
    4 END (S)
    This structure is a do-loop. Because all possible values of T are listed with the BEGIN on line 1, this block is 'unprotected' and control enters it in all cases. Thereafter, as long as the TEST on line 3 fails, control bounces back to line 2, and P gets executed. If it succeeds, control exits through the END on line 4.
    Bounce-and-skip is a particularly useful tool for debugging programs, if the user is allowed to interfere, by means of setting parameters, into the interaction between flow of control and block structure. E.g., every END might have a count associated with it, which gets reset to zero every time control passes, and gets incremented by one each time control bounces. The user might specify a limit L (either for all or for a particular END) such that if this count exceeds L, some systems action gets invoked.
    In NUCLEOL, the variable T may also assume a value W ('wrong'), which gets set whenever erroneous conditions arise. Hence blocks may be protected from being entered in the W state, one can count how many BEGIN'S or END'S were encountered while T had the value W, and the user can specify that some system action occurs whenever this count exceeds some limit.
    We considered other rules for setting and using the test variable T in addition to the ones described above.
    E.g., if T were a pushdown stack, the current value at T could be pushed down every time a block is entered (and a new value N put on top), and the stack could be popped when control leaves a block. We could not see any advantage of this scheme over the one we chose. In both cases, the outcome of a test is available only at the same level of block nesting at which the test occurred, the only difference being that in one case the current value of T is permanently lost upon entering a block, while in the pushdown case it is only temporarily lost.
          in The Computer Journal 13(3) view details
  • Nievergelt J and Lukaszewicz L. "NUCLEOL -- a tree-processing language" in Computers and automata, J. Fox (Ed.), John Wiley ~ Sons, New York, 1972, pp89-104. view details
          in The Computer Journal 13(3) view details
  • Sammet, Jean E., "Roster of Programming Languages 1972" 196 view details
          in Computers & Automation 21(6B), 30 Aug 1972 view details
  • Sammet, Jean E. "Roster of Programming Languages for 1973" p147 view details Extract: NUCLEOL
    A language which tends to simulate a computer specifically adapted to list processing. Strongly influenced by EOL. Definition and implementation consist of a pen interpreter plus postulates which relate certain functions to each other.
          in ACM Computing Reviews 15(04) April 1974 view details
  • Stock, Marylene and Stock, Karl F. "Bibliography of Programming Languages: Books, User Manuals and Articles from PLANKALKUL to PL/I" Verlag Dokumentation, Pullach/Munchen 1973 421 view details Abstract: PREFACE  AND  INTRODUCTION
    The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one.

    There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages.

    The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM.

    Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) .

    It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers.

    The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA).
    As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found.

    It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel.

    We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work.

    Graz / Austria, May, 1973
          in ACM Computing Reviews 15(04) April 1974 view details
  • Williamson, N. F. review of Nievergelt and Lukaszewicz 1972 view details Abstract: NUCLEOL is intended to be a small system for processing tree-structured data which can serve as a basis for implementing higher-level tree-processing languages conveniently. The main part of the paper is an informal introduction to a revised version of NUCLEOL. The designers' concern with the problems of formal definition and implementation has led to an unusual, informal presentation. Since they regard the definition of a language as being equivalent to the definition of a machine to carry out the computations prescribed by programs in the language, they introduce the concept of state and state transition as a part of the informal language description.

    The most interesting and powerful features of the language stem from its use of linear representations of rooted ordered trees for both data and instruction segments, and from the tree- addressing scheme used to reference both data and instructions. Trees are represented in NUCLEOL by well-formed strings (WFS). A state is a set of WFS which contains all the information required to execute the computation determined by a program and data. Actual imply mentations (which do exist) are extensions of the basic language described in the paper. From the program fragments displayed, it would appear that NUCLEOL programs, like LISP programs, are infested with parentheses. It is hoped that a different syntax would make NUCLEOL more convenient. One possibility is described in a paper by C. Christensen [ "An introduction to AMs~T/L, a diagrammatic language for list processing," in Proc. Second Symposium on Symbolic and Algebraic Manipulation, S. R. Pctrick (Ed.), ACM, New York, 1971, 248-260 ] .

          in ACM Computing Reviews 14(05) May 1973 view details