Trac Implementation

This is a dump of the documentation I have on Trac. It's html files, which I displayed in Firefox and then cut-n-pasted. Hopefully it won't torque too badly when wikified.

TRAC Language: T64 Version

TRAC T64 | TRAC Language Home TRAC, A Text-Handling Language

by C. N. Mooers and L. P. Deutsch (1965) Paper presented at the 20th National Conference of the Association of Computing Machinery, Cleveland, Ohio, August 1965.

THE TRAC SYSTEM for Text Reckoning And Compiling was developed as a software package and user language to go with the reactive typewriter. Design goals included the attainment of a concise and efficient input language, a straightforward philosophy and a high order of logical versatility. The external and internal forms of the TRAC language are the same. TRAC can accept, name, store, operate upon in any way, and emit any string of characters that can be produced on a teletypewriter keyboard. Any string can be treated at any time as text, name, or program.

This paper describes the design decisions that went into the construction of the TRAC language and system. The acronym TRAC stands for "text reckoning and compiling" 1) The TRAC system had its genesis in the need for a general tool for dealing with text. In its later stages, TRAC developed in parallel with the evolution of the reactive typewriter concept; 2) TRAC is now running in a time-shared environment, and is currently undergoing testing and operational refinement; 3) In preliminary assessment, TRAC appears to exceed the design targets set for it.

By text is meant any string of characters (alphabetic, numeric, punctuation, other signs, format control and signal control characters) which can be generated from a teletypewriter keyboard, or any other keyboard, or which can control the printing action of a teleprinter machine, or can control the action of any other device.

By dealing with text is meant any effectively definable operation upon characters, strings of characters, or their code representation. Such operations may include making corrections and insertions in text, storage of text for later use, retrieval of text, re-formatting of text and page make-up, data formatting for numerical computation, simple numerical computation, character recoding, and many other possibilities.

By reactive typewriter is meant a teletypewriter, or typewriter with teletypewriter capabilities, connected by telegraph line to a multiple access, time-shared computer with large storage capabilities. Low cost, full upper- and lower-case character capabilities, and convenient immediate responsiveness are important elements of the concept of the reactive typewriter (2).

The TRAC system can be thought of as the "genie at the other side of the keyboard" for a person using the reactive typewriter. Such a person may be a scientist doing a computation, a stenographer correcting a legal brief, or a librarian composing a catalog card. Each user should have a set of procedures that can be called, used, and even redefined at his keyboard. These procedures should be callable in the TRAC language directly, or in English or "plain language" with intervening TRAC control. A subset of the TRAC language should be so simple in concept and use that a stenographer or librarian can use it constructively, while the full language should be of sufficient power so that it can be used to formulate any well-defined procedure. TRAC should secure these ends through a common-sense conceptual approach, as opposed to an approach requiring a high order of indoctrination in some system of symbolic logic, or an extensive background in computer programming notions and methods.

Since the procedures written in the TRAC language are carried out interpretively, the versatility of TRAC occurs at the cost of lower absolute efficiency than for the same procedures written in assembly language programming. Therefore it is not intended that TRAC be used in large batch production jobs such as partial differential equation solution, matrix inversion, sorting, large file management, language translation; character recoding, and the like. On the other hand, TRAC would be economical for on-line attended operation in letter writing, editing, bookkeeping, data formatting, computer program writing, logical experimentation, and other task where continuous human intervention is important. GENERAL GOALS

In the design of TRAC, there were the following broad technical goals. As already stated, TRAC should be hospitable to, and should be able to accept, name, manipulate, store, and emit, any teletypewriter character or string of characters. This ability should include any control or formatting characters of any kind, or in any combination, i.e., to such characters as carriage return, space, and, in certain instances, to the specific lack of a character -- null in the most precise sense.

Through suitable strings produced at the keyboard, it should be possible to specify any well-defined procedural operation upon strings of characters. It should do this through combinations of primitive functions which are used to make up such procedures. It should be able to perform integer arithmetic and to manipulate bit strings. It should be able to treat any character string as text, procedure, or name. It should be able to treat a string at one time in one way, and later in another way. Therefore it should have the ability to treat the statement of a procedure temporarily as text, and, as such, to modify it, and thereafter to execute the corrected statement as a new procedure.

TRAC should permit the keyboard user to move any named string off onto a mass storage device (disc, drum, or tape), to retrieve it at will, and to control the organization of the strings within the storage device. It should also permit the user to output strings onto external media such as paper tape, and to read them back in again. By extension, it should permit the receipt and transmission of strings over common carrier communication channels, including transmission into, and recording in, other TRAC-controlled systems.

In its time-shared environment, TRAC is a "user program", and thus is one of the many user programs which may be in simultaneous operation. In some cases, it may be desirable to have a version of TRAC as a component of an executive program serving many users -- a matter which has yet to be investigated.

It was a goal that TRAC should be a "keyboard" language easily usable on line. Thus it should not be upset by the usual typing mistakes, and the user should find it easy to recover from such mistakes. No inadvertent combination of characters should cause TRAC to "blow up". It should accept nonsense gracefully, with at most a polite diagnostic response of "program error" or the like. At any time, it should be possible to stop extended loops and "sorcerer's apprentice" actions, merely with a touch of the break key. This should result automatically in the re-initialization of the state of the TRAC processor, though without loss of any work in storage.

A goal of the TRAC language was to produce a simple and explicit syntax which was independent of a line format on a page, and which was not a descendant of a syntax based upon the tabulating card. Another goal was to avoid a "crypto-syntax" such as one based on nonprinting characters, or on a confusing hierarchy of rules; or a "hopefully simplified" syntax based on English and built around some specific job.

It was desired that the syntax of TRAC be based upon as few control (i.e., syntactic or meta) characters as possible, since the more such characters there are, the greater the possibility of getting into unanticipated trouble. When not acting in their syntactic role, these characters, as much as possible, should behave as ordinary characters. There should be the possibility of changing at least certain of the control characters while under TRAC control. For some purposes, it may be desirable to be able to change all of them.

The language should be based, as is most natural, upon strings of arbitrary length marked by some easily understood and used mode of punctuation and delimitation. Particularly to be avoided is a dependence upon atomic symbol strings which do not allow splitting or joining of character substrings within the ordinary scope of the language. It should be possible to divide any string, or to put together any two strings at any time to make an integral (non punctuated) new string.

For the most natural usage, strings should stand for themselves. In other words, "a character string is a character string", and only if the TRAC syntax requires a string to be interpreted as a name is it treated as a name. On the other hand, naming and indirect addressing through names should be possible to any necessary depth.

In the language, one should be able to nest any primitive function or procedural statement inside any other, to any depth, and without confusion. One should be able to handle iterations (repetitions of the same step) and recursions (deferrals of a partially complete step with a call upon itself or another step) to any depth within the limits of storage space in the host machine. Procedures should be able to operate upon themselves, or to refer to themselves, without limitation. Procedures should be able to create new definitions of procedures, and then to execute such procedures. It should not be necessary to keep track of "level", and the statement of procedures should be independent of level.

The set of primitive functions available in TRAC should be carefully selected. There should be enough to provide convenience in the kinds of operations most used in practice, yet not so many that the functions become individually detailed and overly specialized. It might be an interesting logical exercise to try to develop another logically minimal, non-redundant set of functions. However, experience (such as with the logically elegant five-function set of primitives in LISP) shows that a practical operating system must have conveniently available to it a substantially larger set of user functions. Thus the goal should be to find some set of primitive user functions which have the required versatility and generality, yet which are still manageable in number and intellectual complexity.

TRAC should be capable of performing decisions during the execution of procedures, and the procedures should be able to change and evolve through redefinition in consequence of data which is brought to them. Procedures should be capable of defining and storing new matter at any time, either text or new procedures. Procedures should be capable of creating new unique names for such matter, or for other purposes, as may be required.

One of the main design goals was that the input script of TRAC (what is typed in by the user) should be identical to the text which guides the internal action of the TRAC processor. In other words, TRAC procedures should be stored in memory as a string of characters exactly as the user typed them at the keyboard. If the TRAC procedures themselves evolve new procedures, these new procedures should also be stated in the same script. The TRAC processor in its action interprets this script as its program. In other words, the TRAC translator program (the processor) effectively converts the computer into a new computer with a new program language -- the TRAC language. At any time, it should be possible to display program or procedural information in the same form as the TRAC processor will act upon it during its execution. It is desirable that the internal character code representation be identical to, or very similar to, the external code representation. In the present TRAC implementation, the internal character representation is based upon ASCII (American Standard Code for Information Interchange). Because TRAC procedures and text have the same representation inside and outside the processor, the term homoiconic is applicable, from homo meaning the same, and icon meaning representation (4).

Many of these stated goals were set early in the development. However, some of the goals were added more recently, as the power and the scope of the present TRAC programming emerged. THE SOURCES OF INSPIRATION

TRAC had a number of sources of inspiration; COMIT and LISP provided the main challenge to devise a system which could do at least as much as they could, yet would not have their limitations. A major limitation of COMIT was clearly the need for compilation, resulting in rigid procedures which could not be fundamentally modified at the keyboard during run time. Other shortcomings were in its line-by-line format, and the inability of one procedure to operate upon another procedural statement and then to execute the result. LISP, although elegant in concept, becomes inelegant in practice. It even "cheats" in the frequent use of machine-language procedures. It is still not an easily used keyboard language. More unfortunately, its documentation seems to require a "mystique" of a sort that not all the reactive typewriter users will have. Its bifurcated list structure basis significantly limits the generality of the data structures. Finally, LISP is troubled with a dual language problem: an M-language, which is easy to read, and is used externally, and an S-language, with which the LISP processor operates, and which is usable externally only by the hardened initiates. It should be noted here that were the S-language the only LISP language, LISP would be close to being homo-iconic (excluding the machine-language functions). IPL-V was also a challenge. However, it seemed that IPL-V was closer to a stylized computer language than it was to a user language as conceived here. Certainly for the reactive typewriter purposes, it was altogether too much like conventional computer programming to be usable by the expected user groups.

The main inspiration for TRAC came from three papers by McIlroy and colleagues discussing their work with a macro assembly system (5,6,7). These papers pointed out that a macro assembly system had unexpected power as a symbol manipulator, and that if the system could store definition schemata, could create definitions, could execute such definitions, and could determine its next actions from a decision capability, then the system was indeed a Turing machine and was of complete logical generality.

Unfortunately, the two most interesting papers by McIlroy (6,7) were never published in a journal.

In discussing the implications of such an extended macro assembler system, McIlroy (5) had this to say about what a generalized compiler-processor should have:

    Definitions should be able to contain macro calls.
    Parenthetical notation should be available for nesting and compounding calls.
    Conditional statements should be operative at any time.
    Created symbols should be available for such use as in names.
    Definitions should themselves be able to contain schemata for creating additional definitions.
    Repetitions over a list should be permitted. 

(These are paraphrased slightly for clarity.) All of these capabilities in some form are available in the present TRAC system.

TRAC, upon close inspection, shows itself as a system built around the notion of the macro as it is used in macro assembly languages. It is designed to be strong at putting things together and for carrying out tasks. Less attention was paid to providing extensive analytical ability. Thus TRAC may be clumsy (though not impossibly so) if one uses it to imitate a compiler's scanner and parser. A goal for later work is to strengthen TRAC's analytical ability.

McIlroy's system was cast in the format of the symbolic assembly language of the IBM 704 computer. In other words, it was based on a tabulating card format. Like LISP, it dealt with atoms (symbolic addresses and symbolic operation codes). Because it was written in the usual columnar programmer's format, it was clearly unsuitable. The problem was: how to modify it, how to generalize it, and how to extend it to give the results desired.

This process of generalization turned out to be similar to the problem facing the inventor of some game using a playing board, pieces and rules. In the development of TRAC, the general nature of the end goal was intuitively visible from the beginning. Yet it was not evident what the end result would look like. The development process was one of tentatively setting forth a complete set of "rules of the game" and then trying to "play the game". In the early stages, there was no need to try to implement the ideas by programming on a computer. If the statement of the rules and of the moves would not permit performing certain useful procedures, that was the end of it. It was then necessary to go back and try to devise some new set of rules that would. In a highly interlocked and interdependent system such as TRAC, very small changes in a rule may cause major consequences in a number of unanticipated places. DECISIONS ON CONTROL CHARACTERS

A critical decision in TRAC, on which almost everything else rested, was the form of, and the manner of operation of, an elemental "statement". The hope was for a kind of statement having minimal complexity (visual, logical, and typographical), using the simplest explicit syntax giving the utmost logical versatility, all being done with the fewest possible syntactic or meta characters. In the end, as one might expect, it was necessary to accept some compromises; nevertheless, the overall result has proved to be quite satisfactory.

The manner in which the scope of an elemental statement is indicated may appear to be a simple matter, yet it is far from trivial. Its consequences provide a good illustration of the high dependence of a language system upon the adopted script. Decisions on script were especially important in this case, since it was intended that TRAC be homo-iconic. Thus the script should not present severe problems of use either to the human or to the machine. It might seem that the choice of the script was a mere matter of decision based upon human convenience and scanability for the machine processor. This is not so. The consequences of the script decisions go a great deal deeper, as was apparent only after the script was implemented and tried on the computer. Some of the most valuable features of the script were not suspected when the script was first under consideration.

The modes for delimitation of a statement seem to be restricted to the following three: 1) The use of word delimiting as in ALGOL, such as "begin A ... end A' where A is the name of a procedure; 2) The use of a numerical projection, such a: "take the next N characters" or the next N units of text; and 3) The use, in some manner, of paired punctuation marks, such as parentheses.

At first, "word delimiting" seemed attractive. Upon study, it was found that because the operands of procedures were going to be text strings, usually in a page format, there was a likelihood of collision between the uses of the words "begin" and "end" as delimiters and as elements of text. Another consideration was that word delimiting requires a substantial number of characters, and therefore with multiple nesting, it would be confusing and far from compact. It was also clear that the points of delimitation would not be readily visible when immersed in a stream of text. Therefore this approach was discarded primarily because of its clumsiness.

The "numerical projection" method depends upon a prediction of how many characters or units of text should be taken after some point of projection. The methods of the "Polish" prefix notation are of this character, in that each function implicitly calls for a very specific number of arguments to follow -- usually two arguments. This is satisfactory if one can predict the situation. However, it often happens that one does not know, or there is no way of knowing, how many units of text or how many characters will eventually come within the scope of a statement. TRAC, as currently used, often encounters this situation in important applications. From the user's standpoint, the prefix notation is almost unreadable if there is any depth of functional complexity. It is purported that machine processing is easier with prefix notation. However, in comparison with other easily-parsed notations, this advantage is probably more superficial than of any real consequence. The prefix style of notation and methods based on numerical projection were therefore discarded because of their inability to handle strings of unpredictable length, and because of unreadability.

There remained the method of paired punctuation signs, best exemplified by parentheses. Parentheses have the advantage of being familiar from the script of algebra, and they are effective and compact when used to delimit text. Their major difficulty is demonstrated in an acute form by the parenthesis problems of LISP, where expressions can have a dozen or more parentheses at the end. However, it appears that the primitive functions chosen in LISP tend to aggravate the parenthesis problem. Atypical compound expression in LISP will tend to be of the form (symbol(expression)) with all the parentheses piling up at the end. In TRAC, as will be seen, compound expressions tend to have the form (symbol(expression)symbol) and thus there does not tend to be such a concentrated pile-up at the end. There will always be the need for careful parenthesis counts to make sure that delimiting will occur as intended. In balance, parentheses were chosen as the means of statement delimiting in TRAC. DECISIONS ON FUNCTION REPRESENTATION

The parentheses as text delimiters in TRAC have the purpose of indicating that something is to be done to the enclosed text. There are two main cases: 1) to indicate that the text is the argument of a function, and 2) to indicate that something is not to be done with the enclosed text, i.e., to protect functions within the text from immediate execution.

In the first case, TRAC uses the format #(text string) to indicate a function. Here the "sharp sign" or "number sign" is a character having a special meaning when it immediately precedes a parenthesis. Its meaning can be roughly stated as "evaluate what is enclosed". In other words, it signals that the delimited statement should be treated as a function, if that is possible. Later we will consider a modified function represented by ##(text string). In TRAC, if the number sign does not occur in these two very specific ways: either as #( or as ##( , it is invariably treated as an ordinary alphabetic text character.

In practice, the function indicator sign #, as well as the other TRAC control or meta characters, should be chosen in accordance with their ease in typing on the particular keyboard that will be used. When working with the Teletype Model 33 keyboard, the "up arrow" character is particularly easy to use in sequence with the parenthesis.

Because most functions require several arguments, it is necessary to have a set of rules for dividing the text string inside a function into the various substrings which will then be individual arguments. Commas fulfill this role of marking the points of division. If the text string inside the function-delimiting parentheses consists only of commas and alphabetic characters, division is done simply at the locations of the commas.

More generally, the text string of a function will be more complicated. It may contain the statement of another function. It may have pairs of protective parentheses. There may be other variations. It is precisely at this point that TRAC epitomizes several unique contributions to the development of a language system. Before getting into these details, first consider some of the superficial aspects of TRAC functions, while omitting the problems of nesting or the other tricky aspects of argument strings.

For simplicity, imagine the argument strings to be composed merely of commas and alphabetic characters, the latter having no syntactic significance. A typical TRAC function will have this form:

    #(ab,S1,S2, ... ,Sn) 

where the "a" and "b" are individual alphabetic characters, and the "S1" are alphabetic strings not containing commas. The two initial characters distinguish the particular TRAC function represented; the particular characters chosen for each function are chosen for their memory-aiding or mnemonic ability. TRAC has about 35 primitive functions, and thus a single character would not suffice.

A variety of different ways of representing a function was considered during the design of TRAC. In the beginning it was hoped that there would be only five or six basic functions, and that some quite abbreviated expression, perhaps involving punctuation, could be developed. Convenience of use soon forced the decision to provide a larger number of primitive functions. That being the case, the indication by the two-letter mnemonic seemed to be the best solution.

Consideration was also given during design to the alternative functional forms:

    #ab(S1, ... ,Sn)

    (#ab,Sl, ... ,Sn) 

The latter form was the strongest alternative to the form finally adopted. The adopted form #(ab,Sl, ... ,Sn) was finally chosen, partly because of its slightly better readability, but more particularly because it would allow the two-letter mnemonic to be treated consistently as one of the argument substrings.

Let us now consider two of the most basic of the TRAC primitive functions. The first is the define string function which allows us to name and to store a piece of text. It is illustrated by:

    #(ds,Abc,The apple is red.) 

This function causes the text "The apple is red." to be placed in storage, and the name "Abc" to be set up in a table of contents with a pointer to the location of the stored text. Note that alphabetic case shifts, if they are applicable, are retained in TRAC.

The counterpart function is call, illustrated by:

    #(cl,Abc) 

The result of this call is to bring the named text out of storage (without erasure) and to insert the text in place of the statement of the call functions, i.e., in the place of the "X(cl,Abc)". Specifically,

    #(cl,Abc) 

is deleted from the string in which it is found, the following text (if any) is pushed ahead, and the text

    The apple is red. 

is put in the place formerly occupied by the call.

Note that the call function leaves a value behind in its place. Thus the call function is a representative of the class of TRAC functions which have a value. On the other hand, the define string function, although producing a useful action, leaves nothing behind at the location where the define string statement occurred. Thus the define string function is an example of a TRAC function with a null value. If such a function occurs in a string of text, after the performance of the function, the enclosing text is closed up, leaving no trace of the function behind. Note especially that in TRAC, "null value" means specifically "no character of any kind", not even the space character or "blank" of the tab card.

At this date, with TRAC running, the present form of the define string function and the call function seem very simple and obvious. Neither started this way.

Initially, the analog of the define string function in TRAC did more than merely name and record a string. Following McIlroy, it created an entire macro expression, including the points of substitution. Due to its complexity, it required a special syntax and functional form which was different from the rest of the functions.

The call function was in even a worse state of affairs. Initially, the call was an operator that moved a string from the memory into some central "accumulator" or scratch pad, where further operations might be performed on the string. Essentially the call function, in its philosophy, was then closely related to the "single address" mode of operation now almost universal in computer programming. The difficulty with this was that text, unlike a number, is not a simple entity; it has extension, and has many separate parts. Therefore, once the text from a call was in the accumulator, perhaps with segments of other text, it was difficult to specify the ways in which the various elements were to be combined. There were so many possibilities -- such as concatenate, interchange, substitute, segment, take a character -- that it seemed unlikely that a useful set of operations could be kept either small in number or of sufficient generality. An associated difficulty was the apparent need for a great variety of text markers to control the action of the various functions, i.e., to mark the beginning points, end points, insertion points, and the like. Also, the design of useful functions continued to give rise to instances where a special case with a special rule was needed for a proposed new function. This was intolerable. No good solution to these problems was found during the study of the single address mode of operation. THE COMPREHENSIVE PHILOSOPHY OF NESTED FUNCTIONS

The breakthrough in dealing with text and calls (and therefore with all the functions) occurred as a consequence of a suggestion in the handling of input and output controls made by Deutsch. Up to the time of this suggestion, input and output was messy and generally non-uniform with the rest of the evolving system. As in most programming systems, it didn't fit in. The suggestion was that we have two input-output functions, print string and read string, and that for basic input and output control these two functions be nested. Print string is represented by #(ps,X) where X represents any string of alphabetic characters. This function causes the printing out of the string represented by X. Read string is represented by #(rs), and causes the processor to "listen" to the typewriter. The value of the read string function is the string of characters typed in at the keyboard. For input and output control, these functions are nested into the expression called the idling program:

    #(ps,#(rs)) 

As will be explained in greater detail later, such compound expressions are evaluated by working from the inside out, evaluating all functions. Thus the read string function is the first one to be evaluated.

The idling program is the initial state of the processor. Then when a define string expression such as

    #(ds,aa,The rat ate the cheese.) 

is typed in, this expression replaces the #(rs) to give:

    #(ps,#(ds,aa,The rat ate the cheese.)) 

The define string expression is next executed and causes the naming and recording of the text. At the end of the operation, only #(ps,) is left, because of the null value of the define string function, and nothing is left to type out. The processor is again restored to the initial state by automatic reloading of the idling program. Next, by typing in #(cl,aa)we will, step by step, have the following actions:

    #(ps,#(cl,aa))

    #(ps,The rat ate the cheese.) 

and finally a typeout of the text:

    The rat ate the cheese. 

From this initial suggestion, it was possible to evolve a comprehensive philosophy of nested functions, and to recast all of the ideas of TRAC which had been developed to that date. The first thing was to throw out completely the notions of a "single-address-accumulator" form of organization. In its place, a thoroughgoing adoption of the notion of nested functional expressions was taken. All functional expressions have either a null value, or, if they have a value, their value is inserted in the place of the functional expression. Accordingly, there is no need for a temporary limbo with the name of "accumulator" to hold text in process. Perhaps more important, each functional expression serves as a syntactic marker for showing where its text value is to be inserted within some other expression. This is an exceedingly powerful and versatile device.

One should not be surprised at the power of using a functional expression as the marker for the location of insertion of a value, since this is exactly the technique developed over the centuries in mathematics for dealing with the most general kinds of combination of abstract and literal quantities. Also, since mathematical script is nothing but a standardized and printed version of handwritten signs, evolved and modified to suit the convenience of generations of mathematicians, again we should not be surprised that the technique makes for a convenient user's script.

The comprehensive treatment of nested functions in TRAC permits the building of a TRAC processor which has no "special cases" for the performance of its actions. At the beginning of any processing cycle, as the initialization step, the idling expression #(ps,#(rs)) is automatically loaded into the computational or scratch pad area of the processor. Text read in from the typewriter keyboard then appears in place of the #(rs) in the argument string of the print string function. If this text read in includes any functional statements, these are performed. At the end, if there is a value left behind from the functional statements, it is printed out by the print string function. The print string function itself has a null value, so the scratch pad is finally left empty. At this point, the processor re-initializes (resetting push down lists and registers, reloading the idling expression, but it does not erase the strings in storage or their names). The TRAC processor is now ready for further input.

Implicit in the above statement is the important fact that all the computation in TRAC (i.e., all the evaluation of functions, all manipulation of strings) logically occurs within the argument string of the print string function. Since functions can be nested to any depth, by induction all computation in TRAC occurs within some argument string in the nest.

To understand the operation of TRAC, one must therefore always think in terms of what is happening in an argument string. Moreover, since functions are embedded in argument strings, and since these functions themselves have argument strings, we have an unlimited ability to deal with higher and higher levels of discourse. If the problems of relating these levels of discourse can be completely solved, then we should presumably have a most powerful processor. It appears that in TRAC we have a simple and closed solution to these matters. THE TRAC ALGORITHM

The evaluation of TRAC functions, and the relation between the different levels of the argument strings, is completely determined by the scanning and evaluation algorithm of TRAC. To a first approximation, the scan process operates from left to right, from the outside in, starting with the print string function of the idling expression. In order for any function to be evaluated, it is necessary that all of its argument string must be converted from an "active form", containing possible unevaluated functions, to a "neutral form" in which all the evaluations permitted by the TRAC scanning algorithm have been completed. Thus, in an expression of nested functions, the first function actually to be evaluated will be the first inner function which contains no other function in its argument string.

Sometimes the value of a function will be a string again containing one or more functions. If so, there are two ways in which the scanning is resumed. These possibilities are determined by whether the function producing the new value was of type #( ) or of type ##( ). If the value string was produced by a #( ) function, the new value string must in turn be scanned and its functions evaluated, and so on, so long as #( ) functions continue to appear and to produce values. However, if the value was produced by a ##( ) function, the new value string -- whatever it may contain -- is treated thereafter as a neutral string, i.e., any functions it may contain (of any sort) are not evaluated.

As the active argument string is scanned, its characters are transferred one by one from the active to the neutral string. Thus an active string is depleted from its left-hand end, and the characters obtained are added to the right-hand end of the neutral string being built up. If a comma. is encountered during the scan of an active string, it is deleted, and its location marks the end of one argument substring and the beginning of the next. Thus if an argument string consists of only alphabetic characters and commas, the commas will completely determine the divisions of the text string into the various arguments of the function.

By the scanning process, if a pair of closed parentheses not indicating a function is encountered in an argument string, the parentheses themselves are deleted, and the entire content between the matching pair of parentheses is transferred to the neutral string. This transfer includes any function expression, any commas, any number of closed paired parentheses to any degree of nesting, as well-as any format characters such as carriage return. The processor keeps a strict parenthesis count to determine the location of the matching right-hand parenthesis. This means that any attempt to insert unpaired parentheses explicitly in an argument string will generally cause the scope of some argument to be in error, and will usually cause a serious error in the execution of a procedural statement.

The inability explicitly to handle unpaired parentheses is not an absolute limitation in TRAC, since unpaired parentheses can be dealt with implicitly by use of the neutral function form of the call ##(cl, ). Since unpaired parentheses can in this manner be kept out of the active argument string of any function, they do not cause trouble.

We should note the close parallel between the single set of protecting parentheses ( ). and the ##( ) functions. The ( ) inside a function causes a transfer of the entire expression contained within to the neutral string of that function. The ##( ) causes a transfer of the entire string produced by the function to the neutral string of an enclosing function.

TRAC appears to be the only processor which permits use of both the #( ) and the ##( ) kind of function evaluations. The string processor of McIlroy based upon the macro assembly system uses functions solely of the #( ) type. This kind of function, called the active function, is the one that seems to be the most used in writing TRAC procedures. The neutral function epitomized by ##( ) is used somewhat less frequently, mainly because it does not lead to an automatically iterated , re-evaluation of the strings produced. LISP, for example, appears to be based exclusively upon the neutral function.

There is a final point about the TRAC scanning algorithm, which might at first seem to be trivial, but which is of considerable practical importance. The characters for "carriage return", "line feed", and "tabulate" (if available to the keyboard) are automatically deleted by the scan algorithm where they occur in an argument string, unless they occur within some protecting pair of parentheses. The reason for this is that a TRAC procedure may contain a very complex sequence of functions. It is then helpful for easy readability to write these functions in a column, rather than in a solid line across a page. By automatic deletion of the unprotected format characters, it is possible to format such a sequence of functions without having the format characters themselves turn up later (as values) in an unwanted fashion at the end of the evaluation. THE TRAC PRIMITIVE FUNCTIONS

We now resume our consideration of the TRAC primitive functions, with a few examples of their effect. It should be stressed that the major contribution of TRAC does not lie in the particular set of primitive functions that were chosen. While they are a very useful and convenient set for the work contemplated, for other work another set might be more appropriate. The important contribution of TRAC lies in the thoroughgoing viewpoint of functions nested within argument strings, the distinctions between the manner of use of # ( ) and ## ( ) , and the scheme by which this is all tied together. In other words, the major contribution lies in the area of the TRAC scanning algorithm. Given the TRAC algorithm as a substrate, it is possible to consider the employment of a variety of useful primitive functions. As two examples, functions might be used which were more appropriate to a dichotomous list-structured data base, or functions might be used to implement the COMIT or SNOBOL type of scanning and replacement philosophy.

In systematic review of the TRAC primitive function set, we begin with the print string function (8). Print string #(ps,X) is a primitive function of two arguments, namely the two-letter mnemonic ps and the single neutral string represented by X. If the scope of any print string function has additional neutral strings, such as in #(ps,X1,X2,X3), only the first neutral string X will be used, and the rest will be ignored and will disappear from the computation. It has been found, in this and other functions, that this feature provides a very handy way to get rid of things. The principle operates for all functions which are defined for a specified number of argument strings. The print string function has a null value. Note that the #( ) versus ##( ) distinction makes no difference in the effect of the print string function, since print string has no value.

The read string function #(rs) has the value consisting of the string of characters typed at the keyboard up to the first occurrence of a specified meta character. Here we will use the apostrophe ' as the meta character. This character has a meaning that can be read "end of text". This meta character can be readily changed, as will be explained later. The meta character is removed from the input string for all read in done by #(rs).

A variation of the read string function is the read character function #(rc) which will read in one character. It will accept and transmit any character, including the end-of-text meta character, or even a single, unpaired parenthesis.

Note that by use of ## or # it is possible to control the disposition, at the next level, of the characters read by either the read string or the read character function. Consider the two TRAC expressions:

    #(ds,A,#(rc))'X

and

    #(ds,B,##(rc))'X 

These will cause the recording of various things, depending upon what is typed in for the symbol X. The second expression will cause whatever character was typed in to be stored, whether the character was an alphabetic character, ail apostrophe, a comma, a right or left parenthesis, or a number sign. However, because a #( ) function permits a re-scan of the value emitted, the first expression will not permit storage in certain of these cases. In particular, the form A will be null (empty) when X has the value of comma, or either of the parentheses, but it will store any other character.

Consider the case he read string function. The TRAC expression

    #(ds,C,#(rs))'X 

in which X may contain a function, or a procedure of several functions, will cause the processor to try to execute immediately any functions which were read in, before the text is sent off to storage.

On the other hand, the expression

    #(ds,D,##(rs))'X 

will read in and record "verbatim" absolutely any string of characters (including unpaired parentheses, commas, functions, or anything else) up to the point at which the first apostrophe is typed in (which is deleted). No evaluation is performed before recording.

The end-of-read-in meta character can be changed with the function change meta #(cm,X). Execution of this function will cause the first character of the neutral string X to become the new meta character. By use of this function, we can sidestep any limitation due to a fixed end-of-text meta character.

TRAC must have the ability to locate characters and substrings within strings, and to insert new text in such location. At an early design stage, a primitive insert string function was considered for performing such an operation. Such a function would have the form #(is,N,X,Y) where N stands for the name of the form to be acted upon, X represents the literal value of the substring to be located in the

string with name N, and Y represents the value of the string to be inserted as a replacement.

TRAC performs this task in another way, gaining some generality by separating the operation into two steps. It uses the segment string operation represented by

    #(ss,N,X1,X2, ... ,Xn) 

where N represents the name of the text which is acted upon, and the X1 represent neutral strings. In operation, the string named N is taken from the store. It is first scanned from left to right in search for a match with string X1. Wherever a match with X1 is found, the matching characters are deleted from the string, and the place is marked with a segment gap indicator of ordinal value one. This marker could be a pointer. However, in the current TRAC implementation, the marker is a special character outside the range of the input codes. The scanner now resumes with with X1, finding and marking other matching portions of text, deleting and marking these locations in turn with the segment gap indicator or ordinal value one. When the matching operation with string X1 is completed, the processor scans the modified text (With deletions and markers) and looks for a match with the string X2. Where it finds a match, it makes a deletion and inserts markers of ordinal value two. And so on, until the string named N has been scanned for matches with all the strings enumerated in the segment string function. The marked string is now replaced in the TRAC memory under the name N. Such a marked string in storage is called a form, and in general any text in storage is called a form. The segment string function has null value.

A segmented form now can be brought forth, with insertions of new text in the segment gaps by means of the call function, which in its full form is represented by

    #(c1,N,Y1,Y2, ... ,Yn) 

where N again stands for the name of the form called forth, and the neutral strings Yl, Y2, ... ,Yn are the new strings to be inserted in the locations marked by the corresponding segment gaps.

Observe that the define string and the segment string function together effectively create a macro definition, in which the Xl's are the dummy variables in the macro definition. The macro call is then performed by the TRAC call, with the parameters of the call being the Y1's.

An important point to observe in connection with the TRAC segment string function is that, in comparison, McIlroy's macro assembler and LISP can act only upon atoms (in the terminology of LISP). By this is meant that each dummy variable X1 has to be an indivisible symbol (like the symbols in assembly language programming) and each symbol must match exactly some other symbol set off by commas, i.e., another atom. Matches are not permitted in the middle of the text or in arbitrary character strings. Thus both these systems are quite limited in their ability to deal with text in general. Quite strictly, they are symbol manipulators, rather than being text manipulators, as is TRAC. They cannot concatenate two atoms, with the removal of commas between; neither can they divide atoms. Since atoms don't exist for TRAC, both of these are trivial operations for it.

The main structure of TRAC -- epitomized by the six primitive functions ps, rs, rc, ds, ss, and cl -- have now been covered. Examples of the use of these functions will be found in the appendix. The remaining TRAC primitive functions will now be reviewed. Branching is performed in a number of different ways. The most obvious is according to string equality. This is done by the equals function which is represented by #(eq,X,Y,T,F) where each of X, Y, T, and F stand for a string. If the string X is the same as string Y, the value of the function is the string T; otherwise its value is the string F. Note that strings T and F may contain either text or function; thus it is possible to branch to a new subroutine. Numerical comparisons are made by the greater than function #(gr,X,Y,T,F). This has the value T or F according to whether X is numerically equal to or greater than Y, or not.

Parts of forms can be read from storage, with branching if the form is empty. Each application of the call character function #(cc,N,F) results in reading out the next character from the form whose name is represented by the symbol N. As each character is read out, a pointer is moved ahead one place. The character read out is the value of this function. When the pointer has reached the right end of the form, the value of the function is F. Again, the string F may contain a call for a new procedure or subroutine. The closely related call segment function #(cs,N,F) calls out the text segments, one by one, which were formed by the operation of the segment string function. Again when the segments are exhausted, the function has the value of the string F.

The function call n characters (#(cn,N,n,F) has as its value the next n characters of the form named N (segment gaps being deleted during the call), and has the value F when the form is empty. The function initial #(in,N,X,F) looks for the first occurrence of the neutral string X in the form with name N. The value of this function is then the head end, or the initial part, of the form N, up to the point where the string X finds a match. The matching characters of the form N are now skipped over, and the read pointer is now moved up to the first character of the remaining form. When this function is applied again to the same form, it will get another initial string from the remaining part of the form, and so on. When the form is empty, the function has the value F.

The calls with mnemonics cc,cs, in, and cn all modify the same pointer, which is attached to the recorded form. When the location of the pointer in a form has been changed by cc, cs, in, or cn, a subsequent call by cl will have a value which is the text that follows the pointer. The pointer can be restored to the head of the form by the call restore function #(cr,N) which has null value.

Another technical point, but one of considerable practical importance, is that the functions cc, cs, in, and cn have their values as read out from the called form controlled by the #, ## distinction, while the function value for the empty form (i.e., from the string F) is always treated according to the # rule. This permits one to read out strings into the neutral argument string, but when the form is empty to cause execution of a call buried in F to cause a transfer to a new procedure.

It was not intended that TRAC have any great power in numerical computation, but an ability with integer arithmetic was considered essential in order to handle arrays. Thus TRAC was given a capability for integer arithmetic, with the operations addition, subtraction, multiplication, and division, having the respective mnemonics ad, su, ml, and dv. The addition function is typical of these functions: #(ad,D1,D2). The arithmetic functions take decimal arguments, and the value is the decimal result. The TRAC memory stores the numbers in their decimal ASCII representation, but the computer arithmetic in the present implementation is in binary.

TRAC can deal with patterns of zeroes and ones, i.e., with Boolean vectors. The patterns are represented by a sequence of octal digits. The functions available are Boolean union, intersection, complement, shift, and rotate. Shift and rotate are to the left with the number of binary places being given by a decimal number. These functions are represented, respectively, by #(bu,01,02), #(bi,01,02), #(bc,01), #(bs,D,01), and #(br,D,01) where the symbols 01 and 02 stand for an octal value, and D stands for a decimal number.

TRAC would be of little practical interest if it could not be used to manage the transfer of content back and forth between some large-scale back-up storage. In the present time-shared environment, the back-up store is a UNIVAC Fastrand drum. The TRAC function store block #(sb,M,N1,N2, ... ,Nn) causes the forms whose names are represented by N1, N2, etc., to be taken from the TRAC processor storage and to be written onto the drum. These forms and their names are deleted from the TRAC storage and table of contents. At the same time, a new form is created, with the name represented by M and with the content being the drum address where the sequence of forms is stored. The length of the stored sequence is of no concern, since the drum is organized in chained 50-word blocks by the executive program of the time-shared system.

The converse function is fetch block #(fb,M) which causes retrieval without erasing of the stored drum forms. With the fetch order, the forms and their names are again set up in the TRAC processor memory. It should be noted that pointer values to the text of a form are preserved in the drum store and fetch operations. In fetch, the form M is not erased. Drum space can be regained, if this is a problem, by the function erase block #(eb,M), which erases the drum content and also the TRAC form named M.

Diagnostic capabilities are very important for a. processor dealing with complex procedures. The list names function #(ln,X) has as its value the names of all the active forms in the TRAC memory, with the string X (usually taken to be carriage return and line feed) inserted ahead of each of the names. Forms -- complete with an indication of. the segment gaps -- can be inspected by the function print form #(pf,N) where N stands for the name of the form. Print form has null value. A step by step trace mode is activated by the function trace on #(tn). This has the result that as each complete set of neutral strings for a function is built up, it is typed out for inspection. Then a touch to the carriage return key causes the function to be evaluated. The neutral strings of the next function are then found and typed out, and so on. This action is halted by the trace off function #(tf).

Control of additional peripheral units is gained by the select device function #(sd,X) in which X stands for the mnemonic of the device selected. The select device function modifies the next-following action of the read string function, the read character function, or the print string function, causing these functions to cause input-output on the named peripheral. For example, #(sd,p)#(rs) causes operation of the paper tape reader.

Because many operations have null value, with no type out, it is desirable to indicate to the user that an action has been completed, for example that the paper tape punch has finished, or that a very complex transfer has been completed and that the processor is ready to receive more input. This is accomplished by having the reinitialization procedure type out a carriage return and a line feed just before the idling program is called into action. FINAL COMMENTS

This paper has endeavored to furnish an insight into the reasons behind a number of design considerations of TRAC. To do so, it was necessary to describe briefly the TRAC language itself. However, a complete technical specification of the TRAC language, its algorithm, and its functions will be found in another paper to which the reader is referred .

TRAC is currently implemented on the PDP-1 computer in the Hospital Computer Project at Bolt Beranek and Newman Inc. in Cambridge, Mass. This computer furnishes to each time-sharing user a memory store of 4,000 words of 18 bits each. The backup store is the Fastrand drum. There are separate swapping drums for the user's programs. The present TRAC translator program, with about 35 primitive functions, occupies only slightly more than half of the 4,000-word memory. The scratch pad can hold about 3,700 characters. The internal storage if TRAC is not list-structured in the manner of LISP and related processors. Instead the content is stored in a linear fashion, with garbage collecting and rewriting to reform and compact the lists whenever more space is needed. Despite the speed penalties due to a highly compressed program, and of a time-shared environment, TRAC is rapidly responsive. The usual responses occur within 1/3 to 3 seconds, and about one second when a Fastrand action is called for. Response times of this order will be required for full satisfactory use of the reactive typewriter.

Although the action of the TRAC processor, in the evaluation of the nested functions, is highly recursive, the TRAC computer program is not -- in the sense that a machine language subroutine is never entered twice. This is a consequence of using the TRAC scanning algorithm first, and storing the results of the scanning operation in a push-down list prior to the evaluation of any specific nested function.

The TRAC language has gone through some four major stages of evolution since the beginning of the project in 1960. It was first programmed in a list-structured version for the PDP-1 in the summer of 1964 after Deutsch joined the project. During the resulting extended period of development and testing, TRAC has shown a gratifying convergence to a stable system. ACKNOWLEDGMENTS

For their interest and encouragement during early development of TRAC, special thanks are due to Dr. Max A. Woodbury of the New York University Medical Center, and to Dr. Harold A. Wooster of the Information Sciences Branch of the Air Force Office of Scientific Research. Appreciation is also expressed to Dr. Jordan Baruch of Bolt Beranek and Newman Inc., Cambridge, Mass., for cooperation and permission to use their PDP-1 computer complex. APPENDIX -- EXAMPLES OF TRAC

The bold text is typed by the user; all other text is the response given by the TRAC system

 #(ds,Store,(

 # (ds ,# (ps , (

 Give Name--))# (rs),#(ps,(

 Give Text--))##(rs)
 )))'
 #(c1,Store)'
 Give Name--Right Parenthesis'
 Give Text--)'
 #(c1,Right Parenthesis),)
 #(c1,Store)'
 Give Name--' (Null is here used as a name.)
 Give Text--ABC'
 #(cl,)'ABC
 #(c1,Store)'
 Give Name--1'
 Give Text--(((A)))'
 #(ss,l,##(cl,Right Parenthesis))'
 ##(cl,l,Q)'(((AQQQ
 # (pf,1)'((([email protected]@[email protected] ([email protected] is the segment gap indicator.)
 #(ln,*)'*Store*Right Parenthesis**1

(Note that one name is null.)

Project supported in part by the following grants and contracts: AF-AFOSR 376, AF-AFOSR 377, AF-AFOSR 461-64 from the Information Sciences Branch of the Air Force Office of Scientific Research; and GM 10416 from the Division of General Medicine of the National Institutes of Health, U.S. Public Health Service.

    "Reckon," Oxford Universal Dictionary on Historical Principles, third ed./Clarendon Press, Oxford; 1955, offers following definitions: "to enumerate serially or separately; to go over or through a series, ' "to count," "to ascertain the number or amount of," "to count up,.also to sum up, to estimate the character of (a person),' "to include in a reckoning; hence to place or class," "to estimate, value . . take into consideration," "to consider, judge, or estimate by."
    Mooers, C. N., "A Progress Report, The Reactive Typewriter Program," Comm. ACM, p. 48; Jan., 1963.
    Advanced Research Projects Agency, Information Processing Techniques Div., Contract No. SD?295.
    Following suggestion of McCullough, W. S., based upon terminology due to Peirce, C. S. s McIlroy. M. D., "Macro Instruction Extensions of Compiler Languages," Comm. ACM, p. 214?220; April, 1960.
    Eastwood, D. E., and McIlroy, M. D., "Macro Comoiler Modification of SAP," unpublished memorandum, Bell Telephone Laboratories, Computation Laboratory; Sept. 3, 1959.
    Mcllroy, M. D., "Using SAP Macro Instructions to Manipulate Symbolic Expressions," unpublished memorandum, Bell Telephone Laboratories, Computation Laboratory; early 1960.
    Mooers. C. N., "TRAC, A Procedure Defining and Executing System, circulated in preliminary form as Rockford Research Memo No. V-157; June, 1964: in revision for publication. 

© Copyright 2000 by the TRAC Foundation, Inc.

=============================================

TRAC Language: T64 Version

TRAC T64 | TRAC Language Home TRAC, A Procedure-Describing Language for the Reactive Typewriter

by Calvin N. Mooers (1965) Paper presented at the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965. Abstract

A description of the TRAC (Text Reckoning And Compiling) language and processing algorithm is given. The TRAC language was developed as the basis of a software package for the reactive typewriter. In the TRAC language, one can write procedures for accepting, naming and storing any character string from the typewriter; for modifying any string in any way; for treating any string at any time as an executable procedure, or as a name, or as text; and for printing out any string. The TRAC language is based upon an extension and generalization to character strings of the programming concept of the "macro." Through the ability of TRAC to accept and store definitions of procedures, the capabilities of the language can be indefinitely extended. TRAC can handle iterative and recursive procedures, and can deal with character strings, integers and Boolean vector variables.

The present work was supported in part by the following grants and contracts: Advanced Research Projects Agency contract SD-295, Information Sciences Branch of the Air Force Office of Scientific Research contracts AF-AFOSR 376, 377 and 461-64, and Division of General Medicine, National Institutes of Health, U.S. Public Health Service grant GM 10416. Contents

Introduction TRAC Syntax Examples of Functions TRAC Algorithm The TRAC Functions Input-Output Define and Call Functions Arithmetic Functions Boolean Functions Decision Functions External Storage Management Functions Diagnostic Functions Examples of TRAC Procedures INTRODUCTION

The TRAC (Text Reckoning And Compiling) language system is a user language for control of the computer and storage parts of a reactive typewriter system. A reactive typewriter is understood to be one of a number of tele-typewriters simultaneously connected online by wire to a memory and computer complex which permits real-time, multiple access (time-shared) operation. In the philosophy of the reactive typewriter, the man at the typewriter keyboard is the focal point of the system. The connected storage and computer devices are considered to be peripheral service units to the reactive typewriter.

The design goals for the TRAC language and its translating system included: (1) high capability in dealing with back-and-forth communication between a man at a keyboard and his work on the machine, so as to permit him to make insertions and interventions during the running of his work; (2) maximum versatility in the definition and performance of any well-defined procedure on text; (3) ability to define, store and subsequently use such procedures to extend the capabilities of the language; and finally (4) maximum clarity in the language itself so that it could be easily taught to others. A discussion of these design goals, and of the design decisions which went into the language, may be found in a companion paper 1. The TRAC language has now been programmed for several computers. It has shown a high degree of stability during the past year of experimental use.

The present TRAC language is machine-independent and is closed with respect to operations performed upon sets of characters from a typewriter keyboard. The present language should be precisely designated as "TRAC 64." Later versions of TRAC are expected to have the ability to deal with strings of machine-coded words and with subroutines, and will thus be self-implementing.

The TRAC language was developed after a study of a number of procedure-describing languages, but only after it was concluded that each of these had features which were believed to be unsuitable or unduly constraining for the purposes contemplated by TRAC. In particular, the languages IPL-V, LISP and COMIT were carefully examined. In brief, IPL-V appeared to be too closely oriented to computer programming. LIPS had severe restrictions due to its "atomic" symbols, certain conceptual confusions and too great an orientation to mathematical logic. COMIT, while suitable in many respects, had the rigidity associated with a compiler. When work was begun on TRAC (1960) none appeared to have the capabilities desired, though they were a definite source of inspiration.

The prime stimulus to the present TRAC language came from two important unpublished papers by Eastwood and McIlroy 3 and McIlroy 4. The first paper described a macro assembly system having run-time definition-making and decision-making capabilities. The second paper showed how this system could perform very general manipulations on symbol strings. TRAC is a refinement and extension of the macro approach of these papers. Therefore it can be said that the present TRAC system consists of a machine-independent language together with a generalized macro text processor which runs interpretively to provide versatile interaction capabilities at run time. A recent, independently developed system by Strachey 5 has a number of remarkable similarities to TRAC.

TRAC SYNTAX

A TRAC string may contain a substring enclosed by a matching pair of parentheses, such as (···) where the dots indicate a string. The matching parentheses indicate the scope of some particular action. There are three cases, epitomized by #(···), # #(···) and (···). The first two formats indicate the presence of a TRAC "primitive function." The format #(···) denotes an "active function," while the format # #(···) denotes a "neutral function." This distinction is clarified below. The string interior to either kind of function is generally divided into substrings by commas as in #( , , ) where these substrings constitute the arguments of the function. Parentheses in the format (···) have roughly the same role as paired quotation marks, and, in particular, whatever string is inside the paired parentheses is protected from functional evaluation.

TRAC strings are dealt with by the TRAC processor according to a scanning algorithm which works from left to right and performs the evaluation of nested expressions from inside outward. In the expression

    #( , #( , , #( ) , # #( ) ) )

    4 3 1 2

the functions are evaluated in the order indicated. As each function is evaluated, it is replaced in the TRAC string by the string (possibly null) which is its value. The evaluation of an active function is followed directly by the evaluation of any function in its value string not protected by matched parentheses. The value string of a neutral function is not further evaluated.

 EXAMPLES OF FUNCTIONS

An example of the "define string" primitive function is the expression #(ds,AA,CAT). This causes recording of the string CAT in the memory and places the name AA of the string in a table of contents. The string can be called out of memory by the "call" function #(cl,AA). The result of the call function is to place the string value of the call, namely CAT, in the former location of #(cl,AA), with an expansion or a closing up of the surrounding strings. The call function is in the class of functions having a "value string." The define string function is an example of a function having a "null value"; i.e., no string is left behind in its place after its evaluation.

Evaluation of the "read string" function #(rs) causes the processor to accept input from the typewriter. Its value is the string as received from the typewriter up to a terminating "meta character" which is usually taken to be the apostrophe. The meta character can be changed. The "print string" function #(ps,X) causes printing out of the argument string, here represented by the symbol X. It has null value. The nested expression #(ps,#(cl,AA)) will cause CAT to be printed out.

In the beginning and at the completion of every processing cycle, the TRAC "idling procedure" #(ps,#(rs)) is automatically loaded into the TRAC processor. It is therefore seen that all strings and programs are effectively loaded into the interior of the idling procedure, and furthermore, all TRAC computations are made on functions nested within the argument string of some other function.

TRAC ALGORITHM

The TRAC algorithm governs the precise manner in which TRAC expressions are scanned and evaluated by the TRAC processor. At the beginning, the unevaluated strings are in the "active string" and the "scanning pointer" points to the leftmost character in this string. As characters have been treated by the scanning algorithm, they may be added to the right-hand end of a "neutral string," which is so called because its characters have been fully treated by the algorithm and are thus neutral, like alphabetic characters. The algorithm follows.

    The character under the scanning pointer is examined. If there is no character left (active string empty), go to rule 14.

    If the character just examined (by rule 1) is a begin parenthesis, the character is deleted and the pointer is moved ahead to the character following the first matching end parenthesis. The end parenthesis is deleted and all nondeleted characters passed over (including nested parentheses) are put into the neutral string without change. Go to rule 1.
    If the character just examined is either a carriage return, a line feed or a tabulate, the character is deleted. Go to rule 15.
    If the character just examined is a comma, it is deleted. The location following the right-hand character at the end of the neutral string, called the "current location," is marked by a pointer to indicate the end of an argument substring and the beginning of a new argument substring. Go to rule 15.
    If the character is a sharp sign, the next character is inspected. If this is a begin parenthesis, the beginning of an active function is indicated. The sharp sign and begin parenthesis are deleted and the current location in the neutral string is marked to indicate the beginning of an active function and the beginning of an argument substring. The scanning pointer is moved to the character following the deleted parenthesis. Go to rule 1.
    If the character is a sharp sign and the next character is also a sharp sign, the second-following character is inspected. If this is a begin parenthesis, the beginning of a neutral function is indicated. Two sharp signs and the begin parenthesis are deleted and the current location in the neutral string is marked to indicate the beginning of a neutral function and the beginning of an argument substring. The scanning pointer is moved to the character following the deleted parenthesis. (Go to rule 1.
    If the character is a sharp sign, but neither rule 5 or 6 applies, the character is added to the neutral string. Go to rule 15.
    If the character is an end parenthesis, the character is deleted. The current location in the neutral string is marked by a pointer to indicate the end of an argument substring and the end of a function. The pointer to the beginning of the current function is now retrieved. The complete set of argument substrings for the function have now been defined. The action indicated for the function is performed. Go to rule 10.
    If the character meets the test of none of the rules 2 through 8, transfer the character to the right-hand end of the neutral string and go to rule 15.
    If the function has null value, go to rule 13.
    If the function was an active function, the value string is inserted to the left of (preceding) the first unscanned character in the active string. The scanning pointer is reset so as to point to the location preceding the first character of the new value string. Go to rule 13.
    If the function was a neutral function, the value string is inserted in the neutral string with its first character being put in the location pointed to by the current begin-of-function pointer. Delete the argument and function pointers back to the begin-of-function pointer. The scanning pointer is not reset. Go to rule 15.
    Delete the argument and function pointers back to the begin-of-function pointer for the function just evaluated, resetting the current location to this point. Go to rule 15.
    Delete the neutral string, initialize its pointers, reload a new copy of the idling procedure into the active string, reset the scanning pointer to the beginning of the idling procedure, and go to rule 1.
    Move the scanning pointer ahead to the next character. Go to rule 1. 

The TRAC processor will accept any string of symbols. Nonexistent functions are given a null value. Omitted arguments are given a null value, while extra arguments are ignored. Omitted right parentheses will cause the processor to terminate its action and reinitialize itself at an unexpected point, while extra right parentheses are ignored and deleted at the end of a procedure. When the processor becomes too full, perhaps due to an infinite iteration or recursion, a diagnostic is typed out to indicate that fact and the processor is re-initialized by going to rule 14. The break key stops any action and causes re-initialization.

THE TRAC FUNCTIONS Input-Output

All functions are shown in their active representation, which is the form most often used. As shown, the argument strings are presumed not to contain functions or other active matter.

#(rs) "read string" (one argument). (Note that the mnemonic for the function name is counted as the first argument.) The value is the string as read from the tele-typewriter keyboard up to the point of occurrence of the meta character, which is deleted.

#(rc) "read character" (one argument). The value is the next character, which may be any character (including the meta character) received from the tele-typewriter.

#(cm,X) "change meta" (two arguments). This null-valued function changes the meta character to the first character of the string symbolized by X. Upon starting, the TRAC processor is loaded with a standard meta character, usually the apostrophe.

#(ps,X) "print string" (two arguments). This null-voided function points out on the tele-typewriter the string represented by X.

Define and Call Functions

#(ds,N,X) "define string" (three arguments). This is a null-valued function. The string symbolized by X is placed in storage and is given the name symbolized by N. The name is placed in a name list or table of contents to the "forms" in storage. A "form" is a named string in storage. If a form is already in storage with name N, this form is erased. The name N may be a null string.

#(ss,X1,X2,···) "segment string" (three or more arguments). This is a null-valued function. The form name N is taken from storage and is scanned from left to right with respect to string X1. If a substring is found matching X1, the location of the match is marked. The matching substring is excluded from further action, thus creating a "segment gap." The rest of the form is scanned with respect to X1 to create any additional segment gaps. These segment gaps are all given the ordinal value one. The parts of the form not taken by segment gaps are now scanned with respect to string X2, with the creation of segment gaps of ordinal value two. This action is repeated with all of the remaining argument strings. At the end, the marked form, along with its pointers and ordinal identifiers for the segment gaps, is put back into storage with the name N. The untouched portions of the string in the form are called "segments." It is seen that the segment string function creates a "macro" in which the arguments X1, X2, etc., indicate the dummy variables. The segment string function subsequently can be applied with other arguments to the same form, with the result of new segment gaps being created with ordinal value one, two, etc., and being inserted among those already there. A null string for one of the arguments X causes no action for this argument.

#(d,N,X1,X2,···) "call" (two or more arguments). The value is generated by bringing the form named N from storage and filling the segment gaps of ordinal value one with string X1, the gaps of ordinal value two with string X2, and so on for all the segment gaps in the form.

The following specialized calls read out a part of a form. They treat the segment gaps as if the gaps were filled with the null string. These calls (cs, cc, en, and in) preserve the neutral-active function distinction only for the strings coming from the form named N. Since the alternative value of these functions, symbolized by Z, may be a call to a procedure, the alternative value is always treated as if the function were active.

All the call functions (cs, cc, en, and in) read the text of a form beginning at the location indicated by a "form printer" which is part of the apparatus of the form. Initially the form pointer points at the first character of the form. The call function does not change the form pointer.

#(cs,N,Z) "call segment" (three arguments). The value of this function is the string from the current location of the form pointer to the next segment gap of the form named N. If the form is empty, the value is Z. The form pointer is moved to the first character following the segment gap.

#(cc,N,Z) "call character" (three arguments). The value is the character under the form pointer. If the form is empty, the value is Z. The form pointer is moved one character ahead (segment gaps are skipped).

#(cn,N,D,Z) "call n characters" (four arguments). This function reads from the form name N from the point indicated by the form pointer and continuing for a number of characters specified by the decimal integer number at the tail end of the string symbolized by D. Segment gaps are skipped. If the decimal number is positive, this function reads the string to the right of the pointer; if negative, to the left. The strings so read are preserved in their character sequence. If no characters are available to read, the value is Z. The form pointer is moved to the character following the matching substring, or is not moved if there is no match.

#(cr,N) "call restore" (two arguments). This null-valued function restores the form pointer of the form named N to the initial character.

#(dd,N1,N2,···) "delete definition" (two or more arguments). This null-valued function deletes the forms named N1, N2, etc. from memory and removes their names from the list of names.

#(da) "delete all" (one argument). This null-valued function deletes all the forms in memory, and removes their names.

Arithmetic Functions

TRAC does integer arithmetic, taking decimal arguments. The decimal numeric digits are looked for at the tail ends of the argument strings. The prefix string of the first argument string is preserved and is appended to the answer, while the prefix string of the second argument is ignored. Negative quantities are indicated by the minus sign "-", and initial zeros are ignored. Whenever the integer values become so large as to overflow the capacity of the arithmetic processor, the overflow value Z of the function is taken. The overflow value is always treated as if it were produced by an active function. The arithmetic functions are: #(ad,D1,D2,Z) "add", #(su,D1,D2,Z) "subtract", #(ml,D1,D2,Z) "multiply" and #(dv,D1,D2,Z) "divide". They all take four arguments. In these functions, D2 is subtracted from D1, and D1 is divided by D2, with the answer being the largest integer contained in the dividend.

Boolean Functions

Boolean TRAC functions operate on strings of bits (of value 0 or 1), i.e., on Boolean vectors. The bit strings are represented by octal digits, with each digit representing three bits. Thus the bit strings have lengths in multiples of three. The octal digits are looked for at the tail end of the 01 and 02 strings, and any non-octal prefix matter is deleted. The functions are: #(bu,01,02) "Boolean union," #(bi,01,02) "Boolean intersection," #(bc,01) "Boolean complement," #(bs,D1,01) "Boolean shift" and #(br,D1,01) "Boolean rotate." The bit strings are right justified. In the Boolean union the shorter string is filled out with leading zeros, while in the Boolean intersection, the longer string is truncated at the left. In the complement, shift and rotate, the length of the bit string remains the same. Shift is to the left by the number of places specified by the decimal D1 (with leading nondecimal matter being deleted) when D1 is positive, and to the right when D1 is negative. The new positions created by the shift are filled with zeros. Rotate is also to the left or right, with positive or negative values of D1. The digits displaced from one end of the vector are added to the place created at the other end.

Decision Functions

#(eq,X1,X2,X3,X4) "equals" (five arguments). This is a test for string equality. If X3 is equal to X2, the value is X3; otherwise it is X4.

#(gr,D1,D2,X1,X2) "greater than" (five arguments). This is a test of numerical magnitude. If the integer decimal number at the tail of string D1 is algebraically greater than the number at the tail of D2 the value is X1; otherwise it is X2.

External Storage Management Functions

#(sb,N,N1,N2,···) "store block" (three or more arguments). This null-valued function assembles the group of forms named N1, N2, etc., and stores them as a block in an external storage area. The form names, segment gaps, etc., are all preserved. When the forms have been put into the external storage, they are erased from form storage. A new form is created with name N and with a string which is the address of the block in external storage.

#(fb,N) "fetch block" (two arguments). This null-valued function is the converse of the store block function. The name N is the name of the block to be fetched. The function restores to form storage all the forms in the block, complete with names, segment gaps, pointers, etc. It does not erase the block in external storage, nor the form named N.

#(eb,N) "erase block" (two arguments). This null-valued function erases the form name N and also the group of forms in the block in external storage.

These functions permit forms to be moved to and from the main memory and also protect the stored forms from accidental erasure. They also permit one to build a "storage tree." By this technique, a group of forms can be stored under a group name, a set of group names can be stored under a section name, and so on.

Diagnostic Functions

#(ln,X) "list names" (two arguments). The value of this function is the list of names in the name list, i.e., the names of all the forms in form storage. Each name in the value string is preceded by string X. If X is the character pair "carriage return, line feed" protected by double parentheses, the names will be listed in a column.

#(pf,N) "print form" (two arguments). This causes the typing out of the form named N with a complete indication of the location and ordinal values of the segment gaps.

#(tn) "trace on" (one argument). This null-valued function initiates the trace mode in which, as the computation progresses, the neutral strings for each function are typed out. Typing the backspace key causes evaluation of the function, and presentation of the neutral strings of the next. Typing anything other than backspace causes initialization. Carriage return may be used instead of backspace.

#(tf) "trace off" (one argument). This is a null-valued function which terminates the trace mode without initialization. Both trace on and trace off functions may be placed anywhere in a procedure.

EXAMPLES OF TRAC PROCEDURES

1. The distinction between active and neutral functions is usually puzzling. In essence, the value from an active function is rescanned, while in the neutral function it is not. The following example shows the action of the protective parenthesis, the neutral and the active forms of the function. Consider that both #(ds,AA,CAT)' and the simple program #(ds,BB,(#(cl,AA)))' have been presented to the processor. Then,

    #(ps,(#(cl,BB)))', #(ps,# #(cl,BB))', #(ps,#(cl,BB))'

prints out, respectively:

    #(cl,BB), #(cl,AA), CAT

2. When the processor is quite full, it is often desirable to delete all forms but one of a particular name. The procedure #(ds,N,# #(cl,N)#(da)) will accomplish this. Here # #(cl,N) reads the form N into the processor, and it is held in the neutral string while all the forms in memory are erased. The form is then redefined with its original name. In this example, segment gaps are lost.

3. This and the following example illustrate the extension of TRAC capabilities through defining and storing of suitable procedures. The calculation of the factorial of a number can be done by simple recursion:

    #(ds,Factorial,(# (eq,1,X,1,

    (#(ml,X,#(cl,Factorial,#(ad,X,-1))))

    )))#(ss,Factorial,X)'

Then the call #(cl,Factorial,5)' produces the result 120.

4. Many users will prefer to have TRAC supply its own sharp signs and parentheses when calling a procedure. The following will do this:

    #(ds,English,(#(ps,

    # (cl,#(rs))(

    ))#(cl,English)))'

To start this action, we use #(cl,English)', and then if one types in Factorial,5' the response is 120 followed by carriage return, line feed. The action is terminated by #(dd,English)'.

Acknowledgments. Special thanks are due to my collaborator L. Peter Deutsch for his assistance in the development and implementation of TRAC. REFERENCES

    Mooers, C. N. TRAC, a text handling language. Proc. ACM 20th Nat. Conf. Cleveland, Aug. 1965, pp. 229-246.
    TRAC--a procedure defining and executing system. Mem. V-157, Rockford Research, Cambridge, June 1964.
    Eastwood, D. E., and McIlroy, M. D. Macro compiler modification of SAP. Mem., Comput. Lab., Bell Telephone Labs., Murray Hill, N.J., Sept. 3, 1959. (Unpublished)
    McIlroy, M. D. Using SAP macro instructions to manipulate symbolic expressions. Mem., Comput. Lab., Bell Telephone Labs., Murray Hill, N.J., 1960. (Unpublished)
    Strachey, C. A general purpose macrogenerator. COMPUT. J. 8, 3 (1966). 

© Copyright 2000 by The TRAC Foundation, Inc.

=====================================================

TRAC Foundation

Appendix C: The TRAC Processor

This appendix describes the TRAC processor and analyzes the rules followed by the TRAC interpreter.

Contents

C.1

Introduction to the TRAC Processor

C.2

Fundamentals

C.3

The Guiding Principle

C.4

The Five Meanings of Primitive

C.5

Two Aspects: Langauge and Machine

C.5.1 The Language Aspect

C.5.2 The Machine Aspect

C.6

The TRAC Interpreter

C.7

TRAC Syntax Characters

C.8

The Simplest Case: No Nested Primitives

C.9

Nested Primitives

C.10

The i Suffix

C.11

The d Suffix

C.12

The z-Return Argument

C.13

Protective Parentheses

C.13.1 Commas

C.13.2 White Space and Control Characters

C.14

The TRAC Memory System

C.15

The Rules of TRAC Interpretation

Back to TRAC Manual: Table of Contents

© Copyright 2000 by the TRAC Foundation, Inc. TRAC is a trademark of the TRAC Foundation, Inc. This document does not constitute a license to use TRAC. License conditions will be published later.

Note on Document Conventions: Bold monospace type indicates characters that the user enters. Monospace type indicates information that the TRAC processor generates and displays on the screen. C.1 Introduction to the TRAC Processor

This appendix amplifies the information in Chapter 1, Introduction to TRAC, providing more details about the TRAC.DLL processor and its interpreter, and providing examples to illustrate the concepts. This appendix explains two vital aspects of the TRAC processor:

    The manner in which TRAC finds the arguments of a primitive, which is important because all of the action of TRAC takes place within the argument of some primitive.

    The tree-structured data storage structure used by TRAC. 

This appendix also provides a step-by-step analysis of the actions of the TRAC interpreter. TOP C.2 Fundamentals

The term TRAC processor refers to the interaction of the physical computer and the TRAC program. The TRAC processor operates on scripts, which are descriptions of computer actions written in TRAC language.

The actions controlled by a TRAC script may be very general. They can include such things as:

    Sending characters to be displayed on the screen or to the serial port (output).
    Taking characters from the keyboard or from the serial port (input).
    Creating disk files and moving data to them.
    Manipulating strings of characters (text).
    Executing compound actions.
    Passing the result from one action to another.
    Starting and using other software available to the computer.
    Performing the action of any of the primitives of the TRAC language. 

TOP

C.3 The Guiding Principle

The fundamental principle of the TRAC language and its processor is that any activity done by a computer, no matter how complex, can be analyzed into smaller and smaller operational units, each unit performing its own task, and then passing its results from one unit to another, to produce the final cooperative result.

A primitive is the lowest level action unit in TRAC. The TRAC language has more than eighty primitives, chosen for their functional capability. The primitives can act jointly by passing a strings of characters from primitive to primitive. C.4 The Five Meanings of Primitive

The term primitive has several meanings in the description of the operation of the TRAC language and processor. In this manual, the term primitive can mean any of the following:

    The description of the primitive action as defined in the primitive reference chapters.
    The machine code in the TRAC processor that actually produces the action of the primitive.
    The letters of the mnemonic that specifies the primitive, and is the first argument in a primitive statement.
    A string in a script enclosed by the header and trailer symbols : ( and ) that delimit a primitive statement. The primitive statement may contain as arguments other, nested, primitive statements.
    A primitive statement that is ready for execution, which is a statement for which the interpreter has analyzed all of the arguments. 

TOP C.5 The Two Aspects: Language and Machine

The operation of TRAC in a computer has two aspects: the language aspect, and the machine aspect. The language aspect concerns the TRAC language, its concepts, its manner of describing a computer activity, and its repertoire of actions. The machine aspect concerns the physical computer, its memory, its peripherals, and the program code implementing TRAC.

The language aspect and the machine aspect are both important, and they parallel each other. At times this appendix speaks of one aspect and then the other, often without indicating the transition. C.5.1 The Language Aspect

The language aspect and the machine aspect of TRAC are tied very closely together, since TRAC is an interpretive language and its processor is an interpreter. The interpreter operates directly upon the source description, the script containing primitive statements. This is unlike some other programming languages in which the source description is transformed by a compiler into object code that the computer executes.

Since the TRAC language has no compile step, what you write in a script is the action the processor performs.

The TRAC processor follows the logic of the TRAC language script, performing actions in the exact sequence that the script specifies. There are no exceptions in the logic of the TRAC language. This appendix emphasizes the logic of the process described in the language, but also describes some collateral relevant matters of the machine aspect. C.5.2 The Machine Aspect of TRAC

The code body of the TRAC processor is in two parts, the program code area and the data space area. The program code area contains the code implementing the more than 80 primitives. The program code area also contains the individual units of code for the interpreter and the dispatcher. (For information on the interpreter, see Section C.6, "The TRAC Interpreter." For information on the dispatcher, see Section C.8, "The Simplest Case, No Nested Primitives.")

In the code body, the data space area is divided into two parts, the workspace and the forms store. The workspace is a dynamic area the interpreter uses for the analysis of scripts. The forms store is the place for temporary storage of data; it is the memory of the TRAC processor. The forms store allows for a tree?structured arrangement of data items. TOP C.6 The TRAC Interpreter

Central control of the TRAC processor is the role of the interpreter. The interpreter analyzes a script in the workspace and orchestrates the computer actions that the script specifies. The processor initially moves a script into the workspace, where the interpreter begins analyzing it, starting at the left end of the script.

A script may contain any alphabetic letter (a-z, A-Z), numerical digit (0-9), punctuation mark (. , ; : ^ ), any special ASCII character (#$%^), or any ASCII control character (which is invisible as displayed). The only characters a script cannot contain are the tab character, the TRAC terminate input meta character, and the dump input buffer meta character (the @ sign). (For information on the terminate input meta character, see Section C.9, "The Case Of Nested Primitive Statements." For information on including a tab in a script, see Section 1.5, "Strings.")

A script contains TRAC primitives statements describing desired actions. The interpreter recognizes a primitive statement within a script because the statement is delimited by the following header and trailer symbols:

:( )

The symbol at the head of the primitive statement is the colon and open parenthesis combination of characters. The symbol at the tail of the primitive is the close parenthesis character. The content of the primitive statement consists of the characters between these two marker symbols. TOP

C.7 TRAC Syntax Characters

Syntax characters in any language have the purpose of indicating the essential parts of the language. In ordinary written text, like this exposition, the important syntax characters are the space character, the comma, and the period. These syntax characters indicate the division of the text into words, phrases and sentences. In English text, many more syntax characters are also used.

In TRAC, there are only four syntax characters. They are:

    : colon
    ( open parenthesis
    ) close parenthesis
    , comma 

TOP

C.8 The Simplest Case: No Nested Primitives

The simplest case is that of a script in which primitives are not nested one inside the other. The primitives linearly follow one another in the script, denoting that one action follows another. Example 1 illustrates a linear script.

    Example 1

    :(aa,5,6)
    :(o,Hello)
    :(s,textform,(Here is some text.))' 

The interpreter analyzes the details of a script in a linear manner, working from left to right, taking the primitive statements one at a time. It finds and records, or marks, the extent (from head to tail) of a statement, and then marks the arguments contained in the primitive statement.

Arguments supply information telling the primitive what to do. Arguments are separated by commas. In general, a TRAC argument may be any string. Example 2 is a script that consists of one primitive statement. In the statement, the arguments are limited to alphabetic characters:

    Example 2

    :(fo,abc,fail)' 

In the above command, the file open primitive fo is directed to open the file named abc. In case the primitive cannot open the file, the primitive statement provides the argument fail, which the fo primitive uses to report the failure.

There are three arguments in the script; each argument is a character string:

    fo abc fail 

The commas in the primitive are separators and are not part of an argument. You can make a comma a part of an argument by using protective parentheses, as described in Section C.13, "Protective Parentheses."

When the interpreter has completely marked out the full extent of a primitive from head to tail in the script and all the arguments are ready, the primitive is ready for execution.

At this stage, the interpreter passes the first argument string to the code of the dispatcher. The dispatcher verifies that the argument string received is a valid mnemonic for a TRAC primitive. Each TRAC primitive has its own unique mnemonic, which is a string of one or more characters that mnemonically suggest the action of the primitive. If the argument is a valid mnemonic, the interpreter passes control to the code for carrying out the primitive.

This code then carries out the actions of the primitive. The data that the primitive requires for execution is supplied from the marked-out arguments of the primitive statement.

At the completion of the action of the code for the primitive, the primitive may have a string produced by the commanded action. This string is the value string produced by the primitive. The processor sends the value string back to the interpreter for possible further action. The interpreter may do any of several things with the string.

The value string may have one, many, or no characters. A value string with no characters is a null string, which is a perfectly acceptable string in TRAC. The processor treats a null string the same way as it treats a string containing characters. The processor handles a string by placing pointers at the head and the tail characters of the string. For a null string, these two pointers coincide.

The statement in Example 2 produces a null string if it is successful. If the fo primitive could not open the file, the primitive statement produces the third argument, which is a z-return. For information on z-return arguments, see Section C.12, "The Z-Return Argument."

Control is now passed to the interpreter. The interpreter, which has control of the workspace, deletes the entire sequence of characters making up the just-executed primitive statement, and closes up the vacated space in the workspace.

The TRAC processor cleans up after every action. There is no deferred garbage collection, so consequently the processor has no unpredictable pauses.

The interpreter now continues its action, moving to the right in the workspace, examining the not yet interpreted sections of the script and looking for more primitive statements requiring action. Since the Example 2 script consisted of only one primitive, control returns to the processor, which runs the idle script and waits for further input. If the script had contained other primitives in serial order, the interpreter would find each primitive in order, and cyclically repeat the actions described in this section for each primitive. TOP

C.9 Nested Primitives

Frequently a primitive statement contains arguments that are, or that contain, other primitive statements. These inner primitive statements are nested inside the enclosing outer primitive. This nesting of primitive statements provides the means by which TRAC primitives cooperate and pass data from one to another. In Example 3, the script fragment is a simple nested statement:

    Example 3

    :(fo,:(i),fail)' 

The input primitive i is enclosed inside the file open primitive fo. The :(i) primitive statement describes an action that must occur before the fo primitive can execute. In Example, 3 the i primitive supplies the file name that the fo primitive needs to open a file. However, the literal string :(i) is not a file name.

TRAC has a fundamental rule of execution of its primitive statements: A primitive cannot be executed until all its arguments have been interpreted.

In Example 3 the second argument of the fo primitive statement has not been executed. Therefore, the execution of the fo primitive statement must be deferred until :(i) is executed.

The interpreter analyzes a primitive statement and marks out the arguments in the statement. The interpreter continues analyzing until it finds the symbol indicating the tail end of the primitive. However, if the interpreter finds another primitive statement inside an argument while analyzing the statement, a new action takes place. The interpreter saves the complete state of its analysis up to this point, and begins a new analysis of the primitive statement that it has just discovered.

The interpreter saves information about the enclosing primitive statement, including the location within the workspace of the head of the deferred statement, as well the pointers marking out all of the arguments up to the point where the new primitive statement was found.

The interpreter now analyzes the new primitive statement and its arguments. If the analysis can continue to the tail end of the new primitive statement, the first argument of the new statement (the mnemonic of the new primitive) is referred to the dispatcher. Control then passes to the applicable code for the primitive of the new statement, and the action of the new statement is performed.

In Example 3, the input primitive takes in a string typed at the keyboard. For the example, the string entered at the keyboard is the following:

    abc' 

The apostrophe here is something new. The apostrophe is the TRAC terminate input meta character. This character tells the TRAC input primitive that the input stream from the keyboard is complete, and that the primitive should take the string input provided so far and perform its action. The primitive removes the terminate input meta character from the input string and produces the rest of the string as its value string. By default, the apostrophe is the TRAC terminate input meta character, but you can specify another character as the terminate input meta character with the ic primitive. (For more information on the is primitive, see Chapter 6, "Extended Input and Communication Primitives.")

You can use the Enter key as the TRAC terminate input meta character, but do so only if you intend to enter a single line at a time. Usually you would choose some character other than the Enter key to be the terminate input meta character because the Enter key produces (in TRAC) the two ASCII characters line feed and carriage return. If you want to input multi-line strings, you need both the line feed and carriage return formatting characters to separate the lines.

By definition of the input primitive, the value string of the i primitive is the sequence of characters provided to it as typed at the keyboard.

When the action of the primitive is completed, the primitive produces its value string to the interpreter. The interpreter, in managing the workspace, now erases the character string comprising the primitive statement that caused the action, and inserts the new value string in its place.

In our example, the value string produced by the i primitive now replaces the :(i) statement literal string in the workspace, so the workspace now has:

    :(fo,abc,fail)

    ^ 

The caret (^) marks the location where the interpreter action resumes, at the tail end of the replaced i primitive. The argument string abc from the input action of the :(i) primitive statement now is the second argument of the file open primitive.

The saved state of the interpreter is restored, and interpreter action resumes at the tail end of the new inserted string. If the interpreter analysis reaches the tail end of the enclosing primitive statement without finding another nested primitive statement, then all the arguments of the enclosing primitive statement have been executed. The arguments are now all marked out by commas, which are not part of the arguments themselves.

At this point no more inner primitive statements are waiting for execution, so the enclosing primitive executes. In the present example, the fo primitive now tries to open the file named abc. If the file opens, the fo primitive produces a null string and its action is complete. If the file does not open successfully, the fo primitive produces its third argument, which is a z-return argument. In our example, the third argument is fail. (For more information on z-return arguments, see Section C.12, "The Z-Return Argument") TOP

C.10 The Case of the i Suffix

The first argument to a primitive statement is always the primitive's mnemonic, which specifies the primitive action to execute. This mnemonic may have an i suffix. The i suffix has a very important effect upon the action of the interpreter. You can use the i suffix on the mnemonic of any of the TRAC primitives to modify the way the interpreter handles the value string produced by the execution of the primitive statement.

In Example 4, the i primitive has the i suffix:

    Example 4

    :(fo,:(ii),fail)' 

The i suffix on the mnemonic of a primitive causes the interpreter to restart the interpretive action at the head, rather than at the tail, of the value string that the primitive statement produces and that replaces the primitive statement in the workspace. The result of this is that the interpreter interprets the inserted value string when the action of the interpreter resumes. This interpretation of the value string produced by a primitive statement can be very useful in TRAC operations.

For the current example we need to introduce the TRAC concept of forms. Forms are named items of data stored in TRAC forms store memory. For our example, assume that the keyboard operator does not know the name of the file to supply as the second argument in the fo primitive statement, but the operator does know the name of a TRAC form that contains the desired filename. Let's say the form is named aa.

When it comes time to supply the script with information for opening the file, instead of supplying the filename, the operator can now furnish a recall command to retrieve the filename stored in TRAC forms store. The recall primitive r recalls the contents of a stored form.

So the interpreter starts interpreting our example of the fo primitive. The interpreter stops the interpretation of the fo primitive after finding the :(ii) primitive statement. The interpreter saves the state of the interpreter action and waits for input from the keyboard. At the keyboard, the operator types in:

    :(r,aa)' 

The value string produced by the ii primitive is:

    (r,aa) 

The interpreter replaces the :(ii) string of the workspace with the string :(r,aa). The temporary result is:

    :(fo,:(r,aa),fail) 

Now the question is: where does the interpretation resume? Does the action resume at the head or the tail of the new replacement string? THe answer is that the location for resuming interpretation is always determined by whether or not the primitive statement has an i suffix on the mnemonic.

If there is no i suffix, the interpretation resumes at the tail end of the replacement string, which was the case in Example 3. If there is an i suffix, the interpretation resumes at the head of the replacement string. Since the :(ii) statement in our Example 4 has the i suffix, interpretation resumes at the red colon in the workspace:

    :(fo,:(r,aa),fail) 

Interpreter action begins at the ^, and the :(r,aa) primitive statement is now discovered, analyzed, and executed. The primitive statement produces the value string abc, which is the desired filename. In the workspace, the :(r,aa) string now replaced by the string abc. Also, since the :(r,aa) primitive statement does not have the i suffix on the mnemonic, interpretation of the fo statement resumes at the tail end of the inserted abc string (at the red comma):

    :(fo,abc,fail) 

The interpreter marks the final argument, which in this case is the z-return argument fail. Since there are no more primitive statements nested in this final argument, the fo primitive now executes with the arguments shown. TOP

C.11 The Case of the d Suffix

Sometimes it is convenient to discard the value string produced by a primitive. The d suffix has that result. If a primitive statement has the d suffix in the mnemonic, the processor carries out the action of the primitive statement. However, instead of the replacing the primitive statement in the workspace with the value string produced by the primitive action, the interpreter:

    Replaces the primitive statement with a null string
    Discards the value string the primitive produced (unless the value string is a z-return argument)
    Closes up the gap in the workspace
    Resumes interpretation at the spot closed up 

TOP

C.12 The z-return Argument

Sometimes you want to be able to specify what action to take if a primitive does not or cannot perform its defined action. For example, the inability to open a file may be an expected result of the file open primitive action, and you may want to provide an alternative action in that case. The z-return argument of the TRAC language provides such a notification, and the means for a TRAC script to take a new course of action.

Many TRAC primitives have designated z-return arguments. When a primitive does have a z-return argument, the definition of the primitive specifies exactly when this argument comes into action. When a primitive with a z-return argument encounters the specified difficulty, the primitive produces the z-return argument string specified in the primitive statement. Note that z-return arguments are defined in the code of the primitive. You cannot arbitrarily turn any of the other arguments in a primitive statement into a z-return argument.

The production of a z-return argument overrides the usual manner of resuming the interpretation according to whether or not there is an i suffix on the mnemonic of the primitive statement. If a z-return condition occurs and the primitive statement produces the z-return argument, the interpreter always resumes interpretation as if there were an i suffix on the mnemonic of the primitive statement.

In Example 5, fail is a z-return argument:

    Example 5

    :(fo,abc,fail)' 

The definition of the file open primitive states that the third argument is a z-return. The primitive produces the third argument if the specified file did not open. So, in Example 5, if the processor cannot open the file abc, the fo primitive statement produces the z-return argument, which is the string fail.

    Example 6

    :(o,:(fo,abc,fail))' 

The script in Example 6 would report the failure of the nested fo primitive statement by using the output primitive o according to the following steps:

  1. :(o,:(fo,abc,fail))'
  2. :(o,fail)
  3. fail

The script displays fail on the screen, and then takes no other action.

The z-return is the most useful when you use it to automatically begin a corrective action. It can do this by recalling and executing a recovery script you previously stored in a text or macro form.

The recall primitive r with an i suffix, ri, recalls and places into execution any named recovery script. Thus you can use an ri primitive statement as the z-return argument in any primitive statement that has a designated z-return argument.

The ri primitive statement in Example 7 recalls and executes the stored script named recovery if the fo primitive statement cannot open the file abc:

    Example 7

    :(fo,abc,(:(ri,recovery)))' 

Note that the ri primitive statement in Example 7 is inside another set of parentheses. These extra parentheses protect the statement from immediate interpretation. To use a primitive statement as a z-return argument, you must enclose the statement in such protective parentheses. See Section C.13, "Protective Parentheses." TOP C.13 Protective Parentheses

In most of our examples so far, when a primitive statement was within the argument string of another primitive statement, the statement within the argument was executed immediately when it was found by the interpreter. This is the usual intent in a script.

However, there are situations in which you may not want to immediately execute a statement within an argument. You may want the statement to execute at some other point in the script. For example, you may want to simply display the primitive statement and not execute it at all. Another example is that you may want to store a primitive statement and then retrieve and execute the statement at some other time, as seen in the z-return argument in the fo primitive statement in Example 7 in Section C.12, "The z-return Argument."

To protect strings from immediate execution by the TRAC interpreter, you can use protective parentheses. A string inside protective parentheses is a protected string.

The store primitive s creates a form and, for a text or macro form, stores a string. The syntax for a store primitive statement is the following:

    :(s,<address>,<string>) 

In this syntax statement, the angle bracket markers < > enclose a word or phrase that suggests the kind of argument string to use in the argument. An s primitive statement takes an address as its second argument and a string as its third argument. The address of a text form is the node_path to and name of the form. (For information on forms see Section 1.7, "Forms," and Section C.14, "The TRAC Memory System." For information on addresses see Section 1.8, "Addressing Forms.")

The statement in Example 8 stores the string Hello! in the text form tform1:

    Example 8

    :(a, tform1, Hello!)' 

Since TRAC has the absolute rule that every argument must be interpreted before the action of any primitive can take place, you cannot store a primitive statement without protecting the statement from immediate execution.

The statement in Example 9 does not store the string :(o,Hello!). Instead, the statement stores a null string in the form tform2:

    Example 9

    :(a, tform2, :(o,Hello!))' 

In analyzing the Example 9 statement, the interpreter executes the output statement, which displays Hello! on the screen and produces a null string. In the workspace, the interpreter replaces the output statement string with the null string the statement produced. The interpreter then executes the store primitive, which creates the text form tform2 and stores the null string in the form.

To protect the statement from immediate execution, you can enclose the statement in protective parentheses, as shown in Example 10:

    Example 10

    :(a, tform3, (:(o,Hello!)))' 

This time the store statement creates the text form tform3 and stores in it the string :(o,Hello!). When analyzing the argument, the interpreter removes the protective parentheses.

In the interpretation of an argument string, if the interpreter encounters an open parenthesis character, the interpreter:

1. Removes the character 2. Sets its internal parenthesis count to one 3. Stops the usual interpreter action 4. Enters protected mode

In protected mode, the interpreter's inspection of the characters in the workspace continues, character by character, moving to the right. However, now the interpreter does not execute . primitive statements it encounters and does not notice commas, which means it does not mark arguments.

If the interpreter encounters additional open parenthesis characters, the interpreter increments its internal parenthesis counter by one for each ( character. If the interpreter encounters additional close parenthesis characters, the interpreter decrements its internal parenthesis counter by one by one for each ) character.

At all times while the interpreter's internal parenthesis counter is greater the zero, no other action is taken with respect to the characters inspected. These characters are inert and do not, for the moment, become part of the action.

When the internal parenthesis counter returns to zero, the interpreter leaves protected mode. The interpreter removes the close parenthesis character and resumes its normal unprotected mode action.

Following these rules for protective parentheses, the interpreter leaves intact the fo and o primitives in the following argument string and does not execute them:

    ,(:(fo,abc,fail) ((xyz)pq) (((:(o,hello))))), 

If the above string were an argument in a primitive statement, after analyzing the argument the interpreter would leave the following string in the workspace:

    :(fo,abc,fail) ((xyz)pq) (((:(o,hello)))) 

Note that protected mode not only protects the primitive statements from immediate execution, it also protects characters such as the inner parentheses, commas, colons, spaces and all other characters, including control characters, from deletion by the interpreter. TOP C.13.1 Commas

In analyzing a primitive statement, the TRAC interpreter interprets a comma as a symbol that separates an argument within the primitive statement, unless the comma is in a protected string. Since commas delimit the argument string, the interpreter does not interpret the commas as part of the argument string itself. However, sometimes you may want to have commas in an argument string. You can include a comma in a text string by enclosing the string in protective parentheses.

In Example 11, the output primitive statement does not do the obvious, which is to display on the screen Hello, my name is Joe:

    Example 11

    :(o, Hello, my name is Joe.)' 

Instead the statement only displays Hello because only the second argument of the output primitive goes to output. The comma following Hello ends the second argument, and the o primitive ignores any characters after the second argument.

To have the o primitive print the entire string, including the comma and the space characters, you must put the text in protective parentheses, as in Example 12:

    Example 12

    :(o,(Hello, my name is Joe.))' 

The statement in Example 12 displays the following string on the screen:

    Hello, my name is Joe. 

To specify one or more commas as an argument, put them in a protected string, as in Example 13:

    Example 13 

    :(o,(Commas: ,,, ,,,))' 

The statement in Example 13 displays the following string on the screen:

    Commas: ,,, ,,, 

C.13.2 White Space and Control Characters

The space, carriage return, and line feed characters do not display a graphic character. Instead they move the point of display on the screen. Other ASCII control characters such as Ctrl+C also do not display on the screen.

When analyzing a string, the TRAC interpreter deletes from the workspace all unprotected control and white space characters.

You can, however, protect such characters from deletion by enclosing them in protective parentheses. The TRAC processor preserves and handles (moves, stores, and so on) any characters in a protected string, such as control characters, or indeed any eight-bit code combination such as those found in binary files. TOP C.14 The TRAC Memory System

The memory system of the TRAC processor is the area of the processor devoted to the storage of data and scripts. The basic data unit stored by TRAC is called a form. A form consists of three parts: pointers, name, data. Forms are kept in the forms store, a contiguous area of memory. There are three kinds of forms: text forms, macro forms, and node forms.

The pointers of a form are not directly accessible to scripts or to the TRAC user, though the action of some of the TRAC primitives may read or modify the pointers. The pointers are part of the infrastructure of the TRAC memory system.

To create a form, you must supply a name for the form in the primitive statement. The name of a form is a string of characters. A name may be a null string with no characters, or a string of any length up to the entire amount of space available in the forms store memory area. You can ascertain the size of the free space in memory through the status of workspace primitive xs.

A text form stores data, which may be any sequence of eight-bit bytes. The most frequent use of a text form is to store text strings of ASCII characters. The data part of a text form, like the name part, may store strings of any length, up to the entire amount of space available in the forms store memory area. A text form may store literary text (words and sentences) or TRAC scripts that may be executed.

A macro form stores macros, which consist of script in ASCII characters, supplemented by binary twiddles interspersed in the script. Twiddles correspond to the formal variables of functions in conventional programming. Twiddles provide the method by which TRAC supplies arguments to a macro when a macro is called into execution.

The following is the text for a macro that opens a file. In the text, <1> and <2> are text indications of the twiddles:

    :(fo,<1>,<2>) 

In twiddles, the angle bracket characters are a necessary part of the twiddle argument. The angle brackets must enclose a digit in the range of 0 to 255. You can store a script as a macro form with the make macro primitive mm. The primitive statement in Example 14 stores a macro form with the name open (note the protective parenthesis around the fo primitive):

    Example 14

    :(mm,open,(:(fo,<1>,<2>))' 

To retrieve and execute the macro, use the recall primitive r with the i suffix, ri, as in Example 15:

    Example 15

    :(ri,open,abc,fail)' 

The r primitive retrieves the macro form open and produces into the workspace the contents of the macro form as its value string. In the value string, the interpreter replaces the twiddles of the macro form with the argument strings abc and fail. The i suffix causes the TRAC interpreter to interpret the value string so the fo primitive executes, using the parameters supplied in the ri statement:

    :(fo,abc,fail) 

This fill-in-the-form capability of TRAC is the origin of the term form for the basic TRAC storage element.

In the TRAC processor memory, each form constitutes a contiguous string of bytes in which there are no gaps. The processor enters forms into the forms store, which is a large buffer. The processor enters the forms on a last in, last-on-top basis, in a linear stack arrangement.

You can retrieve a form from any location in the forms store. In retrieving a form, the processor only makes a copy of the form and does not move the original form. You can also rewrite or move a form. Moving or rewriting a form does change the form's location in the forms store.

All three types of form are stored in the same area. The processor does not segregate forms by type. The processor accesses the data in a form only by means of the form name.

The node forms do not directly hold data. Node forms provide the means for structuring the forms store memory.

The node form acts very much like a directory of a conventional computer disk system. That is, a node form acts as a container of other forms, including other node forms. Node forms enable the TRAC forms store system to create and administer a private tree?structured forms store architecture.

Since a node form contains contiguously-stored forms, TRAC primitives can move, store (on external disk), or retrieve entire nodes (subdirectories) of the forms store area. All the forms of a node occupy contiguous computer memory. In other words, the processor can treat an entire branch of the tree-structured forms store as a unit, and you can move the unit with a single primitive statement that specifies that node. (For information on the primitives that manipulate forms, see Chapter 7, "Memory Primitives.") TOP

C.15 The Rules of TRAC Interpretation

The TRAC interpreter operates in the workspace of the processor. When the processor starts, it loads an idling script into the empty workspace. The idling script is the following:

        :(o,:(ii)( 

    ))

        :(ri,idle) 

This idling script says "interpret the input from the keyboard and output the value string produced, then output a carriage return and line feed, then run the idling script again."

The action of the interpreter is cyclic and goes from left to right in the workspace, character by character. The interpreter has two modes of operation, protected and unprotected. The interpreter remembers locations that it marks while it is analyzing the characters in the workspace. The state of the interpreter consists of the set of locations marked by the interpreter.

The TRAC interpreter operates according to the following set of rules, which do not have exceptions. The rules are: TOP The interpreter cycle begins in unprotected mode:

Rule 1. The interpreter starts before the left-most character, and goes to Rule 2.

Rule 2. If there is a next character, the interpreter

    - Finds the next character;

    - Holds the character for comparison;

    - Goes to Rule 3.


    If there is no next character, the interpreter


    - Clears the workspace;

    - Copies the idling script into the workspace;

    - Goes to Rule 1. 

Rule 3. If the character from Step 2 is an open parenthesis, and if the previous character was a colon, then the two characters identify a primitive statement header group :( . The interpreter then:

    - Stores the state of the interpreter action up to this point;

    - Marks the location of the colon in the workspace as the beginning of a new Primitive statement;

    - Marks the location following the open parenthesis as the beginning of the first argument of the new statement;

    - Goes to Rule 2. 

    If the character from Step 2 is an open parentheses but the preceding character was not a colon, the interpreter goes to Rule 4.

    If the character from Step 2 is not a colon or an open parentheses, the interpreter goes to Rule 5. 

Rule 4. The interpreter comes here from Step 2 with an open parenthesis character that was not part of a primitive statement header group. The interpreter now:

    - Removes the open parenthesis character from the workspace;

    - Goes into the protected mode;

    - Goes to Rule 8. 

Rule 5. If the interpreter has found one of the ASCII control characters or the space character, it removes the character from the workspace and goes to Rule 2. Otherwise, it goes to Rule 6.

Rule 6. If the interpreter has found a comma, the interpreter:

    - Marks the previous character location as the end of one argument and the next character location, beyond the comma, as the beginning of another argument;

    - Goes to Rule 2. 

    If the interpreter has not found a comma, the interpreter goes to Rule 7. 

Rule 7. If the interpreter has found a close parenthesis character, the interpreter:

    - Marks the previous character location as the end of an argument;

    - Takes the ) character as the end of the current primitive statement.

    - Goes to Rule 13.

    If the interpreter has not found a close parenthesis character, the interpreter:

    - Leaves the character as part of the argument;

    - Goes to Rule 2. 

TOP

The protected mode cycle begins:

Rule 8. The interpreter comes to this rule when it enters the protected mode after finding an open parenthesis character. The interpreter:

    - Sets its parenthesis counter for the current state to 1;

    - Locates the next character;

    - Goes to Rule 9. 

Rule 9. If the interpreter has found neither an open parenthesis character or a close parenthesis character, the interpreter:

    - Leaves the character in the workspace;

    - Finds the next character in the workspace;

    - Goes to Rule 9.

    If the interpreter does have an open parenthesis character or a close parenthesis character, the interpreter:

    - Goes to Rule 10 if the character is an open parenthesis.

    - Goes to Rule 11 if the character is a close parenthesis. 

Rule 10. The interpreter has found an open parenthesis character. The interpreter:

    - Increments the parenthesis counter by 1;

    - Does not delete the ( character;

    - Finds the next character;

    - Goes to Rule 9. 

Rule 11. The character is a close parenthesis character. If the parenthesis count is not 0, the interpreter:

    - Decrements the parenthesis counter by 1;

    - Does not delete the ) ;

    - Finds the next character;

    - Goes to Rule 9.

    If the parenthesis count is 0, the interpreter goes to Rule 12. 

Rule 12. The character is a close parenthesis character, and the parenthesis count is 0. The interpreter:

    - Deletes the ) character from the workspace;

    - Returns to unprotected mode;

    - Goes to Rule 2.

TOP

The protected mode cycle ends.

The interpreter cycle ends.

Executions begins:

Rule 13. The interpreter comes here if it has found a close parenthesis character signaling the execution of a primitive statement. The interpreter:

    - Passes the first argument of the primitive statement to the dispatcher which in turn sends control to the TRAC code implementing the primitive described by the first argument;

    - Goes to Rule 14. 

Rule 14. The code for the primitive carries out the primitive's defined action according to the arguments that the interpreter marked out for the primitive statement. In addition to the primitive action, the code may produce a value string. At the end of the primitive action, the code returns control to the interpreter for disposition of any value string produced by the primitive statement. The interpreter continues with Rule 15. TOP Execution ends.

Disposition of the value string begins:

Rule 15. The interpreter now takes control. The interpreter:

    - Deletes from the workspace the entire primitive statement just executed;

    - Marks the delete location in the workspace;

    - Determines whether there is an i or d suffix character to the first argument of the just-executed primitive statement;

    - Goes to Rule 16. 

Rule 16. If the execution of the primitive statement produced a value string, and that value string is a z-return argument, the interpreter:

    - Inserts the produced string into the workspace at the delete location marked;

    - Restores the stored state of the interpreter;

    - Resumes interpretation in the workspace beginning at the head (left end) of the inserted string;

    - Goes to Rule 2. 

    If the value string is not a z-return argument, the interpreter goes to Rule 17. 

Rule 17. If the suffix character is d, the interpreter:

    - Discards the value string;

    - Resumes interpretation in the workspace at the delete location marked;

    - Goes to Rule 2. 

    If the suffix character is not d, the suffix character is i. The interpreter goes to Rule 18. 

Rule 18. The interpreter:

    - Inserts the value string into the workspace at the delete location marked;

    - Resumes interpretation in the workspace beginning at the head of the inserted string;

    - Goes to Rule 2. 

Disposition of value string ends. TOP