View source for Snobol

An [[Algorithmic language|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|Refal]], Snobol has its own theoretical premise, Markov normal algorithms (cf. [[Normal algorithm|Normal algorithm]]), in which the basic computing operation is the detection in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859501.png" /> of a given substring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859502.png" /> and its subsequent replacement by another string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859503.png" />.

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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859504.png" /> or two models <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859505.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859506.png" /> creates a model, successful comparison with which requires success in the comparison with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859507.png" /> followed by success in comparison of the remainder of the subject with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859508.png" />. The alternation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s0859509.png" /> of two models <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595011.png" /> creates a model with which successful comparison means success in comparison with either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595012.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595013.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595014.png" /> is a model and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595015.png" /> a variable, then the construction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595016.png" /> denotes a model with which successful comparison preserves as the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595017.png" /> that control line whose occurrence in the subject led to the success.

The instruction of comparison with a model has the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595018.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595019.png" /> is a variable-subject and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595020.png" /> a model. Conditional control transfer is represented by the instruction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595021.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595022.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595024.png" /> are the transfer labels in the case of failure and success of comparison, respectively. A substitution instruction has the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595025.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595026.png" /> is a line expression whose value in a successful comparison replaces the selected subline in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s085/s085950/s08595027.png" />.

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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  D.J. Farber,   R.E. Griswold,   I.P. Polonsky,   "SNOBOL, a string manipulation language"  ''J. Assoc. Comput. Mach.'' , '''11''' :  1  (1964)  pp. 21–30</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  R.E. Griswold,   "String and list processing in SNOBOL 4. Techniques and applications" , Prentice-Hall  (1975)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Griswold,   J. Poage,   I. Polonsky,   "The SNOBOL-4 programming language" , Prentice-Hall  (1968)</TD></TR></table>