Декларативные языки программирования - История декларативных языков

Декларативные Языки Программирования

История декларативных языков

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

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

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

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

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

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

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

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

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

В 1976 г. Девидом Уорреном создана реализация Пролога, известная как Edinburgh Prolog. Компилятор Уоррена продемонстрировал эффективность не хуже, чем лучшие существующие в то время реализации Лиспа и вызвал интерес к Прологу как к реальному языку программирования. Программы на Прологе компилировались в команды специально разработанной виртуальной машины, получившей название 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 , в котором впервые использовались ленивые вычисления - важная концепция современного функционального программирования. Собственно ленивые вычисления были введены ещё в Алголе-60 как следствие передачи параметров по имени, но там они воспринимались как ошибка создателей языка и никогда не реализовывались в полном объеме. Действительно, такая схема вычислений противоречит принципу императивного программирования - явному описанию последовательности вычислений.

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

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

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

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

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

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

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

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

иллюстрирует эту последнюю особенность языка.

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

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

или, используя сопоставления, так:

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

и даже вот так (с использованием ZF-выражений):

        fac n  = product [1..n]

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

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

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

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

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

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

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

Вверх