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

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

2. История.

Истоки декларативного программирования лежат в математике и логике, точнее в синтезе этих наук именуемом математической логикой.

Фактически современную математическую логику основал Готлоб Фреге. В 1899 г. он придумал Begriffsschrift ("исчисление понятий" или "система обозначения понятий") [Frege]. Это был самый значительный шаг в логике со времён Аристотеля. Формальна система Фреге позволила логикам разработать строгое определение доказательства. Кроме того, Фреге был первым, кто серьёзно отнёсся к идее применения функций к сущностям отличным от чисел (и в частности к другим функциям).

С начала XX века математическая логика - объект пристального внимания математиков. Для информатики большое значение имеет работа Жака Эрбрана [Herbrand], в которой он предложил несколько версий процедуры доказательства теорем в логике первого порядка.

В 1920 г. советский математик Моисей Шёнфинкель в своем сообщении "О строительных камнях математической логики" [Schonfinkel] провозгласил новые тенденции в основаниях математики. Сущностью новой концепции был вычислительный (или алгоритмический) подход к понятию функции, в отличие от традиционного её определения как множества пар вида (аргумент, значение). В некотором смысле это был возврат к представлениям математиков XVIII века, но на новом уровне строгости. Шёнфинкель рассматривал функции как композиции базовых "комбинаторов" и пытался найти минимальный набор таких комбинаторов, пригодный для определения любой функции. Исчисление комбинаторов было независимо разработано и глубоко исследовано Хаскелем Карри и получило наименование "комбинаторной логики". Появились и другие формализмы, такие как "лямбда-исчисление" Алонзо Чёрча, ставшее основой многих языков функционального программирования и теория рекурсивных функций.

Собственно история начиняется в 1958 году, когда Джон Маккарти изобрел язык Лисп [McCarthy] (LISP - LISt Processing) первый в мире функциональный язык программирования. В каком-то смысле Лисп - функциональный эквивалент Фортрана. В течение некоторого времени Лисп, и Фортран были единственными широко доступными языками программирования (кроме ассемблерных языков). Как "первый блин" Лисп обладал рядом недостатков. Самый заметный из них - громоздкий синтаксис.
Например, определение факториала:

        (define fac (n)
            (if (eq n (quote 0))
                (quote 1)
                (mul n (fac (sub n (quote 1))))))

Это обилие скобок дало повод некоторым острословам утверждать, что LISP в действительности означает "Lots of Infuriating, Stupid Parenthesis". Изначально такую запись предполагалось использовать только для данных и как промежуточное представление, а для программ применять другую нотацию, что-то вроде:

        fac[n] = [eq[n ; 0] -> 1;
               T -> mul[n; fac[n - 1]]]

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

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

Можно перечислять и другие недостатки Лиспа. И всё же немногие языки могут сравниться с ним по количеству новых идей привнесённых в программирование. И, пожалуй, главная из них - язык программирования вовсе не обязан отражать особенности вычислительной машины.

Несколько отвлекаясь от темы. С Лиспом связаны многие нововведения, ставшие ныне привычными: полноэкранные редакторы, и многооконный графический интерфейс, символические отладчики и инспекторы данных, инкрементные компиляторы и диалоговые системы программирования не говоря уж об автоматическом управлении памятью и "уборке мусора". Common Lisp - первый стандартизированный язык объектно-ориентированного программирования. Что же касается декларативного (и в частности функционального) программирования, Лисп по мере развития удалялся от него, обзаведясь полным набором императивных инструментов вплоть до таких маргинальных, как go.

В 1964 г. Питер Ландин продемонстрировал связь языков программирования, в том числе Лиспа и Алгола с лямбда-исчислением, придумал абстрактную машину для вычисления лямбда-выражений "SECD-машину"  [Landin64]. С тех пор варианты этой машины часто использовались для реализации функциональных языков.

В 1966 г. Ландин предложил язык ISWIM (If you See What I Mean) [Landin66], который сыграл роль Алгола в функциональном программировании. Он не использовался как промышленный язык, но послужил прототипом для всех "современных" функциональных языков. ISWIM создавался как лямбда-исчисление с более привычным синтаксисом (привычным, по крайней мере, для тех, кто читает математические тексты). Именно Ландин ввёл в обиход термин "синтаксический сахар". Среди нововведений - инфиксные операции, локальные определения (let- и where- выражения) использование отступов для определения структуры программы. Факториал на ISWIM выглядит вполне современно.

        rec fac(n) = (n = 0) -> 1 ; n fac(n-1)

В 1963 г. Джон Алан Робинсон [Robinson] реализовал метод автоматического доказательства теорем, получивший название "принцип резолюции". Идея этого метода принадлежит Эрбрану, но поскольку тот не думал о применении своего метода на компьютерах (что не удивительно в 1930 г.), он оказался не очень подходящим с вычислительной точки зрения. Робинсон сделал его пригодным для реального применения и разработал эффективный алгоритм унификации, являющийся основой метода.

В 1971 г Ален Колмероэ положил резолюцию в основу Пролога (PROLOG - PROgrammation en LOGique) [Colmerauer] - первого языка логического программирования. Чтобы добиться приемлемой эффективности и избежать "комбинаторных взрывов" на язык были наложены существенные ограничения. Роберт Ковальский показал [Kowalski], что эти ограничения эквивалентны использованию известного подмножества логики предикатов, так называемых хорновских дизъюнктов [Horn] и таким образом подвёл теоретический фундамент под Пролог. Именно процедурная интерпретация логических предложений, предложенная Ковальским, даёт основания говорить о Прологе как о первом логическом языке, несмотря на то, что ранее уже существовали системы, основанные на логике, такие как Absys Майкла Фостера и Теда Элкока [Elcock, Foster] и ПРИЗ Энна Тыугу [Тыугу]. Интересно что, работая над Лиспом, Маккарти также пытался создать логический язык, но отсутствие эффективных алгоритмов вывода не позволило ему сделать это.

В 1976 г. Девидом Уорреном создана реализация Пролога, известная как Edinburgh Prolog [Warren]. Компилятор Уоррена продемонстрировал эффективность не хуже, чем лучшие существующие в то время реализации Лиспа и вызвал интерес к Прологу как к реальному языку программирования. Программы на Прологе компилировались в команды специально разработанной виртуальной машины, получившей название WAM (Warren's Abstract Machine). В этой реализации Пролог обрёл свой привычный вид. На долгое время Edinburgh Prolog стал стандартом де-факто для Пролога.

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

Определение факториала на Прологе

        fac(0, 1).
        fac(N, M):-  sub(N, 1, N1), fac(N1,M1), mul(N, M1, M).

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

В 1976 г. Петер Хендерсон и Джеймс Моррис реализовали диалект Лиспа Lispkit [Henderson], в котором впервые использовались ленивые вычисления - важная концепция современного функционального программирования. Собственно ленивые вычисления были введены ещё в Алголе-60 как следствие передачи параметров по имени, но там они воспринимались как ошибка создателей языка и никогда не реализовывались в полном объеме. Действительно, такая схема вычислений противоречит принципу императивного программирования - явному описанию последовательности вычислений.

Значительное влияние на популяризацию функционального программирования оказала лекция Джона Бекуса и его статья [Backus]. В 1977 г. Бекус получает премию Тьюринга, прежде всего за участие в создании Фортрана и Алгола. В своей лекции он обрушивается с критикой на императивные языки, за то, что они вынуждают программиста сосредоточится на операциях с памятью компьютера, а не на проблеме, которую надо решить и за то, что они не обладают полезными математическими свойствами для рассуждений о программах. Достаётся и лямбда-исчислению. Бекус сравнивает его с использованием произвольных передач управления в императивных языках. Взамен он предлагает системы программирования, основанные на "функциональных формах" (то есть функциях высшего порядка или комбинаторах), которые выражают общие образцы вычислений. Функции высшего порядка - важна особенность современных функциональных языков программирования, но другие предложения Бекуса широкого признания не получили. Программирование без переменных - не лёгкое занятие и требуются некоторые усилия, чтобы понять определение факториала на FP.

        def fac = eq o [id , 0] -> 1 ; x o [id , fac o - o [id , 1]]

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

ML (Meta Language, изначальное предназначение- метаязык для системы доказательств) [Gordon] очень похож на ISWIM, но имел важную особенность: полиморфную систему типов данных разработанную Робином Милнером [Milner]. Подобная система была раньше предложена Роджером Хиндли [Hindley] и сейчас часто называется системой типов Хиндли-Милнера. Наличие механизма вывода типов позволило избавить программиста от необходимости явно описывать типы функций и в то же время производить строгий контроль типов.
ML не чисто функциональный язык, он включает и императивные инструкции. С тех пор ML развивался и включил в себя многие особенности других функциональных языков. Появилось несколько диалектов, наиболее известные из которых Standard ML [Harper], CAML [Cousineau] и чисто функциональный Lazy ML [Augustsson].

Факториал на ML:

        fun fac(n) = if n = 0 then 1 else n * fac(n-1);

Другой язык, Hope [Burstall], использует подобную систему типов, но требует явных объявлений типов. Важные нововведения - алгебраические определения типов и сопоставление с образцом - разновидность унификации.
Факториал на Hope:

        dec fac : num -> num;
        --- fac(0) <= 1;
        --- fac(n) <= n*fac(n-1);

В 1985 г. Дэвид Тёрнер объединил в одном языке Miranda [Turner] многие важные особенности функциональных языков (функции высшего порядка, ленивые вычисления, алгебраические типы данных, параметрический полиморфизм, сопоставление с образцом). Введены удобные конструкторы списков (ZF-выражения), позаимствованные из другого языка Тёрнера KRC.
Факториал на Миранде можно выразить, например, так:

        fac n
            = 1, if n = 0
        = n * fac (n - 1), otherwise

        fac 0 = 1
        fac n = n * fac (n-1)

        fac n  = product [1..n]

Тёрнер запатентовал свой язык (Miranda^TM - торговая марка Research Software, Ltd), что замедлило его развитие и распространение. На основе Миранды было создано много языков, в том числе и популярные ныне Haskell [!] и Clean.

В 1981 г. стартует японский проект "вычислительных систем следующего поколения", который вызвал взрыв интереса к логическому программированию. Пролог входит в число самых популярных языков. Появляются реализации для всех распространенных компьютеров. Начинаются исследования по параллельным логическим языкам, таким как Parlog, Concurent Prolog, GHC.

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

Часто можно слышать о крахе японского проекта. На самом деле технические задачи были выполнены - созданы мощные параллельные компьютеры и соответствующие им языки программирования. Но оказалось, что потребность в них невелика. Та область исследований ("искусственный интеллект"), с которой обычно связывалась с применением Лиспа и Пролога попала в очередной кризис. Сказался и общий спад в экономике. Примерно в это же время обанкротились и американские компании, выпускавшие Лисп-машины по $70000.

Положение начало изменятся в последнее время. Производительность компьютеров давно перестала быть проблемой, сложность решаемых задач возрастает, а эйфория ООП постепенно утихает. Кроме того, значительные успехи были достигнуты в технике реализации. Успело сложиться мнение, что декларативные языки "принципиально неэффективны". Но, применяя методы глобального анализа программ, создатели систем Aquarius Prolog [VanRoy] и Parma [Taylor] смогли вплотную приблизился к лучшим компиляторам императивных языков. Маленькой сенсацией стал компилятор для функционального языка Sisal [Feo, Cann], ориентированного на численные расчёты, созданный в американском ядерном исследовательском центре (Lawrence Livermore National Laboratory). Он превзошёл не только Си, но и Фортран, бывший в этой области вне конкуренции.

Другие направления исследований в последнее десятилетие:

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

1. [Frege] Frege G. Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. 1879
2. [Schonfinkel] Schonfinkel M. Ueber die Bausteine der mathematischen Logik. Mathematische Annalen, 1924.
3. [Herbrand] Herbrand J. Une methode de demonstration. Thesis, 1931
4. [Horn] Horn A. On sentences which are true of direct unions of algebras. Journal of Symbolic Logic, 1951.
5. [McCarthy] McCarthy J. Recursive functions of symbolic expressions and their computation by machine. CACM 3(4), 1960
6. [Landin64] Landin P. The Mechanical evaluation of Expressions. Computer Journal v.6, 1964
7. [Landin66] Landin P. The next 700 programming languages. CACM 9(3) 1966. ( 1,2MB pdf )
8. [Robinson] Robinson A. J. A machine oriented logic based on the resolution principle. Journal of the ACM vol 12 1965. [перевод: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции. Кибернетический сборник вып.7, 1970.]
9. [Hindley] Hindley R. The principle type scheme of an object in combinatory logic. Transactions AMS 146, 1969
10. [Elcock] Elcock, E.W. Descriptions. In Machine Intelligence. vol. 3, Edinburgh, 1968.
11. [Foster] Foster, J.M. Assertions: Programs written without specifying unnecessary order. ibid.
12. [Тыугу] Тыугу Э. Х. Решение задач на вычислительных моделях. - Ж. вычис. матем. и матем. физизики. 1970
13. [Colmerauer] Colmerauer A., Kanoui H., Pasero R., Roussel P. Un Systeme de Comunication Homme-machine en Francais. Universite d'Aix Marseille, 1973
14. [Kowalski] Kowalski R. Predicate Logic as Programming Language. IFIP Congress, 1974
15. [Warren] Warren D. Implementing Prolog - compiling logic program. Edinburgh, 1977.
16. [Henderson] Henderson P., Morris J.H. A Lazy Evaluator. Conference Record of the Third ACM symposium on Principles of Programming Languages 1976
17. [Backus] Backus J. Can Programming be Liberated from the von Neumann style? A functional style and its Algebra of Programs. CACM 21(8), 1978 ( 3MB pdf)
18. [Milner] Milner R. A theory of type polymorphism in programming. Journal of Computer and System Science 17(3), 1978.
19. [Gordon] Gordon M. J., Milner R., Wadsworth C.P. A metalanguage for interactive proof in LCF. Conference Record of the 5th Annual ACM Symposium on Principles of Programming Languages.1978
20. [Burstall] Burstall R., MacQueen D., Sannella D. Hope: an experimental applicative language. Proceedings First LISP Conference, 1980.
21. [Augustsson] Augustsson L. A compiler for Lazy ML. Proceedings 1984 ACM Conference on LISP and Functional Programming, 1984
22. [Harper] Harper R., MacQueen D., Milner R. Standard ML. Technical Report, University of Edinburgh, 1986.
23. [Cousineau] Cousineau G. Huet G. The CAML primer. Technical Report, INRIA,1990
24. [Turner] Turner D. Miranda : A non-strict functional language with polymorphic types Proceedings, Functional Programming Languages and Computer Architecture, 1985
25. [Feo] Feo J. T et al. A Report on the SISAL Language Project. 1990.
26. [Cann] Cann D. Retire FORTRAN? A debate rekindled. CACM 35(8), 1992.
27. [Taylor] Taylor A. LIPS on a MIPS: Results from a Prolog Compiler for a RISC. In ICLP, 1990.
28. [VanRoy] Van Roy P. Can Logic Programming Execute as Fast as Imperative Programming?

[!] Для тех, кого ещё не достали факториалы имеется замечательная коллекция на Haskell.

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