SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Парадигмы программирования


[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]


© 2003 И.А. Дехтяренко

1. Программирование в повествовательном наклонении.

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

Эдсгер Дейкстра

В грамматике различает три наклонения предложений: изъявительное (повествовательное), вопросительное и императивное (повелительное). И если в обычной речи преобладают повествовательные предложения, то в программировании повелительные. В традиционном представлении программа - последовательность команд, выполняемых компьютером. Но существует и другой стиль программирования, программирование в повествовательном наклонении, при котором программа - просто совокупность утверждений. Этот стиль (или, как сейчас модно говорить, парадигма) получил название декларативное программирование. В противоположность первый стиль называют императивным программированием. Соответственно и языки программирования делят на императивные и декларативные. Наиболее важными разновидностями декларативного программирования, являются функциональное и логическое (или реляционное) программирование.

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

В своей статье "Алгоритм = Логика + Управление" [1] Роберт Ковальский подчеркивал тот факт, что во всякой программе можно выделить две составляющих: логику, описывающую собственно решение проблемы и управление процессом вычислений. В этой терминологии декларативное программирование - описание логики алгоритма, но не (обязательно) управления.

Пожалуй, лучше всего описывает ключевую идею декларативного программирования следующее определение (принадлежащее Джону Робинсону [2]): программа является теорией, а вычисления представляют собой вывод в этой теории.

Ещё одно, негативное определение: декларативные программы не используют понятия состояния и не содержат переменных. Следовательно, они не могут использовать операторы присваивания, так как нечему присваивать. Кроме того, понятие последовательности выполнения команд становится бессмысленным и, значит, бесполезными становятся операторы управления процессом вычислений. Исходя из этого определения, можно прийти к выводу, что декларативные языки - всего лишь ущербные версии императивных, из которых удалены некоторые удобные и привычные средства. Но интересно обратить внимание, что многие важные усовершенствования в технике программирования связаны скорее с ограничением, а не расширением возможностей доступных программисту. Ранние языки высокого уровня, начиная с Фортрана, разделили глобальную память на области кода и данных, и установили ограничение, что только данные могут изменяться. Концепции модульности, структурного программирования, строгой типизации также ограничивают свободу программиста. Последние веяния - более строгие интерфейсы и запреты на непосредственные изменения объектов. Декларативное программирование может рассматриваться как еще один, более радикальный, шаг в этом направлении. Джон Хьюз сравнивал функциональных программистов со средневековыми монахами, отвергающими удовольствия жизни. Понятно что, принимая схиму и отказываясь от средств, которые менее набожные программисты считают стандартными, мы надеемся получить некоторые

преимущества.

Императивные языки развивались путем абстракции от модели вычислений типичного компьютера, известной как модель фон Неймана. Поэтому они позволяют эффективно использовать ресурсы компьютера. Но человек не компьютер. И рассуждать в терминах и понятиях вычислительной машины для него трудно и неестественно. Решая достаточно сложную задачу, мы обычно сначала создаем модель в некоторой формальной системе, а затем переписываем найденное решение в виде программы, то есть, переводим с одного формального языка на другой. Этот второй этап не имеет отношения собственно к процессу решения, и в то же время требует большого количества усилий и специальных навыков. Возникло даже разделение труда среди программистов: одни (аналитики) думают, как решить задачу, а другие (кодировщики) записывают найденное первыми решение на языке программирования. В основе декларативных языков лежит не какая-то машинная модель, а логика и математика. И появляется возможность формализовывать наши знания о проблеме непосредственно в терминах языка программирования. Это утверждение может показаться сомнительным, но в любом случае декларативные программы гораздо ближе к формальным спецификациям, чем их "обычные" аналоги.

Вернёмся к уравнению "Алгоритм = Логика + Управление". При программировании на императивном языке, эти две составляющих переплетены и у программиста нет выбора, кроме как вникать в низкоуровневые подробности выполнения программ. В декларативных языках, логика и управление разделены. Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование. Декларативную программу, вообще говоря, проще написать и, что немаловажно, легче понять, чем соответствующую императивную программу. Кроме того, возникает возможность передачи ответственности за создание управления компьютеру. Часто наличие наиболее эффективного алгоритма не настолько уж важно и можно удовлетвориться разумно эффективным алгоритмом, который находит сама система. Более того, появляются интересные возможности использовать нетривиальные алгоритмы управления, такие как недерминированные, "ленивые" и параллельные вычисления.

Многие практически важные задачи требуют огромного количества вычислений и очевидный путь обеспечения требуемой вычислительной мощности - использование параллельных компьютеров. Но автоматическое распараллеливание последовательных программ очень редко обеспечивает достижение приемлемого уровня параллелизма. Программа на императивном языке "переопределена". Она устанавливает определенный порядок вычислений, часто не связанный с решением задачи. Векторизующий компилятор пытается ретроспективно обнаружить параллелизм первоначально присущий задаче, но сделать это очень сложно, а часто и невозможно. В конечном счете, компилятор, который находит возможности для параллелизма, только избавляется от переопределенности присущей последовательным языкам. В связи с этим возник класс параллельных языков программирования, которые имеют явные средства для выражения параллелизма. Но программировать на таких языках гораздо труднее, чем на последовательных - человеку гораздо легче понять статические соответствия, чем осознать протекающий во времени процесс и совсем уж трудно наглядно представить совокупность одновременно протекающих процессов.

Декларативные языки хорошо подходят для программирования параллельных компьютеров. Они не требуют специальных методов описания параллелизма. Параллелизм программы определяется неявно её информационными связями. Другими словами, работает ли программа на последовательном или параллельном компьютере, программисту безразлично. Чем более декларативен язык программирования, тем более вероятно наличие неявного параллелизма и тем проще будет параллельное выполнение программы. Такое неявное использование параллелизма очень удобно для программиста, поскольку для него не возникает дополнительных трудностей сверх тех, которые присутствуют в программе для последовательного компьютера. Но сама система должна быть достаточно "разумна", чтобы найти наиболее эффективный способ выполнения программы. Это очень трудная задача, но некоторые положительные результаты уже достигнуты и можно надеяться, что в ближайшем будущем станет возможно эффективно выполнить декларативные программы на параллельных компьютерах "прозрачно" для программиста.

Ещё одно достоинство декларативных языков - пригодность для формальных рассуждений. Известно, что тестирование позволяет обнаружить ошибки, но не может гарантировать их отсутствия. Единственный способ убедиться в правильности программы - проанализировать её код. К сожалению, существующие методы формального анализа программ чрезвычайно трудоёмки. Дело в том, что широко используемые языки типа Си имеют очень сложную и запутанную семантику. Это означает, что очень трудно формально (и даже неформально) рассуждать о программах на таких языках. Много усилий было направлено на создание более простых и строгих языков, а также на совершенствование методов анализа, но результаты не обнадёживают. Применение формальных методов остаётся очень дорогостоящим и ограничивается теми областями, где надёжность программного обеспечения критична.

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

После панегириков декларативному программированию, стоит упомянуть и свойственные этому подходу

недостатки.

- А на той планете есть охотники?
- Нет.
- Как интересно! А куры там есть?
- Нет.
- Нет в мире совершенства! - Вздохнул лис.

Антуан де Сент-Экзюпери "Маленький принц".

Существующие формы декларативного программирования плохо справляются с временными аспектами многих задач. Для приложений, которые активно взаимодействуют с пользователями или внешними процессами декларативных средств часто оказываются недостаточно и программистам приходится применять довольно специфические методы, нарушающие декларативность программ.
Часто утверждают, что декларативные языки не подходят для параллельного программирования. При этом под "параллельным программированием" подразумевается не распараллеливание вычислений, а задача в некотором смысле противоположная - адекватно выразить в программе естественный параллелизм задачи. То есть речь идёт опять же о временных аспектах.

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

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

Пока же на практике предпочитают включать в декларативные языки программирования императивные свойства. Такой подход не лишён смысла. В конце концов, не зря же существуют повелительные предложения и, если мы хотим, чтобы что-то произошло, проще всего сказать "сделай это". Но прямолинейное добавление императивных операторов часто перечёркивает многие достоинства декларативных языков. Объединение различных парадигм в рамках одного языка, требует тщательной проработки. К сожалению, долгое время создатели функциональных и логических языков недостаточно серьёзно относились к идее декларативности и в результате практические программы на Прологе или Лиспе ненамного легче анализировать, чем даже программы на Си.

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


  1. R. A. Kowalski Algorithm = Logic + Control. CACM 22(7), 1979
  2. J. A. Robinson : Editor's Introduction. Journal of Logic Programming Vol.1 1984
  3. J. W. Lloyd Practical Advantages of Declarative Programming. Proceedings of the 1994 Joint Conference on Declarative Programming.
  4. D.A. Turner Programs as executable specifications. In C. A. R. Hoare and J. C. Shepherdson, Mathematical Logic and Programming Languages, 1985.

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]