Мечта о декларативном программировании [закрыто]

Почему мечта о декларативном программировании не осуществилась? Какие конкретные препятствия мешают? Для простого примера, почему я не могу сказать

sort(A) is defined by sort(A) in perm(A) && asc(sort(A))

и автоматически получить алгоритм сортировки из него. permозначает перестановки и ascозначает возрастание.

Есть несколько очень хороших ответов. Я постараюсь внести свой вклад в обсуждение.

На тему декларативного, логического программирования в Прологе есть замечательная книга Ричарда О'Кифа «Ремесло Пролога» . Речь идет о написании эффективных программ с использованием языка программирования, который позволяет писать очень неэффективные программы. В этой книге, обсуждая эффективные реализации нескольких алгоритмов (в главе «Методы программирования»), автор придерживается следующего подхода:

• определить проблему на английском языке
• написать рабочее решение, как можно более декларативное; обычно это в значительной степени означает именно то, что у вас есть в вашем вопросе, просто исправьте Пролог
• оттуда, предпримите шаги, чтобы усовершенствовать реализацию, чтобы сделать это быстрее

Самое поучительное (для меня) наблюдение, которое я смог сделать, работая над этим:

Да, окончательная версия реализации намного эффективнее, чем «декларативная» спецификация, с которой начинал автор. Это все еще очень декларативно, кратко, и легко понять. Между тем произошло то, что окончательное решение улавливает свойства проблемы, о которой первоначальное решение было не замечено.

Другими словами, при реализации решения мы использовали как можно больше наших знаний о проблеме. Для сравнения:

Найти перестановку списка таким образом, чтобы все элементы были в порядке возрастания

чтобы:

Объединение двух отсортированных списков приведет к сортировке списка. Поскольку могут быть отсортированные списки, используйте их в качестве отправной точки вместо списков длиной 1.

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

Что касается реального вопроса: как двигаться вперед? Ну, один из способов - предоставить как можно больше знаний о проблеме, которую мы объявляем компьютеру.

Лучшая попытка, которую я знаю, чтобы действительно решить эту проблему, представлена ​​в книгах, написанных в соавторстве с Александром Степановым «Элементы программирования» и «От математики к общему программированию» . К сожалению, я не в состоянии подвести итог (или даже полностью понять) все в этих книгах. Однако подход заключается в том, чтобы определить эффективные (или даже оптимальные) библиотечные алгоритмы и структуры данных при условии, что все соответствующие свойства входных данных известны заранее. Окончательный результат:

• Каждое четко определенное преобразование является уточнением уже существующих ограничений (известных свойств);
• Мы позволяем компьютеру решать, какое преобразование является оптимальным, исходя из существующих ограничений.

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

PS

Чтобы дать вам представление о том, что я имею в виду под «уточнением реализации»: возьмем, к примеру, простую задачу получения последнего элемента списка в Прологе. Каноническое декларативное решение состоит в следующем:

last(List, Last) :-
    append(_, [Last], List).

Здесь декларативное значение append/3:

List1AndList2это объединение List1иList2

Так как во втором аргументе append/3у нас есть список только с одним элементом, а первый аргумент игнорируется (подчеркивание), мы получаем разделение исходного списка, который отбрасывает начало списка ( List1в контексте append/3) и требует, чтобы задняя часть ( List2в контексте append/3) действительно является списком только с одним элементом: так, это последний элемент.

Однако фактическая реализация, предоставленная SWI-Prolog , гласит:

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

Это все еще красиво декларативно. Читайте сверху вниз, там написано:

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

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

last(List, Last) :-
    reverse(List, [Last|_]).

Последний элемент списка является первым элементом обращенного списка.

Если вы хотите получить неокончательные дискуссии о том, что является хорошим, декларативным Прологом, просто просмотрите некоторые вопросы и ответы в теге Пролог на переполнении стека .

Логические языки уже делают это. Вы можете определить сортировку так же, как вы делаете это.

Основная проблема - производительность. Компьютеры могут быть хороши в вычислении многих вещей, но они по своей природе глупы. Каждое «умное» решение, которое может принять компьютер, было запрограммировано в нем программистом. И это решение обычно описывается не тем, как выглядит конечный результат, а тем, как шаг за шагом достичь этого конечного результата.

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

Задача программиста - решить, какой уровень абстракции использовать. Для приложения, которое вы создаете, собираетесь ли вы перейти на более высокий уровень и описать его абстрактно и понизить производительность или понизить ее, потратить на нее в 10 раз больше времени, но получить алгоритм, который в 1000 раз эффективнее?

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

• HTML объявляет содержание веб-страницы.

• CSS объявляет, как должны выглядеть различные типы элементов на веб-странице.

• Каждая реляционная база данных имеет язык определения данных, который объявляет структуру базы данных.

• SQL гораздо ближе к декларативному, чем к императивному, поскольку вы сообщаете ему, что хотите видеть, и планировщик запросов базы данных выясняет, как на самом деле это сделать.

• Можно утверждать, что большинство файлов конфигурации (.vimrc, .profile, .bashrc, .gitconfig) используют домен-специфический язык, который в значительной степени декларативен.

Абстракции дырявые

Вы можете реализовать декларативную систему, в которой вы объявляете, что хотите, а компилятор или интерпретатор определяет порядок выполнения. Теоретическое преимущество заключается в том, что это освобождает вас от необходимости думать о том, «как», и вам не нужно подробно описывать эту реализацию. Однако на практике для вычислений общего назначения вам все еще нужно подумать о «как» и написать всевозможные трюки, помня, как это будет реализовано, поскольку в противном случае компилятор может (и часто будет) выбирать реализацию, которая будет очень, очень, очень медленно (например, n! операций, где n будет достаточно).

В вашем конкретном примере, вы получите A алгоритма сортировки - это не значит , что вы получите хороший или даже несколько полезных один. Ваше заданное определение, если оно реализовано буквально (вероятно, компилятором), приводит к http://en.wikipedia.org/wiki/Bogosort, который непригоден для больших наборов данных - это технически правильно, но для сортировки тысячи чисел требуется вечность ,

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

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

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

Я хотел бы привести пример с некоторыми хорошо известными доменами.

Решение о том, какой класс CSS использовать, требует знания и рассмотрения всех правил CSS. Добавление новых правил может сделать недействительными все другие решения. Негативные CSS-классы намеренно не добавляются в язык из-за проблем с NP-полнотой, но отсутствие негативных классов усложняет решения CSS.

В оптимизаторе запросов (SQL) возникает сложнейшая проблема - решить, в каком порядке присоединиться, какие индексы использовать и какую память выделить для каких временных результатов. Это известная NP-полная проблема, которая усложняет разработку базы данных и формулировку запросов. Чтобы сформулировать это по-другому: при проектировании базы данных или запроса разработчику необходимо знать действия и порядок действий, которые, вероятно, предпримет оптимизатор запросов. Опытный инженер нуждается в знании эвристики, используемой основными поставщиками баз данных.

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

В результате эти сложности застают начинающих врасплох, они нарушают «красоту» декларативного программирования и заставляют некоторых инженеров искать другие решения. Миграция неопытных инженеров с SQL на NoSQL могла быть вызвана сложностями реляционных баз данных.

У нас есть разница в декларативности языков программирования, которая находит хорошее применение при проверке цифровой логики.

Обычно цифровая логика описывается на уровне передачи регистров (RTL), где определяется логический уровень сигналов между регистрами. Чтобы убедиться, что мы все чаще добавляем свойства, определенные более абстрактно и декларативно.

Один из более декларативных языков / подмножеств языка называется PSL для языка спецификации свойств. При тестировании модели множителя RTL, в которой, например, должны быть указаны все логические операции сдвига и сложения в течение нескольких тактов; Вы можете написать свойство в порядке assert that when enable is high, this output will equal the multiplication of these two inputs after no more than 8 clock cycles. Затем описание PSL может быть проверено вместе с RTL в симуляции, или может быть формально доказано, что PSL сохраняется для описания RTL.

Более декларативная модель PSL вынуждает описывать то же поведение, что и описание RTL, но достаточно другим способом, который можно автоматически проверять по RTL, чтобы увидеть, согласны ли они.

В основном проблема в том, как вы моделируете данные; и декларативное программирование здесь не помогает. В императивных языках у вас уже есть тонны библиотек, которые многое для вас делают, так что вам нужно только знать, как звонить. В частности, можно рассмотреть это декларативное программирование (вероятно, лучший пример для этого - Stream API в Java 8 ). Имея это, абстракция уже решена, и декларативное программирование не требуется.

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

Следует отметить, что он применяется для языков программирования общего назначения. Для доменных языков декларативные языки намного лучше; SQL, вероятно, является лучшим примером.

Это выглядело бы примерно так .. {(что угодно => прочитать файл и вызвать URL) | вызывать URL и читать файл} Однако это действия, которые нужно выполнить, и в результате состояние системы изменяется, но это не очевидно из источника.

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

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

Я знаю, это звучит немного странно, но в 2008 году я написал программный генератор, который использует этот метод, и сгенерированный C ++ в 2–15 раз больше исходного кода. Теперь у меня более 75 000 строк C ++ из 20 000 строк ввода. С этим связаны две вещи: последовательность и полнота.

Согласованность: никакие два предиката, которые могут быть истинными в одно и то же время, не могут подразумевать противоречивые действия, такие как x = 8 и x = 9, а также различные следующие состояния.

Полнота: указана логика для каждого перехода состояния. Это может быть трудно проверить для систем с N подсостояниями с> 2 ** N состояниями, но есть интересные комбинаторные методы, которые могут проверить все. В 1962 году я написал фазу 1 системной сортировки для машин 7070, используя этот тип генерации условного кода и комбинаторную отладку. Из 8000 строк такого рода количество ошибок со дня первого выпуска навсегда было равно нулю!

Вторая фаза, 12 000 строк, содержала более 60 ошибок в первые два месяца. Об этом можно сказать гораздо больше, но это работает. Если бы производители автомобилей использовали этот метод для проверки прошивки, мы бы не увидели сбоев, которые мы видим сейчас.

Не все может быть представлено декларативным способом.

Часто вы явно хотите контролировать поток выполнения

Например, следующий псевдокод: if whatever read a file call an URL else call an URL write a file Как бы вы представили его декларативно?

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

Все сводится к тому, что «взаимодействие» с вашей средой / системой не декларативно. Все, что связано с вводом / выводом, является процедурным по сути. Вы должны точно сказать, когда и что должно произойти, и в каком порядке.

Декларативный отлично подходит для всего, что связано исключительно с вычислениями. Как гигантская функция, вы вводите X и получаете Y. Это здорово. Примером этого является HTML, ввод - это текст, вывод - это то, что вы видите в своем браузере.