SNOBOL

SNOBOL (String Oriented Symbolic Language) is a computer programming language developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky. It was one of a number of text-string-oriented languages developed during the 1950s and 1960s, others included COMIT and TRAC.

SNOBOL4 stands apart from most programming languages by having patterns as a first-class data type (i.e. a data type whose values can be manipulated in all ways permitted to any other data type in the programming language) and by providing operators for pattern concatenation and alternation. Strings generated during execution can be treated as programs and executed.

SNOBOL was quite widely taught in larger US universities in the late 1960s and early 1970s and was widely used in the 1970s and 1980s as a text manipulation language in the humanities.

In recent years its use has faded as newer languages such as Awk and Perl have made string manipulation by means of regular expressions fashionable. SNOBOL4 patterns subsume BNF grammars, which are equivalent to Context-free grammars and more powerful than regular expressions. ^[1] However, the "regular expressions" in current versions of Awk and Perl are in fact extensions of regular expressions in the traditional sense.

One of the designers of SNOBOL, Ralph Griswold, designed a successor to SNOBOL, called Icon, which combined the backtracking of SNOBOL pattern matching with more standard Algol-like structuring, as well as adding some features of its own.

Features

SNOBOL4 is the fourth and latest incarnation of a series of special purpose programming languages for character string manipulation.

The SNOBOL4 variant of the language supports a number of built-in data types, such as integers and limited precision real numbers, strings, patterns, arrays, and tables (associative arrays), and also allows the programmer to define additional data types and new functions. SNOBOL4's programmer-defined data type facility was advanced at the time—it is similar to the earlier Cobol's and the later Pascal's records.

All SNOBOL command lines are of the form Label1 Subject Pattern = Object :(Goto Label2) Each of the five sections were optional. In general, the subject was matched against the pattern. If the object was present, any matched portion was replaced by the object via rules for replacement. The goto could be an absolute branch, or conditionally based on success or failure of the pattern match.

A SNOBOL pattern can be very simple or extremely complex. A simple pattern is just a text string (e.g. "ABCD"), but a complex pattern may be a large structure describing, for example, the complete grammar of a computer language. It is possible to implement a language interpreter in SNOBOL almost directly from a Backus-Naur form expression of it, with few changes. Creating a macro assembler and an interpreter for a completely theoretical piece of hardware could take as little as a few hundred lines, with a new instruction being added with a single line.

Complex SNOBOL patterns can do things that would be impractical or impossible using the more primitive regular expressions used in most other pattern matching languages. Some of this power derives from the so-called "SPITBOL extensions" (which have since been incorporated in basically all modern implementations of the original SNOBOL 4 language too), although it is possible to achieve the same power without them. Part of this power comes from the side effects that it is possible to produce during the pattern matching operation, including saving numerous intermediate/tentative matching results and the ability to invoke user-written functions during the pattern match which can perform nearly any desired processing, and then influence the ongoing direction the interrupted pattern match takes, or even to indeed change the pattern itself during the matching operation. Patterns can be saved like any other first-class data item, and can be concatenated, used within other patterns, and used to create very complex and sophisticated pattern expressions. It is possible to write, for example, a SNOBOL4 pattern which matches "a complete name and international postal mailing address", which is well beyond anything that is practical to even attempt using regular expressions.

SNOBOL pattern-matching uses a backtracking algorithm similar to that used in the logic programming language Prolog, which provides pattern-like constructs via DCGs.

SNOBOL stores strings in a garbage-collected heap.

SNOBOL rivals APL for its distinctiveness in format and programming style, both being radically unlike more "standard" procedural languages such as BASIC, Fortran, or C.

Implementations

The classic implementation was on the PDP-10; it has been used to study compilers, formal grammars, and artificial intelligence, especially machine translation and machine comprehension of natural languages. The original implementation was on an IBM 7090 at Bell Labs, Holmdel, N.J. SNOBOL4 was specifically designed for portability; the first implementation was on an IBM 7094 but it was rapidly ported to many other platforms.

It is normally implemented as an interpreter because of the difficulty in implementing some of its very high-level features, but there is a compiler, the SPITBOL compiler, which provides nearly all the facilities that the interpreter provides.

The Gnat Ada Compiler comes with a package (GNAT.Spitbol) which implements all of the Spitbol string manipulation semantics. This can be called from within an Ada program.

Several implementations are currently available. Macro SNOBOL4 in C written by Phil Budne is a free, open source implementation, capable of running on almost any platform. It is available at http://www.snobol4.org/. Catspaw, Inc. at http://www.snobol4.com/, provides a commercial implementation of the SNOBOL4 language for many different computer platforms, including DOS, Macintosh, Sun, RS/6000, and others. An older version, SNOBOL4+, is now available free from Catspaw. Minnesota SNOBOL4, By Viktors Berstis, the closest PC implementation to the original IBM mainframe version (even including Fortran-like FORMAT statement support) is also free, and is at http://www.berstis.com/snobol4.htm.

Although SNOBOL itself has almost a complete absence of traditional and familiar-looking structured programming features, a structured version of SNOBOL called Snostorm existed at University College London (UCL) between 1982 and 1984, and another by Andrew Koenig called Snocone. [1]

The SPITBOL implementation also introduced a number of features which, while not using traditional structured programming keywords, nevertheless can be used to provide many of the equivalent capabilities normally thought of as "structured programming", most notably nested if/then/else type constructs. These features have since been added to most recent SNOBOL4 implementations. After many years as a commercial product, in April 2009 SPITBOL was released as free software under the GNU General Public License.

Naming

According to Dave Farber,^[2] he, Griswold and Polonsky "finally arrived at the name Symbolic EXpression Interpreter SEXI."

All went well until one day I was submitting a batch job to assemble the system and as normal on my JOB card -- the first card in the deck, I , in BTL standards my job and my name -- Sexi Farber

One of the Comp Center girls looked at it and said, "That's what you think" in a humorous way.

That made it clear that we needed another name!! We sat and talked and drank coffee and shot rubber bands and after much too much time someone said -- most likely Ralph -- "We don't have a Snowball chance in hell of finding a name". All of us yelled at once, "WE GOT IT -- SNOBOL" in the spirit of all the BOL languages. We then stretched our mind to find what it stood for.

See also

• SPITBOL
• Icon programming language
• Unicon programming language

References

Further reading

• Emmer, Mark B. SNOBOL4+: The SNOBOL4 Language for the Personal Computer User. Englewood Cliffs, NJ: Prentice Hall, 1985 (ISBN 0-13-815119-9).
• Gimpel, James F. Algorithms in SNOBOL4. New York: Wiley, 1976 (ISBN 0-471-30213-9); republished Salida, CO: Catspaw, 1986 (ISBN 0-939793-00-8).
• Griswold, Ralph E., J. F. Poage, and I. P. Polonsky. The SNOBOL4 Programming Language. Englewood Cliffs, NJ: Prentice Hall, 1968 (ISBN 0-13-815373-6).
• Griswold, Ralph E. String and List Processing in SNOBOL4: Techniques and Applications. Englewood Cliffs, NJ: Prentice Hall, 1975 (ISBN 0-13-853010-6).
• Hockey, Susan M. Snobol Programming for the Humanities. New York: Clarendon Press; Oxford: Oxford University Press, 1985 (ISBN 0-19-824676-5).

External links

• Catspaw, Inc. offers implementations of and support for SNOBOL4
• SNOBOL at the Open Directory Project
• Introduction to Snobol by James Ford
• A sample program in SNOBOL
• Charles Hall Collection on the SNOBOL Programming Language. Charles Babbage Institute, University of Minnesota, Minneapolis.