Snobol

An algorithmic language designed for programming problems of processing symbolic information, that is, data represented by words over some alphabet. In the literature on programming, such words are called strings, and the symbols comprising them are called letters or tokens. Based on the original form of Snobol, which was developed in the early 1960-s, several versions of the language were created, of which the most stable proved to be Snobol-4. As in the case of Refal, Snobol has its own theoretical premise, Markov normal algorithms (cf. Normal algorithm), in which the basic computing operation is the detection in $ A $ of a given substring $ B $ and its subsequent replacement by another string $ C $.

The general structure of programs in Snobol is typical of that of algorithmic languages. A program has the form of a sequence of operators (instructions) of conferment, comparison with a model, substitution, control transmission, input, deduction, and halting. The primitive operations used in such expressions are predicates and functions and also functions defined by the programmer (including recursive definitions). Any instruction can be labelled. A label in Snobol can be treated as a line variable whose value is an instruction labelled by this label. Fundamental data types are lines, integers and real numbers, names, and models. The basic type is the line, and all other data have a line representation coinciding with the method for denoting them in the program. Homogeneous data can be combined in groups and tables, and arbitrary data in sets of a given length and with prescribed names for every position (field) of the set. Names denote variables, labels, formal parameters, and functions. Lines in Snobol can have arbitrary length. Variables do not have a type constantly attributed to them, although operands (cf. Operand) of every operation or primitive functions expect data of a specific type, transforming arguments to the expected type or issuing information about an error.

The most typical operation in Snobol is the comparison of a line with a model. A model is a special term in Snobol, creating in some sequence a group of control lines and a specific action of movement from left to right (scanning) along a prescribed line, called the subject. Comparison is a sequence of elementary checks. An elementary check establishes whether the next control line is a subline of the remainder (to the right of the scanning point) of the subject. Depending on the success or failure of an elementary check, there occurs either an elaboration of the information about the success or failure of the comparison on the whole, or a transfer to the next control line of the model and a transfer of the scanning point. As a result of a successful comparison, a sequence of sublines is chosen in the subject. These sublines can be conferred by the above variable or replaced by other sublines.

A primitive model is an expression whose value is a line, and the success of a comparison consists of the occurrence of this line in the subject. The concatenation $ A B $ or two models $ A $ and $ B $ creates a model, successful comparison with which requires success in the comparison with $ A $ followed by success in comparison of the remainder of the subject with $ B $. The alternation $ A \mid B $ of two models $ A $ and $ B $ creates a model with which successful comparison means success in comparison with either $ A $ or $ B $. If $ A $ is a model and $ X $ a variable, then the construction $ A , X $ denotes a model with which successful comparison preserves as the value of $ X $ that control line whose occurrence in the subject led to the success.

The instruction of comparison with a model has the form $ V A $, where $ V $ is a variable-subject and $ A $ a model. Conditional control transfer is represented by the instruction $ V A $: $ F ( M 1 ) S ( M 2 ) $, where $ M 1 $ and $ M 2 $ are the transfer labels in the case of failure and success of comparison, respectively. A substitution instruction has the form $ V A = E $, where $ E $ is a line expression whose value in a successful comparison replaces the selected subline in $ V $.

Snobol has a well-developed library of primitive functions which, in combination with the operations of concatenation and alternation, enables one to create voluminous models and to write compactly in the form of a replacement instruction very complex rules for the analysis and transformation of lines. Programs in Snobol are developed by a programming processor of interpretation type. A program is translated into an intermediate form which is executed with the aid of an interpreter. Snobol has been implemented on all main architectures of contemporary computers. The implementation of this language aided the development of efficient algorithms for manipulating lines of variable length in a computer memory.

References

[1]	D.J. Farber, R.E. Griswold, I.P. Polonsky, "SNOBOL, a string manipulation language" J. Assoc. Comput. Mach. , 11 : 1 (1964) pp. 21–30
[2]	R.E. Griswold, "String and list processing in SNOBOL 4. Techniques and applications" , Prentice-Hall (1975)
[3]	R. Griswold, J. Poage, I. Polonsky, "The SNOBOL-4 programming language" , Prentice-Hall (1968)