Декларативное программирование

[ Содержание | 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 И.А. Дехтяренко

3. Инструменты.

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

С точки зрения функционального программирования программа - функция, применяемая к вводу и возвращающая вывод.

        output = program(input)

        program(input, output)

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

Имеется, однако, более серьёзные отличия. Функции в функциональных языках "однонаправлены". Они получают аргументы и возвращают результат. В логических языках разница между вводом и выводом условна. Мы можем указать желаемый вывод и получить ввод, который его обеспечит. Другое важное отличие - недетерминизм логических языков. Результат в них не обязательно определяется однозначно.

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

Функциональная программа	Логическая программа
area(Eurasia) = 55 area(Africa) = 29 area(NorthAmerica) = 20 area(SouthAmerica) = 18 area(Australia) = 7 area(Antarctica) =14	area(Eurasia,55) area(Africa,29) area(NorthAmerica,20) area(SouthAmerica,18) area(Australia,7) area(Antarctica,14)

Теперь к функциональной программе можно обратиться, например, с запросом area(Eurasia) и получить ответ 55.

Запросы к логической программе разнообразнее: area(Eurasia,a) выдаст ответ {a = 55}, а area(m,29) - {m=Africa}. Запрос area(m,a) выдаст любую из шести возможных пар, но, добавляя ограничения, мы можем сузить область допустимых результатов. Возможные ответы на area(m,a),a>20 - {m=Eurasia,a=55}и {m=Africa, a=29}, а на area(m,a),a>20,a<40 получим единственно возможный ответ: {m=Africa, a=29}. Этот по выражению Хоара "ангельский недетерминизм" и составляет главную силу логического программирования.

Предпринимаются попытки объединить эти два стиля. Один из подходов - "функционально-логическое программирование", в котором отношения задаются функциями, но запросы выполняются как в логических языках. То есть допускаются обращения вида area(m) = 20 --> {m = NorthAmerica}.

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

Другая характеристика языка - используемая в нём система типов данных. Вообще, для декларативных языков характерен "декларативный" подход и к организации данных. То есть понятие структуры данных никак не связано с её представлением в памяти компьютера. Напрочь отсутствует такое понятие как указатель. Редко встречаются и массивы. Наиболее распространенные структуры - списки и деревья.

Некоторые языки полностью игнорируют понятие типа данных. Имена переменных в них не связываются по умолчанию с каким-либо типом - все объекты образуют единое универсальное пространство. Такие языки называют бестиповыми, а также "языками с динамической типизацией" или "языками со скрытыми типами". Наиболее радикальны в этом плане Лисп и Пролог. Формы представления программ и данных в них одинаковы - символьные выражения. Это позволяет программе обрабатывать и преобразовывать другие программы и даже саму себя.

Так или иначе, типы возникают естественно, даже в бестиповых языках, когда объекты классифицируются согласно их использованию. Но вот что лучше - считать типы существующими априори или организовывать подмножества объектов из единой области? Этот вопрос остаётся нерешённым, так как отражает (возможно, неразрешимое) противоречие между надежностью и гибкостью языка. Споры о необходимости контроля типов ведутся и сегодня, но практический успех языка часто определяет более или менее успешная попытка найти компромисс. В этом отношении система типов Хиндли-Милнера - один из наиболее интересных примеров. Её разновидности используются во многих функциональных языках.

Еще одно важное свойство языков - поддержка модульности. Ранние языки слабо развиты в этом отношении. Они имеют "плоское" пространство имён в духе Си. Наиболее развита система модулей у SML и OCAML, но многие считают её чересчур сложной. Возможно "золотую середину" представляют Haskell, Mercury и т.п., использующие простой модульный механизм в стиле Модулы-2. Для практических нужд этого вполне достаточно.

Ниже перечислены наиболее популярные декларативные языки и системы программирования, а также некоторые, показавшиеся мне интересными.

Функциональные языки.

Лисп остаётся наиболее широко используемым функциональным языком. За долгую историю своего развития язык Лисп породил множество диалектов. Несмотря на то, что почти все из них носят названия вида "Some Lisp", разница между ними бывает значительной, не меньше, чем между Алголом и Паскалем или между C и C++. Так что правильнее считать их разными языками.

Предпринимались попытки стандартизировать язык. Наиболее известная из них - стандарт ANSI Common Lisp (см. также CLtL2). К сожалению, язык получился слишком сложным. Его описание содержит более 1000 страниц. Доступны как коммерческие ( Allegro, Harlequin, Corman), так и бесплатные ( GnuCL, CLISP, CMUCL) реализации.

ISLISP - очень компактный диалект Лиспа, принятый в качестве международного стандарта (ISO). Доступны реализации OpenLisp , TISL, OKI ISLISP.

EuLisp разрабатывается группой европейских пользователей Лиспа в надежде создать развитую систему программирования, но не такую громоздкую как Common Lisp. Язык всё ещё в стадии разработки, но уже существует несколько реализаций ( EuScheme, Feel, Youtoo) включающие TELOS (The Eulisp Object System - аналог CLOS) .

Scheme - римейк Лиспа, более простой и даже элегантный язык. Активно используется в исследовательских работах и для обучения. Сторонники Scheme любят подчёркивать, что объем "сообщения о языке" ( R⁴RS, R⁵RS ~50 страниц) меньше чем объем указателя к описанию Common Lisp.

Существует более 50 реализаций Scheme (см. список). Некоторые имеют интегрированные среды ( DrScheme, WinScheme48, 3DScheme и EdScheme). Есть довольно эффективные компиляторы ( Gambit, Bigloo).

Для обучения и экспериментов подойдут Scheme48, WinScheme48, XLISP, MzScheme, DrScheme.

Успеху Scheme значительно способствовала книга Абельсона и Сусмана [20]. Это не учебник функционального программирования, но одна из лучших книг по программированию. Очень жаль, что не переводилась на русский.
Функциональное подмножество Лиспа используется в учебнике Хендерсона [2]. На русском издано несколько книг по Лиспу [3,4, 5]. Ему же посвящён курс лекций М.Н Морозова [6].

Erlang интересный язык, разработанный компанией Ericsson. Подобно Лиспу бестиповый, но имеет очень выразительный синтаксис, основанный на сопоставлении с образцом и несколько напоминающий Пролог. Это делает его более легким в освоении. Специфика языка - ориентация на параллельное программирование систем реального времени. Язык включает средства для описания взаимодействующих процессов, близкие к нотации CSP Хоара [19]. Реализация содержит богатую библиотеку и довольно активно развивается.

Два языка из семейства ML: Standard ML и CAML (Categorical Abstract Machine Language). Функциональные языки с "энергичной" стратегией вычислений. Развитая система типов и модулей. Есть и типично императивные средства: присваивания, циклы, обработка исключений. Различия между двумя диалектами в основном синтаксичские.

Standard ML

• Moscow ML - популярный компилятор, созданный на основе CAML Light. Благодаря ему SML стал широко доступным.
• Poly/ML также неплохой инструмент для экспериментов с SML. Предлагается библиотека графического интерфейса, но она пока недостаточно стабильна (по крайней мере Windows версия).
• SML/NJ (Standard ML of New Jersey) - классическая реализация SML. Хорошо оптимизирующий, но довольно громоздкий компилятор.
• MLton обладает примерно теми же достоинствами и недостатками, что и SML/NJ.
• MLj - компилятор в байт-код JavaVM. Реализует подмножество SML и не очень качественно.
• SML.NET - Великий и Ужасный не мог обойти вниманием SML.

Сравнение производительности некоторых систем можно посмотреть здесь.

CAML

• Objective CAML содержит компилятор в байт-код и оптимизирующий компилятор для объектно-ориентированного расширения CAML.
• CAML Light - компилятор в байт-код. В связи с появлением OCAML может считаться устаревшим, но продолжает развиваться. Широко применяется в учебных заведениях, поскольку очень быстр и нетребователен к ресурсам.
• F# - ещё один диалект ML, созданный на основе CAML специально для .NET.

Классическим учебником по SML считается Programming in Standard ML Роберта Харпера. Есть перевод ранней версии книги [7]. Очень краткое сравнение SML vs Ocaml.

Haskell - быстро набирающий популярность язык. Разрабатывается международным комитетом как чисто функциональный "индустриальный" язык программирования. Язык довольно строгий и выразительный, хотя и может показаться и сложным. Главные особенности: строгая функциональность (отсутствуют императивные операторы), ленивые вычисления, полиморфная система типов и классы типов - попытка ввести в функциональное программирование некоторые концепции ООП.

• Hugs интерпетатор Haskell. Для обучения лучше всего выбрать именно его.
• GHC (Glasgow Haskell Compiler) - наиболее эффективный компилятор, но медленный и весьма требователен к ресурсам.
• nhc98 не столь эффективен как ghc, зато предьявляет гораздо меньшие требования к компьютеру.
• HBC похоже заброшен авторами. Включает компилятор с Lazy ML. Самая интересная особенность - библиотека декларативного программирования пользовательских интерфейсов Fudgets. Сейчас она переносится на ghc.
• Mondrian позволяет компилировать код Haskell в MSIL для .NET.

На www.haskell.org есть описание Haskell и учебные материалы. По-русски введение в язык можно найти в лекциях Романа Душкина [8], а описание  Hugs в его же пособии [9].

На основе Haskell создано уже немало языков. В основном это расширения языка параллельными (DFH, GPH, pH, Goffin, Eden) или императивными (Mondrian) средствами. Есть попытки добавить возможности ООП ( O'Haskell) или другими способами повысить выразительность системы типов (PolyP, Cayenne).

Очень похожий на Haskell язык Clean разработан в Неймегенском университете. Эффективный компилятор и неплохая библиотека (в частности графического интерфейса) делают его вполне пригодным для решения реальных задач.

Hope - очень простой язык и в то же время содержит все важные особенности функциональных языков. Широкого применения не имеет, используется для обучения функциональному программированию. На страничке Роса Патерсона ( Hope) можно найти описание языка и исходный текст ленивого интерпретатора. Существует ещё довольно старый и неудобный интерпретатор для DOS ichope. Можно выполнять программы и через WEB интерфейс.

Учебник Филда и Харрисона [1], использующий этот язык - одна из лучших книг по функциональному программированию и, безусловно, лучшая изданная на русском.

Логические языки.

Пролог - практически единственный широко используемый логический язык. Имеется множество реализаций.

• Две коммерческие системы Quintus Prolog и SICStus Prolog сейчас развиваются и поддерживаются SICS (Swedish Institute of Computer Science). Среды разработки с большим набором инструментов и очень обширными библиотеками. Большинство разработчиков используют SICStus.
• Strawberry Prolog хорошо подходит для знакомства с Прологом и создания небольших программ для Windows, но обладает слишком низкой производительностью для серьезных задач.
• SWI Prolog - довольно популярная система, в основном благодаря удобной среде и переносимой библиотеке для создания графического интерфейса.
• B-Prolog - самая быстрая из реализаций, основанных на байт-коде. Включает некоторые расширения: ограничения на конечных доменах CLP(FD) и запоминание результатов (tabling) - техника известная в функциональном программировании как мемоизация (memoiazation).
• XSB - развитие некогда популярного Stony Brook Prolog. Также поддерживает tabling. Интересная особенность - возможность использования языка второго порядка HiLog.
• GNU Prolog - компилятор в двоичный код. По скорости совсем немного уступает SICStus.

Книга Стерлинга и Шапиро [12] - лучший учебник по Прологу и отличное введение в логическое программирование. Представление о языке можно получить из курса лекций М.Н Морозова [16]. Теории логического программирования посвящены [10] и [11].

Visual Prolog - продукт датской фирмы Prolog Development Center. Ранее распространялся под названием Turbo Prolog (Borland) и PDC Prolog. Несмотря на своё название это - не реализация Пролога, а совершенно особенный язык со строгим контролем типов. К сожалению, отсутствие полиморфизма делает систему типов маловыразительной. В последних версиях появилась поддержка ООП.

Книги по Турбо-Прологу [17, 18] безнадёжно устарели, но полезную информацию можно получить на сайте фирмы Пролог-Софт.

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

Godel - экспериментальный логический язык со строгим контролем типов. Попытка создать декларативную альтернативу Прологу. Значительное внимание уделено средствам метапрограммирования. Замечательное средство для изучения логического программирования. К сожалению, поддержки для Windows нет и не планируется.

"Мультипарадигматические" языки.

Curry - функционально-логический язык, созданный на основе Haskell. Наследует большинство его свойств, но добавляет логические особенности. Всё ещё в стадии разработки.

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

Oz - попытка объединить главные особенности различных парадигм в рамках одного языка. Он включает классы, наследование, активные объекты, функции высшего порядка, недетерминированные вычисления. В настоящее время несколько исследовательских групп объединились в разработке среды программирования Mozart .

Poplog - пример объедининения разных парадигм путём создания многоязычной среды программирования. Включает компиляторы языков Pop-11, Common Lisp, Standard ML и Prolog.

Литература

1. Филд А., Харрисон П. Функциональное программирование. М., Мир, 1993.
2. Хендерсон П. Функциональное программирование. Применение и реализация. М., Мир, 1983.
3. Маурер У. Введение в программирование на языке Лисп. - М.: Мир, 1976.
4. Лавров С., Силагадзе Г. Автоматическая обработка данных. Язык Лисп и его реализация. - М.: Наука, 1978.
5. Хювенен Э., Сеппянен Й. Мир Лиспа. В 2-х т. - М.: Мир, 1990.
6. Морозов М.Н. Функциональное программирование - курс лекций (700Kzip).
7. Харпер Р. Введение в Стандартный ML. ( pdf ps)
8. Душкин Р.В. Лекции по функциональному программированию. (в формате doc)
9. Душкин Р.В. Лабораторный практикум по функциональному программированию.( в формате doc)
10. Ковальски Р. Логика в решении проблем. М.:Наука,1990.
11. Хоггер К. Введение в логическое программирование. - М.: Мир, 1988.
12. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. - М.: Мир, 1990.
13. Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.
14. Братко И. Программирование на языке Пролог для искусственного интеллекта. - М.: Мир, 1990.
15. Малпас Дж. Реляционный язык Пролог и его применение. - Новосибирск: Наука,1990
16. Морозов М.Н. Логическое программирование - курс лекций .
17. Ин Ц., Соломон Д. Использование Турбо-Пролога. - М.: Мир, 1993.
18. Янсон А. Турбо-Пролог в сжатом изложении. - М.: Мир, 1991.
19. Хоар Ч. Взаимодействующие последовательные процессы. - М.: Мир, 1989.
20. Abelson H., Sussman G. Structure and Interpretation of Computer Programs. - MIT Press, Boston, 1986.

[ Содержание | 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 | Литература ]