SNOBOL

Last updated
SNOBOL
Paradigm Imperative, procedural, unstructured
Designed by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky
Developer David J. Farber, Ralph E. Griswold, Ivan P. Polonsky, and Bell Labs
First appeared1962;61 years ago (1962)
Stable release
SNOBOL4 / 1967;56 years ago (1967)
Website https://www.regressive.org/snobol4/
Major implementations
SNOBOL, SPITBOL
Influenced by
COMIT
Influenced
AWK, SL5, Icon, bs, Lua [1]

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

Contents

SNOBOL4 stands apart from most programming languages of its era 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. SNOBOL4 patterns are a type of object and admit various manipulations, much like later object-oriented languages such as JavaScript whose patterns are known as regular expressions. In addition SNOBOL4 strings generated during execution can be treated as programs and either interpreted or compiled and executed (as in the eval function of other languages).

SNOBOL4 was quite widely taught in larger U.S. 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 the 1980s and 1990s, its use faded as newer languages such as AWK and Perl 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. [2] The "regular expressions" in current versions of AWK and Perl are in fact extensions of regular expressions in the traditional sense, but regular expressions, unlike SNOBOL4 patterns, are not recursive, which gives a distinct computational advantage to SNOBOL4 patterns. [3] (Recursive expressions did appear in Perl 5.10, though, released in December 2007. [4] [5] )

The later SL5 (1977) [6] and Icon (1978) languages were designed by Griswold to combine the backtracking of SNOBOL4 pattern matching with more standard ALGOL-like structuring.

Development

SNOBOL1

The initial SNOBOL language was created as a tool to be used by its authors to work with the symbolic manipulation of polynomials. It was written in assembly language for the IBM 7090. It had a simple syntax, only one datatype, the string, no functions, and no declarations and very little error control. However, despite its simplicity and its "personal" nature its use began to spread to other groups. As a result, the authors decided to extend it and tidy it up.

SNOBOL2

SNOBOL2 did exist but it was a short-lived intermediate development version without user-defined functions and was never released.

SNOBOL3

SNOBOL was rewritten to add functions, both standard and user-defined, and the result was released as SNOBOL3. SNOBOL3 became quite popular and was rewritten for other computers than the IBM 7090 by other programmers. As a result, several incompatible dialects arose.

SNOBOL4

As SNOBOL3 became more popular, the authors received more and more requests for extensions to the language. They also began to receive complaints about incompatibility and bugs in versions that they hadn't written. To address this and to take advantage of the new computers being introduced in the late 1960s, the decision was taken to develop SNOBOL4 with many extra datatypes and features but based on a virtual machine to allow improved portability across computers. [7] The SNOBOL4 language translator was still written in assembly language. However the macro features of the assembler were used to define the virtual machine instructions of the SNOBOL Implementation Language, the SIL. This very much improved the portability of the language by making it relatively easy to port the virtual machine which hosted the translator by recreating its virtual instructions on any machine which included a macro assembler or indeed a high level language. [8]

The machine-independent language SIL arose as a generalization of string manipulation macros by Douglas McIlroy, which were used extensively in the initial SNOBOL implementation. In 1969, McIlroy influenced the language again by insisting on addition of the table type to SNOBOL4. [9] [10]

SNOBOL4 features

SNOBOL is distinctive in format and programming style, which are radically different from contemporary procedural languages such as Fortran and ALGOL.

SNOBOL4 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 records of the earlier COBOL and the later Pascal programming languages.

All SNOBOL command lines are of the form

label subject pattern=object:transfer

Each of the five elements is optional. In general, the subject is matched against the pattern. If the object is present, any matched portion is replaced by the object via rules for replacement. The transfer can be an absolute branch or a conditional branch dependent upon the success or failure of the subject evaluation, the pattern evaluation, the pattern match, the object evaluation or the final assignment. It can also be a transfer to code created and compiled by the program itself during a run.

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.

SNOBOL4 pattern-matching uses a backtracking algorithm similar to that used in the logic programming language Prolog, which provides pattern-like constructs via DCGs. This algorithm makes it easier to use SNOBOL as a logic programming language than is the case for most languages.

SNOBOL stores variables, strings and data structures in a single garbage-collected heap.

Example programs

The "Hello, World!" program might be as follows...

OUTPUT="Hello, World!"END

A simple program to ask for a user's name and then use it in an output sentence...

OUTPUT="What is your name?"Username=INPUTOUTPUT="Thank you, "UsernameEND

To choose between three possible outputs...

OUTPUT="What is your name?"Username=INPUTUsername"J":S(LOVE)Username"K":S(HATE)MEHOUTPUT="Hi, "Username:(END)LOVEOUTPUT="How nice to meet you, "Username:(END)HATEOUTPUT="Oh. It's you, "UsernameEND

To continue requesting input until no more is forthcoming...

OUTPUT="This program will ask you for personal names"OUTPUT="until you press return without giving it one"NameCount=0:(GETINPUT)AGAINNameCount=NameCount+1OUTPUT="Name "NameCount": "PersonalNameGETINPUTOUTPUT="Please give me name "NameCount+1PersonalName=INPUTPersonalNameLEN(1):S(AGAIN)OUTPUT="Finished. "NameCount" names requested."END

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 started on an IBM 7094 in 1966 but completed on an IBM 360 in 1967. 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 classic implementation on the PDP-10 was quite slow, and in 1972 James Gimpel of Bell Labs, Holmdel, N.J. designed a native implementation of SNOBOL4 for the PDP-10 that he named SITBOL. He used the design as the basis of a graduate class in string processing that he taught that year at Stevens Institute of Technology (which is why it was named SITBOL). Students were given sections to implement (in PDP-10 assembler) and the entire semester was focused on implementing SITBOL. It was over 80% complete by the end of the semester and was subsequently completed by Professor Gimpel and several students over the summer. SITBOL was a full-featured, high-performance SNOBOL4 interpreter.

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

The file editor for the Michigan Terminal System (MTS) provided pattern matching based on SNOBOL4 patterns. [11]

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. [12] Catspaw, Inc provided a commercial implementation of the SNOBOL4 language for many different computer platforms, including DOS, Macintosh, Sun, RS/6000, and others, and these implementations are 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. [13]

Although SNOBOL itself has no structured programming features, a SNOBOL preprocessor called Snostorm was designed and implemented during the 1970s by Fred G. Swartz for use under the Michigan Terminal System (MTS) at the University of Michigan. [14] Snostorm was used at the eight to fifteen sites that ran MTS. It was also available at University College London (UCL) between 1982 and 1984.

Snocone by Andrew Koenig adds block-structured constructs to the SNOBOL4 language. Snocone is a self-contained programming language, rather than a proper superset of SNOBOL4. [15]

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, [16] 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, punched 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's 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.

Common backronyms of "SNOBOL" are 'String Oriented Symbolic Language' [17] or (as a quasi-initialism) 'StriNg Oriented symBOlic Language'. [18]

See also

Related Research Articles

C is a general-purpose computer programming language. It was created in the 1970s by Dennis Ritchie, and remains very widely used and influential. By design, C's features cleanly reflect the capabilities of the targeted CPUs. It has found lasting use in operating systems, device drivers, and protocol stacks, but its use in application software has been decreasing. C is commonly used on computer architectures that range from the largest supercomputers to the smallest microcontrollers and embedded systems.

Icon is a very high-level programming language based on the concept of "goal-directed execution" in which code returns a "success" along with valid values, or a "failure", indicating that there is no valid data to return. The success and failure of a given block of code is used to direct further processing, whereas conventional languages would typically use boolean logic written by the programmer to achieve the same ends. Because the logic for basic control structures is often implicit in Icon, common tasks can be completed with less explicit code.

<span class="mw-page-title-main">Lisp (programming language)</span> Programming language family

Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1960, Lisp is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket, and Clojure.

<span class="mw-page-title-main">Macro (computer science)</span> Rule for substituting a set input with a set output

In computer programming, a macro is a rule or pattern that specifies how a certain input should be mapped to a replacement output. Applying a macro to an input is known as macro expansion. The input and output may be a sequence of lexical tokens or characters, or a syntax tree. Character macros are supported in software applications to make it easy to invoke common command sequences. Token and tree macros are supported in some programming languages to enable code reuse or to extend the language, sometimes for domain-specific languages.

<span class="mw-page-title-main">Programming language</span> Language for communicating instructions to a machine

A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.

<span class="mw-page-title-main">Regular expression</span> Sequence of characters that forms a search pattern

A regular expression, sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory.

<span class="mw-page-title-main">String (computer science)</span> Sequence of characters, data type

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed. A string is generally considered as a data type and is often implemented as an array data structure of bytes that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence data types and structures.

In computing, a virtual machine (VM) is the virtualization or emulation of a computer system. Virtual machines are based on computer architectures and provide the functionality of a physical computer. Their implementations may involve specialized hardware, software, or a combination of the two. Virtual machines differ and are organized by their function, shown here:

XSLT is a language originally designed for transforming XML documents into other XML documents, or other formats such as HTML for web pages, plain text or XSL Formatting Objects, which may subsequently be converted to other formats, such as PDF, PostScript and PNG. Support for JSON and plain-text transformation was added in later updates to the XSLT 1.0 specification.

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a programming language and machine.

<span class="mw-page-title-main">Douglas McIlroy</span> American mathematician and computer scientist

Malcolm Douglas McIlroy is a mathematician, engineer, and programmer. As of 2019 he is an Adjunct Professor of Computer Science at Dartmouth College. McIlroy is best known for having originally proposed Unix pipelines and developed several Unix tools, such as spell, diff, sort, join, graph, speak, and tr. He was also one of the pioneering researchers of macro processors and programming language extensibility. He participated in the design of multiple influential programming languages, particularly PL/I, SNOBOL, ALTRAN, TMG and C++.

In computing, a polyglot is a computer program or script written in a valid form of multiple programming languages or file formats. The name was coined by analogy to multilingualism. A polyglot file is composed by combining syntax from two or more different formats. When the file formats are to be compiled or interpreted as source code, the file can be said to be a polyglot program, though file formats and source code syntax are both fundamentally streams of bytes, and exploiting this commonality is key to the development of polyglots. Polyglot files have practical applications in compatibility, but can also present a security risk when used to bypass validation or to exploit a vulnerability.

In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be a match." The patterns generally have the form of either sequences or tree structures. Uses of pattern matching include outputting the locations of a pattern within a token sequence, to output some component of the matched pattern, and to substitute the matching pattern with some other token sequence.

SPITBOL is a compiled implementation of the SNOBOL4 programming language. Originally targeted for the IBM System/360 and System/370 family of computers, it has now been ported to most major microprocessors including the SPARC. It was created by Robert Dewar and Ken Belcher, who were then at the Illinois Institute of Technology.

Metaprogramming is a programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyze or transform other programs, and even modify itself while running. In some cases, this allows programmers to minimize the number of lines of code to express a solution, in turn reducing development time. It also allows programs a greater flexibility to efficiently handle new situations without recompilation.

<span class="mw-page-title-main">Conditional (computer programming)</span> Control flow statement that executes code according to some condition(s)

In computer science, conditionals are programming language commands for handling decisions. Specifically, conditionals perform different computations or actions depending on whether a programmer-defined Boolean condition evaluates to true or false. In terms of control flow, the decision is always achieved by selectively altering the control flow based on some condition . Although dynamic dispatch is not usually classified as a conditional construct, it is another way to select between alternatives at runtime. Conditional statements are the checkpoints in the programe that determines behaviour according to situation.

<span class="mw-page-title-main">Syntax (programming languages)</span> Set of rules defining correctly structured programs

In computer science, the syntax of a computer language is the rules that define the combinations of symbols that are considered to be correctly structured statements or expressions in that language. This applies both to programming languages, where the document represents source code, and to markup languages, where the document represents data.

Snostorm (Snostorm3) is a version of the SNOBOL4 language with structured programming constructs added. It compensates for the near absence of structured programming constructs in SNOBOL4 by providing IF, ELSEIF, ELSE, LOOP, CASE, and PROCEDURE statements, among others. It was originally designed and implemented by Fred G. Swartz as a preprocessor for SPITBOL running under the Michigan Terminal System (MTS) at the University of Michigan Computing Center during the 1970s.

Nemerle is a general-purpose, high-level, statically typed programming language designed for platforms using the Common Language Infrastructure (.NET/Mono). It offers functional, object-oriented, aspect-oriented, reflective and imperative features. It has a simple C#-like syntax and a powerful metaprogramming system.

References

  1. ↑ Ierusalimschy, Roberto; de Figueiredo, Luiz Henrique; Celes, Waldemar (2007), "The evolution of Lua", Proceedings of the third ACM SIGPLAN conference on History of programming languages (PDF), p. 26, doi:10.1145/1238844.1238846, ISBN   9781595937667, S2CID   475143
  2. ↑ Gimpel, J. F. (February 1973). "A theory of discrete patterns and their implementation in SNOBOL4". Communications of the ACM. 16 (2): 91-100. doi: 10.1145/361952.361960 . S2CID   17059429.
  3. ↑ "Dr. Dobb's: Programs That Transform Their Own Source Code; or: the Snobol Foot Joke". Dobbscodetalk.com. Retrieved 2011-12-04.
  4. ↑ Contact details. "perlre". perldoc.perl.org. Retrieved 2011-12-04.
  5. ↑ "Recursive Regex Tutorial" . Retrieved 2017-03-19.
  6. ↑ Griswold, Ralph E.; Hanson, David R. (April 1977). "An Overview of SL5". ACM SIGPLAN Notices. 12 (4): 40–50. doi: 10.1145/954654.954658 . S2CID   38692673.
  7. ↑ See Chapter 1 of The Macro Implementation of SNOBOL4
  8. ↑ SNOBOL4 has been implemented using C to recreate the virtual machine instructions.
  9. ↑ Griswold, Ralph (1978). "A history of the SNOBOL programming languages" (PDF). ACM SIGPLAN Notices. 13 (8): 275–308. doi:10.1145/960118.808393. S2CID   5413577. Archived from the original (PDF) on 2019-03-02.
  10. ↑ Wexelblat, Richard L., ed. (2014) [1981]. History of Programming Languages. Academic Press. p. 784. ISBN   9781483266169.
  11. ↑ Introduction to the MTS file editor, University of Michigan Computing Center, 1986.
  12. ↑ "SNOBOL4.ORG -- SNOBOL4 Resources".
  13. ↑ "The MINNESOTA SNOBOL4 Programming Language".
  14. ↑ "SNOSTORM", MTS Volume 9: SNOBOL4 in MTS, Computing Center, University of Michigan, June 1979, pages 99-120. Retrieved 1 September 2014.
  15. ↑ "The Snocone Programming Language", Andrew Koenig, USENIX (Portland, Oregon), June 1985. Retrieved 2 September 2014.
  16. ↑ WORTH READING Wikipedia entry on SNOBOL — the TRUE story NOT Wikipedias (Dave Farber, Interesting People mailing list, 26 December 2008)
  17. ↑ Computers and the humanities1:158, 1967.
  18. ↑ Belzer, Jack; Holzman, Albert G.; Kent, Allen, eds. (1979). "SNOBOL". Encyclopedia of Computer Science and Technology. Vol. 13. CRC Press. p. 173. ISBN   0-8247-2263-9.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.