Язык SNOBOL: история и особенности строковой обработки

Введение

Язык программирования, ориентированный на строковые операции, SNOBOL ("StriNg Oriented and symBOlic Language") – это серия языков программирования, разработанных в период с 1962 по 1967 год в лабораториях AT&T Bell Дэвидом Дж. Фарбером, Ральфом Э. Грисуолдом и Иваном П. Полонским, кульминацией которых стал SNOBOL4. Он был одним из ряда языков, ориентированных на обработку текстовых строк, разработанных в 1950-х и 1960-х годах; другие включали COMIT и TRAC. SNOBOL4 выделяется среди большинства языков программирования того времени тем, что рассматривает шаблоны как данные первого класса (то есть тип данных, значениями которого можно манипулировать всеми способами, допустимыми для любого другого типа данных в языке программирования) и предоставляет операторы для конкатенации и чередования шаблонов. Шаблоны SNOBOL4 являются разновидностью объектов и допускают различные манипуляции, подобно более поздним объектно-ориентированным языкам, таким как JavaScript, шаблоны которых известны как регулярные выражения. Кроме того, строки SNOBOL4, генерируемые во время выполнения, могут рассматриваться как программы и либо интерпретироваться, либо компилироваться и выполняться (как в функции eval других языков). SNOBOL4 широко преподавался в крупных университетах США в конце 1960-х и начале 1970-х годов и широко использовался в 1970-х и 1980-х годах как язык манипулирования текстом в гуманитарных науках. В 1980-х и 1990-х годах его использование сократилось, поскольку новые языки, такие как AWK и Perl, сделали манипулирование строками с помощью регулярных выражений популярным. Шаблоны SNOBOL4 включают в себя грамматики BNF, которые эквивалентны грамматикам, свободным от контекста, и более мощные, чем регулярные выражения. "Регулярные выражения" в современных версиях AWK и Perl фактически являются расширениями регулярных выражений в традиционном смысле, но регулярные выражения, в отличие от шаблонов SNOBOL4, не являются рекурсивными, что дает шаблонам SNOBOL4 явное вычислительное преимущество. (Рекурсивные выражения появились в Perl 5.10, выпущенном в декабре 2007 года.) Позднее разработанные языки SL5 (1977) и Icon (1978) были созданы Грисуолдом для объединения механизма обратного отслеживания при сопоставлении шаблонов SNOBOL4 с более стандартной структурой, характерной для ALGOL.

Text string oriented programming language
the programming language

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. 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. 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. (Recursive expressions did appear in Perl 5.10, though, released in December 2007.) The later SL5 (1977) and Icon (1978) languages were designed by Griswold to combine the backtracking of SNOBOL4 pattern matching with more standard ALGOL like structuring.

СНОБОЛ1

Первоначальный язык SNOBOL был создан как инструмент для его авторов, чтобы работать с символьным преобразованием полиномов. Он был написан на языке ассемблера для IBM 7090. Он обладал простым синтаксисом, только одним типом данных – строкой, не имел функций и объявлений, а также практически не осуществлял контроль ошибок. Однако, несмотря на свою простоту и "персональный" характер, его использование стало распространяться и на другие группы. В результате авторы решили расширить его возможности и упорядочить.

СНОБОЛ2

SNOBOL2 существовал, но это была недолговечная промежуточная версия разработки, не имевшая пользовательских функций и так и не вышедшая в свет.

СНОБОЛ3

SNOBOL был переписан для добавления функций, как стандартных, так и определенных пользователем, и результат был выпущен под названием SNOBOL3. SNOBOL3 стал весьма популярным и был переписан другими программистами для компьютеров, отличных от IBM 7090. В результате появилось несколько несовместимых диалектов.

СНОБОЛ4

По мере того, как SNOBOL3 становился все более популярным, авторы получали все больше запросов на расширение языка. Они также начали получать жалобы на несовместимость и ошибки в версиях, которые они не разрабатывали. Чтобы решить эту проблему и воспользоваться преимуществами новых компьютеров, появившихся в конце 1960-х годов, было принято решение разработать SNOBOL4 с множеством дополнительных типов данных и функций, но на основе виртуальной машины для повышения переносимости между компьютерами. Переводчик языка SNOBOL4 по-прежнему был написан на языке ассемблера. Однако макровозможности ассемблера использовались для определения инструкций виртуальной машины Языка реализации SNOBOL (SIL). Это значительно улучшило переносимость языка, поскольку стало относительно легко переносить виртуальную машину, на которой работал переводчик, путем воссоздания ее виртуальных инструкций на любом компьютере, оснащенном макроассемблером или даже языком высокого уровня. Машинно-независимый язык SIL возник как обобщение макросов для манипулирования строками, разработанных Дугласом Макилроем, которые широко использовались в исходной реализации SNOBOL. В 1969 году Макилрой снова оказал влияние на язык, настояв на добавлении табличного типа в SNOBOL4.

Реализация

Классическая реализация была выполнена на PDP 10; она использовалась для изучения компиляторов, формальных грамматик и искусственного интеллекта, особенно машинного перевода и машинного понимания естественных языков. Первоначальная реализация была на IBM 7090 в лаборатории Bell Labs, Холмдель, штат Нью-Джерси. SNOBOL4 был специально разработан для переносимости; первая реализация была начата на IBM 7094 в 1966 году, но завершена на IBM 360 в 1967 году. Он был быстро портирован на множество других платформ. Обычно он реализуется как интерпретатор из-за сложности реализации некоторых его функций очень высокого уровня, но существует компилятор – SPITBOL – который предоставляет почти все возможности, предоставляемые интерпретатором. Классическая реализация на PDP 10 была довольно медленной, и в 1972 году Джеймс Гимпел из Bell Labs, Холмдель, штат Нью-Джерси, разработал собственную реализацию SNOBOL4 для PDP 10, которую он назвал SITBOL. Он использовал эту разработку в качестве основы для курса для выпускников по обработке строк, который он преподавал в том же году в Технологическом институте Стивенса (отсюда и название SITBOL). Студентам были даны разделы для реализации (на ассемблере PDP 10), и весь семестр был посвящен реализации SITBOL. К концу семестра работа была выполнена более чем на 80%, а затем профессор Гимпел и несколько студентов завершили ее летом. SITBOL был полнофункциональным, высокопроизводительным интерпретатором SNOBOL4. Компилятор Gnat Ada поставляется с пакетом (GNAT.Spitbol), который реализует всю семантику манипулирования строками Spitbol. Его можно вызывать из программы на Ada. Редактор файлов для Michigan Terminal System (MTS) обеспечивал сопоставление с образцом на основе шаблонов SNOBOL4. В настоящее время доступно несколько реализаций. Macro SNOBOL4 на C, написанный Филом Будном, является бесплатной реализацией с открытым исходным кодом, способной работать практически на любой платформе. Catspaw, Inc. предоставляла коммерческую реализацию языка SNOBOL4 для различных компьютерных платформ, включая DOS, Macintosh, Sun, RS/6000 и другие, и эти реализации теперь доступны бесплатно от Catspaw. Minnesota SNOBOL4, разработанный Виктором Берстисом, является наиболее близкой к оригинальной версии IBM реализацией для персональных компьютеров (включая поддержку операторов FORMAT, аналогичных Fortran). Она также распространяется бесплатно. Хотя сам SNOBOL не имеет средств структурированного программирования, препроцессор SNOBOL под названием Snostorm был разработан и реализован в 1970-х годах Фредом Г. Шварцем для использования в Michigan Terminal System (MTS) в Мичиганском университете. Snostorm использовался на восьми-пятнадцати узлах, работающих под MTS. Он также был доступен в Университетском колледже Лондона (UCL) в период с 1982 по 1984 год. Snocone, разработанный Эндрю Кенигом, добавляет блочные структурированные конструкции в язык SNOBOL4. Snocone – это самостоятельный язык программирования, а не надмножество SNOBOL4. Реализация SPITBOL также представила ряд функций, которые, хотя и не используют традиционные ключевые слова структурированного программирования, тем не менее могут быть использованы для обеспечения многих эквивалентных возможностей, обычно рассматриваемых как «структурированное программирование», в частности, вложенные конструкции типа if/then/else. Эти функции были добавлены в большинство современных реализаций SNOBOL4. После многих лет существования в качестве коммерческого продукта в апреле 2009 года SPITBOL был выпущен как свободное программное обеспечение под лицензией GNU General Public License.

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. 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. 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. 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. 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. 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.

Именование

По словам Дэйва Фарбера, он, Грисуолд и Полонский "наконец пришли к названию Symbolic EXpression Interpreter SEXI". Распространенные обратные акронимы "SNOBOL" – "String Oriented Symbolic Language" (строко-ориентированный символический язык) или (как квазиинициализм) "StriNg Oriented symBOlic Language".