1.3. Языки, ориентированные на данные

На заре программирования было создано и реализовано несколько языков, значительно повлиявших на дальнейшие разработки. У них была одна общая черта: каждый язык имел предпочтительную структуру данных и обширный набор команд для нее. Эти языки позволяли создавать сложные программы, которые трудно было бы написать на языках типа Fortran, просто манипули­рующих компьютерными словами. В следующих подразделах мы рассмотрим некоторые из этих языков.

Lisp

Основная структура данных в языке Lisp — связанный список. Первоначаль-но Lisp был разработан для исследований в теории вычислений, и многие ра­боты по искусственному интеллекту были выполнены на языке Lisp. Язык был настолько важен, что компьютеры разрабатывались и создавались так, чтобы оптимизировать выполнение Lisp-программ. Одна из проблем языка состояла в обилии различных «диалектов», возникавших по мере того, как язык реализовывался на различных машинах. Позже был разработан стандар­тный язык Lisp, чтобы программы можно было переносить с одного компью­тера на другой. В настоящее время популярен «диалект» языка Lisp — CLOS, поддерживающий объектно-ориентированное программирование.

Три основные команды языка Lisp — это car(L) и cdr(L), которые извлека­ют, соответственно, начало и конец списка L, и cons(E, L), которая создает но­вый список из элемента Е и существующего списка L. Используя эти коман­ды, можно определить функции обработки списков, содержащих нечисловые данные; такие функции было бы довольно трудно запрограммировать на языке Fortran.

Мы не будем больше обсуждать язык Lisp, потому что многие его основополагающие идеи были перенесены в современные функциональные языки программирования типа ML, который мы обсудим в гл. 16.

APL

Язык APL является развитием математического формализма, который ис­пользуется для описания вычислений. Основные структуры данных в нем — векторы и матрицы, и операции выполняются над такими структурами непо­средственно, без циклов. Программы на языке APL очень короткие по срав­нению с аналогичными программами на традиционных языках. Применение APL осложняло то, что в язык перешел большой набор математических сим­волов из первоначального формализма. Это требовало специальных термина­лов и затрудняло экспериментирование с APL без дорогостоящих аппаратных средств. Современные графические интерфейсы пользователя, применяю­щие программные шрифты, решили эту проблему, которая замедляла приня­тие APL.

Предположим, что задана векторная переменная:

V= 1 5 10 15 20 25

Операторы языка APL могут работать непосредственно с V без записи цик­лов с индексами:

+ /V =76 Свертка сложением(суммирует элементы)

фV = 25 20 15 10 5 1 Обращает вектор

^{2 3 pV = 1} 5 10 Переопределяет размерность

V 15 20 25 как матрицу 2x3

Векторные и матричные сложения и умножения также можно выполнить непосредственно над такими переменными.

Snobol, Icon

Первые языки имели дело практически только с числами. Для работы в таких областях, как обработка естественных языков, идеально подходит Snobol (и его преемник Icon), поскольку их базовой структурой данных является стро­ка. Основная операция в языке Snobol сравнивает образец со строкой, и по­бочным результатом совпадения может быть разложение строки на подстро­ки. В языке Icon основная операция — вычисление выражения, причем выра­жения включают сложные операции со строками.

В языке Icon есть важная встроенная функция find(s1, s2), которая ищет вхождения строки s1 в строку s2. В отличие от подобных функций языка С find генерирует список всех позиций в s2, в которых встречается s1:

line := 0 # Инициализировать счетчик строк while s := read() { # Читать до конца файла

every col := find("the", s) do # Генерировать позиции столбца write (line, " ",col) # Write(line,col) для "the"

line := line+ 1

}

Эта программа записывает номера строк и столбцов всех вхождений стро­ки "the" в файл. Если команда find не находит ни одного вхождения, то она «терпит неудачу» (fail), и вычисление выражения завершается. Ключевое сло­во every вызывает повторение вычисления функции до тех пор, пока оно за­вершается успешно.

Выражения Icon содержат не только строки, которые представляют собой последовательности символов; они также определены над наборами символов csets. Таким образом

vowels := 'aeiou'

присваивает переменной vowel (гласные) значение, представляющее собой набор указанных символов. Это можно использовать в функциях типа upto(vowels,s), генерирующих последовательность позиций гласных в s, и many(vowels,s), возвращающих самую длинную начальную последователь­ность гласных в s.

Более сложная функция bal подобна upto за исключением того, что она ге­нерирует последовательности позиций, которые сбалансированы по «ско­бочным» символам:

bal(' +-*/','([', ')]',*)

Это выражение могло использоваться в компиляторе, чтобы генериро­вать сбалансированные арифметические подстроки. Если в качестве строки s задать

"х + (у [u/v] - 1 )*z", вышеупомянутое выражение сгенерирует индек­сы, соответствующие подстрокам:

x

x+(y[u/v]-1

Первая подстрока сбалансирована, так как она заканчивается «+» и не содержит никаких скобок; вторая подстрока сбалансирована, поскольку она завершается символом «*» и имеет квадратные скобки, правильно вложенные внутри круглых скобок.

Так как вычисление выражения может быть неуспешным (fail), исполь­зуется откат (backtracking), чтобы продолжить поиск от предыдущих генерирующих функций. Следующая программа печатает вхождения глас­ных, за исключением тех, которые начинаются в столбце 1 .

line := 0 # Инициализировать счетчик строк while s := read() { # Читать до конца файла every col := (upto (vowels, line) > 1 ) do

# Генерировать позиции столбца write (line, " ",col) # write(line,col) для гласных

line := line + 1

}

Функция поиска генерирует индекс, который затем проверяется на «>». Если проверка неуспешна (не говорите: «если результат ложный»), программа возвращает управление генерирующей функции upto, чтобы получить новый индекс.

Icon — удобный язык для программ, выполняющих сложную обработку строк. В нем происходит абстрагирование от большей части явных индексных вычислений, и программы оказываются очень короткими по сравнению с обычными языками для числового или системного программирования. Кро­ме того, в Icon очень интересен встроенный механизм генерации и отката, ко­торый предлагает более развитый уровень абстракции управления.

SETL

Основная структура данных в SETL — множество. Так как множество — наи­более общая математическая структура, с помощью которой определяются все другие математические структуры, то SETL может использоваться для со­здания программ высокой степени общности и абстрактности и поэтому очень коротких. Такие программы имеют сходство с логическими программа­ми (гл. 17), в которых математические описания могут быть непосредственно исполняемыми. В теории множеств используется нотация: {х \р(х)}, обозна­чающая множество всех х таких, что логическое выражение р(х) является ис­тиной. Например, множество простых чисел в этой нотации может быть запи­сано как

{ п \ -,3 т [(2<т<п— 1) л (nmodm = 0)]}

Эта формула читается так: множество натуральных чисел п таких, что не cуществует натурального т от 2 до п — 1 , на которое п делится без остатка.

Чтобы напечатать все простые числа в диапазоне от 2 до 100, достаточно «протранслировать» это определение в однострочную программу на языке SETL:

print ({n in {2.. 100} | not exists m in {2.. n — 1} | (n mod m) = 0});

Все эти языки объединяет то, что к их разработке подходили больше с математических, чем с инженерных позиций. То есть решалась задача, как смоделировать известную математическую теорию, а не как выдавать коман­ды для процессора и памяти. Такие продвинутые языки очень полезны для трудно программируемых задач, где важно сосредоточить внимание на про­блеме, а не на деталях реализации.

Языки, ориентированные на данные, сейчас несколько менее популярны, чем раньше, отчасти потому, что объектно-ориентированные методы позво­ляют внедрить операции, ориентированные на данные, в обычные языки ти­па C++ и Ada, а также из-за конкуренции более новых языковых концепций, таких как функциональное и логическое программирование. Тем не менее эти языки интересны с технической точки зрения и вполне подходят для ре­шения задач, для которых они были разработаны. Студентам рекомендуется приложить усилие и изучить один или несколько таких языков, потому что это расширит их представление о том, как может быть структурирован язык программирования.